2015 | OPALE


Axe : DataSense, tâche 4
Sujet : Opérateurs monotones aléatoires et applications à l’optimisation stochastique
Directeurs : Walid HACHEM, Pascal BIANCHI, Jérémie JAKUBOWICZ
Institutions : LTCI, SAMOVAR
Laboratoire gestionnaire : LTCI
Doctorant : Adil SALIM
Début : automne 2015
Date de la soutenance : octobre ou novembre 2018
Productions scientifique :
Journal papers
A. Salim, P. Bianchi, and W. Hachem, Snake: a Stochastic Proximal Gradient Algorithm for Regularized Problems over Large Graphs, accepted for publication in Transaction on Automatic Control, March 2018.
P. Bianchi, W. Hachem, and A. Salim, A constant step Forward-Backward algorithm involving random maximal monotone operators, accepted for publication in Journal of Convex Analysis, March 2018.
P. Bianchi, W. Hachem, and A. Salim, Constant Step Stochastic Approximations Involving Differential Inclusions: Stability, Long-Run Convergence and Applications, accepted for publication in Stochastics, May 2018.
Conference papers
A. Salim, P. Bianchi and W. Hachem “A Splitting Algorithm for Minimization under Stochastic Linear Constraints”, ISMP 2018, Bordeaux, France.
A. Salim, P. Bianchi, and W. Hachem, “A Constant Step Stochastic Douglas-Rachford Algorithm with Application to Non Separable Regularization”, IEEE ICASSP 2018, Calgary, Canada.
A. Salim, P. Bianchi, and W. Hachem, “Snake: a Stochastic Proximal Gradient Algorithm for Regularized Problems over Large Graphs”, CAp 2017, Grenoble, France.
P. Bianchi, W. Hachem, and A. Salim “Convergence d’un algorithme du gradient proximal stochastique à pas constant et généralisation aux opérateurs monotones aléatoires”, GRETSI 2017, Juan-les-Pins, France.
A. Salim, P. Bianchi, and W. Hachem, “A Stochastic Proximal Point Algorithm for Total Variation Regularization over Large Scale Graphs”, IEEE CDC 2016, Las Vegas, USA.
R. Mourya, P. Bianchi, A. Salim and C. Richard, “An Adaptive Distributed Asynchronous Algorithm with Application to Target Localization”, IEEE CAMSAP 2017, Curacao, Dutch Antilles.
P. Bianchi, W. Hachem and A. Salim, “Building Stochastic Optimization Algorithms with Random Monotone Operators”, EUCCO 2016, Leuven, Belgium.

Contexte :
L’objectif général de la thèse est d’étudier le comportement des algorithmes d’optimisation fondés sur l’opérateur proximal dans un cadre bruité, et plus généralement, d’évaluer le comportement asymptotique d’équations d’évolution engendrées par des opérateurs monotones aléatoires. Il s’agit de bâtir les outils méthodologiques permettant d’établir un pont entre la théorie de l’approximation stochastique et celle des opérateurs monotones. Cette connexion théorique met en perspective la construction d’algorithmes stochastiques nouveaux, tels que des algorithmes primaux-duaux, à fort potentiel applicatif pour l’apprentissage statistique et le traitement du signal.

Objectif scientifique :
La thèse s’inscrit dans un programme de recherche articulé autour des opérateurs monotones aléatoires récemment abordé les membres de l’équipe du projet. En partant de l’algorithme où la suite de variables aléatoires observées (ξ k ) k∈N satisfait un modèle statistique donné (iid, martingale, ou chaîne de Markov), nous nous donnons les objectifs suivants :

  • Établir la convergence de la suite des itérées (x k ) ou de la suite de leurs moyennes empiriques vers l’ensemble des zéros de l’intégrale d’Aumann A, dans le cas où les pas γ k sont décroissants,
  • Plus généralement, montrer que les trajectoires convergent vers une solution du système dynamique x(t) ∈ −At?,
  • Considérer le cas où les pas γ sont constants. Dans ce cadre, les preuves de convergence sont d’une nature différente du cas où les pas tendent vers zéro,
  • Utiliser les résultats obtenus afin d’établir la convergence d’algorithmes plus complexes que l’al-

gorithme du point proximal, tels l’ADMM, les algorithmes primaux-duaux, les algorithmes de
descente par coordonnées.

  • Démontrer expérimentalement le bon comportement des méthodes grâce à des validations numériques sur des jeux de données massifs.

Perspectives :
En s’appuyant sur une expertise forte en matière d’approximation stochastique le projet permettra de développer des “solveurs” performants et mieux adaptés à une utilisation sur données massives que l’on rencontre typiquement dans les problèmes d’apprentissage statistique.