Newton acceleration on manifolds identified by proximal-gradient methods

Gilles Bareilles (1) , Franck Iutzeler (1) , Jérôme Malick (1)

1 DAO - Données, Apprentissage et Optimisation

Proximal methods are known to identify the underlying substructure of nonsmooth optimization problems. Even more, in many interesting situations, the output of a proximity operator comes with its local structure to no additional cost, and convergence is improved once some final neighborhood of interest is attained. However, it is impossible in general to know whether the current structure is final or not; such highly valuable information has to be exploited adaptively. To do so, we place ourselves in the case where a proximal gradient method can identify manifolds of differentiability of the nonsmooth objective. Leveraging this manifold identification, we show that Riemannian Newton-like methods can be intertwined with the proximal gradient steps to drastically boost the convergence. We prove the superlinear convergence of the algorithm when solving some nondegenerated nonsmooth nonconvex optimization problems. We provide numerical illustrations on optimization problems regularized by l1-norm or the trace-norm.

Domaines: Traitement du signal et de l'image [eess.SP]; Optimisation et contrôle [math.OC]

Gilles Bareilles, Franck Iutzeler, Jérôme Malick. Newton acceleration on manifolds identified by proximal-gradient methods. 2021. ⟨hal-03197686v1⟩