A Stochastic Levenberg-Marquardt Method for Nonsmooth Regularized Inverse Problems

On conçoit une variante stochastique avec régularisation non lisse de l’algorithme de Levenberg-Marquardt utilisé pour résoudre des problèmes de moindres carrés non linéaires. Notre algorithme est stochastique puisqu’il permet des évaluations inexactes du résidu moindres carrés et de sa jacobienne par un échantillonnage de ces derniers. La dimension non lisse du problème empêche d’utiliser des métriques de stationnarité usuelles en optimisation car celles-ci reposent sur le gradient. Par ailleurs, l’aspect stochastique lié aux estimations basées sur un échantillonnage impacte la manière de sélectionner le prochain itéré ainsi que la convergence de l’algorithme. Nous avons conçu une preuve de convergence de notre variante de l’algorithme de Levenberg-Marquardt accompagnée d’une étude de complexité. Nous avons testé notre méthode avec une implémentation dans le langage de programmation Julia sur des problèmes de grande dimension provenant de l’intelligence artificielle et de la vision par ordinateur. Les résultats de l’analyse théorique montrent que la borne de complexité de cette variante est analogue à d’autres déjà existantes, aussi bien lisses que non lisses. Les tests numériques révèlent que l’échantillonnage permet d’accélérer la vitesse de convergence en réduisant le coût numérique de l’optimisation pour certains problèmes. Ces tests montrent également que la régularisation non lisse permet d’obtenir une solution plus creuse et donc moins volumineuse à stocker.

Abstract

We designed a stochastic and nonsmooth variant of the Levenberg-Marquardt algorithm used to solve nonlinear least squares. With large-scale problems in mind, our algorithm is stochastic in the sense that it allows inexact evaluations of both the least-squares residual and its Jacobian by sampling them. The nonsmooth dimension of the problem prevents the use of common stationarity metrics in optimization because of the inability to access the gradient. Furthermore, the stochastic estimates based on sampling have an impact on how to select the next iterate and on the convergence of the algorithm. We designed a convergence analysis for the Levenberg-Marquardt algorithm, along with a complexity study. We tested our method with an implementation in Julia on high-dimensional problems that arise from artificial intelligence and computer vision. The results of the theoretical analysis show that the complexity bound of this variant is similar to other methods that already exist, both smooth and nonsmooth. Numerical tests illustrate that sampling accelerates the speed of convergence by reducing the numerical cost of optimization for some problems. These tests also show that nonsmooth regularization enables the return of a sparser solution that is cheaper to store.