Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Inspired by the discontinuous phase transition of running time, this paper studies the computation issue of k-sparse parities of n bits via deep learning method. It shows two main results: 1. With standard initialization and training, SGD can solve the k-sparse n-dimensional parities problem at optimal computation time n^(Ω(k)) steps in statistical query (SQ) model, which is much faster than the convergence time of random search 2^(Ω(n)) as previous conjecture. Additionally, it comes up with a “progress measure”, which can indicate when the sudden increasing of loss and accuracy happens. 2. It empirically and theoretically shows that SGD can do feature learning for parity problem even without sparse prior. 
strengths_and_weaknesses: Strength:
1. Under specific setting, the author empirically demonstrates an interesting phenomenon under that SGD can solve k-sparse b-dimensional parities problem at optimal computation time in SQ algorithms, which contrasts to random search process as previously thought. Apart from empirical results, this paper provides theoretical analysis of why SGD is successful in solving the parity problem.
2. This paper has good structure. It starts from the phase transition phenomenon, and then it shows a theoretically analysis with a simple warm-up example as the introduction, which gives me an intuition.  
3. The proposed progress measure seems to be a useful indicator and correlated with the performance (loss and accuracy).

Weakness
1. There is lack of explanation forsome theorems, which may make reader confused. For example, the author says that there exist a (n, k) parity distribution and satisfies some inequality constraint with an embedding in theorem 6, but I don’t know how do we get this D-dimensional embedding, is it the output of the network? And how can we use this theorem in practice?
2. There is lack of explanation for some notations. For example, what “e” denotes in line 281 and what “v(t)” is in theorem 7 (line 291).
3. The purpose of investigating the parity problem needs to further explain.  If the purpose is to understand deep networks,  why we should start from this parity problem? 
questions: 1. I don’t know whether the input from uniform {+1,-1}^n is practical setting in k-sparse n-dimensional parities problem. If not, I think it is a too strong assumption to understand the process of training deep learning.
2. In theoretical part, the author extends the theoretical part from large batch size n^(Ο(k)) to number of steps n^(Ο(k)) , I don’t understand why we can do such extension and I think it would be helpful if there is an intuitive explanation.
3. From my understanding, does the convergence time of this parity problem only work for the special network structure “PolyNet”? If so, I think it is far from practice and its impact may be limited.
4. It was mentioned in Section 2 that  the results are based on online setting. But it is not clearly mentioned in Theorem 4. Does each iteration in Theorem 4 requires new i.i.d. samples? If so, this seems a very strong assumption to hold in practice.
5. Theorem 4 only requires ploy(k,r) iterations, which is much smaller than the number of iterations n^{O(k)} observed in experiments . While Theorem 4 and experiments have different batch sizes, this discrepancy needs more explanation in order to make Theorem 4 as a supporting result for the experiments.
6. I am curious about whether there is more naïve explanation to explain why progress measure can indicate the phase transition once the measure passes the certain threshold.
limitations: This paper does not have the limitations and potential negative societal impact.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: UPDATED SCORE AFTER REBUTTAL.

The authors study parity functions of size k on n bits. Since there are $2^n$ subsets of the literals, sampling from them uniformly at random would take time exponential in n to find a specific parity function. In addition to this naive approach, there are standard lower bounds for learning parity functions in the SQ model (as opposed to the more general PAC model). The authors claim, using experiments, that training neural networks with SGD (without any sparsity penalty) matches this lower bound. Finally the authors suggest a "hidden progress measure" that changes smoothly despite loss and accuracy plateauing.
strengths_and_weaknesses: Strengths
- The problem proposed by the authors is interesting and potentially a useful model for "grokking." 
- The paper considers a variety of different architectures ranging from more realistic to more idealized.

Weaknesses
- Many of the claims lack clarity or seem overstated.
- "Empirical Finding 1": I'm confused by the quantifiers in this statement. Restricting to small n and k is odd as the lower bound from the SQ model is asymptotic in n. Even the empirical evidence is not convincing. In Figure 2 the lines are clearly not straight, undercutting the claim.
- The motivation for the progress measure is weak and no explanation for the infinity-norm is given. This progress measure also does not seem to distinguish between the "stumbling in the dark" model as surely the progress measure would also increase in this case.
- Theorem 6 states there exists some distribution over $(x,y)$ that cannot be learned. This seems quite different than the experiments performed for neural networks, which I believe used the uniform distribution rather than asking whether they can learn any distribution over the literals.

questions: - What is D for the NTK in Theorem 6? Is this the size of the training set?
- What does it mean for f to be continuous in line 150 on a discrete space?
- Figure 2 right: Why are these curves not straight if there is power-law scaling?
- Does the argument in lines 201-203 assume initialization samples uniformly from all subsets? Can you provide more detail.
- Please provide a citation for the Fourier spectrum of Majority.
- How can you distinguish between computational and sample resources in online learning where they are linked?

limitations: No concerns about negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of learning k-sparse parties using SGD on neural network models. In particular, standard deep learning approaches (running gradient-based methods from random initialization) exhibit discontinuous improvement in performance with increasing training time. Importantly, this kind of phase transition is quite robust and SGD can robustly find the sparse subset in a number of iterations that nearly matches optimal lower bounds without sparsity prior. This is strongly against the "random search" hypothesis. Theoretically, the authors show that the first gradient step contains important information to solve the parity problem and feature learning is crucial (as no kernel can solve the sparse parity problem). Finally, the authors argue there is a hidden progress measure which under SGD is steadily improving.
strengths_and_weaknesses: Strengths:
- The idea of applying deep learning methods to solve the sparse parity problem is novel and inspiring.
- The authors conducted comprehensive empirical studies and many results are quite interesting. For example, the results are robust w.r.t the architectures, data subsampling, and initialization schemes, but sensitive to particular initialization.
- The finding that SGD could solve the problem in a number of iterations that matches the lower bounds is surprising and interesting. I believe this would inspire many other follow-up works.
- The authors further proved that feature learning is important and the first gradient step can learn features that contain enough information for solving the problem, even though under a restricted setting.

Weaknesses:
- The authors made the argument that random search is the most natural hypothesis to explain the success of SGD in learning parities. I don't really buy this argument. To me, gradient-based methods have little to do with random search. It is known in the community that SGD uses only local information and is very different from random search. In my opinion, it is not surprising that SGD can do better than random search, instead it is surprising that it can match the optimal lower bound.
- The hidden progress measure looks quite arbitrary to me. The authors argue gradual weight movement is a potential measure. However, it is unclear how the weight movement connects with "real" progress. There are many problems that one can observe weight movement but no improvement in performance.
questions: See some of my comments on the weaknesses.

Other questions:
- I wonder if the authors tried different batch sizes in solving the problem. An empirical batch size scaling curve may provide some insights into the learning dynamics. Also, experiments with SGLD could also be interesting.

limitations: The authors discussed some of the limitations and broad impact at the end of the paper. I don't see any negative societal impact of this work.
review_title: null

Meta-review: metareview: This paper studies learning $k$-sparse parities of $n$ bits by a neural network. The authors show empirically that SGD efficiently learns sparse parties and also provide theoretical analysis for 2-layer MLPs. In particular, the authors show that training neural networks with SGD but without any sparsity penalty can solve the problem with $n^{O(k)}$ samples and steps, matching the standard statistical query (SQ) lower bounds for learning $k$-sparse parties of $n$ bits. 

The major comments pointed out by reviewers include (1) the motivation for studying the parity problem and the progress measure, (2) the mismatch between the experimental results and claim, and (3) the gap between the theoretical results and the empirical observations. To address these comments, the authors have submitted a revised version which includes a further introduction to the parity learning problem and clarifies the reasoning for choosing the progress measure. The authors also clarify the empirical claims concerning the experimental results. Though the gap between the theoretical results and the empirical observations can not be improved in the current version and needs further investigation in future work, this paper advances our theoretical understanding of the computational aspect of scaling in deep learning through the parity learning problem. So I recommend accepting, but the authors are advised to incorporate the discussions about empirical claims in the final version. 
confidence: Less certain
Decision: Accept