# A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

arXiv: https://arxiv.org/abs/2409.19428 · HTML: https://mlsanity.com/paper/2409.19428/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 28 Sep 2024.

## Builds on (most cited first, 15 of 15)

- [Forward-backward quasi-Newton methods for nonsmooth optimization problems](https://mlsanity.com/paper/1604.08096/) (2016)
- [An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions](https://mlsanity.com/paper/1410.0641/) (2014)
- [Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms](https://mlsanity.com/paper/1606.06256/) (2016)
- [On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence](https://mlsanity.com/paper/1801.08691/) (2018)
- [A Simple and Efficient Algorithm for Nonlinear Model Predictive Control](https://mlsanity.com/paper/1709.06487/) (2017)
- [A Proximal Quasi-Newton Trust-Region Method for Nonsmooth Regularized Optimization](https://mlsanity.com/paper/2103.15993/) (2021)
- [A Levenberg-Marquardt Method for Nonsmooth Regularized Least Squares](https://mlsanity.com/paper/2301.02347/) (2023)
- [A smoothing proximal gradient algorithm for matrix rank minimization problem](https://mlsanity.com/paper/2103.09530/) (2021)
- [An inexact regularized proximal Newton method for nonconvex and nonsmooth optimization](https://mlsanity.com/paper/2209.09119/) (2022)
- [Convergence Properties of Monotone and Nonmonotone Proximal Gradient Methods Revisited](https://mlsanity.com/paper/2112.01798/) (2021)
- [Efficient Regularized Proximal Quasi-Newton Methods for Large-Scale Nonconvex Composite Optimization Problems](https://mlsanity.com/paper/2210.07644/) (2022)
- [Proximal gradient methods beyond monotony](https://mlsanity.com/paper/2211.04827/) (2022)
- [The Indefinite Proximal Gradient Method](https://mlsanity.com/paper/2309.08433/) (2023)
- [Complexity of trust-region methods with unbounded Hessian approximations for smooth and nonsmooth optimization](https://mlsanity.com/paper/2312.15151/) (2023)
- [Complexity of trust-region methods in the presence of unbounded Hessian approximations](https://mlsanity.com/paper/2408.06243/) (2024)

## Abstract (arXiv)

We develop R2N, a modified quasi-Newton method for minimizing the sum of a C1 function f and a lower semi-continuous prox-bounded h. Both f and h may be nonconvex. At each iteration, our method computes a step by minimizing the sum of a quadratic model of f, a model of h, and an adaptive quadratic regularization term. A step may be computed by a variant of the proximal-gradient method. An advantage of R2N over trust-region (TR) methods is that proximal operators do not involve an extra TR indicator. We also develop the variant R2DH, in which the model Hessian is diagonal, which allows us to compute a step without relying on a subproblem solver when h is separable. R2DH can be used as standalone solver, but also as subproblem solver inside R2N. We describe non-monotone variants of both R2N and R2DH. Global convergence of a first-order stationarity measure to zero holds without relying on local Lipschitz continuity of nabla f, while allowing model Hessians to grow unbounded, an assumption particularly relevant to quasi-Newton models. Under Lipschitz-continuity of nabla f, we establish a tight worst-case complexity bound of O(1 / ε2/(1 - p)) to bring said measure below ε > 0, where 0 ≤ p < 1 controls the growth of model Hessians. The latter must not diverge faster than |Sk|p, where Sk is the set of successful iterations up to iteration k. When p = 1, we establish the tight exponential complexity bound O(exp(c ε-2)) where c > 0 is a constant. We describe our Julia implementation and report numerical experience on a classic basis-pursuit problem, an image denoising problem, a minimum-rank matrix completion problem, a nonlinear support vector machine and an inverse nonlinear problem.