Research map / Learning theory and algorithms / Sample complexity

MaxSketch: Robust Distinct Counting in Streams via Random Projections

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Private and query-efficient algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MaxSketch, a max-linear sketch of random Gaussian projections, and proves that under a clusterability assumption it estimates the number of distinct latent objects within (1+ε) using Õ(log n/ε²) memory, with experiments on MNIST, CIFAR-10 and merged face datasets.

Problem

Robust distinct counting in streams where repeated observations of the same object are noisy and only approximately similar; prior general-metric methods need Ω(√n) memory.

Approach

A max-linear sketch of random Gaussian projections (max over stream of inner products, averaged over projections) whose expectation is monotone in the number of latent directions under clusterable geometry, so polylogarithmic memory suffices; a monotone readout maps the scalar statistic to a count.

Key results

• On the face-stream experiment, MaxSketch keeps at least 60% accuracy at ±50 across k in 100 to 5100 and near 100% at ±100 and ±150 with a single readout.
• Zhang's algorithm fails to achieve ±150 accuracy on 43 of 51 evaluated values of k on the same face data.
• On MNIST, a model trained at n=50 retains 0.96 exact-count accuracy (1.0 ±1) at n_test=500, while a model trained at n=10 drops to 0.06 exact accuracy at n_test=500.

Surprising findings

• End-to-end CIFAR-10 counting from count supervision alone is markedly worse than frozen pretrained features, with exact accuracy around 0.55 to 0.63.

Limitations

• Guarantees hold only under an explicit (η,ρ)-clusterability assumption that real or end-to-end learned embeddings may violate.
• Exact counting degrades on CIFAR-10 and LFW where clusters are less separated.
• No known lower bound under the clusterability assumption, so optimality of memory is open.

Experimental setup

Datasets: MNIST CIFAR-10 LFW CelebA CMU Multi-PIE

Benchmarks: MNIST count generalization CIFAR-10 count accuracy merged face identity counting

Metrics: exact count accuracy ±1 accuracy ±50/±100/±150 accuracy

Baselines: DeepSets LSTM aggregator Zhang streaming algorithm for robust distinct counting Sup. (Frozen) Sup. (FT) E2E

Builds on: HyperLogLog DeepSets Slepian/Sudakov-Fernique inequalities neural collapse Zhang robust distinct counting

Closest papers by meaning

• CountSketches, Feature Hashing and the Median of Three (ICML 2021 · similarity 0.86)
• Learning-Augmented Frequent Directions (ICLR 2025 · similarity 0.85)
• Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters (NeurIPS 2024 · similarity 0.84)
• Node Similarities under Random Projections: Limits and Pathological Cases (ICLR 2025 · similarity 0.84)
• Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning (NeurIPS 2024 · similarity 0.83)
• Learning to Count without Annotations (CVPR 2024 · similarity 0.83)