3 Presentations

• 
  03:30 PM - 03:55 PM

  An Inexact Modified Quasi-Newton method for Nonsmooth Regularized Optimization

  • Nathan Allaire, presenter, Polytechnique Montréal (GERAD)

  We propose an inexact extension of the R2N algorithm, a Modified Quasi-Newton method tailored for nonsmooth regularized optimization problems. Our approach accommodates inexact evaluations of the objective function, its gradient, and the proximal operator. We provide a convergence analysis, demonstrating that the method retains the same iteration complexity as its exact counterpart. Numerical experiments highlight that maximizing the inexactness yields substantial computational savings without compromising the quality of the solution.

• 
  03:55 PM - 04:20 PM

  A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

  • Mohamed Laghdaf Habiboullah, presenter, GERAD - Polytechnique Montréal
  • Youssef Diouane, Polytechnique Montréal
  • Dominique Orban, GERAD - Polytechnique Montréal

  We develop R2N, a modified quasi-Newton method for minimizing the sum of a 1 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 ∇f, while allowing model Hessians to grow unbounded, an assumption particularly relevant to quasi-Newton models. Under Lipschitz-continuity of ∇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 |k|p, where k 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 basis-pursuit problem, image denoising, minimum-rank matrix completion, and a nonlinear support vector machine. In particular, the minimum-rank problem cannot be solved directly at this time by a TR approach as corresponding proximal operators are not known analytically.

  Link to the paper: https://arxiv.org/abs/2409.19428

• 
  04:20 PM - 04:45 PM

  A Stochastic Levenberg-Marquardt Method for large and Nonsmooth Regularized Inverse Problems

  • Valentin Dijon, presenter, GERAD - Polytechnique Montréal
  • Youssef Diouane, Polytechnique Montréal
  • Dominique Orban, GERAD - Polytechnique Montréal

  To solve nonlinear Least-Squares problems whose objective is to minimize a function which is written as the half of the squared norm of a residual function F, a Levenberg-Marquardt method can be used. A new one has been devised by adding a nonsmooth regularizer (i.e. a proper, lower semi-continuous, and prox-bounded function h is added to the objective function). Besides, in a context of large optimization problems, we compute the Least-Squares residual and its Jacobian using three different sampling strategies using a constant, nondecreasing, and adaptive sample rate.

  This stochastic fashion prevents us from using the full Jacobian or residuals when unsmooth regularization helps to select a solution with specific properties of our problem. This method has been implemented in the Julia programming language and has been run on a collection of problems from the packages RegularizedProblems.jl and BundleAdjustmentProblems.jl. By naming epsilon the tolerance of our stopping criterion, the theoretical mean complexity of the algorithm is proportional to epsilon to the power of (-2), just like the existing methods. So, we have an algorithm with nonsmooth regularization which, thanks to sampling, can solve large problems such as Bundle Adjustment problems or binary classification by nonlinear SVM.