On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
Authors: Nirmit Joshi
Theodor Misiakiewicz
Nathan Srebro
Venue: NeurIPS 2024 poster (2024)
Keywords: Statistical Query Complexity
Differtiable Learning
Sparse Functions
Leap Exponent
Primary area: learning_theory
TL;DR: We study the power of differentiable learning compared to the statistical query (SQ) and correlation statistical query (CSQ) methods for the problem of learning sparse support of size P out of d coordinates with d>>P.

Abstract: The goal of this paper is to investigate the complexity of gradient algorithms when learning sparse functions (juntas). We introduce a type of Statistical Queries ($\mathsf{SQ}$), which we call Differentiable Learning Queries ($\mathsf{DLQ}$), to model gradient queries on a specified loss with respect to an arbitrary model. We provide a tight characterization of the query complexity of $\mathsf{DLQ}$ for learning the support of a sparse function over generic product distributions. This complexity crucially depends on the loss function. For the squared loss, $\mathsf{DLQ}$ matches the complexity of Correlation Statistical Queries $(\mathsf{CSQ})$—potentially much worse than $\mathsf{SQ}$. But for other simple loss functions, including the $\ell_1$ loss, $\mathsf{DLQ}$ always achieves the same complexity as $\mathsf{SQ}$. We also provide evidence that $\mathsf{DLQ}$ can indeed capture learning with (stochastic) gradient descent by showing it correctly describes the complexity of learning with a two-layer neural network in the mean field regime and linear scaling.

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
Nirmit Joshi
Theodor Misiakiewicz Toyota Technological Institute at Chicago
Toyota Technological Institute at Chicago nirmit@ttic.edu
theodor mi risiin wwiiiiiiittttiii..............i.
Nathan Srebro
Toyota Technological Institute at Chicago nati@ttic.edi
Abstract
The goal of this paper is to investigate the complexity of gradient algorithms when learning sparse functions (juntas), We introduce type Statistical Queries (SQ), which we call Differentiable Learning Queries (DLQ), model gradient queries on a specified loss with respect to an arbitrary model. We provide a tight characterization of the query complexity of DLQ for learning the support of a sparse function over generic product distributions. This complexity crucially depends the loss function. For the squared loss, DLQ matches the complexity of much worse than SQ. But for
Correlation Statistical Queries other simple loss functions, including the loss, DLQ always achieves the same complexity as SQ. We also provide evidence that DLQ can indeed capture learning with (stochastic) gradient descent by showing it correctly describes the complexity of learning with two-layer neural network in the mean field regime and linear scaling.
Introduction
In recent years, major efforts have been devoted to understanding which distributions can be learned efficiently using gradient-type algorithms on generic models [Abbe and Sandon, 2020, Allen-Zhu and Li, 2020, Malach et al., 2021, Damian et al., 2022, Abbe et al., 202 2022, 2023, Bietti et al., 2023, Glasgow, 2023, Dandi et al., 2023, 2024, Edelman et al., 2024, Kou et al., 2024]. this paper, focus learning sparse functions (i.e. "juntas" [Blum and Langley, 1997]), that is functions that depend only on a small number P out of much larger set > P of input coordinates. The challenge in this setting is to identify the few relevant coordinates. For some sparse functions, such as noisy parities, learning is believed to require ((dP) runtime [Kearns, 1998), while others, such as linear functions, are easy to learn in ((d) time. Which functions are easy to learn and which hard? What is the complexity of learning a specific sparse function? Recent works [Abbe et al., 2022, 2023] unveiled rich "leap" hierarchical structure and saddle-to-saddie dynamics that drives learning in this setting. The goal the present paper is provide general characterization for the complexity of learning sparse functions that go beyond (i) hypercube data and Fourier analysis, and (ii) CSQ (see below) and focusing only on the squared loss.
The notion of complexity we consider is the Statistical Query (SQ) complexity, which studies learning by measuring expectations up some worst-case tolerance (see [Kearns, 1998, Bshouty and Feldman, 2002, Reyzin, 2020] and Section 3). Although based on worst-case error (or almost equivalently, additive independent noise) rather than the sampling error encountered in practice, statistical query complexity has been proven to be a useful guideline for studying the complexity of learning. In
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

particular, gradient computations are a special case of statistical queries. In specific cases which include binary functions or gradients on the squared or cross-entropy loss, gradient queries are equivalent' to the restricted class of Correlation Statistical Queries (CSQ) which are strictly less powerful than general statistical queries. Lower bounds on the CSQ complexity have thus been seen as corresponding to the complexity of gradient-based learning' in these restricted cases. Part of the motivation for this paper is to emphasize that this relationship is limited to very specific loss functions and does not hold more generally. In order to study the complexity of gradient algorithms for general output and loss functions, we introduce a type of statistical query which we call Differentiable Learning Query (DLQ). These queries are defined with respect to specific loss l dedoted by DLQ,- and are given by gradients on a loss l with respect to an arbitrary model. Specifically, DLQ, algorithms correspond to SQ algorithms with queries of the type
② ( x) dw
((f(z, w) w== where f: 2'
R R.
(I)
Depending the loss l and target distributions, learning with DLQ, can be less, equal, or more powerful than CSQ.
For inputs on the hypercube æ ~ Unif (1)() and CSQ, Abbe et al. [2022, 2023] showed that the complexity of learning sparse functions is sharply captured by a leap exponent defined terms of the non-zero Fourier coefficients of the sparse function. Informally, it states that ((d*.) ) queries are necessary and sufficient to learn with CSQ, where k. the minimum number of coordinates one need to add at once to "leap" between non-zero Fourier coefficients. E.g., consider the following two sparse functions:
(1) + (1) + (2) + T., (1) (2) (3) (3)
(2)
1/2 = x. (2) + =.) (2) + 2, (3) (4) + (3)
Both functions depend on an (unknown) subset of p coordinates (1= Sy (2). (4))
For y1, the monomials are ordered such that we add only one new coordinate to the support at a time: the leap exponent is and (d) queries are sufficient learn y1- For y2, we need to add three new coordinates at once: the leap exponent is 3 and (d queries are required to learn y2-
We extend and generalize this charactarization in several significant ways:
(a) We go beyond binary input space and allow for arbitrary measurable space with product distribution. In particular, the leap complexity arises from the structure of the permutation group rather than a specific functional basis.
(b) We go beyond CSQ and squared loss, and tightly characterize the query complexity for learning sparse functions with SQ and DLQ, algorithms with any loss é. This complexity is in terms of leap exponent defined analogously as above, but now over a set system CA C 2Pl of "detectable" subsets S C [P]. where "detectability" depends on the type of queries A E [SQ, CSQ, D Learning with different loss functions are not necessarily comparable to CSQ or SQ and depend on the sparse function. However, we show that some losses, such as l or exponential loss, are "generic", i.e. COLQ. CsQ for any sparse function, and always match the SQ-leap exponent. This shows that differentiable learning with these losses as powerful learning with SQ for juntas.
(c) Finally, we introduce a cover exponent ceronnet-defined on the same system of detectable sets Ca-which captures learning with A E (SQ, CSQ, DLQ;) when the queries are chosen non-adaptively, i.e., without adapting to the responses of previous queries. This can be roughly thought of as learning with single gradient step, versus many consecutive steps in the adaptive case. The contrast between the two helps understand to what extent learning relies on adaptivity and can help frame other related results- discussion in Section
We summarize the complexity of learning a sparse function with SQ, CSQ, DLQq and adaptive/non- adaptive queries in Table 1. To see some of these notions play out, consider again the two examples in Eq. (2):
Leap(Ccso) = 1, Cover(Ccsa) = 4, y2 Leap(Ccsa) = Cover(Ccsa) 3,
V1
Leap(Csa) = Cover(Csa) = 1, Leap(Csq) Cover(Csa) = 1.
'This equivalence holds if the input distribution is known, which is case we consider here. 'In Section 8, we discuss recent work Dandi et al. [2024] that showed that even with the squared loss, multiple gradient evaluations the same batch can be strictly more powerful than CSQ.

---

q/r² = O(d*.)
Adaptive
Non-adaptive
SQ
k, Leap CsQ
k, Cose
CSQ
k. Leap(Ccso)
k. = Cover(Ccsoo
DLQq
k. Leap(CDLQ.)
k. Cover(CDLQ
Table 1: Complexity of learning sparse function over d input coordinates with different query types based on Theorem 5.1. DLQ, defined in Section 2, Leap and Cover of a set system in Definition 1, and systems CA of detectable sets in Definition based on test functions depending on query type A, as specified in Eq. (14).
For yı, DLQq will require (dd) adaptive or (dd)) non-adaptive queries to learn with squared loss equivalent to CSQ, while ((d) adaptive/non-adaptive queries suffice with & ei-loss-equivalent to SQ. For 1/2, DLQ, will only require (dd) queries, either adaptive or non-adaptive, with filloss, compared to (dd)) queries with the squared loss. Proposition 6.2.(c) provides an example where Leap(Cso) < Leap(CoLo,) Leap(Ccsa))-
D algorithms are quite different than (stochastic) gradient descent algorithms. On one hand, DLQa allows evaluating arbitrary gradients rather than following a trajectory, and is thus potentially more powerful than (S)GD on generic models On the other hand, the lower bound on DLQ, algorithms in Table 1 is against worst-case noise-much much more pessimistic than sampling noise encountered in SGD or GD-on-the-tree thee-rrinnin-sst [Abbe al., 2021b]. Nevertheless, DLQ, does provide useful guidance and we expect that it does capture important aspects of the computational complexity of GD in number of settings. To demonstrate this, Section considers learning sparse functions on the hypercube using online SGD two-layer neural network. We show that in this setting, the DeQ,-leap exponent correctly captures lcarnability in the mean-field regime and linear scaling. Namely, for DLQe-leap 1 functions, SGD on loss É learn in Otd)-steps, while for leap greater than 1, the dynamics remains stuck in a suboptimal saddle subspace and require w (d)-sttps to escape.
Setting
Junta Recovery Problem. A sparse recovery (junta learning) problem with P relevant coordinates is defined in terms of coordinate input space X, an output space )", marginal distribution μ4, over X' and a link distribution Pyls over Y given elements of X This specifies a joint distribution pyy= over a measurable space y x XP, where the marginal distribution z ~ fe is the product distribution, and y My æ- We further denote My be the marginal distribution over Y. We further denote the junta problem by a tuple μ := (Mas My)=)), where the support size P and the spaces X' and y are implicit. Consider some examples,
Unif((+1))), y= (2) + for some h, : (+1) - R and noise 8;
(3)
IOO.Pp), y ~ Bernoulli(sigmoide (z))) for some target h R. R.
For d 2 P. we define the junta recovery problem learning the family of distributions
H = [Di. S P(]
(5)
where P([d) P) is the set of non-repeating sequences from [d] of length P. and the distribution Dd a distribution over y x ddd such that
p.s
p and y (Ia(1): - .T(())) ~ Mylz- x
In words, Hd. is the set of distributions on (y, 21, .., Ta) where follows the product distribution ne and the output y only depends on an (unknown) sequence of P coordinates. For ease notation, we will denote Dd De when the junta problem μ (Mas My]=) is clear from context.
FFollowing Abbe et al. [2021b], we can construct an "emulation" differentiable model, iee. model f(x; w) on which GD emulates D However, this offers limited insights as the model fa; w)) highly non-standard. FFormally, X' and y measurable Polish spaces endowed with sigma algebras E' and My respectively.
3

---

Success as Support Recovery. For any sequence s E P([d], P). we additionally denote the associated unordered set of its elements by S := {s(i)
E [P]]. We consider learning as "succeeding" if it outputs the correct index set. That is, we say junta learning algorithm "succeeds"
in learning H. if for every s, P([d) P), it outputs $ s [d] such that S = S. (s) [P]].
For our purpose, just the recovery of relevant coordinates is the objective as we only care about the complexity as scaling of d. Once we recover the relevant coordinates S.. learning the ordered sequence 3, corresponds to problem of size P. and thus its complexity independent of d. Note that the precise ordering 8, may not be identifiable if for some other s', with S. = S we have 3_ = -D this is possible when the measure Uuy has symmetries with respect to coordinates of z. We further emphasize that even the support S. may not be identifiable, when is independent of some coordinates of z or when only using restricted query access the distribution-we will return to this issue in Section 5.
Does the learner know the link pyy== We always assume that the learner knows fAz- In formulation, we also assume that the learner additionally knows the link Hylz. and the only unknown 8,. Indeed, our lower bounds hold even for this easier setting. But under mild assumptions, our upper bounds can be obtained with an algorithm that does not require knowing Pylz (the complexity still depends on the problem jr-sse discussion in Section 5.
Well Behaved Distributions. For our lower bounds, we will consider junta problems / = (Poz )ylx), which are "well-behaved" in way that is standard in the hypothesis testing litera- ture. Let Py.s be the induced joint distribution on (y,z) where z ~ p and y Hylz- For any subset U C [P], let uy, be the marginal distribution of (y, (zi)iev) and
My.z = Py.z.U @ Hx 101
(6)
meaning that (y, .2....,,27 2p) 22x has (v. (2i)ieu) My,2,U and (2)) v Me indepen- dently of (y, (zi)ev) (we replace 2; for i & U with independent draws from the marginal). The marginal distribution of z under 22, is still ue
Assumption 2.1. For any U S [P), we have py,z & Hy, and the Radon-Nikodym derivative /pp.:/dpy.. u, is square integrable w.r.t Uy i.e.
djy E (p for all (P]. 2
This is a standard and implicit assumption in the hypothesis testing literature whenever a corre- sponding null distribution considered (here all ph,,, i.e., with label y depending only on strict subset S [P]): more specifically for statistical query lower bounds [Feldman al., 2017, Damian et al., 2024b], low-degree likelihood ratio [Hopkins, 2018, Kunisky et al., 2019], contiguity lower bounds [Perry et al., 201 8). It always holds when X is finitely supported. We further comment on the necessity of this assumption in Appendix A.
3 Statistical and Differentiable Learning Queries
We will consider three classes of learning algorithms, all based on the statistical query paradigm, but differing in the type of queries allowed, as captured by set Q of allowed queries.
For a number of queries y tolerance > 0 and set Q C Xxx= of measurable functions y x dd IR, a Q-restricted statistical query algorithm A E Q-SQ(g: r) for junta learning takes an input distribution D over y x x and operates in g rounds where each round t {L..... q). issues query & E Q, and receives a response 2/ such that
1t Ep [pe x)]l <
(8)
where Do = D, & Da is the associated decoupled "null" distribution where and y are independent, but follow their marginals The query Φt can depend on the past responses Ui...., 1t-1- After
'quivalently, could restrict the L2(D)) norm of the query. See also Remark 3.1.

---

issuing q queries, the leamer A outputs S S [d]. We say that A succeeds in learning Hi if for any D._ E Hy and any responses v, satisfying (8) for D = Da.. A outputs S 5= S..
Above we allow the queries to be chosen adaptively, i.e., depending on past responses. We also con- sider Q-restricted non-adaptive statistical query algorithms, which we denote by Q-naSQ(q. r). where the query functions {Ør hel are fixed in advance and do not depend on the past responses. Le. a non-adaptive algorithm is specified by a list of queries and a mapping from the responses to an output S S [d].
Statistical Queries (SQ): In regular, unrestricted Statistical Query learning, the allowed query set, denoted by 2so. is the set of all measurable functions. With slight overloading of notation, we refer to the class of these algorithms simply as SQ(g, 7) and naSQ(q. T).
Correlation Statistical Queries (CSQ): It is special subclass of statistical queries, which require y C R (usually we allow the input and output spaces to be abstract), and are restricted to:
ecsq -
{ (vv, x) = y (xx) é= æ + measurable]
We denote the class of adaptive and non-adaptive algorithms making such queries as CSQ(q, 7) and naCSQ(g, respectively.
Differentiable Learning Queries (DLQ) with Loss f: Let F C V. which is an open subset of some normed vector space V, be the output space of our models, e.g. usually V = F = I for models with single output unit, but we may have V = == R" with multiple output units. We consider a loss function & F x y + R that is locally Lipschitz continuous in its first argument for every y E V. The loss is additionally equipped with derivative operator Vt F as a part of the loss definition such that for any u E F and y E Y we have Vê(u, y) E E, v). the set of generalized Clarke subderivatives of ((:y)) u E F. This is standard generalization of derivatives to non non-differentiable and non-convex losses; in particular, note that (i) for differentiable losses, E(, y) is a singleton with the true gradient of E(.3) y) at u E F. and (ii) for convex losses (in the first argument), 0 f(u, y) is the set of subderivatives of f(,, y) at u E F. Finally, let
M := {f d' x R ++> F f(x, w) is differentiable at w = 0 for all x E 2²d} be the set of allowed models Then the allowed differentiable learning query set set is:
QDLO. = { H6y, x) = dw ((x(
d w)
rem]
(e(((, 0),u)
(10)
w=0
That is, at each round the algorithm chooses a parametric model [(x,, parameterized by a single scalar w, and the query corresponds to the derivative (with respect to the single parameter w) of the loss applicd to the model, at w = 0. This captures the first gradient calculation for a single-parameter model initialized at zero. But the derivative at any other point can also be obtained by querying at a shifted model fi w) = f(x v/ + w), and the gradient with respect to a model f(x, w) with E IR" can be obtained by issuing queries, one for each coordinate, of the form finm.)) (2, (.,w) = fxx w + we;), where 6; is the standard basis vector. Queries of the form QDLO. can thus be used to implement gradient calculations for any differentiable model, noting that the number of queries q is the number of gradient calculations times the number of parameters. Finally, observe that, for differentiable losses, the queries of the form (1) equivalent to the form mentioned in (10) due to the chain rule.
parameters
We denote the class of adaptive and non-adaptive algorithms making such queries DLQe(g, T): = -S(q T) and naDLQe T):= =):==bLQ SaL---LLLLLaa -naSQ(q, T).
Remark 3.1. More common in the SQ literature is restrict the query in T (or equivalently, require precision relative to I Precision relative to (D)) is more similar to VSTAT [Feldman et al., 2017], and is more powerful than relative to L and our lower bounds hold against this stronger notion. In our algorithms and upper bounds we only need this additional power when
"We restrict the model class M to only contain models that are always differentiable at w = 0 without loss of generality, as for any non-differentiable model fa : x x R + F under any "reasonable" generalized notion of derivative with -= fa w) I==o= g(æ)) E V, one can define a differentiable model fz(x, w) fi (zx, 0) + w g( such that f2 0) fi 0) and 4. du fa(2, w== g(x).
5

---

Ve(u, y) is unbounded. If we further assume that these functions are bounded, e.g., the labels are bounded and V continuous, our queries have bounded L L and thus operate the more familiar SQ setling.
4 Leap and Cover Complexities
Definition 1. We define the leap and cover complexities for any system of subsets C S 2
(i) For any system of subsets C _ 21 its leap complexity is defined
Leap(C) == min max
[U, 1
(11)
U, kE(r]
U 0:
(ii) We define the cover complexity of C be Cover(C) = max min iE(P) UECiEEU
|U].
(12)
Remark 4.1. We always have Leap(C) S Cover(C). Both Leap and Cover complexities are closed under taking the union of subsets in C. Also, when supp(C) UVeCU + [P]. then we the convention Leap(C) Cover(C) oc. See a discussion about this convention in Appendix A.3 and in particular, the definition of the relative leap and cover complexities in Definition 3.
Here C is the system of subsets which are "detectable", and will depend on the the query access model. Intuitively, the leap and cover complexities of C capture the exponent of d in the query complexity when recovering the support of an unknown 8, P(dd, P), for adaptive and non-adapee adap-ddptee algorithms respectively. To discover the relevant coordinates of s., that correspond to U C, one needs to enumerate over (dd Hence, non-adaptive algorithm, which fixes the queries in advance, requires (d):) queries to discover 7th relevant coordinate i.e. (t), where k; min [U]. Therefore, non-adaptive algorithms need total number of queries that scales as (ddCover(C) to learn supp(s=) ). On the other hand, adapting queries using previous answers can greatly reduce this complexity as seen in the example in (2) in Section 1. This is captured by the leap complexity, which measures the maximum number of coordinates we need to discover at once. Finally, the set system of detectable subsets will depend on the type of allowed queries.
Definition (Detectable Subsets). Let μ. be a junta problem. Denote
(2((z)) = {T E L (px))) Ezzug =0}
the of zero-mean functions. For set of test function V S L2(Hy) say that U C V-detectable iff'
[P] is
ETEV, 37, E (22) for each i E U such that Epy.. ((v) II Ti(i)) #0.
(13)
IEU
We denote Cyp (1) the set of -edetectable sets, i.e. those sets satisfying (13).
The set of relevant test functions depend on the query types allowed and we define:
For SQ, For CSQ (recall y C IR),
ss (2(,)) (i.e. all L functions).
V Vcs = {u + y) (just the identity).
(14)
For DLQ+;
VDLQ. (v x Ve(u,)) EFF.EV)).
While the queries of the form (13), where V for A (SQ, CSQ, DLQ,) given by (14), are less general than o0y, x)) with ø E QA. they can be implemented by the corresponding query types QA and are sufficient for deciding between "S C [d] maps the corresponding U S P|" or "S g S.". The sets Vsq, V csq, VLL from (14) used for detectibility arise naturally in the proof of the lower bounds of Theorem 5.
To ease notation, for query type A, we use the shorthand CA == Cu and Leap (4) == Leap(CA Leap(Co, (H)),
(оverA(u) == (over(CA())) = Cover (1))
We refer to these the A-leap exponent and A-cover exponent of the problem μ.

---

Main Result: Characterizing the Complexity of Learning Juntas
Theorem 5.1. For any junta problem and any loss l, there exists C' > C > (that depend on P.p and the loss, but not d), such that for query types A {SQ, CSQ, DLQ;} with corresponding test function sets W A as defined in (14):
Adaptive. Let k. = Leapx There exists an algorithm A E A( that succeeds in learning Hip with and Ca" And μ satisfies Assumption 2.1, then for any (q,T) such that 9/T² S edd no algorithm A A(q,T) succeeds at learning H.d.
Non-adaptive. Let k, = Covera(μ). There exists an algorithm A E naA(q, T) that succeeds in learning Hip with T and q = Cdkt.. And if μ satisfies Assumption 2.1, then for any such that q/T² S cdt,, no algorithm A E naA(q, T) succeeds at learning Hy
(g, such
Remark 5.2. In the positive results Theorem 5.1, used all the allowed complexity to have many (g = (dd )) queries, and kept the tolerance constant. More generally, it is possibly to trade off between the number of queries q and tolerance T, at a cost of a log-factor; For k. = LLeap (u) and k. = Cover (H)). respectively, there exists algorithms A E A(q, T) and A E naA(g, that learn Hg. for any 2 C' (og(d) and T S c. with q/ q/T² 2 Ccd log(d).
The proof of this theorem deferred to Appendix B. Theorem 5.1 shows that the leap and cover complexities sharply capture the scaling in d of statistical query algorithms when learning H.d
Remark 5.3. The above upper bound uses that and therefore the T, Ti in Definition 2 are known. In the case when μ is unknown, one can follow a similar strutegy as in Damian et al. [2024b] and randomize the transformations! T and T, over sufficiently large (but finite independent of d) linear combination of functions in ss and L3 Under some regularity assumption on μ and E, one can show by anti-concentration that with constant probability, the expectation in condition (13) is bounded away from by a constant independent of the dimension.
6 Relationship Between SQ, CSQ and DLQ;
Obviously, CSQ C SQ, and indeed we see that Ccsq C. Csq in Definition 2 because of which Leapcsq 2 Leapso and CovercsQ 2 Coversq- For binary V, these query models collapse, but otherwise there can be arbitrary gap.
Proposition 6.1 (SQ versus CSQ). For any μ1 let Csq == (sQ( and Ccsq Ccsa If D/ 2 (binary output), then we always have Ccsq = Csq and Leapsq = Leapcsq and Coverso = Covercsq On the other hand if [>] 2, the SQ-exponents can be much smaller than the C5Q-exponents: e.g., there exist a setting with Leapsq = Coverso = and Leapcso = CovercsQ = P.
Similarly, DLQ, S SQ by definition, and thus, LeappLo. 2 Leapsq and CoverDLQ, 2 Coversq- Proposition 6.2 (DLQ; versus SQ and CSQ). Consider any μr (py. Hylz).
(a) Let y C R. For the squared loss E: (u, v) + (u yy) we always have CoLQr CcsQ- and thus, Leapcso = LeappLo, and Covercso = CoverDLQ.
(b) A sufficient condition for CsQ = CDLQ, is to have span ( (LQ.) dense in (1y)) Conversely, if there exists nonzero T LK(H)) bounded with T(y) orthogonal in (1,)) functions in DL then there exists a problem μ such that CoverbLQ, LeappLo. Coversq = Leapso
) to any
(c) There exists a loss & and a junta problem μ such that Leapsq(1) < LeappLa (n) < Leapcsq(u).. Similarly, we can have LeappLo, > Leapcss-
The condition in Proposition 6.2.(b) can be seen as a universal approximation property of neural networks with activation y + Vl(u, y) [Cybenko, 1989, Hornik, 1991, Sonoda and Murata, 2017].
The next lemma gives a few examples of losses with DLQ; SQ. For concreteness, we consider F = R and y C R.
7

---

Theorem 6.3. For l E {f1: (u. v) + lu- yl, hinge (u. v) + max(1 uy. 0)}, then CDLQ. (14 Csa(u) (u) for all' problems p. If we further assume y - II-M, M M 2 O. then E(u, y) e (exponential loss) has COLo, (4) (so(u) for all problems p.
The cases of & and Hinge loss follow directly from universal approximation of neural networks with linear threshold activation. The proofs of the above propositions and lemma can be found in Appendix Propositions 6.1 and 6.2 combined with Theorems 6.3 and 5.1 directly imply number of separation results between adaptive and non-adaptive algorithms and between different loss functions. See examples (2) in the introduction, and further examples Appendix
Gradient Descent on Neural Networks
The goal of this section is to connect the complexity of DLQ to gradient descent on standard neural networks. We focus the simple case of Unif((+1,-)) -1)d) uniformly distributed the hypercube, and y C I and F = R. In this setting, condition (13) in Definition 2 simplifies to: there exists T A such that E,y, [T(y) IIi 2i| E,,.. [T))) (=)] * O, where xU()) := llke 2 denote the standard Fourier-We Walsh basis. In particular, the set Ccsq contains exactly all non-zero Fourier coefficients of h,,2)) Ely|z], and recover the leap exponent of Abbe et al. [2023] as discussed in the introduction.
We train a standard two layer neural network (see (NNI) in Appendix D) of width M, using online SGD with loss function & x - Rzo, i.e. SGD on E. (x..)) [(( θ), y) for D E Hd More specifically, we train the parameters + = (0z E [M]] using batch-SGD with loss é and batch size 6 from initialization (0z) [0]) itd pa specified in (69). At each step, given samples
(f( 2kr) : [6])) the weights are updated using
0 +1
-
" Σ iE[B]
(JNNN Q'), Mai Voo ( 03) + 200
(E-bSGD)
where is the step-size and we allow for a E2 regularization with parameter À E R4. Recall that ((,,)) y) E Ögl(u, y) is the defined derivative of E(-, y) R. We define the test error
R(f) = Edg, [[(f(x).
(15)
and further introduce the excess test error R()) = R()) inf 11
Dimension-free dynamics. the junta learning setting, when y only depends on P < coor- dinates, following Abbe et al. [2022, Secion 3), the SGD dynamics (L-SGGD) concentrates an effective dimension-free (DF) dynamics as M, - oo and + 0. This equivalence holds under a certain assumption the loss function, and other assumptions the initialization and activation that are similar to the setup of Abbe et al. [2022] (see Appendix for details, especially DF-PDE).
Dimension free dynamics' alignment with the support. In the above limiting regime, LeapDLQ. crisply characterizes (DF-PDE) dynamics' alignment with the support.
Theorem 7.1 (Informal version of Theorem D.6). If LeappLo of the model at time t of (DF-PDE) dynamics depends on all coordinates 2;. On the other hand, if Leapplo, > 1, then there exists coordinate i such that for any time 2 0, the oulput of the model at time & of (DF-PDE) dynamics does no depend on 25-
1 then for some time t, the output
This establishes that the ability of (DF-PDE) dynamics (comparable to (E-SSGD) in the linear scaling) to learn all relevant coordinates depends on LeapDLo. (H) 1. That is if LeappLo, 1, then (DF-PDE) remains stuck in a suboptimal saddle subspace. On the other hand, if LeappLo: 1, then (DF-PDE) dynamics escapes this subspace and the weights align with the entire support.
For Hinge loss, we further restrict My measures with finite second moment that VA S (pw))
8

---

Learning of LeappLo, with finite SGD. Showing directly that (DF-PDE) dynamics indeed reach a near global minimizers of the test error remains challenging. Alternativel,, we show that a specific layer-wise training dynamics similar to Abbe et al. [2022] achieves vanishing excess error for LeapDLo, (n) = 1 settings the linear scaling of samples.
Roughly speaking, we train the first layer for L1 = P steps and then the second layer weights for kg = Oa(1) steps using batch-SGD with batch size
Oa(d), both for loss t. We consider polynomial activation (()) = (1 + x²² of degree L 2 28 The most notable difference from Abbe al. [2022] is that we further slightly perturb step-sizes for each coordinate 17" = 778; with K2 [1/2. /2,, and denote k = (K1..... Kd) E IR for the first layer training. This perturbation is necessary to break possible coordinate symmetries; see Remark 7.3.
Theorem 7.2 (Informal version of Theorem E.1). For a convex and analytic loss l, almost surely over the perturbation K and the initial bias E E the following holds. If Leapplo, (n) then the above layer-wise SGD training dynamics with total sample size = Os(d) and M +a(1)
achieves excess test error R[ (k)t o(1) with high probability.
The formal statement and the precise training specifications can be found in Appendix D. This result generalizes Abbe et al. [2022, Theorem 9] beyond squared loss.
Remark 7.3. A slight coordinate-we wise perturbation in the step-sizes for the first layer training is necessary to break the potential coordinate symmetries in the output y-see discussion in Abbe et al. f2022, Appendix AJ. This can be removed by either stating the theorem all but some measure zero set of Leup-1 functions as in Abbe et al. [2022], or by studying the dynamics for O(log d) steps.
The query complexity of b-batch SGD M neurons for T StD-steps is Tc (bbMTd). The above theorems show that for LeapDLo. (p) = 1, Y = (d/b) steps with M = (11) neurons
therefore Tc ( sufffces to learn the support and minimize the excess test error. Furthermore, for LeaPDLQ, (p) > 1 and neural networks trained in the mean-field regime, Y ((d) (and therefore Tc = ((d))) is not enough. We further comment on the general conjectural picture in Appendix A.2.
Numerical Simulation. We consider a function similar to y2 in (2) with Leapcso but Leapso 1. Specifically, we set P= and C = 2,1,2,3, (1, 2, 4). (1,3, 4}, (2, 4) and define (=) where
1x(2)) Σ (U)xo(() where (U) Unif([-2, for U e. UEC
(16)
We train with online 1-batch SGD (L-bSGD) on two-layer net with different loss functions (without any regularization) and stepsize γ) x 1/d, where we consider ambiant dimensions E {100, 300, 500). In Figure 1, we plot the test mean squared error versus vj x SGD-iterations (thus also scaled with 1 1/)), over 10 trials. Additionally, we also plot the continuous time (DF-PDE) in (dashed black line) that corresponds to the limit d 00. 00.
022-2
-43---13
540. -100 -33
6,25-
248 4- 103 a otiiih
meen squared ertor
542-5 -33
Teat maan squared or
0.35-
effcciv
Tea maaam squated
00:5
60.55
0.32-
0:10
6..0-
0.65
0:55
0.00
6:25-
250
550
150 1990 1250
185 2002
252
350
150
3000
1250
1550
1150
2007
150
1903 p/2 Reraion
1750 2050
Em iteradoons
gx Sersionn
(a) E(, v) (u y)
(b) E(u, y)
(c) E(u, y) = (u y)² + 5/
The function h. (z) in (16) has Leapeso = 3 but Leapso = 1. For the squared loss (left plot), (DF-PDE) remains stuck initialization (no learning), and to escape the saddle, SGD requires number of iterations that increases faster than (d). For the absolute loss (center plot) or the other loss (right plot), have LeappLo, Leapsq and the SGD dynamics learns O(d) steps and (DF-PDE) learns ((1) continuous time.
Figure 1:

---

8 Conclusion and Outlook
In this paper, we considered learning juntas over general product distributions with statistical query algorithms. To capture learning with gradient evaluations over a general loss and arbitrary model, we introduced Differentiable Learning Queries (DLQr), which can be seen as generalization of correlation statistical queries beyond squared loss. We then showed that the complexity of learning juntas with either SQ, CSQ, or DLQ, algorithms is sharply characterized in terms of a leap exponent (adaptive queries) or a cover exponent (non-adaptive queries). These exponents are defined in terms of minimal combination of detectable sets to cover the support, where the system of detectable sets depends on the allowed queries. In general, the leap and cover exponents for different losses are not comparable. However, we identify "generic" losses, including L1, where DLQq algorithms are as powerful as SQ algorithms for learning juntas. We further showed that DLQ, can indeed capture the complexity of learning with SGD in the case of data on the hypercube.
Worst-case v.s. One-pass v.s. Multi-pass SGD. DLQ₁ (like SQ) is defined in terms of worst-case noise. It is well understood that worst-case noise is theoretically very different from estimating population gradients based on samples (either independent samples as in one-pass (S)GD, or with repeated use of samples as in full-batch or multi-pass) when highly specialized models are allowed [Abbe et al., 2021b]. However, we expect DLQ, to still capture the complexity of one-pass SGD in many settings of interest-wiin with "regular" models- such as in Section 7. With sample reuse (e.g. multi-pass) the situation is more complex: Dandi et al. [2024] showed that two steps of full-batch gradient descent with square loss goes beyond CSQ. Heuristically, and in light of our work, two steps on the same batch can be seen as a single gradient evaluation on a modified loss, thus going beyond CSQ = DLQ but remaining inside 2 C SQ for some perturbed non -unadraaaiicc loss f. Indeed, we expect generally that multi-past SGD "regular" model will remain in SQ.
Multi-index and beyond. In this paper, we focused on learning sparse functions. We hope the modular nature of our analysis framework (defining detectable sets in terms of test functions, and leap and cover complexities of set systems), our definition of DLQ, and the distinctions we emphasize between CSQ, SQ and DLQ and between adaptive and adaptive complexities, will be helpful in guiding and contextualizing analysis in other settings such as learning single-index or multi-index functions [e.g. Refinetti et al., 2021, Mousavi-Hosselee et al., 2022, Abbe and Boix-Adsera, 2022, Damian et al., 2022, Bietti et al., 2022, 2023, Damian et al., 2024a]. For example, the information exponent for single-index [Arous et al., 2021] can be seen as analogous to CSQ-cover exponent, the generative exponent for single-index [Damian et al., 2024b] as analogous to our SQ-cover exponent, and the isoleap exponent for multi-index [Abbe al., 2023, Dandi et al., 2023, Bietti et al., 2023] as analogous to our CSQ-leap exponent. It would be interesting to obtain a unified understanding of these specialized treatments and extend our general framework to multi-index models, and also to learning under other invariances beyond permutations and rotations.
In our setup, we emphasize generic input and output spaces, without a field structure. This emphasizes that when learning juntas, polynomials or degree of input or output coordinates is irrelevant. Defining multi-index models and introducing rotational invariance necessitates a field structure and gives rise to the relevance of polynomial degrees and decomposition.
An important point is that when considering permutation (as in juntas) vs. rotational (as in multi-index models) invariance, one must consider not only the invariance structure of the target function class, but also the input distribution (i.i.d. coordinates as in our case, or more generally exchangeable vs. spherical) and learning rule. E.g., learning a parity over input coordinates requires only O (log d) samples, but rotationally equivariant algorithm effectively learns parities also over rotated axis, which requires ((d) samples [Glasgow, 2023] (and thus (2d²)) runtime). This also explains the need for (dd) steps and thus ((d²) runtime to learn 1eap-1 functions using SGD on a rotationally invariant neural net in Section 7. In order to break the ((d)-ample lower bound, we need to break the rotation- equivariance, e.g. using sparse initialization and E regularization, which indeed can achieve (llg(d)) sample complexity.
This research was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of Deep Learning and the NSF Tripod Institute on Data Econometrics, Algorithms, and Learning (IDEAL).
Acknowledgement.
10

---

References
Emmanuel Abbe and Enric Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. Advances in Neural Information Processing Systems, 35:17188-17201 2022.
Emmanuel Abbe and Colin Sandon. On the universality of deep learning. Advances in Neural Information Processing Systems, 33:20061-20072, 2020.
Emmanuel Abbe, Enric Boix-Adsera, Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems, 34:26989-27002, 2021a.
Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340-2445
2021b.
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782 PMLR, 2022.
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552-2623. PMLR, 2023.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv e-prints, pages arXiv-2001. 2020.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high- nigh-dimensional inference. Journal of Machine Learning Research, 22 (106):1-51, 2021.
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768-9783, 2022.
Alberto Bictti, Joan Bruna, and Loucas Viviend-Vivien. On learning gaussian multi-index models with gradient flow. arXiv preprint arXiv:2310. 19793, 2023.
Avrim Blum and Pat Langley. Selection relevant features and examples in machine learning. 1997.
Artificial intelligence,
Nader H Bshouty and Vitaly Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2(Feb):359-395 2002.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Michael Celentano, Theodor Misiakiewicz, and Andrea Montanari. Minimum complexity interpola- tion in random features models. arXiv preprint arXiv:2103. 15996, 2021.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Alex Damian, Eshaan Nichani, Rong Ge, and Jason D Lee. Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. Advances Neural Information Processing Systems, 36, 2024a.
Alex Damian, Loucas Fillaud-Vivien, Jason D Lee, and Joan Bruna. The computational complexity of learning gaussian single-index models. arXiv preprint arXiv:2403. 0555999 2024b.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pages 5413-5452. PMLR, 2022.

---

Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. Learning two-layer neural networks, one (giant) step at time. arXiv preprint (xXi::3305.18270 2023.
Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala.
The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint arXiv:2402.03222 242222222.02., 2024.
Richard M Dudley. Real analysis and probability. Chapman and Hall/CRC, 2018.
Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Pareto frontiers in deep feature learning: Data, compute, width, and luck. Advances in Neural Information Processing Systems, 36, 2024.
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao, Statistical algorithms and lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2): 1-37, 2017.
Margalit Glasgow. Sgd finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the xor problem. In The Twelfth International Conference on Learning Representations, 2023.
Samuel Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))983-1006, 1998.
Yiwen Kou, Zixiang Chen, Quanquan Gu, and Sham M Kakade. Matching the statistical query lower bound for k-sparse parity problems with stochastic gradient descent. arXiv preprint arXiv:2404. 100/4..23344 /2376, 2024.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC' Congress (International Society for Analysis, its Applications and Computation), pages 1-50. Springer, 2019.
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. In International Conference on Machine Learning. pages 7379-7389, PMLR, 2021.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 11533)):76665-8767), 2018.
Alireza Mousavi-Hosseine Sejun Park, Manuela Girotti, Ioannis Mitliagkas, and Murat A Erdogdu. Neural networks efficiently learn low- -ow-iieenioonal representations with sgd. arXiv preprint arXiv:2209.14886 14863, 2022.
DJ Newman and Morton Slater. Waring's problem for the ring of polynomials. Journal of Number Theory, 1144):477-877 1979.
Amelia Perry, Alexander S Wein, Afonso Bandeira, and Ankur Moïtra. Optimality and sub- optimality of pea i: Spiked random matrix models. The Annals of Statistics, 4665):2416-2451, 2018.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed, In International Conference Machine Learning, pages 8936-8947. PMLR, 2021.
Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00537, 2020.
12

---

Grant M Rotskoff and Eric Vanden- Eijnden. Neural networks interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. stat, 1050:22, 2018.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 130(3):180018822 2020.
Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. Advances in neural information processing systems, 30, 2017.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-268, 2017.
Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 1-200. IEEE, 2012.
Santosh Vempala and John Wilmes. Gradient descent for one- mee-hidden-lare layer neural networks: Poly- nomial convergence and sq lower bounds. In Conference on Learning Theory, pages 3115-3117. PMLR, 2019.
13

---

A Additional discussions from the main text
A.1 Necessity of Assumption 2.1
We further elaborate on the necessity of Assumption 2.1 in our setting, Informally, we require the label to have "enough noise". This is necessary to obtain meaningful lower-bounds for general SQ algorithms, as noted in Valiant [2012], Song et al. [2017], Vempala and Wilmes [2019]. When learning real-valued target function classes, allowing for general measurable queries is too weak (note that arbitrary measurable functions are not practical anyway). Indeed, Vempala and Wilmes [2019] showed that any finite set 7 of (noiseless) functions can be learned with log [H| (bounded) queries and constant tolerance They identify three possible approaches address this challenge: (i) Require > (VV az) to be Lipschitz for every fixed æ; (ii) Insist on noisy concepts, e.g. y = f(x) + Ç. with Ç ~ N(O, d²), which equivalent to Lipschitz queries; (iii) Restrict the form of the queries, such as in CSQ. Our Assumption 1 can be viewed as quantitative version of approach (ii). For approach (iii), we restrict ourselves to CSQ or DLQ with piecewise analytic, we can indeed remove Assumption 2.1 by modifying the proof of Theorem 5.1.
A.2 The conjectural picture of complexity of learning (L-bSGD)
For k. :- LeappLO, (4), learning the junta problem with online SGD on loss E requires
k. 1: k.
n (d))
Tc O(d
n (d d),
Tc = O(P))
k. > 2: n 6(d
Tc = ((d
Partial evidence was provided towards this conjecture for the square loss in Abbe al. [2023], Bietti et al. [2023]: they showed that learning in this setting happens through saddle-to-saddle dynamics, where each time the neural network needs align to k >> 1 new coordinates, saddle appears and SGD requires ((dk-1) steps to escape.
1.0
562 100
SGD 166
3.2
5G3 2and-100 Loc
562 300
SGD 166
SGD d- 366
O..
562
SCD 500
6.3
562 500
Text maaat squarred
0.4
6.4
1200
1250
1200
Euration
Rerationa
(a) (u, y) (u y)
(b) E(1, v)
(c) E(u, v) (u v)
Figure 2: We repeat the same experiment, with the step size vj x 1/d as in Figure but now considering the order 3 parity function (z) 23 Since y {-1,+1). Proposition 6.1, have Leapso Leapcso LeaPoLo, = 3 for all the three loss functions considered. observe that online SGD learns in Old)) iterations for all the losses.
A.3 Identifiability and Relative Leap and Cover Complexities
The Leap and Cover complexity may be infinite when supp(CA) Uvec, U Ç (P), in which case Theorem 5.1 (correctly) implies that we cannot recover the relevant coordinates that correspond to supp((a) using queries of type A (even with perfect precision). In this case, can characterize the complexity of recovering supp(Ca) instead, and this is captured by the following "relative" complexities:
*The result holds under a "non-degeneracy" condition, namely, for any f,9 E H. f # 9 almost surely. Consider for example y (1) with N(O, I2): using the construction Vempala and Wilmes [2019], we learn H. with 7/>² ((log(d)) queries instead of q/-² O(d) in Theorem 5.1.
14

---

Definition 3. For any system of subsets C _ 2! the relative leap and cover complexities are:
relLeap(C)
min U.C U==upp(()
max iE(r]
1U4 10AU) b
(17)
relCover(C)- = max
min
10%.
(18)
:Esupp(C) VECREU
A slight variant of Theorem 5.1 can then be shown, where relLeap (4) and relCoverA(μ) for A E {SQ, CSQ, DLQ;} characterizes the complexity of recovering supp(Ca).
For SQ, we may have supp(Cso) & [P] only when y doesn't actually depend on some of the coordinates in [P] (i.e. z = y [z; (csupp(C)) In this case,
recover supp(C)) (and possibly enumerating permutations of its coordinates) can also recover the conditional y/æ. That is, relLeapso and relCoverso characterize the complexity of learning the distribution De., even not the (unidentifiable) set St.
For DLQ;, including CSQ, we may not be able to identify some coordinates even y does depend on + (O =3) Although
them. Consider for example the junta problem of size P= 2 where y identifiable using CSQ queries, supp (cso) = {1)
does depend on the second coordinate 22, it cannot recover the conditional distribution D., (even if we know the link ). What can say for DLQ, after recovering $ supp(CoLQ,), is that although might not know D... . relLeapoLo, and relCoverpLo, characterize the complexity of é-risk minimization.
and using CSQ queries
find the ê-risk minimizer f. arg m. ((y,)),D, [e(f(x), v)]. That is,
A.4 Property of SQ Leap and Cover Complexities
We show a useful property of the SQ-exponent. This characterization is similar to the definition the generative exponent for single-index models on Gaussian data in [Damian et al., 2024b, Definition 2.4], while the detectable set Definition is similar their variational representation [Damian et al., 2024b, Proposition 2.6].
Proposition A.1 (Property of SQ-detectable sets). U E CsQ if and only if there exists T₃ E L)(Mw) for all such that [[Er:l==((,)) > where
Eu (v) Ey
II IEU
(T((2))))
Proof of Proposition A.I. In the forward direction, consider any U E CsQ, then by Definition 2, there exists T, ()x())) and (2(gy) such that
0 + Eyy.a
T(v) II T((2)) SEU
Ep, (T())
where we defined (v) = Epg.. Ieee T((:;) v] We then have
<< Er (v)) S (
(( by Cauchy- inequality.
Therefore, we conclude that || (l.2(1y)) > 0 as desired. In the opposite direction, let us consider U C [P] such that there exists 7, E Lb(x)) for every E U such that ||Eor ((tr))2 0, where
Eo (v) = Buy.
Liet
Then let T'y) = Eu (v). is straightforward verify that
| E,, [T())
En
E
II
(1)) ly
$ E
II TI(2))
< <0.
LiEU
LIEU
15

---

We verified T(y) E (Jyy) Moreover.
Eyg
T(v) II
(i(x))
= Bu
Bu.
II (i(2s) y
IEU
LiEU
Byy (E) (v)] l1Eu (12)( 11 * 0.
Therefore, by Definition 2, obtain U E CsQ-
B Proof of Theorem 5.1
B.1 Preliminaries
Tensor basis of (2 ,,)): Since assumed that (2) is Polish probability space. (X, (2) is separable [Dudley, 2018]. Consider (wi)ez. I S N, an orthonormal basis of T2 (x)) such that vho 1 without loss of generality. In particular, the space [2* p ad-
mits the following tensor basis
[ == w/ 2 the
@ the i= (1...... 4x) E IT)
(19)
We will denote supp(t) = {j d 0}.
Distributions v/: For any non-repeating sequence a E P([d), P) of length P. subset U C
[P]. and system of subsets C (UI...., ............. S 2(r), we denote oU)) := {a(i) : i E U} and (C) := (o(U)),... (U,)) The following analysis holds for fix μ and hence we will often omit the subscript μ by denoting Dí. Dø for any
P([d] P). For
ld. i...
(11) = 1....., (PP) = P. we will further omit writing Id and denote D = Día For S [P]. "y... E P(Y x p) is the distribution of (),,2) corresponding to decoupling y from (=i)ggu in Py.x following Eq. (6), i.e., (yU, (zi)iE)) ~ My,s.u and (zi)igu ~ pzz P-10| independently. For clarity, for every U S [P] and a E P([d], P),
v = [ld @ of 1 y. @ Pz P)
(20)
where we abuse the notation and view a as permutation in ILg, by extending the sequence or P[[d), P) to an ordering of irrelevant coordinates, as notice that it yields the same vū- In words, vi is the distribution of (y, x) where we decoupled from (Fo()))Eg in Dé. For a = Id, we denote vy uld For U [P]. we simply denote 1" = De. Note that vp == uy By @ ng and vg vu (i) for all E U.
Basic properties under Assumption 2.1. Recall that our lower bounds in Theorem 5.1 are under Assumption 2.1. It states that the junta problem μ My)=) .) is such that Eq. (7) holds. An immediate consequence of this assumption, using Jensen's inequality is that
dp duy u
E L 2 ~.))
(21)
Indeed, this follows from
dp diyy @ d
dpy. diy @ a (L(W)en
< 00,
(r
where the first inequality follows from Jensen's inequality and the second by (7).
Another consequence of this assumption is that, for any U S [P] and E P([d, P), we have (2(v)) S L (VG). This is because for any & E (2)))
dv duo
dvy ( < 00,
[ا = (y [1 x]]] (y.
(y, |6(u,z))
du (.2(0))
where we used Cauchy- Schhwar inequality and Eq. (21))
16

---

Algorithms in A: Throughout the proof, we consider A E {SQ, CSQ. ) and CA := (A( defined Definition 2. First, observe that one can alternatively define Qsq L' (vo) because for any measurable Φ & (vo), the received query response can infinite by (8) and the learner does not gain any information. Therefore, it suffices to prove lower bound against the query set Qsq = I.2 (vo). For the same reason, consider the allowed query sets, Qcsq S (1)) containing queries of the form Φly, x) yo(x), and QDLO. LL2 (v6) with queries of the form
[ ov, x) dw f(2,w))
(e(f(z,0),3)
(22)
w=
We claim that, for i E Id and tha defined in Eq. (19) and any e E Qx. Definition 2 implies that if supp(1) @ (CA)), then almost surely over á 10
(y lØ(v. x)][(==]] =.
(23)
This follows from Definition of V/ V-detectibilitty with Eq. (14), and using the fact that thy is the
product of 4/s, (2z)) with 4ii (1z) for supp(i). More specifically, since á T (20)),, the
function (,, 2) E (2(g)) almost surely over plg and In particular, almost surely over & p
For any Φ E QsQ=
we have ( 3) E 1, (11y) Vss
For any ø E Qcso.
we have o( = yo( (i.e. a scaled identity),
For any QDLΩ,
we have () E DLO, (i.e. o(., a) of the form v Vl(,,y)).
B.2 Theorem 5.1.(a): lower bound for adaptive queries
Definition of set S,: Let k, = Leap(Ca). Define C. C CA to be the maximal subset of CA such that Leap(C.) S k, 1, and S. Uteec U. In words, S, is the collection of all coordinates in the support that can be reached by adding at most k. - 1 coordinates at time. In particular, by definition of C., we have U S. 2 k, for every U E CA C.. Denote r = |S. and without loss of generality, assume that S. = [1.....r}. We decompose the covariate into x = (xs) where S. = [d] \ S.. Using these notations, (VS., x) ~ v/3. has (VS_. To(S.) ~ Dg.,,S. and (S() p independently.
Definition of Hy.ss: We introduce ([dd).P.S. _ P([d), P) the subset of non-repeating sequence of length [P] from elements [d] such that (1) = for all E S., and u.s. S Hd the subset of hypotheses D&d with P([d], P.). Recall that for all P([d], P.S.), we have v/g vs.. To prove our lower bound, we will lower bound the complexity learning Hd.ss which implies a lower bound on Hd Specifically, we will show that with g/>² < cd for some constant c > 0 that only depends on P. p. (and the loss for DLQ,), statistical query algorithms in A cannot distinguish for all E P([d), P, S.) between 10
=Dd and vs..
Proof outline: For any a P([d), P. S.) and query & QA C (1))))), define (d = E,- (0) Evs. [ø].
(24)
We will show below that there exists a constant C that only depends on μ such that
E, A.) 1
sup (
S R..
(25)
where E, denote the expectation with respect to a ~ Unid(P([d], ).). The intuition behind this crucial bound in (25) that we defined the null distribution the distribution with matching marginals (y. æ) where the label only depends on the support of x discoverable with "leap" k.. Hence, to make any progress, any new detectable set added to the support needs to contain at least k, new coordinates. In the second moment, to have a non-zero contribution, we need the permutation to map the support to detectable subset, i.e. the permutation map to a subset of size at least k., which has probability O(d-k.) over permutation.
17

---

Let 01..... 04 be the sequence of adaptive queries with responses Evs. [o.]. Then, by Markov's inequality,
E, (0)) dERa 1001
I C qdth.
Po (3t lgl. ( > ((101l13(0)) S
sup
(26)
72
Hence, for g/7² < d /C, there exists P( such that for every / [g], we have [E [6x] - Eys, [ov]] S -ll@xlle?ten Therefore Using Eq (26), we obtain that that there are two members from H4, whose query responses are compatible with the null vss., and hence also mutually compatible and indistinguishable from each other. This then establishes the failure of the learning algorithm in recovering the correct support.
Decomposing A. (o()):
We rewrite (0) in terms of Evs. using the Radon-Nikodym derivative:
dv"
Evs [o] = Evs. [( (dvv-
Ao (Ø) = Evs.
dus. (ys. x)
11) ((s.. : :2)
(27)
dvs.
Recall that (ys.: (s..) is independent (5)() ~ po- under vs., and that du² /dvs. E 1,2 (vs.) by Assumption 2.1. Therefore, we have the following orthogonal decomposition in (vs.)s) using the tensor basis (19):
dı (ys. 20) -1
Σ
(vs., (v.)
(28)
dus.
4EIa-r\00 {0}
where
dv² (ys., x (ass:))))))))))))))))
(US... Eys.
us. US.
Ev- [
(29)
dvs.
Similarly, we decompose o orthogonally in L (vs.))
x)) = Σ
assss (11
(30)
TETN-P
where
04 ayss. a.S.) = Bus.
[olus. ())as us.. as.]
(31)
We deduce that we can decompose Ag (6) as
(o)
Evs. (oss,
(32)
iEZa-r (10)
For convenience, denote m. the summand. From the expressions (29) and (31) and by Fubini's theorem, rewrite m as
us.. mf R.ys. as. Eye [va( uus. ms.] B Raggr1 -- #s. #s;) (s:)
E (y. m. out (T Vo xs. 3 ( [+s;)]
(33)
E - P-r ( ( (g [o(y, ss.. us: W (xs:
Let us decouple from æs. inside the query o using the Radon-Nikodym derivative: conditional on Syy we have
E gg [oly, vS. Ts; ) (xs:)]
du (ys;, a)) plys;, u.s. Ts; vos)))
(34)
= Bsss ~rg
dug.
Similarly to Eq. (28), we have the following orthogonal decomposition in (v3:))
d
(us;, x)
Σ
xt:) ( (35.))
(35)
dug
jEi
18

---

where
{j (ysg. Ts;)) = Ey [ely (zs. Us: Øs;]
(36)
By Fubini's theorem,
(iss ms, msy mss)) 2ougg [ (USs us: U s @ Us. Rs: (
(37)
Ess, ~Mt (uly (ās. ( [Ø ãs. Ss by (as. (xs:)]] Combining Eqs. (34), (35), and (37) into Eq. (33) yields the expression
m
Σ Eenng [vby (ās. ( (o
(1
(38)
JEI
From Eq. (32), we deduce the following simple decomposition
(0))
Σ
Eamny [vhe (z) (y.a)) lo ())())]]]
(39)
tEIS, supp(Uizs.
Bounding E, A (o) If supp(t) E oCA Cx), we have by Eq. (23) that Ex-uy (()a)))) (0(y, (x)( 0.
(40)
Therefore we can rewrite the sum in Eq. (39) with
(Ø)
Σ
E (v and ( ()){ [supp(() o(8) SECA/C.
iE7d
(41)
(w ( 2) ) (x)] ([((spp((i) = S}.
iEId
SECANC.
Recall that for every CA C. by construction. Hence,
EE
Σ
((o(supp(i) S1, o(supp())) S2l
Cdtk.
(42)
S,CACC.
By squaring Eq. (41) and the previous display, we deduce that Eg (
< kd
T (y. a)) (V) () x)ba(()))
du
S Cd
Bynnyy
Banpg
(v. m))a((r)))
Bawpe (o(y. ()).)))((()))
de
iETa
di (u. x)))(())))
27 1/2
E Banny (o(u. [0(0))))((=))) 1/2
2
k.
E
Buy
Epg
(43)
dun
iETa
< <k
E
Buy
Eny
dv
(2. (())(())))
11)
27
Buy Eawny [0(y. [)){())]
deo
iezd
ieza
Cdd
K0d-k.j.. C. Eynny dep
dv
(2.-)
Eyrn, [|dee )112A
(22))))
du 2
-e
| (1) S C'd C'dd (1b0l
dub
(P(())
where we used in the third and fourth line Cauchy- Saanhh--Shhwaz..oe inequality, and in the last line
dv dpy, (²o))) du
(44)
duy @ pff
by Assumption 2.1. Note that the above bound is uniform over all & E T.2(v)). This concludes the proof.
19

---

Remark B.1. We remark that indeed these proofs, after alternatively defining k. = relLeap(CA) and C. to be the maximal subset CA such that relLeap(C..) = ki 1, shows that if 2 S edl then mthods in fail to recover coordinates from CA C..
B.3 Theorem 5.1.(b): lower bound for non-adaptive queries
The proof follows from a similar argument to the adaptive case.
Proof outline: Let k. = Cover(CA) and I. that maximizes minsec,,tes (S]. By definition of the cover complexity, |S| 2 k. for all S CA with 4 S. Let Let := [P] {4.. We define in the
non-adaptive case for all ø E Qa and o E P([d), [[dd],P) P),
(o = E [o] Eug. [o].
(45)
meaning that we compare the query expectation between v and V'S where we decoupled the label from coordinate ol,,. We show again that the bound (25) holds on the second moment of (6)) (l@l)///lll=/ Therefore, for any set of y queries { (etal C Qa. we get similar bound (26) on the probability of all queries being less equal to r in absolute value. We deduce that for q/T² I od!., the algorithm will not be able distinguish for a E P([d], P) between v" and vg..
and therefore recover the coordinate ol.) in the support.
Bounding E,, [+)) Following the same decomposition of A. (6) as above, we first obtain
(0) = Σ
Egg (v3. (oss xc
(46)
iEZ((0)
and then
Σ
Eg Ba (R [0(v. 2) [))][=]]]]]
(47)
KEZA, (())).
Therefore, by Eq. (23), the summand is non zero only if supp(t) C (Ca) with (l.) supp(i).
Recall that in this case |supp(t)] 2 k. by the choice l.. The rest of the proof follows using the same computation as in the previous section.
B.4 Upper Bounds for Adaptive and Non-Adaptive Queries Define
8 min UECA
Byy.. (T((v)
(v) II II (.))
(48)
VEU
with T V and T. (1x) chosen to make the expectation non-zero, where without loss of generality we normalize them so that | Iles II (_))))))) 1. We can then emulate the support recovery algorithm described below Definition in Section 4 using for every U, CA and JS| |U+,.. (s x) T (y) II T. (ax) (note that here S is an ordered subset) and precision 3/2, so that if the response |uy| > 8/2, then S E a. (Ca). Note that Øs x)) are indeed in QA: for SQ, CSQ this is direct, for DLQ,, we take (x; = a + w IlLes T. T2-(2:)
If take 3/2, the number of queries only needs to scale ((dCover)) further trade-off the precision and accuracy and get the result of several of the above queries with one query with small enough т. For example, consider testing subset {i} find s. s1). Then, one can group each of this query in O(log(d) groups G3 following the binary representation of i, For each of these groups, consider the query
Oddeepss). We can
1
Σ (T) (v)T()) SEGL
Note that this is indeed a query in MA it has (P())) norm O(1) (indeed (2) = 0 for any + with at least one not in the support). With precision O(1/Vd), of those expectation is non-zero Repeating for each of the (llg(d)) groups allows to recover the binary representation of {s. (1)). This idea allows to trade-off off the query and precision for any g/-² > Cddt log(d).
test if one
20

---

C Proofs of Technical Results
Proposition 6.1: Denote y {a,b), For any U CsQ(H), by Definition 2, there exists T (Pyy and {T; E Li( such that
0 + E T(v) II Ti(i)
AEU
y a)F
II (1((4) y a) (V = b)
II VEU
T, T.) y bb]
(49)
iED
II T1(2)) = b]. XEU
= (T(() - -(aa)) b
where we used that [x,)] = O. Hence, this expectation is non-zero for any mapping T(b) & T(a). particular 7 1d. We deduce that U (c) too.
Consider X = IR and Ps 7 the standard Gaussian measure. We assume that the label
2122' 2p. Then Cesq only contains the entire support [P) and Covercsa(p) Leapcso (N) P.
On the other hand, consider the mappings (yy -[ly] 7] for some >> 0, and (2)2 2î 1. Then
E[T(V)T(<)) E._. Ezs
(2)
II
3
[]]]
> 0,
(50)
and Csq (n) contains all the singletons {i} for i E [P]. We deduce Coversq(u) Leapso (n)
Proposition 6.2.(a): Note that (( y) = (u - y) for the squared loss. For any U S [P]. and any
(T, E (1xz) [P]), have
Exy.
(u
y) II T((2)) kEU
(u (1+))
-uy.
VII
Ti(zi)
Epy.
y II Ti(2;)
IEU
iEU
sEU
Thus,
(u v) II (2:))
* if and only Epp..
(u
T.(..)
iEU
iEU
This immediately implies CDLQ. = CsQ by Definition 2, and as a consequence Leapcsq = LeappLQ. and Covercsq CoverDLQ.
Proposition 6.2.(b): Consider U E CsQ with
E E
T(y) T.+))) #0. iEU
(51)
Note that without loss of generality we can assume T E (1())) If span(VVLo is dense in Lg(H)). then for every E O, there exists Mr E N and (nj, Uyjj{u) S V x such that
TM,
Σ v]V((u,,))
(52)
JEIMJ
has I|T -TMr (lell) I E. In particular,
Bpye [TM. (1) T.() - Byy.. ((x) II TI((=)) SEU
$ -|T (l
II [|T: [TTille (53) iEU
iEU
Therefore taking sufficiently small, TMr has non zero correlation with Ile T,, and in particular, one of the J. Vi(u, y) must have non-zero correlation too. We deduce that Csa C CDLQ, and we conclude using CDLQ. Csq.
Let assume that there exists nonzero bounded T E Lz(2),, which we take without loss of generality Tyy) C [-1, such that VivTV((u ())] for all u E F, v E V. The goal is to
21

---

define Hy.z such that CDLQ, & Cso. Specifically, we will construct joint distribution on (y. 24) with {i} E Csq but {i} & CDLQ. Let c X' with Pz (A) E (0,1) and consider y that only depends on 2; through L|2 E A]. Denote P(Aly) (2 E Aly). For any T, (Hx))
M=) - (Z) E A] + P(AT))) 24 & A]. Denote x(A) (z) E A). By definition [.T) = 0 - Ms (A) (A9( and therefore x(AA) = (a) (1 (A)). Hence,
(54)
((TT(z)) [l] = x(A)
(A) [P(Aly) - us (A)]
(55)
Taking À > (1 (A)( Pz (/)0////)))))))))))))) we can set
P(Aly) := (1-M(())) + (s(A) (0,
(56)
We then define the joint distribution of (y, 24) as
py. [M=(2e E P(A()) (2 & ()P(A-/)))))))
(57)
Note that [[[((A|)]] = (A) using that E[T(y)) = 0, and therefore the marginals of My.s. are indeed My and Maz For any T. E (1zz) and (u, 0) E F x V. we have
x(A) Ey,, 10 T Velu, g)]( - 00
E Ep lo Viuu vl [z:]]
(58)
and therefore {i} & CDLQ. On the other hand T L' (1yy and therefore {i} CsQ. We conclude that the joint distribution (y, =:) has LeappLo. = CovernLo, = Do while Leapso = Coversq = 1.
Proposition 6.2.(c): We construct a simple example with X' = {+1, -1 and Hex = Unif(X)), i.e.
uniform on the discrete hypercube. Consider P 2k and label
y = 21
22k
Σ
2/
(59)
The set (z) contains all subsets [2k] \ {i} for all E [2k]] and therefore
(overcsa = Leapcso (1)) = 2k 1.
(60)
Consider the loss function E(u, y) 1/2 [y 0.)2 1 u)1 The derivative is given by
E(u,y) y) u y + nd 3u²y y + 3uy² y²
(61)
We have
3
2² = 2k: + 2
Σ PiZgi i<j
3²² = 21 ... 22k
(62)
zi
1E|2)]
For k 2 3. yd only contains monomials over 2 2k 3 2 3 coordinates. Therefore COLQ, (1) contains
all pairs {i but no singleton. Hence,
Coverplo, (p) = LeapbLo. (1) = 2.
(63)
Finally, for CsQ. taking T(y) = - it contains all singleton {8) and therefore
(oversa (4)
(64)
C.1 Proof of Theorem 6.3
Note that CA does not change if we add or remove constant functions to W.
l losss First consider f(u, y) y u// We have Vl(u,)) y) ((, y) sign(u y), where can set without loss of generality (0) = 0. From Hornik [1991, Theorem 5] and Hornik [1991, Theorem 1], we directly conclude that for any probability measure My on R, we have span V A) dense in L (My)) and we conclude using Proposition 6.2.(b).
22

---

Hinge loss: Consider the Hinge loss f(u, y) - max(1 yu. 0). We get (u, -yluysy where without loss of generality, we set (1/y.
y. For a 0 and b < 0, we have (a. y) (b. y) y [V a] y1 yy < bj. Taking b + -0, we have ((a v) L' (b,,, y) that converges to y [y > in
T,a (1ay) (recall that we assume that the second moment (yy is bounded), Similarly, we can construct y1 a] for S O. Following the proof of Hornik [1991, Theorem 1J, if span V A is not dense in
L (1yy), there exists E (Pyy such that
J yyly > ulgly)day
Vu I.
(65)
Define the signed measure oBB) JB voly) lv ( llg (m)))))))) < oo by assumption. We deduce that
It is finite since lug(v)lduy
/ 1lay > 0jdo(y) 0
V(a ER?
(66)
(The case a = O is obtained by taking u + oo in Eq. (65).) We then use that [ay - u > 0] is discriminatory and therefore such finite signed measure exists.
Exponential loss: Consider y S [-M, MM MM] and f(u. y) = e ey so that (' y) - 9y Any Borel probability measure My on [-M, .] is regular, and in particular continuous functions and therefore polynomials dense in L (my)) To show that span (ye yu E E} is dense in L (My). it is sufficient to show that we can approximate any monomial y² in L (May). This is readily proven recursively, using that
ye
u 141 +O(w)
(67)
This concludes the proof of this theorem.
D SGD, mean-field and limiting dimension-free dynamics
Fix link distribution y/æ= Mylz and consider data distribution (y. x) Ddd E Hd with p (per Pylx) and (unknown) 8. P). We consider learning using two-layer neural network with parameters O M(d+2)))+1 and an activation o : R + R:
(a; 2 = c+ M.
Σ +b) JEIM]
c, C,a, ER, wy E RR, for j E (M) (NN1)
For convenience, we will reparametrize the neural network for θ (00))E(M) R M(4+3) with 0, = (aj, wj. bj) Rd43 and
(N +
1 M
Σ o.(2;; O,):
(x; afo((W;, + bj) + cj.
(NN2)
JE[M]
Indeed, the two neural networks (NNI) and (NN2) remain equal throughout training under the initialization C1 =M
Also, recall the definitions of the risk and the excess risk. respectively, for data distribution (y. 2) ~ D, with respect to a loss function R x y + R>o.
R()) Ep [(((()) and R( R()) inf R()).
(68)
sa(+1)d-a
We start with the initialization specified by Po
(a..6 Vd. w. (o0)))) Ha 2 pb X p & dc=n Po.
(69)
23

---

Batch Stochastic Gradient Descent. We train the parameters O using batch-SGD with loss and the batch size b. Even in more generality than stated (e-bSGD), we allow for time-varying step size (7) ):20 where 7h E TRd43 can be different for different parameters (e.g., different layers), and eg-regularization Rd-3, We initialize the weights [ ltd Po from (69), and at each step. given samples ((( Mai) : [b]))20 the weights are updated using
(fNN yts) H V 03) H HsAd,,
(e-bSGD-g)
MEM
where we introduced H == diag(m:) and A == diag(A).
Mcan-Field Dynamics. A rich line work [Chizat and Bach, 2018, Mei et al., 2018, Rotskoff and Handen-Eijndedd 2018, Sirignano and Spiliopoulos, 2020] has established a crisp approximation (e- (-DGGD-g) and continuous dynamics in the space of
between the dynamics of one seee-pass-bac---e probability distributions in R To any distribution p E P(R++3), we associate the infinite-wide neural network
faN p) = ox (2; (dd())
(70)
In partieular, recover the finite-widhe neural network (NN2) by taking ((M) 1.
M EjE(M 60,-
after k-steps of (4-bSGD-g g). In our (L-bSGD-g) dynamics, we allow for a generic step-size schedule that is captured by
Denote bk (M) the empirical distribution of the weights {0) Je
M| MEj
7 = =)(())) for some function : + R2+3
(71)
-0
and that the data at each step are sampled i.i.d. from D; the case of D empirical distribution on training data corresponds to multi-pass batch-SGI, while DD population distribution corresponds online batch-SGD. Under some reasonable assumptions (that we will list below on the activation, step-size schedule ş. initialization Po. and the loss E) on taking M sufficiently large and 1) sufficiently small, setting k t/n, ((M) is well approximated by distribution Pt E P(Rd+3) that evolves according to the PDE:
Oept Vo. (p.H(()oo)((:p..))
1 (00 pt) = ED (f) 0) -
(MF-PDE)
y):
where the initial distribution is Po and we defined (t) diag(E(t)). We will refer to the distribu- tion dynamics (MF-PDE) as the mean-field (MF) dynamics. We now specify the assumptions on hyperparameters under which a non-asymptotic equivalence can be derived.
D.1 (Activation). Our a R + R is three times differentiable with ||o(*) S K, ..... A D.2 (Bounded, Lipschitz step-size schedule). t + E(t) (E:(t))ic(a+a) has bounded Lipschitz entries: ||E/ < K and [|Eilltap S K. D.3 (Initialization). The initial distribution Po E P(Rd+3) is of the form:
(a Vd- w C.) ~ Mo. & pa @ ngd @ 8
where pa Purs Hi are independent of d. We further assume that pa supported on |a| S K. | S K. and pa is symmetric and (.2-sub-Gie Gaussian.
D.4 (Loss). The loss E: IR x y + Rzo is twice-differentaable its first argument for all y E y and satisfies
(e v)1 S K(1 + (ul) and (é"(u, v)1 S K for all y E y.
Assumptions D.1-D.3 are similar to Abbe al. [2022]. Informally, Assumption D.4 states that loss has a quadratic upper bound (which is analogues to the smoothness assumption in the convex optimization literature). Later, to show the learnability of leap one junta settings, we will further require E(-,3) 3) to be convex and analytic. We note that together these assumptions holds for (i) the standard logistic loss for the classification setting when y E (=1]. and (ii) for the squared loss and any of its "analytic perturbations" for the regression setting when )' S I-B., B). In particular, we would like to mention f(u, y) (u - y)archsinh(u - y), for which we have LeappLo, Leapso and these assumptions also hold, and hence our results apply. For classification, by Proposition 6.1, 1, anyway LeapSQ = LeapCSQ LeappLo, for any non-degenerate loss (including the standard logistic loss for which our results hold).
24

---

Limiting Dimension-Free Dynamics. In the junta learning setting, when only depends on P coordinates, following Abbe al. [2022, Secion 3], the SGD dynamics (é-bSGD) concentrates on an effective dimension-free (DF) dynamics as M, d -> co and - 0. This equivalence holds under a certain assumption on the loss function, and other assumptions on the initialization and activation that are similar to the setup of Abbe et al. [2022].
Consider the isotropic parameters H k diag (77 Th Lds Th. nE) and A diag(X", A A², X²). Using technical ideas from Abbe et al. [2022, Secion 3]. the (e-bSGD-g) concentrates on an effective conenssion-free dynamics the limit M, d + oc and 17 - O. This limiting dynamics corresponds to the gradient flow on R(f) 0 AO of the following effective infinite-wied width neural network (recall z E IR" is the support)
[N Pa) Oz:
(=(2;0') e' d'Eooo((z u²) + s B*),
(72)
where G N((0 1) and Pi E P(R is the distribution over 0' , by, u², c', 8)) with u² E eRP.
p.p. Ve (p: (o.(
(0 P.) E (fNN((( Pe) (z: 0)] + 1 0 AO.
(DF-PDE)
2
where (t) diag(5", " <h I 5. 5 (t) and A diag(1", Xb, A X²) from initialization
Po = Pa @ μb @ 0 @ 60z 8 20 my
where m² = Ew ~ // is the second moment of pw= The non asymptotic equivalence is characterized by the following theorem that can be seen as generalization of [Abbe al., 2022, Theorem 5] to non-squared losses.
Theorem D.5. Fix activation, step-size schedule, initialization, and the loss such that Assumptions D.I to D.4 hold and consider any T 2 1 independent of d. Let (pi)120 be the solution of (DF- PDE), and {Ox Jkzo the trajectory of SGD (L-bSGD-g) with initialization {0)) it Pv- Then there exist a constant CK.T > 0 that only depends on K, T, such that for any d, M, 17 >0 with M S ed and 0 < <n S 1/(Ck,r(d log(M))), and
S V d
log(M) M
d Mo
(: ))) - RR(fNN(: S CK.T
+ vTV
V1
(73)
b
for all k T/n, with probability at least 1 - 1/M.
This theorem follows by straightforward modification of the proof of [Abbe et al., 2022, Theorem 16, Proposition 15] using propagation of chaos argument. We note that the only property about the loss that is needed is Assumption D.4.
D.1 DF-PDE alignment with the support.
In this subsection, we provide formal statement of Theorem 7.1 and its proof. The following is an extension of [Abbe et al., 2022, Theorem 7] from square loss to general loss.
Theorem D.6 (Formal statement of Theorem 7.1). Assume that Leapolo, (n) 1. Then there exists U C [P]. |U| 2 2, such that for all t 2 0, the DF dynamics solution remains independent of coordinates (z))ee,, i.e., fNN(2:; support.
[NN((())) (zi)iqus pt), and therefore fails at recovering the
Conversely, if Leapolo, (1) 1 and E is analytic with respect its first argument, then almost surely over 7, there exists t > 0 such that fNN((z;p) depends on all [P].
Proof of Theorem D.6. The proof follows similarly to the proof of [Abbe et al., 2022, Theorem 7]. Assume LeappLo, (μ) > 1. Consider C. C COLQ, the maximal subset such that Leap(C.) 1 and denote U, Urec U. In words, U. contains the subset of coordinates that are reachable by doing leaps of at most 1. By the assumption that LeappLo, (n) 1, we must have [[P] U- 2 2. Let us show that the weights for i [P] U. remain equal to 0 throughout the dynamics.
25

---

For simplicity, we forget about the other parameters which we set to b == c e = 0. For convenience, denote f2 = [P] \ U.. First, we can bound by Gronwall's inequality, for t I C, |a - KC' for all a' on the support of Pr- From the proof of Theorem 5.1, conditioning on already explored coordinates does not change the leap-complexity.
particular,
E[e" (g(zv.)) w)////u))==
Vi E Ω.
Consider the time derivative of uf for i E S2 We have
(fuN((zU, pr), u) (uu, zu.) + (uh, mn)) - l' O:P): w)o =u. ,u.))
1 > / faa [ā'loo 20.) ).. + (ūh= za)) - o ( 20, (d(()
+ (III po) lo zu.) + (uh =n)) o (luti zu.))
S
sup jERRu(ssupp(A))
where we used Assumptions D.1 and D.4. Hence,
d
L'"El"(/NNN( pi), o' z|]=
di
S (fiNN(( O: pr). o) (uu =v.) )).)) K
sup JER.Njauup((a))
lu/]
The first expectation is equal to O. Note that mm == sup Esupp(a)) |uý] has mß = 0 and therefore m² = for all 2
E
Learning Leap One Juntas with SGD: Formalizing Theorem 7.2
In this section, provide our precise layer-wise training algorithm and the proof that it succeeds in learning LeappLo, = 1 junta problems. This section follows the similar training procedure from Abbe et al. [2022] for the layer-wise training but adapted to training with general loss function : RR x y + R> to show Theorem 7.2. The key difference in the training algorithm from Abbe et al. [2022] is the use of coordinate- wise perturbed step-sizes for the first layer weights to break the symmetry between the coordinates. This allows us to learn even some degenerate cases having coordinate symmetries with leap one, in contrast to Abbe et al. [2022].
Discrete Dimension-free Dynamics. We first consider the dimension- dynamics similar to (DF-PDE) but for discrete step-size regime (see [Abbe al., 2022, Appendix C)). We initialize to
(a b0, u. Ce 8) Po P(RR++)
and (px bEE are induced distribution on (a..0 u. d, 5 recursively defined as
+1 = a - (E (
G + +
u k+1 = ~ - nh (B...o(((m(mm)))m)
x"
A+1 gh 1h (uu
(d-DF-PDE)
gh+1 = b² - n (f (|
d+1 d th
E.1
Training Algorithm
Choose a loss : R x y > R>0 and the activation (x) = (1+z)* for L 2 28P We train for O(1)
total steps in two phases and the batch size of (dd) with the following choice of hyperparameters.
* No regularization: set the regularization parameters n = \= = 2 =
26

---

Initialization: Initialize the first layer weights and biases to deterministically 0.
(6f, Vdww)) ne pub @ Pa 66-0 @
d ===-
The second layer weights are sampled uniformly from [-,,1], e.g. aj ~ Ma = Uni 1J). Finally, choose e óc=e for the given global bias choice E For the dimension-free dynamics, this corresponds to taking
(a b, u c. 80 ~ 70 Uni[([-1,1] @ 66=0 @ w 60 dema 8 8y=0-
We deploy a two-phase training procedure. Given parameters and & E [1/2,3/2
1. Phase 1: For all A {0....,k ki - 1), set m/f n oh and nh E IR' such that Th = Tss, for all i E [d]. For the dimension dynamics, train the first layer weights
u for li steps, while keeping other parameters fixed, i.e a² a., b = 0,
2. Phase 2: Set 1/
and mh 0, n The 0 for k E (ki,,..,, ki + l/ 1}. In words, train the second layer weights a for k2 steps, while keeping the first layer weights fixed t uh.
We will take 1) > 0 to be small constant to be specified layer and K, E (1/2,(1 be the random perturbation. We also let I = (2(d), hiding constants in 7, P, u.. For the first phase, suffices to train for k = P time steps. For the second phase, we train for l22 k2 s, P, K. ju) (1) time steps be specified later as we analyze. Note that only unspecified hyperparameter the global bias initialization é and the results holds almost surely over this choice.
Theorem E.1 (Formal statement of Theorem 7.2). Assume i is analytic, convex and that Assumption D.4 holds. Then for any LeappLo, (1) 1 setting, for any Dd Da.s. E Hip almost surely over the initialization E IR, and & E [1/2, 3/2]", the following holds. For any e >> O, with
b 22 (dd), M = -(11, and l22 = S2(),
using D).-) to hide constants e, K, pu T3, K. and e, the above specified layer-wise training dynamics reaches R. (h)t)))) < with probability at least 9/ 9/10.
E.2 Proof of Theorem E.1
The proof of the theorem proceeds by first showing a non-asymptotie approximation guarantee between (d-DF-PDE) and (f-bSGD-g). To this end, we first start by noting a generalization [Abbe al., 2022, Theorem 23] to any loss under satisfying Assumption D.4.
Proposition F.2. Assume that Assumption D.4 the loss holds. Then for any 0 < S K and for any T N, there exists a constant CKK, Y) such that for (L-bSGD-g) and (d-DF-PDE) of the specified layer-wise training dynamics, with probability 1 1/M, we have
(VP+loxe log d
log M
d + log M
inf k=
(R(()))())))( C(K,Y) r)
M
b
The proof of the proposition follows the similar arguments like propagation of chaos used in Theorem D.5. A direct corollary of this proposition is that suffices to focus only on the (d-DF-PDE) to show Theorem E.
Corollary E.3. Assume that Assumption D.4 holds. Then for total T number of (L-bSGD-g) it- erations on a neural network with M 2 Co(K, T,E) and the batch-size b 2 (K, T, d, the aforementioned layer-wise training dynamics, with probability at least 9/10
inf RR[NN(:; )*)) - RR(NNN(:: 2
E
Proof. It is easy to see that it is possible to choose M > Co(K, T,e) and b 2 (K,Y, for sufficiently large constants such that the right hand side equality in Proposition E.2 bounded by e/2 and 1/M I 1/10. The corollary then follows from Proposition E.2.
D
27

---

In light of Corollary E.3, it suffices to simply focus on (d-DF-PDE) and show that it achieves the excess eπror of at most E/2 within total steps Y ( hiding constants in K, p. P.E. E. This will be done by analyzing each phase separately- (i) showing that the training of the top layer weights for steps E (ki....,A k1 + 22 1} in Phase is a linear model trained with a convex loss so succeeds in reaching a vanishing risk as long as the corresponding kernel matrix of the feature map is non-degenerate; (iz) indeed showing that the corresponding kernel matrix of the feature map after k1 P steps of Phase I training on the first layer weights is non-degenerate.
Simplified dynamics. We first make a simple observation that b²th = 0, 0 and c* = ē throughout; this allows us to analyze simpler dynamics. To see this, for (b+, c²)), we use of 1 throughout, and thus, they remain the same from the initialization. We start with s = 0 and using (d-DF-PDE) (assuming s 0). gives us
k+1 = 0 - nk (B..cl((fNNzz
o' - +b) 100) +)"0) = 0.
E.3
Phase 2 (linear training)
We first analyze slightly simpler Phase 2 of training. For convex loss &, the second layer training just corresponds to linear dynamics with kernel ki {+1, 1} x f+1. -1 + R given by
K ki (z,z') = Eawpp (o k1 (a), (()= (a), x))]
(kernel)
We first show some helper lemmas, and using them, show the main lemma. We will then show the proof of the helper lemmas. We start by proving the existence of a sparse function with small excess eтror.
Lemma E.4. For any & > 0, there exists a function fx : {+1)dd + I such that
R(S-) (R(..) inf -
R() $
E
(74)
Moreover, fx()) = hz) for some h. : {+1)" + R indpendent of d, where z is the support of D
Approximation.
The neural network output after training u for 1 steps is given by:
fx.) = -+ ao (o), 2)) (o) = = Eurpo [ao 2))]
Observing that for the next k2 steps, only a is trained while keeping i fixed, the neural network output of the following form
f=) = aolluu, (()((u,)))dpl 2))dp(a. u) c / ao((uu (dd (u).
(75)
now start by showing that our neural network, there exists P. such that exactly represent (z) as long as the resultant (kernel) after 1st layer training is non-degenerate.
Lemma E.5. If Amia ( K 2 c ffor some constant c, then there exists P. P(RP++) such that (a, u) dp(a,, (w) (dpk. (u) and for all E {1
(z) = fNN((z;p)) =c+ E+ / a,,0(lu, z) a.)o(lu,)))
(u).
Moreover, ||a* = d((w)d I C1 for some constant C₁ := ci (Mmin (Amin(K (K*1), hr, c).
Convexity and Smoothness. Finally, we will show that the risk objective terms of p (of the form (75) is convex and smooth in terms of p. The convexity follows from the convexity of E(,, v) and observing that the neural network output in (75) is linear p(a(u)). The smoothness follows from Assumption D.4.
28

---

Lemma E.6. Consider E: R x 3/ 7 Rz0 such that () is convex for every y and that
Assumption D.4 holds. Then
R(p) E(E((NN(zZ) p), y),, where dā(a, u) = dp(a(u))dpp (w).
is convex and H Hssoooth with H K3.
While we denote R(p) as an objective in terms of the joint measure (aa u), it is actually an objective in p(a(u))) since
of the form where d(a, u) dd(a(u))dlk; (u). Also, the convexity and smoothness is in terms of the argument p(a(u)). Having established the convexity and smoothness of the 2nd layer weights training, we will directly apply the convergence rate guarantees for convex and smooth objectives.
Lemma E.7. Consider any convex, differentiable objective f(x) that is H H-smooth. Then for any step-size nj S H. the gradient descent from initialization x² reaches an iterate x² after steps such that for any &' (not necessarily a minimizer), we have
f(x²) f()) 1
81
27p
This a classical convergence rate guarantee for gradient descent on convex smooth objective [Bubeck et al., 2015, Theorem 3.3], but noting that a proof generalizes even when ö is not necessarily a minimizer. We will apply this guarantees with ă as a near minimizer of f. especially when the actual minimizer may not exist (for example with the logistic loss, the infimum is never achieved). We provide the proof with other lemmas for completeness.
Lemma E.8. Assume that Mmi (k**) > > 0 for some constant c, where Kha is the (kernel) matrix. Then discrete dimension-P free dynamics (d-DF-PDE) in Phuse 2 of layer-wise training with step-size 1j S dy as specified before after k2 = (2 8, P, K. p1 6) steps achieves
Ky
R(fNN phan
(((tun(z:phtttt))
inf A(111--B
R())
S e
Proof. First of all, using Lemma E.4, there exists P. such that
R(fNN(z::.)) p.)) = R(fNN(2;P.)) B
inf R()) S 6 4
(76)
Moreover, by Lemma E.6, the objective R(p) is convex and x -smothh and observe that (d-DF-PDE) performing gradient descent with step-size T/f R= on this objective. Thus, using Lemma E.7
I|a
aa 11 p.
TR(fuN(z:puutt))) R(FNN(Z: = (R(phtk)) R(p.)] S
(77)
27pls
Recall that ah M4 Unif([-1,1)).
||aa a" 11 = / (a- for some constant 02 = cz( (e(Nmin(K*))) P. Z). Therefore, choosing k2 2 202
a² a"())) dua (a" (u)) (u) S 11+ +1+2||a"11 11 + +11a" S C2
E (e( - 4'
(78)
Combining (78) and (76)
R(fN (( = (R(hN((z:phittb))) R(FNN p.))
+ [((iN(Z;(p))) f(L1)e-RR
inf
R(F)
Thus, we can show that Amin (K*) 2 e >> O for some constant c(), P, K, (u) for a sufficiently
small constant > 0 that only depends on K, p, then it immediately implies the desired result by Corollary E.3 with Y = kn + 2z. The goal of Appendix E.4 is to show that this holds after k = P steps of the first layer weight training. We now return to the deferred proofs of helper lemmas.
29

---

E.3.1 Proof of helper lemmas
Proof of Lemma E.4. Note that Eq. (74) simply follows from the definition of infimum and the excess risk functional R()). To show that (x) = (=), we make an observation that for any function f: {=1]² + R. one can define he [=1] " + R that only depend on the support and achieve risk no worse than f.. Define h. (z) = E [f= (z)),, where z" x: \ (the coordinates outside the support). In other words, h. is the boolean function after ignoring the monominals that do not depend on z. Then
R(f+) BD [e(f. v)] E P ((f 3)]] 2 Ep,, [C(E [+ (a:) v)] = ((((h, R(h), where the only inequality follows from Jensen's 's inequality and convexity of E(.
Proof of Lemma E.5. Define (z) = (z) č. Our goal is to show the existence of p. such that 9o(=)= = E(a,, u>>p, (a. ((u, z)]].
Consider the following objective least square objective for the domain
[(a(u);))= Σ (Bunpe (u) (a)(a ( (u, 2))] - g. (z)) 2 + X f a² (u)dōs, (u)
*E(=1}-
While this an infinite dimensional problem, the Representer's 's theorem holds and the interpolating solution exists. We refer the reader to [Celentano et al., 2021] for a detailed analysis of interpolation with the random feature model. Moreover,
||a|||a Aminn (K
Σ =E{+1)
(z(2)² S 01
for some constant C1 that only depends on Amiu (K k1), her Pand ट.
Proof of Lemma E.6. For E [0, 1] and any p(") and p(2), consider the density p = (1-))((11)pp)
Then
R(p) -R((p!") + t) Ele(fiN(z; tp( (1 - -))p())).)))
= =B((((in((;; (1 (),( 222) w)1
S EELLeSuNNZZ; ),))) + (1 - [-]))[[NN(( (() v)
(using convexity)
(z) LE [ w) + (1 D)E ((fi )()) = ((((1)) + (1 (p!))
To show smoothness, first observe that direct consequence of Assumption D.4 (the condition le" (u.v) < K) is that for any 12 E I,, we have
K e(u1 v) I Elu2, u) + (22zz)) -u2) + - (u2 =2)
(79)
2
Using this, for any r(4) and 5(2)
R( = E[P(JNN(( iz; )()), v)]
< B[e(Sin((Z (())), v)1 + E ( (()N((z; v) (fNu(z;
- fNN(2;; (using (79))
(z; (())) )
(Iun(Z: - INN(2: p(11) 27
+ -
(80)
Since fuN(2Z 22; (1) - fuN(2: = Eamy a [(a(1) - -a2))) x})], further simplifying the
above
E e' (fNN(( v) (fNN(Z; ((1) SNN(2Z; ((){;;??))]
Bly ((NNN(Z: (1))), v) Bac)) ,, [(a(1) (2)) -a ((u, 2
-Bali,at0), B(y e' (fNN(2 (())), ((), | (0 a
-(VoR(o(1), (1) (2))
(81)
30

---

Also, simplifying the third term of (80)
K
(Juu(Z;P()) - (z; p( 2
K
B [(al]) ( ((e, 2)) ]))
R
B (y
K
[1a))
(v, B 2111,
(by Jensen's ineqaulity)
2
K
$ =1aa0) (2)) 10
(82)
Finally, combining (81) and (82) with (80), obtain
K3
R( = R( (V a al2)
1|aaa - 1|2 pp0
+
pm)
2
which, by definition, gives us H-smoothness with H k
Proof of Lemma E.7. First, the classical descent lemma holds due H -msooohhssss for step-size
7) S H
f(x+t)) S f(x)) + (Vf(x"), ,,, - x²) + H || x = f(x0) - n (1 T \f)(T>> & f(x²) 2 [( S f(x²).
2
(83)
By convexity, for any ž (not necessarily minimizer), also have
S {
+ (V (V[ 8).
Substituting this in (83)
)(x)+1) S f()) (Vf(x'), N 8) 7 "
f(ā) 2n
(2m ((x x. 8) 7² / (x (13)
[()) + 2n
(2n (V/(()))))))))))))))))((())) x 8) /// 112 - || - -5112 + || =113)
= f()) + 2n
(1|0 = - -|-0-1 2213)
Therefore, summing over j fO...., 1}, since the right hand side is a telescopic sum
1 (1120 =112 11
Σ ( < 2n 0=0
2m
Note that the lemma statements trivially holds if f(**) - f()) < 0 already. Therefore, in the case when (a* > f(ā) and using the descent lemma, we finally conclude the proof.
k f(x²) - ff() = Σ (f(x)) (()))-(()}) s ||00 - =512
2nk
1=
E.4 Phase 1 (non-linear training)
We now analyze Phase of the algorithm and show that Amin (k 2 c, for a constant e cnn, μ. P. K) where 7 is also small constant (in terms of μ, K).
31

---

Writing the weight evolution with polynomial. We will by considering general polynomial activation (xx) -i of degree L. whose coefficients are given by (mo. ..... mL). Lemma E.9. (Training dynamics given by a polynomial) Let É - (Es, (ES E R²² k, < E R, p RL+1 E IR. be variables. For each E [P]. define (s, P. = O. For each, 0 S k S 11-1,
PE+I,.(....P.7))) PR,ISS.E,P.). p.?)) CRPIE(S)
+ t%B
Pr+1
Σ
II Pa. (S:
r!
Then there is constant c == c(ki, P. K) such that for any < <c
ui (a) Ph.,(na, m, m, K)),
and 3 = (8sw)sc(M,,SASh) is given by 35.u = -B]6" (fNN() Ps). v)xs(=)].
The term fNN(:: Pk) evolves non-linearly, and difficult to analyze directly. However, for sufficiently small step size 17, the interaction term fNN(:: px) small, and we show that it can be ignored. ki by letting ú (a) = 0 and
Formally, we define the simplified dynamics ú (a) for each inductively setting for each k E (O...., kn 1}.
a (a) = â (a) 1/ o E[C' (fNN(z: po), 9) a d' d'((a(a)) x))))
Using a similar argument, we may show:
Lemma E.10 (Simplified training dynamics are given by polynomial), There is constant O depending only on ki, P, K, such that for any < < G, any [P) and any 0 S & S k1, we have
(a) pa,i(na, ar m, K),,
where we abuse notation (since a = (as) otherwise) and let a = (ass))sgip)o0sss be given by
0sS = as = - (f)n vxxs(2)
Reducing analyzing simplified dynamies We lower-bound Amin (K in terms of the de- terminant of certain random matrix. Let Ç [SI...., .....,,e. S22l be vector of 2" variables. Define
M M(C.E. E R² x2 be the matrix indexed by E [+1,-1} and [2') with
entries
P
Me. Σ Pr
Eapr.(Ch
This matrix is motivated by the following fact:
Lemma E.11. There is constant >> 0 depending only on k1, P, K, such that for any 0 < and any [ai...., [2p] E 1|2 have
M (na, B, m, x) o((u" (a,). 2))
Mz.j (na, a. m, k.) = o((ū (a,), x))
Under this notation, using the exactly same analysis as in [Abbe et al., 2022, Lemma E.9], we can also show
Lemma E.12. There is a constant
0 depending on K, P such that for any < rj < <
Amin (K*))
2 cE ar
92p [det M (na, B, m, k])
On the other hand, we can prove lower-bound bound on Ejdet(M B. m, k)) simply by lower- bounding the sum of magnitudes of coefficients det (C, ar, m, x)) when viewed as polynomial in Ç almost surely over the choice of ć. This is because of (a) the fact that del(M((C ar, m, x)) and det det(M (M, 3, m, x)) have coefficients that are O(7) -close for small, and (b) the fact that polynomials anti-concentrate over random inputs.
32

---

Analysis of simplified dynamics. The proof is now reduced to showing that det(M(( a, m, x)) # O, as polynomial in Ç. In other words. by Lemma E.11, we are now focusing on only the simplified dynamics a². If we can show that det( a, m, x))) # 0 almost surely over the choice of k E [1/2, 3/2|P, then Theorem E.1 follows. Therefore, introducing the variables 7 E IR suffices to show that
det( (c, ax m, 7)) # O, as a polynomial in Y,
(84)
We start by following simple observation.
Claim 1. Almost surely over the choice of initialization C, the set of subsets K= {S as + 0} has Leap((C) 1.
Proof. This basically follows from the fact that és piecewise analytic. The argument is as follows: have that LeapbLo, = Leap(CDLQ.) = 1, where CDLQ. = {S Bu E IR such that [E[ x))) * 0}. Since É is piece-wise analytic, so is (1, in the first argument. Thus, for any S E CDLQ, the set {u: (u, [=)] 0} has measure 0. Thus, almost surely over the choice of ē fNN(2: we have that for any CDLQ,
Bie v)xs(=)]
9))ss)) -as 0.
This implies that S E K. as well. We finally conclude that LeappLo, = Leap(XC) = 1.
Using ideas similar Abbe et al. [2022], we now prove (84) by analyzing the recurrence relations for Pk.i to show that to first-order the polynomials . are distinct for all i E (P). but now doing smooth analysis over y instead. Formally we show the following lemma.
Lemma E.13. Suppose that L 2 28P and let m4 = =i!()) for all 0 Sis S L, which correspond to the activation function a (x) (1 + x² Let h = P. Then det ( m, 7)) # 0, i.e (84) holds.
Claim 2. For any time step 0 S l S 11 any j E [N]. a learning rate n < 21 + Kk),,, and
any E [-1,1] we have
| (a)),, (("""(())) (a)ll < 2n/ (1+ < 1/2.
Proof. We prove this by induction on k. For is 0, we have u û² 0 and the claim holds trivially. For the inductive step, fNN(2:: px) I Euwpa ||l||al (o""", 2))l[ I || I K, since a am Unif([-1,1)) Therefore
++ (a) 11 (a)li m/|xs
Pa), y) (a ((ul 2))==]
< (a)]l) + m/|ls loc Ey. III - E' (fv pa), y) ag ((u* =|1
< || (a)]l: + kn (1 + K)- K |=1||=111| - 2 (a) + k (1 + K)P < Kn + K)Pk.
Note that here we used ||<||| oe < 2, (fNN (z; Px). 4) - K +1++100 [2; - K(1 + K) using
A2, and aa''((" x)) < |a]- lo'((u 2))l < K. The bound for | (a)ll follows exactly the same argument but now we use 1 (fNN Po). v)1 < K.
Proof of Lemmas E.9 and E. We have Ç E R. E = ((Ss:)s((I),,E(....... 7 RRP as variables. Let 80. : [+1,-1] - R be 8x 82(2) Esc(p) {s,xXs(2). Consider the recurrence relation 3 R.. where we initialize d 0 and, for 0 < k ky 1
p E R--1 and
++1 + Eg (x(2)
Pr+1 (v* 2))²²
(85)
r!
r=0
33

---

This recurrence is satisfied by Ç = rja, m. and sx(2) Es (s,)X)(z). This is because
ạ #+1 u² 21 Elle (JNN pk y)u
(aooo(((a ((u* 2))=]
u D1a o E| 8' (fNNN y) Σ mr+1 (u* 2)
u² -1
(k), 1)0 (1u 2))2
u² na. E
mr++1 {u", 22)
t + naa . Ez - (f
mr+1 (u 2)"²)
r!
Finally, noting that E (x; = Es Ss, we showed that recurrence (85) holds with specified value of variables. Similarly, (a) with s4(2) Es osxs(z) for as
-Rie' Pol v))) This is because (iu", =)1. (āa =)1 S 1/2 < 1 by Claim and in the interval (-,, we have (1x) = Et "n It finally remains to show that
p,7).
The proof is by induction on k. For le 0, it is true that (o. = 1f.. For the inductive step, for any r 2 1 and E [d]. we can write
(x(2)
Σ
II
(E..))))
1=1
Σ
Eg (z()xx((z)
II Xu (z)
II Paal
= =%
(E(P)))))(PP)
Σ
II
Pa.a Pa (C.E.
(PP))
E=1
and y, (s)())(()))) 2] = (s = 7E(()). The inductive step follows by linearity of expectation.
E.5 Proof of Lemma E.13
In Lemma 13, we have already fixed m E RR++ to be m; = a()) for all E {o...., L}. This corresponds to the activation function (zx) = (1 + 2)
E.5.1 Reducing to minimal Leap structure
To show that det(M a, m, Y)) * 0 as polynomial Ç. Y, we first show that it suffices to consider "minimal" Leap set structure, without loss of generality.
Claim 3. Let K' C such that Leap(K') Then if
(,, at O, polynomial of S.
we have
a,, 7)) # polynomial of C.
Proof. Directly substituting ag 0 for all IC AVK. K".
Therefore, without loss of generality (up relabelling the indices of the variables), we assume that = (S....., Sp), where, for all i [P) , i E S; and S; [i].
Otherwise, could remove set from IC while still having Leap(XC) 1.
34

---

E.5.2 Weights to leading order
Let define the polynomials ya,i in variables S, P, where &f = (Øs)SEK. For all A ko - and i [P],
qe,(S, p, P. Y) PL.((.E.P.7) Es.u=0 for all Sgk and Ea, for all SEK:
Therefore (C, p. has entries Mz. p. =
(Een qu,lSs &, p. 7)) We
will explicitly compute the lowest degree term Ç. First, we show that many terms are zero. To this end, consider the following notation: Recursively define
0, =1+
Σ for alll [P],
PES.
where the sum over an empty ist 0 by convention. Additionally, let [ p. Y) to be the coefficient of the term Ue, (C, Φ, p: 7) whose degree is o,, Furthermore, recursively define
9 (7) = 74 if {i} KC, and otherwise gi(7)) 7/8
II (EESA()
(r))
Lemma E.14. Under the above notation, we have that quslC, &, m, has no nonzero terms of degree less than in Ç. Furthermore, (d. p. Y) can be decomposed as qR,(Ø, p, p, ge(r) ( p) for some (x.(dd.))) p).
Proof. We will prove this by induction on k. The base case for Ie = 0 trivially holds because qu. = 0. For the inductive step, assume the statement holds for all k' E {O....,k) and we prove the statement for k: + 1. By the recurrence relation of the polynomials Tk,i, we have
1ct1,s P. = (k,i(S, Φ. y) + 7CPI0()) ((1) E.)
1-1
Pr+1
Σ
e ((i) @ (() qu. (s.
[E(P)
1=1
It suffices to show that the claim holds for each one of the three terms above.
1. The first term, (C, Φ. p, 7), is handled by the inductive hypothesis. We can conclude that all the terms of degree less than o, in Ç are zero. Morcover, 9k. (p))...)
2. The second term is nonzero only in the case that {i} Ic, in which case S, {i} K and 0, = 1, so we do not have a contradiction since the Ço: = Ç only and we do not have terms with degree less than oN. Moreover, the coefficient of is 1PP1(()) (()))110())-
3. We break into cases. Case a. {i) @ (i. @ [i. = S. then S; {i} C
4.
so - Σi=1 Oi 2 O,, and no new terms of degree less than o; are added. Moreover, the only way the third term has degree o, in Ç is when + i + # in while still having
{č, 01. ......... } S₁; otherwise the power of is 1 + Ei= on oi. In that case, letting
7' = S. - 1. the coefficient of Ços in the third term is
Pr+1 Øs.
II PeE)
T (0.
Σ
L(fi, iffi, (......,,)+ - Si)
rd
(6 JE(P
Pr'+1 rr
Øs.
II NESA()
go gr
Σ
I(fi, - =Si)
((PP)))))((P
=% ((E))
(>)
Pr'+1 rr
Us
II (p.((.)))
Σ
1((, b S:)
VESM)
(
= @(p 7) for certain q.
35

---

Case b. If {i) (6. Sy for some i' * i, then either i E fdi...., which case 1+ Ei= 0, oz. Otherwise. we must have since i Sy, so also have Σi= oi, o2 and again no new terms of degree less than os are added. In fact, only terms of degree strictly more than og are added. Thus, in either case simply O.
1, in But in this case ov o,
the coefficient the term with degree o,
Finally, we showed that each the three terms have at least the degree o Ç. Moreover, each term can be decomposed as 9: (()))(( Y) for certain q. Thus, overall we can decompose
( P. x) (:())) ( p), concluding the proof of the lemma.
Claim 4. Let
rz(S, p.7)) Σ 2.t p,7).
Then, for each distinct pair z,z' E ++1.-13", we have rx (x(S. m)) Txx Φ m) polynomial in Ç and
as
Proof. Recall the definition of o; from Lemma E. Fix E [P] be such that 2 + z and o, is minimized. It is always possible to choose such an i since 2 + z'. Again Fz(Ø, p; Y) is the term with degree o in Ç. Using Lemma E.14 then
fz(0 p.7) (0 (,)))))
Σ
(zy -x=-2))00 T ( p. y);
S.L. or oy
but . are non-zero polynomials in y with different dependence that is captured by ge (7) according to Lemma E. Thus, (2 Φ m) - - (S, Φ, m) * O.
E.5.3 Linear Independence of Powers of Polynomials
Similar to Abbe al. [2022], we finish our proof using the classical result of Newman and Slater [1979] about the linear independence large powers of polynomials.
Proposition E.15 (Remark 5.2 in Newman and Slater (1979]). Let Rq,..., Rm E C(C] be non- constant polynomials such that for all i' [m]] we have R2(C) is not constant multiple of (C) Then L 2 8m2 we have that (R1) ...., (Rm)² E C(c) are C-linearly independent.
We will finally show that det (C, m, 7)) # 0.
Proof of Lemma E. Let us fix K. E R. such that for all + z', we have T=(C, Or, m, k)
Tg (S, (S, ax m, x) * ( as polynomials in Ç. This can be ensured by drawing since for all z of z' we have haver m, -r a, m, m, & 0 as polynomials in (, by Claim 4. We now rewrite FC( rC( a, m, k) further indicate that the variables & at p m and k are instantiated, and that we are looking at a polynomial over Ç. We have also chosen (?)) for all LJ.
Unif( 1.5) P).
LJ. We then have
Mr a, m, k.) = (1 F1+
Also, observe from the recurrence relations Ç divides (S, at m, x) for each i E [P], so Çy divides Fx (C;) Σ 244k,, (SG at, k).. Therefore, polynomials (1 (x))) and (1 + iz (C,)) are not constant multiples of each other for any z z'.
Now see Ç variables, and construct the Wronskian matrix over the L-th power polynomials {(1 + (z(()) 2x((4--11)- ( This is 2" 2n matrix H({) whose entries are indexed by and
I E [2P] and defined by:
g/-1 Hz,(()= ac- (1 4
36

---

Applying Proposition E.15 implies the polynomials {(1 + ==(())))=<(+4)- 1)) are linearly- independent, and so the Wronskian determinant is nonzero as a polynomial in
(ct(H(())) #0.
Also, observe that we can write det (((())
0 8²
oc I det(M a, m, k)) ==
0²n
85a 8Cg
This finally gives us (S at m. k)) (et(M m.
#
0 as a polynomial in S. and thus,
m, 7)) * 0 as polynomial in Ç and 7.
37

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, it does.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We do specify the limitations of our work.
38

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, 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 to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency 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 fairnsss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Yes, we do provide all the assumptions and correct proofs.
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 to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We do provide the code and the experiments are fully reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
39

---

If the paper includes experiments, a No answer to this question will not be 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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 to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.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 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We attach the code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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: / /nips. wttpccccccgppuppiceccce geess////e/e//eee//eee/eeesss Cooeeubmii sssssssssssssooo Ponooicc 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).
40

---

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: [Yes]
Justification:
We specify our training algorithm and related details.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We do report the error bars whenever necessary.
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, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error 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 figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
show in tables
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments relatively small scale and can be reproduced under hr of compute on a standard computer with 16 GB RAM.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
41

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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 Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h http://eeerppppeeeeee cc Spppulic/EthisSuiiiii
Answer: [Yes]
Justification: It does.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in 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: This is theoretical work with societal impact.
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.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: This paper does not have models or data with safety concerns.
Guidelines:
The answer NA means that the paper poses such risks.
42

---

Released models that have 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 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: The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset 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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is 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: The paper does not release new asset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model 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. Crowdsourcing 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 does not require crowd sourcing research with human subject.
43

---

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 the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, 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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our study does not require IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to 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 the institution conducting the review.
44


Reviews:
[{"review_id": "RIrbVr6M8K", "reviewer": "Reviewer_zev8", "summary": "This paper studies the complexity of learning sparse functions (i.e., juntas) using statistical and gradient queries. For that, it introduces Differentiable Learning Queries (DLQ) that can be seen as a generalization of correlation statistical queries beyond square loss. \n\nWith the notion, the paper gives a characterization of the query complexity for learning the support of a sparse function over generic product distributions. The characterization is in terms of leap exponent introduced from Abbe et al earlier. \n\nFinally, the paper also introduces cover exponent that characterizes non-adaptive query complexity.", "questions": "Any upper bound results or conjectures on how to match the lower bound in section 5?", "limitations": "The paper lists several limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a well-motivated question of query complexity of learning juntas, a long established question in ML theory. The paper builds upon the prior work of Abbe et al and provides a generalization beyond CSQ and square loss function. I find the results strong at a technical level. To my knowledge, the main theorems are novel. \n\nThe work proves general relations between SQ, CSQ and DLQ.\n\nThe paper also provides experimental validation of the theoretical results, though it's somewhat limited.\n\nThe paper is well written.", "weaknesses": "Figure 1 is an experimental study. I believe it'd be nice to expand this into a small section that extends beyond learning y_2 (2) and using the 2 loss functions here. I also can't find more details: what is the architecture of this two-layer net? \n\nAbbe et al [2023] has some nicer numerical results. I'd recommend check it out.\n\nCompared with Abbe et al 2023, the paper only tackles the case when the target function is junta. It doesn't extend much beyond sparse functions. \n\nMinor comments follow:\n* Line 18: remove “that is”\n* Line 24: it should be clarified that Abbe et al. [2022, 2023] studies learning juntas using neural networks via SGD", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation and their valuable feedback! Below we address the weaknesses and questions.\n\n**Simulations:** \n\nFollowing the reviewer’s suggestion, we will include additional figures (beyond just the function $y_2$) in a separate section, as well as details on the architecture and algorithm used in the simulations. We will further improve their presentations to make them more striking. In all simulations, we use the two-layer neural network stated in Eq $(15)$, with a sigmoid activation function. We set the biases to 0 and train simultaneously $a_j$ and $w_j$ with vanilla one-pass SGD and stepsize $\\propto 1/d$.\n \n----\n**Only tackling sparse functions:** In this paper, we focus on the setting of learning sparse functions (juntas). Note that learning juntas is a popular model in learning theory, and has been the testbed for many investigations on the power of different classes of algorithms. For example, learning sparse functions on the hypercube has been studied in the context of $\\mathsf{SQ}$ [Kearns 1998], differentiable learning [Abbe et al. 2021b], and SGD on regular neural networks [Abbe et al. 2022, 2023, Telgarsky 2022, Margalit 2023].\n\n[Abbe et al, 2023] considers both uniform on the hypercube and isotropic Gaussian data, which are associated to two symmetry groups: the permutation group and orthogonal group respectively. In this paper, we focus on the permutation group. However, compared to [Abbe et al, 2023], which only considers the hypercube and adaptive $\\mathsf{CSQ}$, we vastly generalize their results by allowing: 1) general product measurable spaces, 2) general $\\mathcal{Q}$-restricted $\\mathsf{SQ}$ algorithms, including $\\mathsf{SQ}$ and $\\mathsf{DLQ}_{\\ell}$, 3) both adaptive and nonadaptive algorithms.  We show that in this general setting, the complexity of $\\mathsf{SQ}$ algorithms is tightly captured by a leap and cover complexities. This demonstrates the generality of the leap complexity first introduced in [Abbe et al 2022, 2023]: it is induced by the permutation group structure rather than any other properties of the hypercube, and extends beyond $\\mathsf{CSQ}$ to any $\\mathcal{Q}$-restricted $\\mathsf{SQ}$ algorithms by changing which subsets of coordinates can be detected.\n\nWe further emphasize that key takeaways from our paper are fully independent of [Abbe et al. 2022, 2023, Damian et al 2023, 2024]: (1) The introduction of $\\mathcal{Q}$-restricted $\\mathsf{SQ}$ algorithms, in particular $\\mathsf{DLQ}$ that generalizes $\\mathsf{CSQ}$ algorithms, which are novel to the best of our knowledge. (2) Functions with high $\\mathsf{CSQ}$ Leap [Abbe et al 2023] can still be learned at much lower complexity by simply changing the loss function, with a tight characterization for a given loss function and target distribution using $\\mathsf{DLQ}_\\ell$, as well as in the mean-field regime for SGD on two-layer neural networks.\n\n\nThe other setting that was considered in the literature is the case of isotropic Gaussian data: isoLeap with multi-index functions and $\\mathsf{CSQ}$ [Abbe et al, 2023], information exponent for single index and $\\mathsf{CSQ}$ [Damian et al, 2023], and generative exponent for single index and $\\mathsf{SQ}$ [Damian et al, 2024]. We believe that our results can be extended to this setting (and more general symmetry groups), and we are planning to report on these extensions in future work. See also the discussion in Section 8.\n\nFinally, note that our results apply to isotropic Gaussian data where the multi-index function is coordinate aligned (e.g. when the coordinate system is known in advance).\n\n---\n**Questions:**\n\nTheorem 5.1 shows algorithms that match the lower bounds for $\\mathsf{SQ}, \\mathsf{CSQ}$, and $\\mathsf{DLQ}_\\ell$. The algorithm is straightforward: in the definition of the detectable subgroups, the condition $(13)$ corresponds to one query evaluation. Then these queries can be combined following the leap and cover complexities. See also Remark 5.2 and the proof of the upper bound in Appendix B.4 which shows how to trade-off tolerance and number of queries (resulting in an extra $\\log(d)$ factor). Further note that these upper bounds require the knowledge of the link function. However, this can be relaxed following a procedure similar to [Damian et al 2024b] (see Remark 5.3).", "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": "BZZYGQYIM5", "reviewer": "Reviewer_atP9", "summary": "This submission studies the computational complexity of learning low-dimensional functions (juntas) and examines a new type of statistical query termed DLQ, which captures the difficulty of learning using gradient-based queries. The authors identify quantities that dictate the computational lower- and upper-bounds based on the properties of the link function and show that the DLQ complexity may match either SQ or CSQ depending on the loss function. This generalizes the earlier leap exponent in (Abbe et al. 2023), which is specific to CSQ models. Finally, in a simplified hypercube setting, the authors show that a mean-field neural network can learn functions with DLQ-leap exponent 1 using $n=O(d)$ samples, which matches the DLQ complexity.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This submission makes a number of contributions to the learning of low-dimensional functions on product distributions:\n\n* The proposed DLQ \"interpolates\" between SQ and CSQ depending on the structure of the loss function. This provides insights into the class of low-dimensional functions that can be learned by gradient descent algorithms.\n\n* The authors also distinguish between adaptive and non-adaptive queries, providing a separation between algorithms with one gradient step versus consecutive steps.\n\n* The mean-field analysis extends (Abbe et al. 2022) to different loss functions and confirms that gradient descent training of a two-layer neural network learns juntas with DLQ leap exponent 1.", "weaknesses": "I have the following concerns/questions:\n\n1. The class of functions with the prescribed DLQ leap exponent is rather opaque, even in the simple hypercube setting. For Gaussian single-index models, the SQ-leap exponent is completely characterized in (Damian et al. 2024), and it is known that all polynomial links have SQ exponent 1 or 2. But in the current submission, it is not clear what functions have DLQ leap exponent 1. The authors provided one example in Proposition 6.2(c) for one specific loss and link function, but there is no general principle that determines the DLQ hardness.  \nIntuitively, if the output is discrete, then the detectable set for SQ versus CSQ may not differ too much, so it is not easy to see that the SQ/DLQ-learnable function class is significantly larger on hypercube input. Can the authors clarify?\n\n2. The current submission does not take the rotational symmetry into account, and the query dependence in the lower bound is polynomial as opposed to logarithmic in the Gaussian case (Damian et al. 2022). For algorithms that are not axis-aware, such as SGD from rotationally invariant initialization, do we expect a lower bound that is stronger in terms of query dependence?\n\n3. Assumption 2.1 needs more explanation beyond \"*it always holds when $\\mathcal{X}$ is discrete*\". Can the authors comment on how to translate this assumption to a condition on the link function when the input is continuous, such as Gaussian? \n\n4. How do the authors relate the number of queries in the SQ lower bound to the sample size in the mean-field analysis?\n\n---\nThe authors’ response addressed most of my concerns. I have updated my evaluation accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation and their valuable feedback! Below we address the weaknesses/questions in order:\n\n---\n**Intuition behind easily learnable functions:** The simple characterization for the generative exponent in [Damian et al. 2024] is due to the setting they consider: 1) Gaussian data, 2) single-index model, 3) SQ algorithms. This allows them to define their generative exponent in terms of (one-dimensional) hermite coefficients of the Radon-Nikodym derivative. \nIn our case, we have 1) generic product spaces, 2) multi-index functions, 3) $\\mathcal{Q}$-restricted $\\mathsf{SQ}$ algorithms. The generality of our setting doesn’t allow for such a simple characterization. We further believe that despite the generality of our results, the characterization remains surprisingly simple: the $\\mathcal{Q}$ class of queries defined a system of detectable subsets, while the leap and cover complexities describe how to combine these subsets to achieve the optimal query complexity (similarly to [Abbe et al. 2023] for $\\mathsf{CSQ}$ leap on the hypercube).\n\nIn the case of $\\mathsf{SQ}$, $T(y)$ in $(13)$ can be replaced by the Radon-Nikodym derivative (see Proposition A.1) and an equivalent characterization can be obtained by looking at its decomposition in the tensor product basis (analogous to the Hermite polynomials in [Damian et al. 2024]). However, for general $\\mathcal{Q}$-restricted $\\mathsf{SQ}$, no such simplification exists.  Because of this generality, no simple principle allows us to characterize the $\\mathsf{DLQ}$ exponent besides Definitions 1 and 2. Hence, Theorem 5.1 should be thought of as a meta-theorem where one has to characterize detectable sets for each given setting (see below for illustrations and response to reviewer Grg1). But we again emphasize that this abstract characterization captures precisely the complexity of $\\mathcal{Q}$-restricted algorithms for learning juntas.\n\nAs for the question on $\\mathsf{SQ}$ vs $\\mathsf{CSQ}$ for detectable sets being not too different on the hypercube data: unfortunately, this intuition is not correct. In particular, on the hypercube data, even with discrete outputs, there are functions with $ Leap_{\\mathsf{SQ}}=1$ but $Leap_{\\mathsf{CSQ}}=P-1$, where $P$ is the support size, i.e. we can get arbitrarily large separations between these complexities even on the hypercube data. See for example the proof of Proposition 6.2.(c) for such an instance.\n\nFor $\\mathsf{DLQ}$, we show an example that is strictly between $\\mathsf{SQ}$ and $\\mathsf{CSQ}$, when the loss function is a polynomial. However, for non-polynomial loss, we expect in general that $\\mathsf{SQ}=\\mathsf{DLQ}$ (see Proposition 6.2).\n\nLet us add that for the example in Proposition 6.2.(c) proof, our results in Section 7 show that it can be learned in linear scaling by SGD with $\\ell_1$ loss (or a smoothed version to satisfy our technical conditions) on a two-layer neural network, while we expect online SGD on the squared loss to require $d^{P-2}$ iterations. See response to Reviewer zev8.\n\n-----\n**Rotational symmetries and clarification $(q,\\tau)$ relationship:** Note that in [Damian et al. 2024], they can show an analogous lower bound $q/\\tau^2 \\geq d^{k/2}$, where $k$ is the generative exponent. They further show that if $\\tau^2 > d^{-k/2}$, an exponential number of queries is required. However, one should be careful in interpreting lower bounds for SQ algorithms: for example, such an exponential lower bound exists for $\\mathsf{CSQ}$ (i.e., with adversarial noise), while [Damian et al. 2023] presents an algorithm with a polynomial number of queries and $\\tau = \\Theta(1)$ with statistical noise (batch size $1$ online SGD).\nInterestingly, their second lower bound for low-degree polynomials shows that there is an information-to-computational gap in their model: $\\Theta (d)$ samples is optimal information-theoretically, while $\\Omega (d^{k/2})$ samples are necessary for a low-degree polynomial algorithm to succeeds. Such an information-to-computation gap does not appear in the axis-aligned case (permutation symmetry), even when considering Gaussian data (both are $\\Theta (\\log(d))$).\n\nIf we consider a rotational equivariant algorithm to learn a sparse function on the hypercube, the issue is subtle. [Margalit 2023] (and generalizations of their results) show that the information-theoretic threshold becomes $\\Theta(d)$ (instead of $\\Theta (\\log (d))$). However, we believe that an information-to-computation gap does not appear: one can use the input $\\boldsymbol{x}$ to first learn the axis (which requires $O(d)$ samples) and then fit a sparse function on these coordinates (which requires $O(\\log d)$ samples). \nAn open problem would be to show that a regular equivariant algorithm, such as SGD on a two-layer neural network, cannot emulate this axis-alignment first stage and would inherit the information-to-computation gap from Gaussian data.\n\n-----\n**Clarification on Assumption 2.1:** Indeed this assumption requires a longer discussion which we will include in the revised version. In short, Assumption 2.1 is necessary for our results to hold in the case of continuous functions, as argued in [Vempala, Wilmes, 2019]: with a finite and noiseless class of functions $\\mathcal{H}$, it turns out that $\\log |\\mathcal{H}|$ queries are sufficient with $\\tau^2 = \\Theta (1)$ under a weak “non-degeneracy” assumption. Hence, enough noise in the link function is required to prevent these algorithms (that require highly non-regular measurable functions). Intuitively, Assumption 2.1 is a quantitative measure for “enough noise in the concepts”. E.g., it is easy to check that Assumption 2.1 will always be satisfied for the link of the form $y=f_*(\\boldsymbol{z})+\\varepsilon$, for any bounded $f_*$ and $\\varepsilon \\sim \\mathsf{N}(0,\\sigma^2)$ as soon as $\\sigma>0$, for arbitrary product measure on $\\mathcal{X}^d$.\n\nWe continue in common rebuttal space for the last point.", "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": "h1zSzYS4gf", "reviewer": "Reviewer_Grg1", "summary": "This paper studies the problem of learning juntas from the perspective of restricted statistical query algorithms. Concretely, for some d-dimensional product distribution \\mu_x^d and some conditional distribution \\mu_{y|z}, the learner is given access (via samples or, in this paper, certain queries) to the distribution of (y,x) where x ~ \\mu_x^d and y|x has distribution \\mu_{y|z} where z is some tuple of P unknown coordinates of x. That set of coordinates that influence y is called the support of the distribution, and the goal is to learn the support.\n\nA Q-restricted statistical query algorithm is one that only makes queries to E[phi(y,x)] for functions phi in Q. Examples include SQ and CSQ; this paper introduces, for any fixed loss function \\ell, another class DLQ_\\ell, where the allowable queries are gradients of \\ell(f(x,w),y) (w.r.t. w) for arbitrary functions f.\n\nThe main result of this paper is a characterization for any {SQ, CSQ, DLQ} of the query complexity of the support learning problem, when P, \\mu_x, \\mu_{y|z} are fixed but d is growing: up to lower-order terms it has the form d^k for a \"leap exponent\" k that can be determined from \\mu_x,\\mu_{y|z}, and the query class Q. As a consequence, the paper gives separations and equivalences among these classes: notably, CSQ is equivalent to DLQ for \\ell_2 loss (Proposition 6.2a), but SQ is equivalent to DLQ for \\ell_1 loss (Proposition 6.1a). \n\nAdditionally, the paper has some results showing that if one performs SGD on a two-layer neural network in the mean-field regime and with loss function \\ell, then DLQ_\\ell (rather than SQ or CSQ) is what generically characterizes success of the dynamics (more precisely, Leap(DLQ_\\ell) = 1 is what characterizes success with O(d) samples).", "questions": "- Does the characterization extend beyond just {SQ, CSQ, DLQ} to any query class Q, or if not what breaks down?\n- The equivalence between SQ and DLQ for ell_1 loss rests on a universal approximation result. I am curious if there is intuition for why the analogous approximation result for ell_2 does not hold? Is it just that there is no non-linearity in the gradient? If this is the intuition, it seems to me that in some sense \"most\" loss functions besides ell_2 ought to induce an equivalence between DLQ_ell and SQ? Proposition 6.2(c) is interesting because it gives a loss function that does not degenerate to SQ nor CSQ: is there no universal approximation here because it's a polynomial?\n- I assume that CSQ and SQ provably *do not* capture SGD on neural networks, but I didn't see a formal statement to this effect; does this follow from the separations in Section 6?\n- This is a minor technical confusion: in lines 505-506, I see why the null responses are compatible with nu^\\sigma, but since nu_{S^\\star} is not in the hypothesis class (since it's a partially \"decoupled\" distribution), I don't see why this immediately gives failure of the learning algorithm? I would have thought one needs two hypothesis in the hypothesis class to be indistinguishable. Of course I think this should also follow from (26) but I just wanted to check if I am misunderstanding.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper extends prior work by Abbe, Boix-Adsera, and Misiakiewicz to a more general setting (specifically, the prior work considered the special case of CSQ and the uniform distribution on the hypercube). While CSQ has long been motivated by the fact that it captures gradient descent, a key takeaway of this paper is that this is only for \\ell_2 loss, and for other losses a different characterization is needed. This seems like a useful observation for the community.\n- The paper also contrasts the power of adaptive queries versus non-adaptive queries, and gives a characterization of query complexity for both.\n- The paper is written carefully and rigorously.", "weaknesses": "- I spent a while trying to parse the notation for the proof of Theorem 5.1(a). Ultimately I think it is not super complicated, but some intuitive, high-level explanation of the construction would have been very helpful in addition to the formal definitions. Also, the proof outline explains the boilerplate elements that appear in any SQ lower bound argument but gives no intuition/proof sketch for the crucial and presumably novel inequality (25).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation and their valuable feedback! Below we address the weaknesses and questions.\n\n**Addressing the weakness:** Thank you for pointing that out. We will add a more intuitive summary of the proof, especially how Equality $(25)$ is derived and how the Leap exponent appears in the RHS. \n\nWe define the null distribution as the distribution with matching marginals $(y,\\boldsymbol{x})$ where the label only depends on the support of $\\boldsymbol{x}$ discoverable with leap $k_*-1$. Hence, to make any progress, any new detectable set added to the support needs to contain at least $k_*$ new coordinates. In the second moment, to have a non-zero contribution, we need the permutation to map the support to a detectable subset, i.e. the permutation to map to a subset of size at least $k$, which has probability $d^{-k_*}$ over permutation.  \n\n**Questions:**\n1. Yes, the characterization generalizes to any query class $\\mathcal{Q}$ with the class specific system of detectable subsets, where the set of test functions $\\Psi$ is simply defined as the set of $\\\\{ y \\mapsto \\phi (y,\\boldsymbol{u}) : \\phi \\in \\mathcal{Q}, \\boldsymbol{u} \\in \\mathcal{X} \\\\}$. The lower bound is proved under this general setting. However, note that our upper bound uses that (13) can be obtained using a query $\\phi \\in \\mathcal{Q}$. We can add a further property on the set $\\mathcal{Q}$ so that it is the case (note that the lower bound in Theorem 5.1 is not achievable for all classes $\\mathcal{Q}$, for example if $\\mathcal{Q}$ only contains $\\phi(y,\\boldsymbol{x}) = y$. However, we consider these cases to be less interesting).\n\n2. Yes, the general intuition behind the universality is correct. Roughly speaking, we need functions ($\\mathcal{Y} \\to \\mathbb{R}$) of the form $\\Psi_{\\mathsf{DLQ}}$ for a loss $\\ell$ mentioned in Eq (14) to be dense in $L^2(\\mu_y)=\\Psi_{\\mathsf{SQ}}$ to match the $\\mathsf{SQ}$ complexity for any link distribution. For the squared loss, $\\Psi_{\\mathsf{DLQ}}$ only contains affine functions, and thus are not dense in $L^2(\\mu_y)$ (except for $y$ supported on two points where $\\mathsf{SQ}=\\mathsf{CSQ}$). \n\nThe intuition for Proposition 6.2.(c) is indeed similar: $\\Psi_{\\mathsf{DLQ}}$ is a set of polynomials and is not dense in $L^2(\\mu_y)$ (except when the support of $y$ is finite and the dimension of the span of the polynomials in $\\Psi_{\\mathsf{DLQ}}$  is equal to the number of points in the support, i.e., all polynomials of degree is at most $P-1$, where $P$ is the support size). However, it is more powerful than $\\Psi_{\\mathsf{CSQ}}=\\\\{ y \\mapsto y \\\\}$ which only contains  identity, and there exist distributions such that the $\\mathsf{DLQ}$ exponents will be strictly smaller than the  $\\mathsf{CSQ}$ exponents.\n\n3. We do not quite understand the question on “$\\mathsf{SQ/CSQ}$ provably not capturing SGD”. \nIn general, the question of whether $\\mathsf{SQ}$-type lower bounds capture the complexity of SGD algorithms (and other algorithms) is a subtle and difficult one.  First, SQ lower bounds are proved under “adversarial noise” (worst case response in the tolerance interval $[-\\tau,\\tau]$) instead of statistical noise (when samples are used to evaluate the expectations). Second, $\\mathsf{SQ}$-algorithms only constrain the access to the data distribution, and not on how the responses are combined to produce the next query and the output (for example, in Section 7, $\\log d$ online SGD steps are enough to discover the support by looking at the gradient evaluations, however regular SGD will require $O(d)$ online SGD steps for the weights of the neural network to be updated and fit the target function).\n\nIn general, it is known that $\\mathsf{SQ}$ cannot capture the complexity of learning algorithms that use samples (e.g., separation results between PAC and $\\mathsf{SQ}$ learning), even for SGD on neural networks. Indeed, [Abbe et al. 2021b] shows that with enough machine precision and for any PAC algorithm, one can construct a neural network such that SGD emulates it by implementing sample extraction. However, such a neural network is highly irregular. It is however conjectured that $\\mathsf{SQ}$ lower bounds capture the complexity of a large class of regular algorithms (e.g., regular neural networks such as fully connected neural networks). Note that proving general computational lower bounds is difficult, and researchers often only prove lower bounds against restricted classes of algorithms such as $\\mathsf{SQ}$.\n\nAnother subtlety concerns the reuse of samples between different queries. [Dandi et al 2024] shows that by re-using samples, SGD on square loss can beat the $\\mathsf{CSQ}$ lower bound. This requires choosing hyperparameters (batch size and step size) such that two gradient steps interact to transform two $\\mathsf{CSQ}$ queries into one $\\mathsf{SQ}$ query. In general, we expect that sample reuse will not be able to beat $\\mathsf{SQ}$ lower bounds on regular architectures (as discussed above), while $\\mathsf{CSQ}$ (and $\\mathsf{DLQ}$) will capture online SGD or multi-pass SGD where the hyperparameters are not chosen carefully.\n\nMany of these issues are open questions, which do not (yet) have satisfactory answers. We discuss some of them in the introduction and the discussion section (Section 8). We will expand these discussions in the revised version.\n\n4. Yes, you are understanding correctly. Using Eq $(26)$ we get that there are two members from $\\mathcal{H}^d_\\mu$ whose query responses are compatible with the null $\\nu_{\\mathcal{S}_*}$ and hence also mutually compatible. This then establishes the failure of the learning algorithm.", "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:
This is a continuation of the response to the Reviewer atP9; other reviewers are not subjected to read.

**Relation between $\mathsf{DLQ}_\ell$ complexity and the online SGD samples:** 

In Section 7, we show that $\mathsf{DLQ}_\ell$ leap 1 functions correspond exactly to the class of functions that can be learned in the mean-field regime and linear scaling (i.e., $O(d)$-online SGD steps with batch $1$, which corresponds to $O(d)$ samples). This is similar to [Abbe et al 2022, 2023], but now beyond square loss and $\mathsf{CSQ}$. As noted in lines 286 to 297, this corresponds to a number of queries $O(d^2)$ (each gradient step corresponds to $d$ queries, which is the size of the gradient vector). This is different from the optimal $\Theta(d)$ queries in Theorem 5.1. This discrepancy was already noted in [Abbe et al 2022, 2023], and is further discussed in Section 8. The reason is that SGD on two-layer neural networks is rotationally equivariant and cannot emulate the optimal algorithm in Theorem 5.1 (this can be seen also in terms of the $\Theta (d)$ information-theoretic lower bound, which implies that $\Omega(d)$ steps is necessary). A possibility is to change the architecture of the two-layer neural network to make it “axis-aware”, as mentioned in Section 8 (see also the response to Reviewer Grg1).

Despite this discrepancy, we included Section 7 to show the relevance of the $\mathsf{DLQ}$-leap complexity in a practical setting (SGD on a regular two-layer neural network) as well as to provide a concrete separation result for regular SGD between different losses: SGD on the $\ell_1$ loss will vastly outperform online SGD on the square loss as soon as the $\mathsf{SQ}$ leap is 1 but $\mathsf{CSQ}$ leap is much bigger (e.g., the example in Proposition 6.2.(c)).

Meta-review: The authors present Differentiable Learning Queries (DLQ), a new theory framework for differentiable learning, comparing it to the existing SQ and CSQ frameworks. This clarifies the complexity of differentiable learning as being distinct from them, which is a useful observation for the community. They give a characterization of the power of DLQ for learning the support of a sparse function. All reviewers viewed the paper favorably. One of the reviewers increased their rating after discussion.
Decision: Accept (poster)