Gd Nonconvex — Smooth Nonconvex Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Smooth Nonconvex Stationarity · Lean proof
Smooth Nonconvex Stationarity
We consider a differentiable, possibly nonconvex function
We seek approximate stationarity for the optimization problem
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Lower bound and initial gap). There
exists
Queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothNonconvex.spec OracleTemplate.NonconvexGradient.budgetRelevant previous results
- Yurii Nesterov. Introductory
Lectures on Convex Programming, Volume I: Basic Course. 1998
preprint, 2 July version; book publication 2004. Complexity:
exact-gradient oracle calls using constant-step gradient descent and the best queried iterate, with . - Saeed Ghadimi and Guanghui Lan. Stochastic First- and
Zeroth-Order Methods for Nonconvex Stochastic Programming. 2013,
arXiv v1; journal publication 2013. Complexity:
exact-gradient oracle calls for randomized stochastic gradient with zero oracle variance, with a fixed call cap and .