论文标题
最佳和适应性蒙特罗派服务员加速
Optimal and Adaptive Monteiro-Svaiter Acceleration
论文作者
论文摘要
我们开发了Monteiro-Svaiter（MS）加速框架的变体，该框架消除了在每次迭代中求解昂贵的隐式方程的必要性。因此，对于任何$ p \ ge 2 $，我们通过对数因子与Lipschitz $ p $ ph衍生物的凸的复杂性提高了相匹配的下限。我们还引入了一个不需要问题参数的MS子问题解决者，并分别通过求解线性系统或施加微小设备来将其实现为二阶或一阶方法。关于逻辑回归，我们的方法优于以前的二阶动量方法，但表现不足牛顿的方法；只需迭代我们的一阶自适应子问题求解器与L-BFG的表现相当。
We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any $p\ge 2$ we improve the complexity of convex optimization with Lipschitz $p$th derivative by a logarithmic factor, matching a lower bound. We also introduce an MS subproblem solver that requires no knowledge of problem parameters, and implement it as either a second- or first-order method by solving linear systems or applying MinRes, respectively. On logistic regression our method outperforms previous second-order momentum methods, but under-performs Newton's method; simply iterating our first-order adaptive subproblem solver performs comparably to L-BFGS.
