Abstract: The present work proposes new methodologies for controlling the False Discovery Proportion (FDP) while accommodating different types of data structures arising from the underlying scientific context. Since the seminal work of Benjamini and Hochberg (1995) (BH) introducing the FDP, multiple testing procedures have found widespread applications across diverse domains. The BH procedure has facilitated the identification of significant variables within large data sets, providing insights to scientific questions in fields such as biology, medicine, or marketing research, by ensuring guarantees on the proportion of false discoveries. However, the BH procedure has several limitations, among which e.g. the fact that it is most effective for uniform p-values under the null; it is developed within a batch framework requiring simultaneous availability of all p-values; the false discoveries control guarantee is only in expectation. These limitations can lead to a range of unfavorable outcomes – spanning from reduced interpretability, loss of statistical power, to potential inflation of the Type I error rate – particularly in contexts where we perceive the data as possessing inherent “structure.” This work aims to push back those limits by providing new procedures and methodologies that adapt to settings where p-values can be discrete, online, preordered, or weighted. This ultimately gives the practitioner more effective tools for identifying significant variables in structured data sets as we illustrate in various numerical experiments.

Considérons, sur chaque case du réseau Z^d, un certain nombre de grenouilles (ou particules) qui peuvent être ou bien actives ou bien endormies. Chaque grenouille active effectue une marche aléatoire en temps continu sur Z^d et s'endort avec un certain taux. Une grenouille endormie cesse de bouger, jusqu'à ce qu'une autre grenouille arrive sur le même site, ce qui la réveille. Ce modèle présente une transition de phase : en fonction de la densité de grenouilles (initialement toutes actives) et du taux d'endormissement, ou bien presque sûrement chaque grenouille finit par s'endormir définitivement, ou bien presque sûrement chaque grenouille marche un nombre infini de pas, sans jamais s'endormir définitivement. Dans cet exposé, je présenterai mes travaux avec Amine Asselah et Alexandre Gaudillière qui montrent l'existence d'une phase active non triviale en dimension 2.

Je donnerai un exposé d'introduction au calcul différentiel sur les espaces de mesures, via le transport optimal. Le but sera de présenter le cadre et les outils, ainsi que la descente de gradient sur les espaces de mesures, en préparation d'exposés ultérieurs sur les applications aux réseaux de neurones.

Résumé: L’émergence des produits d’assurance couvrant les risques numériques s’accompagne d’interrogations relatives à la maîtrise des engagements souscrits par les organismes d’assurance. La volatilité des coûts, la dépendance entre les garanties et les potentielles accumulations de sinistres sont autant de spécificités que nous considérons pour proposer des modèles mathématiques adaptés aux enjeux. Nous introduisons d’abord des arbres de régression permettant de comprendre l’hétérogénéité des queues de distribution des risques. Ensuite, nous étudions l’estimation de copules dans un contexte de données censurées pour préciser l’impact des interactions entre les garanties sur les engagements globaux. Enfin, nous proposons une analyse de la fréquence des sinistres numériques par des processus ponctuels adaptés aux phénomènes d’accumulation. Nos contributions suggèrent des méthodes d’analyse pour la souscription, le provisionnement et la gestion des risques numériques.

Trois exposés de 30 min chacun par les doctorants du labo. Une deuxième séance aura lieu en janvier :

Orphée Colin :

La chaîne d'Ising avec champ aléatoire,

Le modèle d'Ising est un modèle classique de physique statistique, décrivant le comportement de moments ferromagnétiques (spins) sur un réseau, interagissant via une interaction site-à-site. Lorsque le réseau est unidimensionnel et dans le cas d'interactions au plus proche voisin homogènes, le modèle est exactement soluble (et simple). Néanmoins, une version désordonnée du modèle d'Ising unidimensionnel, dans laquelle la chaîne interagit avec un environnement i.i.d., est d'analyse plus ardue. Une description des configurations typiques de la chaîne, lorsque l'intensité Gamma de l'interaction interne est grande, apparaît dans la littérature en physique. Nous présenterons le modèle de chaîne d'Ising désordonnée, et montrerons que, en accord avec la description des physiciens, les configurations typiques sont proches de la configuration déterminée par le processus des Gamma-extremas du potentiel associé à l'environnement, lorsque Gamma est grand.

Léo Daures

A weak large deviation principle for the empirical measure of a discrete, possibly reducible Markov chain

In this talk, I will introduce the questions I have been trying to answer in the first year of my PhD. The object of interest is the empirical measure of a Markov chain X, that is the random probability measure L_n = \frac1n\sum_1^n \delta_{X_i}. Our goal is to show a large deviation principle (LDP) for L_n, which roughly speaking means understanding the exponential rate of decay of the probability of rare events involving L_n. The behaviour and the large deviations of the empirical measure is well known in “good” cases, e.g. in irreducible setups. Those properties do not extend easily to reducible setups, as it is not sufficient to study independently the irreducible classes to derive a LDP on the whole chain. In this talk, I will present my current work on a method based on subadditivity, to derive a weak LDP when X is reducible. The usual subadditive method has to be consequentially reworked to fit the context of reducible Markov chains, and notably provides a non-convex rate function.

Principe des grandes déviations faible pour la mesure empirique d’une chaîne de Markov discrète et possiblement réductible. Dans cet exposé, je compte développer les questions auxquelles j’ai essayé de répondre pendant la première année de ma thèse. On s’intéresse à la mesure empirique d’une chaîne de Markov X, c’est-à-dire la mesure de probabilité aléatoire L_n = \frac1n\sum_1^n \delta_{X_i}. Notre objectif est de démontrer un principe de grandes déviations (LDP) pour L_n, ce qui signifie comprendre le taux de décroissance exponentiel de la probabilité d’évènement rares impliquant L_n. Le comportement et les grandes déviations de L_n sont bien connus dans les “bons” cas, i.e. quand la chaîne de Markov est irréductible. Mais ces propriétés ne se prolongent pas facilement aux cas réductibles, car il ne suffit pas d’étudier indépendamment chaque classe d’irréductibilité pour obtenir un LDP sur la chaîne toute entière. Dans cet exposé, je présenterai mon travail sur une méthode fondée sur la sous-additivité pour obtenir un LDP faible quand X est réductible. La méthode sous-additive habituelle doit être considérablement remaniée pour s’adapter au cas des chaînes de Markov réductibles, et elle mène notamment à une fonction de taux non-convexe.

Pablo López-Rivera

Préservation des inégalités fonctionnelles sous des perturbations log-Lipschitz

Étant donné une mesure de probabilité satisfaisant certaines inégalités fonctionnelles (Poincaré, log-Sobolev, etc.), il est naturel de se demander si celles-ci restent valables pour une perturbation de la mesure. En particulier, s'il existe une application globalement Lipschitz qui pousse en avant la mesure source vers sa perturbation, alors il est facile de transporter certaines inégalités fonctionnelles. Par exemple, le théorème de contraction de Caffarelli dit que le transport optimal entre la mesure gaussienne et une perturbation log-concave est 1-Lipschitz.

Dans cet exposé, je montrerai comment une telle application existe si l'on considère des perturbations log-lipschitz d'une mesure sur une variété riemannienne, via l'interpolation donnée par la diffusion de Langevin associée à la mesure source (dite l’application de transport du flot de la chaleur, due à Kim et Milman), en supposant également des bornes sur la courbure de la variété au premier et au second ordre au sens de Bakry-Émery-Ricci.

Maximum likelihood estimation (MLE) enjoys strong optimality properties for statistical estimation, under strong assumptions. However, when these assumptions are not satisfied, MLE can be extremely unreliable. In this talk, we will explore alternative estimators based on the minimization of well chosen distances. In particular, we will see that the Maximum Mean Discrepancy (MMD, based on suitable kernels) leads to estimation procedures that are consistent without any assumption on the model nor on the data-generating process. This leads to strong robustness properties in practice, and this method was already used in complex models with promising results: estimation of SDE coefficients, ccopulas, data compression, generative models in AI…

In the second part of this talk, I will discuss the extension of this method to the estimation of conditional distributions, which allows to use MMD-estimators in various regression models. On the contrary to mean embeddings, very technical conditions are required for the existence of a conditional mean embedding that allows defining an estimator. In most papers, these conditions are often assumed, but rarely checked. It turns out that, in most generalized linear regression models, we proved that these conditions can be met, at the cost of more restrictions on the kernel choice.

This is based on joint works with: Badr-Eddine Chérief-Abdellatif (CNRS, Paris), Mathieu Gerber (University of Bristol), Daniele Durante (Bocconi University), Sirio Legramanti (University of Bergamo), Jean-David Fermanian (ENSAE Paris), Alexis Derumigny (TU Delft), Geoffrey Wolfer (RIKEN-AIP, Tokyo).

La marche aléatoire de l’éléphant est une marche aléatoire qui évolue sous l’influence d’un paramètre de mémoire et qui présente trois régimes de comportement (diffusif, critique et super-diffusif). Dans cet exposé, on commencera par présenter les résultats connus de la littérature ainsi que le lien entre le processus et les urnes de Polya. Ensuite, on expliquera comment ce lien permet de montrer que la variable aléatoire limite qui apparait dans le régime super-diffusif satisfait une équation de point fixe aléatoire. On déduira de cette équation de nombreuses informations sur la limite, notamment sur l’existence d’une densité et le calcul des moments. (Travail en collaboration avec Hélène Guérin et Kilian Raschel)

Fröhlich and Spencer proved the Berezinskii-Kosterlitz-Thouless transition in 1981, through a relation with delocalisation of height functions. My talk focuses on the phase transition for height functions. We mix ideas coming from height functions and planar percolation models in order to prove a coarse-graining inequality inspired by the renormalisation group picture. This allows us to make precise statements about the phase transition (e.g. sharpness) even without knowing exactly where this transition point lies. This talk is based on the recent preprint arXiv:2211.14365 (A dichotomy theory for height functions).

Résumé: Cette thèse traite d’aspects théoriques et méthodologiques de l’apprentissage automatique. Cette discipline a trouvé de nombreuses applications grâce aux grandes quantités de données disponibles. Cependant, des constats empiriques suggèrent souvent des distributions à queue lourde et de la corruption dans les jeux de données ce qui pourrait compromettre les performances des modèles. Ceci a motivé le développement de la statistique robuste qui cherche des méthodes plus fiables sous des hypothèses affaiblies sur les données. Nous présentons des algorithmes d’apprentissage efficaces et robustes avec une analyse théorique établissant la convergence de leur optimisation et les propriétés statistiques de leurs estimateurs. La première contribution propose d’utiliser la descente de gradient par coordonnées (CGD) avec estimation robuste des dérivées partielles pour effectuer de l’apprentissage robuste. Cela permet d’éviter les calculs coûteux liés à l’estimation de moyenne vectorielle robuste grâce à des estimateurs scalaires. Le procédé obtenu est robuste aux queues lourdes et à la corruption comme attesté par les bornes d’erreur de généralisation établies pour des fonctions convexes et gradient-Lipschitz. De plus, le surplus de calcul est minime vu que la complexité est la même que les méthodes non robustes. Nous proposons une implémentation efficace dans la librairie Python linlearn et confirmons les avantages de CGD robuste à travers des expériences numériques. La seconde contribution traite le cas en haute dimension où l’optimisation se fait par méthode non-Euclidienne. Nous développons un cadre d’apprentissage en haute dimension adapté à plusieurs fonctions objectif qui utilise des méthodes d’estimation de gradient robustes adaptées aux métriques non-Euclidiennes spécifiques à chaque problème. Dans le cas de l’estimation éparse standard, on obtient un algorithme efficace et fortement robuste. En plus de l’analyse théorique établissant ces propriétés, nous implémentons cet algorithme dans la librairie linlearn et confirmons ses performances à travers des expériences sur données réelles. La contribution suivante apporte une solution pour les flux de données où les échantillons ne sont accessibles qu’individuellement et séquentiellement. Nous proposons un algorithme SGD tronqué pour l’optimisation stochastique utilisant comme seuils des quantiles de norme de gradient. Grâce à des outils de chaînes de Markov, nous prouvons que l’itération est robuste aux queues lourdes et aux données corrompues et qu’elle converge vers une distribution limite concentrée autour d’un optimum. Dans un autre chapitre, nous utilisons des outils similaires pour étudier les propriétés de convergence et concentration de l’itération SGD classique. En particulier, nous obtenons une borne de concentration non asymptotique pour les moyennes de Polyak-Ruppert. Nos contributions comprennent également un nouvel algorithme de forêt aléatoire appelé WildWood. Ce dernier ajoute un mécanisme d’agrégation par arbre utilisant les échantillons bootstrap pour calculer une prédiction moyenne sur les sous-arbres. Ce calcul est précis et efficace grâce à l’algorithme de context tree weighting. Un résultat théorique montre que cette agrégation permet d’approcher la performance du meilleur sous-arbre. Nous proposons une implémentation efficace dans la librairie Python wildwood et montrons expérimentalement sa compétitivité avec des méthodes d’ensemble connues comme les forêts aléatoires standards et les algorithmes de boosting. Enfin, nous présentons un algorithme non Bayésien efficace pour la régression logistique en ligne qui peut atteindre le regret optimal et fournissons une analyse préliminaire pour ce dernier.

—

Abstract: This thesis deals with theoretical and methodological aspects of machine learning. This discipline has found numerous applications thanks to the availability of vast amounts of data. However, empirical evidence suggests that heavy-tailed distributions and corruption can often emerge in training datasets and may compromise the performances of machine learning models. This has motivated the development of robust statistics which seek more dependable methods when data assumptions are weakened. In this thesis, we propose computationally efficient robust learning algorithms and back them up with theoretical analyses establishing their optimization convergence and the statistical properties of their estimates. In our first contribution, we propose to use coordinate gradient descent (CGD) with robust scalar estimators of the partial derivatives in order to perform robust learning. This allows to avoid the computational cost of robust vector mean estimation by using only scalar estimates. The resulting procedure is robust to heavy-tails and corruption as attested by the generalization error bounds we show for smooth convex objectives. Moreover, computational overhead is minimal since the complexity is the same as non robust methods. We efficiently implement this method in a Python library called linlearn and confirm the advantages of robust CGD through extensive numerical experiments. Our next contribution deals with robust learning in the high-dimensional setting where optimization is carried out using non-Euclidean methods. We develop a robust high-dimensional learning framework suitable for smooth and non-smooth objectives which uses robust gradient estimation methods tailored to problem-specific non-Euclidean metrics. For the particular case of Vanilla sparse estimation, we obtain an efficient solution algorithm with strong robustness properties. Besides the theoretical analysis establishing these properties, we implement this algorithm in the linlearn library and demonstrate its performance through experiments on real data. The third contribution brings a solution for the streaming data setting where samples are only seen once in a sequential fashion. We propose a clipped SGD algorithm for stochastic optimization using gradient norm quantiles as thresholds. Using Markov chain tools, we prove that the iteration is robust to heavy tails and corrupted data and converges to a limit distribution concentrated around an optimum. In another chapter, we leverage similar tools to study the convergence and concentration properties of standard SGD. In particular, we obtain a non asymptotic concentration bound for Polyak-Ruppert averaging of a tail SGD sequence. Our contributions also include a new random forest algorithm called WildWood. The latter adds an aggregation mechanism within each tree of a forest which uses out-of-bag samples to compute average predictions over all subtrees. This computation is precise and efficient thanks to the context tree weighting algorithm. As we show theoretically, this allows to nearly match the performance of the best subtree. We propose an efficient implementation in the Python library wildwood and experimentally demonstrate the algorithm’s competitiveness with popular ensemble methods such as classical random forests and boosting algorithms. Finally, we present an efficient non Bayesian algorithm for online logistic regression which may achieve optimal regret and provide a preliminary analysis for it.

Dans cet exposé, on introduira un modèle d’arbre aléatoire récursif présentant une structure à deux « communautés », au sens où chaque nouveau noeud s’attache de façon préférentielle à un noeud du même type que lui, cette préférence étant mesurée par un paramètre q de [0,1]. De nombreuses questions d’ordre statistique peuvent être posées sur ce modèle: si l’on observe l’arbre aléatoire obtenu au bout d’un temps donné, en enlevant la donnée des types mais en gardant éventuellement la donnée des temps d’arrivée, peut-on estimer le paramètre q? Ou simplement distinguer deux valeurs différentes de ce paramètre? De façon plus ambitieuse, peut-on trouver une partition des noeuds qui soit corrélée de façon significative avec la « vraie » partition? Nous apporterons quelques éléments de réponse à ces questions. Il s’agit d’un travail en collaboration avec Vasiliki Velona (Université hébraïque de Jerusalem).