On the Iteration Complexity of Oblivious First-Order Optimization
  Algorithms
  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)$.
