A coderivative-based nonmonotone Newton method with HAN line search and adaptive regularization cuts iterations and CPU time on Lasso, SVM, and logistic Lasso

It introduces the NCN method, which uses the Mordukhovich coderivative of the gradient mapping as a generalized Hessian together with the HAN line search and adaptive regularization for nonsmooth optimization. Existing coderivative-based Newton methods use either an Armijo line search, which may accept excessively small steps, or a Wolfe line search, which adds a curvature condition and higher cost, and they rely on fixed regularization; NCN switches adaptively among Armijo, nonmonotone Armijo, and nonmonotone Wolfe stages based on step size and adjusts the regularization parameter via a trust-region ratio or the accepted step length. Proposition 3.1 shows that under positive semidefiniteness of the generalized Hessian the search direction exists and is a descent direction; Proposition 4.1 establishes global convergence from arbitrary initial points; Proposition 4.2 proves Q-superlinear convergence under semismooth* and metric regularity conditions. In the Lasso experiments NCN attains the lowest CPU time in most instances and the fewest iterations in most cases, while GRNM-W incurs noticeably higher CPU time consistent with the extra cost of the Wolfe line search.

It extends the convergence analysis to inexact second-order information within a unified framework. Earlier convergence results for coderivative-based Newton methods mainly target exact generalized Hessians; this analysis allows an approximate generalized Hessian as long as it is positive semidefinite and its approximation error vanishes faster than the distance to the solution, preserving global and local superlinear convergence. The global convergence result in Proposition 4.1 is independent of the particular choice of second-order information; Proposition 4.2 and Corollary 4.3 give superlinear convergence when the approximation error decreases fast enough, including along the algorithmic step direction, and the text notes that in a semi-stochastic setting this can be controlled by increasing the number of samples.

It extends NCN to convex composite optimization through the forward-backward envelope, covering Lasso and SVM. Convex composite problems are first-order nonsmooth, whereas NCN targets second-order nonsmooth systems; the forward-backward envelope preserves the set of minimizers while endowing the problem with a second-order nonsmooth structure suited to NCN, and the paper derives explicit Newton systems for computing search directions in the Lasso and SVM cases. Proposition 5.2 lists smoothness and convexity properties of the forward-backward envelope; Propositions 5.3-5.5 provide coderivative characterizations, the equivalence between metric regularity and tilt stability, and semismooth* and directional differentiability conditions. In the SVM experiments NCN requires less CPU time than CNFB in both low- and high-rank cases.

It proposes a coderivative-based proximal Newton (CPN) method for the case where the smooth component is nonquadratic and demonstrates it on logistic Lasso. CPN constructs a quadratic composite subproblem from a Taylor expansion at each iteration and uses NCN as the inner solver, extending the analysis developed for quadratic smooth components to nonquadratic smooth components. In the logistic Lasso experiments CPN and FISTA are the only methods that consistently obtain high-accuracy solutions across all tested cases under the post-processed residual criterion, and CPN requires fewer iterations than FISTA while remaining competitive in CPU time with SpaRSA and PNOPT.

The results target nonsmooth optimization problems whose objective is of class C^{1,1} or of convex composite form with a positive semidefinite generalized Hessian; in this setting NCN converges globally from arbitrary initial points and attains local superlinear convergence under semismooth* and metric regularity conditions. For readers who want to bring second-order information to machine learning models such as Lasso, SVM, and logistic Lasso, the paper gives a concrete route through the forward-backward envelope and the proximal Newton framework, and shows that the HAN line search can be used as a general globalization strategy independent of the specific algorithm.

The numerical comparisons rely on fixed computational environments within each problem class and on randomly generated data, with Lasso, SVM, and logistic Lasso run under different MATLAB versions and hardware; the methods use different residual definitions, and logistic Lasso is evaluated through a post-processed residual. Whether assumptions such as positive semidefiniteness of the generalized Hessian, semismooth*, metric regularity, and tilt stability hold in a given application needs to be verified for the specific model. The paper notes open directions including semi-stochastic and lazy variants, the case where both first- and second-order information are inexact, and extension to nonconvex problems.