New analysis proves sketching operators' RIP guarantees for mixture models without importance sampling.
problem Proving sketching operators' Restricted Isometry Property (RIP) for mixture models without assuming importance sampling.
method Proposed alternative analysis based on new deterministic bounds and concentration inequalities.
result Theoretical guarantees for sketching operators without importance sampling.
A new method improves convergence in low-rank approximation.
problem Efficiently solving large-scale numerical linear algebra problems.
method Error-Powered Sketched Inverse Iteration (EPSI) Method.
result Convergence rate improves at least linearly with sketch size.
A new method for estimating large-scale linear models with improved precision.
problem Estimating large-scale linear statistical models efficiently.
method Sequential Least-Squares Estimators with Fast Randomized Sketching (SLSE-FRS), integrating Sketch-and-Solve and Iterative-Sketching methods.
result SLSE-FRS produces high-precision estimators, outperforming state-of-the-art methods.
New algorithm reduces big data processing time by sketching and random projection.
problem Efficiently processing large and high-dimensional data sets.
method Developed a new algorithm combining sketching and dual random projection, using preconditioned conjugate gradient.
result The algorithm can recover the optimum of the original problem up to arbitrary precision with a logarithmic number of small-scale solver calls.
The paper sharpens the analysis of sketch-and-project methods using randomized singular value decomposition.
problem Improving convergence rates of sketch-and-project methods for solving linear systems and non-linear optimization problems.
method Developing a theoretical framework and new spectral bounds for the expected sketched projection matrix.
result The convergence rate improves linearly with sketch size and even faster with certain spectral decays.
We consider statistical as well as algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. For a LS problem with input data ( X , Y ) ∈ R n × p × R n (X, Y) \in \mathbb{R}^{n \times p} \times \mathbb{R}^n ( X , Y ) ∈ R n × p × R n , sketching algorithms use a sketching matrix, S ∈ R r × n S\in\mathbb{R}^{r \times n} S ∈ R r × n with $r \…
A simple sketch improves online eigenvector and SDP problems.
problem Online eigenvector and semidefinite programming problems.
method Randomized mirror projection and mirror descent analysis.
result Regret bounds similar to MMW with reduced complexity.
A new sketching method reduces tensor memory usage and enables efficient tensor operations.
problem Efficiently compressing and retaining tensor structure in large datasets.
method Higher-order Count Sketch (HCS) using multiple hash functions and tensor products.
result HCS achieves significant memory savings and efficient tensor operations.
We improve prediction risk estimation for large datasets using sketching and ridge regression.
problem Estimating prediction risks for large datasets efficiently and accurately.
method Random matrix theory, generalized cross validation, sketched ridge regression ensembles, and ensemble trick.
result Consistent risk estimation and prediction intervals for large-scale datasets.
Sketch-SC accelerates SC for large volumes of high-dimensional data.
problem High computational complexity in SC for large volumes of high-dimensional data.
method Random sketching for dimensionality reduction.
result Sketch-SC accelerates SC, enabling fast and accurate large-scale SC.
Newton-LESS sparsifies Gaussian sketching for faster optimization.
problem Computing the Hessian matrix in optimization is computationally expensive.
method Uses a sparsified version of a dense Gaussian sketching matrix.
result Achieves nearly the same convergence rate as dense Gaussian embeddings without the computational cost.
Develops precise expressions for random projections for better machine learning tasks.
problem Improving the accuracy of dimensionality reduction in machine learning tasks.
method Exploits recent developments in spectral analysis of random matrices to derive accurate expressions for random projection matrices.
result Provides precise expressions that reflect the practical performance of sketching methods, including Gaussian and Rademacher sketches.
Unified bounds for sketched bilinear forms in machine learning and statistics.
problem Uniform bounds on sketched bilinear forms for modern analyses.
method Generic chaining and new techniques for handling suprema over pairs of sets.
result Improved convergence bounds for sketched Federated Learning and bandit algorithms.
A new method reduces the complexity of tensor products from cubic to quadratic, improving both speed and accuracy.
problem Efficiently computing high-dimensional tensor products for polynomial kernels.
method Complex-to-Real (CtR) modification of sketches using complex random projections.
result Achieves state-of-the-art performance in accuracy and speed.
The paper shows how sketching data can simplify regression inference even when errors are heteroskedastic.
problem Performing robust inference with heteroskedastic errors using sketched data.
method Using random projections to sketch data, the paper shows that sketched estimates behave as if errors are homoskedastic.
result Estimation by random sampling does not have the same property, and sketched estimates are asymptotically normal with homoskedastic variance.
New algorithm converts data into sub-gaussian designs efficiently.
problem Efficiently converting large datasets into sub-gaussian random designs for robust performance.
method Algorithmic Gaussianization through sketching and averaging, using LESS embeddings.
result Efficient data sketches nearly indistinguishable from sub-gaussian designs.
Improved estimator for least squares using random projections achieves smaller error.
problem Improving the accuracy of least squares solutions for large-scale problems.
method James-Stein estimator applied to Gaussian sketching of least squares problems.
result Upper and lower bounds match when SNR is small and data matrix is well-conditioned.
We consider statistical and algorithmic aspects of solving large-scale least-squares (LS) problems using randomized sketching algorithms. Prior results show that, from an \emph{algorithmic perspective}, when using sketching matrices constructed from random projections and leverage-score sampling, if the number of sampl…
Paper proposes Nyström sketches for better adaptive compressive learning.
problem Improving adaptability of sketching for compressive learning.
method Data-dependent Nyström approximation for mean embedding.
result Excess risk can be controlled with geometric assumption.
Matrix sketching balances class sizes for better supervised classification performance.
problem Class imbalance in supervised classification leads to poor performance.
method Matrix sketching using random projections to rebalance class sizes.
result Rebalanced classes improve classification performance, especially for minority classes.
Projector-based approach quantifies uncertainties in sketched linear regression.
problem How sketching affects statistical properties of linear regression solutions.
method Projector-based approach to sketched linear regression that is exact and requires minimal assumptions.
result Derives key quantities from classic linear regression that account for combined uncertainties.
Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given n n n samples, the time and space complexity of computing the KRR estimate scale as O ( n 3 ) \mathcal{O}(n^3) O ( n 3 ) and O ( n 2 ) \mathcal{O}(n^2) O ( n 2 ) respectively, and so is prohibitive in many cases. We prop…
A scalable framework for clustering large graphs using randomized sketching.
problem Clustering large partially observed graphs efficiently.
method Randomized graph sketching, correlation-based retrieval, uniform and degree-based node sampling.
result Improved phase transitions for clustering with reduced computational complexity and minimum cluster size.
Unified methodology for statistical inference in least squares and PCA via randomized sketching.
problem Statistical inference in least squares and PCA problems.
method Randomized sketching and projections, asymptotic normality of quadratic forms.
result Unified statistical inference methods for various sketching distributions.
A fast sketching algorithm solves regularized least squares problems efficiently.
problem Solving large-scale optimization problems with convex or nonconvex regularization.
method Sketching for Regularized Optimization (SRO) algorithm that generates a sketch of the original data matrix and solves the sketched problem.
result General theoretical results for the approximation error between the original and sketched problems, including minimax rates for sparse signal estimation.
DBCL defends collaborative learning by sketching parameters to prevent gradient-based privacy inference attacks.
problem Privacy leaks in collaborative machine learning due to gradient-based attacks.
method Random matrix sketching applied to parameters, followed by re-generation of sketching after each iteration.
result DBCL prevents effective gradient-based privacy inference attacks without significant computational or accuracy costs.
This paper compresses large datasets for efficient machine learning.
problem Efficiently processing large datasets for machine learning.
method Constructing a sketch of the dataset using random features and averaging, then learning from the sketch.
result The approach can perform machine learning tasks without full dataset access, preserving both information and privacy.
Corrects bias in random sampling matrices for improved ML methods.
problem Inversion bias in random sampling matrices hampers ML applications.
method Corrects inversion bias for various random sampling methods.
result Establishes local convergence rates for sub-sampled Newton methods.
A new framework for efficient large-scale learning using sketching of moments.
problem Efficiently learning from large datasets with limited computational resources.
method Compressing the training data into a low-dimensional sketch and solving a nonlinear least squares problem.
result Sufficient sketch sizes to control the generalization error of the procedure.
Improved ridge regression with Frequent Directions for large-scale tasks.
problem Improving performance of ridge regression for large-scale data.
method Combines Frequent Directions with iterative optimization schemes.
result Achieves high accuracy in estimating bias and variance for sketched ridge regression.
Paper develops a bootstrap method for estimating sketched SVD errors.
problem Lack of tools for accurately estimating sketched SVD errors.
method Develops a fully data-driven bootstrap method for numerical error estimation.
result Allows users to adaptively predict extra work needed for desired error tolerance.
The paper analyzes sketching methods for regression, showing SRHT is superior.
problem Improving regression accuracy with sketching methods.
method Randomly projecting data and then performing regression.
result SRHT outperforms Gaussian projections in asymptotic analysis.
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.
Paper presents a new trie for integer sketches to improve similarity searches.
problem Efficient similarity searches on integer sketches.
method Introduces a novel b b b -bit sketch trie that leverages succinct data structures. result Significantly improves search time and space-efficiency of similarity searches.
SRS samples data points based on their proximity to randomly sampled points on the unit sphere.
problem Random sampling does not always preserve data structures and may not adequately sample from less-populated clusters.
method Spatial Random Sampling (SRS) samples points based on their proximity to randomly sampled points on the unit sphere, with sampling probability proportional to surface area.
result SRS provides descriptive and balanced data representations, addressing the need for better data sketches.
Develops accelerated methods for optimization using low-dimensional projected-gradient information.
problem Optimization with low-dimensional projected-gradient information and Nesterov acceleration.
method Randomized-subspace Nesterov accelerated gradient methods for smooth convex and strongly convex optimization.
result Established accelerated oracle-complexity guarantees and unified basis for comparing sketch families.
Adaptive IHS improves sketching for large-scale data.
problem Efficiently modeling large-scale data with iterative Hessian sketch.
method Deterministic A-optimal subsampling for improved IHS.
result A-optimal IHS outperforms existing accelerated IHS methods.
Bayesian method estimates coverage from sketching imperfect data.
problem Estimating coverage probabilities from compressed data.
method Bayesian nonparametric approach using Dirichlet process prior.
result Estimators accurately recover distinct counts and frequencies.
Recursive sketches summarize deep networks, aiding quick analysis and learning.
problem Understanding and analyzing complex deep learning models.
method Developed a recursive sketch mechanism to summarize inputs and outputs of modular deep networks.
result Sketches can identify key components and summarize essential information, even if partially erased.
This paper explores and analyzes two randomized designs for robust Principal Component Analysis (PCA) employing low-dimensional data sketching. In one design, a data sketch is constructed using random column sampling followed by low dimensional embedding, while in the other, sketching is based on random column and row …
Four conditions ensure low-rank projection costs using random matrix tricks.
problem Preserving projection costs in low-rank approximations.
method Four structural conditions using randomized matrix techniques.
result Conditions guarantee cost preservation in rank- k k k projections. 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. Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms based on sketching. We build on the idea of count sketches, but introduce many novel ideas which are un…
Gaussian sketching preserves kernel inner products in low dimensions.
problem Preserving kernel inner products in low-dimensional spaces.
method Gaussian sketching of kernel Gram matrices and random projections in RKHS.
result Sketching yields a random projection operator that preserves weighted RKHS inner products.
New algorithm optimizes positions of CountSketch non-zero entries for better data compression.
problem Optimizing positions of CountSketch non-zero entries for better data compression.
method Learning algorithm that optimizes both values and positions of CountSketch non-zero entries.
result Improves accuracy for low rank approximation and other problems like k-means clustering.
The paper develops methods to estimate frequencies in large discrete data sets with improved coverage and robustness.
problem Estimating frequencies in large, discrete data sets with valid coverage and robustness.
method Conformal inference methods using discrete sketches, marginal coverage for queries, and novel conformal calibration.
result Improved empirical performance compared to existing methods in simulations and real data.
A parallel optimization method for convex functions using Hessian sketching and debiasing.
problem Massively parallel optimization of convex functions with limited communication.
method Newton method with Hessian sketching and debiasing by workers, server averages descent directions.
result Approximation of Newton step with low-complexity adaptive sketching scheme.
Algorithm learns a better sketch matrix for low-rank approximations.
problem Efficiently compute low-rank approximations of large matrices.
method Uses a learned sketch matrix instead of random matrix for optimization.
result Learned sketch matrix reduces approximation loss significantly compared to random matrix.