Weakly Convex Silver — Gradient Descent for Weakly Convex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Gradient Descent for Weakly Convex Optimization · Lean proof
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
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothWeaklyConvex.spec OracleTemplate.WeaklyConvexSilverGd.budgetRelevant previous results
- Guanghui Lan and Yu Yang. Accelerated Stochastic
Algorithms for Nonconvex Finite-sum and Multi-block Optimization.
2019 (preprint 2018; version 5 consulted). Complexity:
fixed-budget exact-gradient calls, including initialization, for single-component unconstrained RapGrad to obtain . Here is a positive weak-convexity upper bound when ; requires only returning .