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

Authors: puqian  wang
nikos  zarifis
ilias  diakonikolas
jelena  diakonikolas
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:57:35

Abstract: A single-index model (SIM) is a function of the form $\sigma(\mathbf{w}^{\ast} \cdot \mathbf{x})$, where
$\sigma: \mathbb{R} \to \mathbb{R}$ is a known link function and $\mathbf{w}^{\ast}$ is a hidden unit vector. 
We study the task of learning SIMs in the agnostic (a.k.a. adversarial label noise) model 
with respect to the $L^2_2$-loss under the Gaussian distribution. 
Our main result is a sample and computationally efficient agnostic proper learner 
that attains $L^2_2$-error of $O(\mathrm{OPT})+\epsilon$, where $\mathrm{OPT}$ is the optimal loss. The sample complexity of our algorithm is 
$\tilde{O}(d^{\lceil k^{\ast}/2\rceil}+d/\epsilon)$, where 
$k^{\ast}$ is the information-exponent of $\sigma$ 
corresponding to the degree of its first non-zero Hermite coefficient. 
This sample bound nearly matches known CSQ lower bounds, even in the realizable setting. 
Prior algorithmic work in this setting had focused 
on learning in the realizable case or in the presence 
of semi-random noise. Prior computationally efficient robust learners required 
significantly stronger assumptions on the link function.

Main paper: 
 introduction: 
 Single-index models (SIMs) [Ich93, HJS01, HMS + 04, DJS08, KS09, KKSK11, DH18, DGK + 20, DKTZ22, WZDD23, DNGL23] are a classical supervised learning model characterized by hidden low-dimensional structure. The term SIM refers to any function f of the form f (x) = σ(w • x), where σ : R → R is the link (or activation) function and w ∈ R d is the hidden vector. In most settings of interest, the link function is assumed to satisfy certain regularity properties. Indeed, for an arbitrary function, learnability is information-theoretically impossible.The efficient learnability of SIMs has been the focus of extensive investigation for several decades. For example, the special case where σ is the sign function corresponds to Linear Threshold Functions whose study goes back to the Perceptron algorithm [Ros58] . Classical early works [KS09, KKSK11] studied the efficient learnability of SIMs for monotone and Lipschitz link functions. They showed that a gradient method efficiently learns SIMs for any distribution on the unit ball. More recently, there has been a resurgence of research on the topic with a focus on first-order methods. Indeed, the non-convex optimization landscape of SIMs exhibits rich structure and has become a useful testbed for the analysis of such methods. [Sol17] showed that SGD efficiently learns SIMs for the case that σ is the ReLU activation and the distribution is Gaussian. [CLS15, CCFM19, SQW18] showed that gradient descent succeeds for the phase retrieval problem, corresponding to σ(t) = t 2 or σ(t) = |t|.More recently, a line of work [DH18, BAGJ21, DNGL23, DPVLB24] studied the efficient learnability of SIMs going significantly beyond the monotonicity assumption. Specifically, [BAGJ21, DNGL23] developed efficient gradient-based SIM learners for a general class of -not necessarily monotone -link functions under the Gaussian distribution. Roughly speaking, these works show that the complexity of learning SIMs is intimately related to the Hermite structure of the link function (roughly, the smallest degree non-zero Hermite coefficient). The results of the current paper are most closely related to the aforementioned works.All the aforementioned algorithmic results succeed in the realizable model (i.e., with clean labels) or in a few cases in the presence of random label noise. The focus of this work is on learning SIMs in the challenging agnostic (or adversarial label noise) model [Hau92, KSS94] . In the agnostic model, no assumptions are made on the observed labels and the goal is to compute a hypothesis that is competitive with the best-fit function in the class. The algorithmic study of agnostically learning SIMs is not new. A recent line of work [DGK + 20, DKTZ22, ATV23, WZDD23, GGKS23, ZWDD24] has given efficient agnostic SIM learners (typically based on first-order methods) with near-optimal error guarantees under natural distributional assumptions. The key difference between prior work and the results of the current paper is in the assumptions on the link function. Specifically, prior robust learners succeed for (a subclass of) monotone and Lipschitz link functions. In contrast, this work develops robust learners in the more general setting of [BAGJ21, DNGL23] .In order to precisely describe our contributions, we require the definition of the agnostic learning problem for Gaussian SIMs. Let D be a distribution of labeled examples (x, y) ∈ R d × R whose x-marginal is the standard Gaussian, and let L σ 2 (w) := E (x,y)∼D [(σ(w • x) -y) 2 ] be the L 2 2 (or squared) loss of the hypothesis h(x) = σ(w • x) with respect to D. Given i.i.d. samples from D, the goal is to compute a hypothesis with squared error competitive with OPT, where OPT is the best attainable L 2 2 -error by any function in the target class. Problem 1.1 (Robustly Learning Gaussian SIMs). Let D be a distribution of labeled examples (x, y) ∈ R d × R whose x-marginal is D x = N (0, I d ) and y is arbitrary. We say that an algorithm is a C-approximate proper SIM learner, for some C ≥ 1, if given ϵ > 0 and i.i.d. samples from D, the algorithm outputs a vector w ∈ S d-1 such that with high probability it holds L σ 2 ( w) ≤ C OPT + ϵ, where OPT := L σ 2 (w * ) and w * ∈ argmin w∈S d-1 L σ 2 (w).First, note that Problem 1.1 does not make realizability assumptions on the distribution D. That is, the labels are allowed to be arbitrary and the goal is to be competitive against the best-fit function in the class. Second, our focus is on obtaining efficient learners that achieve a constant factor approximation to the optimum loss -independent of the dimension d. The reason we require a constant factor approximation, instead of optimal error of OPT + ϵ, is the existence of computational hardness results ruling out this possibility. Specifically, even if the link function is the ReLU, there is strong evidence that any algorithm achieving error OPT + ϵ in the above setting requires d poly(1/ϵ) time [DKZ20, GGK20, DKPZ21, DKR23].Recent work [DGK + 20, DKTZ22, ATV23, WZDD23] gave efficient, constant-factor robust learners, for the special case of Problem 1.1 where the link function lies in a proper subclass of monotone and Lipschitz functions. In this work, we obtain a broad generalization of these results to a much more general class of link functions, defined below.We now proceed to formalize the assumptions on the link function. Let σ : R → R be a realvalued function that admits the Hermite decomposition σ(z) = k≥0 c k he k (z), where c k = E z∼N (0,1) [σ(z)he k (z)] and he k is the normalized probabilist's Hermite polynomial, defined byhe k (z) = (-1) k √ k! exp z 2 2 d k dz k exp - z 2 2 .We make the following assumptions.Assumption 1 (Family of Link Functions). Suppose that σ is normalized, namely E z∼N (0,1) [σ 2 (z)] = k≥0 c 2 k = 1. We assume the following: (i) The first non-zero Hermite coefficient has degree k * and is prominent: c k * is an absolute constant that is bounded away from zero.(ii) The fourth moment of σ(z) is bounded: E z∼N (0,1) [σ 4 (z)] ≤ B 4 < ∞.(iii) The second moment of the derivative of σ(z) is bounded: E z∼N (0,1) [(σ ′ (z)) 2 ] = k≥k * kc 2 k ≤ C k * , where C k * is an absolute constant whenever k * is an absolute constant.The parameter k * is known as the information exponent of σ.The information exponent k * can be viewed as a complexity measure of the link function. Specifically, ReLU activations correspond to k * = 1. The same holds for the class of bounded activations considered in [DKTZ22, WZDD23] . The link functions used in phase retrieval have k * = 2.We note that Assumption 1 is (at least) as general as those used in [BAGJ21, DNGL23] -which focused on the realizable setting. Comparing against previous constant-factor agnostic learners, Assumption 1 strongly subsumes the class of "bounded activations" [DKTZ22, WZDD23] . In particular, it is easy to see that there exist functions satisfying Assumption 1 with constant k * that are far from monotone. See Appendix A for a detailed justification.In prior work, [DNGL23] , building on [BAGJ21] , gave a sample-efficient gradient method for learning SIMs under Assumption 1 in the realizable setting. The sample complexity of their method is Õ(d k * /2 + d/ϵ). This sample upper bound essentially matches known lower bounds in the Correlational Statistical Query (CSQ) model [DLS22, AAM23] . This discussion leads to the following question, which served as the motivation for the current work:Is there an efficient constant-factor agnostic learner for Gaussian SIMs under Assumption 1?As our main contribution, we answer this question in the affirmative. Interestingly, our algorithm also relies on a gradient-method (Riemannian optimization over the sphere) following a non-trivial initialization step. We emphasize that this is the first polynomial-time constant-factor agnostic learner for this task under Assumption 1.Specifically, we establish the following result (see Theorem 3.5 for a more detailed statement).Theorem 1.2 (Main Result, Informal). There exists an algorithm that draws n = Θk * (d ⌈k * /2⌉ + d/ϵ) labeled samples, runs in poly(n, d) time, and outputs a weight vector w ∈ S d-1 that with high probability satisfies L σ 2 ( w) ≤ C OPT + ϵ, where C = O(C k * ).Theorem 1.2 gives the first sample and computationally efficient robust learner for Gaussian SIMs under Assumption 1. This generalizes the algorithm of [DNGL23] to the agnostic setting and nearly matches the aforementioned CSQ lower bounds (our algorithm fits the CSQ framework). It is worth pointing out that, while more efficient (non-CSQ) algorithms have been developed for the realizable case [CM20] , these algorithms provably fail in the agnostic regime. Finally, we remark that very recent work [DPVLB24] developed an efficient SIM learner and a nearly matching SQ lower bound in a model that allows for some forms of label noise. Importantly, their model does not capture the adversarial label noise studied here. More specifically, the algorithms developed in this prior work [DNGL23, DPVLB24] fail in the agnostic setting. See Appendix B for a detailed discussion.For n ∈ Z + , let [n] := {1, . . . , n}. We use lowercase bold characters to denote vectors and uppercase bold characters for matrices and tensors. For x ∈ R d and i ∈ [d], x i denotes the i-th coordinate of x, and ∥x∥ 2 := ( d i=1 x 2 i ) 1/2 denotes the ℓ 2 -norm of x. We use x • y for the inner product of x, y ∈ R d and θ(x, y) for the angle between x, y. We slightly abuse notation and denote by e i the i th standard basis vector in R d . We use 1{E} to denote the indicator of a statement E. We use N d to denote the d-dimensional standard Gaussian distribution, i.e., N d = N (0, I). We use B d to denote the centered unit ball in R d and denote the unit sphere in R d by S d-1 . We use proj B d (•) to denote the projection operator that projects a vector to the unit ball.Given M ∈ R d1×d2 and a left singular vector v ∈ R d1 of M, we denote the corresponding singular value of v by ρ(v). In addition, we use ρ 1 ≥ ρ 2 ≥ • • • ≥ ρ min{d1,d2} to denote the singular values of a matrix M ∈ R d1×d2 . We use S k to denote the set of all possible permutations of k distinct objects. Given a unit vector w, we define P w ⊥ := Iww ⊤ to be the projection matrix that maps a vector v to its component that is orthogonal to w, i.e., P w ⊥ v = v ⊥w . Given a vector x ∈ R d , the (normalized) Hermite multivariate tensor is defined by [Rah17] :(He k (x)) i1,...,i k := α 1 ! . . . α d ! k! 1/2 he α1 (x 1 ) . . . he α d (x d ), where α j = k l=1 1{i l = j}, ∀j ∈ [d].We use the standard O(•), Θ(•), Ω(•) asymptotic notation. We use O(•) to omit polylogarithmic factors in the argument. We write E ≳ F for two non-negative expressions E and F to denote that there exists some positive universal constant c > 0 such that E ≥ c F .Our technical approach consists of two main parts: (1) new results for tensor PCA, which allow us to obtain an initial parameter vector w 0 that is nontrivially aligned with the target w * and (2) a structural "alignment sharpness" result, which we use to argue that a variant of Riemannian minibatch stochastic gradient descent on a sphere applied to a "truncated square loss" (defined below) converges geometrically fast. In proving these results, we review elementary tensor algebra and basic properties of Hermite polynomials, and prove several structural results for Hermite polynomials that are instructive and may be useful to non-experts entering this area.We now highlight some of the key ideas used in our work.Initialization via Tensor PCA For our optimization algorithm to work, a warm start ensuring nontrivial alignment between the initial vector w 0 and the target vector w * , as measured by w 0 • w * , is essential. In particular, a consequence of our results in Claim 3.1 and Lemma 3.2 is that w 0 • w * = Ω(1) is required to deal with the highly corruptive agnostic noise. Unfortunately, if we were to select w 0 by drawing uniformly random samples from the sphere, exponentially many in d such samples would be needed to ensure that with constant probability at least one of the sampled vectors w 0 is such that w 0 • w * = Ω(1), due to standard results on concentration of measure on the (unit) sphere.Perhaps surprisingly, we prove that the tensor PCA method developed in [RM14] when applied to our problem with O(d ⌈k * /2⌉ ) samples1 ensures that w 0 • w * ≥ 1 -min{1/k * , 1/2}. The reason that this result is surprising is that the method in [RM14] was developed to solve the following problem: given a k-tensor of the form T = τ v ⊗k + A, (PCA-S) where A is a k-tensor with i.i.d. standard Gaussian entries and τ > 0 a "signal strength" parameter, recover the planted (signal) vector v. This 'single-observation' model is equivalent (in law) to the following 'multi-observation' model ( [BAGJ20] ): given n i.i.d. copiesT (i) = τ ′ v ⊗k + A (i) with τ ′ = τ /√ n, recover v using the empirical estimation:T = τ ′ v ⊗k + (1/n) n i=1 A (i) . (PCA-M)In our setting, we wish to recover a vector w * (up to some constant alignment error) for the k-Chowtensor C k = E (x,y)∼D [yHe k (x)],which can be decomposed asEQUATIONThe first term in this decomposition can be viewed as the "signal" k-tensor. The second term represents noise, which, due to y being potentially arbitrary, cannot be assumed to be Gaussian. Thus, previously developed techniques for tensor PCA, which crucially rely on the "Gaussianity" of the noise term, do not apply here.To obtain our result, we first argue that for any k ≥ k * , the top left singular vector v * of the k-Chow tensor C k unfolded into a matrix of roughly equal dimensions carries a "strong signal" about the target vector w * : its associated singular value scales with c k whenever c k = Ω( √ OPT) and it has a nontrivial alignment with the vectorized version of the l-tensor w * ⊗l for l = ⌊k/2⌋ (Lemma 2.2).To prove the desired alignment result using the empirical estimate of the matrix-unfolded k-Chow tensor C k , we rely on the application of a matrix concentration inequality obtained very recently in [BvH22] . This requires a rather technical argument utilizing Gaussian hypercontractivity of multivariate polynomials of bounded degree, which we show characterizes the different "variancelike" quantities associated with the empirical estimate of (the matrix-unfolded) C k , for which we apply the aforementioned matrix concentration (see Lemma 2.4 and its proof).Another intriguing aspect of our initialization result is that it is possible to use it directly to obtain an O( √ OPT + ϵ)-error solution. In particular, in the realizable case studied in [DNGL23] , where OPT = 0, this result directly leads to error O(ϵ) in a sample and computationally efficient manner, with a rather simple algorithm and sample complexity comparable to [DNGL23] .Optimization on a Sphere The second key ingredient in our work is a structural result, stated in Lemma 3.3, which ensures that the gradient field (Riemannian gradient of a truncated loss) guiding the steps of our algorithm (which can be interpreted as a Riemmanian minibatch SGD on a sphere) negatively correlates with w * to a significant extent. This property can be viewed as the considered gradient field, associated with the L 2 2 loss truncated to only contain the first nonzero term in the Hermite expansion of the activation function, containing a strong "signal" that can "pull" the algorithm iterates towards the target O(OPT) + ϵ solutions. We rely on this property to argue that as long as our algorithm (initialized using the tensor PCA method described above) does not have as its iterate a vector with O(OPT) + ϵ loss, the distance between the iterate vector and the target vector must contract. As a consequence, this algorithm converges in O(log(1/ϵ)) iterations. This argument parallels the line of work [MBM18, DGK + 20, WZDD23, ZWDD24] on addressing learning of single-index models by proving structural, optimization-theory local error bounds that bound below the growth of a loss function outside the set of target solutions. Conceptually, the local error bounds from this line of work all have an intuitive interpretation as showing existence of a strong "signal" in the problem that can be used to guide algorithm updates towards target solutions. However, the methodology by which our structural result is obtained is entirely different, as it crucially relies on properties of Hermite polynomials, which were not considered in this past work.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: The abstract summarizes main contribution of our paper provided in Theorem 3.5, that is, we provide the first algorithm for agnostically learning SIMs under a broad class of activations. In the introduction, we summarize the motivation of our work, provide a detailed discussion of our results, and compare our work with prior literature.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
initialization procedure: 
 In this section, we show how to get an initial parameter vector w 0 such that w 0 • w * = 1 -ϵ 0 for some small constant ϵ 0 . The main technique is a tensor PCA algorithm that finds the principal component of a noisy degree-k-Chow tensor for any k ≥ k * , as long as OPT ≲ c 2 k . Such a degree-k Chow tensor is defined by C k = E (x,y)∼D [yHe k (x)], and we denote its noiseless counterpart byC * k = E x∼N d [σ(w * • x)He k (x)] = E x∼N d j≥k * c j ⟨He j (x), w * ⊗j ⟩He k (x) .Furthermore, let us denote the difference between C k and C * k byH k := C k -C * k = E (x,y)∼D [(y -σ(w * • x))He k (x)].Note that since He k (x) is a symmetric tensor for any x, all C k , C * k , and H k are symmetric tensors. We use the following matrix unfolding operator that maps a k-tensor T to a matrix inR d l ×d k-l : 2 Mat (l,k-l) (T) i1+(i2-1)d+•••+(i l -1)d l-1 ,j1+•••+(j k-l -1)d k-l-1 := (T) i1,i2,...,i l ,j1,...,j k-l for all i 1 , . . . , i l , j 1 , . . . , j k-l ∈ [d].We also define the 'vectorize' operator and 'tensorize' operators, which map a vector v ∈ R d l to an l-tensor for any integer l, and vice versa. In detail,Tensor(v) i1,...,i l := v i1+(i2-1)d+•••+(i l -1)d l-1 , ∀i 1 , . . . , i l ∈ [d], Vec(v ⊗l ) i1+(i2-1)d+•••+(i l -1)d l-1 := v i1 v i2 . . . v i l , ∀i 1 , . . . , i l ∈ [d].Finally, given a vector v ∈ R d l , we can also convert this vector to a matrix of size R d×d l-1 :Mat (1,l-1) (v) i,j1,...,j l-1 = v i+(j1-1)d+•••+(j l-1 -1)d l-1 , ∀i, j 1 , . . . , j l-1 ∈ [d].Throughout this section, we take l := ⌊k/2⌋. We leverage the tensor unfolding algorithm proposed in [RM14] , which can succinctly be described as follows. First we unfold the degree-k Chow tensorAlgorithm 1 k-Chow Tensor PCA 1: Input: Parameters ϵ, k, ϵ 0 , c k , B 4 > 0; Sample access to D 2: Let l = ⌊k/2⌋ 3: Draw n = Θ(e k log k (B 4 /ϵ)d k-l /(ϵ 2 0 ) + 1/ϵ) samples {(x (i) , y (i) )} n i=1 from D 4: Construct M := (1/n) n i=1 Mat (l,k-l) (y (i) He k (x (i))); compute its top left singular vector v * 5: Compute the top-left singular vector u of the matrix Mat 1,l-1 ( v * ) 6: Return: u to a matrix in R d l ×d k-l and find its top-left singular vector v ∈ R d l . Then, we calculate the matrix Mat (1,l-1) (v), and output its top left singular vector u.Our main result for initialization is that the output of Algorithm 1 significantly correlates with w * . Proposition 2.1 (Initialization). Suppose Assumption 1 holds. Assume that OPT ≤ c2 k * /(64k * ) 2 , and letϵ 0 = c k * /(256k * ). Then, Algorithm 1 applied to Problem 1.1 with k = k * uses n = Θ((k * ) 2 e k * log k * (B 4 /ϵ)d ⌈k * /2⌉ /(c 2 k * ) + 1/ϵ) samples, runs in polynomial time, and outputs a vectorw 0 ∈ S d-1 such that w 0 • w * ≥ 1 -min{1/k * , 1/2}.We remark here that Algorithm 1 can also be used to find an approximate solution of our agnostic learning problem; however the error dependence on OPT is suboptimal, scaling with its square-root. For full details of this argument, included for completeness, see Proposition D.3 in Appendix D.In the remainder of this section, we sketch the proof of Proposition 2.1, which relies on two main ingredients: (1) alignment of the left singular vectors v of matrix-unfolded k-Chow tensor and the target vector w * , which can be interpreted as the k-Chow tensor containing a strong "signal" about the target vector w * , and (2) matrix concentration for the unfolded tensor, so that we can translate "population" properties of the k-Chow tensor to computable empirical quantities.Signal in the k-Chow Tensor Our first observation is that for any left singular vector v of Mat (l,k-l) (C k ), the singular value ρ(v) is close to the inner product between v and Vec(w * ⊗l ), where l = ⌊k/2⌋. Concretely, we have: Lemma 2.2. Let v be any left singular vector ofMat (l,k-l) (C k ). Then, |ρ(v)-c k (Vec(w * ⊗l )•v)| ≤ √ OPT.Proof Sketch of Lemma 2.2. Recall that the singular value of the left singular vector v satisfiesρ(v) = max r∈R d k-l ,∥r∥2=1 v ⊤ Mat (l,k-l) (C k )r (i) = max r∈R k-l ,∥r∥2=1 ⟨C k , Tensor(v) ⊗ Tensor(r)⟩,where we used Fact C.1(2) in (i).Since C k = C * k + H k , we further have ⟨C k , Tensor(v) ⊗ Tensor(r)⟩ = ⟨C * k , Tensor(v) ⊗ Tensor(r)⟩ + ⟨H k , Tensor(v)⊗ Tensor(r)⟩. We bound both terms above respectively. For the first term, plugging in the definition of C * k and using the orthonormality property of Hermite tensors (Fact C.3) and basic tensor algebraic calculations,EQUATIONNext, for the second term, after applying Cauchy-Schwarz inequality, one can show that it holdsEQUATION)Combining Equation (2) and Equation (3), we get that the singular value of v must satisfyEQUATIONwhere in the equation above, we used the observation that as ∥Vec(w * ⊗k-l )∥ 2 = ∥w * ⊗k-l ∥ F = 1, it holds max r∈R d k-l ,∥r∥2=1 (Vec(w * ⊗k-l ) • r) = ∥Vec(w * ⊗k-l )∥ 2 = 1. Since Equation (3) implies ⟨H k , Tensor(v) ⊗ Tensor(r)⟩ ≥ - √ OPT, similarly we have ρ(v) ≥ c k (Vec(w * ⊗l ) • v) - √ OPT,(l,k-l) (C k ) satisfies v * • Vec(w * ⊗l ) ≥ 1 -(2 √ OPT)/c k .Concentration of the Unfolded Tensor Matrix Let us denoteM (i) = Mat (l,k-l) (y (i) He k (x (i) )), for i ∈ [n] and M = 1 n n i=1 M (i) , which is the empirical approximation of M = Mat (l,k-l) (C k ) = Mat (l,k-l) (E (x,y)∼D [yHe k (x)]). Though we showed in Corollary 2.3 that the top left singular vector v * of the population M strongly correlates with the signal Vec(w * ⊗l ), we only have access to the empirical estimate M and its corresponding top left singular vector v * . Thus, to guarantee that v * correlates significantly with Vec(w * ⊗l ) as well, we need to show that the angle between the v * and v * is sufficiently small as long as we use sufficiently many samples. To this aim, we apply Wedin's theorem (Fact D.6). Wedin's theorem states that sin(θ(v * , v * )) can be bounded above by:sin(θ(v * , v * )) ≤ ∥M -M∥ 2 /(ρ 1 -ρ 2 -∥M -M∥ 2 ),where ρ 1 and ρ 2 are the top 2 singular values of M. We prove in Claim D.7 that ρ 1 -ρ 2 ≥ (c k -8 √ OPT)/2 ≳ c k under the assumption that √ OPT ≲ c k , hence ρ 1 -ρ 2 is bounded below by a constant. Thus, our remaining goal is to bound the operator norm such that ∥M -M∥ 2 ≤ ϵ 0 where ϵ 0 > 0 is a small constant. This can be accomplished by applying a recently obtained matrix concentration inequality from [BvH22, DPVLB24] (stated in Fact D.8), with additional technical arguments. Plugging the lower bound on the singular gap ρ 1 -ρ 2 and the upper bound on the operator norm ∥M -M∥ 2 back into Wedin's theorem (Fact D.6), we obtain the following main technical lemma of this subsection, whose proof can be found in Appendix D: Lemma 2.4 (Sample Complexity for Estimating the Unfolded Tensor Matrix). Let ϵ, ϵ 0 > 0. Consider the unfolded matrix M = Mat (l,k-l) (E (x,y)∼D [yHe k (x)]) and its empirical estimateM := (1/n) n i=1 Mat (l,k-l) (y (i) He k (x (i) )), where {(x (i) , y (i) )} n i=1 are n = Θ(e k log k (B 4 /ϵ)d k/2 /ϵ 2 0 + 1/ϵ) i.i.d. samples from D. Then, with probability at least 1 -exp(-d 1/2 ), ∥ M -M∥ 2 ≤ ϵ 0 .Moreover, if v * is the top left singular vector of M, then with probability at least 1 -exp(-d 1/2 ),v * • Vec(w * ⊗l ) ≥ 1 - 2 c k √ OPT - 2ϵ 0 (c k /2 -4 √ OPT) -ϵ 0 .After getting an approximate top left singular vector v * ∈ R d l of Mat (l,k-l) (E (x,y)∼D [yHe k (x)]), the final piece of the argument is that finding the top left singular vector of the matrix Mat (1,l-1) ( v * ) completes the task of computing a vector u that correlates strongly with w * . Concretely, we have: Lemma 2.5. Suppose that v * • Vec(w * ⊗l ) ≥ 1 -ϵ 1 for some ϵ 1 ∈ (0, 1/16]. Then, the top leftsingular vector u ∈ R of Mat (1,l-1) ( v * ) satisfies u • w * ≥ 1 -2ϵ 1 . Proof of Proposition 2.1 Since √ OPT ≤ c k * /(64k * ) ≤ c k * /64, choosing ϵ 0 = c k * /(256k * ) ≤ c k * /256 in Lemma 2.4, we obtain that using n = Θ((k * ) 2 e k * log k * (B 4 /ϵ)d ⌈k * /2⌉ /(c 2 k * ) + 1/ϵ), it holds with probability at least 1 -exp(-d 1/2 ) that v * • Vec(w * ⊗l ) ≥ 1 - 2 c k √ OPT - 2ϵ 0 (c k /2 -4 √ OPT) -ϵ 0 ≥ 1 - 1 16k * .Then applying Lemma 2.5 with ϵ 1 ≤ 1/(16k * ) ≤ 1/16, we get that the output u of Algorithm 1 satisfies u• w * ≥ 1 -2ϵ 1 ≥ 1 -1/(8k * ) ≥ 1 -min{1/k * , 1/2}, completing the proof.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The limitations of our work are discussed in the introduction, and are clearly stated in the statements of the theorems.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
optimization via riemannian gradient descent: 
 After obtaining w 0 from Algorithm 1, we run Riemannian minibatch SGD Algorithm 2 on the 'truncated loss' (see definition in Equation ( 5)). In the rest of the section, we first present the definition of the truncated L 2 2 loss L ϕ 2 and its Riemannian gradient and then proceed to proving that Algorithm 2 converges to a constant approximate solution in O(log(1/ϵ)) iterations. Due to space constraints, omitted proofs are provided in Appendix E. g(w t ) = 1 n n i=1 k * c k * y (i) (I -w t (w t ) ⊤ )⟨He k * (x (i)), (w t ) ⊗k * -1 ⟩.w t+1 = (w t -η g(w t ))/∥w t -η g(w t )∥ 2 . 7: Return: w T 3.1 Truncated Loss and the Sharpness property of the Riemannian Gradient Instead of directly minimizing the L 2 2 loss L σ 2 , we work with the following truncated loss that drops all the terms higher than k * in the polynomial expansion of σ:EQUATIONSimilarly, the noiseless surrogate loss is defined asEQUATION)It can be shown (using Fact C.1(2)) that the gradient of the truncated L 2 2 loss equals:EQUATIONwhile for the gradient of the noiseless L 2 2 loss we haveEQUATIONRecall that P w ⊥ := Iww ⊤ . Then the Riemannian gradient of the L 2 2 loss L ϕ 2 , denoted by g(w) is g(w)EQUATIONSimilarly, the Riemannian gradient of the noiseless L 2 2 loss L * ϕ 2 is defined by g * (w) :EQUATION)We first show that g * (w) carries information about the alignment between vectors w and w * . Claim 3.1. For any w ∈ S d-1 , we have g* (w) = -2k * c k * (w • w * ) k * -1 (w * ) ⊥w .Let us denote the difference between the noisy and the noiseless Riemannian gradient by ξ(w), i.e., ξ(w) := g(w) -g * (w) = -2 E (x,y)∼D [(y -σ(w * • x))P w ⊥ ∇ϕ(w • x)].We next show that the norm of ξ(w) and the inner product between ξ(w) and w * are both bounded. Lemma 3.2. Let ξ(w) = g(w) -g * (w) as defined above. Then, ∥ξ(w)∥ 2 ≤ 2k * c k * √ OPT and |ξ(w) • w * | ≤ 2k * c k * √ OPT∥(w * ) ⊥w ∥ 2 .We are now ready to present the main structural result of this section. Lemma 3.3 (Sharpness). Assume OPT ≤ c/(4e) 2 for some small absolute constant c < 1. Let w ∈ S d-1 and suppose that w• w * ≥ 1 -1/k * . Let θ := θ(w, w * ). If sin θ ≥ 4e √ OPT, then g(w) • w * ≤ -(1/2)∥g * (w)∥ 2 sin θ.Proof. We start by noticing that by Claim 3.1, the noiseless gradient satisfies the following property:g * (w) • w * = -2k * c k * (w • w * ) k * -1 ∥(w * ) ⊥w ∥ 2 2 = -∥g * (w)∥ 2 sin θ,where we used that since ∥w∥ 2 = ∥w * ∥ 2 = 1, we have ∥(w * ) ⊥w ∥ 2 = sin θ. Furthermore, applying Lemma 3.2 we have the following sharpness property with respect to the L 2 2 loss:g(w) • w * = g * (w) • w * + ξ(w) • w * ≤ -(∥g * (w)∥ 2 -2k * c k * √ OPT) sin θ. (11) Observe that (1 -1/t) t-1 ≥ 1/e for all t ≥ 1. Therefore, when w • w * ≥ 1 -1/k * , we have ∥g * (w)∥ 2 = 2k * c k * (w • w * ) k * -1 sin θ ≥ 2k * c k * (1 -1/k * ) k * -1 sin θ ≥ e -1 k * c k * sin θ.Hence, when sin θ ≥ 4e√ OPT and w • w * ≥ 1 -1/k * , we have ∥g * (w)∥ 2 ≥ 4k * c k * √ OPT. Thus, as long as sin θ ≥ 4e √ OPT, we have that g(w) • w * ≤ -1 2 ∥g * (w)∥ 2 sin θ.Define the empirical estimate of g(w) as g(w) := (1/n) n i=1 k * c k * y (i) P w ⊥ ⟨He k * (x (i) ), w ⊗k * -1 ⟩.The following lemma provides the upper bounds on the number of samples required to approximate the Riemannian gradient g(w) by g(w). Lemma 3.4 (Concentration of Gradients). Let w * , w ∈ S d-1 . Let g(w) be the empirical estimate of the Riemannian gradient. Furthermore, denote the angle between w and w * by θ, and denoteκ = (k * c k * ) 2 e k * log k * (B 4 /ϵ).Then, with probability at least 1 -δ, it holds ∥ g(w) -g(w)∥ 2 ≲ dκ/(nδ), and ( g(w) -g(w)) • w * ≲ κ/(nδ) sin 2 θ.We proceed to the main theorem of this paper. It shows that using at most Θ(d ⌈k * /2⌉ + d/ϵ) samples, Algorithm 2 (with initialization from Algorithm 1) generates a vector w such that L σ 2 ( w) = O(OPT) + ϵ within O(log(1/ϵ)) iterations. Theorem 3.5. Suppose Assumption 1 holds. Choose the batch size of Algorithm 2 to be n = Θ(C k * de k * log k * +1 (B 4 /ϵ)/(ϵδ)), and choose the step size η = 9/(40ek * c k * ). Then, afterT = O(log(C k * /ϵ)) iterations, with probability at least 1 -δ, Algorithm 2 outputs w T with L σ 2 (w T ) = O(C k * OPT) + ϵ. The total sample complexity of Algorithm 2 is N = Θ((k * /c k * ) 2 e k * log k * (B 4 /ϵ)d ⌈k * /2⌉ + (C k * e k * log k * +2 (B 4 /ϵ)) d ϵδ ). Proof Sketch of Theorem 3.5. Suppose first that OPT ≥ (c k * /64k * ) 2 , then by Claim E.7 we know that any unit vector (e.g., w = e 1 ) is a constant approximate solution with L σ 2 ( w) = O(OPT). Now suppose that OPT ≤ (c k * /64k * ) 2 . Consider the distance between w t and w * after each update of Algorithm 2. By the non-expansive property of projection operators, we haveEQUATIONOn the other hand, the squared norm term ∥ g(w t )∥ 2 2 from Equation (12) can be bounded above by∥ g(w t )∥ 2 2 ≤ 2∥ g(w t ) -g(w t )∥ 2 2 + 2∥g(w t )∥ 2 2 ≤ (k * c k * ) 2 (OPT + ϵ) + ∥g * (w)∥ 2 2 .(14) Plugging Equation (13) and Equation ( 14) back into Equation (12), we get that w.p. at least 1 -δ,EQUATIONLet us assume first thatθ t ≤ θ t-1 ≤ • • • ≤ θ 0 and sin θ t ≥ 4e √ OPT + √ ϵ, then we show that it holds θ t+1 ≤ θ t . Recall in Claim 3.1 it was shown that ∥g * (w t )∥ 2 = 2k * c k * (w t • w * ) k * -1 sin θ t . Since w 0 is the initial parameter vector that satisfies w 0 • w * ≥ 1 -1/k * , by the inductive hypothesis it holds w t • w * ≥ 1 -1/k * and hence 1 ≥ (w t • w * ) k * -1 ≥ 1/e. Therefore, we further obtain (2k * c k * /e) sin θ t ≤ ∥g * (w t )∥ 2 ≤ 2k * c k * sin θ t .Therefore, using the inductive assumption that sin θ t ≥ 4e √ OPT + √ ϵ and further noticing that ∥w tw * ∥ 2 = 2 sin(θ t /2), with step size η = 9/(40ek * c k * ) we can further bound ∥w t+1 -w * ∥ 2 2 in Equation (15) as:EQUATION)This shows that θ t+1 ≤ θ t , hence completing the inductive argument. Furthermore, Equation ( 16) implies that after at most T = O(log(1/ϵ)) iterations it must hold that sin θ T ≤ 4e √ OPT + √ ϵ, therefore, we can end the algorithm after at most O(log(1/ϵ)) iterations. Applying Claim E.7 we know that this final vector w T has error boundL σ 2 (w T ) = O(C k * (OPT + ϵ)). Thus, choosing ϵ ′ = C k * ϵ, δ ′ = δT , where T = O(log(C k * /ϵ ′ )), Algorithm 2 outputs a parameter w T such that with probability at least 1 -δ ′ , L σ 2 (w T ) = O(C k * OPT) + ϵ ′ , with batch size n = Θ(d/(ϵ ′ δ ′ )). In summary, the total number of samples required for Algorithm 2 isN = Θ(d ⌈k * /2⌉ + d/(ϵ ′ δ ′ )).Organization The appendix is organized as follows. In Appendix A, we provide a detailed discussion about our assumptions on the activation functions. In Appendix B we compare our results with the most related prior works. In Appendix C, we provide additional preliminaries on basic tensor algebra as well as Hermite polynomials and Hermite tensors. In Appendix D and Appendix E we provide full versions of Section 2 and Section 3 respectively, with omitted lemmas and proofs.Assumption 1(i) appears in the same form in [BAGJ21, DNGL23] . The remaining two assumptions are implied by |σ ′ (z)| ≤ A|z| q + B for constants A, B, q, assumed in these works. In detail, Assumption 1(ii) can be implied from |σ ′ (z)| ≤ A|z| q + B using the Gagliardo-Nirenberg inequality [FFRS21] ; Assumption 1(iii) follows from direct calculations as E z∼N1 [(A|z| q + B) 2 ] is finite. Hence Assumption 1 is no stronger than the assumptions made in prior work, which considered the less challenging realizable and zero-mean label noise settings. Proof. We calculate the Hermite coefficient c 1 of σ:E z∼N1 [σ(z)z] = E z∼N1 [σ(z)z1{z ≥ 0}] + E z∼N1 [σ(z)z1{z ≤ 0}] (i) ≥ E z∼N1 [σ(z)z1{z ≥ 0}] ≥ E z∼N1 [az 2 1{z ∈ [0, R]}] ≳ aR 3 exp(-R 2 ),where in (i) we used the monotonicity property of σ and that σ(0) = 0. Thus we get that all wellbehaved activations as k * = 1. In addition, theE z∼N1 [σ(z) 2 ] ≤ E z∼N1 [b 2 z 2 ] ≤ b 2 ,hence after normalization, we have c 1 ≳ aR 3 exp(-R 2 )/(2b 2 ), which is an absolute constant bounded away from 0. Finally, we haveE z∼N1 [σ(z) 4 ] ≤ 3b 4 and E z∼N1 [(σ ′ (z)) 2 ] ≤ b 2 since σ is b-Lipschitz.Thus, we have that all well-behaved activations satisfy Assumption 1.A long thread of research has been focusing on agnostic learning of single index models, including [FCG20, DGK + 20, DKTZ22, WZDD23, ZWDD24]. A common assumption on the activation function σ used in these works is the so-called "well-behaved" property, namely that σ is nondecreasing, zero at the origin (σ(0) = 0), b-Lipshitz, and σ ′ (z) ≥ a when z ∈ [0, R]. In particular, ReLUs and sigmoids are well-behaved activations. For well-behaved activations, we have shown in Claim A.1 that they have k * = 1 and satisfy Assumption 1. Therefore, we conclude that our assumption Assumption 1 is indeed milder compared to prior works.We also note that Assumption 1 allows for non-monotonic activations as well, for example σ(z) = z 2 and σ(z) = |z| satisfy Assumption 1 with k * = 2.At the level of techniques, the algorithmic approaches in the aforementioned prior works on agnostically learning SIMs [FCG20, DGK + 20, WZDD23] inherently fail in our more general activation setting. The main reason is that the underlying algorithms only exploit the information in the degree 1-Chow parameters. However, under Assumption 1 with k * ≥ 2, the inner product between degree 1-Chow vector and any unit vectorv equals | E (x,y)∼D [yx] • v| ≤ √OPT -which provides no information about the hidden vector w * . That is, in our more general setting, considering Chow vectors of higher degree appears necessary for any optimization method to succeed.On the other hand, we remark that the algorithms in these works succed under more general distributions (including the Gaussian distribution), such as log-concave distributions.The work by [DNGL23] applied a smoothing operator to the L 2 2 loss inspired by [ADGM17] . For any function f : R → R, let the smoothing operator beg λ (f (w • x)) := E µw f w + λz ∥w + λz∥ 2 • x ,where z ∼ µ w is the uniform distribution on the sphere S d-2 that is orthogonal to w, and λ is the 'smoothing strength'. Applying the smoothing operator to the loss we getEQUATIONℓ λ (w; x, y) := 1 -E µw yσ w + λz ∥w + λz∥ 2 • x .The main algorithm of [DNGL23] is an online Riemannian gradient descent algorithm on the smoothed loss L λ (w).The dynamics of the online SGD algorithm in [DNGL23] can be split into three stages: In the first stage, starting from a randomly initialized vector w 0 such that w 0 • w * = Θ(d -1/2 ), the algorithm used a large smoothing operator with λ = d 1/4 . Then, after Õ(d k * /2-1 ) iterations the algorithm converges to a parameter w 1 such that w 1 • w * ≥ d -1/4 . Then, in the second stage, with zerosmoothing λ = 0, they run the algorithm for another Õ(d k * /2-1 ) iterations and get a parameter w 2 such that w 2 • w * ≥ 1 -d -1/4 . In the third stage, online SGD converges to w 3 with w 3 • w * ≥ 1 -ϵ in d/ϵ iterations.However, the smoothing technique does not work in the agnostic setting. The main reason is that the agnostic noise buries the signal of the gradient. To see this, note that in Lemma 11 of [DNGL23] , they showed that g λ (he k (w • x)) = ⟨He k (x), T k (w)⟩, whereT k (w) := 1 (1 + λ 2 ) k/2 ⌊k/2⌋ j=0 k 2j Sym(w ⊗k-2j ⊗ (P ⊗j w ⊥ ))λ 2j ν (d-1) j, and ν(d-1) j = E z∼S d-2 [z 2j 1 ] = Θ((d-1) -j ) = Θ(d -j). Note since the smoothing operator is a linear operator, it holds thatL λ (w) = 1-E (x,y)∼D [yg λ (σ(w•x))] = 1-E (x,y)∼D [y k≥k * c k g λ (he k (w• x))] = 1 -E (x,y)∼D [y k≥k * c k ⟨He k (x), T k (w)⟩]. Let g λ (w) := P w ⊥ ∇L λ (w) denote the Riemannian gradient of L λ (w), we have g λ (w) • w * = -E (x,y)∼D y k≥k * c k ⟨He k (x), ∇T k (w) ⊗ (w * ) ⊥w ⟩ = -E (x,y)∼D σ(w * • x) k≥k * c k ⟨He k (x), ∇T k (w) ⊗ (w * ) ⊥w ⟩ I1 -E (x,y)∼D (y -σ(w * • x)) k≥k * c k ⟨He k (x), ∇T k (w) ⊗ (w * ) ⊥w ⟩ I2 (17)We show that the noise term I 2 kills the signal term I 1 in the beginning stage when w•w * = Θ(1/ √ d) and λ = d 1/4 . Claim B.1. When w • w * = Θ(1/ √ d) and λ = d 1/4 , it holds |I 1 | ≲ d -k * /2 , |I 2 | ≲ √ OPTd -k * /4 .Thus, in order for the signal to overcome the noise, one requires OPT ≲ d -k * /4 , which is too strict to hold in reality.Proof of Claim B.1. Following the steps in Lemma 12 in [DNGL23] , ∇T k (w) ⊗ (w * ) ⊥w equals:∇T k (w) ⊗ (w * ) ⊥w = k (1 + λ 2 ) k/2 ⌊ k-1 2 ⌋ j=0 k -1 2j Sym(w ⊗k-2j-1 ⊗ P ⊗j w ⊥ ) ⊗ (w * ) ⊥w λ 2j ν (d-1) j - λ 2 k(k -1) (d -1)(1 + λ 2 ) k/2 ⌊ k-2 2 ⌋ j=0 k -1 2j Sym(w ⊗k-2j-1 ⊗ P ⊗j w ⊥ ) ⊗ (w * ) ⊥w λ 2j ν (d+1) j .Plugging the equation above back into Equation ( 17), we study each term |I 1 | and |I 2 | respectively in the beginning phase when w• w * = O(d -1/2 ).Using Fact C.3, and recall that in [DNGL23] λ is chosen to be λ = d 1/4 and νEQUATION= Θ(d -j ) by definition, I 1 equals:|I 1 | = k≥k * c 2 k Sym(w * ⊗k ), Sym(∇T k ⊗ (w * ) ⊥w ) ≲ k≥k * c 2 k k (1 + λ 2 ) k/2 ⌊ k-1 2 ⌋ j=0 k -1 2j (w • w * ) k-2j-1 (1 -(w • w * ) 2 ) j ∥(w * ) ⊥w ∥ 2 d j/2 d -j + k≥k * c 2 k λ 2 k(k -1) (d -1)(1 + λ 2 ) k/2 ⌊ k-2 2 ⌋ j=0 k -1 2j (w • w * ) k-2j-1 (1 -(w • w * ) 2 ) j ∥(w * ) ⊥w ∥ 2 d j/2 d -j (i) ≲ k≥k * c 2 k k d k/4 ⌊ k-1 2 ⌋ j=0 k -1 2j d -(k-2j-1)/2 d j/2 d -j + k≥k * c 2 k k(k -1) d k/4+1/2 ⌊ k-2 2 ⌋ j=0 k -1 2j d -(k-2j-1)/2 d j/2 d -j (ii) ≲ k≥k * c 2 k k d k/4 ⌊ k-1 2 ⌋ j=0 2 k d -k/2+1/2 d j/2 + k≥k * c 2 k k(k -1) d k/4+1/2 ⌊ k-2 2 ⌋ j=0 2 k d -k/2+1/2 d j/2 (iii) ≲ k≥k * c 2 k k d k/4 + c 2 k k(k -1) d k/4+1/2 2 k d -k 2 + 1 2 + k 4 ≲ k≥k * (kc k ) 2 2 k d -k/2 ≲ k≥k * 4 k d -k/2 ≲ 4 k * d -k * /2 ,where in (i) we plugged in the value of λ and νEQUATION; in (ii) we plugged in the value of w • w * = 1/ √ d; and in (iii) we used the fact that k j ≤ 2 k . However, the magnitude of the signal from |I 1 | is much smaller compared to the strength of the noise, |I 2 |, as by Cauchy-Schwarz, we have|I 2 | (iv) ≤ E (x,y)∼D [(y -σ(w * • x)) 2 ] E x∼N d k≥k * c k ⟨He k (x), ∇T k (w) ⊗ (w * ) ⊥w ⟩ 2 1 2 ≤ √ OPT k≥k * c 2 k ∥∇T k (w) ⊗ (w * ) ⊥w ∥ 2 F 1 2.Note that in Lemma 12 of [DNGL23] , it was proved that∥∇T k (w) ⊗ (w * ) ⊥w ∥ 2 F ≲ k 2 (1 + λ 2 ) k ⌊ k-1 2 ⌋ j=0 k -1 2j λ 4j ν (d-1) j + λ 4 k 4 d 2 (1 + λ 2 ) k ⌊ k-2 2 ⌋ j=0 k -2 2j λ 4j ν (d+1) j (v) ≲ k 2 2 k d k 2 + k 4 2 k d k 2 +1 ≲ k 4 2 k d -k/2 .where in (v) we plugged in the value of λ and νEQUATION. Thus, it holds that|I 2 | ≲ √ OPT k≥k * c 2 k 4 k d -k 2 1/2 ≲ √ OPT2 k * d -k * /4 .Finally, we remark that the equality holds at (iv) wheny = σ(w * • x) + √ OPT k≥k * c 2 k ∥∇T k (w) ⊗ (w * ) ⊥w ∥ 2 F k≥k * c k ⟨He k (x), ∇T k (w) ⊗ (w * ) ⊥w ⟩ .In [DPVLB24] , the authors studied a milder noise model than the agnostic setting. In their model, the joint distribution on (x, y) is defined asE y [y | x] = σ(w * • x) + ξ(w * • x), where ξ : R → R is assumed to be known to the learner. Note that in this model the labels y are independent of all the directions orthogonal to w * , i.e., the random vector x ⊥ w * is independent of y. In comparison, in the agnostic setting, the distribution of the labels isE y [y | x] = σ(w * • x) + ξ ′ (x), where ξ ′ : R d → R is unknown and can depend arbitrarily on x. In particular, the aforementioned independence with the directions orthogonal to w * does not hold. As a result of their milder noise model, the authors can utilize information on the joint distribution to mitigate the corruption of the noise. This assumption is significantly weaker than agnostic noise.In addition, instead of studying the information component k * defined as the first non-zero Hermite coefficient of the activation σ, [DPVLB24] considered the generative component of the label y, which is defined as k * := min k≥0 {λ k > 0}, whereλ k := E y [ζ 2 k ], and ζ k (y) := E z [he k (z)|y].The main results in [DPVLB24] are twofold. First, they proved an SQ lower bound showing that under the setting aforementioned, any polynomial time SQ algorithm requires at least O(d k * /2 ) samples to learn the hidden direction w * . Then, they provided an SQ algorithm using partial-trace operators that returns a vector w such that ( w• w * ) 2 ≥ 1 -ϵ 2 with O(d k * /2 + d/ϵ 2 ) samples, matching the SQ lower bound.The algorithm proposed in [DPVLB24] can be described in short as follows: given joint distribution P, calculate ζk * (y) and transform the label y to ζk * (y). Then, they applied tensor PCA on ζk * (y)He k (x), using the partial trace operator and tensor power iteration.We note that the partial trace method for tensor PCA fails to find an initialization vector w 0 such that w 0 • w * ≥ c for some positive absolute constant c under agnostic noise. We explain this briefly below. For simplicity, let us consider k being even. Note that for a k-tensor T with even k, the partial trace operator is defined by PT(T) = ⟨T, I ⊗(k-2)/2 ⟩, where I is the identity matrix in R d×d . The idea in [DPVLB24] and [ADGM17] is to use the top eigenvector v 1 ∈ R d of PT(E (x,y)∼D [yHe k (x)]) as a warm-start. However, we show that under agnostic noise, this eigenvector v 1 does not contain a strong enough signal to provide information of w * . Note that by definition of the partial trace operator, for any v ∈ B d we haveEQUATION)The first term in the equality above equalsc k ⟨w * ⊗k , I ⊗(k-2)/2 ⊗ v ⊗2 ⟩ = c k (w * • v) 2, however, the second term can be as large as (by Cauchy-Schwarz):E (x,y)∼D [(y -σ(w * • x))⟨He k (x), I ⊗(k-2)/2 ⊗ v ⊗2 ⟩] (i) ≤ E (x,y)∼D [(y -σ(w * • x)) 2 ] E x∼N d [⟨He k (x), I ⊗(k-2)/2 ⊗ v ⊗2 ⟩ 2 ] ≤ √ OPT∥I ⊗(k-2)/2 ⊗ v ⊗2 ∥ F = √ OPTd (k-2)/4 .As suggested by inequality (i) above, let v be any unit vector orthogonal to w * , consider an agnostic noise modely = σ(w * • x) + ( √ OPT/d (k-2)/4 )⟨He k (x), I ⊗(k-2)/2 ⊗ v ⊗2 ⟩, then E (x,y)∼D [(y -σ(w * • x)) 2 ] = OPT.However, as we can see from Equation (18), it holds that(w * ) ⊤ PT( E (x,y)∼D [yHe k (x)])w * = c k + √ OPT d (k-2)/4 E (x,y)∼D [⟨He k (x), I ⊗(k-2)/2 ⊗ v ⊗2 ⟩⟨He k (x), I ⊗(k-2)/2 ⊗ (w * ) ⊗2 ⟩] = c k + √ OPT d (k-2)/4 ⟨Sym(I ⊗(k-2)/2 ⊗ v ⊗2 ), Sym(I ⊗(k-2)/2 ⊗ (w * ) ⊗2 )⟩ (ii) ≲ c k + √ OPT d (k-2)/4 d (k-4)/2 = c k + √ OPTd k/4-3/2 ,where (ii) comes from the fact that for any permutation π such that {π(1), π(2)} ∩ {1, 2} ̸ = ∅, since v ⊥ w * , it holds i1,...,i k v i1 v i2 w * i π(1) w * i π(2) I i3,i4 . . . I i k-1 ,i k I i π(3) ,i π(4) . . . I i π(k-1) ,i π(k) = 0;and on the other hand, when {π(1), π(2)} ∩ {1, 2} = ∅, then d i1,...,i k =1 v i1 v i2 w * i π(1) w * i π(2) I i3,i4 . . . I i k-1 ,i k I i π(3) ,i π(4) . . . I i π(k-1) ,i π(k) ≤ d (k-4)/2 .To see this, note that there exists a chain of identity matricesI i π(a 1 ) ,i π(a 1 +1) I ij 1 ,ij 1 +1 I i π(a 2 ) ,i π(a 2 +1) I ij 2 ,ij 2 +1 • • • I i π(am) ,i π(am +1) I ij m ,ij m +1 such that π(a 1 ) = 1, π(a 1 + 1) = j 1 , j 1 + 1 = π(a 2 ), π(a 2 + 1) = j 2 . . . until we have i π(am+1) ∈ {i 1 , i 2 } or i jm+1 ∈ {i π(1) , i π(2) }.For the latter case, it implies thatv i1 (w * ) ij m+1 I i π(a 1 ) ,i π(a 1 +1) I ij 1 ,ij 1 +1 I i π(a 2 ) ,i π(a 2 +1) I ij 2 ,ij 2 +1 • • • I ij m ,ij m+1 = d i1 v i1 (w * ) i1 = 0.Therefore, only the first case is interesting. Since π(a 1 ) = 1, and π is a bijection, hence π(a m +1) ̸ = 1 therefore the only possible case would be i π(am+1) = i 2 , then we havev i1 v i π(am +1) I i π(a 1 ) ,i π(a 1 +1) I ij 1 ,ij 1 +1 I i π(a 2 ) ,i π(a 2 +1) I ij 2 ,ij 2 +1 • • • I i π(am) ,i π(am+1) = d i1 v 2 i1 = 1.Continue the discussion for v i2 , w * i π(1) and w * i π(2) , and let {j 5 , j 6 , . . . ,j k-1 , j k } = {i 1 , . . . , i k } - {i 1 , i 2 , i π(1) , i π(2) }, we get that d i1,...,i k =1 v i1 v i2 w * i π(1) w * i π(2) I i3,i4 . . . I i k-1 ,i k I i π(3) ,i π(4) . . . I i π(k-1) ,i π(k) ≤ d j5,...,j k =1 I 2 j5,j6 • • • I 2 j k-1 ,j k = d (k-4)/2 .Similarly, for any unit vector u ⊥ v and u ⊥ w * , it holdsu ⊤ PT( E (x,y)∼D [yHe k (x)])u ≲ √ OPTd k/4-3/2 .But one can also show thatv ⊤ PT( E (x,y)∼D [yHe k (x)])v = √ OPT d (k-2)/4 E (x,y)∼D [⟨He k (x), I ⊗(k-2)/2 ⊗ v ⊗2 ⟩ 2 ] = √ OPT d (k-2)/4 ∥Sym(I ⊗(k-2)/2 ⊗ v ⊗2 )∥ 2 F ≈ √ OPTd k/4-1/2 ;This implies that to guarantee that w * is the unique top eigenvector, it has to be that OPT ≲ c 2 k d -(k-2)/2 . Therefore, the noise term completely buries the signal (w* • v) 2 unless OPT ≲ d -(k-2)/2, which is unrealistic to assume.We summarize some historical bits of Tensor PCA. [RM14] proposed the following 'spiked' tensor PCA problem: given a k-tensor of the form3 T = τ v ⊗k + A, (PCA-S)where A is a k-tensor with i.i.d. standard Gaussian entries, recover the planted vector v. The 'singleobservation' model is equivalent (in law) to the following 'multi-observation' model([BAGJ20]): given n i.i.d. copies T (i) = τ ′ v ⊗k + A (i) with τ ′ = τ / √ n, recover v using the empirical estimation:T = τ ′ v ⊗k + 1 n n i=1 A (i) . (PCA-M)In [RM14] , it has been shown that for model (PCA-S), it is information-theoretically impossible to recover v when τ <(β * k -o d (1))√ d, for some real constant β * k ; however, there also exists a constant β ′ k such that the information-theoretic optimal threshold for τ is τ >(β ′ k + o d (1))√ d (see also [DH21] ). However, there is a huge statistical-computational gap for solving tensor PCA problems and it is conjectured impossible to solve (PCA-S) when τ ≲ d k/4 for k ≥ 3 [RM14, DH21]. For multi-observation model (PCA-M), this thresholds translates to a sample complexity of n ≳ d k/2 when τ ′ = O(1).[RM14] proposed the tensor unfolding algorithm that recovers v in (PCA-S) when τ ≳ d ⌈k/2⌉/2 , i.e., for (PCA-M), the required sample complexity is Ω(d ⌈k/2⌉ ). However, it is conjectured in [RM14] that the tensor unfolding algorithm can actually deal with τ ≳ d k/4 . Note that the unfolding algorithm requires τ ≳ d when k = 3. Many papers are devoted to improving from τ ≳ d to τ ≳ d 3/4 and reducing the runtime and memory cost. To name a few, [HSS15, HSSS16] used Sum-of-Squares algorithms with partial trace operators to achieve the goal within O(d 3 ) runtime; [ADGM17] also used partial trace operators, but instead of using SOS algorithms, they injected noise to smooth the landscape of the loss.Perhaps an interesting aspect of our paper is that the unfolding algorithm can deal with stronger noise (compared to the Gaussian noise A, our noise is very heavy-tailed) and is more robust to the noise, as partial trace operator does not work under our agnostic noise. However, this might be attributed to the special structure of the noisy chow tensor.We review basic definitions and elementary tensor algebra used throughout the paper. For any positive integer k, a k-tensor T is defined as a multilinear real function that maps k vectors to a real number, i.e., T :R d × • • • × R d → R.A k-tensor T can also be viewed as a multidimensional array, where each entry is associated with k indices i 1 , . . . , i k in [d] and equals T i1,...,i k = T(e i1 , . . . , e i k ).Given a vector w ∈ R d , w = (w 1 , . . . , w d ) ⊤ , the k-product-tensor w ⊗k is defined by(w ⊗k ) i1,...,i k := w i1 w i2 • • • w i k , ∀i 1 , . . . , i k ∈ [d].Given a k-tensor T and an l-tensor T ′ (with l ≥ k), the inner product (or contraction) between T and T ′ is defined by (⟨T, T ′ ⟩) i k+1 ,...,i l := d i1,i2,...,i k (T) i1,i2,...,i k (T ′ ) i1,i2,...,i k ,i k+1 ,...,i l . In other words, the inner product of a k-tensor and an l-tensor yields an (l -k)-tensor. When k = l, the inner product between T and T ′ is a real number. In particular, for vectors w, v ∈ R d , and any k ≥ 1,EQUATIONwhere w • v is the standard inner product between vectors.A tensor T is symmetric if (T) ...,i,...,j,... = (T) ...,j,...,i,... . We can symmetrize a k-tensor T by summing up all its copies with permuted indices i 1 , . . . , i k and dividing the sum by k!, which is the total number of permutations. We define the symmetrization operator of a k-tensor T by(Sym(T)) i1,...,i k = 1 k! π∈S k (T) i π(1) ,...,i π(k) .When k = 2, this reduces to the symmetrization of a square matrix:Sym(T) = (1/2)(T + T ⊤ ).Let us provide some useful observations about tensor algebra. Fact C.1. Let w ∈ R d and let T be any k-tensor. Then,(1) The inner product between w ⊗k and Sym(T) is equal to the inner product between w ⊗k and T:EQUATION(2) If T is a symmetric tensor,∇(⟨T, w ⊗k ⟩) = k⟨T, w ⊗k-1 ⟩ (22)Proof. To prove the first statement in Fact C.1, note that direct calculation yields:⟨w ⊗k , Sym(T)⟩ = i1,...,i k w i1 • • • w i k 1 k! π∈S (T) i π(1) ,...,i π(k) = 1 k! π∈S i1,...,i k w i π(1) • • • w i π(k) (T) i π(1) ,...,i π(k) = i1,...,i k w i1 • • • w i k (T) i1,...,i k = ⟨w ⊗k , T⟩.Next for the second statement, let f (w) = ⟨T, w ⊗k ⟩ where T is a k-tensor. Then, the partial derivative of f w.r.t. w j is ∂f (w)∂w j = ∂ ∂w j ⟨T, w ⊗k ⟩ = ∂ ∂w j i1,...,i k (T) i1,...,i k w i1 • • • w i k = i2,...,i k (T) j,i2,...,i k w i2 • • • w i k + i1,i3...,i k (T) i1,j,i3,...,i k w i1 w i3 • • • w i k + • • • + i1,...,i k-1 (T) i1,...,i k-1 ,j w i1 • • • w i k-1 .Thus if T is symmetric, then ∇(⟨T, w ⊗k ⟩) = k⟨T, w ⊗k-1 ⟩.We make use of the normalized probabilist's Hermite polynomial, defined byhe k (z) = (-1) k √ k! exp z 2 2 d k dz k exp - z 2 2 .We will heavily use the following properties of the normalized Hermite polynomials [AS68]: Fact C.2. Hermite polynomials satisfy the following properties:1. (Orthonormality) E z∼N (0,1) [he k (z)he j (z)] = 1{k = j}. 2. (Recurrence) he ′ k (z) = √ k he k-1 (z).Given a vector x ∈ R d , we can then define the (normalized) Hermite multivariate tensor by [Rah17] :(He k (x)) i1,...,i k := α 1 ! . . . α d ! k! 1/2 he α1 (x 1 ) . . . he α d (x d ), where α j = k l=1 1{i l = j}, ∀j ∈ [d].For Hermite tensors, we have the following facts: Fact C.3. Let x be a d-dimensional standard Gaussian random vector.1. For any k-tensor A and j-tensor B,E x∼N d [⟨He k (x), A⟩⟨He j (x), B⟩] = 1{k = j}⟨Sym(A), Sym(B)⟩.2. For any w ∈ R d such that ∥w∥ 2 = 1, he k (w • x) = ⟨He(x), w ⊗k ⟩.We consider the L 2 2 (or square) loss, defined byL σ 2 (w) := E (x,y)∼D [(σ(w • x) -y) 2 ].Let w * ∈ argmin w∈S d-1 L σ 2 (w), and denote the minimum value of the L 2 2 loss by OPT := min w∈S d-1 L σ 2 (w). Furthermore, let us define the "noiseless" L 2 2 loss byEQUATIONWe observe that the L 2 2 loss is determined by the inner product between w and w * , therefore, to obtain error O(OPT) + ϵ, it suffices to minimize the angle between w and w * . Concretely, we have: Claim C.4. Let w ∈ R d be a unit vector. Then, the L 2 2 loss L σ 2 (w) satisfies:L σ 2 (w) ≤ 2OPT + 4 1 - k≥k * c 2 k (w • w * ) k .Proof. Recalling that the activation σ is normalized so thatE x∼N d [σ 2 (w • x)] = E x∼N d [σ 2 (w * • x)] = 1, we can simplify the L 2 2 loss to L σ 2 (w) = 2 1 -E (x,y)∼D [yσ(w • x)] .The noiseless L 2 2 loss admits the following decomposition:EQUATIONwhere in the last equality we used the orthonormality property of Hermite tensors (Fact C.3). Further, using Young's inequality and the definitions of OPT and L * σ 2 (w), we also have L σ 2 (w) ≤ 2OPT + 2L * σ 2 (w), which combined with Equation (24) leads toL σ 2 (w) ≤ 2OPT + 4 1 - k≥k * c 2 k (w • w * ) k .Remark C.5. Equation (24) suggests that even in the realizable case, some assumption on boundedness of k≥k * kc 2 k (see Assumption 1(iii)) may be necessary to have a nontrivial bound on the L 2 2 loss. Consider an algorithm that outputs a vector w such that w • w * = 1 -α for some α ∈ (0, 1) (if α = 0, w = w * since both vectors are on the unit sphere). Since k≥k * c 2 k = 1, we can also writeL * σ 2 (w) = 2 k≥k * c 2 k (1 -(1 -α) k ). For k = Ω(1/α), 1 -(1 -α) k ≈ kα.Thus, if we want an algorithm that works generically for any target accuracy, k≥k * kc 2 k ought to be bounded. Remark C.6. Even though for ∥w∥ 2 = 1 we have he k (w • x) = ⟨He k (x), w ⊗k ⟩, the gradients with respect to w of these two functions are different in general. For example, for k = 2, we have⟨He 2 (x), w ⊗2 ⟩ = (1/ √ 2)((w • x) 2 -∥w∥ 2 2 ) and he 2 (w • x) = (1/ √ 2)((w • x) 2 -1),which are equal in function value, but∇⟨He 2 (x), w ⊗2 ⟩ = √ 2((w • x)x -w) = 2⟨He 2 (x), w⟩, ∇he 2 (x) = √ 2(w • x)x = √ 2he 1 (w • x)x,are different. In particular, for the derivative of the left-hand side of Equation (24) to be equal to the derivative of its right-hand side, we need to use the tensor form of Hermite polynomials, because to ensure interchangeability of differentiation and summation, the sequence needs to be uniformly convergent. Note thatE x∼N d [ k≥k * c k ⟨He k (x), w ⊗k ⟩ k ′ ≥k * c k ′ ⟨He k ′ (x), w * ⊗k ′ ⟩] converges to k≥k * c 2 k (w • w) k uniformly for all w ∈ R d , but the sequence E x∼N d [ k≥k * c k he k (w • x) k ′ ≥k * c k ′ he k ′ (w * • x)] converges to k c 2 k (w • w) k only when ∥w∥ 2 = 1, since it requires w • x ∼ N (0, 1) to ensure that E x∼N d [he k (w • x)he j (w * • x)] = 1{k = j}(w • w * ) k .As observed in Remark C.6, the gradients of he k (w • x) and ⟨He k (x), w ⊗k ⟩ are different in general. Throughout the paper, we will be taking the gradient with respect to the tensor form of σ(w • x); in other words, ∇σ(w • x) = ∇( k≥k * c k ⟨He k (x), w ⊗k ⟩).In this section, we show how to get an initial parameter vector w 0 such that w 0 • w * = 1 -ϵ 0 for some small constant ϵ 0 . The main technique is a tensor PCA algorithm that finds the principal component of a noisy degree-k-Chow tensor for any k ≥ k * , as long as OPT ≲ c 2 k . Such a degree-k Chow tensor is defined by C k = E (x,y)∼D [yHe k (x)], and we denote its noiseless counterpart byC * k = E x∼N d [σ(w * • x)He k (x)] = E x∼N d j≥k * c j ⟨He j (x), w * ⊗j ⟩He k (x) .Furthermore, let us denote the difference between C k and C * k byH k := C k -C * k = E (x,y)∼D [(y -σ(w * • x))He k (x)].Note that since He k (x) is a symmetric tensor for any x, all C k , C * k and H k are symmetric tensors. We use the following matrix unfolding operator that maps a k-tensor to a matrix in R d l ×d k-l . Concretely, given a k-tensor T, we define:Mat (l,k-l) (T) i1+(i2-1)d+•••+(i l -1)d l-1 ,j1+•••+(j k-l -1)d k-l-1 := (T) i1,i2,...,i l ,j1,...,j k-l for all i 1 , . . . , i l , j 1 , . . . , j k-l ∈ [d].For notational convenience, we also define the 'vectorize' operator and 'tensorize' operator, which map a vector v ∈ R d l to an l-tensor for any integer l, and vice versa. In detail,Tensor(v) i1,...,i l := v i1+(i2-1)d+•••+(i l -1)d l-1 , ∀i 1 , . . . , i l ∈ [d];and conversely, we defineVec(v ⊗l ) i1+(i2-1)d+•••+(i l -1)d l-1 := v i1 v i2 . . . v i l , ∀i 1 , . . . , i l ∈ [d].Finally, given a vector v ∈ R d l , we can also convert this vector to a matrix of size R d×d l-1 :Mat (1,l-1) (v) i,j1,...,j l-1 = v i+(j1-1)d+•••+(j l-1 -1)d l-1 , ∀i, j 1 , . . . , j l-1 ∈ [d].Some simple facts on the algebra of the unfolded matrix are in order.Fact D.1. Let T be a symmetric k-tensor, and letEQUATION)EQUATION)EQUATIONProof. First we show that for a symmetric tensor T, the linear transformation Mat (l,k-l) (T)r of vector r ∈ R d k-l is equal to the tensor inner product ⟨T, Tensor(r)⟩. This can be proved by direct calculations that for any i ∈ [d l ]:(Mat (l,k-l) (T)r) i = d (k-l) j=1 Mat (l,k-l) (T) i,j r j = j1,...,j k-l ∈[d] Mat (l,k-l) (T) i,j1+•••+(j k-l -1)d k-l-1 r j1+•••+(j k-l -1)d k-l-1 = j1,...,j k-l ∈[d] (T) i ′ 1 ,...,i ′ l ,j1,...,j k-l Tensor(r) j1,...,j k-l , where i ′ 1 , . . . , i ′ j ∈ [d] satisfies i = i ′ 1 + (i ′ 2 -1)d + • • • + (i ′ l -1)d l-1 .Observe that the summation above further equals(Mat (l,k-l) (T)r) i = i1,...,i l ∈[d] j1,...,j k-l ∈[d](T) i1,...,i l ,j1,...,j k-l Tensor(r) j1,...,j k-l 1{i1 = i ′ 1 } . . . 1{i l = i ′ l } = i1,...,i l ,j1,...,j k-l ∈[d](T) i1,...,i l ,j1,...,j k-l (e i ′ 1 ⊗ . . . ⊗ e i ′ l ⊗ Tensor(r)) i1,...,i l ,j1,...,j k-l = T, e i ′ 1 ⊗ . . . ⊗ e i ′ l ⊗ Tensor(r) .Similarly, for a symmetric tensor T and any vector v ∈ R d l , and any index j ∈ [d k-l ], it holds(Mat (l,k-l) (T) ⊤ v) j = T, Tensor(v) ⊗ e j ′ 1 ⊗ . . . ⊗ e j ′ k-l,where j ′ 1 + • • • + (j ′ k-l -1)d k-l-1 = j.Finally, combining Equation (26) and Equation (25) we get that for anyv ∈ R d l , r ∈ R d k-l , the quadratic form v ⊤ Mat (T)r equals v ⊤ Mat (l,k-l) (T)r = ⟨T, Tensor(v) ⊗ Tensor(r)⟩.Throughout this section, we define l = k/2 when k is even, and l = (k -1)/2 when k is odd. In other words, l = ⌊k/2⌋. We leverage the tensor unfolding algorithm proposed in [RM14] , which can be described in short as follows. First we unfold the degree-k Chow tensor to a matrix in R d l ×d k-l , and find its top-left singular vector v ∈ R d l . Then, we calculate the matrix Mat (1,l-1) (v), and find its top left singular vector u. One can show that this eigenvector u correlates with w * significantly. ∈ S d-1 such that w 0 • w * ≥ 1 - min{1/k * , 1/2}.We remark here that Algorithm 3 can also be used to find an approximate solution of our agnostic learning problem; however the dependence on the value of OPT is suboptimal, scaling with its square-root. In particular, we have the following proposition: Proposition D.3 (Solving the Agnostic Learning Problem Using Tensor PCA). Suppose Assumption 1 holds. Assume that OPT ≤ c 2 k * /(64k * ) 2 and ϵ ≤ 1/64. Let ϵ 0 = c k * ϵ/16. Then, Algorithm 1 applied to Problem 1.1 with k = k * uses n = Θ(e k * log k * (B 4 /ϵ)d ⌈k * /2⌉ /(c 2 k * ϵ 2 ) + 1/ϵ) samples, runs in polynomial time, and outputs a vector w 0 ∈ S d-1 such thatw 0 • w * ≥ 1 - 4 c k * √ OPT -2ϵ/3.Furthermore, the L 2 2 error of w 0 is at mostL σ 2 (w 0 ) = O C k * 1 c k * √ OPT + ϵ .Thus, when OPT = 0 (i.e., in the realizable cases), applying Algorithm 3 with O(d ⌈k * /2⌉ /ϵ 2 ) samples recovers the hidden vector w * .Roadmap To prove Proposition D.2 and Proposition D.3 we need three main ingredients. First, we will show (in Lemma D.4 and its corollary Corollary D.5) that the top-left singular vector v * of the unfolded matrix M := Mat (l,k-l) (E (x,y)∼D [yHe k (x)]) correlates significantly with the vectorized l-product tensor, Vec(w * ⊗l ). This indicates that v * contains rich information about the direction of w * . However, since we only have access M, the empirical estimation of M, we need to ensure that the top-left singular vector of M, denoted by v * , is close to v * . This is proved in Lemma D.13 using sophisticated matrix concentration bounds. In particular, in Equation ( 35) we guarantee that the angle between v * and v * is bounded by O(ϵ 0 /c k ) for any small constant ϵ 0 > 0, provided that we take Θ(d ⌈k/2⌉ /ϵ 2 0 ) samples and assume that OPT ≲ c 2 k . The inner product between v * and Vec(w * ⊗l ) can then be bounded below by 1 -O((√ OPT + ϵ 0 )/c k ).Combining with Corollary D.5, this implies that v * correlates with Vec(w * ⊗l ) significantly. Finally, in Lemma D.17 we show that after unfolding the R d l vector v * to an R d×d l-1 matrix, its top-left singular vector u correlates with w * significantly; it particular, we have w * • u ≳ 1 -cϵ 0 for some absolute constant c > 0. Combining these results and choosing ϵ 0 ≈ c k * /k * , we get Proposition D.2, and choosing ϵ 0 ≈ c k * ϵ yields Proposition D.3.Our first observation is that for any left singular vector v of Mat (l,k-l) (C k ), the singular value ρ(v) is close to the inner product between v and Vec(w * ⊗l ), where l = ⌈k/2⌉. Concretely, we have: Lemma D.4. Let v be any left singular vector of Mat (l,k-l) (C k ). Then,|ρ(v) -c k (Vec(w * ⊗l ) • v)| ≤ √ OPT.Proof. Recall that the singular value of the left singular vector v satisfies ρ(v) = max r∈R d k-l ,∥r∥2=1 v ⊤ Mat (l,k-l) (C k )r (i) = max r∈R k-l ,∥r∥2=1EQUATIONnote that we applied Fact C.3 in equation (i) and Fact C.1(1) in (ii). Next, for the second term, after applying Cauchy-Schwarz inequality, it holds|⟨H k , Tensor(v) ⊗ Tensor(r)⟩| = E (x,y)∼D (y -σ(w * • x))⟨He k (x), Tensor(v) ⊗ Tensor(r)⟩ ≤ E (x,y)∼D [(y -σ(w * • x)) 2 ] E x∼N d He k (x), Tensor(v) ⊗ Tensor(r) 2 = √ OPT∥Sym(Tensor(v) ⊗ Tensor(r))∥ F .Since for any k-tensor A we have ∥Sym(A)∥ F ≤ ∥A∥ F , and in addition, observe that as ∥v∥ 2 = ∥r∥ 2 = 1 it holds∥Tensor(v) ⊗ Tensor(r)∥ 2 F = i1,...,i l i l+1 ,...,i k (Tensor(v)) 2 i1,...,i l (Tensor(r)) 2 i l+1 ,...,i k = d l i=1 d k-l j=1 v 2 i r 2 j = 1,we finally haveEQUATION)Combining Equation (28) and Equation (30), we get that for anyv ∈ R d l , r ∈ R d k-l such that ∥v∥ 2 = ∥r∥ 2 = 1, it holds v ⊤ Mat (l,k-l) (C k )r ≤ c k (Vec(w * ⊗l ) • v)(Vec(w * ⊗k-l ) • r) + √ OPT.Therefore, the singular value of v must satisfyEQUATIONwhere in the equation above, we used the observation that as ∥Vec(w* ⊗k-l )∥ 2 = ∥w * ⊗k-l ∥ F = 1, it holds max r∈R d k-l ,∥r∥2=1 (Vec(w * ⊗k-l ) • r) = ∥Vec(w * ⊗k-l )∥ 2 = 1.Similarly, we have Corollary D.5. The top-left singular vector v * ∈ R d l of the unfolded tensorρ(v) = max r∈R d k-l ,∥r∥2=1 v ⊤ Mat (l,k-l) (C k )r = max r∈R d k-l ,∥r∥2=1 ⟨C k , Tensor(v) ⊗ Tensor(r)⟩ = max r∈R d k-l ,∥r∥2=1 c k (Vec(w * ⊗l ) • v)(Vec(w * ⊗k-l ) • r) + ⟨H k , Tensor(v) ⊗ Tensor(r)⟩ ≥ max r∈R d k-l ,∥r∥2=1 c k (Vec(w * ⊗l ) • v)(Vec(w * ⊗k-l ) • r) - √ OPT = c k (Vec(w * ⊗l ) • v) - √ OPT,Mat (l,k-l) (C k ) has corresponding singular value ρ(v * ) ≥ c k - √ OPT. In addition, it holds that v * • Vec(w * ⊗l ) ≥ 1 -(2 √ OPT)/c k .Proof. Plugging in v = Vec(w * ⊗l ) to Lemma 2.2, we get that ρ(Vec(w * ⊗l )) ≥ c k -√ OPT. Thus, the top singular value must satisfyρ 1 ≥ c k - √ OPT. Recall again that as proved in Lemma 2.2, it holds ρ(v * ) ≤ c k v * • Vec(w * ⊗l ) + √ OPT. Thus, since ρ(Vec(w * ⊗l )) ≥ c k - √ OPT we have v * • Vec(w * ⊗l ) ≥ 1 -(2 √ OPT)/c k .We start with some notations. Let us denoteM (i) = Mat (l,k-l) (y (i) He k (x (i) )) for i ∈ [n] and M = 1 n n i=1 M (i) , which is the empirical approximation of M = Mat (l,k-l) (C k ) = Mat (l,k-l) (E (x,y)∼D [yHe k (x)]). We will use Wedin's theorem to bound the distance between the top left singular vector v * of M and the top singular vector v * of the empirical M. Fact D.6 (Wedin's theorem). Let θ(v * , v * ) be the angle between the top left singular vectors v * ∈ R d l and v * ∈ R d l of M and M respectively. Let ρ 1 and ρ 2 be the first 2 singular values of M. Then, it holds that:sin(θ(v * , v * )) ≤ ∥M -M∥ 2 ρ 1 -ρ 2 -∥M -M∥ 2 .We first observe that M admits a large gap between the first and second singular values. Claim D.7 (Singular Gap of Unfolded Tensor Matrix). Let ρ 1 , ρ 2 be the top two singular values ofM = Mat (l,k-l) (C k ). Then ρ 1 -ρ 2 ≥ (c k -8 √ OPT)/2.Proof. Recall that in Corollary D.5 we showedρ 1 = ρ(v * ) ≥ c k - √ OPT and v * • Vec(w * ⊗l ) ≥ 1 -(2 √ OPT)/c k . Now let v ∈ R d lbe any left singular vector of M that is orthogonal to v * . We can decompose Vec(w * ⊗l ) into Vec(w * ⊗l ) = av * + bv + v ′ where v ′ is orthogonal to both v * and v, anda 2 + b 2 ≤ 1. Then, since Vec(w * ⊗l ) • v * = a ≥ 1 -(2 √ OPT)/c k , we thus have Vec(w * ⊗l ) • v = b ≤ √ 1 -a 2 ≤ 1 -a 2 /2. This implies that ρ 1 -ρ(v) ≥ c k - √ OPT -(c k (Vec(w * ⊗l ) • v) + √ OPT) ≥ c k (1 -b) -2 √ OPT ≥ c k (1 -(1 -a 2 /2)) -2 √ OPT ≥ c k /2 -4 √ OPT,and hence we getρ 1 -ρ 2 ≥ (c k -8 √ OPT)/2, completing the proof of Claim D.7.Thus, our remaining goal is to bound the operator norm of M -M. For this purpose, we use the following matrix concentration inequality from [DPVLB24] (also Theorem 2.7 in [BvH22] ).Fact D.8 (Lemma I.5 [DPVLB24] ). Let Z (i) , i ∈ [n], be independent, mean-zero, self-adjoint matrices. Define:γ 2 := E n i=1 Z (i) 2 2 , γ 2 * := sup ∥v∥2=∥r∥2=1 E n i=1 v ⊤ Z (i) r 2 , R2 := E max i∈[n] ∥Z (i) ∥ 2 2 .Then, for anyEQUATION)However, note that M and M are not symmetric matrices, hence to apply matrix concentration inequalities we will be working on the symmetrization of M and M for simplicity, which we will denote by P and P:P = 1 n n i=1 P (i) = 1 n n i=1 0 M (i) M (i)⊤ 0 = 0 M M ⊤ 0 ; P = 0 M M ⊤ 0 .Before we prove the main theorem of this subsection, we introduce two final pieces of tools that will be used later in the proof. The first one is Gaussian hypercontractivity. Fact D.9 (Gaussian Hypercontractivity). Let f (x) : R d → R be a multivariate polynomial of degree at most k. Let x be a standard Gaussian random variable of R d . Then, for any p ≥ 1 it holds∥f (x)∥ L p ≤ (p -1) k/2 ∥f (x)∥ L 2 .Gaussian hypercontractivity controls the moments of a polynomial f (x). To utilize the bound on these moments, we make use of the following inequality from [DNGL23] . Fact D.10 (Lemma 23 [DNGL23] ). Let A, B be random variables such that ∥B∥ L p ≤ σ B p C for all p ≥ 1 and some positive real numbers σ B , C. Then,E[AB] ≤ E[|A|]σ B (2e) C max 1, 1 C log (E[A 2 ]) 1/2 E[|A|] C .We also make use of the following lemma that bounds the magnitude of label y without loss of generality.Lemma D.11 (Bound on Labels). Let P By (z) : R → R be a function that truncates the value of z to the threshold B y : P By (z) = z1{|z| ≤ B y } + B y 1{|z| ≥ B y }. Assume that Assumption 1 holds. Then choosing B y := 4B 4 /ϵ, it holds thatE (x,y)∼D [(P By (y) -σ(w * • x)) 2 ] ≤ OPT + ϵ.Therefore, it is without loss of generality to assume that |y| ≤ B y .Proof. After truncating the label y, we have E (x,y)∼D [(P t (y) -σ(w * • x)) 2 ] = E (x,y)∼D [(P t (y) -σ(w * • x)) 2 1{σ(w * • x) ≤ t}] + E (x,y)∼D [(P t (y) -σ(w * • x)) 2 1{σ(w * • x) ≥ t}] ≤ E (x,y)∼D [(y -σ(w * • x)) 2 ] + E (x,y)∼D [(P t (y) -σ(w * • x)) 2 1{σ(w * • x) ≥ t}] ≤ OPT + 2 E (x,y)∼D [(t 2 + σ 2 (w * • x))1{σ(w * • x) ≥ t}]. Since E x∼N d [σ 4 (w * •x)] ≤[(P t (y) -σ(w * • x)) 2 ] ≤ OPT + 2B 4 t 2 + 2 E x∼N d [σ 4 (w * • x)] Pr[σ(w * • x) ≥ t] ≤ OPT + 4B 4 t 2 .Thus, choosing t = 4B 4 /ϵ we haveE (x,y)∼D [(P t (y) -σ(w * • x)) 2 ] ≤ OPT + ϵ,indicating that we can assume without loss of generality that |y| ≤ B y := 4B 4 /ϵ, completing the proof of Lemma D.11.After assuming that y is bounded by B y without loss of generality, we can then bound the 2 nd and 4 th moments of y. These bounds on the moments of the label y will be used when we implement Fact D.10 to get finer bounds compared to what we would get from a simple application of Cauchy-Schwarz.In particular, we use Fact D.10 to derive upper bounds on expectations like E (x,y)∼D [y 2 f 2 (x)], where f (x) is a polynomial of x, as we have control on the p th moments of f (x) using Gaussian hypercontractivity Fact D.9. Lemma D.12 (Moments of Labels).If OPT ≤ 1/16, then 1/2 ≤ E y [y 2 ] ≤ 2 and E y [y 4 ] ≤ 8B 4 /ϵ.Proof. We first bound the 2 nd moment of the label y. Note that since σ(w* • x) is normalized such that E x∼N d [(σ(w * • x)) 2 ] = 1, we have E y [y 2 ] = E (x,y)∼D [(y -σ(w * • x) + σ(w * • x)) 2 ] (i) ≤ (1 + 1/a) E (x,y)∼D [(y -σ(w * • x)) 2 ] + (1 + a) E x∼N d [(σ(w * • x)) 2 ].We used Young's inequality in (i). Choosing a = 1/8 and since we assumed OPT ≤ 1/16, it holds E y [y 2 ] ≤ 9/16 + 9/8 ≤ 2. In addition, using Cauchy-Schwarz inequality, we haveE y [y 2 ] = E (x,y)∼D [(y -σ(w * • x) + σ(w * • x)) 2 ] = E (x,y)∼D [(y -σ(w * • x)) 2 ] + E x∼N d [(σ(w * • x)) 2 ] + 2 E (x,y)∼D [(y -σ(w * • x))σ(w * • x)] ≥ 1 -2 E (x,y)∼D [(y -σ(w * • x)) 2 ] E x∼N d [(σ(w * • x)) 2 ] ≥ 1/2.This yields the first statement of the lemma. For the remaining statement, notice that since y ≤ B y , we haveE y [y 4 ] ≤ B 2 y E y [y 2 ] ≤ 2B 2 y = 8B 4 /ϵ.We now proceed to bound the sample complexity of Algorithm 3, the argument for which relies on applying Fact D.8 to Z (i) = 1 n (P (i) -P) and is summarized in the following lemma. Lemma D.13 (Sample Complexity for Estimating the Unfolded Tensor Matrix). Let ϵ, ϵ 0 > 0. Consider the unfolded matrix M = Mat (l,k-l) (E (x,y)∼D [yHe k (x)]) and its empirical estimateM := (1/n) n i=1 Mat (l,k-l) (y (i) He k (x (i) )), where {(x (i) , y (i) )} n i=1 are n = Θ(e k log k (B 4 /ϵ)d k/2 /ϵ 2 0 + 1/ϵ) i.i.d. samples from D. Then, with probability at least 1 -exp(-d 1/2 ), ∥ M -M∥ 2 ≤ ϵ 0 .Moreover, if v * is the top left-singular vector of M, then with probability at least 1 -exp(-d 1/2 ),v * • Vec(w * ⊗l ) ≥ 1 - 2 c k √ OPT - 2ϵ 0 (c k /2 -4 √ OPT) -ϵ 0 .Proof. The proof hinges on applying Fact D.8, for which we need to bound above the parameters γ, γ * , and R defined in the same fact. We do so in three separate claims, as follows.Claim D.14. γ ≲ d (k-l)/2 e k log k/2 (B4/ϵ) √ n = d k-l e k log k (B4/ϵ) n .Proof. By the definition of γ, we have:γ 2 = E 1 n n i=1 P (i) -P 2 2 ≤ 1 n ∥ E[(P (i) -P) 2 ]∥ 2 ≤ 1 n ∥ E[(P (i) ) 2 ]∥ 2 = 1 n max v∈R d l ,r∈R d k-l ∥v∥ 2 2 +∥r∥ 2 2 =1 E[v ⊤ M (i) (M (i) ) ⊤ v + r ⊤ (M (i) ) ⊤ M (i) r], Observe that v ⊤ M (i) (M (i) ) ⊤ v = ∥v ⊤ M (i) ∥ 2 2 = d k-l j=1 (v ⊤ M (i)) 2 j , and notice that by definition M (i) = Mat (l,k-l) (y (i) He k (x (i) )) where y (i) He k (x (i) ) is a symmetric tensor, hence using Equation (26) we getv ⊤ M (i) (M (i) ) ⊤ v = (j1,j2,...,j l-k )∈[d] l-k y (i) He k (x (i) ), Tensor(v) ⊗ e j1 ⊗ . . . ⊗ e j k-l 2 .As (x (i) , y (i) ) are i.i.d. copies of (x, y), using the linearity of expectation, we haveEQUATION)Now given any indices j 1 , . . . , j k-l ∈ [d], observe that f j1,...,j k-l (x) := ⟨He k (x), Tensor(v) ⊗ e j1 ⊗ . . . ⊗ e j k-l ⟩ is a polynomial of x of degree at most k, and note thatEQUATIONF ≤ 1, where the second line is by Fact C.3. Our goal is to apply Fact D.10 with A = y 2 and B = f j1,...,j k-l (x) 2 . To this aim, we need to bound above the L p -norm of f j1,...,j k-l (x) 2 , i.e., E x∼N d [(f j1,...,j k-l (x) 2 ) p ] 1/p , which can be done using Fact D.9:E x∼N d [(f j1,...,j k-l (x) 2 ) p ] 1/(2p) ≤ (2p -1) k/2 E x∼N d [f j1,...,j k-l (x (i) ) 2 ] ≤ (2p) k/2 .This implies that ∥f j1,...,j k-l (x) 2 ∥ L p ≤ 2 k p k . Thus, using Fact D.10 with A = y 2 and B = f j1,...,j k-l (x) 2 , we getE (x,y)∼D y 2 He k (x), Tensor(v) ⊗ e j1 ⊗ . . . ⊗ e j k-l 2 ≤ E y [y 2 ](4e) k 1, 1 k log E y [y 4 ] 1/2 E y [y 2 ] k .Finally, using the bound on the moments of the labels as we proved in Lemma D.12, it holds thatE (x,y)∼D y 2 He k (x), Tensor(v) ⊗ e j1 ⊗ . . . ⊗ e j k-l 2 ≲ e k log k (B 4 /ϵ).Plugging the bound above back into Equation (33), we obtain:E (x,y)∼D [v ⊤ M (i) (M (i) ) ⊤ v] = j1,...,j k-l ∈[d] E (x,y)∼D y 2 He k (x), Tensor(v) ⊗ e j1 ⊗ . . . ⊗ e j k-l 2 ≤ e k d k-l log k (B 4 /ϵ).We now proceed to bound above the second termE[r ⊤ (M (i) ) ⊤ M (i) r].Using Equation (25), similar calculations yield thatE[r ⊤ (M (i) ) ⊤ M (i) r] = E[∥M (i) r∥ 2 2 ] = i1,...,i l E x∼N d (y) 2 He k (x), e i1 ⊗ . . . ⊗ e i l ⊗ Tensor(r) 2 ≤ e k d l log k (B 4 /ϵ) ≤ e k d k-l log k (B 4 /ϵ).Thus, plugging in the value of B y = B 4 /ϵ from Lemma D.11, the variance γ can be bounded byγ ≲ d (k-l)/2 e k log k/2 (B4/ϵ) √ n = d k-l e k log k (B4/ϵ) n .Next, we bound the operator norm γ * from above.Claim D.15. γ * ≲ e k/2 log k/2 (B4/ϵ) √ n.Proof. By the definition of γ * ,γ 2 * = sup ∥ṽ∥2=∥r∥2=1 E 1 n n i=1 ṽ⊤ (P (i) -P)r 2 ≤ sup ∥ṽ∥2=∥r∥2=1 1 n E ṽ⊤ (P (i) -P)r 2 ≤ sup ∥ṽ∥2=∥r∥2=1 1 n E ṽ⊤ P (i) r 2 .Decompose ṽ into ṽ⊤ = [(ṽ (1) ) ⊤ , (ṽ (2) ) ⊤ ], where ṽ(1) ∈ R d l and ṽ(2) ∈ R d k-l. Similarly, we can decompose r into r⊤ = [(r (1) ) ⊤ , (r (2) ) ⊤ ] with the same structure. Then, ṽ⊤ P (i) r = y (i) (ṽ (1)⊤ M (i) r(2) + r(1)⊤ M (i) ṽ(2) ). Thus, as (x (i) , y (i) ) are i.i.d. samples, we can further bound γ 2 * byγ 2 * ≲ sup v∈R d l ,∥v∥2=1 r∈R d k-l ,∥r∥2=1 1 n E (x,y)∼D y 2 (v ⊤ Mat (l,k-l) (He k (x))r) 2 = 1 n sup v∈R d l ,∥v∥2=1 r∈R d k-l ,∥r∥2=1 E (x,y)∼D y 2 He k (x), Tensor(v) ⊗ Tensor(r) 2 ,where in the last equality we used Equation (27).2 = ∥v∥ 2 = 1, define f (v,u) (x) := He k (x), Tensor(v) ⊗ Tensor(r) , where v ∈ R d l , r ∈ R d k-l, and f (v,u) is a polynomial of (x 1 , . . . , x d ) of degree at most k. Note that the polynomialf (v,u) (x) satisfies f (v,u) (x) ≥ 0 and E x∼N d [(f (v,u) (x)) 2 ] = ∥Tensor(v) ⊗ Tensor(r)∥ 2 F = 1.Similarly to the upper bound on γ, we apply Fact D.10 with A being y 2 and B being f (v,u) (x) 2 , which yields that for any ∥v∥ 2 = 1, ∥u∥ 2 = 1,E (x,y)∼D y 2 He k (x), Tensor(v) ⊗ Tensor(r) 2 ≤ e k log k (B 4 /ϵ).Thus, plugging this inequality back into the upper bound on γ * above, we obtainγ 2 * ≲ e k log k (B 4 /ϵ) n .Taking the square root on both sides completes the proof of Claim D.15.To apply Fact D.8, it remains to bound R, which we do in the following claim.Claim D.16. R ≤ e k/2 log k/2 (B4/ϵ) √ n .Proof. By the definition of ℓ 2 norm, we haveR2 = E max i∈[n] sup ∥ṽ∥2=∥r∥2=1 1 n 2 (ṽ ⊤ (P (i) -P)r) 2 ≲ 1 n 2 E max i∈[n] sup ∥ṽ∥2=∥r∥2=1 (ṽ ⊤ P (i) r) 2 .Let us definef i (x (i) ) := ∥Mat (l,k-l) (He k (x (i) ))∥ 2 = sup ∥v∥2=∥r∥2=1 He k (x (i) ), Tensor(v) ⊗ Tensor(r) , where v ∈ R d l , r ∈ R d k-l, and f i (x (i) ) is a polynomial of (xEQUATIONd ) of degree at most k. Using the decomposition of ṽ⊤ = [(ṽ (1) ) ⊤ , (ṽ (2) ) ⊤ ] and r⊤ = [(r (1) ) ⊤ , (r (2) ) ⊤ ] again, we getR2 ≲ 1 n 2 E max i∈[n] sup v∈B d l ,r∈B d k-l (y (i) ) 2 ⟨He k (x (i) ), Tensor(v) ⊗ Tensor(r)⟩ 2 ≤ 1 n 2 E max i∈[n] (y (i) ) 2 (f i (x (i) )) 2 . Note that the polynomial f i (x (i) ) satisfies f i (x (i) ) ≥ 0 and E x (i) ∼N d [(f i (x (i) )) 2 ] = ∥Tensor(v) ⊗ Tensor(r)∥ 2 F ≤ 1. Note that E[max i∈[n] Z i ] ≤ n i=1 E[Z i ],thus using Fact D.10 we get:R2 ≤ 1 n 2 n i=1 E (x (i) ,y (i) )∼D [(y (i) ) 2 (f i (x (i) )) 2 ] ≤ e k log k (B 4 /ϵ) n .Taking the square root on both sides completes the proof.To apply Fact D.8, we need to choose the parameterR such that δ = Pr[max i∈[n] (1/n)∥P (i) - P∥ 2 ≥ R] is sufficiently small. Consider choosing R such that R ≳ e k log k (B 4 /ϵ)d (k-l)/4 √ n ≥ R1/2 γ 1/2 + √ 2 R.To determine δ, recall that from Fact D.9, we have (using Markov's inequality):EQUATIONNote that∥P (i) -P∥ 2 = |y (i) |f i (x (i) ), hence δ = Pr max i∈[n] 1 n ∥P (i) -P∥ 2 ≥ R ≤ Pr max i∈[n] B y f i (x (i) ) ≥ nR (i) ≤ n Pr B y f i (x (i) ) ≥ nR (ii) ≤ n p k/2 nR/B y p ,where in (i) we used a union bound and in (ii) we used Equation (34) with t = nR/B y . Now setting p k/2 = nR/(eB y ), we getδ ≤ exp(-(nR/(B y e)) 2/k + log(n)) ≲ exp(-log 2 (B 4 /ϵ)(ϵn) 1/k d 1/4 ).In summary, applying Fact D.8 with the bound on δ and γ (Claim D.14), γ * (Claim D.15), R (Claim D.16), and choosing t = d k/4 in Equation (32), we finally get that with probability at least1 -exp(-log 2 (1/ϵ)(ϵn) 1/k d 1/4 ) -d exp(-d k/4 ), it holds ∥M -M∥ 2 = ∥ P -P∥ 2 ≲ 2γ + γ * t 1/2 + R 1/3 γ 2/3 t 2/3 + Rt ≲ log k/2 (B 4 /ϵ)d (k-l)/2 √ n .Therefore, choosingn = Θ e k log k (B 4 /ϵ)d k-l ϵ 2 0 + 1 ϵ ,we have ∥M -M∥ 2 ≤ ϵ 0 , with probability at least 1 -exp(-d 1/2 ).To complete the proof of Lemma D.13, we apply Wedin's theorem (Fact D.6) and Claim D.7, which together imply thatEQUATIONWe then decompose v * into v * = av * + br, where r ∈ R d l such that r ⊥ v * and ∥r∥ 2 = 1, and a 2 + b 2 = 1. Since b = sin(θ(v * , v * )), applying Corollary D.5 we havev * • Vec(w * ⊗l ) = av * • Vec(w * ⊗l ) + br • Vec(w * ⊗l ) ≥ 1 -b 2 (1 -2 √ OPT/c k ) -b ≥ (1 -2 √ OPT/c k ) -(2 -2 √ OPT/c k )b ≥ 1 - 2 c k √ OPT - 2ϵ 0 (c k /2 -4 √ OPT) -ϵ 0 .This completes the proof of Lemma D.13.After getting an approximate top-left singular vector of Mat (l,k-l) (E (x,y)∼D [yHe k (x)]), v * ∈ R d l , we show that finding the top-left singular vector of the matrix Mat (1,l-1) ( v * ) completes the task of computing a vector u that correlates strongly with w * . Lemma D.17.Suppose that v * • Vec(w * ⊗l ) ≥ 1 -ϵ 1 for some ϵ 1 ∈ (0, 1/16]. Then, the top-left singular vector u ∈ R of Mat (1,l-1) ( v * ) satisfies u • w * ≥ 1 -2ϵ 1 . Proof. Consider the SVD of Mat (1,l-1) ( v * ) ∈ R d×d l-1 : Mat (1,l-1) ( v * ) = d i=1 ρ i u (i) (r (i) ) ⊤ ,whereEQUATIONr (i) ∈ R d l-1 , i ∈ [d],are two sets of orthonormal vectors. Note that {r (1) , . . . , r (d) } is a subset of {r (1) , . . . , r (d l ) }, which is an orthonormal basis ofR d l . Since (w * ) ⊤ Mat (1,l-1) ( v * )Vec(w * ⊗l-1 ) = v * • Vec(w * ⊗l ) ≥ 1 -ϵ 1 , we have ρ 1 ≥ 1 -ϵ 1 ,(w * ) ⊤ Mat (1,l-1) ( v * )Vec(w * ⊗l-1 ) = d i=1 ρ i (w * • u (i) )(Vec(w * ⊗l-1 ) • r (i) ) ≥ 1 -ϵ 1 . (36) Since u (i) , i ∈ [d] and r (i) , i ∈ [d l-1 ] form orthonormal bases of R d and R d lrespectively, we can decompose w * and Vec(w * ⊗l-1 ) in these bases respectively:w * = d i=1 a i u (i) , Vec(w * ⊗l-1 ) = d l-1 i=1 b i r (i) .Note that since ∥w * ∥ 2 = 1 and ∥Vec(w* ⊗l-1 )∥ 2 2 = ∥w * ⊗l-1 ∥ 2 F = 1, we have i a 2 i = 1 and i b 2 i = 1. In addition, since ∥ v * ∥ 2 = 1, we have ∥Mat (1,l-1) ( v * )∥ 2 F = d i=1 ρ 2 i = 1.Therefore, plugging the decomposition above back into Equation (36), we get1 -ϵ 1 ≤ d i=1 ρ i a i b i ≤ ρ 1 a 1 b 1 + ρ 2 d i=2 a 2 i d i=2 b 2 i ≤ ρ 1 a 1 b 1 + 1 -ρ 2 1 1 -a 2 1 1 -b 2 1 ≤ ρ 1 a 1 b 1 + 1 -ρ 2 1 (1 -a 1 b 1 ). When ρ 1 ≥ 1 -ϵ 1 ≥ √ 2/2, we have ρ 1 -1 -ρ 2 1 ≥ 0 and then it holds that a 1 b 1 ≥ 1 -1 -ρ 2 1 -ϵ 1 ρ 1 -1 -ρ 2 1 := g(ρ 1 ).We show that when 0 ≤ ϵ 1 ≤ 1/16 (which implies that 15/16 ≤ ρ 1 ≤ 1), it holds that g(ρ 1 ) ≥ 1 -2ϵ 1 . By the definition of g(ρ 1 ), it suffices to argue that1 -ρ 1 ≥ ϵ 1 (1 -2ρ 1 + 2 1 -ρ 2 1 ).This follows by direct calculations as whenρ 1 ∈ [15/16, 1], 1 -2ρ 1 + 2 1 -ρ 2 1 ≤ 0. Therefore, when ϵ 1 ≤ 1/16, it holds that a 1 b 1 ≥ 1 -2ϵ 1 . Since 0 ≤ a 1 , b 1 ≤ 1, it must be that a 1 ≥ 1 -2ϵ 1 ; this further implies that w * • u ≥ 1 -2ϵ 1 . D.3 Proof of Proposition D.2 Proof of Proposition D.2. Since √ OPT ≤ c k * /(64k * ) ≤ c k * /64, choosing ϵ 0 = c k * /(256k * ) ≤ c k * /256 in Lemma D.13, we obtain that using n = Θ((k * ) 2 e k * log k * (B 4 /ϵ)d ⌈k * /2⌉ /(c 2 k * ) + 1/ϵ), it holds with probability at least 1 -exp(-d 1/2 ) that v * • Vec(w * ⊗l ) ≥ 1 - 2 c k √ OPT - 2ϵ 0 (c k /2 -4 √ OPT) -ϵ 0 ≥ 1 - 1 32k * - c k * /(128k * ) c k * /2 -c k * /16 -c k * /256 ≥ 1 - 1 16k * .Then applying Lemma D.17 with ϵ 1 ≤ 1/(16k * ) ≤ 1/16 we get that the output u of Algorithm 3 satisfies u • w * ≥ 1 -2ϵ 1 ≥ 1 -1/(8k * ) ≥ 1 -min{1/k * ,-exp(-d 1/2 ) that v * • Vec(w * ⊗l ) ≥ 1 -(2/c k * )OPT + ϵ/3(≥ 15/16). Then applying Lemma D.17 with ϵ 1 = (2/c k * )OPT -ϵ/3, we get that the output w 0 of Algorithm 3 satisfiesw 0 • w * ≥ 1 -2((2/c k * ) √ OPT + ϵ/3).Finally, to show the upper bound on the L 2 2 loss of w 0 , we bring in the definition of the L 2 2 loss L σ 2 (w 0 ), which yieldsL σ 2 (w 0 ) ≤ 2OPT + 2L * σ 2 (w 0 ) = 2OPT + 2 1 - k≥k * c 2 k (w 0 • w * ) k = 2OPT + 2 k≥k * c 2 k (1 -(w 0 • w * ) k ) = 2OPT + 2 k≥k * c 2 k (1 -(w 0 • w * ))(1 + (w 0 • w * ) + • • • + (w 0 • w * ) k-1 ) ≤ 2OPT + 2 k≥k * kc 2 k (1 -(w 0 • w * )) ≲ k≥k * kc 2 k 4 c k * √ OPT + ϵ/3 .Since k≥k * kc 2 k ≤ C k * by Assumption 1(iii), this completes the proof of Proposition D.3.After getting an initialized vector w 0 using Algorithm 1, we run Riemannian minibatch SGD Algorithm 2 on the 'truncated loss'. In the following sections, we will first present the definition of the truncated L 2 2 loss L ϕ 2 and its Riemannian gradient, then we will proceed to show that Algorithm 2 converges to a constant approximate solution in O(log(1/ϵ)) iterations. k * c k * y (i) (I -w t (w t ) ⊤ )⟨He k * (x (i) ), (w t ) ⊗k * -1 ⟩.w t+1 = (w t -η g(w t ))/∥w t -η g(w t )∥ 2 . 6: Return: w T .Instead of directly minimizing the L 2 2 loss L σ 2 , we work with the following truncated loss that drops all the terms higher than k * in the polynomial expansion of σ:EQUATIONSimilarly, the noiseless surrogate loss is defined asEQUATION)Using Fact C.1(2), the gradient of the truncated L 2 2 loss equals:EQUATIONwhile for the gradient of the noiseless L 2 2 loss we haveEQUATION)Recall that P w ⊥ := Iww ⊤ . Then the Riemannian gradient of the L 2 2 loss L ϕ 2 , denoted by g(w) is g(w)EQUATIONSimilarly, the Riemannian gradient of the noiseless L 2 2 loss L * ϕ 2 is defined by g * (w) :EQUATION)The following claim establishes that g * (w) carries information about the alignment between vectors w and w * . Claim E.1. For any w ∈ S d-1 , we have g* (w) = -2k * c k * (w • w * ) k * -1 (w * ) ⊥w .Proof. Using the definition of g * (w) from Equation (42), a direct calculation shows thatg * (w) • (w * ) ⊥w ∥(w * ) ⊥w ∥ 2 (i) = -2k * E x∼N d k≥k * c k He k (x), w * ⊗k • He k * (x), w ⊗k * -1 ⊗ (w * ) ⊥w ∥(w * ) ⊥w ∥ 2 (ii) = -2k * c k * Sym(w * ⊗k * ), Sym w ⊗k * -1 ⊗ (w * ) ⊥w ∥(w * ) ⊥w ∥ 2 (iii) = -2k * c k * (w • w * ) k * -1 ∥(w * ) ⊥w ∥ 2 ,where (i) is by the definition of g * (w) and σ(w * • x), (ii) is by Fact C.3, and (iii) is by Fact C.1(1), Equation (20), and ∥w * ∥ 2 = 1. Let v ∈ R d be any unit vector that is orthogonal to (w * ) ⊥w . Observe that v ⊥w • w * = v • (w * ) ⊥w = 0. Thus, we haveg * (w) • v = -2k * c k * Sym(v ⊥w ⊗ w ⊗k * -1 ), Sym(w * ⊗k * ) = -2k * c k * (w • w * ) k * -1 (v ⊥w • w * ) = 0.This implies that g * (w) is parallel to (w * ) ⊥w and thus g * (w) = -2k * c k * (w•w * ) k * -1 (w * ) ⊥w .Let us denote the difference between the noisy and the noiseless Riemannian gradient by ξ(w):ξ(w) := g(w) -g * (w) = -2 E (x,y)∼D [(y -σ(w * • x))P w ⊥ ∇ϕ(w • x)] .We next show that the norm of ξ(w) and the inner product between ξ(w) and w * are both bounded: Lemma E.2. Let ξ(w) = g(w) -g * (w) as defined above. Then,∥ξ(w)∥ 2 ≤ 2k * c k * √ OPT and |ξ(w) • w * | ≤ 2k * c k * √ OPT∥(w * ) ⊥w ∥ 2 .Proof. Using the definition of ξ(w) and the definition of the 2-norm,∥ξ(w)∥ 2 = 2k * c k * max v∈S d-1 E (x,y)∼D (y -σ(w * • x))P w ⊥ ⟨He k * (x), w ⊗k * -1 ⟩ • v = 2k * c k * max v∈S d-1 E (x,y)∼D (y -σ(w * • x))⟨He k * (x), v ⊥w ⊗ w ⊗k * -1 ⟩ ≤ 2k * c k * max v∈S d-1 E (x,y)∼D [(y -σ(w * • x)) 2 ] E x∼N d ⟨He k * (x), v ⊥w ⊗ w ⊗k * -1 ⟩ 2 = 2k * c k * max v∈S d-1 √ OPT∥Sym(v ⊥w ⊗ w ⊗k * -1 )∥ F ,where the (only) inequality is by Cauchy-Schwarz, and the last equality is by Fact C.3. As a tensor A, it holds ∥Sym(A)∥ F ≤ ∥A∥ F , we have∥Sym(v ⊥w ⊗ w ⊗k * -1 )∥ 2 F ≤ ∥v ⊥w ⊗ w ⊗k * -1 ∥ 2 F = ∥v ⊥w ∥ 2 2 ≤ 1, which then implies that 4 ∥ξ(w)∥ 2 ≤ 2k * c k * √ OPT.Following the same line of argument as above, we also get|ξ(w) • w * | ≤ 2 √ OPT (k * c k * ) 2 ∥(w * ) ⊥w ⊗ w ⊗k * -1 ∥ 2 F = 2k * c k * √ OPT∥(w * ) ⊥w ∥ 2 .This completes the proof of Lemma E.2.As a direct corollary of Lemma E.2, we now show that the norm of the noisy gradient ∥g(x)∥ 2 is close to the norm of the noiseless gradient ∥g * (w)∥ 2 .Corollary E.3. For anyw ∈ S d-1 , ∥g(w)∥ 2 ≤ 2k * c k * √ OPT + ∥g * (w)∥ 2 .Proof. Follows by the triangle inequality, as ∥g(w)∥ 2 ≤ ∥ξ(w)∥ 2 + ∥g * (w)∥ 2 .We are now ready to present the main structural result of this section. Lemma E.4 (Sharpness). Assume OPT ≤ c/(4e) 2 for some small absolute constant c < 1. Let w ∈ R d such that ∥w∥ 2 = 1 and suppose that w• w * ≥ 1 -1/k * . Let θ := θ(w, w * ). If sin θ ≥ 4e √ OPT, then g(w) • w * ≤ - 1 2 ∥g * (w)∥ 2 sin θ.Proof. We start by noticing that by Claim E.1, the noiseless gradient satisfies the following property:g * (w) • w * = -2k * c k * (w • w * ) k * -1 ∥(w * ) ⊥w ∥ 2 2 = -∥g * (w)∥ 2 sin θ,where we used that since ∥w∥ 2 = ∥w * ∥ 2 = 1, we have ∥(w * ) ⊥w ∥ 2 = sin θ. Furthermore, applying Lemma E.2 we have the following sharpness property with respect to the L 2 2 loss:EQUATIONObserve that (1 -1/t) t-1 ≥ 1/e for all t ≥ 1. Therefore, when w • w * ≥ 1 -1/k * , the norm of the gradient vector g * satisfies∥g * (w)∥ 2 = 2k * c k * (w • w * ) k * -1 sin θ ≥ 2k * c k * (1 -1/k * ) k * -1 sin θ ≥ e -1 k * c k * sin θ.therefore, when sin θ ≥ 4e√ OPT and w • w * ≥ 1 -1/k * , we have ∥g * (w)∥ 2 ≥ 4k * c k * √ OPT.Thus, as long as sin θ ≥ 4e √ OPT, we have that g(w) • w * ≤ -1 2 ∥g * (w)∥ 2 sin θ.For notational simplicity, define:EQUATION)Then the empirical estimate of g(w) isEQUATION)The following lemma provides the upper bounds on the number of samples required to approximate the Riemannian gradient g(w) by g(w).Lemma E.5 (Concentration of Gradients). Let w * , w ∈ S . Let g(w) be the empirical estimate of the Riemannian gradient. Furthermore, denote the angle between w and w * by θ. Then, with probability at least 1 -δ it holds∥ g(w) -g(w)∥ 2 ≲ d(k * c k * ) 2 e k * log k * (B 4 /ϵ) nδ ; ( g(w) -g(w)) • w * ≲ (k * c k * ) 2 e k * log k * (B 4 /ϵ) sin 4 (θ) nδ .Proof. By Chebyshev's inequality, we haveEQUATION)Let e j be the j th basis of R d , we have ∥g(w; x, y) -g(w)∥ 2 2 = d j=1 (g(w; x, y) • e j -g(w) • e j ) 2 . Thus, it suffices to bound the expectation of each summand (g(w; x, y) • e j -g(w) • e j ) 2 , for j ∈ [d]. Note first that since g(w) = E (x,y)∼D [g(w; x, y)], we haveE (x,y)∼D [(g(w; x, y) • e j -g(w) • e j ) 2 ] ≤ E (x,y)∼D [(g(w; x, y) • e j ) 2 ] = 4(k * c k * ) 2 E (x,y)∼D y 2 He k * (x), e ⊥w j ⊗ w ⊗k * -1 2 .Denote f j (x) := ⟨He k * (x), e ⊥w j ⊗ w ⊗k * -1 ⟩, which is a polynomial of x of degree k * . In addition, note thatE x∼N d [f j (x) 2 ] = ∥e ⊥w j ⊗ w ⊗k * -1 ∥ 2 F ≤ ∥e ⊥w j ∥ 2 2 ≤ 1.Therefore, applying Fact D.9 and Fact D.10 with A = y 2 and B = f j (x) 2 , we getE (x,y)∼D y 2 He k * (x), e ⊥w j ⊗ w ⊗k * -1 2 ≤ E (x,y)∼D [y 2 ](4e) k * max 1, 1 k * log(B 4 /ϵ) k * ≲ e k * log k * (B 4 /ϵ).Thus, it holds that E (x,y)∼D [(g(w; x, y) • e j -g(w)• e j ) 2 ] ≲ (k * c k * ) 2 e k * log k * (B 4 /ϵ), which further implies that the expectation of ∥g(w; x, y) -g(w)∥ 2 2 is bounded above byE (x,y)∼D [∥g(w; x, y) -g(w)∥ 2 2 ] ≲ d(k * c k * ) 2 e k * log k * (B 4 /ϵ).Plugging this back into the Chebyshev's bound Equation (46), we obtainPr[∥ g(w) -g(w)∥ 2 ≥ t] ≤ d(k * c k * ) 2 e k * log k * (B 4 /ϵ) nt 2 .Therefore, with probability at least 1 -δ, it holds∥ g(w) -g(w)∥ 2 ≤ d(k * c k * ) 2 e k * log k * (B 4 /ϵ) nδ .Now for the second statement of Lemma E.5, we similarly Chebyshev's inequality, which yieldsPr 1 n n i=1 g(w; x (i) , y (i) ) • w * -g(w) • w * ≥ t ≤ 1 t 2 E (x,y)∼D 1 n n i=1 g(w; x (i) , y (i) ) • w * -g(w) • w * 2 ≤ 1 nt 2 E (x,y)∼D [(g(w; x, y) • w * ) 2 ] = 4(k * c k * ) 2 nt 2 E (x,y)∼D [(y⟨He k * (x), w ⊗k * -1 ⊗ (w * ) ⊥w ⟩) 2 ]. Let f w * (x) := ⟨He k * (x), w ⊗k * -1 ⊗ (w * ) ⊥w ⟩. Note that E x∼N d [f w * (x) 2 ] = ∥w ⊗k * -1 ⊗ (w * ) ⊥w ∥ 2 F = ∥(w * ) ⊥w ∥ 2 2 . Since w * , w ∈ S d-1, we have ∥(w * ) ⊥w ∥ 2 = sin θ. Thus, by Fact D.9,∥f 2 w * (x)∥ L p = E x∼N d [(f w * (x)) 2p ] 2/(2p) ≤ (2p-1) k * /2 E x∼N d [(f w * (x)) 2 ] 2 ≤ (2p) k * sin 4 θ.Hence, applying Fact D.10 with A = y 2 , B = f 2 w * (x), σ B = sin 4 θ, and C = k * , we obtainE (x,y)∼D [(y⟨He k * (x), w ⊗k * -1 ⊗ (w * ) ⊥w ⟩) 2 ] ≲ sin 4 θe k * log k * (B 4 /ϵ).Therefore, it holds thatPr[|( g(w) -g(w)) • w * | ≥ t] ≲ (k * c k * ) 2 e k * log k * (B 4 /ϵ) sin 4 (θ) nt 2, which implies that with probability at least 1 -δ it holds( g(w) -g(w)) • w * ≲ (k * c k * ) 2 e k * log k * (B 4 /ϵ) sin 4 (θ) nδ .We proceed to the main theorem of this paper. It shows that using at most Θ(d ⌈k/2⌉ + d/ϵ) samples, Algorithm 2 (with initialization subroutineAlgorithm 1) generates a vector w such that L σ 2 ( w) = O(OPT) + ϵ within O(log(1/ϵ)) iterations.Theorem E.6. Suppose that Assumption 1 holds. Choose the batch size of Algorithm 4 to be n = Θ(C k * de k * log k * +1 (B 4 /ϵ)/(ϵδ)), and choose the step size η = 9/(40ek * c k * ). Then, after T = O(log(C k * /ϵ)) iterations, with probability at least 1 -δ, Algorithm 4 generates a parameter w T that satisfies L σ 2 (w T ) = O(C k * OPT) + ϵ. The total number of samples required for Algorithm 4 isN = Θ (k * /c k * ) 2 e k * log k * (B 4 /ϵ)d ⌈k * /2⌉ + e k * log k * +2 (B 4 /ϵ)C k * d ϵδ .Proof. Suppose first that OPT ≥ (c k * /(64k * )) 2 , i.e., OPT is of constant value. Then by Claim E.7 we know that for any unit vector w (e.g., w = e 1 ) it holdsL σ 2 ( w) ≤ 2OPT + 4 k≥k * kc 2 k (1 -(w • w * )) ≤ 2OPT + 4C k * = O(OPT).Hence w is an approximate solution of the agnostic learning problem. Now suppose OPT ≤ (c k * /(64k * )) 2 , the assumption in Proposition D.2 is satisfied and Algorithm 3 can be applied. Consider the distance between w t and w * after each update of Algorithm 4. By the non-expansive property of projection operators, we haveEQUATION)Let us denote the angle between w t and w * by θ t . Furthermore, let us assume for now that θ t satisfies sin θ t ≥ 4e √ OPT + √ ϵ, hence the condition for Lemma E.4 is satisfied. Note by definition g(w t ) ⊥ w t , hence using Lemma E.4 and Lemma E.5 we have that with probability at least 1 -δ, the inner product term in Equation ( 47) is bounded above by:EQUATIONwhere C 1 is a sufficiently large absolute constant. On the other hand, the squared norm term ∥ g(w t )∥ 2 2 from Equation (47) can be bounded above using Lemma E.5 and Corollary E.3:EQUATIONfor a sufficiently large absolute constant C 2 . Plugging Equation (48) and Equation (49) back into Equation (47), and denoting κ := max{C 1 , C 2 }k * c k * e k * /2 log k * /2 (B 4 /ϵ), we get that with probability at least 1 -δ,∥w t+1 -w * ∥ 2 2 ≤ ∥w t -w * ∥ 2 2 + ηκ √ nδ sin 2 θ t - η 2 ∥g * (w t )∥ 2 sin θ t + η 2 dκ 2 nδ + (k * c k * ) 2 OPT + ∥g * (w t )∥ 2 2 .Let us assume first that θ t ≤ θ t-1 ≤ • • • ≤ θ 0 and θ t satisfies sin θ t ≥ 4e √ OPT + √ ϵ. We will argue that in this case θ t+1 ≤ θ t (in fact, that it contracts by a constant factor). Then, by an inductive argument, we immediately know that the assumption is valid and that θ t is a decreasing sequence (as long as sin θ t ≥ 4eOPT + ϵ). To prove θ t+1 ≤ θ t , recall that in Claim E.1 it was shown that∥g * (w t )∥ 2 = 2k * c k * (w t • w * )∥(w * ) ⊥ w t ∥ 2 = 2k * c k * (w t • w * ) k * -1 sin θ t .Recall that w 0 is the initial parameter vector that satisfies w 0 • w * ≥ 1 -1/k * . By the inductive hypothesis it holds θ t ≤ θ 0 , hencew t • w * ≥ w 0 • w * ≥ 1 -1/k * . Furthermore, as we have (1 -1/t) t-1 ≥ 1/e for t ≥ 1, it holds 1 ≥ (w t • w * ) k * -1 ≥ 1/e.Therefore, we further obtain(2k * c k * /e) sin θ t ≤ ∥g * (w t )∥ 2 ≤ 2k * c k * sin θ t . Now choosing n ≳ dκ/((k * c k * ) 2 ϵδ), and recalling that we have assumed sin θ t ≥ 4e √ OPT + √ ϵ by the induction hypothesis, we can further bound ∥w t+1 -w * ∥ 2 2 above as:∥w t+1 -w * ∥ 2 2 ≤ ∥w t -w * ∥ 2 2 + η((ϵ/d) 1/2 -(4k * c k * /e)) sin 2 θ t + η 2 (k * c k * ) 2 (ϵ + OPT + 4 sin 2 θ t ) (50) ≤ ∥w t -w * ∥ 2 2 -(3k * c k * /e)η sin 2 θ t + 5η 2 (k * c k * ) 2 sin 2 θ t .Observe that since θ t ≤ θ 0 and by assumption w 0 • w * = cos θ 0 ≥ 1 -min{1/k * , 1/2} ≥ 1/2, we have cos(θ t /2) ≥ √ 3/2 and thus it further holds that ( √ 3/2)(2 sin(θ t /2)) ≤ sin θ t ≤ 2 sin(θ t /2). Since ∥w tw * ∥ 2 = 2 sin(θ t /2) follows from w t , w * ∈ S d-1 , we finally obtain that, with probability at least 1 -δ,∥w t+1 -w * ∥ 2 2 ≤ (1 -(9k * c k * /(4e))η + 5(k * c k * ) 2 η 2 )∥w t -w * ∥ 2 2 .Choosing η = 9/(40ek * c k * ) yields probability at least 1 -δ): EQUATIONsin(θ t * +1 ) ≤ 1 + 8η 2 (k * c k * ) 2 sin(θ t * ) ≤ 3 sin θ t * ≤ 3(4e √ OPT + √ ϵ).In other words, for all steps t * ≤ t ≤ T , it holds that sin θ t ≤ 30( √ OPT + √ ϵ). Thus, in summary, choosing T = O(log(1/ϵ)), we get that with probability at least 1 -δT , sin θ T ≲OPT + √ ϵ, and applying Claim E.7 we get:L σ 2 (w T ) = O k≥k * kc 2 k (OPT + ϵ) = O(C k * OPT) + ϵ ′ ,where we set ϵ ′ = ϵ/C k * ≤ ϵ/( k≥k * kc 2 k ), and used Assumption 1(iii) that k≥k * kc 2 k ≤ C k * . Thus, choosing δ ′ = δT , where T = O(log(C k * /ϵ ′ )), Algorithm 4 outputs a parameter w T such that with probability at least 1-δ ′ , L σ 2 (w T ) = O(C k * OPT) + ϵ ′ , with batch size n = Θ dC k * e k * log k * +1 (B 4 /ϵ ′ ) ϵ ′ δ ′ .In summary, the total number of samples required for Algorithm 4 isN = Θ (k * ) 2 e k * log k * (B 4 /ϵ ′ )d ⌈k * /2⌉ c 2 k * + C k * de k * log k * +2 (B 4 /ϵ ′ ) ϵ ′ δ ′ .The final claim shows that if sin(θ(w, w* )) ≲ √ OPT + √ ϵ, then L σ 2 (w) ≲ C k * (OPT + ϵ).Claim E.7. Let w ∈ S d and denote the angle between w and w * by θ. If θ satisfies sin θ ≤ C( √ OPT + √ ϵ) for some absolute constant C, then we haveL σ 2 (w) ≲ k≥k * kc 2 k (OPT + ϵ).Proof. Since w • w * = cos θ ≥ 1 -sin 2 θ, according to Claim C.4 L 2 2 loss L σ 2 (w) can be upper bounded byL σ 2 (w) ≤ 2OPT + 4 1 - k≥k * c 2 k (w • w * ) k = 2OPT + 4 k≥k * c 2 k (1 -(w • w * ) k ) = 2OPT + 4 k≥k * c 2 k (1 -(w • w * ))(1 + (w • w * ) + • • • + (w • w * ) k-1 ) ≤ 2OPT + 4 k≥k * kc 2 k (1 -(w • w * )) ≤ 2OPT + 4 k≥k * kc 2 k sin 2 θ ≤ 2OPT + 4 k≥k * kc 2 k C 2 (OPT + ϵ) ≲ k≥k * kc 2 k (OPT + ϵ).NeurIPS Paper Checklist• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA]Justification: The paper is theoretical in nature and does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification: The paper is theoretical in nature, and we do not see any major or immediate implications for society.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper is theoretical and does not use data or models that have a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This work does not use any assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Ignoring dependence on other problem parameters for simplicity; see Proposition2.1 for a precise statement.A summary of useful algebraic properties of the unfolded tensor is provided in Fact D.1 in Appendix D.Note that[RM14] takes a different normalization and in the notation of[RM14], it holds β ≈ τ / √ d.Note here that if we had not used the truncation of the activation, then the bound on the error term ξ(w) we could get would be ∥ξ(w)∥2 ≤ ( k≥k * c 2 k k 2 ) 1/2 √ OPT. 
 
 Appendix:  


Decision: This paper make progress on a problem in machine learning theory of significant recent interest: efficiently learning single index models. The paper gives a computationally efficient algorithms with near optimal sample complexity that works even in the challenging agnostic (adversarial noise) setting. Prior work mainly focuses on the realizable setting. While there are areas for the result to be tightened or improved, it seems clear from the discussion that this work will open the doors to future results, and the very knowledgeable reviewers were all positive on the work in the end. We recommend acceptance.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: 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.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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 ?
limitations: limitations: N/A
paper_summary: paper_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).
strength_weakness: strength_weakness: NA
questions: 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.
limitations: limitations: NA

Comments: title: Your answer Q5 is not correct
comment: We reiterate that our work provides guarantees in the *agnostic model*, where the labels $y$ can be arbitrarily corrupted. Consequently, a function of the form $f(x)= E[y|x]$  is  *unknown* to the learner and cannot even be estimated efficiently (as the $x$-marginal follows a standard normal, which makes it impossible to sample the same point twice). 
The works cited by the reviewer give necessary conditions to lower the information exponent down to $2$, assuming that the distribution of $y$ is *known* to the learner. We invite the reviewer to check the statement of Theorem 2 in [MM18], and in particular how the function $T(y)$ is defined. In summary, the algorithms given in these works do not succeed in our corruption model.  

Moreover, even assuming the distribution of $y$ is known to the learner (in which case the above theorem would be applicable), there exist function/distribution pairs where the information exponent=generating exponent>2 (see for example [MM18] and Figure 2 in [DPVLB24]). For such instances, the aforementioned works do not achieve the stated results. In summary, even for the easier setting where the learner knows the distribution of $y$ a priori, the above works do not in general achieve improved sample complexity for our setting. 

The reviewer argues that “virtually any link function (except made-up, carefully fine-tuned ones)” has a generative exponent up to $2$. We respond in two parts. First, our work is theoretical, establishing algorithmic results under a clearly defined set of assumptions. If we strengthen these assumptions (e.g., assume a generative exponent at most $2$), potentially more efficient results are possible (but even that remains open in the agnostic model). We emphasize however that this is formally a special case of our setting. Second, from the practicality perspective, one can construct natural examples where information exponent=generating exponent>2.  In particular, this holds if the distribution of $y$  is supported in ${\pm 1}$, in which case the two exponents are identical (because in this case SQ and CSQ are known to be equivalent). Note that the distribution of $y$ can be Boolean-valued even if the link function is real-valued (e.g., a sigmoid).
I thank the authors for their detailed response. 
The comments regarding preprocessing appear convincing to me and my overall evaluation remains unchanged. 

I have one more quick clarification question that's somewhat related to (C2), (C5). 
Should I think of $\epsilon$ as a constant or depending on $d$ (potentially arbitrarily)?
With respect to Q5, your statements are uncorrected.

The papers I mentioned solve ALL problems with generative (and not information, as you claim) exponent up to two. This means that virtually any link function (except made-up, carefully fine-tuned ones) are covered. See, for instance, the discussion on page 5 in the first paragraph of https://arxiv.org/pdf/2403.05529: "In fact, [MM18, BKM+19, MLKZ20] give a necessary and sufficient condition on P that enables such T to lower the information exponent to 2." 

I invite the authors to check theorem 1 and theorem 2 in [MM18] https://arxiv.org/abs/1708.05932, which are for "generic sensing models," (this is also the case of [BKM+19, MLKZ20], phase retrieval is just an a particular application). The authors can also check https://arxiv.org/abs/2012.04524, section 1.2 Main results, eq(5) for optimal transformation valid for almost any link function.

The ONLY functions not covered in these works are those with generative (again, not information) exponent 3 and higher (see again https://arxiv.org/pdf/2403.05529), a class that essentially consists of fine-tuned functions, corresponding to unnatural, made-up problems, without much application for generic single-index exponents.
 
To quote your answer, all these papers do study  "algorithms that can weakly recover the signal for much more general link functions with any constant information exponent $k^*$" (in fact they do so for arbitrary k^* with just O(d) samples and O(dlogd) iterations) and I thus invite the authors to check these papers carefully.
#### 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.
(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