Publications

2017

• On the asymptotic behaviour of the kernel of an adjoint convection-diffusion operator in a long cylinder
  
  • Allaire Grégoire
  • Piatnitski Andrey
  Revista Matemática Iberoamericana, European Mathematical Society, 2017, 33 (4), pp.1123-1148. This paper studies the asymptotic behaviour of the principal eigen-function of the adjoint Neumann problem for a convection diffusion operator defined in a long cylinder. The operator coefficients are 1-periodic in the longitudinal variable. Depending on the sign of the so-called longitudinal drift (a weighted average of the coefficients), we prove that this principal eigenfunction is equal to the product of a specified periodic function and of an exponential, up to the addition of fast decaying boundary layer terms. (10.4171/RMI/965)
  DOI : 10.4171/RMI/965
• Price incentives in mobile data networks: bilevel programming, competitive equilibria and discrete convexity
  
  • Eytard Jean Bernard
  • Akian Marianne
  • Bouhtou Mustapha
  • Gaubert Stephane
  • Koshevoy Gleb A.
  , 2017.
• Multi-task Bolasso based aircraft dynamics identification
  
  • Rommel Cédric
  • Bonnans Joseph Frédéric
  • Gregorutti Baptiste
  • Martinon Pierre
  , 2017.
• Some contributions to the clustering of financial time series and applications to credit default swaps
  
  • Marti Gautier
  , 2017. In this thesis we first review the scattered literature about clustering financial time series. We then try to give as much colors as possible on the credit default swap market, a relatively unknown market from the general public but for its role in the contagion of bank failures during the global financial crisis of 2007-2008, while introducing the datasets that have been used in the empirical studies. Unlike the existing body of literature which mostly offers descriptive studies, we aim at building models and large information systems based on clusters which are seen as basic building blocks: These foundations must be stable. That is why the work undertaken and described in the following intends to ground further the clustering methodologies. For that purpose, we discuss their consistency and propose alternative measures of similarity that can be plugged in the clustering methodologies. We study empirically their impact on the clusters. Results of the empirical studies can be explored at www.datagrapple.com.
• Dispersal heterogeneity in the spatial Λ-Fleming-Viot process
  
  • Forien Raphaël
  , 2017. We study the evolution of gene frequencies in a spatially distributed population when the dispersal of individuals is not uniform in space. We adapt the spatial Λ-Fleming-Viot process to this setting and consider that individuals spread their offspring farther from themselves at each generation in one halfspace than in the other. We study the large scale behaviour of this process and show that the motion of ancestral lineages is asymptotically close to a family of skew Brownian motions which coalesce upon meeting in one dimension, but never meet in higher dimension. This leads to a generalization of a result due to Nagylaki on the scaling limits of the gene frequencies: the non-uniform dispersal causes a discontinuity in the slope of the gene frequencies but the gene frequencies themselves are continuous across the interface.
• Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems
  
  • Wai Hoi-To
  • Lafond Jean
  • Scaglione Anna
  • Moulines Éric
  IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, 2017, 62 (11), pp.5522 - 5537. Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high-dimensional constrained problems, as the projection step becomes computationally prohibitive. To address this problem, this paper adopts a projection-free optimization approach, a.k.a. the Frank-Wolfe (FW) or conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule and letting t be the iteration number, we show that the DeFW algorithm's convergence rate is O(1/t) for convex objectives; is O(1/t2) for strongly convex objectives with the optimal solution in the interior of the constraint set; and is O(1/√t) toward a stationary point for smooth but nonconvex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. We demonstrate the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion and communication efficient sparse learning. Numerical results on synthetic and real data are presented to support our findings. (10.1109/TAC.2017.2685559)
  DOI : 10.1109/TAC.2017.2685559
• Optimal side-channel attacks for multivariate leakages and multiple models
  
  • Bruneau Nicolas
  • Guilley Sylvain
  • Heuser Annelie
  • Damien Marion
  • Rioul Olivier
  Journal of Cryptographic Engineering, Springer, 2017, 7 (4), pp.331–341. Side-channel attacks allow to extract secret keys from embedded systems like smartcards or smartphones. In practice, the side-channel signal is measured as a trace consisting of several samples. Also, several sensitive bits are manipulated in parallel, each leaking differently. Therefore, the informed attacker needs to devise side-channel distinguishers that can handle both multivariate leakages and multiple models. In the state of the art, these two issues have two independent solutions: on the one hand, dimensionality reduction can cope with multivariate leakage; on the other hand, online stochastic approach can cope with multiple models. In this paper, we combine both solutions to derive closed-form expressions of the resulting optimal distinguisher in terms of matrix operations, in all situations where the model can be either profiled offline or regressed online. Optimality here means that the success rate is maximized for a given number of traces. We recover known results for uni- and bivariate models (including correlation power analysis) and investigate novel distinguishers for multiple models with more than two parameters. In addition, following ideas from the AsiaCrypt’2013 paper “Behind the Scene of Side-Channel Attacks,” we provide fast computation algorithms in which the traces are accumulated prior to computing the distinguisher values. (10.1007/s13389-017-0170-9)
  DOI : 10.1007/s13389-017-0170-9
• Accelerated Alternating Descent Methods for Dykstra-like problems
  
  • Chambolle Antonin
  • Tan Pauline
  • Vaiter Samuel
  Journal of Mathematical Imaging and Vision, Springer Verlag, 2017, 59 (3), pp.481-497. This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how ‘fast’ methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed. (10.1007/s10851-017-0724-6)
  DOI : 10.1007/s10851-017-0724-6
• Numerical simulation of suspensions: lubrication correction, including fluid correction
  
  • Lefebvre-Lepot Aline
  , 2018. When simulating systems of particles embedded in a Stokes flow, it is necessary to question the treatment of close interacting particles. Indeed, when two solids come close one to another, it becomes difficult to approximate the velocity and pressure fields which become singular. However, taking the corresponding singu-larity is essential, both from a numerical and physical point of view. Moreover, experimentalists now need more and more precise results, taking into account the effect of these interactions on the whole flow. The method we propose is based on a decomposition of the fluid/particle problem into two subproblems: a singular problem (when the distance between the particles goes to zero) and a regular problem. The singular field is supposed to be known and the resolution of the problem comes back to solving the regular problem. A first approach have been proposed in [6], where the singular field is tabulated. Here, we propose a new method, based on an asymptotic expansion of the singular field. This method allows to catch the effect of the lubrication on the whole velocity and pressure flows and can deal with any forms of particles. We focus on a toy problem in two dimensions to present the method. Numerical results are given, using a finite element discretization.
• Strong approximation of stochastic processes at random times and application to their exact simulation
  
  • Gobet Emmanuel
  • Mrad Mohamed
  Stochastics: An International Journal of Probability and Stochastic Processes, Taylor & Francis: STM, Behavioural Science and Public Health Titles, 2017, 89 (6-7), pp.883-895. We study the convergence rates of strong approximations of stochastic processes (possibly non semi-martingales) at random times (possibly non stopping times). Examples include Brownian local times at random points, Fractional Brownian motions or diffusion processes at Brownian time. These strong approximation results allow to design an exact simulation scheme. (10.1080/17442508.2016.1267179)
  DOI : 10.1080/17442508.2016.1267179
• Demand Response in the Smart Grid: the Impact of Consumers Temporal Preferences
  
  • Jacquot Paulin
  • Beaude Olivier
  • Oudjane Nadia
  • Gaubert Stephane
  , 2017. In Demand Response programs, price incentives might not be sufficient to modify residential consumers load profile. Here, we consider that each consumer has a preferred profile and a discomfort cost when deviating from it. Consumers can value this discomfort at a varying level that we take as a parameter. This work analyses Demand Response as a game theoretic environment. We study the equilibria of the game between consumers with preferences within two different dynamic pricing mechanisms, respectively the daily proportional mechanism introduced by Mohsenian-Rad et al, and an hourly proportional mechanism. We give new results about equilibria as functions of the preference level in the case of quadratic system costs and prove that, whatever the preference level, system costs are smaller with the hourly mechanism. We simulate the Demand Response environment using real consumption data from PecanStreet database. While the Price of Anarchy remains always close to one up to 0.1% with the hourly mechanism, it can be more than 10% bigger with the daily mechanism. (10.1109/SmartGridComm.2017.8340690)
  DOI : 10.1109/SmartGridComm.2017.8340690
• A DDFV method for a Cahn-Hilliard/Stokes phase field model with dynamic boundary conditions
  
  • Boyer Franck
  • Nabet Flore
  ESAIM: Mathematical Modelling and Numerical Analysis, Société de Mathématiques Appliquées et Industrielles (SMAI) / EDP, 2017, 51 (5), pp.1691-1731. In this paper we propose a "Discrete Duality Finite Volume" method (DDFV for short) for the diffuse interface modelling of incompressible flows. This numerical method is, conservative, robust and is able to handle general geometries and meshes. The model we study couples the Cahn-Hilliard equation and the unsteady Stokes equation and is endowed with particular nonlinear boundary conditions called dynamic boundary conditions. To implement the scheme for this model we have to define new discrete consistent DDFV operators that allows an energy stable coupling between both discrete equations. We are thus able to obtain the existence of a family of solutions satisfying a suitable energy inequality, even in the case where a first order time-splitting method between the two subsystems is used. We illustrate various properties of such a model with some numerical results. (10.1051/m2an/2016073)
  DOI : 10.1051/m2an/2016073
• Optimization of interactive binaural processing
  
  • Salmon François
  • Aussal Matthieu
  • Hendrickx Etienne
  • Messonnier Jean-Christophe
  • Millot Laurent
  , 2017. Several monitoring devices may be involved during a post-production. Given its lower cost and practical aspects, head-tracked binaural processing could be helpful for professionals to monitor spatialised audio contents. However, this technology provides significant spectral coloration in some sound incidences and suffers from its current comparison to a stereophonic signal reproduced through headphones. Therefore, different processing methods are proposed to optimize the binaural rendering and to find a new balance between externalization and timbral coloration. For this purpose, the alteration of the HRTF spectral cues in the frontal area only has been studied. In order to evaluate the accuracy of such treatments, listening tests were conducted. One HRTF processing method offered as much externalization as the original HRTFs while having a closer timbre quality to the original stereo signal.
• Transportation cost-information and concentration inequalities for bifurcating Markov chains
  
  • Bitseki Penda Siméon Valère
  • Escobar-Bach Mikael
  • Guillin Arnaud
  Bernoulli, Bernoulli Society for Mathematical Statistics and Probability, 2017, 23 (4B), pp.3213-3242. We investigate the transportation cost-information inequalities for bifurcating Markov chains which are a class of processes indexed by binary tree. These processes provide models for cell growth when each individual in one generation gives birth to two offsprings in the next one. Transportation cost inequalities provide useful concentra-tion inequalities. We also study deviation inequalities for the empiri-cal means under relaxed assumptions on the Wasserstein contraction of the Markov kernels. Applications to bifurcating non linear autore-gressive processes are considered: deviation inequalities for pointwise estimates of the non linear leading functions. (10.3150/16-BEJ843)
  DOI : 10.3150/16-BEJ843
• A Fast Method to Compute Disjunctive Quadratic Invariants of Numerical Programs
  
  • Allamigeon Xavier
  • Gaubert Stéphane
  • Goubault Eric
  • Putot Sylvie
  • Stott Nikolas
  ACM Transactions on Embedded Computing Systems (TECS), ACM, 2017, 16 (5s), pp.1-19. We introduce a new method to compute non-convex invariants of numerical programs, which includes the class of switched affine systems with affine guards. We obtain disjunctive and non-convex invariants by associating different partial execution traces with different ellipsoids. A key ingredient is the solution of non-monotone fixed points problems over the space of ellipsoids with a reduction to small size linear matrix inequalities. This allows us to analyze instances that are inaccessible in terms of expressivity or scale by earlier methods based on semi-definite programming. (10.1145/3126502)
  DOI : 10.1145/3126502
• Anytime Benchmarking of Budget-Dependent Algorithms with the COCO Platform
  
  • Tušar Tea
  • Hansen Nikolaus
  • Brockhoff Dimo
  , 2017, pp.1-4. Anytime performance assessment of black-box optimization algorithms assumes that the performance of an algorithm at a specific time does not depend on the total budget of function evaluations at its disposal. It therefore should not be used for benchmarking budget-depending algorithms, i.e., algorithms whose performance depends on the total budget of function evaluations, such as some surrogate-assisted or hybrid algorithms. This paper presents an anytime bench-marking approach suited for budget-depending algorithms. The approach is illustrated on a budget-dependent variant of the Differential Evolution algorithm.
• Learning from Sequences with Point Processes
  
  • Achab Massil
  , 2017. The guiding principle of this thesis is to show how the arsenal of recent optimization methods can help solving challenging new estimation problems on events models.While the classical framework of supervised learning treat the observations as a collection of independent couples of features and labels, events models focus on arrival timestamps to extract information from the source of data.These timestamped events are chronologically ordered and can't be regarded as independent.This mere statement motivates the use of a particular mathematical object called point process to learn some patterns from events.Two examples of point process are treated in this thesis.The first is the point process behind Cox proportional hazards model:its conditional intensity function allows to define the hazard ratio, a fundamental quantity in survival analysis literature.The Cox regression model relates the duration before an event called failure to some covariates.This model can be reformulated in the framework of point processes.The second is the Hawkes process which models how past events increase the probability of future events.Its multivariate version enables encoding a notion of causality between the different nodes.The thesis is divided into three parts.The first focuses on a new optimization algorithm we developed to estimate the parameter vector of the Cox regression in the large-scale setting.Our algorithm is based on stochastic variance reduced gradient descent (SVRG) and uses Monte Carlo Markov Chain to estimate one costly term in the descent direction.We proved the convergence rates and showed its numerical performance on both simulated and real-world datasets.The second part shows how the Hawkes causality can be retrieved in a nonparametric fashion from the integrated cumulants of the multivariate point process.We designed two methods to estimate the integrals of the Hawkes kernels without any assumption on the shape of the kernel functions. Our methods are faster and more robust towards the shape of the kernels compared to state-of-the-art methods. We proved the statistical consistency of the first method, and designed turned the second into a convex optimization problem.The last part provides new insights from order book data using the first nonparametric method developed in the second part.We used data from the EUREX exchange, designed new order book model (based on the previous works of Bacry et al.) and ran the estimation method on these point processes.The results are very insightful and consistent with an econometric analysis.Such work is a proof of concept that our estimation method can be used on complex data like high-frequency financial data.
• Méthodes numériques pour la simulation d'équations aux dérivées partielles stochastiques non-linéaires en condensation de Bose-Einstein
  
  • Poncet Romain
  , 2017. Cette thèse porte sur l'étude de méthodes numériques pour l'analyse de deux modèles stochastiques apparaissant dans le contexte de la condensation de Bose-Einstein. Ceux-ci constituent deux généralisations de l'équation de Gross-Pitaevskii. Cette équation aux dérivées partielles déterministe modélise la dynamique de la fonction d'onde d'un condensat de Bose-Einstein piégé par un potentiel extérieur confinant.Le premier modèle étudié permet de modéliser les fluctuations de l'intensité du potentiel confinant et prend la forme d'une équation aux dérivées partielles stochastiques. Celles-ci conduisent en pratique à un échauffement du condensat, et parfois mêmeà son effondrement. Nous proposons dans un premier chapitre la construction d'un schéma numérique pour la résolution de ce modèle. Il est fondé sur une discrétisation spectrale en espace, et une discrétisation temporelle de type Crank-Nicolson. Nous démontrons que le schéma proposé converge fortement en probabilité à l'ordre au moins 1 en temps, et nous présentons des simulations numériques illustrant ce résultat. Le deuxième chapitre est consacré à l'étude théorique et numérique de la dynamique d'une solution stationnaire (pour l'équation déterministe) de type vortex. Nous étudions l'influence des perturbations aléatoires du potentiel sur la solution, et montrons que la solution perturbée garde les symétries de la solution stationnaire pour des temps au moins de l'ordre du carré de l'inverse de l'intensité des fluctuations. Ces résultats sont illustrés par des simulations numériques exploitant une méthode de Monte-Carlo adaptée à la simulation d'événements rares.Le deuxième modèle permet de modéliser les effets de la température sur la dynamique d'un condensat. Lorsque celle-ci n'est pas nulle, la condensation n'est pas complète et le condensat interagit avec les particules non condensées. Ces interactions sont d'un grand intérêt pour comprendre la dynamique de transition de phase et analyser les phénomènes de brisure de symétrie associés, comme la formation spontanée de vortex. Nous nous sommes intéressés dans les chapitres 3 et 4 à des questions relatives à la simulation de la distribution des solutions de cette équation en temps long. Le troisième chapitre est consacré à la construction d'une méthode d’échantillonnage sans biais pour des mesures connues à une constante multiplicative près. C'est une méthode de Monte Carlo par chaînes de Markov qui a la particularité de permettre un échantillonnage non-réversible basé sur une équation de type Langevin sur-amortie. Elle constitue une extension de Metropolis-Adjusted Langevin Algorithm (MALA). Le quatrième chapitre est quant à lui consacré à l'étude numérique de dynamiques métastables liées à la nucléation de vortex dans des condensats en rotation. Un intégrateur numérique pour la dynamique étudiée est proposé, ainsi qu'une méthode de Monte-Carlo adaptée à la simulation d'événements rares correspondant aux changements de configurations métastables. Cette dernière est basée sur l'algorithme Adaptive Multilevel Splitting (AMS).
• Efficient tracking of a growing number of experts
  
  • Mourtada Jaouad
  • Maillard Odalric-Ambrym
  , 2017, 76, pp.1 - 23. We consider a variation on the problem of prediction with expert advice, where new forecasters that were unknown until then may appear at each round. As often in prediction with expert advice, designing an algorithm that achieves near-optimal regret guarantees is straightforward, using ag-gregation of experts. However, when the comparison class is sufficiently rich, for instance when the best expert and the set of experts itself changes over time, such strategies naively require to maintain a prohibitive number of weights (typically exponential with the time horizon). By contrast, designing strategies that both achieve a near-optimal regret and maintain a reasonable number of weights is highly non-trivial. We consider three increasingly challenging objectives (simple regret, shifting regret and sparse shifting regret) that extend existing notions defined for a fixed expert ensemble; in each case, we design strategies that achieve tight regret bounds, adaptive to the parameters of the comparison class, while being computationally inexpensive. Moreover, our algorithms are anytime , agnostic to the number of incoming experts and completely parameter-free. Such remarkable results are made possible thanks to two simple but highly effective recipes: first the " abstention trick " that comes from the specialist framework and enables to handle the least challenging notions of regret, but is limited when addressing more sophisticated objectives. Second, the " muting trick " that we introduce to give more flexibility. We show how to combine these two tricks in order to handle the most challenging class of comparison strategies.
• Gaussian approximations for chemostat models in finite and infinite dimensions
  
  • Cloez Bertrand
  • Fritsch Coralie
  Journal of Mathematical Biology, Springer, 2017, 75 (4), pp.805-843. In a chemostat, bacteria live in a growth container of constant volume in which liquid is injected continuously. Recently, Campillo and Fritsch introduced a mass-structured individual-based model to represent this dynamics and proved its convergence to a more classic partial differential equation. In this work, we are interested in the convergence of the fluctuation process. We consider this process in some Sobolev spaces and use central limit theorems on Hilbert space to prove its convergence in law to an infinite-dimensional Gaussian process. As a consequence, we obtain a two-dimensional Gaussian approximation of the Crump-Young model for which the long time behavior is relatively misunderstood. For this approximation, we derive the invariant distribution and the convergence to it. We also present numerical simulations illustrating our results. (10.1007/s00285-017-1097-6)
  DOI : 10.1007/s00285-017-1097-6
• Total Roto-Translational Variation
  
  • Chambolle Antonin
  • Pock Thomas
  , 2017. We consider curvature depending variational models for image regularization, such as Euler's elastica. These models are known to provide strong priors for the continuity of edges and hence have important applications in shape-and image processing. We consider a lifted convex representation of these models in the roto-translation space: In this space, curvature depending variational energies are represented by means of a convex functional defined on divergence free vector fields. The line energies are then easily extended to any scalar function. It yields a natural generalization of the total variation to the roto-translation space. As our main result, we show that the proposed convex representation is tight for characteristic functions of smooth shapes. We also discuss cases where this representation fails. For numerical solution, we propose a staggered grid discretization based on an averaged Raviart-Thomas finite elements approximation. This discretization is consistent, up to minor details, with the underlying continuous model. The resulting non-smooth convex optimization problem is solved using a first-order primal-dual algorithm. We illustrate the results of our numerical algorithm on various problems from shape-and image processing.
• A Formalization of Convex Polyhedra Based on the Simplex Method
  
  • Allamigeon Xavier
  • Katz Ricardo D.
  , 2017.
• Occlusion Detection in Dense Stereo Estimation with Convex Optimization
  
  • Chambolle Antonin
  • Monasse Pascal
  • Tan Pauline
  , 2017. In this paper, we propose a dense two-frame stereo algorithm which handles occlusion in a variational framework. Our method is based on a new regularization model which includes both a constraint on the occlusion width and a visibility constraint in nonoccluded areas. The minimization of the resulting energy functional is done by convex relaxation. A post-processing then detects and fills the occluded regions. We also propose a novel dissimilarity measure that combines color and gradient comparison with a variable respective weight, to benefit from the robustness of the comparison based on local variations while avoiding the fattening effect it may generate. (10.1109/ICIP.2017.8296741)
  DOI : 10.1109/ICIP.2017.8296741
• WEAK INTERACTIONS IN A BACKGROUND OF A UNIFORM MAGNETIC FIELD. A MATHEMATICAL MODEL FOR THE INVERSE β DECAY.I.
  
  • Guillot Jean-Claude
  , 2017. In this paper we consider a mathematical model for the inverse $\beta$ decay in a uniform magnetic field. With this model we associate a Hamiltonian with cutoffs in an appropriate Fock space. No infrared regularization is assumed. The Hamiltonian is self-adjoint and has a unique ground state. We study the essential spectrum and determine the spectrum. The coupling constant is supposed sufficiently small.
• Clustering and Model Selection via Penalized Likelihood for Different-sized Categorical Data Vectors
  
  • Derman Esther
  • Le Pennec Erwan
  , 2017. In this study, we consider unsupervised clustering of categorical vectors that can be of different size using mixture. We use likelihood maximization to estimate the parameters of the underlying mixture model and a penalization technique to select the number of mixture components. Regardless of the true distribution that generated the data, we show that an explicit penalty, known up to a multiplicative constant, leads to a non-asymptotic oracle inequality with the Kullback-Leibler divergence on the two sides of the inequality. This theoretical result is illustrated by a document clustering application. To this aim a novel robust expectation-maximization algorithm is proposed to estimate the mixture parameters that best represent the different topics. Slope heuristics are used to calibrate the penalty and to select a number of clusters.