Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent
Authors: Yiwen Kou
Zixiang Chen
Quanquan Gu
Sham M. Kakade
Venue: NeurIPS 2024 poster (2024)
Keywords: k-Parity
Optimization
Generalization
Primary area: optimization_for_deep_networks

Abstract: The $k$-sparse parity problem is a classical problem in computational complexity and algorithmic theory, serving as a key benchmark for understanding computational classes. In this paper, we solve the $k$-sparse parity problem with sign stochastic gradient descent, a variant of stochastic gradient descent (SGD) on two-layer fully-connected neural networks. We demonstrate that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube ($k\le O(\sqrt{d})$) with a sample complexity of $\tilde{O}(d^{k-1})$ using $2^{\Theta(k)}$ neurons, matching the established $\Omega(d^{k})$ lower bounds of Statistical Query (SQ) models. Our theoretical analysis begins by constructing a good neural network capable of correctly solving the $k$-parity problem. We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors. To the best of our knowledge, this is the first result that matches the SQ lower bound for solving $k$-sparse parity problem using gradient-based methods.

Matching the Statistical Query Lower Bound for k-Sparse Parity Problems with Sign Stochastic Gradient Descent
Yiwen Kou*
Zixiang Chen"
Department of Computer Science University of California, Los Angeles Los Angeles. CA 90095, USA evankoudcs ucla edu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095, USA chenzx190cc ucla. edu
Quanquan Gu
Sham M. Kakade Kempner Institute at Harvard University Harvard University Cambridge, MA 02138, USA sham0seas. harvard edu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095, USA qguêcs ucwa. edu
Abstract
The k-sparse parity problem is classical problem in computational complexity and algorithmic theory, serving as a key benchmark for understanding computational classes. In this paper, solve the k-sparse parity problem with sign stochastic gradient descent, a variant stochastic gradient descent (SGD) on two-layer fully- connected neural networks. We demonstrate that this approach can efficiently solve the k-sparse parity problem a sample complexity (dd-11 using 28(k) neurons, matching the established (cdh) lower bounds of Statistical Query (SQ) models?. Our theoretical analysis begins by constructing a good neural network capable of correctly solving the k-parity problem. We then demonstrate how trained neural network with sign SGD can effectively approximate this good network, solving the k-parity problem with small statistical errors. To the best of our knowledge, this is the first result that matches the SQ lower bound for solving k-sparse parity problem using gradient- based methods.
d-dimensional hypercube (k: I O(Vd) with
Introduction
The k-parity problem, defined on a binary sequence of length d, is a fundamental problem in the field of computational complexity and algorithmic theory. This problem involves finding subset of cardinality & by assessing if the occurrence of 1's in this subset is even or odd. The complexity of the problem escalates as the parameter l: increases. Its significance, while evidently practical, is rooted in its theoretical implications; it serves as a vital benchmark in the study of computational complexity classes and has profound implications for our understanding of P versus NP (Vardy, 1997; Downey al., 1999; Dumer al., 2003) and other comnrrtonn questions in computational theory (Blum, 2005; Klivans et al., 2006). Furthermore, the k-parity problem's 's complexity underpins many theoretical models in error detection and information theory (Dutta et al., 2008), and is instrumental
"qqual contribution
"The ((d sample complexity implies Ō(d*) query complexity, because each sample corresponds to d scalar- valued queries.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

in delineating the limitations and power of algorithmic efficiency (Farhi et al., 1998). This paper tackles the k-sparse parity problem (Daniely and Malach, 2020), where the focus is on the parity of a subset with cardinality k < d.
Recent progress in computational learning theory has focused improving the sample complexity guarantees for learning k-sparse parity functions using stochastic gradient descent (SGD). Under the framework of the Statistical Query (SQ) model (Kearns, 1998), has been established that learning the k-sparse parity function requires a minimum of M(d") queries (Barak et al., 2022), highlighting the challenge efficiently learning these functions. On the other hand, considerable effort has been devoted to establishing sample complexity upper bounds for the special XOR case (k- = 2), with notable successes including (dd sample complexity using infinit-wwidth or exponential-wine ))2")) two-layer neural networks trained via gradient flow (Wei et al., 2019; Chizat and Bach, 2020; Telgarsky, 2022), and (dd) sample complexity with polynomial-width networks via SGD (Ji and Telgarsky, 2020; Telgarsky, 2022). A significant advancement in solving the 2-parity problem was recently introduced by Glasgow (2023). They proved a sample complexity bound of ((d) using a two-layer ReI.U network with logarithmic width trained by SGD, thus matching the SQ lower bound when k 2.
(i.e..
In the general case of k 2 2, Barak et al. (2022) has made significant progress, achieving a sample complexity of O(d*+1) with a network width requirement of 28()), which is independent of the input dimension d. Additionally, Barak et al. (2022) demonstrated that the neural tangent kernel (NTK)-based method (Jacot et al., 2018) requires a network of polynomial width d((() to solve the k-parity problem. Recently, Suzuki et al. (2023) achieved a sample complexity of ((d) by the mean-field Langevin dynamies (MFLD) (Mei al., 2018; Hu et al., 2019), which requires neural networks with an exponential width in d, i.e., O(e"), and an exponential number of iterations (i.e., ((e)) ) to converge. Thus, their method is not computationally efficient and does not match the SQ lower bound. Notably, Abbe et al. (2023a) introduced the leap-k function for binary and Gaussian sequences, which extends the scope of the k-parity problem. They also proved Correlational Statistical Query (CSQ) (Kearns, 1998; Bshouty and Feldman, 2002) lower bounds for learning leap-k function for both Gaussian and Boolean inputs. In detail, they proved CSQ lower bounds of 9(d==1) for Boolean input and (2) for Gaussian input, which suggests that learning from Boolean input can be substantially harder than learning from Gaussian input. They also proved that SGD can learn low dimensional target functions with Gaussian isotropic data and 2-layer neural networks using n Z dleap-1 examples. However, their upper bound analysis is based on the assumption that the input data x follows Gaussian distribution and relies on Hermite polynomials, making it unclear how to extend it to analyze Boolean input. Based on the above review of existing literature, raises a natural but unresolved question:
Is possible to match the statistical query lower bound for k-sparse parity problems with stochastic gradient descent?
In this paper. we give an affirmative answer the above question. In particular, we consider the standard k-sparse parity problem, where the input x is drawn from a uniform distribution over d-dimensional hypercube (ni,((-1,1)) 1)) Our approach involves training two-layer fully-connected neural networks with m = ()(k) width using sign SGD (Bernstein et al., 2018) with batch size B = 0 polylog(d)). We prove that the neural network trained by SGD can achieve a constant- order positive margin with high probability after T Olog d) iterations. Therefore, the total number of examples required in our approach is n = BT = (dkk-l) Thus, the total number of scalar-valued queries required in our paper is m d n = 20()) dd (d polylogd) = 20(k) d polylogd, where m is the number of neurons, d is the input dimension, and n is the total number of fresh examples seen by the algorithm². Abbe et al. (2023a) also proved a CSQ lower bound 22d+)) for learning d-dimensional k-parity problems, which implies the sample complexity lower bound n 2 d Thus, our sample complexity result also matches the CSQ lower bound in Abbe et al. (2023a).
1.1 Our Contributions
The Statistical Query (SQ) lower bound indicates that, regardless of architecture, SGD requires a query complexity of (d for learning k-sparse d-dimensional parities under constant noise level.
Note that d is the total number of scalar-valued queries used for one example.

---

We push the sample complexity frontier of k-sparse parity problem to O(d via SGD, specifically with online stochastic sign gradient descent. Our main result is stated in the following informal theorem:
Theorem 1.1 (Informal). For two-layer fully-comeettdd neural networks of width 2 online sign SGD with batch size () can find solution to the k-parity problem with small test error within O log d) iterations.
The above theorem improves the sample complexity in Barak al. (2022) from ((d*+1) O(d Moreover, the total number of queries required is O(d"), which matches the SQ/CSQ lower bound up to logarithmic factors. Additionally, under the standard basis setting, our result matches the sample complexity Glasgow (2023) for solving the XOR (i.e., 2-parity) problem with sign SGD. It is worth noting that our result only requires two-layer fully connected neural networks with 2 width and sign SGD training with (k log d) iterations, which gives computationally efficient algorithm. Finally, we empirically verify our theory in Appendix A, showcasing the efficiency and efficacy of our approach.
Notation. We use [N] to denote the index set {1,..., NJ. We use lowercase letters, lowercase boldface letters, and uppercase boldface letters to denote sealars, vectors, and matrices, respectively. For a vector v = (21,'.. ( T,
we denote by ||v|22 == ( uz)1/2 its L2 norm. For a vector (ui,... ".) we denote by V[tsia] := (Ub..... 0i2) its truncated vector ranging from the i1-th coordinate to the i2-th coordinate. We denote by 0 a vector of all zeros. For two sequence } and {ba). we denote ag = O(bx) if |ax| S C' by| for some absolute constant C, denote α = 3(bb)) if by (ax), ) and denote a -a==6 (bb)) if ag = Obb)) and a₂ = lbbb)). We also denote a₁ o(bs) if lim | denote In (oly(yn) if In = Ovy P) for some positive constant D, and T, = polylog(yx)) if In = poly (l.g())))).
O. We use Ō() and (2) to omit logarithmic terms in the notation. Finally, we
2 Related Work
XOR Problem. The performance of two-layer neural networks in the task of learning 2-parity has been the subject of extensive research in recent years. Wei et al. (2019); Chizat and Bach (2020); Telgarsky (2022) employed margin techniques to establish the convergence toward a global margin maximization solution, utilizing gradient flow and sample complexity of O(d). Notably, Wei et al. (2019) and Chizat and Bach (2020) employed infinite- width neural networks, while Telgarsky (2022) employed more relaxed width condition of Odd'). A significant breakthrough in this domain was achieved by Glasgow (2023), who demonstrated a sample complexity of O(d) by employing SGD in conjunction with ReLU network of width polylog(d) (d). Furthermore, several other studies have shown that when input distribution follows Gaussian distribution, neural networks can be effectively trained to learn the XOR cluster distribution (Frei et al., 2022; Meng et al., 2023; Xu et al., 2023). A comparison between the results in this paper and those of related work solving the XOR problem can be found in Table 1.
The challenge of training neural networks to learn parities has been explored in previous research from diverse angles. Several papers studied learning the k-parity function by using two-layer neural networks. Daniely and Malach (2020) studied learning k-parity function by applying gradient descent on the population risk (infinite sample size). Notably, Barak et al. (2022) presented both empirical and theoretical evidence that the k-parity function can be effectively learned using SGD and a neural network of constant width, demonstrating a sample complexity of O(d++1) and query complexity of ((d Edelman et al. (2024) demonstrated that sparse initialization and increased network width lead to improvements in sample efficiency. Specifically, they showed that the sample complexity can be reduced at the cost of increasing the width. However, the best statistical query complexity they can achieve is (d)++2), which is the same as that in Barak al. (2022). Suzuki et al. (2023) reported achieving sample complexity of O(d) by employing mean-field Langevin dynamics (MFLD). Furthermore, Abbe et al. (2022) and Abbe et al. (2023a) introduced novel complexity measure termed "leap" and established that leap-k (with k-parity as a special case) functions can be learned through SGD with a sample complexity of Ö ((maax(k-1.)) Additionally, Abbe et al. (2023b) demonstrated that curriculum- based noisy-GD (or SGD) approach
k-parity Problem.
3

---

Activation
Loss Function
Width (m) Requirement
Sample (n)
Iterations (t)
Algorithm
Function
Requirement
to Converge
Theorem (Wei 2019)
ReLUU
logistic
WF with Noise
8
d/c
(Chizat and Bach, 2020)
Theorem 8
2-homogenous
logistic/hinge
WF
d/c
Theorem 3.3 (Telgarkyy, 2022)
ReL.U
Ingistic
scalar GF
d
dfc
d/t
Theorem 3.2
RcLU
logistic
defe
de/e
(Ji and Telgarsky, 2020)
Theorem 2.1 (Telgarsky, 2022)
ReL.U
logistic
SGD
de
dP/c
d//c
Theorem
ReL.U
Ingistic
SGD
polylog(d)
d polylog(d)
polylog(d)
(Glasgow, 2023)
Ours
correlation
Sign SGD
0(1)
(olylog(d)
log
Table 1: Comparison of existing works on the XOR (2-parity) problem. We mainly focus on the dependence the input dimension d and test error and treat other arguments constant, Here WF denotes Wasserstein flow technique from the mean-field analysis, and GF denotes gradient flow. The sample requirement and convergence iteration both Glasgow (2023) and our method do not explicitly depend on the test error Instead, the dependence on é is implicitly incorporated within the condition for d. Specifically, our approach requires that d 2 C' logg (2m/e) while Glasgow (2023) requires exp((1/e))) where C' is constant.
Activation
Loss Function
Width Requirement
Sample Requirement
Iterations (1) Converge
Algorithm
Function
Theorem 4 (Barak et al., 2022)
ReLU
hinge
2014)
d+ log(d/e)/2
d/e2
Theorem 4 (Edelman et al., 2024)
ReLU
hinge
SGD
(d/s)*
(s/R)*-1d log(d)/2
1/c2
Corollary
Variant of Tanh
logistic
MFLD
ed
d/c
ca
(Suzuki al., 2023)
Ours
correlation
Sign SGD
28(A) d polylog(d)
log d
Table 2: Comparison of existing works for the general k-parity problem, focusing primarily on the dimension d and error 6, treating other parameters as constants. Edelman al. (2024) the sparsity of the initialization that satisfies 8 >> k. The activation function by Suzuki et al. (2023) is defined h (x) R f'tanh(xx W1 w2) tanh(w:)))33, where and R is hyper-parameter determining the network's scale. For the sample requirement and convergence iteration, we focus on the dependency of d, e and omit another terms. Our method's sample requirement and convergence iteration are independent of the test error instead relying condition for d that implicitly includes e. Specifically, we require d 2 C (2m/e).
(W1, W22 W3) E Rd-2
could attain a sample complexity of (dd) provided the data distribution comprises mix of sparse and dense inputs. The conditions outlined in this paper are compared to those from related work involving uniform Boolean data distribution, as presented in Table
3 Problem Setup
In this section, we introduce the k-sparse parity problem and the neural network we consider this paper.
Definition 3.1 (k-parity). Let each data point (x, y) with x E Rd and y E [-1,1} be generated from the following distribution DA, where A is non-empty satisfying A [n]:
xy ~ (-1,1) 1} as uniform random bit for E [d].
2. The label y is generated as 1I

---

Modified vs. Standard Sign Function
1.00
sign (x)
sign(x)
0.75
0.50
0.25
0.00
-0.55
-0.50
00.55
-1.00
-2.0
Figure 1: The plot above illustrates the comparison between the modified sign function (i 0.5) and the standard sign function sign(x). The sign(x) function introduces 'dead zone' between -p and where the function value zero, which not present in the standard sign function. This modification effectively creates threshold effect, only outputting non-zero values when the input exceeds the specified bounds of in either direction.
The k-parity problem with dimension d is defined as the task of recovering A, where |A] k, using samples from A-
Without loss of generality, we assume that A [ k} if || A| = k. Under this assumption, denote D by D for simplicity. This k-parity problem in Definition 3.1 a classical one, which has been studied by Daniely and Malach (2020); Barak al. (2022) using neural network learning. When restricted to the 2-parity function, the problem is reduced to the XOR problem (Wei et al., 2019).
Two-layer Neural Networks. We consider two-layer fully-connected neural network, which is defined as follows:
f(W. x)
Σ a ( ((w,,))
(3.1)
where is the number of neurons. Here, employ polynomial activation function defined by (=) = z The term w, E Rd represents the weight vector for the r-th neuron, and W denotes the aggregate of all first-layer model weights. The second-layer weights a, ' are sampled uniformly from the set 1,1, } and fixed during training.
Algorithm.
We train the above neural network model by minimizing the correlation loss function:
Lp ()) = Exxx))=Dll f(W, x)],
where ((=)= 2. We consider binary initialization with w, Unif (ni which widely used for neural networks solving parity problem (Barak et al., 2022; Abbe and Boix-Adsers 2022). We then employ the stochastic sign gradient descent with constant step size and weight decay (i.e., & norm regularization on the first-layer weights) to minimize the correlation loss follows:
O (t)
w(++1) = (1 An) w())
sign
aW
where À > is the weight decay parameter, 1) is the step size, and sign(r) is the modified sign function defined as:
1,
for r 2 p.
(x) sign(x) (1x120)
0, for p < P.
for x < -p.
5

---

Here, > 0 is a threshold parameter. In this context, ( is computed using randomly sampled
online batch S, with batch size |S B:
6 1
fly (WW)))))
B
(x,))ES,
Consequently, the update rule for each w, is given by:
w. (((+1) = (1 - w + sign
Σ (X,))ES,
o' o'(ww!),x)) aryx
(3.2)
where sign is applied on an element-wise basis.
Remark 3.2. Sign SGD has been previously studied in Riedmiller and Braun (1993); Bernstein et al. (2018). Recently, it has become increasingly popular and has been utilized in adaptive optimizers for training large models (Chen et al., 2024; Liu et al., 2023). Previous studies (Balles and Hennig, 2018; Bernstein et al., 2018; Zou et al., 2021) have demonstrated that Sign SGD behaves similarly to Adam when using sufficiently small step sizes small moving average parameters, 31 and B3. In our work, the choice of sign SGD over standard SGD stems primarily from our adoption of the polynomial activation function (2) 2hh As later explained in Section 4. this specific activation function is pivotal in constructing a neural network that accurately tackles the k-parity problem. However, it introduces trade-off: the gradient's ' dependency on the weights becomes polynomial rather than linear. Sign SGD addresses this issue by normalizing the gradient, ensuring that all newrons progress uniformly towards identifying the parity. Moreover, incorporating a threshold within the sign function plays a crucial role as it effectively nullifies the gradient of noisy coordinates. This, together with weight decay, aids in reducing noise, thereby enhancing the overall performance of the network.
4 Main Results
In this section, we begin by demonstrating the capability of the two-layer fully connected neural network (3.1) to classify all examples correctly. Specifically, we construct the following good network:
f(W" x) = a,o((w;,,)))
(4.1)
where (Wi E - - a. = II sign(w", and wT [R+1idd]] = Oa- for any E [2*] Notably, leveraging the inherent symmetry within our neural network model, we can formally assert the following proposition: yf( x) v'f(W"'xx x') for any (y, x) and (3/ x') generated from DA The subsequent proposition demonstrates the precise value of the margin.
Proposition 4.1. For any data point (x, v) generated from the distribution DA it holds that
vf(W" x) = k! 2*
(4.2)
Proof. Given (), DA. have that y 11 We divide the neurons into (k + 1) groups 02 i (O....,Ai k). A neuron E Ω and only if E 1ww = 22)) = i. Then we have that
2
v/(W", x) =
y a.) x(W;,))
(u (.,) (w)
1=0 ref
sign(z;)
II sign((e(s) a o((w;, x))
-=0 reft
j=1
(-1) 1
oA - 22)

---

k! 2
where the third equality is due the fact that y = IT sign(z,) and a; IT; = sign( (wi,)) the fourth equality is due to the definition of 92, the last equality holds because a is k-th order polynomial activation function and Lemma F.2.
Therefore,
conclude that for any (x, y). we have yf vf("".. x) k! 2 0. We will demon- strate in the next section that training using large batch size online SGD, as long as Condition 4.2 met, will lead to the trained neural network f(W((), x) approximating (m//2 S(W", x) effectively after I = O(k lo)( iterations. Our main theorem is based on the following conditions on the training strategy.
Condition 4.2. Suppose there exists sufficiently large constant C, such that the following conditions hold:
Neural network width satisfies m 2 C C. log(1/8).
Dimension is sufficiently large: d 2 C log (2m/e) e)..
Online SGD batch size B 2 C2*
1)!) dd loghllool0nn (16mdBBT)) log (8md[ (5).
Learning rate satisfies 1 S C-
Regularization parameter À is taken as X 1.
The threshold for the modified sign function satisfies 0.1
In the k-parity problem, the label y is determined by a set of k bits. Consequently, the total count of distinct features 2h, reflecting all possible combinations of these bits. The condition of m is established to guarantee roughly equal number of neurons within the good neuron class, each correctly aligned with distinct features. The condition of d ensures that the problem is in a sufficiently high-dimensional setting. The condition of m, d implies that d 2 52 m) 2 22(422, which is mild requirement for the sparsity k. In comparison, Barak et al. (2022) requires d 2 12(K+) for neural networks solving k- k-parity problem. By Stirling's approximation, the condition of B can be simplified to B 2 (2e log( (1mdd6mm (6)d/2/()) Therefore, the conditional batch size B will exponentially increase parity & < O(vd) goes up, which ensures that the stochastic gradient can sufficiently approximate the population gradient. Finally, the conditions of r7, À ensure that gradient descent with weight decay can effectively learn the relevant features while simultaneously denoising the data. Finally, the threshold condition increases as sparsity k increases to accommodate the increase of the population gradient. Based on these conditions, we give our main result on solving the parity problem in the following theorem.
Theorem 4.3. Under Condition 4.2, we run online SGD for iteration T = Okm I x log d)
iterations. Then with probability at least 1 - ö we can find (T)) such that
P(yf(W(T) (T) x) 2 7mm 2 1-c.
where y = 0.25k! is a constant.
Theorem 4.3 establishes that, under certain conditions, a neural network is capable of learning to solve the k-parity problem within (ken X log d) iterations, achieving a population error of at most c. According to Condition 4.2, the total number of examples utilized amounts to BT = (ddk-1) given polynomial logarithmic width requirement of m O(1) with respect to d.
Remark 4,4. While Theorem 4.3 works for fixed second-layed layer training, we demonstrate that com- parable results can be obtained when the second layer of the network is simultaneously trained with a lower learning rate. Detailed results and further elaboration of this aspect are provided in Appendix E. Our findings present sample complexity of ((d--1), aligning with Conjecture 2 posited by Abbe al. (2023a), which suggests a sample complexity lower bound of (1d==1)). Besides, our results for the uniform Boolean distribution match the complexity achieved by Abbe et al. (2023a) under the isotropic Gaussian scenario. Despite these similarities in outcomes, our methodology diverges significuntly: we employ online sign SGD utilizing a large batch size of Ō(d=-1) and conduct training over merely Ó(1) iterations. In contrast, Abbe et al. (2023a) implement projected online SGD with minimal batch size of 1, extending training over (df--1) ierration.. Abbe et al. (2023a) also requires two-phase training process for the first and second layer weights, requiring them to be trained separately.
7

---

5 Overview of Proof Technique
In this section, we discuss the main ideas used in the proof. Based on these main ideas, the proof of our main Theorem 4.3 will follow naturally. The complete proofs all the results are given in the appendix. Section 5.1 serves as a warmup by examining population sign gradient descent. Here, three pivotal ideas crucial the proof of stochastic sign gradient descent are introduced:
1. The impact of the initialization's 's positivity or negatívity on the trajectory of neuron weights.
2. The divergence between feature coordinates and noise coordinates of different neurons.
3. How a trained neural network can effectively approximate the good neural network (4.1).
Moving on to Section 5.2, delve into the analysis of sign SGD. Contrasting with population GD, the addition in SGD analysis involves accounting for the approximation error between the population gradient and the stochastic gradient. This consideration leads to the stipulation of the batch size B outlined in Condition 4.2.
5.1 Warmup: Population Gradient Descent
For population gradient, perform the following updates:
w [t++1) 1) (1 - 777) w(! 77 sign VV. LD (W())))
where (D) - [[(y, f(W x))]
E (x,)) (W (W.x)) x)].
Then, the following
coordinate-wee wise population gradient update rules hold:
w
(2) w 4.2
(t)
(1)
(++1) w rj = (1 (1-n))) ())) + sign
kla,
j E [k],
(5.1)
w rg
(++1) = (1 - n)) W.
j [k]]
(5.2)
In the preceding discussion of the update rule, we have identified that the noise coordinates (j & [+]) exhibit exponential decay, characterized by decay constant of 1 - nn. To further dissect the dynamics of this system, we turn our attention to the behavior of feature coordinates. We categorize neurons into two distinct types based on their initial alignment: neuron is classified as a good bad neuron if a, - I[ sign(w?.)) This distinction is pivotal, it divides the neuron population into two distinct classes: good and bad. Neurons in the good class are integral to the functionality of the final trained neural network, playing a significant role in its test accuracy. Conversely, neurons classified as bad tend to diminish in influence over the course of training, ultimately contributing minimally to the network's 's overall performance. For good neurons, the update rules for feature coordinates can be reformulated
neuron if a, I sign(w;"), (0) ), and conversely,
sign ( )u (0(t)))
(++1) (1 n7a sign(u; (w )w(")
(0) (t) sign(w (w 7. u sign Ww r,2 (1:2) sign(wi (0) (0) (w p.k)
(0) (2)
(5.3)
+
sign (w, wrr
For neurons classified as bad, the update rules for feature coordinates can be rewritten as: sign(w 10 ((+1) = (1 (a sign(w (0) (
(
sign(w, w sign(w (0) (t) 2 ... sign(w
(0) (1)
(5.4)
n
sign(w, (0) (t)
w
Comparing equations (5.3) and (5.4), becomes apparent that the feature coordinates of good and bad neurons exhibit divergent behaviors. Consequently, the feature coordinates of good neurons will significantly outweigh those of bad neurons in the long term. With the regularization parameter set in Condition 4.2, derive the following lemma illustrating the divergent trajectories of population gradient descent for both neuron types:
Lemma 5.1. Under Condition 4.2, for good neurons E f2 := fr [m] a, I sign w ())) the feature coordinates will remain the same as initialization throughout the training:
w W.
(1)
(0)
Vj E [k], 2 0.
8

---

For bad neurons E R. == fr f - -I[ sign(w;))} } the feature coordinates will decay faster than noise coordiantes:
(t+1) 0 sign(w, (0) ( S (1-mA) sign(w )w/
Vj [k], 0.
According to (5.2) and Lemma 5.1, after training 7 - Okk log(d)) iterations, bad neurons and noise coordinates in good neurons diminish to a magnitude of (11ppoly(d)) as shown in Lemma 5.2. In contrast, the feature coordinates of good neurons remain unchanged. Lemma 5.2. Under Condition for.for T 2 (k 1> - log(d). it holds that
[ $ d (k+1),
(T)
Vr Sgg. [d] [K],
S d (k+1),
Vr Sb. j [d].
This leads the following approximation for the trained neural network:
m
f(W()) x Σ a
((w
(T x))
a (ra((w)
rE
(II (ign(w((9) o (((w rEBx
Σ rEox
[I
o o((w (ign(
x))
Σ
r:[1:k] x(Ixt)))
Under Condition 4.2, the condition on m ensures a balanced distribution of neurons across different initializations, approximately m/2 m//2+1_ given 2 kinds of possible initializations. This results in the trained neural network f(W(T), x) closely approximating (m/2*+1). f(W", x)).
5.2 Stochastic Sign Gradient Descent
Transitioning from the trajectory trained by population gradient descent, this section delves into the dynamics under sign stochastic gradient descent (Sign SGD). We commence by presenting lemma that estimates the approximation error between the population gradient and the stochastic gradient.
Lemma 5.3. Under Condition 4.2, with probability at least 1 8 with respect the online data generation, the stochastic gradient approximates the population gradient well:
OLD(WO)) ()
E
[0,70, e [m], E [d].
Owr.
Owrg
where T,00 is the loss of randomly sampled online batch S, and
= (k 83/2 B/
The choice of batch size Odd our algorithm is crucial for gradient concentration. According to Lemma 5.3, the gap between stochastic gradient and population gradient is bounded by || 1 At initialization, the absolute value of the population gradient on the signal coordinate approximately ((d-(k-1)/))) ||w, |-11 To ensure the stochastic sign gradient matches the population sign gradient, the approximation error e must be smaller than this value, which requires
= ((d-(k-1)/) Solving B-1/2 + (k3 3 d (k-11) yields our sufficient batch size.
Building upon this approximation guarantee from Lemma 5.3, and considering the established order of 61 and [| |2, we arrive at an important corollary.
Corollary 5.4. Under Condition 4.2, given the same initialization, with probability at least 1 6,
the stochastic sign gradient is the same as the population sign gradient:
sign (TLp(W())
(T
=sign
sign
Vt [0, TT.r [m].j j E [d].
Owry
Owry
This corollary suggests that, under identical initialization, the trajectory of model trained using population gradient descent will, with high probability, align with the trajectory of a model trained using stochastic gradient descent.

---

Conclusion and Future Work
In our study, we have conducted detailed analysis of the k-parity problem, investigating how sign Stochastic Gradient Descent (sign SGD) can effectively learn intricate features from binary datasets. Our findings reveal that sign SGD, when employed in two-layer fully-connected neural networks solving k-sparse parity problem, is capable of achieving sample complexity O(d*=1). Remarkably, this result matches the theoretical expectations set by the Statistical Query (SQ) model, underscoring the efficiency and adaptability of sign SGD.
Looking ahead, an intriguing direction for future research to explore the possibility of learning k-parity using SGD with even smaller queries that surpass the SQ lower bond, and understand whether more standard neural network architectures allow such improvement. This potential advancement could pave the way for developing more efficient algorithms capable of tackling complex problems with weaker data requirements. Another promising direction to extend our results to non-isotropic data settings (Nitanda et al., 2024), where sign gradient descent with momentum could be effective in handling the transformed feature space.
Acknowledgements
We thank the anonymous reviewers for their helpful comments. YK, ZC, and QG are supported in part by the National Science Foundation CAREER Award 1906169, IIS-2008981, and the Sloan Research Fellowship. SK acknowledges: this work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence; support from the Office of Naval Research under award N00014-22-1-2555 and the National Science Foundation Grant under award #IIS 2229881.
References
ABBE, E., ADSERA, E. B. and MISIAKIEWICZ, T. (2022). The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory. PMLR.
ABBE, E., ADSERA, E. B. and MISIAKIEWICZ, T. (2023a). Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory. PMLR.
ABBE, E. and BOIX-ADSERA, E. (2022). On the non-universality of deep learning: quantifying the cost of symmetry. Advances in Neural Information Processing Systems 35 17188-17201
ABBE, E., CORNACCHIA, E. and LOTFI, A. (2023b). Provable advantage of curriculum learning parity targets with mixed inputs. In Seirth-sevntth Conference on Neural Information Processing Systems.
BALLES, L. and HENNIG, P. (2018). Dissecting adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning. PMLR.
BARAK, B., EDELMAN, B. L., GOEL, S., KAKADE, S., MALACH, E. and ZHANG, C. (2022). Hidden progress in deep learning: Sgd learns parities near the computational limit. arXiv preprint arXiv:2207.08799
BERNSTEIN, J., WANG, Y.-X., AZIZZADENESHELI, K. and ANANDKUMAR, A. (2018). signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning. PMLR.
BLUM, A. (2005). On-line algorithms in machine learning. Online algorithms: the state of the art 306-325.
BSHOUTY, N. H. and FELDMAN, V. (2002). On using extended statistical queries to avoid member- ship queries. Journal of Machine Learning Research 2 359-395.
CHEN, X., LIANG, C., HUANG, D., REAL, E., WANG, K., PHAM, H., DONG, X., LUONG, T. HSIEH, C.-J., LU, ET AL. (2024). Symbolic discovery of optimization algorithms. Advances in Neural Information Processing Systems 36.
10

---

CHIZAT, L. and BACH, F. (2020). Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory. PMLR.
DANIELY, A. and MALACH, E. (2020). Learning parities with neural networks. Advances in Neural Information Processing Systems 33 20356-20365.
DOWNEY, R. G., FELLOWS, M. R., VARDY, A. and WHITTLE, G. (1999). The parametrized complexity of some fundamental problems in coding theory. SIAM Journal on Computing 29 545-570.
DUMER, I., MICCIANCIO, D. and SUDAN, M. (2003). Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory 49 22-37.
DUTTA, C., KANORIA, Y., MANJUNATH, D. and RADHAKRISHNAN, J. (2008). A tight lower bound for parity in noisy communication networks. In Proceedings of the nineteenth annual ACM-SIAM symposium Discrete Algorithms.
EDELMAN, B., GOEL, S., KAKADE, S., MALACH, E. and ZIINGG, C. (2024). Pareto frontiers in deep feature learning: Data, compute, width, and luck. Advances in Neural Information Processing Systems 36.
FARII, E., GOLDSTONE, J., GUTMANN, S. and SIPSER, M. (1998). Limit on the speed of quantum computation in determining parity. Physicul Review Letters 81 5442.
FREI, S., CHATTERJI, N. S. and BARTLETT, P. L. (2022). Random feature amplification: Feature learning and generalization neural networks. arXiv preprint urXiv:2202.07626.
GLASGOW, M. (2023). Sgd finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the xor problem. arXiv preprint 11111:2309.1511.
HU, K., REN, Z., SISKA, D. and SZPRUCH, L. (2019). Mean-field langevin dynamics and energy landscape of neural networks. arXiv preprint 175.77990..0776.
JACOT, A., GABRIEL, F. and HONGLER, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems.
J1, Z. and TELGARSKY, M. (2020). Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations.
KEARNS, M. (1998), Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM) 45 983-1006.
KLIVANS, A. R., SERVEDIO, R. A. and RON, D. (2006). Toward attribute efficient learning of decision lists and parities. Journal of Machine Learning Research
LIU, HI, LI, Z., HALL, D., LIANG, P. and MA, T. (2023). Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprint arXiv:2305. 14342..
MEI, S., MONTANARI, A. and NGUYEN, P.-M. (2018). A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences 115 E7665-E7671.
MENG, X., Zou, D. and CAO, Y. (2023). Benign overfitting in two-layer relu convolutional neural networks for xor data.
MILNE--THOMSO, L. M. (2000). The calculus of finite differences. American Mathematical Soc.
NITANDA, A., OKO, K., SUZUKI, T. and Wu, D. (2024). Improved statistical and computational complexity of the mean-field langevin dynamics under structured data. In The Twelfth International Conference Learning Representations.
RIEDMILLERR, M. and BRAUN, H. (1993). A direct adaptive method for faster backpropagation learning: The rprop algorithm. In IEEE international conference neural networks. IEEE.

---

SUZUKI, T., WU, D., OKO, K. and NITANDA, A. (2023). Feature learning via mean mean-field langevin dynamics: classifying sparse parities and beyond. In Thirty-sevnnth Conference on Neural Information Processing Systems.
TELGARSKY, M. (2022). Feature selection with gradient descent on two-layer networks in low- rotation regimes. arXiv preprint arXiv:2208.02789/
VARDY, A. (1997). The intractability computing the minimum distance of code. IEEE Transactions Information Theory 43 1757-1766.
WEI, C.., LEE, J. D., LIU, Q. and MA, T. (2019). Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. Advances in Neural Information Processing Systems.
XU, Z.,, WANG, FREI, S., VARDI, G. and Hu, (2023). Benign overfitting and grokking in relu networks for xor cluster data.
Zou, D., CAO, Y., LI, Y. and Gu, Q. (2021). Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108.11371
12

---

Limitations
While our study provides valuable insights into the effectiveness of SGD in learning the k-parity problem, there are some limitations:
Our study focuses on sign gradient descent (Sign SGD). This approach normalizes the gradient, ensures uniform neuron updates toward identifying parity, and effectively nullifies noisy coordinate gradients. However, it's worth noting that data may be presented in non-standard or unknown coordinate systems, which could limit Sign SGD's effectiveness. To address this limitation, future work could explore alternatives such as normalized gradient descent with an adaptive learning rate incorporating momentum into Sign SGD.
Our analysis primarily based on polynomial activation functions. While effective for the standard k-parity problem, extending our approach to other activation functions like sigmoid or ReLUU presents challenges. This extension could potentially be achieved through polynomial function approximation. However, the main challenge lies in identifying an appropriate functional decomposition and accurately characterizing the approximation error during training.
By acknowledging these limitations, we aim to provide a transparent assessment of our work's scope and potential areas for future exploration.
A Experiments
In this section, we present series of experiments designed empirically validate the theoretical results established in our main theorem. The primary objectives of these experiments are to (I) assess the test accuracy of the trained neural network, thereby corroborating the theorem's 's results, and (2) verify the key lemmas concerning the behavior of good and bad neurons. Specifically, we aim demonstrate that for good neurons, the feature coordinates remain largely unchanged from initialization while the noise coordinates decay exponentially. Conversely, for bad neurons, we expect both feature and noise coordinates to exhibit exponential decay.
Model. We generated synthetic k- d-parity data based on Definition 3.1. Each data point (x, y) with E Rd and {+1} is produced from distribution DA, where A specifically is taken as [k]. We utilized two-layer fully-connected neural networks with m number of neurons. The network employs
polynomial activation function (2) = ²². The first layer weights for the r-th neuron, w E Rd,
were initialized following binary scheme, where ( Unif( { (+1)d). The second layer weights for the r-th neuron, dr, is randomly initialized as 1 or -1 with equal probability.
Computation Resources
The experiments are conducted on A6000 server. As these are synthetic experiments, the requirement for computational resources minimal.
Training. Our model was trained to minimize the empirical correlation loss function, incorporating L2 regularization with a regularization parameter set at X 1. The training process utilized online stochastic sign gradient descent (Sign SGD) with fixed step size 77 and a predetermined batch size B. The principal metric for assessment was test accuracy. Our experiments were conducted considering parity & E (2,3,4 4.
For h: = 2, the model configuration included data dimension of d = 8, a hidden layer width of m 12, total of T 25 epochs, a learning rate 1) = 0.1, an online batch size of B 64, and threshold for sign set at م = 0.3. In the case of = 3, we employed a data dimension of 16, increased the hidden layer width to 48, extended the training to T 50 epochs, adjusted the learning rate to 17 0.05, used an online batch size of B 256, and set the threshold for sign at 1. For k = 4, the model was further scaled up with a data dimension of d = 20, a hidden layer width of m 128, a training epoch of T 100, a smaller learning rate of r 0.02, an online batch size of B- 2048, and a threshold for sign established at = 3.
Experimental Results. The evaluation of test accuracy across various configurations is presented in Table 3. Using neural networks with merely (k(k) neurons, we observed high test accuracy for k k-parity problem with & e (2,3, 4), confirming the results of our main theorem (Theorem 4.3).
13

---

These empirical results validate the efficacy of our studied model architecture (3.1) and training methodology in tackling the k-sparse parity problem.
To further validate our theoretical findings, we examined the change of feature and noise coordinates
for the first neuron wi (+) over multiple iterations, focusing specifically the setting k {2. 3, 4). Figures 2, 3, 4, 5, 6, and visually represent these trajectories. Our empirical findings reveal a consistent pattern: the feature coordinates ('i,1)..... wi,))
(1) of the neurons identified as good (with
initialization satisfying a, - w/y) exhibit relative stability, while their noise coordinates (wf. (1.++ show decreasing trend over time. In contrast, the trajectories for neurons classified as bad (with initialization satisfying a, - -I w indicate general reduction in all coordinate values.
These empirical observations support our theoretical analyses, as outlined in Lemma 5.1 and Lemma 5.2, showcasing the consistency between the theoretical foundations of our model and its practical performance. The disparities between good and bad neurons, as evidenced by their feature and noise coordinate behaviors, underscore the nuanced dynamics inherent in the learning process of k-parity problems.
k
2
3
Test Accuracy (%)
99.69% 99.69% + 0. 0.29%
97.75% + 1.37% 96.89% + 0.44%
Table 3: Test accuracy for solving k-spasse parity problem with (2,3, 4), averaged over 10 runs.
Change of the first Neuron in the Hidden Layer
Change the first Neuron the Hieden Layer
1.00
1.00
Teature wiT
mideen Layer Weigts
0.50
Nois 1:
Noiwe 2: 2
0.25-
0.25
Feature m/)
0.00
Nuisw 1: nl's
60.25
Noise 2: mf2
6025
-0.50
-0.50
-0.75
1.00
10
15
20
25
10
15
20
25
Epochs
Epochs
Figure 2: Illustration of 2-parity good neuron
Figure 3: Illustration of 2-parity had neuron
with initial weights Wi,1 = 1, 11, 1, and
(0)
(0)
with initial weights Wi,1 1,, Wi,2 = 1, and a1
(0)
a1
Change of the First Neuron in the Hidden Layer
Change of the Airst Neuron the Hisden Layer
1.00
w/:
Festure w
0.75
Festure 3, m
mipaa Laye Weggha
0.50
0.59
Noise Mf
0.25
0.25
0.00
Feature m..
-0.25-
Feature 2: w?
-0.25
Festure w/.
-0.50
-0.50
Noise M..
-1.00
Noise 3: wf*
-1.00
10
20
Epochs
50
10
20
Epocts
30
40
50
Figure 4: Illustration of 3- -aritt good neuron with initial weights (0) = 1, w 1, and aj 1.
Figure 5: Illustration of 3-parity bad neuron
(0)
with initial weights (0) = 1, w1 = -1 w = 1, and 0 = 1.
1, w
14

---

Change of
Layer
Change
Hidden Layer
1.00
1.00
Feature 1: m/h
0.75
Festure 1: wd:
0.75
Feature m/
Inddin Negita
Festure m//
Feature mi
0.25
0.25
New 1:
0.00
Noise 1: wf's
0.00
Noiw 2: wl's
M.
-0.50
Noise
-0.50
-0.75
-4.75
100
60
Epochs
Epochs
Figure 6: Illustration of a 4-parity good neuron (0)
Figure 7: Illustration of 4-parity bad neuron (0)
with initial weights W1,1 -1, 112
(0)
-1,
with initial weights W1,1 -1, Wi,2 (0)
(0)
1,
(0) W1.3 1, w1,4 = 1, and 01 = 1.
Wis = 1, w1,d -1,, and 01 = =1.
B Preliminary Lemmas
During the initialization phase of a neural network, neurons can be categorized into 2 distinct groups. This classification is based on whether each feature coordinate is positive or negative. We define these groups as follows:
Dig bo fr E [m]] sign(w{)) - bj, Vj E [+]]]
where by, b2, by [=1]. To illustrate with specific examples, consider the following special cases:
Q11-.1 = fr E [m] WT
0, 0, E [+]
Q-1-1---1 = fr E [m] w
0, Vjj E [k]]
In these cases, 2 1.... represents the group of neurons where all initial weights positive across the features, while 1- consists of neurons with all initial weights being negative. Within each group of neurons, can further subdivide them into two subgroups based the value of a,- Let's denote
Og = T [m]] a, II sign (w (2)) Stb = { [m] a, II sign(w?9)
where Py denotes the good neuron set and Q2 denotes the bad neuron set. We will later demonstrate in the proof and experiments that neurons in 22g and neurons in Q2, exhibit distinct behaviors during the training process. Specifically, for neurons in Pgg. the feature coordinates will remain largely unchanged from their initial values throughout training, while the noise coordinates will decrease to a lower order compared the feature coordinates. On the other hand, for neurons in Pp. both feature coordinates and noise coordinates will decrease to lower order compared to their initial values.
In order to establish the test error result, it is essential to impose condition on the initialization. Specifically, the number of neurons for each type of initialization should be approximately equal. Lemma B.I. With probability at least 1 - 8 for the randomness the neural network's initialization, the sizes of the sets Pgg and S4p are bounded as follows:
14xl. 19abl ([1-a))m/2) (1 a)m/2].
Besides, the intersections of Do by with both Og and Pb are also bounded within specified range:
be n Pgl. Roi nlo [[1 - am (1 + amm/2 ++1]
where
3 2 log (2 2
m
15

---

Proof. Let X, > 0....
[w/ (0)
(0)
> 0, 1].
Then, by Chernoff bound, we have
a²m
Σ X
m
2
m
S 2exp
2
2
3 2k21
Then, with probability at least 1 6, we have
(1 - a)
2 S 1811--.1 782g S (1+a)
m
m
2k+1
where
3 2 (2g(2/5)
m
By applying union bound to all 2 kinds of initialization, with probability at least - ō it holds that for any 1b.b2---be n 2g and 0b.bar.bb St ((b). ,b)) E {=1}*)
(1 - a)
m
I
192 b2. by 0m2g S (1 a)
m
2k+1
2
(1 a) 2
m
v ba
n0a S + a)
m
2h+17
where
3. 24+1 1og(2k+2/0)
m7
C Warmup: Population Sign GD
In this section, we train a neural network with gradient descent on the distribution D. Here we correlation loss funetion f(y, y) 1 vÿ. Then, the loss on this attribution is LD(W) E(x.))=D((() (ly, f(W, x))], and we perform the following updates:
(++1) (1 w/ 7 - sign Slign(Vw..o Lo.(L))
We assume the network is initialized with symmetric initialization: for every [m], initialize Wr (0) Unif((-1,1)d) and initialize a, ~ Unif({-1,11).
Lemma C.1. The following coordinate-wise population sign gradient updote rules hold:
(1) (t)
(t)
(t+1) = (1 -1-10) m + n sign kla, Wrj
W w
Wrik
j [k]]
(8)
w W
(++1) w PJ
= (1- 1
j $ [k].
Proof. For population gradient descent, we have
(1+1) (1 1}²) w(() 17 sign W.. L.D (W))
(1 17/)= w((() 17 sign(a, (a, (V xx)])
(1 n72) w((() 17 sign kay E (x)) x)) xx)+-11).
Notice that for j & [kc], we have
((x,y)) ((w ((w))x)))*++ x-) E(x,)~D T1 ".E
Σ
w
(1)
..... (1)
Wr Fii ... 13o-.)
51, J6-1
Σ
w
r.j
(0)
w
T-j--
E Exxgy I102 ... IK ... [p2-1
far fe-1
0,
16

---

where the last equality is because
, & {1, k, This implies that
w rd
(((+1) (1 177) w()
For j E [k], we have
E ((x.))-Dlya, x)){-11
(()))//))+x)11 (xx))= 2142-- 23JI
Σ
whit
w m 2/ -..
1 J6-1
Σ
(1)
J (1x.)>>((110) ... Inlydh ... -.
r.
...
fa Je-1
(t) (t) (1)
r, 222 w
(A: 1)!
r
where the last inequality is because -x 01 ... IAZgJhj (i,51, ... _h-13 = {1,,2 2, ... kj. It follows that
IJ--1l * O if and only if
(t) (1)
(t)
((+1) = (1 m/a w/3 sign W/y
kla,
wr, 7
Wirk
(t)
T
Given the update rules in Lemma C.I, we observe distinct behaviors for good neurons (2gg) and bad neurons (5%). The following corollary illustrates these differences:
Corollary C.2. For any neuron r E -o nggg the update rule for feature coordinates (j E [1]] given by:
((+1) by
m
sign(b, sign (b) ... sign(by (brw
Iw r.
w
(c)
+n.
sign(b, w())
w
k!
For any neuron Sb....bb bb abr the update rule for feature coordinates (j [k]) is given by:
b
((+1) = (1 m/)b,
sign(b (1 sign (igg(byrr)) (b2m) sign(h, (!))
sign(by
Iw
r w
Wo.k
p
n
I
By setting the regularization parameter 1, observe noteworthy property of the weight of feature coordinates in good neurons. This is formalized in the following lemma:
Lemma C.3. Assume À 1 and p < kt. For neuron 9o,,..b 0Sg. the weight associated with any feature coordinate remains constant across all time steps 2 O. Specifically, it holds that:
byw!)
(t)
Vj
[k],
1
0.
Proof. We prove this by using induction. The result is obvious at 0. Suppose the result holds when & = Then, according to Corollary C.2, we have
(f+1) = (1 - n))b, by /
sign(br w (bg (1) ... sign sign(bsuun w. (.2 sign (b, w,!!!! (!
7
2
r.
P
+ .
(t)
7c!
w
r
(1 -) 1 pl
17

---

The following lemma demonstrates that for bad neurons, the weights of feature coordinates tend to shrink over time. The dynamics of this shrinking are characterized as follows:
Lemma C.A. Assume À = 1 and n/(1nA) < (p/kt)/=s For neuron r E bb,bb-.bb O Sb. the weights of any two feature coordinates j and j' (where j. [k]] are equal at any time step, that is, bywiz = by Furthermore, the weight of any feature coorlinate j E [k]] evolves according to the following inequality for any 2 0:
0 < 65
(1+1) < - -11
Proof. We prove this by using induction. We prove the following three hypotheses:
byw (t)
by wrggt
(t)
Vj.J' [k]]
(H1)
byu rj >
(1)
Vj E [k:].
(H2)
bywrs (e+1)
n
(0)
vj E [R:]
(H3)
We will show that H (0) and H2(0) are true and that for any 1 2 0 we have
H2(l) HL)
(1) (1)
- (1+1),
(t). Ht( H2(++
(0) and (0) are obviously true since b = 1 for any j E [k].. Next, we prove that
Hz(t) - H3 (t) and H, (t), H2(1) -t + 1). According to Corollary C.2, we have by
(++1) = (1 n,,
sign(b, w sign (b2 w w ... sign (bu with))
w
(1) r,
1,2
w.
r.
(t)
p
sign (,
(8)
h!
u (1)
(1 (1-)))b 1
r.
1.2
P.
(C.1)
(t)
k!
S (1 m)
where the second equality is by (t). This verifies (t).). Besides, given Ht(t), we have
Iw (2) (c)
(0)
I (2)
(t)
[ 7.2
w
w.
Vj.j' E [k).
w (2)
1 rg
rgg
Plugging this into (C.1), can get
by (++1)
by (++1)
Vj.j' E [k],
which verifies (t + 1). Finally, prove that Ht),), Hz(t) = Hz(t + 1). By (C.1) and H, we have
b ((+1) = =1 (1- ( - 17 1 1w k-1 > P
((+1)
K!
If [1/3]] < (p/k!)= we can get
by b (t+1) = (1 nn.-n)bb >0. O.
If (1) 2 (p/k!)=- given that
1 nn (p/
71
we can get
byw
(1+1) = (1 - nd)b, (2) - 17 > 0.
18

---

Given Lemma C.3 and Lemma C.4, we can directly get the change of neurons of all kinds of initialization.
b2. ... b&) Corollary C.5. Assume x = 1. p kl and (1-mA) < (p/kl)ET. For any fixed (b (br,b2.". (+1},, considering
by we have the following statements hold.
For any neuron r bb O Ag the weights of feature coordinates remain the same as initialization: Wr. by for any 0 and E [k].
For any newron E bz n So the weights of feature coordinates will shrink simultaneousty over time: byw, = by W (t), ni for any t 2 0 and j. E [k] and
0 < by (1+1) I (1 - m/)) by
for any any t and j E [k].
Building on Corollary C.5, we can now characterize the trajectory of neurons over time. Specifi-
cally, after time period T Oknn - loo(d)), hold:
(oooond) the following observations about neuron weights
Lemma C.6. Assume X p < k! and n/(1 n7) (p/k!) For T 2 (Is + 1)m 1 log it holds that
[r bj:
(T)
Vr b7 0 ngg.i E [1]]
|m0 rj I dd(t)))
Vr Sg. [d] \ [kt],
| S dd(++))
Vr Sb.j [d].
Proof. The first equality is obvious according to Corollary C.5, We only need to prove the inequalities. According to Lemma C.I. we have for any r E [m]] and j E [d] \ [k] that
( = (1 nA) 10 ((1 m))((A) ( exp(-TTA) < d (k+1).
where the last inequality by T 2 kn-ix - log(d). According Corollary C.5, for any Qn and E [k], we have that
@ 1 I (1 - maa [ = ((1 ((1- (1-m7))00) 7))(02)11)) S <exp(-TT>) s dd (k+1),
Lemma C.7. Under Condition 4.2, with a probability of at least 1 - 8 with respect to the randomness in the neural network's 's initialization, trained neural network f(W(T), x)) approximates accurate classifier (m/22+1). f(W*, x) well:
((W(T), x)
P Px
(m (m/2k+l) I). f(W-,x) E (0.5,
21-6.
Proof. First, we can rewrite (4.1) follows:
f(W'
Σ
(b....bu by) o((Wi x)).
(b1 Bx)E
where w [b2, b..... bb. O, ... TO To prove this lemma, we need estimate the noise
part of the inner product (w!") (T) x). By Hoeffding's inequality, we have the following upper bound
for the noise part - ;. az:
d
Px
Σ
r.j
x E
(T) w TJj zúj
20
Px
w
j=
j=++1
j=k+1
x²
$ exx
d Σ
[1o[912]
19

---

Then with probability at least 1 - e/m we have that for fixed r E [m]]
d Σ
w
(T) zjj
S
(2log(2m/c))
Σ
[w (2)
1==++
5 j-
/c) |w (7)
r.[[++1 ll2
S V2 22m/ / -))-
(k+1) (d 1)2/2
S <d
where the last incquality is by Condition 4.2. By applying union bound to all m neurons, with probability at least 1 we have that for any E [m]
(T) Wri Ii S <d
(C.2)
j=b+1
By Lemma C.6, we have
m [(W(1), (T) x)
2k+1 f(W", xx)
24
< Σ (,o((w!T) (T), ,)) 2*+I
0. ((w x)) + Σ
Lapo((!!T) (T), ,x))
g
Σ
(( (T), xx))
m
T (( ((Wor_.be
+
Σ a ((w (T) (x))
2
(n bx)E
Ra n0g
reBh
Σ
am
Σ
(((w!(7)x)) a b(w (()1
byz
+
25+1
(b WNEE
/=1
Σ rEs
ano((w (T) xx))
(x))
k
Σ am
am
bygr
+
Σ
kd ke (kk + (lll+ttt))))) + -120 (2d (2
kd
26+T
(0 (+)e
j=1
2o .. mf4g
24* (1 - + 152g Ikd x (k + d k-1 + /00 (2d
2k+I
2 k (1+e -2 + 0.5(1 + aakd * (K + d x) 6-1 + 0.5(1 + a) (2d m,
where the first three inequalities are by triangle inequality and Lemma B.I: the fourth inequality is due to
((((())) ((w((),)))) ,)) ((W x))
(((W(T) x))** ((w6, bb x
(w!T))x x) - -(wi, x|| k(mmxx (l(w!?) (ww(T),))l, xx),1(( (W b. x)
d
k max {
d
Σ by })
b
(T)
Σ byzy +
Σ
(T)
und Iz
Iz
j=k+1
j=k+1
d
A:
A-1
k
Σ
(T)
Σ وورو
+
Σ
(T)
23
j=
j=b+1
< kd (k + #)
by (C.2), mean value theorem and Lemma C.6 and for r E So
(a((w(?) (T) xx)] < (w x){* < (kd (k+1) + d d-b)
kg - (2d
(C.3)
20

---

Since (m/2 If((W", "x), x)] = 0.5k! - m, then as long
22
(e (e+e* (e+to))- and S
8
2
we have
(f((() 1l f(W" .x)
(m/2k+2) ([(W][((W)))))))
ak (1 3) 0.5(1 + kd (k + d d + +.5((1 - a))
0.5k!
2ah222 ((1=*=+++_tttt 2)6 + a) '(K + d
+
a1+
(2/k(k/e)*
2
cete
c
d
k
k-1
C
2
2e K
V nk
2
+
Th
1
k
d
ok
kdk
0.5,
where the second inequality is by Stirling's approximation. Then it follows that f(W(T), xx)
(m/2kt1). f(W*,x) E e00.5,
D Stochastic Sign GD
In this section, consider stochastic sign gradient descent for learning k-parity function. The primary aim of this section is to demonstrate that the trajectory produced by SGD closely resembles that of population GD. To begin, let's recall the update rule of SGD:
(++1) = (1 - An) (( + sign
Σ (x,y)ES,
d((w?"), ,)) aryx
St
where [S&] = B. Our initial step involves estimating the approximation error between the stochastic gradient and the population gradient, detailed within the lemma that follows.
Lemma D.1. With probability least 1 with respect the randomness of online data selection, for all t T, the following bound holds true for each neuron [m]] and for each coordinate j E |d]:
Σ
d'(w(()) x)) a,yx Bix,)) ((W(())), x)) a.yry]] Sei /el//w(())
k- 11
(D.I)
JS
(x,
where Ej is defined as
2 (0/2)(00g( log(SmdT/8))
kd
61
VB
8m..T
Proof. To prove (D.1), let us introduce the following notations:
(x,(X,9) y) a'((w!? x)) 0,y2, k((w((()))))))) x))* k-1 ayyyyj
b 9) = 9hu (x. y) (")
(0, x)1 S 7].
where Gr,y (x, y) represents the gradient the point (x. v). and hx, y) denotes the truncated version of gr,j (x, y), which is employed for the convenience applying the Hoeffding's 's inequality. Firstly, utilizing Hoeffding's inequality, we assert the following:
Bx
P
Σ
(x. u) - D(n y) 2 x
< 2exp
(D.2)
B
2(k
(X,
21

---

Furthermore, we can establish an upper bound for the difference between the expectations of Ar. (x. V) and Ir (x. y):
R Dlx (x.y) - B(x.w)DDnssx v) = ( (x, v) [((w x)1 > >]
kd 11/2 11 IP ((
, xx) > 7)
72
kd ( 11/2 11/2
1| 2exp
2 w (
(D.3)
where the first inequality is by Cauchy inequality and the second inequality is by Hoeffding's inequality. Additionally, with high probability, the gradient and the truncated gradient are identical:
P
1e (x, v)
Σ
Ir (x,(X,))
=0
B
B
(X.u)ES,
(x,,))E,
P
Σ
gr.(X,, 8) 1 [[ ( x)
> 71
=0)
(x.W)ES.
P
(((W())
( x)1 S 7, V(x, 3) St
(D.4)
B
72
exp
w/ (~ 11
72
2 1 2B exp
where the second inequality applies Hoeffding's inequality. Combining inequalities (D.2), (D.3), and (D.4), we can assert with probability at least
Br² 21k
(
72
1 - 2exp
2B exp
exp
(D.5)
2 w/
(1)
that the following inequality holds:
722
Σ
gna(x, 4) - (xx,)) v) S x + kd || (|
2exp
B
2/| //
11
(x.y)ESt
(D.6)
By setting 7 2o (16B w 10 and v2kg probability at least 1 - ō, the following bound is true:
establish that with
1
Σ
(x y) E(x.)))Drrjxx, v)
B
(x.))ES,
V2k k- - log(8/0) ked 1)/2 !0 14911--26
+
VB
8B
2 21o2((o (0000)))(BB))(((---0 ())(((11)) 13/2 (8/) (atl////)//////////1/1
(1) k-1
112 ||1-11
VB
8B
Applying a union bound over all indices E [m]. E [d], and iterations E [O.T 1), we conclude with probability at least - 8 that
Σ Oxs(X,9) v) - B(x.n) v) (x.))ES,
B
2*/2 2=22((og(16m)17))8)))4)) 1)/2 log (og(SmmT///
k-1 11/2-1)/2 (1) 11
VB
8mdBT
22

---

2 21PK((og((6mdBB/)))) log(8mdT/0)
kd/2-
vB
8mBT
Based on Lemma D.I, we can get the following lemma showing that with high probability, the stochastic sign gradient follows the same update rule the population sign gradient.
Lemma D.2. Under Condition 4.2, with probability at least ô with respect to the randomness of online data selection, the following sign SGD update rule holds:
(t)
(f)
(1+1) = =(1 (1-1)/ =1 + +1--80 sign kla, Wey
2 w
wirh
j E [k:]
(8)
Wr.
(++1) TT = - m (e)
j $ [R:].
Proof. We prove this by using induction. We prove the following hypotheses:
|| 1|2 S || // 12, 1|,
Vr E [m].
(H))
(2) 1r
(1+1)
(1 --))) + n sign kla,
nn ...
(1) Vr E [m].j [k].
(H2)
w 3
w(t (1 (-
Vr E [m].j $ [k].
(Hg)
b =1
vr E P Ggg: Vj [k].
(H,)
b (1) by
Vr E ba Ugg vj.j
[k]]
(Hş)
0 < (x, < (1 m
((+1)
Vr E bu n ng Vj E [k].
(H₂)
We will show that (0), H3()), (0) and H0) are true and for any 2 we have
Ht(t), (t) = (t + 1). (This can be established by adapting the proof of Lemma C.3; hence, we omit the proof details here.)
Hz(t), H₂(() - Hs(t 1), Ht((). (This can be shown by following the proof of Lemma C.4, so the proof details are omitted here.)
Ha(t), (t). (t + 1). Ht(() (t)..
(H) = H1 + 1). H3(l 1).
Ho) and Ho( are obviously true since w Hz(0) and (3(0) are true, we only need to verify that
(0) = b, for any r E Db
and j E [K]. To prove that
sign
o' d'(w ((w((),x)) y.y
x))
sign
kla,
w
w
7.2
... w r.kk
Vj [k], (D.7)
So
(0)
(x.u)E
r.
sign
d'((w(0) (x(w) a. yrz 0.
Yj [k.. (D.8)
Sn
(x
By Lemma D.I, we have for $ [k]
Σ o' d'(ww x)) (()) arysy
5 (1) k-1 ( 61 .d d <pp
|Sal
(x.))ES,
23

---

leading to (D.8). For j E [k], we have
1
o' ((w,,
x)) x)) a,ya, kla,
w
(0) (0)
r.
(0)
1-1
[o
(0)
(x,1))So
Since - 61 d d 2 p. we can get
(0) (0)
(0)
sign
d'(w!!), (0) x)) a,y
= sign
kla,
Wr.1 7,
r.k
Sul
(1))
(x
which verifies (D.7). Next, we verify that Ha((), H4))), H4(l + 1), Ho(l) HH For r E Sgg given Hs(t), (t) and Ht(t + 1). we can get
(w 12
3
A
Σ ((1 - (1=n)));?)) $
| 12
Σ
s //
j=k+1
For r E Sb. given Ht(t) and Ht)t), we can get
[w((+t)|22 = Σ (
Σ ((1 (2)
d
1 |w
Finally, we verify that (Hr (s)) given (H, (s)) we can prove Ha(t - 1) and H2 + 1) by following the prove of (D.7) and (D.8) given Lemma D.I.
Hz(t 1), Ha(t 1). Notice that l|w, (w
1|2 S ||w, (0) l12
Based on Lemma D.2 and the proof of Lemma C.6, Lemma C.7, we can get the following lemmas and theorems aligning with the result population sign GD.
Lemma D.3. Under Condition 4.2, for T 1 log(d)). probability of least 1 6 with respect to the randomness of the online data selection, holds that
(T) bj.
Vr E Rb Ggg. E [k]]
Iw (T)
I d (k+1))
Vr E Sgg. [d] [k],
|w S (d+())))
(T)
Vr E Sb, [d].
Lemma D.4. Under Condition 4.2, with probability of at least 1 26 with respect to the randomness in the neural network's initialization and the online data selection, trained neural network f ( (x) approximates accurate classifier (m/22 mm/2k+1). f(W", x) well:
(TW x)
P Px
E [0.5, 1.5) 21-6.
(m/2k+)
f(W x)
Based on Lemma D.4, we are now ready to prove our main theorem.
Theorem D.5. Under Condition 4.2, we run mini-batch SGD for = -okgt))--loo(d)) iterations.
Then with probability at least 1 - 28 with respect to the randomness of neural network initialization and the online data selection, il holds that
(xx)))(yf((((T)) x) 2 7m) > 1 11
where 7 = 0.25k! a constant.
Proof. Given Lemma D.4, we have
f(W(T), (x)
PXWD.
(m/2++1) f((W.x) 2 0.5
f(W(T), .x)
PXWDs
(m/2k+1) f(W*,x) E [0.5, 1.5]
24

---

2 -
According to Proposition 4.1, we can get
f(W()) ,x)
PxwD=
(m/2k+1), f(W*, ,x) 2 0.5
uf(W(() ,x)
Px-Dx
(m//2+1) .k! . 2 0.5
Px (yf(W(1), 0.25k! m)
which completes the proof.
E
Trainable Second Layer
In this section, we consider sign SGD training the first and second layers together. In this scenario, we have the following sign SGD update rule:
w (++1) (1- - ?
(1) +
sign
Σ
d'(w!!9,
x at aa yxx)
(E.1)
SPA
(x.a))
a (++1)
a, + 172
sign
o ((w(9)x)))
(E.2)
S
(x,))ES,
where [S.| = B. For training the neural network over 7 O ((A(n))-oog((() small learning rate for the second layer, adhering to the condition:
log(d) iterations, we adopt
Tk e mett -
(e+e))=
12 S
2
The network is initialized symmetrically: for every r [m], initialize w Unif((-1,1)4 and initialize or (0) Unif({- (1,1). Under this setting, denote
(2 ag = r [m] a, II sign (ign(u ) S0 = =fre [m] a,
II sign w
Similar to the fix-se fix-second-layer case, our initial step involves estimating the approximation error between the SGD gradient and the population gradient, detailed within the lemma that follows. Lemma E.1. With probability at least 1 with respect the randomness of online data selection, for all t < T, we have for any E [m] and j E [d] that
Σ (x.V)ES.
d'(w x)) a yr, - E[o' ((w x)) a yx,] I E1 .
[1 (E.3)
JS,
where
2 (074((0((16m log(SmdT/5) kc)k-83/22
6
VB
8m.T
Proof. To prove (E.3), we denote
gri (x, 3) = a' e((w x)) o yr, k((w((,,)) x) ( yr,, hr (x,y) 9r. (x, v) 1 (!( x)1 S {
Initially, by invoking Hoeffding's inequality, we have the following probability bound:
B
P
Σ
(x,() - BixwiDDin (x, v) 2 x
< 2exp
(E.4)
B
2(k 1a (0)
(X.))ES,
25

---

Next, we establish an upper bound for the difference between the expected values of (x, y) and (x, y):
E (xx v) ((x,)))Drns w) = 1 (( (x, y) 1 (( (0) x)) > 7
I kdd - 13/2 / ! 1a ((( ( xx) > 7)
72
S kd 1d | 11
2 2xx
2 21|w 2
(E.5)
where the first inequality follows from the Schwwaz inequality and the second from Hoeffd- ing's 's inequality. With high probability, the gradient and the truncated gradient coincide:
P
Σ
Wn v)
Σ
gr.s (x, 21
= 0
B
(X.))ES
(x.8))
P
Σ (x, 1) 1
x)1 7
=0)
(x
P
(ww()) x)1 7, (xx v) ES
(E.6)
B
72
2 - exx
2| ? 1
72
2 1 2B exp
w/ (2)
Combing (E.4), (E.5) and (E.6), it holds with probability at least
Brd
72
1 - 2exp
2B exp exp
2/| 2"|
that
72
Σ 9rd (x, v) (x. (x, S Sxtad(t-)) 1)/2 (!) (/-))_11111
11 1
B
2/|w -
(X,))ES,
By taking 7 = v log (66B w! 11 ll2 and x */ (0)
(lo)(8/)// 8/88///BB then with probabil-
ity at least 1 - d it holds that
Σ
Irs (x,8) - E(xD) (x,
B
(x,))ES,
V2k
11 1og(8/8)
le 1)/2
wr
(1)
1011 10
+
VB
8B
2 2+/2k((og(16B/))) 1)/2 log log(8/))
(1) k-1
kd(k-1)/2 |/ 11 [// 1
VB
8B
Then, by applying a union bound to all r E [m], [d] and iterations / [0, 1]. it holds with probability at least 1 - that
(x y) E (x, v)
B
(x.))ES,
2 (m/2)())((6 (k1 log (8md7) /8) [|]]] w/ 1018 1|1-1|(00)) 1/a00)
1)/2
kd(k-1)/22 1)/2 w/ (1) k- 1/4911
kd
11
VB
SmdBT
(2FFh(00((16mdBT///)))) log (mddT/8)
kd kddl-3)/28
-1a..)) (
VB
SMBT
26

---

log(d)), Lemma E.2 (Stability of Second Layer Weights), Fort S -ogd)) the magnitude of change in the second layer weights from their initial values is bounded as follows:
10. - a 1 Sc.
where
c 4V Th ( (etter (
-k
8
2
Consequently, the sign of each weight remains consistent time:
(agn(a.") = sign(a.")
Proof. Notice that by (E.2) and sign()) (.) E f, 13,, we can get for any t 2 that
(0) 1/2 S a (111 S o + 1/2
which implies that
|a.0) / S 72l 12T Sc where the second inequality is by s T. and the last inequality is by the condition f/2
rk
ete-1
17
Lemma E.3. With probability at least 1 - å with respect to the randomness of online data selection, the following sign SGD update rule holds:
w: (2) 1,2 n,k
....!
wi =1 -11-n)) 17 sign kla!().
((+1)
j E [M],
(0)
(++1) (1 mn
i $ [A].
Proof. We prove this by using induction. We prove the following hypotheses:
||w((+1)
((((1) 122 S [w (2) l|,
Vr E [mx].
(H))
(6)
(8)
(t)
WrJ
((+1)
(1 mmd) (2) + m1
sign klag)
w.
(1)
w
Vr [m].j E [A]]
(H2)
W
(e+1) (1 " (2)
Vr E [m]]j $ [Ai].
(H3)
b
(1)
=1,
Vr E Sb 0 5 Vj E [k].
(H₂)
b (t)
= byr
Vr E No Agg Vj. E [k].
(H₂)
0 < by
(++1)
< (1 (1- m1))b/,,,,
Vr E ho O Sb. Vj E [k].
(Ha)
We will show that H0)) (g) (0) and H3( are true and for any 1. 2.2 0 we have
Hz(t), (t) = Ht + 1).
H2((), Hs(() - H5(1 + 1), Ha(().
Hs(t), (t)t), H2(t + 1), Hg (t) =t)
(H) = Hb 1), Ha(t 1).
27

---

(0) and (0) are obviously true since (0) by for any E Dbzbz-bb. and j E [A:]. To prove that (0( and H0( true, we can follow the proof of Lemma D.2 by noticing that lat 1. Now, we verify that H2((), (t(() = H4(t 1). By H2(t) and sign(a,") = sign(a? according to Lemma E.2, we have for any neuron r E Rbib2--be Osgg that
(++1) (1 my)6 (t) by
sign(bi w7 (1)
sign (b2w/12 ... ..siin(bbw sign(byw,)) w/
(0) (1) (t) r W
...W....
Wr,k
(t)
0
+
2
100
k!
= (1 - nA) + 1 pl
1
where the last equality is by p S k! c) S kt (1 Ht) - 1), (t()) can be verified in the same way as Lemma C.4 by noticing that S kt c) S k!- la Ht(t), (t).). (t + 1), Ht(t) H (t) can be proved by following exactly the same proof as Lemma C.4. [H](s) 7 H2(t + 1). H3 + 1) be verified in the same way as Lemma C.4 by noticing that 9 (1.1 h-1 < and k! 61 + c) d
p.
Based on Lemma E.2 and Lemma E.3, we can get the following lemmas and theorems aligning with the result of the fixed second-layer case.
Lemma E.4. For T = O(ko)-(A-11 lo(()) with probability of at least 1 8 with respect to the randomness of the online data selection, it holds that
w rj bj.
Vr E Rbybr...b Aggg E [k]]
Im 1 < d (k+1).
(T)
Vr E Jg j [d] \ [A].
|m - (k+1),
Vr E Sb.j E [d].
Lemma E.S. With probability of least 1 - 26 with respect the randomness in the neural net- work's 's initialization and the online data selection, trained neural network f f(W(T), x) approximates accurate classifier (m/ (m/2k+2) f(W x) well:
((W(T), x)
P PAWDA (m/22+1)) f(W*, x)
E [0.25, 1.75] 2
Proof. Let
F(W(T) x) Σ (0) o((w! ((w[T)xx)) x)).
By the proof of Lemma C.7, we can get
((W(()) x) (m/2 22m/2211. f(W", x) (m/2k+1) Is(W*,x)
0.5.
To prove the result, we need to estimate the difference between F(W(T), x) and f(W()),
| x) ((W())))) = Σ (0) . (
(((w!?)) x))
< l (T) 0 00) 1l ,x)
(E.7)
(ww(7) (T) x
c Σ
(ww (T)
xx
8 +c Σ
I( x))
refh
Ja
28

---

where the first inequality is by triangle inequality; the second inequality is by Lemma E.2. Then, we provide upper bounds for terms 1, and 12 respectively. For 1,, we have the following upper bound:
11
Σ 3Egg
((w (2)
r.[1sk] x(1-1) + (2) r,]kk+1:d) x|++1:a))*
$
((w (T)
r,[1:]] ((Ian)1 +
(w
r1[++lad] x(++1 (((Ww (T) r.(1:k] x((xs>| + Kw (T) r: Iad] x 1:4)))
(2)
re
rER
h Σ
Σ
Σ
byoty
+ Ed k(I + R) reg
d
(bar" (e)))
12 n
jml
k
E
Σ
+ + a
m d k(kk + d-
26+1
172
2
(bir" (1)))
j=1
1 + 2/++1 m 21
2/
(1 +
m d k(k d k)*
(E.8)
where the first inequality is by mean value theorem; the second inequality is by (C.2) and Lemma E.4; the third inequality is by Lemma B.1; the last inequality is by Lemma F.3. For 12, we have the following upper bound
1 1+a
12 [00 (2d k2 1
2 m (2d (2d
(E.9)
By plugging (E.8) and (E.9) into (E.7), we can get:
[s(w x) f(W(1), x
I <c((1 + aa2 (1 + 2- + 0.5(1 + a)m d= - + +- + +.5((1 + aam (2d kt)))
Therefore, we have
[(W(() x) J(W()) x)
(m/2k+1) - x))
c.. (1 (1+a)2 (1+ k (1 2)) + 0.5(1 + amm d= ls(k: + )= 0.5(1 + amm k)
0.5k! m
2(1 + aa)2 k² + 2 + (1 + a) d & k(k + d
- (1 + a) (2d k2d
se.
(kTk(k/e)*
( nh
(1 + a)
c (cte-) k
2
+ +1
2
1+
d d- k-1
k
7
e k
+
V
2
( (Re)x
kdd
8
b
c.
1
4
where the second inequality is by Stirling's approximation, and the last equality is due to
F
Auxiliary Lemmas
We first introduce a finite difference operator with step and order n as follows,
= Σ ( (0) - ih).
==0
The following Lemma calculates the value finite difference operating on the polynomial function. Lemma F.1. (Milne-Thomson, 2000) For f(z) x²,, have that (z) h"!!.
29

---

Based on Lemma F.1, we have the following Lemma, which calculates the margin of good NNs defined in (3.1). Lemma F.2. For any integer k, we have
Σ : (-1) 21)* 2 k!.
(F.1)
Proof. Applying Lemma F.1 with f(z) = x. n Lemma F.1 gives,
k Σ 1=
- 21) = -- (1)
2%k!,
where the first equality is due to the definition of finite difference operator and the last equality is due to Lemma F.1.
Lemma F.3. For any positive integer k, it holds that
k 1k 21th S 22h (1+e
Σ
Proof. We can establish the following inequality:
k k
211
2 2
Σ
1K 21th
==0
i=0
1 (1
28
2
i
k
1c
S 2
exp(-= (2))
i
$ 21
exp( -2))
21* e 2)8
where the first inequality is by (+) = (c-1), the second inequality is by L exp(-1) 14 E R. the last inequality is by (?) exp(-22) > 0.
0
30

---

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: The claims made abstract and Section are supported by results Section and also the additional expeiremnts in the Appendix.
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 can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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:
The limitation section presented in page 12.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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- well-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged 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 penalize honesty concerning limitations.
the paper. The authors should use their best
will be specifically instructed
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]
31

---

Yes, the full set of assumptions are provided in Section 3 and the complete (and correct) proof are provided in the Appendix A.
Justification:
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 or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
This paper provides detailed experiment settings Section A, which should be sufficient for reproducing the main experimental results.
Justification:
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it 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 appropriate to the research performed.
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be 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 describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
32

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The experiments in this paper based on synthetic data generated to support the theoretical findings. As such, there is no real-world dataset or code to be made openly accessible. The question of open access to data and code is not applicable in this case, the main contributions are purely theoretical and do not rely on empirical results from specific datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ http:/guidee//Codeuueeeeee wtt.ssummsssiioooooooooooooooeoo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is 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: / /nips. httpcc/ppbb. cwcppblicgguieeecccccccecooooooe wtte//ggiiee//oeeeeeeeeeeee
"CooeeSumissiinn siinbbmiiii 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 as 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 understand the results?
Answer: [Yes]
Justification: This paper provides detailed experiment settings in Section A, which should sufficient for reproducing the main experimental results.
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 a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: This paper provides detailed experiment settings in Section A, which include important details such as the error bars reported Table 3.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables 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
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
The requirement of Compute Resources are stated in Section 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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 NeurlPS Code of Ethics https: : //t///eurrp.../ htc//ppiic/thhiccuideeeeee
Answer: [Yes]
Justification: As theoretical paper, the research presented in this paper has been conducted with the highest ethical standards and is fully compliant with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work provides the theoretical understanding of generic optimization algorithm (SGD). Although there might be some potential social impacts on applications, according to the guidelines, we believe our result does not have direct connection with
these issues.
34

---

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 negatíve 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: As theoretical paper, this work does not involve the development or release of any models datasets, particularly those that might be considered high-risk for misuse, such as pretrained language models, image generators, or scraped datasets. Therefore, the question of safeguards for responsible release does not apply.
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 challenging, and many papers do not require this, but 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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
This paper is theoretical work that does not utilize rely on any existing assets such as code, data, or models from other sources. Therefore, the question of crediting creators or detailing licenses and terms of use for such assets does not apply.
Guidelines:
The answer NA means that the paper does not existing assets.
35

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include 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 in the package should be provided. For popular datasets, paperswithcode. thcode. com datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: As this theoretical paper, it does not introduce or release any new assets such as datasets, code, or models. Thus, there is need for documentation related to new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This theoretical paper does conduct any experiments involving crowd- sourcing or research with human subjects, thus there are no participants, instructions, or compensation details to report.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
36

---

Answer: [NA]
Justification: As this paper is purely theoretical and does not involve any research with human subjects, there study participants, thus associated risks requirements for Institutional Review Board (IRB) approvals.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending 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.
37


Reviews:
[{"review_id": "7RnID9z2nm", "reviewer": "Reviewer_9WvP", "summary": "This work considers learning k-sparse parities with two layer neural networks trained with stochastic signed gradient descent, where the second layer is fixed at initialization and the first layer is trained. It is shown that with the activation $\\sigma(z) = z^k$, a network with width $2^{\\Theta(k)}$ can solve the k-sparse parity problem with $\\tilde{O}(d^{k-1})$ samples in $O(\\log d)$ iterations, almost matching the Statistical Query lower bound for this problem in terms of the number of queries.", "questions": "1. Is there a way to trade off compute (iterations/neurons) against samples in upper bounds while maintaining the optimal number of queries?\n\n2. The authors mention non-i.i.d. data as room for future research. There are perhaps even more accessible settings to be investigated. For example, can these results be extended to non-isotropic data, similar to the setting of [1]?\n\n3. The summation notation in Line 183 might need clarification. I might have missed this, but I didn't see the definition of $s$ used here.\n\n\n[1] Nitanda et al. \"Improved statistical and computational complexity of the mean-field Langevin dynamics under structured data.\" ICLR 2024.", "limitations": "Some limitations could be more explicitly discussed as described in the “Weaknesses” section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis of the paper is conceptually simple and clean, and there is sufficient discussion on the intuition behind the proof techniques in the main text, easily conveying the ideas to the reader.", "weaknesses": "While the goal of this work is to understand the training dynamics of modern neural networks, given the use of a polynomial activation and signed gradients, it is not clear to what extent the intuitions from this work extend to more mainstream algorithms, such as ReLU networks trained with SGD. \n\nFurther, it is possible to more explicitly discuss some limitations of the work. For example, it appears that the algorithm is not rotationally invariant, therefore is using the knowledge of the coordinate system, in comparison with the work of Glasgow (2023) which does not require this knowledge (for the simpler XOR problem). It might also give readers a more accurate picture if “signed SGD” is used in the title and abstract instead of “SGD”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and constructive feedback. We address your questions as follows.\n\n***\n\n**Q1**. While the goal of this work is to understand the training dynamics of modern neural networks, given the use of a polynomial activation and signed gradients, it is not clear to what extent the intuitions from this work extend to more mainstream algorithms, such as ReLU networks trained with SGD.\n\n**A1**. Our study focuses on efficiently solving the k-parity problem using gradient descent, employing polynomial activation and sign SGD for theoretical analysis. Although our setting is specific, core insights like separating features and noise may extend to broader settings. Moreover, recent research has shown connections between sign-based methods and adaptive optimizers like Adam [1-3], indicating relevance to practical algorithms. Importantly, our results match the statistical query lower bound, thus providing valuable theoretical benchmarks and analytical techniques for learning k-parity problems. Our findings have the potential for extension to ReLU activations through polynomial function approximation. The main challenges in extending this to ReLU activation lie in identifying an appropriate functional decomposition and accurately characterizing the approximation error during training. While we primarily use sign SGD due to our polynomial activation function, standard SGD may also be applicable.\n\n[1] Balles et al. \"Dissecting adam: The sign, magnitude and variance of stochastic gradients.\" ICML 2018.\n\n[2] Bernstein et al. \"signSGD: Compressed optimization for non-convex problems.\" ICML 2018.\n\n[3] Zou et al. \"Understanding the generalization of adam in learning neural networks with proper regularization.\" ICLR 2023.\n\n***\n\n**Q2**. Further, it is possible to more explicitly discuss some limitations of the work. For example, it appears that the algorithm is not rotationally invariant, $\\ldots$ It might also give readers a more accurate picture if “signed SGD” is used in the title and abstract instead of “SGD”.\n\n**A2**. Our algorithm is not rotationally invariant, which is a limitation compared to gradient descent. We have acknowledged it in the comparison tables 1 & 2. In the revision, we will expand our limitations section to explicitly discuss this as well, and use 'signed SGD' in the title and abstract. While these limitations exist, our approach provides valuable insights into efficiently solving the k-parity problem, demonstrating the power of SGD. Furthermore, adaptive optimizers with sign SGD have been recently developed to train large models [1, 2]. We believe our work could potentially extend to momentum-based sign SGD algorithms. This could be an interesting direction for future research, potentially leading to even more efficient algorithms for the k-parity problem. \n\n[1] Chen, Xiangning, et al. \"Symbolic discovery of optimization algorithms.\" Advances in neural information processing systems 36 (2023).\n\n[2] Liu, Hong, et al. \"Sophia: A scalable stochastic second-order optimizer for language model pre-training.\" arXiv preprint arXiv:2305.14342 (2023).\n\n***\n\n**Q3**. Is there a way to trade off compute (iterations/neurons) against samples in upper bounds while maintaining the optimal number of queries?\n\n**A3**. Yes, there is a way to trade off computation resources against sample size while maintaining the optimal query complexity. Edelman et al. [1] demonstrated that sparse initialization and increased network width lead to improvements in sample efficiency for solving the k-parity problem. We believe this technique could be adapted to our method to achieve better sample complexity at the cost of using more neurons.\nSpecifically, using sparse initialization and a larger number of neurons would likely reduce the stochastic approximation error of the gradient under the same batch size. Lemma 5.3 of our paper shows that this estimation error is significantly influenced by the weights' norm, which decreases with sparse initialization. This suggests we can use a smaller batch size during training while maintaining performance.\nThis trade-off would preserve the optimal query complexity while reducing the sample size, at the expense of an increased number of neurons. However, further analysis would be needed to determine the exact relationship between network size, sample complexity, and overall query complexity in our approach. This could be an interesting direction for future work.\n\n[1] Edelman et al. \"Pareto frontiers in deep feature learning: Data, compute, width, and luck.\" NeurIPS 2023.\n\n***\n\n**Q4**. The authors mention non-i.i.d. data as room for future research. There are perhaps even more accessible settings to be investigated. For example, can these results be extended to non-isotropic data, similar to the setting of [1]?\n\n**A4**. Thank you for highlighting this important direction and pointing out the related work. We will add a discussion on extending our results to non-isotropic data settings [1] in the revision. To address the k-sparse parity problem under linear transformations (which would result in non-isotropic data), we believe that sign gradient descent with momentum could be a promising approach. Momentum-based methods have shown effectiveness in handling ill-conditioned optimization landscapes, which often arise from non-isotropic data distributions. Specifically, momentum could help in two ways:\n- It could accelerate learning along the directions of consistent gradient, which may correspond to the important features in the transformed space.\n- It could help overcome local irregularities in the loss landscape introduced by the linear transformation.\nHowever, a rigorous analysis would be needed to determine how the sample complexity and convergence guarantees would change as the linear transformation matrix varies. \n\n[1] Nitanda et al. \"Improved statistical and computational complexity of the mean-field Langevin dynamics under structured data.\" ICLR 2024.", "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": "VrnwXQtb36", "reviewer": "Reviewer_f3yt", "summary": "The paper addresses the k-sparse parity problem, a fundamental one in computational complexity and algorithmic theory, by using stochastic gradient descent (SGD) on two-layer fully-connected neural networks. The authors demonstrate that SGD can efficiently solve the problem on a d-dimensional hypercube with a sample complexity that matches the established  lower bounds of Statistical Query (SQ) models.", "questions": "A variant of the parity problem that is not on the hypercube would be if one uses y = sign(z1 z2 z3) with z_mu = x*w_mu, with w_mu a hidden direction on the hypercube. I was wondering how different would the SG bounds and the results of the algorithm be in this case.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a solid theoretical foundation by matching the SQ lower bound for learning k-sparse parity problems, which is a significant achievement in this area. Given the recent interest in SQ and CSA bounds and the amount of works on single and multi-index models folllowing the work of Abbe et al, I find these results pertinent.", "weaknesses": "The results, both in their scope and sytle, are more aligned with theoretical computer science (CS) than machine learning (ML). While the mathematical contributions are significant, the immediate applicability to practical ML problems is very limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and valuable feedback. We address your questions as follows. \n***\n**Q1**. The results, both in their scope and style, are more aligned with theoretical computer science (CS) than machine learning (ML). While the mathematical contributions are significant, the immediate applicability to practical ML problems is very limited. \n\n**A1**. While our results are more aligned with theoretical computer science in style, they still make contributions to the machine learning community. Our work provides insights into the power and limitations of gradient-based learning methods. Furthermore, sign SGD based adaptive optimizers have been recently developed to train large models [1, 2, 3]. \n\nThe theoretical analysis of sign SGD's behavior on the k-parity problem sheds light on how neural networks learn complex patterns, which can motivate the development of more efficient training algorithms. While not immediately applicable to all ML problems, our results provide a rigorous foundation for future work that could bridge theory and practice more directly. In addition, since most of the relevant work discussed in our paper has been published in leading machine learning venues (e.g., NeurIPS, ICLR, ICML), we believe that NeurIPS is an ideal venue for our work.\n\n\n[1] Bernstein, et al. \"signSGD: Compressed optimization for non-convex problems.\" ICML2018.\n\n\n[2] Chen,  et al. \"Symbolic discovery of optimization algorithms.\" NeurIPS 2023.\n\n[3] Liu, et al. \"Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training.\" ICLR 2024. \n\n\n***\n\n\n\n**Q2**. A variant of the parity problem that is not on the hypercube would be if one uses y = sign(z1 z2 z3) with $z\\_{\\mu} = \\mathbf{x}*\\mathbf{w}\\_{\\mu}$, with $\\mathbf{w}\\_{\\mu}$ a hidden direction on the hypercube. I was wondering how different would the SG bounds and the results of the algorithm be in this case.\n\n**A2**. Thank you for your insightful question. The variant you propose introduces interesting modifications to the standard k-parity problem. Let's analyze this in stages:\n- When $\\mathbf{w}\\_{\\mu} \\in \\\\{e_1, ..., e_d\\\\}$ (standard basis vectors), the problem reduces to the standard 3-parity problem. In this case, the SQ bounds and the results of our algorithm would be O(d^3), consistent with our findings for k=3.\n- For general $\\mathbf{w}\\_{\\mu} \\in \\\\{0,1\n\\\\}^d$, the problem becomes more complex as the hypothesis space expands. This would likely worsen both the SQ bounds and the algorithm's performance compared to the standard case. However, with additional information about the formula, it's possible to decompose the problem into monomials to obtain tighter bounds. For example, $(\\mathbf{x}\\cdot \\mathbf{w}_1)(\\mathbf{x}\\cdot \\mathbf{w}_2)(\\mathbf{x}\\cdot \\mathbf{w}_3) = (x_j+x_k)x_lx_m = x_j x_l x_m + x_k x_l x_m$. This monomial decomposition enables us to apply the CSQ lower bound with leap complexity from [1].\n- For analysis of our algorithm, we can start by examining the population gradient descent. With some additional information about the formula of w_mu, we can decompose the population gradient into different parts using the same technique in point 2 and then analyze the weight update as in Equations 5.3 and 5.4 of our paper. We can then apply the approximation error between the population gradient and the stochastic gradient (Lemma 5.3) to derive the final results. Such an approach allows us to extend our current techniques to more complex settings.\n\nIn conclusion, while the exact bounds and algorithm performance for this variant require detailed analysis, we expect both the SQ bounds and the required sample complexity to be highly dependent on the specific form of $\\mathbf{w}\\_{\\mu}$. This variant presents an interesting direction for future research, potentially bridging our results with more general machine-learning problems.\n\n\n[1] Abbe, et al. \"SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics.\" COLT 2023.", "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": "J9YTApOlLD", "reviewer": "Reviewer_Bgvr", "summary": "This paper considers the problem of learning a $k$-parity function on the $d$-dimensional hypercube using SGD on a two-layer neural network. They consider a specific choice of activation ($\\sigma (x) = x^k$) and training dynamics (correlation loss, online sign SGD, fixed second layer weights) and show the following: for $m = 2^{\\Theta (k)}$ neurons, batch size $B = \\Theta (d^{k-1} \\text{polylog} (d))$, then $T = \\Theta (log (d))$ steps of online sign SGD achieves small $0/1$-test error. In particular, the total computation time scales as $\\Theta (mTB) = \\Theta (d^{k} \\text{polylog} (d))$. This is noteworthy as it matches the lower bound for learning parities from a large class of learning algorithms, namely statistical queries.", "questions": "About the conclusion on going beyond SQ: the paper “On the power of differentiable learning versus PAC and SQ learning” shows that it is indeed possible with enough machine precision: we can emulate Gaussian elimination. Of course, this is not a very interesting result, as it uses a highly non-standard network that encodes an algorithm in its architecture. There are other noise-tolerant algorithms that do slightly better than SQ, it would be interesting to show that regular architectures prevent their emulation (besides low machine precision).", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is well written, clear, and a very pleasant read (thank you!). Remarks and discussions provide background and comparison with other works, and help outline the contributions.\n\n- The theoretical analysis and statements are clean, and the proof quite compact and elegant, thanks to some simplifying assumptions in the model..\n\n- The fact that SGD on a (quite regular) neural network can match the runtime complexity of the SQ class of algorithms is a nice message. There is a growing literature trying to understand the power of learning with SGD on neural networks, compared to other classes of algorithms, and I believe this paper is a useful addition to the literature.", "weaknesses": "I am not sure the paper offers striking novel insights compared to existing literature, or that the analysis is particularly interesting in terms of proof techniques. This is the reason for my rating, but I remain open to changing it during the discussion period.\n\n- I think it was already quite widely believed that SGD on NNs can match the SQ lower bound (this is indicated in many papers on learning sparse functions on the hypercube/multi-index functions on Gaussian data). The case of $k$-parities was not written/proven before, and I think this paper makes the necessary effort to settle it. However, I believe some existing analysis can be extended to this case (e.g., [Abbe2023a], [Margalit et al., 2023]), even though they will have drawbacks specific to their choice of simplifications.\n\n- The analysis and proofs are quite nice, but it feels like a game of “there exists a specific choice of hyperparameters so that an analysis goes through”. Given that the paper doesn’t put forth particularly novel insights/phenomena, the analysis of a more vanilla training setting (non-monomial activation, more general loss, and standard GD) would have felt more substantial.\n\n- There are several questions about this setting that remain completely not understood (e.g., what happens when reusing batches) which further contributes to the impression that this work is incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and helpful comments. Below, we address the questions.\n\n***\n\n**Q1**. I think it was already quite widely believed that SGD on NNs can match the SQ lower bound (this is indicated in many papers on learning sparse functions on the hypercube/multi-index functions on Gaussian data). The case of k-parities was not written/proven before, and I think this paper makes the necessary effort to settle it. However, I believe some existing analysis can be extended to this case (e.g., [Abbe2023a], [Margalit et al., 2023]), even though they will have drawbacks specific to their choice of simplifications.\n\n**A1**. Extending existing analyses to the Boolean k-parity case is not straightforward. [Abbe2023a]'s results [1] rely on Gaussian input and Hermite polynomial techniques, which don't directly translate to discrete Boolean input space. In addition, [Margalit et al., 2023]'s proof [2] depends on specific feature growth patterns of w_{sig} in xor problem, which requires non-trivial extensions for k-parity. In contrast, our paper addresses the Boolean input k-parity problem directly, introducing a feature-learning technique that illustrates the divergence between feature and noise coordinates of different neurons. By settling this case, we provide a rigorous framework for understanding SGD's behavior in this important discrete setting, bridging a gap in the literature. \n\n[1] Abbe et al. \"Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[2] Glasgow, Margalit. \"SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem.\" The Twelfth International Conference on Learning Representations.\n\n***\n\n**Q2**. The analysis and proofs are quite nice, but it feels like a game of “there exists a specific choice of hyperparameters so that an analysis goes through.” Given that the paper doesn’t put forth particularly novel insights/phenomena, the analysis of a more vanilla training setting (non-monomial activation, more general loss, and standard GD) would have felt more substantial.\n\n**A2**. While our chosen hyperparameters may seem specific, they allow us to provide rigorous proof that matches the SQ lower bound, which is the main contribution of our paper. The insights gained from this analysis—particularly the separation of feature and noise coordinates—are novel and potentially applicable to more general settings. Our approach can be extended to other scenarios: non-monomial activations could be approximated by polynomial functions; for different loss functions, we could divide the learning process into phases, with the first phase mimicking our current analysis where neural network outputs are small and different neurons update independently; and our analysis could potentially be extended to sign SGD with momentum, which has shown connections to adaptive optimizers like Adam in recent research [1~4]. These extensions demonstrate the flexibility and potential broader applicability of our analytical approach.\n\n[1] Balles et al. \"Dissecting adam: The sign, magnitude and variance of stochastic gradients.\" ICML 2018. \n\n[2] Bernstein et al. \"signSGD: Compressed optimization for non-convex problems.\" ICML 2018.\n\n[3] Zou et al. \"Understanding the generalization of adam in learning neural networks with proper regularization.\" ICLR 2023.\n\n[4] Xie et al. \"Implicit bias of adamw: ℓ∞ norm constrained optimization.\" arXiv 2024. \n\n*** \n\n**Q3**. There are several questions about this setting that remain completely not understood (e.g., what happens when reusing batches) which further contributes to the impression that this work is incremental.\n\n**A3**. While some aspects, like batch reuse, remain unexplored, we believe this doesn't diminish the significance of our contribution. Our results use the online learning setting, widely adopted in k-parity problem studies [1-3], aligning our work with existing literature and enabling direct comparisons.\nWe use fresh samples in each iteration to provide a clear gradient estimation error analysis, demonstrating the separation between feature and noise coordinates. Exploring batch reuse effects could be a valuable future direction, potentially employing more advanced concentration techniques or implicit bias analysis. This might lead to more efficient algorithms or tighter bounds. We view these open questions as opportunities for future research, building upon the foundation our work provides.\n\n[1] Barak et al. \"Hidden progress in deep learning: Sgd learns parities near the computational limit.\" NeurIPS 2022. \n\n[2] Edelman et al. \"Pareto frontiers in neural feature learning: Data, compute, width, and luck.\" NeurIPS 2023.\n\n[3] Glasgow, Margalit. \"SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem.\" ICLR 2024. \n\n***\n\n**Q4**. About the conclusion on going beyond SQ: the paper “On the power of differentiable learning versus PAC and SQ learning” shows that it is indeed possible with enough machine precision: we can emulate Gaussian elimination $\\dots$ it would be interesting to show that regular architectures prevent their emulation (besides low machine precision).\n\n**A4**. Thank you for your insightful comment and for sharing the paper on emulating Gaussian elimination with non-standard networks. Your suggestion to investigate whether standard architectures prevent the emulation of noise-tolerant algorithms that outperform SQ is a valuable research direction.  It can reveal fundamental limitations of common neural network designs and deepen our understanding of the relationships between architecture, learning algorithms, and computational complexity. We will include this discussion in our future work section.", "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": "MdSnnQPHPE", "reviewer": "Reviewer_6YuP", "summary": "This paper studies the problem of learning the $k$-sparse parity problem over the $d$-dimensional boolean hypercube, using a two-layer neural network. The main result is that a specific modification of online SGD, called \"sign SGD,\" can learn the k-parity problem $n = \\tilde O(d^{k-1})$ samples and a network width of $2^{\\Theta(k)}$; the number of scalar queries to the model is $m\\cdot n \\cdot d = \\tilde O(d^k)$, and thus this algorithm matches the SQ lower bound of $d^k$.", "questions": "- Can you include more intuition in the main text for Lemma 5.3, specifically why a batch size of $\\tilde O(d^{k-1})$ is sufficient for gradient concentration?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The k-sparse parity problem has attracted much recent interest in the deep learning theory community, with many prior works focusing on both lower bounds (via the SQ/CSQ framework) and learning guarantees for neural networks. This paper makes good progress by showing that the SQ lower bound of $d^k$ queries can indeed be achieved by a gradient-based algorithm.\n- The paper is well written and easy to understand, and I was able to follow the proof sketch.\n- I have skimmed the appendices, and the proofs appear to all be correct.", "weaknesses": "- My main issue with this paper is the choice of the Sign SGD algorithm. Unlike vanilla SGD, Sign SGD is not invariant to the choice of the basis, and is implicitly taking advantage of the structure of the problem being k-parity (where in the ground truth solution each neuron weight is either -1, 0, or 1). For example, the Sign SGD algorithm here would fail if the task was instead k-parity in an unknown basis. Many of the prior works discussed in Tables 1 and 2, however, are rotationally invariant. \n- In particular, the paper (Glasgow, 2023) had the more ambitious goal to show that vanilla SGD, with minimal modifications, can learn the 2-parity problem. The algorithm in that paper is rotationally invariant and will succeed if the target was XOR in an unknown basis. I thus find the comparisons to (Glasgow, 2023) in the paper, such as \"our result matches the best sample complexity for solving the XOR (i.e., 2-parity) problem (Glasgow, 2023)\" (line 84) to be a bit misleading.\n- On a more minor note, I also find the choice of activation $\\sigma(z) = z^k$ to be unrealistic, as this again is essentially hardcoding the fact that the target problem is $k$-parity. As seen in Tables 1 and 2, most of the prior work uses the ReLU activation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and constructive feedback. We address your questions and provide clarifications below.\n\n***\n\n**Q1**. My main issue with this paper is the choice of the Sign SGD algorithm. Unlike vanilla SGD, Sign SGD is not invariant to the choice of the basis, and is implicitly taking advantage of the structure of the problem being k-parity (where in the ground truth solution each neuron weight is either -1, 0, or 1). For example, the Sign SGD algorithm here would fail if the task was instead k-parity in an unknown basis. Many of the prior works discussed in Tables 1 and 2, however, are rotationally invariant.\n\n**A1**. Our choice was motivated by several factors outlined in Remark 3.2: it normalizes the gradient, ensures uniform neuron updates towards identifying parity, and effectively nullifies noisy coordinate gradients. While effective for the standard k-parity problem with a standard basis, we acknowledge its limitations for unknown bases. To address this, we could consider alternatives like normalized gradient descent with an adaptive learning rate, or incorporating momentum into Sign SGD. These approaches could potentially achieve rotational invariance while retaining the benefits of Sign SGD. It's worth noting that our use of Sign SGD is primarily due to the polynomial activation function; normal SGD could potentially be applied if we can extend our analysis from polynomial activation to other activation functions. For instance, we could potentially extend our approach to sigmoid or ReLU activation through polynomial function approximation. However, the main challenge lies in identifying an appropriate functional decomposition and accurately characterizing the approximation error during training. We will discuss this rotation invariant issue in our limitations section, along with potential future research directions to address it.\n\n***\n\n**Q2**. In particular, the paper (Glasgow, 2023) had the more ambitious goal to show that vanilla SGD, with minimal modifications, can learn the 2-parity problem. The algorithm in that paper is rotationally invariant and will succeed if the target was XOR in an unknown basis. I thus find the comparisons to (Glasgow, 2023) in the paper, such as \"our result matches the best sample complexity for solving the XOR (i.e., 2-parity) problem (Glasgow, 2023)\" (line 84) to be a bit misleading.\n\n\n**A2**. We appreciate your observation regarding the differences between our work and Glasgow (2023) [1]. Their paper studied vanilla SGD learning the 2-parity problem, which is rotationally invariant. Our work focuses on solving the general k-parity problem with sign SGD, which doesn't include XOR in an unknown basis. We have highlighted the differences in optimizers in Tables 1 and 2. Given these differences, we will revise our statement on line 84 to more accurately reflect that we match the best sample complexity only for the standard basis case. Additionally, we will use 'Sign SGD' in the title and abstract to better reflect the specific nature of our method.\n\n\n[1] Glasgow, Margalit. \"SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem.\" ICLR 2024. \n\n***\n\n**Q3**. On a more minor note, I also find the choice of activation to be unrealistic, as this again is essentially hardcoding the fact that the target problem is k-parity. \n\n**A3**. We chose $\\sigma(z) = z^k$ activation function primarily to facilitate our theoretical analysis and derive clean results for solving the k-parity problem. Since our work is the first to achieve the SQ lower bound for learning k-parity, we believe that even using a monomial activation function is significant enough. For future work, we plan to explore non-monomial activations that can be approximated by polynomial functions. This approach could lead to a more general activation function for solving a broader class of problems while maintaining theoretical traceability. \n\n***\n\n**Q4**. Can you include more intuition in the main text for Lemma 5.3, specifically why a batch size of O(d^{k-1}) is sufficient for gradient concentration?\n\n**A4**. The batch size of O(d^{k-1}) is crucial for gradient concentration due to the specific structure and learning dynamics of the k-parity problem. Here's an intuitive explanation:\n\n- Lemma D.1 shows that for each coordinate of the $r$-th neuron, the gap between population gradient and stochastic gradient is bounded by $\\epsilon_1 \\cdot \\\\|\\mathbf{w}\\_r\\\\|\\_{2}^{k-1}$, where $\\epsilon_1 = \\tilde O(B^{-1/2} + d^{(k-3)/2}B^{-1})$. This implies that increasing the batch size B reduces the approximation error.\n- Lemma 5.3 and Corollary 5.4 demonstrate that we need $\\epsilon_1 = \\tilde O(d^{-(k-1)/2})$ to ensure the stochastic sign gradient matches the population sign gradient. Solving $B^{-1/2} + d^{(k-3)/2}B^{-1} = d^{-(k-1)/2}$ yields a sufficient batch size of O(d^{k-1}) for gradient concentration.\n- The condition $\\epsilon_1 = \\tilde O(d^{-(k-1)/2})$ is crucial because the absolute value of the population gradient on the signal coordinate is approximately $\\tilde O(d^{-(k-1)/2}) \\cdot \\\\|\\mathbf{w}\\_r\\\\|\\_{2}^{k-1}$ at initialization. To guarantee that the gradient sign doesn't flip, the approximation error must be smaller than this absolute value.\n\nWe recognize the value of including this intuition in the main text. Given the one extra page for camera ready, we will add a discussion explaining these points after Lemma 5.3, helping readers better understand the connection between the problem structure, our method, and the resulting sample complexity. For a more detailed technical analysis of the gradient concentration and the derivation of the O(d^{k-1}) batch size, we refer readers to Appendix D, specifically the proof of Lemma D.1, which provides a rigorous proof of the concentration bounds and explains how we arrive at this batch size condition.", "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: This paper constructs a depth-2 neural network with polynomial activations such that a variant of SGD solves the sparse parity problem nearly as well as any Statistical Query algorithm. This work is part of an extensive line of work over the past years. While results of qualitatively the same flavor have been shown for several related problems, the reviews agreed after the discussion that this work meets the acceptance threshold.
Decision: Accept (poster)