Online Control for Meta-optimization

Choosing the optimal hyperparameters, including the learning rate and momentum, for specific optimization instances is a significant yet nonconvex challenge. This makes conventional iterative techniques such as hypergradient descent insufficient in obtaining global optimality guarantees in general. We consider the more general task of meta-optimization - online learning of the best optimization algorithm given problem instances. For this task, a novel approach based on control theory is introduced. We show how meta-optimization can be formulated as an optimal control problem, departing from existing literature that use stability-based methods to study optimization. Our approach leverages convex relaxation techniques in the recently-proposed nonstochastic control framework to overcome the challenge of nonconvexity, and obtains regret guarantees vs. the best offline solution. This guarantees that in meta-optimization, we can learn a method that attains convergence comparable to that of the best optimization method in hindsight from a class of methods.