Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models
Authors: Ilias Diakonikolas
Giannis Iakovidis
Daniel Kane
Lisheng Ren
Venue: NeurIPS 2025 spotlight ()
Keywords: learning theory
PAC learning
agnostic learning
multi-index models
Statistical Query model
Primary area: theory
TL;DR: We present a general algorithm for learning real-valued Multi-Index Models and matching Statistical Query lower bounds.

Abstract: We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A $K$-MIM is a function $f:\mathbb{R}^d\to \mathbb{R}$ that depends only on the  projection of its input onto a $K$-dimensional subspace.  We give a general algorithm for PAC learning a broad class  of MIMs with respect to the square loss, even in the presence of adversarial label noise. Moreover, 
we establish a nearly matching Statistical Query (SQ) lower bound, providing evidence that the complexity of our 
algorithm is qualitatively optimal as a function of the dimension. Specifically, we consider the class of bounded variation MIMs with the property that degree at most $m$ distinguishing moments exist with respect to projections onto any subspace.  In the presence of adversarial label noise, the complexity of  our learning algorithm is $d^{O(m)}2^{\mathrm{poly}(K/\epsilon)}$.   For the realizable and independent noise settings,  our algorithm incurs complexity $d^{O(m)}2^{\mathrm{poly}(K)}(1/\epsilon)^{O(K)}$. To complement our upper bound, we show that if for some subspace degree-$m$ distinguishing moments do not exist, then any SQ learner for the corresponding class of MIMs  requires complexity $d^{\Omega(m)}$. As an application, we give  the first efficient learner for the class of positive-homogeneous 
$L$-Lipschitz $K$-MIMs. The resulting algorithm has complexity  $\mathrm{poly}(d) 2^{\mathrm{poly}(KL/\epsilon)}$. This gives a new PAC learning algorithm  for Lipschitz homogeneous ReLU networks with complexity   independent of the network size, removing the exponential dependence  incurred in prior work.

Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
Ilias Diakonikolas
Giannis lakovidis UW Madison iakovidss@wisc.edi
Daniel M. Kane UC San Diego dakaneQucsd.
UW Madison ilias@es, wisc edu
Lisheng Ren
UW Madison 1ren29@wisc. edu
Abstract
We study the complexity of learning real-valued Multi-Index Models (MIMs) un- der the Gaussian distribution. K-MIM is a function f R2 that depends only on the projection of its input onto a K -ddiimnsioonal subspace. We give a general algorithm for PAC learning a broad class of MIMs with respect the square loss, even in the presence of adversarial label noise. Moreover, we estab- lish nearly matching Statistical Query (SQ) lower bound, providing evidence that the complexity of our algorithm is qualitatively optimal as function of the dimension. Specifically, we consider the class of bounded variation MIMs with the property that degree most distinguishing moments exist with respect projections onto any subspace. the presence adversarial label noise, com- plexity of our learning algorithm is (P(m))2pnl(K//4 For the realizable and inde- pendent noise settings, our algorithm incurs complexity (pooy())))((K) (1//)) (Kk), To complement our upper bound, we show that if for some subspace degree-m dis- tinguishing moments do not exist, then any SQ learner for the corresponding class of MIMs requires complexity (()) As application, learner for the class of
give the first efficient 1.-Lipschitz K-MIMs. The result- ing algorithm has complexity poly (d)2poly(KLLs) This gives a new PAC learning algorithm for Lipschitz homogeneous ReLU networks with complexity indepen- dent of the network size, removing the exponential dependence incurred in prior work.
Introduction
A common assumption in supervised learning is that real-world data possess hidden low- dimensional structure, in the sense that the relationship between the features is of a lower- dimensional nature. A natural formalization of this principle leads to the notion of Multi-index Li91 [ XTL202 [ia08), defined below.
model [FSS1] Hub85
Definition 1.1 (Multi-Index Model (MIM)). A function f Rdd -> R is K-MIM if there exists ) for all x E Rd. where Xw is the projection of onto W. The special case of K 1 corresponds to Single-Index Models (SIMs).
a K-dimmnsioonal subspace W C Rd such that f(x) = fxxw)
A few comments are in order. First, the dimension K of the hidden subspace is typically assumed to be significantly smaller than the ambient dimension d. Second, certain regularity assumptions
Authors are listed in alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

on the target class are required for learning to be (even information-thewee theoretically) possible. MIMs can be viewed as lens for studying neural networks and other natural function classes. In re- cent years, we have witnessed a resurgence of research interest on learning SIMs and special cases
of MIMs; see.e.g.. [HI8 DKKZ20 2K200 [A121 DKTZ22, CKM22 WZDD23 GGKS23
DPLB24 ZWDD24 WZDD224 DIKZ25 ZWDD255 and references therein. See Section 1.3 for a summary of related work. Yet, our understanding of the computational complexity of learning MIMs remains limited, especially in the presence of noisy data.
The main result of this paper is an efficient robust regression algorithm, with respect to the square loss. for a broad class of MIMs. We complement our upper bound with nearly matching Statistical Query lower bound, providing evidence that the sample complexity of our algorithm qualitatively optimal- as function of the dimension for computationally efficient algorithms.
We start with the definition of learning in context.
Definition 1.2 (Agnostic PAC Learning under Gaussian Distribution). Let C be class of functions f: _R + R and D be a distribution of (x, y) over H x IR with Dx equal to the standard Gaussian. Given i.i.d. samples from D, the goal to output a hypothesis h Rd > such that with high prob- ability the error (h)
del' E(x,))~D(y h( is small, compared to OPT def inf sec errp
Definition 1.2 corresponds to the agnostic model 2Hau92 KSS94) that does not make any assump- tions on the labels. The special case corresponding to OPT = 0 (when each label is consistent with a function in the class) is known as realizable PAC learning [Va184, Moreover, the goal is to find a hypothesis with small loss-as opposed to identifying the parameters of the target function.
1.1 Our Results
We give new algorithm for learning MIMs under fairly general assumptions. Essentially, our algorithm is an iterative subspace finding method that learns better and better approximations V to the hidden subspace W. Our method succeeds under suitable conditions on the target MIM class. Roughly, we need know that, for any subspace V, either V is a good enough approximation to W (i.e., we can use it to learn f); or that by computing moments of x conditioned on the value of f and the projection onto V, we can learn some previously undiscovered direction in W. We additionally require the technical conditions that the target function has bounded norm and bounded variation, as the sample complexity of learning inherently scales with these bounds.
For two subspaces W, V of Rd, denote by Wr {wr w W} which is itself subspace. The necessary condition for our function class is given in the following definition.
Definition 1.3 Weell-eeavedd MIMs). Let d, K, m E Z+ and T, We define the class F(K, m, Ç. T)) or) as the set of all continuous and continuously differentiable almost everywhere K- MIM functions f Rd -> TR. which have the following properties:
1. Ex [Il (x) ExwAN, (f2(x) are finite and f is close to a bounded function in L2-norm
For any subspace C Rdd and any distribution D on Rd x R with Dx = Naa such that errp(/) S Ç either (a) there exists
V + I such that Ex~Na [[[(xx - g(xv) )) < T, or (b) with non- trivial probability over Z ~ Na independent of x there exists a degree at most m, zero-mean, unit variance polynomial p: U + R. where U = Wy and W is the hidden K -dimensional subspace
corresponding to f. such that E (p) xz Ex [p(x)) |xy = zv y = yo! 2 a.
Our main algorithmic result is the following:
Theorem 1.4 (Robust Regression for Well-behaved MIMs), Let D be distribution on TR. x RR with Dx = Ng.. There exists an agnostic PAC learner for F(K, m, C.T,O) a), where Ç 2 OPT + e, that m,C,T,
draws d00m) ppoly... (K/((e)) i.i.d. samples, runs in poly(N) (N) time, and computes a hypothesis h such that with high probability (h) < OPT +
We establish a similar algorithmic result for the realizable and independent label noise settings. In these (easier) settings, the complexity of our algorithm becomes (0()))poly(K) (1/))) O(kK)) poly((/o)))) i.e., we incur exponential dependence only on K. This is because in these settings the label is independent of the irrelevant subspace W ensuring that
TTis is mild assumption which holds, e.g., when the function has bounded 2.1-ree moment.

---

every direction extracted by our algorithm lies (up to estimation error) within W. For the details, we refer the reader to (eectin D.2
As we establish in Theorem 1.10 the dhd complexity dependence is qualitatively optimal in the Statistical Query model, even in the realizable (clean label) setting.
As an application of our general algorithmic technique, we obtain the first learner for positive- homogeneous Lipschitz MIMs whose complexity is fixed-degree polynomial in the dimension.
Definition 1.5 (Poittiv-Hommoeeeeou Lipschitz MIMs). For K E E4 and L > O, we define K.LL to be the class of all L-Lipschitz and unit 2-norm K-MIMs f IR + I such that f is positive- homogeneous, i.e., [(xx 1 (x) for all > Rd.
We note that K is a broad nonparametric class containing various MIMs of interest. For example, contains the class of Lipschitz and homogeneous ReLU networks (since the ReLU activation is itself
As an application of our general algorithm, we show:
Theorem 1.6 (PAC Learning HK,L)) Let D be the distribution of (x, fx)), where x ~ Na and HK.L- There exists algorithm that draws N d2 2012 (0(k2 i.i.d. samples from D, runs in time poly(N), and returns a hypothesis such that with high probability err S...
As immediate corollary of Theorem 1.6 we obtain new dlgorithm-witt qualitatively better L be the class of L-Lipsshitz functions of the form fx) W WDo(W (W D-1(--.. (-... ((W,x xx) ..)))), )), where 6(2) max 0} is the ReLU activation, W; E IR ggk+iixk, E D 1J. with kn = d and knp = 1, rank(W,)) K, and S -i ks, Since L. HK,L. we obtain the following.
complexity- for homogeneous Lipschitz ReLU networks. Let Fs,K.L
Corollary 1.7 (Learning ReLU Networks). Let D be the distribution of (x, fx)), with x Na
and f Fs.K.L. There is an algorithm that draws N d2 20 (e) samples from D, runs in Poly(N) time, and returns a hypothesis h such that with high probability err S
Corollary I.7 improves on the prior work of [CKM22) by eliminating the complexity dependence on the network size S (on which the prior algorithm of [CKM22 had an exponential dependence).
We now proceed to describe our Statistical Query lower bounds. We start with the model definition. Definition 1.8 (Statistical Query Model). Let D be a distribution on Rdd A statistical query is a bounded function q : dRd [0, I]. We define (TAT(T) to be the oracle that given any such query q. outputs value v such that |0- Exx)[ I т, where 7 > O is the tolerance of the query. A Statistical Query (SQ) algorithm is an algorithm whose objective
learn some information about an unknown distribution D by making adaptive calls to the corresponding STAT(T) oracle.
Our SQ lower bound relies on the existence of distribution on labeled examples that has similar low-degree moments as the standard Gaussian projected onto some subspace. Namely, for dis- tribution (x, y) supported on Rd+1 and an appropriate subspace V C IRd, the distribution of xy conditioned on any fixed value of xv and y matches its first m moments with (( Ily )) (the stan- dard Gaussian projected onto the subspace Vd), where Ily denotes the projection matrix of the subspace VL.
Definition 1.9 (Relative Matching of Degree-m Moments). Let m Z4, A be distribution of supported on In and U C RD be a subspace. We say that A matches degree-m moments relative to the subspace U (with the standard Gaussian projected onto U-) if for almost all V E U, under the distribution of v vy. for all m' S m it holds Ev [(Vrr j@m' Ev ) @m'), where we denote by v @@m' the m'-fold tensor product.
We are now ready to state our SQ lower bound for agnostic PAC learning of K-MISs under the Gaussian distribution.
Theorem 1.10 (SQ Lower Bound for Learning K- K-MIMs), Let C be a class of rotationally invariant K-MIMs on Rd. Suppose there exist m E E O, and a joint distribution D of (x, supported
on Rdd x R with Dx equal to Na such that for some subspace V C RRd, we have:
1. The distribution matches degree-m moments relative to the subspace V RR where the extra TR. contains the label; and
3

---

2. Any function h R - R has ((x.))-(((((x)) - -
Then, under the mild assumption that the extreme values of y have small contribution to the variance, the following holds: for d sufficiently large compared to K and m, and c E (0, 1), any SQ algorithm that learns C within error substantially better than T given OPT S infeec errp (c) requires either a query to STAT (d-(1-c)//1) or 2d many queries.
Since a query to (TA requires 12(1/72) samples to simulate in general, the intuitive interpre- tation of our SQ lower bound is the following: any simulation of an SQ algorithm for our learning task using samples, either requires d(2-a)/m/2 samples or exponential in d' time.
Note that Theorem 1.10 is essentially (up some technical conditions on each side) a converse to Theorem 1.4 In particular, Theorem 1.10 says that if there is a subspace V so that it is neither the case that y is 7-close to function of Xy nor is there non-trivial moment conditioned and y of degree at most m, then it is SQ-hard to learn (with queries of d dd0(m) accuracy) to error much better than т. On the other hand, Theorem I.4ssyss that if for every subspace V we either are approximated by a function of Xy or have a non-trivial conditional moment, then we can learn to error roughly t in time (1)) times some function of the other parameters.
xy
It is worth pointing out that an SQ lower bound for realizable learning of K-MIMS can be obtained here as a corollary of Theorem 1.10 by additionally having that OPT infeee err
Both Definition 1.9 and the corresponding SQ lower bounds for learning MIMs can be generalized for approximate moment-matching and for more general label spaces; see (Section C
1.2 Technical Overview
Intuitively, our plan is first estimate the hidden subspace. W, and then to use brute-force technique to learn distribution that depends on K dimensions. A straightforward approach to implement this plan is to use the method of moments. Since (in the noiseless case) y de- pends only on the components of x within W, any non-vanishing moments must lie entirely within W. Unfortunately, this approach can perform poorly-even for simple function classes, such as linear combinations of ReLUs. Specifically, [KK7200 showed that there exist linear combinations of l ReLUS whose first & moments vanish. This implies that any purely "moment-based strategy would require at least d((k) sample and time complexity. The work [CKM22) improved on this (for Lipschitz and homogenerous ReLU networks) by considering a more powerful test: examining moments of x conditioned on y falling within a specified range (or, equivalently, analyzing moments of indicator functions applied to y). While this broadens the power of the algorithm, simply com- puting moments in one shot may still be insufficient to obtain near-optimal algorithms. In particular, DIK725 presents class of Boolean functions for which no constant number of moments suffices to learn the hidden subspace. However, a two-stage procedure- first using moments to identify a lower-dimensional subspace V. and then leveraging additional moments conditioned on the projec- tion onto can successfully learn the full subspace.
General Algorithm.
This approach underlies our algorithm (see LearnMIMs). We employ an iterative approach that constructs progressively larger subspaces V. At each stage, we analyze the moments of x condi- tioned on y lying within small range and the projection of x onto V falling within another localized region. If any of these conditional moments exhibits significant correlation with a particular direc- tion (which we can detect using spectral methods), we augment V by adding that direction. We repeat this process for several iterations, and then learn function of the projection onto V via brute-force search.
This method does not work for all functions, but is successful for functions that are suitably well- behaved. In particular, we require that at each stage, either at least one of the discovered directions correlates non-trivially with the hidden subspace W (indicating progress), or that the current sub- space V already contains sufficient information to learn the target function to suitable error. In particular, we aim to ensure that for every function of in our class (possibly with added noise) and every subspace V, either f is well-approximated by some function of the projection onto V (within the allowable error tolerance of our learner), or there exists a neighborhood N C V and an interval I C Ih such that, conditioned on Xv E N and E 1, the distribution of x exhibits a non-trivial moment in some direction in Wy.. To achieve this, we prove that a weaker condition actually suf- fices. This condition essentially states that either the function is close to function of the projection

---

onto V, or that every noisy version of the function with small amount of additional additive noise- noise-exhibic exhibits distinguishing moments (see Proposition 2.2p. To make the algorithm work, we also need a few other minor technical assumption to ensure that it is sufficient to condition on small neighborhoods. For the full condition, see Definition 1.3
SQ Lower Bound. While the aforementioned condition might not appear especially natural, we show that it is essentially necessary-in the sense that we establish a nearly-matching lower bound in the Statistical Query (SQ) model. In particular, if we have a anationalll-invariinn function class containing some function f that does not satisfy this condition- manditi for some subspace V. is neither close to function of Xy nor is there some conditioning on y and Xy that leads to non-trivien con-trivial low degree moments- then we prove a lower bound for learning this function class to suitably small error in the SQ model. In particular, if we rotate this function I' and the joint distribution of (x, y) about V. we have a distribution chat-once we condition on the value of y/ and xy-we end-up with random rotation of the distribution Ay.xv. where Ay.xv is the distribution of xy conditioned on y and xy. Furthermore, Ay.xv matches its first m moments with the standard Gaussian projected onto the subspace V+. This is an example of a Relativized Non-Gaussian Component Analysis (RNGCA) problem. Given the moment-matching property, one would expect the following: the SQ co-mlleexyty of distinguishing between this distribution and the one where Xy is independent of Xy and the y is dd((m), Since the latter distribution cannot learned within any error better than the error of learning y as function of Xy (which by our assumption is large), this provides our learning SQ lower bound.
Unfortunately, while this kind of SQ lower bounds for Non-Gaussian Component Analysis (NGCA) are well-established [DKS17], the distributions Ay.xv will likely not be continuous with respect to the standard Gaussian. In particular, they will not have finite chi-squared norm with respect to the standard Gaussian. This rules out the traditional SQ dimension based arguments for proving the desired lower bounds. Recent work [DKRS23] showed that these kinds of SQ lower bounds can be proven with just moment-matching and no assumption on the Chi-squared norm. However, that work did not prove these bounds for RNGCA, i.e., could prove lower bounds for learning a single Ay.xy- but not the mixture over many of them (as we vary y and xy). Fortunately, this can be fixed by generalizing the techniques of [DKS223 to our more challenging context. Specifically, we show that an arbitrary bounded SQ query function g is overwhelmingly likely to have expectation over the joint distribution of (x, y) very close to the averaged expectation over random rotations of this distribution described above. By mirroring the analysis of [DKS223,, we prove this by using Fourier analysis. We note that the low-degree Fourier coefficients of Ay,xv vanish (or nearly vanish) and so contribute little to the expectation of q; and that the higher-degree Fourier coefficients are unlikely to correlate well with q after the random rotation is applied.
Conerete Applications. Given our general algorithm, our applications hinge on establishing struc- tural results for the relevant function classes. In particular, in order to obtain an algorithm for function class F, we need to show that it satisfies Definntion 1.3 with suitably favorable parameters. Specifically, we need to establish that, unless function in F is already close to depending only on the projection onto V, it exhibits non-trivial conditional low degree moments.
Our main application is to the class of positive- hottoeeeoo Lipschitz functions- broad, non- parametric generalization of the ReLU networks studied in [CKM22). Here we show that second moments are sufficient. The basic idea is that if f is not close to zero, then there exists some x for which [x() is reasonably large. This implies that [((x)) will be quite large for suitably large X. On the other hand, by the Lipschitz property, [/(x) can only be large if ||xw || is large. Therefore, the set S, = fx [x(x) > + will exhibit a non-trivial second moment along W for sufficiently large т. This argument yields at least one relevant direction. Moreover, given subspace V. we can apply the same reasoning to the residual function f(x) - fx(v), ). This shows that either f(x) is close to f(xv) (i.e., a function of the projection onto V), or f exhibits a non-vanishing conditional moment. Consequently, by approximating the Boolean function 1 ([f(x)= f(xv)) ) 2 r) by a piece- wise constant function over a partition consisting of cubes in xy and intervals in y, we show that there exists partition element for which the conditional distribution exhibits a non-trivial moment. This, in turn, implies that the function class is well-behaved, so our algorithm applies.
An additional application is for the class of polynomials that depend only on projections onto a nww-dimensional subspace, recovering the upper bounds of (CM20). See Section D.3]
5

---

1.3 Related Work
Due to space limitations, here we record the most directly relevant works. For detailed overview, see [Section A] Roughly speaking, our algorithmic understanding of learning SIMS is currently fairly complete, both for parameter recovery [HH88 [AG2I DPLB24] and agnostic PAC learn- ing [DKTZ22] WZDD24 ZWWD224 ZWDD25]. On the other hand, our understanding of the effi- cient learnability of MIMs somewhat more limited. A number of papers have developed efficient learners for interesting special cases, including low- low-dimensional polynomials [CM0 and homoge-
neous ReLU networks [CKM22]. LABAB 21 ABBAM22 ABAM23 introduced a complexity no- tion (leap complexity) for learning structured MIMs, which turns out to essentially characterize the Correlational SQ (CSQ) complexity of learning under certain assumptions. More recently, [JS24] adapted the notion of leap complexity to characterize the SQ hardness of hidden-junta functions (a natural special case of MIMs). The reader is referred (BH25 for a very recent survey on the topic.
[PLB22] defined the notion of the generative exponent, which plays the role of our parameter m in characterizing the complexity of parameter recovery for SIMs. As explained in Appendix [C.3] our Definition 1.3 reduces to a modification of the generative exponent when K = 1. Such modifica- tion is necessary, account for the fact that we characterize the complexity of PAC learning, rather than parameter estimation, even in the presence of adversarial label noise. Thus, our techniques can be viewed as generalization of D2LB24] to multi-index models.
Comparison with DIKZ255 At the technical level, the most closely related work to ours is [DIKZ25]. that established a aasalote-analogue of our results in the context of classification for MIMs with finite output space. While our work broadly follows the approach of [DIKZ25], the transition from discrete-valued MIMs to those with infinitely many outputs, as well as the shift from To-loss to L2-loss, requires significant changes in the mechanics of our results and the analysis.
In terms of our algorithm, perhaps the most significant change is that on specific values of y-since we do not expect to observe repeated y values. Instead, we need condition on y falling within small interval. Additionally, since y is now unbounded and we are working with the L2 loss, establishing convergence results for our piecewise constant approxi- mations becomes more challenging. Finally, [DIKZ25) used technical condition on the Gaussian surface area of the level-sets to allow conditioning on small rectangles, and to guarantee that the learned directions are sufficiently distinct from those already identified. Here we need to design new conditions to deal with these issues. Regarding our SQ lower-bound analysis, conditioning on a given value of y in this setting would likely yield a singular distribution. So establishing the de- sired bounds requires us to develop new machinery for proving lower bounds for relativized NGCA without having bounds on the chi- chi-squared divergence. Another technical complication arises in our reduction from testing lower bounds to learning. In particular, we need to be able to approximate the L2 loss within the SQ framework. While this is essentially trivial for the Lo loss, here we need to add some technical conditions to make it feasible, as y might be unbounded.
longer condition
We compare our contributions to the independent work of (DLB25). Roughly speaking, both works study the task of learning MIMs and obtain efficient algorithms with qualitatively similar sample complexities with respect to the dimension. This similarity notwith- standing, the two works address fundamentally different objectives:
Comparison with [DL225]
1. PAC Learning vs. Parameter Recovery: Our work focuses on the PAC learning task, i.e., the task of obtaining hypothesis with low prediction error (without requiring to identify the underlying subspace). In contrast, (LB225) focuses on parameter recovery, aiming to precisely estimate the underlying subspace. Note that PAC learning may be feasible in settings where parameter recovery is information-theorrticall very simple functions that admit accurate predictors even when the subspace is not identifiable. In infSection C.3 we elaborate on this distinction in the context of the prior work [DPLB24] (which focused on single-index models).
impossible. Specifically, it is possible to design
2. Agnostic Sharning/Adversrrtin Label Noise:
Our work provides an algorithm with provable guarantees for both the independent label noise and the agnostic settings. In contrast, the work of (DLB25 focuses on the realizable setting.

---

Interestingly, when restricted to the realizable setting and when parameter-recoven is possible, one can show that our Definiiio I.3] and the "generative-leap exponent" of [DL225] are essentially equivalent. This can be shown by roughly the same analysis as presented in Section C.3 for the generative exponent (the single-index special case). In other words, our complexity measure from Definition 1.3 can be viewed as generalization of the "generative leap" to the potentially noisy setting.
Finally, we note that the sample complexity dependence of the algorithm in DDB25 is, roughly, /max{(1.m/2) (excluding factors that depend on e and the underlying activation), is quantitatively optimal with respect to the dimension in the class of SQ algorithms (as follows from our SQ lower bound). Our work focused on obtaining qualitative bound of the form d0(m), which suffices for the purpose of characterizing polynomial learnability of MIMs. Remark D.15 outlines a simple approach to obtain a sample bound of dfm/22 in our setting.
2 General MIM Algorithm
As mentioned in Section 1.2 to apply the moment method effectively to such a general class of functions, we need to condition on x and falling within certain ranges. To achieve this, we par- tition the space of and y into sufficiently small regions-speciinnn specifically, regular cubic regions for and intervals for y. We prove that, as long as these partitions are fine enough, they can detect distinguishing moments. Formally:
Definition 2.1 (e-Approximating Discretization). Let V be a subspace of Rd. We define an e- approximating discretization of V x R as a pair (S) satisfying the following. The set S partitions the subset of V, consisting of all vectors whose coordinates in a fixed orthonormal basis of V are less than /log 1/c) in absolute value, into cubes of side length c (with respect to the same orthonormal basis). The Z partitions the interval [-1/e, 1/e] into intervals of length
Moreover, for a partition S, we denote by hs the piecewise constant function that for every S E S outputs (x) = Ely x E S] for all x E S.
As mentioned in [Section 1.2 our algorithm, LearnMIMs, performs iterative subspace approxi- mation. At each step 1, it updates a list of vectors Tup (Line of of LearnMIMs) so that the span V span(Le) becomes a better approximation of the hidden subspace W. Specifically, at each iteration, the algorithm computes a sufficiently fine discretization (S, I) of the space V x IR (Line 2 of FindDirection). Using the assumption that the distribution is well-behaved (Definition 1.3), we can show that a non-negligible fraction of the discretization cells exhibit distinguishing moments.
As result, we extract relevant directions by computing the top eigenvectors of the influence matrix corresponding to a regression polynomial fitted within each cell (Line of FindDirection). How- ever, since the number of discretization cells depends exponentially filtering step to avoid adding too many vectors. To this end, we construct a matrix U, which the weighted sum of influence matrices across all discretization cells, with weights given by the proba- bility mass of each cell (Line 4 of FindDirection). It is not difficult to show that, since a constant fraction of the cells exhibit distinguishing moments, there exists an eigenvector of U with a suffi- ciently large eigenvalue that correlates with a distinguishing moment, thereby revealing a relevant direction. Once further distinguishing moments fies Definition 1.3] the current subspace V forms a good enough approximation of W. Finally, the algorithm returns a piecewise constant function hi, defined over sufficiently fine partition S of Vi-
dim (Vz), we must apply
be found, since the target function satis-
The main part of our analysis is to show that, at each iteration, as long as V, is not sufficient to compute a hypothesis with small error, the algorithm will add a direction that correlates with W. By applying this argument iteratively, can show that improvement will eventually stop and we will have a good predictor.
Proposition 2.2 (Estimating a Relevant Direction). Let D be distribution supported on Rd x R whose x-marginal is Na. Let Rd + E. be such that f E F(K, m, OPT + E, T,.), and denote by W K --dimensional subspace defining f. Let V be a k-dimensional subspace of Rd and let S be a partition of V into cubes of width (1))))(1)) If (oxx))-p((sss FindDirection, when given N = ((m)) (k/)))))//000k /o0kk//ol O()) samples, runs in time poly(N) and with
y) > r OPT + c, then
7

---

LearnMIMs: Robust Regression for Well-Behaved MIMs
Input:
Accuracy 0, sample access to distribution D over Rdd x for which there exists K-MIM function f F(K, m, OPT + c, T, r) parameters m. d. K.
Output: hypothesis such that with high probability errp(h) Σ 7 OPT +
1. Let T be sufficiently large constant-degree polynomial in m, K, 1/1,//,1/ 1/c.
2. Initialize 1 <- 0. N 20 1og(1/6).
3. Fort= 1.......
(a) Draw set St of N i..d. samples from D. (b) & + Fee.DFiieetionsppaae Lx), St, m, K).
(c) L1+1 + L &
4. Construct e-approximating discretization (8, I) of span(L.) R.
5. Draw N ii.d. samples from D and empirically approximate the piecewise constant function hs.
6. Return hg.
Algorithm 1: Learning Well-Behaved MIMs
FindDirection: Estimating a relevant direction
Input: A subspace V of Rd, and set of N samples from distribution D over R$ x E for which there exists a K-MIM function f E F(K,m, OPT + G,T,)) parameters c, a, m, K. Output:A set of unit vectors E
1. Let be a sufficiently small polynomial in o,,,
Construct an e-approximating discretization (S, of x R.
3. For each S S and I I, perform degree-m polynomial regression on 1 I) over the samples, resulting in polynomial (x.
4. Let U Eses,rez Ex-D,, (Vp., (at.:/XXX>VVsssxx____ (Xy,)
S)Pr(x.))-D(S)
5. Return the set & of unit eigenvectors of U with corresponding eigenvalues at least A.
Algorithm 2: Estimating a relevant direction
high probability returns a list of unit vectors & of size |8] = (m,K(ee)))01) such that for some
v E, ||vwil = (ea (ta//mK))00)
We sketch the analysis our driving proposition bellow. Full details the proof are provided in Section D
Proof Sketch oroooosiin 2.2] Let w (k) be an orthonormal basis of W and denote by
U the matrix computed at Line Let I a partition of (-1/c0(1, 1/(0(] to intervals of width ,(1).
Our strategy for proving the proposition essentially involves three steps: (i) show that Condition (2b) Definittin 1.3 satisfied; (ii) prove that the discretization of V R into cube-interval pairs is sufficient to detect moments; and (iii) argue that, given the observed moments, there exists an eigenvector U corresponding to a large eigenvalue that has a non-trivial projection onto W. We briefly discuss the proof of each of these steps.
Notice that, establish the first step, it suffices show that if E((((x hs (x)) 2 T c, then [x(((x) {(x
for all V + R. This follows from the assumption that f is a function of bounded variation, i.e.. Ex-N, [VVJ is bounded, and that approximately bounded: any such function can be approximated arbitrarily well by piecewise-constant functions over sufficiently fine partition of cubes covering of TRd except for of small mass under Na, Hence, Condition (2a) is not satisfied, therefore Condition (2b) is (see Definition 1.3).

---

Step (ii) holds essentially because, by assumption, the distinguishing moment condition applies to all label random variables y' that are (OPT+c)-closs to f in L2. Specifically, we construct label y' that remains close to f in two steps: first discretizing and then averaging y over boxes. We discretize y by rounding it to the nearest multiple of c, thereby partitioning the label distribution into intervals of width c. Then, since f has bounded variation, for each cube. S E S the value [(x) is close to the average label over that cube, so we can do the same for the label. By combining these two steps, we obtain a label random variable y' that is discretized over small intervals, is conditionally independent of a specific point x given a cube distinguishing moment condition the joint discretization of xy and y. Moreover, since Condition (2b) ensures that distinguishing moments hold for a non non-trivial fraction of xv, it follows that we observe these moments conditioned on a cube S with probability at least over S, for some >> 0.
S, and remains close to f. Using this independence yields the
Step (iii) follows because the regression polynomial ps,r must match low-degree Hermite coeffi
cients with the function (xx def E(x,y)-n((( E I) | E S], and hence must exhibit sufficient variation along directions where g has a nontrivial low-degree moment, which in turn implies a nonzero directional derivative in these directions.
Recall that with probability a > O over S E S there exists some i E [K] such that E[(w(0) Vps, r (xv )) = ((/KK). This implies that, for some i E [K], with probability a/K K over S it holds that E((w(). V )) = / Therefore, the quadratic form of U for I Uw(() \²) Moreover, from well- facts about polynomials over the standard Gaussian, we obtain that ||U]| F S m/poly(e).
the corresponding (()) is large, i.e., (w())
Finally, by a standard linear algebraic fact, if we consider the unit eigenvectors of U corresponding to eigenvalues greater than O(r/K²), we obtain at most (|U|= K/))(())))) such vectors. Among them, at least one achieves correlation at least
with the aforementioned (+)
Furthermore, we note that the number of samples specified in the statement is precisely the num- ber required perform polynomial regression with enough accuracy to observe these low-degree moments with high probability. This completes the proof sketch of Proposiiion 2.2
3 SQ Lower Bounds for MIMs
In order to prove our SQ lower bound for learning MIMs, develop the framework of Rela- tivized Non-Gaussian Component Analysis (RNGCA), a generalization of the previously developed Non-Gaussian Component Analysis (NGCA) framework [DKS17 DKRS23 where we allow the hidden distribution to be a labeled distribution so that we can tackle the supervised MIM setting. The main technical contribution of this section (hheoemm 3.3) is an SQ lower bound for RNGCA. Our SQ lower bounds for learning MIMs follow as an application of this general result. We believe that our generic SQ lower bound for RNGCA will be of broader applicability.
We start by defining the family of relativized hidden-subspace distributions, which is a core ingre- dient of the RNGCA framework.
We require some additional notation. We use Os,k S R with k S d to denote the set of all d xx orthogonal matrices, i.e., the set of all matrices V such that VTV- = Lg. For two distributions D1, D2 over X1, X2, we use D₁ @ D2 to denote the product distribution of D2 and D2 over X1 x Xx2 Definition 3.1 (Relativized Hidden--Subspace Distribution). For joint distribution A of (z. y) sup- ported on R IR" and matrix U Oakk, we define the distribution P4 as the joint distribution of (z', y') supported on Rd R" such that
1. the joint distribution of (UT x',y') )") is A; and 2. z'yu is distributed according to (0, 11r=) independent of the value of (UT 22,''''' y'), where U is the column space of U and A(, Igga) ) is the standard Gaussian projected onto U-.
That is, up to a rotation on Rd. Pd is the distribution on dd x (R* x R") given by Na- & A.
We now define the natural hypothesis testing version of the RNGCA problem. This suffices for the purpose of proving hardness, as the learning version typically reduces to the testing problem. Intuitively, the task here to test whether there is a subspace such that the marginal distribution on the subspace is not a standard Gaussian.

---

Definition 3.2 (Hypothesis Testing Version of Relativized Non- Von-Gaussian Component Analysis), Let d k 2 1 be integers. For a joint distribution A of y) supported on IR R", one is given access to a distribution D such that either: Ho: D = Na & Ay. or H1: D is given by P where U U.0,))) The goal is to distinguish between these two hypotheses Ho and H1.
We are now ready to give our main SQ lower bound result for this problem. Intuitively, our lower bound states that if the distribution A of y) matches degree-m moments relative to the subspace with the standard Gaussian, then any SQ algorithm solving the RNGCA testing problem requires complexity d((m) The reader is referred to Section C for the generalization of Theorem 3.3 with approximate moment matching and generalized label spaces.
Theorem 3.3 (SQ Lower Bound for RNGCA). Let A E (0,1) and d, k, m E N with m even and k. m S d /o/logd, d. Let A be a distribution over R x IR" that matches degree-m moments relative the subspace R. (with the standard Gaussian on R$). Let 0 < (1 X and d be sufficiently large. Then any SQ algorithm solving the d-dimensional RNGCA problem with hidden distribution A (as defined in Defimition 3.2) with 2/3 success probability requires either a query to or 2d many queries.
STAT (Ok,m (d-(11>))4--pp)
is worth noting that the relatiiadi special case of Theorem 3.3 (i. (i.e., when n = 0) was already proven in prior work [DKRS23] It is important to note that [Theorem 3.3 cannot be derived using [KRS233 as a black-box. While weaker version of Theorem 3.3]could be potentially obtained using techniques in previous works (see, e.g., [DKS17 DKSI9), this would necessarily require the additional assumption that (A, & Ay) is finite. As a result, one would not be able to apply to even the simplest settings like realizable MIMs-as having noiseless labels would induce infinite x² (A,,%, & Ay). Our proof here builds on the earlier proof in [KRS233.. Namely, we apply similar technique of truncating the part of the distribution inside ball, and then use Fourier analysis on the truncated A. However, doing so for the labeled distribution A here would also mess up the marginal distribution Ay and change the notion of the norm in Fourier analysis. To deal with this problem, our analysis employs a new reweighting technique to ensure the equivalence of norm before and after the truncation. The detailed proof is given in Section C.I
Given Theorem 3.3 we are now ready to prove Theorem 1.10 (see full proof in Section C.2)
Proof sketch of Theorem 1.10 The proof follows directly by embedding an RNGCA problem to agnostic PAC learning of the class C. Let A' be the distribution D in Theorem 1.10 and W be the K-dimensional relevant subspace of the K-MIM c that minimizes the error ert x-() Let V be
the subspace satisfying the conditions in Theorem 1. 1.10 and = Wy-, where Wyd def {wy1 : w E WJ. Without loss of generality, we assume that V is the subspace spanned by the last dim(V) (V) coordinates, and U is the subspace spanned by the dim(U) coordinates immediately preceding those of V, which can be arranged by appropriate rotation.
Let (x, y) A'. We define the distribution A for the RNGCA (Definition 3.2) as the joint distribu- tion of (x', (x", ,)) over (Rdim(U) [gdim(V)++ ++1 where x' and x" each contains the coordinates of corresponding to U and V. i.e., x' contains the part of the relevant subspace (of the optimal hypothe- sis) outside V and (x". y) contains V and the label y. Let be the input distribution of this RNGCA problem. Notice that D can be equivalently thought of labeled distribution supported on Rd x R, where we treat the coordinate corresponding to the y part as the label. If D is the null hypothesis distribution, we would simply observe the production distribution of (O, Id-dim(())) ( @ Ay. where Ay is the marginal distribution of (x", .). If we treat D as labeled distribution, then any hypothesis can only predict the label by the value of xv. therefore, no hypothesis h : Rd - R can have error err (h) < T from the assumption. However, if D is the alternative distribution, the distribution we observe is the product distribution of (O, [d-dim(U) we treat D as a labeled distribution, since A contains the coordinates of A' that span the relevant subspace W of the optimal hypothesis. when given to the MIM algorithm, it is obliged to return a hypothesis with squared error substantially better than T.
à A (up to applying a rotation). If
Given the above discussion, we can simply give the distribution D to the MIM algorithm as a labeled distribution over Rd x IR and check the error of the output hypothesis. If the emror is better than т, D must be the alternative hypothesis distribution. Otherwise, D the null hypothesis distribution. This completes the proof sketch of l'heorem 1.10
10

---

4 Acknowledgments
Ilass Diakonikolas was supported by NSF Medium Award CCF-2107079, ONR award number 100014-25-1-2268 and an H.I. Romnes Faculty Fellowship. Giannis Iakovidis was supported in part by ONR award number N00014-25-1- 1-2668 and NSF Award Kane was supported by NSF Award CCF-1553288 (CAREER) and Sloan Research Fellowship. Lisheng Ren was supported in part by NSF Medium Award CCF-2107079.
(TRIPODS). Daniel
References
[ABAB*21] E. Abbe, E. Boix-Adsera, M. S. Brennan, G. Bresler, and D. Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems, 34:26989-27002, 2021.
[ABAM22] E. Abbe, E. Boix-Adsera, and T. Misiakiewicz. The merged-stairease property: necessary and nearly sufficient condition for sgd learning of sparse functions on two- layer neural networks. Conference on Learning Theory, pages 4782-4887, PMLR, 2022.
[ABAM23] Abbe, E. Boix- Adsera, and T. Misiakiewicz. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference on Learning Theory, pages
PMLR, 2023.
[AGJ21] G. B. Arous, R. Gheissari, and A. Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22(106):1-51, 2021.
[BH25] J. Bruna and D. Hsu. Survey algorithms for multi-index models. arXiv preprint arXiv:2504.05422 05546,, 2025.
[BLM13] Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymp- lotic Theory of Independence. Oxford University Press, 2013.
[CKM22] S. Chen, A. R Klivans, and R. Meka. Learning deep relu networks is fixed- sardd-errameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707. IEEE, 2022.
[CM20] S. Chen and R. Meka. Learning polynomials in few relevant dimensions. In Confer- ence on Learning Theorr, pages 1161-1227. PMLR, 2020.
[CMM25] E. Cornacchia, D. Mikulincer, and E. Mossel. Low-dimensional functions efficiently learnable under randomly biased distributions. arXiv preprint arXiv:2502. 06443, 2025.
[CW01] A.
Carbery and J. Wright. Distributional and L norm inequalities for polynomials over convex bodies in R Mathematical Research Letters, 8(3):233-248, 2001.
[DDM+25] L. Defilippis, Y. Dandi, Mergny, F. Krzakala, and B. Loureiro. Optimal spectral transitions in high-dimensione multi-index models. arXiv preprint arXiv:2502.0254: 2025.
[DGK+20] I. Diakonikolas, Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi. Ap- proximation schemes for relu regression. In Conference on Learning Theory, COLT, volume 125 of Proceedings of Machine Learning Research, pages 1452-1485. PMLR, 2020.
[DH18] R. Dudeja and D. Hsu. Learning single-index models in gaussian space. In Confer- ence On Learning Theory, COLT, volume 75 of Proceedings of Machine Learning Research, pages 1887-1930. PMLR, 2018.
[DIZ255] I. Diakonikolas, G. lakovidis, D. M. Kane, and N. Zarifis. Robust learning of multi- index models via iterative subspace approximation. arXiv eprint Xixv:2502.00525, 2025.

---

[DK20] I. Diakonikolas and D. M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), 2020.
[DKK* I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Agnostic proper learning of halfspaces under gaussian marginals. In Conference on Learning Theory, pages 1522-1551. PMLR, 2021.
[DKK720] I.
Diakonikolas, M. Kane, V. Kontonis, and Zarifis. Algorithms and SQ lower bounds for PAC learning mne-hidden-layer relu networks. In Conference on Learn- ing Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 1514-1539. PMLR, 2020.
[DKRS23] I. Diiakonikolas, D. M. Kane, L. Ren, and Y. Sun. SQ lower bounds for non gan-saanninn component analysis with weaker assumptions. In Advances Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Sys- tems 2023, NeurlPS 2023, 2023.
[DKS17] I. Diakoniiolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of diggeniinnsi gaussians and gaussian mixtures. In 58th IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2017, pages 73-84, 2017. Full version at http://arxiv.orggab///// 111.///////111.333333 .03473.
[DKS19] I. Diakonikolas, W. Kong, and A. Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2019, pages 2745-2754, 2019.
[DKTZ22] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning a single neuron with adversarial label noise via gradient descent. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4313-4361, 2022.
[DLB25] A. Damian, D. Lee, and J. Bruna. The generative leap: efficiently learning gaussian multi-index models. arXiv preprint arXiv:2506.05500 2025.
Sharp sample complexity for
[DPLB24] A. Damian, L. Pillaud- Vivien, J. D. Lee, and J. Bruna. Computationaalssttissti gaps in gaussian single-index models. In The Thirty Seventh Annual Conference on Learn- ing Theory, volume 247 of Proceedings of Machine Learning Research, page 1262, 2024.
[FIS81] J. H. Friedman, M. Jacobson, and W. Stuetzle. Projection Pursuit Regression. J. Am. Statist. Assoc., 76:817, 1981.
[GGKS23] A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. In Advances in Neural Information Pro- cessing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS, 2023.
[Hau92] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78-11 -5000 1992.
[HL93] P. Hall and K.-C. Li. On almost Linearity of Low Dimensional Projections from High Dimensional Data. The Annals of Statistics, 21(2):867 - 889, 1993.
[Hub85] J. Huber. Projection Pursuit. The Annals of Statistics, 13(2):435 475, 1985.
[JMS24] N. Joshi, T. Misiakiewicz, and N. Srebro. On the complexity of learning sparse func- tions with statistical and gradient queries. In Advances in Newral Information Pro- cessing Systems 38: Annual Conference Neural Information Processing Systems, NeurlPS, 2024.
[KKS11J] M. Kakade, A. Kalai, Kanade, and O. Shamir. Efficient learning of general- ized linear and single index models with isotonic regression. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems, pages 927-935, 2011.
12

---

[KSS94] M. Kearns, R. Schapire, and L. Sellie. Toward Efficient Agnostic Learning. Machine Learning, 17(2/3)115--111, 1994.
[KTZ19] V. Kontonis, C. Tzamos, and M. Zampetakis. Efficient Truncated Statistics with Unknown Truncation In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1578-1595, 2019.
[KZM25] Kovacevic, Y. Zhang, and M. Mondelli. Spectral estimators for multi-index models: Precise asymptotics and optimal weak recovery. arXiv preprint arXiv:2502.01588, 2025.
[Li91] K. Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, 86(414):316-32) 1991.
[MHJE24] A. Mousavi-Hosseini, A. Javanmard, and M. A. Erdogdu. Robust feature learning for multi-index models in high dimensions, arXiv preprint SKIv:24100164449 2024.
[MHWE25] A. Mousavi-Hosseini, D. Wu, and M. A. Erdogdu. Learning multi-inder models with neural networks via mean-fiele langevin dynamics. International Conference on Learning Representations, ICLR, 2025.
[O'D14] R. O' O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[OSSW24] K. Oko, Y. Song. T. Suzuki, and D. Wu. Learning sum of diverse features: compu- tational hardness and efficient gradient- training for ridge combinations. In The Thirty Seventh Annual Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4009-4081, 2024.
[RL24] Y. Ren and J. D. Lee. Learning orthogonal multi-index models: A fine-grained infor- mation exponent analysis. arXiv preprint arXiv:2410.09678. 2024.
[SBH24] B. Simsek, A. Bendjeddou, and D. Hsu. Learning gaussian multi-index models with gradient flow: Time complexity and directional convergence. arXiv preprint arXiv:241 1108798,, 2024.
[TDD+24] E. Troiani, Y. Dandi, L. Defilippis, L. Zdeborová, B. Loureiro, and F. Krzakala. Fun- damental computational limits of weak learnability high-dimensional multi-index models. arXiv preprint arXiv:2405. 15480, 2024.
[Va184] L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134- 1142, 1984.
[Ver18] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018
[WZDD23] Wang, N. Zaritis, I. Diakonikolas, and J. Diakonikolas. Robustly learning a single neuron via sharpness. In International conference on machine learning, pages 36541- 36577. PMLR, 2023.
[WZDD24] Wang, N. Zarifis, I. Diakonikolas, and Diakonikolas. Sample and computation- ally efficient robust learning of gaussian single-index models, Advances in Neural Information Processing Systems, 37:58376-58422, 2024.
[Xia08] Y. Xia. A multiple-index model and dimension reduction. Journal of the American Statistical Association, 103(484): 1111-1614444 2008
[XTLZ22] Y. Xia, H. Tong, W. K. Li, and L. Zhu. An adaptive estimation of dimension reduc- tion space. Journal of the Royal Statistical Society Series B: Statistical Methodology, 64(3):363-41 2002.
[ZWDD24] N. Zarifis, P. Wang, I. Diakonikolas, and Diakonikolas. Robustly learning single- index models via alignment sharpness. In Proceedings of the 41 International Con- ference on Machine Learning, volume 235 of Proceedings of Machine Learning Re- search, pages 58 58197-58243, 2024.
13

---

[ZWDD25] N. Zarifis, P. Wang. I. Diakonikolas, and J. Diakonikolas. Robustly learning monotone
generalized linear models via data augmentation. arXiv preprint arXiv:2502.08611, 2025.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract summarizes the result provided in Theorems 1.4 and 1.10 which are thoroughly proven in the supplementary material. The introduction describes how this contribution resolves the open problem characterizing the complexity of learning real- valued MIMs and describes prior work's contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as it 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: The limitations are clearly stated in the statements of each theorem and are discussed in the introduction of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
15

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Each theorem statement provides all the assumptions and we provide a com- plete proof for all statements in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
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 to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily 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) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
16

---

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: [NA]
Justification: The paper is theoretical in nature and does not include code, data experi- ments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS 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 including code, unless this is central to the contribution (e.g., for a 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.c.////// httplss.ccppublccguu.eeeee Cod///ooeeeeeeeeeecee onPolicy)
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 omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably 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 (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory. time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://eeruiisscc//////////e
Answer: [Yes]
Justification:
Our research conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is theoretical and we do not see any major or immediate implica- tions on society.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work is theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
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 re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
This work does not use any assets.
Guidelines:
The answer NA means that the paper does 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, 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.
license, copyright information, and terms of use the pack- age should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
If assets are released,
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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 documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This work does not any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: This work does not involve any crowdsourcing research with human sub- jects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution 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, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
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: This work does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) 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 we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
20

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs where used only for writing, editing and formatting purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standard components.
Please refer to our LLM policy htttp::/meurrpps.cc/ooffeee for what should or should not be described.
21

---

Appendix
Organization The appendix is structured as follows: In Section A we discuss additional related work. In [Section B we record the notation and mathematical background required in our technical sections. The technical content of the appendix consists of two sections: Section C presents our SQ lower bounds and Section D presents our algorithmic results.
A Related Work
The most closely related works to ours is [DKK225] which studies the problem of learning discrete- valued MIMs. In [Section 1.2 we highlight the technical and conceptual distinctions between our approach and that of IDIZ225 However, for learning real-valued MIMs, there has been no prior work establishing a characterization of the SQ complexity of the problem.
For the special case of SIMs, the problem is much better understood. Specifically, recent work (DPLB24) examined the complexity of parameter estimation for SIMs and identified complexity measure that, under certain assumptions, characterizes the SQ sample complexity. As we demon- strate in |Section C.3] our SQ lower bound strictly generalizes theirs, applying both to learning to small-L2 error learning and parameter estimation whenever the MIM matches moments. More- over. there has been a lot of algorithmic works for general classes of SIMs/GLMs from classical works like [KKSIT] to more recent works obtaining near optimal complexity and error guarantees [DGK 20
WZDD24
ZWDD24 ZWDD25 WZDD23].
Several works introduce CSQ complexity measures and algortihms for learning MIMs and SIMs e.g. the information exponent for SIM link functions [AGJ21] [HH8], the leap complex- ity [ABAB+21, ABAM22 ABAM23] for MIMs. However, all of these measures yield only CSQ guarantees, since they neither condition the label y. Notably, (JMS24) further generalized the no- tion of leap complexity to characterize the SQ hardness of hidden-junta functions (which is a special case of MIMs).
Moreover, recently there is a significant interest in learning several structured subclasses of MIMs. Specifically [OSSW24] studied the problem of learning sums of SIMs under a near-orthonormality and [RL24] under a strict orthonormality assumption, providing both algorithms and lower bounds. Iterative dimensionality reduction techniques have been used in the past for learning certain func- tions families such as homogeneous ReLU networks [CKM22] and polynomials in a few relevant directions [CM20) There has also been lot of work (DDM 25 TDD 24 KZM25) on the prob- lem of weak subspace recovery for MIMs using a linear number of samples within the approximate message passing framework.
Other works offer alternative guarantees, complexity under random bias [CMM25), gradient- convergence and time bounds (SBH24), mean-field Langevin dynamics yielding global conver- gence in -nfinite-width nets [MHWE25] and agnostic subspace-recovery learning with an oracle
EMH
B Preliminaries
Basic Notation For n E E4, let [n]] def n.). We will use lowercase boldface letters for vectors and capitalized boldface letters for matrices and tensors. For x E Rd and E [d], x; denotes the i-th coordinate of and ||x||= := (> |x/1*)2/6 denotes the 4n-orrm of x. Throughout this text, we will often omit the subscript and simply write ||x|] for the f2-norm of x. For a matrix V E Raxm, we denote by || [|][= to be the operator norm and Frobenius norm respectively.
We will use x for the inner product of y E Rd
For subspace V of Rdd, matrix. For vectors x, v E Rd and a subspace V S IR denote by xy the projection of x onto V and by xv the projection of x onto the line spanned by v. For two subspaces V, W C IRd we denote by Wv = {wv= : w E W} and by V + W = [ + v w E W, v E J. note that Wv and V + W are both subspaces. Furthermore, for a set of vectors C IRd, we denote by span(L) the subspace of Rd defined by their span. We slightly abuse notation and denote by e; the i-th standard basis vector in d We use Sn-1 = [x E R. ||x||2 = 1} to denote the n-dimensional unit sphere.
denote by V+ its orthogonal complement and by Ty its projection
22

---

We use the standard asymptotic notation, where Ō(-) is used to omit polylogarithmic factors. Fur- thermore, we use a I to denote that there exists an absolute universal constant C' > 0 (independent of the variables or parameters on which and b depend) such that Σ Cb, Z is defined similarly. We use the notation g(t) I poly(t) for a quantity 2 indicate that there exists constants C' > 0 such that g(t) I Ct Similarly we use g(t) 2 poly(t) for a quantity < 1 to denote that there exists constants c, > 0 such that g(t) 2 Ct.
Tensor Notation For tensors, we will consider k-tensor to be an element in (Rd)@k 2 Rdd. This can be thought of as a vector with d coordinates. We will use Ai..... to denote the coordinate of a k-tensor A indexed by the k-tuple (i,...., ..). By abuse of notation, we will sometimes also use this to denote the entire tensor. The inner product and gh -o-no of a k-tensor are defined by viewing the tensor as a vector with d coordinates and then applying the standard definitions of the inner product and f*-norm for vectors. The inner product of two tensors will be denoted by (: For vector E R4, we denote by y* to be vector (linear object) in I, In addition, for matrix V E Rddmm we denote by v@k to be a matrix (linear operator) mapping Rm to Rd*, Also, we define the set of orthogonal d x matrices by Oa,m {V E Rdxm
V V Im]
Probability Notation We use Eg-D [x] for the expectation of the random variable x according to the distribution D and Pr[e] for the probability of event & For simplicity of notation, we may omit the distribution when it clear from the context. For a continuous distribution D over R2 we sometimes use for both the distribution itself and its probability density function. For two distributions
D1, D2 over a probability space Ωt let drv (D,, D2) def supscn prr,, (5) - p.,, (S)l denote the total variation distance between Dj and D2. For two continuous distributions D1, D2 both over Idd, use X (D,, D2) Jg D, (xxx)/DDxxxx
1 to denote the chi-square norm of D w.r.t. D2-
For distribution D on space X and measurable functions f1, f2 X - Rd. we define their inner product w.r.t. D as D del (xx) (x))), and define the L norm of a function 1/2 I w.r.t. D as || def ( For two distributions D1, D2 over X1, X2, we use D₁ @ D2 to denote the product distribution over X1 x X2.
For a subset S S ded with finite measure or finite surface measure, we use USS) to denote the uniform distribution over S (w.r.t. Lebesgue measure for the volume/surface area of S).
We use 1 to denote the indicator function of a set, specifically 1 E S) = 1 ift E S and otherwise. For joint distribution D of (x, y) over X' x x), we use Dx and Dy to denote the marginal distribution of x and y and use Dxlymy' to denote the conditional distribution of x given y s/ (we will use the notation Dxly as a shorthand when the variable y is used in the context). Let (H, Σ) denote the d-dimensional Gaussian distribution with mean μ E Rd and covariance Σ E Rddxd For simplicity of notation, we use Na for the d-dimensional standard normal 10.
Basics of Hermite Polynomials We require the following definitions.
Definition B.1 (Normalized Hermite Polynomial). For E N, we define the k-th probabilist's Hermite polynomials Hes IR + R as Hex(t) (t) = ef at -2/22 We define the k-th normalized Hermite polynomial h4 R + h2 (t) = He, (t)
de
Furthermore, we will use multivariate Hermite polynomials in the form of Hermite tensors (as the entries in the Hermite tensors are rescaled multivariate Hermite polynomials). We define the Hermite tensor as follows.
Definition B.2 (Hermite Tensor). For &o e N and x E Rd, we define the k-th Hermite tensor as
(H& (x))ss.te....
Σ
(-Ii
X
kd!
Partitions P of [k] size and
ta.btEP
lctEP
For function f Rdd RR and E N. we use f to denote f5((x) -x H (x)). where
A (x) which is the degree-l approximation of S. We use f to denote its residue. We also remark that both our definition of Hermite polynomial and Hermite tensor are "normalized" the following sense: For Hermite polynomials, it holds || = For Hermite tensors, given any symmetric tensor A, we have (A, (x)) (A, A)
f
23

---

C
Statistical Query Lower Bounds
In this section, we establish our SQ lower bounds for learning Multi-Index models, thereby proving Theorem 1.10
Organization. The structure of this section is follows: In Section C.1 we define relativized version of non-Gaussian Component Analysis that is appropriate for supervised learning tasks and establish an optimal SQ lower bound for it under appropriate conditions. In In[Section C.2 we leverage this general result to show our SQ lower bounds for learning MIMs, for both the realizable and the agnostic settings. Finally, in (Section C.3] relate the conditions of our SQ lower bounds for learning MIMs with prior complexity measures the literature.
C.1 Statistical Query Lower Bounds for Relativized NGCA
In this section, we prove SQ lower bound for Relativized Non-Gaussian Component Analysis (RNGCA). The main result this section generalization of Theorem 3.3 handling more general label spaces and approximate moment matching. We leverage this technical result in the following subsection to prove our main SQ lower bounds for Multi-Index Models.
To be compatible with more general label spaces, we start with the following definitions generalizing the relativized cudden-subspace distribution of Detinition 3.T and the hypothesis testing version of RNGCA of Defiiiion 3.2] The main difference here is that we replace the space IR", appearing in Definition 3.1 and Definiton 3.2] with general space y.
Distribution; Generalization of Defintion 3.1). For joint distribution A of (z. y) supported on I x x and matrix E Od,k, we define the distribution P as the joint distribution of (z'.y) y²) supported on I y such that
Definition C.1 (Relativized Hliden-SSubsppp
1. the joint distribution of (U' x', () is A; and
2. zy is distributed according (O, 1I independent of the value of (UTz) 2/)z)), where U is the column space of U and (O Hy is the standard Gaussian projected onto U-.
We next give the generalization of Definition 3.2
Definition C.2 (Hypothesis Testing Version of RNGCA; Generalization of Definition 3.2 Let
> 2 be integers. For a joint distribution A (x, y) supported on _ x V, one is given access to a distribution D such that either: Ho: D Na @ Ay. or Hi: D is given by PA where U ~ U.. The goal is to distinguish between these two hypotheses Hy and H1.
For the hidden distribution A in the definition of RNGCA, the lower bound construction here re- quires that the conditional distribution of Axly is well-defined for every y. order to ensure that this conditional distribution is well-defined, we first introduce the following technical condition.
Definition C.3 (Regular Distribution). Let be a joint distribution of (x, y) supported on R$ V. We say that A is regular if there is a family of distributions Axly on RR for each
such that for any measurable S of A, Pr(x.y)~A|(S [(x, y) 8] -Ja Prx-Ani [xx, v) E S]dy We will call such distributions Axly the conditional distributions of x given y. Remark C.4. Note that A is always regular if y RR,, which is Polish space.
Our SQ lower bound construction crucially relies on the assumption that the conditional dis- tributions Axly approximately match their low-degree moments with the standard Gaussian, ie., that A has similar low-degree moments with Nig X Ay. Roughly speaking, for each conditional distribution Axiy. we characterize the mismatch between Axly and the standard Gaussian as supp (Ex~Ac,, [p(x)] Ex-Aa [p(x)]). where p is any low-degree polynomial with Ex-N; [p(x)=] 1. Then we take the L norm of this quantity over the marginal distribution A,, as the overall mismatch between A and N₁ & A.. as described in the following definition (generalizing the exact wooment-matchinn in Definition 1.9).
Condition C.5 (Relatively y-Matching Degree-m Moments; Generalization of Definition 1.9p. Let
0 < V < 2, m E N, and A be a regular distribution of (x. y) supported on IR. x X. We say that A v-matches degree-m moments with the standard Gaussian relative to y if for any f RR x y R such that
24

---

1. the function f(r,)) is polynomial of degree at most m for any y E V; and
2. II Il I 1, where Ay is the y-marginal of A and No. @ Ay is the product distribution of N and Ag
it holds that (x(x,))Alf(xx y)] B(x.))-M4 [f(x y)1l v.
With this context, we are ready to state our main SQ lower bound theorem for RNGCA. Roughly speaking, we show that for any regular distribution A that satisfies [Condition C.3 there is an SQ lower bound for RNGCA using A as the hidden distribution.
Theorem C.6 (SQ Lower Bound for RNGCA; Generalization of Theorem 3.3p. Let X E (0. 1)
and d, k, m E N with m even and k, m S d Let 0 V 2 and A be a regular distribution over R x y such that A y-matches degree-m moments with the standard Gaussian relative to y and d be at least sufficiently large constant depending on c. Then any Let 0 < e < (1-x)/4 >)/4
SO algorithm solving the d-dimensional RNGCA problem with hidden distribution A, as defined in Definition C.2 with 2/3 success probability requires either query to STAT (T), where
Ok.m (d (d-((1-)/44 m) + (1 + +[])),, or 2d many queries.
To prove the desired lower bound, we need to show that for any query function I' the algorithm selects, over the choice of the hidden subspace U ~ (Oa,k). ). the expectation (x [f,, y)] is concentrated around E(x.,)~N,8.4, L/ (x(, w)]- Therefore, the algorithm cannot tell if the distribution is the alternative hypothesis distribution P. the null hypothesis distribution Na @ Ay.
Such concentration result is given in the following proposition.
Proposition C.7. Let À E (0,1) and d. ki E N with m even and k.m S dd. <RO<D<> and A be a regular distribution over H& x y such that v-matches degree-m moments with the standard Gaussian relative Y. Let O- < c < (1 - 2)/4, d be at least sufficiently large constant
depending on and J: Bd x y [0, 11. Then it holds that
Pro-U(Oa.))
E Px (f(x v) - E(x.))NN (1 (x, 2 27] s 2-
where
[(mm/2 / k/2) d (11 + (1+o
T(k/22)
Given Proposition C.7 the proof of Theorem C.6 straightforward. We just need to show that for all the queries the algorithm makes, with high probability, the expected values E P( (f v)] and Exx,))~N.AA, (x, y)] are always close to each other for any query function f. Therefore, the SQ oracle can always answer the queries with E Exx.))~N.04, [x v)] and the algorithm cannot differentiate between the alternative and null hypotheses.
Proof of Theorem C.6
Suppose there is an SQ algorithm A using q 20)) many queries of accu- ((1-))/4-c)m + (1 + (()) and succeeds with at least 2/3 probability.
(m//246/2)
racy T
T(k/2)
We prove by contradiction that such an cannot exist. Suppose that the input distribution is Na & Ay. and the SQ oracle always answers ((x.))~Nae4A, [f y)] for any query f. Then the assumption A implies that it answers "null hypothesis" with probability > 2/3. Now consider the case that the input distribution is P and ~ (Oa,)). Suppose the SQ oracle still always answers E E(x.))~Nv.0,, [f(x, y)] whenever possible. Let fi...., fg be the queries the algorithm makes, where y 200()) for a sufficiently small implied constant in the big-O. By Proposition C.7 and union bound, we have
Pro-c(os..) [ E [g), (e), (x.)) (xx v)] Exx.))- (x, v)]l 2 r] = o(1)
Therefore, with probability 1 1-o o(1) the oracle will be able to always answer Elf: ( A,)]. From & assumption on A, the algorithm needs to answer the "alternative hypothesis" with probability at least (1)).
But since the oracle always answers Pxx.y)~NaAAA (fi(x, (which is the same in the above discussed null hypothesis case), we know that the algorithm will return "null hypothesis" with prob- ability 2/3. This gives contradiction and completes the proof of Theorem C.6
D
25

---

The rest of the section is devoted to proving Proposition C.7 In the next subsection, we will first show that in order prove Proposition C.7 it suffices for us apply Fourier analysis on the dis- tribution A', modification of A (for convenience of the analysis) that has bounded total variation distance with A. The approach here shares similarities with [KRS233). Then, Section C.T.2) we put everything together and establish Proposition C.7
C.1.1 Fourier Analysis using Hermite Polynomials
We will first try to use Fourier Analysis to analyze the value of (ol,)) v)]. We can calculate Ex-Pa [f y)] by its Hermite decomposition as stated in the following lemma.
Lemma C.8 (Fourier Decomposition Lemma), Let A be regular joint distribution (x,y) supported on R x y U E Ra and U = Ig- Then for any f R y + RR and E N,
((xx))pp [f(x,))] = Σ U A.))) ((())), + ((x)))PP [x**(x,u]]
1=0
where A,(y) = Ex~Axio (x)) and T,(y) = Ex-ra [f y) Hx)) and f> =
(fl: (f(,)))>'(x)
Proof of Lemma C.8 The proof of the theorem directly follows by applying the law of total expec- tation on Lemma 3.3 from [KRS23). We first state Lemma 3.3 from [KRS23 below.
Fact C.9 (Lemmaa 3.3 of [DKS233) ) Let A be any distribution supported on IR U E gdck and
U U L. Then for any E,N,
E ExPPa [f()] = Σ
( U Ex (x)),, Nx (x)) + (xxx)-P [f²((x)]
Applying the law of total expectation, we get
E (x.) P
[[xx v)]
= -Ey Ey-A,
E (x [x)
= -Ey~A,
E
x (Axiz) u)]
E
(U Ex (x)),, [x y), H), + E
(x (mm)) [V[ ((()0)))((x))
=Ey-A,
Σ (U (S T,)) + (x (AmD) [(((,)))>*(x)
Σ (U + (xWN) (x,
1=0
This completes the proof of Lemma C.8
We note that, ideally, would like to have
E (fxx))Palfxx,.. v)] = Σ U A, T.)Ay
(1)
1=0
However, Equation (1) is not true in general for technical reasons. Namely, it is possible that (A, 3 Ay) is infinite (this is true even assuming Ax Na); therefore, the convergence in Equation may not hold (see Remark 3,4 of [DKRS23] for more detailed discussion). Instead,
26

---

we will show that for a sufficiently large we can have 11 be arbitrarily close to O. Com- bining this with some other technical facts will suffice to obtain that (x,))- [f y)] is also arbitrarily close to O. Now notice that
(U Ao. To) = B Bx-NN = (xx,)-)e,,,11(xxx
Therefore, the quantity we want to bound is just
((x.)) [x v)] Bix.))-assalf(xxx)) Σ ( A, T.),, + Bxx [x y)
As we have mentioned above, for sufficiently large 1, the second term (x.x))pp [f=t(x, b)] will be arbitrarily close to O. Therefore, we just need to bound the first term (U A,, A.)
To bound E (USi (USiA,, A,, A, notice that
Σ 111
A, T < (A; (UT) 01 TWA, S
| MaAll,,1(00 ([ @0 ) TTlll
1=1
To proceed, we just need to bound the terms ||illa, and [I(UT) @1 T TillA, for all i. We first tablish the following fact, which can derived from Lemma 3.7, Lemma 3.8 and Corollary 3.9 of DKRS23 This fact bounds from above the ath moment [I(UT) 80 Till%, and implies that ( @4 Tella, is o(1) with high probability.
Fact C.10. Let i, ki d E 24 with & d, a E 24 be even and i' ai/2. Let be distribution over y and T y - Rd Then
i'tb 2 [(=+td)
(5)
EULD(OZ))
[I(UTT (W) =0
[T(]))
Furthermore,
EV-U(Oa)) [II(UT) (I(UT)&TT(Vlll T(o)) /2d max(k: 11)2- [
In addition, if there exists some constant e (0, 1) such that k S de < i', then
((++d) + (d-R)/2)
Eust(oan (I(UU))"T(T))ll = log d))
[T())
27

---

Proof Fact C.10
Notice that
EU-U(Oa,)
9/2
=Ou-U(Oa.
EyeD
a/2
E =Bu-U(O..)
T(;))
Ya. We//a~Doana
a/2
-Eu-U(Oa.))
y Ma/22 Mo022
(U (UT) 87/88//22
T(y))
j=1
(Uent/2 U T
a/2
822
-Eu-U(Oa))
E Marr
T(ys)
Ø=1
827
a/2
< EU.U(On)))
(
T(y))
spectral
Ou.)
USai/2 (U |0at/2 (UT)///
ByND
[T(p] 02 Sa/2
spectral
O..)(O..))
(U 801/22
B
T(y) 82
spectral
0/2
OU~
USai/2(U) (UT))a//2
@ai/2]
E B
(T2y)
spectral
Eu-u((..)))
USai/2 (UT Sot/2
[T (y
spectral
[ (UT) 8aai2] specttal for the spectral norm of EV- [Usai/2 )oni/2] which we consider as a (IR jo0ai/2 x (I y symmetric ma- trix.
where we used the notation EU-U(Oa)))
Therefore, we just need to bound [EU)C(O))) (USa:/2(UT) (uT)/ Ispectrall The calculation here follows Lemma 3.7 of [DKRS23] Namely, let A = Eu-u(o..)) (USai/2(UT) (UT)). To be the eigenvector associated with the largest absolute eigenvalue, and let u argmax a ( u S. Then, we have
|| 2 =| (ATo, //t/2 u Sai/2)| (To, Au
Sal/2 1/K 1ai/22 //KKT
(To, Eu
(UUTu 0/t//1\1 (T S
Eu-U(O..... (To, (UUTu) 0 /0t/ To Kasie8
u
000 To
Eu-U(O
(UUT 0
(To: @ai/2
/I u
EU-U(O
0ot/2
-EU-UO m.
|
m/// mi/2
where we used u = argmax (To, u Sai/2y in the second inequality. Plugging everything back into the representation for EU-U (UT) Tiee pp) we get
EV-U(o (Il (UTT" o < Eu-rion
| 0i/2
T |
y
Therefore, it only remains bound the term EV-U(NN Lemma 3.8 of [DKRS23 stated below.
which can be bounded by
28

---

Fact C.11 (Lemma 3.8 of [DKRS23], ). For any even i E N, and u E S 1 we have that
Bur Uul =
r itd (
Plugging it back into the equation right before this fact gives
r+ r
(1)
EU~U [I[(UU))TTTT (y)o(
IT(2)l
" r
(5)
r('4 (()) 1 "1 ((())
The remaining statements follow directly by simplifying the term the exact same calculation in Corollary 3.9 of [DKRS23].
which follows via
Given that ) @4 Tella, is o(1) with high probability discussed above, we just need to show that || = |Bx (x)]lla, does not grow too fast with respect to compared to ) 60 Ta Illay. so that the summation converges. However, for general hidden distribution A, the quantity ||A,]| A, is not bounded. To overcome this obstacle, we leverage an idea from [DKR223. Specifically, we can truncate the x part of A inside ball to obtain distribution A'. This incurs negligible total variation distance error between A and A' and forces |[E HH, (x)]ll,, to not grow too fast with respect to i. We can then proceed with the analysis with respect to A' instead of A.
However, this naive approach of directly truncating x will not work in our context for the following reason: this truncation also changes the marginal distribution of y and the norm we need to bound (we now need to bound || ||A;- instead of -IlA,). To overcome this issue, we will do a proper im- portance sampling y after the truncation, so that the new distribution A' is close in total variation distance to A and has |Ex~ALip (x)]]l bounded. Since the total variation distance between A and A' is small, if we show SQ lower bound for the RNGCA problem with the hidden distribution A', this implies an SQ lower bound for the RNGCA problem with hidden distribution A.
For B E R_,, use BB* (BB C R to denote the ball defined as (B) def {x E IR* We first give the following definition and lemma about A'.
||||| S B}.
Definition C.12 (Truncated and Reweighted Distribution inside Ball). Let A be regular joint distribution of (x, y) over & x y and B E R.. We define the truncated and reweighted distribution A' as the joint distribution of (x', ./) supported on TB BB(BB) x y obtained by the following process.
We first sample y' Ag. then we reject the sample with probability 1 Prx-A If the sample is not rejected, then we sample x' Axly==//xxe**(B)
[x E BB (B))²
We note that A' is by definition a regular distribution since it is defined by A for each and A', is also well defined. We now give the following lemma, which shows that A and A' are close in total variation distance and Ex (x)]l),, is bounded.
Lemma C.13. Let k. m N with be even. Let O
and A be a regular distribution on R x y that v-matches degree-m moments with the standard Gaussian relative to y. Lel B E R. such that Bm 2 ei 22//2 T(m++k/2) where er is at least a sufficiently large universal constant. T(k/2)
Let A' be the truncated and reweighted distribution over B (B) x V, as defined in Definition C.12
Then we have that
dry (A, A') = O (2m/22 T(m+k/2)
m-; and T(k/2)
29

---

2. For any i E Z+,
2011) (2m/2,
T(m+t//2)
Bi-m
1(k/22
Ex Ex H[x)]
A,
+ +(1+0 2mm
T(k/2)
B-T
V,
i <
2010) (2m/2
[(m++/22)
Bi-
i2
T(k/2)
Proof of Lemma C.13 We first bound drv(A, [, A'). For convenience of the analysis, we define the distribution A as the distribution of (x, y) A conditioned x TBK Since drv A') S (Av(A, A) + drv (A, A'), suffices for us to bound each term separately.
We first bound drv (A, A) using the fact that A y-matches degree-m moments with the standard Gaussian relative to V. Namely, we have that
E(xxy)> | = Ex [| + v Ex [||||
E ((k) [1m1/]] + ' (x) 1CT11//2
2m/ I((m + +1)/22
I[(2m + k2)2) r(k/22
+ 2m/
T(k/2)
T(m T(m+k/2) T(k/2)
So² 2m/2
where C2 is universal constant. Using Markov's inequality and the union bound, we have
I(m + k/2)
Prix.g)aax B (B)) S 02
22m/2
B B"
T(k/2)
By the definition of A, have that dIv(A, x 2/m+ B B-m
Prixa)aaX
BT(B)) <
2m/2
T(k/2)
Then, for drv (A, A'). notice that Axly and A'yn are the same for any y. Therefore,
AA) <drv <drv(Ag
(Ay, Ar) S drv (Ay, + drv Av) I'm + k/22)
=02
2m/2
B B- + drv Ag)
r(k/2)
So we just need to bound dTv(A') Ay).
From the definition of A', notice that
dTv Ay) < =E EynA, A, Prx [X BB((())
E EynA, [2PrxAA
B (B)]]
T(m + k/2)
2F xx (B)] 20z
2m/
B
r(k/2)
Combining the above, we get drv (A, A1) 402 (2m/2
[(m+k/2) T(6/2)
B-m.
remains verify the bound on Ex
(x)]
We will analyze the cases < i < and
Ar
i 2 respectively. We first prove the following bound that will be convenient for the analysis that
30

---

follows. Notice that, by the definition of A', we have that for any function f: IR + R
Ex A/1 [f(x)]
27 1/2
E Eg
Ex Ax [[(x]]
Ex [[(x) (x E (B)))) Pr [x E B* (B)] 2 1/2
Ey
(2)
[| [f(x)] E (B)]]] 1/2
EynAy PrxxAAe [x [B)
= Eynd,
$ f11f(x)1 (x |l,, (1 (1-2Prig (1-22P(xM))AA (B)))-
T(m + k/22) T(k/2)
1+
2m/2
B-
[|5(2)) (x
where the last equality follows from the earlier bound that
Pr(xa)~A xx B*)("))) S c2
2m/2
T(m + k/2) T(k/2)
B-
and the assumption that Bmh
2 c1 22m/2
T(m k/2) 1(k/2)
Given Equation (2), we have
E Ex
[H(x)]
I'm + k/2)
-11+0 1+0
2m/2
B
Ex-Axin [[()] (x (x)B((B)
T(k/2)
Therefore, we just need to bound Ex~ANI
H(x) (x B*()))
For the case S k < notice that
Ex~AAlv
H(x)1 (x E (B))]
ExrAxiv
H(x)]]l Ay + Ex [((x) (x & B* (B))]]l
<V + Ex
([) Il (x (B)))] 4,
To bound the second term, we will use the following fact from DKRS23
Fact C.14 (Fact B.1 of (DKR223), ) Ler H, be the i-th Hermite tensor in k dimensions. Suppose that ||x||2 2 1/4, Then [H 11 20(0) |
Given that mm
c₁
22//2
l(m++/22) T(k/2)
Fact we have B² > k. Therefore, using Fact C.14
get
Ex Ex
|(())l (x # B
ExnAdty
2000 [
(x E B (B))
Ag
<0)
EX ||x||| (x & B (B))]
PrxZAui ||x||2 2 un & Ba (B) du
<0 /
||Prx~AM ||x|12 2 uix B (B) A, du-
where
PIxwAMI ||xx||2 2 w||l uillA, - Ex |||x| /
1 11 Ex [||x||2]] m
31

---

Therefore, using the earlier bound on Ex~Axx [||x|221| Al, A," we get
Ex-Axio
[[[(())]12 1 (x & B² (B)) A.
I'm + k/2)
$2
22//2
min B m u )du'
T(k/2)
7(m + k/2)
11
B-ndd du / u ammdd
$20(0
2m/2
T(k/2)
T(m + h:22
<20()
2m/2
Bt-m
T(k/2)
Plugging this back in the ealier equation for
Ex
[H(x)]
get that for 1 siic m,
7(m + k/2)
Bx x/N
H(x)
=20(
2m/2
B
A
T(k/2)
I'm + k/2)
1+0
2m/2
B
T(k/2)
Now bound || [Ex [x)ll]lla, for i 2 m. For order-i tensor A, A T to denote the matrix A
f1 du A r(n on de) and A 1 || 2|2. From the definition of the Hermite tensor, we
have
1 1/2
H(x)
Σ
2' 21)! (1-1)8xe011-2))
Vi
Permulation a [4]
This implies that
Ex H (x))
A/
[//2]
1
Σ
1
(1-1)
( Ax (x0(6-20))
2'el(i 2t)!
t= Penmutation
1/2
Vil
(9 l12
Ex
20 20)
2i
2t)!
Ag
1/2]
ViI
0 112
Ex
(x)))-20)
||
2it!(i
21)!
14
1/2]
Vi.
|
E Ex
[||x||_211
2i
2t)!
13
$/2J
Vil
1/2 Bmmax(- (-- 1-m-2mmm-0000
Ex Ex
||x|| min((m.--22)
2tt!(i
2t)!
1/
4/2]
Vi!
m m3/4 (imax(i-m--- m 20 (max(0.2
ExnAbin
||x| puin(m.
2it!(i
2t)!
A6
[1/2]
Vi
<B'
(0
Ex
[|x|] [|x| (2)
201((i 26)!
where the last inequality follows from the fact that B² 2 (which, as already noted, implied by the fact that mm 2 01 (2m/2
T/m+k/2)
T(k/2)
32

---

We now bound the term ExnA'an 2210
||x1| mm (om..mm.)))
For convenience of the analysis, let Notice that the quantity we want to bound
m' = min(m, i 2t) and f(y) = Exndxiv
[
|l lla Furthermore, using the fact that A' v-matches degree-m moments relative to y with the standard Gaussian, have that
Ilff = (xx))~ [(U))
s ((x.)~M.. [())l (I][(()) IIA
By (f Ex [Ix v Ex-iNe [|x12mm 2mm2 1/2
Ex ||x Ex || w/l Al, Excon ||x|
||x1 mm 1/2
Ex (ominillxx11 + vilf Il Exmri [|1x 1/2
Bxx<all>>133 EE
= -Ex~Ni || EE
[1x11_m]]
Ex wilf IA; Ex | 20m
Since v 0(),, we must have
[|x|12 1/2 )1z2)
A =
max
(Ex~sxll<x|E"" Ex
Notice that both quantities can calculated using the x" distribution. From previous calculations, we have that
[|xx|3m0] 1/2 2min(m,.-200/2
1/2
T(min(m, 21) k/2) r(k/2)
E Ax [Ixx[12) S Excrs
Therefore, we get IfllA O (2min(m.i-22)/2
[(min(m. (m.i (m0mmmmmm222))+2) 22)++/2) [(k72]
Plugging back in the ealier
representation for Ex [x)(
gives
Ar,
H. E M/j
A/
[1/2]
Vi!
T(min(m, 21) + k/2) T(k/2)
<Bi-
mmax(022--44m)44
2min(m.i-20/22
2it 2t)!
I'm + k/2)
[//21
Vi
<Bi-mo
2m/2
T(k/2)
20
2/Y!
where the second inequality follows from the elementary fact max(0, 2t 2t) +-iimmmimmmm i22)) One that the denominator is minimized when i/2 O(vi). Then it follows that the sum is most 20) Bi-m
2m/2
T(m+k/2)
T(k/2)
This completes the proof of Lemma C.13
Recall that the quantity want to bound is (x y)] E,x.))-W,ss y)]l- Given that A' and A close in total variation distance, we have that for any U Oa the distributions PA and PA' are close in total variation distance. Therefore, for any query function f ddd y [-1,1], (x (f(x, v)] (xx,))~p [f y)] is small and (xx.s) If(, v)] ((x,))-Na [f v)] is small. Thus, we can bound E (x. [x y)1 ((x,)) [x v)]l instead.
For that it suffices for apply the Hermite decomposition Lemma C.8 A' instead of A and analyze E (U@i A,, T.)a where A, = Ex-AA [H, [x)] We give the following upper
bound on (U A,, T.
33

---

Lemma C.15. Under the conditions of Proposition C.7 and further assuming m, k S d log d,
V < 2 and [[mm/24//2) d1) < 2, the following holds: For any d that is at least T(k/2)
sufficiently large constant depending on e, there is a B such that the truncated and reweighted satisfies
distribution A' over (BB) x y defined Definition C.12
(T(m/2 + k//2) T(k/2)
d (A)
d ((((1)))4-o))m
Furthermore for any E E4, except with probability at most 2 dlte) it holds
with respect to ((o,,)))
Σ (A (UT)O
- (1 d' d-((1-A)/4-0)m +(1+
(Tmm/2+k/2)
T(k/2)
where A:(y) = Ax Aix
(x)) and Tv) (f
Proof. For convenience in the relevant calculations, we will break the summation into four ranges. We can write
Ai
V
T A
A; (V)
dAa
Ai (V 81 T;
Ai
(V
84
T.
1/
14.
im
AA (A. (VT)
T: A
Σ
Aii
T;
Ag
i=1+1
where T value we will later specify. To analyze each K (A..(V)) (VT) 8i T; recall that
(A..(VT 81 T,) $ &|AAll (VT)
@i T
where A; = ExmAK (x)) is a constant
(not depending on the randomness of V). For (v
Si T
we can show it is small by bound-
ing its a-th moment for even a using Fact C.10 ranges of i.
We will apply this strategy on the four different
Without loss of generality, we will assume that À 2 4c. Suppose that À < 4c. Then we can simply consider new pair X',' where X' = À + 2c and c' = c/2. Notice that (1 X)/4 - (1 (1-X) /4 c'; therefore, the SQ lower bound in the statement remains unchanged.
We start by picking the following parameters (the "sufficiently close" here only depends on c):
We require m, k s / (//log/d d;
= d where a < (1 - >a) /4 and (1 Aa) /4 - a is sufficiently small constant fraction of G
T = maax(2a.A);
We let λa X2 A₁ > À to be sufficiently close (the difference between these quantities will be a sufficiently small constant fraction of c).
(VT) 84 T:),, 19 We now bound the summation Ein (A.. (VT)
as follows:
Em < A: (VT)* 88 T, Ag
(VT)&
is small with high probability:
34

---

Since
T(m+k/21 d' ((1-A)/4-))) c)m < 2 and B d², where a sufficiently close to (1 A)/4. T(k/2)
the parameters satisfy the condition 8Th = w 22m/2
k/2) in Lemma C.13 T(f/2)
Since < m,
by Lemma C.13] we have
7(m + k/2)
I(m - k/2)
|| A/ 20(0)
2m/
B B=n + 1+0 2m/2
B Bm
T(k/2)
r(k/2)
Let a be the largest even number such that ai/2 S d=, where m = o (d*)) implics a 2 2. Then using Fact C.10 we have
Ev-u(Oa))
[|(V))
84
T 1
0
aa-//ad--- = -
Using Markov's Inequality, this implics the tail bound
@+ T: T:llag 2 d (1
= =2 2- < <2-0((d")
Pr
Therefore, we have
Ai (VT) Tx
AAillA (VT) T
15
m
I'm + k/2)
(1
(1-22)1/4201)
2m/2
Bi-m
r(k/2)
T(m + k//2) I(k/2)
d (1-12)1/4
1 1+0
2m/2
B-m
+ T(m+h/2)
o(1+
2m/2
1-m +
T(k/2)
T(m+ + +x/2) d-am +
=(1+o(1))
2m/
I(k/2)
except with probability 2 2000
@i T small with high probability: E (A,, (VT)
dd
In the previous case, we have argued that the parameters satisfy the condition Dr
+k/++ T(k/2)
in Lemma C.13 Since k 2 m, by Lemma C.13 we have || Ar, =
20))) 22m/2
Bi-m Let be the largest even number that ai/2 I d², where m (d*) implies a 2 2. Applying Fact C.10 yields
T(m-k/2 ((722)
aa AC
- (d-(1-AijajAA)
EV~U(O,)))
T
O
-0
Therefore, we have
Σ Ais (VT) 60
(T,
|Aill 10,,,1(11 (VT) 60 TT: T:IlA
Ag
d²
T(m + k/2)
Σ
d (1 (1->23k/42003 22/22
Bi-m
I(k/2)
i=
(mm) d -(1->2)/44) = ((1->))))))
35

---

except with probability 2- (the first equality above follows from B = =d = o (d(2 (d)1-A))/4)).
Eimer (A A (V
T;
is small with high probability: We assume without loss of gen-
erality that dd < T, since otherwise, this term is just O. Notice that this implies that A < 2a. We will then use Fact 3.5 of [DKRS23 to bound ||A.IIA,
Fact C.16 (Fact 3.5 of DKRS23)). ). Let H, be the i-th Hermite tensor & dimensions. Suppose H. (x) - 2 13//////--00 B4- exp (G)/B²).
that ||x||2 S B. Then
Using Fact C.16, we have
||Aill
[x]]
Ex [H,())]
= ||Bans (
AG.
52 exp exp (() / B2 < 220(0 (0000)//Bi--111
where the last inequality follows from (B)B² < iT /T/B B² / /B² Then, let be the largest even number such that ai/2 < T, where i < T implies 2 2. Applying Fact 1. 0s/4
|| 84 T N/
( d ai
Ev-
o (2ai)(ai//2d
0
which implies the tail bound
T. Tillay d (1-( d Xai/4 <2 9(())
2- 2 22(((()
2 2
Pr
Therefore, we have
T
T
Σ
(VT) 60 T; AG Ai, (VT)
S
Σ
||Ailla
001 T AC. 1/////101 (VT)
i=d++1
i=+++1
T
20(k) B/ // (11-))/48
i=d++1
T
(k() B (11-))/4);
i=d++1
=0 [B d (1 ((1-)\)))((++1)) =d -(((d)))))
d Meem log < dm
except with probability 2 n00) where the third line follows from > d=a k. (A... /
Ei=r41
(V Si T
is small with high probability:
We will first need Fact 3.6 of [DKRS23 bound AAsl
Fact C.17 (Fact 3.6 of [KRS233
Let H, be the i-th Hermite tensor in k dimensions. Then
1 + k ++
H (x)
cxp((|x|2/4))
k k-1
Combining Fact C.17 with the fact that A' is bounded inside B (B), we have that
(Aill A4, E Ex [x)] - Ex-rx (x))
Ex
H [x,])]
16
A
( 1 k: - -1 I 201)
1/2
h-1 exp (B2/4)
36

---

We pick = 2. Note that ai/2> T = d'max(2n.A), Applying Fact 1.10 yields
[[(VT] 8i T; 1
(
dd i+d
(d-k)/2)
Evr)(
= exp (xp(-(((Tog d)) O
Applying Markov's 's inequality yields the tail bound
Pr (VV))
84 T A6
22
aaTTloon log O
((++) (d-k)/s)
(T+d)
)
(T+6 d i+d
2 2-d0(o)
Therefore, we have
A (V)) 01 Tz
A/2
$
<A.: A (VT) @i T;
S Σ
||A.l|
0+ T: A/ (V
A/
1=
T=
20(k)
(i+ k - 1)
k - 1 1)
1/2
exp (B² /4) (0(T
+ d) itd d
(d-i)/5)
T+
T k. 1/2
i k T k.
k/2
T + d (itd d
(d-1)/5
(T lo
k
i+k
k/2 (T + d'
d/8
2-
(T logn)
T+k
i d
T=T
where the last inequality follows from our choice of parameters. Therefore, we have that
Σ A1. (VT)
TT))
[+ [1+ 1+i-T) T k/2
1+ (1+ 1+1-T
i-T
-d/8
19
T + k
T+d
im T
2
D( logd)
1+ T -
i-
(2/2)(2d/T)
(1+ i i-
-4/8
T +d)
1= T
1+ i- i-T T
d/8+dk/TT
2
Q(T log d)
T+d
1=T
-d/16
d
2 (ogg)
<
T+d
1=T
-d/16
d - i
<2 2 D-- d)
di
T 7++ d
i=
(T + d) -d/16
= -(TTool d)
(d/16- 1) (T + d - 1) d/16-1
= Q(dp))
37

---

except with probability Σi=r
Adding the four cases above together, we get for any m, h - d / log and at least sufficiently large constant depending on C,
T+d i+d
2 2-
=2 d'to)
2-
As: (VT) 60 T; 1/,
<(1 + +(())
22m/2
[(m + k/2)
T(k/2) d dam + + + ((1-As))/4)m + +dd +2 2-0(dd
Tmm/2 + +k/2)
((1 (11-A)4-</23)) + +1+
T(k/2)
T(m/2 + k/2)
d (1(1--)/ + +1++
T(k/2)
except with probability 2 )f where the second line above follows from F(m/24k/2) T(k/2)
T(m+k/21 2m/2
This completes the proof of Lemma C.15
T(E/2)
C.1.2 Proof of Proposition
We are now ready to prove Proposition C.7 which is the main technical ingredient of our lower bound. Proposition C.7 states that ((x.)) (f, (f(, Wxx.))~Nas44,fff y)] is small with high probability. The main idea of the proof to use Fourier analysis on E (xx))) [f(x, y)] we discussed in the last section, where A' is the distribution obtained by truncating and reweighting A (see Definition C.12) and is close in total variation distance.
Proof of Proposition C.7 For convenience, we let Ç (1 A)/4 c. We will first truncate and reweigh defined Definition C.12 and then apply Lemma C.15 Notice that Lemma C.15
2. We show that all these three conditions can be assumed true without loss of generality. If either the second or the third condition is not true, then our lower bound here is trivialized and is always true since f is bounded between [1]. For m, k S d' /log d, consider a X' > À such that (1 X)/4 - Ç that for any sufficiently large d depending (1 A)/4 /4- C.
additionally assumes k d> /A/log
2 and (Tmm/2+k/2) d
r(k/2)
(1-2)/1-5 Then it is easy have m, S d² log and Ç S (1 A)/4 - Ç. Therefore, we can apply Lemma C.15 for X'
Now let B = d where < <1 - A)/4 is the constant in Lemma C.15 Then we consider the truncated and reweighted distribution A', as defined in Definition C.12 By Lemma C.15 we have (A, < T(m [(mm2+k/2) d Cmn Given that f is bounded between [-1, 1). this implies T(k/2)
E B(x)) Lf U) E (x.)) [f(x, w)]
k/22) T(m/2 + k/2) 1(k/2)
<drv(Pd ddd -dv((A))))))
dIv(A,A)
d dm
Similarly, we have
E Exx.))-N,o4, v)] - - (fx.)-Nsxx,((xx...)
<dTv(Na Ag, @ A,) dTv(A,, A,) s dTv(A, < +/22) dm [(k/2)
Therefore, by the triangle inequality. it suffices for us to analyze the dif-
ference E Px [f(x - Mex.i instead of the difference E Exx,)>~P [x(x))) - Ex 1/ l/(x,
38

---

Let t= (d) E N be function depending only on the query function f and the dimension d (E to be specified later). By Lemma C.8 we have that
E Pxx [f y)] (A., (UT) (OUT)'iT (Ti)))TTT)))))))))
TT))A, Be Pxx))p If (x,y)) 8)
where (y) = Ex v. (x)) and Ty( (xx H and f²((x.1) = (f(,0))>E(x)) Recall that want bound
POW (f(x,)) v)] E(x,o)~ [x) w0]
with high probability, where we note that E(x.i) N, [x U)] (Au: To) Ar. Therefore,
we can write E Fix,))pg [f(x y)] - M( [f y)] - Ei (U )oT +
E (xx))pp''
For the first term, by Lemma C.15 we have that
(T(m/2+ + k/2)
AA (U (UT))
d=cm
d cm + +(1+
T(k/2)
except with probability 2 (ftc))
2-d
It now remains for us to show that E (xx)) [f (x, (x,v)] is also small with high probability.
Consider the distribution D Ev-u((,,))
U that Dxly is continuous for any y and (D, Aly) is at most a constant only depending on (independent of the choice of the distribution A).
We then use Lemma 3.11 of [DKRS23 show
Fact C.18 (Lemma 3.11 of (DKRS23). Let A be any distribution supported on (+(d) for d E 2, which is at least sufficiently large universal constant. Let D Ev~(((.,.) [P Then, D is continuous distribution and (D, O1()).
Now for our regular distribution A' supported on (d) x V, by applying Fact C.18 for each Ax|y- get that
E(r-UOOa [Pd] Na @ A1) - 1|x² (Eu-cioun)
P .Na 1 0(1)
1s
Therefore, we have that
Bu- (x> x)]l < EU [ (xw (x,
S D(xx))Dll(xxx))
$ XD @ A,) 12 11
< 1(d))S IN
We can take ( E (E only depends on the query function ff and dimension d) to be a sufficiently large function such that f| IINeAA
[(m/2+k/2) T(k/2)
Cm, Then we get
((d)
((mm/2+ + k/2) T(k/2)
EU-U(OZ)
E ((x.)) [f (x, w)ll| < 8(d))1f> ((d))))"(I 5--
d- cm
This gives the tail bound Pru E ((xx))-p' (x,(x))))] >
[(m/2+k/22) [(k/2)
d
d( [m 2-
Using the above upper bounds, we have
E ((xx))pd' [x()] - E(x,)) [f(x)] S El (Ai, (UT)STT))
+ E ExXPy [f2((x]] [xxpgg((((x)]]
T(m/2 + +k/2)
=2
d- + (1 o(1)),,
I(k/2)
39

---

except with probability 2 2 using the fact that c c= 0(1). Therefore,
(xx))-Pp - E(x.))-Nes,, 6 (T(m/2 2 k/2)
r(k/2) (
) d= 5m + (1+o()))
except with probability 2 2-d
In summary, notice that the above argument remains true if we take Ç' > Ç such that (1-A)/4-6 (1-A)/4-5, Using the above argument for Ç', and given d is sufficiently large constant depending on (1 A)/4 2((1 - A)/4 <'), we get
(Tm/2++k/2) d d + (1 + (11)), T(k/2)
(x [x()) E(x.)) [f()]] [f
except with probability 2- 2-00 X144 <'>
=2 2-
Reepacinng Ç with (1 A)/4 completes the
proof of Proposition C.7
C.2 SQ Lower Bounds for Learning Multi-index Models
In this section, we prove our SQ lower bound for learning Multi-index Models, application of Theorem C.6 We first give the formal statement of Theorem 1.10w
Theorem C.19 (SQ Lower Bound for Learning K-MIMs; Formal Version of Theorem 1.10p. Let be a class of rotationally invariant K-MIMS on IRd, Suppose there exist m E E4, T > O, and a joint distribution D of (x, y) supported on Rdd RR with Dx equal No such that for some subspace
V C Rd we have:
The distribution D y-matches degree-m moments relative to the subspace x R. where the extra R. contains the label;
Any function Rd + I. has (xxx))=D((((xv)) - -) 2 r; and
3. There exist B, 8 E 14 such that Ey Ey > B)] S 8.
Then, for m. K S d' for some X E (0, 1), dim(V) S d/2, e E (0. X)/4) and d at least sufficiently large constant depending within error T T 78 -3GB² given OPT S. iinfocc errp(e) requires either a query to STAT (C) or 2d many queries, where Ç =KKm (d-((1-A)/4-c)m) (1 + o(1))..
C, the following holds: any SQ algorithm that learns C
Some comments regarding the difference between Theorem 1.10 and Theorem C.19 are in order here. We first note that Condition 11 in Theorem C. 19 generalizes Condition ①I in Theorem 1.10
with approximate moment matching, as defined Condition C.5) We then note that Condition (3)
in Theorem C.19]t is required for technical reasons, namely assuming that the extreme values of
(i.e.. [y] > B) have contribution at most to the variance. Without such a condition, it is possible that almost all the variance of the label comes from an arbitrarily small mass of the input distribu- tion. For most applications, we will have B (LL and 5 2 2-((d), where L is the Lipschitzness of the functions in the concept class. Under such circumstances, Theorem C.19 rules out any algorithm that outperforms the best function in subspace V by some additive factor of o(1) (with respect to d).
Proof of Theorem C.19 The proof follows directly by embedding an RNGCA problem to agnostic PAC learning of the class C. Let A' be the distribution supported on Rd & Theorem C9 and W be the K-dimensional relevant subspace of K-MIM C that minimizes the error er
Let V be the subspace satisfying the conditions in Theorem C.19 and U Wy,, where Wy def (Wya w E W). Let U E Rdxdim(U)) and V E V be matrices whose column vectors are arbitrary orthonormal basis vectors that span the subspaces U and V respectively.
Let (x,y) ~ A'. We define the distribution A for RNGCA (Definition 3.2) as the joint distribution of (x', ()) over (ddi((U) x [V)m (with y = [ddim())F)) where ie., x' contains the part of the relevant subspace (of the optimal hypothesis) outside V and (x" y) contains V and the label Then we consider the RNGCA problem of Detinition C.2 with hidden distribution A and input distribution supported on Rd-dim(V). [ddm)[V)+1 By Condition in Theorem C.19 and Theorem C.6 by choosing the parameters X, in Theorem C.6 to be the same
U x and x" V x,
40

---

as the parameters X, in Theorem C.19 we have that any SQ algorithm that solves this RNGCA problem must use either a query to (C) 2id-diu(V)) ((d) many queries, where
< ==Odim(U), ((d dim (V + (1+ +1+
=0k,m (d- (d-(1-A//4-c)m) + (1 + o(1))
Therefore, we just need to show that the K-MIM learning algorithm described in Theorem C.19 can
solve this RNGCA problem.
Let A be such algorithm for learning Multi-index models and D' be the input distribution of for the RNGCA problem. First notice that D' can be equivalently thought of as a labeled distribution supported on Rdd x R, where we treat the coordinate corresponding to the y part as the label. Namely, we define the new input distribution D the joint distribution of (x, y) supported on Rdd x I. where x contains x' and all except the last coordinate of y' and y is the last coordinate of y'. We then give D as the input distribution to the algorithm A (notice that any SQ query on D can be answered with an SQ query on D'). Let h Rd + I be the output hypothesis of the algorithm. Then we will check the value of E(x.))>D ((x.)))=(((()))) [(((x) - y) 1 E - B. B)) to error at most CB². Notice that this can be done by using the query function (x, v) (h(x) 1) [- B)) with query tolerance Ç.
yx),y') supported on Rdd-di(()) [ddi(()+11
Now suppose that the original D' is from the null hypothesis distribution. Then, by the definition of RNGCA, we have that for (x', y") D', x' and y' are independent and y' has the same distribution as the marginal distribution of Ay', which is the marginal distribution of (V x, for (x, y) ~ A'. Notice that for any the algorithm satisfies that
E [(xx)))D((h(()) 1 I-B, BJJ Z min E ((x.)) x) 1 (-B, BJ]]
g:R-33
To bound this quantity, we will use the following fact, which states that if the squared error of function f is large and the labels outside of [-B, B] only have bounded variance, then there is lower bound on the squared error of on the labels inside [-B, B).
Fact C.20. Let A be joint distribution of (x. y) over X x IR such that for any function f: X - R, E(x.))~A(( Ily {x 2 and Eyn,, 2 [1y] > B)] S 6. Then for any g : X we have ((x.))~A(1)) 1(1 - g(x)) I-B. B)] 2 78
Proof of Fact C.20
Notice that
min ((x.0)~a(((x)) - 2)21(y E [[), g:X R
Ax~Ax [Pry~A, by E BJ (
Therefore, we just need consider the distribution of Ayix- For convenience of analysis, we give the following intermediate fact.
Fact C.21. Let D be a distribution of over R such that Var (D) 2 т and
Ey (1 [-B, BI)r²)
88. Then Pry~dly E [-B, BiJaa(D ly I-B, BJ) 2 7 76.
Proof of Fact C.27 S/B2, we have that
Applying the law of total variance and the fact that Pr Prywoly & [-B, B, B]] s
Prywoly E [-B, Var(D e B, BJ)
=Var(D) Pr Pr (y & [- B, B] Var o [-B, BJ)
- -Pry-Dly E - B, Pr Dly & [-B, B] (Bn-D By>DDye([ B. [v))
2T 8 - Pry~D 8-Pr & B, Ey B 101²
2Pry~DDy [y $ [-B, BJ B BBB
Pry /y $ |-B, B]
2x 8 Pry~D D /y & | B, B] B² Eynn (1 & 1- B) Ey-n(1 & I (-B, Bl)=
2T - 35- - 2 E E | B, Bl
41

---

So it only remains to bound EBy-D/(y & (-B,B)yll Notice that by Markov's inequality, we have
BB B- Bly] < = /
8/ dt [ 8/l S 28/B.
Plugging it back gives proof of Fact C.21
B)B 2 76. This completes the
Now, using
Fact C,21
we get
min E E(x.y)~ - -)) E (-B,
+3
E Ex~Ax
Pry~A E 1- Var Ay)iAAE(--BBBB))
> E Ex
[Var(Ayp) ( (1 B, B])r²]
76.
This completes the proof of Fact C.20)
Applying Fact C.20 gives that
(xx,)) [((()) ()) E
[ (-B, BJ] 2 2T 78
if the original D' is from the null hypothesis case.
Now suppose that the original D' from the alternative hypothesis. Then it immediate that D is the same as the product distribution Ard-dim(V)-dim()) @ A up to rotation in the first d - dim(V) coordinates. From the definition of (A contains the part of x in the optimal relevant subspace W) and C being rotation-invariant, we must have infere ert A (c) infeec pcr Therefore, from the definition of A, we must have
E (x.,))
[(h(x) ((xx))>[(((x)) 1)
E [- B)] & ((x,))((((())) - y) S - -0-3311 -3BB
Given the analysis above, we can simply check (h(x)) 1 [-B, (which has eπrоr most TB?) is greater than 70 3(B²/2 If so, then it must be from the null hypothesis. Otherwise, it must be from the alternative hypothesis. This completes the proof of Theorem C.19
our estimate of
L
C.3 Relation between Our Result and Other Complexity Measures
In this section, we discuss the relationship between our conditions efficient learnaillity of MIMs and other complexity measures.
As noted in the related work section, prior work [BBAM3]] defined the notion of leap complexity and showed that it characterizes the CSQ complexity of learning hidden junta functions over the uniform distributions the Boolean hypercube (these discrete Multi-index models). We remind the reader that CSQ lower bounds are in general strictly weaker compared to SQ lower bounds.
For the special case of SIMs under the Gaussian distribution, [DPLB24] defined the notion of gener- ative exponent and showed that it essentially characterizes the complexity of parameter estimation. It is important to remark that our work focuses on the related but distinct notion of (agnostic) PAC learning, i.c., learning the label distribution to small error. Indeed, PAC learning can feasible even when parameter estimation is not. For instance, if consider distributions where the conditional distribution y x is constant for all x, then parameter estimation is impossible (and the generative exponent becomes infinity). In this case, while it is information information-thhorttiaalll theoretically impossible to recover the hidden direction, it trivial to output a hypothesis achieving small squared error.
The structure of this section is as follows: In Section C.3.1 a corollary the main SQ lower bound of [DPLB24 for Single-Index models without a finite chi- squared condition implicitly used in their work. In Sectioo C.3.2) we show that for realizable PAC learning of Singe-Index models, our condition is essentially equivalent to an appropriate adaptation of the generative exponent.
we show that our techniques imply as
42

---

C.3.1 SQ Lower Bound for Parameter Estimation of SIMs
We begin by providing the definition of the generative exponent for parameter recovery of SIMs. For convenience of the discussion, all the statements presented in this section are simplified for exact moment matching, which-while qualitative the same as the full statements-will be weaker quantitatively in some parameters.
Definition C.22 (Generative Exponent), For realizable learning of Single-Index models under the Gaussian distribution, we define the Generative Exponent of the link function f : R + as the smallest m² E E+ such that | [Amm (t)]llA, > 0 where A is the joint distribution of (t, y) on R x I with t ~ M1 and y = f(t), and h2 is the i-th normalized Hermite polynomial. For a SIM g: Rd + R defined as g(x) = s(w x) for some vector w E Rdd and link function ʃ :R- + R, we define the generative exponent of y to be that of the link function f.
[PLB24] gives the following lower bound on the problem.
Fact C.23 (Theorem 3.2 of (DPLB24). Let E S be a 1-dimensional subspace unknown the algorithm and D be a joint distribution of (x, y) over TRd x R such that x ~ Na and y only depends on Xw (i.e., Dyix distribution of (Xw.y), where (x.y) ~ D, and assume that (D,Na @ Dy) funte Then any SQ algorithm that returns such that |ww . w| 2 (dd-1/2) with probability at least 2/3 requires either query to STAT(S (d-0.21(m"-11)
Daix' for any Xw xw)- Let m" be the generative exponent for the joint
2d0)) many queries.
We note that since Fact C.23 requires the condition XD, Dyy) being finite, cannot be applied to the setting of realizable Single-index models, where f(x) without noise, as this induces an infinite (D, @ Dy).
As corollary of our techniques, this condition can be removed. In particular, for our ourCCondition C.5 the generative exponent m for distribution D is simply the smallest integer m such that 1) does not relatively match degree-m" moments with the standard Gaussian. An application of Theo- rem C.6 would give SQ lower bound to the same decision problem that is used reduce to the subspace recovery problem in [DPLB24]. This in turn gives a similar lower bound on the sub- space recovery problem as Fact C.23 but without the assumption that (D, @ D2) is finite. Specifically, we obtain:
Corollary C.24 (SQ Lower Bound for Parameter Recovery in Single-index Model). Let w E Sd-1 be a 1-dimensional subspace unknown to the algorithm and D be a joint distribution of (x.y) over Rd R such that x ~ Na and y only depends on Xw (i.e., Dyix Dyle for any Xw Xw). Let m² be the generative exponent for the joint distribution of (Xw: where (x,y) ~ D, and assume that m² I d' for a sufficiently small constant c. Then any SQ algorithm that returns a w &d-1 such that [w- w| 2 w(d-1/2) with probability at least 2/3 requires either query to STAT(Q (d- (d-0.22(m--1)) or (0 many queries.
Proof of Corollary C.24 Let A be the joint distribution of (Xw:y) where (x, ~ D where (x, y) ~ D. From the definition of generative exponent, we have that A must be (0.m* 1)- relatively matching moments with the standard Gaussian. Therefore, according to Theorem C.6 any SQ algorithm that solve the RNGCA for input distribution over Rd x R with hidden distribu- tion A with probability 2/3 requires either query to STAT (Pm. (00022((m-11)) or 22)) many queries. Therefore, it suffices for us to reduce the RNGCAdecision problem above to the parameter recovery problem for Single-index model.
Let A be such an algorithm for parameter recovery in Single-index model and D be the input dis- tribution of y) over d x H for the RNGCAproblem. We will sample a random rotation matrix A ~ UOd..). which applies an random rotation over Rdd. Then we give the joint distribution of (Ax, y) (where (x, ~ D) to the algorithm A as the input distribution and let w be the output vector. We will repeat the above process for / = d times and let B be the empirical estimation of (A (A -Iw) and let be the max eigenvalue of B.
"The assumption (D, (D,N& D,, being finite is required here in order for the Fourier expansion to converge in 2 norm, which is explicitly stated in [DPLB24)
43

---

Notice that if the original D is the null hypothesis distribution, then we must have A A-w U() Let wi. W/ be the value of A w for each round and let M Ew 11 [w'ww then we have that
2
w w T /t M
Bwi " W/-U(SS-1)0
-E - w/ w/-0((001)01
w/w, - -M)
Σ ==1
Ww -M)) (wiw--M))
i=1
1
t (S IIW'''
M 13
-)
Notice that for any w E 5d-1, we must have (www
M) - d from the symmetry argument.
Given w/ Bwf W || w/w! /t M
2
=Od 1), by Markov's inequality, with
F
S d= Therefore, we must have probability (1), we have that | w/w, /t M
A = O=O(d11/3) with probability at least 1 o(1).
On the other hand, if D is from the alternative hypothesis, then since the algorithm succeeds with probability least 2/3 and outputs a w such that |w, w (ddd1/2), must have that w Bw ". Therefore, we must have the max eigenvalue À 1/2)
Given the above analysis, we can simply check if À 2 cd 12 for sufficiently large constant If so, the input distribution D must be from the alternative hypothesis. Otherwise, input distribution D must be from the null hypothesis. This completes the proof of Corollary C.24
C.3.2 Near-Equivalence with Generative Exponent
We now show that, for realizable SIMs, the generative exponent and the conditions in our lower bound result @Teoreem 1.10) are essentially equivalent up to some minor technicality, stated by the proposition below. Notice that the first condition below is essentially the same condition in our lower bound result (Theorem 1.10), but without the technical assumption that the extreme values of labels have small contribution to the variance.
Proposition C.25. Let C be class of rotational invariant SIMs on Rdd. Let T E R. and m E Z... then the following two conditions are equivalent:
1. There exists f E C and subspace V Rdd such that (a) the joint distribution of (x, fx)) with x ~ Na matches degree-m moments relative to the subspace V (with the standard Gaussian projected onto V and (b) (br any function h V + R. Ex-Nal((xx) h(xv)) )) 2 T.
2. There exists an C with Generative exponent strictly greater than such that the variance of fxx) with x ~ Na is at least T.
Proof. Notice that it suffices for us fix C and prove the equivalence. For convenience of analysis, let w E Sd be the relevent direction f and W be the 1-dimensional subspace spanned by Let D be the joint distribution of (x,y) supported and A be the joint distribution of (t, y) supported on R x IR with ~ N1 and y f(tw). Then suffices for us prove that the following two equivalent.
IRd x IR with x Na and y f(x)
There exists subspace V S Rd such that (a) matches degree-m moments relative to the subspace V (with the standard Gaussian projected onto V-); and (b) for any function h V - R. E(x,)=l(x l(xx))(x)) T.
2. f has Generative exponent strictly greater than m and the variance of f(x) with x ~ Na is at least
The direction that Condition implies Condition is immediate. We simply take V {0]- Then Condition bb) follows directly from the fact that infoeR ((c.))~a(( - c)2] 2 Since
44

---

the Generative exponent of f is greater than m, we get that |[E [t)](t)]])l = 0 =
[i (,) for any 1 S k S which is E (t)] E [+x(t)] for almost all y Ay. Notice that the matching degree-m moments condition (Definition 1.9) the same as the O-matching degree-m moments condition (Condition C.5). Therefore, we just need show that for any function f : Id++1 + R such that f(,, v) is a polynomial for any fixed y, then ((xx))-n[(( y)] ((xx)))NGen, [f(. 3)] = 0. To do so, notice that
((x.))~D[[( v)] = Ey~D, (Ex-Da, [xx u)]l = EY,D, EE - ( (WW +x))))
Let f" 12- + R be the function of [t, y) Ex-Nioo (f v)]. Notice that f'(: v) is polynomial for any fixed yy. Then using the fact that Hermite polynomials form an orthornomal basis, we have
E(x.))=D[((x, u)] = EEu.oraaas v)] BuL,)AGaA (4,
=EyDD, [E ( (f - x', y))ll = (xx.))-NG&n, (f(x, y)
where we use the Generative exponent condition in the second equality. This proves Condition (b) and completes the proof that Condition implies Condition !
For the direction that Condition I implies Condition
2 we prove its contrapositive. Assume that
Condition 2 does not hold, then must either have inf ((t.))~((y - c) or f has Gen-
erative exponent at most m. If infog Eqt,y)~aly c)²] т. then taking the h in Condition (b) to be the function h(x)
would imply that Condition 1 (b) does not hold for any subspace V. If f has Generative exponent at most m, then we get that there must be a 1 S S m such that ((()))))AA11 [hx (f)]lI,, O. Now, suppose V IRd is any subspace and we will analyze the following cases.
1. I S V. then taking h(xv) = fxw is well-defined and we have Ex (x O, which implies that Condition (b) does not hold.
If W Z V. we assume that Condition (b) holds for the purpose of contradiction. Let u Wy+ / ( 12 and w' uw /ww/|/uwll2 We now consider the polynomial p V - R defined
as p [v= hu ((u, x)). Notice that
Ex-D [x(x==]]
Exxx -
h (u,, x:)]
= Ex,~N(0.11) EX
Xv x Ay= voll
-x EX~D [/x[((,, u) (w,x) + u)) xv = X Ay= yo]]
-E -E [hw (), + (w', u)z) y y yol
-E [1 ((w, u)t uw), yul
-E(I,yaa ( /u (() y- yo]
=(w, u E(t,))~ [1 (f) y yol
where U, is the Ornstein- -hhlebeek operator. Therefore, get
0. Now notice that p(xv=) = Eie(m) A; (xva) )8 for some linear maps As (V-) + R.
E (p(xx_ )llA,
Given Condition (b) holds, we have
Ex- [p(xy= 1 )1 Exx
Σ As ( :c(m]
A E Exw
ic [m]
A Ex (80) o0
y- Dy
:E|m]
-Ex ( = Ex (u,((ux))) 0
45

---

where denotes equivalence for almost all Dy. Therefore, IIx(x)llo, = 0, which Dr
contradicts the fact that l,, > 0. Thus, Condition (b) does not hold.
This proves the direction that Condition implies Condition 2 and completes the proof of Proposi
tion C.25
D Algorithms for Learning Real-valued MIMs
In this section, we establish Theorem 1.4
Theorem 1.6 and Corollary 1.7
Organization. In Section D..1, we present our agnostic learning algorithm (Algorithm 3), along with the formal conditions that a MIM must satisfy for the algorithm to succeed (see Definition D.I) In [Seciion D.2] we demonstrate that our algorithm exhibits improved efficiency when the labels de- pend only low-dimensional subspace- regime that encompasses the realizable setting well as cases with added random noise. Finally, Section D.3] we describe our applications to positive- homogeneous Lipschitz functions (including homogeneous ReLU networks) and polynomials few relevant directions.
D.1 Agnostically Learning Real-Valuet MIMs
D.1.1 Agnostic Learning Algorithm and Results
In this section, we present algorithm that agnostically learns MIMs that satisfy well-defined set of assumptions. The set of conditions we require is given in the following definition, which is formal version of Definition 1.3]
Definition D.1 (Well-Behaved MIMs). We denote by F(m, S, or, K, K,M, L,M,L,B,n B,D,T,)) the class of all functions f : nd + IR satisfying the following conditions:
1. There exists K -ddimensional subspace W of gd such that f(x) f(xw) for all e Rd.
2. is continuous everywhere and continuously differentiable almost everywhere, with Ex~AN, (
3. has bounded norm [X-xx[ S M and is p-close to B-bounded function, i.e., there exists Jn d B, B) such that Ex-Nal([(x) - fn(x)) p.
4. For any subspace V of Ø& and any distribution D on Rd R with Dx -Na such that ((xx)))l([(x)) u) < < the following hold:
((xx))) S for some g : V RR or with probability a over Na independent of x there exists a degree most zero-mean, unit variance polynomial p U + IR, where U = Wv such that Ex<>N,(((xx ||xv zv yo 1 a.
either Px<NN,1((*
E (Do
A Well- Well-Behaved MIM is bounded variation MIM function that exhibits distinguishing moments despite the presence of arbitrarily small L adversarial noise. Using this robustness property, one can show that for sufficiently fine partition of subspace V into cubes and of the real line & into intervals, there exists a constant fraction of the partition elements for which distinguishing moments are observable. In other words, conditioning on belonging to particular cube and y lying within a particular interval, distinguishing moments persist.
Before presenting our algorithm and results, we first introduce several key concepts used by the algorithm.
One of the crucial components of our algorithm the discretization of the space of examples (x, y) into thin regions. To achieve this, we partition and separately into small, equal-width cubes and intervals, respectively.
'This is mild assumption which is satisfied for example when the function has bounded 2. 1-d-ree mo- ment, that is 2 is appropriately bounded.
46

---

In particular, to efficiently approximate distributions over subspace V, we partition V into equal- width cubes, excluding the region where any coordinate exceeds Vlog(h/E). This approach ensures that we retain nearly all of the mass of the distribution while maintaining regions that are both sufficiently fine and can be sampled efficiently.
Definition D.2 (e-Approximating Partition). Let V be a k-dimensional subspace of IR with an orthonormal basis v()) ,.... v(8), and let e E (0, 1). An e-approximating partition with respect to V is a collection of sets S defined as follows: For each multi-index j = .ik.....kk E [M.]]. define Sj = {x E IR 2j. - I v(0.x x S Zj, i E [k]] where z; are defined as 2; -V- log(k/))++ie++
for E , M. E (0,e/2) and M. = (2 log(k/e))/
Moreover, we also discretize the label space IR into thin, equal-sized intervals, and refer to the pair of these partitions approximating discretization of V x R.
Definition D.3 (Approximating Discretization). Let V be a subspace of Rd. We define an (E1, 62, B) approximating discretization of x R as a pair (S,I) where
(i) S is an 61 apapppoxing partition of V;
(ii) I is the set of intervals {lie2 e2/2, ie2 e2/2] : E 2 S B/ea - 13
[0- B]. [B, -x]}
We use the term (<1, 62) approxiaaxi discretization to refer to the special case where B 1/22. Moreover, when 62 we simply refer to (S,I) as e-approximating discretization.
Note that [DKZ225] does not use a discretization over the label domain and instead obtains a com- plexity that scales with the number of its elements. As result, their approach becomes vacuous in the real-valued setting. In contrast, we bin the values of the label domain using a thin but reasonably efficient partition, thereby circumventing this issue.
In order to construct an approximation after identifying the appropriate subspace W, we approxi- mate using a piecewise constant function defined on the projection xw. For this, we start with partial partition of W. and define a function that constant on each element (region) in and minimizes the L2 loss. In particular, given the partition S, the function assigns to each region S e S S]. We formalize this definition as follows:
the value E y x E
Definition D.4 (Piecewise Constant Approximation). Let D be a distribution over Rd x R, let V be subspace of Rdd and let (0, 1). Let S be partial partition of V. piecewise constant approximation of the distribution D. with respect to S, is the function hs : R - R such that for each S E S and x E S, hs is defined as hx(x)) = E(x,)~DDy x S]. Furthermore, for any point outside the partition x & USES S, we define hx(x) = O.
We set (x) = 0 for all points outside the partition to simplify variance control, since these regions will carry negligible probability mass do not need be approximated.
We now present the main result of this section, which establishes that the aforementioned class of well-behaved distributions can be learned efficiently using Algorithm 3)
Theorem D.5 (Agnostically Learning MIMs). f Rd + R be function from the class F(m, a, K, M, L, B, /M, T.) Let be a distribution over Idd R. whose x-marginal is Na and let OPT def Ex (ff() =) with <> OPT + O(e). Then, Algorithm draws at most N = (mm) 2poly((( BKLM/ log(1/6) i.i.d. samples from D, runs in time poly poly(N), and returns hypothesis h such that, with probability at least ō, it holds
[(x())D((((x)) - y) & (VT+c+ (VT+)+ +c.
D.1.2 Finding a Relevant Direction
First, we show that if there exists sufficiently accurate approximation of our function within V. then a piecewise constant approximation over a sufficiently fine partition of V yields comparable error.
47

---

Learn-MIMs: Robustly Learning Well- Bell-Behaved MIMs
Input: Accuracy e >> O, failure probability E (0, 1), sample access to a distribution D over R xR with Dx Na for which there exists F(0) for some (m, OPT+,, K, M, L, B,p; T,O) known to the algorithm.
Output: A hypothesis h such that, w.p. 1 8 (xx))~D((((()) - v) (VT+C+ VOPT) +c.
1. Let T be sufficiently large constant-degree polynomial in 1/a, 1/s, 1/0, K, L, M, B, and let C be sufficiently large universal constant..
2. Let L1 + 0. N t dmm2?" log(1/0), + 1/T,n 1/T, 2 (/(MM)
< (aoc((MBK2")))
3. fort=1,....
(a) Draw set S, of N i.i.d. samples from D.
(b) & Algorithm 4 17. C1, C2, B, spann(L) St, 0).
(c) L1+1+ L,
4. Construct S, an é1 ai-apprxinnating partition with respect span(L.) (see Definition D.2).
5. Draw N i.i.d. samples from D and construct the piecewise constant function hş as follows: For each S, assign the median of O(log(1/6) means of the labels from the samples falling in
S.
6. Return hg.
Algorithm 3: Robustly Learning Well-Behaved MIMs
FindDirection: Estimating relevant direction
Input:
1,,1,,,, 62, B, X>0, subspace V C Rd, samples ((x((), y:) Output: A set unit vectors E.
Ris from distr. D over Rd R.
1. Construct an 62, appapoxxingg discretization of V x IR. (8, (see Definition D.3
2. For each S E S and each E I, find polynomial (x) such that
E E(x,)>D((1 E I) I x
< min E Exx.)) E p' p'(xy1))² | x p'EPm
3. Let Ū Eses,EE Ex (Vps, Vps, T
S) ((PPrx.)~iiSS)))
4. Return the set E of unit cigenvectors of Ô with corresponding eigenvalues at least X.
Algorithm 4: Estimating a relevant direction
48

---

Lemma D.6 (Piecewise constant approximation suffices), Let e, M.T E Ry, k.d E 2+ with T S M and с > 0 be a sufficiently small absolute constant. Let f : R + R be an almost everywhere continuously differentiable function such that Ex [II [x)]() S L and Ex (x)] I M. Moreover, assume that there exists a B > O and fB : R - I- B] such that [[( - [x)] S ct2 /M. Let V be k-dimensional subspace Rd and let S be an n-approximating partition of V with qj S. oe2 /(M BLk). there exists a function V - such that Ex~Na [[f(x) g(xv) ))a] <. T, then we have that Ex-Nallf(x) hs(x))² + 6, where hs denotes any piecewise constant approximation of f.
Proof. Note that for any function g V + R the following holds
Be=-N[(((x)) - E [f() zy = =xv]) Ex~Ax1(((x)) - -(xx))(()
Therefore, we have that the function s(x)) def
Eg,,,, (f()) By = xv] achieves squared error at most 7. Note that since Xy and xy independent for Na. we have that
s(xv) = EenNia zv = xv] = Exp, [f(xv + +xy+]]
Hence from the linearity of the derivative operator and Jensen's inequality we have that [|Vs(x>)]l < Exp1 V + x|=] Consequently
Exy [ss(x)) < ExmNa V f(v + xv=) S ExmNa [IxNN((IVV(x)]]]] SL.
Moreover by Jensen's 's inequality we have that
Ex-wa[(<(xvv) - Ex,_ [Nn(xv + xv= ))²) ExxNu + xv=) (n=)-fa(xx) + xv= 11)
S ((f fo (x S
Therefore, is close bounded function. Let h be approximation to 8 that achieves squared eπror a. We have that the function 1x))((xx E A*) achieves squared error 2 + 2p + a wheee A
is any region of Id with mass less than c.
As a result we can apply Fact E.11 for the function s have that the piecewise constant function hs(xy) def E|s Ixx E (x) x E $1 for all x E S and S E S and hs(xy) = 0 otherwise achieves error Nx [(((()))))))))))))) (x(x)))) < 4p + n + Bn.
Finally, we have that Bx=Na[(((x] - hs(x)) = r + e, which concludes the proof of Lemma D.6
we show that there exists a non-negligible fraction of finite-width cubes over Xv and intervals over y where distinguishing moments can be observed. Furthermore, we demonstrate that if a direction of the target model learned to accuracy then there exists observable moment that depends only on the remaining directions.
Moreover, under the conditions defined in Definition D.I.
Intuitively, the proof proceeds as follows. Since f is well-behaved MIM, we can round y to some small accuracy while maintaining distinguishing moments. This discretizes the label space into intervals, and so with non-trivial probability over Xy there is degree-m moment that correlates with the rounded label. Next, because f has bounded variation, f(x) and f(x') where x' is obtained by averaging Xy within x's cube S-remain close mean-squared error. This insensitivity lets us discretize over V as well. Finally, for any direction with small projection onto W, bounded variation and the well-behaved MIM condition imply that averaging along that direction preserves the distinguishing moment, yielding moment independent of these directions.
Lemma D.7 (Cube-interval Discretization Suffices). There exists a sufficiently large constant C' >> 0 such that the following holds. Let d, k, m E., and L, M, Ç, T, GEE O with Ç < M. Let f Rd + R. be in F(m, S + Ce, a, K, M, L, B, B(CM T, o)) and let W be a K K-dimensional subspace such that f(x) = f(xw). Let D be a distribution over Rd x R such that Dx = Na and ((x.,)~ ((](())x(x--)())))))))<>)>) =) < Ç. Let V be k-dimensional subspace, k ' 1 and denote by U wy Let (S,I) 2) be an (c1, 62, Bpppprooxngg discretization of V x R. with 6 S è 22/(22M2 and <2 S è² (CM... Moreover let F, C V be a subspace such that || S c/(CKTMM for every unit vector V E E.
49

---

for all g V + R. then there exists T S S with ΣSET Pr[S] 2 a such that for all S E there exist I E I and zero mean variance one polynomial p + R of degree at most on such that the following hold:
fE(((x
i) Elp(xx))(y E 1) xv E S] 2
ii) Vp(xe) = = for all E E and x E RR..
Proof of Lemma D.7 We prove the two items in order. Specifically, we first show that there exists a sufficiently fine discretization (S,I) of V R such that, for a fraction of cubes S E S, there exists a degree-m polynomial that correlates nontrivially with the boolean functiin 1 (y E I) conditioned on E S. Then, we show that averaging each such polynomial over the subspace E' preserves its correlation on S while forcing all directional derivatives along E to vanish.
Existence of correlating polynomials Without loss of generality, we can let y be the random variable obtained by truncating the original random variable y to J-B,B) (meaning that we assign
the value Bsign(y) if lyl Z B) and rounding the nearest multiple of eg. Indeed, let ye def sign(y) min(1y), B) be the truncation of the original random variable y. by expanding the square and applying Cauchy-Schwarz [x(ʃ((x) - y) S O(e). Hence, (x) - yBB]]
E[[Sg( (x)
F) S $ which by similar argument implies that E[(f(x) - yB)² S +
Similarly, rounding yB to multiples of e2 S (CMC also keeps the random variable (ç (c+ Oceo)- to f in squared error. Therefore, for the new random variable it holds that [[( y) =(e)()).
For any x E IRd denote by Sx the set S S such x E S. We define a random vector x' such that x = Xy and xy is the sampled from the standard Gaussian over V conditioned on Sx. i.e., Na Sx- Note that x' also follows the standard normal distribution over Rd because its V- component is resampled from Na. Define y' such that for all HRd the distribution of y given x' z is the same as the distribution of y given x = z. Notice that y' and y have the same support, i... y' is also a multiple of Denote by D' the joint distribution of 3").
By applying Fact E. we have that (x( fxx)) S L/M Moreover, it holds that Ef(((x)
r') = E (x(') - 2). Therefore, by expanding the square we obtain
- [(( - -/ 11F)=E((4 Ex(](x)()x y) 2E((((x) v)( - [(x)) -
where in the last inequality we used Cauchy-Schweer Schwarz and the assumption that < S M. Consequently, by Condition (4) of Detinition D.I we have that with probability over Z Na there exist a zero mean, variance one polynomial E Byo (D), ((x."'>>>'pp (p(x)))(X))) |xx = zv. - vol |
U + R such that
Fix such that the aforementioned statement is satisfied. Note that E = O(M). Recall that by the Gaussian hypercontractivity inequality (Fact E.4), we have that Ex)] S 3 for any zero-mean, unit-variance polynomial q Rd + R of degree at most m. Let r E (0, 1) be parameter to be quantified later and denote by V, the set of all y0 in the support of y' such that Pry
((),,,((//ver Ixv=zv)(u' !o] S v). For a label a E )/, we have that
Eyo-(D' y jxy av) [1 (yo a) ())( (p(xu) ) x = =V. = yul?
S Ego bx (1o = a) E (xu) = zv.y' yol
S VTV Ex,rN Xv ]v
where in the first inequality we used Jensen and in the second inequality Cauchy-Schwar and in the last inequality the hypercontractivity bound along with the fact that U CV-
Note that the number of different values in the support of y' are at most O (2). As a result, we have that
E (Do,(D() [x (p(x)) (xV = zv. = yol?]
< E Eg (xy= [1(y0 & 2r) (x (p(xu) )xe zv.3/ yo1'] + +(BBee)) / 7m
50

---

Setting the parameter and thus B (oo (xy=ry) [y0 & ( (xx))) (x(x))xx = Zv. yolo
(ca results to O(B/e2) n23 3
0 /2, o/2.
Therefore, there exists a y0 with Pr xv=zv)l = vol
" such that
(xx.g") (p(xx) Xv = zv.y' = vo] va/2. Hence, for the aforementioned yo it holds that ((x)//DD ((x((())))))))) ) = yo) xy - zv) poly(ar/(BA33)).
Finally, since of is independent of zv when conditioned on its cube Sev we have that ((x.)")~>r (p(xu) [1 = yo) Xy S] 2
(BM3))) Noticing that the moments with respect to U on each E S are the same for yf we have that also (xxx))>(lp(()) [I = yo) Therefore we have that the first part of the statement follows as conditioning on the truncated and rounded label to equal icg is the equivalent conditioning on the intervals (ic-- - e2/ icz + e for ji] S B/c- - 1 and [-oc, -B]. [B, oc].
Xy E 5] 2 poly(oe/(BM3"
Using a similar strategy, we show that there exists polynomial satisfying the second part of the statement also.
Averaging over E Define the parameter 8 def c/(CLKM). Recall that for all unit vectors E E, it holds that Vw S 6. Let x' = zg + XEL, where z ~ Na independent of x.
In the following claim we show that fxx is very close to fxx',, to do this simply integrate the change of f across path from x to x'. Since f is a function of bounded variation and [[ (x x this change is small.
Claim D.8. It holds that E[(((x) - f(x))) L(K8)².
ProofClaim Claim D.8 Note that since want to utilize the fact that El| fx) [?3] < L want inte-
grate at along a rotation from x to to preserve the all intermediate points the path to be standard Gaussian.
For that purpose u()) (xg cos(@) + z sin xg. Note u(0) and u(x/2) x'
Now by the Fundamental Theorem of Calculus
//2
((((())) d
f(x) - (xx)
u())d0
dB
1/2
A(((())) IIw (&n cos(O) x (O))do
< (nr x sin (6) si)) (d0,
where in the last inequality we used Cauchy-Schwarz. Hence,
( 1/2
< [VS(u(O)) Hw (zg cos(O) XE sin(
( (2/>)|Vf(u((0)I)))) (2g cos(O) x sin |[d
1/
2
2/2
$ (T/2)
(V)(( [w [z cos x sin sin(())]] (d))
where in the last inequality we used Jensen. Taking the expectation and noticing that u(0) and Xg si) are independent (since they are jointly normally distributed and uncorrelated),
Zg co) (0)-
we get
E[( - f(x))
V (((()))) (Z5 cos(O) X (0))
[[ cos X sin (
LE LE [
51

---

Noticing that Ex-.N_ W gg [3] P]=
[[ | - (rank(I[w Iglla)² < (K8)² com-
pletes the proof of Claim D.8
Consider the random variable Hence, by Claim D.8 we have that ( E (c/())))
y' supported on that is distributed like y for x', i.e., D(y = p x' = 2) ( p x = z), for all E RR pepeee E R.
Note that E[(f(x) - y0) = El(f(x') - 3), which, similarly to before, can be shown- by ex- panding the square and applying Cauchy-Schwarze to be less than Ç < for sufficiently large constant C. As a result, we have that by applying part (i) of the statement to y there exists such that for each S T there exists zero-mean, variance- R of degree at most m along with an interval E I such that X (X o, where U = (V W) V+. However, we have that for
T S S with SET Pr[s]
one polynomial
U +
Ex [p(xx) 11y E 1)
all S ET
Ex,y Bx.rl((x))1 E
E[Exg (p(x)) X |E
[1 [1 1) X 1| x []]
Notice that p' p'xx)) def Exs (xxx) xg_] mean-zero polynomial of degree at most m with variance at most one by Jensen's inequality. Furthermore, as p' is independent of Xg we have that Vy((xu) for any v E E and x E Rdd
Before proceeding with the proof of Theorem D.5 we establish the following proposition, which states that each iteration, as long as the current subspace yields an insufficient approximation of the labels, it is possible to extract a direction that is correlated with the remaining subspace.
Proposition D.9 (Finding a Relevant Direction). Let d, k, m, K E Z,,, 8, a E (0, n, e, M, L
and let C > 0 be a sufficiently large universal constant. Let f : Rd + R be a function from the class S, K, M, L, B, B² B.e//./CCM). /CMM), o) and denote by W C Ed with dim(W)
K the hidden subspace of f. Let D be a distribution over Id x R whose x-marginal is Na and let OPT def Bix.))=D(f((x)- - u)² with Ç Z O(E). Let V C Rd be a k-dimensional subspace and let (S.I) be an E2, B) approxiiiing discretization of V x R. with e1 S <C/(CLM Vk) and E2 S. 2CM Additionally, let his be a piecewise constant approximation of D. with respect such that, if E(xx)>Dl(he
to S. There exists N- = (dm))(m)) (k/e)) (K()
y)²] (VT+E++ 2 then Algorithm 4 given N i.i.d. samples from D and parameters n S (are/ (M )) c1, E2, X = (aoe/(MMB) 2") runs in poly(N) time, and with probability at least - 8, returns list of unit vectors & of size [E] p2t KM B/ (B/(()))))) ), such that: For (KLMB221)
some v E E and unit vector w E W it holds that Wy v 2
Proof of Proposition D.9 Let w(1), w(1),..., (K) be an orthonormal basis for the subspace W. For each pair S E S and I E I, let I denote the regression polynomial of degree at most computed Line of Algorithm 4 Further, let Ü be the matrix computed at Line of Algorithm 4 and let 7 denote the T.2 error chosen in the polynomial regression step (see Line of Algorithm 4.
We begin by proving the following general lemma, which states that if a fraction of the discretization cubes exhibit non-trivial moments, then-with a sufficiently large number of samples the output set E will be non-empty and will contain only a small number of vectors.
Lemma D.10 (Existence of Correlating Vectors). Let (S.I) be an 62, B) approoximating dis- cretization of V R. Assume that there exists subset T S S with Eset Pr[S] 2 a. such that for each S E T there exists an interval I E I and a zero-mean, variance-one polynomial qs : + R of degree at most m such that Exx,y))- (x5( [1 1) x E S] > 2 2n for some subspace U of V Furthermore, assume that the eigenvalue threshold X = (aa/ (aa/K)C C, for some sufficiently large universal constant C > O. Then, there exists N = (dm) ((m) (k/e)) with probability least - 8 the output set & has cardinality at most [1| and contains at least one vector v E E such that u v 2 poly(ao (I((m)) ( some u E U.
( (k))
(ZI)()//// (L)) such that (m// K/aa//(ao (I)(II)
Proof Lemma D.10 Let (')).... (k) denote an orthonormal basis of the subspace U. We prove the lemma in two stages. First, we analyze each cube S that exhibits non-trivial moments by evaluating the quadratic forms of its influence matrix Ms.
52

---

Ex~D, [Vps. (xs.((x=) x E S] the vectors u Then, we extend the analysis by averaging over all such cubes and examining the eigenvectors of the aggregated influence matrix, U.
In the following claim, we leverage the existence of non-trivial moments over U for the regions S T, to show that if the sample size is sufficiently large then for each region T, there exists an interval I E I, such that the associated influence matrix, Ms,,, has large quadratic form for at least one of the u 's..
Claim D.11 (Quadratic form of the Influence Matrix). Let C 0 be a sufficiently large universal constant, Fix, S E T. If the number of samples that fall in S is Ns 2 (dm) 1og(1/(öog) (öc2))/n then with probability at least 1 - 5 there exists i E [['] and I E I such that (u Ms z o²/ (2/(
Proof of Claim D.II] Notice that membership of a point x in cube S depends solely on its projec-
tion onto V. I.e., on Xy. Therefore, the error guarantee obtained in the polynomial regression step
E(x,))= (y I) - (x.r(xy=)))> x E S] m Exxg)>D((11 (1 1) ('y )) S] + 17² equivalent to (x [(1 E I) ( miny' D TT [11 e I) - -xx + where D is the marginal obtained by averaging over V conditioned on S i.e. DE (X) = Exy [D(x,) v) x S].
Moreover, by the properties of the Gaussian distribution, we have that the x-marginal of D a standard Gaussian. Therefore, since [ = poly(1/e2) if Ns 2 (dm)Cm ())2)) for sufficiently large universal constant C > then by applying the union bound and Fact E.9 we have that with probability at least 1 - 8:
VL is
E (xx,))DD Ve [[]y E I) - ps. min PePm
B(x,))DD e -)
for all 7 T I. Furthermore, by the orthogonality of Hermite polynomials, have that
(( Vi [11( E T) (x))
Σ E (x.g) [H) 1)] (x,)) (x)())ss.
BCN
In particular, if we decompose the error into its Hermite polynomial components of degree - 19]
have that Σm ((x.)) [( p (x)) s)²
From the rotational invariance of the Gaussian without loss of generality, we can denote by e1....,er ey the orthonormal vectors u')....., u(k), Furthermore, since U is a subset of V we similarly have that (xx,)>=DS [gs ( E I)] > for some I E I. Decomposing qs (x(xx) to the basis of Hermite polynomials have that qs (xx) EBENd 11 1 Sm H3 where = dim(U). Moreover, note that since qs has no component outside ei...., eg we have that (x())) = Ese. (3) where J denotes the set of B E No such that B, 2 1 for some i [W]. Considering the correlation of qs with the label interval I, we have that
E (xx,))DDE f1 (as(x)))[( [)] Σ EB) (()(x))((EE4)
BEJ
1/2
Σ BEJ
E (itpi:/g_[(xx)Xyyeeeee
where we used the fact that ||as||2 = 1 and the Cauchy-Schwarz inequality. Hence, we have that the sum of the squares of the Hermite coefficients for of the degree m restriction the random variable 1 1) is at least o?
53

---

Now evaluating the quadratic form of Ms using Fact E.6 gives us
K'
e,
Ms
Σ
E (
(Vps,, e
Σ
Bos (3))
BENd i=1
E (x.y)~ ( E 1)}2-2n -2 2n
BEJ
2 o²² 21 2 0212
for 7 S 0/2. Thus, since dim (U) < K we have that ej Ms,re, 2 02/(2K) for some j E [A']. This concludes the proof of Clai D.II
Now note that by the definition of an approximating partition (see Definition D.2) and Fact E.2 for all S E S we have that Pro[S]= (er /k) hence |S]= (k/e) (ou), Therefore, by union bound and Hoeffding's s inequality, it holds that if 2 (k/Ei) log( (o(([S(/))) = (k/e,) (O()) log(1/0) for sufficiently large constant C 0, then with probability least å we have that [Pr Pro[S] < [r for all S E Hence, it is true that Pr 2 Prp[S]/2, i.e., the number of samples that fall in each set S E S is at least N WPrp((S/22 = ((el/k)0(()
Therefore, for 2 (dm))m(k/(c))) (k/G)) 0, by applying Claim D.11. we have that for all E T it holds that (u()) Ms. nu() (3) > o² (2K( (T.))
(og(([//))/1 for a sufficiently large universal constant C >
for some E FJ,7 E Z. Hence, since k'' < K, we have that there exists subset T C T and
i E [K] with Eser [S 2 ESET Pro that ( ( 2 (2K) for some E I.
Q(a/K) such that for all S E T' we have
Thus, for some [K] we have that
(u )
a / 2 poly(aa/K). K Z
where we used the fact that Ü is PSD.
Moreover, note that from Fact E. 10 we have that tr(Ms.r) = O(m). Therefore, we have that
|Ms, - E P/s,
) = ir sr(Ms.).. As result, by the triangle inequality we can see that
| S
Σ
MM Pr S O(m)
Σ
Pr m/Z].
SES,IEI
SES,
Hence, by Fact E.7 we have that there exists unit eigenvector of Ü with eigenvalue at least poly(ar/ K) for a sufficiently small polynomial, such that u(i) v 2 poly(ag voly(aa/(mK]]) [[]) for some i E [K]. Moreover, the number of such eigenvectors, [E), at most (M)])/(())) Which concludes the proof Lemma D.10.
We now leverage the assumption that hs exhibits large error, along with the previously established lemmata, to complete the proof.
Define the subspace E def span((v E E /| S p/ where p def 2/(CKLM). Notice holds for every unit vector
that || S p
Also denote by def WvL.
Since E(x.))DD((hs(*
(VT+é vOPT)² and ʃ is assumed be in the class a, K, L. B, 2 (CM,) we have that Lemmas D.6 and D.7 together imply F(m, OPT
y)
+ OM.
that there exists subset T C S with EsET Pr[S] 2 such that for each S E there exists an interval I and zero-mean, variance-one polynomial qs : - R of degree at most m such that ((x,))
(aa))~D(ls((pp) (xs [ E x E S] > / for some / = (o2)(r)((MMB2")) and Vzgs(Xu) 0.
Denote by ( (Kk)
orthonormal basis of the space U projected onto E We have that K' 2 1, otherwise we would not have the existence of qs that is defined over this space.
.....
Finally, note that for C' sufficiently large constant 7) < 1/2 and also À (la/K)C, There- fore, since N (mm) (k/e,) O(k) (og(B/(8ea))/mn on)) 0(1) applying Lemma D.10 for the space
54

---

U projected onto E', we have that |8| poly(2" B/ (aoreey)) and there exists at least one vector v E & such that u v * O for some i E [K]. However, note that since u v + O, we have that v can not belong in E. Thus there exists a unit vector w E W such that
V w| 2 p/ p/VE= 2 poly(eoeza/ B2")) which completes the proof of Proposition D.9
D.1.3 Proof of Theorem D.5
In this section, given Proposition D.9 we proceed to the proof of Theorem D3. Recall that, in Proposition D.9, we have shown that if our current approximation to the hidden subspace is not accurate enough to produce function that has sufficiently small error, then Algorithm 4efficiently finds direction that has non-trivial correlation the hidden subspace. In the proof that follows, we iteratively apply this argument to show that, after a moderate number of iterations, Algorithm outputs function with sufficiently small error.
Proof of Theorem D.5 Denote by W the K-dimensional subspace defining f. We show that Algo- rithm 3 with high probability, returns a hypothesis h with L3 error at most (VT + e + VOPT)*
Denote by w=(1),... (*) E Rd an orthonormal basis of W Let Lg be the list of vectors up- dated by the algorithm (Line 3c of Allorithm 3) and V2 span(Lt). dim(V))
kg Also, let St
for & E [T] be arbitrary é1 E1-approximating partitions of V2 where e the value set at Line [ Let he Rd -> [K] be piecewise constant functions, defined h = hs, according to Definition D.4 for the distribution D.
To prove the correctness of Algorithm 3, we need to show that if he has significant error, then the algorithm improves its approximation Ve to W For quantifying the improvement at every step, we consider the following potential function Φ; Σ
We will use the following fact that quantifies how much adding a correlating direction decreases D,-
Fact D.12 (Potential Decrease, e.g., see Claim 2.16 [DKZ255 ). Let B 2 0. If there exists a unit
vectors (() E Ve+1 and w E W* such that VV. V. 2 B then D.41 s; - 32.
(t)
We next prove the following claim which shows that the error of the functions he decreases add more vectors.
Claim D.13 (Error Decrease). For each E [T]. it holds E((h44 v) - (x(,,(x) -
Proof. Since the statement of Proposition D.9 for any 61 C1-partitions S,, t E [T]. independent of the choice of basis and threshold points, can assume that all the approximations h, are computed with respect to extensions of a common orthonormal basis and that all threshold points are aligned. Hence, S1+1 is subdivision of Sr. Thus, each set S St can be written a union of sets S E S4+1. i.e., S = S
S By definition, for any set S S, we have (x()) E(xy) x E S] for E S, and similarly, for any S, S1+1. (x+1(x)= = (xxx)>=D x E St] for x E S: Thus, for any S E S.
E ((x,)) (1)+1 2) x X
Pr SS) ((x) (bbz1) - y)² x E S,
Pr Pr[S.] E E(x,)) (EIxS)DDD I X SES - - w)² x s:
Pr[S.] E ((x,)\D E (EIxy))DDI
l x) x E
i=1
(x.)> (h+(x) y)² E)
where we used the fact that [p-r((> Elr)) S Eg-p((x - 2) for any z E R and distribution
P supported on IR. Summing over all S E S, completes the proof of Claim D.13
D
55

---

Finally, we prove the following claim which shows that the population piecewise constant functions are close to the corresponding empirical ones.
Claim D.14 (Concentration of Piecewise Constant Approximation), Let e, E (0,1) and k. K 2+ with e' S c/2. Let C Rd be k- k-dimensional subspace, and consider piece- wise constant approximation h TR. [K] of D, with respect an c'-approximating parti- tion of V. Let D be the empirical distribution obtained from N ii.d. samples drawn from D, and let h be a piecewise constant approximation of D defined with respect to the same parti- tion. If is computed using the median of means estimator Fact E.13) for each S E S, then there exists N- (k/e))00)) (M/e) log(1/6) such that, with probability at least 1 1-6 8. we have E[(h(x) - y) = E[ y) +c
Proof. Denote by the approximating partition for the functions h, h. First, note that by the def- inition of approximating partition (Definition D.2 and by Fact E.2 we have that Pro [S] (d/k))akk) and hence S (k/c))
Fix S E S. Note that since Pro [S] is lower bounded we have that the second moment of y condi- tioned on S can not be arbitrarily large. Specifically, Ely² x E S Ely²1(x S)]/Prr[S] M(k/e")o(k) Therefore, for any S E S by applying Fact E.13 we have that, if the number of sam- ples that fall in S is Ns = C(k/e)CCMM M²/e² Poo////ool////// log(1/o) for a sufficiently large constant C' > 0, then with probability 1 5 it holds [hxx) - Ely x E S]| I for all x E S. Noting that by definition h(x)= = Ely E 5] for all x E S, we have that [π(x) h(x) S c for all x E.
Hence, by union bound and Hoeffding's inequality, if N > (k/E') log([S1/0) (kk)")O(k) log(//8) for a sufficiently large constant C, then with probability 1 8 we have that [Prp[S]- - Prp[S]| S Prp|SS/2 for all S S. Hence, it is true that Pr 2 [r i.c., the number of samples that fall in each set S E S is at least N NPrD[S1/2 (((/k))(() Therefore, N 2 C(k M2/e2 log(1 (1)) for a sufficiently large constant C, then with probability at least 1 5 5 for all S E S it holds that [7(x) h(x)) S for all x E Rd.
As result, by Mauchy-Schward E[(((x) y) < (((((x) y) +) E((((x) y) More- over, by Jensen's 's inequality Ely²], Elh (x)] I M. hence <h(( - u) S V2M. Therefore,
if N > C(k/e) Ck M log(1/8), with probability at least 1 - it holds that E[([(xx) y)²] <
[h((x)) y) +
Which completes the proof of Claim D.14
Note that from Lines and of Algorithm 3. tions. Furthermore, in each iteration, update the vector set with at most poly BK (caor) vectors. Hence, it follows that ke S pollloyyLLL. (DDKBBBKM//// (cao)), for all t 1, I....,T. T.
we perform at most poly (BKLM2 /cao)) itera-
Assume that fact that N dCmg((KLLM2 ((eaa) 1og(1/5) for sufficiently large universal constant C > (Line 2 of Algorithm 3) we can apply Proposition D.9 and conclude that, with probability 1- 1- 6, there exists unit vectors v(t) E Vi+1 and unit vectors w(() E W' for t = [T] such that (() (1)
y)21 > (VT+E+ + VOPT)² for all t = I....,T. Using the
Thus, by Fact D.12 we have that with probability 1 - 8. for all E [T], 4, < 2,-1 poly(era/ (BMcea//BMMBB K ))" After T iterations, it follows that Φr I K Tooly (Erae/ (2"M)2"")). However, since T set
Vi 2
2o Tpoly(eaa/ (BM "Tooy(eaa/BMMKL2))) to be a sufficiently large polynomial of 2mm B, M, L, 1/e, and 1/a we would arrive at contradiction, since t 2 0. Hence, we have that E(x.v)~
- y) < (VT+ +e VOPT)², for some t E {1,..., T}. Since the error of hú can only be decreasing by Claim 10.13land and he is close to its sample variant by Claim D.14 we have that ((x.))~[((h(())) - 2 (VT+ 2OPT) +c.
Sample and Computational Complexity: From the analysis above we have that the algorithm terminates in (o /(eaо)) /(aoo) iterations and at each iteration we draw of the order of (((m))poly(Bkkkmm ((aar)) log(1/8) samples. Hence, we have that the total number of samples (0tm)gooly(KKLMMe ((eaa) (1g(1 Moreover, we use at most poly(N) time as all operations can be implemented in polynomial time.
56

---

Remark D.15. While our algorithm is sufficient to obtain polynomial dependence on d for any constant values of and the other parameters, is worth looking closer at the exponent of this poly- nomial. The algorithm that we have presented requires d'M samples in order to accurately estimate the degree-m parts of the relevant indicator functions in Line of Algorithh 4, Observe that there is quadratic gap between this bound and our SQ lower bound. Recall that our SQ lower bound requires either exponentially many queries or a query of accuracy d d-m/4, which in turn requires roughly ddz/2 samples to simulate.
We believe that this gap can be closed with slightly different algorithm. In particular, instead of finding the polynomial approximation ps,r for each S and I in our discretizing approximation, and combining them into matrix U to find directions that are often influential, we instead merely sample (S, 1) pairs and find the influential directions for each sampled pair (and note that with high probability should find one which correlates with W). Then instead of estimating Ps, in L2- norm (which requires roughly d'n samples), we can treat it as an m-tensor T, which in turn we flatten into a d m/22 d ml//2 matrix M. Since by assumption T has a large component in the W- directions, M must have some singular vectors with relatively large singular values that themselves correspond to polynomials in which the W W-directions are influential. We can again find these estimate suitable approximation to M, but importantly for purposes, only need to estimate M to small error in operator norm rather than small error in Frobenius norm. This allows the algorithm to succeed with only around d/m//2 samples.
D.2 Learning Real- Value MIMs: Realizable and Random Label Noise
In this section, we demonstrate that our algorithmic approach becomes more efficient when the label y depends only on the projection of x to a dimennnnsional subspace.
Specifically, we assume that there exists a K K-ddimensional subspace W such that depends on x only through its projection onto W; that is, Prly
x = u] Pr(y = = Xw uw] for all R 2 E R. This is setting that captures both the realizable and the independent noise settings. We refer to this as the MIM distribution setting, indicating that the random variable is a MIM, i.c., it depends only
now-dimensional subspace.
This structural assumption implies that all non-zero moments of the joint distribution are entirely within W. Consequently, our algorithm achieves constant correlation gain in each iteration (unlike the agnostic setting analyzed in Proposition D.9,, resulting in only O(K) iterations overall. This leads to significant improvements in sample and computational complexities.
We begin by formally defining the class of distributions for which our algorithm guarantees a sat- isfactory solution. In Section D.3] we will demonstrate that for several MIM function classes, their distribution of examples belongs this class.
Definition D.16 (Well Reell-Behaved MIM Distributions). Fix d, K, m Z_, a E (0, 1) and M, T, 62 > O. We say that a distribution D over Rd x R whose marginal is Na is (m, a, K, M, r, a,,,,,,,, (2, ee)--ell--bbhawee MIM distribution, if the following conditions hold:
There exists subspace W C Rd of dimension most K such that y depends on x only through the projection onto W, i.e., Pr(x.))~DV = =z x ul Pr = Xw uww, for all Rd TR.
2. The label has bounded variance, i.e., E(x.))Dly"] I M.
3. For any subspace V C Rd with dim(V) < K and for any (m, n2) -pprroiixiigti discretization
(S, I) with m S eı, 1/2 52
(a) either E(x,a)~ (hs(xy)) 2) < r, where hs denotes the piecewise constant approxima- tion of according to Definition D.4
(b) or there is subset T C
S such that ESET Pr[S] 2 and for U = Wvi, there ex- + E of degree at most m and an interval I E I such that
ists a polynomial p : U
E E(xx))-((((x)) (y E 7) |||x x > a <lp(xx)))l I| and E Ex(p(xx:)) 0.
We now present the main theorem of this section, which shows that Algorithm achieves improved complexity in this setting.
57

---

Leam-MIM--Distrbrtion Learning Well-Behaved MIM distributions
Input: Aceuracy E (0, 1), failure probability (0, 1), sample access to a distribution over R R. and parameters distribution.
(m, a, M, 7, o, c1, 62) for which D @-well-behaved MIM
Output: hypothesis h such that, with probability least 1- ((x,))>D((((()) y) +
1. Let C' be sufficiently large universal constant.
2. Let L1 0, +
(mmKK((teea)) log(1/0).
3. Fort ,.....TT
(a) Draw set St of N i.i.d. samples from D.
(b) & Algorithm ( , /i/Kt, <2, 1/62, (oa/ (aa/K), Sp,n(L)),S,,00 (c) Construct L by adding one vector of & to L1-
4. Construct 8, an 61 aaappooximt partition with respect span(L.) (see Definition D.2).
5. Draw N i...d. samples from D and construct the piecewise constant function hs as follows: For each E S, assign the median of ((log(166) means of the labels from the samples falling in S.
6. Return lss.
Algorithm 5: Learning Well-Behaved MIM distributions.
Theorem D.17 (Learning Well-Behaved MIM Distributions). Let D be (m, K, M, M,,,,,,1,,2) well-behuved MIM distribution supported on Rd R. Then, Algorithm 3 draws N (dm) ((m)) (m/ htep/(cc2g00) (M((a))) log(1/6) i.i.d samples from D, runs in time (Nly(N), and returns a hypothesis h such that, with probability at least -, 6,
log(1//
E B(x,))-D((((x)- - v) S +ec
We now prove the following proposition, which demonstrates that compared to the agnostic setting (see Sreppostoni
correlation can be achieved in the MIM distribution setting.
Proposition D.18 (Correctness of Learning Well-Behaved MIM Distributions). There exists sufficiently large universal constant > such that the following holds. Let D be (m, a. K, M, T, (1, (2)-well-eehawe with dim(W)- = K be the hidden subspace of D. Let V C IR be a k-dimensional subspace with S K such that [[ 1 || S é' S ele162ar / K)C for all unit vectors v E.. Also, let (S,I) be an (e1/K), (ea/KK,,))-aproxttii approxiixingg dicretization of V x R. Additionally, let lig be piecewise constant approximation of D, with respect to S. There exists N = (dm) (K()(KA)) (K/e) ((k)))))))))))))))())))) log([Z)) (() such that if (xxxy)>DD(l (()ss)((((x))----))))>>>>>>))>>) - > t then Algorithm 4 when given N i.i.d. samplesfres D and parameters S (eaeza/(mkK)) ,e//K,, E2, x= = (arax/ K)) runs in time poly (N) and, with probubility least 8, returns list of unit vectors & of size | poly(mK) (mK/((KKad (e2nk)))))) such that for every vector E, there exists a unit vector w E W with w v 2 1 1
MIM distribution supported on Rdd x R and let W C Rd
Proof. Let Ú be the matrix computed in Line 3 of Algorithm and let r7² be the L3 error chosen in the polynomial-regresson step, i.c., Line of Algorithm 4
In the next claim, we show that if the sample size for cubic region S E S is sufficiently large, then for every I E I the influence matrix, Ms., def Ex~D, (xx. (xyx) T x E S), (see Line of Algorithm 4 has small quadratic form when evaluated for any unit vector in W- + V.
Lemma D.19 (No Bad Vector). Fix S E S. Suppose that the number of samples falling in S is Ns 2 (dm) Cm (og(1/(6e)))) C for sufficiently large universal constant C. 0. Then, for any unit vector E (V + W-) )) n V- we have that v Ms $ (K3é/e))² mn?
Proof of Lemma D.19 Let Ns. S E S, be the number of samples that land in the set S. First, observe that the guarantee obtained at the regression step
E [( E !) 1)-p). (x)=)) x S] < min E( E ()-x(xx=))² x S1+?
p PP
58

---

is equivalent to
E(x [1 -
min E E(x.))=De [1(y ( p' (x)) +
MeE
where Dÿ is defined to be the marginal obtained by averaging D over V conditioned S, 5). Moreover, by the properties of the Gaus- sian distribution, we have that the x-marginal of D is a standard Gaussian and denote by k' def dim = d Hence, by applying Fact E.9 and the union bound, we have that with Ns = (dm))(m) ())1((( (11) i.i.d. samples and runtime poly(Ns, d), we can compute poly- nomials ps, that satisfy the aforementioned condition with probability at least 1 6.
Le., (Xy1,
Exv (D(x,
For 3 E NK', the Hermite coefficients of Ps, and 1V E 1) are defined by (s,r(3) def E (x Ti [Hs(x)ps.rxx)] and (3) def ((xa)>D [Hz(x) E T)]. By the orthogonality of Hermite polynomials, we have
E Ex
E (
BERN
Thus, restricting the sum multi-indices B with S || S m. it follows that EsENt .15 1m (3) Dr (3))2 < 17.
Note that (B) E. [zv Pr E Xv E S, xy.]]. For E V define Xv E S, =v=
the function g(z) def Pr(x,))nll
In the following claim, we show that the directional derivative of the function 9 in directions within V + W is small. This implies that the quadratic form of Ms, in these directions is also small, since I and ps,s match Hermite coefficients.
Claim D.20 (Directional-deriiativv bound on the averaged indicator). Fix interval T E I and cube S E S. Let u E (V + W--nV- be a unit vector. Then for all x E V- it holds that
K5d
g(x + su)
S
Proof of Claim D.20 Define the function ((2) Pr(x,)iDDu E / z] and note that for all z E IRd holds that g(zv1) = [x + _) Xv S, = zy1].
Let a b, where E V and b W Since E V it holds that ||a|| + a b Note that by assumption |a Aw || S é' ||a||. thus aw aw + ||a|| for some unit vector v E Rdd Hence, we have that ||a| = ||al| ||a|| (v-b) which implics that ||a|| < ||b]] Therefore,
0.
by triangle inequality |bb| S ||a|| + 1 as result | O(e)).
Since y depends on x only through the projection onto W, we have that g(x + tu) g(x ta). Thus, shifting x by tu is equivalent to shifting by ta.
Denote by y standard normal random variable over V and by standard normal random variable over V-_ From the fact that g is invariant in changes in W we have that
Ey [g(x + y + tu) SS] Eylg(x + + ta) e S)]
ø(x + tu)
Priy E S]
Priy E
Now define the random variable def y fa. By change of variables we have that
Eg Fx 2) la E 5)]
[(x + (n)
Priy
Therefore, shifting the argument by tu results to shifting the box by tta Thus, in order to bound the derivative, suffices to bound Pr[SA(S- ta)]. where denotes the symmetric difference of the two sets.
Recall that the edge width of each cube is c KM, as defined the statement of the proposition. Denote by ó V + E the density function of standard Gaussian random variable in V and by
59

---

v(O v(a) the orthonormal basis of V used to define S. Note that from the anti- concenttennnrnnnn of the Gaussian distribution, suffices bound the volume of the symmetric difference. To this end define the following sequence of sets 5 = So St,... Ss S la, where S; is equal to S - -i v y!!)) By the triangle inequality and a simple volume calculation we have that
Pr[SA(S - ta)] = Pr[I(x S) & 1(x E (S -ta)]
Σ Pr[ St-1) * 1(x E S))l
$ (2/K 11) Σ e v00)
sup
o(x)
xESU(S-ta)
KE
< (2/K 1/ |La||
sup xESU(S-ta)
<(x).
where in the last inequality we used the Cauchy-Schwarz inequality. Define the following ratio
ps(() def (S 6(x)
inf ((x)
Therefore, we have that
[ + tu) - [(x) Pr[SA(S ta)] Pr E S)
K infxes oxx)
Pr(SA(S ta)]
of
V |taal
K
ps())
of
S K kkttle
ps((),
where in the second equation we used the fact that Pr(x S] 2 infxes ((x)e /K and in
the third one we substituted our prederived upper bound for Pr[SA(S ta)]. Finally, note that
ps(() = exp((x y) (x + y)/2) for some S and y E SU (5 ta). Hence, lim Ps(() s exp(e1 K /og((=)) (e)) which is bounded by constant since < K. This concludes the proof Claim D.20
L
Let unit vector E (V W V-, from Claim D.20 we have that ju Vo(xv ) S Koe'/ei for all x e Rd. From the rotational invariance of the standard gaussian, let us for simplicity denote u by 01. By applying Fact E.6 we have that
Σ BeNA
Consequently,
(K&e) (K))) + mnj²
c E (x (xps, le
Σ BENK
(
é1
This completes the proof of Lemma D.19
First note that by the definition of an approximating partition (Definition D.2 and Fact E.2
pattiiittinnatttttitoooooooo for all S S have that Prp [S] = (c (KI(()))))()) and [S] (kK/ee) j (k) Therefore,
by the union bound and Hoeffding's inequality, it holds that if N 2 (kK/a)) ck log([S) (((([[///)) /8) (kK/e,) log(1/8) for sufficiently large constant C > 0. then with probability at least 1 8 we have that Pr S]] - Pro[S]] < Prp[S1/2 for all E S. Hence, Pr 2 Prp[S1/2. /2, i.c., the number of samples that fall in each set S E S is at least NPrp/S]/2 = ((aE(K))))*())
Therefore, if N 2 (dm)Cm/ (kK / C* log(1 (00(11((rg))) ((5e2))/f² for a sufficiently large universal constant C. > 0, then by applying Lemma D.19 we have the following: with probability 1 - 8, for any unit
60

---

vector V E (W) + +ANVA
( 61
+ mn? Prşls] s II ( ) 61
V S
E SES,JEI
+ mn²
Hence, since Ü is symmetrie PSD matrix, applying Fact E.8 have that for all E & and unit vectors V (W+ VV- it holds that Ju vl S Vmn² + (K3e'/E))² (/plel///////aaaa////// (mn²² + - poly(orza//K) As a result, substituting é' and n, since C' is a sufficiently large constant, we have that for all u E and any unit vector v (W+ + V) n V it holds lu.v/ S e. Note that the subspace space (W + +V))V* is the subspace constructed by projecting every vector of W to V Consequently, for any unit vector V E W and any u &, we have that [vy u/ [|v IlI S 6, which implies that |v ul S since l|v S..
S
Consequently, by applying Lemma D.10 (dm) Cm (kK/a) CK non-empty. Thus, as any E & is a unit vector and ||ug= See, we have ||ww|| || 2 v1 - e > 1 6.. This completes the proof of Proposition D.18
have that if N for a sufficiently large universal constant C > 0. the set & in
Now we are ready to prove Theorem D.17 Our proof similar the proof of Theorem D.5 The difference is that we are going to use Proposition D.18 which provides improved correlation when compared to Proppsstion D.9
Proof of Theorem D.17 We show that Algorithm 5 with high probability, returns a hypothesis with L3 error most + Let W be the K-dimensional subspace that y depends on. Let Le be the set of vectors maintained by the algorithm (Line Be) and V- = span [Te) dim(V) = 1y- Also let <1 be the partition width parameter (see Definition D.1 and for E [T] let S, be arbitrary c1 K approximating partitions with respect to V. (see Definition D.2). Let he IR + [K] be piecewise constant functions, defined as h2 hs. according to Definition D.4 for the distribution D.
Note that from Lines of Algorithm 5, we perform T def K iterations. Furthermore, in each iteration, we update the vector set by adding one vector. Hence, k2 I K for all t E [T].
Assume that (xxx)) ( y) > + c/2 for all [T). Denote by v(t) E Ve41 V [7'] the unit vectors added at each iteration and let C be sufficiently large universal constant.
Note that in order to add a new vector ((f) E Vi+e n Vg" with [
1--P-- by applying Proposition D.18 we need to already have that every unit vector v E Vi-1 satisfies || Z 1- p(E1eeaa/ / ( Moreover, since (t) are orthonormal in this case, for all unit vectors E Ve Thus, the number of samples is sufficiently large, for all iterations E [T] applying the proposition for (E/(2)))( (m/ga//mmm))))) (in place of <) would result to orthonormal vectors ((() with ([(v()) 2 - 1/2K for all t E [K].
it holds that v 2 1 - p(c1c2a/(mKK)
(Line of Algorithm 5). we can iteratively apply Proposition D.18) and conclude that, with probability 1- 8, there exist unit vectors (() E V4+ and unit vectors ((() E W for t E [T] such that
Therefore, using the fact that N (dm) Cm (m K (()))))) (MM/(e)))))))(()))))))))))))))))
w(O) (1) > 1 - 1/(KK). Thus, from Fact D.12. have that with probability 1 - ô, for all I E [T]. 6 < . - 1 +111 1/(2). After 7 iterations, it follows that क < $ - T T/(2K). However, if T is set to be K + we would arrive at contradiction, since Φf 0. Hence, we have that ((xx
2) < + e/2, for some t E {I...., T"). Since the error of h1 can only
be decreasing (see Claim D.13 and he is close to its sample variant by Claim D.14 we have that (xx.))>D[(((x - < +e.
Sample and Computational Complexity: and at each iteration we draw N log(1/0) samples. Hence, the total sam- (M/(()))) log(1/5). Moreover we use at most PNly(N) time, as all operations can be implemented in polynomial time.
Note that the algorithm ter-
minates in O(K) iterations
(dm) ((m) (0/
ple size is (dm) ((m))oyyy
D
61

---

D.3 Algorithmic Applications to Structured Multi-Index Model Classes
In this section, we show that our general algorithm can be leveraged to obtain sfte-of-the-ar guar- antees for learning posttie-homogennouu Lipschitz MIMs and polynomials in a few relevant direc- tions. The former result is new and subsumes prior work on homogeneous ReLU networks.
D.3.1 Learning
Lipschitz MIMs
For each application, we show that the resulting distribution D over examples (x.y) is a well- behaved MIM distribution with favorable parameters, and we consequently apply Theorem D.17
First, we recall the target class definition.
Definition D.21 (Positive- Homooeneous Lipschitz MIMs). For K E 2,4 and > O, we define HK,L to be the class of all I--Lipschitz K-MIMs f Rd -> IR such that f is positive-homogeneou meaning fttx fx) for all t > 0 and x Rd, and f has unit L norm under the Gaussian
distribution, that is, Ex~NN If (x)
This class generalizes the class of Lipschitz and homogeneous ReLU networks of arbitrary depth, since the ReLU activation is itself rositiv-hhomggenee we can learn the aforementioned class efficiently. Specifically, note the following theorem.
We prove that by applying our algorithm
Theorem D.22 (PAC Learning H...). Let f IR + IR be a function in HK... and let D be the joint distribution of (x,, fx)), where ~ NN. Then, Algorithm 5 draws N d2-20K3 log(1 /8) ii.d. samples from D, runs in time poly(N), and returns a hypothesis h such that, with probability least 6,
6, it holds ((xxx))((((()) y) <.
Moreover, consider the following class of bounded depth ReLU Networks.
Definition D.23 (Lipschitz and Homogeneous ReLU Networks). Let Fs.K.L denote the concept class of Z-Lipschitz, homogeneous (feedforward) ReLU networks over Rd of size S that depend only on the projection onto a subspace of dimension at most K. Specifically, f E Fs,K,I. if is T--Lipscitz, [x=_A,[]3(xx) = and there exist weight matrices W; E R k1 = d and kD = 1, rank W1) I K, for which fx) = o W WDD1( ( ....)) )), where <(z)= 2 2, 0} is the ReLU activation applied entrywise, and k + KD-1 = S.
(D 1] with
Since the class of ReLU Networks we defined is positive homogeneous we can apply Theorem D.22 and obtain the following implication.
Corollary D.24 (Learning Homogeneous ReLU Networks). Let f ; Rd + R be a ReLU network in the class Fs.LKK and let D be the joint distribution of (x, fx)),, where x ~ No. Then, Algorithm 5
draws N = d220 (+ log(1/8) i.i.d. samples from D, runs in time (N)y(N), and returns hypothesis h such that, with probability least 1 6, it holds (ikag)>D(((()) y) se.
Lipschitz functions We remark that our primary result about learning general proper algorithm that always outputs not achievable by the algorithm of [CKM22), as homogeneous ReLU network. The fact that we use general approximation of Lipschitz functions by piecewise constant ones (Definition 1.4) makes this result possible. Furthermore, the complexity of [CKM22 depends exponentially on the size of the network S, which can be significantly larger than the rank K of the first layer.
Before we prove Theorem D.22 we first present a key structural result for the class HK,r. For distribution over Ra x IR, a function f IRd -, IR, a scalar r >> O, and a subspace V C Rd. define the following matrix:
V del
E(x,))D T(xy, v) (xx= - [yzt]. T(xv. v) 11y-1111--- fxv) T).
The following lemma states that this filtered second moment matrix has large correlation with some direction in WLV.
Lemma D.25 (Generalization of Lemma 5.5 in (KM22)). Let V. W be subspaces of IRd with dim(W) = K, dV) = k and V C. W. Let Rd + R be a function in HK.L such
that f(xw) f(x). Suppose that Ex [[[(x) f(x))) 2 2 for some 0. For
62

---

T> 2VK - and M. E Baxd the matrix defined in Equation (3) we have that there exists unit vector W such that w M. w 2 e e-3K
VR12
Proof of Lemma D.23 Let U denote the projection of the subspace W onto V-. Note that since f is L- E-Lipschitz the condition [f(x) f(xv) 2 2 - &L implies that ||x=| 2 2(K k). As result, by taking the trace inner product with the projection matrix onto W, we have that there exists a unit vector E W such that
w MM 2 (K- ())r)))r(/(()) f(xv) 2VK- kk]]
Note that since f is positive-homogee homogeneous function we have that f(x) f(xy) is positive- homogencous. Moreover, because f depends only on the projection x onto W and V is subspace of W. the function fx) f(xv) depends also only the projection of x onto W. Thus in
der to complete the proof it suffices to prove an anticoncetration result about positive-homogeneous functions:
Claim D.26 (Anticoncetration of Positive- Homogeneous Functions). IfG R.K - R is positive-
homogeneous and L-Lipschitz and E 2 o², then for any 2 0,
Prx~Aw [G((x) s) 2 exp(-3K 3Ks 02))
80
VKL
Proof of Claim D.26 Note that if x ~ Nx then it can be decomposed as x = vrv where X
and v is drawn uniformly from S independent of r. First note that by independence and we have that
0² Ex~NK (x E[r]E KE(G
Thus, E[G²(v)] = 22/K. Hence, by elementary anticoncetration Fact we have that
(Xxwx1/G((x)) 2 Pr|rG2 2 2 Pr(r 2 2Ks o Pr[ o/V2K)
a²
2 Pr(r 2 2K'²/0
2KL2
2 exp( 3K33 //2
30
VKL2
where we used the well-known fact that Pr Pr 2 fr
>
> crfc(1/vz) and erfe(r) >
12/T me = #+1 for all x Which concludes the proof of Claim D.26
Therefore, we can apply Claim D.26 for the function f(x) - -xxv), which concludes the proof of Lemma D.25
Now following this structural result, in order show that the class H.K. & leads well-behaved MIM distributions and allows the application of Theorem D.17 it suffices to establish the existence of non-trivial moments for a cube-interval pair.
We prove this result in two stages. First, we show that if it is possible to obtain distinguishing region of V R that is well-approximated by cubes and intervals,
moments by conditioning then there exists a specific cube-interval pair exhibiting distinguishing moments. Consequently, we prove that the region T defined in Equation (3) can indeed be well-approximated by such cube- interval pairs.
Lemma D.27 (Label Transformation Approximation). Let be a distribution supported on IRd x IR, whose x-marginal is Na. and let V be subspace RRd. Suppose that T(xv, uy :): V x R - {0, 1) is label transformation function and that p I + R. is a mean, variance such that E( wppppppppxpppppp (x)]TxxVVvvv 4)] 2 O. Let P be a partition of V x R. and let P' C P. Define the
polynomial
approximation T(xv, y) def EnEP ((xVv, y) E R). If PPixx)>D(((Xxxss + T(xv. S d²
then there exists some R E P' such that E [ (xx ((xv,y) R)] 2 2...
63

---

Proof. First we can write
((xx)))D(((x)X((xx v)] Eix,y) (xx)) (xx,))> ( T(xv, w))]
Therefore, have that
((x,)) (ptn))/((xxT(x///) w) 2 - 1 ( (x(x) - F(xv,8)]]]
Since p(x) has variance one, by Cauchy- -cchaa,,
E (x.)) ((()) - T(xv, - VV Elpxx)) T(xv, ()),, va12.
Thus,
(xxa)>/lp(x)T(pp 5)1 2 0/2.
We can write
E Dxx,)>((p(x)) (xv,
Σ
(x (p(x) v) R)]-
REP
Hence, by the pigeonhole principle, there exists some E P' such that
(xx,))~ [x(x) y) R]
E (xx.)) (x Pd
2
This completes the proof of Lemma D.27
In the following lemma we show that the label transformation defined in Equation (3) can be ap- proximated arbitrary well by a piecewise constant function over discretization of V R in cubes and intervals.
Lemma D.28 (Cube-Interval Approximation of T). Let d, E Z4,c,
(0,1), T, E E R+ with
L > Let V, W be subspaces of Rd with V C W, dim(V) = and dim(WW K. Let fxxw), and let D be the joint distribution of (x, f(x)) where x ~ Na. Denote by T V x R - {0, 1} the function defined in Equation (3) Let
f: Rd +R be function in HK,L such that f(x)
(S,I) be an nrapproximating discretization of V x I. with S e (LVVk))
There exists subset of the discretization P S S x I such that for the function T(xv, ,y) = E(snee (xx S.y I) it holds that Pr(x.)) (T(x))))))((....... y) T(xv, y)l Se.
assume that the discretizations S and I of the spaces V and IR, extend to their entire respective domains (see Deeinition D.3). This is justified because the partition S is defined over the subset of IRd whose coordinates, are most / Vlog(k/n). By the union bound, the probability mass outside this region at most n. Similarly, the same holds for I, since Ix probability mass outside the relevant interval when |y] 2 1/e". As result, by the union bound, we have
Proof. Without loss of generality,
orthonormal basis of V.
1, there is at most an fraction of the
Pr T(xv,2) 9) + T(xx, v),
Usv u
U1 2ec
SES
JEI
((xv.0) : f(xv) 7) be the boundary set of boolean function T. We set P to be the subset of the discretization regions (S, I) with 5 E S and I E I such that for all points in (Xv,y) E (S, I) holds that ly - f(xv) > т. Note the diameters of the sets and are Vin and 77 for all regions (S,I) with S E S and I E I respectively. Hence, we have that (r(x.))nn[TG (Txv, .xv.v) v) * T(xv.v) < Pr(x.))n((x)) E def [(xv, v) (x v/) E A: |XV I'vll S Vlnn, by - S n)
Define the set
E E], where we define
Note that for every (xv, 3) E E since f is L-Lipschitz we have that by f(v)) = 2L Therefore, it suffices upper bound Pr(x.))>oly f(xv) + 2L km) or in other words to show anticoncetration of the random variable y f(xv) = f(x) f(xv).
64

---

Define the parameter ò = 2Lvkn Since f depends only on the projection onto the K X-dimensional subspace W. the function g(xv) f(x) f(xv) also depends only on Xw. Moreover, because is
TR= - RR by g(z) = f(z) - f(zv), ) which is likewise positve-homoogeeeuss and observe that g(x) = g(xw). )
so is 9. Hence we may define an induced function
Under x ~ Na the projected vector Xw is distributed as NK- Therefore Prx-N,, [x() = +
Prz~Nx (ğ(z) = т 8.. and one can carry out the anticoncentration analysis on the positive- homogeneous function IR* + IR.
We show anticoncetration of the function g. We do this in two stages. First we show anticoncetration over fibers, i.e. fixed lines that go through the origin, and then we take the expectation over fibers.
We can rewrite gaussian vector rv, where as a uniform unit random vector and scalar random variable independent v such that y² ~ XK- Note that for any fixed direction v it holds that
Pr[7(x) = T T = =| Pr(rī(z) = ö]
Let a > be a parameter to be quantified later. First, consider the case where [ō(2) 2 a this case by the Carbery-Wrige Wright inequality (seeFaact E.5) we have that
S Pr r == (r+ -
V78
Pr(rī(z) = r + 5 v=
K1/4
Second, we consider the case where [[(2] < a. We have that
Pr[rī(z) = T v = z| S Prir 2 (2a)))]
since 5 2 7/2. Note that setting / (2v K by the Gaussian Annulus theorem Fact E.3 we have that Pr(rī(z) = r = 8 = 2) < e - vkjā - V0/K.
Thus in both cases we have that Pr(rğ(z) = + 8] s (K8) Taking the expectation over v completes the proof of Lemma D.28
Moreover, we can also show that f is very close in squared error to a bounded function. This is needed order for us to be able to approximate f using finite collection of cubes.
Lemma D.29 (Functions in HK.L are almost bounded). Let f : I + E be a function in HK,,L
then for any B CVRL (nLK/e)) a sufficiently large constant 0, there exists a function fB Rd B, B) such that Ex--Nil(fxx) fB(x)) S.
Proof. Define the function fa(x) = sign(f(x)) min (ff(x)), B). Note that since f E HK,L from Fact E.3 we have that for t > LVK and some universal constant C' 0
Pr[lf(x)] 2 t] < Pr[]|xw| || 2 t/4] S -CU((R)))))
Therefore, by applying this tail bound, we have
[[(((x) fx(x)) E[ > Bj = B'Pr([((x) B] / Pr[]((x) 2 tldt
Ba
B CBBLLK) +2
[Pr[ff(x) 2 tldt
=E-CBILWR)(B + BLVK/C" LLVK/C")
Choosing B be CVKLIn(LK)o) for sufficiently large constant C 0, completes the proof.
Finally, before proceeding to the proof of our theorem, we make the following remark concerning the precise dependence of our algorithm's sample complexity on the dimension.
Remark D.30. We remark that the sample complexity bound in Theorem D.17 is (m)))))), since at each step we perform polynomial regression of degree m (see (seeFaat F.9p. In the special case m = 2, reduce this ((d)) by noticing that the polynomial regression task is directly reducible
65

---

to covariance estimation in the Frobenius norm. Furthermore, achieving O(d) sample complexity possible by replacing the regression in Line with a simple covariance-estimation step since covariance estimation in the operator norm requires (d) samples. Concretely, for each interval I E I and region S E S, define Ms,1- = ((x.))_D [
E (xx 1) x E S), and let uy,s be its top eigenvector. Then, following the filtering in Line set Ū Σ EIeI.sEs y ur,s vi.s fl Pr[S].
By essentially the same argument as in the proof of Proposition D.18 Ü provides an arbitrarily accurate projection onto W, while it requires only (dd) samples.
now prove the main theorem of this section, which shows that the class HK,L can be learned efficiently using our algorithmic approach.
Given Lemma D.28
Proof of Thhorrmmm D.22 Let V C IRd be a subspace of W, and let (S.I) denote an n-approximating discretization of x I. where v def E cc (see Definition D.3
The proof consists of showing that D e CK ,K, e, , CK , -
well-behaved MIM distribution, as in Definition D.16, for sufficiently large constant C > 0, and then simply applying [Teorrem D.17
First, observe that for the distribution D Conditions (1) and (2) are satisfied with parameters (xx,))~>N, [v2]] 1 and dimension of the low dimensional subspace equal to K.
Let W be K dimensional subspace of TRd such that f(x) f(x") (existence of W is guaranteed since f E H...) and let V a subspace of W. Notice that since rj has been chosen appropriately small Fact D.32 and lemmas D.27 and D.28 together imply that if Ex~AN,
(xxx)) 2 c, then there exists (S, E (S,I) and zero mean, unit variance polynomial p : Wy R of degree at most such that ((x.))= (p(w,, [y E T) Xy E E e
We can generalize the above statement for a general subspace V of Rd with dim < K by noticing that f also depends only on W = W + V. Since V C W and dim(W") S 2K we have that if Ex=Na (a.=Nal((((x [[f(x) - ((x))) 2 e, then there exists (S,1) E (S,I) and zero mean, unit variance polynomial p W Eー + R of degree most such that E(x.))DD(((xw; )((y E 1) xy E E 2 c-8CK$12/2 Noticing that W Wv= gives us the statement for a general subspace V of R. of dimension at most K.
Therefore, by the assumption that is L-Lipschitz, to verify Condition (3), we can apply the aforementioned statement along with [emmas D.6 and D.29] imply that if for a piecewise con- stant approximation hs (see Definition D.4p holds that ((xs)))((hs(x))) - y) S c, then E(x.))~D (p(p)> (ı(( E 7) XV S) 2 e 320 1.2/22 Consequently, conclude that Condi- tion (3) is satisfied with the specified parameters.
Taking into account Remark D.30 on the sample complexity of the algorithm, concludes the proof Theorem D.22
D.3.2
Polynomials in a Few Relevant Directions
In this section, we demonstrate an application of our algorithm to the problem of learning polyno- mials that depend only few directions. Specifically, consider the class of a-non-degemerate, low-rank polynomials.
Definition D.31. A polynomial q Rd R is a-non-degenerate if
M = Ex-M2 [x(x) Vg(x) ]] satisfies M > a M
We say a rank-K K polynomial p Rdd + R is non-degenerate if p is non-degenerate in the K- dimensional subspace corresponding to the relevant directions. That is, there exist orthonormal vectors w(!), ..... (K) such that p(x) q(((1), x.... (K) x) and g is non-degenerate. We denote by Pa the class of a non-degenerate polynomials of rank K, degree at most m that have zero mean and unit variance under the standard gaussian.
Note the assumption on the mean and the variance is without loss of generality as we can normalize the samples and obtaining a variance dependency however we assume it for simplicity. We first
66

---

present key structural result of [CM20] for the aforementioned class of polynomials, Specifically, for distribution D of Ie x I. scalar r > 0 and subspace V with orthonormal basis v dim(V) k define the following matrix:
v (8)
M (EiXWDD ((xx. (xv: (Tvv))-ITyy) 01) T(xv, ((v) > 1 x $1,46 [+:)
The following fact states that this label transformation T leads to non-trivial moment.
Fact D.32 (e.g., Lemma 4.2 (M20 Let d, m. K Z+ and > O. There exists constants and that depend only on K, m and a such that the following holds. Let V and W be a subspaces TR with dim(V) dW) K such that |v 1- X for all unit vectors V. Let p R - TR. be a polynomial in the class Pk.. mm (see Definition D.31 with p(x) = p(xw). There exists unit
vector Wv+ such that u MMu u
In the following lemma we show that the label transformation defined in Equation (4) can be ap- proximated arbitrary well by a piecewise constant function over discretization of V E in cubes and intervals.
Lemma D.33. Let d, E 2④ and let >> such that < C, for a sufficiently small constant and variance under No. and let D be the joint distribution of (x, p(x)) where x ~ NN.. Let V be a k-dimensional subspace of RR, k 2 1. Denote by V R + {0. 1} the function defined in (4), and let (S. I) be e-approximating discretization of V x IR (see Definition D.3). Assume that T and S are defined with respect to the same orthonormal basis of V. There exists a subset of the discretization
<> O. Let p Rdd -> R be a polynomial of degree that has mean
P. S S x I such that for the function Txxv, y) = E(,NE 1(xv E S,y E 1) it holds that Pr(x.))-((((xxx y) + (xxx, u)) = O(ke + m/m)
Proof. Let v(1) ,i.,,.., (kk) be a basis of used to define T; this same basis also used to construct the e-approximating partition S. We construct P cartesian product of subsets S' S S and I' CI
Define R def {x: (v(0)x < 1,i E [b]]. Since 1 < Vlo((//)) for e S c, for sufficiently small constant e > 0, it follows from the definition of an c-approximating partition (see Definition D.2)
that for all x E R, there exists some S E S such that x E S.
We define S' to be the union of the sets S E S such that S C R. Note that in order for Eses' I (x S) and 1(x IR) to disagree on some point x E Rd, must be that [y x| E [1, - e| for some
i E [k). Indeed, if x satisfies (v()) x < 2e for all E [R). then the corresponding contains xSS must lie lie entirely within R
that
Using the union bound and the anti-coneentration of the Gaussian distribution, we obtain the fol- lowing bound on the disagreement probability
Prx Ri E [k] /v() x E [1, -e]]-]]]-- 2ke
Next, since Ex,,N (x)) 1, by Markov's inequality we have that Prx [ly] 1/62 S 6.
Hence, all but an fraction of the probability mass of y that satisfying the condition [y] 2 r lies within the discretization Urer!!
We define I' to be the union of all I E I such that for all y E I, we have that [y] r. Then, similar to the argument above have that
Pr| E I') + 1(y) > +) < Pr[lvi E (r (r) S me! 1/m
where the final inequality follows from the Carbery- inequality (see Fact H.5). union bound concludes the proof of Lemma D.33]
Applying the
Now given Lemma D.33 we can prove the following theorem which states that polynomials a few relevant directions can learned by using algorithmic approach.
67

---

to Theorem D.34 (Learning Polynomials in Few Relevant Directions). Let K, m. d E 24, > and ò, (0,1). There exists constant C(K, m.aa a) that depends only on K, m and a such that the following holds. Let p Rd + R be a polynomial in Pk. (see Definition D.37) and let D be the joint distribution of (x.p(x)) where x No. Then, Algorithm draws ii.d. samples from D, runs in time poly(N). and returns
N de log(L/8)C(K, m, a)/c0(kk)) a hypothesis h such that, with probability at least - ô, it holds E(x.))-D((((x) y) Se.
Proof. The proof is very similar to the proof of Theorem D.17 Let W be a K K-dimensional subspace of Rd such that p(x) - p(xw) (note that the existence of W guaranteed by since E P,
First, observe that for the distribution D, Conditions (1) and (2) of Definition D. 16 are satisfied for (xx,))= [y²]| 1 and dimension of the low dimensional subspace equal to K.
We can apply Proposition D. togetherrrr with Lemma D.27 and fact D.32 iteratively K + +1 times to obtain subspaces Ve, each of dimension t I for & K 11, starting from V1 {0) (exactly as in the proof Theooer D.17 Using N d? log(1/6)C m, a)/c samples and poly (N) time for all K iterations, we have that every unit vector in VK+1 is arbitrarily some unit vector in W
Using this we prove that ||lw 1lvll c/(mK). Denote by V def VK+1. by { and (O) orthonormal basis of V and W respectively. Also denote by My and Mw matrices that have { and (W( as column vectors. We have that
K
W - Tv & My My K
Σ
IM S Swllse/mmi (/(m))
E1
Hence, it also holds that [II 1 || = W[Iw Ivll S </(m)).
Therefore, by applying Fact E.6 we have that Ex- ( S m. Hence, the difference E(p((x)) Elp(z + xW,, we have that after K iterations that there exists function g(xv) that achieves error e.
xwyl)] can be bounded above by O(e) using/Claim D.8, Thus,
Finally, note that from the well-known fact that for t > 20(m) holds that Pr[pp(x) 2 f] S cxp(-0(mt2/m)) by simply integrating we can show that p is c-close in squared error to a function bounded on [-B, B] with B = mm)0(m) Hence, we can apply Lemma D.6 and claim D. 1. for the aforementioned number of samples for the output hypothesis h. Taking into account Remark D.30 on the sample complexity of the algorithm, concludes the proof of Theorem D.34
conclude that the difference E(x.g)> ((xx,))~=[(((x))) - y) O(e),
E
Omitted Technical Facts
E.1
Basic Mathematical Facts
Fact E.1 (see e.g. Claim 2.3 (KRS23). Let 1 S n. Let ma with BBT holds that
Im
= B & H. (x) E R".
Fact E.2 (Gaussian Density Properties). Let N be the standard one one-dimensional normal distribu- tion. Then, the following properties hold:
1. For any t > 0, it holds e -1//2/4 S Pr > $ S R11222
For any a, b E R with a < b, it holds Pr Pr la S < bJ s (b a)/V2m.
Fact E.3 (Gaussian Annulus Theorem see e.g.. Verlg)). 1fx ~ Na. with probability at least 1 T
we have that ||x]] d < log 1 + + V dlog?
Fact E.4 (Gaussian Hypercontractivity; see e.g., ('D144) Let Rd R be polynomial of degree at most m. which has zero mean and variance one under the gaussian distribution. For every real number q 2, we have [|p] b (g 1) ||
68

---

Fact E.5 (Carbery-Waid Wriggtt Inequality see e.g., [CWOl])
pe R + BR be polynomial of degree
m. If Varx-N, [x(x]] 1, then it holds that for any R and e > 0 Prx-NN [l]lll(()/))))))))(())) - t S 2
Fact E.6 (see, e.g. Lemma 6 in KTZ19) Let f E (2 (Na) with its k-degree Her- mite expansion f(x) Coers so H(a)H, It holds that Ex~Na [(V((x) c.)
E.2 Omitted Content from Section to Section D.3
Fact E.7 (see e.g. Claim B.1 [DIKZ25). Let M E Rdxd symmetric positive semi-definite (PSD)
matrix and let v E Idd with [|v|l S such that v Mv 2 a. Then there exists a unit eigenvector u of M with eigenvalue least a/2 such that Ju . v| Z (a/l[M]]) )3/2 ) Moreover, the number of eigenvectors of M with eigenvalue greater than ox/2 is at most ||//2
Fact E.8 (see e.g. Claim 4.12 (DIKZ25)). Let M E Raxd be symmetric. PSD matrix and let Idd be a unit vector such that v "Mv I E. Let U denote the set of unit eigenvectors of M with eigenvalue at least Then, for every u E U, holds that u v
Fact E.9 (see, e.g., Lemma 3.3 in DKK+21I). Let D be distribution on IRd {+1} whose x-marginal is -Na- Let k E Z+ and c, > 0. There is an algorithm that draws N (dk)o(k) log(1/8)/e² samples from D. runs in time poly(N, d), and outputs a polynomial P(x) of degree at most k such that (xxx))=D(3 P(x)) probability 1 5. 5.
with S minprep, (oy-))-lllPP''x))0
Fact E.10 (see, e.g., Lemma 3.3 in DKK 21h. Fix e E (0,1) and let P(x) be a degree-k polynomial, such that E(x.y)=D(('' - P(x))²I S minpreps E(x.a)=Dlly - P' + O(e). Let
M Ex P(x)VV((x)) and V be the subspace spanned by the cigenvectors of M with eigenvalues larger than n. Then the dimension of the subspace V is dim(V) = O(k/n) and more- over tr tr(M)= Ok))
Fact E.11 (Approximation of a Bounded Variation Function using Cubes). There exists a sufficiently small constant > 0 such that the following holds. Let f R.a - R continuous and continuous differentiable almost everywhere such that Ex-N, [Il V [(x) [13] [x)]l]
L. Moreover, assume that there
f S p. Denote by h : IRd - R the piecewise constant approximation h(x) = Ex-AG, (x(x) x E S1, for all x E S and S E S. where S is collection of consecutive cubes over Rd of width 17 S ce/ (odlog())) i.e. S denotes all subsets Te the
exists B O and fB Rd + 1-B, B) such that Bx-N2((f(x)
the form {x : Jae + 1 L x, S (): + 1)e + 1).J: E zd, E 10,e/2].
Then Ex~N, [U((x - -) + 2p.
exp( exp(-||x/ [x|12/2] and set (x)(x)= = Pr (x E S]. For each cube E S define fs E Exznus (z)) and ms 1/|5| Is (z) du, where we denote by [S| the geometric volume of the set S. Write
Proof. Denote by o(x) = -2/2
ain
inf o(x), xES
mmax
sup Φ(x), xES
Kg
Pmax
d min
Fix R- logo B/e)/c and let T
UIS minxes ||||||
R}. From the Gaussian Annulus
Theorem FFct E.3) have that Pr(x T) S </(S²)).
Moreover, note that since of is close to bounded function, by Jensen's 's inequality so is h. Indeed [[(h(x) (e((x)>ExxxAA,, (x) x E S < p. Hence the tail error approximation error of h is bounded the tail error [xf 1 E T) < 2p + e/2.
Hence without loss of generality we can consider cubes with ||x||| < R for all x E S. Moreover, for those cubes S g T holds that
Kg S
From the fundamental theorem of calculus, for every y, E S, it holds that
f(x) - f(y)= = //' vf + f(x y)) (x y) dt.
69

---

Hence, using Jensen's 's inequality we have
((x))f(yy) < -yl? L. IVV + y1)l s dnd ( IVV + t(x - y)>11 dt
Averaging in y S and then in S yields
|S| [ (f(x) mms) dx S dn² 1
[S] / [x)(
We can transfer the above bound to the gaussian case for all cubes S g T. Specifically,
Bus [CS m
d
max
S
Eunir(s)
[(S m
Pr(s]
max [S]
d (Inirss)|IVV[
Pr[S]
kgdrj E [/
Moreover, since fs minimizes Bpsl(f(x) m) we have
Eps((f(x) - fs) z Eus ((f(( ms)
Averaging over cubes we have
[[(f(x) h(x))) kdn E[]VV + 2p c/2 s Ldknn² + 2p c/2.
Setting 7 (ee((L)og((B)) for sufficiently small constant
concludes the proof of
Fact E.
Fact E.12 (Discretization over a Subspace). Ler f Rd + R is continuous, continuous differ- entiable almost everywhere and satisfies Ex~NN ( S L. Moreover, assume that there fn(())²] S p. Let V be be an orthonormal basis of and let S be the [ʃ(zv
exists B O and fB Rdd > [-B, B) such that Ex~N.((f(x) k- k-dimensional subspace of IRd and let v!1) .....; partition of V into axis-aligned cubes of width e. Define h(() = Exy~ [ +Xv1) Zy E S]. Then Ex~Na [(f(x)(((x))))))))))) hxx)) s L
(k) v(..,,(())
Proof. Let fB be the truncation of f to the interval [-B, B), that is fB(x) sx)n(f(x)) min(I (xx), B). Note that El(ff(x) f(x)) s p since fB is closer to f than any other truncated function.
The function fa is continuous since truncate at the level set B continuously. Moreover, fa is non-differentiable at the points [((x) = () + 0). But by the implicit-function theorem, whenever f (xp) = B and fx())) * there is neighborhood in which {a: f(x) B) is C' submanifold of codimension 1 in Fdd hence of Lebesgue (and thus Gaussian) measure O. Therefore these extra non-iiffcrentiable points lie in a countable union, since each neighborhood contains at least point in Q" of such submanifolds and so form Gaussian-measte 0 set.
Moreover, almost everywhere
V fx(x),
[f(x)) < B,
fx((x) =
0,
[s(x) > B or (f(x) + with Vs(x)
= -),
and on the remaining set ntt-nmmlly {x(x) +B) n { (V f * 0} together with the set of origi- nal non-differentiable points of the function fails to be differentiable but that set has Gaussian measure O. Hence
Ex [[V
E [[V)(()
<
Denote by (x) Ez [a(zv + xy=) zv E S). First, by the law total expectation and the independence of orthogonal components of the standard gaussian we have that
[x(fx(x) h
Ex,, Exy [(fb(x) h=(x))
70

---

For each fixed Xya, we can apply Fact E.Il in the k-dimensional subspace V to the func- tion Oxyi (xv) def fB fx + Xy+), ) which is always bounded by B. Noting that inequality [|Vxy Pxp2 (xv)ll & [[V (x)ll gives us that that for any fixed Xy
Exy [ff(x)) hx(x))9] 2p t
Taking the outer expectation over Xy1 yields
Exl(fx(x) -
S 22p +
Finally, we have that
B((((x) h(x))²²
- 2E((f(x) - fB(())) (f((ff(x) - hn(x))² + ( - h(x)) 2 p ttc,
where we used that (((h((x) - h(x)) - 2p + e because of Jensen's 's inequality.
Fact E.13 (Median of Means Estimator see, c.g., [BM13]] Let Ii..... 2n be i.i.d. random variables with mean μ and variance a², Suppose that mk, where and k are positive integers. Define the median-of estimator Pr. as the median of k = [8 [810g(1/5)] independent sample
means. Then, with probability at least 1 - 6, we have 1in ul V
32 log(1/8)
Fact E, E. (see e.g. Fact 3.3 CKM22)
) 7 is random variable for which / S M almost surely, M (a² 12).
and 7 2 o², then Pr / 2 1
71


Reviews:
[{"review_id": "ZF4Gut7QD0", "reviewer": "Reviewer_xGhv", "summary": "This paper studies the problem of learning K-Multi-Index-Models (K-MIMs), which are models that depend on a K-dimensional subspace of the input.\n\nThe input distribution assumed in this paper is isotropic Gaussian, and the cases of agnostic learning, and independent noise are considered.\n\nThe paper provides:\n\n1. a new algorithm for learning a K-MIM $f$ which satisfies the following condition.\nCondition: for any subspace V,\n- either (i) a good approximation to $f$ can be found that depends only on the input projected to V\n- or, roughly speaking, (ii) if we subdivide the data space $\\mathbb{R}^d \\times \\mathbb{R}$ into fine-grained buckets depending on the projection to V and the label $y$, then with non-trivial probability a degree-$m$ polynomial applied to data from a randomly chosen bucket will be able to distinguish between the case that $V$ contains all of the directions on which $f$ mostly depends, and the case that there are more directions on which $f$ depends.\n\n2. The paper also proves matching SQ complexity bounds, showing that the dependence on the number of degree $m$ of the distinguishing polynomial is optimal.\n\nAs a corollary of the first result, the paper provides a new algorithm for learning homogeneous Lipschitz functions (which includes ReLU networks without biases), improving over the previous result of [CKM20] by removing an exponential dependence on the size of the network.", "questions": "No questions -- am in favor of acceptance", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Clarity: despite the technical nature of this paper, it is quite clear and easy to read. The exposition is well done, and the results are presented in logical order.\n\nOriginality: as the paper itself emphasizes, some of the techniques draw heavily from the very recent paper \"Robust Learning of Multi-index Models via Iterative Subspace Approximation\" by Diakonikolas et al. 2025. The main difference between these papers appears to be (as the paper indicates), a generalization from discrete labels to continuous labels. This necessitates new techniques, which make the technical contributions of this paper sufficiently substantial in my opinion to count as original.\n\nSignificance: understanding the complexity of learning multi-index functions is a central question in understanding feature learning in neural networks, as multi-index functions are a central toy case in that field. This paper helps clarify the picture by providing a new learning algorithm for K-MIMs, along with matching SQ bounds.\n\nQuality: the mathematics that I checked seemed correct", "was_revised": true, "final_justification": "The paper is an interesting contribution to the theoretical literature on feature learning.", "rebuttal": "We would like to thank the reviewer for the appreciation of our work and for providing helpful feedback."}, {"review_id": "yoxqyQuLkw", "reviewer": "Reviewer_woY5", "summary": "The paper presents a robust and efficient algorithm for PAC learning real-valued multi-index models, even under adversarial label noise. It matches its algorithmic sample complexity upper bounds with nearly tight Statistical Query lower bounds, showing the qualitative optimality of the proposed method in terms of dimension and noise tolerance.", "questions": "### Suggestions\n- In Section 1.4, the authors present their techniques as an generalization of [DPLB24] to MIMs. It would be relevant and helpful to extend this comparison to the recent paper [Damian et al., 2025] on MIMs, which addresses analogous questions. Moreover, the cited work [TDD+24] presents a first extension of the \"generative exponent\" concept to MIMs (in the proportional regime). This connection is worth mentioning in the same paragraph for completeness.\n- Points 1. and 4. in the Weaknesses section.\n\n\n\nDamian et al., \"The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models\", 2025.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "### Strenghts\nThe paper is well-written, theoretically sound, and significant. It provides strong results on the learnability of multi-index models for a broader class of functions than in previous works. The exposition is clear and includes detailed algorithmic descriptions, comparisons with prior literature, and explanations of the results.\n\n### Weaknesses\nNo major weaknesses were identified. Minor points:\n1. The second condition in Definition 1.3 is quite technical and may be difficult to parse for non-experts; an intuitive explanation would improve accessibility.\n2. Line 45: is the symbol $c$ intended to be $f$?\n3. Typo on line 202: \"Specificalaly\" → \"Specifically\".\n4. The paper would benefit from a simple illustrative example to help readers build intuition around the main ideas and techniques.", "was_revised": true, "final_justification": "The authors have addressed the comments, I mantain my positive score.", "rebuttal": "We thank the reviewer for their careful reading of our work and for pointing out typos. We will fix these minor issues in the revised manuscript. We address the reviewer’s points and suggestions below. \n\n**Intuition for the Moment Condition (Def 1.3):**\nWe start by pointing out that our submission includes an intuitive explanation regarding this part of Definition 1.3: please see lines 54-56, and 165-178. As mentioned in lines 54–56, the “distinguishing low‑degree moment” condition measures how much improvement one can guarantee when the current subspace guess is off. Concretely, if the guess subspace yields large residual error, then a degree at most $m$ moment will detect that misfit and guide the next update—quantifying exactly how much progress one can make per iteration. If the reviewer has additional suggestions, we are happy to expand on this explanation in the revised version.\n\n**Comparison with [DBLP24]:** \nAs mentioned in lines 245-246 of our submission and pointed out by the reviewer, our Multi‑Index Model (MIM) results can be viewed as a generalization of analogous results for the case of Single‑Index Model (SIMs) studied in [DBLP24]. However, as we explain in our technical overview, the transition to the MIM setting introduces qualitatively new challenges—both in theoretical analysis and in algorithm design—which necessitate substantially novel techniques. Moreover, as reviewer xGhv also noted, our work handles both the noiseless (realizable) and agnostic settings; whereas [DBLP24] treated only the noiseless case. Finally, we emphasize that our focus has been on the task of PAC learning, i.e., computing a hypothesis with low prediction error, as opposed to parameter recovery (i.e., identifying the hidden subspace); see lines 243-245 and 1406-1413. The prior work [DBLP24] on SIMs had focused on identifying the hidden direction (in a setting where it is identifiable).\n\n**Comparison to [Damian et al. (2025)]:**\nWe thank the reviewer for pointing us to that arxiv manuscript (arXiv:2506.05500). That paper appeared online on June 5, 2025, i.e., three weeks after the NeurIPS submission deadline.  As a result, we were unable to include a comparison in our submission. We are happy to provide a comparison in the revised version of our manuscript. Please see our response to reviewer **AGEu** for such a comparison.\n\n**Incorporating [TDD+24]:** \nWe appreciate the pointer to [TDD+24] as the first proportional‑regime generalization of the generative exponent to multi‑index models. We note that [TDD+24] is already cited in the supplementary material of our submission. We will include a detailed explanation and comparison in the revised version."}, {"review_id": "Ek0UiBvJXU", "reviewer": "Reviewer_rcRM", "summary": "In this paper, the authors study the problem of PAC learning multi-index functions. They show if the multi-index function $f$ has \ndistinguishing moments of degree at most $m$, then there is an algorithm that uses at most $d^{O(m)}$ i.i.d. samples \nthat can learn this function (even in the presence of adversarial noises). As an application of this generic result, \nthey show that homogeneous Lipschitz ReLU networks can be learned using $O(d^2)$ samples. They also complement their upper \nbounds with a Statistical Query (SQ) lower bound which says that if degree $m$ distinguishing moments do not exist for \nsome subspaces, then any efficient algorithm will require a SQ oracle with tolerance smaller than $d^{-\\Omega(m)}$.", "questions": "* Can you obtain bounds on the Lipschitz constant of ReLU networks (probably under some other conditions)?  \n  I am asking this because Corollary 1.7 depends on the Lipschitz constant of the network, which is expected to become \n  worse as the network becomes deeper. \n* Do your results cover [DIKZ25] as special cases if we treat the discrete label space as a subset of the real line?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths \n\n* Overall, this is a well-written paper. The presentation is clear, and the proof sketches are easy-to-follow.\n* The authors provide an algorithm that learns general multi-index functions with polynomial samples (assuming $m = O(1)$) \n  under fairly general assumptions, and show the corresponding SQ lower bounds. These can potentially be used as baseline \n  results in later analysis of multi-index models with more structures. \n* The authors show that their complexity measure (the lowest degree of the distinguishing moments) is approximately \n  equivalent to the Generative Exponent in the single-index case. In some sense, this can be viewed as an evidence \n  that they are using the right/a reasonable measure. \n* The RNGCA framework introduced in the proof of the lower bounds explicitly encodes the label subspace, which not only \n  looks more natural for this type of learning tasks, but also makes the lower bounds applicable to the realizable/noiseless settings. \n\n### Weakness \n\n* The authors claim that Corollary 1.7 (Learning ReLU networks) is depth-independent. However, Corollary 1.7 requires the \n  target class to be $L$-Lipschitz and has a super-exponential dependence on $L$, and it is not clear how $L$ grows when \n  the network becomes deeper. \n* Some parts of this paper, such as Definition 1.3 and Algorithm 1 and 2, are extended/refined/continuous version of the \n  counterparts in [DIKZ25]. The authors should mention this more explicitly in the main text. \n\n\n### Typos\n* Line 45: should be $\\mathrm{err}_D(f)$.\n* Line 307: $\\| v_W \\|$. Do you mean something like $v_{W \\cap V^\\perp}$?\n\n[DIKZ25] Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Nikos Zarifis. Robust Learning of Multi-index Models via Iterative Subspace Approximation. 2025.", "was_revised": true, "final_justification": "The authors have resolved my concern (the improvement of Corollary 1.7 over the [CMK22]) during the rebuttal. I maintain my positive score (5).", "rebuttal": "We thank the reviewer for their time, effort, and insightful questions. We address the points and questions by the reviewer below.\n\n**Dependence on Network Size vs. Lipschitz Constant:** Regarding the dependence of Corollary 1.7 on the Lipschitz constant $L$, there are a few comments we would like to make. We first want to emphasize that the depth of the network and the Lipschitz constant are independent quantities. Specifically, it is possible to have a depth-one network with arbitrarily large Lipschitz constant; or a very deep network with arbitrarily small Lipschitz constant. \n\nWhile the dependence of our algorithm (establishing Corollary 1.7) on the parameter $L$ may not be optimal, some dependence on $L$ is information-theoretically necessary (since the target function can be supported on a set of probability mass $O(1/L)$). The main contribution of Corollary 1.7 over the prior work [CKM22] is that it completely removes the dependence on the network size (parameter $S$, see Line 97, which is bounded below by the depth and may be much larger) while having qualitatively similar dependence on the Lipschitz constant $L$. \n\n**Discrete Label Case:** While the main results of [DIKZ25] could be morally viewed as a special case of ours, certain non-trivial technical differences between the settings make it difficult to conclude this immediately. Specifically, our paper uses the $L_2$ loss, rather than the $L_0$ loss (misclassification error) in [DIKZ25]. Consequently, our setting allows agnostic noise that produces output values not in the given discrete set."}, {"review_id": "vpyQPPSbks", "reviewer": "Reviewer_qTJB", "summary": "The paper studies the problem of learning real-valued multi-index models (MIMs) under Gaussian covariates in the presence of adversarial label noise. The paper proposes an iterative, subspace recovery based algorithm that PAC learns well-behaved MIMs. As a corollary, the authors derive the complexity of learning low rank Relu networks, improving existing results.", "questions": "1. The moment condition in part (2) of Definition 1.3 feels quite abstract. Can the authors give a more intuitive explanation or interpretation of what this condition is actually capturing?\n\n2. Corollary 1.7 is said to improve over [CKM22] by removing the dependence on the network size $S$. But isn’t the Lipschitz constant $L$ effectively taking its place? If no prior bound on $L$ is assumed, and ReLU networks naturally have Lipschitz constants that scale with depth and width, doesn’t that reintroduce a kind of hidden dependence on $S$? Can the authors clarify whether $L$ can be controlled independently of $S$?\n\n3. Also, maybe I’m misunderstanding something, but the discussion around optimality of Theorem 1.4 focuses on the $d^m$ term, due to the SQ lower bound. But in practice, isn’t the $2^{\\mathrm{poly}(K/\\varepsilon\\sigma)}$ term a much bigger deal? For small enough $\\varepsilon$, this term should easily dominate $d^m$, no?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This is a technically solid paper. It provides a PAC learner with sample complexity $N$ that runs in $\\mathrm{poly}(N)$ time. A SQ lower bound is also given, which qualitatively matches some terms in $N$. So this is, to my knowledge, the first paper to give a partial characterization of efficient PAC learning for MIMs.\n\nMy main concern is that the paper doesnot do a great job of contextualizing the results. It says that “our understanding of the efficient learnability of MIMs is somewhat more limited,” but it is unclear what exactly this means. Are there known (possibly inefficient) PAC learners for MIMs? If so, how do the statistical and computational complexities of this paper’s algorithms compare to those?\n\n\n\nBased on Definition 1.3, it looks like the authors are working with a subclass of $C^1$. For that class, are there standard covering number-based bounds for agnostic PAC learning. How do those sample complexity bounds compare to the ones proved in this paper? A common issue with traditional sample complexity bounds is that they often rely on ERM over the class (or a discretization), which results in exponential computational complexity in $1/\\varepsilon$. But the algorithm from Theorem 1 already has exponential dependence on $1/\\varepsilon$, so it’s not clear whether this approach improves on ERM from a computational perspective. Can the authors comment on this?", "was_revised": true, "final_justification": "I am happy with the response provided by the authors regarding my original comments. However, my knowledge in the field of computational learning theory is minimal to non-existent. So, please take my assessment with a grain of salt.", "rebuttal": "We thank the reviewer for their time, effort, and insightful questions. We address the reviewer's points below.\n\nBy the term “efficient learnability of MIMs”, we refer to the computational complexity of learning. Ignoring computational constraints, essentially tight bounds on the sample complexity of PAC learning follow easily from known techniques. On the other hand, prior to our work, no algorithm with runtime subexponential in the dimension $d$ was known (even for constant values of the parameters $L, K, \\epsilon$.) We elaborate on these points in the following paragraphs.\n\n**Previously Known (Inefficient) PAC Learners for MIMs:** Via standard uniform convergence arguments, it can be shown that for well-behaved MIMs (in fact, for any bounded‐variation $C^1$ class on $\\mathbb{R}^d$) the Empirical Risk Minimizer (ERM) is an agnostic PAC learner with sample complexity linear in the dimension $d$ and polynomial in the parameters $L, K, 1/\\epsilon$.  Unfortunately, known implementations of the ERM require searching over an $\\epsilon$–cover of the $K$-MIM Lipschitz functions, which takes time $2^{\\Omega(d/\\epsilon)}$. This runtime is exponential in the dimension $d$, even for constant values of the accuracy parameter. In contrast, the complexity of our algorithm is a fixed-degree polynomial in $d$ (with exponent roughly $m$, the degree of distinguishing moments in Definition 1.3).\n\n**Complexity of ERM vs. Our Algorithm:** As explained above, while the sample complexity of ERM is near-optimal, its computational complexity is exponential in $d$ (even for constant $\\epsilon$). Our SQ lower bound strongly suggests an information-computation gap for our learning problem: while the information-theoretically optimal sample complexity is $O(d)$ (times some function of the other parameters), to achieve runtime sub-exponential in the dimension, we need to draw more samples—namely $d^{\\Omega(m)}$. Our algorithm qualitatively matches this lower bound (as a function of the dimension), by drawing $d^{O(m)}$ samples (times some function of the other parameters) and running in sample-polynomial time.\n\n**Intuition for the Moment Condition (Def 1.3):** Our submission includes an intuitive explanation regarding this part of Definition 1.3: please see lines 54-56, and 165-178. As mentioned in lines 54–56, the “distinguishing low‑degree moment” condition measures how much improvement one can guarantee when the current subspace guess is off. Concretely, if the guess subspace yields large residual error, then a degree at most $m$ moment will detect that misfit and guide the next update—quantifying exactly how much progress one can make per iteration. If the reviewer has additional suggestions, we are happy to expand on this explanation in the revised version.\n\n**Dependence on Network Size vs. Lipschitz Constant:** \nRegarding the dependence of Corollary 1.7 on the Lipschitz constant $L$, there are a few comments we would like to make. We first want to emphasize that the depth of the network and the Lipschitz constant are independent quantities. Specifically, it is possible to have a depth-one network with arbitrarily large Lipschitz constant; or a very deep network with arbitrarily small Lipschitz constant. While the dependence of our algorithm (establishing Corollary 1.7) on the parameter $L$ may not be optimal, some dependence on $L$ is information-theoretically necessary (since the target function can be supported on a set of probability mass $O(1/L)$). The main contribution of Corollary 1.7 over the prior work [CKM22] is that it completely removes the dependence on the network size (parameter $S$, see Line 97, which is bounded below by the depth and may be much larger) while having qualitatively similar dependence on the Lipschitz constant $L$. \n\n**Relative Impact of the $2^{\\mathrm{poly}(1/\\epsilon)}$ vs. $d^m$ Terms:**\nThe focus and main contribution of our paper is to qualitatively characterize the complexity of PAC learning MIMs as a function of the dimension $d$. Specifically, our work establishes that the $d^m$ term in the complexity of our algorithm is qualitatively optimal in the SQ model (see lines 80-81). We did not make any claims about the optimality of our methods in terms of the other parameters. \n\nNotably, prior to our work, no algorithm with sub-exponential dependence on $d$ was known in our setting, even for constant values of the parameters $\\epsilon, L, K$.  As the first algorithmic result in this setting, our primary goal was to establish the correct dimension‐dependence. \n\nAs pointed out by the reviewer, for $\\epsilon$ very small, the $2^{\\mathrm{poly}(1/\\epsilon)}$ term may dominate the $d^m$ term. (It is worth pointing out here that, as mentioned in lines 75-76, the version of our algorithm for the case of independent noise has a $\\mathrm{poly}(1/\\epsilon)^K$ complexity.) Developing algorithms with polynomial dependence in all parameters is left as an interesting open problem."}, {"review_id": "xDAKllNbgf", "reviewer": "Reviewer_AGEu", "summary": "The paper studies learning real-valued Multi-Index Models (MIMs) under Gaussian inputs, where the target depends on an unknown $K$-dimensional subspace. It gives a robust PAC regression algorithm (agnostic setting) that tolerates arbitrary label noise. Under mild regularity (“bounded variation” and “distinguishing low-degree moments”) it runs in time polynomial in $d$ (ambient dimension). A matching SQ lower bound showing any Statistical Query learner must incur roughly $d^{\\Omega(m)}$ complexity when the low-degree moment condition fails. There is also a concrete application to positive-homogeneous Lipschitz MIMs (including certain ReLU networks).", "questions": "See above.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is clearly written, and the mathematical arguments are rigorous and not hard to follow. The results are strong, providing decent results on learning MIM, and I recommend a clear acceptance provided the following concern is addressed.\nI would point out one more related work (arXiv:2506.05500) that introduces a “generative leap” measure for multi-index models. It would greatly clarify the paper if the authors clarified how their parameter \\$m\\$ corresponds to this generative leap (which controls the overall learning complexity). \nI would be happy to raise my score further once that connection is made explicit.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, effort, and positive evaluation of our work. We address the reviewer's question below.\n\nThe arxiv paper by [Damian et al., 2025] pointed out by the reviewer  (arXiv:2506.05500) appeared online on June 5, three weeks after the NeurIPS submission deadline. As a result, we were unable to include a comparison in our submission. \n\nWe provide a brief comparison below, and we would be happy to incorporate it in the revised version of our paper.  \n\nAt a high-level, while our work and [Damian et al., 2025] study qualitatively similar tasks (“learning multi-index models”), the two works address fundamentally different objectives:\n\n* **PAC Learning vs. Parameter Recovery:** Our submission focuses on the PAC learning task, i.e., the task of obtaining a hypothesis with low prediction error (without requiring to identify the underlying subspace). In contrast, [Damian et al., 2025] focuses on parameter recovery, aiming to precisely estimate the underlying subspace. Note that PAC learning may be feasible in settings where parameter recovery is information-theoretically impossible. Specifically, it is possible to design very simple functions that admit accurate predictors even when the subspace is not identifiable. We mentioned this distinction in our submission, when we compared against the prior work [DBLP24] (which focused on single-index models); see lines 1406-1413.\n\n* **Agnostic Noise:** Our submission provides conditions and provable guarantees for both the realizable/independent label noise and the agnostic settings. In contrast, the complexity measure introduced in [Damian et al., 2025] assumes a realizable, noiseless model.\n\nDespite the above differences, when both works are restricted to a realizable setting and when parameter-recovery is possible, one can show that our Definition 1.3 and the “generative-leap exponent” of [Damian et al., 2025] are essentially equivalent. This can be shown by roughly the same analysis as presented in Appendix C.3 of our submission for the generative exponent (the single-index special case)."}]

Author rebuttal:

Meta-review: This paper studies the problem of learning real-valued multi-index models where the input distribution is standard Gaussian and the output depends only on a low-dimensional subspace of the input.
The main contributions of the paper are two-fold: first, under some technical conditions on the target function, the authors provide an agnostic PAC learning algorithm that works for a broad class of multi-index models, in the potential presence of adversarial noise; second, they establish a lower bound for the sample complexity using the statistical query framework.
The upper and lower bounds nearly match in terms of the dependence on the dimension of the input space.

Overall the paper is well-written and presents its ideas and results clearly.
The technical results are significant and contribute to our understanding of the fundamental learning problem for multi-index models.
While some of the techniques are based on [DIKZ25], the paper extends these ideas in non-trivial ways.
This adds to the recent literature on characterizing the computational complexity for learning single- and multi-index models.

Finally, the paper has received unanimous support from all reviewers.
The authors are encouraged to address the minor comments and suggestions and incorporate the feedback provided by the reviewers to further improve the paper.
Decision: Accept (spotlight)