L’Ecole doctorale : Mathématiques Hadamard

et le Laboratoire de recherche SAMOVAR – Services répartis, Architectures, Modélisation, Validation, Administration des Réseaux

présentent

l’AVIS DE SOUTENANCE de Monsieur Hugo MARIVAL

Autorisé à présenter ses travaux en vue de l’obtention du Doctorat de l’Institut Polytechnique de Paris, préparé à Télécom SudParis en :

« Algorithmes de chaînes de Markov séquentielles et d’inférence variationnelle : développement et analyse pour approcher des distributions complexes. »

le MERCREDI 19 MARS 2025 à 14h00

à

Amphithéâtre 4
Télécom Paris 19 Place Marguerite Perey 91120 Palaiseau

Membres du jury :

M. Randal DOUC, Professeur, Télécom SudParis, FRANCE – Directeur de these
M. Victor ELVIRA, Professor, University of Edinburgh, ROYAUME-UNI – Rapporteur
M. Jean-Michel MARIN, Professeur, Université de Montpellier, FRANCE – Rapporteur
M. Christian ROBERT, Professeur, Université Paris-Dauphine, FRANCE – Examinateur
Mme Hélène HALCONRUY, Maîtresse de conférences, Télécom SudParis, FRANCE – Examinateur
M. Julien STOEHR, Maître de conférences, Université Paris-Dauphine, FRANCE – Examinateur

« Algorithmes de chaînes de Markov séquentielles et d’inférence variationnelle : développement et analyse pour approcher des distributions complexes. »

présenté par Monsieur Hugo MARIVAL

Résumé :

Cette thèse s’intéresse à la conception et à l’analyse d’algorithmes de chaînes de Markov séquentielles et d’inférence variationnelle pour approcher des distributions complexes. La première partie introduit une nouvelle classe de chaînes de Markov, appelée Importance Markov chains. Il s’agit d’un méta-algorithme, construisant une chaîne de Markov étendue, visant une distribution cible sur sa première composante, à partir d’une chaîne de Markov auxiliaire, visant une distribution instrumentale, par réplication et rejet des points de la chaîne auxiliaire. Cette chaîne de Markov étendue, conserve les propriétés de la chaîne auxiliaire, à savoir la loi des grands nombres (LGN), le théorème central limite (CLT) et l’ergodicité géométrique, sous des conditions faibles et quasiment optimales. La deuxième partie développe un algorithme séquentiel de chaînes de Markov dites projetées (pMC), obtenues comme la projection d’une chaîne de Markov sur un sous-espace, permettant d’approcher une distribution cible fixée (ex. tempering) ou une séquence de distributions évoluant dans le temps pour des modèles espace-état (ex. filtrage particulaire). Similairement aux méthodes SMC, notre algorithme alterne entre phases de resampling et d’enrichissement-propagation, mais en maintenant des échantillons pMC à chaque étape. En particulier, nous nous appuyons sur l’Importance Markov chain développée dans la première partie pour l’étape de resampling, et sur des explorations à l’aide d’un noyau de Markov pour l’enrichissement-propagation. Sous des hypothèses faibles, nous prouvons que la LGN, le CLT et surtout l’ergodicité géométrique se propagent à travers les itérations, constituant une amélioration notable par rapport aux erreurs de resampling d’ordre O(1/N) en SMC. Par ailleurs, les propriétés atomiques de l’Importance Markov chain permettent de paralléliser notre algorithme sur M nœuds pour estimer des intégrales sous la loi cible, avec une erreur tendant vers 0 quand le nombre de nœuds tend vers l’infini. La dernière partie porte sur l’approximation paramétrique de la cible par des méthodes d’inférence variationnelle. Nous analysons notamment un algorithme d’inférence variationnelle par poids d’importance, célèbre pour son utilisation dans le cadre des auto-encodeurs variationnels, et prouvons des propriétés théoriques (consistance, normalité asymptotique, efficience) jusqu’alors inexistantes dans la littérature.

Abstract :

This thesis focuses on the design and analysis of sequential Markov chain algorithms and variational inference to approximate complex distributions. The first part introduces a new class of Markov chains, called Importance Markov chains. This is a meta-algorithm that constructs an extended Markov chain, targeting a complex distribution on its first component, starting from an auxiliary Markov chain targeting an instrumental distribution, by replicating and rejecting points from the auxiliary chain. This extended Markov chain retains the properties of the auxiliary chain, namely the law of large numbers (LLN), the central limit theorem (CLT), and geometric ergodicity, under weak and nearly optimal conditions. The second chapter develops a sequential algorithm, based on so-called projected Markov chains (pMC), obtained by projecting a Markov chain onto a subspace. This approach allows the approximation of a fixed target distribution (e.g., tempering) or sequence of distributions evolving over time for state-space models (e.g., particle filtering). Similar to SMC methods, our algorithm alternates between resampling and enrichment-propagation phases but maintains pMC samples at each step. In particular, we rely on the Importance Markov chain developed in the first part for the resampling step and on explorations using a Markov kernel for enrichment-propagation. Under weak assumptions, we prove that LLN, CLT, and especially geometric ergodicity propagate through the iterations, constituting a significant improvement over the typical O(1/N) error rate of resampling procedures in SMC. Furthermore, the atomic properties of the Importance Markov chain allow us to parallelize our algorithm for the empirical estimation of integrals under the target distribution, with an error tending toward 0 as the number of nodes increases. The last part focuses on the parametric approximation of a target distribution using variational inference. More specifically, we analyze a popular variational inference algorithm based on importance weighting, extensively used for variational autoencoders, and prove theoretical properties (consistency, asymptotic normality, efficiency) that were previously unavailable in the literature.