Rates in the Empirical Central Limit Theorem for Stationary Weakly Dependent Random Fields

A weak dependence condition is derived as the natural generalization to random fields on notions developed in Doukhan and Louhichi (1999). Examples of such weakly dependent fields are defined. In the context of a weak dependence coefficient series with arithmetic or geometric decay, we give explicit bounds in Prohorov metric for the convergence in the empirical central limit theorem. For random fields indexed by &Zopf ^d , in the geometric decay case, rates have the form n ^−1/(8d+24) L(n), where L(n) is a power of log(n). This revised version was published online in June 2006 with corrections to the Cover Date.     

Empirical distributions in marked point processes

We study the asymptotic behaviour of the empirical distribution function derived from a stationary marked point process when a convex sampling window is expanding without bounds in all directions. We consider a random field model which assumes that the marks and the points are independent and admits dependencies between the marks. The main result is the weak convergence of the empirical process under strong mixing conditions on both independent components of the model. Applying an approximation principle weak convergence can be also shown for appropriately weighted empirical process defined from a stationary d-dimensional germ-grain process with dependent grains.     

Nonasymptotic Bounds on the L 2 Error of Neural Network Regression Estimates

The estimation of multivariate regression functions from bounded i.i.d. data is considered. The L ₂ error with integration with respect to the design measure is used as an error criterion. The distribution of the design is assumed to be concentrated on a finite set. Neural network estimates are defined by minimizing the empirical L ₂ risk over various sets of feedforward neural networks. Nonasymptotic bounds on the L ₂ error of these estimates are presented. The results imply that neural networks are able to adapt to additive regression functions and to regression functions which are a sum of ridge functions, and hence are able to circumvent the curse of dimensionality in these cases.     

Empirtical estimates with minimal <Emphasis Type="Italic">d</Emphasis>-risk for discrete exponential families

We develop an empirical d-a posteriori approach to estimations with uniformly minimal d-risk, when the a priori distribution is completely unknown. For a scalar parameter of a discrete exponential family we construct empirical estimates based on archive data and prove the convergence of the empirical d-risk to the true one. As an example we adduce the estimation of the Poisson distribution parameter. We numerically study the accuracy of the estimates by a statistical modeling technique.     

Renormalised Steepest Descent in Hilbert Space Converges to a Two-Point Attractor

The result that for quadratic functions the classical steepest descent algorithm in R ^d converges locally to a two-point attractor was proved by Akaike. In this paper this result is proved for bounded quadratic operators in Hilbert space. The asymptotic rate of convergence is shown to depend on the starting point while, as expected, confirming the Kantorovich bounds. The introduction of a relaxation coefficient in the steepest-descent algorithm completely changes its behaviour, which may become chaotic. Different attractors are presented. We show that relaxation allows a significantly improved rate of convergence.     

About the prohorov distance between the uniform distribution over the unit cube in R dand its empirical measure

Summary We compute the almost sure order of convergence of the Prokhorov distance between the uniform distribution P over [0, 1] ^d and the empirical measure associated with n independent observations with (common) distribution P. We show that this order of convergence is n ^-1/d up to a power of log(n). This result extends to the case where the observations are weakly dependent.     

Convergence Properties of Two-Stage Stochastic Programming

This paper considers a procedure of two-stage stochastic programming in which the performance function to be optimized is replaced by its empirical mean. This procedure converts a stochastic optimization problem into a deterministic one for which many methods are available. Another strength of the method is that there is essentially no requirement on the distribution of the random variables involved. Exponential convergence for the probability of deviation of the empirical optimum from the true optimum is established using large deviation techniques. Explicit bounds on the convergence rates are obtained for the case of quadratic performance functions. Finally, numerical results are presented for the famous news vendor problem, which lends experimental evidence supporting exponential convergence.     

On Monte Carlo methods for Bayesian multivariate regression models with heavy-tailed errors

We consider Bayesian analysis of data from multivariate linear regression models whose errors have a distribution that is a scale mixture of normals. Such models are used to analyze data on financial returns, which are notoriously heavy-tailed. Let π denote the intractable posterior density that results when this regression model is combined with the standard non-informative prior on the unknown regression coefficients and scale matrix of the errors. Roughly speaking, the posterior is proper if and only if n≥d+k, where n is the sample size, d is the dimension of the response, and k is number of covariates. We provide a method of making exact draws from π in the special case where n=d+k, and we study Markov chain Monte Carlo (MCMC) algorithms that can be used to explore π when n>d+k. In particular, we show how the Haar PX-DA technology studied in Hobert and Marchev (2008) [11] can be used to improve upon Liu’s (1996) [7] data augmentation (DA) algorithm. Indeed, the new algorithm that we introduce is theoretically superior to the DA algorithm, yet equivalent to DA in terms of computational complexity. Moreover, we analyze the convergence rates of these MCMC algorithms in the important special case where the regression errors have a Student’s t distribution. We prove that, under conditions on n, d, k, and the degrees of freedom of the t distribution, both algorithms converge at a geometric rate. These convergence rate results are important from a practical standpoint because geometric ergodicity guarantees the existence of central limit theorems which are essential for the calculation of valid asymptotic standard errors for MCMC based estimates.     

Nash inequalities for finite Markov chains

This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds onl ₂-norms in terms of Dirichlet forms andl ₁-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.     

Cubature formulas for function spaces with moderate smoothness

We construct simple algorithms for high-dimensional numerical integration of function classes with moderate smoothness. These classes consist of square-integrable functions over the d-dimensional unit cube whose coefficients with respect to certain multiwavelet expansions decay rapidly. Such a class contains discontinuous functions on the one hand and, for the right choice of parameters, the quite natural d-fold tensor product of a Sobolev space H^s[0,1] on the other hand.The algorithms are based on one-dimensional quadrature rules appropriate for the integration of the particular wavelets under consideration and on Smolyak's construction. We provide upper bounds for the worst-case error of our cubature rule in terms of the number of function calls. We additionally prove lower bounds showing that our method is optimal in dimension d=1 and almost optimal (up to logarithmic factors) in higher dimensions. We perform numerical tests which allow the comparison with other cubature methods.     

Random polarizations

We derive conditions under which random sequences of polarizations (two-point symmetrizations) on S^d${\mathbb{S}}^d$, R^d${\mathbb{R}}^d$, or H^d${\mathbb{H}}^d$ converge almost surely to the symmetric decreasing rearrangement. The parameters for the polarizations are independent random variables whose distributions need not be uniform. The proof of convergence hinges on an estimate for the expected distance from the limit that yields a bound on the rate of convergence. In the special case of i.i.d. sequences, almost sure convergence holds even for polarizations chosen at random from suitable small sets. As corollaries, we find bounds on the rate of convergence of Steiner symmetrizations that require no convexity assumptions, and show that full rotational symmetry can be achieved by randomly alternating Steiner symmetrizations in a finite number of directions that satisfy an explicit non-degeneracy condition. We also present some negative results on the rate of convergence and give examples where convergence fails.     

The Hilbert Kernel Regression Estimate

Let (X, Y) be an ^d× -valued regression pair, whereXhas a density andYis bounded. Ifni.i.d. samples are drawn from this distribution, the Nadaraya–Watson kernel regression estimate in ^dwith Hilbert kernelK(x)=1/x^dis shown to converge weakly for all such regression pairs. We also show that strong convergence cannot be obtained. This is particularly interesting as this regression estimate does not have a smoothing parameter.     

Entropy estimate for high-dimensional monotonic functions

We establish upper and lower bounds for the metric entropy and bracketing entropy of the class of d-dimensional bounded monotonic functions under L^p norms. It is interesting to see that both the metric entropy and bracketing entropy have different behaviors for p<d/(d-1) and p>d/(d-1). We apply the new bounds for bracketing entropy to establish a global rate of convergence of the MLE of a d-dimensional monotone density.     

The Marčenko‐Pastur law for sparse random bipartite biregular graphs

We prove that the empirical spectral distribution of a (d_L, d_R)‐biregular, bipartite random graph, under certain conditions, converges to a symmetrization of the Mar?enko‐Pastur distribution of random matrix theory. This convergence is not only global (on fixed‐length intervals) but also local (on intervals of increasingly smaller length). Our method parallels the one used previously by Dumitriu and Pal (2012). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 313–340, 2016     

Basic-set algorithm for a generalized linear complementarity problem

In this paper, the authors develop a new direct method for the solution of a BLCP, that is, a linear complementarity problem (LCP) with upper bounds, when its matrix is a symmetric or an unsymmetricP-matrix. The convergence of the algorithm is established by extending Murty's principal pivoting method to an LCP which is equivalent to the BLCP. Computational experience with large-scale BLCPs shows that the basic-set method can solve efficiently large-scale BLCPs with a symmetric or an unsymmetricP-matrix.     

Estimating the error distribution in nonparametric multiple regression with applications to model testing

In this paper we consider the estimation of the error distribution in a heteroscedastic nonparametric regression model with multivariate covariates. As estimator we consider the empirical distribution function of residuals, which are obtained from multivariate local polynomial fits of the regression and variance functions, respectively. Weak convergence of the empirical residual process to a Gaussian process is proved. We also consider various applications for testing model assumptions in nonparametric multiple regression. The model tests obtained are able to detect local alternatives that converge to zero at an n^−1/2-rate, independent of the covariate dimension. We consider in detail a test for additivity of the regression function.     

On r-quick limit sets for empirical and related processes based on mixing random variables

The r-quick limit points of normalized sample paths and empirical distribution functions of mixing processes are characterized. An r-quick version of Bahadur-Kiefer-type representation for sample quantiles is established, which yields the r-quick limit points of quantile processes. These results are applied to linear functions of order statistics. Some results on r-quick convergence of certain Gaussian processes are also established.     

A Note on the Convergence of Integral Functionals of Diffusion Processes. An Application to Strong Convergence

For a diffusion type process dX_t = dW_i + a(t, X)dt and a sequence (f_n) of nonnegative functions necessary and sufficient conditions to the f_n are established which guarantee the a.s. convergence of f_n(X_t)dt to zero. This result is applied to derive simple necessary and sufficient conditions for the strong convergence of distributions of diffusion processes formulated in terms of the corresponding drift functions.     

Swendsen‐Wang dynamics for general graphs in the tree uniqueness region

The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = (V,E). The dynamics is conjectured to converge to equilibrium in O(|V|^1/4) steps at any (inverse) temperature β, yet there are few results providing o(|V|) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite d‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics, for which we obtain new tight mixing time bounds.     

Gradient algorithms for quadratic optimization with fast convergence rates

We propose a family of gradient algorithms for minimizing a quadratic function f(x)=(Ax,x)/2−(x,y) in ℝ ^d or a Hilbert space, with simple rules for choosing the step-size at each iteration. We show that when the step-sizes are generated by a dynamical system with ergodic distribution having the arcsine density on a subinterval of the spectrum of A, the asymptotic rate of convergence of the algorithm can approach the (tight) bound on the rate of convergence of a conjugate gradient algorithm stopped before d iterations, with d≤∞ the space dimension.