← All setups

Local Reference Dueling Lower Bound — Strongly Convex Minimization with Flat Comparisons

Descriptions may be stale. Consult the linked Lean sources.

Strongly Convex Minimization with Flat Comparisons · Lean proof

Strongly Convex Minimization with Flat 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. At each queried pair x,y∈B, the oracle uses a fresh independent sample to return a sign with mean ρ(f(x)−f(y)). The unknown transfer function ρ is odd and nondecreasing, with a polynomial lower bound on its slope near zero. For 0<ε≤1/64, 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.

Writing ∥⋅∥ for the Euclidean norm, the optimization problem is minx∈Bf(x),B={x∈Rd:∥x∥≤1}. The algorithm receives d, ε, the objective constants specified below, and the transfer parameters r=1, k=2j, c=(2j+1)/8, and M=(2j+1)/4, where j is a nonnegative integer.

Our assumptions:

Assumption 1 (Objective regularity and curvature). The function f belongs to C1(Rd). For every x,y∈B, |f(x)−f(y)|≤4∥x−y∥,∥∇f(x)−∇f(y)∥≤2∥x−y∥,f(y)≥f(x)+⟨∇f(x),y−x⟩+14∥y−x∥2.

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

Assumption 3 (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 i at an ordered pair (x,y)∈B×B, the oracle returns g(x,y,Zi), 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 algorithm must return a measurable B-valued output x¯. Its gap relative to a minimizer x⋆∈argminx∈Bf(x) must be integrable and satisfy E[f(x¯)−f(x⋆)]≤ε.

Proved result

⌊d265536⋅(2⋅j+1)2⋅ε2⌋+

OracleTemplate.NonConvergence LongTails.Setups.FlatTransferDueling.spec
  LongTails.Theorems.LocalReferenceDuelingLowerBound.budget

Relevant previous results

  • Wataru Kumagai. Regret Analysis for Continuous Dueling Bandit. 2017. Complexity: Ω(d2/ε2) pairwise comparisons are necessary for expected objective gap at most ε, for 0<ε<0.004, under a fixed budget and a Gaussian comparison link with variance 2.