Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models
Authors: Puqian Wang
Nikos Zarifis
Ilias Diakonikolas
Jelena Diakonikolas
Venue: NeurIPS 2024 poster (2024)
Keywords: single index models
agnostic learning
adversarial label noise
Primary area: learning_theory
TL;DR: We provide the first sample and computationally efficient learner for Gaussian Single-Index Models, for link functions with a constant information exponent, in the agnostic model.

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.

Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models
Puqian Wang
Nikos Zarifis
Department of Computer Science University of Wisconsin, Madison
Department of Computer Science
University of Wisconsin, Madison
pwang333uvisc.edd
Ilias Diakonikolas Department of Computer Science University of Wisconsin, Madison ilias@cs. wisc.
Jelena Diakonikolas
Department Computer Science University of Wisconsin, Madison jelena@cs wisc. edu
Abstract
A single-index model (SIM) a function of the form o(w* x), where - is a known link function and w* is 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ă-loss under the Gaussian distribution. Our main result is sample and computationally efficient agnostic proper learner that attains L3-error of + e, where OPT is the optimal loss. The sample complexity of our algorithm is (ddTk" /2] + d/e), where k* is the information-exponent of a corresponding to the degree 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.
Introduction
Single-index models (SIMs) Ich933 HJSOT HMS+04 DIS08 KS09 KKSKII DH18 DGK+20
DKTZ22 WZDD23] DNGL23] are a classical supervised learning model characterized by hidden low-dimensional structure. The term SIM refers any function of the form f(x) o(w x). where a R + R is the link (or activation) function and w E Rd 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-theorrticall 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 the Perceptron algorithm [Ros58]. Classical early works [KS09] KKSKII studied the efficient Icarnability 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 resurgence of research on the topic with 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. [Sol1]] showed that SGD efficiently learns SIMs for the case that the ReLU activation and the distribution Gaussian. (CLSI5 CCFM19 SQW1S) showed that gradient descent succeeds for the phase retrieval problem, corresponding to a a(l) = L' or a() [4].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

More recently, a line of work [DHI8] BAGI2I DNGL23 DPVLB24] studied the efficient learnability of SIMs going significantly beyond the monotonicity assumption. Specifically, [BAGI2T 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 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 hypothesis that is competitive with the best-fit function the class. The algorithmic study of agnostically learning SIMs is not new. A recent line of work IDGK 20, DKT2222 VT WZDD23] GGKS23 [WDD224 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 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 DNGL233.
In order to precisely describe our contributions, we require the definition of the agnostic learning problem for Gaussian SIMs. Let D be distribution of labeled examples (x, y) E F2 x R whose x-marginal is the standard Gaussian, and let (w) == E(x.y)>>D (a(ww x) - -) be the T.2 (or squared) loss of the hypothesis fxx) = (w x) with respect to D. Given i..dd samples from D, the goal is to compute a hypothesis with squared error competitive with OPT, where OPT is the best attainable L3- -3-error by any function in the target class.
Problem 1.1 (Robustly Learning Gaussian SIMs). Let D be distribution of labeled examples (x, y) E Rd x E whose x-marginal is Dx = (0, Ig) and y is arbitrary. We say that an algorithm is C-approximate proper SIM learner, for some C 2 1, if gigeen algorithm outputs a vector w E Sd-1 such that with high probability it holds D2 ))= S COPT + where OPT := (w") and w argmin 1 C3 (w).
0 and i.i.d. samples from D, the
First, note that Problem 1.1 does not make realizability assumptions 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 obtaining efficient learners that achieve 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 + c, 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 + e in the above setting requires (Poly(1/c)
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 I R be real- valued function that admits the Hermite decomposition (z) = Exzo (2))x(2), where = (o--) and heę is the normalized probabilist's Hermite polynomial, defined by
hex(2) (-1)
22 d ( d exp ( (- 2² --)))
Vh! exp
We make the following assumptions.
Assumption (Family of Link Functions). Suppose that is normalized, namely Exz0 of = We assume the following:
Es
(i) The first non-zero Hermite coefficient has degree k" and is prominent: cg- an absolute constant that is bounded away from zero.
(ii) The fourth moment of (z2) is bounded: Eo < B1 < co.
2

---

(iii) The second moment of the derivative of ((2) is bounded: on- Exzx kcj S Cwe, where O₁e is an absolute constant whenever k- is an absolute constant. The parameter k" is known the information exponent of
The information exponent k* can be viewed as a complexity measure of the link function. Specifically, The same holds for the class of bounded activations ReLU activations correspond to k- The link functions used in phase retrieval have k* = 2.
considered in DKTZ22 W
We note that Assumption I is (at least) as general as those used in [BAGI21 DNGL2 L23 which focused on the realizable setting. Comparing against previous constant- factor agnostic learners, Assumption strongly subsumes the class of "bounded activations" (DKT722 WZDD23. In particular, it is easy to see that there exist functions satisfying Assumption with constant k. that are far from monotone. See (pppendix for detailed justification.
aatistinggAssumption
In prior work, [DNGL23), building on [BAGI21], gave a sample-efficient gradient method for learning SIMs under Assumption in the realizable setting. The sample complexity of their method is O(t /2 + d/e). This sample upper bound essentially matches known lower bounds in the Correlational Statistical Query (CSQ) model [DS222 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 TV
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 non-trivial initialization step. We emphasize that this is the first polynomial-ting constant-factor agnostic learner for this task under Aasuum//smmtiionn I
Specifically, we establish the following result (see Theorem 3.5 for a more detailed statement).
Theorem 1.2 (Main Result, Informal). There exists algorithm that draws n = (d]k(ddk//2 + d/e) labeled samples, runs in poly(n,
(n,y d) time, and outputs a weight vector w E @d-1 that with high probability satisfies Lg (w) S COPT e, where OCkk))
Theorem 1.2 gives the first sample and computationally efficient robust learner for Gaussian SIMs under Assumption I] This generalizes the algorithm of [NGL233 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-CSe CSQC 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 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 (pppendii B for detailed discussion.
1.1 Preliminaries
For E 24, let [m] == (1, (I,...,n. n). We use lowercase bold characters to denote vectors and uppercase bold characters for matrices and tensors. For x E RR and i E [d], x; denotes the i-th coordinate of x, and ||x||| (E==x²)'' x²2 denotes the &g norm of x. We use x y for the inner product of x.y Rdd and (xx, y) for the angle between x, We slightly abuse notation and denote by e; the 7th standard basis vector in Rd We use 1{E} to denote the indicator of statement E. We use Na to denote the d-dimensional standard Gaussian distribution, i.e., Na = (O, I). We use B3 to denote the centered unit ball in ded and denote the unit sphere Rd by gd-1, We use projs, (-) to denote the projection operator that projects a vector to the unit ball.
Given M Rdixd and left singular vector Rdd of M, we denote the corresponding singular value of v by p(v). In addition, we use P1 2 P2 2 ... 2 (mi to denote the singular values of a matrix M E Ied xd2, We use St to denote the set of all possible permutations of k distinct objects. Given unit vector w, we define Pw! == I ww to be the projection matrix that maps a vector to its component that is orthogonal to w, i.c., P v-v.
3

---

Given vector X E R the (normalized) Hermite multivariate tensor is defined by [aah17]:
(Hes (H)x(())):nn (x))i..... (an!.... Oad!
1/2
hea, (x1) head
.e., (Xa), where 0;- = Σ 1 1), vj [d]
k!
We use the standard O()), (-). .2(-) asymptotic notation. We use Ō(-) to omit polylogarithmic factors in the argument. We write E 2 F for two non-negative expressions E and F to denote that such that E 2 F.
there exists some positive universal constant c
1.2 Technical Overview
Our technical approach consists of two main parts: (1) new results for tensor PCA, which allow us obtain initial parameter vector w that is nontrivially aligned with the target w and (2) a structural "alignment sharpness" result, which we use to argue that variant of Riemannian minibatch stochastic gradient descent on a sphere applied "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 and the target vector w" as measured by w w", essential. In particular, consequence of our results in Claim 3.1 an 3.2 is that w w' ((1) is required to deal with the highly corruptive agnostic noise. Unfortunately, if were to select wo by drawing uniformly random samples from the sphere, exponentially many such samples would be needed to ensure that with constant probability at least one of the sampled vectors Wo is such that w w = 22(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 (d "=" /21) samples ensures that w w" 2 1 min 1 kk", 1/2]. The reason that this result is surprising that the method [RM14) was developed solve the following problem: given a k-tensor of the form
T TV +
(PCA-S)
where is k-tensor with i.i.d. standard Gaussian entries and > 0 "signal strength" parameter, recover the planted (signal) vector This 'single-observation" model is equivalent (in law) to the following multi-obserration model ([BAG]20)): given i..dd. copies ( r'y + A with T' =T/Vn, recover using the empirical estimation:
T= @k + (1/n)
Σ A
(PCA-M)
In our setting, we wish to recover a vector w (up to some constant alignment error) for the k-Chow tensor C2 Dly (x)), which can be decomposed
Ck= = E Σ oy (x), w 8/ Hex(x)] + x~~Na 12k
E [(y oww" Hex
(I)
(x.D)=D
The 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 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 2 k*, the top left singular vector v* of the k-Chow tensor Cs unfolded into a matrix of roughly equal dimensions carries "strong signal" about the target vector w": its associated singular value scales with C whenever e₁ ((VOPT) and it has nontrivial alignment with the vectorized version of the I-tensor s for 1 [k/2] (Lemma 2.2
To prove the desired alignment result using the empirical estimate of the matrix unfolled k-Chow tensor C₁ we rely on the application of a matrix concentration inequality obtained very recently
"ggnoring dependence other problem parameters for simplicity; see Proposition 2.1 for precise statement.

---

in [vH222] This requires a rather technical argument utilizing Gaussian hypercontractivity of multivariate polynomials of bounded degree, which we show characterizes the different "variance- like" quantities associated with the empirical estimate of (the matrix-unfolded Cg. for which we apply the aforementioned matrix concentration (see BeeeLemma 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(VOPT + +e) e)-error solution. In particular, in the realizable case studied in [DNGL23], where OPT 0, this result directly leads to error ( in sample and computationally efficient manner, with rather simple algorithm and sample complexity comparable to [DNGL23).
Sphere The second key ingredient in our work is 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 a sphere) negatively correlates with w* to a significant extent. This property can be viewed as the considered gradient field, associated with the L 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 (OPTT) + solutions. We rely on this property argue that as long as our algorithm (initialized using the tensor PCA method described above) does not have as its iterate a vector with ((PPT) + loss, the distance between the iterate vector and the target vector must contract. As a consequence, this algorithm converges in (log (1/e)) iterations.
Optimization
Riemmanian minibatch SGD on
This argument parallels the line of work [MBMI8] DGK + 20 WZDD23 ZWDD24] on addressing learning of single-index models by proving structural, optimization- -thory local error bounds that bound below the growth of 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 considered in this past work.
2 Initialization Procedure
In this section, we show how to get an initial parameter vector w such that w w = co for some small constant cp- The main technique is tensor PCA algorithm that finds the principal component of noisy degree-k-Chow tensor for any k", as long as OPT S oe Such a degree-k Chow tensor is defined by C₁ = DlyHH (x)], and we denote its noiseless counterpart by
C
lo(w" (x) = N~
E
E
Σ oj (x), w Hex(x)]. j2k
x
Furthermore, let us denote the difference between Cs and Cj by
H& == C - C =
(x.0) En - o(w" x) Hx)
[(v
Note that since Hc is symmetric tensor for any x, all C₁,, Cj. and H2 are symmetric tensors. We use the following matrix unfolding operator that maps k-tensor T to matrix in Rd'' xa=
Mat(r,k-)) (tz 11144...4000 1)d-111---- Jit -1-1 (T) fa....
for all ..,.... it........ jn- E [d]. We also define the 'vectorize" operator and "tensorize' operators,
which map a vector RRd to an I-tensor for any integer 7, and vice versa. In detail,
Tensor(v) (v)i V 1)d4 +(4 11)d'1, Vii,...,K E [d]. Vec(v 31 ) 1)d+ +(1-1)d 1)d' = Vs, Vi, Vas Vig...., in E [d].
Finally, given vector v E of we can also convert this vector to matrix of size dddd 1
Mat (v)i = Vi+ (f1 - 1)d+ io..tt........... -h-- 1)dd'1,, - E [d].
Throughout this section, we take I : [k/2]. We leverage the tensor unfolding algorithm proposed in [M14], which can succinctly be described as follows. First unfold the degree-k Chow tensor
5

---

Algorithm 1 k-Chow Tensor PCA
1: Input: Parameters E, k, Eo. Ck Bs > 0: Sample access to D
2: Let = [k/2]
3: Draw n = (e d ((E)) + 1/e) samples ((x(1, y |= from
4: Construct M == (1/n) E== (n (v Hex (x()) compute its top left singular vector V
5: Compute the top-left singular vector ii of the matrix Mati,--1
6: Return:
to matrix in Rdd xd== and find its top-left singular vector E IRd" Then, we calculate the matrix (It)1, (v), and output its top left singular vector u.
Our main result for initialization is that the output of Algorithm I significantly correlates with w Proposition 2.1 (Initialization). Suppose Assumption / holds. Assume that OPT (64k= and let 6D = Ck- Ck-/ (256kk)) Then, Algorithm I applied to Problem 1.7 with i = k- uses n. (((K)) e log (Bafe)dlk 12) (1g + 1/e) samples, runs in polynomial time, and oulputs vector w such
such that w w 221 1 m31mmin1/k",171
We remark here that Algorithm cean also be used find approximate solution of 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 Appendix D)
In the remainder this section, we sketch the proof of Proposition 2.1 which relies on two main ingredients: (1) alignment of the left singular vectors of 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, that "population" properties the k-Chow tensor to computable empirical quantities.
k-Chow tensor and the
translate
Signal in the k-Chow Tensor Our first observation is that for any left singular vector v of Mat (C&), the singular value p(v) close to the inner product between v and Vec(w (@1), where k/2]. Concretely, we have:
Lemma 2.2. Let v be any left singular vector of Matir,--1) (C²). (Ck). Then, lp(v) -cv cce))cc ( @1) (l).)) s VOPT.
Proof Sketch of Lemma 2.2
Recall that the singular value of the left singular vector satisfies
p(v) max rERuE ||rla==1
Mat (Cc)) PER
max ||||||=1
(Ck, Tensor(v) 6 Tensor(r)).
where we used Fact C.1 (2) in (t). Since C₁ C Hg, further have
(Ca, Tensor(v) @ Tensor(r)) (C2, Tensor(v) (v) @ Tensor(r)) + (Ha, Tensor(v) & Tensor(r)).
We bound both terms above respectively. For the first term, plugging in the definition of Cj and using the orthonormality property of Hermite tensors Fact C.3) and basic tensor algebraic calculations,
(C Tvnsor(v) @ Tensor(r)) = cu (Vec(w (81). (Vec( - (..)))))) r).
(2)
Next, for the second term, after applying Cauchy-Schwarz inequality, one can show that holds
H Tensor(v) < Tensor(r)) S
< Tensor s VOPT.
(3)
Combining Equation (2) and Equation (3) we get that the singular value of v must satisfy
p(v) 5
max
Ch (Vec(w*8l) (Vec(w (kw)) + VOPT
reRa* |||||==1
= cx c 01) v) + VOPT,
where in the equation above, we used the observation that as |Veccw 84 11 w 0k- r 1,
it holds max max |||||]==1111 (Vec(w**kk)) r) [| ( = 1. Since Equation (3) implies
(Ha, Tensor(v) @ Tr))or(r)) > - OPT, similarly we have p(v) 2 cs cx(V (Vec SS) v) VOPT. completing the proof of Lemma 2.2
A summary of useful algebraic properties of the unfolded tensor is provided in Fact D.
Appendix D

---

Lemma 2.2 implies that the top left singular vector v aligns well with Vec(w*Sl). The full version of ooooollyyyy 2.3 is deferred to Corolllryy D.5
Corollary 2.3. The top left singular vector v² E TRd of the unfolded tensor Mat (C+) satisfies
v" Vec((=*)) 2 1 (2/OPT)/ck
Concentration of the Unfolded Tensor Matrix Let us denote M = Mat (v )))(x
i E [n]] and M Ei= M which is the empirical approximation of M Mat(u.-n((C.)) = Mat(.a-o) (E (x(x)))> Heg (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 w**)., ). 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 @!) 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 s theorem (Fact D.6). Wedin's theorem states that sin(O(v", ()) can be bounded above by:
sin(O(v", V*)) S ||M - Mlla/(pi p2 - ||M Ml12),
where P1 and P2 are the top singular values of M. We prove in Claim D.7 that pl - P2 2 (o. - 8VPPT)22 Z C under the assumption that /OPT S ck. hence p1 P2 is bounded below by constant. Thus, our remaining goal is to bound the operator norm such that ||M - |MMM||2 S co where 6p > 0 a small constant. This can be accomplished by applying recently obtained matrix concentration inequality from [BvH22 DPVLB24] (stated in Facc D.8). with additional technical arguments. Plugging the lower bound on the singular gap /1 P2 and the upper bound on the operator norm |M- MIl2 back into Wedin's ss 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 e, > O. Con- sider the unfolded matrix M = Mat (E (x.))) [yH (x))) and its empirical estimate M = (1/n) Em= Mat (ex( where {(x(0, ( ) are n = Oee (Ba/e) (Ba/))d*/2 ) /2/
1/c) i.i.d. samples from D. Then, with probability at least 1 cxp(-d)/2). IM M| S cD-
Moreover, if is the top left singular vector of M. then with probability at least 1 - expl exp(-d!13)
260
G+ .eceec wo @1) 2 VOPT C
(ck/2 4VOPT) cD
After getting an approximate top left singular vector V E Rgd of Mat -1) (E( (x)]). the final piece of the argument is that finding the top left singular vector of the matrix (at (V²) completes the task of computing vector that correlates strongly with w Concretely, we have:
Lemma 2.5. Suppose that V Vec(w" 000)) (o0)) 2 1 - 61 for some 61 E (0, 1/16). Then, the top left singular vector u E I of (at(L.-1))("))) satisfies u w" > 221.
Since VOPT S cx- (6-/(()k*) S cx- /64, choosing 6o = Ck- (256k2) S c+- /256 in Lemma 2.4, we obtain that using n = O(kk')ee log" (2/e))(k/22/((())) + 1/c),
Proof of Proposition 2.1
holds with probability at least 1 - (22) that
2 -
2e0
Vec(w w 31 2 1
VOPT
21
Ck
(cx/2 4v /OPT)
ED
16k
Then applying Lemma 2.5 with 6 1/(16k*) S 11/16, we get that the output u of Algorithm
satisfies u w 21 26 1- 1 1/(8k*) 2 1 minn completing the proof
3 Optimization via Riemannian Gradient Descent
After obtaining w from Algorithm we run Riemannian minibatch SGD Algorithm 2 on the 'truncated loss' (see defimition in Equation (5)) In the rest of the section, we first present the definition of the truncated L3 loss Lg and its Riemannian gradient and then proceed to proving that Algorithm 2 converges to a constant approximate solution in (log((/e)) iterations. Due to space constraints, omitted proofs are provided in Appendix E
7

---

Algorithm 2 Riemannian GD with Warm-start
I: Input: Parameters ,, Ck-s B4 > 0; I, my Sample access to D.
2: w Initialization (,, k" Ck Ba, Co = Cke (256kk) Algorithm
3: for t= 0, 0,...,T-11 do
4: Draw n de log + (Ba/e)/ (E)) samples from D
5: g(w") 1 Sim1 h ke--y(0(( w (w*) ( (x(x), (w*) (ww)ok" -1)
6: w (w' ng(w") ng(ww))//llw) ///lw/ n)((w)))
a
7:
Return: w"
3.1 Truncated Loss and the Sharpness property of the Riemannian Gradient
Instead of directly minimizing the L3 loss L3 work with the following truncated loss that drops all the terms higher than k" in the polynomial expansion of a:
(w) = 2(1
E
[uo(w x)]), where o(w x) = -(He (x), w yook"
(5)
(x.y)~/D
Similarly, the noiseless surrogate loss is defined as (w) = 2(1
E lo(w" x))(w x)l) = 2(1 - c (w w w²)"").
(6)
(x.y)~>
can be shown (using Fact C.1 (C) = 2
2)) that the gradient of the truncated L3 loss equals:
Vol( x)yl = -2 E
[k"c Ck- (HHy(H (x), w 20 -1)]
(7)
(x.
(x.g)>-
while for the gradient of the noiseless L2 loss we have
V L (w) -2
E [K* cw-" (HO (x),, w
(8)
(x.D)~>
Recall that P Pw! = ww! T. Then the Riemannian gradient of the 12 loss Cg. denoted by g(w) () is
g(w) = Pw (V 2
E kyyP w/ (Heg- (x), w 88 ->>]
(x.y)
Similarly, the Riemannian gradient of the noiseless L3 loss C is defined by (He (x), w="'-11)
g" (w) Pw- (VC2 (w)) 2 E
x)P Ik'oww"--
(10)
(x,y)~D
We first show that g" (w) carries information about the alignment between vectors w and w Claim 3.1. For any w Sd-1 we have g" (w) -2k ck (w
w*)""-I(w")>>
Let us denote the difference between the noisy and the noiseless Riemannian gradient by {(w). i.e. 5(w) == g(w)- g" (w) -2 E(x.))=Dl( o(w" P Vo(w x.). We next show that the norm of E(w) and the inner product between E(w) and w are both bounded.
Lemma 3.2. Let E(w) = g(w) - g" (w) as defined above. Then, [lE(w)lla s 2k VOPT and (E(w)- wo| S 2k* C Ck- / /OPT](("") 1w 1l2.
We are now ready to present the main structural result of this section.
Lemma 3.3 (Sharpness), Assume OPT I c/c4)² for some small absolute constant < 1. Let E Sd-1 and suppose that w w 2 1/k Let 0 = 0(w, w) If sin 0 2 4evOPT, then
g(w)- w < -(1/2)]lg (w)llainn 0.
Proof. We start by noticing that by Claim 3.1 the noiseless gradient satisfies the following property:
g"())- w' = -2h" Ck- (w w -[][(=[[[)))) = -llg" (w)ll2 0,
where we used that since ||w || 1, we have ) ||2 sin Furthermore, applying Lemma 3.2 we have the following sharpness property with respect to the L3 loss:
g(w)- w g" (w) w + {ww) w < -(llg" (w)ll 2k ck. VOPT) sin
(11)
Observe that (1 1/t)--1 1 1/e for all 2 1. Therefore, when w w 2 1 - 1/k", we have Ig" (s'(w]l2 2k" ck- (w- W - sin 0 2 21 ck- (1 ) > sin 0 2 e k Cx- sin 0. Hence, when sin 0 2 4e 4e/ and w w 2 1 - 1/k", we have lg((w)) (w) > c / VOPT.
Thus, long sin 0 2 4ev OPT, we have that g(w) w - = [llg(ww]l (w)l sin

---

3.2 Concentration of Gradients
Define the empirical estimate of g (()) as g(w) == (1/n) Ei= ck 12x-g(00 P (Heg- (x()). woek' -!). The following lemma provides the upper bounds on the number of samples required to approximate the Riemannian gradient g( g(w) by g(w).
Lemma 3.4 (Concentration of Gradients). Let w", W E gd-11 Let ((w) be the empirical estimate of the Riemannian gradient. Furthermore, denote the angle between w and w by 0, and denote
R = (k** ) log" (Ba/c). Then, with probability at least 1 - 6, it holds l(ğ(w) - g(w)l22 v dk/((n), and (B(w)- -g(w)) w S v sK/((nd)sin 0.
3.3 Proof of Main Theorem
We proceed to the main theorem of this paper. It shows that using at most @(d /2] + d/E) samples, Algorithm 2 (with initialization from Aogoorittt 1} generates a vector w such that L3 (W) O(OPT) + c within Oglo((1/6) (c)) iterations.
be ter T = OeC log""+ (Ba/e)/(Eô)), and choose the step size n 9/(40ek* c..). Then, af- iterations, with probability at least 1 - 6, Algorithm 2 outputs w with C (W OCC2. OPT) + C. The total sample complexity of Algorithm is N @((K// PEe log" (Ba/e)d W + eC log" k +2 (Ba/c)) (.)
Theorem 3.5. Suppose Assumption 1 holds. Choose the batch size of Algorithm
Proof Sketch of Theorem 3.5] Suppose first that OPT 2 (ek- (ox-/64k*),, then by Claim E.7 we know that any unit vector (e.g., w e1) is constant approximate solution with (w) O(PPT). Now suppose that OPT S (ck- /64k"/4k") ) Consider the distance between w' and w after each update of Algorithm 2 By the non-expansive property of projection operators, we have
||w w 12 = |rrojs ( (w* - n/g(w)) - w 12 S || - ng((w) - w=
= Iww - w "0112 + (//((w)) )- (w- - w') + 1/ (B(()((()
(12)
Let 0: 0(w', w*). For the chosen batch size, Lemma 3.4 implies
l(x(w') - g( g(w") > S (x=*'x+) )²e, (g(w') g(w")) w- S ve/dsin 6..
Assume for now that sin Og 2 4eVOPT + Ve. hence Lemma 3.3 applies. As g((') (w" - -w") = (g(w") ) g(w")) w g(w") w", using Lemma 3.3 we get
g(w") (w* w") S Ve/dsin 02 (1/2)]l (w") 1| sin Oz.
(13)
On the other hand, the squared norm term [gg(w)) 1| from Equation (12) can be bounded above by g w 112 < 21(@(w') - g(w") 1 + 2 21 w 112 S (k' (k-c ( + c) + llg (w)
(14)
Plugging Equation (13) and Equation (14) back into Equation (12) we get that w.p. at least 6, | w 11 |w' w 11 + 2m( (enVe//d l|g (w") (w') 0l22/2) sin Og
r ((K ck (OPT + +c) + llg (w(ww 1[2).
(15)
Let us assume first that 0g < 0 ... S 6g and sin 0, 2 4evOPT + Ve, then we show that
holds 4.41 S Hg. Recall in Claim 3.1 it was shown that ||g (w')) )|( : = 22k ck- (w' - w-)*"-1 sin 0,. Since w is the initial parameter vector that satisfies w"... w 2 1 1/k,,, by the inductive hypothesis it holds w w" 2 1 1/k=" and hence 2 (w" w1 2 1/e. Therefore,
further obtain (2k" Ck- /e) sin Og < l|g (w'')ll2 I 2k*c ct- sin 0z. Therefore, using the inductive assumption that sin Og 2 4PV + Ve and further noticing that | w"ll, = 20in((,/)), with step size 17 9/(40ek* ck-) we can further bound |w*+ w" in Equation (15) as:
||w ++1 w' 112 & (1 (81/ (320(
[]] w'
(16)
This shows that 0,+1 I 0,, hence completing the inductive argument. Furthermore, |Equation (16) implies that after at most T (llg(1/e)) iterations it must hold that sin 0r < 4eVOPT + Ve. therefore, we can end the algorithm after at most (loo know that this final vector w' T has error bound [g(w") " = O (OPT + +)). Thus, choosing é' = Ck- e, 8' = 8T, where T = Olog Cz- Cx- /c))), (Agoorin 2 outputs a parameter w" such that with probability at least 1 - 8', L2 (w O(22- (Pkx-OPT) é', with batch size n ((d/(<8))) In summary, the total number of samples required for Algorithm 2 is N O(d /21 + d/((8"). L
iterations. Applying Claim E.7 we

---

Acknowledgments
PW was supported in part by NSF Award DMS-2023239, NZ was supported in part by NSF Medium Award CCF-2107079. ID was supported in part by NSF Medium Award CCF-2107079 and an H.I. Romnes Faculty Fellowship. JD was supported in part by the Air Force Office of Scientific Research under award number EA9550-2441-000 contract number N00014-22- 1-24-4 Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the U.S. Department of Defense.
and by the U.S. Office of Naval Research under
References
[AAM23] E. Abbe, E. B. Adsera, and T. Misiakiewicz. Sgd learning on neural networks: leap complexity and aaddee-tossadle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552 2623.. PMLR, 2023.
[ADGM17] Anandkumar, Y. Deng. R. Ge, and Mobahi. Homotopy analysis for tensor pea. In Conference on Learning Theory, pages 194104. PMLR, 2017.
[AS68] M. Abramowitz and A. Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1968.
[ATV23] P. Awasthi, Tang, and Vijayaraghavan. Agnostic learning of general ReLU activation using gradient descent. In The Eleventh International Conference Learning Representations, ICLR, 2023.
[BAGJ20] G. Ben Arous, R. Gheissari, and A. Jagannath. Algorithmic thresholds for tensor pca. The Annals of Probability, 48(4):0052-2087, 2020.
[BAGJ21] G. Ben Arous, R. Gheissari, and A. Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1-51 2021.
[BvH22] T. Brailovskaya and R. van Handel. Universality and sharp matrix concentration inequalities. arXiv preprint 2rXiv:2201.05142, 2022.
[CCFM19] Y. Chen, Y. Chi, Fan, and C. Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176:5-37, 2019.
[CLS15] E. Candes, X. Li, and M. Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 1885:207722 2015.
[CM20] S. Chen and Meka. Learning polynomials in few relevant dimensions. In Conference on Learning Theory, pages 1161-1227. PMLR, 2020.
[DGK+20] I. Diakonikolas, S. Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi. Ap- proximation schemes for ReLU regression. In Conference on Learning Theory, COLT, volume 125 of Proceedings of Machine Learning Research, pages 1452-1485, PMLR, 2020.
[DHI8] R. Dudeja and Hsu. Learning single-index models in Gaussian space. In Conference on Learning Theory, COLT, volume 75 of Proceedings of Machine Learning Research, pages 1887-1930. PMIR, 2018.
[DH21] R. Dudeja and D. Hsu. Statistical query lower bounds for tensor pea. Journal of Machine Learning Research, 22(83):1-51) 2021.
[DJS08] A. S. Dalalyan, A. Juditsky, and V. Spokoiny. A new algorithm for estimating the effective diddnsionn subspace. The Journal of Machine Learning Research, 9:1647-1678, 2008.
10

---

[DKPZ21] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polyno- mial regression for agnostic learning under Gaussian marginals in the SQ model. In Proceedings of The 34th Conference Learning Theory, COLT, 2021.
[DKR23] I. Diakonikolas, D. M. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginals. In ICML, 2023.
[DKTZ22] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning single neuron with adversarial label noise via gradient descent. In Conference on Learning Theory (COLT), pages 4313-4361 2022.
[DKZ20] I. Diakonikolas, D. M. Kane, and Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[DLS22] A. Damian, J. Lee, and M. Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference Learning Theory, pages 5413-5452. PMLR, 2022.
[DNGL23] A. Damian, E. Nichani, R. Ge, and J. D. Lee. Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. Advances in Neural Information Processing Systems, 36, 2023.
[DPVLB24] A. Damian, L. Pillaud- Fillaud-Vivien, J. D. Lee, and J. Bruna. The computational complexity of learning gaussian single-index models. arXiv preprint arXiv:2403.05529, 2024.
[FCG20] S. Frei, Cao, and Q. Gu. Agnostic learning a single neuron with gradient descent. In Advances in Neural Information Processing Systems, NeurlPS, 2020.
[FFRS21] A. Fiorenza, M. R. Formica, T. G. Roskovec, and F. Soudský. Detailed proof of classical gagliardo- nirenberg interpolation inequality with historical remarks. Zeitschrift für Analysis und ihre Anwendungen, 40(2):217-236, 2021.
[GGK20] S. Goel, A. Gollakota, and A. Klivans. Statistical-query lower bounds via functional gradients. In Advances in Neural Information Processing Systems, NeurlPS, 2020.
(GGKS23) A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[Hau92] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78-150, 1992.
[HJSO1] M. Hristache, A. Juditsky, and V. Spokoiny. Direct estimation of the index coefficient in single-index model. Annals of Statistics, pages 595-623, 2001.
[MM+00] W. Härdle, M. Müller, S. Sperlich, A. Werwatz, et al. Nonparametric and semiparamet- ric models, volume 1. Springer, 2004.
[HSS15] S. B. Hopkins, J. Shi, and D. Steurer. Tensor principal component analysis via sum-of- square proofs. Conference on Learning Theory, pages 956-1006. PMLR, 2015.
[HSSS16] S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. Fast spectral algorithms from sum- of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 178-191, 2016.
[Ich93] H. Ichimura. Semiparametric least squares (SLS) and weighted SLS estimation of single-index models. Journal of econometrics, 58(1-2):71-12) 1993.
[KSKK1]] S. M Kakade, V. Kanade, O. Shamir, and A. Kalai. Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011.

---

[KS09] A. T. Kalai and R. Sastry. The isotron algorithm: High-dimensione isotonic regression. In COLT, 2009.
[KSS94] M. Kearns, R. Schapire, and L. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2/3):115-14) 1994.
[MBM18] S. Mei, Y. Bai, and A. Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018.
[Rah17] S. Rahman, Wiener-hermite polynomial expansion for multivariate gaussian probability measures. Journal of Mathematical Analysis and Applications, 454(1):303-334, 2017.
[RM14] E. Richard and Montanari. statistical model for tensor PCA. Advances in neural information processing systems, 27, 2014.
[Ros58] F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386-408, 1958.
[Sol17] M. Soltanolkotabi. Learning ReLUs via gradient descent. In Advances in neural information processing systems, pages 2007-2017, 2017.
[SQW18] J. Sun, Q Qu, and Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18:1131-1198, 2018.
[WZDD23] P. Wang, N. Zarifis, I. Diakonikolas, and J. Diakonikolas. Robustly learning a single neuron via sharpness. 40th International Conference on Machine Learning. 2023.
[ZWDD24] Zarifis, Wang. I. Diakonikolas, and J. Diakonikolas. Robustly learning single- index models via alignment sharpness. 41th International Conference Machine Learning, arXiv preprint: 2402. 17756, 2024.
12

---

Supplementary Material
Organization The appendix is organized as follows. In Appendix A, we provide a detailed discussion about our assumptions on the activation functions. In In|Appendix B we compare our results with the most related prior works. In In|Appendix CJ we provide additional preliminaries on basic tensor algebra as well as Hermite polynomials and Hermite tensors. In Anpppeddi D and Appendix E we provide full versions of Section and Section 3 respectively, with omitted lemmas and proots.
A Remarks on the Assumptions
Assumption 1(i) appears the same form BAGJ21 DNGL233. The remaining two assump- tions are implied by [o'(z) S. A|=|4 + B for constants A. B, q. assumed in these works. In detail, Assumption (ti can implied from d=()) S A| + B using the Gaggliardo-iirebeer inequal- ity [FFRS2I]; Assumption l(ti)) follows from direct calculations as Es-Mi [[A22/4 + B) is finite. Hence Assumption ! is no stronger than the assumptions made in prior work, which considered the less challenging realizable and zero-mean label noise settings.
Some activations satisfying Assumption are:
1. All '(a, be-well-behaved" activations [DGK 20 DKTZ22 WZDD23 that are non-decreasing,
zero at the origin, b-Lipschitz and az))) 2 a when = E [0, R|] satisfy Assumption with k
(see Claim A.I. This includes ReLU, (=) max[0, 2} and sigmoid, or=) - e5).
2. Activations for phase-retrieval information component k.* One can verify that they satisfy Assumption aafter normalization.
CLSIS CCFM19 SQWI8): a(2) 2² and ((2) | have
Claim A.1. Let a, b, be some absolute constants. Let IR + R be an activation such that it is non-decreasing, b-Lipschitz. and satisfies (0) = 0 and of (z) 2 for all [0, Rt.. Then satisfies Assumption Tiit information component k²
Proof. We calculate the Hermite coefficient ei of a:
= E (a (z)= E [o(z)=]= zn-N1
2 0}}
E (=)) z
zー~,
(1)
E [o())\1 N~~,
011 E 2~~,
(a 10=221(2
[0, ス RR exp(-R").
where in (i) we used the monotonicity property of a and that (0) 0. Thus we get that all well- behaved activations as E 1. In addition, the Ez-Mi [x) < Es-Mi [b²=3] < b2, hence after normalization, have e₁ Z alt exp(-It)) (2b²), which is an absolute constant bounded away from O. Finally, we have (=))) < 364 and (=>AA[((((>>)) < 6 since a is 6-Lipschitz Thus, have that all well-behaved activations satisfy Assumption
B
Comparison with Prior Work
B.1
Comparison with Prior Works Agnostically Learning SIMs
A long thread of research has been focusing on agnostic learning of single index models, includ- ing [FCG20 22 DKT722 WZDD23 ZWDD24]. A common assumption on the activation function a used in these works is the so-called "well-behaved" property, namely that a is non- decreasing, zero at the origin (o) 0), b-Lipshitz, and d'(z) 2 when z E [o, R]. In particular, ReLUs and sigmoids are well-behaved activations. For well-behaved activations, we have shown in Claim A. that they have K* and satisfy AAsumptiin Therefore, we conclude that our assumption Assumption is indeed milder compared to prior works.
We also note that Asau/mssuptioon 1 allows for non-monotonic activations as well, for example (() 2² and o ((2) = |2| satisty Assumption I with h= 2.
At the level of techniques, the algorithmic approaches in the aforementioned prior works on agnos- tically learning SIMS [FCG20 [DKK +2 WZDD23 inherently fail in our more general activation setting. The main reason is that the underlying algorithms only exploit the information in the degree
13

---

1-Chow parameters, However, under Assumption 1 with k- 2 2, the inner product between degree 1- 1-Chow vector and any unit vector v equals E ((x.))>D [yx] v S vOPT 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 distribu- tions (including the Gaussian distribution), such as log-concave distributions.
B.2 Comparison with [DNGL23
The work by [DNGL23 applied smoothing operator to the I.2 loss inspired by ADGM17]. For any function f: I IR, let the smoothing operator
xz|12 x }
Az
gx x))
E Pow
/
[|w
[|w
where z ~ Hw is the uniform distribution on the sphere S that is orthogonal to w, and is the "smoothing strength'. Applying the smoothing operator the loss we get
w Az
>
(x(w)= = 1 E Hw
E
yo
x
(x.))~D
Az112 2
and
W + Az
(x(w; = E
yo
w + Az|12
Pie
The main algorithm of [DNLL23 is online Riemannian gradient descent algorithm the smoothed loss (w().
The dynamics of the online SGD algorithm in [DGLL23] can be split into three stages: In the first stage, starting from a randomly initialized vector w such that w w" O(d-1/3), the algorithm used a large smoothing operator with À = dz/4, Then, after Ö(dk /2-1) iterations the algorithm converges to a parameter w such that w w-- 2 d-1/4, Then, in the second stage, with zero- smoothing À = 0, they run the algorithm for another 0(d""/2-1 iterations and get a parameter w2 such that w2. w* 2 1 - 1-14 In the third stage, online SGD converges to w with w w 2 1-6 d/e iterations.
However, the smoothing technique does not work 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 gx (her(w w x)) = (Heu (x), Tw())), where
[2/2]
Te(W): = (1 + x2)4//2
Σ
k
Sym(w 8k-2j (P&) ))A35
2j
1=0
and /
(d-1) Ee- 12 -((d-1)-))) O(d-)). Note since the smoothing operator is a linear
operator, it holds that L3 [2(w) = 1- 1-E (o (o = 1- -E(x,))>(l) ΣaZK- C&dx (hen
x)) 1 (xx,))>DD 1y E k2k c (H)) Tw(w))] Let (w) = P (W((w) denote the
Riemannian gradient of Lx(w)) (w). have
gx (w) w'
E
y
Σ aa (x), (w) k>b
(x
E (
a(w" x)
Σ
Ck (ee (x), VTx(w) (w
k2k
Iz
E (x,0)D
(y
o(w" x))
Σ ck (X),(x), VTk(w) @ (w))
(17)
We show that the noise term Ig kills the signal term Z, in the beginning stage when w-w" w-w"= 0(1/Va)
and A d/1
14

---

Claim B.1. When w. w" = @(1/Vd) and À = d//4. it holds
Zi S d k' /2 [ VO
Thus, in order for the signal to overcome the noise, one requires OPT S d= which is too strict to hold in reality.
Proof of Claim B.1 Following the steps in Lemma 12 in DNGL23 VT; (w) @ (w*) - equals:
VT (w) @ (w") (w")
k (1 X2)k/2
(k-1)
Sym Sym(w @k-
2 p @ (w*)+ -w 220
2j
1=0
!
A²k(k 1)
Sym 8 60 p ) 8 (w*) 'n 225 (atz)
(d - 1)
2j
Plugging the equation above back into Equation (17) we study each term [I]] and [,y] respectively
in the beginning phase when w w = O(d 1/2).
Using
Fact C.3. and recall that in DNGL233 À is chosen to be x d/// and v/
(d-1) O(d-2).
(d+1) (d 2) by definition, In equals:
|Z|| Σ &f Sym(w (8k, ), Sym(SyyTVV. 80 (w*)!w)
R26
ek
h
k-1)
(h)) - (w. w (=)))"[((("")) 112 d5/2
(w w
+ X2y8/2
2j
d'
j=U
( 1)
kk (k-1)
1)
(w -w (w w 1312
Σ
1d-1)(1 1)
2j
d=
k>
1=0
k - 1)
d (k- 23 1)/2 d:/2 d//2
d
2j
d-j
1>k
1=0
ck(k
( k 1)
d (k-2j 2j 1)/2 d
Σ
\/111/2
2j
d=
1
1=0
2
kkkk
2/22/2213
2t
/
db/2+1/2
k
1=0
(181
db/4
db/4+1/2
(kcx) 22 22k d k/2 &
Σ 4/2 k2k
k/2 Z 4 12
k2k
(d-1) (d+1)) in (ii) we plugged in the value of where in (i) we plugged in the value of X and 2/ 12j
w w" = =1/vd; and in (iil) we used the fact that (9) < 2 However, the magnitude of the signal from I is much smaller compared to the strength of the noise, [2], as by
we
15

---

have
(1v)
[
VT&(w) (vr)))))) #
T2
E (x,y)n/
[y o(w" x])=] x~Ni
E.
Σ
c
(He
k2k
S VOPT
2 V @ (w*) w ||
Note that in Lemma 12 DNGL23 was proved that
[T&
@ (w") (=))==13 11
2
22
k -
X (d-1)
2
+ de 22)*
(1+
22
2j
2j
j=0
2
1
dž
d
where in (v) we plugged in the value of A and (d-1)) yatt). /
1/j
Thus, it holds that
1/2
[2l S
VOPT
Σ a
S VOPT2 d'11/4
Finally, we remark that the equality holds at (iv) when
VOPT
oww x)
Σ
ca (He(()), VT (Tx(()
V EEZD of (w) & Iw 1 1
k2k"
B.3 Comparison with [DPVLB24]
In [DPVLB24], the authors studied a milder noise model than the agnostic setting. In their model, the joint distribution (x, y) is defined Eyfy x] = a(w" x) + E(w" x), where : IR - R is assumed to be known to the learner. Note that in this model the labels are independent of all the directions orthogonal w i.e., the random vector - is independent of y. In comparison, in the agnostic setting, the distribution of the labels is E, x] oww" x) + c'(x). where 5' IR - IR 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 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 a, [PVLB24] considered the generative component of the label y, which is defined as k= == min {Aa > 0}. where A == /EyIC? and (v( == Ez [he [z)] The main results in DDVLLB24 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 /2) samples to learn the hidden direction w*. Then, they provided an SQ algorithm using partial-trace operators that
1 - with O(dk + d/e²) samples, matching the SQ returns a vector w such that (w- w+)² > lower bound.
The algorithm proposed in [DVLLB2]] can be described in short as follows: given joint distribu- tion P. calculate Çz- (y) and transform the label y to Gū- (2). Then, they applied tensor PCA on Se- He)))x using the partial trace operator and tensor power iteration.
We note that the partial trace method for tensor PCA fails to find initialization vector w such that w w" 2 c for some positive absolute constant c under agnostic noise. We explain this briefly below. For simplicity, let consider & being even. Note that for k-tensor T with even k, the partial trace operator is defined by PT(T) (T, (kk-2)/2)
where I is the identity matrix in dxd The idea
16

---

in [DPLLB24] and [DGMM7] is to use the top eigenvector E R'' of PE He (x]])
as warm- start. However, we show that under agnostic noise, this eigenvector vi does not contain strong enough signal to provide information of w*. Note that by definition of the partial trace operator, for any E Ba we have
PT
E (x))v= E JVv (x), 22(k-2)/2/v) (x,))
(18)
(x
I (x), 2)/222/2 8 2
(x.0)=-
E [o(w" x) (x)) 8 2 v8 x-iNa
E I(y o(w"' (x) 8(k-2)/2 ) (x.y)>D
=q(w 10(k-2) 2 2
E
[yy
o(w" He, (x). 10(k-2)22 @ vo (19)
(x.))D
The first term in the equality above equals ca (w (w (8(k 2)/2 v@2) cs (w* v) however, the second term can be as large as (by Cauchy-Schwardk
E ly a(w" (He pk(k (0(k-(1)))))))) 2)/2 & v82)
(x,))
E [y - a(w x}) E (H)) [8(k 2)/2 & v (x
x
[ 2//2 & v* ||
2-2/4
As suggested by inequality (i) above, let be any unit vector orthogonal to w consider agnostic noise model
o(w" x) (VOPT/d (He 1
(He (k 2)/2 @ 22)
then E (xxx)) 1(v- - or (w" x) OPT. However, we can see from Equation (18) it holds that
(w") (w") PT( E
(x)))
(x,y)>
VOPT
= + 2)/4
(Hok (x), 10(k-2)22 02) (H), (8(k-2)/2
22/222222220 & (w*)
(x.
VOPT
(Sym (I 22/2 30 v Sym(SSSmSSSsaam 2)/2 s (w*)82))
+
2k/4
(1)
VOPT
S + d(k-2)/²
c + 41-32/ (k-4)/2
where (ii) comes from the fact that for any permutation æ such that (T(11, mT2) + Ø, since 1 w", it holds
Σ Vi, Vi, wieny Minca Light In 1 Pepondac Ii = 0;
and on the other hand, when (I(1), (2)) n [1,2] = Ø, then
Σ
Vi Wi Wo w Wiog I Ii ... I 1 I micea d(k-4)/2
To see this, note that there exists chain of identity matrices
I po +1) I di I (eteo) L bu
I Li dsmtt
such that x(a1) ( + +1) ji. fi +1 (az), (aa + 1) = je... until have iz(am+11)
(i1, i2) ijm+1 E (in(1); (- ). For the latter case, it implies that
Σ Vi, )'n"))sm+ II dntee L an L Ie detegtt) Ligaita Iimmsta
Σ Vi, (w") );; =0.
17

---

Therefore, only the first case is interesting. Since ({11) = 1. and i is a bijection, hence π (am (1m+1) #
therefore the only possible case would be (z(am.)) +1) 82. then we have
Σ Vi (ir(om+t1) df di (e dig liccom)itrtmmtt
Σ Vi 1.
Continue the discussion for Viz, w witm: and w wiees and let {js. Ja. Ik-1, = fii....,ik (in, 22, (x1))=((22) we get that
Σ Va, Via Wier) Whay Lisd Lo de dopo
... ...I 1)
so 12 12
Jo...e=11 dlk a(k-4)/2_
Similarly, for any unit vector
v and u w", it holds
PT (x)(x)) VOPT6/4-3/2
But one can also show that
VOPT
PT (HH(())))+
(He (x)) 10(k-2)/2 & v
(x,))D
2)/4 (x.D)/D
VOPT
|Sym ( 2) v82)
d 2)/4
2 4/112//
This implies that to guarantee that w the unique top eigenvector, has to be that OPT odd 2)/2 Therefore, the noise term completely buries the signal (w" v)² unless OPT 2/25 d' (I- 2)/2, which is unrealistic to assume.
B.4 Remarks on Tensor PCA
We summarize some historical bits of Tensor PCA. PCA problem: given a k-tensor of the form
RM14 proposed the following 'spiked' tensor
T TV A,
(PCA-S)
where A is a k-tensor with i.i.d. standard Gaussian entries, recover the planted vector v. The 'single- observation' model is equivalent (in law) to the following 'multi-observation' model (BAGJ20): given n i..d. copies T()) = r'y8k + (i) with =T//n, recover v using the empirical estimation:
x
T T= r 0k
Σ ( n
(PCA-M)
In RM14], has been shown that for model (PCA-S), it is information-theorrtiillll impossible to recover v when 7 < (3i - vd) for some real constant 3 however, there also exists a constant 8% such that the information- optimal threshold for - is > (8) + (a(1)) (see also (DH2I). However, there huge problems and it is conjectured impossible solve (PCA-S) when S d for lo 2 3 [RM14 DH211. For multi-observation model (PCA-M). this thresholds translates to sample complexity of 2 d/2 when r' = (1).
gap for solving tensor PCA
RM14 proposed the tensor unfolding algorithm that recovers v in PCA-S when 2 2dik/21/2 /2 i.e. for (PCA-M), the required sample complexity R(d[4/21). However, it conjectured in [MM44) that the tensor unfolding algorithm actually deal with 2 d/1
Note that RM4 takes different normalization and in the notation of RM14 it holds 9 T/ r/vd.
18

---

Note that the unfolding algorithm requires 7 2 d when k = 3. Many papers are devoted to improving from d to T 2 d//4 and reducing the runtime and memory cost. To name few, HSSTTS HSSS16 used Sum-of-Squares algorithms with partial trace operators achieve the goal within O(d)) 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.
C Additional Preliminaries
C.1 Elementary Tensor Algebra
We review basic definitions and elementary tensor algebra used throughout the paper. For any positive integer k; a k-tensor ' is defined as a multilinear real function that maps vectors to a real number, i.e. T: I2d ... Rd - IR. A k-tensor T can also be viewed multidimensional array, where each entry is associated with k indices i1,-... ig in [d] and equals Ti...... = T(ee......
Given a vector w E Rdd W (Wi..... ( the k-product-tensor w&k is defined by
(w
W. Wa, :. Wast Vii...., ig [d].
Given a k-tensor and an I-tensor T (with / 2 k), the inner product (or contraction) between T and T' is defined by ((T, Tr,,T))) T = Σi, 2i..t...... (T) (TT iT fe.....,,.dd4,,..... In other words, the inner product of a k-tensor and an I-tensor yields an (1 - k-)ttnsor. When h 1, the inner product between T and T is real number. In particular, for vectors v E Rd, and any k 2 1,
(w.v)*,
(20)
where w v is the standard inner product between vectors.
tensor T is symmetric if (T................... summing up all its copies with permuted indices 11,-.., in and dividing the sum by kl, which the total number of permutations. We define the symmetrization operator of k-tensor T by
(T) ................................ We symmetrize k-tensor T by
(Sym(T))
Σ k!
1
When = 2, this reduces to the symmetrization a square matrix: Sym(T) = (T/2) Let us provide some useful observations about tensor algebra.
Fact C.1. Let w E Idd and let be any k-tensor. Then,
(1) The inner product between wh and Sym(T) is equal to the inner product between w ok and T:
(w Sym(TT) = (w (o.k,T
(21)
(2) T is symmetric tensor.
((T, w @h/)) K(T, w wk-11
(22)
Proof. To prove the first statement in Fact C.I. note that direct calculation yields:
1
@w ST)
Σ
Wa
Wie
X(T) (
(T)
K!
MES
Wir() Wi (T) ((c))
El
RES $1....
Σ
Wi. T TTii.. = (wOk T).
Wiy ......,,
19

---

Next for the second statement, let f(w) = (T, w(i) where T is a k-tensor. Then, the partial derivative of f w.r.t. w is
0f(w) 0
(T, w bk)
Σ
(T)
(T)ismnd Wa -.Wi
Wix
Ow; dw,
Jw;
Σ (T) Sitamini Wia
Win +
Σ
(T)i W/y Wis ... Wa,
Σ
(T (T) 1d Wi1
Wiy
Thus if T is symmetric, then ((T,, w(rk) (T,, wilk-
C.2 Hermite Polynomials and Hermite Tensors
We make use of the normalized probabilist's Hermite polynomial, defined by
(-1)
d
2²
(2)
exp
exp
kc!
2
d
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) B2z-N((..))/eexx))ann
( j}.
2. (Recurrence) he/(=) = V 11)=1(=).
Given a vector x E TRdd we can then define the (normalized) Hermite multivariate tensor by Rah17
(Hex ((lexx))) = (o1!... (a!l ord!) hea, (x1) ... hea, (xa), where aj Σ 1 = 1h, Vj e [d]
1/2
k!
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~Na
(H)x(x), A) (He, (x), B)] = 1(k = (Syymm)) Sym(().
2. For any Rdd such that |w|2 ho&(w x) (He(x), w
C.3 Loss and Gradients
We consider the L3 (or square) loss, defined by
C (w)
E (x.1)
(o(w x) - y)
Let w E argmin wig-- (w). Furthermore, let us define the "noiseless" L3 loss by
-- wegetr (w). and denote the minimum value of the L3 loss by OPT
C (w) x~>Na [[o[[ xx) o(w" -))
E
(23)
We observe that the L3 loss is determined by the inner product between w and w therefore, to obtain error ((OPT) +e, it suffices minimize the angle between and w Concretely, we have: Claim C.4. Let w Rd be unit vector. Then, the Liz loss (w) satisfies:
Cg(w) - 20PT 4 1 Σ <l( (i(w-w")) w+))
k2k
20

---

Proof. Recalling that the activation is normalized so that Ex x)] = Ex x)] 1, we can simplify the L3 loss
22 (w) = 2(1
E (wo x)])
(x.y)>
The noiseless L loss admits the following decomposition:
C2 (w) 2(1
lo(w x)o(w".. xi))
x~Na
2
E
Σ
Ck (Hex(x), wor
Σ 12
Ok (x), wAskk
x~Vaa
2 1 - Σ
(24)
k2k
where in the last equality we used the orthonormality property of Hermite tensors (Fac C.3 using Young's s inequality and the definitions of OPT and L (w), we also have L2 2 (w), which combined with Equation (24) leads to
Further,
W S
20PT
Dg (w) < 2OPT + 4 (1 (1-
Σ R2
Ce(w (9)+)
Remark C.5. Equation (24) suggests that even in the realizable case, some assumption on bounded-- ness of ExzRk kej (see Assumption 1 (ii)) may be necessary to have a nontrivial bound the L loss. Consider an algorithm that outputs a vector such that w -w"
a.for some a E (0, 1) (if a= 0. w since both vectors are on the unit sphere). Since Exzg cx = 1, we can also write C22 (w) = Ek c1 (1 a.) ,. For 1211a)), 1- (1-a)* z ka. Thus, if we want an algorithm that works generically for any target accuracy, Σx2I. kež ought to be bounded.
Remark C.6. Even though for ||w]|2 = we have hex(w x) = (x))(x), w.k), the gradients with respect to of these two functions different in general. For example, for k 2, we have
(He(()) (x), w w = (L/V2)((w -Iw-llwl] and hez(w x) = (1/v2)((w x)² 1),
which are equal in function value, but
V (Hez(x), w V2((w x)x w) = 2((He)(x)) w), Vhez(x) = 22(w x)x= = 2he (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 hight-handda side, need use the tensor form of Hermite polynomials, because to ensure interchangeabiligg of differentiation and summation, the sequence needs to be uniformly convergent. Note that Ex-Na 1E C₁ (He (x), w
w ΣxzE. Cy (Hew (x), w w=kk converges to Σe <g(ww w)* uniformly for all E Idd, but the sequence ExnAs (E EkZE- Opher(w x) Σ E2z oyrhew (w= converges to Σx cg(w w)* only when || |||2 = 1, since it requires w (001)) 1) to ensure that Ex--NG [hez (w x x)hhe(w"* xx] [ = )'
As observed in Remark C.6 the gradients of heæ (w x) and (He (x), w are different in general. Throughout the paper, we will be taking the gradient with respect to the tensor form of o o(w x); in other words, Vo(w - x) = V 6 (He (x), w3k)).
D Full Version of Section 2
In this section, we show how to get an initial parameter vector w such that w co for some small constant ep. The main technique is tensor PCA algorithm that finds the principal
21

---

component of noisy degree-k-Chow tensor for any k 2 k", as long OPT X c. Such degree-k Chow tensor defined by Ce (x.y)>= He (x)]. and we denote its noiseless counterpart by
C
E lo(w" x)He (x)] x~~Va
(x)H))(
Hel(x)
x~aNa
j2k
Furthermore, let denote the difference between Cj and Cj by
H₂ Cs C
E (x.y)~>
[yy a(w" Hxx))))
Note that since (x is symmetric tensor for any x, all C₁ Cj and H2 are symmetric tensors.
We use the following matrix unfolding operator that maps k-tensor matrix in Rd xd= Concretely, given k-tensor T, we define:
Ma (T), (66 1)d4 +(u l)d + - 1)d
for all i,,..., n....,,4.... h.. Jx-1 E [d].
For notational convenience, we also define the 'vectorize" operator and 'tensorize' operator, which map vector E IRd an I-tensor for any integer I, and vice versa. In detail,
Tensor(v) (v) V1++(1-1100 1)d4 +(4 1(1-1)d-1 Vi,,... E [d];
and conversely, we define
Vec(v 81 +1a 104- Va, Vi2 ... Vay Vin...., it [d].
Finally, given vector v E IRd", we can also convert this vector to matrix of size Rdx''') Mat (v)
+ 1)d 1, Vi, J1 ................................ j--1 E [d].
Some simple facts the algebra of the unfolded matrix are in order.
Fact D.1. Let be a symmetric k-tensor, and let E Rd .vv Rd Then
1. For any index i E [d"].
(Mat(u.-r)) (T)r); T, ee 3 ... @ eq X Tensor(r))
(25)
where , & [d] satisfies i = 11 (1/2 1)d (t) 1)dt²
2. For any index j E [d
(Matu.x-n)(T [v); = T, Tensor(v) 8 ezz .... (3%
(26)
where Th....,hh-1 E [d] satisfies oi + ... + (ik - - = j.
3. Finally,
v Ma) (T, Tensor(v) 8 Tensor(r)).
(27)
Proof. First we show that for a symmetric tensor T, the linear transformation Mat (T)r
(T)) of
vector r gadd is equal to the tensor inner product (T, Tensor(r)). This can be proved by direct calculations that for any i E [d']:
(Mat,,A-i)(TTr)
Σ
(D +(i-11
in i
Σ
(T) Tensor(T)).....ff
22

---

where ,y....,, o' E [d] satisfies i = (12 1)d + ..... (1) 1)d -1 Observe that the summation above further equals
(M (T)r);
Σ
Σ
Whind Tensor(r) hom 1(1 [n} ... 1iss &f
(1 in Se-odk-leld
= Σ
..... & ex Tensor(r)) T...s
11 M.
eg 8 @ eq Tensor(r))
Similarly, for symmetric tensor T and any vector v Rdd and any index E [d*=1), holds T, Tensor(v) @ ojj x o%
(Mat(,,--)) (T) v),
where jí + .... (/211 1)d
Finally, combining Equation (26) and Equation (25) we get that for any v Rd .r Rd the quadratic form v Mat(I.k-r) (Tr equals v Mat (T)r = (T, (vnsor(v) @ Tensor(r)).
Throughout this section, we define k/2 when k is even, and / = (k - 1)/2 when k is odd. In other words, = [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 Rd xd= and find its top-left singular vector v E Rd"., Then, we calculate the matrix Mat(i,--)((v). and find its top left singular vector u. One can show that this eigenvector u correlates with w significantly.
Algorithm 3 k-CCow Tensor PCA
1: Input: Parameters e, k,
ko co, Ck. B₁ > O: Sample access to D
2: Let = [k/2]
3: Draw n = (c* (Ba/c)d (((2) + 1/c) samples { ((x(") ()) from
4: Construct M == (1/n) Li Mat (y He (x( compute its top left singular vector V
5: Compute the top-left singular vector ñ of the matrix Mata,--(
6: Return: û
Our main result for initialization is the following:
Proposition D.2 (Initialization). Suppose Assumppion holds. Assume that OPT < (i-/(64k*)) and let co c (256k*) ). Then, Algorithu applied Problem 1.1 with k- uses
) 2e log" (Ba/c)alk" /21 (ct))+1/e)
samples, runs in polynomial time, and outputs vector w E gd-1 such that w w- 1 min(1/k", 1/23.
We remark here that Algorithm can also be used to find an approximate solution of our agnostic learning problem; however the dependence on the value of OPT 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 / holds. Assume that OPT & 22- <6-/(64k*) and S 1/64. Let 6n = 116 Then, Algorithm ! applied to Problem 1.1 with k = k² uses O(c log" (Ba/e)a(**/a /cQ. + 1/c) samples,
runs in polynomial time, and outputs vector w E S such that
w w+ 2
VOPT - -2/33.
Ck'
Furthermore, the 122 error of o most
(w 0 Cx- ( -OPT =
23

---

Thus, when OPT = 0 (i.e., in the realizable cases), applying samples recovers the hidden vector w"
Algorithm 3 with 0(d/k//2//
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 = ( (aapg)/wlHHHee HyH correlates significantly with the vectorized 1-product tensor, Vec(w* This indicates that v* contains rich information about the direction of
Roadmap To prove Proposition D.2 Proposition D.3
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. using sophisticated matrix concentration bounds. In particular, in Equation (35) we guarantee that the angle between V and v* is bounded by O(co/ /cx) for any small constant 6D 0. provided that we take (dd /e samples and assume that OPT 2 G.. The inner product between V and Vec(w*88 can then be bounded below by 1 ((VO((((++))))))
Combining with Corollary D.5| this implies that V correlates with Vec(w @01) significantly. Finally, in [emma D.17 we show that after unfolding the RRd vector V an Rx ddxx'=+ matrix, its top-left singular vector correlates with w significantly; it particular, we have w u ž CEg for some absolute constant > O. Combining these results and choosing Eo Ck- /k" we get Proposition D.2, and choosing Eg c yields Proposition D.3
D.1 Signal in the k-Chow Tensor
Our first observation is that for any left singular vector v of Mat (Ck), the singular value p(v) is close to the inner product between v and Vec(w*B1, where / = [k/2]. Concretely, we have: Lemma D.4. Let v be any left singular vector of Mat Then,
lp(v) - ck (Vec(w* @l) v)1 S VOPT.
Proof. Recall that the singular value of the left singular vector satisfies
Ma (i)
p(v)
max
max
(CR, Tensor(v) @ Tensor(r)),
rER |||||==1
FER* [||||:==1
where we used Equation (27) in (t). Since C₁ = C + H., we further have
(C2, Tensor(v) @ Tensor(r)) (C2, Tensor(v) @ Tensor(r)) + (HA, Tensor(v) & Tensor(r)).
We bound both terms above respectively. For the first term, plugging in the definition of C and using Fact C.3
we have
(Ci, Tensor(v)
X Tensor(r))
(28)
E x>>Va
Σ
Cy (Hey (x), w *8/ (Hee Tensor(v) @ Tensor(r))
( Cb
w Sym.SyTmmsorrrr (eenso((v) @ Tensor(r))
(i))
Ck
W Tensor(v) (v) v) i.... w Wig1 w Tensor(r) ( i44i0oi
cb (Vec( (eoc(w* 01) (Vec w 0K- -k-1)- r),
(29)
note that we applied Fact C.3 equation (i) and Fact C.I (1 in (it). Next, for the second term, after applying Sauchy-Schharz inequality, holds
Fact
(He, Tensor(v) @ (en)or(r))
=
E (
(y o(w" x)) (He (x), Tensor(v) @ Tensor(r))
< [(y oww x))²1 [((Hex(x), Tensor(v) @ Tensor(r)))
(x.D)>D
x~>Va
VOPT (yyT[[esTTTessr @ (I)
24

---

Since for any k-tensor A we have [|Sym(A)]l= & ||A|| and in addition, observe that as | = ||||| it holds
d
Tensor(v) Tensor
(Tensor(v)) (Tensor(r))
v2r
we finally have
(Hg, Tensor(v) @ Te)sor(r)) VOPT Tensor(v) & Tensor(r)]l= VOPT.
(30)
Combining Equation (28) and Equation (30) we get that for any v E IRd E Rdd such that
||v]|2 r 1, it holds
v M,t I a (Vec(w* (8)) vVec(w +8 +VPTT
Therefore, the singular value of must satisfy
p(v) S max rERn* -||llla11
Ck (eeeeeww* 81) vVee 8k ().)) VOPT
=
=x (Ce(Veew"* 88) v) + VOPT,
(31)
where in the equation above, we used the observation that as |/Vec(** = || || it holds max tegak ||r|||=1 (Vec(w* 000
1F 1,
||Vec(w &0h l|2 =
Similarly, we have
p(v) = max
v Matiuu-r) (C FER
max
(Ck, Tensor(v) @ Tensor(r))
reRd -|||||a=1
:/|r||2=1
Cx (*(eec (8)) v)ee ( )..))))))))))))) + (H&, Tensor(v) @ Tensor(r))
max
rERdb-! |||||==1
2
max
CVeeVe( 01) VV *k -x VOPT
rERd |||||==1
= Cx (Vec w 31 v) VOPT,
completing the proof of Lemma D.4
direct application Lemma D.4 is that the top-left singular vector v IRd of Mat has singular value at least Cg VOPT, and in addition, v* aligns well with Vel(w*
Corollary D.5. The top-left singular vector v E TRd' of the unfolded tensor Mat (Cx) has corresponding singular value p(v*) 2 Cx VOPT. In addition, it holds that v Vec( w w8)) > 1 -2VOPTT)/c-
Proof. Plugging in v Vec(w*G) 0l) to Lemma 2.2 we get that p(Vec(w (ec(w+())) 2 Ch VOPT. Thus. the top singular value must satisfy Pi 2 /OPT. Recall again that as proved in Lemma 2.2 it holds p(v*) I v Vll) + VOPT. Thus, since p p(Vec(w*8)) 2 /OPT we have
v Vec(w w @1) > (2VOPT)/Cr
D.2 Concentration of the Unfolded Tensor Matrix
We start with notations. Let us denote M (y Hex for i [M]
and M 1 Σ M(), which is the empirical approximation of M = Mat (Cxx) Mat (E(xg))> jyHe (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.
be the angle between the top left singular vectors v" E o and 4 ddd Mf and M respectively. Let P1 and p2 be the first singular values of M. Then, it holds that:
Fact D.6 (Wedin's theorem). Let #(v", v²))
JM-
M
sin(O(v",V'))
P1 P2
M
M|
25

---

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 P1, be the top two singular values of M = Mat Then P1 P2 2 (ck - 8/OPT)/2.
Proof. Recall that in Corollary D.5 we showed P1 p(v*) 2 c VOPT and v Vec (w" (1) > 1 - (2v (2VOPT)/ce Now let E Rd be any left singular vector of M that is orthogonal to v We can decompose Vec(w*@1) into Vec(w*@\) av" + bv + v' where v' is orthogonal to both v and and a² + b² I 1. Then, since Vec(w* V 2 (2v (2/PPT)/C, thus have Vec(w*80 b S v1 a²
a2/2. This implies that
(vv)
2 C₁ VOPT - (cx (Vec(w w 18) +
d² Σ Cx(1 10-222/0T-- 2 c+(1 (1- 2/OPT 2 02/2 4VOPT,
and hence get P1 P2 2 (ck 8/OPT) completing the proof of Claim D.7
completnnn
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 1.5 DPVLB24)). Let ((0) E [n], be independent, mean-zero, self-adjoint matrices. Define:
}
E
Σ
2
22 = sup
E
Σ v i=1
R² = E
max Z
|||
iE ml
Then, for any R 2 R2/221/2 + v 2R, and any 2 0, if = Pr[max,e|M| |Z 2 R). then with
probability at least - 8 de
n
Σ f=1
z 2x S 1/2 1/ R1/3,2/3 + R..
(32)
However, note that M and M are not symmetric matrices, hence to apply matrix concentration inequalities we will working on the symmetrization of M and M for simplicity, which we will denote by P and P:
P
1
Σ 1=1
P
M 0
0
M 0
P
0
M
MOT
M
M
T 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 + R. be multivariate polynomial of degree at most k. Let x be standard Gaussian random variable Bd. Then, for any 2 1 it holds
[x S 1)
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 [DNGL223..
Fact D.10 (Lemma 23 (DNGL23), Let A, be random variables such that | S Snpp for all p 2 and some positive real numbers aB, C. Then,
E[AB] < ((A max (1, 1 log
1
)
(E[A?))
E E[A]]]
We also make use of the following lemma that bounds the magnitude of label y without loss of generality.
26

---

Lemma D.11 (Bound on Labels). Ler PB, (2) :R - R be function that truncates the value of to the threshold By: PB, (2) = 21 {12| S B,y+ BB [|21 2 By)- Assume that Assumption / holds.
Then choosing By v //Ba/e. e, it holds that
(x,y)~ (Pn,(v) a(w" x)) & OPT +
Therefore, it is without loss of generality to assume that lyl - By
Proof. After truncating the label y, we have
E (P:())) ow x))²
(x.))=
[Pr(y) - ow"" x)) [o x) + E (Pe(v) - a(w' (ow" 21]
(x,0)=
(x,y)~
E
[y - oww' x)) + E (P((v) - oow'' x 1fo x=) H
(x,31)=
(x.1i>~D*
< OPT +2 (x,))~D*
E
[((2 + + (ow' xx) 2 17..
Since Ex 10 (w* x)] s Bg by assumption, we have by Markov's inequality that Prfa(w" x)
S Ba/t4 Therefore, we can further bound (xx,))> [(P:(y) o(w" x)) from above by
2B
E [(P(()) -ww x))3 OPT +
E [o'(w" x)
x)] Pr x) 2 0
(x.y)D
x2NNa
4B
OPT
f2
Thus, choosing /4B1/e we have
E (x,y)~
(P(()) - o(w" x)) OPT
indicating that we can assume without loss of generality that lyl S By = /4Bg/c, completing the proof of Lemma D.11
After assuming that y is bounded by By without loss of generality, we can then bound the 2nd and 4th moments of y. These bounds on the moments of the label y will be used when we implement D.10)
to get finer bounds compared what we would get from a simple application of Cauchy- Cauchy-Schwarz. Schwarz. In particular, use Fact 1.10 to derive upper bounds
expectations like E(x,))=ly> (x)),
where (x) polynomial of x, we have control on the ndh moments of fxx using Gaussian hypercontractivity Fact D.9
Lemma D.12 (Moments of Labels). IFOPT < 1/16, then 1/2 S E,, S and Eyln" 8B4/e.
Proof. We first bound the 2ad moment of the label y. Note that since a(w" x) is normalized such that Ex-wN, (a (w" 2] = 1, we have
E
E
[1 o(w"- x) + o(w" x))
(x,y)~D
(1 + 1/a)
(x.y)~ [1 oww x)) + (1 a1+a) E [(((w*x)))3) x
We used Young's inequality in (i). Choosing 1/8 and since we assumed OPT < 1/16, it holds E,, [ /6 + 9/8 < 2. In addition, using Cauchy-Schward inequality, we have
E b (x.D)~D
[y oww x) + o(w" x))²
E E [y (ww x)) x~\ia
[(o(w" x)) +2 E
[Vv - a(w" xx))oww".. x)]
(x.y)>D
(x.1)>
21 21-2
E [1 aww- x)) E [[o(w" x)) 2 1/2.
(x.))~D
x~NN
This yields the first statement of the lemma. For the remaining statement, notice that since y $ By we have E,,e/' < E, 2B 8B,/e.
27

---

We now proceed to bound the sample complexity of Algorithm 3] the argument for which relies on applying Fact D.8 to ( = (p()) P) and is summarized in the following lemma.
Lemma D.13 (Sample Complexity for Estimating the Unfolded Tensor Matrix), Let c, > 0. Con- sider the unfolded matrix M = Mat (B(x.)) [yH (x)]) and its empirical estimate M = are (B (Ba/e)d
(L/n) En= Mat (y Hes )x), where {(x(1,
1/c) Lidd samples from D. Then, with probability at least exp(-d"13).
|M Mil2 S cu-
Moreover, V is the top left-singular vector of M, then with probability at least 1 - exp( (xp(-dt/22 -d2/2).
2E0
V Vec ( 81) 2 VOPT
(ck/2- -VOPT) 6D
Proof. The proof hinges on applying Fact D.8 for which we need to bound above the parameters Ya and R defined in the same fact. We do so in three separate claims, as follows.
Claim D.14.
S
allt gld-112 11/2 10g (Ba/e))
log (B4/e)
Proof. By the definition of y, we have:
)
1 E E -P) -
1 E (11)))l
E
P
Elv M )
max
n VER rER
[lv] ++31++1=13=11
Observe that v M (M 11v T ΣØ (v M and notice that by defini-
tion (+) Matu. (...A--)(( (y (y )x())) where y Hex (x) is a symmetric tensor, hence using
Equation (26) we get
v T ('MO(MM)
Σ Hex(()) Tensor(v) e en 6 H 0jv-
(1 1))
As (x(1), () are i.i.d. copies of (x, y). using the linearity of expectation, we have
Ely M (M())
y² He (x), Tensor(v) ejz .... S se)--. )
Σ
E (x.B)/D
(33)
[d]. observe that fir...ih- (x) = (Hex (x), Tensor(v) x ej ..... 8 ej .) is a polynomial of degree at most k. and note that
Now given any indices ji.... jn-1 E
2 ... ojen ) 27
E X
E x~NNa
(x)(()), Tensor(v) Ø en
[Sym(Tensor(v
(ensorrv v) ej ejr I|
Tensor(v) (v) Cjj
Cj.-1 | 1,
where the second line by Fact C.3
Our goal to apply Fact D.10 with A y² and B S (x)². To this aim, need to bound above the Ly-norm of fi (x)2 i.e. Exa.allfr www.valln..ms... (x//, which can be done using Fact D.9
E [1 (x) 1/(2p) s (2p 1/2/2
E [f (x(00 k/2 N>Ni
Xm<Na
28

---

This implies that (x) (x) S pp Thus, using Fact D.10 with A Je- (x)², we get
y² and B
y² Hex (x), Tensor(v) @ ej @ 8 ej ) - Ely (4e)
E Byly 12/2
log 1, k
Ey [v>]
Finally, using the bound on the moments of the labels we proved in Lemma D.12
holds that
2 E y² Hey (x), Tensor(v) @ e, @ ... e
S et log"((B/())
(x.x)>>D
Plugging the bound above back into Equation (33)
obtain:
2 x² Hx)(x), Tensor(v) @ ei @ ... e/u ) (x.1)~
M (M (
Σ
(x,9)=
Jrond iE|d]
S d (Bg/)B//))
We now proceed to bound above the second term E|r T (M())M((r) Using Equation (25) similar calculations yield that
B/r (M
-E E
E (x)2 (x) ei @... 2 e, @ Tensor(r) |
Σ
NuNi
S e d' log" (Ba/c) S e d (B./c).
Thus, plugging in the value of By = v Bafe from Lemma D.11 the variance can be bounded by /(2-1)/2 2/22" log
(Baee) di let log (Ba/c)
Vn
Next, we bound the operator norm 7, from above.
4/2 log (Ba/c))
Claim D.15. 7x S
Proof. By the definition of Y
1
(p()) p)F 2 }
sup
E
||]|=
11
i=1
1
( (p()) - P)F 21
sup
E
|M R1 nh
1 E
( p()) 27
sup
||
11
72
R Similarly, we can decompose F into r" [((()T (F(2)) with the same structure. Then, v + (((1) ((2 F(1) (2)). Thus, as (x(1), (()) are i.id samples, we can further bound
Decompose v into V [( (T(2)) 7, where v(1) Rd and v(2)
7x by
2 verd
(y T
sup
(x.))-D
[||/|a==
r |||||==1
1
12 Hex Tensor(v) Ø Tensor(r) )
sup
n
v ||v||a==
(x.))>D
rE
||||||==
29

---

where in the last equality we used Equation (27)
Now for any ||u||2 ||v|2 define
(x) = (x), Tensor(v) @ Tensor(r)
where v Rdd r Rdd and J(v.u) polynomial (x Xa) degree most k. Note that the polynomial (x) satisfies fiv.u)xx) 2 0 and Ex-Ma (fw.aaalvvv... w (x))² [[Tensor(v) @ Tr)sor(r) | 1. Similarly to the upper bound on 7 we apply Fact D.10 with A being y² and B
being fiv.u) (x)? which yields that for any | 1. ||u||2 1,
y² Hx)(x), (ensor(v) @ Tensor(r) )
>
E (x.y)>>
S e log" (Ba/e).
Thus, plugging this inequality back into the upper bound on y. above, we obtain
e log sogg(B.n (Ba/c)
Taking the square root 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.
k/2 log (B,e/)
Claim D.16. R
<
V/
Proof. By the definition of la norm, we have
R² max sE(n || [|
-P))) (v ([T
1
(v ((0)))
sup
max (E ||]]a P|
sup
Let us define
fxx(()) [|Mat (
Hx)() Tensor(v) @ Tensor(r))
sup
where v E IRd E Rd== and [+(x(()) polynomial of (x ,.... x of degree at most k.
Using the decomposition of VT =T= =[((1)) ( and F = [(((1)) (F(2))T again, we get
R2
(()))(HHx(( Tensor(v) s Tensor(r)))
sup iE(n) vEB a rEB
max
n
max LE(M)
1 (X
n
Note that the polynomial (x) satisfies (i) 2 and ( [[]((x ()) = Tensor(v) ?
Tensor(r) < 1. Note that E E[maxxE(w) 2₂] S ΣE E(Z,), thus using Fact D.10 10 we get:
[(y (({ e* log (Ba/e)
R
n
n
Taking the square root both sides completes the proof.
To apply Fact D.8 we need to choose the parameter Rt such that å = Pr[max fn| (1/ (L/n)] Plla 2 I is sufficiently small. Consider choosing It such that
e log" (Ba/e)d(k-D) 1)/4
R
R1/2,1/2 + /2R.
Vn
To determine 8, recall that from Fact D.9
we have (using Markov's inequality):
Ex ()x((x())))))))
p kp/2
(r
t
(34)
30

---

Note that p(() Pll2 = ( [xx(x()).
hence
= Pr
max - | P12 2 R iE(n]
S Pr
max (yfi(x(()) iE(n|
nR
(10
pb12 By
P
n Pr
Byfi(x())
2 nR
nR/
where in (i) used union bound and in (it) we used Equation (34) with .RRBBy. Now setting ph/2 nR/ (Byy) we get
log(()) S exp(- log (Ba/O)een)
In summary, applying Fact D.8 with the bound on 6 and 7 (Claim D.14 % Claim D.15), R Claim D.1 and choosing = h/1 in Equation (32) we finally get that with probability least 1 exp( log (1/c)(en) (kll/) dexpl- (exp(-d"/1), it holds
(Bs/c((B Vn
M M 2 = P S 27 + 1/2 R 2/332/33//3 + Rt S
Therefore, choosing
( et log* (Ba/c)d 1
+ )
θ
we have |MM M| I co. with probability at least 1 -
1xxx-(-epppppp exp(-d1/2)
To complete the proof Lemma D.13 we apply Wedin's theorem together imply that
Fact D.6 and Claim D.7 which
sin(" v²)) I (cx/2 4VOPT)
60
(35)
We then decompose 4 into v = av' + br, where r E gd such that r 1 v and |||||2 = and a² 12 = 1. Since b sin(O(v*, v*)). applying Corollary D.5 we have
V Vec(w av' Vec(w** 88) br Vec(w* )()
2 / - 62 - 1 C0//PT//0 /cx) - b 2 - (1-2VOPT/c)) (2 220OP/PT///)
2 VOPT
250
Ck
11/2-440PP ED
This completes the proof of Lemma D.13
After getting an approximate top-left singular vector of Mat ( (x( we show that finding the top-left singular vector the matrix Mat (V*) completes the task of computing vector that correlates strongly with w*.
v E Reo
Lemma D.17. Suppose that V Vec(w @l) 2 1 1- E1 for some E (0, 1/16). Then, the top-left singular vector u E IR of Mat (V*) satisfies u w- 2 26
Proof. Consider the SVD of Mat 1at( (V*) Rd
Mat (V*) = Σ p.u (r
i=1
where ( E RRd, [d], and ((0) E Rd .iE [d], are that (r()) , (()] is subset of (r(1), (r(!))..,,,,(""))) r(d)), which is an orthonormal basis of IR" Since
of orthonormal vectors. Note
(w*)" Mat Vec( 8/-11- ge. Vec(w= 2 --11, e1, we have #r 2 61, and thus
(w") "MM ( (ec) 01-1) (V)) Σ pi(w" 81-1 2 1 c1. (36)
31

---

Since n i [d] and r(t) [d"-"] form orthonormal bases of Rd and Rd respectively, we can decompose w and Vec(w~Ol-I) 1) in these bases respectively;
dl
w
a,u
Vec(w~Glt)
Σ bir(")
1=1
Note that since ||w" ll2 = 1 and |Vec(w (eo(w+sl-1111 111 = || 10 113 1, we have E. a 11 and
Σ, df 1. In addition, since || 1, we have | (V*) = Σi of 1. Therefore,
plugging the decomposition above back into Equation (36) we get
1 - S
pia,b S spabbl + P2 Σ 1=1
Σ 1=2
a
b2
1=2
S s101b1 + v oiv1 1- - b9 S Pladb + V1- 1- -1)b).
When P1 - 2 22/2, we have - /1 - o N 0 and then it holds that
1 1- V - 6 - g(r)). aibi 2
P1 /
We show that when 0 S c1 < 1/16 (which implies that 15/16 S P1 S 1), it holds that g(p1) 2 1 261. By the definition of g(P)), it suffices to argue that
- Pi 2 (1 2p1 + 1-
This follows by direct calculations as when Pl E [15/16, 16, 11, - 2p1 + +221 - p 0.
Therefore, when < 1/16, it holds that aιbı 2 - 2e1. Since 0 S ai bi S 1, it must be that
a1 25g; this further implies that w 1 2e1.
D.3 Proof of Propasition D.2
Since VOPT S <+//()4k") S ck. /64, choosing 6 = ce <=/(66kk*) S cp- /256 in Lemma D.13 we obtain that using n = ((kk")22e log" (Ba/e)dlk//)) + 1/c),
Proof of Proposition D.2
it holds with probability at least 1 - -ex(pdd that
4 Vec(w" 80
> 1
OPT
260 (cx/2 - 4v OVOP) - c
Ch
Cx- (128k))
1 32k
1 16k
Ck Ck./2 12
Ck /16 ck. /256
Then applying Lemma D.17 with 6 < 1/(11k))) 1 1/16 we get that the output u of Algorithm
satisfies
261 1/(8k*) 1-m1nmmn111/ min(1/k", 1/2), completing the proof.
D.4 Proof of Proposition D.3
Proof of Proposition D.3 Since VOPT < /64 and < 1/64, choosing ep C 1g-e/16 in
Lemma D.13, we obtain that using n = ( log" (Bi/e)dl" /2) / 1/c) samples, it holds with probability at least 1 - eexp( eep(_dd1/2 that vt Vec(w 2 1- (2/ck-) OPT++/+// 15/16 (6) Then applying Lemma D.17 with (2/c=)VOPT c/3, we get that the output w of Algo rithm 3 satisfies w" w" 1- (1122/==VVVPP)) t/33.
32

---

Finally, to show the upper bound on the L loss of w", we bring in the definition of the L loss C2 (w"), which yields
L (w S 20PT + 2C2 (w")
20PT + +2
Σ
k2
20PT Σ 2 (w" w*)hh)
12k
2OPT +2 2
Σ
c2((1 (1 (w" w ))(1 + (w -w") + .... + (w" w w))
12K
s 20PT +
koj (1 (w" w v
ket
(44 (= VOPT + e/3)
Cp.
k
Since Σxzk- ke S Ca- by Assumption (ii), this completes the proof Proposition D.3
E Full Version of Section 3
After getting an initialized vector w using Algorithm we run Riemannian minibatch SGD Algorithm 2 on the 'truncated loss'. In the following sections, will first present the definition of the truncated L loss C3 and its Riemannian gradient, then will proceed to show that Algorithm converges to a constant approximate solution in (log(1/))) iterations.
Algorithm 4 Riemannian GD with Warm-start
1: Input: Parameters c, k² Ck*, B4 > 0: T, Sample access to D.
2: w Initialization [,, k- Ck= B4, co = Ck- (256k)))
3: for t= = =,...,,T- do
4: Draw n O(Ck- log +1 (Bz/e))((e)) samples from D and compute
g(w") =
ks ch+ y (I- ( (x(1)), (
i=1
5: w (w"
1/8 w/ 3)/l -1g(w")22
6: Return: w².
E.1
Truncated Loss and the Sharpness property of the Riemannian Gradient
Instead of directly minimizing the L2 loss L3 we work with the following truncated loss that drops all the terms higher than K" in the polynomial expansion of a:
(w = 2(1 E (x,y)>
(uo(w (w x))), where p(w.o x) = -HHe (x), w WO
(37)
Similarly, the noiseless surrogate loss is defined as
22 2(1
[o(w" x))(w x)]) = 2(1 - Ck- (w w w²)
(38)
(x.y)>
Using Fact C.I (2). the gradient of the truncated L3 loss equals:
(C)( = 2
(Vo(w x)yl = - E
[Kt cu- (He (x), w 0K -10
(39)
(x.u)~>
(x.a)>
while for the gradient of the noiseless I.3 loss have
V (w) -2 E
[k"ce (e"ceoo""" o(w" x) (x), w -10]
(40)
(x.
33

---

Recall that P Pw == I ww
Then the Riemannian gradient of the L3 loss L2, denoted by g(w) is
(w) = P. w (V w)) -2
E [k' yP w (Hog- (x), w 8 [)]
(41)
(x.g)>D
Similarly, the Riemannian gradient of the noiseless Li loss L is defined by
g' (w) Pw - (VL2 (w)) -2 k kw"oww" P (He (x), w 1)].
(42)
(x.y)>/D
The following claim establishes that g" (w) carries information about the alignment between vectors and w*.
Claim E.1. For any w E gd-1, we have g' (w) -2k" Cx- (w w (aa))"'"(ww (w"" -ww
Proof. Using the definition of g" (w) from Equation (42) direct calculation shows that
(w-*)
(ww
ll(w*) - ll2
(w (w*)+- 3-m
2k
Ck
Hea(x),, week)
Hox (x), wi 2
[(w*) w 112
(w |[ ((w*) 1.
2k ck Sym(w** Sym w
(152)
2k Ck- - (w w w*)""~1|(wW>
where (i) is by the definition of g" (w) and oww" x). (fi) is by Fact C.3 and (fi1) is by Fact C.
Equation (20) and wwlle 112 = 1. Let v E Rd be any unit vector that is orthogonal to (w*) Observe
that v w V (w*) 1 0. Thus, we have
g (w() v= - cx- (Sym(v' so wI Sym
= = ce. (w w"" ww) O.
This implies that (w(w ) is parallel to (w*)-w and thus g g"(w) - 2k: 2 (www") -
Let us denote the difference between the noisy and the noiseless Riemannian gradient by g(w): E [(V o(w' P) Vo(w x)]
[(w) = g(w) g((w" = (x.9)=
We next show that the norm of E(w) and the inner product between (ww) and w are both bounded:
Lemma F.2. Let E(w) = g( (w)) - g' (w) as defined above. Then,
[E(w)]l2 < 2k c v OPT and [E(w) w S 2k* ex (OPT]|(w*)=**
Proof. Using the definition of E(w) and the definition of the 2-norm,
|[E(w)ll2 2k* Ck.
max
E (x
(y o(w" -x) P (He (x), w 600
vE34-1
2k*ck= ck. max
2k*
E (x.v)DD
(y --oww" Hee (x), v & w -10
veed
((HC (x), w/ @ w 2
< 2k ck. max vesu
E (x max VEB4-1
[(y o(w" x)) E
X~NN
21* ck-
Sym w @k wkk--))llr-
where the (only) inequality is by Cauchy-Schward and the last equality is by Fact C.3 A, it holds [|Sym(A A)lle < || we have
As a tensor
|yym(v
@ w SK
I| <
ll & w ok* - -1 ||v < 1,
34

---

which then implies that
lIÉ(w)llz S 2k Ck. VOPT.
Following the same line argument as above, we also get
((()). w" 2vOTT V (k** )ll())))) & w wook-1111 2k"c ck.
This completes the proof of Lemma E.2
As direct corollary of Lemma E.2 close to the norm of the noiseless gradient (g'(()]la.
show that the norm of the noisy gradient (lg(()) [2 is
Corollary E.3. For any E gd-1, [lg(w))] S 2k ck. VOPT + (w"(wlll
Proof. Follows by the triangle inequality, as l|g( ( - [lÉ(w)lla + lig (w)ll2.
We are now ready to present the main structural result of this section. Lemma E.4 (Sharpness). Assume OPT S (4e) 2 for some small absolute constant e < 1. Let w E Rd such that ||w||2 = 1 and suppose that w w 2 - 1/k". Let == 6(w, w*) If
sin 2 4evOPT, then
g(w) w' |lg (w)llasin()
Proof. We start by noticing that by Claim E.I the noiseless gradient satisfies the following property:
(w) w 22k" Ck (w w y [[w -
11 -llg' (w) sin 0,
where we used that since ||w//2 | = 1, we have [(w*)-- ||2 = sin Furthermore, applying Lemma E.2 we have the following sharpness property with respect to the L3 loss:
g(w): w = g" (w() w + E(w) w < -(lg"
2k* ck- VOPT) sin
(43)
Observe that (1 - 1/t)*=1 2 1/e for all 2 1. Therefore, when w w 2 1 - 1/k", the norm of the gradient vector g* satisfies
Ig (w)]l 2k ck- (w w w*)""" sin 2 2k Ck (1- -1- sin 2 e- Cx- sin 0.
therefore, when sin 2 4evOPT and w 2 1/k" we have
Ig" (w) 2 4k" ck VOPT.
Thus, as long sin 0 2 devOPT, we have that g(w) w S - (
E.2
Concentration of Gradients
For notational simplicity, define:
g(w; (+), (0)) K ( (x(x)(x(1), w -1)
(44)
Then the empirical estimate of g(w)
da
(w
(0)
Σ Ko PP (Hes- w
(45)
The following lemma provides the upper bounds on the number of samples required to approximate the Riemannian gradient g(w) by g(w).
Note here that had used the truncation of the activation, then the bound the error {(w)
could get would be [[[(w)]la & (Euzo 1/2
35

---

Lemma E.5 (Concentration of Gradients), L" of the Riemannian gradient. Furthermore, denote the angle between w and w by B. Then, with probability at least E it holds
w" w
ga-1 Let g(w) be the empirical estimate
c(- )2ch log (Ba/c) nd (k* (k*cz=) log" (Bafe) (0) n2
[g()) - g(w)ll2
(g(w) g(w)) w S
Proof. By Chebyshev's inequality, we have
1
a g g(w; (0 ,0)))))))))))))))))))) g(w)
Σ g(w; x(w; ,,) g(()
Pr
2 l
E
12
(x,))~D
2
2
1
g((;x,)) 8(w) /
E
(46)
nf2
(x.y)~~
Let e be the jth basis of RRd we have (lg(w; x. y) - g w = (g( c, -c--((w) e,)²
Thus, it suffices bound the expectation of each summand (g(w:x, 3) ej - ((() .e,) for j [d. Note first that since g(w)= = E(x.))>(B((w: y)I, we have
E (g( (1:((wx.))) ej g(w) e;) (x.g)
E
[g (g(w;x,y) ee,
(x.0)~
y² He (x). @ w oK -1 w )
4(k" ck- )²
E (x,y)>>
Denote fx(x) = (He e @ 0k* -1), which a polynomial x of degree k², addition, note that Ex-NN, (xx) |10/ w w8k -1 | 1 < 1. Therefore, applying Fact D.9 and
Fact D.10 with = y²² and B (x)², we get
Hew- ex) @ w w 17
Iy (4e)* max { 1, ş. log(B1/e)) K (x.))D
E (x.y)>D
y
<e"² log" (B1/c).
Thus, it holds that B(x.))-p(lg(wwxx))) y) e, g(w) e S (k* (k*cc=)) ) log" (B1/e), which further implies that the expectation of lgg (e( x, y) - g( g() is bounded above by
E Ilg(: g(w) < d(k' cke e log" (Ba/c).
(x,y)>
Plugging this back into the Chebyshev's bound Equation (46) obtain
d(k' ck- Fzc log" (Ba/e)
Pr[ w) g((w ( 2/2 2 1] <
nt2
Therefore, with probability at least 5, holds
d(k Pet" log (B4/e)
[(() - g(w)lla S
nd
36

---

Now for the second statement of Lemma E.5 yields
we similarly apply Chebyshev's 's inequality, which
Pr
g x
(10)) w g(() w 2
1 E
g w; x )")) w' g(w) w"
1 (x.y)
(g(w; w=)
nt (x.I)DD
4(k* ch.) )²
E
(1 He (x), w 0K -1 60 (w*)+w))²
nt²
(x,))
Let fw- (x) = (He (x), w.kk -1 @ (W*) Note that Ex (fw (x) = 1/ 1|w
(w*) 1"1 = =1(ww)) 1|.. Since w" w E Sd-1, we have [l(w") 1/2 = sin Thus, by Fact D.9
2/(2p)
[l (x)]lz=
E x
[[fw (x)
(2p-1) 62/2 /2 E [(fw (x))21) (2p) sin 0.
x~Na
Hence, applying Fact D.10 with A = 112 B = fw-(x), (x), 0B = sin 0, and C' = k", we obtain
E [1 (HCK- (x), w @ (w*) sin Ae log" (Ba/c).
(x
Therefore, it holds that
(k* ck- ) log" (Ba/c) /c) sin (0)
(r(l@(())gg(f - ww| 2 t]
nt²
which implies that with probability at least 1 - 5 it holds
(ø(w) g(w)) w $ (k* Pekk Pek
log" (Ba/e) (i)
n2
We proceed to the main theorem of this paper. It shows that using at most (ddTk/2] + d/e) samples, Algorithm 2 (with initialization uubroutin(Algoritie generates a vector w such that Lg (W) O(OPT) within (log(1//c) iterations.
E.3 Proof of Main Theorem
Theorem E.6. Suppose that Assumption holds. Choose the batch size of Algorithm to be de log" 11''"+(("") (Ba/e)/ and choose the step size n 9/(40kk"* (x-)) Then, after
= O(log( (Clog(Ca=/Cc /c)) iterations, with probability at least 1 6, Algorithm 4 generates a parameter
w T that satisfies L (wT) OCCx- OPT) + The total number of samples required for Algorithm 4
is
/cx O
log" (Ba/e)alk<1)) 121 (c (ct''ogg' 1o +B+BBB//)Cx))
d c3
N - (k*
Proof. Suppose first that OPT 2 (64k)() OPT is of constant value. Then by Claim E.7 we know that for any unit vector w (e.g., w e1) holds
Σ ke (w w')) < 20PT 40,- O(OPT).
( < 20PT +
Hence w is approximate solution of the agnostic learning problem.
37

---

Now suppose OPT I (ck- (64k)) then the assumption in Proposition D.2 satisfied and Algo rithm can be applied. Consider the distance between w' and w" after each update of Algorithm By the non-expansive property of projection operators, we have
|| 3 |proje, (w' n/((w") w
Iw 7/(ww") - wwll |w' w'1 + 2ngg(w") (w") (w* - -'''"""l(('""""
(47)
Let us denote the angle between w' and w by 0,. Furthermore, let us assume for now that O, satisfies sin 0, 2 4evOPT + /e, hence the condition for Lemma E.4 is satisfied. Note by definition
g(w") 1 wf, hence using Lemma E.4 and Lemma E.5 we have that with probability at least 1 8, the inner product term in Equation i4 is bounded above by:
B B(w"). (w* w') -g(w") w (B(w") g(w")) w + +(ww") ww 102""/2 Cik cs. e 12 log" 12 (Ba/c) sin sin) 2 llg """(w")lle sin 0,.
(48)
vnd
where Ci is sufficiently large absolute constant. On the other hand, the squared norm term [l (B(3) from Equation (47) can be bounded above using Lemma E.5 and Corollayy E.3)
[ ( )12 = l1(@(w") g(w") )) + 112 s 21 - g(w")) )12 + 2|lg(w
C2d(k* cx ) log (Ba/t) (k* cu. POPT (w)]l
(49)
nd
for a sufficiently large absolute constant C2. Plugging Equation (48) and Equation (49) back
into Equation (47) and denoting K = max C2 - cx- 72 log"" 72 (Ba/c), we get that with probability at least 1 - 8,
|| w0 < lww
w" 11 +
n
sin 0,
2 218" (lg(w")ll2sin 122 02
vnd
dn
+ 1/2
+ (k*
cx 2 + +llg"(w'))
no
Let us assume first that 02 < 01-1 S .... Og and 0g satisfies sin 0. 4evOPT + Ve. We will argue that in this case 0,+1 S O: (in fact, that it contracts by a constant factor). Then, by an inductive argument, we immediately know that the assumption is valid and that 0, is decreasing sequence (as long sin 0, 2 4PvOPTT- + c). To prove 0 I 6,, recall that in Claim E. it was shown that (lg((w") 122 2k* cx- (w" w w"]ll(""))>>>>"" [ ||2
2k" ck- CK-(W' w ) sin O,.
Recall that w is the initial parameter vector that satisfies w w > 1 - 1/k". By the inductive hypothesis it holds Og I Co hence w' w 2 w w 2 1 1/k". Furthermore, as we have (1-1, 1/1) > 1/e for 1 2 1, it holds I > (w" ) 2 1/e. Therefore, we further obtain
(2k* (e) sin Og S (w"(wll S 2k*c, sin0,.
c+
Now choosing n 2 dx<((kk cx- )c8), and recalling that we have assumed sin 0, 2 4ev Ve by the induction hypothesis, we can further bound | w above as:
|| --11- < Iw- -w"li w111 + n((e/d)1/2 1/2 (4k* /e)) sin? 0,
+ n (k* cx. )2 OPT 4 0b)
(50)
< |w' - 1I2 (3k* cx. hes/eensiss sin? 02 5/72 (k" ck. )22 sin? O..
Observe that since 0, < 0g and by assumption w w cos 0g > min (1 /k= 1/2] >
1/2, we have cos(0,/2) 2 v3/2 and thus it further holds that (2 (0, < sin O2 <
2 sin Since l|w" w ||2 sin(0:/2) follows from w w E sd-1, we finally obtain that,
with probability at least 1-d 8.
|| 113 < (1 (9k* ck ((4)) + 5(k" cx 333 )[w] w'1
38

---

Choosing 9/(40kk ck-) yields (with probability at least 1 - 6):
4sin (0141/2) = =|w ww 11
< (1 (81/(320e) ++1 - -
= (1 (81/(320c (4
(51)
This shows that 0(+1 Σ 0r, hence completing the inductive argument. Furthermore, (Euuationnn (51) implies that after at most Ologg( (1/e)) iterations it must hold that sin 0r S 4evOPT + Ve, therefore, we can end the algorithm after at most (llog(1/e) iterations. Though the contraction Equation (51) only holds when sin Or 2 4eVOPT + Ve, we can further show that if after some iteration 1" we have sin 8,- I 4ey0PTT Vc, then sin 0 is still of order VOPT+ Concretely, if there exists some step t" < T such that sin( s 4ev + Ve. then at step t + it must hold (by Equation (50)):
{ sin(0:++1) S V (k* sin(( S 3sin 0:- 33(4ev + Vo).
In other words, for all steps St T, holds that sin 0, S 30(V VE). Thus, in summary, choosing = (llg((//)) we get that with probability at least 87, sin Or z vOPT + ve, and applying Claim E.7 we get:
(3(w")=0 C3(w") =0 0((
Σ ket (OPT+0)) OP) k2k
where we set é' e/Ckk. S E/(2 kez), and used Assumption (ii) that ΣB kej S Ck.
Thus, choosing 8' = 8T, where T = (log Ct- /c')),
Algorithm 4 outputs a parameter w such that with probability at least - 8', C3 (w = O(C2 OPT) +e. with batch size
θ @ (dCriet log" (Bs/e)) togg"+((B./e)) 6'8'
In summary, the total number of samples required for Algorithm 4 is
N o (k*)2e4 log" (Ba/e))dlk* /2)
+ Cx-de* log"
(oaa")((a/())
c.
e'8'
The final claim shows that if sin(f(w, w*)) S VOPT Ve, then C3(w) S Ck. (OPT + c). Claim E.7. Let w E Sd and denote the angle between w and w by If satisfies sin S
C(VOPT + for some absolute constant C, then we have
(g(w)= 2
Σ ket (OPT+c). 12
39

---

Proof. Since w. w cos 0 2 1 - -sinnn 8, according to Claim C.4 the L3 loss L3 (w) can be upper
bounded by
[3 2OPT 4 1 Σ c (w w*)²
k2b
20PT + 4
Σ
c1(1 (w . Nww.w"Jg. w()b))
42k
20PT 4
Σ c1(1 (w w (1 + (w . w*) + + (w w=)
k2k
20PT +4 4
Σ
kef(1 (1 - (w w'))
20PT 4
Σ
kct sin 2 0
S 20PT + 4
Σ
ket (9POPT+))
+0)
Σ 12k
kct (OPT +c).
42
40

---

NeurIPS Paper Checklist
1. Claims
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 the main contribution our paper provided in Theorem 3.5| that is, provide the first algorithm for agnostically learning SIMs under broad class of activations. In the introduction, we summarize the motivation of our work, provide detailed discussion of our results, and compare work with prior literature.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
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 the statements of the theorems.
Guidelines:
The answer NA means that the paper has 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
41

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our assumptions on the activations are summarized in Assumption 1] Complete proof' are provided in the main body and the appendix (opoodxxxApppeee (Appendix D and Appendix E
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
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.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
42

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. htcp//blcc/guddeeeeeeeeeeeeeeeee
soiobiiiissiooccccyc. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
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 experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of 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 authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
43

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps://eeurpp::::: http://aaarrr...cccaaaaaaccccaaa
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
44

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is theoretical and does not data models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
This work does not use any assets.
Guidelines:
The answer NA means that the paper does 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 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.
45

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work does not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve any crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This work does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
46

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "6sD7zcEjcL", "reviewer": "Reviewer_9oLo", "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.", "questions": "* Is the proposed algorithm expected to reach the SQ lower-bounds upon transformation of the labels?\n\n* Intuitively, why does unfolding fare better than the partial trace estimator under adversarial noise? \n\n* 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)?\n\n* 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.\n\n* 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) ? \n\n*  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": "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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper makes novel technical contributions towards understanding the sample-complexity of learning under the adversarial noise. Understanding the differences between the adversarial and realizable/random noise settings is crucial towards justifying applicability of CSQ and SQ lower-bounds in typical maching learning setups. The paper adequetly describes the technical challenges in matrix-concentration under adversarial noise as well as why the partial trace algorithm in Damian et al. (2024) cannot be directly applied under the adversarial noise setting (Appendix B.3).", "weaknesses": "* The central ideas of obtaining weak-recovery by estimating the Hermite tensor and subsequently running minibatch SGD is largely similar to existing works (Biroli et al. (2020), Damian et al. (2023), Damian et al. (2024), Chen and Meka (2020)). Therefore, the major contribution of the work are adapting the ideas and analysis in these papers to adversarial noise, which has some technical but limited conceptual novelty. Even under adversarial noise, prior works have establishing similar guarantees for smaller classes of link functions. It is unclear whether the setup of  adversarial noise is relevant for gradient based training in machine learning models. Discussion of the motivation behind studying the adversarial noise  and the novel conceptual contributions/implications of the work will improve the paper.\n\n* 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.\n\nMissing references of closely related works:\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General Response to Reviewer 9oLo**\n\nWe thank the reviewer for the provided feedback. Before responding to specific questions and comments, we address two main points, which we believe are the main sources of the reviewer's somewhat negative view of our work. We hope that upon clarifying the context, the reviewer would consider reevaluating our work.\n\nFirst, our work is motivated by the line of work on **agnostic learning** of single-index models under structured marginal distributions and broad classes of activations, as discussed in the top-level response. Agnostic learning, introduced in [Hau92, KSS94], is a well-established model meant to capture **realistic** learning settings, where we do not assume that the labels perfectly follow a model from the class (where \"perfect\" also accounts for, e.g., zero-mean noise), and the goal is to be competitive with the best-fit model from the class. The line of work on agnostic learning has a long history in the learning community, with papers regularly published at top ML theory venues such as COLT, NeurIPS, and ICML over the past three decades. \n\nThe aforementioned line of work on agnostically learning SIMs (see the top-level response) elaborates on the  difficulties of polynomial sample and time learning, and develops the first **efficient** and **constant-factor** **agnostic** algorithms for **monotone** activations. While these algorithms rely on first-order methods, they do not rely on “vanilla SGD on the square loss” and their analyses are fairly sophisticated. \n\nSecond, it is important to note here that our focus was **not on the CSQ model** itself or on the optimality of our sample complexity for **all SQ algorithms**. It is a plausible conjecture that the sample complexity of our algorithm can be improved (by an appropriate label transformation preprocessing or some other method) and this remains an interesting open question for future work. As we explain below, the applicability of existing such approaches is **unclear**. Importantly, our main result is **the first** constant-factor agnostic learner with polynomial sample and time complexity addressing the broad class of activations defined via Hermite polynomials. It is also **the most sample and computationally efficient algorithm** for this task known to date — not only within the class of first order/SGD-type algorithms, but **in general**. \n\n---\nBelow we address specific comments and questions raised by the reviewer.\n\n#### Weakness 1\nWe respectfully disagree with the reviewer’s points. As is explained in the submission and we reiterate below, there is a vast difference between the **realizable/random noise** setting and the challenging **agnostic** setting that we study (both in terms of algorithms and analysis). \n\nConceptually, it is important to recall that our goal is to obtain error $O(\\mathrm{OPT})+\\epsilon$, which is the best possible error achievable in polynomial time (please see our general response). None of the aforementioned works achieves such a guarantee, even for very special cases, e.g., for a ReLU activation. (That is, the algorithms themselves in these prior works do not suffice; not merely the analyses.)\n\nAt the technical-level, our approach also differs significantly from these prior works. Specifically, our algorithm has two main components:  an initialization subroutine and an optimization algorithm. Both are new and require novel analysis. To obtain a non-trivial weak recovery in the initialization step, we carried out a **fine-grained** analysis of a $k$-tensor-PCA algorithm in the presence of agnostic noise. The optimization algorithm is different from these prior works as well and its analysis hinges upon a critical **structural result** for the $L_2^2$ loss, which we term ‘(alignment) sharpness’ (Lemma 3.3). In more detail, we show that the Riemannian gradient $\\mathbf{g}$ of the $L_2^2$ loss of the *truncated activation* contains a **strong signal** in the direction of $w^*$: $\\mathbf{g} \\cdot w^* \\leq -\\mu\\sin^2(\\theta)$, where $\\mu$ is an absolute constant. Intuitively, this structural result conveys that the gradient vector $\\mathbf{g}$ can *pull* the algorithm iterates towards $O(\\mathrm{OPT})+\\epsilon$ solutions. **None** of the prior works listed by the reviewer established such a structural result, which is **key** to obtaining a constant factor approximation. We refer to Section 1.2 (Technical Overview, line 176-192) for a more detailed discussion.\n\n>It is unclear whether the setup of adversarial noise is relevant for gradient based training in machine learning models [...]\n\nAs noted in our general response, the agnostic model is **fundamental** in learning theory and has been **extensively studied** in the context of learning SIMs with monotone activations. From a practical perspective, the realizable or random label noise settings are often unrealistic, as they posit the existence of a model that perfectly fits the data (possibly on average). \n\n#### Weakness 2\n\nAs noted in our general response, the focus of our work is **not on the CSQ vs SQ** distinction. We provide **the first polynomial-time algorithm** for our problem that achieves near-optimal error of $O(\\mathrm{OPT})+\\epsilon$; a goal **not achieved by these prior works** (with any polynomial sample complexity). Importantly, when one talks about \"SQ complexity\" in the agnostic model, the accuracy achieved by the algorithm is **critical**. Please see below as a response to the reviewer's relevant question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xeAPQaWgoL", "reviewer": "Reviewer_wBuC", "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.\n\nThe 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.", "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)$ ?\n- 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": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I found the topic of the paper very interesting; I was mostly familiar with the realizable setting, and the adversarial version provides interesting insights and challenges. I particularly appreciated Appendix B, which compares in-depth the present work with previous papers on both the realizable and agnostic settings.\n\nThe results encompass a wide class of link functions, and make no assumption on the data distribution at all (apart from Gaussian marginals). The arguments to handle such a diverse class of problems are conceptually interesting, and (as far as I checked -- see `Weaknesses`) correct.", "weaknesses": "Apart from a few qualms with the presentation (see the minor remarks), my main issue with the paper is simply its length. With the short review time and high review count, it is strictly impossible to certify that a proof which consists of 20-25 pages of dense math, with many computation-heavy steps, is correct. I did check that the proof outline and the main steps seem correct, but it is my opinion that such a paper is incompatible with the Neurips review format, and should be submitted to a journal instead. My recommendation for acceptance, based on the overall quality of the paper, should be taken with such a caveat.\n\nMinor remarks:\n- 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.\n- 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.\n- there should be a $w^t$ in the RHS of eq. (16).\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper and the positive assessment. Below, we provide specific responses to the points and questions raised by the reviewer.\n\n\n\n>(Question 1): Can such a measure be defined in your setting, instead of considering the worst-case scenario on (x,y)?\n\nThe prior work [DPVLB24] considered the generative exponent $\\bar{k}^*$ of the label $y$, which is defined as the first non-zero term $E_y[(E_x[he_k(w^*\\cdot x)|y])^2]$. It is not clear how to leverage such a measure for the agnostic setting for a number of reasons, including the fact that the \"noise\" in our setting is **unknown** to the algorithm and that the labels may take real values (in which case it is unclear how to estimate the conditional expectation stated above). \n\n\n> (Question 2): a mismatch between 𝜎 and the ``true'' link function can lead to a value of 𝑂𝑃𝑇 of order Ω(1), but some algorithms manage to achieve almost perfect alignment with the vector $w^*$. In your case, a large value of 𝑂𝑃𝑇 yields vacuous bounds on both the performance of your algorithm and its alignment with $w^*$; is there an explanation of this phenomenon ?\n\nThis is indeed the case and it is a consequence of the **agnostic** model. Specifically, in the presence of agnostic noise, it is not possible to achieve perfect recovery for the target vector $w^*$ (i.e., find a $w$ such that $w\\cdot w^*\\geq 1 - \\epsilon$ for any desired accuracy $\\epsilon>0$) -- even information-theoretically. Specifically, one can construct examples where two different weight vectors both achieve the optimal error while being far from each other. This is a fairly standard fact in agnostic learning and holds even for simple activations like ReLU. In the **realizable** setting, the reason that one can recover the target vector $w^*$ almost perfectly is that the distribution of the label $y$ is **known**, and hence it is possible to manipulate the labels to gain more information about $w^*$.\n\n\n\n>(Minor Remark 1) the vector $w^*$ is never rigorously defined\n\n\nWe thank the reviewer for pointing this out. We clarify that $w^*\\in\\mathrm{argmin}_{w\\in\\mathbb{S}^{d-1}} \\mathcal{L}_2^{\\sigma}(w)$; i.e., $w^*$ is defined as a vector that achieves the minimum $L_2^2$ loss. We have added this definition to the main body. \n\n> (Minor Remark 2) My best guess is that the results hold uniformly over a class of link functions where $c_{k^*}$ is bounded from below, and $C_{k^*}$ and $B_4$ from above \n\nThe reviewer’s understanding of assumption 1 is correct. We further clarify that the activation $\\sigma$ is fixed, but it needs to satisfy assumption 1 so that our algorithm achieves $C\\cdot \\mathrm{OPT}+\\epsilon$ error, where $C$ is an absolute constant, using the sample complexity and runtime as claimed in Theorem 1.2. The constant $C$ in the error depends on the parameter $C_{k^*}$, therefore, if $C_{k^*}$ is not an absolute constant, then our algorithm does not achieve constant factor approximate error. The parameters $c_{k^*}$ and $B_4$ appear in the sample complexity. This implies that if $c_{k^*}$ and $B_4$ are not independent of $d$, the sample complexity and runtime might not be of order $O(d^{\\lceil k^*/2 \\rceil} + d/\\epsilon)$.\n\n>(Minor Remark 3): You mention in the introduction that achieving 𝑂𝑃𝑇+𝜖 performance is likely to be hard, but it's difficult to parse why the proof wouldn't extend in this case: this seems hidden in the recursion of Theorem 3.5. Highlighting this barrier would be a nice addition to the proof.\n\nThank you for the suggestion; we'll incorporate it. \n\nFirst, we note (as stated in the paper) that there exist both SQ lower bounds and reduction-based hardness results implying that achieving error $\\mathrm{OPT}+\\epsilon$ requires $d^{\\mathrm{poly}(1/\\epsilon)}$ time, even for a ReLU activation. To see why a constant factor approximation is inherent in our algorithmic approach, we refer to the Technical Overview section (lines 176-185). The main technical reason is that the sharpness structural does not hold on the whole sphere –– it is only valid on the sphere excluding a spherical cap centered at the target vector $w^*$. Specifically, by Lemma 3.3, we have sharpness on the subset $\\mathbb{S}^{d-1} \\setminus \\mathcal{S}$, where $\\mathcal{S} = \\lbrace w: || w || = 1, \\sin(\\angle(w, w^*)) \\leq 4e\\sqrt{\\mathrm{OPT}} \\rbrace$. This restriction of sharpness is due to the strong agnostic noise. Since every point in the spherical cap $\\mathcal{S}$ is a $O(C_{k^*}\\mathrm{OPT})+\\epsilon$ accurate solution (Claim E.7),  we can terminate the algorithm after entering this spherical cap if we are only looking for constant factor approximate solutions. However, since sharpness no longer holds once the algorithm’s iterates enter this spherical cap $\\mathcal{S}$, we lose the information about the direction in which we should update $w$; hence, we cannot continue decreasing the error to $\\mathrm{OPT} + \\epsilon$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wT8tA5aU0b", "reviewer": "Reviewer_z8KF", "summary": "This paper studies efficient parameter estimation from generalized linear models with adversarial noise (a.k.a. agnostic learning), assuming a known link function. \nThe goal is to find a parameter vector that best explains the data. \nThe authors show that $d^{\\lceil k^*/2 \\rceil}$ samples suffice for this problem with $k^*$ being the information exponent. \nThe algorithm is given by certain projected gradient descent (w.r.t. loss truncated to degree $k^*$ Hermite polynomials) initialized with PCA for tensor unfolding. \nThe sample complexity matches a known CSQ lower bound $d^{k^*/2}$ for even $k^*$ in the realizable setting (i.e., random noise).", "questions": "Major comments: \n\n1. The work [DPVLB24] is compared in B.3, but I'm not sure it's comparable. \nThat 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^*$. \nThe way I read [DPVLB24] is that if preprocessing is allowed, $d^{\\bar{k}^*/2}$ can be achieved. \nOtherwise, we're stuck at $d^{{k}^*/2}$. \nIn the current paper, no preprocessing is used. \nCould the authors comment on the possibility of reducing the sample complexity in the agnostic setting with preprocessing?\nOr the difficulty of applying a suitable preprocessing that brings down the effective information exponent?\nNote that the optimal preprocessing in [DPVLB24] relies on the link function. \nWith additional work, they can make it work for misspecified models (a.k.a. unknown link function). \nBut I'm not sure if this is possible with adversarial noise. \n\n1. 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^*$. \nThis is inconsistent with the standard definition of \"nearly\" in say TCS. \n\n1. 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 . \n\nMinor comments: \n\n1. 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. \nIn classical stats, learning single-index models means learning the unknown link function. \nOTOH, for known link function with unknown parameter vector, the model is referred to as generalized linear models. \nThere're also works consider learning the parameter vector from GLMs with unknown link function (as a nuisance parameter). \nHowever, it seems in recent years, people (especially deep learning theorists) have been interchangeably using SIM and GLM to refer to the above problems. \nPlease make sure such discrepancies are taken into account when comparing prior works with the present result. \n\n1. Line 63-66, I'm not familiar with the line of cited work on hardness, why is $d^{O(1/\\epsilon)}$ regarded as hard?\nThis seems to me a legitimate polynomial running time. \nCould 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?\n\n1. Line 72, what does $\\sim$ mean?\n\n1. Line 77, the condition $c_{k^*} = \\Omega(1)$ doesn't make sense to me. \nI'm not sure what's the asymptotic in $\\Omega(\\cdot)$. \nI 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). \n\n1. Line 103, could the authors also specify the dependence of running time on $1/\\epsilon$?\n\n1. 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)?\n\n1. Line 195, \"small constant $\\epsilon_0$\" is mildly misleading -- $1/2$ doesn't seem to be a small constant... \n\n1. End of line 200, there's a redundant 2 in the exponent. \n\n1. Line 223, is $l$ defined to be $\\lceil k/2 \\rceil$ or $\\lfloor k/2 \\rfloor$?\n\n1. Line 2 of Algorithm 2, the subroutine Initialization is undefined. I assume it refers to PCA for tensor unfolding. \n\n1. 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$?\n\n1. Line 572, I'm not sure why $\\mathbf{w}^*$ is desired to be the unique top eigenvector. \nDo the authors mean that $\\mathbf{w}^*$ is an outlier top eigenvector (meaning there's an eigengap between top two eigenvalues)?\n\n1. Line 581-583, I think the exact information theoretic threshold is known for tensor PCA: https://arxiv.org/abs/1812.03403\n\n1. Line 590, I think [HSS15] studies SoS instead of tensor unfolding (correct me otherwise). \nFor tensor unfolding, the correct reference is https://arxiv.org/abs/2110.10210 which confirms the $d^{(k-2)/4}$ conjecture of [RM14]. \nI'm not sure of the relevance of the bound $d^{k/4}$. \n\n1. Line 591, I don't understand where the $O(d)$ bound for unfolding comes from. \nThe suboptimal analysis of [RM14] already gives $d^{1/2}$. \nAnd again, the above reference shows that $d^{1/4}$ suffices for tensor unfolding (which is sharp for unfolding). \nI'm not sure the relevance of $d^{3/4}$ here.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "NA", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper, as well as the positive evaluation of our work. We respond to the reviewer's comments below.\n\n#### Response to Questions\n\n##### Question 1: \n(Q1) We agree that care is needed when comparing to [DPVLB24]. As the reviewer remarks, it is unclear whether their preprocessing ideas can be transferred to the agnostic model, for the following reasons. \n\nFirst, the noise model considered in [DPVLB24] **does not cover the agnostic noise** setting. In particular, [DPVLB24] requires the label $Y$ to be independent from $w\\cdot x$ for any $w\\perp w^*$, which excludes even some standard classes of structured semi-random noise such as the Massart noise. Thus, it is **unclear** whether the SQ lower bound obtained in [DPVLB24] is **tight** for the **agnostic** setting. \n\nSecond, it is not clear how to apply the label transformation process $T(y) = E[he_{\\bar{k^*}}(w^*\\cdot x) | Y = y]$ in the **agnostic** setting. Since the distribution of $Y$ in **unknown**, we cannot compute this conditional expectation. Further, how to even approximate this function $T(y) = E[he_{\\bar{k^*}}(w^*\\cdot x) | Y = y]$ is unclear when the labels take real values. \n\nThe difficulty of calculating or approximating this conditional expectation in the agnostic setting also poses challenges in transferring this measure of hardness to our setting. In particular, it is not clear how to calculate the generative component $\\bar{k^*}$ uniformly over **all possible noise distributions**. \n\nFinally, we note that other data transform processes also **fail** in the **agnostic** setting. For example, the SQ algorithm proposed in [CM20] that applies an implicit data transformation process via a thresholding procedure, **provably fails in our setting**, as we have remarked in the introduction. That said, we do not claim that further reducing our sample complexity via other more sophisticated techniques is impossible, and we leave it as an interesting future direction. \n\nWe further refer to our response to reviewer 9olo, weakness 2 and question 1, for additional  comparison with [DPVLB24].\n\n(Q2&Q3) Thank you for pointing this out; we will revise appropriately. We also thank the reviewer for the provided reference, which we will look into for possibly closing the gap mentioned by the reviewer. \n\n#### Minor comments:\n(C1) We thank the reviewer for pointing out the possible ambiguity in the terminology. We chose to be consistent with the terminology used in the existing line of work addressing the same activations, from [CM20] to [DPVLB24]. However, we will add a remark to disambiguate.\n\n(C2) We are interested in efficient algorithms with sample complexity and runtime that are polynomial in both $d$ and $1/\\epsilon$, as $\\epsilon$ is usually chosen as a small error tolerance. It was showin in [GGK20,DKZ20,DKPZ21] that for any SQ algorithm, agnostically learning ReLU (one of the most basic activations) to error $\\mathrm{OPT}+\\epsilon$ requires at least $d^{\\Omega(\\mathrm{poly}(1/\\epsilon))}$ queries, which is not polynomial in $1/\\epsilon$. Thus, this line of prior work rules out the possibility of having an SQ algorithm that achieves $\\mathrm{OPT} +\\epsilon$ error with $\\mathrm{poly}(d, 1/\\epsilon)$ complexity under our setting. Moreover, the same hardness result ($d^{\\Omega(\\mathrm{poly}(1/\\epsilon))}$ complexity lower bound) holds for low-degree polynomial tests (using the near-equivalence between SQ and low-degree tests shown in [BBHLT21]) and via reduction-based computational hardness (cryptographic hardness) [DKR23]. \n\n(C3) In line 72, we use $\\sim$ to denote that the function on both sides is equal in the Hermite orthonormal basis under Gaussian measure. Note that $\\sigma(z)$ might not be equal to $\\sum_{k\\geq 0} c_k he_k(z)$ pointwise due to the Gibbs phenomenon of Fourier expansions. We will clarify.\n\n(C4) Thank you for catching this typo, it should be $|c_{k^*}| = \\Omega(1)$, meaning that it is a universal constant, independent of other problem parameters like $d$ and $1/\\epsilon$.\n\n(C5) It takes roughly $d^{k^*}$ time to read one $k^*$-Chow tensor, and thus it takes $\\tilde{O}(d^{3\\lceil k^*/2\\rceil} + d^{k^*}/\\epsilon)$ time to read all $k^*$-Chow tensors required for estimating the unfolding matrix. Since we only need to estimate the top singular vector to constant error, this can be done with a standard matrix SVD algorithm (like power iteration) in time no higher than reading the aforementioned tensors, up to constants. The optimization subroutine takes time $O(nT) = O(d\\log(1/\\epsilon))$. Thus, in summary, the total runtime of our algorithm would be $\\tilde{O}(d^{3\\lceil k^*/2\\rceil} + d^{k^*}/\\epsilon)$.\n\n(C6) If one is interested in error  $\\mathrm{OPT} +\\epsilon$, such SQ lower bounds are known (as explained above). As elaborated in our response to reviewer 9olo, the SQ complexity of agnostically learning SIMs to error $O(\\mathrm{OPT}) +\\epsilon$ is not well-understood. Specifically, it is unclear if the SQ complexity is the same or significantly higher than that of the realizable setting. Fully characterizing the SQ complexity of the agnostic problem remains an interesting open problem. The main point is that our algorithm is the best known algorithm for this problem to date and almost matches the lower bound for a natural restricted class of algorithms (CSQ algorithms). \n\n(C9&10) In line 223, $l$ is defined as $\\lfloor k/2 \\rfloor$; in line 2 of algorithm 2, the initialization subroutine is the tensor PCA algorithm, i.e., algorithm 1 –– we will clarify this in the description of algorithm 2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Top-Level Response**

We thank the reviewers for their time and effort invested in evaluating our paper. We are encouraged by reviewers finding our results **technically novel** (**9olo**), **conceptually interesting** (**wBuC**), and rating the **presentation** of our work as **excellent** (**z8KF**).

Below, we restate our motivation and main contributions, along the way hoping to clarify the context of our work. Specific comments from the reviews are addressed in individual responses. We look forward to the opportunity to respond to further questions and engage in a discussion with the reviewers.  

#### Motivation & Context

The main motivation of our work is to develop polynomial-sample and time algorithms for **robustly** learning SIMs when the activation function is **not necessarily monotone**. "Robust" here refers to the well-established **agnostic learning** setting, where the labels do not necessarily correspond to any model from the class (i.e., there is no "perfect" model), and the goal is to be competitive with the *best-fit* model. Prior work [DGK+20, DKTZ22, ATV23, WZDD23, GGKS23, ZWDD24] has developed such efficient algorithms, albeit **restricted to a subclass of monotone functions**.  Obtaining similar results for more general activations, namely for monotone and Lipschitz functions (a **subset** of the activations we handle) was explicitly stated as an open problem in [ZWDD24].

A **major goal** in the agnostic setting is to obtain as high accuracy as possible in polynomial time. The information-theoretically optimal error is $\mathrm{OPT}+\epsilon$ where $\mathrm{OPT}$ is defined as the minimum mean square loss that is attainable by any function in the target class. However, obtaining such an error guarantee requires SQ complexity $d^{\mathrm{poly}(1/\epsilon)}$. The **best error we can hope for** with SQ complexity $\mathrm{poly}(d/\epsilon)$ is $C*\mathrm{OPT}+\epsilon$, where $C>1$ is a **universal constant** independent of the problem dimension. Obtaining such an error guarantee in polynomial time is **highly non-trivial**. Standard SGD-based algorithms and/or their analyses **inherently fail** to achieve this error even for the basic case of a ReLU activation, as discussed, for example, in the introduction  of [WZDD23]. Specifically, even with a tight analysis, the best possible parameter $C$ for such methods would scale polynomially either with the **dimension** or the **diameter** of the space; and the dependence on $\mathrm{OPT}$ would **not necessarily** be **linear** (e.g., scaling with $\mathrm{OPT}^{1/2}$).

The class of activations we consider is the same as considered in the prior work of [DNGL23], also studied in [DPVLB24] (and other works), generalizing the monotone activations in the line of work mentioned above. We emphasize that the algorithms appearing in  [DNGL23, DPVLB24] do **not** achieve the desired $O(\mathrm{OPT})+\epsilon$ error guarantee in the agnostic model, even restricted to the case of a ReLU activation (which corresponds to the information exponent of $k^*=1$). 

#### Main Contribution

Our main contribution is **the first polynomial-time algorithm** that achieves the $O(\mathrm{OPT}) + \epsilon$  error guarantee for any activation in the aforementioned broad class, with sample complexity scaling with $d^{\lceil k^*/2\rceil},$ where $k^*$ is the information exponent characterizing activations in the class. For small constant values of $k^*$, this yields **the first polynomial sample and time agnostic learner** that goes well beyond the monotone case. Prior work does not achieve this error guarantee **even when restricted to** $k^*=1$.

Meta-review: 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.
Decision: Accept (poster)