Non-parametric classification via expand-and-sparsify representation
Sinha, Kaushik
Sinha, Kaushik
An error occurred retrieving the object's statistics
Citations
Altmetric:
Authors
Sinha, Kaushik
Other Names
Location
Time Period
Advisors
Original Date
Digitization Date
Issue Date
2024-12-09
Type
Conference paper
Genre
Keywords
Decisions trees,Random forest,Machine learning
Subjects (LCSH)
Citation
Sinha, K. (2024). Non-parametric classification via expand-and-sparsify representation. Advances in Neural Information Processing Systems 37 (NeurIPS 2024)
Abstract
In expand-and-sparsify (EaS) representation, a data point in Sd-1 is first randomly mapped to higher dimension ℝm, where m > d, followed by a sparsification operation where the informative k ≪ m of the m coordinates are set to one and the rest are set to zero. We propose two algorithms for non-parametric classification using such EaS representation. For our first algorithm, we use winners-take-all operation for the sparsification step and show that the proposed classifier admits the form of a locally weighted average classifier and establish its consistency via Stone's Theorem. Further, assuming that the conditional probability function P(y = 1|x) = η(x) is Hölder continuous and for optimal choice of m, we show that the convergence rate of this classifier is minimax-optimal. For our second algorithm, we use empirical k-thresholding operation for the sparsification step, and under the assumption that data lie on a low dimensional manifold of dimension d0 ≪ d, we show that the convergence rate of this classifier depends only on d0 and is again minimax-optimal. Empirical evaluations performed on real-world datasets corroborate our theoretical results. © 2024 Neural information processing systems foundation. All rights reserved.
Table of Contents
Description
Click on the DOI link to access this article at the publishers website (may not be free).
Publisher
Neural information processing systems foundation
Journal
Book Title
Series
Advances in Neural Information Processing Systems Proceedings - 38th Conference on Neural Information Processing Systems, NeurIPS 2024
9 December 2024 through 15 December 2024
Vancouver
207061
9 December 2024 through 15 December 2024
Vancouver
207061
Digital Collection
Finding Aid URL
Use and Reproduction
Archival Collection
PubMed ID
DOI
ISSN
10495258