Research
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.

169,051 papers · 148 categories

Trend · papers per month

0111 · Jun 201519922001200920182026
15 results for count-sketches

Count-sketches reduce memory usage for deep learning models without sacrificing performance.

problem Memory constraints in deep learning models as they grow larger.
method Maintain a linear sketch to compress auxiliary variables in optimization methods.
result Compressed optimization methods maintain the same performance as full-sized baselines while using significantly less memory.

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.

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.

DiffSketch combines privacy and communication efficiency in distributed learning.

problem Privacy and communication efficiency in distributed machine learning.
method DiffSketch uses Count Sketch for data stream summarization to achieve both privacy and efficiency.
result DiffSketch provides strong differential privacy guarantees and significant communication compression.

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…

2018-06-12abs ↗pdf ↗

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.

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.

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…

2017-11-07abs ↗pdf ↗

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…

2015-06-14abs ↗pdf ↗

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…

2016-02-09abs ↗pdf ↗

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.

The paper introduces DP algorithms using random projections and sign random projections for improved privacy in machine learning.

problem Improving differential privacy in machine learning applications.
method Developed algorithms based on random projections and sign random projections, focusing on individual differential privacy (iDP) and standard differential privacy (DP).
result DP-SignOPORP and iDP-SignRP achieve superior performance in differential privacy, especially for small epsilon values.

Improved CountSketch method reduces variance for estimating vector coordinates.

problem Estimating coordinates of high-dimensional vectors efficiently.
method Revisits CountSketch method, using median of estimates to reduce variance.
result Variance reduced to O(min{v12/s2,v22/s})O(\min\{\|v\|_1^2/s^2,\|v\|_2^2/s\}) for t>1t > 1.

OPORP combines permutation and random projection for efficient data vector compression.

problem Efficiently estimating cosine similarity in embedding-based retrieval applications.
method OPORP uses a permutation followed by a random vector dot product, then aggregates and normalizes the results into bins.
result OPORP improves the estimation of cosine similarity, reducing variance and improving accuracy.