  Selecting the best hyperparameters for a particular optimization instance,
such as the learning rate and momentum, is an important but nonconvex problem.
As a result, iterative optimization methods such as hypergradient descent lack
global optimality guarantees in general.
  We propose an online nonstochastic control methodology for mathematical
optimization. First, we formalize the setting of meta-optimization, an online
learning formulation of learning the best optimization algorithm from a class
of methods. The meta-optimization problem over gradient-based methods can be
framed as a feedback control problem over the choice of hyperparameters,
including the learning rate, momentum, and the preconditioner.
  Although the original optimal control problem is nonconvex, we show how
recent methods from online nonstochastic control using convex relaxations can
be used to overcome the challenge of nonconvexity, and obtain regret guarantees
against the best offline solution. This guarantees that in meta-optimization,
given a sequence of optimization problems, we can learn a method that attains
convergence comparable to that of the best optimization method in hindsight
from a class of methods.
