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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity on the ball). For every
Assumption 2 (Spherical perturbations and Lipschitz
utilities). The perturbation law
For an ordered query
After the allotted calls, the algorithm must return
Proved result
OracleTemplate.NonConvergence LongTails.Setups.SphericalRandomUtility.spec
LongTails.Theorems.SphericalPreferenceLowerBound.budgetRelevant 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:
adaptive same-sample paired-value calls for expected gap , where is universal. On the Gaussian linear hard instances, bounds the root-mean-square sample slope norm. Taking 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:
adaptive binary comparisons for expected gap , where is the objective Lipschitz bound, , and is universal. On the radius- ball, and give admissible instances and comparisons.