← All setups

Spherical Preference Lower Bound — Spherical Random Utility Comparisons

Descriptions may be stale. Consult the linked Lean sources.

Spherical Random Utility Comparisons · Lean proof

Spherical Random Utility Comparisons

We minimize a function f:Rd→R that is convex on the closed Euclidean ball K of radius R>0 centered at the origin, where d≥2. For each ordered pair in K, the oracle independently draws a spherically symmetric vector Z from a common law and reports whether the first point has at least as large a utility uZ(x)=f(x)+⟨Z,x⟩ as the second. With probability at least 1/2, uZ is B-Lipschitz on K, where B>0. The goal is a feasible output with integrable objective gap and expected gap at most ε, for 0<ε≤BR/16.

The optimization problem is minx∈Kf(x),K={x∈Rd:∥x∥2≤R}. The algorithm receives the integer dimension d, the radius R, the bound B, and the tolerance ε.

Our assumptions:

Assumption 1 (Convexity on the ball). For every x,y∈K and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Spherical perturbations and Lipschitz utilities). The perturbation law μ is a probability measure on Rd. For every orthogonal transformation U and every Borel set A⊆Rd, it satisfies μ(U−1A)=μ(A). Define the set of perturbations G={z∈Rd:|uz(x)−uz(y)|≤B∥x−y∥2 for all x,y∈K}. Then μ(G)≥1/2.

For an ordered query (x,y)∈K×K, the comparison bit is c(x,y,z)=1{uz(y)≤uz(x)}. The map c is jointly measurable on K×K×Rd. On call k, the oracle returns c(x,y,Zk), where the Zk are independent random vectors with law μ and the entire sequence is independent of the algorithm’s randomness.

After the allotted calls, the algorithm must return x¯∈K. There must exist a minimizer x⋆∈argminx∈Kf(x) for which the gap f(x¯)−f(x⋆) is integrable and E[f(x¯)−f(x⋆)]≤ε, where the expectation is over the algorithm’s randomness and the oracle perturbations.

Proved result

⌊d⋅(B⋅Rε)2524288⌋+

OracleTemplate.NonConvergence LongTails.Setups.SphericalRandomUtility.spec
  LongTails.Theorems.SphericalPreferenceLowerBound.budget

Relevant previous results

  • John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods. 2012. Complexity: Ω(dG2R2/ε2) adaptive same-sample paired-value calls for expected gap ε<cGR, where c>0 is universal. On the Gaussian linear hard instances, G bounds the root-mean-square sample slope norm. Taking G=B/2 ensures the required half-mass condition, and each value pair yields its comparison bit.
  • Evgeniy Kovalev, Fedor Stonyakin, and Alexander Gasnikov. Nonsmooth Convex and Strongly Convex Optimization from Noisy Comparisons. 2026 (arXiv v1). Complexity: Ω(d2σ2R2/ε2) adaptive binary comparisons for expected gap ε<cMR, where M is the objective Lipschitz bound, Z∼N(0,σ2Id), and c>0 is universal. On the radius-R ball, M=B/2 and σ=B/(22d) give admissible instances and Ω(dB2R2/ε2) comparisons.