← All setups

Strongly Convex Minimization with Flat Comparisons

Descriptions may be stale. Consult the linked Lean sources.

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⋆)]≤ε.

Results

On the closed Euclidean unit ball Bd, d≥1, the C1 loss is 1/2-strongly convex, 2-smooth and 4-Lipschitz. Each comparison uses fresh IID randomness and returns a sign with conditional mean ρ(f(x)−f(y)). The odd, nondecreasing C1 link satisfies |ρ|≤1 and q|t|2j/8≤ρ′(t)≤q/4 for |t|≤1, where q=2j+1 and j∈{0,1,…}. The target for any randomized adaptive algorithm is x^∈Bd with E[f(x^)−minBdf]≤ε, 0<ε≤1/64.

Necessary comparison budgets for flat-transfer dueling.
Result Oracle complexity Novelty Limitations
(1) LocalReferenceDuelingLowerBound (Ours) (⋆⋆) (review) Lower bound Ω(1+d2q2ε2) comparisons.
(2) (Kumagai 2017, Thm. 14) Lower bound Ω(d2/ε2) for ε<0.004 on Bd with variance-2 probit feedback. (1) proves fixed-ball hardness even for ρ(t)=14arctan⁡(tq), flat at ties for j≥1. At j=0 it matches the order of (2) under different normalizations. (1) uses 2-smooth losses. (2) allows 3.5-smooth losses and fixes ρ′(0)=1/π, outside the link envelope of (1).
(3) (Jamieson et al. 2012, Thm. 1, Lem. 1) Lower bound Ω(d/ε2q) for fixed q=κ−1 and margin parameters, d≥8 and sufficiently large T. (1) establishes hardness on a fixed ball in every dimension. The query cube in (3) shrinks with T, so the rates are not directly comparable. (1) fixes the local slope bounds and window. (3) allows any comparison oracle satisfying its reliability margin.

Abbr: T counts one-bit comparisons. κ−1 is the power of the absolute loss difference in the reliability margin.

Jamieson, Kevin G., Robert D. Nowak, and Benjamin Recht. 2012. “Query Complexity of Derivative-Free Optimization.” Advances in Neural Information Processing Systems 25. https://doi.org/10.48550/arXiv.1209.2434.
Kumagai, Wataru. 2017. “Regret Analysis for Continuous Dueling Bandit.” Advances in Neural Information Processing Systems 30. https://doi.org/10.48550/arXiv.1711.07693.

Lean setup