Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization

2025/12/10 by Marumo, Naoki
#65K05 #65K10 #90C26 #90C30 #90C53 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2512.09439

Abstract

We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an ε-stationary point within O(d^1/4 ε^-13/8) gradient evaluations, where d is the problem dimension. Although this bound includes an additional logarithmic factor compared with the best known complexity, our method is parameter-free in the sense that it requires no prior knowledge of problem-dependent parameters such as Lipschitz constants or the optimal value. Moreover, it does not need the target accuracy ε or the total number of iterations to be specified in advance. The result is achieved by combining several key ideas: momentum-based acceleration, quartic regularization for subproblems, and a scaled variant of the Powell-symmetric-Broyden (PSB) update.

Citations

• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
• Non-asymptotic Global Convergence Rates of BFGS with Exact Line Search
• AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization
• Second-order methods for quartically-regularised cubic polynomials, with applications to high-order tensor methods
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
• Super-Universal Regularized Newton Method
• Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε^-7/4) Complexity
• Regularized Newton Method with Global O(1/k²) Convergence
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
• Online Learning: A Modern Introduction Using Convex Optimization
• Revisiting the Polyak step size
• Universal regularization methods - varying the power, the smoothness and\n the accuracy
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Neon2: Finding Local Minima via First-Order Oracles
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Online to Offline Conversions, Universality and Adaptive Minibatch Sizes
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient\n Descent on Non-Convex Functions
• Monotone Operators and the Proximal Point Algorithm
• An Automatic Method for Finding the Greatest or Least Value of a Function

Related

• New Globalized Newton-Type Methods for Nonconvex Optimization Problems
• Accelerated Methods for Non-Convex Optimization
• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
• A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
• Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε^-7/4) Complexity