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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Smoothness). The function
Assumption 3 (Initial distance). There exists
Queries may use any pair
After the allotted comparison calls, the output must satisfy
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ComparisonOrthConvex
(Ours) |
|||
| (2) Comparison-AdaNGD (Zhang and Li 2024, Thm. 2) | (1): |
(1) adds |
|
| (3) Comparison cutting plane (Zhang and Li 2024, Thm. 3) | (1): gain |
(1) loses |
|
| (4) OrderACDM (Lobanov et al. 2024,
Thm. 4.1); |
(1): scope extends to
|
(1) lacks linear
convergence for |
|
| (5) (Wu et al. 2026, Thm. 3.3); unique-minimizer restriction | (1) uses comparisons instead of values on the common unique-minimizer class. | (1) adds logarithmic
factors and |
Abbr: