Non-parametric classification via expand-and-sparsify representation

In *expand-and-sparsify* (EaS) representation, a data point in \mathcal{S} {d-1} is first randomly mapped to higher dimension \mathbb{R} m, where m d, followed by a sparsification operation where the informative k \ll 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) \eta(x) is H\"{o}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\ll d, we show that the convergence rate of this classifier depends only on d_0 and is again minimax-optimal.