Venue: NeurIPS 2022 Conference

Reviews:

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: The authors consider the problem of regression in high dimensions, with Gaussian i.i.d. inputs and a target function that is an arbitrary function that only depends on the projection of the input along a special direction, θ*. They study the performance of a two-layer neural network with many neurons, which however all share the same weight θ (the biases are different for each neuron, but they are random and fixed). The second-layer weights are free and optimised.

The authors first show that at small regularisation, the only first-order critical points of the population loss of the model correspond to a magnetisation of the model m =〈 θ, θ*〉= 0 at initialisation, and m=1 at perfect recovery. (Theorem 4.2). In other words, the optimization landscape in the population limit does not contain spurious minima or other obstacles.

They then study the generalisation of a model trained on the empirical loss. Considering an algorithm where they first train the first layer, then fine-tune the second layer while keeping the direction θ fixed, they obtain a bound on the excess risk (eq. 17) that has two parts: one that depends on the dimension, and which relates to the cost of escaping the saddle-point at initialisation, and a second part which comes from the non-parametric fine-tuning.
strengths_and_weaknesses: This is a clean and well-written analysis of feature learning dynamics. The authors propose an original model for the two-layer network that allows for a precise analysis, and I believe this model can be a nice addition to the set of models where these questions can be studied, in addition to the teacher-student setup. The authors do a good job imho of putting their work into the context on other recent results, such as recent work on "information exponents" Ref. [3]. All in all, I believe this paper will be of interest and use to the theory community at NeurIPS and should therefore be published.

questions: n/a
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 manuscript studies the supervised problem of learning a single-index model with a proxy model for a two-layer neural network where the first layer weights are tied and the biases are random. Different from previous works on single-index models, the link function of the target single-index model are not matched with the network architecture. Both layers are trained. The key result is to show that gradient flow on the empirical loss can achieve good approximation error of the target. More specifically, the main theoretical results are:

1. To show that the critical points of the population loss are benign, i.e. that all the local minimisers are global and correspond to the target weights.

2.  To show that gradient flow on the empirical loss with a particular choice of relative time-scaling for the update of the first and second layer weights finds an approximate minimiser of the population loss. Although recovery is optimal with respect to the first layer weights, it is sub-optimal in terms of the target function.

3. To show that the optimal statistical sample complexity for the recovery of the target can be achieved by re-training the last layer on fresh samples.
strengths_and_weaknesses: This manuscript adds to the increasing literature of theoretical works showing the separation between neural networks and random features model and the benefits of overparametrisation for optimisation in non-convex landscapes [1, 43, VSL+22, SVL22, BES+22]. Although the setting considered is artificial in many ways (tied weights, random bias, delayed gradient flow), the fact that  gradient flow on this network can approximate "well" a mismatched single-index model with is an interesting result.

**Strengths**: Despite the density of technical details, the paper is well written and the main thread is easy to follow. The main result is significant and timely.

**Weaknesses**: The setting considered is artificial in many ways, and therefore it is hard to say it is directly relevant to our understanding of the approximation and optimisation properties of two-layer neural networks. Rather, I see it as a constrained first step with desirable extensions.

**References** (numbered refs. are from the bibliography in the paper)

[VSL+22], R. Veiga, L. Stephan, B. Loureiro, F. Krzakala, L. Zdeborová, "Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks", arXiv: 2202.00293 [stat.ML]

[SVL22] I. Safran, G. Vardi, J.D. Lee, On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias

[BES+22] J. Ba, M.A. Erdogdu, T. Suzuki, Z. Wang, D. Wu, G. Yang, "High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation", arXiv: 2205.01445 [stat.ML].
questions: - **[Q1]**: Can the authors clarify why they believe the setting considered is natural when learning a single-index model (discussion in L38-L40)?

- **[Q2]**: Why the variance of the bias needs to be larger than one in the analysis (L94)? What would change in the analysis for $\tau<1$?

- **[Q3]**: Why the $\ell_2$ penalty parameter $\lambda$ is restricted to $(0,1)$ (L47)? Is this always satisfied by the optimal $\lambda$ leading to corollary 5.2?

- **[Q4]**: What role does the choice of $\phi = relu$ plays in the results? Would it be possible to derive similar guarantees for other activations?
limitations: The authors provide a nice discussion of the limitations of their work, as well as a list of possible improvements and future directions (L296-L308).
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 a single-index function with a shallow network trained via gradient descent. The function to be learned is of the form $f_{\star}\left(\theta^{\star}\cdot x\right)$, where both $f_{\star}:\mathbb{R}\rightarrow\mathbb{R}$ and $\theta^{\star}\in\mathbb{S}^{d-1}$ are unknown, and the data $x$ is Gaussian. The authors establish that the training landscape of this problem has no bad local minima, and then prove that $(f_{\star}, \theta^{\star})$ can be learned efficiently, modulo conditions on the width of the network and a two-part structure during training, where only $\theta$ is learned during the first part.
strengths_and_weaknesses: This is a very nice paper. It provides a positive answer to the (previously open) question of whether or not a shallow neural net can learn single-index functions via a constructive proof. The result contributes to our knowledge of the class of functions that can be learned efficiently with shallow networks and is therefore relevant to a broad machine learning audience. The paper is clearly written.

I do not find significant weaknesses.
questions: I’m curious why the authors feel that the teacher-student terminology is necessary in this paper? Can $F_{\theta^{\star}}$ not simply be referred to as ‘ground truth’ or the ‘true’ data generating process, as is standard in learning theory? If they can, then I suggest eliminating nonstandard terminology.

I think it would be helpful to the reader to explicitly state the following implications of Theorem 4.2 for the learning problem right after the theorem is presented: (1) all minima are global minima and (2) gradient descent will have to either avoid or escape the minima corresponding to $\langle\theta^{\star}, \theta\rangle=0$.

A little more discussion of $T_0$ and $T_1$ in the main text would also be useful. At present, $T_1$ appears in the main text for the first time in Algorithm 1, and I think there isn’t enough information in the main text about it to understand the algorithm. With regards to $T_0$, perhaps the logical place to first introduce it might be line 234? This will help the reader really understand the meaning of $\zeta(t)$, as well, without first having to go through the proofs. This will also make it clear \textit{before} the math is presented that the algorithm constructed by the authors has two different learning phases.

**A few minor things:**

Typo in line 35. Remove the word ‘in’ between ‘incurring’ and ‘a’.

Line 116. Maybe insert the word ‘between’ between ‘relationship’ and ‘each’?

The first time the acronym RKHS (line 99?) is used, its full form should be given.

A little bit of attention needs to be paid to capitalization in the references. For example, in line 311, ‘sgd’ should be ‘SGD’, and so on.
limitations: Yes.
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: The paper's focus is the learning of single-index models, in which the label $y$ of a datapoint $x\sim\mathcal N(0,I_d)\in\mathbb R^d$ is obtained as $y=f_\star(\langle \theta_\star,x\rangle)$, i.e., by projecting the data in a direction $\theta^\star\in\mathbb S^{d-1}$ and then feeding the result in a "link function" $f_\star\colon\mathbb R\to\mathbb R$. Both $\theta^\star$ and $f_\star$ have to be learned. The authors consider a shallow neural network of the type $$G(x;c,\theta)=\frac{1}{\sqrt N}\sum_{i=1}^Nc_i\phi(\langle\theta,x\rangle-b_i),\qquad \phi(u)=\max(0,u)$$
with frozen biases $b_i$ and depending on $c\in\mathbb R^N$ and $\theta\in\mathbb R^d$. They show that, in the considered setting, the critical points of the population landscape can be fully characterised: for example, for sufficiently small regularisation and sufficiently large width of the network, the critical points $\hat\theta$ of the population loss are such that $\langle\hat\theta,\theta^\star\rangle\in\\{-1,0,1\\}$.  They also provide a bound for the random feature approximation error in terms of the RKHS error. 

The paper moves then to analyze the empirical landscape, extracting the sample complexity scaling required to escape from the uninformative equator $\\{\theta\colon \langle \theta,\theta^\star\rangle=0\\}$, showing that the gradient flow on the empirical loss finds an approximate minimizer for a number of samples $n=O(d^s)$, where $s$, called information exponent, is related to the Hermite polynomial expansion of the target function $f_\star$. The theoretical understanding of the (empirical) landscape properties leads to the proposal of a gradient descent algorithm for $c$ and $\theta$, whose flow efficiently finds an approximate minimizer of the population loss.
strengths_and_weaknesses: *Originality* The considered setting can be seen as a special one within the large literature on single- and multi-index models that the authors properly cite in the paper; the landscape analysis is very inspired by the one presented in [19] (where a similar landscape topology is found, as acknowledged by the authors). All results are supported by rigorous analysis built upon the available literature on random features and kernel methods. To my understanding, the originality of the paper consists in constructing a simple and completely characterizable example of a learning task performed by training both layers of a shallow network using gradient descent in a nonconvex yet "benign" landscape.

*Quality* All results are supported by rigorous analysis and precise analytical bounds to the performances are provided. On the other hand, the proposed algorithm is not explored extensively from the numerical point of view (very few numerical experiments are given in the Appendix, and without implementation of the second fine-tuning step which is discussed in the main text).

*Clarity* The paper is clearly written and proceeds in sequential order in studying the population landscape and the empirical landscape, up to the proposal of an efficient gradient descent algorithm for the solution of the task.

*Significance* The main result of the paper is the full characterisation of the performances of a shallow neural network architecture (of a specific type) in learning a single-index model by means of gradient descent. The main significance comes, in my understanding, from the hybrid nature of the learning task (aiming at obtaining both $\theta$ and, non-parametrically, the link function) via a gradient descent scheme whose performances are clarified in terms of the benign landscape. As somehow the authors themselves stress in the conclusion, a weakness of the contribution is the rigidity of the investigated setting: the architecture consists of a shallow neural network whose hidden layer consists of $N$ ReLU neurons parametrised by the same $\theta$, differing only by their quenched bias. Also, assumptions on the dataset seem to be crucial for the analysis (see below). These assumptions might look a little bit restrictive/unrealistic, and it is not very clear to me how much the results can be considered robust: in particular, I wonder how much the simple properties of the landscape, which are pivotal for the results, are due to this combination of assumptions. Despite these observations, I personally found the paper interesting and possibly the first step for the study of more complex set-ups to investigate both the breaking down and the persistence/generalization of the phenomenology observed here.
questions: As the authors themselves pointed out, and as mentioned above, the considered model might look somehow rigid in its parametrization. I would like the authors to further comment on the robustness of their results. In particular, the Gaussian dataset leads the authors to choose Hermite polynomials as a basis of their decomposition and, e.g., the expansion of $f_\star$ on this basis determines relevant quantities, such as the information exponent. The authors might further comment on what they expect in the case of different data set distributions, maybe expanding the discussion on lines 157-163.

If compatible with the length restrictions, I think it might be useful to add to the paper a brief section discussing the implementation of the algorithm (e.g., moving the material in the Appendix in the main text) and some details on the numerical results.

*Minor typographical comments.*
- On page 3 (and in many other points, in particular in Secion 5) $F^*$ is sometimes called $F_{\theta^*}$ (see Definition 3).
- On page 4, line 119 has $\phi_{b_j}$ in place of $\phi_{b_i}$. Also, I believe that the coefficients $\alpha_j$ missing are missing in the sum. In line 133, "we first the study optimization" > "we first study the optimization".
- On page 5, in Remark 4.4, $\hat P_\lambda$ misses a hat.
- On page 6 line 206 subscript d missing on $I_d$.
- On page 7 in Theorem 5.1, it is maybe more convenient to write "Algorithm 1" in place of "procedure 1" for reasons of clarity (similarly at a later stage in line 281 Procedure 1 refers to the box named Algorithm 1). Also, there is an extra parenthesis in eq. 12 and, in line 241, an exponent 'outside' the O-notation.
- In Appendix eq 15, $\sigma$ should probably be replaced by $\phi$.

*Additional references*
The authors might consider adding the reference
V Ros, G Ben Arous, G Biroli, C Cammarota, Physical Review X 9 (1), 011003 (2019)
in line 86, as in this paper the quenched entropy of the spiked tensor model is computed, complementing the rigorous results in [4].
limitations: The paper is of theoretical nature and there are no potential negative societal effects and/or limitations of a sort in this respect. The weaknesses of the contributions are discussed above.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors study the problem of learning a single index model using a specific class of two-layer neural networks. The network structure is nonstandard, because its bias terms are random initialized and fixed (not trained), and weights are tied across all neurons. The first main result is a population landscape theorem, which states that the first-order critical points are either in the poles ($\pm \theta^*$) or on the equator ($\langle \theta, \theta^* \rangle = 0$). Building on this result, the authors then study the empirical loss. They prove that the (nonstandard) gradient flow converges to a solution with desired generalization error.
strengths_and_weaknesses: Overall, I find this paper very clear and solid. The model under study is simplified but more complicated than existing ones (i.e., random features model). While the proof strategy is mostly built upon existing ideas, the new challenge is the interaction between parameters $c$ and $\theta$. Below is a more detailed assessment.

**Pros**:
- The landscape result is very clear. It shows that under essentially minimal overparametrization the critical points are either the true directions or orthogonal to the true directions. 
- It is proved that gradient flow (with certain warmup and fine-tuning) achieves the optimal generation error under optimal sample complexity $n \gtrsim \Omega(d^s)$.
- The proof seems to be a nice combination of the landscape analysis that is popular for analyzing many nonconvex problems and gradient flow analysis for lazy training. 

**Cons**:
- The neural network structure is rather simplified. While I do not complain about useful simplification (which is standard in the literature), the title and abstract are rather misleading; for instance, it is not mentioned that the weights are tied, which is crucial for this work.
- It is not clear whether certain tweaks such as warmup and fine-tuning are necessary in practice. Perhaps the authors should discuss how these tweaks would affect the practical aspect of training neural nets.
- Some further questions about theorem statement (see below).
questions: - Q1: In the statement of Theorem 5.1, the probability is "greater than $1/4 - 2\delta$". Is it possible to strengthen this to a high probability statement? If not, why?
- Q2: The authors mention that they student the critical points of $L(c, \theta)$ through projected population loss. Based on that, I expected that during the initial warmup stage ($t \le T_0$) one trains $c$ first, but Eqn. (11) is the contrary. 
- Q3: I do not understand why we cannot achieve the optimal generalization error without fine-tuning. Is this an artifact of the proof? If so, where is the bottleneck and how fine-tuning improves the rate? If not, what is the implication for the practice?

Some typos:
- Line 119: $\varphi_{b_i}$ not $\varphi_{b_j}$
- Line 133: "first the study" --> "first study"
limitations: An evident limitation is that the model is rather simplified, but I believe this is on par with the current level of neural network theories. There are tweaks such as certain nonstandard $\zeta$ scheduling, and these limitations are discussed in the paper.
review_title: null

Meta-review: metareview: In this paper, the authors study the problem of learning a single index model using a specific class of two-layer neural networks. Interestingly, at variance with previous works on single-index models, the target single-index model is not matched with the network architecture and Both layers are trained. One of the key results is that gradient flow can achieve a good approximation error in this setting.

The consensus is that this theoretical paper constitutes a nice, and well-written analysis of feature learning dynamics, a topic of current interest in statistical learning theories. It definitely adds to the current literature on the separation between neural networks and lazy regime (NTK, etc...),  and on the benefits of over parametrization for optimization in non-convex landscapes (benign overfitting, etc...). All referees were clearly supporting acceptance.
confidence: Certain
Decision: Accept