Séance du 14 mars 2016

Séance organisée par Erwan Le Pennec et Joseph Salmon.

Lieu : IHP, Amphithéâtre Hermite.

14.00 : Vincent DUVAL, (INRIA, Équipe Mokaplan)

Titre : Déconvolution avec a priori de parcimonie, avec ou sans grilles.

Résumé :

Le problème de déconvolution consiste à retrouver un signal à partir de ses basses fréquences et d'un a priori sur le type de signal recherché. Introduites en Géophysique pour la reconstruction de signaux concentrés sur quelques pics (des sommes de masses de Dirac), les techniques de déconvolution avec régularisation de type $\ell^1$ ont connu leur essor à la suite notamment des travaux de Donoho (Basis Pursuit) d'une part et Tibshirani (LASSO) d'autre part.

Il existe de nombreux travaux sur les propriétés de robustesse et de stabilité du support pour le LASSO, mais on montrera dans cet exposé que dans le cas particulier de la déconvolution sur des grilles fines, les critères proposés ne sont pas valides. Le support n’est pas stable, et le LASSO identifie en fait deux fois plus de masses de Diracs que celles présentes dans le signal original.

On fera le lien entre les propriétés du LASSO sur des grilles fines et un problème récent, étudié notamment par Candès et Fernandez-Granda, pour la reconstruction de mesures de Radon dans un cadre continu. Enfin, on étudiera ce problème continu dans le cas de masses de Dirac très proches.

15.00 : Charles DOSSAL (Université Bordeaux 1)

Titre : Convergence et stabilité de FISTA (Fast Iterative Soft Thresholding Algorithm).

Résumé :

FISTA est une version accélérée de l'algorithme algorithme proximal Forward Backward utilisé pour minimiser la somme F

de deux fonctions f et g convexes dont une seule, disons f, est différentiable. Cette accélération est due à Beck et Teboulle en 2008 et est largement utilisée en optimisation et particulièrement en traitement d'images.

Je présenterai des résultats issus de deux collaborations. La première avec Antonin Chambolle traite de la convergence

des itérés produits par FISTA qui n'était pas prouvée jusqu'à présent. Nous verrons que nous avons dû modifier légèrement l'algorithme initial pour démontrer une telle convergence. La seconde avec Jean-François Aujol traite de la stabilité aux erreurs de la convergence des itérés et de la décroissance de la valeur de la fonctionnelle. On s'intéressera aux situations ou l'opérateur proximal de g et le gradient de f sont entachés d'erreurs.

Nous verrons en particulier qu'il existe des régimes d'erreurs ou il est possible de faire mieux que FISTA et Forward Backward en adaptant l'algorithme proximal au niveau de perturbation.

Le cas d'erreurs stochastiques sur le gradient qui peut être intéressant dans des utilisations de FISTA en machine learning sera également abordé.

https://hal.inria.fr/hal-01060130/file/Fista10.pdf

https://hal.archives-ouvertes.fr/hal-01163432/file/StabFista_siam_rev_final.pdf

16.00 : Massil ACHAB, (École Polytechnique)

Titre : SGD with Variance Reduction Beyond Empirical Risk Minimization

Résumé :

We introduce a doubly stochastic proximal gradient algorithm for optimizing a finite average of smooth convex functions, whose gradients depend on numerically expensive expectations. Our main motivation is the acceleration of the optimization of the regularized Cox partial-likelihood (the core model used in survival analysis), but our algorithm can be used in different settings as well. The proposed algorithm is doubly stochastic in the sense that gradient steps are done using stochastic gradient descent (SGD) with variance reduction, where the inner expectations are approximated by a Monte-Carlo Markov-Chain (MCMC) algorithm. We derive conditions on the MCMC number of iterations guaranteeing convergence, and obtain a linear rate of convergence under strong convexity and a sublinear rate without this assumption. We illustrate the fact that our algorithm improves the state-of-the-art solver for regularized Cox partial-likelihood on several datasets from survival analysis.