Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization

2022/04/24 by Frank E. Curtis, Qi Wang, Curtis, Frank E. +1 · 3 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Advanced Optimization Algorithms Research

paper · pdf · doi:10.48550/arxiv.2204.11322

Abstract

An algorithm for solving nonconvex smooth optimization problems is proposed, analyzed, and tested. The algorithm is an extension of the Trust Region Algorithm with Contractions and Expansions (TRACE) [Math. Prog. 162(1):132, 2017]. In particular, the extension allows the algorithm to use inexact solutions of the arising subproblems, which is an important feature for solving large-scale problems. Inexactness is allowed in a manner such that the optimal iteration complexity of \cal O(ε^-3/2) for attaining an ε-approximate first-order stationary point is maintained while the worst-case complexity in terms of Hessian-vector products may be significantly improved as compared to the original TRACE. Numerical experiments show the benefits of allowing inexact subproblem solutions and that the algorithm compares favorably to a state-of-the-art technique.

Cited by

• A Homogeneous Tensor Framework for High-Order Trust-Region and Spherical Polynomial Optimization
• Non-Convex Self-Concordant Functions: Practical Algorithms and Complexity Analysis
• Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency

Related

• Strong Evaluation Complexity of An Inexact Trust-Region Algorithm for Arbitrary-Order Unconstrained Nonconvex Optimization
• Regional Complexity Analysis of Algorithms for Nonconvex Smooth\n Optimization
• Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
• An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of O(ε^-3/2) for Nonconvex Optimization
• Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds constraints