Random feature matrices' singular values concentrate near their full expectation in high dimensions.
problem Characterizing the spectra of random feature matrices for regression problems.
method Analyzing two settings of input variables (random or well-separated) with conditions on dimension, complexity ratio, and sampling variance.
result The singular values of random feature matrices concentrate near their full expectation and near one with high probability.
Orthogonal random features approximate a Bessel kernel, offering sharper bounds than random Fourier features.
problem Approximating Gaussian kernel efficiently for large datasets.
method Use of Haar orthogonal matrices to construct orthogonal random features and analyze their bias and variance.
result Orthogonal random features approximate a Bessel kernel, not the Gaussian kernel, with sharper bounds.
We analyze the condition number of random feature matrices and prove their well-conditioned nature.
problem Understanding the condition number of random feature matrices and its impact on generalization error.
method Established concentration bounds and derived risk bounds for regression problems using random feature matrices.
result The risk associated with random feature matrices exhibits the double descent phenomenon, improving even with noise.
We propose a scheme for recycling Gaussian random vectors into structured matrices to approximate various kernel functions in sublinear time via random embeddings. Our framework includes the Fastfood construction as a special case, but also extends to Circulant, Toeplitz and Hankel matrices, and the broader family of s…
TRF uses ternary random features to improve ML performance without extra computation.
problem Improving ML performance with less computation and storage.
method Proposes Ternary Random Features (TRF) for random features compression.
result TRF asymptotically yields the same limiting kernel as original matrices, with improved efficiency.
Overview of high-dimensional dynamical systems and their applications to machine learning.
problem Characterizing behavior of high-dimensional dynamical systems driven by random matrices.
method Cavity method arguments, path integrals, dynamical mean field theory (DMFT), and random matrix resolvents.
result Connections between random matrix resolvents and DMFT response, and non-monotonic loss curves in training.
New random feature maps for Laplacian and related kernels.
problem Challenges in approximating the Laplacian kernel and its generalizations.
method Developed random feature maps for Laplacian and related kernels, providing efficient sampling schemes.
result Demonstrated the efficacy of these random feature maps on real datasets.
Study extends bounds on sample covariance matrices with general dependence.
problem Quantitative bounds on sample covariance matrices with i.i.d. columns.
method Extends previous work on deterministic equivalent to rectangular random matrices with general dependence structure.
result Proves quantitative bounds involving dimensions and spectral parameter, including closer proximity to real positive semi-line.
We define a family of probability distributions for random count matrices with a potentially unbounded number of rows and columns. The three distributions we consider are derived from the gamma-Poisson, gamma-negative binomial, and beta-negative binomial processes. Because the models lead to closed-form Gibbs sampling …
This study examines a single attention layer's capabilities using random features.
problem Understanding the learning and generalization of a single multi-head attention layer.
method Random feature setting with large number of heads, frozen query and key matrices, and trainable value matrices.
result Random-feature attention layer can express a broad class of permutation-invariant target functions.
We show that the error probability of reconstructing kernel matrices from Random Fourier Features for the Gaussian kernel function is at most O(R2/3exp(−D)), where D is the number of random features and R is the diameter of the data domain. We also provide an information-theoretic method-independen…
We present an intriguing discovery related to Random Fourier Features: in Gaussian kernel approximation, replacing the random Gaussian matrix by a properly scaled random orthogonal matrix significantly decreases kernel approximation error. We call this technique Orthogonal Random Features (ORF), and provide theoretical…
Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this chal…
Study on the geometric Dyson Brownian motion of non-square matrix products.
problem Understanding the spectrum of a product of non-square random matrices.
method Proportional depth-width limit followed by mean-field limit, solving Burgers equation.
result Free log-normal law is obtained in the identity-start case.
Study on random matrices in deep neural networks with IID entries.
problem Distribution of singular values in product of random matrices for deep neural networks.
method Random matrix theory with a streamlined approach for non-Gaussian data.
result Generalization of macroscopic universality property to non-Gaussian data.
The paper deals with distribution of singular values of product of random matrices arising in the analysis of deep neural networks. The matrices resemble the product analogs of the sample covariance matrices, however, an important difference is that the population covariance matrices, which are assumed to be non-random…
Kernel methods are an extremely popular set of techniques used for many important machine learning and data analysis applications. In addition to having good practical performances, these methods are supported by a well-developed theory. Kernel methods use an implicit mapping of the input data into a high dimensional f…
The paper studies neural networks with wide layers and finds a deformed semicircle law.
problem Investigating spectral distributions of neural networks in the ultra-wide regime.
method Analyzes empirical kernel matrices, proves deformed semicircle law, provides nonlinear Hanson-Wright inequality.
result Emergence of a deformed semicircle law in the ultra-wide neural network regime.
As a typical dimensionality reduction technique, random projection can be simply implemented with linear projection, while maintaining the pairwise distances of high-dimensional data with high probability. Considering this technique is mainly exploited for the task of classification, this paper is developed to study th…
Paper analyzes error bounds for learning with vector-valued RF, improving existing analyses.
problem Learning with vector-valued random features in infinite-dimensional settings.
method Direct analysis of risk functional, avoiding random matrix theory.
result Strong consistency and minimax optimal convergence rates established.
The study proves Gaussian universality of deep random features learning.
problem Understanding the test error in deep random features learning.
method Proving Gaussian universality of test error in ridge regression and arbitrary convex losses.
result Sharp asymptotic formula for test error in ridge regression setting.
A new method for efficient nonlinear process monitoring using random Bernoulli features.
problem High computational demands and real-time responsiveness in online monitoring systems.
method Random Bernoulli principal component analysis to capture nonlinear patterns efficiently.
result The proposed methods offer excellent scalability and reduced computational complexity.
Lower bound proves ridgeless regression performs poorly near interpolation threshold.
problem Proving performance of ridgeless regression near interpolation threshold.
method Distribution-independent lower bound for mean squared error in noisy ridgeless linear regression.
result Lower bound implies ridgeless regression performs poorly near interpolation threshold.
The difficulty of classification affects the weight matrices' heavy tail appearance in deep learning networks.
problem Understanding the spectral properties of weight matrices in deep learning networks.
method Spectral analysis of weight matrices in different modules of DNNs, classification difficulty as a driving factor for heavy tail appearance.
result Higher classification difficulty leads to more frequent appearance of heavy tails in weight matrices spectra.
Uniform approximations for RHTs improve kernel approximation and distance estimation.
problem Theoretical guarantees for RHTs in low-dimensional applications.
method Proved uniform convergence of average of function over RHTs entries.
result Improved guarantees for kernel approximation and distance estimation.
Paper tackles robust graph matching in dense graphs with AMP type algorithm.
problem Matching recovery between correlated Gaussian Wigner matrices with adversarial perturbations.
method Approximate Message Passing (AMP) type iterative algorithm with time-dependent matrix multiplication.
result Algorithm succeeds in polynomial time for non-vanishing correlation and small perturbations.
Feature extraction and dimension reduction for networks is critical in a wide variety of domains. Efficiently and accurately learning features for multiple graphs has important applications in statistical inference on graphs. We propose a method to jointly embed multiple undirected graphs. Given a set of graphs, the jo…
The big data trend has inspired feature-driven learning tasks, which cannot be handled by conventional machine learning models. Unstructured data produces very large binary matrices with millions of columns when converted to vector form. However, such data is often sparse, and hence can be manageable through the use of…
Survey on strong convergence in random matrices and its applications.
problem Understanding convergence of random matrices to operators.
method Analysis of operator norms of noncommutative polynomials.
result New insights and applications in random graphs, geometry, and operator algebras.
The paper proves a distribution claim for neural network Jacobians.
problem Distribution of singular values in deep neural networks.
method Free probability and random matrix theory techniques.
result Singular value distribution matches for specific cases.
We present a generic compact computational framework relying on structured random matrices that can be applied to speed up several machine learning algorithms with almost no loss of accuracy. The applications include new fast LSH-based algorithms, efficient kernel computations via random feature maps, convex optimizati…
Characterizes test error in learning with deep, structured feature maps.
problem Characterizing test error in learning with deep, structured feature maps.
method Asymptotic analysis of feature covariance and population covariance.
result Closed-form formula for feature covariance in Gaussian rainbow neural networks.
Complex systems are typically represented by large ensembles of observations. Correlation matrices provide an efficient formal framework to extract information from such multivariate ensembles and identify in a quantifiable way patterns of activity that are reproducible with statistically significant frequency compared…
Random projections help in representing sparse graphs efficiently.
problem Efficiently representing sparse graphs of varying sizes and vertex sets.
method Random projection of adjacency matrices to retain graph functionality and properties.
result Random projections can accurately represent graphs of different sizes and vertex sets in the same space.
Improved method for computing Fréchet means on SPD matrices.
problem Computing Fréchet means on the manifold of SPD matrices.
method Random matrix theory-based approach for estimating Fréchet means.
result Significantly outperforms state-of-the-art methods in experiments.
New invariants derived from random matrices for words in free groups.
problem Defining and understanding new topological invariants for words in free groups.
method Defining and analyzing invariants from w-random matrices and permutations. result Presented new topological, combinatorial, and algebraic invariants of words.
In this paper, we present a new framework to obtain tail inequalities for sums of random matrices. Compared with existing works, our tail inequalities have the following characteristics: 1) high feasibility--they can be used to study the tail behavior of various matrix functions, e.g., arbitrary matrix norms, the absol…
Paper develops new method for detecting latent structure in large symmetric data matrices.
problem Testing for latent structure in large symmetric data matrices.
method Introduces Wilcoxon--Wigner random matrices based on normalized rank statistics.
result Establishes asymptotic Gaussian fluctuations for leading eigenvalue and eigenvector of Wilcoxon--Wigner matrices.
Nonparametric regression for massive numbers of samples (n) and features (p) is an increasingly important problem. In big n settings, a common strategy is to partition the feature space, and then separately apply simple models to each partition set. We propose an alternative approach, which avoids such partitioning and…
Study spectral density of neural networks using resolvent method.
problem Investigate spectral density of neural networks with random feature matrices.
method Use resolvent method from random matrix theory, cumulant expansion.
result Impossible to preserve singular value distribution with additive bias.
The paper introduces a new method for tail bounds of random vectors and matrices.
problem Estimating norms of random vectors and matrices under moment assumptions.
method Variational tail bounds for norms of random vectors and matrices.
result Dimension-free concentration inequalities for various norms of random vectors and matrices.
Study shows how mini-batch GD with random reshuffling affects least squares regression dynamics.
problem Analyzing the error dynamics of mini-batch GD with random reshuffling for least squares regression.
method Represented training and generalization errors through a sample cross-covariance matrix Z, compared with sample covariance matrix of original features X, and used linear scaling rule for analysis.
result Mini-batch GD with random reshuffling exhibits subtle step-size dependence not detectable by gradient flow analysis, converging to a limit dependent on the step size.
Study shows how feature weighting affects neural network regularization.
problem Understanding how feature weighting influences neural network regularization.
method Derived equivalence paths connecting different weighting matrices and ridge regularization levels.
result Ridge estimators trained on weighted features are asymptotically equivalent when evaluated against test vectors.
The paper analyzes ridge regression with random features for non-identically distributed data.
problem Analyzing ridge regression performance for data with heterogeneous variance profiles.
method Combining linear-plus-chaos approximation and operator-valued free probability.
result Derives asymptotic equivalents for training and test risks under non-identically distributed data.
Enhances graph neural networks with random walks to improve performance.
problem Limited input to graph neural networks, especially for molecular data.
method Random walk data processing to enrich graph neural network input.
result Shallow network outperforms deep GNNs using only node features.
Kernel methods are successful approaches for different machine learning problems. This success is mainly rooted in using feature maps and kernel matrices. Some methods rely on the eigenvalues/eigenvectors of the kernel matrix, while for other methods the spectral information can be used to estimate the excess risk. An …
Graph connection Laplacian (GCL) is a modern data analysis technique that is starting to be applied for the analysis of high dimensional and massive datasets. Motivated by this technique, we study matrices that are akin to the ones appearing in the null case of GCL, i.e the case where there is no structure in the datas…
New theory for eigenvectors of generalized Laplacian matrices, addressing dependency issues.
problem Dependency in random matrix theory hinders eigenvector analysis for latent embeddings.
method Introduces generalized Laplacian matrices and a new asymptotic theory framework.
result Established asymptotic normalities for spiked eigenvectors and eigenvalues.