Given an $n$-dimensional random vector $X^{(n)}$ , for $k < n$, consider its $k$-dimensional projection $mathbf{a}_{n,k}X^{(n)}$, where $mathbf{a}_{n,k}$ is an $n times k$-dimensional matrix belonging to the Stiefel manifold $mathbb{V}_{n,k}$ of orth
onormal $k$-frames in $mathbb{R}^n$. For a class of sequences ${X^{(n)}}$ that includes the uniform distributions on scaled $ell_p^n$ balls, $p in (1,infty]$, and product measures with sufficiently light tails, it is shown that the sequence of projected vectors ${mathbf{a}_{n,k}^intercal X^{(n)}}$ satisfies a large deviation principle whenever the empirical measures of the rows of $sqrt{n} mathbf{a}_{n,k}$ converge, as $n rightarrow infty$, to a probability measure on $mathbb{R}^k$. In particular, when $mathbf{A}_{n,k}$ is a random matrix drawn from the Haar measure on $mathbb{V}_{n,k}$, this is shown to imply a large deviation principle for the sequence of random projections ${mathbf{A}_{n,k}^intercal X^{(n)}}$ in the quenched sense (that is, conditioned on almost sure realizations of ${mathbf{A}_{n,k}}$). Moreover, a variational formula is obtained for the rate function of the large deviation principle for the annealed projections ${mathbf{A}_{n,k}^intercal X^{(n)}}$, which is expressed in terms of a family of quenched rate functions and a modified entropy term. A key step in this analysis is a large deviation principle for the sequence of empirical measures of rows of $sqrt{n} mathbf{A}_{n,k}$, which may be of independent interest. The study of multi-dimensional random projections of high-dimensional measures is of interest in asymptotic functional analysis, convex geometry and statistics. Prior results on quenched large deviations for random projections of $ell_p^n$ balls have been essentially restricted to the one-dimensional setting.
Consider a system of homogeneous interacting diffusive particles labeled by the nodes of a unimodular Galton-Watson (UGW) tree, where the state of each node evolves like a d-dimensional diffusion whose drift coefficient depends on (the histories of)
its own state and the states of neighboring nodes, and whose diffusion coefficient depends only on (the history of) its own state. Under suitable regularity assumptions on the coefficients, an autonomous characterization is obtained for the marginal distribution of the dynamics of the neighborhood of a typical node in terms of a certain local equation, which is a new kind of SDE that is nonlinear in the sense of McKean. This equation describes a finite-dimensional non-Markovian stochastic process whose evolution at any time depends not only on the structure and current state of the neighborhood, but also on the conditional law of the current state given the past of the states of neighborhing nodes. Such marginal distributions are of interest because they arise as weak limits of both marginal distributions and empirical measures of interacting diffusions on many sequences of sparse random graphs, including the configuration model and Erdos-Renyi graphs whose average degrees converge to a finite non-zero limit. The results obtained complement classical results in the mean-field regime, which characterize the limiting dynamics of homogeneous interacting diffusions on complete graphs, as the number of nodes goes to infinity, in terms of a corresponding nonlinear Markov process. However, in the sparse graph setting, the topology of the graph strongly influences the dynamics, and the analysis requires a completely different approach. The proofs of existence and uniqueness of the local equation rely on delicate new conditional independence and symmetry properties of particle trajectories on UGW trees, as well as judicious use of changes of measure.
The hardcore model on a graph $G$ with parameter $lambda>0$ is a probability measure on the collection of all independent sets of $G$, that assigns to each independent set $I$ a probability proportional to $lambda^{|I|}$. In this paper we consider th
e problem of estimating the parameter $lambda$ given a single sample from the hardcore model on a graph $G$. To bypass the computational intractability of the maximum likelihood method, we use the maximum pseudo-likelihood (MPL) estimator, which for the hardcore model has a surprisingly simple closed form expression. We show that for any sequence of graphs ${G_N}_{Ngeq 1}$, where $G_N$ is a graph on $N$ vertices, the MPL estimate of $lambda$ is $sqrt N$-consistent, whenever the graph sequence has uniformly bounded average degree. We then derive sufficient conditions under which the MPL estimate of the activity parameters is $sqrt N$-consistent given a single sample from a general $H$-coloring model, in which restrictions between adjacent colors are encoded by a constraint graph $H$. We verify the sufficient conditions for models where there is at least one unconstrained color as long as the graph sequence has uniformly bounded average degree. This applies to many $H$-coloring examples such as the Widom-Rowlinson and multi-state hard-core models. On the other hand, for the $q$-coloring model, which falls outside this class, we show that consistent estimation may be impossible even for graphs with bounded average degree. Nevertheless, we show that the MPL estimate is $sqrt N$-consistent in the $q$-coloring model when ${G_N}_{Ngeq 1}$ has bounded average double neighborhood. The presence of hard constraints, as opposed to soft constraints, leads to new challenges, and our proofs entail applications of the method of exchangeable pairs as well as combinatorial arguments that employ the probabilistic method.
Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of $N$ parallel queues in which incoming jobs with indepen
dent and identically distributed service times are routed on arrival using the join-the-shortest-of-$d$-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as $Nrightarrowinfty$, the state dynamics converges to the unique solution of a countable system of coupled deterministic measure-valued equations called the hydrodynamic equations. In this article, a characterization of invariant states of these hydrodynamic equations is obtained and, when $d=2$, used to construct a numerical algorithm to compute the queue length distribution and mean virtual waiting time in the invariant state. Additionally, it is also shown that under a suitable tail condition on the service distribution, the queue length distribution of the invariant state exhibits a doubly exponential tail decay, thus demonstrating a vast improvement in performance over the case $d=1$, which corresponds to random routing, when the tail decay could even be polynomial. Furthermore, numerical evidence is provided to support the conjecture that the invariant state is the limit of the steady-state distributions of the $N$-server models. The proof methodology, which entails analysis of a coupled system of measure-valued equations, can potentially be applied to other many-server systems with general service distributions, where measure-valued representations are useful.
For an $ntimes n$ matrix $A_n$, the $rto p$ operator norm is defined as $$|A_n|_{rto p}:= sup_{boldsymbol{x} in mathbb{R}^n:|boldsymbol{x}|_rleq 1 } |A_nboldsymbol{x}|_pquadtext{for}quad r,pgeq 1.$$ For different choices of $r$ and $p$, this norm cor
responds to key quantities that arise in diverse applications including matrix condition number estimation, clustering of data, and finding oblivious routing schemes in transportation networks. This article considers $rto p$ norms of symmetric random matrices with nonnegative entries, including adjacency matrices of ErdH{o}s-Renyi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For $1< pleq r< infty$, the asymptotic normality, as $ntoinfty$, of the appropriately centered and scaled norm $|A_n|_{rto p}$ is established. When $p geq 2$, this is shown to imply, as a corollary, asymptotic normality of the solution to the $ell_p$ quadratic maximization problem, also known as the $ell_p$ Grothendieck problem. Furthermore, a sharp $ell_infty$-approximation bound for the unique maximizing vector in the definition of $|A_n|_{rto p}$ is obtained. This result, which may be of independent interest, is in fact shown to hold for a broad class of deterministic sequences of matrices having certain asymptotic expansion properties. The results obtained can be viewed as a generalization of the seminal results of F{u}redi and Koml{o}s (1981) on asymptotic normality of the largest singular value of a class of symmetric random matrices, which corresponds to the special case $r=p=2$ considered here. In the general case with $1< pleq r < infty$, spectral methods are no longer applicable, and so a new approach is developed, which involves a refined convergence analysis of a nonlinear power method and a perturbation bound on the maximizing vector.
Accurate estimation of tail probabilities of projections of high-dimensional probability measures is of relevance in high-dimensional statistics and asymptotic geometric analysis. For fixed $p in (1,infty)$, let $(X^{(n,p)})$ and $(theta^n)$ be indep
endent sequences of random vectors with $theta^n$ distributed according to the normalized cone measure on the unit $ell_2^n$ sphere, and $X^{(n,p)}$ distributed according to the normalized cone measure on the unit $ell_p^n$ sphere. For almost every sequence of projection directions $(theta^n)$, (quenched) sharp large deviation estimates are established for suitably normalized (scalar) projections of $X^{n,p}$ onto $theta^n$, that are asymptotically exact (as the dimension $n$ tends to infinity). Furthermore, the case when $(X^{(n,p)})$ is replaced with $(mathscr{X}^{(n,p)})$, where $mathscr{X}^{(n,p)}$ is distributed according to the uniform (or normalized volume) measure on the unit $ell_p^n$ ball, is also considered. In both cases, in contrast to the (quenched) large deviation rate function, the prefactor exhibits a dependence on the projection directions $(theta^n)$ that encodes geometric information. Moreover, although the (quenched) large deviation rate functions for the sequences of random projections of $(X^{(n,p)})$ and $(mathscr{X}^{(n,p)})$ are known to coincide, it is shown that the prefactor distinguishes between these two cases. The results on the one hand provide quantitative estimates of tail probabilities of random projections of $ell_p^n$ balls and spheres, valid for finite $n$, generalizing previous results due to Gantert, Kim and Ramanan, and on the other hand, generalize classical sharp large deviation estimates in the spirit of Bahadur and Ranga Rao to a geometric setting.
Consider the projection of an $n$-dimensional random vector onto a random $k_n$-dimensional basis, $k_n leq n$, drawn uniformly from the Haar measure on the Stiefel manifold of orthonormal $k_n$-frames in $mathbb{R}^n$, in three different asymptotic
regimes as $n rightarrow infty$: constant ($k_n=k$), sublinear ($k_n rightarrow infty$ but $k_n/n rightarrow 0$) and linear $k_n/n rightarrow lambda$ with $0 < lambda le 1$). When the sequence of random vectors satisfies a certain asymptotic thin shell condition, we establish annealed large deviation principles (LDPs) for the corresponding sequence of random projections in the constant regime, and for the sequence of empirical measures of the coordinates of the random projections in the sublinear and linear regimes. We also establish LDPs for certain scaled $ell_q$ norms of the random projections in these different regimes. Moreover, we verify our assumptions for various sequences of random vectors of interest, including those distributed according to Gibbs measures with superquadratic interaction potential, or the uniform measure on suitably scaled $ell_p^n$ balls, for $p in [1,infty)$, and generalized Orlicz balls defined via a superquadratic function. Our results complement the central limit theorem for convex sets and related results which are known to hold under a thin shell condition. These results also substantially extend existing large deviation results for random projections, which are first, restricted to the setting of measures on $ell_p^n$ balls, and secondly, limited to univariate LDPs (i.e., in $mathbb{R}$) involving either the norm of a $k_n$-dimensional projection or the projection of $X^{(n)}$ onto a random one-dimensional subspace. Random projections of high-dimensional random vectors are of interest in a range of fields including asymptotic convex geometry and high-dimensional statistics.
We consider a countable system of interacting (possibly non-Markovian) stochastic differential equations driven by independent Brownian motions and indexed by the vertices of a locally finite graph $G = (V,E)$. The drift of the process at each vertex
is influenced by the states of that vertex and its neighbors, and the diffusion coefficient depends on the state of only that vertex. Such processes arise in a variety of applications including statistical physics, neuroscience, engineering and math finance. Under general conditions on the coefficients, we show that if the initial conditions form a second-order Markov random field on $d$-dimensional Euclidean space, then at any positive time, the collection of histories of the processes at different vertices forms a second-order Markov random field on path space. We also establish a bijection between (second-order) Gibbs measures on $(R^d)^V$ (with finite second moments) and a set of space-time (second-order) Gibbs measures on path space, corresponding respectively to the initial law and the law of the solution to the stochastic differential equation. As a corollary, we establish a Gibbs uniqueness property that shows that for infinite graphs the joint distribution of the paths is completely determined by the initial condition and the specifications, namely the family of conditional distributions on finite vertex sets given the configuration on the complement. Along the way, we establish various approximation and projection results for Markov random fields on locally finite graphs that may be of independent interest.
Reflected Brownian motion (RBM) in a convex polyhedral cone arises in a variety of applications ranging from the theory of stochastic networks to math finance, and under general stability conditions, it has a unique stationary distribution. In such a
pplications, to implement a stochastic optimization algorithm or quantify robustness of a model, it is useful to characterize the dependence of stationary performance measures on model parameters. In this work we characterize parametric sensitivities of the stationary distribution of an RBM in a simple convex polyhedral cone; that is, sensitivities to perturbations of the parameters that define the RBM --- namely, the covariance matrix, drift vector and directions of reflection along the boundary of the polyhedral cone. In order to characterize these sensitivities we study the long time behavior of the joint process consisting of an RBM along with its so-called derivative process, which characterizes pathwise derivatives of RBMs on finite time intervals. We show that the joint process is positive recurrent, has a unique stationary distribution, and parametric sensitivities of the stationary distribution of an RBM can be expressed in terms of the stationary distribution of the joint process. This can be thought of as establishing an interchange of the differential operator and the limit in time. The analysis of ergodicity of the joint process is significantly more complicated than that of the RBM due to its degeneracy and the fact that the derivative process exhibits jumps that are modulated by the RBM. The proofs of our results rely on path properties of coupled RBMs and contraction properties related to the geometry of the polyhedral cone and directions of reflection along the boundary. Our results are potentially useful for developing efficient numerical algorithms for computing sensitivities of functionals of stationary RBMs.
We study the limiting behavior of interacting particle systems indexed by large sparse graphs, which evolve either according to a discrete time Markov chain or a diffusion, in which particles interact directly only with their nearest neighbors in the
graph. To encode sparsity we work in the framework of local weak convergence of marked (random) graphs. We show that the joint law of the particle system varies continuously with respect to local weak convergence of the underlying graph marked with the initial conditions. In addition, we show that the global empirical measure converges to a non-random limit for a large class of graph sequences including sparse Erd{o}s-R{e}nyi graphs and configuration models, whereas the empirical measure of the connected component of a uniformly random vertex converges to a random limit. Along the way, we develop some related results on the time-propagation of ergodicity and empirical field convergence, as well as some general results on local weak convergence of Gibbs measures in the uniqueness regime which appear to be new. The results obtained here are also useful for obtaining autonomous descriptions of marginal dynamics of interacting diffusions and Markov chains on sparse graphs. While limits of interacting particle systems on dense graphs have been extensively studied, there are relatively few works that have studied the sparse regime in generality.
