Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models

Summary

This paper studies efficient parameter estimation from generalized linear models with adversarial noise (a.k.a. agnostic learning), assuming a known link function. The goal is to find a parameter vector that best explains the data. The authors show that $d^{\lceil k^*/2 \rceil}$ samples suffice for this problem with $k^*$ being the information exponent. The algorithm is given by certain projected gradient descent (w.r.t. loss truncated to degree $k^*$ Hermite polynomials) initialized with PCA for tensor unfolding. The sample complexity matches a known CSQ lower bound $d^{k^*/2}$ for even $k^*$ in the realizable setting (i.e., random noise).

Strengths

NA

Weaknesses

NA

Questions

Major comments: 1. The work [DPVLB24] is compared in B.3, but I'm not sure it's comparable. That paper obtained the conjecturally optimal sample complexity $d^{\bar{k}^*/2}$ with $\bar{k}^*$ being the generative exponent which can be much smaller than $k^*$. The way I read [DPVLB24] is that if preprocessing is allowed, $d^{\bar{k}^*/2}$ can be achieved. Otherwise, we're stuck at $d^{{k}^*/2}$. In the current paper, no preprocessing is used. Could the authors comment on the possibility of reducing the sample complexity in the agnostic setting with preprocessing? Or the difficulty of applying a suitable preprocessing that brings down the effective information exponent? Note that the optimal preprocessing in [DPVLB24] relies on the link function. With additional work, they can make it work for misspecified models (a.k.a. unknown link function). But I'm not sure if this is possible with adversarial noise. 1. I would be cautious to claim that $d^{\lceil k^*/2 \rceil}$ **nearly** matches the CSQ lower bound $d^{k^* / 2}$ since there's a nontrivial gap in the exponent for odd $k^*$. This is inconsistent with the standard definition of "nearly" in say TCS. 1. Regarding the ceiling in the exponent, I suspect that this is a proof artifact since for tensor PCA, the ceiling in [RM14] can be removed with (much) more careful analysis https://arxiv.org/abs/2110.10210 . Minor comments: 1. I didn't check all the cited papers (in the intro and appendix B) but would like to invite the authors to caution the following terminology discrepancy. In classical stats, learning single-index models means learning the unknown link function. OTOH, for known link function with unknown parameter vector, the model is referred to as generalized linear models. There're also works consider learning the parameter vector from GLMs with unknown link function (as a nuisance parameter). However, it seems in recent years, people (especially deep learning theorists) have been interchangeably using SIM and GLM to refer to the above problems. Please make sure such discrepancies are taken into account when comparing prior works with the present result. 1. Line 63-66, I'm not familiar with the line of cited work on hardness, why is $d^{O(1/\epsilon)}$ regarded as hard? This seems to me a legitimate polynomial running time. Could the authors say a few more words about under which computational model (low-deg, SQ, SoS, AMP, etc) the problem is hard, and hard in what sense? 1. Line 72, what does $\sim$ mean? 1. Line 77, the condition $c_{k^*} = \Omega(1)$ doesn't make sense to me. I'm not sure what's the asymptotic in $\Omega(\cdot)$. I suppose $\sigma$ is a fixed function independent of $n,d$ (otherwise it again doesn't seem to make sense), so $c_{k^*}$ is either zero or strictly nonzero (note also that it can be negative). 1. Line 103, could the authors also specify the dependence of running time on $1/\epsilon$? 1. Paragraph after Thm 1.2: there's a huge difference between CSQ and SQ. Are there more formal reasons (e.g., SQ lower bound) to believe that agnostic learning GLM is still hard under SQ (beyond the fact that known SQ algorithms for realizable learning fail)? 1. Line 195, "small constant $\epsilon_0$" is mildly misleading -- $1/2$ doesn't seem to be a small constant... 1. End of line 200, there's a redundant 2 in the exponent. 1. Line 223, is $l$ defined to be $\lceil k/2 \rceil$ or $\lfloor k/2 \rfloor$? 1. Line 2 of Algorithm 2, the subroutine Initialization is undefined. I assume it refers to PCA for tensor unfolding. 1. Line 557 is somewhat confusing, do the authors mean that **for any** positive constant $c$, partial trace cannot achieve $\mathbf{w}^0 \cdot \mathbf{w}^* \ge c$? 1. Line 572, I'm not sure why $\mathbf{w}^*$ is desired to be the unique top eigenvector. Do the authors mean that $\mathbf{w}^*$ is an outlier top eigenvector (meaning there's an eigengap between top two eigenvalues)? 1. Line 581-583, I think the exact information theoretic threshold is known for tensor PCA: https://arxiv.org/abs/1812.03403 1. Line 590, I think [HSS15] studies SoS instead of tensor unfolding (correct me otherwise). For tensor unfolding, the correct reference is https://arxiv.org/abs/2110.10210 which confirms the $d^{(k-2)/4}$ conjecture of [RM14]. I'm not sure of the relevance of the bound $d^{k/4}$. 1. Line 591, I don't understand where the $O(d)$ bound for unfolding comes from. The suboptimal analysis of [RM14] already gives $d^{1/2}$. And again, the above reference shows that $d^{1/4}$ suffices for tensor unfolding (which is sharp for unfolding). I'm not sure the relevance of $d^{3/4}$ here.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

NA

Summary

This paper studies the problem of _agnostic learning_ of single-index models, which consists of trying to learn a distribution $\mathcal D$ on $\mathbb R^d \times \mathbb R$ with an estimator of the form $y = \sigma(\langle w, x \rangle)$. Since the problem is not necessarily well-posed, the goal is to reach a performance of at most $C \cdot OPT + \epsilon$, where $OPT$ is the best possible performance. The authors present an algorithm that achieves this bound with a sample complexity of $d^{\lceil k^\star/2 \rceil} + d/\epsilon$, where $k^\star$ is the _information exponent_ of the function $\sigma$. This algorithm proceeds in two steps: the first obtains an informed initialization of the optimal vector $w^\star$ through a tensor unfolding method, which is then passed through an SGD algorithm to obtain the final estimator.

Strengths

I found the topic of the paper very interesting; I was mostly familiar with the realizable setting, and the adversarial version provides interesting insights and challenges. I particularly appreciated Appendix B, which compares in-depth the present work with previous papers on both the realizable and agnostic settings. The results encompass a wide class of link functions, and make no assumption on the data distribution at all (apart from Gaussian marginals). The arguments to handle such a diverse class of problems are conceptually interesting, and (as far as I checked -- see `Weaknesses`) correct.

Weaknesses

Apart from a few qualms with the presentation (see the minor remarks), my main issue with the paper is simply its length. With the short review time and high review count, it is strictly impossible to certify that a proof which consists of 20-25 pages of dense math, with many computation-heavy steps, is correct. I did check that the proof outline and the main steps seem correct, but it is my opinion that such a paper is incompatible with the Neurips review format, and should be submitted to a journal instead. My recommendation for acceptance, based on the overall quality of the paper, should be taken with such a caveat. Minor remarks: - the vector $w^\star$ is never rigorously defined; for the sake of exposition, the link between solving Problem 1.1 and obtaining good alignment with $w^\star$ should be emphasized. - In Assumption 1, the wording is confusing: since $\sigma$ is fixed, what is the $c_k^\star = \Omega(1)$ referring to ? My best guess is that the results hold uniformly over a class of link functions where $c_k^\star$ is bounded from below, and $C_k^\star$ and $B_4$ from above, but this should be made apparent if this is the case. - there should be a $w^t$ in the RHS of eq. (16). - You mention in the introduction that achieving $OPT+\epsilon$ performance is likely to be hard, but it's difficult to parse why the proof wouldn't extend in this case: this seems hidden in the recursion of Theorem 3.5. Highlighting this barrier would be a nice addition to the proof.

Questions

- In papers on the realizable setting (e.g. [DNGL23, DPVLB24]), the difficulty of the problem is not measured in terms of the link function $\sigma$, but the distribution of $(x, y)$ (assuming that $\sigma$ is ``nice''). Can such a measure be defined in your setting, instead of considering the worst-case scenario on $(x, y)$ ? - On a related note, in the aforementioned setting, a mismatch between $\sigma$ and the ``true'' link function can lead to a value of $OPT$ of order $\Omega(1)$, but some algorithms manage to achieve almost perfect alignment with the vector $w^\star$. In your case, a large value of $OPT$ yields vacuous bounds on both the performance of your algorithm and its alignment with $w^\star$; is there an explanation of this phenomenon ?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

The paper provides a polynomial-time algorithm reaching the optimal CSQ sample complexity (upto sub-leading factors) for a general class of single-index models under the setup of adversarial noise. Similar to existing works, the algorithm utilizes the empirical estimate of the k_th Hermite tensor of the target to obtain an initialization with a non-trivial overlap (weak-recovery) by estimating the top singular vector of an unfolded tensor. Subsequently, the algorithm utilizes mini-batch SGD on the sphere starting from non-trivial overlap to reach the optimal error upto a constant factor.

Strengths

The paper makes novel technical contributions towards understanding the sample-complexity of learning under the adversarial noise. Understanding the differences between the adversarial and realizable/random noise settings is crucial towards justifying applicability of CSQ and SQ lower-bounds in typical maching learning setups. The paper adequetly describes the technical challenges in matrix-concentration under adversarial noise as well as why the partial trace algorithm in Damian et al. (2024) cannot be directly applied under the adversarial noise setting (Appendix B.3).

Weaknesses

* The central ideas of obtaining weak-recovery by estimating the Hermite tensor and subsequently running minibatch SGD is largely similar to existing works (Biroli et al. (2020), Damian et al. (2023), Damian et al. (2024), Chen and Meka (2020)). Therefore, the major contribution of the work are adapting the ideas and analysis in these papers to adversarial noise, which has some technical but limited conceptual novelty. Even under adversarial noise, prior works have establishing similar guarantees for smaller classes of link functions. It is unclear whether the setup of adversarial noise is relevant for gradient based training in machine learning models. Discussion of the motivation behind studying the adversarial noise and the novel conceptual contributions/implications of the work will improve the paper. * In the realizable and random-noise case, recent works Dandi et al. (2024) and Damian et al. (2024) show the learnability of multi/single index models under reduced SQ complexity through reuse of data (implicitly transforming the labels) and explicit transformation of labels respectively. In light of these works, it has become apparent to the community that the SQ class is more suitable towards describing the limitations of gradient-based learning rather CSQ. Therefore, it is important for the paper to justify the choice of the CSQ class and discuss the effect of data reuse, label transformation. The paper presently only discusses the limitation of some SQ algorithms such as the one in Damian et al. (2024) under adversarial noise. This alone doesn’t justify the relevance of CSQ lower-bounds under the possibility of label transformation in the adversarial noise case. Missing references of closely related works: - Biroli, Giulio, Chiara Cammarota, and Federico Ricci-Tersenghi. "How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA." Journal of Physics A: Mathematical and Theoretical 53.17 (2020): 174003. - Dandi, Y., Krzakala, F., Loureiro, B., Pesce, L., & Stephan, L. (2023). How two-layer neural networks learn, one (giant) step at a time. arXiv preprint arXiv:2305.18270. - Dandi, Y., Troiani, E., Arnaboldi, L., Pesce, L., Zdeborova, L., & Krzakala, F. The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents. In Forty-first International Conference on Machine Learning.

Questions

* Is the proposed algorithm expected to reach the SQ lower-bounds upon transformation of the labels? * Intuitively, why does unfolding fare better than the partial trace estimator under adversarial noise? * Can the memory and runtime requirements for Algorithm 1 be optimized simlar to the partial trace algorithm (see Remark 4.2 in Damian et al. 2024)? * The discussion in lines 158-161 regarding the Gaussianity of the noise term in prior works isn’t accurate since Damian et al. 2024 also consider arbitrary labels leading to general noise. * Why using the tensor PCA for a star while we know there are more efficient starting point for such problems, e.g. (https://arxiv.org/abs/1708.05932, arXiv:1811.04420,https://arxiv.org/abs/2012.04524) ? * Correction: The references list "G. B. Arous" instead of "G. Ben Arous" (Ben Arous is the surname, not a second name). This should be corrected to accurately reflect the author's name.

Rating

4

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

The work precisely describes the theoretical assumptions. One major limitation of the work is the absence of a discussion of label transformations/batch reuse (see weaknesses above). The work is primarily of a theoretical nature and has no potential negative societal impact.