An accelerated first-order method with complexity analysis for solving cubic regularization subproblems

DOI10.1007/S10589-021-00274-7zbMATH Open1473.90116arXiv1911.12545OpenAlexW3144519047MaRDI QIDQ2044484FDOQ2044484

Authors: Rujun Jiang, Man-Chung Yue, Zhishuo Zhou 

Publication date: 9 August 2021

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: We propose a first-order method to solve the cubic regularization subproblem (CRS) based on a novel reformulation. The reformulation is a constrained convex optimization problem whose feasible region admits an easily computable projection. Our reformulation requires computing the minimum eigenvalue of the Hessian. To avoid the expensive computation of the exact minimum eigenvalue, we develop a surrogate problem to the reformulation where the exact minimum eigenvalue is replaced with an approximate one. We then apply first-order methods such as the Nesterov's accelerated projected gradient method (APG) and projected Barzilai-Borwein method to solve the surrogate problem. As our main theoretical contribution, we show that when an $epsilon$-approximate minimum eigenvalue is computed by the Lanczos method and the surrogate problem is approximately solved by APG, our approach returns an $epsilon$-approximate solution to CRS in $ildeO(epsilo{n}^{-1/2})$ matrix-vector multiplications (where $ildeO(cdot)$ hides the logarithmic factors). Numerical experiments show that our methods are comparable to and outperform the Krylov subspace method in the easy and hard cases, respectively. We further implement our methods as subproblem solvers of adaptive cubic regularization methods, and numerical results show that our algorithms are comparable to the state-of-the-art algorithms.

Full work available at URL: https://arxiv.org/abs/1911.12545

Recommendations

• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem
• Solving the cubic regularization model by a nested restarting Lanczos method
• Accelerating the cubic regularization of Newton's method on convex problems
• Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization

zbMATH Keywords

first-order methodscomplexity analysisconstrained convex optimizationcubic regularization subproblem

Mathematics Subject Classification ID

Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
• Benchmarking optimization software with performance profiles.
• Adaptive restart for accelerated gradient schemes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two-Point Step Size Gradient Methods
• A unified formulation and fast accelerated proximal gradient method for classification
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
• Cubic regularization of Newton method and its global performance
• Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid
• Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
• Accelerated methods for nonconvex optimization
• Finding approximate local minima faster than gradient descent
• On the use of iterative methods in cubic regularization for unconstrained optimization
• A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
• Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates
• Gradient descent finds the cubic-regularized nonconvex Newton step
• A second-order cone based approach for solving the trust-region subproblem and its variants
• On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition

Cited In (5)

• Scalable adaptive cubic regularization methods
• A filter sequential adaptive cubic regularization algorithm for nonlinear constrained optimization
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Solving the cubic regularization model by a nested restarting Lanczos method
• A sequential adaptive regularisation using cubics algorithm for solving nonlinear equality constrained optimization

Uses Software

• CUTEst

This page was built for publication: An accelerated first-order method with complexity analysis for solving cubic regularization subproblems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044484)