Vous êtes ici : Accueil » Réunions » Réunion

Identification

Identifiant: 
Mot de passe : 

Mot de passe oublié ?
Détails d'identification oubliés ?

Sur les interactions Méthodes de Monte Carlo et Algorithmes d'Optimisation

Nous vous rappelons que, afin de garantir l'accès de tous les inscrits aux salles de réunion, l'inscription aux réunions est gratuite mais obligatoire.

Inscriptions closes à cette réunion.

Inscriptions

65 personnes membres du GdR ISIS, et 28 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.

Instructions pour une demande de mission par le GdR ISIS

Le GdR ISIS prend en charge les déplacements des organisateurs des réunions et des orateurs. Le GdR prend aussi en charge les déplacements des participants aux réunions membres d'un laboratoire adhérent du GdR dans la limite d'un doctorant et d'un permanent par laboratoire académique et par réunion, ou d'une personne par adhérent du club des partenaires et par réunion.

La plus grande partie du budget du GdR ISIS est consacrée à la prise en charge de ces missions. Pour que le GdR puisse financer le plus grand nombre de réunions, les participants à ces réunions sont vivement incités à choisir les billets les moins chers. Seuls les billets de train ou d'avion en deuxième classe, non échangeables et non remboursables sont pris en charge. Le GdR se réserve le droit de refuser une demande de billet dont le prix excède la moyenne des prix couramment pratiqués pour le trajet de la mission.

Pour le transport et pour l'hébergement, vous êtes priés d'utiliser le portail SIMBAD du CNRS si vous en avez la possibilité. Cela est en particulier obligatoire si vous êtes membre d'une unité CNRS (UPR, UMR, UMI, URA, FRE). Les réservations d'hôtel sont possibles si la réunion dure plus d'une journée ou si le lieu d'habitation le justifie. Dans le cas où le laboratoire n'est pas une unité CNRS, merci d'envoyer votre demande de prise en charge de la mission à l'adresse DR01.SoutienUnites@cnrs.fr en précisant que la mission relève du GdR ISIS. Si vous utilisez votre véhicule personnel pour une distance supérieure à 300 kilomètres (aller+retour), le GdR ISIS ne rembourse pas vos frais de transport.

Les demandes de mission et les réservations sur le site SIMBAD doivent impérativement être effectuées au moins deux semaines avant la date de la mission.

Aucun remboursement de frais de transport ou d'hôtel avancés par l'agent ne peut plus être effectué au retour de la mission.

Annonce

Dans des problématiques rencontrées en traitement du signal et des images, le traitement de l'information se heurte à des questions de plus en plus difficiles, notamment à cause de la complexité des modèles d'observation, de la taille importante du problème ou encore de données massives ou manquantes. Pour surmonter ces difficultés, de nouvelles techniques de calcul exploitant le potentiel des algorithmes de Monte Carlo et de l'optimisation ont suscité un très fort engouement ces dernières années; l'objectif étant d'aboutir à des schémas algorithmiques possédant des garanties de convergence et présentant un coût de calcul maîtrisé.

Le but de cette journée, commune aux actions "Optimisation" et "Méthodes de simulation stochastiques" au sein du thème A, est de faire le point sur les avancées récentes dans la proposition d'approches couplant optimisation et méthodes de Monte Carlo.

Pendant cette journée deux exposés tutoriels permettront de faire le point sur l'association des méthodes de Monte-Carlo et de l'optimisation :

  1. Eric Moulines (CMAP, Ecole Polytechnique) : Tutoriel sur les méthodes de Monte Carlo et Interactions avec l'optimisation (Langevin, Hamiltonien, etc.)
  2. Emilie Chouzenoux (LIGM, Université Paris-Est Marne-la-Vallée) : Tutoriel sur les algorithmes stochastiques pour l'optimisation proximale

D'autres interventions invitées permettront de présenter d'autres récents travaux sur le sujet :

  1. François Orieux (LSS, Université Paris-Sud) : Présentation courte sur l'échantillonnage de Gibbs guidé par le gradient
  2. Gabriel Stoltz (CERMICS, Ecole des Ponts ParisTech) : Présentation courte Using Metropolis schemes to estimate correlation functions
  3. Caroline Chaux (I2M, Aix-Marseille Université) : Présentation courte sur une méthode de Monte-Carlo Hamiltonienne pour une fonction énergie non différentiable

Les personnes souhaitant présenter leurs travaux sont invitées à faire part de leur intention en envoyant un titre et un résumé de 15-20 lignes (en français) à Gersende FORT (gersende.fort@telecom-paristech.fr) avant le 6 novembre 2015.

Les présentations auront lieu en français.

Organisateurs :

Gersende FORT (gersende.fort@telecom-paristech.fr), Saïd MOUSSAOUI (said.moussaoui@irccyn.ec-nantes.fr), Nelly PUSTELNIK (nelly.pustelnik@ens-lyon.fr), François SEPTIER (francois.septier@telecom-lille.fr)

Programme

10h -11h : Eric Moulines (CMAP, Ecole Polytechnique)
Efficient sampling of log-concave distributions over high-dimensional spaces

11h - 11h25 : Rémi Bardenet (CRIStAL UMR CNRS 9189)
Accélérer Metropolis-Hastings pour les grands jeux de données: comment l'optimisation peut-elle aider ?

11h40 - 12h15 : Caroline Chaux (I2M, Aix-Marseille Université)
Approche Hamiltonienne et méthode de Monte Carlo pour l'échantillonnage de loi non différentiable

12h15 - 13h45 : Pause repas

13h45 - 14h45 : Emilie Chouzenoux (LIGM, Université Paris-Est Marne-la-Vallée)
An overview of stochastic methods for solving optimization problems

14h45 - 15h20 : Olivier Féron (EDF R&D, Clamart et Univ. Paris Dauphi,e, Paris)
Gradient Scan Gibbs Sampler: an efficient algorithm for high-dimensional Gaussian distributions

15h35 - 16h10 : Gabriel Stoltz (CERMICS, Ecole des Ponts ParisTech)
Using Metropolis schemes to estimate correlation functions

16h10 - 16h35 : Mathieu Brédif et Julien Perret (IGN, Laboratoire MATIS)
Optimisation stochastique, (RJ)MCMC et applications géospatiales.

16h35 - 17h : Marcelo Pereyra (University of Bristol, UK)
One thousand and one nights of proximal MCMC algorithms

Résumés des contributions

Eric Moulines (CMAP, Ecole Polytechnique)

Titre : Efficient sampling of log-concave distributions over high-dimensional spaces

Abstract : Sampling over high-dimensional space has become a prerequisite in the applications of Bayesian statistics to machine learning problem. In many situations of interest, the log-posterior distribution is concave. The likelihood part is generally smooth and gradient Lipshitz while the prior is concave but typically not smooth (the archetypical problem is the LASSO or the elastic-net penalty, but many other problems can be cast into this framework). We will describe methods to sample such distributions, which are adapted from the state-of-the-art optimization procedures which have been developed in this context. We will also provide convergence in Wasserstein distance to the equilibrium, showing explicitly the dependence in the dimension of the parameter space and the sparsity (effective dimension of the model). Several examples will be presented to illustrate our results.

Rémi Bardenet (CRIStAL UMR CNRS 9189, Univ. Lille)

Titre : Accélérer Metropolis-Hastings pour les grands jeux de données : comment l'optimisation peut-elle aider ?

Abstract : Les méthodes MCMC sont souvent jugées trop chères pour des applications où les données sont massives, et particulier pour l'inférence bayésienne sur des jeux de données contenant un grand nombre n d'individus. Bardenet, Doucet et Holmes (ICML, 2014) ont proposé un algorithme Metropolis-Hastings (MH) approché qui utilise des inégalités de concentration pour tenter de prendre chaque décision de rejet dans MH avant d'avoir vu toutes les données. Cet algorithme hérite de l'uniforme ergodicité éventuelle du MH idéal, qui utiliserait toutes les données à chaque itération, et la cible de cet algorithme approché est également proche en variation totale de celle du MH idéal. Malheureusement, ces propriétés ont un coût : chaque itération semble nécessiter O(n) données, ce qui n'est pas satisfaisant pour des données massives.

Dans les cas favorables où la cible peut être dérivée et où l'on contrôle ses dérivées, nous étudions comment l'obtention d'un maximum approché de la vraisemblance, obtenu par exemple par gradient stochastique, permet de construire des estimateurs de la log vraisemblance de faible variance, ce qui conduit à un coût par itération du MH approché de o(n), voire O(1) dans des cas extrêmes. Ceci illustre un nouvel usage des algorithmes d'optimisation pour l'accélération de l'inférence bayésienne, en fournissant à MH une statistique qui résume les données suffisamment pour lui permettre à MH de se passer de voir toutes ces dernières. Cet exposé est basé sur les chapitres 7 et 8 de la prépublication [Bardenet, Doucet & Holmes, "On MCMC for tall data", Arxiv, 2015].

Caroline Chaux (I2M, Aix-Marseille Université)

Titre : Approche Hamiltonienne et méthode de Monte Carlo pour l'échantillonnage de loi non différentiable

Abstract : On s'intéresse dans ce travail à des techniques d'échantillonnage selon des distributions en grande dimension. Les méthodes Hamiltoniennes sont bien adaptées dans ce cas; cependant, elles requièrent que les distributions soient liées à des énergies (potentiels) différentiables.

Nous proposons de contourner cette limitation en introduisant la notion de sous-différentiel dans ces dynamiques Hamiltoniennes. Plus précisément, nous proposons un schéma modifié de discrétisation de la dynamique Hamiltonienne (leapfrog) dans lequel nous introduisons une étape proximale.

On montre que cette technique permet d'obtenir des échantillons possédant de bonnes propriétés tout en convergeant plus vite que les approches classiques vers la loi cible.

On l'applique également à un problème de débruitage d'image.

Emilie Chouzenoux (LIGM, Univ. Marne-la-Vallée)

Titre : An overview of stochastic methods for solving optimization problems

Abstract : Many problems encountered in machine learning, inverse problems, or adaptive filtering require the minimization of a cost function which is the sum of the expectation of a stochastic term and a regularizing deterministic term. However, the integral involved in the first term often cannot be computed in practice since it is generally high-dimensional and the underlying probability measure is usually unknown. This talk will present two main approaches that have been proposed in the literature to overcome this issue. We start with online learning algorithms based on extensions of the well-known stochastic gradient descent (SGD) approach. Then, assuming that the expected loss function is approximated by an empirical loss, we present stochastic algorithms that can be used to solve efficiently the resulting batch optimization problem.

M. Pereyra, P. Schniter, E. Chouzenoux, J.-C. Pesquet, J.-Y. Tourneret, A. Hero and S. McLaughlin. A Survey of Stochastic Simulation and Optimization Methods in Signal Processing. IEEE Journal of Selected Topics in Signal Processing, 2015 (to appear). http://arxiv.org/abs/1505.00273

Olivier Féron (EDF R&D, Clamart, et Univ. Paris Dauphine, Paris)

Titre : Gradient Scan Gibbs Sampler: an efficient algorithm for high-dimensional Gaussian distributions

Abstract : This talk deals with Gibbs samplers that include high dimensional conditional Gaussian distributions. It proposes an efficient algorithm that avoids the high dimensional Gaussian sampling and relies on a random excursion along a small set of directions. The algorithm is proved to converge, i.e. the drawn samples are asymptotically distributed according to the target distribution. Our main motivation is in inverse problems related to general linear observation models and their solution in a hierarchical Bayesian framework implemented through sampling algorithms. It finds direct applications in semi-blind / unsupervised methods as well as in some non-Gaussian methods.

Gabriel Stoltz (CERMICS, ENPC)

Titre : Using Metropolis schemes to estimate correlation functions

Abstract : Langevin and overdamped Langevin dynamics are often used in molecular simulation as reference dynamics to deduce static and dynamical properties of system of interest. In some cases, standard discretization schemes (such as Euler-Maruyama) are unstable because the force fields are not globally Lipschitz. In this case, it is useful to stabilize the discretizations of SDEs by superimposing a Metropolis-Hasting accept/reject step.

However, the rejection procedure corrupts in general the estimation of the dynamical properties. In this talk, I first quantify the error on integrated correlations as a function of the time step used to integrate the SDE; and then present several ways to reduce this error.

Mathieu Bredif (MATIS, IGN)

Titre : Optimisation stochastique, (RJ)MCMC et applications géospatiales

Abstract : Les laboratoires de recherche de l'IGN développent depuis plusieurs années des algorithmes d'optimisation stochastique basés sur des échantillonneurs (RJ)MCMC. Ces travaux ont mené au développement d'une bibliothèque libres génériques pour l'optimisation stochastique (librjmcmc, implémentée en C++, java et scala). Les enjeux de tels outils portent à la fois sur la reproductibilité des travaux publiés, sur la réutilisabilité des codes développés, mais aussi sur l'accessibilité de telles approches (notamment les échantillonneurs (RJ)MCMC) à une plus large communauté de chercheurs. Plusieurs applications aux sciences de l'information géographique développées à l'IGN sont librement accessibles et permettent d'envisager la mise en concurrence d'algorithmes différents sur les mêmes problèmes. Nous pensons par ailleurs qu'une telle approche pourrait permettre de faire le lien entre des recherches finalisées et des recherches plus théoriques. Enfin, différents verrous concernant la sensibilité du paramétrage et le passage à l'échelle ouvrent des perspectives de recherches stimulantes.

Marcelo Pereyra (Univ. Bristol, UK)

Titre : One thousand and one nights of proximal MCMC algorithms

Abstract : This talk will present key lessons learnt in over three years of proximal MCMC sampling (Pereyra, 2015). The first part of the talk introduces these MCMC algorithms, which relate intimately high-dimensional Langevin sampling with convex analysis and convex optimisation. This then followed by main theoretical results on the stability and geometric ergodicity properties of the algorithms, comparisons with conventional Langevin sampling, and practical guidelines for their efficient algorithmic implementation. Moreover, the second part of the talk will showcase some exploratory experiments that where enabled by proximal MCMC algorithms and that highlight the synergy between stochastic simulation and optimisation. It will be shown that these experiments not only improve our understanding of Bayesian models for convex inverse problems, but may also lead in turn to developments in proximal optimisation for Bayesian computation, for instance in the selection of regularisation parameters for maximum-a-posteriori estimation.

Pereyra M.: Proximal Makov chain Monte Carlo algorithms, Statistics and Computing, 2015, http://dx.doi.org/10.1007/s11222-015-9567-4

Date : 2015-11-26

Lieu : Télécom ParisTech - Amphi B310


Thèmes scientifiques :
A - Méthodes et modèles en traitement de signal

Inscriptions closes à cette réunion.

Accéder au compte-rendu de cette réunion.

(c) GdR 720 ISIS - CNRS - 2011-2018.