An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization
\(\)
We introduce method iR2N, a modified proximal quasi-Newton method for minimizing the sum of a \(C^1\) function \(f\) and a lower semi-continuous prox-bounded \(h\) that permits inexact evaluations of \(f\), \(\nabla f\) and of the relevant proximal operators. Both \(f\) and \(h\) may be nonconvex. In applications where the proximal operator of \(h\) is not known analytically but can be evaluated via an iterative procedure that can be stopped early, or where the accuracy on \(f\) and \(\nabla f\) can be controlled, iR2N can save significant computational effort and time. At each iteration, iR2N computes a step by approximately minimizing the sum of a quadratic model of \(f\), a model of \(h\), and an adaptive quadratic regularization term that drives global convergence. In our implementation, the step is computed using a variant of the proximal-gradient method that also allows inexact evaluations of the smooth model, its gradient, and proximal operators. We assume that it is possible to interrupt the iterative process used to evaluate proximal operators when the norm of the current iterate is larger than a fraction of that of the minimum-norm optimal step, a weaker condition than others in the literature. Under standard assumptions on the accuracy of \(f\) and \(\nabla f\), we establish global convergence in the sense that a first-order stationarity measure converges to zero and a worst-case evaluation complexity in \(O(\epsilon^{-2})\) to bring said measure below \(\epsilon > 0\). Thus, inexact evaluations and proximal operators do not deteriorate asymptotic complexity compared to methods that use exact evaluations. We illustrate the performance of our implementation on problems with \(\ell_p\)-norm, \(\ell_p\) total-variation and the indicator of the nonconvex pseudo \(p\)-norm ball as regularizers. On each example, we show how to construct an effective stopping condition for the iterative method used to evaluate the proximal operator that ensures satisfaction of our inexactness assumption. Our results show that iR2N offers great flexibility when exact evaluations are costly or unavailable, and highlight how controlled inexactness can reduce computational effort effectively and significantly.