Gradient Descent for Weakly Convex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Gradient Descent for Weakly Convex Optimization
We consider minimizing a differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Weak convexity). The function
Assumption 3 (Initial objective gap). There exists
Our result is algorithm-specific: we analyze gradient descent with
positive, iteration-dependent step sizes and an output selected by
gradient norm. The algorithm chooses a sequence
The output must be measurable, its squared gradient norm must be
integrable under
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) WeaklyConvexSilver (Ours) (review) | |||
| (2) Constant-step GD,
|
(1): Method-specific
speedup factor |
(1) needs |
|
| (3) Almost-convex-AGD
(Carmon et al. 2017,
Lemma 3.1) Derived bound; |
Choose |
(1): Predetermined GD analysis; (3) uses momentum and gradient-solved regularized subproblems. Same gradient oracle; no established problem-class improvement. | (1) has term ratios |
| (4) Long-step GD (Grimmer et al. 2024,
Theorem 1) Special case: |
(1): Scope extends to
|
(1): On the convex
overlap, |
Abbr: