Publications

2022

• Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters
  
  • Brogat-Motte Luc
  • Flamary Rémi
  • Brouard Celine
  • Rousu Juho
  • d'Alché-Buc Florence
  , 2022, 162. This paper introduces a novel and generic framework to solve the flagship task of supervised labeled graph prediction by leveraging Optimal Transport tools. We formulate the problem as regression with the Fused Gromov-Wasserstein (FGW) loss and propose a predictive model relying on a FGW barycenter whose weights depend on inputs. First we introduce a non-parametric estimator based on kernel ridge regression for which theoretical results such as consistency and excess risk bound are proved. Next we propose an interpretable parametric model where the barycenter weights are modeled with a neural network and the graphs on which the FGW barycenter is calculated are additionally learned. Numerical experiments show the strength of the method and its ability to interpolate in the labeled graph space on simulated data and on a difficult metabolic identification problem where it can reach very good performance with very little engineering.
• Near-optimal rate of consistency for linear models with missing values
  
  • Ayme Alexis
  • Boyer Claire
  • Dieuleveut Aymeric
  • Scornet Erwan
  , 2022. Missing values arise in most real-world data sets due to the aggregation of multiple sources and intrinsically missing information (sensor failure, unanswered questions in surveys...). In fact, the very nature of missing values usually prevents us from running standard learning algorithms. In this paper, we focus on the extensively-studied linear models, but in presence of missing values, which turns out to be quite a challenging task. Indeed, the Bayes rule can be decomposed as a sum of predictors corresponding to each missing pattern. This eventually requires to solve a number of learning tasks, exponential in the number of input features, which makes predictions impossible for current real-world datasets. First, we propose a rigorous setting to analyze a least-square type estimator and establish a bound on the excess risk which increases exponentially in the dimension. Consequently, we leverage the missing data distribution to propose a new algorithm, and derive associated adaptive risk bounds that turn out to be minimax optimal. Numerical experiments highlight the benefits of our method compared to state-of-the-art algorithms used for predictions with missing values.
• A spectral dominance approach to large random matrices
  
  • Bertucci Charles
  • Debbah Mérouane
  • Lasry Jean-Michel
  • Lions Pierre-Louis
  Journal de Mathématiques Pures et Appliquées, Elsevier, 2022. This paper presents a novel approach to characterize the dynamics of the limit spectrum of large random matrices. This approach is based upon the notion we call "spectral dominance". In particular, we show that the limit spectral measure can be determined as the derivative of the unique viscosity solution of a partial integro-differential equation. This also allows to make general and "short" proofs for the convergence problem. We treat the cases of Dyson Brownian motions, Wishart processes and present a general class of models for which this characterization holds. (10.1016/j.matpur.2022.06.001)
  DOI : 10.1016/j.matpur.2022.06.001
• GECCO 2022 tutorial on benchmarking multiobjective optimizers 2.0
  
  • Brockhoff Dimo
  • Tusar Tea
  , 2022, pp.1269-1309. (10.1145/3520304.3533635)
  DOI : 10.1145/3520304.3533635
• Learning Rate Adaptation by Line Search in Evolution Strategies with Recombination
  
  • Gissler Armand
  • Auger Anne
  • Hansen Nikolaus
  , 2022. In this paper, we investigate the effect of a learning rate for the mean in Evolution Strategies with recombination. We study the effect of a half-line search after the mean shift direction is established, hence the learning rate value is conditioned to the direction. We prove convergence and study convergence rates in different dimensions and for different population sizes on the sphere function with the step-size proportional to the distance to the optimum. We empirically find that a perfect half-line search increases the maximal convergence rate on the sphere function by up to about 70%, assuming the line search imposes no additional costs. The speedup becomes less pronounced with increasing dimension. The line search reduces-however does not eliminate-the dependency of the convergence rate on the step-size. The optimal step-size assumes considerably smaller values with line search, which is consistent with previous results for different learning rate settings. The step-size difference is more pronounced in larger dimension and with larger population size, thereby diminishing an important advantage of a large population. CCS CONCEPTS • Theory of computation → Bio-inspired optimization; Nonconvex optimization. (10.1145/3512290.3528760)
  DOI : 10.1145/3512290.3528760
• Benchmarking several strategies to update the penalty parameters in AL-CMA-ES on the bbob-constrained testbed
  
  • Dufossé Paul
  • Atamna Asma
  , 2022, pp.1691-1699. In this paper, we benchmark several versions of a population-based evolution strategy with covariance matrix adaptation, handling constraints with an Augmented Lagrangian fitness function. The versions only differ in the strategy to adapt the penalty parameter of the fitness function. We compare the resulting algorithms, AL-CMA-ES, with random search and Powell’s derivative-free COBYLA on the recently released bbob-constrained test suite for constrained continuous optimization in dimensions ranging from 2 to 40. The experimental results allow identifying classes of problems where one algorithm is more advantageous to use. They also reveal features of the merit function used for performance assessment and in particular situations where even on simple problems the targets can be hard to meet for algorithms based on Lagrange multipliers. (10.1145/3520304.3534014)
  DOI : 10.1145/3520304.3534014
• Benchmarking of Two Implementations of CMA-ES with Diagonal Decoding on the bbob Test Suite
  
  • Gharafi Mohamed
  , 2022, pp.1700-1707. In this paper, we present a comparative benchmark of two implementations of CMA-ES, both with and without diagonal decoding. The benchmarked variants of CMA-ES with diagonal decoding adaptively split the update of the covariance matrix into an update with the original CMA-ES method and an update with the separable-CMA-ES method. Thus, the diagonal decoding should allow for improved performance on separable functions with minimal loss on nonseparable ones. To gain insight into how diagonal decoding impacts CMA-ES runs, an assessment of the performance gain or loss due to the use of diagonal decoding relative to the original CMA-ES, was performed on bbob problems using the COCO platform. We were also interested in variances that might emerge from the difference in the implementations. The data presented in this paper shows improved performance of the CMA-ES on separable functions when using diagonal decoding, without any apparent loss on nonseparable ones. In addition, a few performance variances were spotted in the weakly structured functions, which appeared uncorrelated with the use of diagonal decoding. However, they can be traced back to implementation differences, such as the stopping conditions that may result in different runs, as the data suggests. (10.1145/3520304.3534011)
  DOI : 10.1145/3520304.3534011
• Multi-Scale Modelling of the Intra-Cellular Actin Dynamics
  
  • van Gorp Anne
  , 2022. This thesis focuses on understanding the dynamics of the actin polymer network constituting the mechanical envelope of a cell. We have developed different mathematical models, considering different scales, in order to understand the different mechanisms.The mechanical properties of embryonic cells, which are involved in many cellular behaviours, such as cell division or cell shape changes, are largely defined by the dynamics of a network of polymers, the actomyosin cortex. Each of these polymers, consisting of actin monomers, has a dynamic of elongation, shortening and potentially branching. These dynamics are subject to a high degree of stochasticity, which is not yet fully considered in existing models. In order to understand how the mechanical properties of cells stem from actin biochemistry, it is necessary to understand how the assembly dynamics of these polymers operate in the cell, first at the scale of a single polymer, then at the level of a population of actin polymers.This thesis is divided into three parts. The first part is focused on the study of the elongation-shortening dynamics of actin in the presence of two proteins, formin and profilin, which accelerate the elongation of the actin polymer.Initially, we consider a single actin polymer, formed by a number of monomers that fluctuates over time. The main idea of our model is to see an actin polymer as a queue; this allows us to introduce a stochastic component, inherent to the randomness of the encounters and fixations between the different entities involved. The elongation-shortening dynamics of the polymers is then entirely described by a jump Markov process. In order to obtain an average behaviour, we studied the limit when the total number of monomers tends to infinity (average field limit). The study of the deterministic limit process obtained allows us to obtain an average polymer length but also to observe the influence of the change in elongation rate on the use of the resource, namely free monomers.Secondly, we consider a population of polymers. Each polymer evolves with the dynamics described in the previous model. The dynamics of the population is this time described by a measure-valued Markov process. The study of the large population limit allows us to obtain a distribution of polymer lengths and specially to observe that there is competition between the polymers for free monomers. The size distribution of the polymers is particularly important since the mechanical properties of the cells depend directly on the length of the actin polymers.The second part deals with the study of the branching dynamics of an actin polymer. In order to model a branched polymer, we use the formalism of metric measure spaces. The aim of this part is to better understand the structure of branched polymers, which could, for example, help to better understand the formation of protrusions. In this model, we consider two proteins that can interact with actin: the Arp2/3 protein complex, which creates a new branching, and cofilin, which causes the fragmentation of the polymer and thus the loss of branches. The dynamics of the branched polymer is then fully described by a tree-valued process. We proved that the process describing the number of extremities (renormalised) converges in distribution to a Feller diffusion.The third part is focused on numerical exploration of the different models. The simulations for the models studying the elongation-shortening dynamics allowed us to understand the role of each protein and to obtain a qualitative study of the average behaviours. The simulations for the model studying a single branched polymer allowed us to compare structures obtained by testing different hypotheses. Finally, we extended the model for a population of polymers (and the corresponding code) to consider more proteins interacting with actin.
• Multiscale eco-evolutionary models: from individuals to populations
  
  • Champagnat Nicolas
  • Méléard Sylvie
  • Tran Viet Chi
  , 2023, 7 (1), pp.5656-5678. Motivated by recent biological experiments, we emphasize the effects of small populations in various biological/medical contexts related to evolution such as invasion of mutant cells or emergence of antibiotic resistances. Our main mathematical challenge is to quantify such effects in particular on macroscopic approximations. In order to track individuals and to take into account small populations, we are led to stochastic multiscale models while the limiting macroscopic equations should involve non local non linear partial differential equations. Such approximations are used to analyse the conditions for a mutant invasion from a monotype population and to provide the mutant probability of fixation and its time to fixation. That allows to exhibit a rare mutation scale assumption yielding a timescale separation between competition and mutation. Under these assumptions, the stochastic measure-valued process at the mutation timescale converges to a jump process which describes the successive invasions of successful mutants. The gene transfer can drastically affect the evolutionary outcomes. For fast mutation timescales, preliminary numerical simulations indicate that these models should exhibit many surprising asymptotic behaviours such as cyclic behaviours. These phenomena are mathematically explored on a simple model. Population sizes and times are considered in a log scale to keep track of small subpopulations that have negligible sizes compared with the size of the resident population. Explicit criteria on the model parameters are given to characterise the possible evolutionary outcomes. An important ingredient for the proofs lies in comparison of the stochastic population process with linear or logistic birth-death processes with immigration. The impact of these time and size scales on macroscopic approximations is also investigated, leading to a new class of Hamilton-Jacobi equations with constraint boundary conditions. (10.4171/ICM2022/24)
  DOI : 10.4171/ICM2022/24
• Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games
  
  • Allamigeon Xavier
  • Gaubert Stéphane
  • Katz Ricardo David
  • Skomra Mateusz
  , 2022. We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on an oracle, evaluating the dynamic programming operator up to a given precision. We show that the number of calls to the oracle needed to determine exact optimal (positional) strategies is, up to a factor polynomial in the dimension, of order R/sep, where the "separation" sep is defined as the minimal difference between distinct values arising from strategies, and R is a metric estimate, involving the norm of approximate sub and super-eigenvectors of the dynamic programming operator. We illustrate this method by two applications. The first one is a new proof, leading to improved complexity estimates, of a theorem of Boros, Elbassioni, Gurvich and Makino, showing that turn-based mean-payoff games with a fixed number of random positions can be solved in pseudo-polynomial time. The second one concerns entropy games, a model introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. The rank of an entropy game is defined as the maximal rank among all the ambiguity matrices determined by strategies of the two players. We show that entropy games with a fixed rank, in their original formulation, can be solved in polynomial time, and that an extension of entropy games incorporating weights can be solved in pseudo-polynomial time under the same fixed rank condition.
• Numerical challenges in the simulation of 1D bounded low-temperature plasmas with charge separation in various collisional regimes
  
  • Reboul Louis
  • Massot Marc
  • Laguna Alejandro Alvarez
  , 2022, pp.190004. We study a 1D geometry of a plasma confined between two conducting floating walls with applications to laboratory plasmas. These plasmas are characterized by a quasi-neutral bulk that is joined to the wall by a thin boundary layer called sheath that is positively charged. Although analytical solutions are available in the sheath and the pre-sheath, joining the two areas by one analytical solution is still an open problem which requires the numerical resolution of the fluid equations coupled to Poisson equation. Current numerical schemes use high-order discretizations to correctly capture the electron current in the sheath, presenting unsatisfactory results in the boundary layer and they are not adapted to all the possible collisional regimes. In this work, we identify the main numerical challenges that arise when attempting the simulations of such configuration and we propose explanations for the observed phenomena via numerical analysis. We propose a numerical scheme with controlled diffusion as well as new discrete boundary conditions that address the identified issues. (10.1063/5.0187483)
  DOI : 10.1063/5.0187483
• A Simple Second-Order Implicit-Explicit Asymptotic Preserving Scheme for the Hyperbolic Heat Equations
  
  • Reboul Louis
  • Pichard Teddy
  • Massot Marc
  , 2022. We propose an asymptotic preserving (AP) Implicit-Explicit (ImEx) scheme for the hyperbolic heat equation in the diffusive regime. This scheme is second order in time and space and l ∞-stabile under relatively low constraints on the time step, and without requiring the use slope limiters. The construction exploits a formalism developed in a previous work and, compared to it, leads to a simpler implementation but it loses uniform accuracy on paper. Stability and accuracy are verified on numerical examples, and even uniform accuracy is obtained on those. Finally, we discuss extensions of this method to the non linear case of isothermal Euler equations with friction.
• CMA-ES and advanced adaptation mechanisms
  
  • Akimoto Youhei
  • Hansen Nikolaus
  , 2022, pp.1243-1268. (10.1145/3520304.3533648)
  DOI : 10.1145/3520304.3533648
• Newton method for stochastic control problems
  
  • Gobet Emmanuel
  • Grangereau Maxime
  , 2022.
• dictionary-learning-RMM
  
  • Allouche Michaël
  • Gobet Emmanuel
  • Lage Clara
  • Mangin Edwin
  , 2022. Rating Migration Matrix is a crux to assess credit risks. Modeling and predicting these matrices are then an issue of great importance for risk managers in any financial institution. As a challenger to usual parametric modeling approaches, we propose a new structured dictionary learning model with auto-regressive regularization that is able to meet key expectations and constraints: small amount of data, fast evolution in time of these matrices, economic interpretability of the calibrated model. To show the model applicability, we present a numerical test with both synthetic and real data and a comparison study with the widely used parametric Gaussian Copula model: it turns out that our new approach based on dictionary learning significantly outperforms the Gaussian Copula model. The source code and the data are available at https://github.com/michael-allouche/dictionary-learning-RMM. git for the sake of reproducibility of our research.
• Ground state energy of the low density Bose gas with three-body interactions
  
  • Nam Phan Thành
  • Ricaud Julien
  • Triay Arnaud
  Journal of Mathematical Physics, American Institute of Physics (AIP), 2022, 63 (7), pp.071903. We consider the low density Bose gas in the thermodynamic limit with a three-body interaction potential. We prove that the leading order of the ground state of the system is determined completely in terms of the scattering energy of the interaction potential. The corresponding result for two-body interactions was proved in seminal papers of Dyson (1957) and Lieb--Yngvason (1998). (10.1063/5.0087026)
  DOI : 10.1063/5.0087026
• Cluster expansion for a dilute hard sphere gas dynamics
  
  • Bodineau Thierry
  • Gallagher Isabelle
  • Saint-Raymond Laure
  • Simonella Sergio
  Proceedings of the International Congress on Mathematical Physics, special issue of Journal of Mathematical Physics, 2022, 63. In [7], a cluster expansion method has been developed to study the fluctuations of the hard sphere dynamics around the Boltzmann equation. This method provides a precise control on the exponential moments of the empirical measure, from which the fluctuating Boltzmann equation and large deviation estimates have been deduced. The cluster expansion in [7] was implemented at the level of the BBGKY hierarchy, which is a standard tool to investigate the deterministic dynamics [11]. In this paper, we introduce an alternative approach, in which the cluster expansion is applied directly on real trajectories of the particle system. This offers a fresh perspective on the study of the hard sphere dynamics in the low density limit, allowing to recover the results obtained in [7], and also to describe the actual clustering of particle trajectories. (10.1063/5.0091199)
  DOI : 10.1063/5.0091199
• Supplementary Material for Learning Rate Adaptation by Line Search in Evolution Strategies with Recombination
  
  • Gissler Armand
  • Auger Anne
  • Hansen Nikolaus
  , 2022.
• A (biased) introduction to benchmarking
  
  • Auger Anne
  • Hansen Nikolaus
  , 2022, pp.801-823. (10.1145/3520304.3533649)
  DOI : 10.1145/3520304.3533649
• Dynamics of lineages in adaptation to a gradual environmental change
  
  • Calvez Vincent
  • Henry Benoît
  • Méléard Sylvie
  • Tran Viet Chi
  Annales Henri Lebesgue, UFR de Mathématiques - IRMAR, 2022, 5, pp.729-777. We investigate a simple quantitative genetics model subjet to a gradual environmental change from the viewpoint of the phylogenies of the living individuals. We aim to understand better how the past traits of their ancestors are shaped by the adaptation to the varying environment. The individuals are characterized by a one-dimensional trait. The dynamics-births and deaths-depend on a time-changing mortality rate that shifts the optimal trait to the right at constant speed. The population size is regulated by a nonlinear non-local logistic competition term. The macroscopic behaviour can be described by a PDE that admits a unique positive stationary solution. In the stationary regime, the population can persist, but with a lag in the trait distribution due to the environmental change. For the microscopic (individual-based) stochastic process, the evolution of the lineages can be traced back using the historical process, that is, a measure-valued process on the set of continuous real functions of time. Assuming stationarity of the trait distribution, we describe the limiting distribution, in large populations, of the path of an individual drawn at random at a given time T. Freezing the non-linearity due to competition allows the use of a many-to-one identity together with Feynman-Kac's formula. This path, in reversed time, remains close to a simple Ornstein-Uhlenbeck process. It shows how the lagged bulk of the present population stems from ancestors once optimal in trait but still in the tail of the trait distribution in which they lived. (10.5802/ahl.135)
  DOI : 10.5802/ahl.135
• Does the multiresolution lattice Boltzmann method allow to deal with waves passing through mesh jumps?
  
  • Bellotti Thomas
  • Gouarin Loïc
  • Graille Benjamin
  • Massot Marc
  Comptes Rendus. Mathématique, Académie des sciences (Paris), 2022, Volume 360, pp.pp. 761-769. We consider an adaptive multiresolution-based lattice Boltzmann scheme, which we have recently introduced and studied from the perspective of the error control and the theory of the equivalent equations. This numerical strategy leads to high compression rates, error control and its high accuracy has been explained on uniform and dynamically adaptive grids. However, one key issue with non-uniform meshes within the framework of lattice Boltzmann schemes is to properly handle acoustic waves passing through a level jump of the grid. It usually yields spurious effects, in particular reflected waves. In this paper, we propose a simple mono-dimensional test-case for the linear wave equation with a fixed adapted mesh characterized by a potentially large level jump. We investigate this configuration with our original strategy and prove that we can handle and control the amplitude of the reflected wave, which is of fourth order in the space step of the finest mesh. Numerical illustrations show that the proposed strategy outperforms the existing methods in the literature and allow to assess the ability of the method to handle the mesh jump properly. (10.5802/crmath.319)
  DOI : 10.5802/crmath.319
• Extended McKean-Vlasov optimal stochastic control applied to smart grid management
  
  • Gobet Emmanuel
  • Grangereau Maxime
  ESAIM: Control, Optimisation and Calculus of Variations, EDP Sciences, 2022, 28, pp.40. We study the mathematical modeling of the energy management system of a smart grid, related to a aggregated consumer equipped with renewable energy production (PV panels e.g.), storage facilities (batteries), and connected to the electrical public grid. He controls the use of the storage facilities in order to diminish the random fluctuations of his residual load on the public grid, so that intermittent renewable energy is better used leading globally to a much greener carbon footprint. The optimization problem is described in terms of an extended McKean-Vlasov stochastic control problem. Using the Pontryagin principle, we characterize the optimal storage control as solution of a certain McKean-Vlasov Forward Backward Stochastic Differential Equation (possibly with jumps), for which we prove existence and uniqueness. Quasi-explicit solutions are derived when the cost functions may not be linear- quadratic, using a perturbation approach. Numerical experiments support the study. (10.1051/cocv/2022034)
  DOI : 10.1051/cocv/2022034
• Inference of nitridation reaction efficiencies of graphite in nitrogen plasma flows using a Bayesian formulation
  
  • del Val Ana Isabel
  • Congedo Pietro
  • Magin Thierry
  , 2022. (10.2514/6.2022-3732)
  DOI : 10.2514/6.2022-3732
• Monnalisa: Modelling Nonlinear Aerodynamics of Lifting Surfaces
  
  • Auteri Franco
  • Gibertini Giuseppe
  • Gori Giulio
  • Guardone Alberto
  • Rausa Andrea
  • Zanotti Alex
  • Congedo Pietro Marco
  • Menzago Andrea
  , 2022. (10.2514/6.2022-4149)
  DOI : 10.2514/6.2022-4149
• No self-concordant barrier interior point method is strongly polynomial
  
  • Allamigeon Xavier
  • Gaubert Stéphane
  • Vandame Nicolas
  , 2022, pp.515-528. It is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative. In this paper, we show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, on parametric families of convex optimization problems, the log-limit of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. We provide an explicit linear program that falls in the same class as the Klee–Minty counterexample for the simplex method, i.e., in which the feasible region is a combinatorial cube and the number of iterations is Ω(2n). (10.1145/3519935.3519997)
  DOI : 10.1145/3519935.3519997