← All setups

Spherical Random Utility Comparisons

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Let f be convex on the closed Euclidean ball Q of radius R>0 centered at zero in dimension d≥2. Each query (x,y)∈Q2 uses one fresh IID draw Z from an unknown spherically symmetric law and returns the jointly measurable bit 1{uZ(x)≥uZ(y)}, where uZ(x)=f(x)+⟨Z,x⟩. With probability at least 1/2, uZ is B-Lipschitz throughout Q. For B>0 and 0<ε≤BR/16, the target is a feasible x^ with integrable gap and E[f(x^)−minQf]≤ε.

Sufficient and necessary comparison budgets for spherical random utility.
Result Oracle complexity Novelty Limitations
(1) SphericalPreferenceDescent (Ours) (⋆⋆⋆) (review) Upper bound (sufficient)
O(d(BR/ε)2)
(2) SphericalPreferenceLowerBound (Ours) (review) Lower bound (necessary)
Ω(d(BR/ε)2) for randomized adaptive algorithms
(3) (Kovalev et al. 2026, Thm. 2(a)) Gaussian probit, convex Upper bound (sufficient)
O(1+(CdσR/ε)2)
(1): Unknown spherical laws, including atoms and infinite means. No M, σ or link calibration. On the Gaussian ball, take B=M+σd. Matches (3) for σ≥M. For t=M/σ>1, the budget improves by a factor ≳t2min{d,t2}. At t=d, (1) costs O(d(MR/ε)2) versus at least order d3(MR/ε)2 in (3)’s budget. (1) needs a fixed horizon and a single envelope B. It covers balls only. (3) is anytime on convex bodies between concentric balls.
(4) (Kovalev et al. 2026, Thm. 2(a)) Gaussian probit, strongly convex Upper bound (sufficient)
O(1+min{(CdσRε)2,Cd2σ2με})
(1) also covers nonsmooth convex objectives without positive curvature or Gaussian noise. (1) retains ε−2 dependence when 0<μ≤M/(8R), where (4) also gives an ε−1 bound.
(5) (Kovalev et al. 2026, Thm. 2(b)) Gaussian probit on the ball Lower bound (necessary)
Ω(d(BR/ε)2) for ε<BR/200, with M=B/2, σ=B/(4d)
(2) formalizes the same order and extends it to BR/200≤ε≤BR/16, giving Ω(d) throughout that band for d≥2048. The full spherical class has matching upper and lower orders in (1), (2). (2) has a roughly 3.3 times smaller lower-bound coefficient for ε<BR/200.
(6) (Lu et al. 2026, Thm. 2) Online dueling No comparable expected-gap budget (1), (6): Rates are not comparable. (6) bounds query regret using an objective-gap link with known slope at zero. (1) compares utility differences whose noise scales with ∥x−y∥.
(7) (Saha et al. 2021) Noisy dueling No comparable spherical-noise budget (1), (7): Rates are not comparable under general spherical noise. (7) assumes smoothness and a constant probability of reversing the true preference.

Abbr: M is a Lipschitz bound for f, σ>0 the Gaussian standard deviation per coordinate, and μ the strong convexity modulus. C=C(M/σ) is the probit factor in Appendix B.1 of the paper cited in (3), with C(t)≥max{1,t2}.

Kovalev, Evgeniy, Fedor Stonyakin, and Alexander Gasnikov. 2026. Nonsmooth Convex and Strongly Convex Optimization from Noisy Comparisons. https://doi.org/10.48550/arXiv.2611.19611.
Lu, Yiyang, Hareshkumar Jadav, Mohammad Pedramfar, Ranveer Singh, and Vaneet Aggarwal. 2026. Online Convex Optimization with Dueling Feedback. https://doi.org/10.48550/arXiv.2608.15050.
Saha, Aadirupa, Tomer Koren, and Yishay Mansour. 2021. “Dueling Convex Optimization.” Proceedings of the 38th International Conference on Machine Learning, Proceedings of machine learning research, vol. 139: 9245–54. https://proceedings.mlr.press/v139/saha21b.html.

Lean setup