Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the learnability of Lipschitz models with GD/SGD optimization. It assumes that the learning algorithm satisfies G-equivariant for some non-trivial symmetry group G (which holds for GD/SGD learning in neural networks), and shows two types of results:
- With GD learning, the paper characterizes the learnability of Lipschitz models on 1) functions of both the hypercube and the unit sphere; 2) functions with latent low-dimensional structure. 
- For the function given in Eq. (4), with SGD learning, a fully-connected network cannot learn and evaluate the function (4) in polynomial time with respect to the input dimension d.

strengths_and_weaknesses: Strength:

The first result characterizes the learnability of a rather general class of learning models. The second result provides a nice example that neural networks, despite their universal approximation ability, cannot efficiently learn.

Weakness:

My major concern is that it requires the architecture to have bounded Lipschitz constant over parameters. However, almost all neural networks have unbounded Lipschitz constants. The authors argue (in the supplementary materials) that, in practice, we can clip the gradients to yield bounded derivatives. However, for a purely theoretical paper, this is not a sound justification. Clipping the gradient is equivalent to changing the learning algorithm, but the objective function remains unchanged, still having an unbounded Lipschitz constant. 

In that sense, Section 3 only holds for models with Liptchiz constant, for example, one-hidden-layer networks with fixed output layers and bounded-gradient activations. This deviates from the major claims --- "regular architectures and initialization" of neural networks. Meanwhile, the authors criticize that the prior work [AS20] does not "reflect architectures used in practice", which is unfair. 

To rigorously prove for neural network training, the authors can either show i) GD operates in a bounded region, within which we have bounded Lipschitz, or ii) the theorem holds for gradient-clipping GD. Please consider addressing this problem. Otherwise, it is not eligible to claim the results hold for general DNN. Note that prior works (such as [Ele22]) that require C-Lipschitz on the learning model did not claim to hold for NN in their theorems.

Another concern is that the second result does not seem to counter [AS20] directly. [AS20] shows there exists DNN that can emulate any efficient learning algorithm (that is able to learn in poly-time). It assumes that at least one poly-time efficient algorithm exists. However, the non-universality shown in Theorem 4.4 relies on the hardness of γ-LPGN hardness, which is not poly-time solvable by any algorithm. There is a gap between the "universality" discussed in [AS20] and this paper. It is still possible that a practical DNN with G-equivariance SGD learning can emulate any efficient algorithm.
questions: Please refer to the [weakness] part.
limitations: Please refer to the [weakness] part.
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 lower bounds of Gradient Descent (with noise) (GD) and Stochastic Gradient Descent (SGD) training algorithms that are also $G$-equivariant. The paper introduces the concept of $G$-orbit alignment which is used towards proving the first main result which is a computational lower bound on $G$-equivariant GD which appears novel. Two applications of this lower bound are provided in terms of weak learnability of functions on the hypercube, hypersphere, and a necessity result on the merged staircase property. As a separate, but interesting in it's own right contribution, the authors provide a first-of-its-kind hardness result for SGD using fully-connected networks on the Learning Parities with Gaussian Noise problem.
strengths_and_weaknesses: **Disclaimer** 
I did not check the veracity of the proofs beyond Appendix A.

This paper enjoys several strengths. In my opinion, the paper studies an extremely interesting problem and makes progress by providing several novel insights. I especially appreciated the idea of $G$-orbit alignment and its use in characterizing weak learnability. This is both intuitively clear and a great application. I also equally found the main results of the lower bounds on $G$-equivariant GD insightful and a significant step over previous work. The computational hardness results for SGD seemed interesting but this aspect was a bit beyond my area of expertise. The authors could do a bit more towards making this section more approachable given that the paper does not completely exhaust the 9-page limit. My main criticism of this work is that a lot of the interesting detail in the Appendix could have been brought forward to the main text. For example, the impossibility results for both applications that actually utilize Theorem 3.1 could be better served in the main paper. Overall, I found this paper to be a thoroughly enjoyable read as overall the clarity and high quality of writing made difficult ideas mostly approachable but at the same time did not water down their perceived impact.

**Minor**
- line 147 compact groups, not any groups

- minor notational issues. In definition 2.4 $\psi, \tilde{\theta}$ are not defined

- Definition 3.2 seems a bit contrived. Can you provide a bit more intuition for the constant 9/10?
questions: One of the central assumptions in much of the technical results is that $\mu_x$ is $G$-invariant. Often times real-world datasets, due to noise or other randomness in the data collection process exhibit soft equivariance rather than hard ones. Can you provide commentary on how this specifically affects the weak learnability results ---i.e. does depth now matter beyond 2-layer networks?
limitations: N/A
review_title: null

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: This paper mainly focused on the universal property of deep learning. Specifically, the authors showed that when the training algorithm satisfies a certain symmetry/equivairance, deep learning is no longer universal. Then, they characterize two types of functions with gradient descent (GD): 1) the functions that fully-connected networks could weakly learn on the binary hypercube as well as the unit sphere, and 2) the functions that neural networks with latent low-d structure. Lastly the authors extend the results to the stochastic GD.
strengths_and_weaknesses: Strength:

1. The paper has good novelty and defines a lot of new concepts, e.g., G-orbit-alignment, etc. It pushes the boundary of the research.

2. Use some decent mathematic tools.

Weakness:

1. The paper is very abstract, and some definition is not easy to think about. Could the authors give some examples to help readers better understand the newly defined concepts?

2. The authors always assume that the GD training algorithm is G-equivariant, but in practice, I was wondering if this condition could hold.

3. The paper lacks some empirical study to support the authors' findings.
questions: 1. In Line 237, the authors mentioned that if the $G-$orbit-alignment is very small, then the GD training cannot efficiently improve on the trivial loss, could the authors elaborate on this part a bit more, since the right-hand side in the equation between 235 and 236 also depends on other factors?

2. As I mentioned in the weakness part, some definitions and assumptions are abstract, could the authors give some examples for readers to follow easily?

3. Could the authors provide some numerical studies to demonstrate the applications mentioned in the paper indeed work in practice.
limitations: N/A.
review_title: null

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: This paper tries to analyze which functions can and cannot be learned by a standard MLP with gradient descent. This is analyzed by looking at the symmetry of the initialization and GD so the intuition is that functions that do not follow this symmetry are hard to learn. 
strengths_and_weaknesses: I would first want to state that I am not a theoretician so I do not think I am the right person to review this paper, but I did the best I could to evaluate it.

Strength:
- The paper is clearly written
- The proofs seem correct to me 
- The question of what functions can be learned is an important one so the work is important and novel.

Weaknesses:
- I mainly question the significance of some of the results, especially since the definition of weak learnability is very weak (as the "non-negligible" edge can be quite negligible with a large value of C). For example in Trm. 3.6 the condition $\sum_{\ell=0}^C||P_{V_{d,
\ell}}f_d||^2\geq d^{-C}$, the r.h.s increases (or not decreases) with $C$ and the r.h.s decreases rapidly. It makes the condition very weak (as weak learnability is very weak) so I don't think it adds any value to our understanding.
- Missing related work Shai Shalev-Shwartz, Ohad Shamir and Shaked Shammah "Failures of Gradient-Based Deep Learning".
- You do not show results for GD/SGD but for GD/SGD with noise. This is equivalent to what is done in SGLD or differentially private learning which significantly hampers performance. It is not clear to me at all that the results with noise are relevant to the standard noiseless training due to the major impact the noise makes on the optimization process.
questions: Can you give an example (that wasn't shown previously) of something that isn't weak learnable?
limitations: Not discussed
review_title: null

Meta-review: metareview: This paper continues a line of work on the universality of deep learning and provide some natural assumptions under which previous results showing universality are not valid any more. This is an important contribution as indeed previous universality result seem to rely on unnatural constructions and architectures and this work highlight this.

There were some concerns about the practicality of the results, however this paper is mostly theoretical and I would like to judge it in the context of previous work such as Abe & Sandon. As far as I can see, in this context, the authors provide new insights and help to advance our understanding.
confidence: Certain
Decision: Accept