Given a graph sequence and a simple connected subgraph , we denote by the number of monochromatic copies of in a uniformly random vertex coloring of with colors. We prove a central limit theorem for (we denote the appropriately centered and rescaled statistic as ) with explicit error rates. The error rates arise from graph counts of collections formed by joining copies of which we call
This content will become publicly available on May 1, 2024
Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
Abstract We present a probabilistic analysis of two Krylov subspace methods for solving linear systems. We prove a central limit theorem for norms of the residual vectors that are produced by the conjugate gradient and MINRES algorithms when applied to a wide class of sample covariance matrices satisfying some standard moment conditions. The proof involves establishing a four‐moment theorem for the so‐called spectral measure, implying, in particular, universality for the matrix produced by the Lanczos iteration. The central limit theorem then implies an almost‐deterministic iteration count for the iterative methods in question. © 2022 Wiley Periodicals LLC.
more »
« less
- Award ID(s):
- 1945652
- NSF-PAR ID:
- 10443736
- Date Published:
- Journal Name:
- Communications on Pure and Applied Mathematics
- Volume:
- 76
- Issue:
- 5
- ISSN:
- 0010-3640
- Page Range / eLocation ID:
- 1085 to 1136
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
good joins . Good joins are closely related to the fourth moment of , which allows us to show afourth moment phenomenon for the central limit theorem. For , we show that converges in distribution to whenever its fourth moment converges to 3. We show the convergence of the fourth moment is necessary to obtain a normal limit when . -
more » « less
Summary Motivated by the increasing use of kernel-based metrics for high-dimensional and large-scale data, we study the asymptotic behaviour of kernel two-sample tests when the dimension and sample sizes both diverge to infinity. We focus on the maximum mean discrepancy using an isotropic kernel, which includes maximum mean discrepancy with the Gaussian kernel and the Laplace kernel, and the energy distance as special cases. We derive asymptotic expansions of the kernel two-sample statistics, based on which we establish a central limit theorem under both the null hypothesis and the local and fixed alternatives. The new nonnull central limit theorem results allow us to perform asymptotic exact power analysis, which reveals a delicate interplay between the moment discrepancy that can be detected by the kernel two-sample tests and the dimension-and-sample orders. The asymptotic theory is further corroborated through numerical studies.
-
more » « less
Summary Consider a probit regression problem in which Y1, …, Yn are independent Bernoulli random variables such that Pr(Yi=1)=Φ(xiTβ) where xi is a p-dimensional vector of known covariates that are associated with Yi, β is a p-dimensional vector of unknown regression coefficients and Φ(·) denotes the standard normal distribution function. We study Markov chain Monte Carlo algorithms for exploring the intractable posterior density that results when the probit regression likelihood is combined with a flat prior on β. We prove that Albert and Chib's data augmentation algorithm and Liu and Wu's PX-DA algorithm both converge at a geometric rate, which ensures the existence of central limit theorems for ergodic averages under a second-moment condition. Although these two algorithms are essentially equivalent in terms of computational complexity, results of Hobert and Marchev imply that the PX-DA algorithm is theoretically more efficient in the sense that the asymptotic variance in the central limit theorem under the PX-DA algorithm is no larger than that under Albert and Chib's algorithm. We also construct minorization conditions that allow us to exploit regenerative simulation techniques for the consistent estimation of asymptotic variances. As an illustration, we apply our results to van Dyk and Meng's lupus data. This example demonstrates that huge gains in efficiency are possible by using the PX-DA algorithm instead of Albert and Chib's algorithm.
-
null (Ed.)We show that if V has a proper class ofWoodin cardinals, a strong cardinal, and a generically universally Baire iteration strategy (as defined in the paper) then Sealing holds after collapsing the successor of the least strong cardinal to be countable. This result is complementary to other work by the authors where it is shown that Sealing holds in a generic extension of a certain minimal universe. The current theorem is more general in that no minimality assumption is needed. A corollary of the main theorem is that Sealing is consistent relative to the existence of a Woodin cardinal which is a limit of Woodin cardinals. This improves significantly on the first consistency of Sealing obtained by W.H. Woodin. The Largest Suslin Axiom (LSA) is a determinacy axiom isolated byWoodin. It asserts that the largest Suslin cardinal is inaccessible for ordinal definable bijections. Let LSA-over-uB be the statement that in all (set) generic extensions there is a model of LSA whose Suslin, co-Suslin sets are the universally Baire sets. The other main result of the paper shows that assuming V has a proper class of inaccessible cardinals which are limit of Woodin cardinals, a strong cardinal, and a generically universally Baire iteration strategy, in the universe V [g], where g is V -generic for the collapse of the successor of the least strong cardinal to be countable, the theory LSA-over-UB fails; this implies that LSA-over-UB is not equivalent to Sealing (over the base theory of V [g]). This is interesting and somewhat unexpected, in light of other work by the authors. Compare this result with Steel’s well-known theorem that “AD in L(R) holds in all generic extensions” is equivalent to “the theory of L(R) is sealed” in the presence of a proper class of measurable cardinals.more » « less
-
more » « less
Abstract In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on
with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o (n )). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.
