← All setups

Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given starting point x0∈E lies within distance R≥0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, L, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

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

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

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

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. Here the minimizer is fixed independently of the algorithm’s randomness; any global minimizer gives the same objective value.

Results

A convex differentiable f:E→R on a real Hilbert space has an L-Lipschitz gradient, L>0, and a minimizer x⋆ with ∥x0−x⋆∥≤R, R≥0. The oracle returns the exact gradient for every query and seed. Target: f(xK)−f(x⋆)≤ε, ε>0, almost surely under every oracle seed law. The setup imposes no algorithm restriction; the constructions use known L, with R,ε determining the stopping budget.

Smooth convex minimization: SmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedConvex (Ours) (review) O(1+LR2/ε)
(2) GdConvex (Ours) (review) O(1+LR2/ε)
(3) Nesterov AGD (d’Aspremont et al. 2021, Cor. 4.9) O(1+LR2/ε) (1): Matches known rate; Lean formalization. The dimension-free argument extends to Hilbert spaces. (2): For LR2/ε≫1, about LR2/(8ε) times more calls. Same oracle and tuning knowledge.
(4) OGM (d’Aspremont et al. 2021, Cor. 4.6) O(1+LR2/ε); stated on Rd. (1): Matches known order on Rd; no established improvement. (1): About 2 times more calls when LR2/ε≫1, on Rd.
(5) Classical GD (Drori and Teboulle 2012, Eq. (3.1)) O(1+LR2/ε); step 1/L, stated on Rd. (1): Known acceleration gives O(1+LR2/ε) instead of O(1+LR2/ε) on Rd. (2): Matches known rate; Lean formalization.
(6) Tight GD (Drori and Teboulle 2012, Thms. 3.1–3.2) O(1+LR2/ε); step 1/L, stated on Rd. (2): Matches known order on Rd; no established improvement. (2): About twice as many calls when LR2/ε≫1, for the same GD algorithm on Rd.
(7) FISTA (Beck and Teboulle 2009, Thm. 4.4) O(1+LR2/ε); constant step 1/L, g=0, E=Rd. (1): Matches known rate at g=0; no oracle saving, since the proximal map is the identity. (1): Up to one extra call at g=0. (1), (2): Do not cover the composite objectives also treated by (7).

Abbr: Costs count exact gradient evaluations. L: gradient Lipschitz constant; R: initial distance bound; ε: objective-gap tolerance; K: number of calls; d: dimension; GD: gradient descent; AGD: accelerated gradient descent; OGM: optimized gradient method; g: FISTA’s convex nonsmooth term.

Beck, Amir, and Marc Teboulle. 2009. “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems.” SIAM Journal on Imaging Sciences 2 (1): 183–202. https://doi.org/10.1137/080716542.
d’Aspremont, Alexandre, Damien Scieur, and Adrien Taylor. 2021. “Acceleration Methods.” Foundations and Trends in Optimization 5 (1–2): 1–245. https://doi.org/10.1561/2400000036.
Drori, Yoel, and Marc Teboulle. 2012. Performance of First-Order Methods for Smooth Convex Minimization: A Novel Approach. https://doi.org/10.48550/arXiv.1206.3209.

Lean setup