Recursive Gradient Nonconvex — Finite-Sum Nonconvex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Finite-Sum Nonconvex Optimization · Lean proof
Finite-Sum Nonconvex Optimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Mean-square smoothness). Each
component
Assumption 2 (Lower bound and initial gap). There
exists
Queries may use any index
Proved result
OracleTemplate.Convergence LongTails.Setups.FiniteSumSmoothNonconvex.spec OracleTemplate.NonconvexFiniteSum.budgetRelevant previous results
- Cong Fang, Chris Junchi Li, Zhouchen Lin, Tong Zhang. SPIDER:
Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated
Differential Estimator. 2018. Complexity:
exact component-gradient calls, including initialization and batches, with fixed cost; SPIDER-SFO obtains . - Lam M. Nguyen, Marten van Dijk, Dzung T. Phan, Phuong Ha Nguyen,
Tsui-Wei Weng, Jayant R. Kalagnanam. Finite-Sum Smooth Optimization
with SARAH. 2019 preprint, version 2. Complexity:
exact component-gradient calls, including full-gradient initialization, refreshes, and paired evaluations, with fixed cost; modified SARAH obtains . - Zhize Li, Hongyan Bao, Xiangliang Zhang, Peter Richtárik. PAGE: A Simple and
Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.
2021. Complexity:
expected exact component-gradient calls, including initialization, refresh batches, and paired evaluations; PAGE obtains .