The need for fast and robust optimization algorithms are of critical importance in all areas of machine learning. This paper treats the task of designing optimization algorithms as an optimal control problem. Using regret as a metric for an algorithm's performance, we study the existence, uniqueness and consistency of regret-optimal algorithms. By providing first-order optimality conditions for the control problem, we show that regret-optimal algorithms must satisfy a specific structure in their dynamics which we show is equivalent to performing dual-preconditioned gradient descent on the value function generated by its regret. Using these optimal dynamics, we provide bounds on their rates of convergence to solutions of convex optimization problems. Though closed-form optimal dynamics cannot be obtained in general, we present fast numerical methods for approximating them, generating optimization algorithms which directly optimize their long-term regret. Lastly, these are benchmarked against commonly used optimization algorithms to demonstrate their effectiveness.
翻译:快速和稳健优化算法的必要性在机器学习的所有领域都至关重要。 本文将设计优化算法的任务视为最佳控制问题。 我们利用遗憾作为算法性能的衡量标准, 研究遗憾优化算法的存在、 独特性和一致性。 我们通过为控制问题提供一阶最佳性条件, 表明遗憾优化算法必须满足其动态中的特定结构, 我们所显示的这种结构相当于在它的遗憾产生的价值函数上进行双质梯度梯度下降。 使用这些最佳动态, 我们提供了它们汇合速度的界限, 以便解决混凝土优化问题。 虽然无法普遍获得封闭式最佳动态, 我们提出了快速的数字方法来接近这些算法, 产生直接优化其长期遗憾的优化算法。 最后, 这些算法是以常用的优化算法作为基准, 以显示其效果。