We introduce a new sub-linear space sketch---the Weight-Median Sketch---for learning compressed linear classifiers over data streams while supporting the efficient recovery of large-magnitude weights in the model. This enables memory-limited execution of several statistical analyses over streams, including online featu…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Data sketching”
Density sketches summarize data distributions for accurate sampling and estimation.
problem Accurately estimating and sampling from complex data distributions.
method Online algorithm generating additive density sketches.
result Density sketches provide statistically sound estimators and sampling capabilities.
Sketch-BERT learns vector sketches using BERT-like self-supervised learning.
problem Lack of effective vector sketch representation for recognition and retrieval tasks.
method Generalized BERT to sketch domain with novel embedding networks and self-supervised sketch gestalt learning.
result Improved performance on sketch recognition, retrieval, and gestalt tasks.
A new data-oblivious sketch for logistic regression reduces data size while maintaining approximation accuracy.
problem Efficiently solving logistic regression in one pass over a data stream.
method Data-oblivious sketching approach that reduces data size to poly(μdlog n) weighted points.
result Sketching reduces data size significantly and provides approximation guarantees.
Localized sketching improves matrix multiplication and ridge regression complexity.
problem Efficiently approximate matrix multiplication and ridge regression with limited data availability.
method Localized sketching matrices for block diagonal structure, reducing sample complexity.
result Localized sketching achieves sample complexity matching global sketching methods.
Sketching reduces data size for accurate spectral estimation.
problem Estimating spectral density from large simulation datasets.
method Sketching for dimensionality reduction and data compression.
result Sketching provides 90% accurate spectral density estimate with 10% data.
Sketching is a randomized dimensionality-reduction method that aims to preserve relevant information in large-scale datasets. Count sketch is a simple popular sketch which uses a randomized hash function to achieve compression. In this paper, we propose a novel extension known as Higher-order Count Sketch (HCS). While …
Flexible method for estimating frequencies in large datasets using sketching.
problem Estimating frequencies in very large datasets efficiently and accurately.
method Data-adaptive conformal inference method based on a smaller sketch of data.
result Proves validity of frequentist confidence intervals under data exchangeability.
Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessia…
FROSH and DFROSH speed up online sketching hashing for big data.
problem Efficiency and scalability of hashing methods for streaming data.
method Online sketching hashing (OSH) and FasteR Online Sketching Hashing (FROSH) algorithm.
result FROSH reduces training time and maintains sketching precision.
New guarantees for asymmetric sketching in compressive learning.
problem Statistical guarantees for compressive learning with asymmetric feature maps.
method Proves existing guarantees carry over to asymmetric scheme with LPD property, applies to quantized sketches.
result Existing statistical guarantees for compressive learning extend to asymmetric schemes with controlled error.
Recently, randomly mapping vectorial data to strings of discrete symbols (i.e., sketches) for fast and space-efficient similarity searches has become popular. Such random mapping is called similarity-preserving hashing and approximates a similarity metric by using the Hamming distance. Although many efficient similarit…
DiPS learns to optimize sketching policies for better recommendation quality.
problem Optimizing sketching policies for long-term user interest prediction in recommender systems.
method Differentiable policy for sketching that learns from training data.
result DiPS requires up to 50% fewer sketch items to achieve the same recommendation quality.
Private sketches protect linear regression data privacy.
problem Protecting sensitive information in linear regression.
method Release private sketches of datasets, compute approximate solutions.
result Private sketches maintain good approximation guarantees to the original problem.
Sketching accelerates structured prediction methods for large datasets.
problem Scaling surrogate kernel methods for large datasets.
method Sketching approximations applied to input and output feature maps.
result Achieves close-to-optimal rates with reduced sketch size.
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.
Improved sketching for logistic and regression with near-linear dimensions.
problem Efficiently approximate and logistic regression problems.
method New sketching techniques achieving near-linear dimensions for both problems.
result Achieved near-linear sketching dimensions for and logistic regression.
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 , sketching algorithms use a sketching matrix, with $r \…
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designscs.LG
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.
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.
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.
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.
New method for efficient sketching of gradients and Hessians.
problem Memory constraints in training machine learning models.
method A novel framework for scalable gradient and HVP sketching tailored for modern hardware.
result Theoretical guarantees and practical applications in training data attribution and Hessian spectrum analysis.
Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queriesstat.ME
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.
Sketching is more fundamental to human cognition than speech. Deep Neural Networks (DNNs) have achieved the state-of-the-art in speech-related tasks but have not made significant development in generating stroke-based sketches a.k.a sketches in vector format. Though there are Variational Auto Encoders (VAEs) for genera…
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.
New sublinear sketches improve ANN and KDE for massive data streams.
problem Efficiently approximate nearest neighbors and kernel density estimation in large datasets.
method Developed sublinear space and query time algorithms for ANN and A-KDE in streaming and sliding-window models.
result Achieved near-optimal trade-offs between memory size and approximation error for ANN.
Structured high-cardinality data arises in many domains, and poses a major challenge for both modeling and inference. Graphical models are a popular approach to modeling structured data but they are unsuitable for high-cardinality variables. The count-min (CM) sketch is a popular approach to estimating probabilities in…
Sketched Subspace Clusteringstat.ML
The immense amount of daily generated and communicated data presents unique challenges in their processing. Clustering, the grouping of data without the presence of ground-truth labels, is an important tool for drawing inferences from data. Subspace clustering (SC) is a relatively recent method that is able to successf…
Linear regression is a classic method of data analysis. In recent years, sketching -- a method of dimension reduction using random sampling, random projections, or both -- has gained popularity as an effective computational approximation when the number of observations greatly exceeds the number of variables. In this p…
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.
Iterative Hessian sketch (IHS) is an effective sketching method for modeling large-scale data. It was originally proposed by Pilanci and Wainwright (2016; JMLR) based on randomized sketching matrices. However, it is computationally intensive due to the iterative sketch process. In this paper, we analyze the IHS algorit…
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.
Matrix sketching is a recently developed data compression technique. An input matrix A is efficiently approximated with a smaller matrix B, so that B preserves most of the properties of A up to some guaranteed approximation ratio. In so doing numerical operations on big data sets become faster. Sketching algorithms gen…
Bayesian nonparametric estimation of coverage probabilities and distinct counts from sketched datastat.ME
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.
New method speeds up k-means clustering using sketch-and-solve.
problem Efficiently solving k-means clustering for large datasets.
method Sketch-and-solve approach with Peng-Wei semidefinite relaxation.
result Provides high-confidence lower bounds on k-means optimal value.
Recent work has explored transforming data sets into smaller, approximate summaries in order to scale Bayesian inference. We examine a related problem in which the parameters of a Bayesian model are very large and expensive to store in memory, and propose more compact representations of parameter values that can be use…
New sketches for weighted sampling without replacement improve accuracy and efficiency.
problem Efficiently sampling weighted data with high accuracy and minimal redundancy.
method Design of novel composable sketches for WOR sampling, based on CountSketch.
result First to provide WOR sampling for and signed updates.
We study sequential change-point detection procedures based on linear sketches of high-dimensional signal vectors using generalized likelihood ratio (GLR) statistics. The GLR statistics allow for an unknown post-change mean that represents an anomaly or novelty. We consider both fixed and time-varying projections, deri…
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 for , significantly smaller than the approximation error.
Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projectionsmath.OC
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.
Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularizationcs.LG
New technique debiases distributed optimization, improving convergence rate.
problem Bias in local estimates limits effectiveness of distributed second order optimization.
method Surrogate sketching and scaled regularization to eliminate bias.
result The debiased local estimates lead to faster convergence in distributed optimization.
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.
Bayesian data sketching speeds up inference for large functional data.
problem Slow posterior computations in Bayesian varying coefficient models for large data.
method Compress functional response and predictor matrix using random linear transformation.
result Fully model-based Bayesian inference on compressed data.
Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averagingstat.ML
We address the statistical and optimization impacts of the classical sketch and Hessian sketch used to approximately solve the Matrix Ridge Regression (MRR) problem. Prior research has quantified the effects of classical sketch on the strictly simpler least squares regression (LSR) problem. We establish that classical …
We present a mechanism to compute a sketch (succinct summary) of how a complex modular deep network processes its inputs. The sketch summarizes essential information about the inputs and outputs of the network and can be used to quickly identify key components and summary statistics of the inputs. Furthermore, the sket…
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.
One-pass private sketch supports various machine learning tasks.
problem Efficiently supporting multiple machine learning tasks with differential privacy.
method Randomized contingency tables indexed with locality-sensitive hashing, constructed in one pass.
result Competitive error bounds for DP kernel density estimation, faster than existing methods.