Lower Bounds for Smooth Nonconvex Finite-Sum Optimization

Abstract

Smooth finite-sum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finite-sum optimization are mostly limited to the setting where each component function is (strongly) convex, while the lower bounds for nonconvex finite-sum optimization remain largely unsolved. In this paper, we study the lower bounds for smooth nonconvex finite-sum optimization, where the objective function is the average of $n$ nonconvex component functions. We prove tight lower bounds for the complexity of finding $\epsilon$-suboptimal point and $\epsilon$-approximate stationary point in different settings, for a wide regime of the smallest eigenvalue of the Hessian of the objective function (or each component function). Given our lower bounds, we can show that existing algorithms including KatyushaX (Allen-Zhu, 2018), Natasha (Allen-Zhu, 2017), RapGrad (Lan and Yang, 2018) and StagewiseKatyusha (Chen and Yang, 2018) have achieved optimal Incremental First-order Oracle (IFO) complexity (i.e., number of IFO calls) up to logarithm factors for nonconvex finite-sum optimization. We also point out potential ways to further improve these complexity results, in terms of making stronger assumptions or by a different convergence analysis.

21 pages

References in corpus (12)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Tight Complexity Bounds for Optimizing Composite Objectives
• A Lower Bound for the Optimization of Finite Sums
• SDCA without Duality
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• SDCA without Duality, Regularization, and Individual Convexity
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure
• Lower Bounds for Higher-Order Convex Optimization
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number

Cited by in corpus (12)

• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Stability of SGD: Tightness Analysis and Improved Bounds
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Optimal Complexity in Decentralized Training
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization