The cumulative empirical spectral measure (CESM) $\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$ of a $n\times n$ symmetric matrix $\mathbf{A}$ is defined as the fraction of eigenvalues of $\mathbf{A}$ less than a given threshold, i.e., $\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$. Spectral sums $\operatorname{tr}(f[\mathbf{A}])$ can be computed as the Riemann–Stieltjes integral of $f$ against $\Phi[\mathbf{A}]$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$ with probability at least $1-\eta$, by applying the Lanczos algorithm for $\lceil 12 t^{-1} + \frac{1}{2} \rceil$ iterations to $\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments.
more »
« less
Diffusions interacting through a random matrix: universality via stochastic Taylor expansion
Abstract Consider $$(X_{i}(t))$$ ( X i ( t ) ) solving a system of N stochastic differential equations interacting through a random matrix $${\mathbf {J}} = (J_{ij})$$ J = ( J ij ) with independent (not necessarily identically distributed) random coefficients. We show that the trajectories of averaged observables of $$(X_i(t))$$ ( X i ( t ) ) , initialized from some $$\mu $$ μ independent of $${\mathbf {J}}$$ J , are universal, i.e., only depend on the choice of the distribution $$\mathbf {J}$$ J through its first and second moments (assuming e.g., sub-exponential tails). We take a general combinatorial approach to proving universality for dynamical systems with random coefficients, combining a stochastic Taylor expansion with a moment matching-type argument. Concrete settings for which our results imply universality include aging in the spherical SK spin glass, and Langevin dynamics and gradient flows for symmetric and asymmetric Hopfield networks.
more »
« less
- Award ID(s):
- 1954337
- NSF-PAR ID:
- 10349917
- Date Published:
- Journal Name:
- Probability Theory and Related Fields
- Volume:
- 180
- Issue:
- 3-4
- ISSN:
- 0178-8051
- Page Range / eLocation ID:
- 1057 to 1097
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract We study the problem of estimating a $k$-sparse signal ${\boldsymbol \beta }_{0}\in{\mathbb{R}}^{p}$ from a set of noisy observations $\mathbf{y}\in{\mathbb{R}}^{n}$ under the model $\mathbf{y}=\mathbf{X}{\boldsymbol \beta }+w$, where $\mathbf{X}\in{\mathbb{R}}^{n\times p}$ is the measurement matrix the row of which is drawn from distribution $N(0,{\boldsymbol \varSigma })$. We consider the class of $L_{q}$-regularized least squares (LQLS) given by the formulation $\hat{{\boldsymbol \beta }}(\lambda )=\text{argmin}_{{\boldsymbol \beta }\in{\mathbb{R}}^{p}}\frac{1}{2}\|\mathbf{y}-\mathbf{X}{\boldsymbol \beta }\|^{2}_{2}+\lambda \|{\boldsymbol \beta }\|_{q}^{q}$, where $\|\cdot \|_{q}$ $(0\le q\le 2)$ denotes the $L_{q}$-norm. In the setting $p,n,k\rightarrow \infty $ with fixed $k/p=\epsilon $ and $n/p=\delta $, we derive the asymptotic risk of $\hat{{\boldsymbol \beta }}(\lambda )$ for arbitrary covariance matrix ${\boldsymbol \varSigma }$ that generalizes the existing results for standard Gaussian design, i.e. $X_{ij}\overset{i.i.d}{\sim }N(0,1)$. The results were derived from the non-rigorous replica method. We perform a higher-order analysis for LQLS in the small-error regime in which the first dominant term can be used to determine the phase transition behavior of LQLS. Our results show that the first dominant term does not depend on the covariance structure of ${\boldsymbol \varSigma }$ in the cases $0\le q\lt 1$ and $1\lt q\le 2,$ which indicates that the correlations among predictors only affect the phase transition curve in the case $q=1$ a.k.a. LASSO. To study the influence of the covariance structure of ${\boldsymbol \varSigma }$ on the performance of LQLS in the cases $0\le q\lt 1$ and $1\lt q\le 2$, we derive the explicit formulas for the second dominant term in the expansion of the asymptotic risk in terms of small error. Extensive computational experiments confirm that our analytical predictions are consistent with numerical results.
-
Abstract For $p\geq 1$ and $(g_{ij})_{1\leq i,j\leq n}$ being a matrix of i.i.d. standard Gaussian entries, we study the $n$-limit of the $\ell _p$-Gaussian–Grothendieck problem defined as $$\begin{align*} & \max\Bigl\{\sum_{i,j=1}^n g_{ij}x_ix_j: x\in \mathbb{R}^n,\sum_{i=1}^n |x_i|^p=1\Bigr\}. \end{align*}$$The case $p=2$ corresponds to the top eigenvalue of the Gaussian orthogonal ensemble; when $p=\infty $, the maximum value is essentially the ground state energy of the Sherrington–Kirkpatrick mean-field spin glass model and its limit can be expressed by the famous Parisi formula. In the present work, we focus on the cases $1\leq p<2$ and $2<p<\infty .$ For the former, we compute the limit of the $\ell _p$-Gaussian–Grothendieck problem and investigate the structure of the set of all near optimizers along with stability estimates. In the latter case, we show that this problem admits a Parisi-type variational representation and the corresponding optimizer is weakly delocalized in the sense that its entries vanish uniformly in a polynomial order of $n^{-1}$.more » « less
-
Several well-known open questions (such as: are all groups sofic/hyperlinear?) have a common form: can all groups be approximated by asymptotic homomorphisms into the symmetric groups $\text{Sym}(n)$ (in the sofic case) or the finite-dimensional unitary groups $\text{U}(n)$ (in the hyperlinear case)? In the case of $\text{U}(n)$ , the question can be asked with respect to different metrics and norms. This paper answers, for the first time, one of these versions, showing that there exist finitely presented groups which are not approximated by $\text{U}(n)$ with respect to the Frobenius norm $\Vert T\Vert _{\text{Frob}}=\sqrt{\sum _{i,j=1}^{n}|T_{ij}|^{2}},T=[T_{ij}]_{i,j=1}^{n}\in \text{M}_{n}(\mathbb{C})$ . Our strategy is to show that some higher dimensional cohomology vanishing phenomena implies stability , that is, every Frobenius-approximate homomorphism into finite-dimensional unitary groups is close to an actual homomorphism. This is combined with existence results of certain nonresidually finite central extensions of lattices in some simple $p$ -adic Lie groups. These groups act on high-rank Bruhat–Tits buildings and satisfy the needed vanishing cohomology phenomenon and are thus stable and not Frobenius-approximated.more » « less
-
more » « less
Abstract When k and s are natural numbers and ${\mathbf h}\in {\mathbb Z}^k$, denote by $J_{s,k}(X;\,{\mathbf h})$ the number of integral solutions of the system $$ \sum_{i=1}^s(x_i^j-y_i^j)=h_j\quad (1\leqslant j\leqslant k), $$ with $1\leqslant x_i,y_i\leqslant X$. When $s\lt k(k+1)/2$ and $(h_1,\ldots ,h_{k-1})\ne {\mathbf 0}$, Brandes and Hughes have shown that $J_{s,k}(X;\,{\mathbf h})=o(X^s)$. In this paper we improve on quantitative aspects of this result, and, subject to an extension of the main conjecture in Vinogradov’s mean value theorem, we obtain an asymptotic formula for $J_{s,k}(X;\,{\mathbf h})$ in the critical case $s=k(k+1)/2$. The latter requires minor arc estimates going beyond square-root cancellation.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s00440-021-01027-7
