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

(C11) Our intention was to explan that even when $\mathrm{OPT}$ is very small, i.e, when $\mathrm{OPT}\gtrsim d^{-(k^* - 2)/2}$, we cannot use the partial trace algorithm to find a vector $w^0$ such that the inner product between $w^0$ and $w^*$ is greater than some positive absolute constant. Note that with a random initialization, one easily gets a vector $w^0$ such that $w^0\cdot w^* \approx 1/\sqrt{d}$ with high probability; however, this trivial alignment is not sufficient for our optimization subroutine to work.

(C12) We want to point out that there are no significant eigengaps between the eigenvalue of $w^*$ and the eigenvalues of other eigenvectors that are orthogonal to $w^*$; hence, we cannot pick out the target vector $w^*$ from the eigenvectors of the partial-trace matrix efficiently.

(C14&15) We apologize for the confusion in the prose of lines 587-594. We emphasize that in Appendix B.4 the definition of the signal strength $\tau$ is different from the definition of the signal strength $\beta$ in [RM14]. In particular, since [RM14] takes a normalization step, it holds that $\tau \approx \sqrt{d}\beta$, as remarked in footnote 1 in [HSS15]. Hence, since [RM14] requires $\beta\gtrsim \sqrt{d}$ for tensor-unfolding, it translates to $\tau\gtrsim d$ in our setting. We have added a footnote to remark on the relation between the definition of $\beta$ in [RM14] and the definition of $\tau$ in our setting, and we have modified lines 587-594 to clarify this.

Reference:

[BBHLT21]Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent, Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm COLT 2021

We thank the reviewer for the time and effort in reviewing our paper, as well as the positive evaluation of our work. We respond to the reviewer's comments below.

Response to Questions

Question 1:

(Q1) We agree that care is needed when comparing to [DPVLB24]. As the reviewer remarks, it is unclear whether their preprocessing ideas can be transferred to the agnostic model, for the following reasons.

First, the noise model considered in [DPVLB24] does not cover the agnostic noise setting. In particular, [DPVLB24] requires the label $Y$ to be independent from $w\cdot x$ for any $w\perp w^*$, which excludes even some standard classes of structured semi-random noise such as the Massart noise. Thus, it is unclear whether the SQ lower bound obtained in [DPVLB24] is tight for the agnostic setting.

Second, it is not clear how to apply the label transformation process $T(y) = E[he_{\bar{k^*}}(w^*\cdot x) | Y = y]$ in the agnostic setting. Since the distribution of $Y$ in unknown, we cannot compute this conditional expectation. Further, how to even approximate this function $T(y) = E[he_{\bar{k^*}}(w^*\cdot x) | Y = y]$ is unclear when the labels take real values.

The difficulty of calculating or approximating this conditional expectation in the agnostic setting also poses challenges in transferring this measure of hardness to our setting. In particular, it is not clear how to calculate the generative component $\bar{k^*}$ uniformly over all possible noise distributions.

Finally, we note that other data transform processes also fail in the agnostic setting. For example, the SQ algorithm proposed in [CM20] that applies an implicit data transformation process via a thresholding procedure, provably fails in our setting, as we have remarked in the introduction. That said, we do not claim that further reducing our sample complexity via other more sophisticated techniques is impossible, and we leave it as an interesting future direction.

We further refer to our response to reviewer 9olo, weakness 2 and question 1, for additional comparison with [DPVLB24].

(Q2&Q3) Thank you for pointing this out; we will revise appropriately. We also thank the reviewer for the provided reference, which we will look into for possibly closing the gap mentioned by the reviewer.

Minor comments:

(C1) We thank the reviewer for pointing out the possible ambiguity in the terminology. We chose to be consistent with the terminology used in the existing line of work addressing the same activations, from [CM20] to [DPVLB24]. However, we will add a remark to disambiguate.

(C2) We are interested in efficient algorithms with sample complexity and runtime that are polynomial in both $d$ and $1/\epsilon$, as $\epsilon$ is usually chosen as a small error tolerance. It was showin in [GGK20,DKZ20,DKPZ21] that for any SQ algorithm, agnostically learning ReLU (one of the most basic activations) to error $\mathrm{OPT}+\epsilon$ requires at least $d^{\Omega(\mathrm{poly}(1/\epsilon))}$ queries, which is not polynomial in $1/\epsilon$. Thus, this line of prior work rules out the possibility of having an SQ algorithm that achieves $\mathrm{OPT} +\epsilon$ error with $\mathrm{poly}(d, 1/\epsilon)$ complexity under our setting. Moreover, the same hardness result ($d^{\Omega(\mathrm{poly}(1/\epsilon))}$ complexity lower bound) holds for low-degree polynomial tests (using the near-equivalence between SQ and low-degree tests shown in [BBHLT21]) and via reduction-based computational hardness (cryptographic hardness) [DKR23].

(C3) In line 72, we use $\sim$ to denote that the function on both sides is equal in the Hermite orthonormal basis under Gaussian measure. Note that $\sigma(z)$ might not be equal to $\sum_{k\geq 0} c_k he_k(z)$ pointwise due to the Gibbs phenomenon of Fourier expansions. We will clarify.

(C4) Thank you for catching this typo, it should be $|c_{k^*}| = \Omega(1)$, meaning that it is a universal constant, independent of other problem parameters like $d$ and $1/\epsilon$.

(C5) It takes roughly $d^{k^*}$ time to read one $k^*$-Chow tensor, and thus it takes $\tilde{O}(d^{3\lceil k^*/2\rceil} + d^{k^*}/\epsilon)$ time to read all $k^*$-Chow tensors required for estimating the unfolding matrix. Since we only need to estimate the top singular vector to constant error, this can be done with a standard matrix SVD algorithm (like power iteration) in time no higher than reading the aforementioned tensors, up to constants. The optimization subroutine takes time $O(nT) = O(d\log(1/\epsilon))$. Thus, in summary, the total runtime of our algorithm would be $\tilde{O}(d^{3\lceil k^*/2\rceil} + d^{k^*}/\epsilon)$.

(C6) If one is interested in error $\mathrm{OPT} +\epsilon$, such SQ lower bounds are known (as explained above). As elaborated in our response to reviewer 9olo, the SQ complexity of agnostically learning SIMs to error $O(\mathrm{OPT}) +\epsilon$ is not well-understood. Specifically, it is unclear if the SQ complexity is the same or significantly higher than that of the realizable setting. Fully characterizing the SQ complexity of the agnostic problem remains an interesting open problem. The main point is that our algorithm is the best known algorithm for this problem to date and almost matches the lower bound for a natural restricted class of algorithms (CSQ algorithms).

(C9&10) In line 223, $l$ is defined as $\lfloor k/2 \rfloor$; in line 2 of algorithm 2, the initialization subroutine is the tensor PCA algorithm, i.e., algorithm 1 –– we will clarify this in the description of algorithm 2.

We thank the reviewer for the time and effort in reviewing our paper and the positive assessment. Below, we provide specific responses to the points and questions raised by the reviewer.

(Question 1): Can such a measure be defined in your setting, instead of considering the worst-case scenario on (x,y)?

The prior work [DPVLB24] considered the generative exponent $\bar{k}^*$ of the label $y$, which is defined as the first non-zero term $E_y[(E_x[he_k(w^*\cdot x)|y])^2]$. It is not clear how to leverage such a measure for the agnostic setting for a number of reasons, including the fact that the "noise" in our setting is unknown to the algorithm and that the labels may take real values (in which case it is unclear how to estimate the conditional expectation stated above).

(Question 2): a mismatch between 𝜎 and the ``true'' link function can lead to a value of 𝑂𝑃𝑇 of order Ω(1), but some algorithms manage to achieve almost perfect alignment with the vector $w^*$. In your case, a large value of 𝑂𝑃𝑇 yields vacuous bounds on both the performance of your algorithm and its alignment with $w^*$; is there an explanation of this phenomenon ?

This is indeed the case and it is a consequence of the agnostic model. Specifically, in the presence of agnostic noise, it is not possible to achieve perfect recovery for the target vector $w^*$ (i.e., find a $w$ such that $w\cdot w^*\geq 1 - \epsilon$ for any desired accuracy $\epsilon>0$) -- even information-theoretically. Specifically, one can construct examples where two different weight vectors both achieve the optimal error while being far from each other. This is a fairly standard fact in agnostic learning and holds even for simple activations like ReLU. In the realizable setting, the reason that one can recover the target vector $w^*$ almost perfectly is that the distribution of the label $y$ is known, and hence it is possible to manipulate the labels to gain more information about $w^*$.

(Minor Remark 1) the vector $w^*$ is never rigorously defined

We thank the reviewer for pointing this out. We clarify that $w^*\in\mathrm{argmin}_{w\in\mathbb{S}^{d-1}} \mathcal{L}_2^{\sigma}(w)$; i.e., $w^*$ is defined as a vector that achieves the minimum $L_2^2$ loss. We have added this definition to the main body.

(Minor Remark 2) My best guess is that the results hold uniformly over a class of link functions where $c_{k^*}$ is bounded from below, and $C_{k^*}$ and $B_4$ from above

The reviewer’s understanding of assumption 1 is correct. We further clarify that the activation $\sigma$ is fixed, but it needs to satisfy assumption 1 so that our algorithm achieves $C\cdot \mathrm{OPT}+\epsilon$ error, where $C$ is an absolute constant, using the sample complexity and runtime as claimed in Theorem 1.2. The constant $C$ in the error depends on the parameter $C_{k^*}$, therefore, if $C_{k^*}$ is not an absolute constant, then our algorithm does not achieve constant factor approximate error. The parameters $c_{k^*}$ and $B_4$ appear in the sample complexity. This implies that if $c_{k^*}$ and $B_4$ are not independent of $d$, the sample complexity and runtime might not be of order $O(d^{\lceil k^*/2 \rceil} + d/\epsilon)$.

(Minor Remark 3): You mention in the introduction that achieving 𝑂𝑃𝑇+𝜖 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.

Thank you for the suggestion; we'll incorporate it.

First, we note (as stated in the paper) that there exist both SQ lower bounds and reduction-based hardness results implying that achieving error $\mathrm{OPT}+\epsilon$ requires $d^{\mathrm{poly}(1/\epsilon)}$ time, even for a ReLU activation. To see why a constant factor approximation is inherent in our algorithmic approach, we refer to the Technical Overview section (lines 176-185). The main technical reason is that the sharpness structural does not hold on the whole sphere –– it is only valid on the sphere excluding a spherical cap centered at the target vector $w^*$. Specifically, by Lemma 3.3, we have sharpness on the subset $\mathbb{S}^{d-1} \setminus \mathcal{S}$, where $\mathcal{S} = \lbrace w: || w || = 1, \sin(\angle(w, w^*)) \leq 4e\sqrt{\mathrm{OPT}} \rbrace$. This restriction of sharpness is due to the strong agnostic noise. Since every point in the spherical cap $\mathcal{S}$ is a $O(C_{k^*}\mathrm{OPT})+\epsilon$ accurate solution (Claim E.7), we can terminate the algorithm after entering this spherical cap if we are only looking for constant factor approximate solutions. However, since sharpness no longer holds once the algorithm’s iterates enter this spherical cap $\mathcal{S}$, we lose the information about the direction in which we should update $w$; hence, we cannot continue decreasing the error to $\mathrm{OPT} + \epsilon$.

General Response to Reviewer 9oLo

We thank the reviewer for the provided feedback. Before responding to specific questions and comments, we address two main points, which we believe are the main sources of the reviewer's somewhat negative view of our work. We hope that upon clarifying the context, the reviewer would consider reevaluating our work.

First, our work is motivated by the line of work on agnostic learning of single-index models under structured marginal distributions and broad classes of activations, as discussed in the top-level response. Agnostic learning, introduced in [Hau92, KSS94], is a well-established model meant to capture realistic learning settings, where we do not assume that the labels perfectly follow a model from the class (where "perfect" also accounts for, e.g., zero-mean noise), and the goal is to be competitive with the best-fit model from the class. The line of work on agnostic learning has a long history in the learning community, with papers regularly published at top ML theory venues such as COLT, NeurIPS, and ICML over the past three decades.

The aforementioned line of work on agnostically learning SIMs (see the top-level response) elaborates on the difficulties of polynomial sample and time learning, and develops the first efficient and constant-factor agnostic algorithms for monotone activations. While these algorithms rely on first-order methods, they do not rely on “vanilla SGD on the square loss” and their analyses are fairly sophisticated.

Second, it is important to note here that our focus was not on the CSQ model itself or on the optimality of our sample complexity for all SQ algorithms. It is a plausible conjecture that the sample complexity of our algorithm can be improved (by an appropriate label transformation preprocessing or some other method) and this remains an interesting open question for future work. As we explain below, the applicability of existing such approaches is unclear. Importantly, our main result is the first constant-factor agnostic learner with polynomial sample and time complexity addressing the broad class of activations defined via Hermite polynomials. It is also the most sample and computationally efficient algorithm for this task known to date — not only within the class of first order/SGD-type algorithms, but in general.

Below we address specific comments and questions raised by the reviewer.

Weakness 1

We respectfully disagree with the reviewer’s points. As is explained in the submission and we reiterate below, there is a vast difference between the realizable/random noise setting and the challenging agnostic setting that we study (both in terms of algorithms and analysis).

Conceptually, it is important to recall that our goal is to obtain error $O(\mathrm{OPT})+\epsilon$, which is the best possible error achievable in polynomial time (please see our general response). None of the aforementioned works achieves such a guarantee, even for very special cases, e.g., for a ReLU activation. (That is, the algorithms themselves in these prior works do not suffice; not merely the analyses.)

At the technical-level, our approach also differs significantly from these prior works. Specifically, our algorithm has two main components: an initialization subroutine and an optimization algorithm. Both are new and require novel analysis. To obtain a non-trivial weak recovery in the initialization step, we carried out a fine-grained analysis of a $k$-tensor-PCA algorithm in the presence of agnostic noise. The optimization algorithm is different from these prior works as well and its analysis hinges upon a critical structural result for the $L_2^2$ loss, which we term ‘(alignment) sharpness’ (Lemma 3.3). In more detail, we show that the Riemannian gradient $\mathbf{g}$ of the $L_2^2$ loss of the truncated activation contains a strong signal in the direction of $w^*$: $\mathbf{g} \cdot w^* \leq -\mu\sin^2(\theta)$, where $\mu$ is an absolute constant. Intuitively, this structural result conveys that the gradient vector $\mathbf{g}$ can pull the algorithm iterates towards $O(\mathrm{OPT})+\epsilon$ solutions. None of the prior works listed by the reviewer established such a structural result, which is key to obtaining a constant factor approximation. We refer to Section 1.2 (Technical Overview, line 176-192) for a more detailed discussion.

It is unclear whether the setup of adversarial noise is relevant for gradient based training in machine learning models [...]

As noted in our general response, the agnostic model is fundamental in learning theory and has been extensively studied in the context of learning SIMs with monotone activations. From a practical perspective, the realizable or random label noise settings are often unrealistic, as they posit the existence of a model that perfectly fits the data (possibly on average).

Weakness 2

As noted in our general response, the focus of our work is not on the CSQ vs SQ distinction. We provide the first polynomial-time algorithm for our problem that achieves near-optimal error of $O(\mathrm{OPT})+\epsilon$; a goal not achieved by these prior works (with any polynomial sample complexity). Importantly, when one talks about "SQ complexity" in the agnostic model, the accuracy achieved by the algorithm is critical. Please see below as a response to the reviewer's relevant question.

Response to Questions

(Q1) It is important to note that the SQ complexity of the learning problem in the agnostic setting is not necessarily the same as the SQ complexity in the realizable or random noise cases. Specifically, the SQ complexity in the agnostic setting depends on the desired accuracy. For example, for accuracy $\mathrm{OPT}+\epsilon$, the SQ complexity of agnostically learning a ReLU (corresponding to $k^{\ast}=1$) under Gaussian marginals is known to be $d^{\mathrm{poly}(1/\epsilon)}$ -- i.e., exponential in $1/\epsilon$ [GGK20,DKZ20,DKPZ21]. In contrast, in the realizable/random noise setting, the SQ complexity is $\mathrm{poly}(d/\epsilon)$, as long as $k^{\ast}$ is bounded by an absolute constant. While an SQ lower bound for the realizable setting also applies to the agnostic setting, it is unclear if a matching SQ upper bound exists. In particular, it remains an open problem what the SQ complexity of our agnostic problem is for error $O(\mathrm{OPT})+\epsilon$.

At a more technical level, it is not clear whether the approaches of [DPVLB24, DTA+24] can be leveraged in the agnostic setting to achieve a constant factor approximation. Regarding [DPVLB24], as explained in our submission, Section B.3 line 536-547, the generative exponent defined there is specific to the joint distribution $P(x,y)$ (in their notation), where the labels $y$ are corrupted by structured and known noise and this is significantly weaker than the agnostic model. Notably, they require the noise $\xi$ to be independent of $w\cdot x$ for any $w \perp w^*,$ which excludes even, for instance, Massart noise. Regarding the result in [DTA+24], it is unclear that it suffices even for weak recovery under the agnostic setting. The reason is that, as shown in [LOSW24], the sample-reuse method implements monomial transformation on the labels $y$, but in the agnostic setting the labels are not guaranteed to have bounded higher moments.

(Q2) At a high level, applying the partial trace operator to a tensor can be viewed as smoothing the tensor PCA objective (see [ADGM17]). While in the realizable setting, smoothing the objective helps the optimization algorithm escape the local minima near the equator, in the agnostic setting, smoothing the landscape could also bury the signal that is already very weak. In particular, the partial trace operator sums up many entries of the noise tensor. Due to the agnostic nature of the noise, this unfortunately further corrupts the labels and makes it harder to discover the signal of the target vector $w^*$ from the tensor.

(Q3) We think this might be possible using the special structure of the Hermite tensors. However, this is beyond the scope of our work, and we leave it as a future direction.

(Q4) First, the label noise handled by Damian et al. 2024 is not arbitrary; please see the second paragraph in our response to the first question.

Additionally, we would like to clarify that here we are referring to the traditional tensor PCA methods (provided in [RM14]), which rely on the Gaussianity of the noise tensor. We emphasize that the analysis and guarantees of traditional tensor PCA methods, like the tensor unfolding or partial trace, cannot be directly applied to our setting, and a fine-grained analysis is required. To avoid confusion, we have modified the phrasing in line 158-161.

(Q5) We respectfully disagree with the reviewer’s comment. First, we are not sure what ‘such problems’ in the reviewer’s question refers to. The articles the reviewer listed provide matrix spectrum methods for phase retrieval problems, which address one specific link function with information exponent $k^* = 2$. In our work, we require algorithms that can weakly recover the signal for much more general link functions with any constant information exponent $k^*$ from a high dimensional tensor. Furthermore, the methods the reviewer points to are not qualitatively more efficient compared to our initialization method. Specifically, they require $n\propto d$ samples asymptotically. This is the same as the sample complexity of our initialization algorithm, which requires $n = O(d)$ samples non-asymptotically for phase retrieval problems, as $k^* = 2$ in this case. In fact, when $k^* =2$, our initialization algorithm is simply a Chow-matrix PCA algorithm that can be carried out efficiently using power iteration.

References:

[DTA+24] Y. Dandi, E. Troiani, L. Arnaboldi, L. Pesce, L. Zdeborova, and F. Krzakala. 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, 2024.

[LOSW24] J. D. Lee, K. Oko, T.i Suzuki, D. Wu. Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit. https://arxiv.org/abs/2406.01581.