A Lower Bound for the Optimization of Finite Sums

Abstract

This paper presents a lower bound for optimizing a finite sum of $n$ functions, where each function is $L$-smooth and the sum is $\mu$-strongly convex. We show that no algorithm can reach an error $\epsilon$ in minimizing all functions from this class in fewer than $\Omega (n+\sqrt{n(\kappa -1)}\log (1/\epsilon ))$ iterations, where $\kappa =L/\mu$ is a surrogate condition number. We then compare this lower bound to upper bounds for recently developed methods specializing to this setting. When the functions involved in this sum are not arbitrary, but based on i.i.d. random data, then we further contrast these complexity results with those for optimal first-order methods to directly optimize the sum. The conclusion we draw is that a lot of caution is necessary for an accurate comparison, and identify machine learning scenarios where the new methods help computationally.

Added an erratum, we are currently working on extending the result to randomized algorithms

References in corpus (2)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• On Lower and Upper Bounds in Smooth Strongly Convex Optimization - A Unified Approach via Linear Iterative Methods

Cited by in corpus (30)

• A Universal Catalyst for First-Order Optimization
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• SDCA without Duality, Regularization, and Individual Convexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Adaptive Step Sizes in Variance Reduction via Regularization
• Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient
• On the Convergence of SARAH and Beyond
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization
• A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
• Stochastic Reweighted Gradient Descent
• Optimal Complexity in Decentralized Training
• A Unifying Framework for Variance Reduction Algorithms for Finding Zeroes of Monotone Operators
• A Survey on Large-scale Machine Learning
• Searching equillibriums in large transport networks
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Bounding the expected run-time of nonconvex optimization with early stopping
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
• A Stochastic Gradient Method with Biased Estimation for Faster Nonconvex Optimization
• Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence