Normal Approximation of Poisson Functionals in Kolmogorov Distance

Peccati, Solè, Taqqu, and Utzet recently combined Stein’s method and Malliavin calculus to obtain a bound for the Wasserstein distance of a Poisson functional and a Gaussian random variable. Convergence in the Wasserstein distance always implies convergence in the Kolmogorov distance at a possibly weaker rate. But there are many examples of central limit theorems having the same rate for both distances. The aim of this paper was to show this behavior for a large class of Poisson functionals, namely so-called U-statistics of Poisson point processes. The technique used by Peccati et al. is modified to establish a similar bound for the Kolmogorov distance of a Poisson functional and a Gaussian random variable. This bound is evaluated for a U-statistic, and it is shown that the resulting expression is up to a constant the same as it is for the Wasserstein distance.     

Normal approximation on Poisson spaces: Mehler’s formula,second order Poincaré inequalities and stabilization

We prove a new class of inequalities, yielding bounds for the normal approximation in the Wasserstein and the Kolmogorov distance of functionals of a general Poisson process (Poisson random measure). Our approach is based on an iteration of the classical Poincaré inequality, as well as on the use of Malliavin operators, of Stein’s method, and of an (integrated) Mehler’s formula, providing a representation of the Ornstein-Uhlenbeck semigroup in terms of thinned Poisson processes. Our estimates only involve first and second order difference operators, and have consequently a clear geometric interpretation. In particular we will show that our results are perfectly tailored to deal with the normal approximation of geometric functionals displaying a weak form of stabilization, and with non-linear functionals of Poisson shot-noise processes. We discuss two examples of stabilizing functionals in great detail: (i) the edge length of the k-nearest neighbour graph, (ii) intrinsic volumes of k-faces of Voronoi tessellations. In all these examples we obtain rates of convergence (in the Kolmogorov and the Wasserstein distance) that one can reasonably conjecture to be optimal, thus significantly improving previous findings in the literature. As a necessary step in our analysis, we also derive new lower bounds for variances of Poisson functionals.     

On the asymptotics of locally dependent point processes

We investigate a family of approximating processes that can capture the asymptotic behaviour of locally dependent point processes. We prove two theorems presented to accommodate respectively the positively and negatively related dependent structures. Three examples are given to illustrate that our approximating processes can circumvent the technical difficulties encountered in compound Poisson process approximation (see Barbour and Månsson (2002) [10]) and our approximation error bound decreases when the mean number of the random events increases, in contrast to the increasing of bounds for compound Poisson process approximation.     

Polynomial Birth–Death Distribution Approximation in the Wasserstein Distance

The polynomial birth–death distribution (abbreviated, PBD) on ℐ={0,1,2,…} or ℐ={0,1,2,…,m} for some finite m introduced in Brown and Xia (Ann. Probab. 29:1373–1403, 2001) is the equilibrium distribution of the birth–death process with birth rates {α _i } and death rates {β _i }, where α _i ≥0 and β _i ≥0 are polynomial functions of i∈ℐ. The family includes Poisson, negative binomial, binomial, and hypergeometric distributions. In this paper, we give probabilistic proofs of various Stein’s factors for the PBD approximation with α _i =a and β _i =i+bi(i−1) in terms of the Wasserstein distance. The paper complements the work of Brown and Xia (Ann. Probab. 29:1373–1403, 2001) and generalizes the work of Barbour and Xia (Bernoulli 12:943–954, 2006) where Poisson approximation (b=0) in the Wasserstein distance is investigated. As an application, we establish an upper bound for the Wasserstein distance between the PBD and Poisson binomial distribution and show that the PBD approximation to the Poisson binomial distribution is much more precise than the approximation by the Poisson or shifted Poisson distributions.      

On exceedances of high levels

The distribution of the excess process describing heights of extreme values can be approximated by the distribution of a Poisson cluster process. An estimate of the accuracy of such an approximation has been derived in [4] in terms of the Wasserstein distance. The paper presents a sharper estimate established in terms of the stronger total variation distance. We derive also a new bound to the accuracy of negative Binomial approximation to the distribution of the number of exceedances.     

Improved lower bounds on the total variation distance for the Poisson approximation

New lower bounds on the total variation distance between the distribution of a sum of independent Bernoulli random variables and the Poisson random variable (with the same mean) are derived via the Chen–Stein method. The new bounds rely on a non-trivial modification of the analysis by Barbour and Hall (1984) which surprisingly gives a significant improvement. A use of the new lower bounds is addressed.     

Normal convergence using Malliavin calculus with applications and examples

We prove the chain rule in the more general framework of the Wiener–Poisson space, allowing us to obtain the so-called Nourdin–Peccati bound. From this bound, we obtain a second-order Poincaré-type inequality that is useful in terms of computations. For completeness we survey these results on the Wiener space, the Poisson space, and the Wiener–Poisson space. We also give several applications to central limit theorems with relevant examples: linear functionals of Gaussian subordinated fields (where the subordinated field can be processes like fractional Brownian motion or the solution of the Ornstein–Uhlenbeck SDE driven by fractional Brownian motion), Poisson functionals in the first Poisson chaos restricted to infinitely many “small” jumps (particularly fractional Lévy processes), and the product of two Ornstein–Uhlenbeck processes (one in the Wiener space and the other in the Poisson space). We also obtain bounds for their rate of convergence to normality.     

Peacocks nearby: Approximating sequences of measures

A peacock is a family of probability measures with finite mean that increases in convex order. It is a classical result, in the discrete time case due to Strassen, that any peacock is the family of one-dimensional marginals of a martingale. We study the problem whether a given sequence of probability measures can be approximated by a peacock. In our main results, the approximation quality is measured by the infinity Wasserstein distance. Existence of a peacock within a prescribed distance is reduced to a countable collection of rather explicit conditions. This result has a financial application (developed in a separate paper), as it allows to check European call option quotes for consistency. The distance bound on the peacock then takes the role of a bound on the bid–ask spread of the underlying. We also solve the approximation problem for the stop-loss distance, the Lévy distance, and the Prokhorov distance.     

One Approach to the Comparison of Error Bounds at a Point and on a Set in the Solution of Ill-Posed Problems

The approximate solution of ill-posed problems by the regularization method always involves the issue of estimating the error. It is a common practice to use uniform bounds on the whole class of well-posedness in terms of the modulus of continuity of the inverse operator on this class. Local error bounds, which are also called error bounds at a point, have been studied much less. Since the solution of a real-life ill-posed problem is unique, an error bound obtained on the whole class of well-posedness roughens to a great extent the true error bound. In the present paper, we study the difference between error bounds on the class of well-posedness and error bounds at a point for a special class of ill-posed problems. Assuming that the exact solution is a piecewise smooth function, we prove that an error bound at a point is infinitely smaller than the exact bound on the class of well-posedness.     

Discrete Approximation Scheme in Distributionally Robust Optimization

Discrete approximation, which has been the prevailing scheme in stochastic programming in the past decade, has been extended to distributionally robust optimization (DRO) recently. In this paper, we conduct rigorous quantitative stability analysis of discrete approximation schemes for DRO, which measures the approximation error in terms of discretization sample size. For the ambiguity set defined through equality and inequality moment conditions, we quantify the discrepancy between the discretized ambiguity sets and the original set with respect to the Wasserstein metric. To establish the quantitative convergence, we develop a Hoffman error bound theory with Hoffman constant calculation criteria in a infinite dimensional space, which can be regarded as a byproduct of independent interest. For the ambiguity set defined by Wasserstein ball and moment conditions combined with Wasserstein ball, we present similar quantitative stability analysis by taking full advantage of the convex property inherently admitted by Wasserstein metric. Efficient numerical methods for specifically solving discrete approximation DRO problems with thousands of samples are also designed. In particular, we reformulate different types of discrete approximation problems into a class of saddle point problems with completely separable structures. The stochastic primal-dual hybrid gradient (PDHG) algorithm where in each iteration we update a random subset of the sampled variables is then amenable as a solution method for the reformulated saddle point problems. Some preliminary numerical tests are reported.     

Optimal Markovian Coupling and Exponential Convergence Rate for the TCP Process

In this work, by constructing optimal Markovian couplings we investigate exponential convergence rate in the Wasserstein distance for the transmission control protocol process. Most importantly, we provide a variational formula for the lower bound of the exponential convergence rate.     

Rates of convergence for extremes of geometric random variables and marked point processes

We use the Stein-Chen method to study the extremal behaviour of univariate and bivariate geometric laws. We obtain a rate for the convergence, to the Gumbel distribution, of the law of the maximum of i.i.d. geometric random variables, and show that convergence is faster when approximating by a discretised Gumbel. We similarly find a rate of convergence for the law of maxima of bivariate Marshall-Olkin geometric random pairs when approximating by a discrete limit law. We introduce marked point processes of exceedances (MPPEs), both with univariate and bivariate Marshall-Olkin geometric variables as marks and determine bounds on the error of the approximation, in an appropriate probability metric, of the law of the MPPE by that of a Poisson process with same mean measure. We then approximate by another Poisson process with an easier-to-use mean measure and estimate the error of this additional approximation. This work contains and extends results contained in the second author’s PhD thesis (Feidt 2013) under the supervision of Andrew D. Barbour.     

Error bound results for generalized D-gap functions of nonsmooth variational inequality problems

Solving a variational inequality problem can be equivalently reformulated into solving a unconstraint optimization problem where the corresponding objective function is called a merit function. An important class of merit function is the generalized D-gap function introduced in [N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, J. Optim. Theory Appl. 92 (1997) 439-456] and Yamashita and Fukushima (1997) [17]. In this paper, we present new fractional local/global error bound results for the generalized D-gap functions of nonsmooth variational inequality problems, which gives an effective estimate on the distance between a specific point to the solution set, in terms of the corresponding function value of the generalized D-gap function. Numerical examples and a simple application to the free boundary problem are also presented to illustrate the significance of our error bound results.     

Percolation and limit theory for the poisson lilypond model

The lilypond model on a point process in d ‐space is a growth‐maximal system of non‐overlapping balls centred at the points. We establish central limit theorems for the total volume and the number of components of the lilypond model on a sequence of Poisson or binomial point processes on expanding windows. For the lilypond model over a homogeneous Poisson process, we give subexponentially decaying tail bounds for the size of the cluster at the origin. Finally, we consider the enhanced Poisson lilypond model where all the balls are enlarged by a fixed amount (the enhancement parameter), and show that for d > 1 the critical value of this parameter, above which the enhanced model percolates, is strictly positive. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

Convergence to equilibrium in Wasserstein distance for Fokker–Planck equations

We describe conditions on non-gradient drift diffusion Fokker–Planck equations for its solutions to converge to equilibrium with a uniform exponential rate in Wasserstein distance. This asymptotic behaviour is related to a functional inequality, which links the distance with its dissipation and ensures a spectral gap in Wasserstein distance. We give practical criteria for this inequality and compare it to classical ones. The key point is to quantify the contribution of the diffusion term to the rate of convergence, in any dimension, which to our knowledge is a novelty.     

Poisson Broken Lines Process and its Application to Bernoulli First Passage Percolation

In this note we introduce a process, which we call 'the Poisson broken lines process", and we compute the intensity of a point process which is obtained by intersecting the Poisson broken lines process with an abscissa axis. In the second part we apply this result to compute an explicit lower bound for the time constant of a planar Bernoulli first passage percolation model with the parameter p < p_c.     

Modified Massive Arratia Flow and Wasserstein Diffusion

Extending previous work by the first author we present a variant of the Arratia flow, which consists of a collection of coalescing Brownian motions starting from every point of the unit interval. The important new feature of the model is that individual particles carry mass that aggregates upon coalescence and that scales the diffusivity of each particle in an inverse proportional way. In this work we relate the induced measure-valued process to the Wasserstein diffusion of von Renesse and Sturm. First, we present the process as a martingale solution to an SPDE similar to that of von Renesse and Sturm. Second, as our main result we show a Varadhan formula 42 for short times that is governed by the quadratic Wasserstein distance. © 2018 Wiley Periodicals, Inc.     

Circuit lower bounds and linear codes

In 1977, Valiant proposed a graph-theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to proving lower bounds on the rigidity of a matrix, a notion that he introduced in that paper. The largest lower bound for an explicitly given matrix is due to J. Friedman, who proved a lower bound on the rigidity of the generator matrices of error-correcting codes over finite fields. He showed that the proof can be interpreted as a bound on a certain parameter defined for all linear spaces of finite dimension. In this note, we define another parameter that can be used to prove lower bounds on circuits with linear gates. Our parameter may be larger than Friedman’s, and it seems incomparable with rigidity, hence it may be easier to prove a lower bound using this notion. Bibliography: 14 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 188–204.