We thank the reviewer for their valuable evaluation and insightful feedback, and address their comments and questions below.
---
**The comparison with information/generative exponent analysis**:
We thank the reviewer for raising their concern about this comparison. We do not claim that MFLA achieves a sample complexity beyond that suggested by computational lower bounds (dictated by the information/generative exponent). Indeed, with exponential width, one may conclude that a small fraction of neurons enter the descent phase upon random initialization. However, as this subset is exponentially small, it is not clear that standard end-to-end training can achieve sufficient amplification of these “warm” neurons after $O(d)$ steps to lower the loss – this will not be the case if we run the spherical gradient algorithm (which is the update studied in most information/generative exponent analyses), because the neural network output is still dominated by the majority of neurons that have not “escaped from mediocrity”. \
Moreover, we highlight that the information/generative exponent analysis is only applicable to the ***Gaussian input*** distribution setting (with the exception of [1] which only considers rotationally invariant input distributions and known link function), and is further limited in either assuming a known single-index link function and choosing the same link function as the activation, or having nontrivial modifications of the standard training procedure for 2-layer neural networks. Moreover, most results so far capture learnability for ***single-index*** models, and characterizing learnability of general ***multi-index*** models with this type of analysis is much more challenging, and these analyses typically fall short of providing a concrete sample complexity for such general settings.\
Part of our motivation here is to instead provide a general and unifying theory for ***all multi-index models*** in a ***distribution free*** sense, which comes at the cost of a larger worst-case computational complexity. Moreover, the adaptivity of such analysis to ***low effective dimension***, i.e. low-dimensional input embedded in a high-dimensional space, has not been established in prior works. We hope that this discussion helps provide additional context in comparing our work with the literature.
---
**Examples of natural functions in Proposition 8**:
Thank you for the suggestion. We have added an example in Appendix D that we believe will in fact provide further insights to the readers. In summary, we let $\mathcal{W} = \mathbb{S}^{d-1}$ and $\Psi(x;w) = \langle x, w\rangle^2$. We let $\mu^*$ be the distribution of $\frac{A^{1/2} u}{\Vert A^{1/2} u\Vert }$, where $u \sim \mathrm{Unif}(\mathbb{S}^{d-1})$. Then, $\hat{y}(x;\mu^*) = \frac{1}{d}\Vert B^{1/2} x\Vert^2$ where $B = A^{1/2}\mathbb{E}\left[\frac{uu^\top}{\Vert A^{1/2}u\Vert^2}\right]A^{1/2}$, whereas $\hat{y}(x;\tau) = \frac{1}{d}\Vert x \Vert^2$ (please note that we assume the typical norm of $x$ to be of order $\sqrt{d}$). If we simply let $A = \mathrm{diag}(\lambda_1,1,...,1)$ and $\lambda_1 = 1/d$, then $\Vert B - I_d\Vert_{\mathrm{op}} \geq \Omega(1)$. This means that for some distribution over $x$, the initialization $\tau$ has $\Omega(1)$ loss, and one needs to train with MFLD to recover $\mu^*$ and achieve small loss. Furthermore, $\bar{\Delta} \leq \mathcal{O}(\ln d)$ in this setting, thus we can achieve the polynomial convergence guarantee of Theorem 10.
---
**The effective dimension does not capture the latent low dimension in the multi-index model**:
We would like to highlight that there are two sources of potential low-dimensionality, and only having a small number of indices $k$ is not sufficient to learn with linear sample complexity while having polynomial time convergence, as evident by computational lower bounds [2,3]. While for isotropic input covariance we can achieve the optimal linear sample complexity *regardless of information/generative exponent*, we believe that the additional benefit in sample and computational complexity thanks to the *low effective dimension* is an interesting phenomenon which is mostly overlooked in the current literature on feature learning of neural networks, especially since in practice directions of high variation tend to be better predictors of the label, i.e. many problems tend to have a low effective dimension [4].
---
We would be happy to clarify any concerns or answer any questions that may come up during the discussion period.
References:
[1] A. Zweig et al. “On single index models beyond gaussian data.” NeurIPS 2023.
[2] A. Damian et al. "Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models." NeurIPS 2023.
[3] A. Damian et al. "Computational-Statistical Gaps in Gaussian Single-Index Models." COLT 2024.
[4] T. Hastie et al. "The elements of statistical learning: data mining, inference, and prediction." 2009.