← All setups

Comparison-Based Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Convex differentiable f:Rn→R, n≥1, with L-Lipschitz gradient and a minimizer x⋆ satisfying ∥x0−x⋆∥≤R; L,R,ε>0. The oracle returns 1[f(x)≤f(y)]. Target: f(xout)−f(x⋆)≤ε almost surely; (1) is deterministic and uses the public n,L,R,ε,x0.

Exact-comparison smooth convex optimization: ComparisonSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) ComparisonOrthConvex (Ours) (⋆⋆⋆) (review) O((1+T)(nℓ+ℓ3)) comparisons
(2) Comparison-AdaNGD (Zhang and Li 2024, Thm. 2) O(n(1+T)ℓ) comparisons (1): T instead of T for T≥1, n≥ℓ2; last iterate instead of comparison-selected best iterate. (1) adds O((1+T)ℓ3) search overhead.
(3) Comparison cutting plane (Zhang and Li 2024, Thm. 3) O(n2ℓ) comparisons (1): gain n/T when 1≤T<n2, n≥ℓ2. At T=n: O(n3/2log⁡n) versus O(n2log⁡n). (1) loses T/n for T>n2; polynomial rather than logarithmic accuracy dependence.
(4) OrderACDM (Lobanov et al. 2024, Thm. 4.1); μ-strongly convex restriction O(nL/μ[1+log+⁡(LR2/ε)]Cls) comparisons, uniform coordinate bounds; expected accuracy (1): scope extends to μ=0; deterministic instead of expected accuracy. Rates are not comparable at μ=0. (1) lacks linear convergence for μ>0 and coordinate-smoothness gains on anisotropic instances.
(5) (Wu et al. 2026, Thm. 3.3); unique-minimizer restriction O(nT) exact values, T≥1; queries in B(x0,2R), output in B(x0,R) (1) uses comparisons instead of values on the common unique-minimizer class. (1) adds logarithmic factors and O(Tℓ3) overhead; no bounded-query guarantee.

Abbr: T=LR2/ε; ℓ=1+log⁡(n(1+T)); log+⁡u=max{0,log⁡u}; μ>0 is the strong-convexity modulus. Cls is the comparison cost of the line searches per OrderACDM iteration (logarithmic precision dependence, suppressed in its published oracle bound).

Lobanov, Aleksandr, Alexander Gasnikov, and Andrei Krasnov. 2024. Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values. https://doi.org/10.48550/arXiv.2402.09014.
Wu, Wendao, Haihan Zhang, Chenheng Zhang, et al. 2026. Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization. https://doi.org/10.48550/arXiv.2609.18230.
Zhang, Chenyi, and Tongyang Li. 2024. Comparisons Are All You Need for Optimizing Smooth Functions. https://doi.org/10.48550/arXiv.2405.11454.

Lean setup