Non-parametric classification via expand-and-sparsify representation
Authors: Kaushik Sinha
Venue: NeurIPS 2024 poster (2024)
Keywords: non-parametric regression
non-parametric classification
expand-and-sparsify representation
universal consistency
minimax-optimal convergence rate
Primary area: other
TL;DR: Propose algorithms for non-parametric classification via expansion-and-sparsify representation and prove that the convergence rate is minimax-optimal.

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.

Non-parametric classification via expand-and-sparsify representation
Kaushik Sinha School of Computing
Wichita State University
Wichita, KS 67260
kaushik. www.sssichaaiaitaaamm.oaa edu
Abstract
In expand-and-sparee (EaS) representation, a data point in Sd is first randomly mapped to higher dimension R" where m > d, followed by sparsification operation where the informative & & m of the m coordinates are set to one and the to zero. We propose two algorithms for non-parametric classification using such EaS representation. For our first algorithm, we use wimners-take-ole operation for the sparsification step and show that the proposed classifier admits the form of locally weighted average classifier and establish its consistency via Stone's Theorem. Further, assuming that the conditional probability function P(y = 1/x) nT(x) is Hölder continuous and for optimal choice of m, we show that the convergence rate of this classifier 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 do < d. we show that the convergence rate of this classifier depends only on dg and is again minimax-optinn opptimal... Empirical evaluations performed on real-world datasets corroborate our theoretical results.
1 Introduction
Given training set .i, In of size and test point x sampled i.i.d. from distribution μ over some sample space X' C Rdd, the basic idea of non-parametric estimation (e.g.. density estimation, regression classification) is to construct a function z + fa(x) fn, Ti...., Fn) that approximates the true function f (which could be a densittyiegressionlllasiiciii appropriate) as oo Tsybakov (2008). For any E X, (1) typically depends on small subset of the training set lying within a small neighborhood of (thus close to) r. For example, in case of k-nearest neighbor, (2) depends the A points from the training set that are closest to in case of random forest, for each tree constituting the forest, fn. (x) depends on the points from the training set that are routed to the same leaf node which x is also routed to; in case of kernel methods, fo (x) depends on the points from training set defined by an appropriate kernel. this paper, we propose a new non- normmarretrric classification method where, for any 8dd1, the appropriate neighborhoods are obtained using expand-and and sparsify (EaS) representation of x.
function as
On high level, dimensional dense representation of sensory inputs to much higher-dimensional, sparse represen- tation. Such representation has been found, for instance, in the olfactory system of the fly (Wilson) 2013 1) and mouse (Stettler and Axel (2099), the visual system of the cat (Olshausen and Field 20044), D, and the clectrosensory system of the electric fish (Chacron al. (2011]). For example, in the olfactory system of Drosophila (Turner et al. (2008), J Masse et al. 2009 Wilson (2013), Caron
andudd--dd-parsfffy representation is essentially transformation from a low-
et al. (2033). the primary sense receptors of the fly are the roughly 2,500 odor receptor neurons
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(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 given type converge on a corresponding glomerulus in the antennal lobe; there are 50 of these in 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% highest- firing KCs to be suppressed (Lin al. [2044). The result is random sparse nigh-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 mapping from the d-dimensional unit sphere S to {0. 13m,, m > d, where a data point x & mension Hn using random projection matrix O and is followed by sparsification opera- tion, where the informative & < m of the m coordinates of the resulting vector Or E R" are set to one and the rest of the coordinates are set to zero. Rows of @ are typically drawn independently from some distribution v over S or Rd. Let Cj.J = 1.....Ph m, be the set of all examples from the input space X C S whose jth coordinate in respective EaS representations are set to 1. We call Cj the response region of 02 (the jth row of +). Note that for any I E X. there are activated response regions corresponding to the k non- zero bits in the EaS representation æ. These k activated response regions serves k neighbor- hoods of æ for our proposed non non-parametric clas- sifier, where, for any x E X' and each activated response region Cj. we estimate Pr(y = C( expected value of y when is restricted C2 and take their average to be the estimate of Pr(y 1|r).. In toy example, we visually show the EaS representation and the activated response regions C of a data point in Fig. [ Comparing whether this conditional probability estimate exceeds 1/2, we predict the class label of y. In particular, we present two algorithms us- ing different sparsification schemes and analyze their theoretical properties.
- is first randomly mapped to higher di-
Expansion via random projection
Sparaifiation
C5
C7
C12
C10
C1
Figure 1: Top: A point R² (coordinate-wise values are different shades of gray) and its projec- tion y Oz E 1R (coordinate-wise values are different shades of red). The sparsification step sets the largest values of y to I (black squares) and the rest to zero. Bottom: Activated response regions Cj. Cj. (z red dot), are shown using different colors. The points from the train- ing set that intersects with these activated response regions are shown using black dots.
One may find similarity between our proposed algorithm and a random forest classifier for any x X, activated response regions Cj. Cj. may be interpreted as the leaf nodes (containing æ) of decision trees in random forest. However, unlike random forest, we can not simply increase (number of trees) with- out changing other crpperpparametet (such as m) hoping to achieving better prediction perfor- mance. Therefore, even-though the consistency settings Biau et al. [2008), Scornet et al. [2015), not be applied for our theoretical analysis.
property of random forest is studied under different Scornet (2016), Tang et al. [2018). those ideas can
We summarize our contributions below:
We present an interesting connection between porramamttiic estimation and EaS represen- tation, and propose two algorithms for non- con-maraettiic classification via EaS representation, and present empirical evaluations on benchmark machine learning datasets.
For our first algorithm (using W-AA sparsification), we establish its universal consistency and prove that it achieves minimax-optimal convergence rate that depends on dimension d.

---

When data lie on low dimensional manifold having dimension do < d. we present second algorithm (using empirical k-thresholding sparsification) and prove that its convergence rate is minimax-optimal and depends only on do-
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
2 Related work
Non-parametris 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-par paramettrric literature, it is typical to estimate the regression function r7(x) = [E(((z) from data, and use the resulting estimate 7h. (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, k- nearest neighbors, and kernel methods Györfi et al.] 2002). Devroye et al. [996]. Under mild conditions, different variations of random forest methods are also known to be consistent [iau et al. 20088 Scornet al. [2015). J. Scornet [2016] Tang et al. [018]. Under the assumption that the regression function 7(x)) is Lipschitz continuous, the 1.2 error of the regression estimate of histogram convergences at a rate O (n-1/(4+)) (Theorem 4.3 Györf et al. (2002) the L2 error of
the regression estimate of the kernel method convergence at rate O (nn 17(42)) (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 (n=22((4+) (Theorem 6.2 Györfi et al. )2002). ). For random forest. Gao and on the convergence of pure random forests for classification, which was be improved to be of Onn-1(((6)) (1/(33.8774+2) by considering the midpoint splitting mechanism. They introduced another variant of random forests, which follow Breiman's s original random forests but with different mechanisms for splitting dimensions and positions, to get a convergence rate Onn-1/(d: (In (nnn) /dd+2)) which reaches the minimax rate, except for a factor (In)))/ ((d+2).
Zhou 2020] established finite-sample rate O(n O 1)(6
For Eas representation, when v is the uniform distribution over S and the sparsification scheme is a --winalrs-take-alll (K-WTA) operation that sets the k largest entries of a vector in IT' 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 - IR in the Lox. norm, where the error decays exponentially slowly with d. Further, they showed when the data lie on a low dimensional submanifold of 8 having dimension do < 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 dg. A different Eas representation, where the projection matrix is 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-ar locality sensitive hashing (LSH) based techniques (Gionis et al. (1999), ). Andoni and Indyk] [2008), DDtar et al. (2004). Such Eas representation has also been used to summarize data in the form of bloom filter, termed as fly bloom filter (FBF), and has been successfully used in solving the novelty detection problems in Dasgupta et al. [0188 and
classification problem in Sinha and Ram 2021 Ram and Sinhal [221 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| [2000] 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
3

---

2020] for function approximation result assumed that the coordinate-wist thresholds were known. We make no such assumption and explicitly describe how to compute such thresholds from data- resulting 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 n)()) = 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 construction similar to EaS, however the choice of random directions there are chosen using a kernel function that measures 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 to recover sparse vector given random projections to it, while random projection is used to generate a sparse representation in case of EaS.
3 Algorithm 1
In 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 & N, we use [R]] to denote the set (1....,k) kj. ..........
Algorithm Training set Dn = {(x,, 8)))=1 C
S x {0, 1}. Projection dimensionality m
N. k < m non-zeros in the EaS representation, random seed R, and inference with test point æ E Sd-1
For any vector v, we use the notation v(v] to denote its jth coordinate value. We use S denote the d-dimensional unit sphere and B(x, r) to denote a closed ball of radius r centered at a. We use to denote indi- cator variable such that for any boolean variable A, [[[A] is I if A is True, and 0 otherwise. We consider the binary classification setting, where the instance space is X' C Sd-1 and the output class label is y {0, 13. Let μ denotes the measure on X' and let X' - [o. 1]. defined as (²)) = Pr(y- 1|zz), represents the conditional probability distribution. Then, the joint probabil- ity distribution on X' x ) is completely defined by and 17. Let {(x;, y: } be a training set of size sampled i..dd. from f x 17. Due space limitation, proofs of all our results (organized section wise) are deferred to the Appendix.
Dn. SeinnEsCCaassifeee (De k, R) Sample O with seed R
Initialize wiil, ct[i] < 0, vi E [m]
for (x, S do
eas + h1 (I)
w|i + wlil + y, e [m] eas
ctl + ctli +1, Vi E [m] eas
end
wel w/jl/ct(i). Vi E [m]
return O, w
end
InferEaSClassifiers θ w) eas < (x)
return T((eas w) /k: 2 !
end
For x E Sd-1, the EaS representation of xr that uses k-WTA sparsification step, is given by the function h1: St-11 + {0, 1) defined as, (1(2) = I'x(Oz).
(I) where is a m x d random projection matrix whose rows 01.....,, 9m are sampled i.i.d from the uniform distribution over S and I, R - {0, 1)"H is the WTA function converting a vector in R. to one in (0, 1mm by setting the largest k & m elements of Ox to 1 and the rest to zero. For any j E [m], let C2 = fa X' []]=) = 1). We note that the subsets (response regions) C1,...; C... does not form a partition since they can be overlapping. We summarize our first algorithm for binary classification using h in Alg. | During its learning/training phase, a vector w E [0, 1 summarizes the average value over m response regions C₁,j E [m] using the training set. In particular, wlj].j E [m]] learned during the training phase precisely given by
El Mal E C₁] Σ
iJ =
(2)
[0: Cj]
Using foor any x E X, we further define
(xx) = Σ i j=reC'
(3)
W

---

During the inference phase, for any test point I, Alg. I first computes (w h1 (x))/k, which is an average of average y values over response regions {c (x) = which can be interpreted as an estimate of the conditional probability n(x)) and is precisely the quantity fy(x;) given in (3). Alg.
I thhen makes its prediction based on whether f(()) greater than or equal 1/2. We can rewrite this conditional probability estimate follows.
f(x))
h1 (x) k
Σ JIREC,
wbi
1 b
Σ J:ZEC;
iJ
Σ jizECy
Σ i= y C₁] E I[ E Cy]
k
I E c
E 1ax E Cyl
Y1
(z))t
(4)
i=1
JuEEC
1=1
(x))
Using viewpoint 4). Alg. 1 can be interpreted "plug-in" classifier Devsrof et [1996] where prediction is based on whether the estimated conditional probability vj exceeds 1/2 or not. In particular, classifier in Alg. can be represented as g : X -> {0. 1) described as
g(x) = {o. if 2 1/2.
(5)
otherwise.
In comparison, the Bayes optimal classifier g. : X + {0, 13 is defined
(.(x) = - 11 if nf)) 2 1/2.
(6)
00 otherwise.
In equation 4 the weights (x) Wn.i F1. .nn) E depends on 21, 21,..., In- Next we show that for sufficiently large sum of these weights is 1. Therefore, is simply a weighted average estimator of y and is non-parametric classifier Devroye al.] [996].
Lemma 3.1. For any x E X, suppose n sufficiently large such that each j satisfying
2n nc, * 0 for
Cj. Then, Ex= (n,((x)= 1.
Indeed, we show in Lemma D.7 (in the Appendix), that for any x E X, whenever n + oo and m² 0 as oc, (x) 10........ 3 CCl -> for all j such that x E Cj-
3.1 Consistency Algorithm
In this section we prove that Alg. is universally consistent. We start with the definition of consistent and universally consistent classification rule Devroye et al. [1996]. Let D, = {(21, 81 ... ((In, }n)} be training set sampled i.i.d. from certain distribution of (z, y) and let 9n X - 1} be classification rule Iearned using Dn. Then In is consistent (or asymp- totically Bayes-risk efficient) for certain distribution of (ær, y) if the expected error probability EL, = Pr (g,(x, D.,) + y} - L as n - oc, 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 (z. y). is well known that general theorem by Stone Stone [1777] (presented below) provides a recipe for establishing universal consistency of any classification rule of the form
(x) = f1. if fz))) 2 1/2,
(7)
0, otherwise.
based on an estimate (x) of the conditional probability f/xx), satisfying The (n)) E (n, where weights (x, Wn, (2,, T1, Fn) non-negative and E (n,((x) =1
Theorem 3.2. [Stone's 's Theorem (Theorem 6.3 [Devroye al. 19961)] Assume that for any distribu- tion of x. the weights satisfy the following three conditions:
(i) There is constant such that, for every non-negative measurable function f sat-
isfying Ef(x) < DC, E ( Wnii (2) I cEf(x). (ūi) For all a > O.
limn-s00 E. (E Wi,n (x)
= 0. (iii) lim (maxi (x)) 0.
Then In is universally consistent.
5

---

Since we have already established in the previous section that the classification rule given in Alg, admits the form given in ( conjunction with (4) and Lemma 3.I we are ready use Theorem
|
3.2 to establish universal consistency of Alg. We state our consistency result below.
Theorem 3.3. Let (kin) and (vT.)) be increasing functions of n. and let (6n) be a decreasing function of n. satisfying limn- On 0. Then the classification rule using Ea$ representation ① given in Alg. [ thhat admits the form given in (5) is universally consistent whenever the following conditions
hold:(i) Sum -> as n > 50, (ii) log(1 11gm1/6m)) + as n. + oc and, (iii) + as n - 00.
Once and k are fixed, for any x E X, there are (** possible subsets of A indices, from the m
possible indices in the EaS representation, that by (ar) can set to 1. For i E (I,.... {. let (i) represents the set of indices in the tth subset and we let C = {ar X h (x)[s]] 1, Vj E a (i)) to denote the set of instances whose EaS representation precisely sets the indices in oii) to 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.
For any E {1..... (T) C C3 ii) [CC forms partition of X. iii For any j E [m], C = U iv) For any j E [m], μ(C,) = ((C)).
Lemma 3.5. Let d 2 3 and pick any O < 8 < 1. There is an absolute constant co > 0 such that the following holds. With probability at least 1 6.
k + cold m log(1/6) +
max (iamm(C)) 8 JE(m]
m
In particular, ifk 2 co log + log(1/5)) then, maxjelm) (C)) S
2k
3.2 Convergence rate of Algorithm 1
While the consistency result established in the previous section provides the behavior of Alg. D 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. given in (5) and the definition of Bayes optimal classifier in (6). it is easy to see that how well the prediction of Algorithm
[ relates to the prediction of the Bayes optimal classifier will depend on how well (z() approximates (z)).
Recall that for any x X, woint-wise error probability or risk of the Bayes optimal classifier is
defined as (x) = Pr(g"(r) # y/æ) = min(n(2), - n(x)} [Devroye et al. 1996). Taking expectation over æ, risk of the Bayes optimal classifier L any plug-in classification rule (x) defined in (7) that uses conditional probability estimate Th
(min(n(x), 7y ()) Now, for
using training data D,,, the excess Bayes risk is given by the following well known result (Corollary 6.1 of Devroye et al. [996].
Lemma 3.6 (Devroye et al. 1996). The error probability of classifier go (x) defined in 7 satisfies
the inequality: Pr (gm(z) * D,) - L s 2E,
(00)))mn())) mm (In(=)-nn(())
Dn) Pn).
Taking expectation over D,,, the above lemma immediately translates to Pr(ga(1) + v) - L S 2E,,,, (1v(x) nn (x)])
(8)
Therefore, in order to establish convergence rate of Alg. following Lemma 3.6 and S to bound expected value of nīxx) n(=)). Towards this end, first extend 7 defined over points x E X' to over measurable sets A C X with ((A) > 0 as follows:
and
we need
((A)= = (AAA) / (()))(d))= 1
1
((AA /
Pr(y=1l))((d)==Pr(y==
A)= E A) (9)
Thus, 1T(AA) is the probability that y = for a point chosen at random from the distribution J restricted to the set A, or in other words, it is the expected value of y when is restricted to the set A.

---

With this definition, we introduce an intermediate quantity
nf(x) = k JanECs
Σ f
(10)
where, fo defined as,
1 7 pL(C)) Jc, ((z)u(dz)= (C()
/
(1I)
((x) n(X)] I Es, D., lñ(x) - []x]] + E..D, D. [7(x)- - n]x)],, and we show how individually bound each term on the right-hand side of this inequality next.
Using triangle inequality, this allows us to write: D.. ((xx) - -n(x)] = Br.
Remark 3.7. Note that, once m and l 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 D. l+()) - π(z)
Note that there is inherent randomness in proposed algorithm associated with the choice of θ In particular, the response regions Cj are random quantities that depend on the choice of O In this section, we fix @ and conditioned this, we bound E,,D, D., lf(xx) - [(x)). This ensures that for any 5 > O, the same bound holds with probability at least - 8 over the choice of O.
Lemma 3.8. Fix any O Then we have, De. f7(x)]
Sketch of proof: From the definition of ff(r) and πī(x) given in 3 and (1)) and applying Jensen's 's inequality, crux of the proof is to focus on the expected value of the random quantity
1 Ejsec,
E Wcll,ec - r(C,)) Note that, for E [m]. Ei Ia. Cý] = (Cn)(C)) is the Lisi Ip,E,,
number of the points from D, that fall in Cj. where nn (Cz) is the empirical probability estimate. We bound the quantity of interest in Lemma 3.8 sum of two quantities corresponding to the following two cases:
Case 1: when un (C,) 0. Using the notation 0/0 0, the quantity of interest becomes 1 E'see, (C)))[[ Lemma 3.4 show in Lemma E.3 that the expected value of the quantity of interest at most xkke
0l). Utilizing the properties of the response regions established in
Here the quantity of interest becomes El (wi-n(C (C M[, (C,) > 0]. Conditioned on 2. we first show in Lemma F.T that expected value (w.r.t. y1.-..,bh Un.) of this quantity becomes at most Next, conditioned on . and utilizing the properties of the response regions established in Lemma 3.4, we show in Lemma E.2 that expected value (w.r.t. x) (CC.))np
Case 2: when nun (C₂)
$ Ejaec
(C,)
TE Ejzec, Mip (C))
Tipaat. )=0)
of this quantity is at most 1 -
Finally, using standard Binomial bound (Lemma E.4 we show that expected value (w.r.t. .1,..., ,.,) of this quantity at most 2kn
(Cn((C)))
3.4 Bounding E2.D,, (m( n)(2)
In order to bound the expected value of 17(x) - -n))) we need to impose certain smoothness condition on 77. We consider general form of smoothness, known as Hölder continuty for 17.
Definition 3.9. We say that 1) X + [0, 1] is (L,3) smooth if for all x, x' E X, we have (n(x))
7(>')] < || =
Using Hölder continuity assumption above, we first show the following:
Lemma 3.10. Suppose 7 is (I, smooth. Then, supzes In(x:) (x)) & L-max (diam(C,))
We have already shown in Lemma 3.5 how to bound the diameters of Cj. Combining these two results we have
7

---

Lemma 3.11.
Let d 2 3 and pick any 0 < 6 < 1. Assume to be (L. 8) smooth. There is an
absolute constant Co 0 such that the following holds. If k Z coldlogm m log(1/))) then with
probability least 6. D. [(x) n(x)] &L
Combining Lemma 3.8 3.1 and 3.6 we are present the main result this section.
Theorem 3.12. Let D,, (24, W)) C X {0, 1 be the training data and consider the EaS and pick any 0 < < 1. Assume to be (L, () smooth. There is an absolute constant cu > 0 such that the following holds. If 2 So(d + log(1/6)) then with probability at least
representation given in (T. Let
over the random choice of θ,
Pr(g(#) + L' S2
m kn
8L
2k m
Corollary 3.13. In Theorem 3.12 set m = kn (0 Then, with probability at least 5, over the choice of O
Pr(g(x) + v) I'- = = (n_ert(e-1)
Remark 3.14. Since X' C. S the effective dimension in our setting is d' = (d and the convergence rate of Corollary 3.13 can be rewritten as (ni 2848' which minimax-optimal for plug-in classifiers under the assumption that 17 is (L, 3)ssmooth [Audibert and Tsybakov, 2007
3.5 Inability adapt to manifold structure
In Theorem 3.12 we derived the convergence rate of the classifier presented in Alg. by bounding
Eg (x) [z),, 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 low dimensional manifold having dimesnion do < there exists smooth rj such that
the quantity Ez,D, In(x) - fix=) decreases at a rate no faster than n कमं, To prove claim, we assume data to lie the following one-dimensional manifold:
X = {(21, I2, 0, .,.,,
0) E Rd ④ + x3 1}
(12)
We further assume that = 3 = which implies that 1j is L-Lipschitz from the definition of (L, --smmontssss Our lower bound result is as follows.
Theorem 3.15. For any d > 3, let imput space X1 be the one-dimensional sub-manifold of Ra given in (1). Take and 3 Suppose the random matrix has rows chosen from distribution that is uniform over S Then there exists a -Lipschitz function rj X1 - [0, 1] such that the following holds with probability at least 1/2 over the choice of
Ex,D.(1(x)) f[x)] = Ω (n -
4 Algorithm 2
In this section we present an alternate EaS representation and an associated classification algorithm that adapts intrinsic dimension de when data lie low dimensional manifold with dimension dy & d. Here, we assume that the rows 8,, ė E [m] of matrix are sampled i..dd from a multivariate Gaussian distribution (0, 1/v denote by v. where La is x d identity matrix. This EaS repre- sentation is denoted by h2 : X + {0, 1)mh, where for any point x E X' the jth coordinate of hy (x) set to 1, given in (14), using data dependent threshold T. In particular, given training set of size 2n sampled from (H, 17), using the first half of it, namely, D', { V),..... (I (. }.
define Ta RRd -> IR to be: Tn (0)=
1 n
T2
k m
E 110
(13)
IInttedd of representing the training set to be Dz. {(x,, y. ) for notational convenience, we represent its first half as D', {(2), vi and the second half as D. = [(T; p:) D', is only used to compute empirical thresholds in [3 and therefore, could unlabeled data sampled i. from p for this purpose.

---

h2 (2(2)[1 1 22 [8(()
(14)
We call the sparsification scheme given in region Cj is defined as:
For j E [m], the jth response
C -
E
(15)
Using the second half of the training data, namely D, = {(.1.1))..... (In; Un)] average y values over different Cj are estimated and summarized in vector w in the same way as in Alg. implying that w = ni Vj E [m], where fi is given in 2 This completes the training phase of our proposed
algorithm summarized in Alg. 2
The inference phase of Alg. iis slightly different from Alg. | While EaS representation using l2 not k-sparse anymore, we show that for large enough sample size, with high probability, it is at least k/2-sparse and most 2k-sparse in expec- tation (see Lemma F.T in Appendix F). Let / be an integer passed as an argument to Alg. For any x E X, let (x))
Algorithm 2 Training set
D'a {(a), v()) Dn {x y1) }i= C X'x {0.1}.
Projection dimensionality m E N, integer l < m. integer I, random seed Rt and inference with test point E S
TrainEaSClassiiierr D,, D', k,,, Sample θ with seed R
C and we define A,(x) to be the set containing the indices j E [m]] such that 03 is one of the / closest points to æ from (xx). To make an inference for any * E X, Alg. 2 first computes (eās w)/t / and makes it prediction based on whether this quan- tity is greater than 1/2. Clearly, (eas w)/t is the average of w[i] for j E A((z) and therefore. the conditional probability estimate (1x)) of Alg.
(0)
Initialize w(i), ct(i + 0, vi E [m]]
for j E [m]] do | Compute Ty (0,) using 13 and D
end
for
(I, E Dn do eas + (2(2)
w[i] + wlil [ + y, V [m] eas =
ct[i] + ct(i Vi E [m] eas -1
end
2 can be represented as,
wli //tl/ct((] Vi E [m]
-(=)=;> ; 9 E A.(x)]
return θ, w
-
(16)
end
InferEaSClassifier (2r, w,
Remark 4.1. Note that hi and h2 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 0, may not be one of the closest ones to any data point. Thus, many of the 8 will be unused. This prob- lem is avoided in hy, where every 8 is used but the respective response region Cj may not be local to the manifold. For this purpose need to identify "good" projection directions. Later in Lemma B.4 we show that, for any ó >> O, with probability at least 25 over the choice of θ and D', the number of "good" projection directions is linear in k.
eas <- 13 (a:)
O f- [0: : h2 [i] = 1}
eâs < eas
eās + 0, Vi E [m] :i A((x)
return l[(eãs w)/t 2
end
Due to space limitation, manifold assumptions and other important details of analysis of Alg. 2 are presented in Appendix [ and we present the main theoretical results below.
Theorem 4.2. Let D, = (1)ty:)); U D', = (a,, vf) C X x 10,1} be the training data low dimensional manifold satisfying manifold assumption presented in
where the data lies section B. and suppose the EaS representation is given as in (14). Pick any 0 < < 1. Assume rj to
be (L, B) smooth. If k 2 da (n(mmm/)), where da a constant that depend on then with probability
at least 1- 1--2 26,
(v
2m Oakn + 4L
2k
40
Pr(g(x) + LL 52
Voakn
Ci
where dgg is a constant that depends on d.
do
Corollary 4.3. In Theorem 4.2 setting m kn 20440 ensure that with probability least 8.
Pr(g(z) + v) L'
Remark 4.4. The convergence rate of Corollary 4.3 depends only on dn and is minimax-optimal for plug-in classifiers under the assumption that 17 (L. 3) smooth [Audibert and Tsybakov 2007

---

mnist35
fmnist24
segment
wine
2.55
0.1
1est accuracy
0.11
10hh
8F
0004
0.70
Ours
0ur
002
14W
3-8
10-44
104
0500
2900
500
2500 2500
1000
2008
3000
wind
pumm8NH
cpu. ssmal
twomoons
0.14
test accuracy
0.07
3.52
0.2
0.55
Ours
0ut
1/W
1:84
10:44
1:90
104N
expansion
expansion
Figure 2: Empirical evaluation of Alg. k-NN (for = and 10) and RF on eight datasets Here expansion factor is m/d. An error bar in the form of shaded graph is provided for Alg. [ove 10 independent runs.
5 Empirical evaluations
We investigate the effectiveness our proposed method by evaluating on eight benchmark datasets, details of which are provided in appendix A We address the following questions:
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-learyy train_test__ne__t_tettettt sest_split method (80 20 split). We compare our proposed method against two non-parametric classifiers scikit-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 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
experimental results in Fig. 2 where plot test accuracy of Alg. [ K-NN (for & = 1 and 10) and RF by varying expansion factor, where we define expansion factor to be m/d. As per Theorem 3.12 set ht to be dlogg As can be seen from Fig. 2 with increasing m test accuracy of Alg. iinceessss all eight datasets and becomes comparable that of k-NN and RF for large m, thus corroborating our theoretical findings.
Conclusions, limitations and future work
In this paper, present interesting connection between non- aon-aaametric estimation and expansion- and-sparsify representation. We presented two non-pane con-paraettric classification algorithms using EaS representation and proved that both algorithms yield minimax-optime convergence rates. The convergence rate the first algorithm depends on the ambient dimension while the convergence rate of the second algorithm, under manifold assumption, depends only on the intrinsic dimension do & d. In both algorithms, the projection directions are chosen in a data- data-independent manner. One limitation of our current work is that, even though the second algorithm adapts to the manifold structure, there a large constant, possibly depending exponentially on d, involved 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 manifold structure, and the constant involved in bounding of the excess Bayes risk from above, would be independent of ambient dimension
We thank the anonymous reviewers for their constructive feedback. This work supported by funding from the "NSF AI Institute for Foundations of Machine Learning (IFML)) (F41442019844).
Acknowledgements:
10

---

References
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117-122, jan 2008. URL htt.tttttt//.o..ooo org////..oo////
1145/1327452. 1327494
Jean-Y Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. The
Annals of Statistics, 35(2):608 633, 2007. doi: 10.12140000556000000000111 URL https
//doi.org/10 1214 2244/0090050000000111111
Gérard Biau, Luc Devroye, and Gábor Lugosi. Consistency of random forests and other averaging classifiers. Journal of Machine Learning Research, (66):211552 2008. URI.http://jml
orgg/papers/vv//iauuu0 hhmml
Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute Mathematical Sciences, 1978) 2006.
S. J. Caron, Ruta, L. F. Abbott, and R. Axel. Random convergence of olfactory inputs in the Drosophila mushroom body. Nature, 497(7447):113-111 May 2013.
Maurice J Chacron, André Longtin, and Leonard Maler. Efficient computation via sparse coding in electrosensory neural networks. Current Opinion in Neurobiology, 21(5):752-760, 2011.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for the cluster tree. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010. URL https: atttps://proceedinggg http://cceediingn..uuui.......p. www.nnuuruucmm cttpsccccpaperaeeeeeee filessffeee/eeleeeee Sasaper_fileesppppe///000 pptppppppp////illlll 1534a68222aa44444422211000.03663
htc.//pppr.....eeeepprr////////. pdf
Sanjoy Dasgupta and Christopher Tosh. Expressivity of expand-and representations. arXiv 037.1.
preprint ar arXiv:2006.0374/1 2020. btatttp:///axxv.org//ttte
Sanjoy Dasgupta, Charles Stevens, and Saket Navlakha. A neural algorithm for a fundamental computing problem. Science, 358(6344)793-7966 2017.
Sanjoy Dasgupta, Timothy Sheehan, Charles F Stevens, and Saket Navlakha. A neural data structure for novelty detection. Proceedings of the National Academy of Sciences, 119(51)110933-1399 2018.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality- hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computatioonal Geometry, SCG '04, page 253-262. Association for Computing Machinery, 2004. doi: 00.11445997817.9998857 httpstts:: //t::///oiiiooo org. org//0..///. 114119977778 .997857
Lue Devroye, László Györfi, and Gábor Lugosi. Probabilistic Theory of Pattern Recognition, volume 31 Stochastic Modelling and Applied Probability. Springer, 1996. ISBN 978-1-4612. 0711-5.
D.L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1300 2006. doi: 10. (009//TT.2006.871555
Wei Gao and Zhi-Hua Zhou. Towards convergence rate analysis of random forests for classification. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9300-9311 2020.
Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. VLDB '99, page 318-529. Morgan Kaufmann Publishers Inc., 1999. ISBN 1558606157.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A Distribution- Free Theory of Nonparametric Regression. Springer series in statisties. Springer, 2002. ISBN 978-0-387-95441-7,
A. C. Lin, M. Bygrave, A. de Calignon, Lee, and ck. Sparse, decorrelated odor coding the mushroom body enhances learned odor discrimination. Nat Neurosci, ((4))559-566. Apr 2014.
11

---

N. Y. Masse, G. C. Turner, and G. S. Jefferis. Olfactory information processing in Drosophila. Curr Biol, 19(16):700-711 Aug 2009.
Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom,, 39(1):119-44 mar 2008. ISSN 0179-5376.
B. A. Olshausen and D. J. Field. Sparse coding of sensory inputs. Curr Opin Neurobiol, 14(4): 481-487, Aug 2004.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL https::/pproceeeedinngg newrgps................. cctpppp.cc.pppppppppprr.
Paper. pdf
Parikshit Ram and Kaushik Sinha. Flynn: Fruit-fly inspired federated nearest neighbor classification. In International Workshop on Federated Learning for User Privacy and Data Confidentiality in Conjunction with ICML 2021 (FL-ICML'21), 2021.
Parikshit Ram and Kaushik Sinha. Federated nearest neighbor classification with colony of fruit- flies. In Thirty- Sixth AAAI Conference on Artificial Intelligence, pages 8036-8044. AAAI Press, 2022.
Erwan Scornet. On the asymptotics of random forests. Multivar Anal., 146(C):72-83, apr 2016. ISSN 0047-259X.
1016// jmmaa. w01. 1...5.66.000 2015.
Erwan Scornet, Gérard Biau, and Jean-Philippe Vert. Consistency of random forests. The Annals of Statistics, 43(4):1766 11111766-7744 2015.
Kaushik Sinha and Parikshit Ram. Fruit-fly inspired neighborhood encoding for classification. In The 27th ACM SIGKDD Conference Knowledge Discovery and Data Mining (KDD), 2021.
D. D. Stettler and R. Axel. Representations of odor in the piriform cortex. Neuron, 63(6):854-864, Sep 2009.
Charles J. Stone. Consistent nonparametric regression. The Annals of Statistics, 5(4):595-620, 1977.
Cheng Tang, Damien Garreau, and Ulrike von Luxburg. When do random forests fail? In S. Bengio, H. Wallach, Larochelle, K. Grauman, N. Gesa-Bianche and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 4, 2018.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
G. C. Turner, M. Bazhenov, and G. Laurent. Olfactory representations by Drosophila mushroom body neurons. J Neurophysiol, 99(2):734-744 Feb 2008.
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo Openml: Networked science in machine learning. SIGKDD Explorations, 15(2):49-60, 2013. doi: 10. 1445224/ 190.2641 198. URL http::///ooi. htt.://...............1111111111 2641119
R. Wilson. Early olfactory processing in Drosophila: mechanisms and principles. Annu Rev Neurosci, 36:217-241, Jul 2013.
12

---

Dataset Name
Samples
# Features
mmist35
13454
20
fmnist24
11200
20
segment (v.2)
2310
19
wine (v.7)
2554
11
wind (v.2)
6574
14
puma8NH (v.2)
8192
8
cpu sou_smllll (v.3)
8192
12
twomoons
5000
2
Table 1: Dataset statistics
A Dataset details and computing environment
Details the eight datasets used in our experiments are listed in Table Among the eight datasets, the twomoons is a synthetic dataset generated using pakee_mone method from sklearn datasetPuve with noise parameter 0.2. All the remaining datasets are taken from the OpenMI. repository Vanschoren al. 2013). Both mnist and fmnist (fashion ondhion-we cemiiostmmist for short) 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-lean 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).
B Missing details of convergence rate of Algorithm 2 from section
In this section we present missing details of convergence rate analysis of Algorithm 2 from section Proofs of various technical results presented in this section as well as the proof of Theorem are deferred to section B
B.1 Manifold assumption
To analyze convergence rate Algorithm 2 we proceed the same was as in section 3.2 However, to take advantage of the fact that data lie a low low-dinensional manifold in analysis, make similar manifold assumptions as in Dasgupta and Tosh [2020]. The input space X' is compact do do-dimensional Riemannian sub manifold M of R contained in the unit sphere, that is M C S M has nice boundaries and that the distribution on μ. is almost uniform: formally, there exists constants CT2 C2 Cg such that for all M and for all vo (where ro is absolute constant)
cr < ((BM((, < cor
(17)
Vol Vol(BM((z))) 2 cyrdo
(18)
Here (z, B(x,r) N.
To effectively analyze the data distribution supported manifold, impose conditions the curvature by adopting the common requirement that M has a positive reach > O: that is, every point in open tubular neighborhood of M of of radius p has unique nearest neighbor in M [Niyogi et al. 2008). For each x E M, let N (x) denotes the (d - do) dimensional subspace of normal vectors to the tangent plane at æ. For each æ e M, the sets I (x) = {x + ru E Rd u E (zx), ||u|| = 1, < < p} disjoint and let Tp be their union. Let πM TT + M be the projection map that sends any point in (z) to x, its nearest neighbor in M.
hhtpss//scikii-ecam.oo//ttt "ntps://www.opemml.rgg
13

---

B.2 Bounding B..D. 17(=))
The response regions Cj.j E [m]] are now random quantities that depend on the choice of θ as well as D', used to compute individual thresholds. The quantity ffxx) given in (T6) depends on t. In this section, we fix & and and conditioned on this, we bound Ex, D.,. p, (((x)) r((=). Later Lemma B.4 we show that, for any O, with probability at least 28 over the choice of θ and D t is linear in k.
Lemma B.1. Fix any O and t. Then the following holds.
D. De.D...;,1i00 (0(x)) -7(xx)] S V tn
m
Sketch of proof: The proof strategy similar to Lemma 3.8 but requires careful analysis to accommodate the facts that Cj.j [m]] depend on the choice of D', and in (I6) has indicator function. Details are provided in Appendix
B.3 Bounding Ex, D. [+(=)) 17(=)]
Using identical proof strategy of Lemma 3.10 we have,
Lemma B.2. Under empirical k-thresholding scheme, if v is (L, smooth, then for all C U... ,...,UCm..
In(x)) - 77x)) s T. max (djam)C;))) jE(m)
Unfortunately, unlike before, all CT such that E Cj may not be local to and thus average y values in some of these Cj. may be very different from n)()). To address this, we call 0 Rd good if it lies in r p/2- Good 0, 's are close to the manifold M and are guaranteed be activated by a single neighborhood of M. Thus, for large enough if the diameters of the Cý 's corresponding to good 0, are made reasonable small then the average y values in such Cj 's will be a reasonably close of n(x) for Cj. First, for any good fj. we bound the diameter of Cj emphasizing that the response region of good 0 is local.
Lemma B.3. Pick any good f E Rd. Define A = 1|0 am) to be the distance from @ to its projection on M. Let C(f) be the response region associated with @ as defined in (15). Pick any 0 0<6 1. Then with probubility at least 1 - 8, over the choice of D' the following holds:
1/do
1/do
BM
P Tas (Ta((),
k
C C(O)
C (M),
2k
A
20ym
cmm
1/da
In particular this implies, diam (Cam)((()) <
2k
provided (2k/ (c < min(p, ro) and
satisfies n 2 * (log log (m)), where co > O is a universal constant.
Next we show that each æ E M has number of good 0, linear in with high probability.
Lemma B.4. Pick ... 0m v. There a constant d'a depending on d, for which the following holds. Pick any 0 < 8 < Set l 2 da In(m/8). then with probability at least 1 28 over the choice of 02 's and D',, for every x E M, there are arkk/2 good 02 with x E C(O,) where e' and aa are constants that depend on dimension d.
Combining SeeiinggLLmmnn Lemma B.3 and B.4
we have
Lemma B.5. Suppose the data distribution is supported on a dg-dimensional submanifold M of 2 with reach 0, that additionally satisfied (17) and (18). Suppose that the rows of O are chosen from (0, Ia). There a constant Cg depending on the dimension d, and co > O, universal constant, for which the following holds. Pick any 0 d << 1. Let k. m and be chosen so that
*We note that Lemma B.3 a modified version Lemma of Dasgupta and Tosh 2020 to incorporate uncertainty associated with the data dependent threshold selection in (13). Also, Lemma B.4 is a modified
version of Lemma 7 of Dasgupta and Tosh 2020] which incorporates threshold selection uncertainty and additionally guaranteeing the number of good be linear in k.
14

---

k caln(mm/eltte (2k/(e < min(p, ro) and n 2 (com/k)(logn + log(m/6)), Then
with probability at least 1 26 over the choice of and D
2k mm
%0
sup #EX
(x))
- 4L
Combining everything leads to the main result presented in Theorem 4.2
C Various proofs from section
C.1 Proof of Lemma 3.1
Proof. Simply interchange the summation. That is,
n
I E c2) E 1x E c,l
Σ E Ua. Cy] i= Ua, E Cy]
Win (a)
Σ
Σ jiZEC;
Σ jinEO,
D Various proofs from section 3.1
In this section we present various technical results that are needed to prove our main theorem (Theorem 3.3). 3.3). Due to space limitation proofs of some these technical results are deferred the supplementary material.
D.1 Proof of Lemma 3.4
Proof. For part (i), note that if e C. then by definition, Vj E hi)), = 1 which implies Cj. Therefore, C. S (jea(t) Cj. On the other hand, if E (jea(t) Cj then he, (x)[5]
1 Vj E aii). which implies x e C.S. Therefore, C) S C.
For part (ii), take any i,j [("]], j. then aii) # a(j). Therefore, if C then & Cj. Since a was arbitrary, C n C.. = 0. Now, for any E X, since (x) has exactly & bits activated C X.
(set to I), there must exist I [(m)] such that Ct. Therefore,
For part (iii), take any x E Cy. From the definition Cj. he, (x) and therefore, x E C for any such that j (i). From part(ii) since such C+ss are disjoint and was arbitrary, the result follows.
Finally, part (iv) follows immediately from part (ii) and (iii) since Cts disjoint.
D.2 proof of Lemma 3,5
Proof. While general idea of this result appeared in Dasgupta and Tosh [2020]. we pro- vide simplified proof. Let v(r) = inf (B((zr)) We first claim that if v(r) 2 2. (k + co (dlog m + log (t))) then for every j E [m]. Cj C B(0,,r). By definition, every ball of radius r, centered at some x E X, has v-mass at least v(r). Thus, by Lemma D.I with probability least 7tth bit of the EaS representation given in (I will be activated by points within distance of 0,. Therefore, diam(C;) < 2r for all j
every I E X' will have its nearest fj's within distance Therefore, the
m, where r satisfies
2 (k + co (d m + log (1))
v(B(z,r))
m
15

---

By Lemma D.2 we can take to be the value
1/(d-1)
3vd
( + co (dlog + log (1)))
(3/4)(4-1)/2
6v (k- cn (d + log (t))) 1/(d-1)
2
v3
Therefore, we have
1/(d-1)
GVd (k (d m + log (t)))
diam(C,)
1 2
v3
1/(d-1)
(k: + co (dlogm log (+)))
< 8
where, for the last incquality, we have used the fact that d I 2 and for d 2 3 holds that 61/(d-1) I V6.
Lemma D.1 ([Chaudhuri and Dasgupta 2010). There is an absolute constant co > 0 for which the following holds. Pick any O < 8 < 1. Pick O,,..., ...... Om independently at random frodomfrom distribution on Rd Then with probubility at least
any bull B in IRd with
)))
1 7
N + co [dlogm log v(B)
contains at least k of the 0;.
Lemma D.2 (Lemmaa 12 Dasgupta and Tosh 2020 Suppose r (0,1), and is the uniform distribution over Sa- Then for any S
v(B(a, r))
1 d-1 (1 11-) (d- (d-1)/2 11/2
1
(3/4)(d-1)/2 ,
3
3vd
D.3 Proof of Theorem 3.3
Proof.
Since the weights Wh,i given in equation 4 are non-negative, in order satisfy condition (i) of Stone's 's theorem, we need to show that there exists a positive constant e such that for any non-negative measurable function f satisfying Ef(x) < co and for any n. JE' (Σ (n,((t)((ss)) cB()(x)).
Using Lemma D.3 we show that this condition is satisfied for 1.
Concerning condition (ii) of Stone's theorem, first define On 1/(d-1)
an(knn Mny 8n)
kn too (dlog m., Hogs 2,))
8
where ep is an absolute constant. Then limm- 8n =
and using condition (i) and (ii) of this theorem we also have limn On 0. Now pick any >> O. We can always find a positive integer N such that for n > N, we have > an satisfying Σn_ Wi,n (I]
for all X. Replacing k, m, and with Rin, 5n and an respectively in Lemma D.6 we have
S Ex= (Z)
E Σ
Winn (x) x1 a)
< E
Σ Winn (x) xll anl s 6n
Taking limit yields, lim E (E Wi,n (r) - Il > a)) =
Concerning condition (iii) of Stone's ' Theorem, note that
max (1) ISi5a
< E
Σ
=E
k
E
1 ECI
E 1xx E Ca(c.e)
j=EE,
k
=
Na,(o,e)
SE
(N
(19)
1=1
16

---

where, for i = I.....k, k,, we have used the notation (z )) to denote the k random coordinates of (2) that are Cj,(,,)) Now from equation 19 is easy see that lim (maxisisv wn,( 0 since oc.
and (z.0)) to denote the number of points from 21,...,. In that fall in
using lemma D.7 minigigh (2,0)) - oo in probability,
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 t satisfying B.((x) < oo and for any E (Ei= (x.((z)) < [z)), where the weights Wn, are as given in 4
Proof.
Ta, E (,)(((,,) Σ JIEEC
Wi,n (z) (wza)
=
E
-i=1 I|r E Cj}
Ix, Cj)f(a;) n
E
h
n
i=l aai E Cy)
1a, C,lf(a;) a
En
k
Ei Mar E Cj)
T
JiPEC's
Mare E C3)s(a;) 1)
Es
1
Σ
E
k
Eiz U1a E Cÿ]
JiXEC,
Sc, (on)lldn)) )
Σ
1 ((C,))
Te
LiiEc,
1 ((C,)) I flaiaaddeo)
Pr(x E c
h
JEO(S)
CT) (E
m(C,) So ((x))ulda))
p(C,) ls f(x1)a(do1) (Ea(()
m(())
5 エ
m m(C,)) ( f(x1)u(dz1) _ Σ f(z1)u(dz1) プ= (ン)((()
m(()))
c,
Σ
/ f(II)u(dx1)
_ k jEa(s)
Σ Σ (Lg s(xi)lldxs)
Jot
F=1
(sfE((s)
(T) / of
Σ Jot f(x))u(dx)) - -
f(x1)u(dx1)
& J ((ai))(da)) E(f(z)) 2 B(f(x)
where, inequality a follows from Lemma D.4 Equality follows from the following observation. In the line above inequality b. we are summing t x (x) terms. Since & x (T) = m x (m-1) and any
j E [m]] can appear in exactly (m=])) 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)
17

---

of Lemma 3.4
Equality d follows from part (iii) of Lemma 3.4 Equality e follows from the following
observation. In the line above equality e, we are summing m x appear in exactly (x-1) different subsets of of size Again noticing that m (R-1) and each a (i) has & terms it, we are simply rearranging the terms from the line above by changing
(m-1)
k-1 terms since any j [ml] can
x (*)
the indices appropriately. Finally, equality follows from part (ii) of Lemma E.4 and equality follows from the fact that æ and æ are i..d.
1 E (xLEC,) I píè, Sc, f(z))u(d11)
Lemma D.4. E EE
Proof.
1|; E Cjlf(an)
1| E Cglf(a.)
E
E 20 Cÿ] (0)
Σ
E
El=1 Mas Cj :)
i=1
1|z; Cjlf(z;)
E
1+ Ei 111 Cjl
1
nÊ
[((nec)))((1))
x
Ei=2 Im E c2
1
nL
((t)
2;
Ei=
1x E Cy]
S nFe., (TEEEEC))((T)) ( np((,) p(C,)) I f(x1)u(dZ1)
1
where, equality a follows from that fact, that if E Cj. then the term in the parenthesis does not change and I; & Cj. then the term within the parenthesis is zero, and inequality b follows from lemma D.5 since conditioned distributed with parameters (n 1) and p(C)).
and æ1, the random variable Ei (mree,) is Binomially
Lemma D.5. (Binomial bound Györfi et al. (002 Let the random variable B(n, p) be Binomially distributed with parameters and p. Then,
E
1+ 1+ B+,,pp,))
(n + 1)p
D.5 Technical results for satisfying condition (ii) of Stone's theorem (Theorem 3.2
1/(d-1)
k-t-0 (d (ot +log( 4))
Lemma D.6. Pick any 0 < 8 1 and let
where co an
m
absolute constant defined in Lemma 3.5 Then,
E
wi W (x)][lz
x|| aa| 8..
we have that with probability at least 1 1-5, diam < a forall S S m Let us define the random variable:
Proof. From Lemma 3.5
[1 E C₁5
A
[[||:: x11 x1|>>1
Di=1 T/ E CC,)
jizEC,
and the event:
A₂ (Uiiee, B(z,a))
18

---

Let Až denotes complement of the event A2. Then,
Win (x)) æ=| 21 = E Σ k
Tee E EC]
E
[11
Ei= Cy)
jizEC,
E (A1 A2) Pr (A2) + E (Ai (b)) Pr (AA5)
0 Pr(A2) + +1. =
where the inequality follows from the fact that maximum value of A is and conditioned on the event A2, value of A₁ is O.
D.6 Technical results for satisfying condition (iii) of Stone's theorem (Theorem 3.2
μ., let ji (z, ....... +) [m]] be the k random coordinates of (o)) that are set to 1. Let Ni N (a be the number of data points falling in Cj((,,)):..., Ciu(,,,) respectively, Then ever n + oo and m /n - as oc.
Lemma D.7. For any
+ oo in probability, when-
((,,)) be the random cell of the partition {C+ (+)
Proof. For any random X. let Ck k random coordinates (z, .)..... (z θ) of he, to one. Then, C+ ((2,0) = n (a(,,))) Let (1, θ) -ir,et ( be the number of data points falling in the same cell as We first show that (n, θ) in probability. Let N1, -.. (rr) be the number of points of F1........ En falling in the (%) respective cells C .f...., C (T) Let {az (1......... ... Zo. denote the set of positions of these + points. Since these points are independent and identically distributed, fixing the set S (but not the order of the points) and Q the conditional probability that x falls in the tth cell C N2((n + 1). Then for any fixed integer > O,
which sets
(r(Na( 0)<()
E
[Pr
(N
(2r, θ) 1|S,0)
E
Σ Lt
N
S (t - 1)
mm
I (t 1) m
++1 1
n ++1
which converges to zero on our assumption on Since C* (), S Cj(t,,) for / = I,...,k k, we have
(x, θ) < min min(N (=,0)): (N,())))))))) and the statement of the Lemma follows.
O
19

---

E
Various proofs from section 3.2
For ease of exposition, the notation [[[.n]] to denote 21,--- Fy and U[1.n] to denote y1, -. Un for various proof' appearing in the section.
E.1
Proof of lemma 3.8
Proof. Fix any O This ensures that Ci,.... Ou are fixed. Now,
B(j(()) 7(x)))
Bu..i......... [()(z) - 17(x))
-
(1((z) ;((x)) [
2
Exg..
Σ (îu Tb))
k
Ji
< [xp
1
Σ
(ng - - 2[1,n|
h
1
i= Y C₁]
2
E B2,0
nn(C,))
h
2im1 1|x; E Cj]
ja
1
n siml
wr; E ECgl -n(c;)
[[1,nl]
Ke juEEC
nljn(Cy (Cý)
1
1i VillT; E Cjl
22
-n(c;) [[TH) > 0]
(C))))(((( (/ =0] 4/1,ml
k
nijln(C (Cj)
j.BEC,
1
Ei=1yy (yi - n(C,)) ECJ)
= -Eapa.)
k
mpn (pn(C))
(C₁)
jiDEC,
+
Σ k
((C)HIun(C)) = [[I.m]
jiZEC'
Eim (T,T)) E C2) 2
< p..)
6
Σ
I[njun(C;) > 0] [[1.1
+ m
Ko
np (C₃)
kne
he (x)
Ei (1 ((C,))((a= E C,I)
Exgg..) ml
Ex
Byg ml
Σ
1|maun > x,
k
(C3)
kne
juEE,
Immu [ 1>0) 0]
Expp..)
Fyyr
X[1.m]
+ m
To
72/4n(Ci))
kne
J=DEC,
d
1
m
((C (C₂) > 01)
<
Exp.al
E
k
T4pa(CC (C,)
kne
Σ
((C, B
(Cp) Mippa (C₂) ())00)}
01)
m kne
4k
1=1
8
1
2p(CC))
m
m
m
m
4k
(n 1))
kne
2k(n + kne
2km
kne
kn
20

---

where, inequality a is due to Jensen's inequality. Inequality b follows from lemma E.3 Inequality
follows from lemma E.1 and inequality d follows from lemma Finally inequality follow from the observation that ninn (Cj) is Binomially distributed with parameters and μ(Ci) and by an
application of lemma E.4 The result follows noting that by Jensen's 's inequality E E(n(()) - 7(x) s
V[(((z) - 1T(x)))²
Lemma E.1. Pick m x projection matrix Q Suppose the EaS representation uses (i) mapping t and (ii) k-winner-take-e
sparsification. Let æ be sampled from i and let Dn ((11, v1), (Jn, Yn.) ) a random training set where 24 is sampled from y and yi is distributed as ((xe)) for E [m]. Then the following holds.
Ei= (M (( E [[j > ( T
&Cl) (Cp)
IImppn 0]
Bygg.n
Σ SUEEC
S
Σ J:ZEC,
Proof. Conditioned on only k of the coordinates in the EaS representation of xr are non-zero. WLOG, for case exposition, assume these k non-zero coordinate to be Ji. E [m]] Then the number of z; that falls in any such Cj where / [k], is nut, (C,,) The y, values corresponding to these z; points (there are ru,nn of them in total) are identically and independently distributed with expectation
Bly E Cn.) Pr(m 1/2; E Cji) M((x)) /
Jc,,
Pr(y: 1/2, pdxx
/
((F))(d))= = (C()
mCC Cs,
Therefore, we can write
>B (yi (C,)) E &C3
Eyp
Σ
Inmnn(CC) (Cz) > 0 F(u.m
(Cg)(Cz)
HuEE,
Bypt.n)
1 n (yi - ((x E C,.) [mpun [m
(mpn(CC)))²
Σ Ey. [3/ (ICx,)) (,,
(nemn (n1 (C²))²
Em
E Cy.llmpnn >0]
(Cp))(C))))
1=1
1
Impa (Ct,
(Cp)
where, equality is due to the following observation. For any i.j [m], i * and vi, 2y C for some E [m]] Yi and 8jj are identically and independently distributed with expectation (y,))) Therefore, the expectation of the cross product is simply:
E En.gs 1( - (n)))(())) - r(C) = Us yeB, - ((C) + + [
Ey, (Ci) + Ey,) + ( =0
Equality b follows from variance computation. In particular for any Y, im] with 2, E C for some I [m]. E [[t ( = Eyy (n)(C) + (())² (Ci) (n)) (G))²
((Ci)( 77( (i)). Finally, inequality c follows from the fact that for any E [0, 1), the maximum
value of 211 - 2) 1.
easy to observe that the final result equivalent to EjizeC, (Ina,(C,)20)
(Cn,(()))
21

---

Lemma E.2. Pick m. x d projection matrix @ Suppose the EaS representation uses (i) mapping and (ii) k-winner-take-d sparsification. Let x sampled from i and let D,, (1), (Ta, Wn)) is random training set where is sampled from μ and yi is distributed as forr) E [n]. Then conditioned on F1,..., Ina the following holds.
(nppn(C)))00) (Cn(C)))
Ey
Σ j=1
k
12 (Cp)
JiZEE
Proof.
Innun > 0 nmt (Cg)
1
Injun(Cz) > 0
Ex
Σ
Pr(x E c
Σ k
k
mpn((Cy)
JiREC'
(EE(()
u(C)) (mp)))))(C())))..)))))))))))))))
Tipna (Cn)
(Ea(((
Mm (C₂) > 0
b
(Cp
iffE((
Umpp (C2) 0
Σ
Σ m((+)
=
Tipe (Cp)
iijE((()
[(CC)L(npu (C₃) > 0]
1ij6 (Cz)
where equality a follows from part (ii) lemma 3.4 since {C+
Ti=l forms partition of X' and the Equality b follows Irom the following observation. In the line above x (T=)) and any j [m] can
definition of in section 3.2
inequality b, appear in exactly (r=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
summing & x ( terms. Since i (*T
Lemma E.3. Pick m X d projection matrix O Suppose the Ea$ representation uses (i) mapping and (ii) t-winner-take-dl sparsification. Let x sampled from μ and let D,, (1),. (In, )n)) is random training set where is sampled from and yi is distributed as ((x;)) for E [n]. Then the following holds.
E Elp.
E Er.yi
= Σ P(C,)))u,)C)))) = 0] J:ZEC;
<
m
K
nke
22

---

Proof.
Exp.a
1
E (CC 0 [(
k
J.XEC,
T((C))TTun(C))) =0f
Ex
JIZEC,
m
Expr,t
Pr(x c.t)
Σ (C)))
K (EE(()
i=1
Σ
"C =
k
1=1 (EO(1)
}
Expp..l
of ((C)) =0] Σ m(C?)
isjr((
m
((C)))((;) (U O]]
k Σ m
m Σ " -C))
P(C))CC)
nk
==1
Σ PCC
nk j=1
np(CC)e
ma(()))
< m nk j
max {
(nu(C))e
_ m nke
nk 1=1
where equality a follows from the fact that the quantity with the inner square bracket is unaffected
(2)
by the Y,s. Equality b follows from part (ii) of lemma 3.4 since {C*} Jiml forms a partition of X and the definition of in section 3.2 Equality follows from the following observation. In the line above inequality c,
summing k: (MT terms. Since k (*T) m (T-+) and any j E [m]] can appear in exactly (m=1) different subsets of of size k; equality is simply rearranging the terms from the line above by changing the indices appropriately. Inequality d follows from the fact max, (C₁) < Finally inequality e follows from the fact that sup, ze E'
Lemma E.4. (Binomial bound Györfi et al. (2002)) Let the random variable B(n, p) be Binomially distributed with parameters and Then,
1B(np
> >0]) s (n 1)p
2
B(n,p)
23

---

E.2
Proof of Lemma 3.10
Proof. Take any x E X. Then
In(x) F](2)|
n(x)=
1
Σ J.rEOs
1
Σ
(1(x)) m7(0))
1
Σ
In(x)
7g.
k
&
k
EEC,
j:zECz
1
Σ
7(x)
1
M1 ((d'))(dz))
k
m(C})
C=
1
Σ
(n(x) - (1(2 (((d)))(
k
j.rEC;
C3
Σ
1
J. (n(x) (((d))
k
(CCz)
j=
/
Σ
L|| - x' 2'113 =0'1)'dda)) u(dx')
((Cr))
Jc3 L. (ddiam(C)))
jUEE
1 Σ h
mLC)) Jc, m(dx') S L. max (di)m(C,))) je(m)
jUDEC,
E.3
Proof of Theorem 3.15
Proof. Define n :i + [0, to be a triangular function defined below: for S 2n,
0 ifA
nycoss 0, sin 0, 0, 0, ...0......00 0)
n
12
if >
Clearly, is & L-iisschitz and for k = 1, f(z) = Σド= ((,))L(rEC)) Therefore, using Theorem E.5 with probability at least 1/2 over the choice of θ,
sup xe
|n(=) - 7(x) d/' m l/ logm
where oj is am absolute constant depending on Taking expectation, with probability at least 1/2 m 1
over the choice of θ, we have, Ex (+( (X 2 di with k yields, Ex,,,, (xX) 7() V 10
logm Next, using Lemma 3.8
Using triangle inequality combining these results,
(t.p,,1(()) - x(x) = Ex,,, (n(X) T(X) + 7 n(x)
Ex,,, (x()) T)(X) Ex li(x - (X)I
W d m ml/(d11) log m
m
(20)
Ignoring the log term we see that for large enough n, the first term on the right hand side of (0 will
dominate. In particular, for n Z (m- ++ 22, we get Ex Ex - x(x >
m
To
see this (ignoring the log term), if / m S Now,
oi
M then EX In - xxx
N d
2
2
m
!/d-1) n (c +
m
24

---

In particular, setting n Tezyz
4 1+ t we have
d=3 Cd
c m 2
d-1
d-1
n2
2
Theorem E.5. [Theorem 4 of Dassupta and Tosh [2020] For any d >> let input space X1 be the one-dimension sub-manifold of E" given in (12). Take = 1. Suppose that random matrix θ has rows chosen from the distribution that is uniform over S For any 0
1, there exists X-Lipschitz, function f X1 + R such that with probability at least 1/2 over the choice of θ, no matter how the weights wi...., Win set, the resulting function f(x) Ej= WyJ[(wE;;) has approximation error al least
sup =eX
2 ca.
m!/(d-1) log
where da is some absolute constant depending d.
F Various proofs from section 4 and Appendix B
F.
Lemma and its proof
We first show that while representation using h2 not k-sparse,,or large enough sample size, with high probability, it is at least k/2 2/2-sparse and at most 2k-sparse in expectation. F).
Lemma F.1. Pick any 8 O. For k. and n, satisfying 2 com (log log ( (")). where co
a universal constant, with probability at least 1 ô, over the random choice of training set D the following holds for all j E [m]]
(k/2m) S PraNp x Tn (0,)) S (2k/m).
Proof. We start with version of relative generalization error bound, originally due Vapnik and Chervonenkis, that appeared in Chaudhuri and Dasgupta (210).
Theorem F.2. (Theorem 15 of Chaudhuri and Dasgupta (2010)) Let G be a class of functions from X {0, 1} with VC dimension d < and P probability distribution X. Let E be the expectation with respect to P. Suppose n points are drawn independently from TP; let Er denotes expectation with respect this sample. Then for any 5 0, with probability least 1 the following holds for all E G:
-min (Bn SRaVEng Eng, , B2 Bn + VBg) S Egg - Eng S min ( + Bn 3B Eng, Bn Eg
where Bn Afd (2)) (8/(8
Let 0g be the ith row of the projection matrix è and let jd be the distribution of 0, x where x is distribution according to μ. Then, for any R.
Pr Pramp (0. 2 a) = (0: x a).
Suppose zf,..., xnn are sampled independently at random from For any interval A, = [a, oo), let
2 (Aa) = Σ 10 2'J 2 a).
Consider the class of indicator functions over the intervals [a, 2o) for E R. This class has VC dimension and define B² = (log 2n + log( 8m )). Suppose μi, (Aa) satisfies the condition μi, (Aa) 2 4.3..
25

---

The bound (Aa))) -1,( S + 3 3. from Theorem F.2 yields,
7
(A(a)) S 1 (Aa) + B2 11/1411 (Aa) & (Aa) + 1 (Aa)
2 1 (Aa) 1 (Aa)
Similarly, the bound- - (Au) (Aa) 1 (Aa) from Theorem F.2 yields,
(1(A)) 2 (Aa) BV 1h 1 (An) - (4 2 p = Mr.
Combining these two bounds, we can can conclude that for all intervals Aa satisfying μe, (Aa) 2 432. with probability at least & it holds that m
7 (Ao).
2
Now if we only consider the intervals (0,)) then from 13) is clear that ja, (,,)) ) This because for any interval (.). can take (n + 1) possible values in steps namely,
0, n n...... 1. Therefore, from the definition of Tn (0,) in (3), ju, (A,,()))) + then to ensure that pt, (Ar, (0,)) m its maximum value can be most dt. 1. Therefore, the condition 2 (ATT()()) 432 implies,
k
+
2
16
log 2n + log
8mm
16 n
(log logn log log )
m
n1
n
64
16
(logn + log
m
+
58
or in other words,
63
16 (logn + log
(T) (z)).
Noting that,
k
2k
1 (e,)) 1
4m +
-
4
4n
4m
4
63m
m
Therefore, if
A co (log n + log ()) for some universal constant co
O, then with probability at
least 1 5.
2k
< Przna Tn -
2m
Taking union bound over oI...., Om yields the desired results.
F.2 Proof Lemma
Proof. Pick any good 6, and let x: (f) be its projection on M. Since X' consists of unit vectors, using Lemma F.I with probability at least 8, the points that lie in C(0) are at least k/(2m) fraction most 2k /m fraction of z's (under distribution
that have highest dot product with 0 or so chosen that k/(2m) < ((, r') < 2k/m. However, it is not of the form B(x, "eer"")hin wh"ch causes complication. In particular, two questions need to be answered: (i) if a point x' .M lics within distance r < p of of 0 how far can it possibly be from x? These two questions are answered in Lemma of Dasgupta and
equivalent closest to Thus, C(0) is the set of the form B(0, r') where radius
how far can it possibly be from 0, and conversely, (ii) if x' .M lies within distance
Tosh 2020 showing that,
p
A
Bar(E,)) C O,
A
2
(21)
D
BM ( C B
I.
((r))2 - A2)
(22)
A
1/dg
For the left-hand containment pick r V
A-
k
Further taking,
p+1
20am
0+
A
p
26

---

P ((r1)2 A2) -
Ic
1/do
p
202m
and using
17 yields that (L (z,, r") < (2m). Now using (21) and (22) we have, Bas(a, C
(xr(O,r)
C Bulæ, r"). Since u (I, ") < (/mm),, this ensures (I, Bxr(0,r) C
C(0).
1/de
Pick
Using
this ensures that (a(B(zr))) 2 2k/m. Further taking
crm
p A
A2
P
p + A p
2k
1/do
r"
((r1)2 A2)
A
Cimi
and using 21 and 22
have, (M, BM (0,r") C Bu (z, r"). Since u BM (x, 2
2k/m, m. this ensures that ((0) C Bas (z, r') which in turn is contained in BM (z. r"). Since for any good 0, A < p/2, 2, the result follows.
F33 Proof of Lemma B.4
Proof. Let E be the event that bounds the diameter of the response region of any good 0, as specified in Lemma B.3 with probability at least 1-8, 5, over the random choice of the training set. We condition
on this event. For any z E M and > 0, let
A(r, r) (0 E T 0/2 (0) æe| < <r}
Since 2 <
P-A for A < p/2, using Lemma B.3 and choosing large enough m satisfying
0+3
(2k((am)) 1/d0 mmnn(, if we set
h 1/do 202m
then,
0 A(z,r1)))= + Bys
TM (0),
k
1/do
x E Bu
Tar(0),
P p+
A A
1/do
20ym
202m
which implies + x E C(0). has been established that A(x, r) has non-negligible probability mass under v.
Lemma F.3 (Lemma 14 of Dasgupta and Tosh 2020 Suppose is multivariate Gaussian N(0, T). There is a constant ca, that depends on the dimension d, such that any x E M and 0 < r < To. we have v (A(x,, r)) do.
Using I7p. M has a r2/2 cover M of size at most (20z/c1)6 htee:c/)ddm///l To see this pick points M that each has μa( B(,,, rı r1)4)) 2 ai (r1/ 44)d (cr (2c2))(1188))) )k/m. Since total probability mass of these balls at most 1, this gives the bound on N.
Fn TI......
distance r //2 from each other. The balls B(x,, r/44 are disjoint and
Pick any å E M. For e [m], let U, be binary random variable that takes value 0, A(#, r1/2) and () otherwise. Therefore,
U, {
w.p. v(A(t,
up.1-v(A(i,r1/))
Note that r(2,r112) 2 ca(r1/2) (ca/ (222) \/m//////m////// / where we have set aa (c1/(2c)))11/44k) Let U Σm Ug be that number of 0, 's that fall in A(2, r1/2) and EU
27

---

E EU; 2 agk. Let Eg be the event that U > aak/2 and let E be the complement event. Using
Chernoff bound, we have
Er( Pr (U & oak/2(E)) (U S (1/2)EU|E)) Se -B// I c aaa//8
Bounding the right most quantity above be most 8/M, for k specified in the lemma statement, for suitable choice of Ç4. we conclude that E2 holds (conditioned on Eạ) with probability at least 1 8. Therefore, with probability least 28, both Ej and Ez hold, impying that for every á M, there least aakh/2 good 0,'s in A(i,r1/2)
Now pick any arbitrary x E M. There some & M with ||x +ll S 12/2. Moreover, for any 0j E A(i, 22) + 0j E A(z,ri/2) = E C(0)).
F44 Proof of Lemma B.1
For ease of exposition, we use the notation F[1.n] denote T1...., F, and V[1.n] denote .ı,.... Un- =/1..) denote 2',... .'...., 2,, and V/,,.) denote V ....... y/ for various proofs appearing the section. Note number of non-zero entries in the EaS representation given (14) is variable and we use the
notation k(z) to denote the number of non-zero entries in h2(x))
28

---

Proof. Fix any θ Then, conditioning on z [[,nn] ensures that C1. Cn are fixed. Now,
Dr.,,, (f(()) - n(x)))
90. //. [1f(2)) - -[(x))
-Er.p,)) (1) (1.))) (1(x)) - [1(x)))
Ex (f(x) - )(x))) T[2,n] (mm)
2
Σ
(îss - 11:))
JIZECs
< (xg.))
Ex, Ez,
Σ junEE,
(Ni n15) (I1m).2(1.m
Σ i= Tx E EC,
n
Ex, Bz
Σ j.rEC
n(C)))
Tī A((x)]
Σ Di= Il, E C,1l
1
Σ -i=1 3oI[2s E cyll -n(c,) Hi Ar(x)] ne ()j)(Ci)
Ex Ex
Σ
juEEC,
El V,I[X, E Cyp m(C,,) 2 nmp (Cý)
1|mpr > ojUiO E A,(1)
7 Σ
JIBEC,
+n - E A+(x))
Ei=1 (v: - -n(CC))) (Cp)(Cy))
2 TInpa(()) > ,TT E A.(x)) (11m)).(11..
= Exg Pag ((...))
Ex.pp..)
jINE,,
1
+ +B -B
BE.y
Σ
((CC))IInCC)) = oJLLi e Ax(x)] 211.0).21111
t
J:ZEC;
Limi (Ui ((,))){[E, E C.l) 2
<
Eng Emg aaj
Ex.ou...)
Σ F
[[njun(C,) oJtli e Ar [[1.n] [1.]]]
n2 (C,)
jIDEC'
Ine
2 ( ((C,))([ C.1) 2 ml/((C,)
T[mp,((C) OOT E As(x))
Exg. -
Ex t.
Enyc.nn mn
S:DEC,
+ m
tne
x, Tp 2/1,11)
Fi 2 [1.m] ]
Er 1 Σ
Innue (C₁) Injnn(CC) OJil E Aj]
< E
+ tne
nipn m(p((C,) (C2)
juEEC,
1
2m
m 2t(n + 1)
m m <
+ kne
< 2tn
t(n+
tne
tne
tn
where equality a follows from the fact that the quantity with the inner square bracket unaffected by the y, ss. Incquality b is due to Jensen's 's inequality. Inequality follows from Lemma E4 in equality d
29

---

follows from Lemma F.6 and inequality follows from Lemma F.7 The result finally follows noting that by Jensen's is inequality [l)((x)) rf(x)] S /B(ń(() - 7()))²
Lemma F.4. Pick m x d projection matrix @ Suppose the Eas representation uses (i) a mapping θ and (ii) empirical k-threshold sparsification. Let x be sampled from ye and let Dn = (I1,)1);-- distributed as (1s)) for [n]. Similarly, D ((11,31) vi)...., (I' Wn)) be another random train- ing set independent of Da, where x; is sampled from and v. is distributed as n(x)) for E [n]. Then the following holds.
(o)) is a random training set where Vi is sampled from j and is
1 E JIDEC,
Σ
2T1,) ((C))))nnC)))))))))))))))))))))) = 0,4 e (1.n) ((1mn))
S
m nte
Proof. We start by taking the 1/t factor outside.
1
E Ra
Ex
Σ
((C))) = = e A,(x)) (1um)] 2f,.)
t
JiREC,
((C))[(un(C)) = oJIl E =T0=)) z
E B
Eg
janECs
Exp Bxp
Pr(k(z)= = = K)E
Σ (C) 011 e Ac(x)) k(o) = k1
1 1/2,1|1 2 [1,0]
JiZEC,
m Pr(k(z)= K) 1EEE
6
E Bun
Σ (CC) = A,(x)] k(x) K1
1(2,n), ((1,)))2(11m)
3 E Bxpp.n))
Pr(k(x)= = K)
Σ
Impa (C,) o]ıli A A k(x) N9
JEEE
$ E Bxpp.)))
Pr(k(x)= =M) > (C) 00 2(10))
<
E Bep.at
Pr(k(x) 0) Σ
(C Σ
Pr(k(z) =k) Σ ((C))\(mpx(CC) 0/1.m]12/1.1
==1
#==1
E
Σ
(C,))Mm,, =
Pr(k(z) = =k3)
1
[CC 0f]am)
Σ (CC))I[p (C₂) = [|1,n] ([1mm|
1. -luifa.
En Exp.
< Exy (L)
(( - m(C;)"
Σ
- n
nt
1 nt Fe
np(C,)e ap(C))
-aptt)))
nt Raf
m Ey
max (mp(C))e -
}}
$
f m
E nt
m nte
e
where equality follows from the fact that the quantity with the inner square bracket is unaf- fected by the y/ s. Equality follows from the fact that for k(x) = O, number of non-zero entries in the Eas of using (14) is zero and & C2 Vj. Therefore, denote the quantity
30

---

EjizEC, (C, Mmpp E A7 = O. Inequality follows from the fact that 77Cc)) S 1, Vj.
Inequality d follows from Lemma F.5 Incquality follows since we are adding non-negative quantity. Finally, inequality f follows from the fact that sup, ze
Lemma F.5.
m
Er
(C;) оJT ( kx)) k'
s (C)) =0]
jEEEC
Proof. Conditioned on k(x)= k', Eas representation given in (14) has exactly k' non-zero entries. Therefore, using Lemma 3.4
1nnpr(C.)) o]iلi A()=)) =
E
J.
Pr (
Σ
Innnn 0Jīli e Ax(x))
5:0())
Σ (i0
m(O [[mppa(CC)) o]1[i A())]
Σ ((mpx = oj1ii E At(x)
1=1 tiEa((s
m
Σ (C, =0]
Σ
u(c jil A((o)]
())E(()
m
m
(mp j=1
Σ ijEa((
u((
Σ (C))Ilpp, = 0]
where equality a follows from part (ii) of lemma 3.4 since (CK)) s==1 forms a partition of X' and the definition of a in section 3.2 with k. Equality 6 follows from the following observation. In the line above incquality 6, we are summing k' (#) terms. Since x (*) = m x (#=]) and any
j E [m] can appear in exactly (#=1) different subsets of of size k', equality b is simply rearranging the terms from the line above by changing the indices appropriately, Equality follows from part (iv) of lemma 3.4
d projection matrix Q Suppose the EaS representation uses (i) mapping O and (ii) empirical k-threshold sparsification. Let x. be sampled from μe and let D, = ((x). 31)... 31)...., (Zn, Bu)) is a random training set where D; is sampled from μ and ys is distributed as vf(x;) for i E [n]. Similarly, D', (er,,)))... (I'n Va)) be another random train- ing set independent of Dn, where x², is sampled from and sh. is distributed as n(a!) for E [m]. Then the following holds.
Lemma F.6. Pick
Ee (y n(C,))[[a, E EC,)
E Byp..)
Σ J:EEC;
I[pp,(C,) > O e Ac(x)] x, x, = [(Im))
(C,,
(Inpn(())) >
T E A,(x))) (C3
< Σ jimnEs
Proof. Conditioned and 2/ only k(()) k of the m coordinates in the EaS representation of x are non-zero.
then the right hand side of the Lemma statement still holds with tghe value being zero since each Cj will be an empty set in that case. WLOG, for case of exposition,
31

---

assume that k' > O and these k' non-zero coordinate to be jik E [m]. Then the number of æ; that falls in any such C where [k', nu,, (C,)) The y, values corresponding to these x; points (there are npa (C of them in total) are identically and independently distributed with expectation
/
Biula E (j)) = Pr(μ = 1/2, E +2,)= 1((z)) cn
Pr(y: = 1|2; ())ddx))
((C))) /
Jon n()))(do) (C({))
Therefore, we can write
Ei= (v6 -nCCn) E C31) 2 [[ppn(C,)) outio Ac(x)] I, [,1,,,,) [/.m]
E Exp...
Σ J.EEGy
(C,)
C (1) ,((Ci)))[aa; C₂1l) [lmpn((Cs)) ojU[й E At(x)) J. 1p (npn((C)))
k
Σ Eyg
(yi: - ((C)))) CnIMMnp(CC)) ofT( E Ac(x)) x,,
(C,))
1=1
1 n(Cx:)(1 ((C))) E Cj (mpp Ojl[ A.(x)]
(C,))
(C,))(CC))> OTT[ E (x))
I^
np, (C₁))
where, equality a due to the following observation. For any i, E [m], 4 * for some [m]. Yi and yy are identically and independently distributed with expectation (C())) Therefore, the expectation of the cross product is simply:
and xi t5 E C
E Ey,,, (1: ((C))) ((.) = Ey [0: - (Ci) + サソ) ((C)
= Ey, ((y) + Eyy) + (,1)² = 0.
Equality b follows from variance computation. In particular for any yr, [m] with x; E C₁ for some E [m].
E (v. (C = Ey, - 2nn(C) +nC)) = - --C
Finally, inequality e follows from the fact that for any E [0, 1], the maximum value of 2 - 2) is 1
is easy to observe that the final result is equivalent to 1 Ejnec, (Inngnn ([in)a Ax(x)) mpa(C,))
d projection matrix O Suppose the EaS representation uses (i) mapping & and (ii) empirical k-threshold sparsification. Let x be sampled from μ and let DR = ((I1, 31), y1)...., (Zn)Vn)) is a random training set where D; is sampled from μ and ys is distributed as n(x.) for i E [n]. Similarly, D ((x2,0)), Vh),.., (x', V.)) be another random train- ing set independent of Dn, where x sampled from P and v. is distributed as n(x() for [n]. Then the following holds.
Lemma F.7. Pick
[ln((C)) > O E Ax(x))
2m
E (1
E
Tp.a), [((.)
<
(Cz)
t(n + 1)
jiDECs
32

---

Proof. We start by taking the 1/t factor outside.
1
[lun(C,) > OJ4Íi E A1(x))
E Bm ffii
Ex
[[l.n) F/1m0l
t
[(,) > O E (x))
7 Bl
((b(z)=))aa
=
k(x) = k']
I[ ((1mm)
(Cn((C))
JiEEC'
Unjun (C2) > ojtli E A,(x:)
Pr(k())= = KK
Σ
k(x) = k1]
T(1.n), (11,0)
1ipin (Cg)
J-EECS
(CC (C,) >
5 B 1/
Σ
Pr(k(z)= =
=)) =)
Σ
T T/1,n]] [(1,n)
nijunn (Cj)
W
M (CC))Mmm (C2) >>]
Pr(k(z) k)) m
((C))T(m),,CC)) (C,) 0] npj((C))
Pr(k(x) 0) +
Σ
Σ
(C,
k=1
E f1.0
F[1.n] F(11mo)
m (C,HHTy,,CCC) 00 (C,)
m
Pr(k(x) = =x1)
Σ
E Bei Fp
m
(mynnn)) >0]
E 1
2 [1 %(1mm
(Cp
m
M(C,))(mu,n (C₃) 0
E
Expn
[1.m]
2m(C,)
2m
2m t(n + 1)
E, Ex(p.n)
Beja.n
(L.m)
(n + 1)p(()
(n+1))
where equality follows from the fact that for k(z)) 0, number of non-zero entries in the Eas of us- ing 14 zero and & Cj, Vj. Therefore, we denote the quantity Ejsec; (C)) 0. Inequality & follows from Lemma F.8 Inequality e follows since we are adding a non-negative quantity. Finally, inequality d follows from the fact that np, (C₂) is Binomially distributed with parameters n and ((,))) and by an application of lemma E.4
(C,)
Lemma E.8.
Inpnn (C,) OJıí E A+(x))
((C,)T(mpn (C,n mp, (C,)
E2
k(x) = k'
<
n2p (C,,(C,))
J=EC;
j=1
33

---

Proof. Conditioned on k(x)= k', EaS representation given in (4 has exactly k'' non-zero entries. Therefore, using Lemma 3.4
Imppn(C)) > OJ[[ A((x)]
Eg
k(w)) k
mpn(C,))
S:EEC,
W
Impn 0JT E A(xx)
Pr (IECT)
(Cp)
1=1
p(C Imp,,(C) оJП[ E Ac(x)
11p2 (C,)
(8)
c(C M[npp (C₂) >
OJIlj E A((x)
(C,)
EFEa(()
m
Infr OJLLi Ax())
Σ m(CH)
1ipn (Cg)
m (nj)n(Cy))> 0] npan(C) (Cr)
M(C,) (Cg))an(CCC))))))(( 0
Σ i:jE((i)
u((
(Cp)(C))
where equality a follows from part (ii) of lemma 3.4 since {C*²) Ji=1 forms a partition of X' and the definition of a in section 3.2 with k = k. Equality 6 follows from the following observation. In the line above inequality 4. we are summing k' x (x)) terms. Since x (*) m x (F=1) and any j E [m] can appear in exactly (m=1) different subsets of size k', equality b is simply rearranging the terms from the line above by changing the indices appropriately. Equality follows from part (iv) of lemma 3.4
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See section 3,4.5.
Guidelines:
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
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 not discussed in the paper.
The authors are encouraged to create 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
35

---

Justification:
See section 3,4 and Appendix B-F.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: section Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
36

---

Answer:
[Yes]
Justification:
Data is available from OpenML repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpipps.ccppullc//uuuii wwwtc//ggue////eeeeceoocc CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bar provided in the form of shaded graph.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
37

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /aaps::///uripss/ http///uris.cppuuupppppeee http://..ccc..occcttttccttttteea
Answer: [Yes]
Justification:
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
38

---

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 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 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 models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Data used from repositry... repository. from Scikit-learn. See section 5.
KNN and Random Forest models are run
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 dataset.
The authors should state which version of the asset used and, possible, include 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, wwwpsspipetattteeeeee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
39

---

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/moddl 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
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.
40


Reviews:
[{"review_id": "8QY5VYfSpF", "reviewer": "Reviewer_Q16i", "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.", "questions": "1. As in Weakness 2, I suggest including more related work on non-parametric classification, particularly focusing on their consistency and convergence results.\n\n2. In Algo 2, how do we choose t? \n\n3. 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'?\n\n4. 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.\n\n## Minor:\n1. 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.\n2. Page 3 line 137. $(x_1,y_1)$ should be $(x_i,y_i)$.\n3. Page 4 line 153. It should be “An average of y values”.\n4. Page 4 line 163. “Non-parametric”.\n5. Page 8 line 323. “Alg. 2”: a missing “.”\n6. Page 8 line 324. A missing $($.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. Relating non-parametric classification with expansion and EaS representation is both interesting and reasonable. The intuition behind it is straightforward: EaS offers a way to identify the 'neighbors' (active regions) of each data point, or in other words, points that are proximate to the data point in a certain representation space. By aggregating the conditional probability distribution of these 'neighbors,' we obtain a consistent classifier.\n\n2. The proposed algorithm is simple and easy to implement. It leverages ideas from unsupervised learning representation and adapts them naturally to the supervised learning setting. It reminds me of several empirical machine learning algorithms, such as prototypical networks, which learn a representation for each class by computing the mean of the support examples' feature representation. During inference, the algorithms classify new examples based on the closest class prototype in the feature space. I believe this paper offers a way to conceptualize a class of empirically successful supervised learning algorithms, which involves learning representations and classifying data using examples that are close to it in the representation space.\n\n3. The paper is well-organized and easy to read. The contributions, theorems, and underlying intuitions are presented clearly.", "weaknesses": "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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing thoughtful and encouraging feedback. The reviewer's suggestion of including consistency and convergence rates of various non-parametric classification is an excellent one and if accepted we will definitely include a discussion on consistency and convergence rates of various non-parametric classifiers, such as, partitioning estimates (histograms), k-nearest neighbors, kernel methods and random forests.\n\nRegarding question 2, $t$ should be linear in $k$, for example $t=k/2$ or $t=k/4$, to have minimax-optimal convergence rate. However, it is possible to choose even $t=1$.\n\nRegarding question 3, your suggested modification of Alg1 is an interesting one. Note that in $k$-WTA sparsification, for any $x$, the closest $k$ $\\theta_i$ are are activated (i.e., the corresponding bits in EaS representation are set to 1) since they have the largest $k$ dot products. Because of this property, your suggestion (choosing large $k$ first and then setting $eas[i]=0$ when $\\theta_i$ is not $t$ close to $x$) boils down to choosing $k=t$. Intuitively, when data lie on or near a low dimensional manifold embedded  within a high dimensional unit sphere, and $\\theta_i$ are chosen uniformly at random from the high dimensional unit sphere, only a tiny fraction of the $\\theta_i$ will ever be used (activated for some $x$, i.e, corresponding bits in EaS representation will be 1), that is, they are one of the $k$ closest ones to at least one $x$ lying on the manifold. In other words, to have reasonable conditional probability estimates of the activated regions, which in turn may be used to provide a good estimate of $\\eta(x)$, we may have to sample large number (exponential in $d$) of $\\theta_i$s, in spite of the fact that most of them will possibly be unused (never activated at all)!\n\nIn comparison, the empirical-k-thresholding is done in such a way that EaS representation of each $x$ is $k$-sparse in expectation but every single $\\theta_i$ is used, that is,  activated for roughly $k/m$ fraction of the data points, (thus, reduces wastage as was the case for $k$-WTA sparsification), however, depending on the manifold structure, every single activated region $C_i$ may not be local anymore, and thus, $\\eta(C_i)$ may not be reliable if we want to use it to estimate $\\eta(x)$. For Alg 2, we first show in Lemma B.3 that when $\\theta_i$ is  **good** in a sense that it is close to the manifold (please see Appendix B.3 for precise meaning) then $C_i$ is local in the sense that diameter of $C_i$ is small and depends only on $d_0$ instead of $d$ as was in the case of $k$-WTA sparsification. Then, we show in Lemma B.4 that when $\\theta_i$ are chosen from appropriate Gaussian distribution, there are enough ``good\" $\\theta_i$ for each $x$ on the manifold with high probability. We set $t$ to be the number of  **good**  $\\theta_i$ and for any $x$ on the manifold, the average of the $t$ corresponding conditional probability estimates $\\eta(C_i)$ is a reasonable estimate of $\\eta(x)$.\n\nRegarding question 4, your suggestion makes a lot of sense and we will definitely pursue this avenue in our future research.\n\nFinally, thank you so much for pointing out the typos. We will fix those. Regarding usage of two sets of data in Alg2, our motivation was to keep the estimated thresholds (computed from one set of data) independent of the other set used to estimate $\\eta_j$. With a careful analysis, it may be possible to use only one set of data to compute both the thresholds and the $\\eta_j$'s.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qn7PM5wDuY", "reviewer": "Reviewer_QQJv", "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.", "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": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The classifier is very natural and can be implemented. \n- Experimental results show a strong performance almost on par with the nearest neighbor and random forest classifiers.\n- The idea that one can lift the feature to a large enough boolean cube and run a sparse linear classifier is beautiful. Hopefully, there will be some followup works using this idea to solve other problems.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing encouraging feedback. We are in fact working on using this expand-and-sparsify representation idea to solve other ML problems.\n\nThe question you have is an important one. The conditions for consistency in Theorem 3.3 and the quantitative rates in Theorem 3.12 are slightly different. The reason is, to establish consistency we simply used the classical Stone's theorem without caring much about the convergence rate (often for a new classifier, the first question one typically asks is whether the classifier is statistically consistent or not). To derive convergence rate, especially to establish minimax-optimality,  we did a bit more careful analysis. However, convergence rate does imply consistency and we will add a comment explaining this difference. If accepted, the camera ready version will provide one extra content page and we will add a proof sketch of Theorem 3.12 in the main paper as well.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Mt8AmMYYQI", "reviewer": "Reviewer_4EZA", "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.", "questions": "- I think in line $42$, $\\mathbb{P}(y=1 \\vert x)$ should be $\\mathbb{P}(y=1 \\vert C_j)$.\n\n- In line $537$, what is $\\nu$?\n\n- The proofs in lines $536$ to $542$ are very unclear, and there are some claims in these lines which I think need mathematical proof.\n\n- 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": "The limitations are addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proofs are rigorous.\n\n- The writing is very good and easy to follow.\n\n- The messages of the paper are very clear.", "weaknesses": "- The contribution with respect to Dasgupta and Tosh [2020] is very marginal, and many of the ideas come from that work.\n\n- In practice, other methods like random forests seem to perform better than the proposed method.\n\n- It is not mentioned in the paper whether this is the best theoretical work with this rate of convergence.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing constructive feedback. \n\nRegarding weakness 1, while our work is inspired by the work of Dasgupta and Tosh [2020], we have clearly articulated how our work is different and advances the result of Dasgupta and Tosh [2020] in lines 96-111.\n\nRegarding weakness 3, in the non-parametric setting, minimax-optimal convergence rate is the best possible convergence rate one can hope for. For appropriate choice of $m$, our proposed method achieves the minimax-optimal convergence rate (Remark 3.14, 4.4), therefore, this is the best possible rate.\n\nRegarding weakness 4, yes, this is a limitation of Alg 1 as Alg 1 does not adapt to low dimensional manifold. We have explicitly established a lower bound in Theorem 3.15. To address this shortcomings, we have developed Alg 2 whose convergence rate, when data lie on a low dimensional manifold with intrinsic dimension $d_0\\ll d$, decays exponentially slowly in $d_0$ (Theorem 4.2, Corollary 4,3, Remark 4.3) which is minimax-optimal. It is well known (Tsybakov [2008], Gyorfi et al. [2002]) that, in the non-parametric setting, minimax-optimal convergence rate decays exponentially slowly with the dimension. When data lie on a low dimensional manifold with intrinsic dimension $d_0$, where $d_0\\ll d$ ($d$ is the ambient dimension), convergence rate of our Alg 2 is minimax-optimal in-terms of $d_0$, without teh knowledge of $d_0$ is. In other words, our Alg 2 adapts to intrinsic dimension.\n\nThank you for pointing out the typo in line 42, we will fix this. In line 537, we overload $\\nu$ so that $\\nu(r)$ denotes the smallest probability mass of any ball centered at $x$ with radius $r$. We will add a footnote to address this confusion. We do not see any incorrectness in the proof, in particular in lines 536-542, the required claim is given in Lemma D.1 which is a standard result from Chaudhuri and Dasgupta [2010]. However, we will spend some time to wordsmith this part of the proof so that it is more readable. Thank you for pointing out notational inconsistency in the proof of Lemma 3.5, we will fix this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gaC0BlzVW5", "reviewer": "Reviewer_E4XV", "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$).", "questions": "1. Is it possible to compare and contrast the two algorithms and specify which algorithm is better under different scenarios?\n2. Why the performance of algorithm 1 in the experiments increases with m but the other methods are the same when m increases?", "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.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem setting is novel as the authors combined the expand-and-sparsify technique to non-parametric classification.\n2. The authors provide two different algorithms for sparsification and show that both of these are minimax-optimal.", "weaknesses": "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}$?\n2. 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?\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing constructive feedback and pointing out the typos (weakness 1). We will fix those.\n\nRegarding weakness 2, it is not ``necessary\" to use expand-and-sparsify representation in non-parametric classification. Note that there different types of non-paranetric classifiers, such as,  histogram classifiers (partitioning estimates), $k$-nearest neighbor classifiers, kernel methods, random forest and so on. Our proposed classifier a new non-parametric classifier that utilizes expand-and-sparsify representation. We establish solid theoretical properties of our proposed classifier -- for appropriate choice of hyper-parameter, excess Bayes risk of our proposed classifier achieves minimax-optimal convergence rate (the best rate possible). Experimental results show a strong performance almost on par with the nearest neighbor and random forest classifiers.\n\nRegarding weakness 3, as mentioned in line 347, details of the datasets are provided in appendix A. As per Theorem 3.12, we use $k= d\\log m$ in our experiments.\n\nTo answer question 1, note that our Alg 1 achieves minimax-optimal convergence rate, the best possible in the non-parametric setting. This convergence rate decays exponentially slowly with (ambient) dimension $d$.  However, we have shown in section 3.5 that even if the data lie on a low dimensional manifold with intrinsic dimension $d_0\\ll d$, there exists a smooth regression function $\\eta$ such that the quantity $\\mathbb{E}_{x,D_n}|\\eta(x)-\\hat{\\eta(x)}|$, where $\\hat{\\eta}(x)$ is the conditional probability estimate of Alg 1, decreases at a rate no faster than $n^{-\\frac{1}{d+1}}$. Therefore, we can not expect excess Bayes risk to decay (a bit faster) at a rate that decays exponentially in $d_0$, instead of $d$, which means Alg 1 can not adapts to the low dimensional manifold structure. Alg 2 is designed for this very purpose. When data lie on a low dimensional manifold with intrinsic dimension $d_0\\ll d$, convergence rate of Alg 2 decays exponentially slowly in $d_0$ (instead of $d$) and is again minimax-optimal. Please also see our rebuttal to reviewer Q16i to have more discussion on this subject.\n\nTo answer question 2, please note that $m$ is a hyper-parameter of our proposed Alg 1 and this hyper-parameter does not affect the performance of other non-parametric classifiers such as $k$-nearest neighbor ($k$-NN) classifier or random forest (RF) classifier. Our theoretical result (Theorem 3.12) suggests that excess Bayes risk decreases with increasing $m$. We wanted to verify this behavior in our empirical results. As a baseline, we chose two other non-parametric classifiers, namely $k$-NN amd RF. For $k$-NN, we chose two values of $k$, namely $k=1$ and $k=10$, which are pretty standard. For RF, we chose the number of trees via grid search and cross validation. Since $m$ is not a hyper-parameter of $k$-NN or RF, for different values of $m$, $k$-NN and RF test accuracies are constant.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)