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,695 papers · 148 categories
Trend · papers per month
48 results for “Count Sketch”
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 …
FetchSGD reduces communication in federated learning with sketching.
problem Communication bottlenecks and convergence issues in federated learning.
method FetchSGD uses Count Sketch to compress and merge model updates efficiently.
result FetchSGD achieves high compression rates and good convergence without sparse client participation.
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.
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…
Many popular first-order optimization methods (e.g., Momentum, AdaGrad, Adam) accelerate the convergence rate of deep learning models. However, these algorithms require auxiliary parameters, which cost additional memory proportional to the number of parameters in the model. The problem is becoming more severe as deep l…
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.
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.
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.
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…
Extracting information from electronic health records (EHR) is a challenging task since it requires prior knowledge of the reports and some natural language processing algorithm (NLP). With the growing number of EHR implementations, such knowledge is increasingly challenging to obtain in an efficient manner. We address…
MaxSketch improves distinct counting in high-dimensional, noisy data streams.
problem Estimating distinct elements in high-dimensional, noisy data streams.
method MaxSketch uses random Gaussian projections to estimate distinct counts.
result MaxSketch achieves factor estimation with random projections.
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…
FedSKETCH and FedSKETCHGATE improve privacy and efficiency in federated learning.
problem Communication and privacy challenges in federated learning.
method Compression of local gradients using count sketch to protect privacy and reduce communication.
result Sharp convergence guarantees and experimental validation of the methods.
Communication and privacy are two critical concerns in distributed learning. Many existing works treat these concerns separately. In this work, we argue that a natural connection exists between methods for communication reduction and privacy preservation in the context of distributed machine learning. In particular, we…
Feature selection is an important challenge in machine learning. It plays a crucial role in the explainability of machine-driven decisions that are rapidly permeating throughout modern society. Unfortunately, the explosion in the size and dimensionality of real-world datasets poses a severe challenge to standard featur…
A three-manifold equipped with a Heegaard diagram can be used to set up a Floer homology theory whose differential counts pseudo-holomorphic disks in the -fold symmetric product of the Heegaard surface. This leads to a topological invariant for three-manifolds, Heegaard Floer homology, which is functorial under cobo…
GCWSNet improves neural network training speed and accuracy with power transformation.
problem Training deep neural networks efficiently and accurately.
method Developed GCWS for hashing powered-GMM kernel, enabling power transformation on data.
result GCWSNet often improves classification accuracy and converges faster with one epoch.
Given a matrix and a vector , we consider the regression problem with guarantees: finding a vector such that where $x^*=\arg\min_{x\in \mathbb{R}^d}\|Ax-b\|…
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.
Study federates measurement of demographic disparities from quantile sketches.
problem Misalignment of fairness goals with siloed data collection and privacy regulations.
method Federated auditing of demographic parity through score distributions, using Wasserstein--Frechet variance and quantile summaries.
result Proposes a one-shot, communication-efficient protocol to estimate global disparity and its decomposition.
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.
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.
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…
In these notes, I will sketch a new approach to Khovanov homology of knots and links based on counting the solutions of certain elliptic partial differential equations in four and five dimensions. The equations are formulated on four and five-dimensional manifolds with boundary, with a rather subtle boundary condition …
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.
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.
Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketchingcs.LG
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.
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.
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.
Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Modelsstat.ML
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.
In the last decade, it has been shown that many hard AI tasks, especially in NLP, can be naturally modeled as extreme classification problems leading to improved precision. However, such models are prohibitively expensive to train due to the memory blow-up in the last layer. For example, a reasonable softmax layer for …
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.
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.
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…
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 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.
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.
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…
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…
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 …