Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
Authors: Gautam Chandrasekaran
Adam Klivans
Lin Lin Lee
Konstantinos Stavropoulos
Venue: ICLR 2025 Poster (2025)
Keywords: pac learning
distribution shift
distribution testing
testable learning
neural networks
kernel methods
Primary area: learning theory

Abstract: We give the first provably efficient algorithms for learning neural networks with respect to distribution shift. We work in the Testable Learning with Distribution Shift  framework (TDS learning) of Klivans et al. (2024), where the learner receives labeled examples from a training distribution and unlabeled examples from a test distribution and must either output a hypothesis with low test error or reject if distribution shift is detected.  No assumptions are made on the test distribution. 

All prior work in TDS learning focuses on classification, while here we must handle the setting of nonconvex regression. Our results apply to real-valued networks with arbitrary Lipschitz activations and work whenever the training distribution has strictly sub-exponential tails. For training distributions that are bounded and hypercontractive, we give a fully polynomial-time algorithm for TDS learning one hidden-layer networks with sigmoid activations. We achieve this by importing classical kernel methods into the TDS framework using data-dependent feature maps and a type of kernel matrix that couples samples from both train and test distributions.

Published as a conference paper at ICLR 2025
LEARNING NEURAL NETWORKS WITH DISTRIBUTION SHIFT: EFFICIENTLY CERTIFIABLE GUARANTEES
Gautam Chandrasekaran, Adam R. Klivans, Lin Lin Lee, Konstantinos Stavropoulos
The University of Texas at Austin
{gaut klivans, kstavrop]@cs utexas.
1 1 ee deeeexxxeseccoo edu
ABSTRACT
We give the first provably efficient algorithms for learning neural networks with respect to distribution shift. We work in the Testable Learning with Distribution Shift framework (TDS learning) of Klivans et al. (2024a), where the learner re- ceives labeled examples from training distribution and unlabeled examples from a test distribution and must either output a hypothesis with low test error or reject if distribution shift is detected. No assumptions are made on the test distribution.
All prior work in TDS learning focuses on classification, while here we must han- dle the setting of nonconvex regression. Our results apply to real-valued networks with arbitrary Lipschitz activations and work whenever the training distribution has strictly sub-exponential tails. For training distributions that are bounded and hypercontractive, we give fully polynomial-time algorithm for TDS learning one hidden-layer networks with sigmoid activations. We achieve this by importing classical kernel methods into the TDS framework using data-dependent feature maps and a type of kernel matrix that couples samples from both train and test distributions.
INTRODUCTION
Understanding when model will generalize from known training distribution to an unknown test distribution a critical challenge trustworthy machine learning and domain adaptation. Tradi- tional approaches to this problem prove generalization bounds in terms of various notions of distance between train and test distributions (Ben-David et al., 2006; 2010; Mansour et al., 2009) but do not provide efficient algorithms. Recent work due to Klivans et al. (2024a) departs from this paradigm and defines the model of Testable Learning with Distribution Shift (TDS learning), where a learner may reject altogether if significant distribution shift is detected. When the learner accepts, however, it outputs a classifier and a proof that the classifier has nearly optimal test error.
A sequence of works has given the first of efficient algorithms in the TDS learning model for well-studied function classes where no assumptions are taken on the test distribution (Klivans et al., 2024a;b; Chandrasekaran et al., 2024: Goel et al., 2024). These results, however, hold for classifica- tion and therefore do not apply to (nonconvex) regression problems and in particular to a long line of work giving provably efficient algorithms for learning simple classes of neural networks under nat- ural distributional assumptions on the training marginal (Goel & Klivans, 2019; Diakonikolas et al., 2020a;e; 2022; Chen et al., 2022b: 2023; Wang et al., 2023; Gollakota et al.. 2024a; Diakonikolas & Kane, 2024).
The main contribution of this work is the first set of efficient TDS learning algorithms for broad classes of (nonconvex) regression problems. Our results apply to neural networks with arbitrary Lipschitz activations of any constant depth. As one example, we obtain a fully polynomial- algorithm for learning one hidden-layer neural networks with sigmoid activations with respect to any bounded and hypercontractive training distribution. For bounded training distributions, the running times of our algorithms match the best known running times for ordinary PAC or agnostic learning (without distribution shift). We emphasize that unlike all prior work domain adaptation, we make assumptions the test distribution.

---

Published as a conference paper at ICLR 2025
Regression Setting. We assume access to labeled examples from the training distribution and unlabeled examples from the marginal of the test distribution. We consider the squared loss CD(h) (=( [y h(z)))]. The error benchmark is analogous to the benchmark for TDS learning in classification (Klivans et al., 2024a) and depends on two quantities: the opti- mum training error achievable by classifier in the learnt class, opt min (f))), and the best joint error achievable by single classifier on both the training and test distributions, = f
+ LD (..)]. Achieving an error of opt + A is the standard goal in domain adaptation (Ben-David et al., 2006; Blitzer et al., 2007; Mansour et al., 2009). We now formally define the TDS learning framework for regression:
Definition 1.1 (Testable Regression with Distribution Shift). For c, 8 1) and function class F C { + JJ. J. the learner receives iid labeled examples from some unknown training distribution D over Rd x I and iid unlabeled examples from the marginal D/ of another unknown test distribu- tion D' over F. x R. The learner either rejects, or it accepts and outputs hypothesis h R - R such that the following are true.
1. (Soundness) With probability at least 1 - 8, if the algorithm accepts, then the output h satisfies CD I minfer(LD(()) + minger(Coo((") + (xx( 6.
2. (Completeness) If Dr = -'z, then the algorithm accepts with probability at least 1 - 6.
1.1 TECHNICAL STATEMENT OF RESULTS
Our results hold for classes of Lipschitz neural networks. In particular, we consider functions f of the following form. Let a + R be an activation function. Let W = (W()).. ... W(9) with W(O) E R x be the tuple of weight matrices. Here, So = d is the input dimension and st = 1. Define recursively the function /; Rd + R as fi(ar) = W o (f(-n(a))) with fi()) = W xc
The function f IRd - R computed by the neural network (W, o) is defined as f(x) = fx(x)) The depth of this network t.
We now present our main results on TDS learning for neural networks.
Function Class
Runtime (Bounded)
Runtime (Subgaussian)
One hidden-layer Sigmoid Net
M,,,/,
(ooly(koggMM/2 (e))
Single ReLU
M) -220//4)) 20(16)
Sigmoid Nets
poly(d, 20((10((11))))) 1)
dpoly (ooby(teoo((MX((gg((/)))))
1-Lipschitz Nets
poly(d, M) 20
log(M))(c)
Table 1: In the above table, k denotes the number of neurons in the first hidden layer. M denotes bound on the labels of the train and test distributions. One hidden-layer Sigmoid nets refers to depth 2 neural networks with sigmoid activation. The bounded distributions considered in the above table have support on the unit ball. We assume that all relevant parameters of the neural network are bounded by constants. For more detailed statements and proofs, see Definition A.12 and (1) Corollaries B.4 and B.6 and Theorems B.3 and B.5 for the bounded case, and (2) Theorems C.9 and C. for the Subgaussian case.
From the above table, we highlight that in the cases of bounded distributions with (1) one hidden- layer Sigmoid Nets, and (2) Single ReLU with < 1/ log d, obtain TDS algorithms that run in polynomial time all parameters. Moreover, for the last row, regarding Lipschitz Nets, each neuron is allowed have different and unknown Lipschitz activation. Therefore, in particular, our results capture the class of single-index models (see, e.g., Kakade et al. (201 1); Gollakota et al. (2024a)).
In the results of Table assumption can be relaxed to a bound on any moment whose degree is strictly higher than (see Corollary D.2). In fact, such assumption is necessary, show in Proposition D.
assume bounded labels for both the training and test distributions. This
2

---

Published as a conference paper at ICLR 2025
1.2 OUR TECHNIQUES
TDS Learning via Kernel Methods. The major technical contribution of this work is devoted to importing classical kernel methods into the TDS learning framework. first attempt at testing dis- tribution shift with respect to fixed feature map would be to form two corresponding covariance matrices of the expanded features, one from samples drawn from the training distribution and the other from samples drawn from the test distribution, and test if these two matrices have similar eigen- decompositions. This approach only yields efficient algorithms for linear kernels, however, as here are interested in spectral properties of covariance matrices in the feature space corresponding to low-degree polynomials, whose dimension is too large.
Instead we form new data-dependent and concise reference feature map Φ. that depends amples from both Dr and D' We show that this feature map approximately represents the ground truth, i.e., some function with both low training and test error (this is due to the representer theo- rem, see Proposition 3.7). To certify that eπror bounds transfer from Di to D'z we require relative error closeness between covariance matrix Ø' L (()x)
of the feature expansion over the test marginal with the corresponding matrix + = EE (<(() ))x))))))))))))))()))))) over the training marginal. We draw fresh sets of verification examples and show how the kernel trick can be used to efficiently achieve these approximations even though ó is a nonstandard feature map. For more technical details, see Section 3.1.
By instantiating the above results using a type of polynomial kernel, we can reduce the problem of TDS learning neural networks to the problem of obtaining appropriate polynomial approxi- mator. Our final training algorithm (as opposed to the testing phase) will essentially be kernelized polynomial regression.
TDS Learning and Uniform Approximation. Prior work in TDS learning has established con- nections between polynomial approximation theory and efficient algorithms in the TDS setting. In particular, the existence of low-degree sandwiching approximators for a concept class is known to imply dimension-efficient TDS learning algorithms for binary classification. The notion of sand- wiching approximators for function f refers to a pair of low-degree polynomials Pup. Pdown with two main properties: (1) Pdown S f S Pup everywhere and (2) the expected absolute distance between Pup and Pdown over some reference distribution is small. The first property is of partic- ular importance in the TDS setting, since holds everywhere and, therefore, it holds for any test distribution unconditionally.
Here we make the simple observation that the incomparable notion of uniform approximation suf- fices for TDS learning. A uniform approximator is polynomial p that approximates a function f pointwise, meaning that Ip fl is small in every point within a ball around the origin (there is no known direct relationship between sandwiching and uniform approximators). In our setting, uniform approximation is more convenient, due to the existence of powerful tools from polynomial approximation theory regarding Lipschitz and analytic functions.
Contrary to the sandwiching property, the uniform approximation property cannot hold everywhere if the approximated function class contains high-(or infinite- )degree functions. When the training distribution has strictly sub-exponential tails, however, the expected error of approximation outside the radius of approximation negligible. Importantly, this property can be certified for the test distribution by using noment-matchinn tester. See also Section 4.
1.3 RELATED WORK
Learning with Distribution Shift. The field of domain adaptation has been studying the distribution
shift problem for almost two decades (Ben-Daviz et al., 2006; Blitzer et al., 2007; Ben-Davin et al., 2010; Mansour et al., 2009; David et al., 2010; Mousavi Kalan et al., 2020; Redko et al., 2020; Kalavasis et al., 2024; Hanneke & Kpotufe, 2019; 2024; Awasthi et al., 2024), providing useful insights regarding the information-theored first efficient end-to-end algorithms for non-trivial concept classes with distribution shift were given for TDS learning in Klivans et al. (2024a;b); Chandrasekaran et al. (2024) and for PQ learning, originally defined by Goldwasser et al. (2020), in Goel et al. (2024). These works focus binary classification for classes like halfspaces, halfspace intersections, and geometric concepts. In the regression setting, need to handle unbounded loss functions, but we also able use I. Lipschitz
(im)possibilities for learning with distribution shift. The
3

---

Published as a conference paper at ICLR 2025
properties of real-valued networks to obtain results for deeper architectures. For the special case of linear regression, efficient algorithms for learning with distribution shift are known to exist (see, c.g., Lei et al. (2021)), but our results capture much broader classes.
Another distinction between the existing works in TDS learning and our work, is that our results require significantly milder assumptions the training distribution. In particular, while all prior works on TDS learning require both concentration and anti-concentration for the training marginal (Klivans al., 2024a;b; Chandrasekaran et al., 2024), we only assume strictly subexponential con- centration in every direction. This is possible because the function classes we consider are Lipschitz, which is not the case for binary classification.
Testable Learning. More broadly, TDS learning is related to the notion of testable learning (Ru- binfeld & Vasilyan, 2023; Gollakota et al., 2023; 2024c; Diakonikolas et al., 2023; Gollakota al., 2024b; Diakonikolas et al., 2024; Slot et al., 2024), originally defined by Rubinfeld & Vasilyan (2023) for standard agnostic learning, aiming to certify optimal performance for learning algorithms without relying directly on any distributional assumptions. The main difference between testable agnostic learning and TDS learning is that in TDS learning, we allow for distribution shift, while in testable agnostic learning the training and test distributions are the same. Because of this, TDS learning remains challenging even in the absence of label noise, in which case testable learning becomes trivial (Klivans et al., 2024a).
Efficient Learning of Neural Networks. Many works have focused on providing upper and lower bounds the computational complexity of learning neural networks in the standard (distribution- shift-free) setting (Goel et al., 2017; Goel & Klivans, 2019; Goel et al., 2020a;b; Diakonikolas et al., 2020a;b;e; 2022: Chen al., 2022a:b; 2023; Wang et al., 2023; Gollakota al., 2024a; Diakonikolas & Kane, 2024; Li et al., 2020; Gao et al., 2019; Zhang et al., 2019; Vempala & Wilmes, 2019; Allen-
Reichman, 2018; Ge et al., 2019; 2018: Du et al., 2018; Goel et al., 2018; Tian, 2017: Li & Yuan, 2017: Brutzkus & Globerson, 2017; Zhong et al., 2017: Zhang al., 2016b; Janzamin et al., 2015). The majority of the upper bounds either require noiseless labels and shallow architectures or work only under Gaussian training marginals. Our results not only hold in the presence of distribution shift, but also capture deeper architectures, under any strictly subexponential training marginal and allow adversarial label noise.
Zhu et al., 2019; Bakshi et al., 2019 Manurangsi
The upper bounds that are closest to our work are those given by Goel et al. (2017). They consider ReLU as well as sigmoid networks, allow for adversarial label noise and assume that the training marginal is bounded but otherwise arbitrary. Our results in Section extend all of the results in Goel et al. (2017) to the TDS setting, by assuming additionally that the training distribution is hypercontractive (see Definition 3.9). This additional assumption is important to ensure that our tests will pass when there is no distribution shift. For more thorough technical comparison with Goel et al. (2017), see Section 3.
In Section 4, we provide upper bounds for TDS learning of Lipschitz networks even when the training marginal is an arbitrary strictly subexponential distribution. In particular, our results imply new bounds for standard agnostic learning of single ReLU neurons, where achieve runtime dpoly(1/e) The only known upper bounds work under the Gaussian marginal (Diakonikolas al., 2020a), achieving similar runtime. In fact, in the statistical query framework (Kearns, 1998), known that (oly(1/e) runtime is necessary for agnostically learning the ReLU, even under the Gaussian distribution (Diakonikolas et al., 2020b; Goel et al., 2020b).
PRELIMINARIES
We use standard vector and matrix notation. We denote with RR. N the sets of real and natural numbers accordingly. We denote with D labeled distributions over RRd x R and with Dr the marginal of D on the features in dgd For set S of points in Rd, we define the empirical probabilities (resp. expectations) as Pra~s(((x)) = S Eees 1 [(E(x)) (resp. [xws] = [ Eaes f(x)). We
denote with S the labeled version of S and we define the clipping function cl IR. + [-M, M,, that maps number t E R either to itself if t E [-M, M), or to M sign(t) otherwise.
Loss function. Throughout this work, we denote with (b))) the squared loss of hypothesis h Rd - R with respect to labeled distribution D, i.e., Lo (h) V (v h(x:))?] More-
4

---

Published as a conference paper at ICLR 2025
over, for any function f IR + R. we denote with Il the quantity llfll v EEwDE (f(x)) For a set of labeled examples S, we denote with (h)h)) the empirical loss on S, i.e., (h) =
V [s] (v - h²=))²² and similarly for Il
Distributional Assumptions. In order to obtain efficient algorithms, we will either assume that the training marginal Da is bounded and hypercontractive (Section 3) or that it has strictly subexponen- tial tails in every direction (Section 4). We make no assumptions on the test marginal D'
Regarding the labels, we assume some mild bound on the moments of the training and the test labels, e.g., (a) that Ey-D, [v"), BynDy [v*] Σ M or (b) that E [-M, a.s. for both D and D'. Although, ideally, we want to avoid any assumptions on the test distribution, as we show in Proposition D.I, a bound on some constant-degree moment of the test labels necessary.
3 BOUNDED TRAINING MARGINALS
We begin with the scenario where the training distribution is known to be bounded. In this case, it is known that mae-hideen-laye sigmoid networks can be agnostically learned (in the classical sense, without distribution shift) in fully polynomial time and single ReLU neurons can be learned up to error ( Togíd)/ polynomial time (Goel et al., 2017). These results are based on a kernel-based approach, combined with results from polynomial approximation theory. While polynomial approx- imations reduce the nonconvex agnostic learning problem to convex through polynomial feature expansions, the kernel trick enables further pruning of the search space, which is important for obtaining polynomial-time algorithms. Our work demonstrates another useful implication of the kernel trick: it leads to efficient algorithms for testing distribution shift.
We will require the following standard notions:
Definition 3.1 (Kernels (Mercer, 1909)). A function K. Rd x Rd - R is a kernel. If for any set of m points 2 y.... F. in IR the matrix (KC(.,, 2t,)) (()))m)) is positive semidefinite, we say that the kernel positive definite. The kernel IC is symmetric if for all æ x' E Rdd K(xx, x²) = K((w', xt).
Any PSD kernel is associated with some Hilbert space H and some feature map from IRd to H.
Fact 3.2 (Reproducing Kernel Hilbert Space). For any positive definite and symmetric (PDS) kernel K., there is a Hilbert space H, equipped with the inner product (,,-) HH x H + R. and a function tb Rd + H such that K(x, x²) = (((x), (b(a)) for all x, x' Rd. We call H the reproducing kernel Hilbert space (RKHS) for K. and up the feature map for K.
There are three main properties of the kernel method. First, although the associated feature map s may correspond to vector in
dinnit--dmeesionall space, the kernel C(æx,x') may still be efficiently evaluated, due to its analytic expression in terms of x, x'. Second, the function class E HI, (v < B} has Rademacher complexity independent from the
Fx (x + (v, (xx) dimension of H. as long as the maximum value of K(x,, x)) for æ in the domain is bounded (Thm. 6.12 in Mohri et al. (2018)). Third, the time complexity of finding the function in Fx that best fits dataset is actually polynomial to the size of the dataset, due to the representer theorem (Thm. 6.11 in Mohri et al. (2018)). Taken together, these properties constitute the basis of the kernel method, implying learners with runtime independent from the effective dimension of the learning problem.
In order to apply the kernel method to learn some function class F, it suffices to show that the class F. can be represented sufficiently well by the class Fx. We give the following definition.
Definition 3.3 (Approximate Representation). Let F be function class over IRd, KC: IRd x Rdd + R a PDS kernel, where H. is the corresponding RKHS and vp the feature map for K. We say that F can be -pppooiiioo represented within radius with respect I. if for any f E F, there is E H with (v, v) < B such that [(x) (v, (x))) < for all x E Idd, ||>||| S R.
For the purposes of TDS learning, we will also require the training marginal to have be hypercon- tractive with respect to the kernel at hand. This is important to ensure that our test will accept whenever there is no distribution shift. More formally, we require the following.
5

---

Published as a conference paper at ICLR 2025
Definition 3,4 (Hypercontractivitty) Let Da be some distribution over R let HH be Hilbert space and let vb R + H. We say that Da is (v, C, hyypeerccontrtetvve for any E and v E Hi:
Ex ((v, (xx)) - (Ct)a (LEeDD [0, 2))
If IC is the PDS kermel corresponding to s), we also say that Da is (K. C, E) -yperrcootrrteeeeee
3.1 TDS REGRESSION VIA THE KERNEL METHOD
We give general theorem TDS regression for bounded distributions, under the following assumptions. Note that, although we assume that the training and test labels are bounded, this assumption can be relaxed in black-box manner and bounding some constant-degree moment of the distribution of the labels suffices, as we show in Corollary D.2.
Assumption 3.5. For a function class C {TR > [R], and training and test distributions 'D DD' over Rd x R. assume the following.
1. F (e, appppoxximaa represented within radius R w.r.t. a PDS kernel K: Rd x Rd IR, for some E (0, 1) and B, R 2 and let A = sup allaS K)x
2. The training marginal Da (1) is bounded within {z || I R} and (2) is (K, C,
hypercontractive for some C, E 1.
3. The training and test labels are both bounded in [- M) for some M 2 1.
Consider the function class F. the kernel K and the parameters e, A, B, M, as defined in the assumption above and let (0, 1). Then, we obtain the following theorem.
Theorem 3.6 (TDS Learning via the Kernel Method). Under Assumption 3.5, Algorithm learns the class F in the TDS regression setting up to excess error and probability of failure 8. The time complexity is OTT) poly(d, 1, (log(1/8)){ B, C 2,, M), where I is the evaluation time of K.
The main ideas of the proof are the following.
Obtaining concise reference feature map. The algorithm first draws reference sets Ster, Stet from both the training and the test distributions. The representer theorem, combined with the ap- proximate representation assumption (Definition 3.3) ensure that the reference examples define new feature map Φ Rd + R2mm with x(x) = (K(x, =) =))= such that the ground truth + LD'(f) can be approximately represented as a linear combination of
f = arg the features in & with respect to both Stet and S i.e., I - (a*) TTll] ol and || - (a") Tolls both small for some a* E _m In particular, we have the following.
Proposition 3.7 (Representer Theorem, modification of Theorem 6.11 in Mohri et al. (2018)). Sup- pose that function f Rd - R can be (e, B)-BBpppp -approximately represented within radius R w.r.f. some PDS kernel IC (as per Definition 3.3). Then, for any set of examples S in {x E Tedd ||0:|| l2 S R}, there is = (aæ)æss E R|SI such that for p(x) = =ExES (=K(zz,) we have:
|l 1ff-ll: 5lls and Σ aaaeK(Zz ZE
Proof. We first observe that there is some v E such that (b. v) S B and for p(z) = (v. (xx)) we have [l. f -pls S e, because by Definition 3.3, there is pointwise approximator for f with respect to K. By Theorem 6.11 in Mohri et al. (2018), this implies the existence of p as desired.
Note that since the evaluation of ((r) only involves Kernel evaluations, we never need to compute the initial feature expansion (xx) which could be overly expensive.
Forming a candidate output hypothesis. We know that the reference feature map approximately represents the ground truth. However, having access to test labels, we cannot directly hope to find the corresponding coefficient a" E 2m Instead, we use only the training reference examples to find a candidate hypothesis with close-to-optimat performance can be also expressed in terms of the reference feature map d, as X = à TTo. Φ. then suffices to test the quality of the test distribution.
the training distribution which

---

Published as a conference paper at ICLR 2025
Algorithm 1: TDS Regression via the Kernel Method
Input: Parameters M, R, B, A, C, 2 1, e, E (0, 1) and sample access to D, D' Set m0 cLABM log( (), N cm2 ABC (4C' ))) 4 large enough constant
Draw m i..dd labeled examples Sret from D and m i.i.d. unlabeled examples Siet from D it for some a St we have || ||2 > R then L Reject and terminate;
Let (0z)=ES,n be the optimal solution to the following convex program
min aER
Σ
Σ
azK(z,z))
(s,e)
ZES
s.t.
Σ
agawN(2 () S B, where a (ax)
2,WESref
Draw N i..dd unlabeled examples Sver from Dr and N unlabeled examples S from D'd if for some x Sver we have || >> then Reject and terminate;
Compute the matrix $ = w. with 22,0 t Emesu K)x;, w);
Compute the matrix &' w. with 22. N Enes, K(x, 2 K(x, w): Let be the value of the following eigenvalue problem
max a T s.t. a ta 1
a
if pf 504B then Reject and terminate;
2
Otherwise, accept and output h : h(x) clas (f(x)) where f(x) Exes,.. d=N(z,
Testing the quality of reference feature map on the test distribution. We know that the function p" = =(a") performs well on the test distribution (since it is close to f on a reference test set). We also know that the candidate output à Φ performs well on the training distribution. Therefore, order to ensure that ý performs well on the test distribution, suffices to show that the distance between P and ý" under the test distribution, i.e., l|á Φ (a*) ØIl is small. In fact, it suffices to bound this distance by the corresponding one under the training distribution, because P fits the training data well and l|á run a test on & that certifies the desired bound for any possible a².
(a*) øIIp_ is indeed small. Since we do not know a", we need to
Using the spectral tester. We observe that ||a ④ - (a*) BlB (a a²) a²). where [E [0(=)((x)) and similarly l|á Φ (a*) 01B: (a aa)
T a') Since we want to obtain a bound for all a", we essentially want to ensure that for any E R2m we have ''a < (1 + p)a da for some small p. Having multiplicative bound is important because we do not have any bound on the norm of la a." 2|2-
To implement the test, and since we cannot test and क' directly, we draw fresh verification ex- amples Sver, S' from Da and DD' and run spectral test on the corresponding empirical versions é Φ of the matrices Φb d'. To ensure that the test will accept when there is distribution shift, use the following lemma (originally from Goel et al. (2024)) on multiplicative spectral concentration for é, where the hypercontractivity assumption (Definition 3.4) is important.
Lemma 3.8 (Multiplicative Spectral Concentration, Lemma B.1 in Goel et al. (2024), modified). Let D', be a distribution over Rd and à RRd - Rm such that Da, is (d), C, typerrcccotrrreeeeee for some C. > 1. Suppose that S consists of N i.i.d. examples from Da and let & Ex~D_ [0(x)((x)) and & = + Emes ((x))(x)) For any e, 6 E (0,1), if probability at least 8, we have thut
64Cm² (4C logz( ( 16+1, then with
For any TRM a a [(1 -)a ta, (1 + c)a TTa)
7

---

Published as a conference paper at ICLR 2025
Note that the multiplicative spectral concentration lemma requires access to independent samples. However, the reference feature map @ depends on the reference examples Sret, Stet This is the reason why we do not reuse Sret, Set+ but rather draw fresh verification examples.
For the full formal proof of Theorem 3.6 as well as a proof of Lemma 3.8, see Appendix B. The full proof involves appropriate uniform convergence bounds for kernel hypotheses, which are important in order to shift from the reference to the verification examples and back.
3.2 APPLICATIONS
Having obtained general theorem for TDS learning under Assumption 3.5, will now instantiate it to obtain TDS learning algorithms for learning neural networks with Lipschitz activations. In particular, we recover all of the bounds of Goel al. (2017), using the additional assumption that the training distribution is hypercontractive in the following standard sense.
Definition 3.9 (Hypercontractivitt)). We say that D is C-hypercontractive if for all polynomials of degree and & N, we have that
EwED [p(x)²*| < (Ct)2 (EanD [p(x))
Note that many common distributions like log-concave or the uniform over the hypereube are known to be hypercontractive for some constant C' (see Carbery & Wright (2001) and O' D'Dnneell (2014)). We provide the following lemma, whose proof can be found in the appendix (see Theorems A.19 and A.21 and Lemma A.1
Lemma 3.10. The following bounds on the parameters Assumption 3.5 hold for specific instanti- ations of the function classes.
Representation Bound (B)
Kernel Bound (AA)
Function Class
Degree (E)
Sigmoid Nets
(RW(=2((1lg)) )) log R)
2 ((((w)lo(()))++
(2
T--Lipshitz Nets
o ((WI)--R
(I: + E)0())
RO(E)
Table 2: We instantiate the parameters relevant to Assumption 3.5 for Sigmoid and Lipschitz Nets. We have: (1) / denotes bound the depth of the network, (2) W is bound the sum of network weights in all layers other than the first, (3) (e, B) and radius R are the approximate representation parameters, (4) is the number of hidden units the first first layer. The kernel function can be evaluated in time poly(d, f). For each of the classes, we assume that the maximum two norm of any row of the matrix corresponding to the weights of the first layer bounded by 1. The kernel we use is the composed multinomial kernel MK(() with appropriately chosen degree vector l. Here, é equals the product of the entries of Any C-hypercontractive distribution also (MK!)) C) hypercontractive for as specified in the table. For the case of l: = 1, the bound B in the second row can be improved to 20())
Combining Lemma 3.10 with Theorem 3.6, we obtain the results of the middle column of Table 1.
UNBOUNDED DISTRIBUTIONS
We showed that the kernel method provides runtime improvements for TDS learning, because it can be used to obtain a concise reference feature map, whose spectral properties on the test distribution are all we need to check to certify low test error. similar approach would not provide any run- time improvements for the case of unbounded distributions, because the dimension of the reference feature space would not be significantly smaller than the dimension of the multinomial feature ex- pansion. Therefore, can follow the standard mooment-matchinn testing approach commonly used in TDS learning (Klivans et al., 2024a) and testable agnostic learning (Rubinfeld & Vasilyan, 2023; Gollakota et al., 2023). We require the following assumptions.
8

---

Published as a conference paper at ICLR 2025
Assumption 4.1. For function class F S {R" + RJ, and training and test distributions D, D over R x R, we assume the following.
1. For any E F, there is W Bexd with |W]l2 1 and WWT I and a function all x E Rd. Moreover, -
R + IR such that f(x) =
-
2. For any f E F, with f(z) = g(Wa), there polynomial q over R of degree at most
E s.I. for any E Rd with ||a=||2 S R we have (q(W 9( x)1 S 6, where R 2 1, 10. We also require that < (RR), where ÖF, is hiding factors that are at most logarithmic in R, but can also depend on e.
3. The training marginal Da is 7-strictly subexponential for E (0, 1].
4. The training and test labels are both bounded in [-M, MM some M 2 1.
Consider the function class F, and the parameters e, 7, M, k. as defined in the assumption above and let 8 E (0, 1). Then, we obtain the following theorem.
Theorem 4.2 (TDS Learning via Uniform Approximation). Under Assumption 4.1, Algorithm learns the class F in the TDS regression setting up excess error 5e and probubillity of failure 6. The time complexity is poly dd, 1/e, log(1/6))) where s = (MllogMMee))0///
Note that Assumption 4.1 involves low-degree uniform approximation assumption, which only holds within some bounded-radius ball. Since we work under unbounded distributions, we also need handle the errors outside the ball. To this end, use the following lemma, which follows from results in Ben-David et al. (2018).
Lemma 4.3. Suppose f = fww and q satisfy parts and of Assumption 4.1. Then
[p(x)] s (k6)
for all [[aall 2 R.
The lemma above gives bound on the values of a low-degree uniform approximator outside the interval of approximation. Therefore, we can hope to control the error of approximation outside the interval by taking advantage of the tails of our target distribution as well as picking I suffi- ciently large. In order for the strictly subexponential tails to suffice, the quantitative dependence of on is important. This why we assume (see Assumption 4.1) that E = Ó(R). In particular, in order to bound the quantity Ee-D, (
2 [.)], we use Lemma 4.3 the Cauchy- Schwarz inequality and the bounds EgnD, [|| <|1 S (kE))()) and Præ~Da.ll) [[] l|2 R] < (RR/)) (+)). Substituting for é ÓR), we observe that the overall bound on the quan- tity Em-D,, [p" [1]1{[ 2 R3] decays with R. whenever 7 is strictly positive. Therefore, the overall bound can be made arbitrarily small with an appropriate choice of R (and therefore f). For more details on the proof, see Appendix C. Apart from the careful manipulations described above, the proof follows the lines of the corresponding results for TDS learning through sandwiching poly- nomials (Klivans al., 2024a).
In order to obtain end-to-end results for classes of neural networks (see the rightmost column of Table 1), we need prove the existence of uniform polynomial approximators whose degree scales almost linearly with respect to the radius of approximation for the reasons described above. For arbitrary Lipschitz nets (see Theorem A.19), we use general tool from polynomial approximation theory, the multivariate Jackson's 's theorem (Theorem A.9). This gives us a polynomial with degree scaling linearly in R and polynomially on and the number of hidden units (k) in the first layer.
For sigmoid nets, a more careful derivation yields improved bounds (see Theorem A.21) which have a poly-logarithmic dependence on J. Our construction involves composing approximators for the activations at each layer. Naively, the degree of this composition would be super linear in Rt. To get around this, we use the key property that the size of the output of a sigmoid network at any layer is memoryless (i.e., has R dependence). This follows from the fact that the sigmoid is bounded in [0, 1]. Using this, we obtain an approximator with almost- lineer dependence on R. For more details Appendix A.5.

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank the anonymous reviewers of ICLR 2025 for their feedback. Gautam Chandrasekaran was supported by the NSF AI Institute for Foundations of Machine Learning (IFML). Adam R. Klivans was supported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Lin Lin Lee was supported by the NSF AI Institute for Foundations of Machine Learning (IFML). Konstantinos Stavropoulos was supported by the NSF Al Institute for Foundations of Machine Learning (IFML) and by scholarships from Bodossaki Foundation and Leventis Foundation.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. Advances neural information processing systems, 32, 2019.
Pranjal Awasthi, Corinna Cortes, and Mehryar Mohri. Best-effort adaptation. Annals of Mathematics and Artificial Intelligence, 92(2):393-438, 2024.
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. Conference on Learning Theory, pp. 195-268. PMLR, 2019.
Shai Ben- David John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances neural information processing systems, 19, 2006.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine leurning, 79:151-175, 2010.
Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari. Classical lower bounds from quantum upper bounds. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 339-349. IEEE, 2018.
John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman. Learning bounds for domain adaptation. Advances in neural information processing systems, 20, 2007.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International conference on machine learning, pp. 605-614. PMLR, 2017.
Anthony Carbery and James Wright. Distributional and lq norm inequalities for polynomials over convex bodies in m. Mathematical research letters, 8(3):233-244 2001.
Gautam Chandrasekaran, Adam R Klivans, Vasilis Kontonis, Konstantinos Stavropoulos, and Ar- sen Vasilyan. Efficient discrepancy testing for learning with distribution shift. arXiv preprint arXiv:2406.09333, 2024.
Sitan Chen, Aravind Gollakota, Adam Klivans, and Raghu Meka. Hardness of noise-free learning for two-hiddeen-layr neural networks. Advances in Neural Information Processing Systems, 35: 10709-10724, 2022a.
Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed-parameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 696-707. IEEE, 2022b.
Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, and Raghu Meka. Learning narrow one- hidden-layer reiu networks. In The Thirty Sixth Annual Conference Learning Theory, pp. 5580-5614. PMLR, 2023.
Shai Ben David. Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 239-136.70 JMLR Workshop and Conference Proceedings, 2010.
10

---

Published as a conference paper at ICLR 2025
Ilias Diakonikolas and Daniel M Kane. Efficiently learning pee-hidden-layee relu networks via schurpolynomials. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1364- 1378. PMLR. 2024.
Ilaas Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Conference learning theory, pp. 1485.
PMLR, 2020a.
Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Process- ing Systems, 33:13586-11 -1111666611366,,, 2020b.
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one- cee-hhddd-llyeee relu networks. In Conference on Learning Theory, pp- 1514-1539. PMLR, 2020c.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning single neuron with adversarial label noise via gradient descent. In Conference on Learning Theory, pp. 4313- 4361. PMLR, 2022.
Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Efficient testable learning of halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 36, 2023.
Ilias Diakonikolas, Daniel Kane, Sihan Liu, and Nikos Zarifis. Testable learning of general halfs- paces with adversarial label noise. The Thirty Seventh Annual Conference on Learning Theory, PMLR, 2024.
pp.
Simon Du, Jason D Lee, and Yuandong Tian. When is a convolutional filter easy to learn? In 6th International Conference on Learning Representations, ICLR 2018, 2018.
Dietmar Ferger. Optimal constants in the marcinkiewiez-zyymmnd inequalities. Statistics & Probability Letters, 84:96-101, 2014. ISSN 0167-7152. doi: http:://do..og/10.101111 com/ htt///cinnc/rrricleeeeee
2013.09.029. URL https:// http:///wwwwccicceeecccccc 5016771521300327
Weihao Gao, Ashok V Makkuva, Sewoong Oh, and Pramod Viswanath. Learning one-hidden- layer neural networks under general input distributions. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1950-1959) PMLR, 2019.
Rong Ge, Jason Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In 6th International Conference on Learning Representations, ICLR 2018, 2018.
Rong Ge, Rohith Kuditipudi, Zhize Li. and Xiang Wang. Learning two-layer neural networks with symmetric inputs. In International Conference on Learning Representations, 2019.
Surbhi Goel and Adam R Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference on Learning Theory, pp. 1470-1499. PMLR, 2019.
Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in poly- nomial time. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1004-1042. PMLR, 07-10 Jul 2017.
Surbhi Goel, Adam Klivans, and Raghu Mcka. Learning one convolutional layer with overlapping patches. In International conference machine learning, pp. 1783-1791. PMLR, 2018.
Surbhi Goel, Aravind Gollakota. Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolyno- mial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pp. 3587-3596. PMLR, 2020a.
Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147-2158 2020b.

---

Published as a conference paper at ICLR 2025
Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, and Arsen Vasilyan. Tolerant algorithms for learning with arbitrary covariate shift. arXiv preprint arXiv:2406.02742, 2024.
Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. Advances in Neural Information Processing Systems, 33:15859-15870 2020.
Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari. A moment-matching approach to testable learning and characterization of rademacher complexity. Proceedings of the fifty- fifth annual ACM Symposium on Theory of Computing, 2023.
Aravind Gollakota, Parikshit Gopalan, Adam Klivans, and Konstantinos Stavropoulos. Agnostically learning single-index models using omnipredictors. Advances in Neural Information Processing Systems, 36, 2024a.
Aravind Gollakota, Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Tester-learners for halfspaces: Universal algorithms. Advances Neural Information Processing Systems, 36, 2024b.
Aravind Gollakota, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. An efficient tester-learner for halfsspaces. The Twelfth International Conference on Learning Representations, 2024c.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. Advances in Neural Information Processing Systems, 32, 2019.
Steve Hanneke and Samory Kpotufe. A more unified theory of transfer learning. arXiv preprint arXiv:2408. 16189, 2024.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guar- anteed training of neural networks using tensor methods. arXiv preprint vrXiv:/506.08.. 2015.
Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of generalized linear and single index models with isotonic regression. J. Shawe- Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24, Curran Associates, Inc., 2011.
Alkis Kalavasis, Ilias Zadik, and Manolis Zampetakis. Transfer learning beyond bounded density ratios. arXiv preprint arXiv:2403. 2024.
Michael Kearn.. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1066, 1998.
Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribu- tion shift. The Thirty Seventh Annual Conference on Learning Theory, 2024a.
Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of half- spaces with distribution shift: Improved algorithms and sq lower bounds. The Thirty Seventh Annual Conference on Leurning Theory, 2024b.
Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. In Interna- lional Conference on Machine Learning, pp. 6164-6174. PMLR, 2021.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. Advances in neural information processing systems, 30, 2017.
Yuanzhi Li, Tengyu Ma. and Hongyang R Zhang. Learning wer-parametrized two-layer neural networks beyond ntk. In Conference on learning theory. pp. 2613-2682, PMLR, 2020.
Roi Livni, Shai Shalev-Shware and Ohad Shamir. On the computational efficiency of training neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume I, NIPS' 14, pp. 855 Cambridge, MA, USA, 2014 4. MIT Press.
12

---

Published as a conference paper at ICLR 2025
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Proceedings of The 22nd Annual Conference on Learning The- ory (COLT 2009), Montréal, Canada, 2009. URL http:/ www. www.:nuu....uuuooooe..
post scri pt padap.pp.....a pdf.
Pasin Manurangsi and Daniel Reichman. The computational complexity of training relu (s). arXiv preprint arXiv:1810.0423 2018.
James Mercer. Functions of positive and negative type, and their connection with the theory of
integral equations. Philosophical Transactions of the Royal Society A, 209:415-446, 1909. URL
https: /app...... semant i cescholla ar. org/ Ctwp//rrruuaaa/eee ID 121070291.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, second edition, 2018.
Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Min- imax lower bounds for transfer learning with linear and one-hidden layer neural networks. Ad- vances Neural Information Processing Systems, 33:1959- 1969, 2020.
D. J. Newman and H. S. Shapiro. Jackson's Theorem in Higher Dimensions, pp. 208-219. Springer Basel, Basel, 1964.
Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
levgen Redko, Emilie Morvant, Amaury Habrard, Mare Sebban, and Younès Bennani. A sur- vey on domain adaptation theory: learning bounds and theoretical guarantees. arXiv preprint arXiv:2004. / 18299, 2020.
Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning algorithms.
Proceedings of the fifty-fitth annual ACM Symposium on Theory of Computing. 2023.
Lucas Slot, Stefan Tiegel, and Manuel Wiedmer. Testably learning polynomial threshold functions.
arXiv preprint
2024.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In International conference on machine learning. pp. 3404 3413. PMLR, 2017.
Santosh Vempala and John Wilmes. Gradient descent for mne-hidden-laee layer neural networks: Poly- nomial convergence and sq lower bounds. In Conference on Learning Theory, pp. 3115-3117. PMLR, 2019.
Roman Vershynin. Hligh-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Pugian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning sin- gle neuron via sharpness. In International Conference on Machine Learning, pp. 36541-36577. PMLR, 2023.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer relu networks via gradient descent. In The 22nd international conference on artificial intelligence and statistics, pp. 1524-1534. PMLR, 2019.
Yuchen Zhang, Jason D. Lee, and Michael I. Jordan. Ll-regularized neural networks are improperly learnable in polynomial time. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Pro- ceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 900-1001, New York, New York, USA, 20-22 Jun 2016a.
PMLR.
Yuchen Zhang, Jason D Lee, and Michael Jordan. 11-regularized neural networks are improperly learnable in polynomial time. In International Conference on Machine Learning, pp. 993-999--11 1001. PMLR, 2016b.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit Dhillon. Recovery guaran- tees for aue-hidden-layer neural networks. In International conference on machine learning, pp. 41 4140-4149. PMLR, 2017.
13

---

Published as a conference paper at ICLR 2025
A POLYNOMIAL APPROXIMATIONS OF NEURAL NETWORKS
A.1 RESULTS FROM APPROXIMATION THEORY
We first introduce some definitions that we will use throughout the appendix.
Definition A.1 ((e, It)-Uniform Approximation). For 0, R 2 1, and g IR* - R, we say that q: R + R is an (e, Rtn-uffform approximation polynomial for g if
(g(x) g(x)) S 1|[l|| - R.
Definition A.2. Let S {R + R) be a function class over R. For E, B > O, we say the (c. R)- uniform approximation degree of F is most with coefficient bound B if for any f F, there is an (e, (2)-uniform approximation polynomial p(æ) (x) for ʃ such that deg(p) I and each of the coefficients of p are bounded in absolute value by B.
The following useful facts about the coefficients of approximating polynomials.
Fact A.3 (Lemma 23 from Goel et al. (2017)). Let p be a polynomial of degree such that [p(x) S b for [x]| < 1. Then, the sum of squares of all its coefficients is at most 62 .2.20 -20())
Lemma A.A. Let p be a polynomial of degree such that [p(x)) S for |x| S R. Then, the sum of squares of all its coefficients is at most b² 20(5) when R. 2 1.
Proof. Consider g(x) - p( Rx). Clearly, |a(x)] < b for all |x|| S 1. Thus, the sum of squares of its coefficients is at most 12 201)) from Fact A.3. Now, p(x) = <(x/ R) has coefficients bounded by 6². 20(1) when R 2 1.
Fact A.5 (Ben-David et al. (2018)). Let q be polynomial with real coefficients on variables with degree E such that for all x E [0, 1] [q(x)] S Then the magnitude of any coefficient of q is at most (2kl(k + E) and the sum of the magnitudes of all coefficients of q at most (2 + E))
Lemma A.6. Let q be a polynomial with real coefficients on k variables with degree & such that for all x E & with ||=|| < R. |a(=)) S b. Then the sum of the magnitudes of all coefficients of is at most b(2(k 32) for R 2 1.
Proof. Consider the polynomial h(x) 1/b a( [Rx/ Vk). Then [h(x)) = 1/b 17bb-lade |a(Re// /v]]
for ||æR| Vklla < R. or equivalently for all |,||| S Vk. In particular, since the unit cube [o, 11tt contained the Vl radius ball, then [h(=)] < for æ E [0. 11a. By Fact A.5, the sum of the magnitudes the coefficients of h is at most (2 + 8))² Since g(x) = h(xVk/R). then the sum of the magnitudes of the coefficients of is at most b(2(k + ge/22
Lemma A.7. Let p(x)) be degree l polynomial in x E Rd such that each coefficient is bounded in absolute value by b. Then the sum of the magnitudes of the coefficients of p(a))² most b' d
In the following lemma, we bound the magnitude of approximating polynomials for subspace juntas outside the radius of approximation.
Lemma A.8. Let 0, > 1, and f Rdd - R be k-subspacc junta, and consider the corresponding function (Wxx.. Let q R& - R be an (c. -u-ufformm approximation polynomial for g, and define p Rd + R as p(æ) == q( (Ww). Let sup (g(We)) x)). Then
W R
< (r ( e) 2/2
< ||I R.
Proof. Since g(x:) is an (e, -unufifrrm approximation for g. then lg(x) g(x)) < for | 2 < R.
Let h(x)) = q( (Rx). Then [h(x/ R) -g(x) < e for ||œ|| < R. and so h(2/ / R) < r + for
|||||| R, equivalently [h(x)] < r for ||0|/ < 1. Write h(x) = E|aall haz 20 ... I..
14

---

Published as a conference paper at ICLR 2025
By Lemma A.6, Σ |all, Ihal (r c)(2
()k k/2 Then for ||>||2 1,
[n(a)]
Σ
ha |2 ... 2x
llall
Σ
|ha ||011 lal
|lell,
$ ||2 112
hhal:
|lallsee
where the second inequality holds because | / ||ll|| for all and last inequality holds because
||>:| 2
|
l2
[oc]
for
||a||| S when ||ح||| 1. Then since p(x) ((Wx) h(Wx/R), we have ()) + E) 24/2 for [[all2 2 R.
[p(x))
W
R
Proof. Note that p(æ) has at most terms. Expanding p(æ)) gives at most d terms, where any monomial formed from product of terms p(z). Then the coefficients of p(x)* bounded in absolute value by B", Summing over all monomials gives the bound.
The following is an important theorem that we use later to obtain uniform approximators for Lips- chitz Neural networks.
Theorem A.9 (Newman & Shapiro (1964)). Let f I2* unit sphere Sk-1. Let wy be the function defined as (y(t) = | la-llvlla (f(x)) - f(y) for any
be a function continuous on the
|z St
t 2 O. Then, we have that there exists a polynomial of degree such that sup||=|las f((x) 10(-)p(() s
C' C. (k/EE) where C is universal constant.
This implies the following corollary.
Corollary A.10. Let f R - R be an L-Lipschitz function for L 2 0 and let 2 0. Then, for any 2 0, there exists polynomial p of degree O(LRk/e) such that p is (e, R) -uniform approximation polynomial for f.
Proof. Consider the function g(a)) = -(Rr). Then, we have that is RL-Lipschitz. From
statement of Theorem A.9, we have that (l)()) S RTA. Thus, from Theorem A.9, there exists polynomial q of degree OLLRk/e) such that sup 12$1 19(y) q(v) s e. Thus, we have that s (x() - q(x R.) = sup]allia 1g(x/A R) q(x R)) = suppy l lo( a(8) < c.
p(x) == <(> R) is the required polynomial of degree (T.Rk/)))
n
A.2 USEFUL NOTATION AND FACTS
Given a univariate function 9 on and a vector æ (#1.... Fz) E Rdd, the vector g(x) e Rd is defined as the vector with hth co-ordinate equal to g(x;). For a matrix A E Rmxx we use the following notation:
||ll2 = su 1aaesslllaa ||
||Al = / maxxx(m) EØ=1 (Aiz)
.
-[A|] EEeSEt(n Asyl-
Fact A.11. Given a matrix W E Rxx, we have that
1. ||A]]2 < ||A|]I
2. ||Al|2 Vm |8
15

---

Published as a conference paper at ICLR 2025
Proof. We first prove (1). We have that for an R" with ||0||| 1,
m
|
S
Σ
(A..
x)²
(At)) = ||Al|
where the second inequality follows from Cauchy Schwartz and the last inequality follows from the fact that for any vector v, ||012 I |/e/11. We now prove (2). We have that
||x
> (A x)²
max VE I
(At)) S /m|lAA8
where the second incquality follows from Cauchy Schwartz and the last inequality is the definition.
Recall the definition of neural network.
Definition A.12 (Neural Network). Let or + R be an activation function with (0) I Let w (W(1)... :... W(+) with W TRaxxs-11 be the tuple of weight matrices. Here, 8p the input dimension and 8, = 1. Define recursively the function Js IR - RR* as f((Ø) - W()) o (x) with fi(x) = W(1) x. The function f I2d + R computed by the neural network (W,a) ar) is defined as ((x) = fe(x:). We denote [|] Ei= || The depth of this network L.
A.3 KERNEL REPRESENTATIONS
We now state and prove facts about Kernel Representations that we require. First, we recall the multinomial kernel from Goel et al. (2017).
Definition A.13. Consider the mapping the : 12" + I N where Nu Ei dl indexed by tuples ..., ig) E [d] for [4] such that value of (x)) index (21, , iz) is equal to IP Tt The kernel MK₃ is defined as
MKe( y) (We(a)) ve(z))
Σ (x y)
We denote the corrresponding RKHS HHMK;
We now prove that polynomial approximators of subspace juntas can be represented as elements of HIMK,-
Lemma A.14. Let E N and c, R 2 O. Let f Rdd + R be k-subspace junta such that f(x) g(Wx) where 9 is function on IR& and W is a projection matrix from Rkxd Suppose, there exists a polynomial of degree E such that supi (g()) - -q(y) S and the sum of
squares of coefficients of is bounded above by B², Then, f is (e, B2 (k + 1))))apppoximatte represented within radius with respect to HIMK,-
Proof. We argue that there exists a vector v E HMK, such that (v, v) < B and If(x)
(el)) S for all ||æ||| & R. Consider the polynomial p of degree & such that p(x:)
(Wx). We argue that p(x) = (v, aε(2)) for some v and that (v, v) S B². Let 9())
EsEn us I y 1s,1 From our assumption on g, we have that Σ EsEN lgs S B. For use define B, as B,
|||= (gsl- Given multi-index S, for any E [d].
define S(i) as the number such that M [S و E! [S.l. We now compute the entry of indexed by (i1, i2,..., 1x). By expanding the expression for pl x), we obtain that
Σ as II -
W j=1
W
16

---

Published as a conference paper at ICLR 2025
We now ready to bound (v, v). We have that
(0, v)
(1) ("hn....i
Σ
Σ
as
II
W
1=0 (E(1)))))(14
1=0 (E
St
j=1
Σ
Σ Ss
Σ
Σ
II
W
1=0 (e)
St|=
|
Σ
Σ
Σ
W
Σ
Σ |8|=t
95
+1
[S]
is|=ti=
OB ISICE
Σ
(k 1)x S B² (k 1)c.
Here, the first inequality follows from Cauchy-Schwarte the second follows by rearranging terms. The third inequality follows from the fact that the number of multi-indices of size from a set elements is at most (A: + 1)r The final inequality follows from the fact that the sum of the squares of the coefficients of q is at most B
We introduce an extension of the multinomial kernel that will be useful for our application to sigmoid-nets.
Definition A.15 (Composed multinomial kernel). Let (f1. 4)) be tuple in N We denote a sequence of mappings
1h We .....,42 2/2 on Rd inductively as follows:
1. / (0) (z)
2. v (x) = Vi, ve (z)).
(t) Let Nr(0) denote the number of coordinates in te This induces sequence of kemnlss
MK()) (0) MK(") ..... MK. .K..KKKKK defined as
MK (x. v) (wb (o), (v)) Σ
(20), v/e (())*)
and a corresponding sequence of RKHS denoted by H MMK H HMKS H Make
Observe that the the multinomial Kernel MK; MK (1) is instantiation of the composed multi- nomial kernel.
We now state some properties of the composed multinomial kernel.
Lemma A.16. Let L (fI,...,fe) Li) be tuple in N and R 2 O. Then, the following hold:
1. sup sn (K( (xx .)) S max{1, (2R)2 (2R)2
2. For any x. y Rd, MK!)) (t) (x, y) can be computed in time poly (d, (Et 6.)).
3. For any w E Makj and æ E Rd, we have (v, (0( (a:) is a polynomial in x of degree Ii C.
Proof. We assume without loss of generality that R 2 as the kernel function is increasing in norm. To prove (1), observe that for any æ. we have that
MK (8) (x, x) Σ
4
(MK! (xc (<:,))) (2MK!i-)(ax (xx 6+11
17

---

Published as a conference paper at ICLR 2025
We also have that suppallas 2 (2) x R. Thus, unrolling the recurrence gives us | (ar, x) S m1 (2+) S max (2R)) [.
The time follows from the fact that 2K? (ar, x) Σラz (MKE (x) and thus can be computed from MK(-)) with & additions and exponentiation operations. Recursing gives the final runtime.
(6) The fact that (2, 2 (a:) follows immediately from the fact the fact the entries of We (æ) arise from the multinomial kernel and hence are polynomials in The degree is most II l.
We now argue that a distribution that is hypercontractive with respect to polynomials is hypercon- tractive with respect the multinomial kernel.
Lemma A.17. Let 'D be distribution on R that is C-hypercontractivv for some constant C. Then, D is also ( C, I. ---eeppercontratieee
Proof. The proof immediately follows from Definition 3.4 and Lemma A.16(3).
A.4 NETS WITH LIPSCHITZ ACTIVATIONS
We are now ready to prove our theorem about uniform approximators for neural networks with Lipschitz activations. First, we prove that such networks describe a Lipschitz function.
Lemma A.18. Let f Rdd R the function computed by an t-layer neural network with L- Lipschitz activation function a and weight matrices W. Say, [|]] S W for W 2 0 and the first hidden layer has k neurons. Then we have that is ( 1 (WL)* - -ipschiitz.
Proof. First, observe from Fact A.11 1 that for all 1 < S T. | S W (since || S W) and || V Recall from Definition A.12, have the functions fi.... fa where and fi(x) w()) x. We prove by induction on that [[f(()) f(( 4) 2)ll2 S (S s-1 ull2.. 2. For the base case, observe that
fzx)
di
(wW ax) (w,") + =a))²
(w:
(w:a)) (u)
[[ + u) f1(20)112 <
S I[ u112 S 15 1|l|2
where the second inequality follows from the Lipschitzness of a and the final inequality follows from the definition of operator norm. We now proceed to the inductive step. Assume by induction that [[f(())) f(( + u)ll2 is at most (2) ||2l1| Thus, we have
di
(w((+)) .0 (f.(x))) (w/++), o (f.l + w)))
[lf+1( + +2) f2)2
< Iello o v (LW)"|lulla
<
where the third inequality follows from the Lipschitzness of and the inductive hypothesis. Thus, get that []( + u) - [a)) [[ u) [1) (a) (WL)
||u]|2
We now state are theorem regarding the uniform approximation of Lipschitz nets. We also prove that the approximators can be represented by low norm vectors in RMK, for appropriately chosen degree E.
Theorem A.19, Let e, R 2 O. Let f on Bd be a neural network with an L-Lipschitz activation function o, depth I. and weight matrices W (W(1)..... ,..., W(O) where W E x Let
18

---

Published as a conference paper at ICLR 2025
k be the number of neurons in the first hidden layer. Then, there exists of polynomial p of de- that is an (e, R) R)-unfform approximation polynomial for f. Furthermore, is (e, (k + E) Japprxxitiil represented within radius R with respect to H]ı,; = THT MK(1) In fact, when k- = 1, it holds that is (e, (0,20(0) ( "approximately represented within R with respect to HMKg".
gree 8 - (IIWa) (
Proof. We can express as f(x)) g(Px) where P is a projection matrix and g is neu- ral network with input size k. We observe that the Lipschitz constant of is the same as the Lipschitz constant of f since P is a projection matrix. From Lemma A.18, we have that g is (IVKW((1) || (W -ipshittt From Corollary A.10, we have that there exists a polynomial of degree l O (I ( that is (c, R)-uniform approximation for g- From Lemma A.6, we have that the sum of squares of magnitudes of coefficients of is bounded by (IVVWW 112 (WL) -) (A: + E)0()) S (k + E)0()) Now, applying Lemma A. yields the result. When le 1, apply Lemma A.4 to obtain that the sum of squares of magnitudes of coefficients of q is bounded by || (WL) 2010) s 220(5_
A.5 SIGMOIDS AND SIGMOID-NETS
We now give custom proof for the case of neural networks with sigmoid activation. We do this as we can hope to get O(log(1/e) degree for our polynomial approximation. We largely follow the proof technique of Goel et al. (2017) and Zhang et al. (2016a). The modifications we make are to handle the case where the radius of approximation is a variable R instead of a constant. We require(for our applications to must scale linear in R, a property that does not follow directly from the analysis given in Goel et al. (2017). We modify their analysis to achieve this linear dependence.
distributions) that the degree of approximation
We first state a result regarding polynomial approximations for a single sigmoid activation.
Theorem A.20 (Livni et al. (2014)). Let o R + IR denote the function (xx) = I+ Let R, 2 Then, there exists a polynomial of degree = O R log( (R/c)) such that sup supj=|sn lo(x) p(=) Also, the sum of the squares of the coefficients of p is bounded above by 20())
We now present construction of uniform approximation for neural networks with sigmoid activa- tions. The construction similar to the one in Goel et al. (2017) but the analysis deviates as linear dependence on radius of approximation is important to us.
Theorem A.21. Let e, R 2 0. Let f on Ed be neural network with sigmoid activations, depth t and weight matrices W = (W()) ..., W(t) where W() E Reex Also, let [| S W. Then, there exists of polynomial p of degree that is an (e, R)-uniform approximation polynomial for S. Furthermore, f is (e, B) -approximaaeel represented within radius R with respect to H MKK!) where e = (E1,...,(4_1 is a tuple of degrees
O ((Rlog R) 1110 - (t log log(W/c))
l2-1)
whose product is bounded by f. Here, B S (2][WW (B Wo
Proof. First, let @ be the polynomial guaranteed by Theorem A.20 that the sigmoid in an interval of radius R. Denote the degree of 91 as l = O [Rt|] log(RW/e))
appprxximaaes
For all 1 < < t, let qi be the polynomial that (c/(2W)*)- approximates the sigmoid upto radius 2W. These have degree equal to O (W'log log(W)))). Let
e l..). For all i E [t - 1), let (x(x) E0= $10 x. We know that Σ (8 s 20(4).
We now construct the polynomial p that approximates f. For i [t], define p,(x) w q-1 (x)) with pı (z) W()) æ. Define p(æ) (x). Recall that (x( is vector of s; polynomials. We prove the following by induction: for every E [t].
1. (m) f((=)]l> $ </((2))-+
19

---

Published as a conference paper at ICLR 2025
2. For each [ss], we have that (n)))(x) (0, (x0) with (0,0) S
) ) -1) 6.) woTTl fa),
where the function ft is as defined in Definition A.12.
The above holds trivially for i = and f1(x) (a()) = W()) (ax) an exact approximator, Also,
(p) (xx) (w(") .)) (w(") ( (x)) from the definition of v Clearly, (w:"), w(") s
(IIW()))) We now prove that the above holds for i + 1 [t] assuming it holds for i.
We first prove (1). For E [s141], we have that
((p+1))(2) (f)1)) / (a(pi(z)) (ff(())))
[W ( ((.((=)) + | -o(p) S SW. (c/(2W)) + w.w.w///// (/(22)/(22- </ (222)
For the second inequality, we analyse the cases = and > 1 separately. When i = 1, we have that (zr) = (a) Rll and (zz) qi (I) < (e/(2W))) when la| S R|JWi 112 For
i >> 1. from the inductive hypothesis. we have that [W(++)) (x)) < f(()) + |WO+*)|
(</(2W)<)) < 2W. The second term in the second inequality bounded since a 1-Lipschitz.
We now ready to prove that (ps+1); is representable by small norm vectors in H MeKf+ for all
j E [8)+1]. We have that
8; qi ((p))
(2)+ = Σ w-b-1) k=1
jk:
From the inductive hypothesis, we have that (p:) = (bll), 1/) Thus, we have that
(p1+2)s(z)= Σ w
9b (1o( (()()),(()))
sk
We expand each term in the above sum. We obtain,
di (10(()) 21(()))
8(i)
(fv(t) (6 )
n=0
g(t)
Σ
(k) (K) (0 (z)) mi
... (w))
(..vv) (2))((0))
mm
MEINN
(M) ()) th. (wv (x)) = (u (K)
2//2
(1+1) (x))
The second inequality follows from expanding the equation. [ Im for S & has entries given by mm..).....)) obtain that
(k) indexed by (m.....,m. E (k)
(k)
(((0) ( Um... Putting things together,
(p(+1)((z)
((++1) (1) 1 (x)))
jk
(1+ 1) (K), wb (x)+)
Thus, we have proved that (pe41); is representable in H HMKK445. We now prove that the norm of the representation small. We have that
w((+)) (1+1) r (k) ||
max | kE(*:]
12 S W. max
| (b0
RE(+.]
20

---

Published as a conference paper at ICLR 2025
We bound [ax we have that
1/2 1|2.
For any k, from the definition of (h) and the inductive hypothesis,
(k)
12
g(0
2
Σ
II
n
2 mm
ma M 2 10 /=1
4
2
g(0
||00
122m S 20(e)) 11.(2)
We analyse the case and 1 separately. When 1, we have that 20161) s (2) (o
from the bound on the base case. When 1, we have
W 1)) w jk
13
w22014 1220
(200.11) woutt 26,
w220
which completes the induction. We are ready calculate the bound on the degree.
We have 2 ((Rt]IW()) log RW/))). Also, for i > 1, we have & O(Wtlog(W/e)) Thus, the total degree is l II & - O ((R R) (1 (|/o////)))))tt/((////)))))))))) (tlog(W/e))*-)), of the norm of the kernel representation is bounded by B where
The square
B S (2)) wo(w "(elog(W/e)* 2).
This concludes the proof.
B TDS LEARNING AND KERNEL METHODS
B.1 GENERAL THEOREM
We provide here the full proof of Theorem 3.6. First, restate and prove the multiplicative spectral concentration lemma (Lemma 3.8).
Lemma B.1 (Multiplicative Spectral Concentration, Lemma B.1 in Goel et al. (2024), mod- ified). Let De be distribution over Re and 6 Hd Rm such that Dx is (ø, C) hypercontractive for some C, 2 1. Suppose that S consists of N i.i.d. examples from Da and let Φb ELwDD (ooeD,,((())ee [0(x)(()) JI, and & NN EeEs ((x) For any c, E (0,1), if
N 64Cm² (4Cllogz (2) se+1, then with probability at least 1 5, we have that
For any a E Rm a T $ E [[1 [(1-e)a va, (1 + e)a $a)
Proof of Lemma 3.8. Let $ T be the compact SVD of + (i.e., D is square with dimension equal to the rank of &b and U is not necessarily square). Note that such decomposition exists (where the row and column spaces are both spanned by the same basis U), because Moreover, note that UUT is an orthogonal projection matrix that projects points in m on the span of the rows of क. We also have that, U TTU U
TT. by definition.
Consider क UDT and $
İTT Our proof consists of two parts. We first show that it is sufficient to prove that | bo! - Φ2Φ0 à l|2 5 e with probability at least - d and then we give a bound on the probability of this event.
Claim. Suppose that for A ΦiΦΦł Φ we have || S e. Then, for any a E R
a t [(1 -c)a Ta, va, (1
e)a Ta.
21

---

Published as a conference paper at ICLR 2025
Proof. Let R", a+ UU a, and au (I UU )a (i.e., do + a+, where ag is the component of a lying in the nullspace of Φ). We have that a Φa = ba..
Moreover, for dg. we have that = a tas = ED [()()) an) and, hence, d(x) ag = 0 almost surely over Dx. Therefore, we also have ag Pas = Excs(((x) ao)² = 0, with probability Therefore, T ta a da+.
Observe, now, that Φ U'D = UUT and, hence, 2 (oUT)aa UU a = a.,, because UU is projection matrix. Overall, we obtain the following
a T ta = a t + a Φ)
a T ta + a x ( hh s plppijol
a v + a A
Since ||||2 S e and &i _ = 4, we have that la 4 A S cla 2a+1 = Val. which concludes the proof of the claim.
remains to show that for the matrix A defined in the previous claim, we have ||||| & e with
probability least 1- 8. The randomness of A depends on the random choice of S from D In the rest of the proof, therefore. consider all probabilities and expectations to be over S ~ D We have the following for (4/8))
E A 2
Pr Pr|l|Ale e) Pr P||l|A| c)
We will now bound the expectation of E||| To this end, define a, dée, R for i E [m]. We have the following, by using Jensen's 's inequality appropriately.
E A
E
Σ
(a day a @aa)))
i.j ml
$ 2((-11
[a Paj a, )
i.E((m
S m
max (jjmm]
El bay a; $a 21
In order to bound the term above, we may use Marcinkiewicz-Zygnne (2014)) to exploit the independence of the samples in S and obtain the following.
inequality (see Ferger
2(4r)*
Bi(a Da a, TT,
No EEwDo [a, Da, a ((x))(x)T Ta,) 21)
((tt)* (2 Da,) 2² + 2 D. I(a ((x))(()) Ta,) 2!])
< N
We now observe that E.-D, [aT ((z))(x) a,] a, ba e, Tpippbe e. eTUUee, ej, which is at most equal to 1. Therefore, we have EzwD, (la x(x)) < and, by the hypercontractiv ity property (which we assume be with respect the standard inner product in TR"", we have En--e, (a, " < (4C1) We can bound Em-D,, (a, ((x))(()) 22 by applying the Mauchy-Schward inequality and using the bound for ENND, (a, ((z)) In total, we have the following bound.
( (16mm((4C1))
Pr||| $554
Ne²
1(Cce Ne²
We choose N such that
< and f (4/5) so that the bound is at most
We are now ready prove the main theorem, which restate here for convenience.
Theorem B.2 (TDS Learning via the Kernel Method). Suppose that F S (RR - R), the training and test distributions D, D' over Rd x IR, are such that the following are true for A, B, C. M, ( and (0, 1).
22

---

Published as a conference paper at ICLR 2025
1. F is (c, -pppprooxil represented within radius R w.r.t. a PDS kernel K. R x R I. for some e E (0,1) and B, R 2 and let A = supa: mlla K(xx x)).
2. The training marginal Dr (1) is bounded within {xr ||||| S R} and (2) is (K, C2
hypercontractive for some C, E 2 L.
3. The training and test labels are both bounded in [-M, M) for some M 2 1.
Then, Algorithm/ I learns the class F in the TDS regression setting up to excess error 5e and proba- bility of failure 5. The time complexity is O(T) poly(d, 2 (log(1/6)) A, B, 2", M), where T is the evaluation time of KC.
Proof Theorem 3.6. Consider the reference feature map á : Rd + R with 6(x)
(K(x,, u rot Let f arg minse=(<D(() + LD (f)) and fops arg minnee((c(()))
By Assumption 3.5, we know that there are functions PPPpppt R2 R with p (a) = (v", (x))
and Popt = (Nope, vb(x)), that uniformly approximate f and Saps within the ball of radius R, i.e, suPa:|lelaasR (x)) p" (x)) I c and supa: |al fapt (x) Popt S c. Moreover, (0","") (Vopt; Pops) S B.
By Proposition 3.7, there a" R.20 such that for p Rd R with (x)) TT())) we have || p7' Suu I 3e/2 and I1f* p" lls, S 3e/2. Let K be matrix in 222xx2m such that K [(zz, w) for z, w E Stet U Shet- We additionally have that (at) Ka' S B. Therefore, for any x Rd we have
(x)()))
Σ
dz((2), ((())){a))) )(x)))²
# U ret
Σ
Σ a()(()) (()))))(a)))
=ES rer
=ES
=aa) Ka K(x, S B K(x,x),
where we used the Schwary inequality. For with ||l|| S R, we, hence, have (z²(z))² S AB (recall that A = max a5| S x)),
Similarly, by applying the representer theorem (Theorem 6.11 1 in Mohri et al. (2018)) for Popt. we have that there exists ar Exes... aa x2z x) we have LS... (Pops.) < Ls, (Pope) and Exwes... aa Since P in Algorithm 1 is formed by solving a convex program whose search space includes Popt we have
)xESta E RT such that for Popt IRd + R with Popt (x)
w) S B.
CS,,, (p) S L3 S L (Pops.
(1)
In the following, we abuse the notation and consider à to be vector in R2m by appending zeroes, one for each of the elements of 5 Note that we then have à T Kä S B, and, also, (f(x))) < A. for all æ with ||a||e R.
Soundness. Suppose first that the algorithm has accepted. In what follows, we will use the triangle inequality of the norms to bound for functions h, h2, hy the quantity ||,, h22 ll by h ha Ia + l D. We also use the inequality LD < LD(h2) + [/ - ha pellD, as well as the fact that |cl o h1 - cl h2llD < ||cla h1 h2llD S ll4g - h2llD- We bound the test error of the output
hypothesis h RR + [-M, M] of Algorithm as follows.
+ C S |/h clas o + CD")))
Since (h(x) clas cf < 4M2 for all æ and the hypothesis h does not depend on the set Ser. by a Hoeffding bound and the fact that m is large enough, we obtain that // c1ys o Dz S
11l-clmoflll +e/10, with probability at least 88100. Moreover, we have //- ch cly p0 I1s + 11 ("1l, We have already argued that ||ø- f llss < 3c/2.
In order to bound the quantity ||A clas pn Ils we observe that while the function h does not depend on S' the function 5 does depend on Sy and, therefore, standard concentration
23

---

Published as a conference paper at ICLR 2025
arguments fail bound the cla 1'1ls,,. in terms of ||A -clas "" lo However, since have clipped p", and 8" is of the form (v", (v), we may obtain bound using standard results from generalization theory (i.e., bounds on the Rademacher complexity of kemel-based hypotheses like Theorem 6.12 in Mohri et al. (2018) and uniform convergence bounds for classes with bounded Rademacher complexity under Lipschitz and bounded losses like Theorem 11.3 in Mohri et al. (2018)). In particular, we have that with probability at least 6/10
|| - clM o ls I ||A clM o p ll + c/11
The corresponding requirement for m 1S | is determined by the bounds on the Lipschitz constant of the loss function (y.t) + (y 1y--cha clas (t)) with E [-M, M] and t E R, which is at most 5M, the overall bound on this loss function, which is at most 4M2 well as the bounds A max=: s K(xx, x) and (a*) Ka I B (which give bounds on the Rademacher complexity).
By applying the Hoeffding bound, we are able to further bound the quantity ||h clM o p llp by || - clas p" l| + +/100, with probability at least 1 8. We have effectively managed to bound the quantity ||A - clM o - lls,,, by || clas o st... +e/5. This is important, because the set S a fresh set of examples and, therefore, independent from p. Our goal is now to use the fact that our spectral tester has accepted. We have the following for the matrix &' ($'s S with $
=, Emesr K(æx, 2)x( w).
|| ClM o p111s S 110 - 100-p1113 11
(a - aa) Ta 10-aaa a²)
Since test has accepted, we know that (á-a") T') a²) (1+ T'i-aaa--@aa a"), for the matrix = ( having a multiplicative bound of this form is important, because we do not have any upper bound on the norms of and a*. Instead, we only have bounds on distorted versions of these vectors, e.g., on à K a, which does not imply any bound on the norm of à, because K could have very small singular values.
with 22.w = Em K(x, K)xx w). We note here that
3s Overall, we have that || Iss 110 5² Is S V 0(21011.... + +1 S VIABp S
TO By using results from generalization theory once more, we obtain that with probability at least 1 1-8/5 5/5 we have | 5 I| S | sl...... + c//5. This step important, because the only fact we know about the quality of is that it outperforms every polynomial on the sample Seef (not necessarily over the entire training distribution). We once more may use bounds on the values of p and p", this time without requiring clipping, since we know that the training marginal is bounded and, hence, the values of P and p" are bounded as well. This was not true for the test distribution, since we did not make any assumptions about it.
In order to bound || - 17' (slms... we have the following.
|p 15 Illss. I Cs, (P) + LB, (clo f*) + 11f -p--ppp 1'1lsset
< Lmn (Dop.) + SS (cl 1*) + 115 - 1" l|stet
(By equation 1)
< L (Pope) + Ls (cl f*) + 1lf* - -
The first term above is bounded as f.S. (Popt) S LSsy, (clm Sopt) + ll Soptlll Is where the second term is at most (by the definition of Popt) and the first term can be bounded by (f(pt)) + e/10 = opt + e/10, 10, with probability at least 1- 8/10, ,, due to an application of the Hoeffding bound.
For the term L (cl o f*) we can similarly use the Hoeffding bound to obtain, with probability at least 1 - 5/10 that Ls.., (cl o f*) I LD(f") + c/10.
Finally, for the term |lf" p" ||s... we have that |lf -5""ls S 33/22, argued above.
Overall, we obtain a bound of the form (/(()) S CD(f*) = (D( + LD(fopt) + 5e, with probability at least 1 - d, desired.
Completeness. For the completeness criterion, we assume that the test marginal is equal to the training marginal. Then, by Lemma 3.8 (where we observe that any (v, C, eyyercorccce
24

---

Published as a conference paper at ICLR 2025
distribution is also (Ø, C, ()-hypercootrractive), with probability at least 8, we have that for all 1+(p/4) IR2". a T I 1-(p/() a T ba S (1+ppa ta, because B[$] = E[ and the matrices are sums of independent samples of ((=))((x= where formed by using Stet) does not depend on the verification samples Sver and Sver which is why we chose them to be fresh. Therefore, the test will accept with probability at least 1 6.
Da- is crucial here that ø (which recall
Efficient Implementation. To compute a, we may least squares program, in time polyno- mial in m. For the spectral tester, we first compute the SVD of O and check that any vector in the kernel of & is also in the kernel of é' (this can be checked without computing the SVD of ('). Otherwise, reject. Then, let & be the root of the Moore-Penrose pseudoinverse & and find the maximum singular value of the matrix $ If the value is higher than 1 + p. reject. Note that this is equivalent to solving the eigenvalue problem described in Algorithm 1.
B.2 APPLICATIONS
We first state and prove our end to end results on TDS learning Sigmoid and Lipschitz nets over bounded marginals that are C-hypereontractive for some constant C.
Theorem B.3 (TDS Learning for Nets with Sigmoid Activation). Let F on H. be the class of neural
network with sigmoid activations, depth t and weight matrices W = -W(1), W()) such that |[[| S W. Let e E (0, 1). Suppose the training and test distributions D, D'D' over Rd x R are such that the following are true:
1. D is bounded within {x |2112 S R} and is C-hopercontraativve for R, C2L
2. The training and test labels are bounded in [-M, M) for some M 2 1.
Then,
Algorithm 1 learns the class F in the TDS regression up excess error 6 and probability of failure 5. The time and sample complexity is poly C ,M, (2))) ( (2)) t= 0 (RRog R) (IWW2)133--2))) : ((log(W/e))--1)
(o((Wolo(()))) 9)
where
Proof. From Theorem A.21, we have that F is (c. (< (w"
approximately represented within radius R w.r.t MK.)) where é is a degree vector whose product
is equal to = O ((Rlog R) (1IW( Wtt2) (l)) Also, from Lemma A. we have that A == SR MK (1) (x,, a)) < (2R)2* From Lemma A.16, the entries of the ker- nel can be computed in poly (d, E) time and from Lemma A.17, we have that D' is (MK (1) C, hypercontractive. Now, we obtain the result by applying Theorem B.2.
The following corollary TDS learning two layer sigmoid networks in polynomial time readily follows.
Corollary B.4. Let on Rd be the class of two-layer neural networks with weight matrices W (W(), W(2) and sigmoid activations. Let [| 11 < 0(1) and |W || < W. Suppose the training and test distributions satisfy the assumptions from Theorem B.3 with R = O(1). Then, Algorithm learns the class F in the TDS regression setting up excess error e and probability of failure 0.1 in time and sample complexity poly(d, 1/e, M).
Proof. The proof immediately follows from Theorem B.3 by setting = 2 and the other parameters to the appropriate constants.
Theorem B.5 (TDS Learning for Nets with Lipschitz Activation). Let FF on IRd be the class of neural network with L-Lipschitz activations, depth t and weight matrices W =(W(),... ..... W(() such that W[] < W. Let E (0, 1). Suppose the training and test distributions D, D' over Rd x R are such that the following are true;
25

---

Published as a conference paper at ICLR 2025
1. Da is bounded within {a | S R) and is C-hypercontracttive for R, C 2 1,
2. The training and test labels are bounded in [-M, MM for some M 2 1.
Then, Algorithm learns the class F in the TDS regression up to excess enoor and probability of failure 8. The time and sample complexity is poly (d, :. C², M, log(1/5);, (2R(k + E))(()) where
L = (1 (WL) (W-)eR When = 1, we have that the time and sample complexity is poly(d, L. C", M,, (2R) where 8 = O (2W) (WL)-1R//4 R/c).
Proof. From Theorem A.19, for k we have that is (e, (k + resented within radius R w.r. 6 where is degree vector whose product is equal to For io = 1, we have that we have that F is (c, (c,20())) approximately represented within radius R w.r.t MK!) where & is a degree vector whose prod- uct is equal to = O ([[W (W Also, from Lemma A.16, we have that A == S M
rep-
é = = [
(t) (x, æ) & (2R)0() From Lemma A.16, the entries of the kernel can be computed in poly(d, E) time and from Lemma A.17, we have that De is (MK&)) C,é) hypercontractive. Now, we obtain the result by applying Theorem B.2.
The above theorem implies the following corollary about TDS learning the class of ReLUs. Corollary B.6. Let F fa - max(0, x) || = 1} R' be the class of ReLU functions with unit weight vectors. Suppose the training and test distributions satisfy the assumptions from Theorem B.5 with R 0(1). Then, Algorithm I learns the class F in the TDS regression setting up excess error and probability of failure 0.1 in time and sample complexity poly (d, (d,20012 2011/), M).
Proof. The proof immediately follows from Theorem B.5 by setting t = 2, W = =(w) and the activation to be the ReLUU function.
In particular, this implies that the class of ReLUs is TDS learnable in polynomial time when c 0(1/ log d).
C TDS LEARNING AND UNIFORM APPROXIMATION
C.I PRELIMINARIES
We first define the notion of subspace junta which will be useful in this section. Intuitively, want to consider the neural network as a function of W after the first layer of weights has been applied, which allows us to project from the higher d-dimensional input space to a k-dimensional subspace.
Definition C.1 (Subspace Junta). A function f RRd - R is a k-subspace junta (where k I d) there exists W E gitdd with || 2| 1 and W WWT. 11 and function g g* IR such that
(x) fw(( gWrr Yor E TRd.
Note that by taking & = d, letting W Ia covers all functions f R.R-RR.
We obtain the following corollary which gives the analogous bound on the (c, R)-ufiform approxi- mation to a k-subspace junta, given the (c, -u)uufrfomm approximation to the corresponding function
g.
Corollary C.2. Let > 0, 2 1. and f Rd + R be a k-subspace junta, and consider the corresponding function g (Wr). Let q R + E be an (c, Ru-unfform approximation polynomial for g. and define p: Rd - R as p(x: = (W.)). Then (p(x) f(x)) S for all || < R.
In this section, we obtain TDS learning algorithms with respect to a training marginal which is a strictly sub-exponential distribution, which now define.
26

---

Published as a conference paper at ICLR 2025
Definition C.3 (Strictly Sub-exponential Distribution). A distribution D on R is y- subex- ponential if there exist constants C, E (0, 1] such that for all w E R" w = 1, f, 2 0,
Pro- (ur, mb] > 8 e -C
These distributions have the following bounds on their moments.
Fact C.4 (see Vershynin (2018)). Let D R be r-strictly subexponential distribution. Then for all w E R | = 1,t 0.p p 2 there exists a constant C' such that
B,-D[l(w, a) S (C)
In fact, the two conditions are equivalent.
We will use the following bounds on the concentration of subexponential moments in the analysis of our algorithm. This will be useful in showing the sample complexity N required in order for the empirical moments of the sample S concentrate around the moments of the training marginal D...
Lemma C.5 (Moment Concentration of Subexponential Distributions). Let D be distribution over Rd such that for any w E Rd with ||w]22 = 1 and any t E N we have Eæ-D, I/ (as)xe(d N we denote with x the quantity (xi)ield)- Then, for any A E (0, if S is set of at least i..dd examples from Drr for some sufficientll large universal constant e 2 2. we have that with probability at least 8, the following is true.
x1'] S (Ct)² for some C 2 1. For
x HH oi"', where
N 3z (Ce) (log(20)))) (log(20d/)))
For any a E Nd with [|e]]] S we have [Fa~s(>= Em I
Proof. Let a (as)ield Nd with ||al|2 S 26. Consider the random variable X Exesar xa
Merran Exes ILE ai We have that B[X] EewDD (x*)) and also the fol-
lowing.
[E[ _[
Pr| E[XI
A
2r
2(46)
B[(x" 2[
(N
where the last inequality follows from the Marcinkiewicz-Zyymmrr inequality (see Ferger (2014)).
We have that [[ [ ))a] < (<x Since ||a||ı < 2f, we have that [[[ S
[ x) [] I (4Ct8) which yields the desired result, due the choice of N and
after a union bound over all the possible choices of a (at most dR
C.2 GENERAL THEOREM
We now present the assumptions that required by our TDS learner under strictly sub-exponential distributions.
Assumption C.6. For a function class F C [Rd R} consisting of k-subspaces juntas, and training and test distributions D, D'' over TRd x IR we assuming the the following.
1. For F, there exists an (E, Rt)uniform approximation polynomial for f with degree at most Rlog R. gF(e), where gF(e) is a function depending only on the class F and e.
2. For f F, the value rf sup wa 1 [f()) is bounded by constant
3. The training marginal Dr is a r-strictly subexponential distribution.
4. The training and test labels are both bounded in [-M, for some M 2 1.
Given this assumption, now give the statement of the TDS learning algorithm.
Theorem C.7 (TDS Learning via Uniform Approximation). Assume Assumption C.6 holds. Let 6, E (0, 1). Then, algorithm (Algorithm 2) learns F in the TDS regression setting up excess error 4c and has probability of failure 8. The time complexity is poly(d", In(1/8). 1/c) where
s = poly (()g((t) log(r) (o)(M)))))+1)) and TDS learns F with respect to D up to excess error 4c and with failure probability 8.
27

---

Published as a conference paper at ICLR 2025
The following lemma allows us to relate the squared loss of the difference of polynomials under set S and under D, as long as we have a bound on the coefficients of the polynomials. This will be convenient in the analysis of the algorithm.
Lemma C.8 (Transfer Lemma for Square Loss, see Klivans al. (2024a)). Let D be a distribution over IR' and S be set of points in R If [[==~((="] Ex-plæ") I A for all a E No with || S 28, then for any degree polynomials pl, P2 with coefficients absolutely bounded by B, holds that
(Ewsl(pi(x)) - (Fap ( P2(1)))
S 4B'
Algorithm 2: TDS Regression via Uniform Approximation
Input: Parameters > 0, E 1), R 1, M 2 1, and sample access to D, D' Rlog R- gr),), == 2log (22) Set Mirain = Miest = poly (M, In(10)),, d', r)) and draw merain i.dd. labeled examples S from D and Meest i.i.d. unlabeled examples S' from D'2
Set c' = c/11, 8/4,
) (22).
r(2(k + E)) A 1
ea
For each & E with ||a|/ S max(e, t), compute the quantity
M, = Eg [a0] = Ex-s'' [Iee ";"
Reject and terminate if IMa - EEWD [x]]| > A for some with ||al|a S 2 max(e, t). Otherwise, solve the following least squares problem on up to error e'
min P
E(Ew)~ [(V - p(x)))
s.t. is a polynomial with degree at most & each coefficient of p is absolutely bounded by B
Let ý be an appapoooie solution to the above optimization problem.
Accept and output clus (f(x)).
Proof. We will prove soundness and completeness separately.
Soundness. Suppose the algorithm accepts and outputs (p). Let f = arg (C)()) + ED (f)] and fopt = arg min)er(CC((f) By the uniform approximation assumption in Assump- tion C.6, there are polynomials p" Popt which are (c, R)-uniform approximations for f" and fopt> respectively. Let f and fopt have the corresponding matrices W Wopt Rxxd respectively. Denote Atrain CDf*)) and Atest functions will not increase their squared loss under any distribution, i.e. ||cl
(f*). Note that for any f.g R + R, "unclipping" both
(g) S - gl which can be seen through casework and when f(x), g(x) are in [-M, MM not.
Recalling that the training and test labels are bounded, we can use this fact as we bound the error of the hypothesis on D'
(clN(())) S
- cl (f)ls: +
S [f)((()((
The second inequality follows from unclipping the first term and by applying Hoeffding's inequality,
8M In(2/5'), the second term is bounded with probability 2 1 8'. Proceeding
so that for Mhst with more unclipping and using the triangle inequality:
edd
CD (p) I Arest + (f*) - clu (v" lls + [|cllr(p)) cly (P) +e'
S Atest + []*) - ClM (1" )ls + '1p" -plls: +6'
We first bound [cck(())) cl (p")) = V Ex [clas (x)( clM (L=()=())))+ [x) Since (x) is an (e, (e, -tn-uiformm approximation to (xx,, we separately consider when we fall in the region of good approximation (i (1*' x: < R) or not.
B (cl (x:) - (x)(")))))
S (cl (f)()) - (M)))))))m((())))))))))))( W æ1| $ R]
+ Ex~s' (f)()) - clar(p' (x))) ]||["a|| x| R]
2 E (2cca + Cly cl (p (x))² -1[["> x1 R]
28

---

Published as a conference paper at ICLR 2025
Then by applying Cauchy-Schward (and similarly for clu (p")):
1[[[W*= æ R]] I VE [clM (f))))) /r [ > R]]. By definition, ClM (p") }², clx < M now have
Ee
So it suffices to bound Pr [[ x > R]]. since we
S (f cl (x)())))) 2 Pra [ m
R
(2)
In order to bound this probability of the test samples falling outside the region of good approxima-
tion, we use the property that the first 2/ moments of S" are close to the moments of D (as tested by the algorithm). Applying Markov's inequality, we have
E Eg 8 I x: x11"1
Pr [
[|
R]] S
R
Write ||**'| x: 21|2² (EL where Ei degree 2 polynomial with each coefficient bounded in absolute value by 2k (noting that since WWT = L, then [Way| < 1). Let aa denote the coefficients of ||** Applying Lemma A.7, E [|l| 52r la I d2 d0t)) By linearity of expectation, also have |E [||W*=]|'
Ei= (E/-
is
EgnD [|] x: 1 S2 |a,l A S do(t) A G, where A I c' dd Since D is (W; )²)²) S (2C")) +.. Then, we can bound + e' I (Ckt) +5 for some large constant C.
y-strictly subexponential, then by Fact C.4, Egwpl
the numerator Ex~s' [[| 131] < Be |||l=
So we have that
(Ckl) 147
Pr Pr [I] [ R] S
R.D
Setting: 2 (e() and R 2 (*(tt) 2 C'k loglog(( (M/e) for large enough C' makes the above probability at most /M so that 4M2 /Prm-s 1 [> > R] S c²2 Thus, from Equa- tion (2), we have that
[[c) (p))) s Se+6'.
We now bound the second term - S will concentrate around those of Dx whenever Marrin 2 (C ((gg))/ (log)(00/))))
By Lemma C.5, the first 2 moments of
1e+1, and similarly the first 28 moments of S" match with Dn because the algorithm accepted. Using the transfer lemma (Lemma C.8) when considering p' = (p" 2) along with the triangle inequality, we get:
(x) - -(x))lss
1 [p'(x) p(z) 1l + V
s (p'(x) p()))l + < Ls(p")+ (p) + 2
where we note that we can bound the sum of the magnitudes of the coefficients by r(2(k + 8))3* using Lemma A.6. Recall that by definition P is an apprroxxie solution to the optimization problem in Algorithm 2, so Ls(D) S (Popp) + +'. Plugging this in, we obtain
Ilp (x) - -(x))l S Ls(p') ) + (P(op))) + +
$ <Ipp* clu (f ((c))(('))s
+ PllPopt (x) - clas (Fopt (x))]ls + (epp)) + 3e'.
By applying Hoeffding's inequality, we get that ||c|
vlls S [f*) Mllp + e' which holds with probability 2 1 1-8 8' when mirain 815" In(2/6'1 By unclipping clar this is at most - -yll S opt e'. It remains to bound [xx) (or)-col (f))l") and [|Popt - clas (fopt (x) [x)) The analysis for both is similar to how
Auaan + Similarly, with probability 2 1-18- 8', [
we bounded (p") cclr)ff except since we do not clip p" or Popt we will instead take
advantage of the bound on (xx) on |["*>|| > R (respectively Popt (ær) on [ > R). We
show how to bound (xx - clla(f")ll lls:
Ees [(c) (()))(((())) - (2))) = Ex- [cll - (z))² ||| x]|| S R
+ E (( (f) pp (=))² W' x > R]
< 2 + 2 (cl (f" (z))² [||l"(|| x|| > R]
+ 2B ( W'| R].
29

---

Published as a conference paper at ICLR 2025
We can bound the first expectation term with c²2/4 since the same analysis holds for bounding Ex (ww.ssccllcfff (f 1[] æi > R]], except instead of matching the first 2r moments of S' with Da match the first 26 moments of S with D=. We use the strictly subexponential tails of Da to bound the second term. Cauchy-Schwarz gives
Ba pp" (a)² [[[] > R]] S (B) Præ-s W > R]
Note that by definition of r and using that is an (c, R)-uniform approximation of f", then p" (z) S er++) when [ < R. By Lemma A.6, Ip" (a=) & (2ke) II(W**) xV)/ for sufficiently
large constant 61 > Then since R 2 1, pz S (r (2k)) [|"*>||** Then we have
E Ex ( - (r + (2k))a)))
Be x| |d1
(r (2ke) of (EgwD, [| 1 +1)
s + e)² (2ke)
similar to above, which can be where using Fact C.4 we bound on Ez~D_, |ll = =1"1 I (48) +
upper bounded with (2k))oz for c2 0 a sufficiently large constant. Take C1 c2. We bound
Praws|l|W' æ|| > R]] as follows:
Præ~s|| R = Praws
Σ (W7 > R²
Praws((WW xx)² R² /k]
S k sup Praws((W, x)²² R²² /k),
|
where the first inequality follows from union bound. Since (w, x)² is degree 2 polynomial, can view sign(( (w. x²)² I1²/k) as degree-2 PTF. The class of these functions has VC dimension most d2 (e.g. by viewing it the class of halfspaces in d2 dimensions). Using standard VC
df +loog(1//8) for some sufficiently large universal constant C > 0, (c"//
arguments, whenever Mirain 2 C.
with probability 2 1 8' we have
Pr s (w. x)²² > R²/R| < Pr Pr (,, R² + j//k.
Using the strictly subexponential tails of Da, we have
Pre-s||['>=l > R]]$ S
sup I(U,,, x2)² 2 R2 R2/R] c"
| |=1
(R(R/R)++)++ +
< exp
24 Choose e" (2kejt
Putting together:
Exss(p' {1 Pra-s [[ æ|| > R]] < (r + +) (2k0) +
S (r e)+ exp (el log(2k))) (R) t
We want to bound the first part with e4 Equivalently, ponent is S 4ln - Substituting l R Rlog R gr((), we get that of log(2kl) s cgr(e) 1222 (og((((2)g(()) Thus, it suffices to show that
need show that the ex-
R 1+7
2 R(( R)² (2kgx(e) 4 1hn d'
k
T+E
This is satisfied when 2 poly (k)g=()) log(r) log log(M/ Then, we have that
E E (p' (z)²
[| 20|| R]] - 22.
30

---

Published as a conference paper at ICLR 2025
So,
[c S
( 222
The same argument will also give
[|clar (x)) Popt (2) S 26'.
Putting everything together, we have
LD (cla + opt + 11 opt + 4e.
The result holds with probability at least 1 - 58' = 1 - (taking union bound over 5 bad events).
Completeness. For completeness, is sufficient ensure that mieett This is because when Dæ = D', our test samples S" are in fact being drawn from the subexponential distribution Dz Then the moment concentration of subexponential distributions (Lemma C.5) gives that the empirical moments of 5" are close to the moments of Dr, with probability 2 1 8'. This is the only condition for acceptance, so when D Dz, the probability of acceptance is at least 1 1-0, 6, required.
for N in Lemma C.S.
The runtime of the algorithm poly(d', Marain: Mtest), where = R log R gz(e). As noted above, the two lower bounds on R required in the proof are satisfied by setting R 2 (kgg(()) log(r) (e)
Runtime.
Note that the lower bounds we required for Marain in the proof are satisfied whenever Mirain = (M, In(1/5) 1/c, d', r). For Miest we required that Must 2 SM1 In(2/8') and also Meest 2 for in Lemma C.5. This is satisfied by choosing mhest =
Muriin Putting this altogether, we see that the runtime is poly(d", (n(1/5)5,1/4 where $ (kgg(())og(r)) (og(M))))))))
C.3 APPLICATIONS
We are now ready state our theorem for TDS learning neural networks with sigmoid activations. Theorem C.9 (TDS Learning for Nets with Sigmoid Activation and Strietly Subexponential Marginals). Let F on Red be the class of neural network with sigmoid activations, depth t and weight matrices W = (W11) ...., (()) such that [| S W. Let e (0, 1). Suppose the training and test distributions D, D' over IRd IR are such that the following are true:
1. Da is y-strictly subexponential.
2. The training and test labels are bounded in [-M, M) for some M 2 1.
Then, Algorithm learns the class F in the TDS regression up to excess error and proba- bility of failure 6. The time and sample complexity is at most pd" (dg')())))))))) where
(k log M (1 Wt-2). (t (1lo
Proof. From Theorem A.21, have that FF there is (c, R)-uniform approximation poly- O ((Rlog R) ([ " (tlo((W/))<-)). Here, let
nomial for f with degree (l)) We also have that r sup) [ [=()) S gr(c) = (I[W() (gr [Wt)) (1 poly [IAk||///\))/)>>>>>>>>> from the Lipschitzness of the sigmoid nets (Lemma A.18) and the fact that the sigmoid evaluated at has value The theorem now directly follows from Theo- rem C.7.
We now state our theorem on TDS learning neural networks with arbitrary Lipschitz activations.
Theorem C.10 (TDS Learning for Nets with Lipschitz Activation with strictly subexponential marginals). Let F on ddd be the class of neural network with L-Lipschitz activations, depth t and weight matrices W (W(1)... ..... W(O) such that [|W] < W. Let E (0, Suppose the training and test distributions D,D' over T&d x TR are such that the following are true:
1. Dr, is y-strictly subexponential,
31

---

Published as a conference paper at ICLR 2025
2. The training and test labels are bounded in [-M, M] for some M 2 1.
Then, Algorithm 2 learns the class F in the TDS regression up to excess ervor and proba- bility of failure 6. The time and sample complexity at most poly(d', log(1/8*) where 8 = (A MoloMM M [| (WL) O(
Proof. From Theorem A.19, we have that F there is (e, Runuforr approxima- tion polynomial for f with degree f = O ORkVE [W0 ( /e). Here, let (W
gz(e)
We also have that r S. lf()) I poly(Rk|) 1| from the Lipschitz constant (Lemmaa A. and the fact that the each individual activation has value most 1 when evaluated (see Definition A.12. The theorem now directly follows from Theorem C.7.
D ASSUMPTIONS ON THE LABELS
Our main theorems involve assumptions the labels of both the training and test distributions. Ideally, one would want to avoid any assumptions on the test distribution. However, we demonstrate that this is not possible, even when the training marginal and the training labels are bounded, and the test labels have bounded second moment. On the other hand, we show that obtaining algorithms that work for bounded labels sufficient even in the unbounded labels case, as long as some moment of the labels (strictly higher than the second moment) is bounded.
We begin with the lower bound, which we state for the class of linear functions, but would also hold for the class of single ReLU neurons, as well as other unbounded classes.
Proposition D.1 (Label Assumption Necessity). Let F be the class of linear functions over R& i.e., F {xc + w x w E Rdd |wll2 1}. Even if we assume that the training marginal is bounded within fx E Rd: |<]1|| S 1], that the training labels are bounded in [0, 11, and for the test labels we have EywD, 1y21 S Y where Y 0, no TDS regression algorithm with finite sample
complexity can achieve excess error less than Y/4 4 and probability of failure less than for F.
The proof is based on the observation that because we cannot make any assumption on the test marginal, the test distribution could take some very large value with very small probability, while still being consistent with some linear function. The training distribution, on the other hand, gives no information about the ground truth and is information theoretically indistinguishable from the constructed test distribution. Therefore, the tester must accept and its output will have large excess error. The bound on the second moment of the labels does imply bound on excess error, but this bound cannot be made arbitrarily small by drawing more samples.
Proof of Proposition D.I. Suppose, for contradiction that we have TDS regression algorithm for F with excess error e < Y/4 and probability of failure ō < 1/4, Let m E be the sample complexity of the algorithm and p E (0, 1) such that m < 1/p. We consider three distributions over Rd x IR. First D(I) outputs (0, 0) with probability 1. Second, D)2) outputs (0, 0) with probability - p and ( vY with probability p. for some w E Rd with / = 1. Third, D(3) outputs (0, 0) with vp
VP w,
probability 1 1 p and
w. 0) with probability +p
We consider two instances of the TDS regression problem. The first instance corresponds the case D D(1)) and D' D(2), The second corresponds the case D D(1) and D' D(3) Note that the assumptions we asserted regarding the test distribution and the test labels are true for both instances. For D(2), in particular, we have TE g. [u²] = =p- (vV/ vp)² = Y. Moreover, in each of the cases, there is hypothesis in F that is consistent with all of the examples (either the hypothesis x + 0 or Ø
+ w xt), so opt == miinfe((CD(]] = 0 = minnrerlCo( + LD (J') =:) X.
Note that the total variation distance between ( and D22) is p and similarly between D(1) and D(3), Therefore, by the completeness criterion, as well as the fact that sampling only increases total variation distance at linear rate, i.e., div @m (D))@m) & d.d (D,D') m p. have that
D')
32

---

Published as a conference paper at ICLR 2025
in each of the two instances, the algorithm will accept with probability at least 1 - m mpp- 8 (due to the definition of total variation distance'). )
Suppose that the algorithm accepts in both instances (which happens w.p. at least 1 - 20 2mp).
By the soundness criterion, with overall probability at least 1 - 46 - 2mp, we have the following.
p (h(x) - 0)2 < X/4
p. (h(z) /
The inequalities above cannot be satisfied simultaneously, so we have arrived to contradiction. only remains to argue that - 45 - 2mp > O, which is true if we choose < a TDS regression algorithm cannot exist.
1-48 Therefore, such 2m
The lower bound of Proposition D.1 demonstrates that, in the worst case, the best possible excess error scales with the second moment of the distribution of the test labels. In contrast, we show that a bound on any strictly higher moment is sufficient.
Corollary D.2. Suppose that for any M > O, we have an algorithm that learns a class F in the TDS setting up to excess error E (0, 1), assuning that both the training and test labels are bounded in [-M, M). Let ( and m(M) be the corresponding time and sample complexity upper bounds.
Then, in the same setting, there is algorithm that learns F up to excess error 4e under the relaxed assumption that for both training and test labels we have Ely")((ui)) < Y for some Y >> O and g some strictly increasing, positive-valuce and unbounded function. The corresponding time and sample complexity upper bounds are T(g (V/(2) and mlg (V/e2))
The proof is based the observation that the effect of clipping the labels, measured by the squared loss, can be controlled by drawing enough samples, whenever moment that is strietly higher than the second moment is bounded.
Lemma D.3. Let Y > O and g (0, oc) - (0, oo) be strictly increasing and surjective. Let y be random variable over I such that [(yl) Y. Then, for any (0,1), if M 2 g (Y/e),
we have (y ( S.
Proof of Lemma D.3. We have that E[(y- Elay-clas (v))² < 15y3 > M MJ. because y 2 cl and
y, cl (1) always have the same sign, so (y (yy-clan clas (z))² 2 y² and also (3 (y = 0f w/ S M.
Since g(lyl) is non-zero whenever y > 0, we have 21 {lyl > M]] = Ely² a(pl)
g(le (( M]]-
We now use the fact that g is increasing to conclude that Efy² L { M) S Bly ailil < Y
((M)
g(M)
By choosing M 2 g (Y/e2) we obtain the desired bound.
We are now ready to prove Corollary D.2, by reducing TDS learning with moment-bounded labels to TDS learning with bounded labels.
Proof of Corollary D.2. The idea is to reduce the problem under the relaxed label assumptions to a corresponding bounded-label problem for M - 9 "YY/e)). In particular, consider new training distribution cly o D and a new test distribution Cl D', where the samples are formed by drawing a sample (x, y) from the corresponding original distribution and clipping the label y to cl (v). Note that whenever we have access to i..dd examples from D, we also have access to i...d examples from M o and similarly for (D', cl oD2))) Therefore, we may solve the corresponding TDS problem for cl a 'D and cl o DD' to either reject or obtain some hypothesis h such that
D (h) S minn[Claro + min min!ColssD((") + Low (f')) + FET
P'E
Our algorithm either rejects when the algorithm for the bounded labels case rejects or accepts and outputs h. It suffices to show (h) I minser(Co(()) + (Co(") LD (f')) 4c, because the marginal distributions do not change and completeness is, therefore, satisfied directly.
We know that the algorithm would accept with probability at least - 5 if the set of test examples was drawn from (Da) Sm Since (D', )8m is (mp))-lose to (Da) )m no algorithm can have different behavior if Hence, any algorithm must accept with
we substitute (Da) j0m with (D', (D=)@m @m except with prohability probability at least m p- 8.
33

---

Published as a conference paper at ICLR 2025
It suffices to show that for any distribution D, have (h) L (h) s c. To this end, note that D (CC We have the following.
(1) - v ([ch))))((cl)()) - 1(x)))
((ca))-((( + h((=)))
$ / ((aw))D((dar()) u) + BB h(x)))²
s Lphh)
The first inequality follows from an application of the triangle inequality for the -oon and the second inequality follows from Lemma D.3. The other side follows analogously.
L
34


Reviews:
[{"review_id": "EcHLrcXl1W", "reviewer": "Reviewer_ovXB", "summary": "This paper studies distribution shift for nonconvex regression using the recently introduced Testable Learning with Distribution Shift framework (TDS) (Klivans et al.’24). The setup is as follows. A TDS  learner observe iid labeled training data from train distribution $D$, along with *unlabeled* iid test data from some other test distribution $D’$. Then, the learner can decide to abstain from predicting on the test data. If it chooses to not abstain, it must produce a hypothesis $h \\in \\mathcal{F}$ generalize on the test data, where generalization is defined with respect to some function class $\\mathcal{F}$. \n\nThe paper designs efficient TDS algorithms under a bounded label assumption (although this is slightly relaxed in the appendix) and sufficiently nice *training* marginals (bounded and hypercontractive or strictly subexponential), when the function class is a Lipschitz neural network. Notably, the paper makes no assumption about the test marginal. The efficient algorithms are based on kernel methods.", "questions": "1. Can the authors comment a bit on when it would be realistic to have access to unlabeled test examples? I know that it is a standard setup for domain adaptation, but it would be good to have some discussion on it\n2. The statement of Lemma A.17 seems unfinished.  \n3. It seems that one needs to prove uniform convergence for the function classes used for the TDS algorithm to work. Are there any situations where we might expect to be able to surpass this barrier, as uniform convergence is quite a strong assumption \n4. Line 330, 333, should $\\overline{S}_{\\mathrm{ref}}$ have no overline?\n5. If I have multiple test time distributions, it seems that a naive extension of the current algorithm would need to retrain my TDS learner for each test distribution? Might there be a way to design an algorithm which can be amortized over multiple different test time distributions?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper comes up with a generic TDS framework using kernel methods, and then verifying the assumptions for a number of concrete examples. Previous algorithms in these testable settings relied on moment-based algorithms and various notions of polynomial approximation. \n2. The paper discusses the numerous assumptions on the marginals / label distributions quite extensively. There is also a matching lower bound in the appendix that shows that some assumptions on the test labels are needed. \n3. The algorithm itself is quite interesting, as it certifies a valid comparison between the training and test marginals via the spectral tester; this latter tester only works under the hypercontractivity assumption. \n4. The results in Section 4 also handle the unbounded setting, by using a moment-based testable learner using polynomial regression instead, building on the previous TDS results of Klivans et al.’24. \n5. The paper is well written, and gives substantial intuitions about how the proof works.", "weaknesses": "1. Although I appreciated that the paper does not make assumptions on the test marginal, it feels like this point is a little misleading, since the whole point of the tester is to certify the niceness of the test marginal. I can definitely agree that it is better to have a provable verifier that ensures your learner works on distribution than not, though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ePcazIxGbg", "reviewer": "Reviewer_pjxs", "summary": "This paper considers the Testable Learning with Distribution Shift (TDS) framework for learning neural networks under bounded or subgaussian inputs. In the TDS framework, the learner recieves m samples $(x_i, f^*(x_i) + \\text{guassian noise})$ from some known covariate distribution $D_x$, and then $m$ unlableled test samples from an **unknown and arbitrary** covariate distribution $D'_x$. If $D'_x = D_x$, then the learner must output labels for the test samples, and is evaluated on the $\\ell_2$ loss. If $D'_x$ is not $D_x$, then the learner can abstain. \n\nThe authors main technical result (Theorem 3.6) shows that if\n   1. The covariates and the labels are bounded and\n   2. the function class $\\mathcal{F}$ is well approximated by some kernel K and \n   3. The distribution $D_x$ is *hypercontractive* with respect to K, \n\nthen learning in the TDS framework is possible to $\\epsilon^2$ mean squared error with polynomial in in the input dimension $d$ and $1/\\epsilon$. A similar result (under stronger assumptions) is shown for unbounded covariates.\n\nThis is then applied to TDS for neural networks with bounded data, yielding an algorithm which runs in time polynomial in $d$ for sigmoid nets, 1-Lipshitz nets, and single ReLU units. Similar results are obtained for unbouned covariates, but the dependence is now exponential int the number of hidden neurons. \n\nThe result is proved using standard kernel regression techniques, with some adaptation for the TDS setting: (1) the algorithm rejects if the data is unbounded and (2) The algorithm uses a spectral testor to if the empirical covariance of the kernel matrix is significantly different from the samples from $D'_x$. \n\nThe authors prove the applications for neural networks by showing how too approximating $f^*$ (with a uniform bound on the domain) by a function in the the RKHS given by a low-dimensional polynomial kernel.", "questions": "See weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The TDS setting is an exciting area, and this paper extends to the TDS toolbox --- which had previously only been studies in classification settings or linear regression settings --- to the kernel regression setting, for both bounded and unbounded distributions. For unbounded distribution, this requires a novel analysis to control the approximation error on the tails of the distribution. In the bounded distribution setting, the main insight to get the results for NNs seems to be using uniform function approximations by polynomials (which is possible for neural nets with low degree polynomials!), as opposed to \"sandwitching\" approximations which were priorly used for TDS.", "weaknesses": "The application to neural networks does not seem to contribute much to our understanding of NNs, because it seems the main novelty is proving the specific assumptions relating to hypercontractivity, which I do not know how useful they are outside of this TDS setting. Further, the bounded distribution assumption is quite strong.\n\nThe paper could be more clear in many place:\n- Pointing out where the technical novelty and main challenges are in the algorithm/analysis \n  - For example, for bounded distributions, the Algorithm seems quite standard aside from the spectral test for the TDS part, which seems like a straightforward idea. Could the authors clarify what are the main technical challenges overcome here?\n - There is nowhere in the main body of the paper explaining what new approximation theory ideas are needed for the NN applications. Are there any potential uses for the new approximation techniques outside of this paper?\n- The authors should explain at the beginning of \"our techniques\" that they intend to approximate NNs by a low-dimensional polynomial kernel, as per other cited works. This was confusing at first to understand why the text was talking about kernels without the connection to NNs made explicit. \n- Where in Algorithm 1 is the part about finding a concise reference feature map?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "40Tg07SCEg", "reviewer": "Reviewer_MWC1", "summary": "This paper presents two TDS learning algorithms for regression problems. The first algorithm integrates kernel methods into the TDS framework, achieving fully polynomial runtime for bounded and hypercontractive training distributions. For unbounded distributions (strictly subexponential distribution), the second algorithm utilizes the moment-matching testing and the uniform approximation approaches. The results apply to classes of Lipschitz neural networks.", "questions": "Is it feasible to conduct experiments and create plots to validate the theorems?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, and the results are clearly presented and demonstrated. It introduces a novel TDS learning algorithm that leverages kernel methods for regression problems, which are different from the classification setting that has been discussed in the literature.", "weaknesses": "There is a lack of experimental results supporting the validity of Theorem 3.6 and Theorem 4.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GF3fGyGuhO", "reviewer": "Reviewer_iuF7", "summary": "This work considers the Testable Learning with Distribution Shift (TDS) framework.\n\nIn TDS, the training and test time distributions can be different, and the learner receives labeled training examples as well as unlabeled test examples. The learner can either declare success—-in which case it must satisfy PAC-like guarantees—or it can declare failure if it detects too large a distribution shift, but this detection must be reliable.\n\nWhile all previous works studied TDS in the classification setting, this work is concerned with TDS for (non-convex) regression. The authors present a general-purpose polynomial time TDS learning algorithm with theoretical performance guarantees.\n\nThe results imply TDS learnability for neural networks, under mild assumptions on the network activations, as well as a hypercontractivity assumption on the training distribution. This setting allows for the use of kernel methods and thereby essentially reduces the learning task to convex agnostic learning over polynomials.", "questions": "- Which steps in the analysis do you believe to be particularly loose (or sharp), and what do you believe are the general limitations of a kernel-based analysis? Perhaps you could provide me with 1-2 key steps you believe to be most ripe for improvement in future work.\n- In Def. 1.1, the completeness condition seems rather lax at first glance. I suspect that items 1 and 2 together imply that the algorithm must accept also in cases where $D_x$ is very close to, but not necessarily equal to, $D’_x$. Is this correct?\n- In domain adaption, why is it standard to consider the training error part of the performance criterion? Intuitively, one might only care about the test error. Even if one does care about training error, why not consider a weighted combination of training and test error?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Extending the TDS framework to regression is an important contribution. As such, this paper is valuable for the broader statistical learning theory community.\n- The tools employed for the proofs are technically non-trivial and could be valuable in their own right for future research in TDS. For example, the coupling of the training and test distribution is achieved through the use of data-dependent feature maps imported from the kernel framework. Additionally, the full analysis combines tools from polynomial approximation theory, hypercontractive concentration, and spectral concentration.\n- The overall writing style is excellent, and the literature review seems to be thorough (though I am admittedly not familiar with the TDS line of work).", "weaknesses": "- Poor scaling of computation complexity:\nWhile the runtime, as claimed, is polynomial in most of the parameters, it is exponential in $1/\\epsilon$ for ReLU neurons and Lipschitz nets. For deep nets, the scaling is doubly exponential in the depth, and in most cases exponential in the width of the first hidden layer.\nEven for the parameters that do scale polynomially, the exponents are very large and most likely quite far from being optimal. For example, for general function classes, even if one naively assumes $A,B,C,l$ all to be constant, the runtime of Algorithm 1 scales at least as $\\Omega(1/\\epsilon^{16})$ from constructing the matrices $\\hat{\\Phi}, \\hat{\\Phi’}$ for the spectral tester, which requires $\\sim m\\cdot N$ kernel evaluations.\n\n- Very large sample complexity:\nAlgorithm 1 requires $m+N$ i.i.d. samples from both $D$ and $D’$, which for Lipschitz nets is doubly exponential in the depth, and exponential in $1/\\epsilon$ and the width of the first hidden layer. Again, even if $A,B,C,l$ are all assumed to be constant, the sample complexity scales at least as $\\Omega(1/\\epsilon^{12})$ since the sample complexity is dominated by the size of the verification samples.\n\nIn the light of the above, the results have more of a proof-of-concept flavour, rather than providing a practically applicable algorithm. I suspect that Algorithm 1 cannot be ran in practise even for very small dimensions and parameter scales.\n\nI want to make clear that I do not consider the above major weaknesses—theoretical results for complex learning settings are often difficult to obtain, and finding efficient, general purpose algorithms can take many years of research, or may not necessarily be possible in the first place, even with the best available mathematical tools.\n\nI think that the paper would benefit from a short discussion regarding the limitations, especially regarding:\n- Sample complexity (see above). Sample complexity is currently not discussed at all. I understand that this work is mostly concerned with runtime, but sample complexity should still not be completely left out of the picture in my opinion. Perhaps you could add a column in Table 1 that contains the sample complexities.\n- I would suggest to mention at least once explicitly that, generally, rather large exponents are obtained for both computational and sample complexity. This limitation should be obvious to the reader even from a cursory read. It takes some effort to puzzle together the scaling exponents from Algorithm 1 and Table 2 due to the multitude of parameters involved. I suggest adding a short discussion of these limitations at the end of Section 1.1, or in a new Conclusion/Limitations section at the end of the paper.\n- This is optional, but perhaps you could also highlight which steps in the analysis you believe to be particularly loose (or sharp), and what you believe the general limitations of the kernel-based approach to be. Such a discussion would make it easier for the reader to gauge the current state of this line of work, and what the major technical roadblocks are.\n\nNote that in this iteration of ICLR, 10 pages are available, so space should not be an issue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)