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.
47 personnes membres du GdR ISIS, et 28 personnes non membres du GdR, sont inscrits à cette réunion.
Capacité de la salle : 100 personnes.
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 :
D'autres interventions invitées permettront de présenter d'autres récents travaux sur le sujet :
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.
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)
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
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 IASIS - CNRS - 2024.