Non-parametric classification via expand-and-sparsify representation

Abstract

In expand-and-sparsify (EaS) representation, a data point in S d − 1 is first randomly mapped to higher dimension R 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 d 0 ≪ d , we show that the convergence rate of this classifier depends only on d 0 and is again minimax-optimal. Empirical evaluations performed on real-world datasets corroborate our theoretical results.