On Lower and Upper Bounds in Smooth Strongly Convex Optimization - A
  Unified Approach via Linear Iterative Methods
  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.
