Quel est le comportement de grandes déviations du spectre d’un graphe d’Erdos-Rényi dense ? En raison de la non-integrabilité de ce modèle, cette question représente un défi majeur à la théorie classique des grandes déviations. Dans cet exposé, nous examinerons une relaxation de ce problème en considérant des graphes d’Erdös-Rényi sparse surcritiques, c’est-à-dire dont le degré moyen est sous-linéaire mais diverge au moins comme le logarithme du nombre de sommets. Dans ce régime de sparsité, où la mesure empirique des valeurs propres converge, après normalisation, encore vers une loi du semi-cercle, nous montrons un principe de grande déviation avec une fonction de taux solution d’un certain problème variationnel. Cette fonction de taux révèle en particulier que les seules déviations possibles sont autour de mesures provenant d’équations quadratiques vectorielles et que les changements de mesures optimaux consistent à rendre le graphe inhomogène, tout en gardant la structure d’indépendance des arêtes.

Exposé basé sur le preprint arXiv:2401.11925.

Alors que l'estimation des coefficients d'une diffusion scalaire semblait bien comprise (minimax, adaptatif, bayésien non-paramétrique) au début des années 2000, alors que la statistique des semi-martingales s'est résolument tournée vers la finance statistique, ces dernières années voient réapparaître le problème de l'estimation du champ de vecteur de dérive et de la matrice de diffusion pour un processus de diffusion multivarié, notamment sous l'influence de questions de ML et de problèmes inverses bayésiens.

Dans cet exposé, issu de travaux en commun avec Chiara Amorino, Claudia Strauch et aussi Kolyan Ray, nous montrons que si l'on se contente d'un programme théorique non-paramétrique classique (perte L^2, minimax adaptatif à la Lepski, mais pas tellement plus), alors il est possible d'obtenir des résultats relativement généraux qui améliorent en dimension arbitraire ce que l'on connaît, et ceci dans plusieurs directions : pour (i) des observations en temps grand avec pas de discrétisation arbitrairement lent (ii) une réflexion du processus aux bords d'un domaine, mais pas forcément (iii) des situations où la diffusion peut dégénérer, ce qui permet d'inclure des modèles de type position-vitesse ; (iv) dans certains cas (conductivité, schémas rapides) des vitesses de contraction bayésiennes.

L'approche est toujours un peu la même : pour les bornes supérieures, construire une équivalence de modèle par un schéma de régression martingale, découpler les propriétés de concentration du bruit martingale de la “vitesse de remplissage” de l'espace par le “design” (souvent mal connue, ou tout au moins difficile à estimer) ; pour les bornes inférieures, des méthodes perturbatives utilisant un peu de calcul de Malliavin et pour les résultats bayésiens, plus fins, des développements en temps petit du noyau de la chaleur pour une “bonne” géométrie.

Dans cet exposé, nous prendrons un arbre de Galton-Watson sur-critique d’espérance m, et nous echantillons une percolation sur l’arbre. Il est bien connu que la probabilité critique pour ce modèle est 1/m et que l’amas de la racine à la loi d’un arbre de Galton-Watson critique. Pour cette raison de nombreuses propriétés de l’amas sont bien comprises, par exemple la probabilité à survivre jusqu’à la k-ieme génération, la loi de la taille de la k-ieme génération conditionnée à être strictement positive (la “limite de Yaglom”), et la convergence vers un processus du branchement. Tous ces résultats sont annealed, c’est-à-dire que nous prenons l’espérance par rapport à la loi de l’arbre et de la percolation simultanément. L’objectif de cet exposé est de considérer le régime quenched : ses propriétés sont-elles vraies pour presque toute réalisation de l’arbre ? Nous allons voir que c’est (plus ou moins) bien le cas.

Basé sur un travail en commun avec Quirin Vogel.

In this talk, I will overview works on random walks in dynamical random environments. I will recall a result obtained in collaboration with Hilario and Teixeira and then I will focus on a work with Conchon–Kerjan and Rodriguez. Our main interest is to investigate the long-term behavior of a random walker evolving on top of the simple symmetric exclusion process (SSEP) at equilibrium, with density in [0,1]. At each jump, the random walker is subject to a drift that depends on whether it is sitting on top of a particle or a hole. We prove that the speed of the walk, seen as a function of the density, exists for all density but at most one, and that it is strictly monotonic. We will explain how this can be seen as a sharpness result and provide an outline of the proof, whose general strategy is inspired by techniques developed for studying the sharpness of strongly-correlated percolation models.

Abstract: Missing values are common in most real-world data sets due to the combination of multiple sources and inherently missing information, such as sensor failures or unanswered survey questions. The presence of missing values often prevents the application of standard learning algorithms. This thesis examines missing values in a prediction context, aiming to achieve accurate predictions despite the occurrence of missing data in both training and test datasets.

The focus of this thesis is to theoretically analyze specific algorithms to obtain finite-sample guarantees. We derive minimax lower bounds on the excess risk of linear predictions in presence of missing values. Such lower bounds depend on the distribution of the missing pattern, and can grow exponentially with the dimension. We propose a very simple method consisting in applying Least-Square procedure on the most frequent missing patterns only. Such a simple method turns out to be near minimax-optimal procedure, which departs from the Least-Square algorithm applied to all missing patterns. Following this, we explore the impute-then-regress method, where imputation is performed using the naive zero imputation, and the regression step is carried out via linear models, whose parameters are learned via stochastic gradient descent. We demonstrate that this very simple method offers strong finite-sample guarantees in high-dimensional settings. Specifically, we show that the bias of this method is lower than the bias of ridge regression. As ridge regression is often used in high dimensions, this proves that the bias of missing data (via zero imputation) is negligible in some high-dimensional settings. These findings are illustrated using random features models, which help us to precisely understand the role of dimensionality. Finally, we study different algorithm to handle linear classification in presence of missing data (logistic regression, perceptron, LDA). We prove that LDA is the only model that can be valid for both complete and missing data for some generic settings.

In this work, we examine the long-run distribution of stochastic gradient descent (SGD) in general, non-convex problems. Specifically, we seek to understand which regions of the problem's state space are more likely to be visited by SGD, and by how much. Using an approach based on the theory of large deviations and randomly perturbed dynamical systems, we show that the long-run distribution of SGD resembles the Boltzmann-Gibbs distribution of equilibrium thermodynamics with temperature equal to the method's step-size and energy levels determined by the problem's objective and the statistics of the noise. In particular, we show that, in the long run, (a) the problem's critical region is visited exponentially more often than any non-critical region; (b) the iterates of SGD are exponentially concentrated around the problem's minimum energy state (which does not always coincide with the global minimum of the objective); © all other connected components of critical points are visited with frequency that is exponentially proportional to their energy level; and, finally (d) any component of local maximizers or saddle points is “dominated” by a component of local minimizers which is visited exponentially more often.

This is a joint work with Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos