Publications

2023

• Bit-complexity estimates in geometric programming, and application to the polynomial-time computation of the spectral radius of nonnegative tensors
  
  • Friedland Shmuel
  • Gaubert Stéphane
  , 2023. We show that the spectral radius of nonnegative tensors can be approximated within $\varepsilon$ error in polynomial time. This implies that the maximum of a nonnegative homogeneous $d$-form in the unit ball with respect to $d$-H\"older norm can be approximated in polynomial time. These results are deduced by establishing bit-size estimates for the near-minimizers of functions given by suprema of finitely many log-Laplace transforms of discrete nonnegative measures on $\mathbb{R}^n$. Hence, some known upper bounds for the clique number of hypergraphs are polynomially computable.
• On the Impossible Safety of Large AI Models
  
  • El-Mhamdi El-Mahdi
  • Farhadkhani Sadegh
  • Guerraoui Rachid
  • Gupta Nirupam
  • Hoang Lê-Nguyên
  • Pinot Rafaël
  • Rouault Sébastien
  • Stephan John
  , 2023. Large AI Models (LAIMs), of which large language models are the most prominent recent example, showcase some impressive performance. However they have been empirically found to pose serious security issues. This paper systematizes our knowledge about the fundamental impossibility of building arbitrarily accurate and secure machine learning models. More precisely, we identify key challenging features of many of today's machine learning settings. Namely, high accuracy seems to require memorizing large training datasets, which are often user-generated and highly heterogeneous, with both sensitive information and fake users. We then survey statistical lower bounds that, we argue, constitute a compelling case against the possibility of designing high-accuracy LAIMs with strong security guarantees.
• Hierarchies d'autoroutes pour les équations d'Hamilton-Jacobi-Bellman (HJB)
  
  • Liu Shanqing
  , 2023. Dans cette thèse, nous développons de nouvelles méthodes numériques pour résoudre des problèmes de contrôle optimal déterministe et les équations d'Hamilton-Jacobi-Bellman (HJB) du premier ordre associées. L'objectif principal est d'atténuer la malédiction de la dimension. Une idée commune à tous nos travaux est de se concentrer sur le calcul d'une ou plusieurs trajectoires optimales avec des conditions initiales et/ou finales fixées.Dans la première partie, nous abordons les problèmes de temps minimum et la résolution des équations eikonales. Nous introduisons une méthode ``fast marching'' multi-niveaux, qui s'appuie sur des grilles imbriquées, permettant de rechercher les trajectoires optimales dans un voisinage tubulaire obtenu au moyen d'approximations dans des grilles grossières. Nous établissons la convergence et la complexité de notre algorithme. En outre, nous analysons un schéma Semi-Lagrangien pour les équations eikonales. Nous montrons la semiconcavité de la solution sous certaines conditions. Nous en déduisons un taux de convergence d'ordre 1 pour les schémas semi-discrétisés et entièrement discrétisés, le taux étant mesuré en terme de pas de temps pour le premier schéma et de pas en espace pour le second. Nous appliquons ces résultats pour obtenir le taux de convergence de la méthode ``fast marching'' et la complexité de notre méthode ``fast marching'' multi-niveaux.Dans la deuxième partie, nous explorons les méthodes num'eriques tropicales pour les problèmes en horizon fini.Dans un premier travail, nous combinons les méthodes directes avec la méthode des éléments finis max-plus, ce qui conduit à une plus grande précision. Ensuite, nous combinons les concepts de la première partie avec la méthode numérique tropicale afin d'obtenir la meilleure borne de complexité sous des conditions plus générales. Dans un deuxième travail, nous introduisons un nouvel algorithme pour approximer numériquement la valeur en un état initial fixé, ainsi que la trajectoire optimale correspondante. Cet algorithme peut être vu comme une combinaison de la méthode numérique tropicale et de la méthode de programmation dynamique stochastique duale. Nous montrons que notre algorithme converge vers l'optimum global, dans le cas de problèmes semi-concaves.
• On the polygonal Faber-Krahn inequality
  
  • Bogosel Beniamin
  • Bucur Dorin
  Journal de l'École polytechnique — Mathématiques, École polytechnique, 2023, 11, pp.19-105. It has been conjectured by Pólya and Szegö seventy years ago that the planar set which minimizes the first eigenvalue of the Dirichlet-Laplace operator among polygons with n sides and fixed area is the regular polygon. Despite its apparent simplicity, this result has only been proved for triangles and quadrilaterals. In this paper we prove that for each n ≥ 5 the proof of the conjecture can be reduced to a finite number of certified numerical computations. Moreover, the local minimality of the regular polygon can be reduced to a single numerical computation. For n = 5, 6, 7, 8 we perform this computation and certify the numerical approximation by finite elements, up to machine errors. (10.5802/jep.250)
  DOI : 10.5802/jep.250
• Credit Assignment in Deep Reinforcement Learning
  
  • Mesnard Thomas
  , 2023. Deep reinforcement learning has been at the heart of many revolutionary results in artificial intelligence in the last few years. These agents are based on credit assignment techniques that try to establish correlations between past actions and future events and use these correlations to become effective in a given task. This problem is at the heart of the current limitations of deep reinforcement learning and credit assignment techniques used today remain relatively rudimentary and incapable of inductive reasoning. This thesis therefore focuses on the study and formulation of new credit assignment methods for deep reinforcement learning. Such techniques could speed up learning, make better generalization when agents are trained on multiple tasks, and perhaps even allow the emergence of abstraction and reasoning.
• Recent progress on limit theorems for large stochastic particle systems
  
  • Fathi Max
  • Le Bris Pierre
  • Menegaki Angeliki
  • Monmarché Pierre
  • Reygner Julien
  • Tomasevic Milica
  ESAIM: Proceedings and Surveys, EDP Sciences, 2023, 75, pp.2-23. This article presents a selection of recent results in the mathematical study of physical systems described by a large number of particles, with various types of interactions (mean-field, moderate, nearest-neighbor). Limit theorems are obtained concerning either the large-scale or the long-time behavior of these systems. These results rely on the use of a large range of mathematical tools, arising from both probability theory and the analysis of partial differential equations, and thereby illustrate fruitful interactions between these two disciplines. (10.1051/proc/202375002)
  DOI : 10.1051/proc/202375002
• Learning extreme expected shortfall with neural networks
  
  • Allouche Michaël
  • Girard Stéphane
  • Gobet Emmanuel
  , 2023. New parameterizations for neural networks are proposed in order to estimate extreme Expected Shortfall in heavy-tailed settings. All proposed neural network estimators feature a bias correction based on an extension of the usual second-order condition to an arbitrary order. The convergence rate of the uniform error between extreme log-ES and their neural network approximation is established. Again, the rate depends on the order parameters which drive the bias in most extreme estimators. The finite sample performance of the neural network estimator is compared to other bias-reduced extreme-value competitors on simulated data. It is shown that the method outperforms in difficult heavy-tailed situations where other estimators almost all fail. Finally, the neural network estimator is implemented to investigate the behavior of cryptocurrency extreme loss returns.
• Wave propagation in random media: beyond Gaussian statistics
  
  • Garnier Josselin
  ESAIM: Proceedings and Surveys, EDP Sciences, 2023, 74, pp.63-89. In this paper we review some aspects of wave propagation in random media. In the physics literature the picture seems simple: for large propagation distances, the wavefield has Gaussian statistics, mean zero, and second-order moments determined by radiative transfer theory. The results for the first two moments can be proved under general circumstances by multiscale analysis. The Gaussian conjecture for the statistical distribution of the wavefield can be proved in some propagation regimes, such as the white-noise paraxial regime that we address in the first part of this review. It may, however, be wrong in other regimes, such as in randomly perturbed open waveguides, that we address in the second part of this review. In the third and last part, we reconcile the two results by showing that the Gaussian conjecture is restored in randomly perturbed open waveguides in the high-frequency regime, when the number of propagating modes increases. (10.1051/proc/202374063)
  DOI : 10.1051/proc/202374063
• Estimation of extreme expected shortfall with neural networks
  
  • Allouche Michaël
  • Girard Stéphane
  • Gobet Emmanuel
  , 2023. New parameterizations for neural networks are proposed in order to estimate extreme Expected Shortfall in heavy-tailed settings. All proposed neural network estimators feature a bias correction based on an extension of the usual second-order condition to an arbitrary order. The convergence rate of the uniform error between extreme log-ES and their neural network approximation is established. Again, the rate depends on the order parameters which drive the bias in most extreme estimators. The finite sample performance of the neural network estimator is compared to other bias-reduced extreme-value competitors on simulated data. It is shown that the method outperforms in difficult heavy-tailed situations where other estimators almost all fail. Finally, the neural network estimator is implemented to investigate the behavior of cryptocurrency extreme loss returns.
• Optimizing Markov Chain Monte Carlo Convergence with Normalizing Flows and Gibbs Sampling
  
  • Schönle Christoph
  • Gabrié Marylou
  , 2023. Generative models have started to integrate into the scientific computing toolkit. One notable instance of this integration is the utilization of normalizing flows (NF) in the development of sampling and variational inference algorithms. This work introduces a novel algorithm, GflowMC, which relies on a Metropolis-within-Gibbs framework within the latent space of NFs. This approach addresses the challenge of vanishing acceptance probabilities often encountered when using NF-generated independent proposals, while retaining non-local updates, enhancing its suitability for sampling multi-modal distributions. We assess GflowMC's performance concentrating on the ϕ 4 model from statistical mechanics. Our results demonstrate that by identifying an optimal size for partial updates, convergence of the Markov Chain Monte Carlo (MCMC) can be achieved faster than with full updates. Additionally, we explore the adaptability of GflowMC for biasing proposals towards increasing the update frequency of critical coordinates, such as coordinates highly correlated to mode switching in multi-modal targets.
• Dynamics of dilute gases : a statistical approach
  
  • Bodineau Thierry
  • Gallagher Isabelle
  • Saint-Raymond Laure
  • Simonella Sergio
  , 2023, 2 (1), pp.750-795. The evolution of a gas can be described by different models depending on the observation scale. A natural question, raised by Hilbert in his sixth problem, is whether these models provide consistent predictions. In particular, for rarefied gases, it is expected that continuum laws of kinetic theory can be obtained directly from molecular dynamics governed by the fundamental principles of mechanics. In the case of hard sphere gases, Lanford showed that the Boltzmann equation emerges as the law of large numbers in the low density limit, at least for very short times. The goal of this survey is to present recent progress in the understanding of this limiting process, providing a complete statistical description. (10.4171/ICM2022/130)
  DOI : 10.4171/ICM2022/130
• Random subsequences problems : asymptotics, variance, and quantum statistics.
  
  • Deslandes Clément
  , 2023. This work considers some random words combinatorial problems and their applications. A random word of length n is an n-tuple of, say, i.i.d. random variables taking values in a finite set called alphabet (for example, a sequence of coin tosses HTTTHTTH is a random word of length 8). The starting point of this endeavor is the following question: given two random words, "how much do they have in common"? The problem of analyzing the similarity between two random words has emerged independently in various fields, including computer science, biology, linguistics...Unfortunately, too little is known on the fundamental problem of the study of the length of the Longest Common Subsequences (LCS) of two random words: the asymptotic distribution, and even the asymptotics of the variance, are unknown. However, by slightly twisting this problem, it becomes easier to find the asymptotic distribution: the first chapter of our work is dedicated to the asymptotic distribution of the length of the longest common and increasing subsequences. There we consider a totally ordered alphabet with an order, say 1,..., m, and the subsequencesare simply made of a block of 1’s, followed by a block of 2’s, ... and so on (such a subsequence is increasing, but not strictly). In this framework, we are able to provide the asymptotic mean,variance and distribution of its maximal length.In the second chapter, we deal with the problem of the variance of the LCS. It is an important open problem to determine whether or not the variance is linear in n. By introducing a general framework going beyond this problem, partial results in this direction are presented. Indeed, for functions of independent random variables, various upper and lower variance bounds are revisitedin diverse settings. These are then specialized to the Bernoulli, Gaussian, infinitely divisible cases and to Banach space valued random variables. Frameworks and techniques vary from jackknivesthrough semigroups and beyond. Some new applications are presented, recovering and improving, in particular, all the known estimates on the variance of the length of the longest commonsubsequences of two random words.In the third and final chapter, we consider the Longest Increasing Subsequences (LIS) of one random word, and the surprising connection with quantum statistics. Indeed, estimating the spectrum of a density matrix of a quantum system with n copies of this system is equivalent to estimating the distribution of the letters of a word of size n given the Robinson–Schensted–Knuth (RSK) output shape of this word (a partition of n whose first term is the length of the LIS). Therefore, we revisit some aspects of the convergence of the cumulative shape of the RSK Young diagrams associated with random words, obtaining rates of convergence in Kolmogorov’s distance. Since the length of the top row of a diagram is the length of the longest increasing subsequences of the word, a corresponding rate result follows. We then provide results on two spectrum estimators, with numerical simulations tending to prove that their risk is smaller than with the empirical Young diagram estimator. Then we bound the sum of the variances of the Young diagram, and lastly, prove a bound on the "excess" of the shape of the RSK algorithm with the help of a Markov chain.
• Résolution numérique de l'équation du transport de neutrons par la méthode des harmoniques sphériques et une méthode de Galerkin discontinue
  
  • Assogba Kenneth
  , 2023. Dans cette thèse, nous étudions un schéma numérique pour la résolution de l'équation du transport de neutrons. Notre étude s'applique dans le domaine de la physique des réacteurs nucléaires pour la simulation numérique de cœurs de réacteurs et d'assemblages combustible. Le schéma numérique étudié est basé sur la méthode des harmoniques sphériques pour la variable angulaire et celle des éléments finis discontinus pour la variable spatiale. Ce schéma numérique permet de traiter les maillages non-structurés, non-conformes avec des faces 2D courbes, typiquement des cercles et des arcs de cercle. La prise en compte de maillages courbes permet de représenter de façon exacte la géométrie des crayons combustibles de réacteurs à eau pressurisée. Par ailleurs, tirant profit de la périodicité des motifs dans un cœur, les produits matrice-vecteur sont optimisés et parallélisés.Le solveur de flux qui en résulte a un large éventail d'applications. Afin d'évaluer sa précision et ses performances, il a été appliqué à des calculs de cœurs de réacteurs et d'assemblages de combustible en une, deux et trois dimensions. Les solutions obtenues sont conformes aux standards de l'industrie nucléaire et les temps de calcul compétitifs, même dans le cas de géométries complexes de cœurs et d'assemblages. D'autre part, nous prouvons la convergence et fournissons des estimations d'erreur de ce schéma numérique.Enfin, nous développons une méthode de décomposition de domaine afin d'effectuer des calculs parallèles en mémoire distribuée. Les tests numériques menés montrent que la méthode permet d'obtenir un passage à l'échelle quasi-linéaire. Nous maintenons une efficacité en scalabilité forte de 100 % jusqu'à 4096 cœurs de calcul et de 80 % jusqu'à 8192 cœurs. Le solveur est en outre robuste, les variations sur les solutions obtenues par rapport au solveur séquentiel étant proches de la précision machine.
• A Quantization Procedure for Nonlinear Pricing with an Application to Electricity Markets
  
  • Jacquet Quentin
  • van Ackooij Wim
  • Alasseur Clémence
  • Gaubert Stéphane
  , 2023. We consider a revenue maximization model, in which a company aims at designing a menu of contracts, given a population of customers. A standard approach consists in constructing an incentive-compatible continuum of contracts, i.e., a menu composed of an infinite number of contracts, where each contract is especially adapted to an infinitesimal customer, taking his type into account. Nonetheless, in many applications, the company is constrained to offering a limited number of contracts. We show that this question reduces to an optimal quantization problem, similar to the pruning problem that appeared in the max-plus based numerical methods in optimal control. We develop a new quantization algorithm, which, given an initial menu of contracts, iteratively prunes the less important contracts, to construct an implementable menu of the desired cardinality, while minimizing the revenue loss. We apply this algorithm to solve a pricing problem with price-elastic demand, originating from the electricity retail market. Numerical results show an improved performance by comparison with earlier pruning algorithms.
• On Fundamental Proof Structures in First-Order Optimization
  
  • Goujaud Baptiste
  • Dieuleveut Aymeric
  • Taylor Adrien
  , 2023. First-order optimization methods have attracted a lot of attention due to their practical success in many applications, including in machine learning. Obtaining convergence guarantees and worst-case performance certificates for first-order methods have become crucial for understanding ingredients underlying efficient methods and for developing new ones. However, obtaining, verifying, and proving such guarantees is often a tedious task. Therefore, a few approaches were proposed for rendering this task more systematic, and even partially automated. In addition to helping researchers finding convergence proofs, these tools provide insights on the general structures of such proofs. We aim at presenting those structures, showing how to build convergence guarantees for first-order optimization methods. (10.48550/arXiv.2310.02015)
  DOI : 10.48550/arXiv.2310.02015
• Convolutional Monge Mapping Normalization for learning on sleep data
  
  • Gnassounou Theo
  • Flamary Rémi
  • Gramfort Alexandre
  , 2023. In many machine learning applications on signals and biomedical data, especially electroencephalogram (EEG), one major challenge is the variability of the data across subjects, sessions, and hardware devices. In this work, we propose a new method called Convolutional Monge Mapping Normalization (CMMN), which consists in filtering the signals in order to adapt their power spectrum density (PSD) to a Wasserstein barycenter estimated on training data. CMMN relies on novel closed-form solutions for optimal transport mappings and barycenters and provides individual test time adaptation to new data without needing to retrain a prediction model. Numerical experiments on sleep EEG data show that CMMN leads to significant and consistent performance gains independent from the neural network architecture when adapting between subjects, sessions, and even datasets collected with different hardware. Notably our performance gain is on par with much more numerically intensive Domain Adaptation (DA) methods and can be used in conjunction with those for even better performances.
• Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent
  
  • Pavasovic Krunoslav Lehman
  • Durmus Alain
  • Simsekli Umut
  , 2023. A recent line of empirical studies has demonstrated that SGD might exhibit a heavy-tailed behavior in practical settings, and the heaviness of the tails might correlate with the overall performance. In this paper, we investigate the emergence of such heavy tails. Previous works on this problem only considered, up to our knowledge, online (also called single-pass) SGD, in which the emergence of heavy tails in theoretical findings is contingent upon access to an infinite amount of data. Hence, the underlying mechanism generating the reported heavy-tailed behavior in practical settings, where the amount of training data is finite, is still not well-understood. Our contribution aims to fill this gap. In particular, we show that the stationary distribution of offline (also called multi-pass) SGD exhibits 'approximate' power-law tails and the approximation error is controlled by how fast the empirical distribution of the training data converges to the true underlying data distribution in the Wasserstein metric. Our main takeaway is that, as the number of data points increases, offline SGD will behave increasingly 'power-law-like'. To achieve this result, we first prove nonasymptotic Wasserstein convergence bounds for offline SGD to online SGD as the number of data points increases, which can be interesting on their own. Finally, we illustrate our theory on various experiments conducted on synthetic data and neural networks.
• Conditional score-based diffusion models for Bayesian inference in infinite dimensions
  
  • Baldassari Lorenzo
  • Siahkoohi Ali
  • Garnier Josselin
  • Sølna Knut
  • de Hoop Maarten V.
  , 2023, 36, pp.24262--24290.
• SNEkhorn: Dimension Reduction with Symmetric Entropic Affinities
  
  • Van Assel Hugues
  • Vayer Titouan
  • Flamary Rémi
  • Courty Nicolas
  , 2023. Many approaches in machine learning rely on a weighted graph to encode the similarities between samples in a dataset. Entropic affinities (EAs), which are notably used in the popular Dimensionality Reduction (DR) algorithm t-SNE, are particular instances of such graphs. To ensure robustness to heterogeneous sampling densities, EAs assign a kernel bandwidth parameter to every sample in such a way that the entropy of each row in the affinity matrix is kept constant at a specific value, whose exponential is known as perplexity. EAs are inherently asymmetric and row-wise stochastic, but they are used in DR approaches after undergoing heuristic symmetrization methods that violate both the row-wise constant entropy and stochasticity properties. In this work, we uncover a novel characterization of EA as an optimal transport problem, allowing a natural symmetrization that can be computed efficiently using dual ascent. The corresponding novel affinity matrix derives advantages from symmetric doubly stochastic normalization in terms of clustering performance, while also effectively controlling the entropy of each row thus making it particularly robust to varying noise levels. Following, we present a new DR algorithm, SNEkhorn, that leverages this new affinity matrix. We show its clear superiority to state-of-the-art approaches with several indicators on both synthetic and real-world datasets.
• Nonlocal approximation of the anisotropic perimeter and application to topology optimization
  
  • Amstutz Samuel
  • Bogosel Beniamin
  , 2023. We present a Γ-convergence approximation of a class of anisotropic perimeter functionals. In contrast to other works on the topic, the construction relies on the solution of possibly nonlinear elliptic boundary value problems. We discuss theoretical and algorithmic aspects. We also show various applications in topology optimization, including multiphase partitioning and overhang penalization in a mechanical framework related to additive manufacturing.
• Plans d'expériences pour simulations numériques
  
  • Sire Charlie
  , 2023.
• Plans d'expériences: Plans associés à la régression linéaire
  
  • Sire Charlie
  , 2023.
• Almost sharp rates of convergence for the average cost and displacement in the optimal matching problem
  
  • Goldman Michael
  • Huesmann Martin
  • Otto Felix
  , 2023. In this note we prove estimates for the average cost in the quadratic optimal transport problem on the two-dimensional flat torus which are optimal up to a double logarithm. We also prove sharp estimates on the displacement. This is based on the combination of a post-processing of our quantitative linearization result together with a quasi-orthogonality property.
• Distances on the $\mathrm{CLE}_4$, critical Liouville quantum gravity and $3/2$-stable maps
  
  • Kammerer Emmanuel
  , 2023. The purpose of this article is threefold. First, we show that when one explores a conformal loop ensemble of parameter $\kappa=4$ ($\mathrm{CLE}_4$) on an independent $2$-Liouville quantum gravity ($2$-LQG) disk, the surfaces which are cut out are independent quantum disks. To achieve this, we rely on approximations of the explorations of a $\mathrm{CLE}_4$: we first approximate the $\mathrm{SLE}_4^{\langle \mu \rangle}$ explorations for $\mu \in \mathbb{R}$ using explorations of the $\mathrm{CLE}_\kappa$ as $\kappa \uparrow 4$ and then we approximate the uniform exploration by letting $\mu \to \infty$. Second, we describe the relation between the so-called natural quantum distance and the conformally invariant distance to the boundary introduced by Werner and Wu. Third, we establish the scaling limit of the distances from the boundary to the large faces of $3/2$-stable maps and relate the limit to the $\mathrm{CLE}_4$-decorated $2$-LQG.
• Coupling by reflection for controlled diffusion processes: Turnpike property and large time behavior of Hamilton–Jacobi–Bellman equations
  
  • Conforti Giovanni
  The Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2023, 33 (6A). (10.1214/22-AAP1927)
  DOI : 10.1214/22-AAP1927