On Lower and Upper Bounds in Smooth Strongly Convex Optimization - A Unified Approach via Linear Iterative Methods
This work provides a unified theoretical framework for analyzing optimization algorithms, which is incremental but addresses limitations in existing bounds for researchers in optimization theory.
The paper tackles the problem of deriving lower and upper bounds for smooth strongly convex optimization by connecting optimization algorithms to polynomial theory, resulting in a new derivation of Nesterov's Accelerated Gradient Descent and a lower bound that holds for fixed dimensionality.
In this thesis 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. In particular, we present a new and natural derivation of Nesterov's well-known Accelerated Gradient Descent method by employing simple 'economic' polynomials. This rather natural interpretation of AGD contrasts with earlier ones which lacked a simple, yet solid, motivation. Lastly, whereas existing lower bounds 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.