Taux de convergence des méthodes du premier ordre d’éclatement d’opérateurs

This manuscript is concerned with convergence analysis of first-order operator splitting methods that are ubiquitous in modern non-smooth optimization. It consists of three main theoretical advances on this class of methods, namely global convergence rates, novel operator splitting schemes and local linear convergence. First, we propose global (sub-linear) and local (linear) convergence rates for the inexact Krasnosel’skii-Mann iteration built from non-expansive operators, and its application to a variety of monotone operator splitting schemes. Then we design two novel multi-step inertial operator splitting algorithms, both in the convex and non-convex settings, and prove their global convergence. Finally, building on the key concept of partial smoothness, we present a unified and sharp local linear convergence analysis for the class of first-order proximal splitting methods for optimization. We show that for all these algorithms, under appropriate non-degeneracy conditions, the iterates generated by each of these methods will (i) identify the involved partial smooth manifolds in finite time, and then (ii) enter a local linear convergence regime. The linear convergence rates are characterized precisely based on the structure of the optimization problems, that of the proximal splitting scheme, and the geometry of the identified active manifolds. Our theoretical findings are systematically illustrated on applications arising from inverse problems, signal/image processing and machine learning.Ce manuscrit traite de l’analyse de convergence des méthodes du premier ordre d’éclatement d’opérateurs qui sont omniprésents en optimisation non-lisse moderne. Il consiste en trois avancées théoriques principales sur la caractérisation de cette classe de méthodes, à savoir: leur taux de convergence globale, de nouveaux schémas d’éclatement et une analyse de leur convergence linéaire locale. Dans un premier temps, nous proposons des taux de convergence globaux (sous-linéaires) et locaux (linéaires) pour l’itération de Krasnosel’skii-Mann inexacte, et ses applications à un large éventail de schémas d’éclatement d’opérateurs monotones. Ensuite, nous mettons au point deux algorithmes inertiels multi-pas d’éclatement d’opérateurs, pour le cas convexe et non-convexe, et établissons leurs garanties de convergence sur les itérées. Finalement, en s’appuyant sur le concept clé de la régularité partielle, nous présentons une analyse unifiée et précise de la convergence linéaire locale pour les méthodes d’optimisation proximales du premier ordre. Nous montrons que pour tous ces algorithmes, sous des conditions de non-dégénérescence appropriées, les itérées qu’ils génèrent (i) identifient les variétés actives de régularité partielle en temps finis, et ensuite (ii) entre dans un régime de convergence linéaire locale. Les taux de convergence linéaire sont caractérisés précisément, notamment en mettant en jeu la structure du problème d’optimisation, celle du schéma proximal, et la géométrie des variétés actives identifiées. Ces résultats théoriques sont systématiquement illustrés sur des applications issues des problèmes inverses, du traitement du signal et des images et de l’apprentissage