Publications

2018

• Log-barrier interior point methods are not strongly polynomial
  
  • Allamigeon Xavier
  • Benchimol Pascal
  • Gaubert Stéphane
  • Joswig Michael
  SIAM Journal on Applied Algebra and Geometry, Society for Industrial and Applied Mathematics, 2018, 2 (1), pp.140-178. We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with $3r+1$ inequalities in dimension $2r$ for which the number of iterations performed is in $\Omega(2^r)$. The total curvature of the central path of these linear programs is also exponential in $r$, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko. Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature, in a general setting. (10.1137/17M1142132)
  DOI : 10.1137/17M1142132
• Hilbert and Thompson geometries isometric to infinite-dimensional Banach spaces
  
  • Walsh Cormac
  Annales de l'Institut Fourier, Association des Annales de l'Institut Fourier, 2018, 68 (5), pp.1831-1877. We study the horofunction boundaries of Hilbert and Thompson geome-tries, and of Banach spaces, in arbitrary dimension. By comparing the boundaries of these spaces, we show that the only Hilbert and Thompson geometries that are isometric to Banach spaces are the ones defined on the cone of positive continuous functions on a compact space.
• Study of new rare event simulation schemes and their application to extreme scenario generation
  
  • Agarwal Ankush
  • de Marco Stefano
  • Gobet Emmanuel
  • Liu Gang
  Mathematics and Computers in Simulation, Elsevier, 2018, 143, pp.89-98. This is a companion paper based on our previous work [ADGL15] on rare event simulation methods. In this paper, we provide an alternative proof for the ergodicity of shaking transformation in the Gaussian case and propose two variants of the existing methods with comparisons of numerical performance. In numerical tests, we also illustrate the idea of extreme scenario generation based on the convergence of marginal distributions of the underlying Markov chains and show the impact of the discretization of continuous time models on rare event probability estimation. (10.1016/j.matcom.2017.05.004)
  DOI : 10.1016/j.matcom.2017.05.004
• The Quasispecies for the Wright–Fisher Model
  
  • Cerf Raphaël
  • Dalmau Joseba
  Evolutionary Biology, Springer, 2018, 45 (3), pp.318-323. We consider the classical Wright-Fisher model of population genetics. We prove the existence of an error threshold for the mutation probability per nucleotide, below which a quasispecies is formed. We show a new phenomenon, specific to a finite population model, namely the existence of a population threshold: to ensure the stability of the quasispecies, the population size has to be at least of the same order as the genome length. We derive an explicit formula describing the quasispecies. (10.1007/s11692-018-9452-0)
  DOI : 10.1007/s11692-018-9452-0
• Sensing Von Economo Neurons in the Insula with Multi-shell Diffusion MRI
  
  • Wassermann Demian
  • Nguyen Dang Van
  • Gallardo Guillermo
  • Li Jing-Rebecca
  • Cai Weidong
  • Menon Vinod
  , 2018.
• From Hammersley's lines to Hammersley's trees
  
  • Basdevant Anne-Laure
  • Gerin Lucas
  • Gouere Jean-Baptiste
  • Singh Arvind
  Probability Theory and Related Fields, Springer Verlag, 2018, 171 (1-2), pp.1-51. We construct a stationary random tree, embedded in the upper half plane, with prescribed offspring distribution and whose vertices are the atoms of a unit Poisson point process. This process which we call Hammersley's tree process extends the usual Hammersley's line process. Just as Hammersley's process is related to the problem of the longest increasing subsequence, this model also has a combinatorial interpretation: it counts the number of heaps (i.e. increasing trees) required to store a random permutation. This problem was initially considered by Byers et. al (2011) and Istrate and Bonchis (2015) in the case of regular trees. We show, in particular, that the number of heaps grows logarithmically with the size of the permutation. (10.1007/s00440-017-0772-2)
  DOI : 10.1007/s00440-017-0772-2
• Vertices with fixed outdegrees in large Galton-Watson trees
  
  • Thévenin Paul
  Electronic Journal of Probability, Institute of Mathematical Statistics (IMS), 2018, 25 (none). We are interested in nodes with fixed outdegrees in large conditioned Galton--Watson trees. We first study the scaling limits of processes coding the evolution of the number of such nodes in different explorations of the tree (lexicographical order and contour order) starting from the root. We give necessary and sufficient conditions for the limiting processes to be centered, thus measuring the linearity defect of the evolution of the number of nodes with fixed outdegrees. This extends results by Labarbe & Marckert in the case of the contour-ordered counting process of leaves in uniform plane trees. Then, we extend results obtained by Janson concerning the asymptotic normality of the number of nodes with fixed outdegrees. (10.1214/20-EJP465)
  DOI : 10.1214/20-EJP465
• Markov chains
  
  • Douc Randal
  • Moulines Eric
  • Priouret Pierre
  • Soulier Philippe
  , 2018, pp.757. This book covers the classical theory of Markov chains on general state-spaces as well as many recent developments. The theoretical results are illustrated by simple examples, many of which are taken from Markov Chain Monte Carlo methods. The book is self-contained, while all the results are carefully and concisely proven. Bibliographical notes are added at the end of each chapter to provide an overview of the literature (10.1007/978-3-319-97704-1)
  DOI : 10.1007/978-3-319-97704-1
• Commentaires sur le projet de document consensus de l’OCDE sur les considérations environnementales relatives à l’évaluation des risques associé. Paris, le 23 mai 2018
  
  • Comité Scientifique Du Haut Conseil Des Biotechnologies .
  • Angevin Frédérique
  • Bagnis Claude
  • Bar-Hen Avner
  • Barny Marie Anne M. A.
  • Bellivier Florence
  • Berny Philippe
  • Boireau Pascal
  • Brévault Thierry
  • Chauvel Bruno B.
  • Coléno François
  • Couvet Denis
  • Dassa Elie
  • Eychenne Nathalie
  • Franche Claudine
  • Guerche Philippe
  • Guillemain Joël
  • Hernandez Raquet Guillermina
  • Jestin André
  • Klonjkowski Bernard
  • Lavielle Marc
  • Le Corre Valérie V.
  • Lemaire Olivier O.
  • Lereclus Didier
  • Maximilien Rémi
  • Meurs Eliane
  • Moreau de Bellaing Cédric
  • Naffakh Nadia
  • Négre Didier
  • Noyer Jean-Louis
  • Ochatt Sergio
  • Pages Jean-Christophe
  • Parzy Daniel
  • Regnault-Roger Catherine
  • Renard Michel
  • Saindrenan Patrick
  • Simonet Pascal
  • Troadec Marie-Bérengère
  • Vaissière Bernard
  • de Verneuil Hubert
  • Vilotte Jean-Luc
  , 2018, pp.25 p.. Le Haut Conseil des biotechnologies (HCB) a été sollicité le 4 avril 2018 par la direction générale de l’alimentation du ministère de l’Agriculture et de l’Alimentation et par la direction générale de la prévention des risques du ministère de la Transition écologique et solidaire pour examiner et commenter le projet de document consensus de l’OCDE (version du 3 avril 2018) sur les considérations environnementales relatives à l’évaluation des risques associés à la dissémination de plantes génétiquement modifiées en vue de la réunion du groupe de travail de l’OCDE sur l’harmonisation de la surveillance réglementaire en biotechnologie les 21 et 22 juin 2018. Le Comité scientifique (CS)1 du HCB a examiné ce document en séance du 26 avril 2018 sous la présidence de Jean-Christophe Pagès. Les commentaires du CS du HCB à destination de l’OCDE, en version française et anglaise2, ont été validés par voie électronique et transmis aux autorités compétentes françaises le 23 mai 2018, et publiés après envoi à l’OCDE le 30 mai 2018.
• Impact of subsampling and tree depth on random forests
  
  • Duroux Roxane
  • Scornet Erwan
  ESAIM: Probability and Statistics, EDP Sciences, 2018, 22, pp.96-128. Random forests are ensemble learning methods introduced by Breiman [Mach. Learn. 45 (2001) 5–32] that operate by averaging several decision trees built on a randomly selected subspace of the data set. Despite their widespread use in practice, the respective roles of the different mechanisms at work in Breiman’s forests are not yet fully understood, neither is the tuning of the corresponding parameters. In this paper, we study the influence of two parameters, namely the subsampling rate and the tree depth, on Breiman’s forests performance. More precisely, we prove that quantile forests (a specific type of random forests) based on subsampling and quantile forests whose tree construction is terminated early have similar performances, as long as their respective parameters (subsampling rate and tree depth) are well chosen. Moreover, experiments show that a proper tuning of these parameters leads in most cases to an improvement of Breiman’s original forests in terms of mean squared error. (10.1051/ps/2018008)
  DOI : 10.1051/ps/2018008
• Generic uniqueness of the bias vector of finite stochastic games with perfect information
  
  • Akian Marianne
  • Gaubert Stéphane
  • Hochart Antoine
  Journal of Mathematical Analysis and Applications, Elsevier, 2018, 457, pp.1038-1064. Mean-payoff zero-sum stochastic games can be studied by means of a nonlinear spectral problem. When the state space is finite, the latter consists in finding an eigenpair (u,λ) solution of T(u)=λe+u, where T:Rn→Rn is the Shapley (or dynamic programming) operator, λ is a scalar, e is the unit vector, and u∈Rn. The scalar λ yields the mean payoff per time unit, and the vector u, called the bias, allows one to determine optimal stationary strategies. The existence of the eigenpair (u,λ) is generally related to ergodicity conditions. A basic issue is to understand for which classes of games the bias vector is unique (up to an additive constant). In this paper, we consider perfect-information zero-sum stochastic games with finite state and action spaces, thinking of the transition payments as variable parameters, transition probabilities being fixed. We show that the bias vector, thought of as a function of the transition payments, is generically unique (up to an additive constant). The proof uses techniques of max-plus (or tropical) algebra and nonlinear Perron-Frobenius theory. As an application of our results, we obtain a perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration. (10.1016/j.jmaa.2017.07.017)
  DOI : 10.1016/j.jmaa.2017.07.017
• Modal basis approaches in shape and topology optimization of frequency response problems
  
  • Allaire Grégoire
  • Michailidis Georgios
  International Journal for Numerical Methods in Engineering, Wiley, 2018, 113 (8), pp.1258-1299. The optimal design of mechanical structures subject to periodic excitations within a large frequency interval is quite challenging. In order to avoid bad performances for non-discretized frequencies, it is necessary to finely discretize the frequency interval, leading to a very large number of state equations. Then, if a standard adjoint-based approach is used for optimization, the computational cost (both in terms of CPU and memory storage) may be prohibitive for large problems, especially in three space dimensions. The goal of the present work is to introduce two new non-adjoint approaches for dealing with frequency response problems in shape and topology optimization. In both cases, we rely on a classical modal basis approach to compute the states, solutions of the direct problems. In the first method, we do not use any adjoint but rather directly compute the shape derivatives of the eigenmodes in the modal basis. In the second method, we compute the adjoints of the standard approach by using again the modal basis. The numerical cost of these two new strategies are much smaller than the usual ones if the number of modes in the modal basis is much smaller than the number of discretized excitation frequencies. We present numerical examples for the minimization of the dynamic compliance in two and three space dimensions. (10.1002/nme.5504)
  DOI : 10.1002/nme.5504
• Dynamic programming approach to principal-agent problems
  
  • Cvitanić Jakša
  • Possamaï Dylan
  • Touzi Nizar
  Finance and Stochastics, Springer Verlag (Germany), 2018, 22, pp.1-37. We consider a general formulation of the Principal-Agent problem with a lump-sum payment on a finite horizon, providing a systematic method for solving such problems. Our approach is the following: we first find the contract that is optimal among those for which the agent's value process allows a dynamic programming representation, for which the agent's optimal effort is straightforward to find. We then show that the optimization over the restricted family of contracts represents no loss of generality. As a consequence, we have reduced this non-zero sum stochastic differential game to a stochastic control problem which may be addressed by the standard tools of control theory. Our proofs rely on the backward stochastic differential equations approach to non-Markovian stochastic control, and more specifically, on the recent extensions to the second order case. (10.1007/s00780-017-0344-4)
  DOI : 10.1007/s00780-017-0344-4
• Peristaltic Waves as Optimal Gaits in Metameric Bio-Inspired Robots
  
  • Agostinelli Daniele
  • Alouges François
  • Desimone Antonio
  Frontiers in Robotics and AI, Frontiers Media S.A., 2018, 5, pp.99. Peristalsis, i.e., a motion pattern arising from the propagation of muscle contraction and expansion waves along the body, is a common locomotion strategy for limbless animals. Mimicking peristalsis in bio-inspired robots has attracted considerable attention in the literature. It has recently been observed that maximal velocity in a metameric earthworm-like robot is achieved by actuating the segments using a “phase coordination” principle. This paper shows that, in fact, peristalsis (which requires not only phase coordination, but also that all segments oscillate at same frequency and amplitude) emerges from optimization principles. More precisely, basing our analysis on the assumption of small deformations, we show that peristaltic waves provide the optimal actuation solution in the ideal case of a periodic infinite system, and that this is approximately true, modulo edge effects, for the real, finite length system. Therefore, this paper confirms the effectiveness of mimicking peristalsis in bio-inspired robots, at least in the small-deformation regime. Further research will be required to test the effectiveness of this strategy if large deformations are allowed. (10.3389/frobt.2018.00099)
  DOI : 10.3389/frobt.2018.00099
• Variational methods for tomographic reconstruction with few views
  
  • Bergounioux Maïtine
  • Abraham Isabelle
  • Abraham Romain
  • Carlier Guillaume
  • Le Pennec Erwan
  • Trélat Emmanuel
  Milan Journal of Mathematics, Springer Verlag, 2018, 86 (2), pp.157--200. We deal with a severe ill posed problem, namely the reconstruction process of an image during tomography acquisition with (very) few views. We present different methods that we have been investigated during the past decade. They are based on variational analysis. This is a survey paper and we refer to the quoted papers for more details. Mathematics Subject Classification (2010). 49K40, 45Q05,65M32.
• Uncovering Causality from Multivariate Hawkes Integrated Cumulants
  
  • Achab Massil
  • Bacry Emmanuel
  • Gaïffas Stéphane
  • Mastromatteo Iacopo
  • Muzy Jean-François
  Journal of Machine Learning Research, Microtome Publishing, 2018, 18, pp.192. We design a new nonparametric method that allows one to estimate the matrix of integrated kernels of a multivariate Hawkes process. This matrix not only encodes the mutual influences of each node of the process, but also disentangles the causality relationships between them. Our approach is the first that leads to an estimation of this matrix without any parametric modeling and estimation of the kernels themselves. As a consequence, it can give an estimation of causality relationships between nodes (or users), based on their activity timestamps (on a social network for instance), without knowing or estimating the shape of the activities lifetime. For that purpose, we introduce a moment matching method that fits the second-order and the third-order integrated cumulants of the process. A theoretical analysis allows us to prove that this new estimation technique is consistent. Moreover, we show, on numerical experiments, that our approach is indeed very robust with respect to the shape of the kernels and gives appealing results on the MemeTracker database and on financial order book data.
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
  
  • Allamigeon Xavier
  • Gaubert Stephane
  • Skomra Mateusz
  Journal of Symbolic Computation, Elsevier, 2018, 85, pp.25-54. A general issue in computational optimization is to develop combinatorial algorithms for semidefinite programming. We address this issue when the base field is nonarchimedean. We provide a solution for a class of semidefinite feasibility problems given by generic matrices. Our approach is based on tropical geometry. It relies on tropical spectrahedra, which are defined as the images by the valuation of nonarchimedean spectrahedra. We establish a correspondence between generic tropical spectrahedra and zero-sum stochastic games with perfect information. The latter have been well studied in algorithmic game theory. This allows us to solve nonarchimedean semidefinite feasibility problems using algorithms for stochastic games. These algorithms are of a combinatorial nature and work for large instances. (10.1016/j.jsc.2017.07.002)
  DOI : 10.1016/j.jsc.2017.07.002
• Quadratic BSDEs with mean reflection
  
  • Hibon Hélène
  • Hu Ying
  • Lin Yiqing
  • Luo Peng
  • Wang Falei
  Mathematical Control and Related Fields, AIMS, 2018, 8 (3 & 4), pp.721-738. The present paper is devoted to the study of the well-posedness of BSDEs with mean reflection whenever the generator has quadratic growth in the $z$ argument. This work is the sequel of Briand et al. [BSDEs with mean reflection, arXiv:1605.06301] in which a notion of BSDEs with mean reflection is developed to tackle the super-hedging problem under running risk management constraints. By the contraction mapping argument, we first prove that the quadratic BSDE with mean reflection admits a unique deterministic flat local solution on a small time interval whenever the terminal value is bounded. Moreover, we build the global solution on the whole time interval by stitching local solutions when the generator is uniformly bounded with respect to the $y$ argument. (10.3934/mcrf.2018031)
  DOI : 10.3934/mcrf.2018031
• Principal-Agent Problem with Common Agency Without Communication
  
  • Mastrolia Thibaut
  • Ren Zhenjie
  SIAM Journal on Financial Mathematics, Society for Industrial and Applied Mathematics, 2018, 9 (2), pp.775-799. In this paper, we consider a problem of contract theory in which several Principals hire a common Agent and we study the model in the continuous time setting. We show that optimal contracts should satisfy some equilibrium conditions and we reduce the optimization problem of the Principals to a system of coupled Hamilton--Jacobi--Bellman (HJB) equations. We provide conditions ensuring that for risk-neutral Principals, the system of coupled HJB equations admits a solution. Further, we apply our study in a more specific linear-quadratic model where two interacting Principals hire one common Agent. In this continuous time model, we extend the result of [B. D. Bernheim and M. D. Whinston, Econometrica, 54 (1986), pp. 923--942] in which the authors compare the optimal effort of the Agent in a noncooperative Principals model and that in the aggregate model, by showing that these two optimizations coincide only in the first best case. We also study the sensibility of the optimal effort and the optimal remunerations with respect to appetence parameters and the correlation between the projects. (10.1137/17M1133609)
  DOI : 10.1137/17M1133609
• Relaxation Limit and Initial-Layers for a Class of Hyperbolic-Parabolic Systems
  
  • Giovangigli Vincent
  • Yang Zai-Bao
  • Yong Wen-An
  SIAM Journal on Mathematical Analysis, Society for Industrial and Applied Mathematics, 2018. We consider a class of hyperbolic-parabolic systems with small diffusion terms and stiff sources. Existence of solutions to the Cauchy problem with ill prepared initial data is established by using composite expansions including initial-layer correctors and a convergence-stability lemma. New multitime expansions are introduced and lead to second-order error estimates between the composite expansions and the solution. Reduced equilibrium systems of second-order accuracy are also investigated as well as initial-layers of Chapman-Enskog expansions. (10.1137/18M1170091)
  DOI : 10.1137/18M1170091
• Full Likelihood Inference from the Site Frequency Spectrum based on the Optimal Tree Resolution
  
  • Sainudiin Raazesh
  • Véber Amandine
  Theoretical Population Biology, Elsevier, 2018.
• Elasto-plastic shape optimization using the level set method
  
  • Maury Aymeric
  • Allaire Grégoire
  • Jouve François
  SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2018, 56 (1), pp.556-581. This article focused on shape optimization of static perfect plasticity problems in the framework of the Von Mises criterion, thanks to the level set method. We circumvent the ill-posedness of the model, by using two regularized versions of the mechanical problem. The rst one is the classical Perzyna formulation which we regularize, the second one is a new regularized formulation derived for the Von Mises criterion. Shape gradients are calculated thanks to the adjoint method. To illustrate the validity of the method, 2D examples are performed.
• Solutions for models of chemically reacting mixtures
  
  • Giovangigli Vincent
  , 2018. The mathematical modeling of chemically reacting mixtures is investigated. The governing equations, that may be split between conservation equations, thermochemistry and transport fluxes, are presented as well as typical simplifications often encountered in the literature. The hyperbolic-parabolic structure of the resulting system of partial differential equations is analyzed using symmetrizing variables. The Cauchy problem is discussed for the full system derived from the kinetic theory of gases as well as relaxation towards chemical equilibrium fluids in the fast chemistry limit. The situations of traveling waves and reaction-diffusion systems is also addressed. (10.1007/978-3-319-10151-4_73-1)
  DOI : 10.1007/978-3-319-10151-4_73-1
• Avis en réponse à la saisine HCB - dossier 2014-123. Paris, le 27 juin 2018
  
  • Comité Scientifique Du Haut Conseil Des Biotechnologies .
  • Angevin Frédérique
  • Bagnis Claude
  • Bar-Hen Avner
  • Barny Marie-Anne
  • Boireau Pascal
  • Brévault Thierry
  • Chauvel Bruno B.
  • Collonnier Cécile
  • Couvet Denis
  • Dassa Elie
  • de Verneuil Hubert
  • Demeneix Barbara
  • Franche Claudine
  • Guerche Philippe
  • Guillemain Joël
  • Hernandez Raquet Guillermina
  • Khalife Jamal
  • Klonjkowski Bernard
  • Lavielle Marc
  • Le Corre Valérie
  • Lefèvre François
  • Lemaire Olivier
  • Lereclus Didier D.
  • Maximilien Rémy
  • Meurs Eliane
  • Naffakh Nadia
  • Négre Didier
  • Noyer Jean-Louis
  • Ochatt Sergio
  • Pages Jean-Christophe
  • Raynaud Xavier
  • Regnault-Roger Catherine
  • Renard Michel M.
  • Renault Tristan
  • Saindrenan Patrick
  • Simonet Pascal
  • Troadec Marie-Bérengère
  • Vaissière Bernard
  • Vilotte Jean-Luc
  , 2018.
• One-sided convergence in the Boltzmann-Grad limit
  
  • Bodineau Thierry
  • Gallagher Isabelle
  • Saint-Raymond Laure
  • Simonella Sergio
  Annales de la Faculté des Sciences de Toulouse. Mathématiques., Université Paul Sabatier _ Cellule Mathdoc, 2018, 27 (5). We review various contributions on the fundamental work of Lanford deriving the Boltzmann equation from hard-sphere dynamics in the low density limit. We focus especially on the assumptions made on the initial data and on how they encode irreversibility. The impossibility to reverse time in the Boltzmann equation (expressed for instance by Boltzmann's H-theorem) is related to the lack of convergence of higher order marginals on some singular sets. Explicit counterexamples single out the microscopic sets where the initial data should converge in order to produce the Boltzmann dynamics. (10.5802/afst.1589)
  DOI : 10.5802/afst.1589