On the Iteration Complexity of Oblivious First-Order Optimization Algorithms

Abstract

We consider a broad class of first-order optimization algorithms which are \emph{oblivious}, in the sense that their step sizes are scheduled regardless of the function under consideration, except for limited side-information such as smoothness or strong convexity parameters. With the knowledge of these two parameters, we show that any such algorithm attains an iteration complexity lower bound of $\Omega (\sqrt{L/\epsilon })$ for $L$-smooth convex functions, and $\tilde{\Omega }(\sqrt{L/\mu }\ln (1/\epsilon ))$ for $L$-smooth $\mu$-strongly convex functions. These lower bounds are stronger than those in the traditional oracle model, as they hold independently of the dimension. To attain these, we abandon the oracle model in favor of a structure-based approach which builds upon a framework recently proposed in (Arjevani et al., 2015). We further show that without knowing the strong convexity parameter, it is impossible to attain an iteration complexity better than $\tilde{\Omega }\left((L/\mu )\ln (1/\epsilon )\right)$. This result is then used to formalize an observation regarding $L$-smooth convex functions, namely, that the iteration complexity of algorithms employing time-invariant step sizes must be at least $\Omega (L/\epsilon )$.

References in corpus (5)

• A Universal Catalyst for First-Order Optimization
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• From Averaging to Acceleration, There is Only a Step-size
• SDCA without Duality
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems

Cited by in corpus (12)

• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Accelerating Smooth Games by Manipulating Spectral Shapes
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Complexity Guarantees for Polyak Steps with Momentum
• Dimension-Free Iteration Complexity of Finite Sum Optimization Problems