论文标题
懒惰的黑森人的二阶优化
Second-order optimization with lazy Hessians
论文作者
论文摘要
我们通过懒惰的黑森更新分析牛顿的方法，以解决一般可能的非凸优化问题。我们建议在方法的每个步骤中计算新梯度时重复使用先前看到的黑森式进行多次迭代。这显着降低了二阶优化方案的总体算术复杂性。通过使用立方正则化技术，我们将方法从二阶固定点建立了快速的全局融合，而Hessian不需要更新每次迭代。对于凸问题，我们证明了使用二次正规化的懒惰牛顿步骤的全球和本地超级线性率是合理的，这更容易计算。更新Hessian的最佳频率是每$ d $迭代一次，其中$ d $是问题的维度。事实证明，这可以通过因子$ \ sqrt {d} $提高二阶算法的总算术复杂性。
We analyze Newton's method with lazy Hessian updates for solving general possibly non-convex optimization problems. We propose to reuse a previously seen Hessian for several iterations while computing new gradients at each step of the method. This significantly reduces the overall arithmetical complexity of second-order optimization schemes. By using the cubic regularization technique, we establish fast global convergence of our method to a second-order stationary point, while the Hessian does not need to be updated each iteration. For convex problems, we justify global and local superlinear rates for lazy Newton steps with quadratic regularization, which is easier to compute. The optimal frequency for updating the Hessian is once every $d$ iterations, where $d$ is the dimension of the problem. This provably improves the total arithmetical complexity of second-order algorithms by a factor $\sqrt{d}$.
