Sketching reduces memory usage for large Bayesian models.
problem Large parameter values in Bayesian models are expensive to store.
method Combines count-min sketch and approximate counters for efficient parameter representation.
result Sketches used during inference converge to exact chain equilibrium.
Bayesian nonparametric CMS improves frequency estimation for power-law data.
problem Estimating frequencies of low-frequency tokens in power-law data streams.
method Developed a learning-augmented count-min sketch using a normalized inverse Gaussian process prior.
result The approach achieves remarkable performance in estimating low-frequency tokens.
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.
MACH reduces memory usage for extreme classification by hashing.
problem Expensive training of deep models with large softmax layers.
method Merged-Average Classifiers via Hashing (MACH) using count-min sketch.
result Significant memory reduction and training speedup.
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…
Enhances CMS with Bayesian nonparametrics for better low-frequency token estimation.
problem Improving frequency estimation of low-frequency tokens in data streams.
method Integrates Bayesian nonparametrics (Pitman-Yor process) into CMS for more accurate frequency estimation.
result CMS-PYP outperforms CMS and CMS-DP in estimating low-frequency tokens.
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.
Two new approaches for point prediction in streaming data, showing consistency and performance.
problem Predicting points in streaming data without a true model.
method Count-Min sketch and Gaussian process priors with random bias.
result CMS-based estimates are consistent under i.i.d. samples assumption.
In this paper, we first demonstrate that b-bit minwise hashing, whose estimators are positive definite kernels, can be naturally integrated with learning algorithms such as SVM and logistic regression. We adopt a simple scheme to transform the nonlinear (resemblance) kernel into linear (inner product) kernel; and hence…
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 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.
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.
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 …
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.
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…
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.
New method reduces linear regret in high-dimensional bandit problems.
problem Heavy spectral tails in streaming matrices lead to linear regret in sketch-based linear bandits.
method Dyadic Block Sketching, a multi-scale matrix sketching approach.
result Achieves sublinear regret bounds without prior knowledge of streaming matrix properties.
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.
Paper proposes GAN architectures for generating vector sketches.
problem Lack of GAN architectures for generating vector sketches.
method Proposes SkeGAN and VASkeGAN architectures for vector sketch generation.
result Validated that proposed architectures generate visually appealing sketches.
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.
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.
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 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.
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.
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.
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.
Sketched SGD reduces communication in distributed SGD by sketching gradients.
problem Limited communication in large-scale distributed training of neural networks.
method Introducing Sketched SGD, an algorithm that communicates sketches of gradients instead of full gradients.
result Sketched SGD reduces communication from O(d) or O(W) to O(logd), achieving up to 40x reduction in total communication cost. 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.
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.
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.
Improved sketching for logistic and ℓ1 regression with near-linear dimensions.
problem Efficiently approximate ℓ1 and logistic regression problems. method New sketching techniques achieving near-linear dimensions for both problems.
result Achieved near-linear sketching dimensions for ℓ1 and logistic regression. 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.
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.
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.
Paper presents a new trie for integer sketches to improve similarity searches.
problem Efficient similarity searches on integer sketches.
method Introduces a novel b-bit sketch trie that leverages succinct data structures. result Significantly improves search time and space-efficiency of similarity searches.
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.
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…
Two bandit algorithms become efficient with sketching.
problem Efficiently processing large-scale linear bandit problems.
method Deterministic online sketching technique (Frequent Directions) to reduce update time.
result Regret bounds matching non-sketched versions when contexts span a subspace of dimension at most m.
We present sketch-rnn, a recurrent neural network (RNN) able to construct stroke-based drawings of common objects. The model is trained on thousands of crude human-drawn images representing hundreds of classes. We outline a framework for conditional and unconditional sketch generation, and describe new robust training …
Generative model improves zero-shot sketch-based image retrieval.
problem Existing SBIR methods struggle with novel classes.
method Generative model learns to generate images conditioned on novel sketches.
result Significantly outperforms baselines on two challenging datasets.
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.
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.
Downsampling can improve generalization in ridgeless linear regression, especially with optimal sketching size.
problem Improving generalization in ridgeless linear regression with limited data.
method Investigating the effects of downsampling on the sketched ridgeless least square estimator in the proportional regime.
result Optimal sketching size minimizes out-of-sample prediction risks and stabilizes risk curves.
Sketch-GNN reduces GNN training time and memory usage to sublinear scales.
problem Training GNNs on large graphs is computationally expensive and memory-intensive.
method Develops a sketch-based algorithm that trains GNNs on compact sketches of graph adjacency and node embeddings.
result Training time and memory usage grow sublinearly with respect to graph size.
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.
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.
This paper speeds up kernel methods using sparsified Gaussian sketches.
problem Kernel methods' computational limitations.
method Sparsified Gaussian sketches for kernel methods.
result Efficient time and space savings for kernel methods.
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.