More Like this

1. Faster Kernel Matrix Algebra via Density Estimation

   Backurs, A ; Indyk, P ; Musco, C ; Wagner, T ( January 2021 , International Conference on Machine Learning)

   null (Ed.)

   We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x_1,...,x_n in R^d. In particular, we consider the estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. These are some of the most basic problems defined over kernel matrices. We show that the sum of matrix entries can be estimated up to a multiplicative factor of 1+epsilon in time sublinear in n and linear in d for many popular kernel functions, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and a witnessing approximate eigenvector) can be approximated to a multiplicative factor of 1+epsilon in time sub-quadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation. 

   more » « less
2. Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation

   Bakshi, Ainesh ; Kacham, Praneeth ; Indyk, Piotr ; Silwal, Sandeep ; Zhou, Samson ( January 2023 , International Conference on Learning Representations)

   Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency – given n input points, most kernel-based algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring Ω(n^2) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain subquadratic time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving lin- ear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recently developed Kernel Density Estimation framework, which (after preprocessing in time subquadratic in n) can return estimates of row/column sums of the kernel matrix. In particular, we de- velop efficient reductions from weighted vertex and weighted edge sampling on kernel graphs, simulating random walks on kernel graphs, and importance sampling on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in sublinear (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsi- fication, where we observe a 9x decrease in the number of kernel evaluations over baselines for LRA and a 41x reduction in the graph size for spectral sparsification. 

   more » « less
3. Ensemble-based estimates of eigenvector error for empirical covariance matrices

   https://doi.org/10.1093/imaiai/iay010  

   Taylor, Dane ; Restrepo, Juan G ; Meyer, François G ( July 2018 , Information and Inference: A Journal of the IMA)

   Abstract Covariance matrices are fundamental to the analysis and forecast of economic, physical and biological systems. Although the eigenvalues $\{\lambda _i\}$ and eigenvectors $\{\boldsymbol{u}_i\}$ of a covariance matrix are central to such endeavours, in practice one must inevitably approximate the covariance matrix based on data with finite sample size $n$ to obtain empirical eigenvalues $\{\tilde{\lambda }_i\}$ and eigenvectors $\{\tilde{\boldsymbol{u}}_i\}$, and therefore understanding the error so introduced is of central importance. We analyse eigenvector error $\|\boldsymbol{u}_i - \tilde{\boldsymbol{u}}_i \|^2$ while leveraging the assumption that the true covariance matrix having size $p$ is drawn from a matrix ensemble with known spectral properties—particularly, we assume the distribution of population eigenvalues weakly converges as $p\to \infty $ to a spectral density $\rho (\lambda )$ and that the spacing between population eigenvalues is similar to that for the Gaussian orthogonal ensemble. Our approach complements previous analyses of eigenvector error that require the full set of eigenvalues to be known, which can be computationally infeasible when $p$ is large. To provide a scalable approach for uncertainty quantification of eigenvector error, we consider a fixed eigenvalue $\lambda $ and approximate the distribution of the expected square error $r= \mathbb{E}\left [\| \boldsymbol{u}_i - \tilde{\boldsymbol{u}}_i \|^2\right ]$ across the matrix ensemble for all $\boldsymbol{u}_i$ associated with $\lambda _i=\lambda $. We find, for example, that for sufficiently large matrix size $p$ and sample size $n> p$, the probability density of $r$ scales as $1/nr^2$. This power-law scaling implies that the eigenvector error is extremely heterogeneous—even if $r$ is very small for most eigenvectors, it can be large for others with non-negligible probability. We support this and further results with numerical experiments. 

   more » « less
4. On ℓ p -Gaussian–Grothendieck Problem

   https://doi.org/10.1093/imrn/rnab311  

   Chen, Wei-Kuo ; Sen, Arnab ( November 2021 , International Mathematics Research Notices)

   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
5. Structured Semidefinite Programming for Recovering Structured Preconditioners

   Jambulapati, Arun ; Li, Jerry ; Musco, Christopher ; Shiragur, Kirankumar ; Sidford, Aaron ; Tian, Kevin ( December 2023 , Advances in Neural Information Processing Systems)

   We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including the following. \begin{itemize} \item \textbf{Diagonal preconditioning.} We give an algorithm which, given positive definite $\mathbf{K} \in \mathbb{R}^{d \times d}$ with $\mathrm{nnz}(\mathbf{K})$ nonzero entries, computes an $\epsilon$-optimal diagonal preconditioner in time $\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot \mathrm{poly}(\kappa^\star,\epsilon^{-1}))$, where $\kappa^\star$ is the optimal condition number of the rescaled matrix. \item \textbf{Structured linear systems.} We give an algorithm which, given $\mathbf{M} \in \mathbb{R}^{d \times d}$ that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in $\mathbf{M}$ in $\widetilde{O}(d^2)$ time. \end{itemize} Our diagonal preconditioning results improve state-of-the-art runtimes of $\Omega(d^{3.5})$ attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of $\Omega(d^{\omega})$ where $\omega > 2.3$ is the current matrix multiplication constant. We attain our results via new algorithms for a class of semidefinite programs (SDPs) we call \emph{matrix-dictionary approximation SDPs}, which we leverage to solve an associated problem we call \emph{matrix-dictionary recovery}. 

   more » « less