Research map / Learning theory and algorithms / Sample complexity
Non-parametric classification via expand-and-sparsify representation
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 two non-parametric classifiers built on expand-and-sparsify (EaS) random representations, one using k-WTA and one using empirical k-thresholding, and proves consistency and minimax-optimal rates (depending on d for the first and intrinsic d0 for the second).
Problem
Non-parametric binary classification on the unit sphere using the sparse high-dimensional expand-and-sparsify representation, with theoretical guarantees on consistency and convergence rates, including adaptation to low-dimensional manifold structure.
Approach
Treats the k active coordinates of an EaS code as k neighborhoods (response regions) and averages per-region label means into a plug-in estimate of eta(x); the first algorithm uses k-WTA sparsification, and the second uses data-driven per-direction thresholds so the rate depends only on the intrinsic dimension.
Key results
- Theory: Algorithm 1 (k-WTA EaS) with m chosen as kn^{(d-1)/(2β+(d-1))} achieves excess risk O(n^{-β/(2β+d-1)}), matching the minimax rate for Hölder-smooth plug-in classifiers.
- Theory: Algorithm 2 (empirical k-thresholding) achieves O(n^{-β/(2β+d0)}) under manifold assumption, depending only on intrinsic dimension d0.
- Experiments on eight datasets: test accuracy of the EaS classifier increases with expansion factor m/d and becomes comparable to k-NN and random forest at large m.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase expansion dimensionality m (with k set to d log m) | EaS classifier (Algorithm 1) · eight benchmark datasets | test accuracy | Helped |
Surprising findings
- For k-WTA, a lower bound shows that on a one-dimensional manifold embedded in R^d the excess error decays no faster than n^{-1/(d+1)}, so the k-WTA scheme cannot adapt to manifold structure.
Limitations
- Constant in the manifold-adaptive bound may depend exponentially on d and is hidden by big-O notation.
- Projection directions are chosen data-independently; data-dependent directions are left for future work.
- Experiments are limited to eight relatively small datasets, with k set heuristically to d log m.
Experimental setup
Datasets: twomoons mnist (binary 3 vs 5, PCA to 20 dims) fashion-mnist (binary, PCA to 20 dims) six other OpenML binary datasets
Benchmarks: twomoons mnist fashion-mnist six other OpenML binary datasets
Metrics: test accuracy
Baselines: k-nearest neighbors (k=1) k-nearest neighbors (k=10) random forest
Builds on: Dasgupta and Tosh 2020 expand-and-sparsify function approximation Stone's theorem plug-in classification rules (Devroye et al.)
Closest papers by meaning
- On Rate-Optimal Partitioning Classification from Observable and from Privatised Data (NeurIPS 2026 · similarity 0.84)
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.84)
- Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification (NeurIPS 2024 · similarity 0.84)
- Distribution-Specific Agnostic Conditional Classification With Halfspaces (ICLR 2025 · similarity 0.83)
- Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data (ICLR 2024 · similarity 0.83)
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.