Publications

2023

• Input uncertainty propagation through trained neural networks
  
  • Monchot Paul
  • Coquelin Loïc
  • Petit Sébastien J
  • Marmin Sébastien
  • Le Pennec Erwan
  • Fischer Nicolas
  , 2023. When physical sensors are involved, such as image sensors, the uncertainty over the input data is often a major component of the output uncertainty of machine learning models. In this work, we address the problem of input uncertainty propagation through trained neural networks. We do not rely on a Gaussian distribution assumption of the output or of any intermediate layer. We propagate instead a Gaussian Mixture Model (GMM) that offers much more flexibility using the Split&Merge algorithm. This paper's main contribution is the computation of a Wasserstein criterion to control the Gaussian splitting procedure for which theoretical guarantees of convergence on the output distribution estimates are derived. The methodology is tested against a wide range of datasets and networks. It shows robustness, and genericity and offers highly accurate output probability density function estimation while maintaining a reasonable computational cost compared with the standard Monte Carlo (MC) approach. 1
• Optimal ecological transition path of a credit portfolio distribution, based on Multidate Monge-Kantorovich formulation
  
  • Gobet Emmanuel
  • Lage Clara
  , 2023.
• Analysis of a combined spherical harmonics and discontinuous Galerkin discretization for the Boltzmann transport equation
  
  • Assogba Kenneth
  • Allaire Grégoire
  • Bourhrara Lahbib
  , 2023. In [11], a numerical scheme based on a combined spherical harmonics and discontinuous Galerkin finite element method for the resolution of the Boltzmann transport equation is proposed. One of its features is that a streamline weight is added to the test function to obtain the variational formulation. In this paper, we prove the convergence and provide error estimates of this numerical scheme. To this end, the original variational formulation is restated in a broken functional space. The use of broken functional spaces enables to build a conforming approximation, that is the finite element space is a subspace of the broken functional space. The setting of a conforming approximation simplifies the numerical analysis, in particular the error estimates, for which a Céa's type lemma and standard interpolation estimates are sufficient for our analysis. For our numerical scheme, based on $P_k$ discontinuous Galerkin finite elements (in space) on a mesh of size h and a spherical harmonics approximation of order N (in the angular variable), the convergence rate is of order $O( N^{−t} + h^k )$ for a smooth solution which admits partial derivatives of order k + 1 and t with respect to the spatial and angular variables, respectively. For k = 0 (piecewise constant finite elements) we also obtain a convergence result of order $O( N^{−t} + h^{1/2} )$. Numerical experiments in 1, 2 and 3 dimensions are provided, showing a better convergence behavior for the L 2-norm, typically of one more order, $O( N^{−t} + h^{k+1} )$.
• Mean field games of controls: On the convergence of Nash equilibria
  
  • Djete Mao Fabrice
  The Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2023, 33 (4). (10.1214/22-AAP1879)
  DOI : 10.1214/22-AAP1879
• Statistical Error Bounds for Weighted Mean and Median, with Application to Robust Aggregation of Cryptocurrency Data
  
  • Allouche Michaël
  • Echenim Mnacho
  • Gobet Emmanuel
  • Maurice Anne-Claire
  , 2023.
• Structured dictionary learning of rating migration matrices for credit risk modeling
  
  • Allouche Michaël
  • Gobet Emmanuel
  • Lage Clara
  • Mangin Edwin
  , 2023.
• A Rank-Based Reward between a Principal and a Field of Agents: Application to Energy Savings
  
  • Alasseur Clémence
  • Bayraktar Erhan
  • Dumitrescu Roxana
  • Jacquet Quentin
  , 2023. In this paper, we consider the problem of a Principal aiming at designing a reward function for a population of heterogeneous agents. We construct an incentive based on the ranking of the agents, so that a competition among the latter is initiated. We place ourselves in the limit setting of mean-field type interactions and prove the existence and uniqueness of the equilibrium distribution for a given reward, for which we can find an explicit representation. Focusing first on the homogeneous setting, we characterize the optimal reward function using a convex reformulation of the problem and provide an interpretation of its behaviour. We then show that this characterization still holds for a sub-class of heterogeneous populations. For the general case, we propose a convergent numerical method which fully exploits the characterization of the mean-field equilibrium. We develop a case study related to the French market of Energy Saving Certificates based on the use of realistic data, which shows that the ranking system allows to achieve the sobriety target imposed by the European commission.
• Reducing exit-times of diffusions with repulsive interactions
  
  • Chaudru de Raynal Paul-Eric
  • Duong Manh Hong
  • Monmarché Pierre
  • Tomasevic Milica
  • Tugaut Julian
  ESAIM: Probability and Statistics, EDP Sciences, 2023, 27, pp.723-748. In this work we prove a Kramers' type law for the low-temperature behavior of the exit-times from a metastable state for a class of self-interacting nonlinear diffusion processes. Contrary to previous works, the interaction is not assumed to be convex, which means that this result covers cases where the exit-time for the interacting process is smaller than the exit-time for the associated non-interacting process. The technique of the proof is based on the fact that, under an appropriate contraction condition, the interacting process is conveniently coupled with a non-interacting (linear) Markov process where the interacting law is replaced by a constant Dirac mass at the fixed point of the deterministic zero-temperature process. (10.1051/ps/2023012)
  DOI : 10.1051/ps/2023012
• Introduction to Many-Criteria Optimization and Decision Analysis
  
  • Brockhoff Dimo
  • Emmerich Michael
  • Naujoks Boris
  • Purshouse Robin
  , 2023, pp.3-28. Many-objective optimization problems (MaOPs) are problems that feature four or more objectives, criteria or attributes that must be considered simultaneously. MaOPs often arise in real-world situations and the development of algorithms for solving MaOPs has become one of the hot topics in the field of evolutionary multi-criteria optimization (EMO). However, much of this energy devoted to MaOP research is arguably detached from the challenges of, and decision analysis requirements for, MaOPs. Motivated by this gap, the authors of this chapter organized a Lorentz Center workshop in 2019 entitled Many-Criteria Optimization and Decision Analysis (MACODA) bringing researchers and practitioners together to reflect on the challenges in many-objective optimization and analysis, and to develop a vision for the next decade of MACODA research. From the workshop arose the MACODA book, for which this chapter forms the introduction. The chapter describes the organizers’ perspectives on the challenges of MaOP. It introduces the history of MaOP principally from the perspective of EMO, from where the terminology originated, but drawing important connections to pre-existing work in the field of multi-criteria decision-making (MCDM) which was the source or inspiration for many EMO ideas. The chapter then offers a brief review of the present state of MACODA research, covering major algorithms, scalarization approaches, objective-space reduction, order extensions to Pareto dominance, preference elicitation, wider decision-maker interaction methods and visualization. In drawing together the vision for MACODA in 2030, the chapter provides synopses of the unique and varied contributions that comprise the MACODA book and identifies further under-explored topics worthy of consideration by researchers over the next decade and beyond. (10.1007/978-3-031-25263-1_1)
  DOI : 10.1007/978-3-031-25263-1_1
• Many-Criteria Optimization and Decision Analysis
  
  • Brockhoff Dimo
  • Emmerich Michael
  • Naujoks Boris
  • Purshouse Robin
  , 2023. (10.1007/978-3-031-25263-1)
  DOI : 10.1007/978-3-031-25263-1
• Balanced Training of Energy-Based Models with Adaptive Flow Sampling
  
  • Grenioux Louis
  • Moulines Éric
  • Gabrié Marylou
  , 2023. Energy-based models (EBMs) are versatile density estimation models that directly parameterize an unnormalized log density. Although very flexible, EBMs lack a specified normalization constant of the model, making the likelihood of the model computationally intractable. Several approximate samplers and variational inference techniques have been proposed to estimate the likelihood gradients for training. These techniques have shown promising results in generating samples, but little attention has been paid to the statistical accuracy of the estimated density, such as determining the relative importance of different classes in a dataset. In this work, we propose a new maximum likelihood training algorithm for EBMs that uses a different type of generative model, normalizing flows (NF), which have recently been proposed to facilitate sampling. Our method fits an NF to an EBM during training so that an NF-assisted sampling scheme provides an accurate gradient for the EBMs at all times, ultimately leading to a fast sampler for generating new data.
• Automated approach for source location in shallow waters
  
  • Niclas Angèle
  • Garnier Josselin
  , 2023. This paper proposes a fully automated method for recovering the location of a source and medium parameters in shallow waters. The scenario involves an unknown source emitting low-frequency sound waves in a shallow water environment, and a single hydrophone recording the signal. Firstly, theoretical tools are introduced to understand the robustness of the warping method and to propose and analyze an automated way to separate the modal components of the recorded signal. Secondly, using the spectrogram of each modal component, the paper investigates the best way to recover the modal travel times and provides stability estimates. Finally, a penalized minimization algorithm is presented to recover estimates of the source location and medium parameters. The proposed method is tested on experimental data of right whale gunshot and combustive sound sources, demonstrating its effectiveness in real-world scenarios.
• The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems
  
  • Akian Marianne
  • Béreau Antoine
  • Gaubert Stéphane
  , 2023. (10.1145/3597066.3597089)
  DOI : 10.1145/3597066.3597089
• An Active Learning Strategy for Joint Surrogate Models Construction with Compatibility Conditions: Application to VPP
  
  • Pocheau Malo
  • Le Maître Olivier
  • Bañuls Renaud
  Journal of Sailing Technology, The Society of Naval Architects and Marine Engineers, 2023, 8 (01), pp.76-95. Static Velocity Prediction Programs (VPP) are standard tools in sailing yachts’ design and performance assessment. Predicting the maximal steady velocity of a yacht involves resolving constrained optimization problems. These problems have a prohibitive computational cost when using high-fidelity global modeling of the yacht. This difficulty has motivated the introduction of modular approaches, decomposing the global model into subsystems modeled independently and approximated by surrogate models (response surfaces). The maximum boat speed for prescribed conditions solves an optimization problem for the trimming parameters of the model constrained by compatibility conditions between the subsystems’ surrogate solution (e.g., the yacht equilibrium). The accuracy of the surrogates is then critical for the quality of the resulting VPP. This paper relies on Gaussian Process (GP) models of the subsystems and introduces an original sequential Active Learning Method (ALM) for their joint construction. Our ALM exploits the probabilistic nature of the GP models to decide the enrichment of the training sets using an infilling criterion that combines the predictive uncertainty of the surrogate models and the likelihood of equilibrium at every input point. The resulting strategy enables the concentration of the computational effort around the manifolds where equilibrium is satisfied. The results presented compare ALM with a standard (uninformed) Quasi-Monte Carlo method, which samples the input space of the subsystems uniformly. ALM surrogates have higher accuracy in the equilibrium regions for equal construction cost, with improved mean prediction and reduced prediction uncertainty. We further investigate the effect of the prediction uncertainty on the numerical VPP and in a routing problem. (10.5957/jst/2023.8.5.76)
  DOI : 10.5957/jst/2023.8.5.76
• Decomposed resolution of finite-state aggregative optimal control problems
  
  • Liu Kang
  • Oudjane Nadia
  • Pfeiffer Laurent
  , 2023, pp.56-63. A class of finite-state and discrete-time optimal control problems is introduced. The problems involve a large number of agents with independent dynamics, which interact through an aggregative term in the cost function. The problems are intractable by dynamic programming. We describe and analyze a decomposition method that only necessitates to solve at each iteration small-scale and independent optimal control problems associated with each single agent. When the number of agents is large, the convergence of the method to a nearly optimal solution is ensured, despite the absence of convexity of the problem. The procedure is based on a method called Stochastic Frank-Wolfe algorithm, designed for general nonconvex aggregative optimization problems. Numerical results are presented, for a toy model of the charging management of a battery fleet. (10.1137/1.9781611977745.8)
  DOI : 10.1137/1.9781611977745.8
• Conformal Prediction with Missing Values
  
  • Zaffran Margaux
  • Dieuleveut Aymeric
  • Josse Julie
  • Romano Yaniv
  , 2023, PMLR202, pp.40578. Conformal prediction is a theoretically grounded framework for constructing predictive intervals. We study conformal prediction with missing values in the covariates -- a setting that brings new challenges to uncertainty quantification. We first show that the marginal coverage guarantee of conformal prediction holds on imputed data for any missingness distribution and almost all imputation functions. However, we emphasize that the average coverage varies depending on the pattern of missing values: conformal methods tend to construct prediction intervals that undercover the response conditionally to some missing patterns. This motivates our novel generalized conformalized quantile regression framework, missing data augmentation, which yields prediction intervals that are valid conditionally to the patterns of missing values, despite their exponential number. We then show that a universally consistent quantile regression algorithm trained on the imputed data is Bayes optimal for the pinball risk, thus achieving valid coverage conditionally to any given data point. Moreover, we examine the case of a linear model, which demonstrates the importance of our proposal in overcoming the heteroskedasticity induced by missing values. Using synthetic and data from critical care, we corroborate our theory and report improved performance of our methods.
• Comparison of meta-learners for estimating multi-valued treatment heterogeneous effects
  
  • Acharki Naoufal
  • Lugo Ramiro
  • Bertoncello Antoine
  • Garnier Josselin
  , 2023, 202, pp.91-132. Conditional Average Treatment Effects (CATE) estimation is one of the main challenges in causal inference with observational data. In addition to Machine Learning based-models, nonparametric estimators called meta-learners have been developed to estimate the CATE with the main advantage of not restraining the estimation to a specific supervised learning method. This task becomes, however, more complicated when the treatment is not binary as some limitations of the naive extensions emerge. This paper looks into meta-learners for estimating the heterogeneous effects of multivalued treatments. We consider different metalearners, and we carry out a theoretical analysis of their error upper bounds as functions of important parameters such as the number of treatment levels, showing that the naive extensions do not always provide satisfactory results. We introduce and discuss meta-learners that perform well as the number of treatments increases. We empirically confirm the strengths and weaknesses of those methods with synthetic and semi-synthetic datasets.
• On Sampling with Approximate Transport Maps
  
  • Grenioux Louis
  • Durmus Alain Oliviero
  • Moulines Éric
  • Gabrié Marylou
  Proceedings of the 40th International Conference on Machine Learning, PMLR, 2023, 202, pp.11698-11733. Transport maps can ease the sampling of distributions with non-trivial geometries by transforming them into distributions that are easier to handle. The potential of this approach has risen with the development of Normalizing Flows (NF) which are maps parameterized with deep neural networks trained to push a reference distribution towards a target. NF-enhanced samplers recently proposed blend (Markov chain) Monte Carlo methods with either (i) proposal draws from the flow or (ii) a flow-based reparametrization. In both cases, the quality of the learned transport conditions performance. The present work clarifies for the first time the relative strengths and weaknesses of these two approaches. Our study concludes that multimodal targets can be reliably handled with flow-based proposals up to moderately high dimensions. In contrast, methods relying on reparametrization struggle with multimodality but are more robust otherwise in high-dimensional settings and under poor training. To further illustrate the influence of target-proposal adequacy, we also derive a new quantitative bound for the mixing time of the Independent Metropolis-Hastings sampler.
• Naive imputation implicitly regularizes high-dimensional linear models
  
  • Ayme Alexis
  • Boyer Claire
  • Dieuleveut Aymeric
  • Scornet Erwan
  , 2023. Two different approaches exist to handle missing values for prediction: either imputation, prior to fitting any predictive algorithms, or dedicated methods able to natively incorporate missing values. While imputation is widely (and easily) use, it is unfortunately biased when low-capacity predictors (such as linear models) are applied afterward. However, in practice, naive imputation exhibits good predictive performance. In this paper, we study the impact of imputation in a high-dimensional linear model with MCAR missing data. We prove that zero imputation performs an implicit regularization closely related to the ridge method, often used in high-dimensional problems. Leveraging on this connection, we establish that the imputation bias is controlled by a ridge bias, which vanishes in high dimension. As a predictor, we argue in favor of the averaged SGD strategy, applied to zero-imputed data. We establish an upper bound on its generalization error, highlighting that imputation is benign in the d √ n regime. Experiments illustrate our findings.
• Unbiasing and robustifying implied volatility calibration in a cryptocurrency market with large bid-ask spreads and missing quotes
  
  • Echenim Mnacho
  • Gobet Emmanuel
  • Maurice Anne-Claire
  Quantitative Finance, Taylor & Francis (Routledge), 2023, 23 (9), pp.1285-1304. We design a novel calibration procedure that is designed to handle the specific characteristics of options on cryptocurrency markets, namely large bid-ask spreads and the possibility of missing or incoherent prices in the considered data sets. We show that this calibration procedure is significantly more robust and accurate than the standard one based on trade and mid-prices. (10.1080/14697688.2023.2229022)
  DOI : 10.1080/14697688.2023.2229022
• Orthogonal directions constrained gradient method: from non-linear equality constraints to stiefel manifold
  
  • Schechtman Sholom
  • Tiapkin Daniil
  • Muehlebach Michael
  • Moulines Éric
  , 2023, 195, pp.1228--1258. We consider the problem of minimizing a non-convex function over a smooth manifold $\mathcal{M}$. We propose a novel algorithm, the Orthogonal Directions Constrained Gradient Method (ODCGM) which only requires computing a projection onto a vector space. ODCGM is infeasible but the iterates are constantly pulled towards the manifold, ensuring the convergence of ODCGM towards $\mathcal{M}$. ODCGM is much simpler to implement than the classical methods which require the computation of a retraction. Moreover, we show that ODCGM exhibits the near-optimal oracle complexities $\mathcal{O}(1/\varepsilon^2)$ and $\mathcal{O}(1/\varepsilon^4)$ in the deterministic and stochastic cases, respectively. Furthermore, we establish that, under an appropriate choice of the projection metric, our method recovers the landing algorithm of Ablin and Peyr\'e (2022), a recently introduced algorithm for optimization over the Stiefel manifold. As a result, we significantly extend the analysis of Ablin and Peyr\'e (2022), establishing near-optimal rates both in deterministic and stochastic frameworks. Finally, we perform numerical experiments which shows the efficiency of ODCGM in a high-dimensional setting.
• Benchmarking CMA-ES with Basic Integer Handling on a Mixed-Integer Test Problem Suite
  
  • Marty Tristan
  • Semet Yann
  • Auger Anne
  • Héron Sébastien
  • Hansen Nikolaus
  , 2023, pp.1628-1635. We compare the performances of one implementation of CMA-ES (pycma version 3.3.0) for optimizing functions with both continuous and integer variables. The implementation incorporates a lower bound on the variance along the integer coordinates to keep the optimization from stalling. This benchmark will serve as a baseline for further works on pycma. Results show substantial improvement since the last benchmarked version of pycma. Also this implementation is competitive with other mixed integer algorithms. (10.1145/3583133.3596411)
  DOI : 10.1145/3583133.3596411
• CMA-ES and Advanced Adaptation Mechanisms
  
  • Akimoto Youhei
  • Hansen Nikolaus
  , 2023, pp.1157-1182. (10.1145/3583133.3595054)
  DOI : 10.1145/3583133.3595054
• An Introduction to Scientific Experimentation and Benchmarking
  
  • Auger Anne
  • Hansen Nikolaus
  , 2023, pp.854-877. (10.1145/3583133.3595064)
  DOI : 10.1145/3583133.3595064
• GECCO 2023 Tutorial on Benchmarking Multiobjective Optimizers 2.0
  
  • Brockhoff Dimo
  • Tusar Tea
  , 2023, pp.1183-1212. Benchmarking is an important part of algorithm design, selection and recommendation---both in single- and multiobjective optimization. Benchmarking multiobjective solvers seems at first sight more complicated than benchmarking single-objective ones as there exists no natural total order on the objective space. In the past, comparisons of multiobjective solvers have therefore been done either entirely visually (at first) or via quality indicators and the attainment function. Only very recently did we realize that the quality indicator approach transforms a multiobjective problem into a single-objective (set-based) problem and thus all recent progress from the rapidly evolving single-objective benchmarking field can be transferred to the multiobjective case as well. Moreover, many multiobjective test functions have been proposed in the past but not much has changed in the last 15 or so years in terms of addressing the disadvantages of those problems (like Pareto sets on constraint boundaries, usage of distance variables, etc.). In this tutorial, we will discuss the past and future of benchmarking multiobjective optimizers. In particular, we will discuss the new view on benchmarking multiobjective algorithms by falling back on single-objective comparisons and thus being able to use all methodologies and tools from the single-objective domain such as empirical distributions of runtimes. We will also discuss the advantages and drawbacks of some widely used multiobjective test suites that we have all become familiar with over the years and explain how we can do better: by going back to the roots of what a multi-objective problem is in practice, namely the simultaneous optimization of multiple objective functions. Finally, we discuss recent advances in the visualization of (multiobjective) problem landscapes and compare the previous and newly proposed benchmark problems in the context of those landscape visualizations. (10.1145/2598394.2605339)
  DOI : 10.1145/2598394.2605339