Publications

2023

• Goal-oriented sensitivity analysis of hyperparameters in deep learning
  
  • Novello Paul
  • Poëtte Gaël
  • Lugato David
  • Congedo Pietro Marco
  Journal of Scientific Computing, Springer Verlag, 2023, 94 (3), pp.45. Tackling new machine learning problems with neural networks always means optimizing numerous hyperparameters that define their structure and strongly impact their performances. In this work, we study the use of goal-oriented sensitivity analysis, based on the Hilbert-Schmidt Independence Criterion (HSIC), for hyperparameter analysis and optimization. Hyperparameters live in spaces that are often complex and awkward. They can be of different natures (categorical, discrete, boolean, continuous), interact, and have inter-dependencies. All this makes it non-trivial to perform classical sensitivity analysis. We alleviate these difficulties to obtain a robust analysis index that is able to quantify hyperparameters’ relative impact on a neural network’s final error. This valuable tool allows us to better understand hyperparameters and to make hyperparameter optimization more interpretable. We illustrate the benefits of this knowledge in the context of hyperparameter optimization and derive an HSIC-based optimization algorithm that we apply on MNIST and Cifar, classical machine learning data sets, but also on the approximation of Runge function and Bateman equations solution, of interest for scientific machine learning. This method yields competitive and cost-effective neural networks. (10.1007/s10915-022-02083-4)
  DOI : 10.1007/s10915-022-02083-4
• Observation of light thermalization to negative-temperature Rayleigh-Jeans equilibrium states in multimode optical fibers
  
  • Baudin K.
  • Garnier J.
  • Fusaro A.
  • Berti N.
  • Michel C.
  • Krupa K.
  • Millot G.
  • Picozzi Antonio
  Physical Review Letters, American Physical Society, 2023, 130 (6), pp.063801. Although the temperature of a thermodynamic system is usually believed to be a positive quantity, under particular conditions, negative temperature equilibrium states are also possible. Negative temperature equilibriums have been observed with spin systems, cold atoms in optical lattices and two-dimensional quantum superfluids. Here we report the observation of Rayleigh-Jeans thermalization of light waves to negative temperature equilibrium states. The optical wave relaxes to the equilibrium state through its propagation in a multimode optical fiber, i.e., in a conservative Hamiltonian system. The bounded energy spectrum of the optical fiber enables negative temperature equilibriums with high energy levels (high order fiber modes) more populated than low energy levels (low order modes). Our experiments show that negative temperature speckle beams are featured, in average, by a non-monotonous radial intensity profile. The experimental results are in quantitative agreement with the Rayleigh-Jeans theory without free parameters. Bringing negative temperatures to the field of optics opens the door to the investigation of fundamental issues of negative temperature states in a flexible experimental environment. (10.1103/PhysRevLett.130.063801)
  DOI : 10.1103/PhysRevLett.130.063801
• Numerical shape optimization among convex sets
  
  • Bogosel Beniamin
  Applied Mathematics and Optimization, Springer Verlag (Germany), 2023, 87 (1), pp.1. This article proposes a new discrete framework for approximating solutions to shape optimization problems under convexity constraints. The numerical method, based on the support function or the gauge function, is guaranteed to generate discrete convex shapes and is easily implementable using standard optimization software. The framework can handle various objective functions ranging from geometric quantities to functionals depending on partial differential equations. Width or diameter constraints are handled using the support function. Functionals depending on a convex body and its polar body can be handled using a unified framework. (10.1007/s00245-022-09920-w)
  DOI : 10.1007/s00245-022-09920-w
• Development and Theoretical Analysis of the Algorithms for Optimal Control and Reinforcement Learning
  
  • Kaledin Maksim
  , 2023. In this PhD dissertation, we address the problems of optimal stopping and learning in Markov decision processes used in reinforcement learning (RL). In the first direction, we derive complexity estimates for the algorithm called Weighted Stochastic Mesh (WSM) and give a new method for comparing the complexity of optimal stopping algorithms with the semi tractability index. We show that WSM is optimal with respect to this criterion when the commonly used regression methods are much mess effectiveFor reinforcement learning, we give a non-asymptotic convergence analysis of a stochastic approximation scheme with two time scales - gradient TD - under assumptions of "martingale increment" noise - buffer replay - and of "Markov noise" (when learning is done along a single run). We obtain upper bounds that are rate-optimal by constructing an error expansion method that provides accurate control of the remainders terms.We also present a new algorithm for variance reduction in policy gradient schemes. The proposed approach is based on minimising an estimator for the empirical variance of the weighted rewards. We establish theoretical and practical gains over the classical actor-critic (A2C) method. (10.70675/d7fbe111z5bacz4419zb392z7adbeab6f5f9)
  DOI : 10.70675/d7fbe111z5bacz4419zb392z7adbeab6f5f9
• Truncation errors and modified equations for the lattice Boltzmann method via the corresponding Finite Difference schemes
  
  • Bellotti Thomas
  ESAIM: Mathematical Modelling and Numerical Analysis, Société de Mathématiques Appliquées et Industrielles (SMAI) / EDP, 2023, 57, pp.1225–1255. Lattice Boltzmann schemes are efficient numerical methods to solve a broad range of problems under the form of conservation laws. However, they suffer from a chronic lack of clear theoretical foundations. In particular, the consistency analysis and the derivation of the modified equations are still open issues. This has prevented, until today, to have an analogous of the Lax equivalence theorem for Lattice Boltzmann schemes. We propose a rigorous consistency study and the derivation of the modified equations for any lattice Boltzmann scheme under acoustic and diffusive scalings. This is done by passing from a kinetic (lattice Boltzmann) to a macroscopic (Finite Difference) point of view at a fully discrete level in order to eliminate the non-conserved moments relaxing away from the equilibrium. We rewrite the lattice Boltzmann scheme as a multi-step Finite Difference scheme on the conserved variables, as introduced in our previous contribution. We then perform the usual analyses for Finite Difference by exploiting its precise characterization using matrices of Finite Difference operators. Though we present the derivation of the modified equations until second-order under acoustic scaling, we provide all the elements to extend it to higher orders, since the kinetic-macroscopic connection is conducted at the fully discrete level. Finally, we show that our strategy yields, in a more rigorous setting, the same results as previous works in the literature. (10.1051/m2an/2023008)
  DOI : 10.1051/m2an/2023008
• STATISTICAL INFERENCE FOR ROUGH VOLATILITY: MINIMAX THEORY
  
  • Chong Carsten
  • Hoffmann Marc
  • Liu Yanghui
  • Szymanski Grégoire
  • Rosenbaum Mathieu
  , 2023. Rough volatility models have gained considerable interest in the quantitative finance community in recent years. In this paradigm, the volatility of the asset price is driven by a fractional Brownian motion with a small value for the Hurst parameter H. In this work, we provide a rigorous statistical analysis of these models. To do so, we establish minimax lower bounds for parameter estimation and design procedures based on wavelets attaining them. We notably obtain an optimal speed of convergence of n −1/(4H+2) for estimating H based on n sampled data, extending results known only for the easier case H > 1/2 so far. We therefore establish that the parameters of rough volatility models can be inferred with optimal accuracy in all regimes.
• Optimal incentives in a limit order book: a SPDE control approach
  
  • Baldacci Bastien
  • Bergault Philippe
  , 2023. With the fragmentation of electronic markets, exchanges are now competing in order to attract trading activity on their platform. Consequently, they developed several regulatory tools to control liquidity provision / consumption on their liquidity pool. In this paper, we study the problem of an exchange using incentives in order to increase market liquidity. We model the limit order book as the solution of a stochastic partial differential equation (SPDE) as in [12]. The incentives proposed to the market participants are functions of the time and the distance of their limit order to the mid-price. We formulate the control problem of the exchange who wishes to modify the shape of the order book by increasing the volume at specific limits. Due to the particular nature of the SPDE control problem, we are able to characterize the solution with a classic Feynman-Kac representation theorem. Moreover, when studying the asymptotic behavior of the solution, a specific penalty function enables the exchange to obtain closed-form incentives at each limit of the order book. We study numerically the form of the incentives and their impact on the shape of the order book, and analyze the sensitivity of the incentives to the market parameters.
• Automated Market Makers: Mean-Variance Analysis of LPs Payoffs and Design of Pricing Functions
  
  • Bergault Philippe
  • Bertucci Louis
  • Bouba David
  • Guéant Olivier
  , 2023. We analyze the performance of Liquidity Providers (LPs) providing liquidity to different types of Automated Market Makers (AMMs). This analysis is carried out using a mean / standard deviation viewpoint \`a la Markowitz, though based on the PnL of LPs compared to that of agents holding coins outside of AMMs. We show that LPs tend to perform poorly in a wide variety of CFMMs under realistic market conditions. We then explore an alternative AMM design in which an oracle feeds the current market exchange rate to the AMM which then quotes a bid/ask spread. This allows us to define an efficient frontier for the performance of LPs in an idealized world with perfect information and to show that the smart use of oracles greatly improves LPs' risk / return profile, even in the case of a lagged oracle.
• A Formal Disproof of Hirsch Conjecture
  
  • Allamigeon Xavier
  • Canu Quentin
  • Strub Pierre-Yves
  , 2023, pp.17-29. The purpose of this paper is the formal verification of a counterexample of Santos et al. to the so-called Hirsch Conjecture on the diameter of polytopes (bounded convex polyhedra). In contrast with the pen-and-paper proof, our approach is entirely computational: we have implemented in Coq and proved correct an algorithm that explicitly computes, within the proof assistant, vertex-edge graphs of polytopes as well as their diameter. The originality of this certificate-based algorithm is to achieve a tradeoff between simplicity and efficiency. Simplicity is crucial in obtaining the proof of correctness of the algorithm. This proof splits into the correctness of an abstract algorithm stated over proof-oriented data types and the correspondence with a low-level implementation over computation-oriented data types. A special effort has been made to reduce the algorithm to a small sequence of elementary operations (e.g. matrix multiplications, basic routines on graphs), in order to make the derivation of the correctness of the low-level implementation more transparent. Efficiency allows us to scale up to polytopes with a challenging combinatorics. For instance, we formally check the two counterexamples to Hirsch conjecture due to Matschke, Santos and Weibel, respectively 20- and 23-dimensional polytopes with 36425 and 73224 vertices involving rational coefficients with up to 20 digits. We also illustrate the performance of the method by computing the list of vertices or the diameter of well-known classes of polytopes, such as (polars of) cyclic polytopes involved in McMullen's Upper Bound Theorem. (10.1145/3573105.3575678)
  DOI : 10.1145/3573105.3575678
• State and parameter learning with PARIS particle Gibbs
  
  • Cardoso Gabriel Victorino
  • Janati Yazid
  • Le Corff Sylvain
  • Moulines Éric
  • Olsson Jimmy
  , 2023. Non-linear state-space models, also known as general hidden Markov models, are ubiquitous in statistical machine learning, being the most classical generative models for serial data and sequences in general. The particle-based, rapid incremental smoother (PARIS) is a sequential Monte Carlo (SMC) technique allowing for efficient online approximation of expectations of additive functionals under the smoothing distribution in these models. Such expectations appear naturally in several learning contexts, such as likelihood estimation (MLE) and Markov score climbing (MSC). PARIS has linear computational complexity, limited memory requirements and comes with non-asymptotic bounds, convergence results and stability guarantees. Still, being based on selfnormalised importance sampling, the PARIS estimator is biased. Our first contribution is to design a novel additive smoothing algorithm, the Parisian particle Gibbs (PPG) sampler, which can be viewed as a PARIS algorithm driven by conditional SMC moves, resulting in bias-reduced estimates of the targeted quantities. We substantiate the PPG algorithm with theoretical results, including new bounds on bias and variance as well as deviation inequalities. Our second contribution is to apply PPG in a learning framework, covering MLE and MSC as special examples. In this context, we establish, under standard assumptions, non-asymptotic bounds highlighting the value of bias reduction and the implicit Rao-Blackwellization of PPG. These are the first non-asymptotic results of this kind in this setting. We illustrate our theoretical results with numerical experiments supporting our claims. (10.48550/arXiv.2301.00900)
  DOI : 10.48550/arXiv.2301.00900
• Human-environment feedback and the consistency of proenvironmental behavior
  
  • Ecotière Claire
  • Billiard Sylvain
  • André Jean-Baptiste
  • Collet Pierre
  • Ferrière Régis
  • Méléard Sylvie
  PLoS Computational Biology, PLOS, 2023, 19 (9), pp.e1011429. Addressing global environmental crises such as anthropogenic climate change requires the consistent adoption of proenvironmental behavior by a large part of a population. Here, we develop a mathematical model of a simple behavior-environment feedback loop to ask how the individual assessment of the environmental state combines with social interactions to influence the consistent adoption of proenvironmental behavior, and how this feeds back to the perceived environmental state. In this stochastic individual-based model, individuals can switch between two behaviors, ‘active’ (or actively proenvironmental) and ‘baseline’, differing in their perceived cost (higher for the active behavior) and environmental impact (lower for the active behavior). We show that the deterministic dynamics and the stochastic fluctuations of the system can be approximated by ordinary differential equations and a Ornstein-Uhlenbeck type process. By definition, the proenvironmental behavior is adopted consistently when, at population stationary state, its frequency is high and random fluctuations in frequency are small. We find that the combination of social and environmental feedbacks can promote the spread of costly proenvironmental behavior when neither, operating in isolation, would. To be adopted consistently, strong social pressure for proenvironmental action is necessary but not sufficient—social interactions must occur on a faster timescale compared to individual assessment, and the difference in environmental impact must be small. This simple model suggests a scenario to achieve large reductions in environmental impact, which involves incrementally more active and potentially more costly behavior being consistently adopted under increasing social pressure for proenvironmentalism. (10.1371/journal.pcbi.1011429)
  DOI : 10.1371/journal.pcbi.1011429
• Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization
  
  • Fort Gersende
  • Moulines Eric
  Statistics and Computing, Springer Verlag (Germany), 2023, 33, pp.65. This paper introduces a novel algorithm, the Perturbed Proximal Preconditioned SPIDER algorithm (3P-SPIDER), designed to solve finite sum non-convex composite optimization. It is a stochastic Variable Metric Forward-Backward algorithm, which allows approximate preconditioned forward operator and uses a variable metric proximity operator as the backward operator; it also proposes a mini-batch strategy with variance reduction to address the finite sum setting. We show that 3P-SPIDER extends some Stochastic preconditioned Gradient Descent-based algorithms and some Incremental Expectation Maximization algorithms to composite optimization and to the case the forward operator can not be computed in closed form. We also provide an explicit control of convergence in expectation of 3P-SPIDER, and study its complexity in order to satisfy the epsilon-approximate stationary condition. Our results are the first to combine the composite non-convex optimization setting, a variance reduction technique to tackle the finite sum setting by using a minibatch strategy and, to allow deterministic or random approximations of the preconditioned forward operator. Finally, through an application to inference in a logistic regression model with random effects, we numerically compare 3P-SPIDER to other stochastic forward-backward algorithms and discuss the role of some design parameters of 3P-SPIDER. (10.1007/s11222-023-10230-6)
  DOI : 10.1007/s11222-023-10230-6
• Federated Averaging Langevin Dynamics: Toward a unified theory and new algorithms
  
  • Plassier Vincent
  • Durmus Alain
  • Moulines Eric
  , 2023. This paper focuses on Bayesian inference in a federated learning context (FL). While several distributed MCMC algorithms have been proposed, few consider the specific limitations of FL such as communication bottlenecks and statistical heterogeneity. Recently, Federated Averaging Langevin Dynamics (FALD) was introduced, which extends the Federated Averaging algorithm to Bayesian inference. We obtain a novel tight non-asymptotic upper bound on the Wasserstein distance to the global posterior for FALD. This bound highlights the effects of statistical heterogeneity, which causes a drift in the local updates that negatively impacts convergence. We propose a new algorithm VR-FALD* that uses control variates to correct the client drift. We establish non-asymptotic bounds showing that VR-FALD* is not affected by statistical heterogeneity. Finally, we illustrate our results on several FL benchmarks for Bayesian inference.
• Well posedness and stochastic derivation of a diffusion-growth-fragmentation equation in a chemostat
  
  • Tchouanti Josué
  Stochastics and Partial Differential Equations: Analysis and Computations, Springer US, 2023. We study the existence and uniqueness of the solution of a non-linear coupled system constituted of a degenerate diffusion-growth-fragmentation equation and a differential equation, resulting from the modeling of bacterial growth in a chemostat. This system is derived, in a large population approximation, from a stochastic individual-based model where each individual is characterized by a non-negative real valued trait described by a diffusion. Two uniqueness results are highlighted. They differ in their hypotheses related to the influence of the resource on individual trait dynamics, the main difficulty being the non-linearity due to this dependence and the degeneracy of the diffusion coefficient. Further we show that the semi-group of the stochastic trait dynamics admits a density by probabilistic arguments, that allows the measure solution of the diffusiongrowth-fragmentation equation to be a function with a certain Besov regularity. (10.1007/s40072-023-00288-8)
  DOI : 10.1007/s40072-023-00288-8
• A Posteriori Validation of Generalized Polynomial Chaos Expansions
  
  • Breden Maxime
  SIAM Journal on Applied Dynamical Systems, Society for Industrial and Applied Mathematics, 2023, 22 (2), pp.765-801. Generalized polynomial chaos (gPC) expansions are a powerful tool for studying differential equations with random coefficients, allowing, in particular, one to efficiently approximate random invariant sets associated with such equations. In this work, we use ideas from validated numerics in order to obtain rigorous a posteriori error estimates together with existence results about gPC expansions of random invariant sets. This approach also provides a new framework for conducting validated continuation, i.e., for rigorously computing isolated branches of solutions in parameter-dependent systems, which generalizes in a straightforward way to multiparameter continuation. We illustrate the proposed methodology by rigorously computing random invariant periodic orbits in the Lorenz system, as well as branches and 2 dimensional manifolds of steady states of the Swift–Hohenberg equation. (10.1137/22M1493197)
  DOI : 10.1137/22M1493197
• Development and clinical validation of real‐time artificial intelligence diagnostic companion for fetal ultrasound examination
  
  • Stirnemann Julien J.
  • Besson Rémy
  • Spaggiari Emmanuel
  • Rojo Sandra
  • Logé Frédéric
  • Saint Paul Hélène Peyro
  • Allassonnière Stéphanie
  • Le Pennec Erwan
  • Hutchinson C.
  • Sebire Neil J
  • Ville Yves
  Ultrasound in Obstetrics and Gynecology = Ultrasound in Obstetrics & Gynecology, Wiley-Blackwell, 2023, 62 (3), pp.353-360. Objective: Prenatal diagnosis of a rare disease on ultrasound relies on a physician's ability to remember an intractable amount of knowledge. We developed a real‐time decision support system (DSS) that suggests, at each step of the examination, the next phenotypic feature to assess, optimizing the diagnostic pathway to the smallest number of possible diagnoses. The objective of this study was to evaluate the performance of this real‐time DSS using clinical data. Methods This validation study was conducted on a database of 549 perinatal phenotypes collected from two referral centers (one in France and one in the UK). Inclusion criteria were: at least one anomaly was visible on fetal ultrasound after 11 weeks' gestation; the anomaly was confirmed postnatally; an associated rare disease was confirmed or ruled out based on postnatal/postmortem investigation, including physical examination, genetic testing and imaging; and, when confirmed, the syndrome was known by the DSS software. The cases were assessed retrospectively by the software, using either the full phenotype as a single input, or a stepwise input of phenotypic features, as prompted by the software, mimicking its use in a real‐life clinical setting. Adjudication of discordant cases, in which there was disagreement between the DSS output and the postnatally confirmed (‘ascertained’) diagnosis, was performed by a panel of external experts. The proportion of ascertained diagnoses within the software's top‐10 differential diagnoses output was evaluated, as well as the sensitivity and specificity of the software to select correctly as its best guess a syndromic or isolated condition. Results: The dataset covered 110/408 (27%) diagnoses within the software's database, yielding a cumulative prevalence of 83%. For syndromic cases, the ascertained diagnosis was within the top‐10 list in 93% and 83% of cases using the full‐phenotype and stepwise input, respectively, after adjudication. The full‐phenotype and stepwise approaches were associated, respectively, with a specificity of 94% and 96% and a sensitivity of 99% and 84%. The stepwise approach required an average of 13 queries to reach the final set of diagnoses. Conclusions: The DSS showed high performance when applied to real‐world data. This validation study suggests that such software can improve perinatal care, efficiently providing complex and otherwise overlooked knowledge to care‐providers involved in ultrasound‐based prenatal diagnosis. (10.1002/uog.26242)
  DOI : 10.1002/uog.26242
• Filling the gap between individual-based evolutionary models and Hamilton-Jacobi equations
  
  • Champagnat Nicolas
  • Méléard Sylvie
  • Mirrahimi Sepideh
  • Chi Tran Viet
  Journal de l'École polytechnique — Mathématiques, École polytechnique, 2023, 10, pp.1247-1275. We consider a stochastic model for the evolution of a discrete population structured by a trait with values on a finite grid of the torus, and with mutation and selection. Traits are vertically inherited unless a mutation occurs, and influence the birth and death rates. We focus on a parameter scaling where population is large, individual mutations are small but not rare, and the grid mesh for the trait values is much smaller than the size of mutation steps. When considering the evolution of the population in a long time scale, the contribution of small sub-populations may strongly influence the dynamics. Our main result quantifies the asymptotic dynamics of sub-population sizes on a logarithmic scale. We establish that under the parameter scaling the logarithm of the stochastic population size process, conveniently normalized, converges to the unique viscosity solution of a Hamilton-Jacobi equation. Such Hamilton-Jacobi equations have already been derived from parabolic integro-differential equations and have been widely developed in the study of adaptation of quantitative traits. Our work provides a justification of this framework directly from a stochastic individual based model, leading to a better understanding of the results obtained within this approach. The proof makes use of almost sure maximum principles and careful controls of the martingale parts. (10.5802/jep.244)
  DOI : 10.5802/jep.244
• A growth-fragmentation-isolation process on random recursive trees and contact tracing
  
  • Bansaye Vincent
  • Gu Chenlin
  • Yuan Linglong
  The Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2023, 33 (6B), pp.5233-5278. We consider a random process on recursive trees, with three types of events. Vertices give birth at a constant rate (growth), each edge may be removed independently (fragmentation of the tree) and clusters (or trees) are frozen with a rate proportional to their sizes (isolation of connected component). A phase transition occurs when the isolation is able to stop the growthfragmentation process and cause extinction. When the process survives, the number of clusters increases exponentially and we prove that the normalised empirical measure of clusters a.s. converges to a limit law on recursive trees. We exploit the branching structure associated to the size of clusters, which is inherited from the splitting property of random recursive trees. This work is motivated by the control of epidemics and contact tracing where clusters correspond to trees of infected individuals that can be identified and isolated. We complement this work by providing results on the Malthusian exponent to describe the effect of control policies on epidemics. (10.1214/23-AAP1947)
  DOI : 10.1214/23-AAP1947
• Cross impact in derivative markets
  
  • Tomas Mehdi
  • Mastromatteo Iacopo
  • Benzaquen Michael
  Wilmott Journal, Wiley, 2023, 123, pp.16–28. We introduce a linear cross-impact framework in a setting in which the price of some given financial instruments (derivatives) is a deterministic function of one or more, possibly tradeable, stochastic factors (underlying). We show that a particular cross-impact model, the multivariate Kyle model, prevents arbitrage and aggregates (potentially non-stationary) traded order flows on derivatives into (roughly stationary) liquidity pools aggregating order flows traded on both derivatives and underlying. Using E-Mini futures and options along with VIX futures, we provide empirical evidence that the price formation process from order flows on derivatives is driven by cross-impact and confirm that the simple Kyle cross-impact model is successful at capturing parsimoniously such empirical phenomenology. Our framework may be used in practice for estimating execution costs, in particular hedging costs.
• Mean field game of mutual holding with defaultable agents, and systemic risk
  
  • Djete Mao Fabrice
  • Guo Gaoyue
  • Touzi Nizar
  SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2023, 64 (1), pp.24-58. We introduce the possibility of default in the mean field game of mutual holding of Djete and Touzi [11]. This is modeled by introducing absorption at the origin of the equity process. We provide an explicit solution of this mean field game. Moreover, we provide a particle system approximation, and we derive an autonomous equation for the time evolution of the default probability, or equivalently the law of the hitting time of the origin by the equity process. The systemic risk is thus described by the evolution of the default probability. (10.1137/24M1658668)
  DOI : 10.1137/24M1658668
• Time reversal of spinal processes for linear and non-linear branching processes near stationarity
  
  • Henry Benoît
  • Méléard Sylvie
  • Chi Tran Viet
  Electronic Journal of Probability, Institute of Mathematical Statistics (IMS), 2023, 28 (none). We consider a stochastic individual-based population model with competition, trait-structure affecting reproduction and survival, and changing environment. The changes of traits are described by jump processes, and the dynamics can be approximated in large population by a non-linear PDE with a non-local mutation operator. Using the fact that this PDE admits a non-trivial stationary solution, we can approximate the non-linear stochastic population process by a linear birth-death process where the interactions are frozen, as long as the population remains close to this equilibrium. This allows us to derive, when the population is large, the equation satisfied by the ancestral lineage of an individual uniformly sampled at a fixed time $T$, which is the path constituted of the traits of the ancestors of this individual in past times $t\leq T$. This process is a time inhomogeneous Markov process, but we show that the time reversal of this process possesses a very simple structure (e.g. time-homogeneous and independent of $T$). This extends recent results where the authors studied a similar model with a Laplacian operator but where the methods essentially relied on the Gaussian nature of the mutations. (10.1214/23-EJP911)
  DOI : 10.1214/23-EJP911
• Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach
  
  • Greco Giacomo
  • Noble Maxence
  • Conforti Giovanni
  • Durmus Alain
  , 2023. Computational optimal transport (OT) has recently emerged as a powerful framework with applications in various fields. In this paper we focus on a relaxation of the original OT problem, the entropic OT problem, which allows to implement efficient and practical algorithmic solutions, even in high dimensional settings. This formulation, also known as the Schrödinger Bridge problem, notably connects with Stochastic Optimal Control (SOC) and can be solved with the popular Sinkhorn algorithm. In the case of discrete-state spaces, this algorithm is known to have exponential convergence; however, achieving a similar rate of convergence in a more general setting is still an active area of research. In this work, we analyze the convergence of the Sinkhorn algorithm for probability measures defined on the d-dimensional torus , that admit densities with respect to the Haar measure. In particular, we prove pointwise exponential convergence of Sinkhorn iterates and their gradient. Our proof relies on the connection between these iterates and the evolution along the Hamilton-Jacobi-Bellman equations of value functions obtained from SOC-problems. Our approach is novel in that it is purely probabilistic and relies on coupling by reflection techniques for controlled diffusions on the torus.
• Tree-Based Diffusion Schrödinger Bridge with Applications to Wasserstein Barycenters
  
  • Noble Maxence
  • de Bortoli Valentin
  • Doucet Arnaud
  • Durmus Alain
  , 2023. Multi-marginal Optimal Transport (mOT), a generalization of OT, aims at minimizing the integral of a cost function with respect to a distribution with some prescribed marginals. In this paper, we consider an entropic version of mOT with a tree-structured quadratic cost, i.e., a function that can be written as a sum of pairwise cost functions between the nodes of a tree. To address this problem, we develop Tree-based Diffusion Schrödinger Bridge (TreeDSB), an extension of the Diffusion Schrödinger Bridge (DSB) algorithm. TreeDSB corresponds to a dynamic and continuous state-space counterpart of the multi-marginal Sinkhorn algorithm. A notable use case of our methodology is to compute Wasserstein barycenters which can be recast as the solution of a mOT problem on a star-shaped tree. We demonstrate that our methodology can be applied in high-dimensional settings such as image interpolation and Bayesian fusion.
• Error estimates for finite differences approximations of the total variation
  
  • Caillaud Corentin
  • Chambolle Antonin
  IMA Journal of Numerical Analysis, Oxford University Press (OUP), 2023, 43 (2), pp.692--736. We present a convergence rate analysis of the Rudin-Osher-Fatemi (ROF) denoising problem for two different discretizations of the total variation. The first discretization is the well-known isotropic total variation that suffers from a blurring effect in a special diagonal direction. We prove that in the setting corresponding to this direction, the discrete ROF energy converges to the continuous one in O(h^2/3). The second total variation is based on Raviart-Thomas fields and achieves a O(h) convergence rate for the same quantity under some standard hypotheses. (10.1093/imanum/drac001)
  DOI : 10.1093/imanum/drac001
• Design patterns of hierarchies for order structures
  
  • Allamigeon Xavier
  • Canu Quentin
  • Cohen Cyril
  • Sakaguchi Kazuhiko
  • Strub Pierre-Yves
  , 2023. Using order structures in a proof assistant naturally raises the problem of working with multiple instances of a same structure over a common type of elements. This goes against the main design pattern of hierarchies used for instance in Coq's MathComp or Lean's mathlib libraries, where types are canonically associated to at most one instance and instances share a common overloaded syntax. We present new design patterns to leverage these issues, and apply them to the formalization of order structures in the MathComp library. A common idea in these patterns is underloading, i.e., a disambiguation of operators on a common type. In addition, our design patterns include a way to deal with duality in order structures in a convenient way. We hence formalize a large hierarchy which includes partial orders, semilattices, lattices as well as many variants. We finally pay a special attention to order substructures. We introduce a new kind of structure called prelattice. They are abstractions of semilattices, and allow us to deal with finite lattices and their sublattices within a common signature. As an application, we report on significant simplifications of the formalization of the face lattices of polyhedra in the Coq-Polyhedra library.