Newton-type methods for non-convex optimization under inexact Hessian information

• 成果类型: Article
• 署名作者: Xu, Peng; Roosta, Fred; Mahoney, Michael W.
• 署名单位: Stanford University; University of Queensland; University of California System; University of California Berkeley
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01405-z
• 发表日期: 2020
• 页码: 35-70
• 关键词: trust-region methods; cubic regularization; Stochastic algorithms; iterative methods; complexity; CONVERGENCE; POWER

摘要

We consider variants of trust-region and adaptive cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under certain condition on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve epsilon-approximate second-order optimality which have been shown to be tight. Our Hessian approximation condition offers a range of advantages as compared with the prior works and allows for direct construction of the approximate Hessian with a priori guarantees through various techniques, including randomized sampling methods. In this light, we consider the canonical problem of finite-sum minimization, provide appropriate uniform and non-uniform sub-sampling strategies to construct such Hessian approximations, and obtain optimal iteration complexity for the corresponding sub-sampled trust-region and adaptive cubic regularization methods.