论文标题
非convex二次最小化的一阶方法
First-Order Methods for Nonconvex Quadratic Minimization
论文作者
论文摘要
我们考虑使用信任区域（规范）约束或立方正规化的无限四倍体的最小化。尽管这些问题没有任何概念性，但我们证明，在温和的假设下，梯度下降会收敛到其全球溶液，并给出了非征收的分数融合速率。我们还考虑Krylov子空间解决方案，并为信任区域和立方规范化问题的解决方案建立急剧的收敛保证。我们的费率反映了这些方法在凸四次和特征向量问题上的行为，突出了它们的可扩展性。当我们使用Krylov子空间解决方案近似于立方规范化的牛顿步骤时，我们的结果恢复了最强的已知收敛保证，以使一般平滑非凸功能的近似二阶固定点近似。
We consider minimization of indefinite quadratics with either trust-region (norm) constraints or cubic regularization. Despite the nonconvexity of these problems we prove that, under mild assumptions, gradient descent converges to their global solutions, and give a non-asymptotic rate of convergence for the cubic variant. We also consider Krylov subspace solutions and establish sharp convergence guarantees to the solutions of both trust-region and cubic-regularized problems. Our rates mirror the behavior of these methods on convex quadratics and eigenvector problems, highlighting their scalability. When we use Krylov subspace solutions to approximate the cubic-regularized Newton step, our results recover the strongest known convergence guarantees to approximate second-order stationary points of general smooth nonconvex functions.
