Scientific computing seminar

Lorenz Richter


18 June 2018, 14:00, salle de séminaire du CERMICS

Optimal importance sampling using stochastic control

We investigate importance sampling of stochastic processes and outline its connections to optimal control and large deviations theory. One can formally identify an optimal change of measure, however, especially in high dimensions clever numerical strategies are necessary to reduce variance of Monte Carlo estimates effectively. We review some iterative and approximate approaches and outline how the problem can be seen from different perspectives.

Pierre Alquier


25 June 2018, 9:30, salle de séminaire du CERMICS

Variational approximations in machine learning: theory and applications

Many theoretical tools allow to derive non-asymptotic risk bounds for randomized estimators: aggregation theory, PAC-Bayesian bounds… but the corresponding statistical distribution, the Gibbs posterior, is unfortunately often intractable. The classical approach to overcome this difficulty is Markov chain Monte Carlo, but this is usually too slow for big datasets. A popular alternative is to compute variational approximations of the posterior thanks to fast approximation algorithms. In this talk,

1) I will provide a short introduction to aggregation theory and to variational approximation,

2) I will present the theoretical analysis of the paper [P. Alquier, J. Ridgway , N. Chopin , On the Properties of Variational Approximations of Gibbs Posteriors, Journal of Machine Learning Research, 2016]. This paper contains an attempt of a general theory on variational approximations.

3) I will provide various applications to statistics and machine learning, with a special focus on recent results in matrix completion and collaborative filtering taken from [V. Cottet, P. Alquier, 1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation, Machine Learning, 2018].

Yohann De Castro


26 June 2018, 14:30, salle de séminaire du CERMICS

Le Problème des Moments et son Impact en Machine Learning

Dans cet exposé, nous nous intéresserons au problème suivant : étant donnée une suite de nombres réels, à quelle conditions celle-ci est une suite de moments d’une mesure positive sur un domaine de R^n fixé à l’avance ? Peut-on vérifier qu’une suite tronquée de cette suite (on garde que les m premières valeurs) est bien une suite tronquée de moments en temps polynomial ? De nouveaux outils de géométrie algébrique computationnelle permettent de répondre à ces questions, ce sont les hiérarchies de Lasserre. Ces outils sont bien connus en théorie de la complexité en informatique théorique car ils donnent systématiquement le meilleur algorithme en temps polynomial pour un grand nombre de problème d’optimisation combinatoire sur les graphes (Max Cut, Planted Clique…). Dans cet exposé nous présenterons ces outils et leur utilisation récente en Machine Learning.

David Aristoff

Colorado State University

2 July 2018 10:00 and 3 July 2018 10:00, salle de séminaire du CERMICS

Optimization of weighted ensemble sampling

We show how to optimize weighted ensemble (WE) sampling in rare event
and steady state settings. WE is an unbiased resampling method for
variance reduction. Traditionally, WE has been based on an ad hoc
rule: binning state space and maintaining roughly the same number of
replicas in each populated bin. We describe a general recipe for
optimizing replica allocation, using first principles in a framework
more general than the usual Feynman Kac/Gibbs-Boltzmann setting.
Though it is not practical to implement the optimal strategy exactly,
in some cases it may be approximated by a cheaper proxy model. We show
how to do this using the usual bin structure of WE. Numerical results
suggest our replica allocation strategy is significantly better than
the traditional uniform allocation.

Archive of past seminars: here

Organizers: Antoine Levitt, Julien Reygner.