We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.

My understanding is that three layers aligns closely with the target model (where the middle layer matches up with the polynomial features h). As such, is there any benefit to introducing additional layers?

The reviewer is correct in their interpretation. For our class of targets, there is no benefit, as far as feature learning and the scaling of sample complexity is concerned, in introducing an additional layer in the scenario described where the target model is also three-layer like.

For simple real datasets, can we observe a separation in sample complexity between two- and three-layer networks?

We did not explore sample-complexity separation on real datasets in the present manuscript. Although the focus here is theoretical, exploring the consequences of our results on real data, via identification of effective dimension and intermediate hidden representations, is a promising avenue for future work, and we will mention this in L73–74.

Assumptions are clear, although somewhat overly specific at times.

We acknowledge concerns about the specificity of our assumptions. In the revised version, we will integrate Appendix C.7 into the main text, where we will explicitly construct an activation that satisfies all assumptions to provide clarity.

However, numerical simulations are quite limited, and although they explore relaxing certain assumptions, are still largely rooted in the synthetic setting.

Extending the verification of our theory to realistic data distributions is challenging, as we currently lack methods to identify the "effective dimensions" of hidden representations in such settings. Nevertheless, our analysis provides concrete directions for such explorations, for example, by interpreting the eigenfunctions of the conjugate kernel across depth and considering appropriate notions of "effective rank" for the same. We will highlight these experiments as future work in the revised version.

The target introduced for imposing hierarchical structure does not appear to be significantly novel, weakening this aspect of the paper.

While several hierarchical data models have inspired our targets (see L163–172), we respectfully disagree that our MIGHT targets lack novelty. They offer an exactly solvable playground enabling rigorous description of feature learning capabilities in deep networks trained with Gradient Descent through progressive dimensional reduction.

Thank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification.

We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.

To my understanding, Theorem 2 is not really considering training in arbitrary middle layers. It only studies what happens when training the $L-1$ layer where $L$ is the network depth. Would it be possible that under a specific initialization of later layers, the same result can hold for middle layers without much additional effort?

Theorem 2 applies to a simplified setting where the $(L-2)$th layer has already perfectly recovered the corresponding features. Hence, only the $L-1$ layer is required to additionally learn the last level of hidden features. Ideally, we hope to apply the argument inductively to prove feature learning for all layers. The primary bottleneck toward such a generalization is that our analysis does not apply to the recovery of a diverging number of non-linear features.

A missing related work is [1] where the authors study learning multi-index models with neural nets under structured input. Specifically, a direction for future work can be to extend the definition of effective dimension in [1] to hierarchical models to capture the effect of anisotropy on sample complexity.

We thank the reviewer for the suggestion regarding [1]; extending the definition of effective dimension in [1] to hierarchical models is an exciting direction for future research and will be discussed in the revised version.

My main concern is the lack of a concrete negative result for 2-layer networks. The authors provide a heuristic argument in the main text for why they would achieve a higher sample complexity for learning higher degree components in the target, but given the importance of such a negative result to theoretically capture the computational limitations of 2-layer nets, I think it deserves a theorem of its own. Specifically, I think the argument presented in Appendix B.1 is nice, I’m not sure why it isn’t highlighted as a formal theorem in the main text.

We agree on the importance of obtaining and stating precise negative results. The discussion in Appendix B.1 is limited to a particular choice of the MIGHT target, different from the SIGHT targets considered in Theorem 1. In the revised version, we will integrate this discussion into the main text as a formal corollary of existing results. Obtaining such negative results for the general choices of SIGHT and MIGHT targets is however, beyond the scope of our work.

I think the numerical simulations, in their current presentation, may not be entirely conclusive about the separation between 2-layer and 3-layer nets. The range of $\kappa$ in Figure 2 mostly includes the [0,1.5] interval where no algorithm achieves small test loss. It would be nice if the figure focused on larger $\kappa$ where a more clear separation should be observed between all algorithms, at least up to $\kappa=3$ similar to Figure 1. However, I agree that performing experiments for larger $\kappa$ can be challenging due to the amount of needed compute.

To address concerns about the simulation section, we will include references to Appendix F.3, where the evolution of the order parameters (Definition 236) exemplifies sharper transitions, and add experiments for additional input dimensions and values of $\kappa$. We appreciate the reviewer’s understanding regarding computational constraints and will clarify learning-rate choices in the numerical appendix.

Thank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification.

We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.

Can the authors comment on the technical benefits of using online batch learning for the first layer and a giant step for the second?

We will expand the paragraph dealing with the use of online batch learning for the first layer and a giant step for the second (L266–270) in the revised version. The use of online learning for the second layer is both harder to analyze as well as suboptimal in terms of sample complexity due to the ill-conditioning of the landscape. Due to the polynomial decay in spectrum of the conjugate Kernel, without pre-conditioning, both online or batch gradient descent would require polynomial in $d$ steps, which would in turn need a “drift plus martingale” type of analysis for the second layer features, leading to various technical challenges. However, our experiments support that our theoretical results hold for non-conditioned Gradient Descent with multiple iterations on the same batch (see L269–270 and L418–419); we will comment on this further in the revised version.

Why do the networks in Figure 2 perform worse than random chance during the initial stages of learning?

In the regimes of low sample-complexity, the gradient steps effectively add noise to the parameters. Since our simulations do not involve projections, this noise results in a scaling of the norms of the parameters. We believe this initial worsening of performance to simply be an artifact of this scaling.

As a curiosity: I would expect that once the condition $1 > \epsilon_1 > \dots > \epsilon_L$ is violated, depth would no longer be beneficial. Can the authors comment on this scenario?

We thank the reviewer for this insightful question. We believe that an advantage of depth would persist even in the absence of a strict decrease in the chain of dimension exponents, since a high-degree polynomial expressible as a composition of lower-degree polynomials can be learned with fewer samples upon the recovery of the intermediate low-degree polynomials. For instance, consider the following heuristic example: a degree-4 target would require $O(d^4)$ samples to be directly learned in the original input-space. However, if the degree-$4$ target is expressible as a degree-2 function of $O(d)$ quadratic features, then upon learning these $O(d)$ hidden quadratic features, the sample complexity of the target would be reduced to $O(d^2)$. Thus, the "dimension-reduction" can proceed at the level of the space of high-degree polynomial features even without an explicit reduction in the dimension of the features. Turning this heuristic into a rigorous analysis would, however, require a control over the "approximate independence" of such non-linear features, which we believe to be technically challenging. The strict decrease in dimensionality and the "tree-like" construction of targets in our setup avoids such issues by ensuring the exact independence of non-linear features. We will include the above clarifications in the revised version.

Lines 260–261 seem contradictory: a problem is stated to be open, yet the next line references [7] as providing a solution. Does [7] consider a different setting than the open problem just mentioned?

The reviewer is correct and the present phrasing is confusing; it will be corrected in the revised version. What we meant is that [7] considers the problem of joint training and introduces the concept of backward feature correction, i.e., how errors in lower-level features can be corrected through training of higher-level features. Although [7] is an inspiring reference, the key element in our analysis is to rigorously control the overlap between the target and network preactivations and to precisely describe the separation of deep networks versus shallow ones thanks to non-linear feature learning and progressive dimensionality reduction. This task is currently hard to tackle in a joint training setting and it constitutes an interesting direction of research.

[Idealized setting] a) All the analysis relies on the assumption of Gaussian inputs. While this is a clear gap with respect to real-world applications, I believe it should not carry much weight as a weakness ... b) The theoretical analysis assumes a simplified layer-wise training protocol which ... could be suboptimal. However, simulations support that for this class of targets, standard SGD also achieves the same thresholds.

We strongly appreciate the constructive comments on the Gaussian-input assumption and the simplified training protocol. We agree there is a gap between theory and real-world applications, and our work provides initial steps towards understanding the mechanisms that one could expect to hold in other realistic settings.

The simulation section is not entirely satisfactory. Figure 2 shows very limited separation between two- and three-layer neural networks. I suggest extending the plot to larger values of $\kappa$, to verify whether the predicted plateaus are attained. It would also be advisable to run simulations for different values of $d$, to check whether the expected scalings hold. Additionally, the descent phase for both two- and three-layer networks seems to require many samples to approach their plateaus—could this be due to suboptimal learning rates during the descent phase?

To enhance the presentation of the numerical illustrations, we will include in the main text references to Appendix F.3, where we consider the evolution of the order parameters appearing in the main theorems (Definition 236)—i.e., the overlap between target and network preactivations—that exemplify a sharper transition around the predicted threshold. Moreover, we will include additional input dimensions and values of $\kappa$ as suggested. Details on learning-rate scaling and hyperparameter sweeps will be added to the numerical appendix.

Thank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification.

Thanks for the detailed and satisfying answers, especially for the intuition in case the condition $1>\epsilon_1>\dots>\epsilon_L$ is violated: that polynomial example is really interesting and conveys another important aspect of depth. I suggest including it at least in the appendix. I confirm my rating.

We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.

Is there any overlap between these results and those of [1]? This also involved layer-wise training of hierarchical tasks.

There has been an extensive line of research in the theoretical machine learning community focusing on the learnability of multi-index models by shallow two-layer networks with layer-wise gradient descent (see L27 of the submitted version). The reference [1] that the reviewer points out defines rigorously the concept of “staircase”, or sequential learning of relevant directions (in our notation, rows of $W^\star_1$). While staircase functions exhibit sequential learning, they do not require adaptation across depth. In this manuscript, we offer perspectives on the learnability of deep hierarchical targets (as opposed to multi-index models) with deeper networks (in contrast with two-layer ones).

Could the authors offer more intuition about why pre-conditioning is useful for training the second layers, and whether they suspect it to be necessary?

The choice of pre-conditioning is needed for the rigorous scheme due to the ill-conditioning of the landscape and to the polynomial decay in the Random Feature kernel’s spectrum. Without such pre-conditioning, Gradient Descent will require polynomial in $d$ steps on the same batch of data to learn our class of target functions, which remains outside the scope of present proof techniques in the literature. However, our numerical experiments support that the theoretical claims hold for non-conditioned Gradient Descent with multiple iterations on the same batch (see L269–270). Therefore, we do not believe this element to be necessary and we will state it more clearly in the revised version.

The role of the assumptions: a) I would recommend introducing the information exponent rather than referring readers to other papers, especially given its relevance to Assumption 3. b) When introducing assumptions in Section 3, it would be helpful to highlight examples that satisfy those assumptions (e.g. targets satisfying Assumption 3).

We thank the referee for the pertinent suggestions regarding Assumption 3. The existence of an activation satisfying the assumptions is present in Appendix C.7 but is not referenced correctly in the main text. We will introduce the information exponent explicitly and highlight concrete examples that satisfy each assumption.

L314: Instead of ‘exists a sequence of random matrices,’ should this refer to a distribution of random matrices?

The exact distribution of the random matrices is specified under the formal statement of the theorem in Appendix C.1.

Thank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification.

We sincerely thank the reviewer for the positive comments about our work and constructive feedback. Below, we answer your remarks individually.

The theoretical challenges involved in establishing these results are not detailed in the text. Discussing the main ideas and difficulties that led to this extension would help readers better follow the contributions.

We will expand upon the challenges in our analysis under the proof sketch in Section 3. The revised paragraphs will provide additional details along the lines of point (ii) in the proof sketch. More precisely, the analysis of the dynamics of the first-layer weights $W_1$ in our setting requires incorporating the diverging dimensionality of the subspace $d_{\epsilon_1}$, while for updates to the second layer $W_2$, the central novelty is combining the adaptivity of $W_1$ with the random features scaling polynomially in the dimension.

What happens if there is a mismatch between teacher and student depth? Is there any benefit to using a three‑layer network to learn a two‑layer teacher model?

The benefit in [65] towards using a three-layer network to learn a two-layer target arises primarily from the ability of the second layer to learn non-linear features, a capacity which the first layer explicitly lacks. For general depth, however, all intermediate layers can learn non-linear features. We conjecture that for our class of targets, an $L$-layer model suffices to reach the optimal sample-complexity for an $L$-layer deep MIGHT.

I could not follow the part regarding $a^\star_i$. It is introduced as sampled from a distribution but later fixed to all ones. Is there a mistake here?

Our class of targets is defined with a general distribution over $a^\star$. However, for technical reasons, such as the requirement for spherical symmetry, our proofs are limited to the case $a^\star_i = 1$. In the revised version, we will clarify this point along with reporting that the simulations have been carried out for $a^\star_i \neq 1$, but rather drawn i.i.d. from a Rademacher distribution.

Thank you for pointing out the typos that will be fixed in the revised version and the valuable observations. We remain available for any additional clarification.