Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors consider the representation learning ability of two layer neural
networks trained with gradient descent to approximate the outputs of a function
in a nonparametric class, applied to a few projections of a high-dimensional
input vector -- in this setting, kernel methods and other rotation-invariant
predictors generally suffer from a curse of dimensionality, but methods such as
neural networks can potentially avoid the curse of dimensionality by learning
the relevant directions and then fitting the target in this lower-dimensional
space. They consider the setting of gaussian inputs, standard (mean-field-type)
random initialization, and training with variants of stochastic gradient
descent on the square loss and smooth activations, and on convex Lipschitz losses
and the ReLU, with large weight decay regularization. Their main technical result
consists of showing that online SGD (samples from the population loss) on the
first layer weights leads to fairly rapid convergence to weights that are
suitably close to the span of the relevant $k$ directions of the teacher model
-- the rates for the norm of the irrelevant components of the trained weights
are on the order $\sqrt{dm/T}$, where $d$ is the ambient dimension, $m$ is the
number of neurons, and $T$ is the number of iterations of SGD, which is
sufficient to bound the risk given that the losses are locally Lipschitz. The
authors apply this result to obtain a guarantee for learning noisy single-index
teacher models (single neuron) up to the noise level with a two-stage procedure
(after SGD on the first-layer weights to learn the right representation for the
input, fit the readout layer weights with essentially ridge regression), and
generalization gap control (no empirical risk control) in more general settings
due to the low-dimensional representation learned. 


strength_and_weaknesses: ## Strengths

- The paper is very well written. The coverage of background material and
  related work seems essentially exhaustive. The notation and technical
  discussions are precise and easy to parse at multiple levels of detail. The
  authors provide interesting intuitions and connections to classical work in
  statistics (e.g.  model misspecification) that enhances the level of insight
  of the presentation.

- The results concern the important problem of representation learning in
  nonlinear neural networks. The authors seem to have taken some care to
  present their results in some generality (different losses and activations,
  step size regimes for SGD, etc.). The conclusions for learning the first
  layer weights are qualitatively interesting.

## Weaknesses

- The algorithmic results for neural network training + generalization are
  relatively weaker than the results for recovery of the first layer weights --
  just concerning single index models or the generalization gap.

- It would be helpful for the sake of comparison if the theorems did not hide
  properties of the link $g$ -- especially to compare with the results of
  Damian et al., which expose specific rates when the target is a polynomial
  with a certain neural-net-like structure.

## Minor / Questions / Etc.

- The role of the noise $\epsilon$ in the link function does not seem clear in
  the theorems in the main body, prior to section 4 -- what dependence does it
  play in the results?  Can it be zero? In section 4, why is this noise
  necessary? (It would be helpful in understanding this if Theorem 4 exposed
  the dependence on the subgaussian rate of the noise $\sigma^2$, say.)

- Some discussion of why the risk needs to be truncated at level $\tau$ in
  section 4 would be helpful.

- With regards to the similarity to previous works, some discussion in the
  rebuttal might be helpful to understand the distinct insights in this work
  (especially, on the technical side, the differences that the authors allude
  to in the related work section between analysis of the SGD trajectory, as
  here, with the one-step gradient trajectory, given that both are unnatural
  two-stage ("layerwise training") algorithms).

- The claim at the start of section 4.1, suggesting that a key aspect of the
  neural network training/generalization problem revolves around coping with
  model misspecification (positing the existence of such an underlying model),
  is interesting and thought-provoking. Another line of theoretical work on
  neural nets focuses on the ability of neural networks to learn to adapt to
  specific low-dimensional structures in data itself -- e.g. in terms of
  representation capacity [1], or algorithmic aspects [2-5]. Adapting to this
  type of structure, and the analysis it entails, seems somewhat different from
  what the authors study here, and I would be curious to hear the thoughts of
  the authors on whether there are similarities, whether they are in tension,
  etc.

[1] http://dx.doi.org/10.1093/imaiai/iaac001

[2] https://proceedings.neurips.cc/paper/2020/file/a9df2255ad642b923d95503b9a7958d8-Paper.pdf

[3] https://openreview.net/forum?id=O-6Pm_d_Q-

[4] https://papers.nips.cc/paper/2021/hash/f26df67e8110ee2b44923db775e3e47f-Abstract.html

[5] http://arxiv.org/abs/2206.12314


clarity,_quality,_novelty_and_reproducibility: The paper is excellently written. The paper has a similar motivation, and
applies similar technical tools, to other concurrent works in this area --
there are slight differences in the setting considered here that the authors
may unpack in more detail in the rebuttal (the differences mentioned in the
paper, that of SGD vs one-step gradient, seem like they might be superficial).


summary_of_the_review: Similar to other quasi-concurrent works, this work presents an interesting
mathematical study of a single level of representation learning in nonlinear
neural networks trained in function approximation-type tasks with imperfectly
specified models (beyond the typical teacher-student). The results here are
similar to those in concurrent works, but the excellent presentation makes this
work a valuable entry point to this evolving topic in the literature.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper  proves  that SGD on neural networks can learn low-dimensional features in certain settings, and uses this to derive novel generalization and excess risk bounds.
strength_and_weaknesses: 
This paper study the convergence of SGD (applied  to two layer networks)  to the principle subspaces of the teacher model.
Strength:
Studying the convergence of SGD sequence to the estimation target (not only to the minimizer at the optimization level) is an important perspective to understand SGD in deep learning.
Since the the target model is a multi-index model which is easier to due to the low dimensional intrinsics structure. So it is not surprise the final   results   reducing  the curse of dimensionality.

Weakness:  In the perspective of nonparametric regression, we also need bound the estimation error, i.e., the estimated network function and 
target function g.  But the authors never mentioned  about this.   See for example  
1:  I. Kuzborskij and Cs. Szepesvári. Nonparametric regression with shallow overparameterized neural networks trained by gd with early stopping. COLT, 2021.
2:  T. Hu, W. Wang, C. Lin, and G. Cheng. Regularization matters: A nonparametric perspective
on overparametrized neural network. AISTATS, 2021.
3: S Frei, NS Chatterji, PL Bartlett， Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data， COLT,  2022.
clarity,_quality,_novelty_and_reproducibility: The paper is well orgnized.
summary_of_the_review: A nice work. And it can be better if  the author will study the nonparametric estimation error.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies layer-wise training by SGD for two-layer neural networks under teacher-student setups. Specifically, for the multiple-index models as teachers, the paper shows the convergence to the principal subspace spanned by the true parameters of the teacher. Moreover, several applications of this result are provided: (i) the learnability of the single-index model, (ii) an efficient generalization error bound, and (iii) compressibility guarantees.
strength_and_weaknesses: **Strengths**:

The feature learning property of neural networks trained with SGD has become a challenging research interest. Recently, many studies have been devoted to this line of research, but there are still several limitations. In this sense, the paper certainly contributes to the context by studying the SGD with multiple steps.

- This paper provides an efficient sample complexity linear in the input dimension for learning the single-index model, which improves the existing results in related studies which treat one-step gradient descent. This improvement would be nice.

- Moreover, the connection with an efficient generalization bound (Theorem 5) and the compressibility guarantee (Theorem 6) are also interesting, although these results are straightforward applications of Theorem 3.

**Weaknesses**:

- For the case $k>1$, the theory (Theorem 3) does not guarantee the convergence to the true parameter. In other words, the optimization accuracy is unclear in general, and thus the theory cannot estimate how small the expected risk can be.
- A learnable class (i.e., $k=1$ and $f$ is monotone) is still rather limited compared to [Abbe et al. (2022)] which shows the learnability of staircase functions.

However, I also acknowledge the difficulty of overcoming these limitations.
clarity,_quality,_novelty_and_reproducibility: This paper is well-organized and easy to read, and there is a certain improvement over the existing results.

Minor comment:

- The definitions of notations $R(W), R_\lambda(W)$ omitting $a, b$ are missing, although we can guess them.

Question:

- The right-hand side of Eq. (3.2), (3.3) can be arbitrarily small as $\gamma \to \infty$. Is there any condition on $\gamma$ missed in this statement?
summary_of_the_review: Although there are still several limitations in the theory, this paper certainly contributes to the context by providing an improvement over the existing studies.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies neural network learning problems in which the target y is a function of a few linear projections <u_1,x>, …, <u_k,x> of the input x (the “multi-index model”). This problem is motivated by the general goal of understanding how deep networks adapt to low-complexity structure in the learning task. The paper studies the convergence and generalization of SGD for learning two-layer networks from this data, and shows that with weight decay, the first layer weights converge to the subspace spanned by u_1, …, u_k. The paper gives generalization bounds for SGD which are dictated by the dimension of this subspace, and proves that the weights of the learned network are compressible. 

Reviewers expressed a uniformly positive evaluation of the paper’s contributions: conceptually, it illustrates how neural networks adapt to low-dimensional task structure, while at a technical level it improves over related works by controlling the entire trajectory of SGD, rather than just a single gradient step (which has a closed-form expression). One technical limitation is that although this approach shows convergence to the principal subspace, it does to control the behavior within the principal subspace, and hence for k > 1 controls the generalization gap, and not the excess risk. However, these results still show the benefit of low-dimensionality, and the paper’s learning results for single index models are novel. The paper’s results for single index models contrast favorably with lower bounds for learning polynomials in the NTK regime. Reviewers also found the paper to be very clearly presented. 
justification_for_why_not_higher_score: Overall, this is a strong technical paper. There are some minor limitations to the results -- the strongest generalization guarantees are for the k = 1 case, and, while the theory shows convergence to the principle subspace, it does not control what is learned within the principle subspace. 
justification_for_why_not_lower_score: This is a high quality technical paper, with an interesting message (weights converge to the principal subspace) and technical contributions (control of entire SGD trajectory, generalization results for single index model and generalization gap for multi-index model that leverage low-dimensional structure). It deserves to be accepted in some form.
Decision: Accept: notable-top-25%