Title: Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking Show Chinese title

Title: 寻找最优坐标步长的多维回溯搜索

Abstract: The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate stepsizes. We propose multidimensional backtracking, an extension of the backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the gradient with respect to the step-sizes, also known as hypergradients, yields separating hyperplanes that let us search for good preconditioners using cutting-plane methods. As black-box cutting-plane approaches like the ellipsoid method are computationally prohibitive, we develop an efficient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning. Show Chinese abstract

Abstract: 回溯线搜索是一种自动调整光滑优化问题中步长的有效技术，它保证了与使用理论上最优步长时的性能相当。许多方法被开发用于调整每坐标的步长（也称为对角预条件子），但现有的所有方法都无法在理论上证明能与最优的每坐标步长竞争。我们提出了多维回溯线搜索，这是回溯线搜索的一种扩展，旨在为光滑凸问题找到良好的对角预条件子。我们的关键见解是，关于步长的梯度（也称为超梯度）提供了分离超平面，使我们可以利用割平面法来搜索良好的预条件子。由于像椭球法这样的黑盒割平面方法在计算上是不可行的，我们为此设定开发了一种高效的算法。多维回溯线搜索在理论上被证明可以与最佳对角预条件子竞争，并且不需要人工调参。