LeAP--SSN: A semismooth Newton method with global convergence rates

Abstract

We propose LeAP-SSN (Levenberg?Marquardt Adaptive Proximal SemismoothNewton 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?Łojasiewicz 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/sqrtk) under nonconvexity in terms of subgradients, and linear convergence under a Polyak?Łojasiewicz 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.