← All setups

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 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⋅(672⋅B⋅Rε)2⌉+

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.