论文标题
关于张量优化方法的最佳组合
On the Optimal Combination of Tensor Optimization Methods
论文作者
论文摘要
我们考虑了具有Lipschitz常数不同的Lipshitz $ p $ th阶衍生物的许多功能总和的最小化问题。在这种情况下，为了加速优化，我们提出了一个通用框架，允许分别以总和为单独的每个函数获得近乎最佳的甲骨文复杂性，尤其是，尤其是，较低Lipschitz常数的函数的甲骨文称为较小的次数。作为一个构建基础，我们扩展了当前的张量方法理论，并展示了如何概括近距离张量的方法来处理不精确张量的步骤。此外，我们研究了总和中具有不同顺序的Lipschitz衍生物的情况。在这种情况下，我们提出了一种将甲骨文复杂性分离总和部分之间的通用方法。我们的方法不是最佳的，这导致了一个开放的问题，即不同顺序的Oracles的最佳组合。
We consider the minimization problem of a sum of a number of functions having Lipshitz $p$-th order derivatives with different Lipschitz constants. In this case, to accelerate optimization, we propose a general framework allowing to obtain near-optimal oracle complexity for each function in the sum separately, meaning, in particular, that the oracle for a function with lower Lipschitz constant is called a smaller number of times. As a building block, we extend the current theory of tensor methods and show how to generalize near-optimal tensor methods to work with inexact tensor step. Further, we investigate the situation when the functions in the sum have Lipschitz derivatives of a different order. For this situation, we propose a generic way to separate the oracle complexity between the parts of the sum. Our method is not optimal, which leads to an open problem of the optimal combination of oracles of a different order.
