Summary
This paper studied the problem of learning single index models under Isotropic Gaussian distribution. The target model $f^*(x) = \sigma(\theta^\top x)$ is a polynomial function $\sigma$ composed with a one-dimensional structure $\theta^\top x$, where the polynomial $\sigma$ is of degree at most $q$ and has information component (i.e., the order of the first non-zero Hermite polynomial expansion) $p$. The paper studied the sample and computational complexity of learning such single index models with 2-layer neural networks, using gradient descent type methods. The critical aspect of the algorithm is reusing the same batch of samples every two iterations, which frees the algorithm from CSQ constraints and becomes an SQ algorithm. A critical observation is that by reusing samples at each iteration, the algorithm induced a monomial transformation of the labels, which effectively reduced the information component from $p$ to less than 2. Hence, the algorithm can achieve near-optimal sample complexity $\tilde{O}(d)$.
Strengths
1. This paper is clearly written with intuitions and useful explanations.
2. This paper provides new perspectives on designing SQ algorithms to learn single-index models using neural networks. Though the idea of reusing samples has already appeared in prior works ([DTA+24]), this work shows that resuing samples can achieve strong recovery of the hidden direction and provides a well-rounded analysis of the sample and computational complexity. Importantly, the authors showed that by reusing the mini-batches, one can learn the target model with $\tilde{O}(d)$ samples, which is near the information-theoretic limit.
3. This paper provides a very interesting intuition on reducing the information exponent of the link function $\sigma$ using monomial transformations, which could be of independent interest for future works.
Weaknesses
1. Though the authors claimed that they were using neural networks to learn the single index model, the activation of each neuron turns out to be a combination of polynomials. Hence, the neural network $\sum a_j\sigma(w_j^\top x + b_j)$ is essentially a linear combination of Hermite polynomials. In this case, I am wondering what the differences are between using the 'neural network' to learn the single index models and using polynomials to learn the single index models, which is already done in [CM20]. Of course, [CM20] requires a warm start procedure, which is not a gradient descent type algorithm, but I think it would be more interesting if that analysis is carried out on conentional neural networks like ReLU networks.
2. The authors hide many constants in the big-O notations. However, I am skeptical that all those parameters are independent of the dimension $d$. For example, in the proof of Proposition 4, the upper bound on $C_q$ is $1+\log_2(H_0^{-1})$. However, there is no actual lower bound on $H_0$ other than that being non-zero. Therefore, I am wondering if it is possible that $H_0$ can be as small as $2^{-d}$? I think the paper will be more theoretically sounded if the authors can explicitly present the dependence on the parameters $C_q$, $C_\sigma$ etc. in the final bounds on the sample complexity and iteration complexity.
Questions
1. Do ReLUs and sigmoids satisfy the assumption 2?
2. I think there are typos on line 593 to 595. What is 'x' on the right-hand side of line 593 and 595?
3. Since only $exp(-q)$ neurons satisfy assumptions 2 and 3, does it imply that the width of the network is at least $exp(q)$?
4. Since Theorem 2 relies on neurons that satisfy assumptions 2 and 3, does it imply that having only an $exp(-q)$ fraction of good neurons (neurons with $w_j^\top \theta>1 - \epsilon$) is enough to achieve small $L_2^2$ error? What is the intuition behind this?
Limitations
The authors addressed the limitations of the paper and provided inspiring future directions.