Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model

As the authors will see, my rating is largely due to the presentation. Please consider making some of the following edits and/or answering my questions and I will gladly raise my score.

Major comments:

Alg 1: I am having trouble understanding the definition of the main algorithm, Alg 1. What is $err^t$? It never seems to be defined in the paper (main body or appendix).

Eq D.2 Was this sketch intended only for the case of $s_* \geq 2$? If $s_* = 1$ then the $\tilde{O}$ term in the norm bound in Eq D.2 seems to be the dominant term and divergent.

Gradient based: It is not to me why the authors refer to their algorithm as gradient based. On the one hand, their algorithm as stated is more general, it is an online algorithm given some function $\psi$ which, in certain cases, is a gradient.

However this does not seem to correspond to an optimization algorithm for risk based inference on a loss of the form $L(y - f(z,\theta))$. How can you get a small loss since the algorithm is only updating the hidden layer? Also, why can't we just take $a = 1$ in this algorithm?

It seems that the answer is that something essential is baked-in to Assumption 4.1(b). E.g., if $y$ can be both positive and negative but we take $a,\sigma$ to both be positive we run in to issues; This will presumably violate (b)? Am I missing something?

Also, perhaps your point is that you can view it as an optimization scheme where youre finding the best fit in this model with constant second layer, and we don't really care about minimizing the loss because our goal is really to infer $\theta_*$?

Minor questions/comments + typos:

unknown link Contributions item 2, you state that the link function is unknown. Is the assumption that the generative exponent mild? Can you access this given just the data/without knowing the link? What happens if it is misspecified?

Definition of model In Eq 2.1 you define the model, but your first example, immediately after seems to not fit in to this framework due to overloaded notation. Perhaps choose different letters for the link function and link probability?

Ln 83: "thus there is no...gap..." I do not see how this is concluded. what you stated only implies that the algorithmic and information theoretic thresholds are the same order of magnitude. They can still be different, no?

Ln 176: The notation $\mathcal{N}(z^\perp;0,I)$ should be defined.

L^p The notation $\stackrel{L^2(P)}{=}$ is a bit excessive. Perhaps just write = ?

Assumption 4.1 Please condense this. For example, instead of "Both $\psi(x,y)^2$ and $\psi(x,y)^2x^2$ are square integrable..." maybe just "$\psi(x,y),\psi(x,y)\cdot x \in L^4(Q)$? Also, the remainder of Item (a) is more of a downstream consequence. Perhaps move this observation outside of the assumption environment.

Ln 254 "Fourier coefficient" Perhaps "Hermite coefficient"? Ln 302 Netwok ---> Network ?

Ln1280 “follows from [a] Bernstien type...”

• Is there any potential to use losses other than the squared loss to avoid label transformation, similar to [1]?

• In the case of sparse priors, prior work [2] also employs a similar approach to that used in this paper, involving index-sensitive perturbation followed by gradient sparsification and support identification via a top-k operator, achieving the CSQ-optimal bound for sparse priors. Could the authors elaborate on how their technique differs from this previous approach and discuss the challenges encountered in extending these CSQ results to the SQ setting?

[1] Joshi, N., Misiakiewicz, T., & Srebro, N. (2024). On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries. ArXiv, abs/2407.05622.

[2] Vural, N., & Erdogdu, M.A. (2024). Pruning is Optimal for Learning Sparse Features in High-Dimensions. Annual Conference Computational Learning Theory.

• There are some ambiguities in the discussion starting from Line 258:

  • The paragraph before introduces a general class of gradients $\psi(y,x)z$, but here we switch back to activations. What kind of loss function are we using here? The calculation seems to be for squared loss, but my impression was that we have to change the loss to go beyond correlational queries in this online setting.
  • The identity in Line 267 might require further clarification. For example, I think $E_Q[y^2]$ should be replaced with $E_Q[\zeta_s(y)y^2]$. Maybe we can apply Cauchy-Schwartz from here to use the assumption on $\zeta_s$, but this would lead to the fourth moment of $y$ appearing. Perhaps the authors could add more details on the derivation to make it clearer.
  • My impression was that the only benefit of weight perturbation is to give a smaller denominator in the SNR, however, that doesn't match the following argument. If I try to replicate the SNR calculation of the paragraph starting at Line 220 for this paragraph, the numerator in the SNR is still $d^{-(s^*-1)}$ while the new denominator coming from weight perturbation is $d^{-(s^*-3)/2}$. This leads to an SNR of order $d^{-(s^*+1)/2}$. We argued we need $\sqrt{n\mathrm{SNR}} \gg d^{-1/2}$, therefore $n$ should be of the order $d^{(s^*-1)/2}$. Are there other effects happening when we perturb the weights?

• Line 320 mentions that $L = \tilde{\Omega}(n/\sqrt{d})$ is sufficient. Given $n = d^{s^*/2}\lor d$, this leads to $L = d^{(s^*-1)/2}\lor d^{1/2}$ (which seems to be used in Remark 4.3 as well), which is different from $L$ in Theorem 4.2.

• The loss defined at the end of Page 22 is not exactly a loss function, for example it seems that it can decrease while $y$ is moving away from zero due to the derivative being negative. If this interpretation is correct, perhaps it could be highlighted in the main text that the goal of this loss is not to measure the difference with ground-truth labels, but to construct suitable gradient oracles.

• Can Assumption C.2 be verified for distributions with high generative exponent?

• Theorem 4.2 only states a lower bound on the learning rate. To me it seems like the ideal scenario would be to let the learning rate go to infinity, and directly update the model weights with the gradients as in Algorithm 2. Is there a reason we would want to have a finite learning rate in Algorithm 1?

• Relevant prior works:

  • Theorem 5.4 resembles Theorem 3.1 of [VE24], which presents the CSQ lower bound under sparsity, where generative exponent is replaced with information exponent. I think having a discussion on the similarities and differences of the two statements and techniques would be interesting.
  • The authors cite [Bach17] as an example of neural networks achieving $O(d)$ sample complexity for learning single-index models. From [Bach17, Table 1], it seems the sample complexity of learning single-index models is $O(d^2)$. In [Bach17, Table 2], the sample complexity will be $d$ with a sign activation and $d^2$ with the ReLU activation. There is a discussion on the sample complexity obtained from [Bach17] in [MHWE24], where the authors also show that standard gradient-based algorithms can achieve the optimal $O(d)$ sample complexity, albeit with a number of queries going beyond the SQ lower bound. This might be interesting to point out while having the discussion on information-theoretically optimal sample complexity with neural networks.
  • Another example of additional structure reducing sample complexity is structure in the input covariance, which is known to help in the CSQ setting [BESWW23, MHWSE23]. Developing algorithms that benefit this structure to achieve a smaller sample complexity in the SQ setting can be an interesting direction for future work.

References:

[VE24] N. M. Vural and M. A. Erdogdu. "Pruning is Optimal for Learning Sparse Features in High-Dimensions". COLT 2024.

[Bach17] F. Bach. "Breaking the Curse of Dimensionality with Convex Neural Networks". JMLR 2017.

[MHWE24] A. Mousavi-Hosseini, D. Wu, M. A. Erdogdu. "Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics". arXiv 2024.

[BESWW23] J. Ba, M. A. Erdogdu, T. Suzuki, Z. Wang, D. Wu. "Learning in the presence of low-dimensional structure: a spiked random matrix perspective". NeurIPS 2023.

[MHWSE23] A. Mousavi-Hosseini, D. Wu, T. Suzuki, M. A. Erdogdu. "Gradient-Based Feature Learning under Structured Data". NeurIPS 2023.

• Is there anything you can say for non-high-pass activations? More generally, I would like to understand whether these results generalises to some extents to natural gradient oracles.