Spherical Random Utility Comparisons
Descriptions may be stale. Consult the linked Lean sources.
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
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) SphericalPreferenceDescent
(Ours) |
Upper bound (sufficient) |
||
| (2) SphericalPreferenceLowerBound (Ours) (review) | Lower bound (necessary) |
||
| (3) (Kovalev et al. 2026, Thm. 2(a)) Gaussian probit, convex | Upper bound (sufficient) |
(1): Unknown spherical
laws, including atoms and infinite means. No |
(1) needs a fixed horizon
and a single envelope |
| (4) (Kovalev et al. 2026, Thm. 2(a)) Gaussian probit, strongly convex | Upper bound (sufficient) |
(1) also covers nonsmooth convex objectives without positive curvature or Gaussian noise. | (1) retains |
| (5) (Kovalev et al. 2026, Thm. 2(b)) Gaussian probit on the ball | Lower bound (necessary) |
(2) formalizes the same
order and extends it to |
(2) has a roughly |
| (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 |
|
| (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: