← All setups

Comparison Orth Convex — Comparison-Based Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Comparison-Based Smooth Convex Minimization · Lean proof

Comparison-Based Smooth Convex Minimization

We consider minimizing a differentiable convex function f:Rn→R, where n≥1 is an integer. Its gradient is L-Lipschitz in the Euclidean norm, with L>0, and a given starting point x0∈Rn lies within distance R>0 of a global minimizer x⋆. At a queried pair (x,y), the oracle returns the Boolean value of f(x)≤f(y). For a tolerance ε>0, the goal is an output x¯∈Rn satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Rnf(x). Throughout, ∥⋅∥ denotes the Euclidean norm. The algorithm receives n, L, R, ε, and x0.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈Rn and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Smoothness). The function f is differentiable everywhere on Rn, and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rn.

Assumption 3 (Initial distance). There exists x⋆∈Rn such that f(x⋆)≤f(x)for every x∈Rn,∥x0−x⋆∥≤R.

Queries may use any pair (x,y)∈Rn×Rn. Comparisons are exact: the reply is true precisely when f(x)≤f(y), including equality, and false otherwise.

After the allotted comparison calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. The minimizer is fixed independently of the algorithm’s randomness; all global minimizers have the same objective value.

Proved result

(⌈6⋅L⋅R2ε⌉++1)⋅((12⋅log2⁡(n⋅⌈L⋅R2ε⌉+)+96)⋅(3⋅n+7⋅(12⋅log2⁡(n⋅⌈L⋅R2ε⌉+)+96)2))

OracleTemplate.Convergence LongTails.Setups.ComparisonSmoothConvex.spec OracleTemplate.ComparisonOrth.budget

Relevant previous results

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