On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
arXiv:1503.06833
Abstract
We develop a novel framework to study smooth and strongly convex optimization algorithms, both deterministic and stochastic. Focusing on quadratic functions we are able to examine optimization algorithms as a recursive application of linear operators. This, in turn, reveals a powerful connection between a class of optimization algorithms and the analytic theory of polynomials whereby new lower and upper bounds are derived. Whereas existing lower bounds for this setting are only valid when the dimensionality scales with the number of iterations, our lower bound holds in the natural regime where the dimensionality is fixed. Lastly, expressing it as an optimal solution for the corresponding optimization problem over polynomials, as formulated by our framework, we present a novel systematic derivation of Nesterov's well-known Accelerated Gradient Descent method. This rather natural interpretation of AGD contrasts with earlier ones which lacked a simple, yet solid, motivation.
Cited by in corpus (13)
- A Variational Perspective on Accelerated Methods in Optimization
- Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
- SDCA without Duality, Regularization, and Individual Convexity
- Towards Riemannian Accelerated Gradient Methods
- On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
- Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
- Tight last-iterate convergence rates for no-regret learning in multi-player games
- Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
- Lower Bounds for Higher-Order Convex Optimization
- Parametrized Accelerated Methods Free of Condition Number
- Semantics, Representations and Grammars for Deep Learning
- Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
- Adversarial Delays in Online Strongly-Convex Optimization