arXiv:2610.31992v1 Announce Type: new Abstract: We propose a globally convergent Newton method for convex composite optimization problems with polyhedral regularizers. The method rests on the observation that the proximal gradient step yields not only a new point but also a subgradient, which determines the face on which the linearization of the regularizer is exact. Minimizing a second-order model of the objective over this face produces a Newton direction that involves no generalized second-order information about the regularizer and is a descent direction for the objective itself. The method is therefore globalized by an Armijo line search on the original objective which, unlike forward-backward envelope techniques, requires only evaluations of the smooth component. We establish global convergence and local quadratic convergence to tilt-stable minimizers without any nondegeneracy condition, and show that the unit step is always accepted when the smooth component is quadratic, which yields a line-search-free method. The subproblems require only projections onto faces, which are explicit for the Lasso and nonnegative least squares and computable in linear time for the fused Lasso. Numerical experiments show that the method compares favorably with state-of-the-art solvers.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page