Non-parametric classification via expand-and-sparsify representation

Authors: kaushik  sinha
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:51:38

Abstract: 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. Empirical evaluations performed on real-world datasets corroborate our theoretical results.

Main paper: 
 introduction: 
 Given a training set x 1 , . . . , x n of size n and a test point x sampled i.i.d. from a distribution µ over some sample space X ⊂ R d , the basic idea of non-parametric estimation (e.g., density estimation, regression or classification) is to construct a function x → f n (x) = f n (x, x 1 , . . . , x n ) that approximates the true function f (which could be a density/regression/classification function as appropriate) as n → ∞ Tsybakov [2008] . For any x ∈ X , f n (x) typically depends on a small subset of the training set lying within a small neighborhood of (thus close to) x. For example, in case of k-nearest neighbor, f n (x) depends on the k points from the training set that are closest to x; in case of random forest, for each tree constituting the forest, f n (x) depends on the points from the training set that are routed to the same leaf node to which x is also routed to; in case of kernel methods, f n (x) depends on the points from training set defined by an appropriate kernel. In this paper, we propose a new non-parametric classification method where, for any x ∈ S d-1 , the appropriate neighborhoods are obtained using expand-and sparsify (EaS) representation of x.On a high level, expand-and-sparsify representation is essentially a transformation from a lowdimensional dense representation of sensory inputs to a much higher-dimensional, sparse representation. Such representation has been found, for instance, in the olfactory system of the fly (Wilson [2013] ) and mouse (Stettler and Axel [2009] ), the visual system of the cat (Olshausen and Field [2004] ), and the electrosensory system of the electric fish (Chacron et al. [2011] ). For example, in the olfactory system of Drosophila (Turner et al. [2008] , Masse et al. [2009] , Wilson [2013] , Caron et al. [2013] ), the primary sense receptors of the fly are the roughly 2,500 odor receptor neurons (also known as, ORNs), which can be clustered into 50 types, based on their odor responses, leading to a dense, 50-dimensional sensory input vector. In fact, all ORNs of a given type converge on a corresponding glomerulus in the antennal lobe; there are 50 of these in a topographically fixed configuration. This information is then relayed via projection neurons to a collection of roughly 2000 Kenyon cells (KCs) in the mushroom body, with each KC receiving signal from roughly 5-10 glomeruli (Dasgupta and Tosh [2020] . The pattern of connectivity between the glomeruli and Kenyon cells appears random (Chacron et al. [2011] ). The output of the KCs is integrated by a single anterior paired lateral (APL) neuron which then provides negative feedback causing all but the 5% highestfiring KCs to be suppressed (Lin et al. [2014] ). The result is a random sparse high-dimensional representation of the sensory input, that is the basis for subsequent learning. The primary motivation of this paper is to study the benefit of this type of naturally occurring representation in the context of supervised classification.In our setting, the EaS representation is a mapping from the d-dimensional unit sphere S d-1 to {0, 1} m , m ≫ d, where a data point x ∈ S d-1 is first randomly mapped to higher dimension R m using a random projection matrix Θ, and is followed by a sparsification operation, where the informative k ≪ m of the m coordinates of the resulting vector Θx ∈ R m are set to one and the rest of the coordinates are set to zero. Rows of Θ are typically drawn independently from some distribution ν over S d-1 or R d . Let C j , j = 1, . . . , m, be the set of all examples from the input space X ⊂ S d-1 whose j th coordinate in respective EaS representations are set to 1. We call C j the response region of θ j (the j th row of Θ). Note that for any x ∈ X , there are k activated response regions corresponding to the k nonzero bits in the EaS representation of x. These k activated response regions serves as k neighborhoods of x for our proposed non-parametric classifier, where, for any x ∈ X and each activated response region C j , we estimate Pr(y = 1|C j ) -expected value of y when x is restricted to C j -and take their average to be the estimate of Pr(y = 1|x). In a toy example, we visually show the EaS representation and the activated response regions C j of a data point in Fig. 1 . Comparing whether this conditional probability estimate exceeds 1/2, we predict the class label of y. In particular, we present two algorithms using different sparsification schemes and analyze their theoretical properties.• When data lie on a low dimensional manifold having dimension d 0 ≪ d, we present a second algorithm (using empirical k-thresholding sparsification) and prove that its convergence rate is minimax-optimal and depends only on d 0 .The rest of the paper is organized as follows. We discuss related work in 2. We present our first algorithm and its theoretical analysis including consistency and convergence rate in section 3. We present our second algorithm and derive its convergence rate in section 4. We present our empirical results in section 5 and conclude discussing limitations and future work in section 6. 
related work: 
 Non-parametric estimation is an important branch of statistics with a rich history and classical results. Interested readers may refer to Tsybakov [2008] , Györfi et al. [2002] , which provide excellent treatment of this subject. Here we briefly review consistency and convergence rates of well-known non-parametric methods such as, partitioning estimates (histograms), k-nearest neighbors, kernel methods, and random forests. In the non-parametric literature, it is typical to estimate the regression function η(x) = E(y|x) from data, and use the resulting estimate η n (using a sample of size n) to construct plug-in decision function (classification rule). Under mild conditions, such regression estimates and the resulting plug-in classification rules are consistent for histograms, knearest neighbors, and kernel methods Györfi et al. [2002] , Devroye et al. [1996] . Under mild conditions, different variations of random forest methods are also known to be consistent Biau et al. [2008] , Scornet et al. [2015] , Scornet [2016] , Tang et al. [2018] . Under the assumption that the regression function η(x) is Lipschitz continuous, the L 2 error of the regression estimate of histogram convergences at a rate O n -1/(d+2) (Theorem 4.3 Györfi et al. [2002] , the L 2 error of the regression estimate of the kernel method convergence at a rate O n -1/(d+2) (Theorem 5.2 Györfi et al. [2002] ), and the L 2 error of the regression estimate of k-nearest neighbors method convergences at a rate O n -2/(d+2) (Theorem 6.2 Györfi et al. [2002] ). For random forest, Gao and Zhou [2020] established finite-sample rate O(n -1/(8d+2) ) on the convergence of pure random forests for classification, which was be improved to be of O(n -1/(3.87d+2) ) by considering the midpoint splitting mechanism. They introduced another variant of random forests, which follow Breiman's original random forests but with different mechanisms for splitting dimensions and positions, to get a convergence rate O(n -1/(d+2) (ln n) 1/(d+2) ), which reaches the minimax rate, except for a factor (ln n) 1/(d+2) .For EaS representation, when ν is the uniform distribution over S d-1 and the sparsification scheme is a k-winners-take-all (k-WTA) operation that sets the k largest entries of a vector in R m to one the rest to zero, Dasgupta and Tosh [2020] proposed a function approximation scheme using such EaS representation that can approximate any Lipschitz continuous function f : S d-1 → R in the L ∞ norm, where the error decays exponentially slowly with d. Further, they showed when the data lie on a low dimensional submanifold of S d-1 having dimension d 0 ≪ d, using a different sparsification step, termed as k-thresholding, any Lipschiz continuous function defined on this manifold can be approximated in the L ∞ norm, where the error decays exponentially slowly with d 0 . A different EaS representation, where the projection matrix is a sparse binary matrix and the sparsification step is k-WTA, was proposed in Dasgupta et al. [2017] that effectively hash input data points and such hashing has been shown to provide improved performance in accurately solving the similarity search problems compared to the state-of-the-art locality sensitive hashing (LSH) based techniques (Gionis et al. [1999] , Andoni and Indyk [2008] , Datar et al. [2004] ). Such EaS representation has also been used to summarize data in the form of a bloom filter, termed as fly bloom filter (FBF), and has been successfully used in solving the novelty detection problems in Dasgupta et al. [2018] and classification problem in Sinha and Ram [2021] , Ram and Sinha [2021, 2022] .While our work is inspired by the results of Dasgupta and Tosh [2020] , there are key differences. First, we explicitly expand upon and apply the idea of Dasgupta and Tosh [2020] to the supervised binary classification setting, and derive the rate at which the error probability of our proposed classifier converges to that of the Bayes optimal classifier. In comparison, the main motivation of Dasgupta and Tosh [2020] was to prove the existence of a weight vector that results in arbitrarily well function approximation in the unsupervised learning setting using EaS representation. Because of this existential nature of their result, the effect of sample size was neither needed nor considered in their result. Second, the k-thresholding sparsification scheme proposed in Dasgupta and Tosh [2020] for function approximation result assumed that the coordinate-wise thresholds were known.We make no such assumption and explicitly describe how to compute such thresholds from dataresulting in realizable algorithm and derive convergence rate of our proposed classifier that takes care of the uncertainly associated with random natures of these thresholds. Third, while Dasgupta and Tosh [2020] only considers LipSchitz continuous functions, we consider that conditional probability function η(x) = Pr(y = 1|x) to be Hölder continuous (a broader function class), and prove that our proposed classifier achieves minimax-optimal convergence rate -whether such optimal convergence rate was achievable in the proposed setting was, unknown prior to our result.Finally, we note that random Fourier features Rahimi and Recht [2007] are generated using a construction similar to EaS, however the choice of random directions there are chosen using a kernel function that measures a notion of similarity in the input space. EaS representation can also be though of an opposite process of compressed sensing Candes et al. [2006] , Donoho [2006] , where the goal is to recover a sparse vector given random projections to it, while random projection is used to generate a sparse representation in case of EaS.3 Algorithm 1Algorithm 1 Training set D n = {(x i , y i )} n i=1 ⊂ S d-1 × {0, 1}, Projection dimensionality m ∈ N, k ≪ m non-zeros in the EaS representation, random seed R, and inference with test point x ∈ S d-1 . TrainEaSClassifier(D n , m, k, R) Sample Θ with seed R Initialize w[i], ct[i] ← 0, ∀i ∈ [m] for (x, y) ∈ S do eas ← h 1 (x) w[i] ← w[i] + y, ∀i ∈ [m] : eas[i] = 1 ct[i] ← ct[i] + 1, ∀i ∈ [m] : eas[i] = 1 end w[i] ← w[i]/ct[i], ∀i ∈ [m] return Θ, w end InferEaSClassifier(x, Θ, k, w) eas ← h 1 (x) return I[(eas • w)/k ≥ 1 2 ] endIn this section we present our first algorithm and analyze its statistical properties. For the rest of our presentation, we use the following notations. For any positive integer k ∈ N, we use [k] to denote the set {1, . . . , k}. For any vector v, we use the notation v[i] to denote its i th coordinate value. We use S d-1 to denote the d-dimensional unit sphere and B(x, r) to denote a closed ball of radius r centered at x. We use I to denote indicator variable such that for any boolean variable A, I[A] is 1 if A is True, and 0 otherwise. We consider the binary classification setting, where the instance space is X ⊂ S d-1 and the output class label is Y = {0, 1}. Let µ denotes the measure on X and let η : X → [0, 1], defined as η(x) = Pr(y = 1|x), represents the conditional probability distribution. Then, the joint probability distribution on X × Y is completely defined by µ and η. Let {(x i , y i )} n i=1 , be a training set of size n sampled i.i.d.from µ × η. Due to space limitation, proofs of all our results (organized section wise) are deferred to the Appendix.For x ∈ S d-1 , the EaS representation of x, that uses k-WTA sparsification step, is given by the function hEQUATIONwhere Θ is a m × d random projection matrix whose rows θ 1 , . . . , θ m are sampled i.i.d from the uniform distribution over S d-1 and Γ k : R m → {0, 1} m is the k-WTA function converting a vector in R m to one in {0, 1} m by setting the largest k ≪ m elements of Θx to 1 and the rest to zero. For any j ∈ [m], let C j = {x ∈ X : h 1 (x)[j] = 1}. We note that the subsets (response regions) C 1 , . . . , C m does not form a partition since they can be overlapping. We summarize our first algorithm for binary classification using h 1 in Alg. 1. During its learning/training phase, a vector w ∈ [0, 1] m summarizes the average y value over m response regions C j , j ∈ [m] using the training set. In particular, w[j], j ∈ [m] learned during the training phase is precisely given byηj = n i=1 y i I[x i ∈ C j ] n i=1 I[x i ∈ C j ](2) Using (2),for any x ∈ X , we further defineEQUATIONDuring the inference phase, for any test point x, Alg. 1 first computes (w • h 1 (x))/k, which is an average of average y values over k response regions {C j : h 1 (x)[j] = 1}, which can be interpreted as an estimate of the conditional probability η(x) and is precisely the quantity η(x) given in (3). Alg. 1 then makes its prediction based on whether η(x) is greater than or equal to 1/2. We can rewrite this conditional probability estimate as follows.η(x) = w • h 1 (x) k = 1 k j:x∈Cj w[j] = 1 k j:x∈Cj ηj = 1 k j:x∈Cj n i=1 y i I[x i ∈ C j ] n i=1 I[x i ∈ C j ] = n i=1   1 k j:x∈Cj I[x i ∈ C j ] n i=1 I[x i ∈ C j ]   wn,i(x) y i = n i=1 w n,i (x)y i (4)Using viewpoint (4), Alg. 1 can be interpreted as a "plug-in" classifier Devroye et al. [1996] where prediction is based on whether the estimated conditional probability η exceeds 1/2 or not. In particular, classifier in Alg. 1 can be represented as g : X → {0, 1} described asEQUATIONIn comparison, the Bayes optimal classifier g * : X → {0, 1} is defined asEQUATIONIn equation 4, the weights w n,i (x) = w n,i (x, x 1 , . . . , x n ) ∈ R depends on x 1 , . . . , x n . Next we show that for sufficiently large n sum of these weights is 1. Therefore, η is simply a weighted average estimator of η and is a non-parametric classifier Devroye et al. [1996] .Lemma 3.1. For any x ∈ X , suppose n is sufficiently large such that {x i , . . . , x n } ∩ C j ̸ = ∅ for each j satisfying x ∈ C j . Then,n i=1 w n,i (x) = 1.Indeed, we show in Lemma D.7 (in the Appendix), that for any x ∈ X , whenever n → ∞ and m k /n → 0 as n → ∞, |{x 1 , . . . , x n } ∩ C j | → ∞ for all j such that x ∈ C j .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: See section 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
consistency of algorithm 1: 
 In this section we prove that Alg. 1 is universally consistent. We start with the definition of consistent and universally consistent classification rule Devroye et al. [1996] . Let D n = {(x 1 , y 1 ), . . . , ((x n , y n )} be a training set sampled i.i.d. from a certain distribution of (x, y) and let g n : X → {0, 1} be a classification rule learned using D n . Then g n is consistent (or asymptotically Bayes-risk efficient) for a certain distribution of (x, y) if the expected error probabilityEL n = Pr {g n (x, D n ) ̸ = y} → L * as n → ∞, where L * is the Bayes error probability. A sequence of decision rules is called universally consistent, if it is consistent for any distribution of the pair (x, y). It is well known that a general theorem by Stone Stone [1977] (presented below) provides a recipe for establishing universal consistency of any classification rule of the formEQUATIONbased on an estimate η n (x) of the conditional probability η(x), satisfying η n (x) = n i=1 w n,i (x)y i where weights w n,i (x) = w n,i (x, x 1 , . . . , x n ) are non-negative and n i=1 w n,i (x) = 1. Theorem 3.2. [Stone's Theorem (Theorem 6.3 [Devroye et al., 1996] )] Assume that for any distribution of x, the weights satisfy the following three conditions: (i) There is a constant c such that, for every non-negative measurable functionf sat- isfying Ef (x) < ∞, E ( n i=1 w n,i (x)f (x i )) ≤ cEf (x). (ii) For all a > 0, lim n→∞ E n i=1 w i,n (x)I {∥xi-x∥>a} = 0. (iii) lim n→∞ E (max 1≤i≤n w n,i (x)) = 0.Then g n is universally consistent.Since we have already established in the previous section that the classification rule given in Alg. 1 admits the form given in (5), in conjunction with (4) and Lemma 3.1, we are ready to use Theorem 3.2 to establish universal consistency of Alg. 1. We state our consistency result below. Theorem 3.3. Let (k n ) and (m n ) be increasing functions of n and let (δ n ) be a decreasing function of n satisfying lim n→∞ δ n = 0. Then the classification rule using EaS representation (1) given in Alg. 1 that admits the form given in (5) is universally consistent whenever the following conditions hold:(i) kn mn → 0 as n → ∞, (ii) log(1/δn) mn → 0 as n → ∞ and, (iii)m kn n n → 0 as n → ∞.Once m and k are fixed, for any x ∈ X , there are m k possible subsets of k indices, from the m possible indices in the EaS representation, that h 1 (x) can set to 1. For i ∈ {1, . . . , m k }, let σ(i) represents the set of k indices in the i th subset and we let C k i = {x ∈ X : h 1 (x)[j] = 1, ∀j ∈ σ(i)} to denote the set of instances whose EaS representation precisely sets the indices in σ(i) to 1 and the rest to zero. The following two results are crucial in proving our consistency results above, as well as in deriving convergence rate in the next section. Lemma 3.4. For any positive integers m, k, where k < m, the following relations hold.i) For any i ∈ {1, . . . , m k }, C k i = ∩ j∈σ(i) C j . ii) {C k i } ( m k ) i=1 forms a partition of X . iii) For any j ∈ [m], C j = ∪ i:j∈σ(i) C k i . iv) For any j ∈ [m], µ(C j ) = i:j∈σ(i) µ(C k i). Lemma 3.5. Let d ≥ 3 and pick any 0 < δ < 1. There is an absolute constant c 0 > 0 such that the following holds. With probability at least 1 -δ,max j∈[m] diam(C j ) ≤ 8 k + c 0 (d log m + log(1/δ) m 1 d-1 . In particular, if k ≥ c 0 (d log m + log(1/δ)) then, max j∈[m] diam(C j ) ≤ 8 2k m 1 d-1 .While the consistency result established in the previous section provides the behavior of Alg. 1 in the large sample limit, it does not provide the rate at which the excess Bayes risk converges to zero. In this section we establish such finite sample convergence rate. From the plug-in classifier view point of Alg. 1 given in (5) and the definition of Bayes optimal classifier in (6), it is easy to see that how well the prediction of Algorithm 1 relates to the prediction of the Bayes optimal classifier will depend on how well η(x) approximates η(x).Recall that for any x ∈ X , point-wise error probability or risk of the Bayes optimal classifier is defined as L * (x) = Pr(g * (x) ̸ = y|x) = min{η(x), 1 -η(x)} [Devroye et al., 1996] . Taking expectation over x, risk of the Bayes optimal classifier is L * = E (min{η(x), 1 -η(x)}). Now, for any plug-in classification rule g n (x) defined in (7) that uses a conditional probability estimate η n using training data D n , the excess Bayes risk is given by the following well known result (Corollary 6.1 of Devroye et al. [1996] . Lemma 3.6 ( [Devroye et al., 1996] ). The error probability of a classifier g n (x) defined in (7) satisfies the inequality:Pr (g n (x) ̸ = y|D n ) -L * ≤ 2E x |η(x) -η n (x)| D n .Taking expectation over D n , the above lemma immediately translates toPr(g n (x) ̸ = y) -L * ≤ 2E x,Dn (|η(x) -η n (x)|) (8)Therefore, in order to establish convergence rate of Alg. 1, following Lemma 3.6 and (8), we need to bound expected value of |η(x) -η(x)|. Towards this end, we first extend η defined over points x ∈ X to over measurable sets A ⊂ X with µ(A) > 0 as follows:η(A) = 1 µ(A) A η(x)µ(dx)= 1 µ(A) A Pr(y=1|x)µ(dx)=Pr(y=1|x ∈ A)=E(y|x ∈ A) (9)Thus, η(A) is the probability that y = 1 for a point x chosen at random from the distribution µ restricted to the set A, or in other words, it is the expected value of y when x is restricted to the set A.With this definition, we introduce an intermediate quantityη(x) = 1 k j:x∈Cj ηj (10)where, ηj is defined as,EQUATIONUsing triangle inequality, this allows us to write:E x,Dn |η(x) -η(x)| = E x,Dn |η(x) -η(x) + η(x) - η(X)| ≤ E x,Dn |η(x) -η(x)| + E x,Dn |η(x) -η(x)|, and we show how to individually bound each term on the right-hand side of this inequality next. Remark 3.7. Note that, once m and k are fixed, our hypothesis space is the set of all linear models on the k-sparse m dimensional binary vectors. The two terms on the right-hand side of the above inequality correspond to estimation error (the error of our proposed classifier with respect to the best hypothesis from the hypothesis space) and approximation error (the error difference between the best hypothesis from the hypothesis space and the target classifier, i.e., Bayes optimal), respectively.3.3 Bounding E x,Dn |η(x) -η(x)|Note that there is an inherent randomness in our proposed algorithm associated with the choice of Θ.In particular, the response regions C j are random quantities that depend on the choice of Θ. In this section, we fix Θ and conditioned on this, we bound E x,Dn |η(x) -η(x)|. This ensures that for any δ > 0, the same bound holds with probability at least 1 -δ over the choice of Θ. Lemma 3.8. Fix any Θ. Then we have,E x,Dn |η(x) -η(x)| ≤ m kn .Sketch of proof: From the definition of η(x) and η(x) given in ( 3) and ( 10) and applying Jensen's inequality, crux of the proof is to focus on the expected value of the random quantity1 k j:x∈Cj n i=1 yiI[xi∈Cj ] n i=1 I[xi∈Cj ] -η(C j ) 2 . Note that, for j ∈ [m], n i=1 I[x i ∈ C j ] = nµ n (C j )is the number of the points from D n that fall in C j , where µ n (C j ) is the empirical probability estimate. We bound the quantity of interest in Lemma 3.8 as a sum of two quantities corresponding to the following two cases:Case 1: when µ n (C j ) = 0. Using the notation 0/0 = 0, the quantity of interest becomes . Finally, using standard Binomial bound (Lemma E.4) we show that expected value (w.r.t. x 1 , . . . , x n ) of this quantity is at most m 2kn .1 k j:x∈Cj η 2 (C j )I[µ n (C j ) = 0] .E x,Dn |η(X) -η(x)|In order to bound the expected value of |η(x)-η(x)|, we need to impose certain smoothness condition on η. We consider a general form of smoothness, known as Hölder continuty for η. Definition 3.9. We say that η :X → [0, 1] is (L, β) smooth if for all x, x ′ ∈ X , we have |η(x) - η(x ′ )| ≤ L∥x -x ′ ∥ β .Using Hölder continuity assumption above, we first show the following:Lemma 3.10. Suppose η is (L, β) smooth. Then, sup x∈S |η(x)-η(x)| ≤ L•max j∈[m] (diam(C j )) β .We have already shown in Lemma 3.5 how to bound the diameters of C j . Combining these two results we have Lemma 3.11. Let d ≥ 3 and pick any 0 < δ < 1. Assume η to be (L, β) smooth. There is an absolute constant c 0 > 0 such that the following holds.If k ≥ c 0 (d log m + log(1/δ)) then with probability at least 1 -δ, E x,Dn |η(x) -η(x)| ≤ 8L (2k/m) β d-1 .Combining Lemma 3.8, 3.11 and 3.6 we are present the main result of this section. Theorem 3.12. Let D n = {(x i , y i )} n i=1 ⊂ X × {0, 1} be the training data and consider the EaS representation given in (1). Let d ≥ 3 and pick any 0 < δ < 1. Assume η to be (L, β) smooth. There is an absolute constant c 0 > 0 such that the following holds. If k ≥ c 0 (d log m + log(1/δ)) then with probability at least 1 -δ over the random choice of Θ,Pr(g(x) ̸ = y) -L * ≤ 2 m kn + 8L 2k m β d-1Corollary 3.13. In Theorem 3.12, set m = kn(d-1)2β+ (d-1) . Then, with probability at least 1 -δ, over the choice of Θ, Pr(g(x)̸ = y) -L * = O n -β 2β+(d-1).Remark 3.14. Since X ⊂ S d-1 , the effective dimension in our setting is d ′ = (d -1) and the convergence rate of Corollary 3.13 can be rewritten as O n-β 2β+d ′which is minimax-optimal for plug-in classifiers under the assumption that η is (L, β)-smooth [Audibert and Tsybakov, 2007] .In Theorem 3.12, we derived the convergence rate of the classifier presented in Alg. 1 by bounding E x,Dn |η(x) -η(x)|, which upper bounds the excess Bayes risk, from above and the resulting convergence rate decays exponentially slowly with the dimension d. We now show that even if the data lie on a low dimensional manifold having dimesnion d 0 ≪ d, there exists a smooth η such that the quantity E x,Dn |η(x) -η(x)| decreases at a rate no faster than n -1 d+1 . To prove claim, we assume data to lie on the following one-dimensional manifold:EQUATIONWe further assume that k = β = 1 which implies that η is L-Lipschitz from the definition of (L, β)-smoothness. Our lower bound result is as follows.Theorem 3.15. For any d > 3, let input space X 1 be the one-dimensional sub-manifold of R d given in (12). Take k = 1 and β = 1. Suppose the random matrix Θ has rows chosen from a distribution that is uniform over S d-1 . Then there exists a 1 2 -Lipschitz function η : X 1 → [0, 1] such that the following holds with probability at least 1/2 over the choice of Θ.E x,Dn |η(x) -η(x)| = Ω n -1 d+1 4 Algorithm 2In this section we present an alternate EaS representation and an associated classification algorithm that adapts to intrinsic dimension d 0 when data lie on a low dimensional manifold with dimension d 0 ≪ d. Here, we assume that the rowsθ i , i ∈ [m] of matrix Θ are sampled i.i.d. from a multivariate Gaussian distribution N (0, 1/ √ dI d ),denote by ν, where I d is d × d identity matrix. This EaS representation is denoted by h 2 : X → {0, 1} m , where for any point x ∈ X , the j th coordinate of h 2 (x) is set to 1, as given in ( 14), using a data dependent threshold τ n . In particular, given a training set of size 1 2n sampled i.i.d.from (µ, η), using the first half of it, namely,EQUATION)1 Instead of representing the training set to be D2n = {(xi, yi)} 2n i=1 , for notational convenience, we represent its first half asD ′ n = {(x ′ i , y ′ i } n i=1and the second half as Dn = {(xi, yi)} n i=1 . D ′ n is only used to compute empirical thresholds in ( 13) and therefore, we could use unlabeled data sampled i.i.d.from µ for this purpose.h 2 (x)[j] = I[θ j • x ≥ τ n (θ j )] (14)We call the sparsification scheme given in ( 14)empirical-k-thresholding. For j ∈ [m], the j th response region C j is defined as:C j = C(θ j ) = {x ∈ X : θ j • x ≥ τ n (θ j )} (15)Using the second half of the training data, namely D n = {(x 1 , y 1 ), . . . , (x n , y n )}, average y values over different C j are estimated and summarized in vector w in the same way as in Alg. 1 implying that w[j] = ηj , ∀j ∈ [m],where ηj is given in (2). This completes the training phase of our proposed algorithm summarized in Alg. 2.Algorithm 2 Training set D ′ n = {(x ′ i , y ′ i )} n i=1 , D n = {(x i , y i )} n i=1 ⊂ X × {0, 1}, Projection dimensionality m ∈ N, integer k ≪ m, integer t, random seed R, and inference with test point x ∈ S d-1 . TrainEaSClassifier(D n , D ′ n m, k, t, R) Sample Θ with seed R Initialize w[i], ct[i] ← 0, ∀i ∈ [m] for j ∈ [m] doCompute τ n (θ j ) using ( 13) andD ′ n end for (x, y) ∈ D n do eas ← h 2 (x) w[i] ← w[i] + y, ∀i ∈ [m] : eas[i] = 1 ct[i] ← ct[i]+1, , ∀i ∈ [m] : eas[i] = 1 end w[i] ← w[i]/ct[i], ∀i ∈ [m] return Θ, w end InferEaSClassifier(x, Θ, t, w) eas ← h n 2 (x) Θ x ← {θ i : h 2 (x)[i] = 1} ẽ as ← eas ẽ as[i] ← 0, ∀i ∈ [m] : i / ∈ A t (x) return I[( ẽ as • w)/t ≥ 1 2 ] endThe inference phase of Alg. 2 is slightly different from Alg. 1. While EaS representation using h 2 is not k-sparse anymore, we show that for large enough sample size, with high probability, it is at least k/2-sparse and at most 2k-sparse in expectation (see Lemma F.1 in Appendix F). Let t be an integer passed as an argument to Alg. 2. For any x ∈ X , let Θ(x) = {θ j : x ∈ C j } and we define A t (x) to be the set containing the indices j ∈ [m], such that θ j is one of the t closest points to x from Θ(x). To make an inference for any x ∈ X , Alg. 2 first computes ( ẽ as • w)/t and makes it prediction based on whether this quantity is greater than 1/2. Clearly, ( ẽ as • w)/t is the average of w[j] for j ∈ A t (x) and therefore, the conditional probability estimate η(x) of Alg. 2 can be represented as,EQUATIONRemark 4.1. Note that h 1 and h 2 are different in a specific way. When the support of data does not cover the whole unit sphere and is concentrated possibly in a small region and m is large, many of the m coordinates in EaS representation will never be activated (set to 1) for any data point as the corresponding projection direction θ j may not be one of the k closest ones to any data point. Thus, many of the θ j will be unused. This problem is avoided in h 2 , where every θ j is used but the respective response region C j may not be local to the manifold. For this purpose we need to identify "good" projection directions. Later in Lemma B.4 we show that, for any δ > 0, with probability at least 1 -2δ over the choice of Θ and D ′ n , the number of "good" projection directions t is linear in k.Due to space limitation, manifold assumptions and other important details of analysis of Alg. 2 are presented in Appendix B and we present the main theoretical results below. Theorem 4.2.Let D n = {(x i , y i )} n i=1 ∪ D ′ n = {(x ′ i , y ′ i )} n i=1 ⊂ X × {0, 1} be the training data where the data lies on a low dimensional manifold satisfying manifold assumption presented in section B.1 and suppose the EaS representation is given as in (14). Pick any0 < δ < 1. Assume η to be (L, β) smooth. If k ≥ c ′ d ln(m/δ), where c ′ d is a constant that depend on d, then with probability at least 1 -2δ, Pr(g(x) ̸ = y) -L * ≤ 2 2m α d kn + 4L 2k c 1 m β d 0where α d is a constant that depends on d.Corollary 4.3. In Theorem 4.2, setting m = kn d 0 2β+d 0 ensure that with probability at least 1 -δ,Pr(g(x) ̸ = y) -L * = O n -β 2β+d 0.Remark 4.4. The convergence rate of Corollary 4.3 depends only on d 0 and is minimax-optimal for plug-in classifiers under the assumption that η is (L, β)-smooth [Audibert and Tsybakov, 2007] . Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
empirical evaluations: 
 We investigate the effectiveness of our proposed method by evaluating it on eight benchmark datasets, details of which are provided in appendix A. We address the following questions:1. Does performance our proposed classifier improve with increasing m as suggested by the theory? 2. How does our proposed classifier perform compared to other non-parametric classifiers?For each dataset, we generate train and test set using scikit-learn's train_test_split method (80 : 20 split). We compare our proposed method against two non-parametric classifiersscikit-learn's implementation of k-nearest neighbor classifier (k-NN) and random forest (RF).For k-NN, we used two values of k: k = 1 and 10. For RF we use a grid search over the number of estimators (trees) from the set {250, 500, 750, 1000} and perform a 3 fold cross validation to choose the final model. We preset our experimental results in Fig. 2 where we plot test accuracy of Alg. 1, k-NN (for k = 1 and 10) and RF by varying expansion factor, where we define expansion factor to be m/d. As per Theorem 3.12, we set k to be d log m. As can be seen from Fig. 2 , with increasing m test accuracy of Alg. 1 increases in all eight datasets and becomes comparable to that of k-NN and RF for large m, thus corroborating our theoretical findings.6 Conclusions, limitations and future workIn this paper, we present an interesting connection between non-parametric estimation and expansionand-sparsify representation. We presented two non-parametric classification algorithms using EaS representation and proved that both algorithms yield minimax-optimal convergence rates. The convergence rate of the first algorithm depends on the ambient dimension d, while the convergence rate of the second algorithm, under manifold assumption, depends only on the intrinsic dimension d 0 ≪ d. In both algorithms, the projection directions are chosen in a data-independent manner. One limitation of our current work is that, even though the second algorithm adapts to the manifold structure, there is a large constant, possibly depending exponentially on d, involved in bounding the excess Bayes risk, that is hidden under the Big Oh notation. In the future, we plan to investigate various data-dependent projection direction choices for a sparse representation, that would adapt to a manifold structure, and the constant involved in bounding of the excess Bayes risk from above, would be independent of ambient dimension d. 1 . Among the eight datasets, the twomoons is a synthetic dataset generated using make_moons method from sklearn.dataset2 with noise parameter 0.2. All the remaining datasets are taken from the OpenML repository 3 Vanschoren et al. [2013]. Both mnist and fmnist (fashion-mnist for short) are 10 class classification problem with 784 features. We convert them to binary classification problems by using the label 3 and 5 for the mnist dataset and label 2 (Pullover) and 4 (Coat)for fmnist dataset. For efficiency purpose, the feature dimensions for both these datasets are reduced to 20 using principal component analysis (PCA). For the remaining six datasets, the task is that of binary classification. For all eight datasets, the features are normalized using StandardScaler option in scikit-learn and are made to be unit norm.We run our experiments on a laptop with Intel Xeon W-10855M Processor, 64GB memory and NVDIA Quadro RTX 5000 Mobile GPU (with 16GB memory).In this section we present missing details of convergence rate analysis of Algorithm 2 from section 4. Proofs of various technical results presented in this section as well as the proof of Theorem 4.2 are deferred to section B.To analyze convergence rate of Algorithm 2, we proceed in the same was as in section 3.2. However, to take advantage of the fact that data lie on a low-dimensional manifold in our analysis, we make similar manifold assumptions as in Dasgupta and Tosh [2020] . The input space X is a compact d 0 -dimensional Riemannian sub manifold M of R d contained in the unit sphere, that is M ⊂ S d-1 . M has nice boundaries and that the distribution on it µ, is almost uniform: formally, there exists constants c 1 , c 2 , c 3 > 0 such that for all x ∈ M and for all r ≤ r 0 (where r 0 is an absolute constant)c 1 r d0 ≤ µ(B M (x, r) < c 2 r d0 (17) Vol(B M (x, r)) ≥ c 3 r d0 (18) Here B M (x, r) = B(x, r) ∩ M .To effectively analyze the data distribution supported on a manifold, we impose conditions on the curvature by adopting the common requirement that M has a positive reach ρ > 0: that is, every point in an open tubular neighborhood of M of of radius ρ has a unique nearest neighbor in M [Niyogi et al., 2008] . For each x ∈ M , let N (x) denotes the (d -d 0 ) dimensional subspace of normal vectors to the tangent plane at x. For each x ∈ M , the sets Γ ρ (x) = {x + ru ∈ R d : u ∈ N (x), ∥u∥ = 1, 0 < r < ρ} are disjoint and let τ ρ be their union. Let π M : τ ρ → M be the projection map that sends any point in τ ρ (x) to x, its nearest neighbor in M .E x,Dn |η(x) -η(x)|The response regions C j , j ∈ [m] are now random quantities that depend on the choice of Θ as well as D ′ n used to compute individual thresholds. The quantity η(x) given in ( 16) depends on t. In this section, we fix Θ and t and conditioned on this, we bound E x,Dn,D ′ n |η(x) -η(x)|. Later in Lemma B.4 we show that, for any δ > 0, with probability at least 1 -2δ over the choice of Θ and D ′ n , t is linear in k. Lemma B.1. Fix any Θ and t. Then the following holds.E x,Dn,D ′ n |η(x) -η(x)| ≤ m tn .The proof strategy is similar to Lemma 3.8, but requires careful analysis to accommodate the facts that C j , j ∈ [m] depend on the choice of D ′ n and η in ( 16) has an indicator function. Details are provided in Appendix B.B.3 Bounding E x,Dn |η(x) -η(x)|Using identical proof strategy of Lemma 3.10, we have,Lemma B.2. Under empirical k-thresholding scheme, if η is (L, β) smooth, then for all x ∈ C 1 ∪ • • • , ∪C m , |η(x) -η(x)| ≤ L max j∈[m] (diam(C j )) βUnfortunately, unlike before, all C j such that x ∈ C j may not be local to x and thus average y values in some of these C j , may be very different from η(x). To address this, we call a θ ∈ R d good if it lies in Γ ρ/2 . Good θ j 's are close to the manifold M and are guaranteed to be activated by a single neighborhood of M . Thus, for large enough m, if the diameters of the C j 's corresponding to good θ j 's are made reasonable small then the average y values in such C j 's will be a reasonably close of η(x) for x ∈ C j . First, for any good θ j , we bound the diameter of C j emphasizing that the response region of a good θ j is local.Lemma B.3. Pick any good θ ∈ R d . Define ∆ = ∥θ -π M (θ)∥ to be the distance from θ to its projection on M . Let C(θ) be the response region associated with θ as defined in (15). Pick any 0 < δ < 1. Then with probability at least 1 -δ, over the choice of D ′ n , the following holds:B M π M (θ), ρ -∆ ρ + ∆ k 2c 2 m 1/d0 ⊂ C(θ) ⊂ B π M (θ), ρ + ∆ ρ -∆ 2k c 1 m 1/d0In particular this implies, diam(C(θ))≤ 4 2k c1m 1/d0, provided (2k/(c 1 m)) 1/d0 < min(ρ, r 0 ) andn satisfies n ≥ c0m k log n + log m δ, where c 0 > 0 is a universal constant.Next we show that each x ∈ M has number of good θ j linear in k with high probability. Combining everything leads to the main result presented in Theorem 4.2.C Various proofs from section 3C.1 Proof of Lemma 3.1Proof. Simply interchange the summation. That is,n i=1 w i,n (x) = n i=1   1 k j:x∈Cj I[x i ∈ C j ] n i=1 I[x i ∈ C j ]   = 1 k j:x∈Cj n i=1 I[x i ∈ C j ] n i=1 I[x i ∈ C j ] = 1D Various proofs from section 3.1In this section we present various technical results that are needed to prove our main theorem (Theorem 3.3). Due to space limitation proofs of some of these technical results are deferred to the supplementary material.D.1 Proof of Lemma 3.4Proof. For part (i), note that if x ∈ C k i , then by definition, ∀j ∈ σ(i), h Θ,k (x)[j] = 1 which implies x ∈ C j . Therefore, C k i ⊆ ∩ j∈σ(i) C j . On the other hand, if x ∈ ∩ j∈σ(i) C j then h Θ,k (x)[j] = 1 ∀j ∈ σ(i), which implies x ∈ C k i . Therefore, ∩ j∈σ(i) C j ⊆ C k i . For part (ii), take any i, j ∈ [ m k ], i ̸ = j, then σ(i) ̸ = σ(j). Therefore, if x ∈ C k i then x / ∈ C k j . Since x was arbitrary, C k i ∩ C k j = ∅. Now, for any x ∈ X , since h Θ,k (x) has exactly k bits activated (set to 1), there must exist l ∈ [ m k ] such that x ∈ C k l . Therefore, ∪ ( m k ) i=1 C k i = X .For part (iii), take any x ∈ C j . From the definition of C j , h Θ,k (x)[j] = 1 and therefore, x ∈ C k i for any i such that j ∈ σ(i). From part(ii) since such C k i s are disjoint and x was arbitrary, the result follows.Finally, part (iv) follows immediately from part (ii) and (iii) since C k i s are disjoint.D.2 proof of Lemma 3.5Proof. While general idea of this result appeared in Dasgupta and Tosh [2020] , we provide a simplified proof. Let ν(r) = inf x∈X ν(B(x, r)). We first claim that if ν(r) r) . By definition, every ball of radius r, centered at some x ∈ X , has ν-mass at least ν(r). Thus, by Lemma D.1, with probability at least 1 -δ, every x ∈ X will have its nearest k θ j 's within a distance r. Therefore, the j th bit of the EaS representation given in (1) will be activated by points x within distance r of θ j . Therefore, diam(C j ) ≤ 2r for all j = 1, . . . , m, where r satisfies≥ 2 m k + c 0 d log m + log 1 δ then for every j ∈ [m], C j ⊂ B(θ j ,ν(B(x, r)) ≥ 2 k + c 0 d log m + log 1 δ mBy Lemma D.2, we can take r to be the valuer = 3 √ d (3/4) (d-1)/2 • 2 k + c 0 d log m + log 1 δ m 1/(d-1) = 2 √ 3 6 √ d k + c 0 d log m + log 1 δ m 1/(d-1).Therefore, we havediam(C j ) ≤ 2r ≤ 4 √ 3 6 √ d k + c 0 d log m + log 1 δ m 1/(d-1) ≤ 8 k + c 0 d log m + log 1 δ m 1/(d-1)where, for the last inequality, we have used the fact that d 1/(2(d-1)) ≤ √ 2 and for d ≥ 3 it holds that 6 1/(d-1) ≤ √ 6.Lemma D.1 ( [Chaudhuri and Dasgupta, 2010] ). There is an absolute constant c 0 > 0 for which the following holds. Pick any 0 < δ < 1. Pick θ 1 , . . . , θ m independently at random from a distribution µ on R d . Then with probability at least 1 -δ, any ball [Dasgupta and Tosh, 2020] ). Suppose d ≥ 3, r ∈ (0, 1), and ν is the uniform distribution over S d-1 . Then for any x ∈ S d-1 ,B in R d with ν(B) ≥ 2 m k + c 0 d log m + log 1 δ contains at least k of the θ i . Lemma D.2 (Lemma 12ν(B(x, r)) ≥ 1 3 √ d r d-1 1 -r 2 /4 (d-1)/2 ≥ 1 3 √ d (3/4) (d-1)/2 r d-1 .Proof. Since the weights w n,i given in equation 4 are non-negative, in order to satisfy condition (i) of Stone's theorem, we need to show that there exists a positive constant c such that for any non-negative measurable function f satisfying Ef (x) < ∞ and for any n, E (n i=1 w n,i (x)f (x i )) ≤ cE(f (x)). Using Lemma D.3, we show that this condition is satisfied for c = 1.n = a n (k n , m n , δ n ) = 8 kn+c0(d log mn+log( 1 δn )) mn 1/(d-1), where c 0 is an absolute constant. Then lim n→∞ δ n = 0 and using condition (i) and (ii) of this theorem we also have lim n→∞ a n = 0. Now pick any a > 0. We can always find a positive integer N such that for n > N, we have a > a n satisfying n i=1 w i,n (x)I {∥xi-x∥>a} ≤ n i=1 w i,n (x)I {∥xi-x∥>an} for all x ∈ X . Replacing k, m, δ and a with k n , δ n and a n respectively in Lemma D.6, we haveEQUATIONwhere, for i = 1, . . . , k, we have used the notation j i (x, Θ) to denote the k random coordinates of h Θ,k (x) that are set to 1 and N ji(x,Θ) to denote the number of points from x 1 , . . . , x n that fall in C ji(x,Θ) . Now from equation 19, is it easy to see that lim n→∞ E (max 1≤i≤n w n,i (x)) = 0 since using lemma D.7, min 1≤i≤k {N ji(x,Θ) } → ∞ in probability, as n → ∞.D.4 Technical results for satisfying condition (i) of Stone's theorem (Theorem 3.2) Lemma D.3. For any non-negative measurable function f : X → R + satisfying Ef (x) < ∞ and for any n, E (n i=1 w n,i (x)f (x 1 )) ≤ E(f (x)), where the weights w n,i are as given in (4).Proof.E n i=1 w i,n (x)f (x i ) = E   n i=1   1 k j:x∈Cj I[x i ∈ C j ]f (x i ) n l=1 I[x l ∈ C j ]     = E   1 k j:x∈Cj n i=1 I[x i ∈ C j ]f (x i ) n l=1 I[x l ∈ C j ]   = E x   1 k E   j:x∈Cj n i=1 I[x i ∈ C j ]f (x i ) n l=1 I[x l ∈ C j ] x     = E x   1 k   j:x∈Cj E n i=1 I[x i ∈ C j ]f (x i ) n l=1 I[x l ∈ C j ] x     a ≤ E x   1 k   j:x∈Cj 1 µ(C j ) Cj f (x 1 )µ(dx 1 )     = ( m k ) i=1   Pr(x ∈ C k i )   1 k j∈σ(i) 1 µ(C j ) Cj f (x 1 )µ(dx 1 )     = ( m k ) i=1 1 k   j∈σ(i) Pr(x ∈ C k i ) µ(C j ) Cj f (x 1 )µ(dx 1 )   = 1 k ( m k ) i=1 j∈σ(i) µ(C k i ) µ(C j ) Cj f (x 1 )µ(dx 1 ) b = 1 k m j=1 i:j∈σ(i) µ(C k i ) µ(C j ) Cj f (x 1 )µ(dx 1 ) c = 1 k m j=1 Cj f (x 1 )µ(dx 1 ) d = 1 k m j=1 i:j∈σ(i) C k i f (x 1 )µ(dx 1 ) e = 1 k ( m k ) i j∈σ(i) C k i f (x 1 )µ(dx 1 ) = 1 k ( m k ) i k C k i f (x 1 )µ(dx 1 ) = ( m k ) i C k i f (x 1 )µ(dx 1 ) f = § f (x 1 )µ(dx 1 ) = E(f (x 1 )) g = E(f (x))where, inequality a follows from Lemma D. I[xi∈Cj ]f (xi) n l=1 I[x l ∈Cj ] x ≤ 1 µ(Cj ) Cj f (x 1 )µ(dx 1 ).Proof.E n i=1 I[x i ∈ C j ]f (x i ) n l=1 I[x l ∈ C j ] x = n i=1 E I[x i ∈ C j ]f (x i ) n l=1 I[x l ∈ C j ] x a = n i=1 E I[x i ∈ C j ]f (x i ) 1 + l̸ =i I[x l ∈ C j ] x = nE I {x1∈Cj } f (x 1 ) 1 1 + n l=2 I[x l ∈ C j ] x = nE x1 I {x1∈Cj } f (x 1 )E x2,...,xn 1 1 + n l=2 I[x l ∈ C j ] x, x 1 b ≤ nE x1 I {x1∈Cj } f (x 1 ) 1 nµ(C j ) = 1 µ(C j ) Cj f (x 1 )µ(dx 1 )where, equality a follows from that fact, that if x i ∈ C j , then the term in the parenthesis does not change and if x i / ∈ C j , then the term within the parenthesis is zero, and inequality b follows from lemma D.5 since conditioned on x and x 1 , the random variable n l=2 I {x l ∈Cj } is Binomially distributed with parameters (n -1) and µ(C j ). , where c 0 > 0 is an absolute constant defined in Lemma 3.5. Then,E n i=1 w i,n (x)I[∥x i -x∥ > a] ≤ δ.Proof. From Lemma 3.5, we have that with probability at least 1-δ, diam(C j ) ≤ a for all 1 ≤ j ≤ m. Let us define the random variable:A 1 =    n i=1 1 k j:x∈Cj I[x i ∈ C j ] n i=1 I[x i ∈ C j ] I[∥x i -x∥ > a]   and the event:A 2 = ∪ j:x∈Cj C j ⊂ B(x, a)Let A c 2 denotes complement of the event A 2 . Then,E n i=1 w i,n (x)I[∥x i -x∥ > a] = E n i=1 1 k j:x∈Cj I[x i ∈ C j ] n i=1 I[x i ∈ C j ] I {∥xi-x∥>a} = E (A 1 |A 2 ) Pr (A 2 ) + E (A 1 |A c 2 ) Pr (A c 2 ) a ≤ 0 • Pr(A 2 ) + 1 • δ = δwhere the inequality follows from the fact that maximum value of A 1 is 1 and conditioned on the event A 2 , value of A 1 is 0.D.6 Technical results for satisfying condition (iii) of Stone's theorem (Theorem 3.2) Lemma D.7. For any x ∼ µ, let j 1 (x, Θ), . . . , j k (x, Θ) ∈ [m] be the k random coordinates of h Θ,k (x) that are set to 1. Let N j1(x,Θ) , . . . , N j k (x,Θ) be the number of data points falling in C j1(x,Θ) , . . . , C j k (x,Θ) respectively. Then min{N j1(x,Θ) , . . . , N j k (x,Θ) } → ∞ in probability, whenever n → ∞ and m k /n → 0 as n → ∞.Proof. For any random x ∈ X , let C k i(x,Θ) be the random cell of the partition{C k i } ( m k ) i=1 which sets k random coordinates j 1 (x, Θ), . . . , j k (x, Θ) of h Θ,k (x) to one. Then, C k i(x,Θ) = ∩ k i=1 C ji(x,Θ) . Let N n (x, Θ) = n i=1 I {xi∈C k i(x,Θ)} be the number of data points falling in the same cell as x. We first we show thatN n (x, Θ) → ∞ in probability. Let N 1 , N 2 , . . . N ( m k ) be the number of points of x, x 1 , . . . , x n falling in the m k respective cells C k 1 , . . . , C k ( m k ). Let S = {x, x 1 , . . . , x n } denote the set of positions of these n + 1 points. Since these points are independent and identically distributed, fixing the set S (but not the order of the points) and Θ, the conditional probability that x falls in thei th cell C k i is N i /(n + 1). Then for any fixed integer t > 0, Pr(N n (x, Θ) < t) = E [Pr (N n (x, Θ) < t|S, Θ)] = E i:Ni<t N i n + 1 ≤ (t -1) m k n + 1 ≤ (t -1) m k nwhich converges to zero on our assumption on n. Since C k i(x,Θ) ⊆ C j l (x,Θ) for l = 1, . . . , k, we have N n (x, Θ) ≤ min{N j1(x,Θ) , . . . , N j k (x,Θ) } and the statement of the Lemma follows.For ease of exposition, we use the notation x [1,n] to denote x 1 , . . . , x n and y [1,n] to denote y 1 , . . . , y n for various proofs appearing in the section.E.1 Proof of lemma 3.8Proof. Fix any Θ. This ensures that C 1 , . . . , C m are fixed. Now,E(η(x) -η(x)) 2 = E x,x [1,n] ,y [1,n] (η(x) -η(x)) 2 = E x [1,n] E x,y [1,n] (η(x) -η(x)) 2 |x [1,n] ) = E x [1,n]   Ex,y [1,n]      1 k j:x∈Cj (η j -ηj )   2 x [1,n]       a ≤ E x [1,n]   E x,y [1,n]   1 k j:x∈Cj (η j -ηj ) 2 x [1,n]     = E x [1,n]   E x,y [1,n]   1 k j:x∈Cj n i=1 Y i I[x i ∈ C j ] n i=1 I[x i ∈ C j ] -η(C j ) 2 x [1,n]     = E x [1,n]   E x,y [1,n]   1 k j:x∈Cj n i=1 y i I[x i ∈ C j ] nµ n (C j ) -η(C j ) 2 x [1,n]     = E x [1,n]   E x,y [1,n]   1 k j:x∈Cj n i=1 y i I[x i ∈ C j ] nµ n (C j ) -η(C j ) 2 I[nµ n (C j ) > 0] + η 2 (C j )I[µ n (C j ) = 0] x [1,n]     = E x [1,n]   E x,y [1,n]   1 k j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0] x [1,n]     +E x [1,n]   E x,y [1,n]   1 k j:x∈Cj η 2 (C j )I[µ n (C j ) = 0] x [1,n]     b ≤ E x [1,n]   E x,y [1,n]   1 k h Θ,k (x)[j]=1 n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0] x [1,n]     + m kne = E x [1,n]   E x   1 k E y [1,n]   j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0] x, x [1,n] )       + m kne c ≤ 1 4 E x [1,n]   E x   1 k j:x∈Cj I[nµ n (C j ) > 0] nµ n (C j ) X [1,n]     + m kne d ≤ 1 4 E x [1,n]   1 k m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j )   + m kne = 1 4k m j=1 µ(C j )E x [1,n] I[nµ n (C j ) > 0] nµ n (C j ) + m kne e ≤ 1 4k m j=1 2µ(C j ) (n + 1)µ(C j ) + m kne = m 2k(n + 1) + m kne ≤ m 2kn + m kne ≤ m kn .where, inequality a is due to Jensen's inequality. Inequality b follows from lemma E.3. Inequality c follows from lemma E.1 and inequality d follows from lemma E.2. Finally inequality e follow from the observation that nµ n (C j ) is Binomially distributed with parameters n and µ(C l ) and by an application of lemma E.4. The result follows noting that by Jensen's inequality E|η(x) -η(x)| ≤ E(η(x) -η(x)) 2 .Lemma E.1. Pick m × d projection matrix Θ. Suppose the EaS representation uses (i) a mapping Θ and (ii) k-winner-take-all sparsification. Let x be sampled from µ and let D n = ((x 1 , y 1 ), . . . , (x n , y n )) is a random training set where x i is sampled from µ and y i is distributed asη(x i ) for i ∈ [n].Then the following holds.E y [1,n]   j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0] x, x [1,n]   ≤ 1 4 j:x∈Cj I[nµ n (C j ) > 0] nµ n (C j )Proof. Conditioned on x, only k of the m coordinates in the EaS representation of x are non-zero. WLOG, for ease of exposition, assume these k non-zero coordinate to be j 1 , . . . , j k ∈ [m]. Then the number of x i that falls in any such C j l , where l ∈ [k], is nµ n (C j l ). The y i values corresponding to these x i points (there are nµ n (C j l ) of them in total) are identically and independently distributed with expectationE(y i |x i ∈ C j l ) = Pr(y i = 1|x i ∈ C j l ) = 1 µ(C j l ) Cj l Pr(y i = 1|x i = x)µ(dx) = 1 µ(C j l Cj l η(x)µ(dx) = η(C j l )Therefore, we can writeE y [1,n]   j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0] x, x [1,n]   = k l=1   E y [1,n] ( n i=1 (y i -η(C j l ))I[x i ∈ C j l ]) 2 I[nµ n (C j l ) > 0]|x [1,n] (nµ n (C j l )) 2   a = k l=1 n i=1 E yi (y i -η(C j l )) 2 I[x i ∈ C j l ]I[nµ n (C j l ) > 0]|x i (nµ n (C j l )) 2 b = k l=1 n i=1 η(C j l )(1 -η(C j l ))I[x i ∈ C j l ]I[nµ n (C j l ) > 0] (nµ n (C j l )) 2 c ≤ 1 4 k l=1 I[nµ n (C j l ) > 0] nµ n (C j l )where, equality a is due to the following observation. For any i, j ∈ [m], i ̸ = j and x i , x j ∈ C l for some l ∈ [m], y i and y j are identically and independently distributed with expectation η(C l ).Therefore, the expectation of the cross product is simply:E yi,yj [(y i -η(C l ))(y j -η(C l )] = E yi,yj y i y j -η(C l )(y i + y j ) + η(C l ) 2 = Ey i Ey j -η(C l )(Ey i + Ey j ) + η(C l ) 2 = 0Equality b follows from variance computation. In particular for anyY i , i ∈ [m] with x i ∈ C l for some l ∈ [m], E (y i -η(C l )) 2 = Ey 2 i -2η(C l )Ey i + η(C l ) 2 = η(C l ) -2η(C l ) 2 + η(C l ) 2 = η(C l )(1 -η(C l )).Finally, inequality c follows from the fact that for any z ∈ [0, 1], the maximum value of z(1 -z) is 1 4 .It is easy to observe that the final result is equivalent to 1 4 j:x∈CjI[nµn(Cj )>0] nµn(Cj ).Lemma E.2. Pick m × d projection matrix Θ. Suppose the EaS representation uses (i) a mapping Θ and (ii) k-winner-take-all sparsification. Let x be sampled from µ and let D n = ((x 1 , y 1 ), . . . , (x n , y n )) is a random training set where x i is sampled from µ and y i is distributed as η(x i ) for i ∈ [n]. Then conditioned on x 1 , . . . , x n , the following holds.E x   1 k j:x∈Cj I {nµn(Cj )>0} nµ n (C j )   ≤ 1 k m j=1 µ(C j )I {nµn(Cj )>0} nµ n (C j )Proof.E x   1 k j:x∈Cj I[nµ n (C j ) > 0] nµ n (C j )   a = ( m k ) i=1   Pr(x ∈ C k i )   1 k j∈σ(i) I[nµ n (C j ) > 0] nµ n (C j )     = ( m k ) i=1   1 k   j∈σ(i) µ(C k i )I[nµ n (C j ) > 0] nµ n (C j )     b = 1 k m j=1 i:j∈σ(i) µ(C k i )I[nµ n (C j ) > 0] nµ n (C j ) = 1 k m j=1 I[nµ n (C j ) > 0] nµ n (C j ) i:j∈σ(i) µ(C k i ) c = 1 k m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j )where equality a follows from part (ii) of lemma 3.4 since {C k i } ( m k ) i=1 forms a partition of X and the definition of σ in section 3.2. Equality b follows from the following observation. In the line above inequality b, we are summing k × m k terms. Since k × m k = m × m-1 k-1 and any j ∈ [m] can appear in exactly m-1 k-1 different subsets of of size k, equality b is simply rearranging the terms from the line above by changing the indices appropriately. Equality c follows from part (iv) of lemma 3.4. Lemma E.3. Pick m × d projection matrix Θ. Suppose the EaS representation uses (i) a mapping Θ and (ii) k-winner-take-all sparsification. Let x be sampled from µ and let D n = ((x 1 , y 1 ), . . . , (x n , y n )) is a random training set where x i is sampled from µ and y i is distributed as η(x i ) for i ∈ [n]. Then the following holds.E x [1,n]   E x,y [1,n]   1 k j:x∈Cj η 2 (C j )I[µ n (C j ) = 0] x [1,n]     ≤ m nke Proof. E x [1,n]   E x,y [1,n]   1 k j:X∈Cj η 2 (C j )I[µ n (C j ) = 0] x [1,n]     a = E x [1,n]   E x   1 k j:x∈Cj η 2 (C j )I[µ n (C j ) = 0] x [1,n]     b = E x [1,n]    ( m k ) i=1 Pr(x ∈ C k i )   1 k j∈σ(i) η 2 (C j )I[µ n (C j ) = 0]      = E x [1,n]    1 k ( m k ) i=1 j∈σ(i) µ(C k i )η 2 (C j )I[µ n (C j ) = 0]    c = E x [1,n]   1 k m j=1 η 2 (C j )I[µ n (C j ) = 0]   i:j∈σ(i) µ(C k i )     = 1 k m j=1 η 2 (C j )µ(C j ) [E x1,...,xn I[µ n (C j ) = 0]] = 1 k m j=1 η 2 (C j )µ(C j )(1 -µ(C j )) n = 1 nk m j=1 η 2 (C j )nµ(C j )(1 -µ(C j )) n ≤ 1 nk m j=1 η 2 (C j )nµ(C j )e -nµ(Cj ) d ≤ 1 nk m j=1 nµ(C j )e -nµ(Cj ) ≤ m nk max j nµ(C j )e -nµ(Cj ) e ≤ m nkewhere equality a follows from the fact that the quantity with the inner square bracket is unaffected by the Y i s. Equality b follows from part (ii) of lemma 3.4 since {C k i } ( m k ) i=1 forms a partition of X and the definition of σ in section 3.2. Equality c follows from the following observation. In the line above inequality c, we are summingk × m k terms. Since k × m k = m × m-1 k-1 and any j ∈ [m] can appear in exactly m-1k-1 different subsets of of size k, equality c is simply rearranging the terms from the line above by changing the indices appropriately. Inequality d follows from the fact max j η(C j ) ≤ 1. Finally inequality e follows from the fact that sup z ze -z = 1 e .Lemma E.4. (Binomial bound Györfi et al. [2002] ) Let the random variable B(n, p) be Binomially distributed with parameters n and p. Then,E 1 B(n, p) I[B(n, p) > 0] ≤ 2 (n + 1)p E.2 Proof of Lemma 3.10 Proof. Take any x ∈ X . Then |η(x) -η(x)| = η(x) - 1 k j:x∈Cj ηj = 1 k x∈Cj (η(x) -η(x ′ ) ≤ 1 k j:x∈Cj |η(x) -ηj | = 1 k j:x∈Cj η(x) - 1 µ(C j ) Cj η(x ′ )µ(dx ′ ) = 1 k j:x∈Cj 1 µ(C j Cj (η(x) -η(x ′ ))µ(dx ′ ) ≤ 1 k j:x∈Cj 1 µ(C j ) Cj |η(x) -η(x ′ )|µ(dx ′ ) ≤ 1 k j:x∈Cj 1 µ(C j ) Cj L∥x -x ′ ∥ β µ(dx ′ ) ≤ 1 k j:x∈Cj L • (diam(C j )) β µ(C j ) Cj µ(dx ′ ) ≤ L • max j∈[m] (diam(C j )) β E.3 Proof of Theorem 3.15Proof. Define η : X 1 → [0, 1] to be a triangular function defined below: for 0 < θ ≤ 2π, η(cos θ, sin θ, 0, 0, . . . ,0) = θ π , if θ ≤ π 2 -θ π , if θ > πClearly, η is 1 2 -Lipschitz and for k = 1, η(x) = m j=1 η(C j )I {x∈Cj } . Therefore, using Theorem E.5, with probability at least 1/2 over the choice of Θ,sup x∈X1 |η(x) -η(x)| ≥ c ′′ d • 1 m 1/(d-1) log mwhere c ′′ d is am absolute constant depending on d. Taking expectation, with probability at least 1/2 over the choice of Θ, we have,E X,Dn |η(X) -η(X)| ≥ c ′′ d • 1 m 1/(d-1) log m . Next, using Lemma 3.8 with k = 1 yields, E X,Dn |η(X) -η(X)| ≤ m n . Using triangle inequality combining these results, E X,Dn |η(X) -η(X)| = E X,Dn |η(X) -η(X) + η(X) -η(X)| ≥ E X,Dn |η(X) -η(X)| -E X,Dn |η(X) -η(X)| ≥ c ′′ d • 1 m 1/(d-1) log m - m n (20)Ignoring the log term we see that for large enough n, the first term on the right hand side of (20) will dominate. In particular, forn = Ω m 1+ 2 d-1 , we get E X,Dn |η(X) -η(X)| ≥ Ω m -1 d-1 . To see this (ignoring the log term), if m n ≤ c ′′ d 2 • 1 m 1/(d-1) , then E X,Dn |η(X) -η(X)| ≥ c ′′ d 2 • 1 m 1/(d-1) . Now, m n ≤ c ′′ d 2 • 1 m 1/(d-1) ⇒ n ≥ 4 (c ′′ d ) 2 • m 1+ 2 d-1 .In particular, setting n = 4(c ′′ d ) 2 m 1+ 2 d-1 , we have E X,Dn |η(X) -η(X)| ≥ c ′′ d 2 m -1 d-1 = c ′′ d 2 d-3 d-1 n -1 d+1 .Theorem E.5. [Theorem 4 of Dasgupta and Tosh [2020] ] For any d > 3, let input space X 1 be the one-dimensional sub-manifold of R d given in (12). Take k = 1. Suppose that random matrix Θ has rows chosen from the distribution ν that is uniform over S d-1 . For any 0 < λ < 1, there exists a λ-Lipschitz function f : X 1 → R such that with probability at least 1/2 over the choice of Θ, no matter how the weights w 1 , . . . , w m are set, the resulting function f (x) = m j=1 w j I {x∈Cj } has approximation error at leastsup x∈X1 | f (x) -f (x)| ≥ c ′ d • λ • 1 m 1/(d-1) log mwhere c ′ d is some absolute constant depending on d.F.1 Lemma F.1 and its proofWe first show that while EaS representation using h 2 is not k-sparse,for large enough sample size, with high probability, it is at least k/2-sparse and at most 2k-sparse in expectation. F). Proof. We start with a version of relative generalization error bound, originally due to Vapnik and Chervonenkis, that appeared in Chaudhuri and Dasgupta [2010] .Theorem F.2. (Theorem 15 of Chaudhuri and Dasgupta [2010] ) Let G be a class of functions from X to {0, 1} with VC dimension d < ∞, and P a probability distribution on X . Let E be the expectation with respect to P. Suppose n points are drawn independently from P; let E n denotes expectation with respect to this sample. Then for any δ > 0, with probability at least 1 -δ the following holds for all g ∈ G:-min β n E n g, β 2 n + β n + Eg ≤ Eg -E n g ≤ min β 2 n + β n E n g, β n Eg where β n = 4(d log(2n)+log(8/δ)) n .Let θ i be the i th row of the projection matrix Θ and let µ i be the distribution of θ i • x where x is distribution according to µ. Then, for any a ∈ R,Pr x∼µ (θ i • x ≥ a) = µ i (θ i • x ≥ a).Suppose x ′ 1 , . . . , x ′ n are sampled independently at random from µ. For any interval A a = [a, ∞), letµ i n (A a ) = 1 n n j=1 1I[θ i • x ′ j ≥ a].Consider the class of indicator functions over the intervals [a, ∞) for a ∈ R. This class has VC dimension 1 and define β 2 = 4 n log 2n + log( 8m δ ) . Suppose µ i n (A a ) satisfies the conditionµ i n (A a ) ≥ 4β 2 . The bound µ i (A a ) -µ i n (A a ) ≤ β 2 + β µ i n (A a ) from Theorem F.2 yields, µ i (A a ) ≤ µ i n (A a ) + β 2 + β µ i n (A a ) ≤ µ i n (A a ) + 1 4 • µ i n (A a ) + 1 2 • .µ i n (A a ) = 7 4 • µ i n (A a )Similarly, the bound -β µ i n (A a ) ≤ µ i (A a ) -µ i n (A a ) from Theorem F.2 yields, µ i (A a ) ≥ µ i n (A a ) -β µ i n (A a ) ≤ µ i n (A a ) - 1 2 • µ i a (A a ) = 1 2 • µ i n (A a )Combining these two bounds, we can can conclude that for all intervals A a satisfying µ i n (A a ) ≥ 4β 2 , with probability at least 1 -δ m it holds that 1 2• µ i n (A a ) ≤ µ i (A a ) ≤ 7 4 • µ i n (A a ).Now if we only consider the intervals A τn(θj ) , then from ( 13) it is clear that µ i n (A τn(θj ) ) ≤ k m + 1 n . This is because for any interval µ i n (•) can take (n + 1) possible values in steps of 1 n , namely, 0, 1 n , 2 n , . . . , 1. Therefore, from the definition of τ n (θ j ) in ( 13), if µ i n (A τn(θj ) ) ̸ = k m , then to ensure that µ i n (A τn(θj ) ) ≥ k m , its maximum value can be at most k m + 1 n . Therefore, the conditionµ i n (A τn(θj ) ) ≥ 4β 2 implies, k m + 1 n ≥ 16 n log 2n + log 8m δ = 16 n log 2 + log n + log 8 + log m δ = 64 n + 16 n log n + log m δ or in other words, k m ≥ 63 n + 16 n log n + log m δ . Noting that, 7 4 • µ i n (A τn(θj ) ) ≤ 7k 4m + 7 4n ≤ 7k 4m + 7 4 • k 63m ≤ 2k m .Therefore, if k m ≥ c0 n log n + log m δ for some universal constant c 0 > 0, then with probability at least1 -δ m , k 2m ≤ Pr x∼µ (θ j • x ≥ τ n (θ j ) ≤ 2k m .Taking union bound over θ 1 , . . . , θ m yields the desired results.Proof. Pick any good θ, and let x = π M (θ) be its projection on M . Since X consists of unit vectors, using Lemma F.1 with probability at least 1 -δ, the points that lie in C(θ) are at least k/(2m) fraction or at most 2k/m fraction of x's (under distribution µ) that have highest dot product with θ or equivalent to closest to θ. Thus, C(θ) is the set of the form B(θ, r ′ ) where radius r ′ is so chosen that k/(2m) ≤ µ(B(θ, r ′ )) ≤ 2k/m. However, it is not of the form B(x, r ′′ )which causes complication.In particular, two questions need to be answered: (i) if a point x ′ ∈ M lies within distance r < ρ of x, how far can it possibly be from θ, and conversely, (ii) if x ′ ∈ M lies within distance r < ρ of θ , how far can it possibly be from x? These two questions are answered in Lemma 6 of Dasgupta and Tosh [2020] showing that,EQUATIONFor the left-hand containment pick r = ρ-∆ ρ+∆ k 2c2m 1/d0. Further taking,r ′ = ∆ 2 + ρ + ∆ ρ r 2 r ′′ = ρ ρ -∆ ((r ′ ) 2 -∆ 2 ) = k 2c 2 m 1/d0and using (17) yields that µ(B M (x, r ′′ ) < k/(2m). Now using ( 21) and ( 22) we have,B M (x, r) ⊂ B M (θ, r ′ ) ⊂ B M (x, r ′′ ). Since µ(B M (x, r ′′ )) < k/(2m), this ensures B M (x, r) ⊂ B M (θ, r ′ ) ⊂ C(θ). Pick r = 2k c1m 1/d0. Using (17), this ensures that µ(B(x, r)) ≥ 2k/m. Further takingr ′ = ∆ 2 + ρ + ∆ ρ r 2 r ′′ = ρ ρ -∆ ((r ′ ) 2 -∆ 2 ) = ρ + ∆ ρ -∆ 2k c 1 m 1/d0and using ( 21) and ( 22), we have,B M (x, r) ⊂ B M (θ, r ′ ) ⊂ B M (x, r ′′ ). Since µ(B M (x, r)) ≥ 2k/m, this ensures that C(θ) ⊂ B M (x, r ′ ) which in turn is contained in B M (x, r ′′ ).Since for any good θ, ∆ ≤ ρ/2, the result follows.Proof. Let E 1 be the event that bounds the diameter of the response region of any good θ, as specified in Lemma B.3, with probability at least 1-δ, over the random choice of the training set. We condition on this event. For any x ∈ M and r > 0, letA(x, r) = {θ ∈ Γ ρ/2 : ∥π M (θ) -x∥ < r} Since 1 2 < ρ-∆ρ+∆ for ∆ ≤ ρ/2, using Lemma B.3 and choosing large enough m satisfying (2k/(c 1 m)) 1/d0 < min(ρ, r 0 ), if we setr 1 = 1 2 k 2c 2 m 1/d0 then, θ ∈ A(x, r 1 ) ⇒ x ∈ B M π M (θ), 1 2 k 2c 2 m 1/d0 ⇒ x ∈ B M π M (θ), ρ -∆ ρ + ∆ k 2c 2 m 1/d0which implies ⇒ x ∈ C(θ). It has been established that A(x, r) has non-negligible probability mass under ν.Lemma F.3 (Lemma 14 of Dasgupta and Tosh [2020] ). Suppose ν is multivariate Gaussian N (0, I). There is a constant c d , that depends on the dimension d, such that any x ∈ M and 0 < r < r 0 , we have ν(A(x, r)) ≥ c d r d0 .Using ( 17), M has a r 1 /2 cover M of size at most (2c 2 /c 1 )8 d0 m/k. To see this pick points x 1 , . . . , x n ∈ M that are at a distance r 1 /2 from each other. The balls B(x 1 , r 1 /4) are disjoint and each has µ(B(x i , r 1 /4)) ≥ c 1 (r 1 /4) d0 = (c 1 /(2c 2 ))(1/8 d0 )k/m. Since total probability mass of these N balls is at most 1, this gives the bound on N .Pick any x ∈ M . For i ∈ [m], let U i be a binary random variable that takes value 1 if θ i ∈ A(x, r 1 /2) and 0 otherwise. Therefore,U i = 1 w.p. ν(A(x, r 1 /2)) 0 w.p.1 -ν(A(x, r 1 /2)) Note that ν(x, r 1 /2) ≥ c d (r 1 /2) d0 = (c d /(2c 2 ))(1/4 d0 )k/m = α d k/m, where we have set α d = (c d /(2c 2 ))(1/4 d0 ). Let U = m i=1 U i be that number of θ i 's that fall in A(x, r 1 /2) and EU = m i=1 EU i ≥ α d k.Let E 2 be the event that U > α d k/2 and E c 2 be the complement event. Using Chernoff bound, we havePr(E c 2 |E 1 ) = Pr (U ≤ α d k/2|E 1 ) ≤ Pr (U ≤ (1/2)EU |E 1 ) ≤ e -EU/8 ≤ e -α d k/8Bounding the right most quantity above to be at most δ/ M , for k as specified in the lemma statement, for suitable choice of c ′ d , we conclude that E 2 holds (conditioned on E 1 ) with probability at least 1 -δ. Therefore, with probability at least 1 -2δ, both E 1 and E 2 hold, impying that for every x ∈ M , there are at least α d k/2 good θ i 's in A(x, r 1 /2). Now pick any arbitrary x ∈ M . There is some x ∈ M with ∥x -x∥ ≤ r 1 /2. Moreover, for anyθ j ∈ A(x, r 1 /2) ⇒ θ j ∈ A(x, r 1 /2) ⇒ x ∈ C(θ j ).For ease of exposition, we use the notation x [1,n] to denote x 1 , . . . , x n and y [1,n] to denote y 1 , . . . , y n , x ′[1,n] to denote x ′ 1 , . . . , x ′ n and y ′ [1,n] to denote y ′ 1 , . . . , y ′ n for various proofs appearing in the section. Note number of non-zero entries in the EaS representation given in ( 14) is variable and we use the notation k(x) to denote the number of non-zero entries in h 2 (x).Proof. Fix any Θ. Then, conditioning on x ′ [1,n] ensures that C 1 , . . , C m are fixed. Now,E x,Dn,D ′ n (η(x) -η(x)) 2 = E x,x [1,n] ,y [1,n] ,x ′ [1,n] ,y ′ [1,n] (η(x) -η(x)) 2 a = E x,x [1,n] ,y [1,n] ,x ′ [1,n] (η(x) -η(x)) 2 = E x [1,n] ,x ′ [1,n] E x,y [1,n] (η(x) -η(x)) 2 x [1,n] , x ′ [1,n] ) = E x [1,n] ,x ′ [1,n]   Ex,y [1,n]      1 t j:x∈Cj (η j -ηj )   2 x [1,n] , x ′ [1,n]       b ≤ E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj (η j -ηj ) 2 x [1,n] , x ′ [1,n]     = E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj n i=1 y i I[x i ∈ C j ] n i=1 I[x i ∈ C j ] -η(C j ) 2 I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     = E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj n i=1 y i I[x i ∈ C j ] nµ n (C j ) -η(C j ) 2 I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     = E x [1,n] ,x ′ [1,n]        E x,y [1,n]        1 t j:x∈Cj    n i=1 y i I[X i ∈ C j ] nµ n (C j ) -η(C j ) 2 I[nµ n (C j ) > 0]I[j ∈ A t (x)] +η 2 (C j )I[µ n (C j ) = 0]I[j ∈ A t (x)]    x [1,n] , x ′ [1,n]               = E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj n i=1 (y i -η(C j ))I {xi∈Cj } nµ n (C j ) 2 I[nµ n (C j ) > 0]I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     +E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj η 2 (C j )I[µ n (C j ) = 0]I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     c ≤ E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0]I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     + m tne = E x [1,n] ,x ′ [1,n]       E x       1 t E y [1,n]       j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0]I[j ∈ A t (x)] x, x [1,n] , x ′ [1,n] )                   + m tne d ≤ 1 4 E x [1,n] ,x ′ [1,n]   E x   1 t j:x∈Cj I[nµ n (C j ) > 0]I[j ∈ A x t ] nµ n (C j ) x [1,n] , x ′ [1,n]     + m tne e ≤ 1 4 2m t(n + 1) + m tne = m 2t(n + 1) + m kne ≤ m 2tn + m tne ≤ m tn .where equality a follows from the fact that the quantity with the inner square bracket is unaffected by the y i 's. E x [1,n] ,x ′ [1,n]   E x,y [1,n]   1 t j:x∈Cj η 2 (C j )I[µ n (C j ) = 0]I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     ≤ m nteProof. We start by taking the 1/t factor outside.1 t E x [1,n] ,x ′ [1,n]   E x,y [1,n]   j:x∈Cj η 2 (C j )I[µ n (C j ) = 0]I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     a = 1 t E x [1,n] ,x ′ [1,n]   E x   j:x∈Cj η 2 (C j )I[µ n (C j ) = 0]I[j ∈ A t (x)] x [1,n] , x ′ [1,n]     = 1 t E x [1,n] ,x ′ [1,n]   m k ′ =0 Pr(k(x) = k ′ )E x   j:x∈Cj η 2 (C j )I[nµ n (C j ) = 0]I[j ∈ A t (x)] k(x) = k ′ ]   x [1,n] , x ′ [1,n]   b = 1 t E x [1,n] ,x ′ [1,n]   m k ′ =1 Pr(k(x) = k ′ )E x   j:x∈Cj η 2 (C j )I[nµ n (C j ) = 0]I[j ∈ A t (x)] k(x) = k ′ ]   x [1,n] , x ′ [1,n]   c ≤ 1 t E x [1,n] ,x ′ [1,n]   m k ′ =1 Pr(k(x) = k ′ )E x   j:x∈Cj I[nµ n (C j ) = 0]I[j ∈ A t (x)] k(x) = k ′ ]   x [1,n] , x ′ [1,n]   d ≤ 1 t E x [1,n] ,x ′ [1,n]   m k ′ =1 Pr(k(x) = k ′ ) m j=1 µ(C j )I[nµ n (C j ) = 0] x [1,n] , x ′ [1,n]   e ≤ 1 t E x [1,n] ,x ′ [1,n]   Pr(k(x) = 0) m j=1 µ(C j )I[nµ n (C j )] + m k ′ =1 Pr(k(x) = k ′ ) m j=1 µ(C j )I[nµ n (C j ) = 0] x [1,n] , x ′ [1,n]   = 1 t E x [1,n] ,x ′ [1,n]   m j=1 µ(C j )I[nµ n (C j ) = 0] m k ′ =0 Pr(k(x) = k ′ ) x [1,n] , x ′ [1,n]   = 1 t E x [1,n] ,x ′ [1,n]   m j=1 µ(C j )I[nµ n (C j ) = 0] x [1,n] , x ′ [1,n]   = 1 t E x ′ [1,n]   m j=1 E x [1,n] µ(C j )I[nµ n (C j ) = 0] x ′ [1,n]   ≤ 1 t E x ′ [1,n]   m j=1 µ(C j )(1 -µ(C j ) n   = 1 nt E x ′ [1,n]   m j=1 nµ(C j )(1 -µ(C j ) n   ≤ 1 nt E x ′ [1,n]   m j=1 nµ(C j )e -nµ(Cj )   ≤ m nt E x ′ [1,n] max j nµ(C j )e -nµ(Cj ) f ≤ m nt E x ′ [1,n] 1 e = m ntewhere equality a follows from the fact that the quantity with the inner square bracket is unaffected by the y i 's. Equality b follows from the fact that for k(x) = 0, number of non-zero entries in the EaS of x using ( 14) is zero and x / ∈ C j , ∀j. Therefore, we denote the quantity j:x∈Cj η 2 (C j )I[nµ n (C j )]I[j ∈ A x t ] = 0. Inequality c follows from the fact that η(C j ) ≤ 1, ∀j. Inequality d follows from Lemma F.5. Inequality e follows since we are adding a non-negative quantity. Finally, inequality f follows from the fact that sup z ze -z = 1 e . Lemma F.5.E x   j:x∈Cj I[nµ n (C j ) = 0]I[j ∈ A t (x)] k(x) = k ′   ≤ m j=1 µ(C j )I[nµ n (C j ) = 0]Proof. Conditioned on k(x) = k ′ , EaS representation given in ( 14) has exactly k ′ non-zero entries. Therefore, using Lemma 3.4,E x   j:x∈Cj I[nµ n (C j ) = 0]I[j ∈ A t (x)] k(x) = k ′   a = ( m k ′) i=1 Pr x ∈ C k ′ i j:σ(i) I[nµ n (C j ) = 0]I[j ∈ A t (x)] = ( m k ′) i=1 j:σ(i) µ(C k ′ i )I[nµ n (C j ) = 0]I[j ∈ A t (x)] b = m j=1 i:j∈σ(i) µ(C k ′ i )I[nµ n (C j ) = 0]I[j ∈ A t (x)] = m j=1 I[nµ n (C j ) = 0]   i:j∈σ(i) µ(C k ′ i )I[j ∈ A t (x)]   ≤ m j=1 I[nµ n (C j ) = 0]   i:j∈σ(i) µ(C k ′ i )   c = m j=1 µ(C j )I[nµ n (C j ) = 0]where equality a follows from part (ii) of lemma 3.4 since{C k ′ i } ( m k ′ )i=1 forms a partition of X and the definition of σ in section 3.2 with k = k ′ . Equality b follows from the observation. In the line above inequality b, we are summingk ′ × m k ′ terms. Since k ′ × m k ′ = m × m-1 k ′ -1and any j ∈ [m] can appear in exactly m-1 k ′ -1 different subsets of of size k ′ , equality b is simply rearranging the terms from the line above by changing the indices appropriately. Equality c follows from part (iv) of lemma 3.4.Lemma F.6. Pick m × d projection matrix Θ. Suppose the EaS representation uses (i) a mapping Θ and (ii) empirical k-threshold sparsification. Let x be sampled from µ and let D n = ((x 1 , y 1 ), . . . , (x n , y n )) is a random training set where x i is sampled from µ and y i is distributed as η(x i ) for i ∈ [n]. Similarly, D ′ n = ((x ′ 1 , y ′ 1 ), . . . , (x ′ n , y ′ n )) be another random train- ing set independent of D n , where x ′ i is sampled from µ and y ′ i is distributed as η(x ′ i ) for i ∈ [n].Then the following holds.E y [1,n]   j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0]I[j ∈ A t (x)] x, x [1,n] , x ′ [1,n]   ≤ 1 4 j:x∈Cj I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j )Proof. Conditioned on x and x ′ [1,n] , only k(x) = k ′ of the m coordinates in the EaS representation of x are non-zero. If k ′ = 0 then the right hand side of the Lemma statement still holds with tghe value being zero since each C j will be an empty set in that case. WLOG, for ease of exposition, assume that k ′ > 0 and these k ′ non-zero coordinate to be j 1 , . . . , j k ′ ∈ [m]. Then the number of x i that falls in any such C j l , where l ∈ [k ′ ], is nµ n (C j l ). The y i values corresponding to these x i points (there are nµ n (C j l ) of them in total) are identically and independently distributed with expectationE(y i |x i ∈ C j l ) = Pr(y i = 1|x i ∈ C j l ) = 1 µ(C j l ) Cj l Pr(y i = 1|x i = x)µ(dx) = 1 µ(C j l ) Cj l η(x)µ(dx) = η(C j l )Therefore, we can writeE y [1,n]   j:x∈Cj n i=1 (y i -η(C j ))I[x i ∈ C j ] nµ n (C j ) 2 I[nµ n (C j ) > 0]I[j ∈ A t (x)] x, x [1,n] , x ′ [1,n]   = k ′ l=1     E y [1,n] ( n i=1 (y i -η(C j l ))I[x i ∈ C j l ]) 2 I[nµ n (C j l ) > 0]I[j l ∈ A t (x)] x, x [1,n] , x ′ [1,n] (nµ n (C j l )) 2     a = k ′ l=1     n i=1 E yi (y i -η(C j l )) 2 I[x i ∈ C j l ]I[nµ n (C j l ) > 0]I[j l ∈ A t (x)] x, x i , x ′ i (nµ n (C j l )) 2     b = k ′ l=1 n i=1 η(C j l )(1 -η(C j l ))I[x i ∈ C j l ]I[nµ n (C j l ) > 0]I[j l ∈ A t (x)] (nµ n (C j l )) 2 c ≤ 1 4 k l=1 I[nµ n (C j l ) > 0]I[j l ∈ A t (x)] nµ n (C j l )where, equality a is due to the following observation. For any i, j ∈ [m], i ̸ = j and x i , x j ∈ C l for some l ∈ [m], y i and y j are identically and independently distributed with expectation η(C l ).Therefore, the expectation of the cross product is simply:E yi,yj [(y i -η(C l ))(y j -η(C l )] = E yi,yj y i y j -η(C l )(y i + y j ) + η(C l ) 2 = Ey i Ey j -η(C l )(Ey i + Ey j ) + η(C l ) 2 = 0.Equality b follows from variance computation. In particular for any yi , i ∈ [m] with x i ∈ C l for some l ∈ [m], E (y i -η(C l )) 2 = Ey 2 i -2η(C l )Ey i + η(C l ) 2 = η(C l ) -2η(C l ) 2 + η(C l ) 2 = η(C l )(1 -η(C l )).Finally, inequality c follows from the fact that for any z ∈ [0, 1], the maximum value of z(1 -z) is 1 4 .It is easy to observe that the final result is equivalent to 1 4 j:x∈CjI[nµn(Cj )>0]I[j∈At(x)] nµn(Cj ).Lemma F.7. Pick m × d projection matrix Θ. Suppose the EaS representation uses (i) a mapping Θ and (ii) empirical k-threshold sparsification. Let x be sampled from µ and let D n = ((x 1 , y 1 ), . . . , (x n , y n )) is a random training set where x i is sampled from µ and y i is distributed as η(x i ) for i ∈ [n]. Similarly, D ′ n = ((x ′ 1 , y ′ 1 ), . . . , (x ′ n , y ′ n )) be another random train- ing set independent of D n , where x ′ i is sampled from µ and y ′ i is distributed as η(x ′ i ) for i ∈ [n].Then the following holds.E x [1,n] ,x ′ [1,n]   E x   1 t j:x∈Cj I[µ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) x [1,n] , x ′ [1,n]     ≤ 2m t(n + 1)Proof. We start by taking the 1/t factor outside.1 t E x [1,n] ,x ′ [1,n]   E x   j:x∈Cj I[µ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) x [1,n] , x ′ [1,n]     = 1 t E x [1,n] ,x ′ [1,n]   m k ′ =0 Pr(k(x) = k ′ )E x   j:x∈Cj I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) k(x) = k ′ ]   x [1,n] , x ′ [1,n]   a = 1 t E x [1,n] ,x ′ [1,n]   m k ′ =1 Pr(k(x) = k ′ )E x   j:x∈Cj I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) k(x) = k ′ ]   x [1,n] , x ′ [1,n]   b ≤ 1 t E x [1,n] ,x ′ [1,n]   m k ′ =1 Pr(k(x) = k ′ ) m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j ) x [1,n] , x ′ [1,n]   c ≤ 1 t E x [1,n] ,x ′ [1,n]       Pr(k(x) = 0) m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j ) + m k ′ =1 Pr(k(x) = k ′ ) m j=1 µ(C j )I[nµ n (C j ) = 0] nµ n (C j ) x [1,n] , x ′ [1,n]       = 1 t E x [1,n] ,x ′ [1,n]   m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n j ) m k ′ =0 Pr(k(x) = k ′ ) x [1,n] , x ′ [1,n]   = 1 t E x [1,n] ,x ′ [1,n]   m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j ) x [1,n] , x ′ [1,n]   = 1 t E x ′ [1,n]   m j=1 E x [1,n] µ(C j )I[nµ n (C j ) > 0] nµ n (C j ) x ′ [1,n]   d ≤ 1 t E x ′ [1,n]   m j=1 2µ(C j ) (n + 1)µ(C j )   = 1 t E x ′ [1,n] 2m (n + 1) = 2m t(n + 1)where equality a follows from the fact that for k(x) = 0, number of non-zero entries in the EaS of x using ( 14) is zero and x / ∈ C j , ∀j. Therefore, we denote the quantity j:x∈CjI[nµn(Cj )>0]I[j∈At(x)] nµn(Cj ) = 0.Inequality b follows from Lemma F.8. Inequality c follows since we are adding a non-negative quantity. Finally, inequality d follows from the fact that nµ n (C j ) is Binomially distributed with parameters n and µ(C j ) and by an application of lemma E.4.Lemma F.8.E x   j:x∈Cj I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) k(x) = k ′   ≤ m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j )Proof. Conditioned on k(x) = k ′ , EaS representation given in ( 14) has exactly k ′ non-zero entries. Therefore, using Lemma 3.4,E x   j:x∈Cj I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) k(x) = k ′   a = ( m k ′) i=1 Pr x ∈ C k ′ i j:σ(i) I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) = ( m k ′ ) i=1 j:σ(i) µ(C k ′ i )I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) b = m j=1 i:j∈σ(i) µ(C k ′ i )I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j ) = m j=1 I[nµ n (C j ) > 0]I[j ∈ A t (x)] nµ n (C j )   i:j∈σ(i) µ(C k ′ i )   ≤ m j=1 I[nµ n (C j ) > 0] nµ n (C j )   i:j∈σ(i) µ(C k ′ i )   c = m j=1 µ(C j )I[nµ n (C j ) > 0] nµ n (C j )where equality a follows from part (ii) of lemma 3.4 since{C k ′ i } ( m k ′ )i=1 forms a partition of X and the definition of σ in section 3.2 with k = k ′ . Equality b follows from the following In the line above inequality b, we are summing k Guidelines:′ × m k ′ terms. Since k ′ × m k ′ = m × m-1 k ′ -1 and any j ∈ [m] can appear in exactly m-1 k ′ -1 different subsets of of size k ′ ,• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Data used from OpenML repository. KNN and Random Forest models are run from Scikit-learn. See section 5.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).https://scikit-learn.org/stable/https://www.openml.org/We note that Lemma B.3 a modified version of Lemma 6 ofDasgupta and Tosh [2020] to incorporate the uncertainty associated with the data dependent threshold selection in (13). Also, Lemma B.4 is a modified version of Lemma 7 ofDasgupta and Tosh [2020] which incorporates threshold selection uncertainty and additionally guaranteeing the number of good θj to be linear in k. 
 
 Appendix:  


Decision: Overall, reviews for this paper are positive -- reviewers feel that the results on expand-and-sparsify classifiers are interesting and novel and that the classifiers themselves are interesting and easy to implement. The paper is also very well-written. While the paper builds fairly directly on prior work of Dasgupta and Tosh [2020] it does make novel technical contributions, and is a good fit for NeurIPS.

Reviews: review: paper_summary: paper_summary: The paper introduces two algorithms for non-parametric binary classification utilizing the expand-and-sparsify (EaS) representation. The first algorithm employs a winners-take-all approach for sparsification. It demonstrates consistency and achieves a minimax-optimal convergence rate that depends on the data dimension. The second algorithm is designed for scenarios where the data lies in a low-dimensional manifold. By utilizing the empirical k-thresholding operation, this algorithm attains the minimax optimal convergence rate dependent on the dimension of the low-dimensional manifold rather than the data dimension.
strength_weakness: strength_weakness: 1. Most parts of the algorithms and some sections of their proofs come from [Dasgupta and Tosh, 2020] directly. The authors have pointed out that technically, they relax the Lipschitz continuous to Holder continuous and consider the effects of sample size. However, overall, the technical contribution is not significantly substantial in this regard. I would not view this point as a negative but rather as a neutral one.

2. I actually appreciate the way you have written the related work section, as it effectively illustrates the intuition behind EaS and how this idea has been developed. It also highlights the differences between this paper and previous works. However, there is a lack of related work on non-parametric classification, particularly focusing on their consistency and convergence results.
questions: questions: 1. As in Weakness 2, I suggest including more related work on non-parametric classification, particularly focusing on their consistency and convergence results.

2. In Algo 2, how do we choose t? 

3. I appreciate your lower bound result in Theorem 3.15. However, we can modify Algo 1 by turning down the effects from $\theta_j$ that are far from $x$, specifically we can choose larger m and k, and then set eas[i] to be 0 when $\theta_i$ is not t-close to $x$. Does this modification make Algo 1 applicable to the manifold setting? If not, what is the intuition behind Algo 2 working in this scenario while the modified Algo 1 does not? In other words, how does 'empirical-k-thresholding' provide an advantage over 'k-WTA'?

4. The EaS method was initially proposed for unsupervised learning because it does not require labels. Given labeled data, we actually possess much more information. For instance, points with the same label should be closer in the representation space. However, your algorithm learns the representation and identifies the 'k-neighbors' primarily based on the data itself rather than their labels. From this perspective, I believe there could be modifications to the algorithm that better utilize the labels during the training phase. This could be a worthwhile area for further exploration.

## Minor:
1. In Algo 2, why we use first and second half of training data separately? In my understanding, the first half of the training data is used to determine the threshold, while the second half is used to determine $\eta_j$. So, we can probably use the whole batch of data twice to do the two things instead.
2. Page 3 line 137. $(x_1,y_1)$ should be $(x_i,y_i)$.
3. Page 4 line 153. It should be “An average of y values”.
4. Page 4 line 163. “Non-parametric”.
5. Page 8 line 323. “Alg. 2”: a missing “.”
6. Page 8 line 324. A missing $($.
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_summary: The paper studies expand and sparsify the approach to non-parametric classification. The high-level idea is to first lift the example $x \in \mathcal{X} = \mathcal{S}^{d-1}$ to a $\{0,1\}^m$, a $m$-dimensional Boolean cube with exactly $k$ ones. The lifting is done by a linear mapping $x \mapsto \Theta x$ followed by top-$k$ selection using the magnitude of $\Theta x$, where the matrix $\Theta$ is sampled randomly. Let $\Theta x \mapsto z$ be the boolean feature obtained after the top-$k$ selection. The authors define a simple learning rule for the weight vector $w \in [0,1]^m$ and propose a linear classification rule $\mathbf{1}[w^{\top} x \geq k/2 ]$. Under the assumption that the score function $\eta: \mathcal{X} \to [0,1] $ of the Bayes optimal classifier is Holder-continuous, the proposed classifier is shown to be minimax optimal. The paper also proposes another classifier that can adapt if the example space $\mathcal{X}$ has a low-dimensional structure.
strength_weakness: strength_weakness: I did not find any apparent weakness in the paper. The paper delivers on its promise to provide a minimax optimal learner based on the expand and sparsify approach.
questions: questions: Does Theorem 3.12 imply the consistency result in Theorem 3.3? If true, I suggest that the authors just state quantitative bound and infer consistency in a remark. The authors can use the saved space to give a more detailed proof sketch of Theorem 3.12. On the other hand, if the conditions for consistency in Theorem 3.3 and the quantitative rates in Theorem 3.12 are different, then some comments on that difference would be helpful.
limitations: limitations: N/A
paper_summary: paper_summary: In this paper, the authors studied the problem of binary classification when the feature vectors are on the unit sphere in $\mathbb{R}^d$. The paper proposed a non-parametric algorithm based on a method called EaS (Expand and Sparsification). They proved that this method is universally consistent and that its errors converge to the Bayes error with a rate of $\mathcal{O}(n^{-\frac{1}{d}})$. They also proposed an algorithm for when the data lie in a $d_0$-dimensional manifold and proved that its errors converge to the Bayes error with a rate of $\mathcal{O}(n^{-\frac{1}{d_0}})$. The paper builds upon the work of Dasgupta and Tosh [2020], which is cited in the paper.
strength_weakness: strength_weakness: - The contribution with respect to Dasgupta and Tosh [2020] is very marginal, and many of the ideas come from that work.

- In practice, other methods like random forests seem to perform better than the proposed method.

- It is not mentioned in the paper whether this is the best theoretical work with this rate of convergence.

- When data lie in a $d_0$-dimensional manifold, the convergence rate again seems exponentially slow with respect to $d$. Although this limitation is mentioned in the paper, I think it is a weakness.
questions: questions: - I think in line $42$, $\mathbb{P}(y=1 \vert x)$ should be $\mathbb{P}(y=1 \vert C_j)$.

- In line $537$, what is $\nu$?

- The proofs in lines $536$ to $542$ are very unclear, and there are some claims in these lines which I think need mathematical proof.

- I think there are some inconsistencies in the notation of the proof of Lemma $3.5$ with the main body of the paper; please correct these.
limitations: limitations: The limitations are addressed in the paper.
paper_summary: paper_summary: This paper addresses how to use expand-and-sparsify techniques to non-parametric classification. More specifically, it uses expand-and-sparsify on the test data point $x$ and then use the response regions of $x$, which are the sets of training data sharing same activation coordinates as $x$, to serve as the neighbourhood of $x$ and then predict the label $y$. It proposes two types of sparsification algorithms for this problem. The first algorithm chooses the $k$ largest values of the higher dimension that $x$ maps to. The authors proves the convergence rate of this algorithm and shows that it is minimax-optimal. The second algorithm chooses the empirical $k$-thresholding for sparsification. Unlike the first algorithm, the authors assume the matrix $\Theta$ which maps $x$ to higher dimension to be multivaraite Gaussian. The authors then prove that the second algorithm is also minimax-optimal. Finally, the authors empirically show the performance of algorithm 1 and compare it with KNN and random forest under different dimensions ($m$).
strength_weakness: strength_weakness: 1. typos: line 137, $\{(x_1, y_1)\}_{i=1}^n \to \{(x_i, y_i)\}_{i=1}^n$. line 348: should be \textit{performance of our proposed classifier}? line 380: Big Oh changes to Big $\mathcal{O}$?
2. The motivation and the use cases of the problem is not addressed, why is it necessary to use expand-and-sparsify in non-parametric classification and if it it used, in which scenarios will this help?
3. The datasets used in the experiments are not explained and there is no experiments for algorithm 2 and different values of $k$ for the sparsification.
questions: questions: 1. Is it possible to compare and contrast the two algorithms and specify which algorithm is better under different scenarios?
2. Why the performance of algorithm 1 in the experiments increases with m but the other methods are the same when m increases?
limitations: limitations: The motivation and applicability of the techniques used in the paper is not specified and the experiments only show the performance of the first algorithm.

Comments: title: Invitation for comments and clarifications
After Rebuttal
comment: We greatly appreciate your positive feedback. We will incorporate the clarifications into the revised version of our manuscript. Should there be any further questions or clarifications we can offer, please do not hesitate to let us know.
We greatly appreciate your positive feedback. We will incorporate the clarifications into the revised version of our manuscript. Should there be any further questions or clarifications we can offer, please do not hesitate to let us know.
We sincerely thank the reviewer for increasing the score, we will integrate the clarification from the rebuttal into our revised version. Should there be any further questions or clarifications we can offer, please do not hesitate to let us know.
Dear Reviewer,

We greatly value your feedback and have added motivation for the setting of our paper and algorithm 1. To ensure that we have properly addressed your concerns, we would greatly appreciate it if you could kindly review our responses and provide any further comments or questions you might have. We are looking forward to engaging with you before the discussion period ends.

Thank you for your time and consideration.
We thank the reviewer for acknowledging that our answers are reasonable. We apologize that the motivation of the algorithm and the setting are not clear. Let us try to argue about our motivation. 

In recent years, it has been observed that a striking neural architecture appears in the sensory systems of several living organisms, which essentially is a transformation from a low-dimensional dense representation of sensory stimulus to a much higher-dimensional, sparse representation. This has been found, for instance, in the olfactory system of the fly (Wilson [2013]) and mouse (Stettler and Axel [2009]), the visual system of the cat (Olshausen and Field [2004]), and the electrosensory system of the electric fish (Chacron et al. [2011]). 

For example, in the olfactory system of Drosophila  (Turner et al. [2008], Masse et al. [2009], Wilson [2013],  Caron et al. [2013]), the primary sense receptors of the fly are the roughly 2,500 odor receptor neurons (also known as, ORNs) in its antennae and maxillary palps, which can be clustered into 50 types, based on their odor responses, leading to  a dense, 50-dimensional sensory input vector. This information is then relayed via projection neurons to a collection of roughly 2000 Kenyon cells (KCs) in the mushroom body, with each KC receiving signal from roughly 5-10 glomeruli. The pattern of connectivity between the glomeruli and Kenyon cells appears random (Chacron et al. [2011]). The output of the KCs is integrated by a single anterior paired lateral (APL) neuron which then provides negative feedback causing all but the 5% highest-firing KCs to be suppressed (Lin et al. [2014]). The result is a *random* sparse high-dimensional representation of the sensory input, that is the basis for subsequent learning.

The primary motivation of this paper is to study the benefit of this type of naturally occurring representation, namely expand-and-sparsify representation  (EaS for short) in the supervised classification setting. In our setting, given a dense vector $x\in \mathcal{S}^{d-1}$ on unit sphere, we first obtain high dimensional transformation $y=\Theta x \in \mathbb{R}^m$, where $d\ll m$, by multiplying $x$ with a random projection matrix $\Theta$. Following this, we obtain EaS representation of $x$, which is a $k$ sparse $m$ dimensional binary vector, by setting (activating) the largest $k$ entries of $y$ to 1 and the remaining entries to 0 (suppression). It turns out that all the examples $x\in\mathcal{S}^{d-1}$ that set the $j^{th}$ bit, for any $j=1,\ldots,m$, to 1 in their respective EaS representations can not be located too far. In fact, the diameter of the ball containing these points can be made small by appropriately choosing large $m$. Thus, we can estimate the average conditional probability of these regions using labeled data. Given any $x$, we can estimate the conditional probability $P(y=1|x)$ by taking the average of conditional probability estimates over $k$ regions corresponding to the $k$ non-zero bits in the EaS representation of $x$. Once we have such a conditional probability estimate, comparing it with $1/2$, we predict the class label in the binary classification setting. This is precisely the intuition of our algorithm 1. It turns out, that this proposed classifier admits the form of a locally weighted average classifier and can be analyzed using the ideas from non-parametric statistics as detailed in section 3. Alg 2 is a bit more complicated and is analyzed in section 4.

**If the paper is accepted we will have one extra content page and if you are satisfied with the motivation and setting presented above, we can summarize the above discussion in the camera ready version.**

Wilson [2013] : R. Wilson. Early olfactory processing in Drosophila: Mechanisms and principles. Annual Review of Neuroscience, 36:217–241, 2013.

Stettler and Axel [2009]: D. Stettler and R. Axel. Representations of odor in the piriform cortex. Neuron, 63:854–864, 2009.

Olshausen and Field [2004]: B. Olshausen and D. Field. Sparse coding of sensory inputs. Current Opinion in Neurobiology, 14:481–487, 2004.

Chacron et al. [2011]: M. Chacron, A. Longtin, and L. Maler. Efficient computation via sparse coding in electrosensory neural networks. Current Opinion in Neurobiology, 21:752–760, 2011.

Turner et al. [2008]: G. Turner, M. Bazhenov, and G. Laurent. Olfactory representations by Drosophila mushroom body neurons. J. Neurophysiol., 99:734–746, 2008.

Masse et al. [2009]: N. Masse, G. Turner, and G. Jefferis. Olfactory information processing in Drosophila: review. Current Biology, 19:R700–R713, 2009.

Caron et al. [2013]: S. Caron, V. Ruta, L. Abbott, and R. Axel. Random convergence of olfactory inputs in the Drosophila mushroom body. Nature, 497:113–117, 2013.

Lin et al. [2014]: A. Lin, A. Bygrave, A. de Calignon, T. Lee, and G. Miesenbock. Sparse, decorrelated odor coding in the mushroom body enhances learned odor discrimination. Nature Neuroscience, 17(4), 2014.
Thanks for the authors' reply, the answers to questions 1 and 2 are pretty reasonable. I still feel the motivation is not clear for the algorithm and setting proposed by the paper, but I have bumped my score to 5 as the main contribution, as specified by the author, is to provide a novel framework and a theoretical guarantee.
I thank the authors for their answers. They addressed my questions, so I increased my score accordingly.
I acknowledge the author's response and will retain my score. Thanks!
Thanks for the reply. The authors have addressed my questions. I will keep my score.