LELONG Jerome

In this work, we propose an algorithm to simulate rare events for electronic circuit design. Our approach heavily relies on a smart use of importance sampling, which enables us to tackle probabilities of the magnitude 10 −10. Not only can we compute very rare default probability, but we can also compute the quantile associated to a given default probability and its expected shortfall. We show the impressive efficiency of method on real circuits.

No summary available.

No summary available.

No summary available.

In this work, we propose a new policy iteration algorithm for pricing Bermudan options when the payoff process cannot be written as a function of a lifted Markov process. Our approach is based on a modification of the well-known Longstaff Schwartz algorithm, in which we basically replace the standard least square regression by a Wiener chaos expansion. Not only does it allow us to deal with a non Markovian setting, but it also breaks the bottleneck induced by the least square regression as the coefficients of the chaos expansion are given by scalar products on the L^2 space and can therefore be approximated by independent Monte Carlo computations. This key feature enables us to provide an embarrassingly parallel algorithm.

The pricing of Bermudan options amounts to solving a dynamic programming principle , in which the main difficulty, especially in large dimension, comes from the computation of the conditional expectation involved in the continuation value. These conditional expectations are classically computed by regression techniques on a finite dimensional vector space. In this work, we study neural networks approximation of conditional expectations. We prove the convergence of the well-known Longstaff and Schwartz algorithm when the standard least-square regression is replaced by a neural network approximation.

In this work, we are interested in the behaviour of a single ferromagnetic mono–domain particle submitted to an external field with a stochastic perturbation. This model is a step toward the mathematical understanding of thermal effects on ferromagnets. In a first part, we discuss modelling issues and propose several ways to integrate a random noise in the deterministic model. Then, among all these approaches, we focus on the more natural one and study its long time behaviour. We prove that the system converges to the unique stable equilibrium of the deterministic model and make precise the L^p rate of the convergence. Finally, we illustrate the theoretical results by numerical simulations.

EASY-Backfilling is a popular scheduling heuristic for allocating jobs in large scale High Performance Computing platforms. While its aggressive reservation mechanism is fast and prevents job starvation, it does not try to optimize any scheduling objective per se. We consider in this work the problem of tuning EASY using queue reordering policies. More precisely, we propose to tune the reordering using a simulation-based methodology. For a given system, we choose the policy in order to minimize the average waiting time. This methodology departs from the First-Come, First-Serve rule and introduces a risk on the maximum values of the waiting time, which we control using a queue thresholding mechanism. This new approach is evaluated through a comprehensive experimental campaign on five production logs. In particular, we show that the behavior of the systems under study is stable enough to learn a heuristic that generalizes in a train/test fashion. Indeed, the average waiting time can be reduced consistently (between 11% to 42% for the logs used) compared to EASY, with almost no increase in maximum waiting times. This work departs from previous learning-based approaches and shows that scheduling heuristics for HPC can be learned directly in a policy space.

In this work, we propose an algorithm to price American options by directly solving thedual minimization problem introduced by Rogers. Our approach relies on approximating the set of uniformly square integrable martingales by a finite dimensional Wiener chaos expansion. Then, we use a sample average approximation technique to efficiently solve the optimization problem. Unlike all the regression based methods, our method can transparently deal with path dependent options without extra computations and a parallel implementation writes easily with very little communication and no centralized work. We test our approach on several multi--dimensional options with up to 40 assets and show the impressive scalability of the parallel implementation.

The STochastic OPTimization library (StOpt) aims at providing tools in C++ for solving some stochastic optimization problems encountered in finance or in the industry. A python binding is available for some C++ objects provided permitting to easily solve an optimization problem by regression. Different methods are available :

• dynamic programming methods based on Monte Carlo with regressions (global, local and sparse regressors), for underlying states following some uncontrolled Stochastic Differential Equations (python binding provided).
• Semi-Lagrangian methods for Hamilton Jacobi Bellman general equations for underlying states following some controlled Stochastic Differential Equations (C++ only)
• Stochastic Dual Dynamic Programming methods to deal with stochastic stocks management problems in high dimension. A SDDP module in python is provided. To use this module, the transitional optimization problem has to written in C++ and mapped to python (examples provided).
• Some methods are provided to solve by Monte Carlo some problems where the underlying stochastic state is controlled.
• Some pure Monte Carlo Methods are proposed to solve some non linear PDEs

For each method, a framework is provided to optimize the problem and then simulate it out of the sample using the optimal commands previously calculated. Parallelization methods based on OpenMP and MPI are provided in this framework permitting to solve high dimensional problems on clusters. The library should be flexible enough to be used at different levels depending on the user's willingness.

The EASY-FCFS heuristic is the basic building block of job scheduling policies in most parallel High Performance Computing platforms. Despite its simplicity, and the guarantee of no job starvation, it could still be improved on a per-system basis. Such tuning is difficult because of non-linearities in the scheduling process. The study conducted in this paper considers an online approach to the automatic tuning of the EASY heuristic for HPC platforms. More precisely, we consider the problem of selecting a reordering policy for the job queue under several feedback modes. We show via a comprehensive experimental validation on actual logs that periodic simulation of historical data can be used to recover existing in-hindsight results that allow to divide the average waiting time by almost 2. This results holds even when the simulator results are noisy. Moreover, we show that good performances can still be obtained without a simulator, under what is called bandit feedback - when we can only observe the performance of the algorithm that was picked on the live system. Indeed, a simple multi-armed bandit algorithm can reduce the average waiting time by 40 percent.

Providing the computing infrastructures needed to solve the complex problems of modern society is a strategic challenge. Organizations traditionally respond to this challenge by setting up large parallel and distributed computing infrastructures. Vendors of High Performance Computing systems are driven by competition to produce ever more computing and storage power, leading to specific and sophisticated "Petascale" platforms, and soon to "Exascale" machines. These systems are centrally managed with the help of job management software solutions and dedicated resources. A special problem that these software solutions address is the scheduling problem, where the resource manager must choose when, and on which resources, to execute which computational task. This thesis provides solutions to this problem. All platforms are different. Indeed, their infrastructure, the behavior of their users and the objectives of the host organization vary. We therefore argue that scheduling policies must adapt to the behavior of the systems. In this paper, we present several ways to achieve this adaptability. Through an experimental approach, we study several tradeoffs between the complexity of the approach, the potential gain, and the risks taken.

In this work, we propose a smart idea to couple importance sampling and Multilevel Monte Carlo (MLMC). We advocate a per level approach with as many importance sampling parameters as the number of levels, which enables us to compute the different levels independently. The search for parameters is carried out using sample average approximation, which basically consists in applying deterministic optimisation techniques to a Monte Carlo approximation rather than resorting to stochastic approximation. Our innovative estimator leads to a robust and efficient procedure reducing both the discretization error (the bias) and the variance for a given computational effort. In the setting of discretized diffusions, we prove that our estimator satisfies a strong law of large numbers and a central limit theorem with optimal limiting variance, in the sense that this is the variance achieved by the best importance sampling measure (among the class of changes we consider), which is however non tractable. Finally, we illustrate the efficiency of our method on several numerical challenges coming from quantitative finance and show that it outperforms the standard MLMC estimator.

No summary available.

We improve an adaptive integration algorithm proposed by two of the authors by introducing a new splitting strategy based on a geometrical criterion. This algorithm is tested especially on the pricing of multidimensional vanilla options in the Black–Scholes framework which emphasizes the numerical problems of integrating non-smooth functions. In high dimensions, this new algorithm is used as a control variate after a dimension reduction based on principal component analysis. Numerical tests are performed on the Genz package, on the pricing of basket, put on minimum and digital options in dimensions up to ten.

In this paper, we revisit the original ideas of Stein and propose an estimator of the intensity parameter of a homogeneous Poisson point process defined in R^d and observed in a bounded window. The procedure is based on a new general integration by parts formula for Poisson point processes. We show that our Stein estimator outperforms the maximum likelihood estimator in terms of mean squared error. In particular, we show that in many practical situations we have a gain larger than 30%.

Adaptive importance sampling techniques are widely known for the Gaussian setting of Brownian driven diffusions. In this work, we want to extend them to jump processes. Our approach relies on a change of the jump intensity combined with the standard exponential tilting for the Brownian motion. The free parameters of our framework are optimized using sample average approximation techniques. We illustrate the efficiency of our method on the valuation of financial derivatives in several jump models.

Financial institutions have massive computations to carry out overnight which are very demanding in terms of the consumed CPU. The challenge is to price many different products on a cluster-like architecture. We have used the Premia software to valuate the financial derivatives. In this work, we explain how Premia can be embedded into Nsp, a scientific software like Matlab, to provide a powerful tool to valuate a whole portfolio. Finally, we have integrated an MPI toolbox into Nsp to enable to use Premia to solve a bunch of pricing problems on a cluster. This unified framework can then be used to test different parallel architectures.

In this article, we are interested in the behaviour of a single ferromagnetic mono-domain particle submitted to an external field with a stochastic perturbation. This model is the first step toward the mathematical understanding of thermal effects on a ferromagnet. In a first part, we present the stochastic model and prove that the associated stochastic differential equation is well defined. The second part is dedicated to the study of the long time behaviour of the magnetic moment and in the third part we prove that the stochastic perturbation induces a non reversibility phenomenon. Last, we illustrate these results through numerical simulations of our stochastic model. The main results presented in this article are the rate of convergence of the magnetization toward the unique stable equilibrium of the deterministic model. The second result is a sharp estimate of the hysteresis phenomenon induced by the stochastic perturbation (remember that with no perturbation, the magnetic moment remains constant).

We present a parallel algorithm for solving backward stochastic differential equations. We improve the algorithm proposed in Gobet Labart (2010), based on an adaptive Monte Carlo method with Picard's iterations, and propose a parallel version of it. We test our algorithm on linear and non linear drivers up to dimension 8 on a cluster of 312 CPUs. We obtained very encouraging speedups greater than 0.7.

It is well-known from the work of Schönbucher (2005) that the marginal laws of a loss process can be matched by a unit increasing time inhomogeneous Markov process, whose deterministic jump intensity is called local intensity. The Stochastic Local Intensity (SLI) models such as the one proposed by Arnsdorf and Halperin (2008) allow to get a stochastic jump intensity while keeping the same marginal laws. These models involve a non-linear SDE with jumps. The first contribution of this paper is to prove the existence and uniqueness of such processes. This is made by means of an interacting particle system, whose convergence rate towards the non-linear SDE is analyzed. Second, this approach provides a powerful way to compute pathwise expectations with the SLI model: we show that the computational cost is roughly the same as a crude Monte-Carlo algorithm for standard SDEs.

We study the convergence rate of randomly truncated stochastic algorithms, which consist in the truncation of the standard Robbins-Monro procedure on an increasing sequence of compact sets. Such a truncation is often required in practice to ensure convergence when standard algorithms fail because the expected-value function grows too fast. In this work, we give a self contained proof of a central limit theorem for this algorithm under local assumptions on the expected-value function, which are fairly easy to check in practice.

The first part of this thesis is devoted to the study of the randomly truncated stochastic algorithms of Chen and Zhu. The first study of this algorithm concerns its almost sure convergence. In the second chapter, we continue the study of this algorithm by focusing on its convergence speed. We also consider a moving average version of this algorithm. Finally we conclude with some applications to finance. The second part of this thesis focuses on the valuation of Parisian options based on the work of Chesney, Jeanblanc and Yor. The valuation method is based on obtaining closed formulas for the Laplace transforms of prices with respect to maturity. We establish these formulas for single and double barrier Parisian options. We then study a numerical inversion method of these transforms and establish its accuracy.

This thesis deals with two independent subjects. The first part is devoted to the study of stochastic algorithms. In a first introductory chapter, I present the algorithm of in a parallel with Newton's algorithm for deterministic optimization. These few reminders then allow me to introduce the randomly truncated stochastic algorithms of which are at the heart of this thesis. The first study of this algorithm concerns its almost sure convergence which is sometimes established under rather changing assumptions. This first chapter is an opportunity to clarify the assumptions of the almost sure convergence and to present a simplified proof. In the second chapter, we continue the study of this algorithm by focusing this time on its speed of convergence. More precisely, we consider a moving average version of this algorithm and prove a central limit theorem for this variant. The third chapter is devoted to two applications of these algorithms to finance: the first example presents a method for calibrating the correlation for multidimensional market models while the second example continues the work of by improving its results. The second part of this thesis focuses on the valuation of Parisian options based on the work of Chesney, Jeanblanc-Picqué, and Yor. The valuation method is based on obtaining closed formulas for the Laplace transforms of prices with respect to maturity. We establish these formulas for single and double barrier Parisian options. We then study a numerical inversion method for these transforms. We establish a result on the accuracy of this very efficient numerical method. On this occasion, we also prove results related to the regularity of prices and the existence of a density with respect to the Lebesgues measure for Parisian times.

This thesis deals with two independent subjects. The first part is devoted to the study of stochastic algorithms. In a first introductory chapter, I present the algorithm of [55] in a parallel with Newton's algorithm for deterministic optimization. These few reminders then allow me to introduce the randomly truncated stochastic algorithms of [21] which are at the heart of this thesis. The first study of this algorithm concerns its almost sure convergence which is sometimes established under rather changing assumptions. This first chapter is an opportunity to clarify the assumptions of the almost sure convergence and to present a simplified proof. In the second chapter, we continue the study of this algorithm by focusing this time on its speed of convergence. More precisely, we consider a moving average version of this algorithm and prove a central limit theorem for this variant. The third chapter is devoted to two applications of these algorithms to finance: the first example presents a method for calibrating the correlation for multidimensional market models while the second example continues the work of [7] by improving its results. The second part of this thesis focuses on the valuation of Parisian options based on the work of Chesney, Jeanblanc-Picqué, and Yor [23]. The valuation method is based on obtaining closed formulas for the Laplace transforms of prices with respect to maturity. We establish these formulas for single and double barrier Parisian options. We then study a numerical inversion method for these transforms. We establish a result on the accuracy of this very efficient numerical method. On this occasion, we also prove results related to the regularity of prices and the existence of a density with respect to the Lebesgues measure for Parisian times.