论文标题
超级正规化牛顿方法
Super-Universal Regularized Newton Method
论文作者
论文摘要
我们分析了牛顿方法的变体的性能和二次正则化，以解决复合凸凸的最小化问题。在我们方法的每个步骤中，我们选择与当前点的梯度标准的一定功率成比例的正则化参数。我们介绍了一个以Hölder连续性为特征的问题类别的家族。然后，我们使用一个简单的自适应搜索步骤介绍该方法，允许自动调整问题类别的最佳全局复杂性界限，而无需知道问题的特定参数。特别是，对于Lipschitz连续第三个导数的函数类别，我们获得了全局$ O（1/k^3）$速率，这先前归因于三阶张量方法。当目标函数均匀凸出时，我们证明了我们方案的自动加速度合理，从而导致全球速率和局部超级线性收敛。不同速率（sublinear，Linear和Superlinear）之间的切换是自动的。同样，为此，不需要先验地了解参数。
We analyze the performance of a variant of Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose regularization parameter proportional to a certain power of the gradient norm at the current point. We introduce a family of problem classes characterized by Hölder continuity of either the second or third derivative. Then we present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds, without knowing specific parameters of the problem. In particular, for the class of functions with Lipschitz continuous third derivative, we get the global $O(1/k^3)$ rate, which was previously attributed to third-order tensor methods. When the objective function is uniformly convex, we justify an automatic acceleration of our scheme, resulting in a faster global rate and local superlinear convergence. The switching between the different rates (sublinear, linear, and superlinear) is automatic. Again, for that, no a priori knowledge of parameters is needed.
