Paper develops efficient methods for leverage score sampling and kernel ridge regression.
problem Efficiently sampling leverage scores for large matrices.
method Novel algorithm for leverage score sampling and kernel ridge regression solver.
result Proposed algorithms are the most efficient and accurate for leverage score sampling and kernel ridge regression.
We explain theoretically a curious empirical phenomenon: "Approximating a matrix by deterministically selecting a subset of its columns with the corresponding largest leverage scores results in a good low-rank matrix surrogate". To obtain provable guarantees, previous work requires randomized sampling of the columns wi…
Generalizes leverage score sampling for neural networks, accelerating kernel methods and deep learning.
problem Accelerating kernel methods and deep learning training.
method Generalizes leverage score sampling to neural networks and proves equivalence to neural tangent kernel ridge regression.
result Equivalence between regularized neural network and neural tangent kernel ridge regression under leverage score sampling initialization.
This paper improves random feature sampling using empirical leverage scores.
problem Optimizing the number of features for kernel approximation and supervised learning.
method Uses empirical leverage scores to optimize feature sampling.
result Empirical sampling of random features using leverage scores outperforms vanilla Monte Carlo sampling.
Efficiently approximates statistical leverage scores for faster KRR.
problem Accurately estimating statistical leverage scores for fast KRR.
method Analytic formula for statistical leverage scores, leveraging kernel spectral density.
result Linear time approximation with theoretical guarantees, significantly faster than existing methods.
Extends importance sampling to nonlinear models using adjoint operators.
problem Lack of tools for identifying important data points in nonlinear models.
method Introduces adjoint operator for nonlinear maps, generalizes norm and leverage scores.
result Generalized scores provide approximation guarantees for nonlinear mappings.
Exact recovery of low-rank matrices from few entries improved with relaxed leverage sampling.
problem Exact recovery of low-rank matrices from a small number of observed entries.
method Sampling probabilities proportional to the sum of leverage scores minus their product.
result Exact recovery with fewer entries than previously possible, matching theoretical lower bounds.
New method connects leverage scores and kernel density, revealing a decreasing relationship.
problem Understanding the relationship between leverage scores and kernel density.
method Introducing regularized Christoffel functions to study leverage scores for kernel methods.
result Quantitatively describes a decreasing relation between leverage score and population density for a broad class of kernels.
Improves generative model coverage of underrepresented modes.
problem Generative models miss underrepresented modes in data.
method Leverage score sampling for complete mode coverage.
result Significantly improves mode coverage compared to standard methods.
Paper introduces max-plus statistical leverage scores for faster approximation of conventional scores.
problem Approximating statistical leverage scores of complex matrices efficiently.
method Max-plus algebraic analogue for statistical leverage scores.
result Max-plus statistical leverage scores can approximate conventional scores quickly and accurately.
Binary testing for softmax models requires many samples, similar to leverage score models.
problem Binary hypothesis testing for softmax models and leverage score models.
method Analyzing sample complexity and drawing analogies between models.
result Sample complexity is asymptotically \(O(ε^{-2})\), where \(ε\) is the distance between model parameters.
ALEVS uses statistical leverage scores for more efficient active learning.
problem Efficiently selecting queries for better classifier accuracy with fewer labels.
method Sampling data instances with high statistical leverage scores.
result Sampling high leverage points leads to effective active learning.
Deterministic column sampling using ridge leverage scores provides accurate matrix sketches for ridge regression.
problem Regularizing ill-posed linear least-squares problems with small but non-zero coefficients.
method Deterministic column sampling using ridge leverage scores.
result Deterministic algorithm provides (1 + ε) error column subset selection and projection-cost preservation.
The paper introduces a new spectral error bound for column subset selection.
problem Improving the reconstruction error in column subset selection.
method Developed a novel analysis of spectral norm reconstruction for a randomized algorithm, introducing a sampling-dependent error bound.
result A new sampling distribution with probabilities proportional to the square root of statistical leverage scores outperforms uniform and leverage-based sampling.
Faster solution for regression and ERM problems using leverage score sampling.
problem Efficiently solving regression and ERM problems with large datasets.
method Combination of leverage score sampling, proximal point methods, and accelerated coordinate descent.
result Improved running time for solving regression and ERM problems.
A new algorithm for efficient kernel Nyström approximation.
problem Efficiently approximating large kernel matrices for machine learning.
method Recursive sampling of landmark points using ridge leverage scores.
result Scalable and accurate kernel approximation with linear runtime.
New algorithm samples matrix rows proportional to their ℓ_p norm in a turnstile data stream.
problem Sampling rows of a dynamic matrix efficiently in a turnstile data stream.
method Develops a novel algorithm for sampling rows proportional to their ℓ_p norm in a turnstile data stream, returning sampled row indexes and approximated sampling probabilities.
result Achieves ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) approximation for logistic regression in a turnstile data stream with polynomial sketch size. Paper introduces a method for continual learning using online leverage scores.
problem Avoiding forgetting and interference of previous knowledge in continual learning.
method Uses statistical leverage scores to measure data importance and a frequent directions approach for online continual learning.
result Demonstrates effectiveness in avoiding catastrophic forgetting and computational efficiency.
New feature selection methods for ridge regression with theoretical guarantees.
problem Improving feature selection for ridge regression with theoretical guarantees.
method Single-set spectral sparsification and leverage-score sampling.
result Risk bounds show that the risk in the sampled space is comparable to the risk in the full-feature space.
This paper improves matrix completion by leveraging element importance and non-uniform sampling.
problem The challenge of completing low-rank matrices from noisy, subsampled measurements.
method Employing leverage scores to characterize element importance and devising a biased sampling procedure.
result Theoretical and empirical evidence shows that a smaller number of entries (about O ( n r log 2 ( n ) ) O(nr\log^2(n)) O ( n r log 2 ( n )) ) can recover a low-rank matrix with noise. Matrix completion, i.e., the exact and provable recovery of a low-rank matrix from a small subset of its elements, is currently only known to be possible if the matrix satisfies a restrictive structural constraint---known as {\em incoherence}---on its row and column spaces. In these cases, the subset of elements is sam…
LSAR efficiently estimates AR models for big time series data.
problem Efficiently analyzing large-scale time series data with high accuracy.
method Developed a fast algorithm to estimate leverage scores and an efficient LSAR algorithm for fitting AR models.
result LSAR algorithm finds maximum likelihood estimates with high probability and improved worst-case running time.
Optimal sampling reduces power grid data analysis costs.
problem Efficient online analysis of high-speed, correlated IoT data.
method D-optimality criterion-based sampling methods combining Bernoulli and leverage score sampling.
result Leverage score sampling improves computational efficiency and outperforms benchmarks.
Non-uniform landmark sampling improves KCCA approximation accuracy.
problem Improving the Nyström approximation for large-scale KCCA.
method Proposes non-uniform sampling based on statistical leverage scores.
result Non-uniform sampling leads to better approximation accuracy.
New active learning methods use statistical leverage scores to select examples efficiently.
problem Efficiently selecting labeled examples for high model accuracy with limited labeled data.
method Proposes ALEVS and DBALEVS methods based on statistical leverage scores.
result DBALEVS selects diverse, representative examples efficiently.
Low-rank matrix completion is an important problem with extensive real-world applications. When observations are uniformly sampled from the underlying matrix entries, existing methods all require the matrix to be incoherent. This paper provides the first working method for coherent matrix completion under the standard …
New algorithms estimate matrix leverage scores using rank revealing and randomization.
problem Estimating leverage scores for matrices of arbitrary rank.
method Combining rank revealing methods with randomized dimensionality reduction.
result Effective estimators for leverage scores, even in rank deficient cases.
For any matrix A in R^(m x n) of rank ρ, we present a probability distribution over the entries of A (the element-wise leverage scores of equation (2)) that reveals the most influential entries in the matrix. From a theoretical perspective, we prove that sampling at most s = O ((m + n) ρ^2 ln (m + n)) entries of the ma…
A new algorithm approximates logistic regression probabilities efficiently.
problem Efficiently approximating probabilities in logistic regression for large datasets.
method Randomized sampling-based algorithm with leverage scores.
result Accurate approximations to estimated probabilities with smaller sample sizes.
Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with pr…
SALSA efficiently approximates leverage scores for big data, improving ARMA model fitting.
problem Efficiently approximating leverage scores for large matrices.
method Sequential approximate leverage-score algorithm (SALSA) using randomized numerical linear algebra.
result SALSA approximates leverage scores within ( 1 + O ( ε ) ) (1 + O({\varepsilon})) ( 1 + O ( ε )) with high probability. Efficiently approximates integrals using a subset of samples from a target distribution in RKHS.
problem Approximating integrals with a target distribution using limited pointwise evaluations.
method Proposes a procedure using a small random subset of samples from the target distribution, either uniformly or using approximate leverage scores.
result Upper bound on approximation error for both sampling strategies, achieving optimal rate with reduced evaluations.
Improved bounds for ℓ p \ell_p ℓ p sensitivity sampling reducing the sample complexity for structured matrices.
problem Improving the sample complexity for structured matrices using ℓ p \ell_p ℓ p sensitivity sampling. method Developed new bounds for ℓ p \ell_p ℓ p sensitivity sampling, achieving a bound of roughly S 2 − 2 / p \mathfrak{S}^{2-2/p} S 2 − 2/ p for 2 < p < ∞ 2 < p < \infty 2 < p < ∞ . result Achieved improved bounds for ℓ p \ell_p ℓ p sensitivity sampling, reducing the sample complexity for structured matrices. Unified analysis improves random Fourier features for kernel methods.
problem Pessimistic theoretical bounds on random Fourier features.
method Unified risk analysis for squared error and Lipschitz loss.
result Improved bounds on number of features for convergence.
New method assesses individual training points' privacy risk without retraining.
problem Privacy vulnerability of individual training points in membership inference attacks.
method Derives a closed-form decomposition of individual black-box MIA vulnerability, extending to deep networks.
result Proposes a surrogate score operating on last-layer representations that requires only a single trained model.
A new method uses local sensitivity to improve importance sampling for approximating complex loss functions.
problem Approximating complex loss functions using subsampling with strong theoretical guarantees.
method Introducing local sensitivity to measure data point importance and using leverage scores for efficient estimation.
result Local sensitivity sampling can be efficiently estimated and used to approximate complex loss functions with strong guarantees.
Sketched SVD improves SVD runtime for large datasets.
problem Efficiently applying SVD to large datasets.
method Randomized sketching to approximate SVD.
result Sketched SVD provides accurate leverage score ordering.
A new robust PCA method uses Innovation Search and Leverage Scores.
problem Outlier detection and robust PCA in data clustering.
method Innovation Search and Leverage Scores.
result The method provides theoretical guarantees and outperforms existing algorithms.
Recently theoretical guarantees have been obtained for matrix completion in the non-uniform sampling regime. In particular, if the sampling distribution aligns with the underlying matrix's leverage scores, then with high probability nuclear norm minimization will exactly recover the low rank matrix. In this article, we…
Faster sampler reduces DPP sampling cost to O(nm + m^3 log m).
problem High cost of sampling discrete DPPs.
method Uses rejection sampling and leverage score i.i.d. sampling.
result Reduces sampling cost from O(n^3) to O(nm + m^3 log m).
SQUEAK reduces space complexity for Nystrom approximations in KRR.
problem Large datasets in KRR require impractical storage space.
method SQUEAK uses unnormalized ridge leverage scores for incremental updates.
result Space complexity improved with constant factor worse than exact RLS.
The paper compares statistical and algorithmic aspects of sketching for LS problems.
problem Solving large-scale least-squares problems efficiently.
method Randomized sketching algorithms using random projections and leverage-score sampling.
result Upper bounds on statistical prediction and residual efficiencies for various sketching methods.
SQUEAK approximates kernel matrices without storing the full matrix, scaling to large datasets.
problem Large datasets make kernel-based methods impractical due to high time and space requirements.
method Sequentially processes the dataset, using RLS sampling to create a small dictionary for accurate approximations.
result SQUEAK achieves accurate kernel matrix approximations with a number of points only dependent on the effective dimension of the dataset.
A new method reduces the bias in estimating inverse covariance matrices from sketches.
problem Reducing the bias in estimating inverse covariance matrices from sketches.
method Developed a framework for analyzing inversion bias and proposed a new sketching technique called LEverage Score Sparsified (LESS) embeddings.
result The new sketching technique reduces the inversion bias to O ( 1 / d ) O(1/\sqrt d) O ( 1/ d ) for m = O ( d ) m=O(d) m = O ( d ) , significantly smaller than the Θ ( 1 ) Θ(1) Θ ( 1 ) approximation error. We study the effectiveness of non-uniform randomized feature selection in decision tree classification. We experimentally evaluate two feature selection methodologies, based on information extracted from the provided dataset: ( i ) (i) ( i ) \emph{leverage scores-based} and ( i i ) (ii) ( ii ) \emph{norm-based} feature selection. Experimenta…
Kernel quadrature uses DPPs for sampling with tight error bounds.
problem Efficiently sampling nodes for quadrature rules in RKHS.
method Nodes sampled from a truncated and saturated DPP kernel.
result Tighter quadrature error bounds using DPPs.
New sampling strategies for graph signal recovery show faster convergence rates.
problem Signal recovery on irregular graphs.
method Two sampling strategies: random and experimentally designed. Proposed recovery strategies based on these.
result Experimentally designed sampling converges faster than random sampling for irregular graphs.
In this work, we propose a new randomized algorithm for computing a low-rank approximation to a given matrix. Taking an approach different from existing literature, our method first involves a specific biased sampling, with an element being chosen based on the leverage scores of its row and column, and then involves we…