Spherical Preference Descent — 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 that is
convex on the closed Euclidean ball of radius centered at the origin, where
. For each ordered pair in
, the oracle independently draws a
spherically symmetric vector from
a common law and reports whether the first point has at least as large a
utility as the second. With probability at least , is -Lipschitz on , where . The goal is a feasible output
with integrable objective gap and expected gap at most , for .
The optimization problem is The algorithm
receives the integer dimension ,
the radius , the bound , and the tolerance .
Our assumptions:
Assumption 1 (Convexity on the ball). For every
and ,
Assumption 2 (Spherical perturbations and Lipschitz
utilities). The perturbation law is a probability measure on . For every orthogonal
transformation and every Borel
set , it
satisfies .
Define the set of perturbations Then .
For an ordered query , the comparison bit is The map is
jointly measurable on . On call , the oracle returns , where the 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 . There must exist a
minimizer for which the gap is integrable and
where the expectation is over the algorithm’s randomness and the oracle
perturbations.
Proved result
OracleTemplate.Convergence LongTails.Setups.SphericalRandomUtility.spec
LongTails.Theorems.SphericalPreferenceDescent.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.