On Single-Index Models beyond Gaussian Data
Authors: Aaron Zweig
Loucas Pillaud-Vivien
Joan Bruna
Venue: NeurIPS 2023 poster (2023)
Keywords: gradient descent
shallow neural networks

Abstract: Sparse high-dimensional functions have arisen as a rich framework to study the behavior of gradient-descent methods using shallow neural networks, and showcasing its ability to perform feature learning beyond linear models. 
Amongst those functions, the simplest are single-index models $f(x) = \phi( x \cdot \theta^*)$, where the labels are generated by an arbitrary non-linear link function $\phi$ of an unknown one-dimensional projection $\theta^*$ of the input data. By focusing on Gaussian data, several recent works have built a remarkable picture, where the so-called information exponent (related to the regularity of the link function) controls the required sample complexity. In essence, these tools exploit the stability and spherical symmetry of Gaussian distributions.

In this work, we explore extensions of this picture beyond the Gaussian setting, where both stability or symmetry might be violated. Focusing on the planted setting where $\phi$ is known, our main results establish that Stochastic Gradient Descent recovers the unknown direction $\theta^*$ with constant probability in the high-dimensional regime, under mild assumptions that significantly extend ~[Yehudai and Shamir,20].

On Single Index Models beyond Gaussian Data
Joan Bruna
Loucas Pillaud- New York University Flatiron Institute
Aaron Zweig New York University
New York University
Abstract
Sparse high-dimensions functions have arisen as a rich framework to study the behavior of gradient-descent methods using shallow neural networks, showcasing their ability to perform feature learning beyond linear models. Amongst those functions, the simplest are single-index models f(x) o(x 0*), where the labels are generated by an arbitrary non-linear scalar link function ø applied to unknown one one- nne-dimensional projection H* of the input data. By focusing Gaussian data, several recent works have built a remarkable picture, where the so- called information exponent (related the regularity of the link function) controls the required sample complexity. In essence, these tools exploit the stability and spherical symmetry of Gaussian distributions. In this work, building from the framework of Ben Arous et al. [2021). we explore extensions of this picture beyond the Gaussian setting, where both stability or symmetry might be violated. Focusing on the planted setting where ø is known, our main results establish that Stochastic Gradient Descent can efficiently recover the unknown direction 0* in the high- dimensional regime, under assumptions that extend previous works Yehudai and
Shamir 2020
Wu 2022]
Introduction
Over the past years, there has been sustained effort to enlarge our mathematical understanding of high-dimensional learning, particularly when using neural networks trained with gradient-descan methods - highlighting the interplay between algorithmic, statistical and approximation questions. An essential, distinctive aspect of such models their ability to perform feature learning, or to extract useful low-dimensional features out of high-dimensional observations.
An appealing framework to rigorously analyze this behavior are sparse functions of the form f(z) p(O] .r), where the labels are generated by generic non-linear, low-dimensional function Φi R of linear features O H, with θ, E kd with k < d. While the statistical and approximation aspects of such function classes are by outstanding challenge remains computational, in particular in understanding the ability of gradient- descent methods to succeed. Even in the simplest setting of single-index models (k: 1), and assuming that ø is known, the success of gradient- based learning depends on an intricate interaction and the 'link' function and in fact computational lower bounds
well-understood Barron 1993), Bach (017)) the
between the data distribution are known for certain such choices Yehudai and Shamir 2020), Song et al. [202]] Goel et al. 2020 Diakonikolas al. (2017), [Shamir [2018].
Positive results thus require to make specific assumptions, either about the data, or about the link function, or both. On one end, there is a long literature, starting at least with Kalai and Sastry 2009 ,,
al. [2010), Kakade et al. [2011), that exploits certain properties of o. such as invertibility or monotonicity. under generic data distributions satisfying mild inti-concentration properties /oltanolkotabii 2017]. Frei et al. [2020), Yehudai and Shamir 2020) Wu (022). On the other end, by focusing on canonical digh-dimensiooal measures such as the Gaussian distribution,
the seminal works Ben Arous al. [202 Dudeja and Hsu 2018 built harmonic analysis
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

framework of SGD, resulting in fairly complete picture of the sample complexity required to learn generic link functions @ and revealing a rich asymptotic landscape beyond the proportional regime = d. characterized by the number of vanishing moments, or information exponent s of r. whereby n = d=-1 samples are needed for recovery. Since then, several authors have built and enriched this
setting to multi-index models Abbe et al. [202] [023). [Damian et al. [2022]. Arnaboldi et al. [2023). | addressing the aami-paraettric learning of the link function Bietti et al. [2022], as well as exploring SGD-variants Ben Arous et al. (2022). Barak et al. (2022). Berthier et al. [0023] Chen et al. 2023
This harmonic analysis framework relies on two key properties of the Gaussian measure and their interplay with SGD: its spherical symmetry and its stability by linear projection. Together, they provide an optimization landscape that is well-behaver in the limit of infinite data, and enable SGD to escape the 'mediocrity' of initialisation, where the initial direction 0b in the high-dimensional setting, has vanishingly small correlation (6g 0*1 1/vd with the planted direction 0*
In this work, we study to what extent the 'Gaussian picture' is robust to perturbations, focusing on the planted setting where known. Our motivation comes from the fact that real data is rarely Gaussian, yet amenable to being approximately Gaussian via CLT-type arguments. We establish novel positive results along two main directions; (i) when spherical symmetry is preserved but stability is lost, and (ii) when spherical symmetry is lost altogether. In the former, we show that spherical harmonics can be leveraged to provide a benign optimization landscape for SGD under mild regularity assumptions, for initialisations that can be reached with constant probability with the same sample complexity as in the Gaussian case. In the latter, we quantify the lack of symmetry with robust projected Wasserstein distances, and show that for "quasi-symmetric" measures with small distance to the Gaussian reference, SGD efficiently succeeds for link functions with information exponent S 2. Finally, using Stein's method, we address substantially 'non-symmetric" distributions, demonstrating the strength and versatility of the harmonic analysis framework.
2 Preliminaries and Problem Setup
The focus of this work is to understand regression problems with input/output data (z, v) IR x I generated by single-inde linge--idex models. This is a class of problems where the data labels are produced by non-linear map of viediinnnsionll projection of the input, that is
y = 6(x - -0))
(1)
where Ø : IR + F is also known as the link function, and H E SSa-1, the sphere of Rdd is the hidden direction that the models wants to learn. Quite naturally, the learning is made through the family of generalized linear predictors H. (0o : x + Φ(x 8), for Ó S built upon the link function (which is assumed known) and parametrized by the sphere.
Loss function. We assume that the input data is distributed according to a probability v E P(RRd) Equation (1) implies that the target function that produces the labels, Φe-, lies in this parametric class. The overall loss classically corresponds to the average over all the data of the square penalisation 1(0,x) x) = (z) Φe- )2 2 so that the population loss writes
(()) = Ey [d((x - 0)- - 6(x 0²))²
21 = 11:00 - P0- 112
where we used the notation || 22 = E. valid for all p E N Let us put emphasis on the fact that the loss L is non-convex function of the parameter 0, hence it is not priori guaranteed that gradient-based method are able retrieve the ground-truth 0*. This often requires a precise analysis of the loss landscape, and where the high-dimensionality can play a role of paramount importance: we place ourselves in this gigh-dimensional setting for which the dimension fixed but considered very large d >> 1. Finally, we assume throughout the article that de belongs to the weighted Sobolev space W:1.4 ;= { such that suppes.-1 [| r. + [6llzz] < 00).
Stochastic gradient descent. To recover the signal given by 8* E S we run online stochastic gradient descent (SGD) on the sphere S2-1. This corresponds to having at each iteration t N* fresh sample I drawn from v and independent of the filtration F. = o(11,..., It-11) and performing spherical gradient step, with step-size 8 0, with respect to 0 - I(0, 2().
8, oV,1(0,,
0
with initialization O. ~ Unif(Sa-1), (3)
0.
2

---

An important scalar function that enables to track the progress of the SGD iterates is the correlation with the signal my := 6 0+ E [-1, 1]. We will drop the subscript in case there is no ambiguity. Note that, due to the high-dimensionality of the setup, we have the following lemma:
Lemma 2.1. For all a >> 0, we have Pe, (me, 2 a/vd) S La'e /4, Additionally, for any d > 0 such that max(a, 8) I vd/4, we have the lower bound: Po, (me, 2 a/ 2 _e -e-aa+0)²
This fact implies that, when running the algorithm in practice, it is initialized with high probability near the equator of Sa-1. or at least in a band of typical size 1/vd (see Figure for schematic illustration of this fact). Finally, we use the notation V to denote the spherical gradient. that is Vg((0, .2) = Vol(0, .)) (0, x) 0)0. As V (t,) is an unbiased estimate of V L, it is expected that the latter gradient field rules how the SGD iterates travel across the loss landscape.
Loss landscape in the Gaussian case. As stressed the introduction, this set-up has been studied by Dudeja and Hsu [2118). Ben Arous et al. [202]] in the case where // is the standard Gaussian, noted as y here to avoid any confusion for later. Let us comment a bit this case to understand what can be the typical landscape of this single-index problem. Thanks to the spherical symmetry, the loss admits a scalar summary statistic, given precisely by the correlation mg. Moreover, the loss admits an explicit representation in terms of the Hermite decomposition of the link function di if (h₂} denotes the orthonormal basis of Hermite polynomials of L then L(O) 2 2x, 1(0, ((,,,)))1 (1)) ) == E(m). As result, the gradient field projected along the signal is a (locally simple) positive function of the correlation that behaves similarly to
LV) ~ Cm Cm (L-m) m).
where & E N* is the index of the first non-zero of the Hermite coefficients {(é) hy) }j- This has at least three important consequences for the gradient flow: (i) if initialized positively, the correlation is an increasing function along the dynamics and there is no bad local minima in the loss landscape, (ii) the parameter E N controls the flatness of the loss landscape near the origin and therefore controls the optimization speed of SGD in this region (iii) as soon as m is large enough, the contractive term 1 m makes the dynamics converge exponentially fast.
Obviously for general distributions v, the calculation presented in (4. is no-longer valid. However, the crux of the present paper is that properties (i)-(i))(iii) are robust to the change of distribution and can be shown be preserved under small adaptations. More precisely, we have the following definition.
Loss landscape in general cases.
Definition 2.2 (Local Polynomial Growth). We say that L, has the local polynomial growth of order 1 E N' and scale Z 0, if there exists C > O such that for all mg Z
L() 0r 2 C(1 - mg) (ma b) 6-1
(5)
In such case we say that L. satisfies LPG b).
In this definition, and as showed later in specific examples given in Section 4 the scale parameter b should be thought as a small parameter proportional to 1/vd. If v is Gaussian, we can rewrite Eq. and show that L verifies LPG(s, 0) for E N referred to as the information exponent of the problem in Ben Arous et al. [202 An important consequence of satisfying LPG b) is that the the population landscape is free of bad local minima outside the equatorial band Σ, := (0 e Sa-1, me < b). Therefore, when b is of scale 1/ 1/Vd, Lemma 2.1 indicates that one can efficiently produce initializations that avoid it. Hence, this property is the Tundamental ingredient that enables the description of the path taken by SGD that we derive in the next Section. Section is devoted to showcasing generic examples when this property is satisfied.
3 Stochastic Gradient Descent under LPG
In this section, we derive the main results the trajectory of the stochastic gradient descent. They state that the property LPG(s, vdv is in fact sufficient to recover the same quantitative guarantees as the one depicted in Ben Arous et al. 202T], despite the lack of Gaussianity of the distribution v. Recall that the recursion satisfied by the SGD iterates is given by Eq. To describe their movement, let us introduce the following notations: for all t E N we denote the normalization and the martingale induced by the stochastic gradient descent as Me := [(0,, xz) x)].
by rı := 00 ov.
3

---

Moment growth assumptions. To be able to analyse the SGD dynamics, we make the following assumptions on the moments of the martingale increments induced by the random sampling. Let us denote for all 0 E IRd -ig- = x 0 E R and Cuu, v) Ø' (u))(v), for u, v E IR
Assumption 3.1 (Moment Growth Assumption). There exists a constant K > O, independent of the dimension d, such that
sup 0ES
Ez 100 Cr vo.)) )] V Ex [ (ro, s K, s Kdd, for = 1, 2.
and,
(6)
| 2k C² (20,,
sup
#ES
precise care is given to the dependency in the dimension in the upper bound to match the practical cases that we later discuss in Section[4 4 Note that these assumptions are typically true for sub-gaussian random variables if Φ belongs to a Sobolev regularity class. These assumptions are similar to the one given in Eqs. (1.3)-(1.4) in Arous et al. [2021) for the Gaussian case. In all the remainder of the section we assume that Assumption 3.1 is satisfied.
Tracking the correlation. Recall that the relevant signature of the dynamics is the one-dimensional correlation my = 8₂ - 6" For infinitesimal bee-sizees 5 - 0, it is expected that 0, follow the spherical gradient flow O,- = V [(O.,, that translates to the evolution on the summary statistics me whereby
vr L(.) -
The main idea behind the result of this section is to show that, even if the energy landscape near m = me is rough at scale 1/ dd, the noise induced by SGD does not prevent m to grow as the idealized dynamics described by the ODE 8 Let us write the iterative recursion followed by (m,))20: with the notation recalled above, for I E N*, we have
m++1 (m- - L()) 0r - M.
(9)
With this dynamics at hand, the proof consists in controlling both the discretization error through Ti and the directional martingale induced by the term 8 M, 0*
Weak recovery. As is the case for the gradient flow, most of the time spent by the SGD dynamies near the equator, or more precisely a band of the type Σt,e = {0 E Sa-1, b/Vd s mg S c/Vd), where b < are constants independent of the dimension. Hence, the real first step of the dynamics is to go out any of these bands. This is the reason why it is natural to define S.- := {0 Sa-1; mg 2 a}. the spherical cap of level a E (0, 1) as well as the hitting time
T == inf 0, ma, 2 2a,
(10)
which corresponds to the first time (0t) enters in Sa. We fix a dimension dimension-independdee independent constant a = 1/2, and refer to the related hitting time 71//2 as the weak recovery time of the algorithm.
Theorem 3.2 (Weak Recovery). Let (0.)120 follow the SGD dynamics of Eq. 3 and let L satisfy
LPG(s, b/Vd), with b > O and E N", then, conditionally on the fact that me 2 Sd/ for any
0 < E S Ex, we have
d K/E d logg2()) K/e d= K/E
when s = 1, and with the choice
8 = e/d
1/2 S
when 8 = 2, and with the choice
8 = 8 e/dd log d)
(11)
when s 2 3, and with the choice
8 = s/2
with probability at least 1 Ke, for generic constants K, E. 0 that depend solely on the link function & and the distribution v.
Let us comment on this result. It says that that the integer coming from the growth condition controls the hardness of exiting the equator of the sphere. Indeed, as can be seen in LPG(s, b/ Vd). the larger the 8, the smaller the gradient projection and hence the less information the SGD dynamics has to move from the initialization. This result can be seen an extension of (Ben Arous et al. 2021 Theorem 1.3] valid only in the Gaussian case (b 0). Furthermore, the Gaussian case shows that Theorem 3.2 is tight up to log(d) (d) factors. Finally, note that the result is conditional to the fact that the

---

0"
b/va
Ow
Figure 1: Sketch of the SGD dynamics. After a long time spent in band of typical size 1/ 1/vd, the dynamics escapes at weak recovery point Ow and then goes rapidly to the ground-truie trutttruhhhh 0*
initialization is larger that some constant factor of 1/ 1/vd, which has at least constant probability to be lowered by any constant factor by sampling
happen in virtue of Lemma 2.1 This probability offline a constant factor (independent d) i..dd initializations and keeping the one that maximizes its correlation with 0* Finally, note that in all the cases covered by the analysis, it is possible to w.r.t the Gaussian the one hand and (ii) on the Sobolev norm of the link function || the other.
keep track of the constant C, and show that overall depends only (i) on the property
Strong recovery. We place ourselves after the weak recovery time described in the previous question and want to understand if the (6,)220 dynamics goes to 0 and if yes, how fast it does so. This is what we refer to as the strong recovery question, captured by the fact that the one-dimensional summary statistics m go towards 1. Thanks to the Markovian property of the SGD dynamics, we have the equality between all time s > marginal laws of
Origtt /
Law
0g 0, 0 0
11/2
and hence the strong recovery question is equivalent to study the dynamics with initialization that has already weakly recovered the signal, i.e. such that ma = 1/2. We show that this part of the loss landscape is very different that the equator band in which the dynamics spends most of its times: in all the cases, we can choose stepsizes independent of the dimension and show that the time reach the vicinity of 6* will be independent of d.
Theorem 3.3 (Strong Recovery). Let (0e)c20 follow the SGD dynamics of Eq. B and let L satisfy LPG(s, b/ dd), with time T 0, such that
and s E N², then, for any 0, laking /dd, we have that there exists
[1 - mrl S E, and
[T T|/2 S (dl
(12)
with probability at least 1 for some generic K 0 that depends solely of the link function Φ.
As introduced above, the important messages conveyed by this theorem are that (i) there is no difference between the different parameters setups captured by the information exponent s, and (ii) the time takes to reach an e-vicinity of is always strictly smaller than the one needed to exit the weak recovery phase (e.g. d compared to d=-1 when 3). This means that the dynamics spends most of its time escaping the mediocrity. Remark that we decided to present Theorem 3.3 resetting the step-size 5 put emphasis the intrinsic difference between the two phases. Yet, could have kept the same stepsize at the expense of slowing the second phase.
4 Typical cases of loss landscape with LPG property
In this section, we showcase two prototypical cases where the LPG holds true: the section 4.1 deals with the spherically symmetric setting, whereas the section 4.2 describes perturbative regime where the distribution is approximately Gaussian is quantitative sense.
5

---

4.1 The symmetric case
We start our analysis with the spherically symmetric setting. We show that spherical harmonic decomposition provides a valid extension of the Hermite decomposition in the Gaussian case, leading to essentially the same quantitative performance up to constant (in dimension) factors.
Spherical Harmonic Representation of the Population Loss. We express the data distribution as mixture of uniform measures v = Jo Tr.d p(dr). where Tr.d = Unif(rSa-1). Let TO T1.d and d. P([ 1, 1)) be the projection of Ta onto one direction, with density given in close form by ua((t)) Z (1 (2)(d-3)/21 ((4) S 1)dt, where Z is a normarlizing factor. Let {Paa)eeN be the
orthooonal basis of Gegenbauer polynomials of L ([-1, ([), normalized such that (3.((1) = 1 for
all j. d. For each r > 0, consider
(0) == (do: Qu- ) = (6bb) 1000) )
where we define ((r) [-1, + R such that (1) == @(rt). We write its decomposition
in ( (1-1, 1]) ()()) E; aj.r.aP.d with Ojjr,d -
(p Let Z2g be the Lebesgue
measure of S and N d(, 2 (d+j-3) the so-called dimension on the spherical harmonies of degree j in dimension d. From the Hecke-Funk representation formula (Frye and Efthimiou 2012
d
Lemma 4.23] and the chosen normalization (1,((1) = 1, we have || 94 and Efthimiou 2012 Proposition 4.15) and obtain finally
Frye
2N(d)
(0) -, L CrraPr.a .0)
(13)
where we defined for convenience aj,r,d = aj,raa/ V dj. As a result, it follows that the overall
loss writes as solely the correlaton mg = 0 0* as
((0) 211
Σ,
== =(mm)
(14)
where Jo a², a. s dr) > 0. Unsurprisingly, we observe that, thanks to the spherical symmetry and analogous to the Gaussian case, the loss still admits = 0 0-0 6* as a summary statistics. Yet, it is represented in terms of Gegenbauer polynomials, rather than monomials as in the Gaussian case. The monomial representation is a consequence of the stability of the Gaussian measure, as seen by the fact that (Øe. 63) (ó. Av.g%) where (t) = [f + v1 - //-m32)) has a semi- group structure (it is even known fact as the Ornstein- Ulhenbeck semi-group).
Let P(R) be the marginal of along any direction. The following proposition charaterizes the coefficients Bi. as integrals over the radial distribution p and projections of the link function di Proposition 4.1 (Loss representation). The 3r,d defined (4) have the integral representation
Bid = (d,, K. ()) L3
(15)
where K, is a positive semi-defiiite integral operator of L2 that depends solely on p and Φ.
Note that a closed form expression of K. can be found in Appendix D.2 The above proposition is in fact the stepping stone to calculate properly the information exponent that plays crucial role in the property LPG. This given through the link between the spectrum 33.d and the decomposition of ø in the L orthogonal basis polynomials, that we denote by {qr}g.
Proposition 4.2. Let s = (n; BJ,a > 0} and inf [j: (0, (e,4),, * 0). Then 8 S
Thus, the number of vanishing moments of & with respect to the data marginal n provides an upper bound on the "effective" information exponent of the problem as we will see next.
Local Polynomial Growth. From 14 and V (()) = (m -m0), we directly obtain
LS = m1- = 2(1 m²) Σ, By.aPj
(16)
which the quantity we want to understand to exhibit the property LPG in this case. Hence, we now turn into the question of obtaining sufficient guarantees the coefficients (3g,a); that ensure

---

local polynomial growth. Since the typical scale of initialization for m is (1/VVd), our goal is to characterize sufficient conditions of local polynomial growth with 6 = O(I/vd).
For that purpose, let us define two key quantities of Gegenbauer polynomials:
Uj.d == min (t) (0,1)
(smallest value)
(17)
3j, = arg max (t E (0. 1); P3.(t)) = 0}
(largest root)
(18)
We have the following sufficient condition based the spectrum (3g,))):
Proposition 4.3 (Spectral characterization of LPG). Suppose there exist constants K, C > 0 and 8 E N such that we both have 3a,d 2 C and Ej>s 35aā J + 2) I Kd(3-a)/2 Then, taking s" as the infinum of such s. L has the property LPG(ss 1,, .d). In particular, whenever s* < d, we have 2 .d S ////' /d.
This proposition thus establishes that, modulo mild regularity assumption expressed though the decay of the coefficients 33.d. the spherically symmetric non- Gaussan setting has the same geometry as the Gaussian setting, for correlations slightly above the equator. Crucially, the required amount of correlation to 'feel' the local polynomial growth is a ((vs) factor from the typical initialization, and can be thus obtained with probability = over the initialization, according to Lemma 2.1 lower bound which is independent of d.
The sufficient condition for 3g appearing in Proposition 4.3 involves the minimum values Uy of Gegenbauer polynomials Pj.a. as well as sums of the form E In order to obtain a more user-friendly condition, we now provide an explicit control of Uj.ds and leverage mild regularity of ø to control Σ; j2 9y.d- This motivates the following assumption on e and
Assumption 4.4. The link function & satisfies & E L and d' E L.g. and the radial distribution has finite fourth moment [p < co.
Theorem 4.5 (LPG for symmetric distributions). Assume that & and v satisfy Assumption 4.4 and let 3* inf (é, qz)n, * 0}. Then L has the property LPG(s* - 1,,2/s*fo0
The proof's is provided in Appendix D.5 At technical level, the main challenge in proving Theorem 4.5 to achieve a uniform control of Uj in J. a result which may be of independent interest. We address it by combining tate-of-the-ar bounds on the roots of the Gegenbauer polynomials, allowing us to cover the regime where j is small or comparable to d, together with integral representations the Cauchy integral formula, providing control in the regime of large j. On the other hand, we relate the sum ン Br, to a norm of ø' using a Cauchy-Schwartd Schwartz argument, where we leverage the fourth moments from Assumption 4.4
Remark 4.6. Since we are selting where & known, an alternative the original recovery problem from Eq (2) is to consider a pure Gegenbauer 'student' link function of the form 6 Ps.d. where: 8 is the information exponent from Proposition 4.2) Indeed, the resulting population loss
[(0) = [[(((x - 8) ő(x {²] satisfies the LPG property, as easily shown in Fact D.5
For the sake of completeness, we describe more precisely two concrete case studies below.
Example 4.7 (Uniform Measure on the Sphere). When Unif( / VdSa-1), we have p p= 8 and therefore ,i 2² 2.va, In that case, the orthogonal polynomial basis {g)(1))} of 122 coincides with the rescaled Gegenbauer polynomials, (t()) Pj.((t/Vi), Consider now a link function Ø with vanishing moments with respect to L i.e. such that āj, (Ø) 9s)n 0 for j < s and ō..d 9.), + 0; and with sufficient decay the higher harmonics as to satisfy the bound on the sum presented in Proposition 4.3 (for example, @(t) (t(t) trivially satisfies this condition).
Then Proposition 4.3 applies and we conclude that the resulting population landscape satisfies
LPG(s - 1, O s/d)).
In Yehudai and Shamir 2020 Wu 2022 it is shown that monotonically increasing link function lead to a benign population landscape, provided the data distribution v satisfies mild anti-coneentration properties. We verify that in our framework.
frr link functions where their monotonic behavior dominates; Wu 2022
7

---

Example 4.8 (Non-decreasing é). Indeed, Proposition 4.3 is verified with 1. provided ø' E L'g Indeed, Φ + assume without loss of generality that @(t) 2 for 2 0 and (()) S for i S 0.
is monotonic, then we have 31 = (0. Kio), = Ca (to,(t((()) + 0 since we can
We emphasize that the results Yehudai and Shamir 2020 Wu 2022 extend beyond the spherically symmetric setting, which is precisely the focus of next section.
4.2 Non-Spherically Symmetric Case
We now turn to the setting where is no longer assumed to have spherical symmetry. By making further regularity assumptions on o, our main insight is that distributions that are approximately symmetric (defined in appropriate sense) still benefit from well-behaved optimization landscape.
Two-d Pro-dimensional Wasserstein Distance. When is not spherically symmetric, the machinery of spherical harmonics does not apply, and we thus need to rely on another structural property. Consider centered and isometric data distribution E P2( i.c. such that E, 0 and
Σ, Eg xr
Ia- We consider the two-dimensional 1-Wassertein distance [Niles- and Definition 1] -see also Paty and Cuturi [019] between a pair distributions
Rigollet 2022
Va, E ( defined as
W1,2 = sup W Wi PWv1),
(19)
PEGr(2,d)
where the supremum runs for any two-dimensional subspace P E Gr(2, d), and PaU E P(R)2) is the projection (or marginal) of y onto the span of P. W1,2 is a distance (Patyy and Cuturi 2019
Proposition 1J) and measures the largest 1-Wasserstein distance over all two-dimensional marginals. We are in particular interested in the setting where Va- v our data distribution, and vs is reference symmetric measure - for instance the standard Gaussian measure Ya. Consider the fluctuations
A (0) = [T.(0) - E(mm)) and
(20)
AV (0) = (T) 0" - F (1 - -m²)
(21)
where {(m) is the Gaussian loss defined in Section and L(0) = E,, [1o(1 0) (0xx=((xx)))) 00) Ar. and ávz thus measure respectively the fluctuations of the population loss and the relevant (spherical) gradient direction. By making additional mild regularity assumptions can obtain a uniform control of the population loss geometry using the dual representation of the 1- Wasserstein distance.
the link function o,
Assumption 4.9 (Regularity of link function). We assume that o' are both B-Lipschitz, and that (1) = (11/t)
Assumption 4.10 (Subgaussianity). The data distribution v is M M-subgaussian: for any u E Sa-1. we have || vllsa S M, where ||=1|ya == inf 0; [[eex(=>//12 S 2 is the Orlitz-2 norm.
Proposition 4.11 (Uniform gradient approximation). Under Assumptions 4.9 and 4.10 for all 0 E Sa-1-
(V = (1 (1-m²) (Wi,2(,, v) (W1, 7)-
(22)
where the O(-) notation only hides constants appearing in Assumptions 4.9 and 4.10
In words, the population gradient under v viewed as a perturbation of the population gradient under y, which has the bell-behaved geometry already described in Section 2 These perturbations can be uniformly controlled by the projected 1- I-Wasserstein distance, thanks to the subgaussian tails v.
Our focus will be in situations where (I,((V 7) O(1/Vd). This happens to be the 'natural' optimistic scale for this metric in the class of isotropic distributions Σ, Id, as can be seen for instance when v= = Unif( VdS,-1). Under such conditions, turns out that link functions with information exponent
2 can be recovered with simple gradient-based methods, by paying an additional polynomial (in d) cost in time complexity.
Assumption 4.12. The Gaussian information exponent of c), 8 = arg min (:: (0, H2) * 0) satisfies < 2.
8

---

Assumption 4.13. The projected Wasserstein distance satisfies (1, - M' Mv/V
Proposition 4.14 (LPG, non-symmetric setting). Under Assumptions 4 9
4.10
4.12 and 4.13
(V (log d
verifies LPG 1,,0
where depends only B,M, M'.
This proposition illustrates the cost of breaking spherical symmetry in two aspects: (i) it requires additional regularity on d. and notably restricts its (Gaussian) information exponent to s = 2. and (ii) the scale to reach LPG is now no longer dimension-free but has polynomial dependency on dimension, since from Lemma 2.1 picking any positive constant we have
Peo (maa) 2 /logd=//a)
8 4
(VTog 4-62 2 2 (d=(1+o()))
We are not able to rule this out as a limitation of our proof; whether this polynomial dependency on dimension is inherent to the symmetry breaking is an interesting question for future work.
While assumptions
4.9 4.10 4.12 transparent and impose only mild conditions on the link function and tails of p. the 'real' assumption of Proposition 4.14 is the concentration of W1, (2,7)
(Assumption 4.13). The ball {v; W1,2(v,7) = O(1/Vd)} contains many non-symmetric measures, for instance empirical measures sampled from y with n = wdd²) (Niles and Rigollet 2022 Proposition 8), and suspect contains many other examples, such as convolutions of the form y/ arising for instance in diffusion models. That said, one should not expect the distance 2 (v, 7) to be of order 1/ V for generic 'nice' distributions vı for instance, log- log-concave distributions are expected to satisfy W₁ (P = 1//d d for most subspaces P. as captured in Klartag's ' CLT for convex bodies |Klatta| [007].
Localized Growth via Stein's method. To illustrate the mileage of the previous techniques beyond this "quasi-symmetric" case, we consider now an idealised setting where the data is drawn from a product measure p n7 with 1 E P(R) and W1 (1 71) O()). In other words, = ( x.) ~ v if o; ~ 7 are i..d. In this setting, the distances (I 7) reflect a CLT phenomena, which requires the subspace P 'mix' across independent variables. Consequently, one may expect the expression of the hidden direction H* in the canonical basis to play certain role so we make the following additional regularity assumption on the tails of Φ::
Assumption 4.15 (Additional Regularity in third derivatives). & admits four derivatives bounded by L, with (0) (t) O(1/t) and jo 4) (t) 0(1/E), Moreover, the third moment of the data distribution is finite: T3- E < co.
Stein's method provides powerful control (f) and ( shown by the following result:
Proposition 4.16 (Stein's method for product measure). Lel x(0,0") = |0013 11001 Under
Assumptions 4.9 4.10 and 4.15.15 there exists a universal constant C = C(M, Ba) such that
(2 S Cx(0, 0*) and (v < - (")
(23)
The proof is based the Stein's 's method for multivariate variables [Röllin 2013 Theorem 3.1] with independent entries, which provides a quantitative CLT bound. Contrary to the quasi-symmetric case, here the concentration is uniform over the sphere, but crucially depends the sparsity of both 0 and 0*, measured via the Ea norms |0]]4, ||0 [|4: for incoherent, non-sparse directions, we have ||0|]]|| = 1/Vd, recovering the concentration rate that led to Proposition 4.14 while for sparse directions we have |Ø]] = (11. indicating an absence of concentration to the Gaussian landscape.
Therefore, the natural conclusion is to assume a planted model where 0" is incoherent with the data distribution, i.e. ||0*|| (4) While the LPG property does not directly apply in this setting, we outline an argument that suggests that the single-index model can still be efficiently solved using gradient-basee methods. For that purpose. we assume that 0* is drawn uniformly in Sa-1, which implies that its s norm ||0*| ||ă is of order d 1/2 with high probability:
Fact 4.17. Assume 6* Unif(Sa-1). Then P([ 113 s C/va) 2 1 C' exp(-C).
Because Op is also drawn uniformly on the sphere, the typical value of x0, 0*) is of order d12//2 For Gaussian information exponent 2, the population gradient under Gaussian data satisfies

---

-- (0))-0 2 Cma. As consequence, by Proposition whenever 100-0" > ev (which happens with constant probability lower bounded by e" we enter 'local' LPG region where L()) 0r > C(m c/ vd) > O. While this condition is sufficient in the quasi-symmetric setting to start accumulating correlation (Theorem 3.2). now this event is conditional on being dense, so that x(0, 0*) = O(1/vd).
Since the typical value of x(0, 0*) is of scale 1/Vd, one would expect that SGD will rarely visit sparse points where x(0, 0*) > O(1/vd), and thus that the local LPG property will be valid for most times during the entropic phase of weak recovery, summarized by the following conjecture:
Conjecture 4.18 (SGD avoids sparse points). Assume 0*, Oo are drawn from the uniform measure, and let Og be the t-th iterate of SGD with å = 1/ d). There exists a universal constant C such that for any & > O, we have
c flog T d
P sup 10.112
2
S Ceep(-
(24)
Since the time to escape mediocrity in the case s 2 is T' ~ d'log(d),, this conjecture would imply that SGD does not effectively 'see' any sparse points, and thus escapes mediocrity. If one assumed that in this phase the dynamics is purely noisy, now pretending that 6; were drawn independently from the uniform measure, and that |00| approximately Gaussian with mean d= and variance d the result follows by simple concentration. The challenging aspect of Conjecture/4.18]s precisely to handle the dependencies across iterates, as well the spherical projection steps.
Experiments
In order to validate our theory, and inspect the degree to which our bounds may be pessimistic, we consider empirical evaluation the training process our two primary settings. Specifically, we consider random initialization on the half-sphere (with the sign chosen to induce positive correlation as in Arous et al. (20TT), and investigate how often strong recovery occurs relative to the information exponent of the link function. Ultimately the empirical evidence corroborates the theory, showing the symmetric case succeeds when the initial correlation is above a polynomial threshold and the non- symmetric case succeeds as long as 2. Due to space constraints, the details of the experimental setup and further discussion appear in Section A
6 Conclusion and Perspectives
In this work, have asked whether the remarkable properties of nigh-dimensional Gaussian SGD regression of single-index models are preserved as one loses some key aspects that make Gaussian distributions special (and appealing for theorists). Our results mostly positive, indicating robustness of the Gaussian theory, especially within the class of spherically symmetric distributions, where a rich spherical harmonic structure is still available. As one loses spherical symmetry, the situation becomes more dire, motivating a perturbative analysis that we have shown is effective via projected Wasserstein and Stein couplings.
That said, there several open and relevant avenues that our work has barely touched upon, such as understanding whether the robustness can be transferred to other algorithms beyond SGD, or addressing the cerimearaettric problem when the link function is unknown, along the lines of Bietti et al. 22022, Abbe et al.] 2023 Damian et al. (2022), Berthier et al. 2003) A particularly interesting direction of future work is extend the analysis of product measures to 'weakly dependent'
distributions, motivated by natural images where locality in pixels captures most (but not all) of the
statistical dependencies. Stein's method appears be a powerful framework that can accommodate such weak dependencies, and deserves future investigation.
Acknowledgements This work was partially supported by NSF DMS 2134216, NSF CAREER CIF 1845360, NSF IIS 1901091 and the Alfred P Sloan Foundation.
10

---

References
Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-staircantt property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks, arXiv preprint 22XX::2202.086555 2022.
Emmanuel Abbe, Enric Adira,, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and suddle-t-ssadle dynamics. arXiv preprint arXiv:2302.11055 2023.
Iván Area, Dimitar K. Dimitrov, Eduardo Godoy, and André Ronveaux. Zeros of gegenbauer and hermite polynomials and connection coefficients. Math. Comput., 73:1937-1951, 2004.
Luca Arnaooldi, Ludovic Stephan, Florent Krzakala, and Bruno Loureiro. From nigh-diimessioal mean-field dynamics to dimensionless odes: A unifying approach to sgd in two-layers networks. arXiv preprint arXiv:2302.055:: 2023.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. The Journal of Machine Learning Research, 22(1):4788-435 4838, 2021.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systemx, 35:2 15:21750-21164, 2022.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3)9330-94,, 1993.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research (JMLR), 22:106-1, 2021.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. High-dimensional limit theorems for sgd: Effective dynamics and critical scaling. arXiv preprint arXiv:2206. 200.0220060 2022.
Raphaël Berthier, Andrea Montanari, and Kangjie Zhou. Learning time-scales in two-layers neural networks. arXiv preprini 23X3::230300055: 2023.
Alberto Bietti, Joan Bruna, Clayton Sanford. and Min Jae Song. Learning single-index models with shallow neural networks. In Advances in Neural Information Processing Systems, 2022.
Sitan Chen, Zehao Dou, Surbhi Goel, Adam R Klivans, and Raghu Meka. Learning narrow one- hidden-layer relu networks. arXiv preprint arXiv:2304. 10524, 2023.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, 2022.
Laura De Carli. Local lp inequalities for gegenbauer polynomials. In Topics in classical analysis and applications in honor of Daniel Waterman, pages 73-87, World Scientific, 2008
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73 84. IEEE, 2017.
Dimitar K. Dimitrov and Geno P. Nikolov. Sharp bounds for the extreme zeros of classical orthogonal polynomials. Journal of Approximation Theory, 162(10):1733-1844 2010. ISSN 0021-9045. doi: sciencedirect. com/ sts/sciincccc atticle/pp1//00011945609999999 Special Issue dedicated the memory Borislav Bojanov.
https://doii.rrg/100001166
.006.
DLMF. NIST Digital Librury of Mathematical Functions. https://dlmt nist. mist.gov/ Release 1. of 2023-06-15, 15, 2022. URL httpp::/ //dmmf nist gov/ F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. Schneider, R. Boisvert, Clark, B. R. Miller, V. Saunders, H. S. Cohl, and M. A. McClain, eds.

---

K. Driver and K. Jordaan. Bounds for extreme zeros of some classical orthogonal polynomials. Journal of Approximation Theory, 164()):200-1204, 2012. ISSN 0021-9045. doi: https://doi. org/10. p11/$002190455200106)
Rishabh Dudeja and Daniel Hsu. Learning single-index models in gaussian space. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1887-1930. PMLR, 06-09 Jul 2018. URL httts::/proceeddnggg
www.srressev.. v/tsss///5////i dudeeeaa httml
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 110-118, 1975.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-5428,, 2020.
Christopher Frye and Costas J Efthimiou. Spherical harmonics in p dimensions. arXiv preprint 1rX5v:1205.3546 2012.
Walter Gautschi. Some elementary inequalities relating to the gamma and incomplete gamma function. J. Math. Phys, 38(1):87--8) 1959.
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pages 3587-3596. PMLR, 2020.
Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24, 2011.
Adam Tauman Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT, 2009.
Boaz Klartag. A central limit theorem for convex sets. Inventiones mathematicae, 168( 11):1911111,, 2007.
Andrea Laforgia and Pierpaolo Natalini. On some inequalities for the gamma function. Advances in Dynamical Systems and Applications, 8(2):261-267, 2013.
Jonathan Niles-Weed Weed and Philippe Rigollet. Estimation of wasserstein distances in the spiked transport model. Bernoulli, 28(4):2663- 2688, 2022.
François-Pierre Paty and Marco Cuturi. Subspace robust wasserstein distances. In International conference on machine learning, pages 5072-5081. PMLR, 2019.
Adrian Röllin. Stein's method in high dimensions with applications. In Annales de l'IHP Probabilités et statistiques, volume 49, pages 529-549, 2013.
Shai Shalev-Shwartz. Ohad Shamir, and Karthik Sridharan. Learning kernel-based halfspaces with the zero-one loss. arXiv preprint 1005.366. 2010.
Ohad Shamir. Distribution-specific hardness of learning neural networks. The Journal of Machine Learning Research, 19(1):1135-113, 2018.
Mahdi Soltanolkotabi. Learning relus via gradient descent. Advances in neural information processing systems, 30, 2017.
Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. Advances in Neural Processing Systems (NeurIPS), 2021.
Adriaan J Stam. Limit theorems for uniform distributions on spheres in high-dimensional euclidean spaces. Journal of Applied probability, 19())221-228, 1982.
Gabor Szego. Orthogonal polynomials, volume 23. American Mathematical Soc., 1939.
12

---

F Ursell. Integrals with nearly coincident branch points: Gegenbauer polynomials of large degree. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2079): 697-710, 2007.
George Neville Watson, A treatise the theory of Bessel functions, volume 3. The University Press, 1922.
Lei Wu. Learning a single neuron for non-monotonic activation functions. In International Conference Artificial Intelligence and Statistics, pages
PMLR, 2022.
Gilad Yehudai and Ohad Shamir. Learning single neuron with gradient methods. In Conference on Learning Theory, pages 3756-3786. PMLR, 2020.
13


Reviews:
[{"review_id": "xAjnbT19MF", "reviewer": "Reviewer_kUyA", "summary": "This paper studied the online SGD of learning a single-index teacher model with the link function as the student model. This work generalized the results of [Ben Arous et al. 2021], where the information exponent of the link function governs the sample complexity, to the non-Gaussian dataset, where the author raised a local polynomial growth (LPG) to describe the loss landscape.  This LPG prevents the loss landscape to have bad local minima outside a band of the equator. The author provided two cases of loss landscape with LPG: (i) in the spherically symmetric case, similar behavior as the Gaussian case is exhibited; (ii) in the non-symmetric case, more assumptions on link function and feature direction $\\theta^*$ are needed and the deviation between the non-Gaussian and Gaussian distribution in certain metric characterizes the LPG property.", "questions": "1. [Ba et al. 2022] is another paper addressing a semi-parametric problem when the link function is unknown with certain GD training. [Arnaboldi et al. 2023] also studied the SGD training of two-layer neural networks in high-dimensional settings.\n2. Can we consider noisy labels in (1)? \n3. Line 106: information exponent $s$ should be explicitly defined here.\n4. [Tan and Vershynin 2019] considered uniform sphere data distribution, although the link function is only quadratic in this phase retrieval case. The SGD dynamics for the non-Gaussian phase retrieval model may be analyzed in the literature.\n5. Line 154 double \"that\"\n6. Between lines 189 and 190, what is distribution $\\rho$ when we define measure $\\nu$?\n7. In Proposition 7, is there some relation between $s^*$ information exponent $s$ as $d\\to\\infty$? There is a formula describing the relation between Hermite coefficients and spherical harmonic coefficients. Hence, asymptotically, will the results of Example 8 return to the Gaussian case or not?\n8. How about the problem of model misspecification, where the link function of the target is not known?\n\n===================================================================================================\n- Ba, J., Erdogdu, M.A., Suzuki, T., Wang, Z., Wu, D. and Yang, G., 2022. High-dimensional asymptotics of feature learning: How one gradient step improves the representation. Advances in Neural Information Processing Systems, 35, pp.37932-37946.\n- Arnaboldi, L., Stephan, L., Krzakala, F. and Loureiro, B., 2023. From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks. arXiv preprint arXiv:2302.05882.\n- Tan, Y.S. and Vershynin, R., 2019. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. arXiv preprint arXiv:1910.12837.", "limitations": "I think the authors have adequately addressed the potential negative social impact of their work. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Overall, the presentation of this paper is clear, and the motivation of the paper is strong. It is important to generalize online SGD with non-Gaussian data distributions and extend the information exponent of the link function in this general setting. The results obtained by the authors are as sharp as can be expected given the problem under consideration. Although the model studied is simple, the insights derived are non-trivial and the technical approach is original. Especially, in general cases, this paper introduces a two-dim Wasserstein distance to measure the deviation from the Gaussian reference and Stein method for product measures, which are interesting directions for future work.", "weaknesses": "1. Simulations like [Ben Arous et al. 2021] did should be included in the paper. Especially certain non-Gaussian distributions either spherically symmetric or not, should be presented in the simulations to see how information exponent and LPG control the weak recovery and training dynamic.\n2. More examples of non-Gaussian distribution could be mentioned in Section 4. Like Example 8 and 9, there should be some examples for non-spherically symmetric cases in Section 4.2.\n3. Unlike [Ben Arous et al. 2021], there is no lower bound showing the smallest sample complexity for efficient online SGD using LPG in non-Gaussian cases. In the Gaussian case, $n\\ge d^{s-1}$ is nearly tight for online SGD where $s$ is the information exponent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, our response follows:\n\n**Main response**\n\n- *Simulations.* We've included simulations of learning single index models that verify our theory under rotationally invariant and non-Gaussian input distributions in a new draft of the paper.  Specifically, we see that inputs uniform on the sphere only reach strong recovery when the random initialization exceeds the last zeros of the associated Gegenbauer polynomial's largest root, and iid hypercube inputs can reliably learn functions with s = 2 but not s = 3.\n\n- *Examples of non-spherically symmetric.* Typical examples are in fact given in the paragraph between lines 294 and 303. We will state this more precisely as we have done in Examples 8 and 9. Going further, let us mention that studying thoroughly this family of perturbed Gaussian distribution is a relevant (but hard!) question on its own and we consider this study for future investigations.\n\n- *Lower bound.* Generally speaking, a tight lower bound for learning *general* spherical distributions is a desirable result, but not at all as simple as the Gaussian case.  The theory provides a necessary setting for the LPG condition, but unlike the Gaussian case, there can be advantage to choosing a different link function for the student model than the teacher model.  In other words, the range where the loss landscape will be increasing as a function of the correlation $m$ will depend very carefully on the orthogonal polynomials of the radial distribution. That being said, for *specific* problems, as the uniform distribution over the sphere or (obviously!) the Gaussian case, it is relevant to point out it is possible to derive such lower-bounds. We'll add a commentary on this fact in the revised manuscript.\n\n**Answer to specific questions.**\n\nFirst, thank you for the additional papers and the typos, we'll add/correct them and this will help improving the overall quality of the manuscript.\n\n- *Noisy labels.* Yes, subgaussian noisy labels shouldn't make any impact on the analysis since this would simply add an extra noise term in the growth of the correlation $m_t$ that is negligible in the step size regime we are considering. We'll add a comment on this fact.\n\n- *Phase retrieval.* The paper [Tan and Vershynin 2019] in indeed *included* in our setting. This corresponds to $s = 2$, and the second degree Gegenbauer polynomial being a simple parabola, as long as $|x|$ satisfies the decay conditions of Proposition 7, this fits into our framework.\n\n- *Asymptotic case where $d \\to \\infty$.* Asymptotically, yes the Gegenbauer polynomials approach Hermite polynomials (under appropriate scaling by the dimension) as $d \\to \\infty$, so in this limit this returns to the Gaussian case and $s^*$ and $s$ will match.\n\n- *Unknown link function*. Even in the Gaussian case, the story that comes out if the link function is unknown is totally different, and may be subtle. We refer to articles already mentioned in the main text lines 45-46 to show that the way the unknown function is simultaneously learn changes totally the picture. It could be interesting to extend the present analysis to such a framework, but this is obviously not the purpose of the present work.  "}, {"review_id": "mp6bSxGYcf", "reviewer": "Reviewer_VAjP", "summary": "The main contributions of the authors are as follows:\n\n\t(a) Rather than assuming the features are i.i.d. Gaussian, the authors identify a condition called Local Polynomial Growth (LPG, see Def. 2) on the population loss, under which the analysis of Ben Arous et. al. still goes through without any change in their conclusions (see Theorem 3 and Theorem 4 in the paper). Roughly speaking this condition posits a lower bound on the directional derivative of the population loss along the hidden direction at a given point $\\theta$ in terms of the overlap between $\\theta$ and $\\theta_\\star$. \n\n\t(b) In Proposition 7, the authors then verify that the LPG condition holds when the features are sampled from a possibly non-Gaussian, rotationally invariant distribution (for e.g., the uniform distribution on the sphere). \n\n\t(c) In Proposition 15, the authors show that if the 2D projected Wasserstein distance (see eq. 18) between the feature distribution and the standard Gaussian scales like $1/sqrt(d)$ ($d$ is the feature dimension), then for population losses whose Gaussian information exponent is at most $2$ satisfy the LPG condition. \n\n\t(d) In Proposition 17, the authors make some partial progress in verifying a relaxed form of the LPG condition for i.i.d. non-Gaussian feature vectors. The basic idea here is that since the LPG condition only depends on a two-dimensional projection of the feature vectors, because of the central limit theorem, the LPG condition should hold. The authors conjecture that SGD path avoids localized vectors, and based on this conjecture, sketch an informal argument that would show that the conclusions of Ben Arous et. al. should also extend to feature vectors with i.i.d. coordinates. ", "questions": "It would be great if the authors could clarify the following:\n\n\t1) In Theorem 4, is the scaling of the iteration bound with the desired recovery accuracy $\\epsilon$ expected to be optimal? This seems important since it would clarify if SGD achieves the optimal statistical rate of convergence. In addition, the result stated in Theorem 4 seems inconsistent with the result obtained in the proof (Page 16 in the supplement). \n\n\t2) In Prop 7, the authors consider the setting where the features are rotationally invariant. In this situation, I wonder if it might be possible to recover this result from the results of Ben Arous et. al. since it seems to me that the main assumption of Ben Arous et. al. holds in this case (that is, the population loss at a point $\\theta$ is only a function of the dot product between $\\theta$ and the hidden direction). \n\n\t3) A relevant reference to cite is the work ``One-bit compressed sensing with non-Gaussian measurements'' by Albert Ai, Alex Lapanowski, Yaniv Plan, and, Roman Vershynin. This work also uses a central limit theorem-type argument to go beyond i.i.d. Gaussian measurements to i.i.d. non-Gaussian measurements, as in Section 4.2 of this paper.  \n\nI have the following minor comments:\n\n\t(1) I think the discussion of the work of Ben Arous et. al. can be improved to clarify that their analysis of SGD doesn't use Gaussianity per se, but is under a general condition, which can be verified for i.i.d. Gaussian features and rotationally invariant features. \n\n\t(2) In the introduction, lines 55-57, I didn't quite understand what the authors mean by \"stability\". \n\n\t(3) The discussion in lines 162-164 seems a bit inappropriate: the authors propose drawing many random initializations and keeping the one that has the maximum correlation with the hidden direction - but the hidden direction is unknown. \n\n\t(4) Below Eq: 18: Has the notation $Gr(2,d)$ been defined? ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I found the paper to be well-written and the proofs (as far as I checked them) seem correct to me. The SGD analysis of Ben Arous et. al. does not assume that the features are i.i.d. Gaussian. specifically, but assume a condition on the population loss (see Eq. 1.1 in the ``Online stochastic gradient descent on non-convex losses from high-dimensional inference'', JMLR 2021),  and analyze SGD dynamics under this condition. However, in most of their examples, the condition can only be verified under the i.i.d. Gaussian feature assumption. The condition proposed by the authors is weaker than the condition in the work of Ben Arous et. al. and can be verified in examples beyond those considered in the work of Ben Arous et. al. This is a key strength of this paper.  \n", "weaknesses": "The key weakness of this paper seems to be that most of the examples discussed by the authors seem to be small perturbations of Gaussian sensing vectors. \n\nAt the same time, the abstract and the introduction seem to overclaim the generality of the results obtained in the paper. For instance, in the abstract, the authors write ``our main results establish that Stochastic Gradient Descent can efficiently recover the unknown direction in the high dimensional regime, under mild assumptions that significantly extend Yehudai and Ohad (2020) and Wu (2022)''. However, the papers cited by the authors appear to make weaker assumptions on the feature vectors (compared to rotationally invariant features or i.i.d. features), but stronger assumptions on the non-linear link functions, so it appears that the results of the authors are not stronger or weaker - rather complementary. \n\nA second weakness of the paper is that the analysis of the authors for i.i.d. feature vectors seems incomplete. It does seem quite plausible that the conclusions of Ben Arous et al. should extend to this case. However, the claims of the authors are conditional on a conjecture (see Conjecture 35 in the supplement). Furthermore, the fact that their results are conditional on this unproven conjecture is not transparently indicated in the main paper, where the authors simply write ``While the LPG property does not directly apply in this setting, in Appendix B.4 we outline an energy-barrier argument that demonstrates that the single-index model 324 can still be efficiently solved using gradient-based methods'', without mentioning that the result relies on a conjecture they haven't proven.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response, we answer questions below:\n\n**General answer**\n\n- *Tempering the overclaim.* Regarding Yehudai and Ohad (2020) and Wu (2022)', both contain theorems specifically demonstrating strong recovery under specific family of functions and spherically rotationally invariant distributions (these are Theorem 6.4 and Theorem 3.3, respectively).  It is true that Theorem 5.3 in the former paper considers a setting we don't extend but is complementary to our own, we will update the paper to reflect this fact. However, we want to be clear that we did not cover only the \"small perturbation of Gaussian case\": indeed the Section 4.1 is devoted to a setup that can be far from Gaussian, while preserving its spherical symmetry. \n\n- *Conjecture in the case of product measure.* We want to be clear that the only case that remains conjectural is at the end of the paper when the product measure is introduced. We see this paragraph (appearing only page 9!) as a nice perspective that carries a *universality* flavor, but as said by the reviewer, we never claim to have fully solved it: we do not see this as a weakness but rather as a nice perspective that naturally arises with our work. We will make this more clear in the revised manuscript.\n\n\n**Answer to specific questions.** Thanks for the comments and the proposed (relevant) paper, we will add these in a later draft. \n\n1) *Epsilon dependency.* Note that all that matters in this strong recovery phase is that this dependency *is independent of the dimension*: this is the critical point of this theorem. The precise dependency on *$\\varepsilon$* is not very important in that sense. In fact, all the time spent is in the first phase described by Theorem 3. To be clear about this fact, we decided, as it is done implicitly in [Ben Arous et al]'s work to reschedule the step-size. Thanks to point out this fact, this will be clearer in the updated version.\n\n2) *Rotation invariance does not suffice.* This is one of the principal conclusion of our study: the result does not immediately follow from Ben Arous, as for spherically symmetric inputs that are non-Gaussian, the loss is not globally monotonic.  Indeed, controlling Gegenbauer polynomials to determine how large the initial correlation must be to land in the monotonic part of the loss landscape is the bulk of the proof: in the Gaussian case higher order Hermite terms cannot possibly hurt you (they can only make the loss decrease faster), whereas in our setting we need to carefully control the higher order terms in order to avoid local minima.\n\n3) *Initialization.* Thank you for pointing out this fact! It is true we cannot directly measure the correlation between $\\theta$ and $\\theta^*$.  However, for large $d$ and constant values of $s$, the LPG condition implies that once we've reached weak recovery and e.g. $m \\geq 1/2$, the loss landscape is monotonic.  This implies we can, after training several possible $\\theta$ in parallel, test which one has the highest correlation with $\\theta^*$ by simply looking at which one minimizes the empirical loss over a batch of fresh samples. We'll make this important fact clearer.\n\n4) *Grassmannian.* $Gr(2,d)$ is a notation for the Grassmannian of two-dimensional subspaces (the manifold of all the two-dimensional linear spaces), but we didn't include this definition explicitly and will update in a later draft."}, {"review_id": "ClNtaHbOEq", "reviewer": "Reviewer_tgdy", "summary": "The paper deals with the study of online SGD in single-index models of the type $f(\\mathbf x)=\\phi(\\boldsymbol\\theta^\\intercal\\mathbf x)$ for a generic non-linear scalar link function $\\phi$. The work builds on previous results of Ben Arous et al and aims at going beyond the Gaussian-data assumptions therein. A theorem extending the Gaussian result is given where a crucial condition on the population loss, namely the local polynomial growth, is identified. Finally, the theoretical results are applied to the spherically symmetric setting and to specific non-spherical symmetric settings.", "questions": "As discussed in the *Weaknesses* section, it appears that verifying the LPG property requires a case-by-case, very nontrivial analysis of the distribution involved. Could the author comment on this point? Do they expect that a general (even heuristic) strategy is feasible to expect to be within the hypothesis of Theorem 3 in the case of a general measure? Finally, with respect to future developments, do the authors expect the LPG condition to be necessary for Theorem 3 to hold?\n\nAs a final comment, the authors might consider citing in their work the very classical contribution\n> David Saad and Sara A. Solla, Phys. Rev. E 52, 4225 (1995)\n\nwhere the dynamic of $m$ was studied within the framework of statistical mechanics.\n\nTypos and other comments.\n* The authors refer to the goal function as a *Sparse high-dimensional function* but there is no sparsity assumption on, e.g., $\\theta$ and, if referring to the fact that the goal is to learn a single direction, the terminology appears slightly misleading.\n* In line 70, $\\theta^*$ in the definition of $\\mathcal H$ should be $\\theta$.\n* In line 76 $\\|f\\|^p_{L_\\mu^p}$ should be $\\|f\\|^p_{L_\\nu^p}$.\n* In lines 248-249, two subsequent \"Indeed\" appear.\n* In line 260 \"Wassertein\" in place of \"Wasserstein\".\n", "limitations": "See the *Weaknesses* section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is an interesting attempt to go beyond the Gaussian data assumption in the study of online SGD in single-index models and provides a criterion for preserving the scenario observed in the Gaussian setting, characterizing therefore its robustness. If on one hand, the theoretical analysis seems to become extremely complex going beyond the Gaussian realm, it is nevertheless essential to better understand the SGD dynamics on real data. The paper is quite clear although the analysis in Section 4 is more cumbersome (but I have the feeling that this is unavoidable).", "weaknesses": "I have the impression that a weakness of the paper lies in the fact that the main information on the loss landscape in the general setting is concentrated on a property, the local polynomial growth condition, which is in general not straightforwardly analyzable. If, on one hand, the typical case discussed in Section 4.1 exemplifies the application of the theorem, on the other hand, it also seems to show that verifying the LPG property is not trivial and requires a setting in which a proper basis (in the case, the Gegenbauer polynomials) is available. The study in Section 4.2, mostly instead relies on a Gaussian reference measure, which, as the authors themselves stress, is also a limitation. I wonder therefore if the theorem is *practically* useful beyond a small set of adequate measures that actually satisfy the LPG property (in this sense the title sounds partially misleading a", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response, comments and paper suggestion that will help improve the paper. We answer precisely to the questions below:\n\nWe agree that the LPG condition requires an input distribution for which one can at least approximate the loss landscape in terms of the correlation. Surely, it is very hard, if not impossible, to verify such a property *a priori*. However, we want to argue that the paper aims at understanding what intrinsinc features of the Gaussian distribution helps to analyze a loss landscape: in this paper we give such necesarry conditions. Yet, we still believe it is a useful way of addressing multiple settings, since it clarifies the martingale and drift argument for weak and strong recovery in a way we can apply to multiple settings.\n\nObviously, we do not expect that LPG hold for every measure, as there as many settings, e.g. described in [Yehudai, Ohad, 2020, Wu, 2022] where the single-index loss landscape is totally *benign* in terms of sample complexity. Yet we believe that the Gaussian distribution offers a rich picture for this problem, and furthermore has a sense of universality as being central in probability and learning. In this direction, the aim of this work was to describe setups where there is this flavor of *universality* as the high-dimensional loss landscape resembles the one canonically given by the Gaussian distribution. Finally, let us mention that the LPG condition is, in some sense necessary if we want to go beyond the Gaussian setting where we know that the dynamics spends most of its time to correlate weakly with the signal."}, {"review_id": "5z9tLqUg7D", "reviewer": "Reviewer_PMRM", "summary": "This paper extends the results of Ben Arous et al., 2021 for learning a single-index model with a known link function via online SGD beyond the Gaussian input setting. The authors introduce a condition called Local Polynomial Growth (LPG) and establish the convergence rate of online SGD under LPG for spherically symmetric input distributions and certain perturbations from the isotropic Gaussian distribution.", "questions": "* I believe it would be helpful to have a discussion on the connection between the calculations of Section 3 and the framework of Ben Arous et al., 2021. In particular, is showing LPG strictly required for establishing SGD convergence for spherically symmetric distributions, or is it possible to use the Taylor expansion of Ben Arous et al., 2021 to arrive at the same results?\n\n* In line 161, it is mentioned that \"This probability can be lowered by any constant factor ...\". Is this not the success probability? If that is the case, is this sentence meant to say the probability can be increased?\n\n* In the same sentence, how can one measure the alignment of different initializations with $\\theta^*$ in order to maximize such alignment, without having knowledge of $\\theta^*$?", "limitations": "The authors have mostly adequately discussed the limitations of the work, and additional details are provided above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper has an excellent presentation with sufficient intuition given for different regimes of SGD convergence.\n* Learning single-index models for distributions without spherical symmetry is an interesting and significant open problem.\n* The calculations performed for spherically symmetric distributions can serve as a useful example of how to perform a harmonic analysis for such distributions in the context of learning with online SGD.", "weaknesses": "* My main concern is that LPG might not be the right definition to analyze this problem with non-Gaussian distributions, due to the following reasons:\n    * For spherically symmetric distributions, I'm not sure if LPG is required. Specifically, I believe the *information exponent* framework of Ben Arous et al., 2021, which only depends on spherical symmetry and Taylor expansion of the population loss, must be able to handle such distributions, and the contributions in this section might be interpreted as calculating the information exponent for non-Gaussian examples.\n\n    * For distributions without spherical symmetry, it appears that LPG is not the suitable definition. Particularly, as the authors have pointed out, the validity of Assumption 14 for many distributions of interest is not clear, and the probability that SGD has a successful initialization is of order $O(1/d^2)$, making it inapplicable in high-dimensional settings. Moreover, there appears to be no direct connection between the Stein's-method-based argument and LPG.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your response and questions, hopefully they will help improve greatly the paper. We give a precise answer to your concerns below:\n\n - *Necessity of LPG.* Thanks for raising this question that allows us to clarify an important point. In *the Gaussian case*, the definition in the information exponent as done in Ben Arous et al., is sufficient alone as outside the equator $m \\neq 0$, **there is no local minima of the population loss**,  as the loss is strictly monotonic for $m > 0$. However, let us put emphasis on the fact that this is not the case in our setup: higher order Gegenbauer polynomials can introduce local minima into the loss landscape, which complicates the definition of information exponent and requires us to control decay of higher order terms as in Proposition 7.\n\n- *No spherical symmetry.* For the first point on the success of initialization, we agree that this is a limitation and we have complemented the result with a discussion indicating that we do not know whether this polynomial number is only a technical limitation or not. Yet, on the second point, we beg to differ. Let us emphasize that the aim of the section 4.2 is to provide the basis of a perturbative setup where the LPG is realised. More precisely, this says that the perturbation of the Gaussian should occur at scale $1/\\sqrt{d}$. In that direction, the Stein's method gives nearly (except in small regions with sparse predictors) a positive result for product measures: that is to say that, in high-dimension, for product measure, Stein's method and LPG are well connected! We will make this important fact clearer.\n\n- *Taylor expansion and information exponent.* As said before, the Taylor expansion of Ben Arous et al. 2021 cannot be applied simply because, in the rotationally invariant case, the expansion will include negative coefficients and therefore spurious minima.  \n\n- *Initialization.* For line 161, we wanted to say that if we initialized randomly a batch of different $\\theta_0$, then the probability of one being well initialized (i.e. success) will be lowered significantly.  You are right that it is *a priori* impossible to measure the alignment without the knowledge of $\\theta_*$. What can be done in practice is to run in parallel all the dynamics with different initializations and to take, at the end of training, the one with smallest empirical error (wrt the samples used for SGD). We will clarify this, thanks for raising this problem."}, {"review_id": "FSqlXbmONZ", "reviewer": "Reviewer_CJfX", "summary": "This paper studies the problem of learning a single-index model beyond Gaussian data. Prior work (Ben Arous et al. 2021) studies the optimization landscape of recovering the hidden direction $\\theta^*$ given a known link function $\\phi$ when the covariates are drawn from the standard Gaussian distribution; in this case, the sample complexity is governed by the information exponent of $\\phi$. This paper’s key contribution is defining the “Local Polynomial Growth” condition, which characterizes the geometry of the population loss landscape. The main results, Theorems 3 and 4, show that online SGD recovers the hidden direction with sample complexity depending on the order parameter in the LPG condition. The proof of this main theorem relies on the same martingale-plus-drift decomposition from (Ben Arous et al. 2021). The paper concludes with specific examples of data distributions satisfying the LPG condition; for example, spherically symmetric distributions.", "questions": "- As mentioned above, can you please comment on the dimension dependence of the constant $C$ in Theorem 3?\n- A key requirement in the paper is for the initialization to have sufficient correlation with $\\theta^*$. How does one check whether an initialization has sufficient correlation? This is particularly of interest for the 2D-Wasserstein distance example, where the probability of achieving a good initialization is polynomially small.\n- Do you have examples of specific distributions which satisfy Assumption 14?\n- lines 283-284: “by paying an additional $O(d^2)$ cost in complexity” — what do you mean by this? is this just the complexity of resampling until a good initialization is achieved?", "limitations": "Limitations/broader impact are adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-written and easy to understand.\n- Learning a single-index model is a well studied problem in the statistics literature and is a primitive for neural network learning. Prior work in this area either assumes Gaussian data or that the link function satisfies basic properties such as monotonicity. This paper initiates the study of the landscape properties of learning single-index models with arbitrary data distribution and link function, which is to the best of my knowledge novel and an important direction of future work.\n- The local polynomial growth definition is an interesting and useful way to abstract away the key ideas of the proof in (Ben Arous et al. 2021), and has not appeared previously in the literature. This definition allows for their key idea of escaping a higher-order saddle at initialization to apply to a larger family of distributions more generally.\n- Section 4.1 shows how the LPG framework can be used to learn single index models over arbitrary spherically symmetric distributions, which is a novel and interesting result.", "weaknesses": "- There is one major weakness I am concerned about. Theorem 3 depends on this constant $C$, which in turn depends on a constant $K$ defined in Appendix B. This constant is used to upper bound quantities such as $\\sup_\\theta E_x\\|\\nabla M(x, \\theta)\\|^2$ which show up when concentrating the martingale term. However, it appears to me that this constant is not actually dimension independent. In the proof of Lemma 22, before line 558, this constant depends on $|x|^2$ which is typically $\\Theta(d)$ for many examples (such as Gaussian or uniform on sphere of radius $\\sqrt{d}$). Thus it seems that there is an additional dimension dependence hidden in the constant $C$. Can you please clarify whether there is indeed a hidden dimension dependence here? This is a key issue because it changes the exponent of $d$ in Theorem 3. In my opinion this is a major issue that makes me recommend reject, but if you can clarify this point or I have misunderstood I am wiling to increase my score.\n- A more minor weakness is that I find the examples in Section 4.2 to be a bit restrictive. For instance, requiring *all* 2d marginals of $\\nu$ to be close to Gaussian in Wasserstein distance seems to be a very restrictive assumption, and I am not sure what distributions satisfy this property (beyond uniform on the sphere of radius $\\sqrt{d}$). Next, proposition 15 shows that LPG is satisfied only for $b = \\log d/\\sqrt{d}$, which seems to imply that polynomially many initializations would need to be sampled before a good one is reached. Finally, as the authors indeed point out, the Stein’s method argument only shows the LPG along dense directions and does not yield an end-to-end guarantee for online SGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank very much the reviewer for the sharp comments and discussion that will help improve the paper greatly.\n\n- *Dimension dependent constants.* This is the major concern of the reviewer, and we would like to thank him for the important comment: indeed constants like $\\sup_{\\theta} E[\\|\\nabla M(x, \\theta)\\|^2]$ typically depend on the dimension as $O(d)$ (e.g. gaussian data) and the way the proof was written in the Neurips submission is wrong! However, we want to emphasise that this is only a technical flaw that can be easily circumvented by the following: in fact, the correct object that we need to upper bound carefully is the variance of *directional martingale* $\\sup_\\theta E[\\langle \\nabla M(x, \\theta), \\theta_*\\rangle^2]$ (and not its norm) which, this time, does not depend on the dimension (e.g. for approximately gaussian or spherically symmetric data)! This corresponds to equation 1.3 of Ben Arous et al. paper, and we were too loose on this argument by bounding directly quantity like $\\langle \\nabla M(x, \\theta), \\theta_*\\rangle$ with $\\| \\nabla M(x, \\theta)\\|$. We have fixed this in the proof in the Appendix and clearly acknowledge the previous flaw.\n\n- *Section 4.2.* It is true that this section, which makes a perturbative statement on the distribution, suffers from the limitations that the reviewer mention. However, we see this section as paving the way of the description that offers Stein's Lemma for product measures. The aim of this section is hence to provide the basis of a promising route in order to understand the universality of the Gaussian for this problem.\n\n- *Initialization.* For the sake of clarity, we repeat the comment made for another reviewer. For line 161, we wanted to say that if we initialized randomly a batch of different $\\theta_0$, then the probability of one being well initialized (i.e. success) will be lowered significantly.  As it is *a priori* impossible to measure the alignment without the knowledge of $\\theta_*$, what can be done in practice is to run in parallel all the dynamics with different initializations and to take, at the end of training, the one with smallest empirical error (wrt the samples used for SGD). We will clarify this.\n\n- *Distribution satisfying Assumption 14.* There is a discussion on such distributions given from line 294 to line 303. Furthermore, as already explained, even if this is not the case uniformly, for product measures,  Proposition 17 also tells us that typically, a LPG property is also expected."}]

Author rebuttal:

Meta-review: This paper studies the behaviour of gradient descent for learning a single-index model. Recent work by Ben Arous et al. has provided a precise description of online SGD, assuming Gaussian data. The key contribution of this work is to go beyond Gaussian data, and the authors identify an assumption (called Local Polynomial Growth) under which the existing analysis and the corresponding conclusions go through.

The authors have addressed the concerns of the reviewers via a thoughtful rebuttal, and the consensus is towards accepting the paper. After my own reading of the reviews, rebuttal and paper, I agree with this view: removing Gaussian assumptions is an important problem and, even if the LPG may be hard to verify, this paper still does a step in the right direction providing interesting and non-trivial results. I thus recommend acceptance. 

I warmly encourage the authors to incorporate the rebuttal in the final version. I would also like to see a comparison with the classical work "One-bit compressed sensing with non-Gaussian measurements" by Ai et al. (https://arxiv.org/abs/1208.6279). In fact, the model considered in that work can also be regarded as a single index model with non-Gaussian measurements.
Decision: Accept (poster)