← All setups

Local Reference Dueling — Strongly Convex Minimization with Comparisons

Descriptions may be stale. Consult the linked Lean sources.

Strongly Convex Minimization with Comparisons · Lean proof

Strongly Convex Minimization with Comparisons

We minimize a continuously differentiable function f:Rd→R over the closed Euclidean unit ball B in dimension d≥1. On B, f is strongly convex and Lipschitz with Lipschitz gradient. For each query x,y∈B, the oracle uses a fresh independent sample to return a sign in {−1,1} with mean ρ(f(x)−f(y)), where ρ is an unknown odd, nondecreasing function with local derivative bounds. Given ε>0, the goal is a feasible output x¯∈B with E[f(x¯)−f(x⋆)]≤ε, where x⋆ minimizes f on B and the expectation includes algorithm and oracle randomness.

With ∥⋅∥ denoting the Euclidean norm, the constrained problem is minx∈Bf(x),B={x∈Rd:∥x∥≤1}. The algorithm receives the dimension d, the objective constants μ,L,G>0, the transfer parameters r,c,M>0 and k∈{0,1,2,…}, and the tolerance ε.

Our assumptions:

Assumption 1 (Objective regularity and strong convexity). The function f is continuously differentiable on Rd. For every x,y∈B, it satisfies |f(y)−f(x)|≤G∥y−x∥,∥∇f(y)−∇f(x)∥≤L∥y−x∥,f(y)−f(x)≥⟨∇f(x),y−x⟩+μ2∥y−x∥2.

Assumption 2 (Comparison transfer). The transfer function ρ:R→[−1,1] is continuously differentiable, odd, and nondecreasing. Its derivative satisfies c|t|k≤ρ′(t)≤M,|t|≤r, where |t|0=1 for every t.

Assumption 3 (Pairwise comparison oracle). Let Z1,Z2,… be independent random variables with common law ν on a measurable space Z, independent of the algorithm’s randomness. On call j with ordered pair (x,y)∈B×B, the oracle returns the bit g(x,y,Zj) encoded as a sign, where g:B×B×Z→{−1,1} is jointly measurable. For every x,y∈B, EZ∼ν[g(x,y,Z)]=ρ(f(x)−f(y)).

After the allotted comparisons, the output x¯ must be a measurable B-valued random variable. For a minimizer x⋆∈B, the gap f(x¯)−f(x⋆) must be integrable under the joint law of the algorithm’s randomness and the oracle samples and satisfy E[f(x¯)−f(x⋆)]≤ε.

Proved result

⌈72⋅d2⋅(4μ)2⋅k⋅(max{1,8⋅Gr})4⋅k+2c2⋅μ⋅ε+10368⋅(d⋅M⋅L)2⋅(4μ)4⋅k⋅(max{1,8⋅Gr})8⋅k(c2⋅μ⋅ε)2⌉+

OracleTemplate.Convergence LongTails.Setups.StronglyConvexDueling.spec LongTails.Theorems.LocalReferenceDueling.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.