An official website of the United States government
Let (kn)n∈N be a sequence of positive integers growing to infinity at a sublinear rate, kn → ∞ and kn/n → 0 as n → ∞. Given a sequence of n-dimensional random vectors {Y (n)}n∈N belonging to a certain class, which includes uniform distributions on suitably scaled ℓnp -balls or ℓnp -spheres, p ≥ 2, and product distributions with sub-Gaussian marginals, we study the large deviations behavior of the corresponding sequence of kn-dimensional orthogonal projections. For almost every sequence of projection matrices, we establish a large deviation principle (LDP) for the corresponding sequence of projections, with a fairly explicit rate function that does not depend on the sequence of projection matrices. As corollaries, we also obtain quenched LDPs for sequences of ℓ2-norms and ℓ∞-norms of the coordinates of the projections. Past work on LDPs for projections with growing dimension has mainly focused on the annealed setting, where one also averages over the random projection matrix, chosen from the Haar measure, in which case the coordinates of the projection are exchangeable. The quenched setting lacks such symmetry properties, and gives rise to significant new challenges in the setting of growing projection dimension. Along the way, we establish new Gaussian approximation results on the Stiefel manifold that may be of independent interest. Such LDPs are of relevance in asymptotic convex geometry, statistical physics and high-dimensional statistics.
more »
« less
Geometric sharp large deviations for random projections of ℓpn spheres and balls
Accurate estimation of tail probabilities of projections of high-dimensional probability measures is of relevance in high-dimensional statistics and asymptotic geometric analysis. Whereas large deviation principles identify the asymptotic exponential decay rate of probabilities, sharp large deviation estimates also provide the “prefactor” in front of the exponentially decaying term. For fixed p ∈ (1, ∞), consider independent sequences (X(n,p))_{n∈N} and (Θ_n)_{n∈N} of random vectors with Θn distributed according to the normalized cone measure on the unit l^n_2 sphere, and X(n,p) distributed according to the normalized cone measure on the unit lnp sphere. For almost every realization (θn)_{n∈N} of (Θ_n)_{n∈N}, (quenched) sharp large deviation estimates are established for suitably normalized (scalar) projections of X(n,p) onto θ_n, that are asymptotically exact (as the dimension n tends to infinity). Furthermore, the case when (X(n,p))_{n∈N} is replaced with (X(n,p))_{n∈N}, where X(n,p) is distributed according to the uniform (or normalized volume) measure on the unit lnp 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 (θ_n)_{n∈N} that encodes additional geometric information that enables one to distinguish between projections of balls and spheres. Moreover, comparison with numerical estimates obtained by direct computation and importance sampling shows that the obtained analytical expressions for tail probabilities provide good approximations even for moderate values of n. The results on the one hand provide more accurate quantitative estimates of tail probabilities of random projections of \ell^n_p spheres than logarithmic asymptotics, and on the other hand, generalize classical sharp large deviation estimates in the spirit of Bahadur and Ranga Rao to a geometric setting. The proofs combine Fourier analytic and probabilistic techniques. Along the way, several results of independent interest are obtained including a simpler representation for the quenched large deviation rate function that shows that it is strictly convex, a central limit theorem for random projections under a certain family of tilted measures, and multidimensional generalized Laplace asymptotics.
more »
« less
- Award ID(s):
- 1954351
- PAR ID:
- 10484620
- Publisher / Repository:
- IMS
- Date Published:
- Journal Name:
- Electronic Journal of Probability
- Volume:
- 29
- Issue:
- 1
- ISSN:
- 1083-6489
- Page Range / eLocation ID:
- 1--56
- Subject(s) / Keyword(s):
- sharp large deviations random projections rate function prefactor Bahadur-Rao correction lnp spheres cone measure spherical caps central limit theorem for convex sets.
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract The study of high-dimensional distributions is of interest in probability theory, statistics, and asymptotic convex geometry, where the object of interest is the uniform distribution on a convex set in high dimensions. The ℓ p -spaces and norms are of particular interest in this setting. In this paper we establish a limit theorem for distributions on ℓ p -spheres, conditioned on a rare event, in a high-dimensional geometric setting. As part of our proof, we establish a certain large deviation principle that is also relevant to the study of the tail behavior of random projections of ℓ p -balls in a high-dimensional Euclidean space.more » « less
-
Using precise random matrix theory tools and the Kac–Rice formula, we provide sharp O(1) asymptotics for the average number of deep minima of the ( p, k) spiked tensor model. These sharp estimates allow us to prove that, when the signal-to-noise ratio is large enough, the expected number of deep minima is asymptotically finite as N tends to infinity and to establish the occurrence of topological trivialization by showing that this number vanishes when the strength of the signal-to-noise ratio diverges. We also derive an explicit formula for the value of the absolute minimum (the limiting ground state energy) on the N-dimensional sphere, similar to the recent work of Jagannath, Lopatto, and Miolane [Ann. Appl. Probab. 4, 1910–1933 (2020)].more » « less
-
We consider the multiparameter random simplicial complex as a higher dimensional extension of the classical Erdős–Rényi graph. We investigate appearance of “unusual” topological structures in the complex from the point of view of large deviations. We first study upper tail large deviation probabilities for subcomplex counts, deriving the order of magnitude of such probabilities at the logarithmic scale precision. The obtained results are then applied to analyze large deviations for the number of simplices of the multiparameter simplicial complexes. Finally, these results are also used to deduce large deviation estimates for Betti numbers of the complex in the critical dimension.more » « less
-
Abstract We establish sharp tail asymptotics for componentwise extreme values of bivariate Gaussian random vectors with arbitrary correlation between the components. We consider two scaling regimes for the tail event in which we demonstrate the existence of a restricted large deviations principle and identify the unique rate function associated with these asymptotics. Our results identify when the maxima of both coordinates are typically attained by two different versus the same index, and how this depends on the correlation between the coordinates of the bivariate Gaussian random vectors. Our results complement a growing body of work on the extremes of Gaussian processes. The results are also relevant for steady-state performance and simulation analysis of networks of infinite server queues.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1214/23-EJP1020
