LeAP-SSN: A Semismooth Newton Method with Global Convergence Rates

2025/08/22 by Alphonse, Amal, Dvurechensky, Pavel, Papadopoulos, Ioannis P. A. +1 · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2508.16468

Abstract

We propose LeAP-SSN (Levenberg--Marquardt Adaptive Proximal Semismooth Newton method), a semismooth Newton-type method with a simple, parameter-free globalisation strategy that guarantees convergence from arbitrary starting points in nonconvex settings to stationary points, and under a Polyak--Lojasiewicz condition, to a global minimum, in Hilbert spaces. The method employs an adaptive Levenberg--Marquardt regularisation for the Newton steps, combined with backtracking, and does not require knowledge of problem-specific constants. We establish global nonasymptotic rates: O(1/k) for convex problems in terms of objective values, O(1/√(k)) under nonconvexity in terms of subgradients, and linear convergence under a Polyak--Lojasiewicz condition. The algorithm achieves superlinear convergence under mild semismoothness and Dennis--Moré or partial smoothness conditions, even for non-isolated minimisers. By combining strong global guarantees with superlinear local rates in a fully parameter-agnostic framework, LeAP-SSN bridges the gap between globally convergent algorithms and the fast asymptotics of Newton's method. The practical efficiency of the method is illustrated on representative problems from imaging, contact mechanics, and machine learning.

Citations

• Convergence rates of regularized quasi-Newton methods without strong convexity
• A globalized inexact semismooth Newton method for strongly convex optimal control problems
• Inertial Bregman Proximal Gradient under Partial Smoothness
• A Globalized Inexact Semismooth Newton Method for Nonsmooth Fixed-point Equations involving Variational Inequalities
• Convergence of Descent Optimization Algorithms under Polyak-Łojasiewicz-Kurdyka Conditions
• An Inexact Regularized Proximal Newton Method without Line Search
• Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
• An inexact q-order regularized proximal Newton method for nonconvex composite optimization
• On growth error bound conditions with an application to heavy ball method
• Riemannian Trust Region Methods for SC¹ Minimization
• Fast convergence to non-isolated minima: four equivalent conditions for C² functions
• An inexact regularized proximal Newton method for nonconvex and nonsmooth optimization
• Super-Universal Regularized Newton Method
• Optimal and Adaptive Monteiro-Svaiter Acceleration
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Inexact Proximal Newton methods in Hilbert spaces
• Gradient Regularization of Newton Method with Bregman Distances
• Regularized Newton Method with Global O(1/k²) Convergence
• Globally Convergent Coderivative-Based Generalized Newton Methods in Nonsmooth Optimization
• Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition
• A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
• Second order semi-smooth Proximal Newton methods in Hilbert spaces
• A Globally Convergent Proximal Newton-Type Method in Nonsmooth Convex Optimization
• A Semismooth Newton Method for Support Vector Classification and Regression
• Active-set Newton methods and partial smoothness
• Partial smoothness and constant rank
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Sensitivity Analysis for Mirror-Stratifiable Convex Functions
• Nonsmooth optimization using Taylor-like models: error bounds,\n convergence, and termination criteria
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• A Regularized Semi-Smooth Newton Method With Projection Steps for Composite Convex Programs
• Error bounds, quadratic growth, and linear convergence of proximal\n methods
• From error bounds to the complexity of first-order descent methods for\n convex functions
• From error bounds to the complexity of first-order descent methods for convex functions
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Model Consistency of Partly Smooth Regularizers
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods
• Optimality, identifiability, and sensitivity
• Proximal alternating minimization and projection methods for nonconvex\n problems. An approach based on the Kurdyka-Lojasiewicz inequality
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Nonlinear total variation based noise removal algorithms

Cited by

• Mesh-dependent iteration count growth in primal-dual active set strategies

Related

• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• On a globally convergent semismooth* Newton method in nonsmooth nonconvex optimization
• Global Convergence of Semismooth Newton Methods for Quadratic Problems
• An efficient primal dual semismooth Newton method for semidefinite programming
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond