Direct Synthesis of Iterative Algorithms With Bounds on Achievable Worst-Case Convergence Rate
Direct Synthesis of Iterative Algorithms With Bounds on Achievable Worst-Case Convergence Rate
复制标题
DOI：
10.23919/acc45564.2020.9147401
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Laurent Lessard;P. Seiler
中科院分区：
文献类型：
--
作者：
Laurent Lessard;P. Seiler
迭代一阶方法，如梯度下降及其变种，被广泛用于求解优化和机器学习问题。最近，人们对用于计算这类算法的最坏情况下的性能界的解析或数值有效的方法感兴趣，例如在强凸损失函数类上。一种流行的方法是假设算法具有固定的大小(固定维度或内存)，并且其结构由一个或两个超参数来参数化，例如，学习率和动量参数。然后，寻找一个Lyapunov函数来证明鲁棒稳定性，并进行后续的优化以找到最优的超参数调节。在目前的工作中，我们改为固定表征损失函数的约束，并应用从鲁棒控制综合到直接搜索算法的技术。这种方法产生了比以前可用的更强的结果，因为产生的界限适用于具有任意但有限的内存量的算法，而不仅仅是具有指定结构的算法。
Iterative first-order methods such as gradient descent and its variants are widely used for solving optimization and machine learning problems. There has been recent interest in analytic or numerically efficient methods for computing worst-case performance bounds for such algorithms, for example over the class of strongly convex loss functions. A popular approach is to assume the algorithm has a fixed size (fixed dimension, or memory) and that its structure is parameterized by one or two hyper-parameters, for example a learning rate and a momentum parameter. Then, a Lyapunov function is sought to certify robust stability and subsequent optimization can be performed to find optimal hyperparameter tunings. In the present work, we instead fix the constraints that characterize the loss function and apply techniques from robust control synthesis to directly search over algorithms. This approach yields stronger results than those previously available, since the bounds produced hold over algorithms with an arbitrary, but finite, amount of memory rather than just holding for algorithms with a prescribed structure.