Efficient Discrepancy Testing for Learning with Distribution Shift
Authors: Gautam Chandrasekaran
Adam Klivans
Vasilis Kontonis
Konstantinos Stavropoulos
Arsen Vasilyan
Venue: NeurIPS 2024 poster (2024)
Keywords: pac learning
testable learning
distribution shift
distribution testing
discrepancy distance
Primary area: learning_theory

Abstract: A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. While in general hard to compute, here we provide the first set of provably efficient algorithms for testing *localized* discrepancy distance, where discrepancy is computed with respect to a fixed output classifier.  These results imply a broad set of new, efficient learning algorithms in the recently introduced model of Testable Learning with Distribution Shift (TDS learning) due to Klivans et al. (2023).

Our approach generalizes and improves all prior work on TDS learning: (1) we obtain *universal* learners that succeed simultaneously for large classes of test distributions, (2) achieve near-optimal error rates, and (3) give exponential improvements for constant depth circuits. Our methods further extend to semi-parametric settings and imply the first positive results for low-dimensional convex sets. Additionally, we separate learning and testing phases and obtain algorithms that run in fully polynomial time at test time.

Efficient Discrepancy Testing for Learning with Distribution Shift
Gautam Chandrasekaran' UT Austin
Adam R. Klivans UT Austin
Vasilis Kontonis UT Austin
Konstantinos Stavropoulos
Arsen Vasilyan*
UT Austin
UC Berkeley
Abstract
A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. While in general hard to compute, here we provide the first of provably efficient algorithms for testing localized discrepancy distance, where discrepancy is computed with respect to a fixed output classifier. These results imply broad set of new, efficient learning algorithms in the recently introduced model of Testable Learning with Distribution Shift (TDS learning) due to Klivans et (2023).
Our approach generalizes and improves all prior work on TDS learning: (1) obtain universal learners that succeed simultancously for large classes of test distributions, (2) achieve near-optimal error rates, and (3) give exponential improvements for constant depth circuits. Our methods further extend to semi- parametric settings and imply the first positive results for fow-dimensional convex sets. Additionally, separate learning and testing phases and obtain algorithms that run in fully polynomial time at test time.
Introduction
Distribution shift remains a central challenge in machine learning. While practitioners may exert some level of control over model's training distribution, they have far less insight into future, potentially adversarial, test distributions. Developing algorithms that can predict whether a trained classifier will perform well modern foundation models.
unseen test set is therefore critical the widescale deployment of
A heavily-studied framework for modeling distribution shift is domain adaptation, where a learner has access to labeled examples from some training distribution, unlabeled examples from some test distribution and is asked to output a hypothesis with low error the test distribution. Over
ggautamcCcs... wwwpe/ccccsu.eee..ccce utexas. edu. Supported by the NSF AI Institute for Foundations of Machine Learning (IFML).
'klivnnsccs. utw.as.eee....mmm..... edu. Supported by NSF award AF-1909204 the NSF Institute Founda-
tions of Machine Learning (IFML).
fassiliscss. utexas.e..... edu. Supported the NSF Al Institute for Foundations of Machine Learning (IFML).
'kstavrop&cs utexas. edu. Supported by the NSF AI Institute for Foundations of Machine Learning (IFLL) and by scholarships from Bodossaki Foundation and Leventis Foundation.
larsenvasilyandgaail com. Supported in part by NSF awards CCF-2006664, DMS-2022448, CCF. 1565235, CCF-1955217. CCF-2310818, Big George Fellowship and Fintech @ visiting UT Austin. Part of this work conducted while the author visiting the Simons Institute for the Theory of Computing.
CSAIL. FintechCCSAIL.
Work done in part while
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the last twenty years, researchers in domain adaptation and related fields [BDBCP06, 07, MMR09, BDBC* 10, RMH ZLWJ20, KM21b, HKM23, KZZ24] have established bounds for out-of-distribution generalization in terms of some type of distance between train and test distributions. By far the most commonly studied notion is discrepancy distance:
disce (D, = sup P [)(((( [2(x)) P X-D (((()) + [2(x)] #2(x))
fI.JEC X
Estimating or even testing discrepancy distance, however, seems difficult, as its definition involves an enumeration over all classifiers from some underlying function class (in Appendix F we give the first hardness result for computing discrepancy distance in general). As such, obtaining provably efficient algorithms for domain adaptation has seen little progress (none of the above works give polynomial-tine guarantees).
In search of efficient algorithms for learning with distribution shift with certifiable error guarantees, recent work by [KSV24b] defined the Testable Learning with Distribution Shift (TDS learning) framework. In this model (similar to domain adaptation), a learner receives labeled examples from train distribution D, unlabeled examples from test distribution D', and then runs a test. the (efficiently computable) test accepts, the learner outputs h that is guaranteed to have low test error with respect to D'. No guarantees are given if the test rejects, but it must accept (with high probability) if the marginals of D and D' are equal. This framework has led to the first provably efficient algorithms for learning with distribution shift for certain concept classes (for example, halfspaces) [KSV24b, KSV24a].
straightforward to see that if algorithm A learns concept class in the (ordinary) PAC/agnostic model, and we have an efficient localized discrepancy tester for C, then C' is learnable in the TDS framework: simply apply the discrepancy tester to the output of A and accept if this quantity is small. A dream scenario would be to augment all known PAC/agnostic learning algorithms with associated localized discrepancy testers. This nontrivial in part because we cannot make any assumptions on the test distribution D' (our test has to always accept reject correctly). Nevertheless, our main contribution is suite of new discrepancy testers for well-studied function class/training distribution pairs that unifies and greatly expands all prior work on TDS learning.
1.1 Our Contributions
Optimal Error Guarantees via La Sandwiching. The work of [KSV24b] followed moment- matching approach to show that the existence of L2 sandwiching polynomial approximators implies TDS learning up a constant factor of the optimum error. Although their result implies TDS learning for several fundamental concept classes, the L2 sandwiching requirement seems restrictive for classes such as constant-depth circuits or polynomial threshold functions. In Theorem 3.1, we provide TDS learning results in terms of the much more well-understood notion of C1 sandwiching, resolving one of the main questions left open [KSV24b] As such, we obtain exponential improvements for TDS learning constant depth circuits (AC"), and the first results for degree-2 polynomial threshold functions (see Table 1). Our result also bridges a gap between TDS learning and testable agnostic learning [RV23], since the latter has been known to be implied by L1 sandwiching [GKK23]. Additionally, in the agnostic setting, the error guarantees we achieve are essentially optimal (as opposed to the constant-factor approximation by [KSV24b]).
Universal TDS Learners. A natural and important goal in TDS learning is to design algorithms that accept and make trustworthy predictions whenever the distribution shift is benign. In Theorems 4.2 and 5. we give the first TDS learners that are guaranteed to accept whenever the test marginal falls in a wide class of distributions that are not necessarily close to the training distribution (in say statistical distance) but, instead, share some mild structural properties. In the literature of testable agnostic learning, testers with relaxed completeness criteria are called universal [GKSV23]. Our universal TDS learners accept all distributions that are sufficiently concentrated and mnteeconcentrated and work for convex sets with low intrinsic dimension (Theorem 4.2) and halfspace intersections (Theorem 5.1). Surprisingly, our algorithms can handle distributions that are heavy-tailed and multimodal, for which efficient (ordinary) agnostic learning algorithms are not known to exist. Our algorithms exploit localization guarantees from the training phase (e.g., subspace or boundary recovery) to relax the requirements of the testing phase.

---

Fully Polynomial- Time Testing. All of the TDS learners we provide consist of two decoupled phases. In the training phase, the algorithm uses labeled training examples to output a candidate hypothesis h. The testing phase receives the candidate h and uses unlabeled test examples to decide whether to reject or accept and output h. Separation of the two phases is an important feature of our approach, as it may be desirable for these tasks to be performed by distinct parties who have different amounts of available (computing) resources. Efficient implementations of the testing phase are of utmost importance, especially for potential users of large pre-trained models who need to certify that the candidate model at hand is safe to deploy. In Theorem 5.1, we give the first TDS learner for intersections of halfspaces that runs in fully polynomial test time, and additionally improves the overall runtime of the previous state-of-the art TDS learner for intersection of halfspaces by [KSV24a]. In fact, our TDS learner' overall runtime is polynomial in the dimension d, while the time complexity of the TDS learner given by [KSV24a] involved factor of d (logg((/))) where is the error parameter.
1.2 Our Techniques
Our approach for designing TDS learners focuses on efficient algorithms for testing a new notion of localized discrepancy distance:
Definition 1.1 (Localized Discrepancy). Let 'D be a distribution over X' C Rd and let H. C C (+1)* be hypothesis and concept classes respectively. Define neighborhood N to be a function N + 2c. For f E H. the (f, -localizd discrepancy from D to D' is defined as:
(D, = sup ( IP SEN(f) (2 # f(x)] IP [P] + f(x)))
Testing localized discrepancy is clearly easier than testing the traditional (global) discrepancy distance, since global discrepancy is defined with respect a supremum over all pairs of concepts within some given class, while localized discrepancy only depends on a small neighborhood of concepts around some given reference classifier f.
Assume for moment that we have fixed neighborhood function N and have obtained learner that always outputs a classifier close to the ground truth function f" (i.e., I E N()). In this case, if we can test localized discrepancy, then we obtain a TDS learner as follows: output f if the corresponding localized discrepancy is small and reject otherwise (recall î is close to the ground truth for both training and test distributions).
The algorithmic challenge is finding definition of neighborhood that admits both an efficient learner (for outputting& classifier close to the ground truth) and an efficient localized discrepancy tester. Smaller neighborhoods make the learning problem more difficult while larger neighborhoods make discrepancy testing more challenging.
Ultimately, the appropriate localized discrepancy relaxation of the testing phase depends on the guarantees can ensure during training, which, in turn, depends on the properties of the concept class C and the training distribution. For our main applications below we briefly describe the choice of neighborhood and the corresponding discrepancy tester. Note that give a different discrepancy tester for each of the following cases.
Classes with Low-Degres Sandwiching Approximators. We show that the existence of degree- C Ci-sandwiching approximators for class over X' C Rd turns out to be sufficient to design a localized discrepancy tester that runs in time d0(() where the notion of neighborhood is widest possible, i.c., N() = C. In this case, the requirement for the training algorithm is minimal, as the ground truth f lies within C, which coincides with N(f). The proposed tester is based on estimating the chow parameters of the reference hypothesis ff under the test marginal and checking whether they closely match the chow parameters of under the training marginal. For more details, see Section 3.
Convex Sets with Low Intrinsic Dimension. For convex sets with few relevant dimensions, there algorithms from standard PAC learning that guarantee approximate recovery of the relevant subspace. This guarantee allows one to choose a much stronger notion of neighborhood while
'The discrepancy is still localized, since is defined with respect to reference hypothesis f.
3

---

still ensuring that f E N()). The appropriate notion of neighborhood contains low- -iw-dmmensionll concepts whose relevant subspace is geometrically close the subspace of the reference hypothesis. The corresponding tester exhaustively checks that the marginal 'D' is well-behaved on the relevant subspace. For more details, see Section 4.
Intersections of Halfspaces. For intersections of halfspaces, we prove a structural result stating that finding a hypothesis with low Gaussian disagreement with the ground truth f implies approximate pointwise recovery of the boundary of f* It is therefore sufficient to check whether the marginal of the test distribution assigns unreasonably large mass near the boundary of the training output hypothesis f. which can be done in fully polynomial time. Any proper algorithm for learning halfspace intersections under Gaussian training marginals is then sufficient for our purposes. For more details, see Section 5.
1.3 Related Work
Domain Adaptation. In the past two decades, there has been a long line of research on generalization bounds for domain adaptation. The work of [MMR09] introduced the notion of discrepancy distance, following work by [BDBCP06, BDBC* 10), which used similar notions of distance between distri- butions. Other important notions of distribution similarity include bounded density ratios [SSK]] 12] and related notions [KM21b, KZZ24]. A type of localized discrepancy distance was defined by [ZLWJ20] and used to provide improved sample complexity bounds for domain adaptation. None of the above works give efficient (polynomial-tme) algorithms. Here, we give a more general notion of localization and use it to obtain efficient and universal algorithms for TDS learning.
TDS Learning and Related Models. The framework of TDS learning was defined by [KSV24b], where it was shown that any class that admits degree- Cy-sandwiching approximators can be TDS learned in time d((()) up to error O()), where À is the standard (and necessary) benchmark for the error in domain adaptation when the training and test distributions are allowed to be arbitrary. Here, we show that the relaxed notion of L ---sandwihhing approximators suffices for TDS learning and we improve the error guarantee to nearly-match the information theoretically optimal À (see Section 3). For intersections of halfspaacss under Gaussian training marginals, [KSV24a] gave TDS learners with improved guarantees compared to those given by [KSV24b] through L2 sandwiching. Our TDS learners for halfspace intersections are superior to the ones from [KSV24a] in terms of overall runtime, universality and test-time efficiency (see Section 5).
Another related framework for learning with distribution shift is PQ learning, which was defined by [GKKM20]. In PQ learning, the learner may reject regions of the domain where it is not confident to make predictions, but the total mass of these regions under the training distribution must be small. In fact, PQ learning is known to imply TDS learning (see [KSV24b]). However, the only known algorithms for PQ learning, which were given by [GKKM20, KK21], require access to oracles for learning primitives that are known to be hard even for simple classes (see [KK21]).
The framework of TDS learning is also related to testable agnostic learning, where the goal of the tester is certify near-optimal error guarantee. Testable agnostic learning was defined by [RV23] and there are several subsequent works in this framework [GKK23, GKSV24, GKSV23, +3K+ 23]. There are many important differences between TDS learning and testable agnostic learning, including the fact that, in testable agnostic learning, there is no distribution shift and that in TDS learning, the learner does not have access to labels from the distribution on which it evaluated. In particular, testable agnostic learning is only defined in the presence of noise in the labels, while TDS learning is meaningful even when the labels are generated noise-free (i.c., realizable learning).
PAC Learning. In the standard framework of PAC learning, there is an abundance of algorithmic ideas and techniques that aim achieve efficient learning, under various assumptions (see e.g., [LW94, BK97, KOS04, KLT09, KOSO8a, Vem 10b, Vem 10, GKM12, KKM13, DKS18a, DTK221)). In this work, we make use of polynomial regression [KKMS08], dimension reduction techniques [Vem10at as well as techniques for robustly learning geometric concepts [DKS in order to obtain efficient TDS learners. In fact, our approach of designing TDS learning algorithms through localized discrepancy testing sheds light on what kinds of guarantees from the training algorithms are desirable for learning in the presence of distribution shift. For example, we show that if approximate subspace recovery is guaranteed after training, then the discrepancy testing problem can be relaxed to

---

an easier, localized version. Moreover, our results on TDS learning halfspace intersections emphasize the importance of proper learners in the context of learning with distribution shift.
2 Preliminaries
We use standard big-O notation (and Ô to hide poly-logarithmic factors), R' is the d-dimensional euclidean space and Nu the standard Gaussian over TR. [=1]² is the d-dimensional hypercube and ( the uniform distribution over { N is the set of natural numbers N = {1, 2.... and x E IR denotes a vector with x = (x1...., x2) and inner products x v. See also Appendix A.
Localized Discrepancy Testing, Testing localized discrepancy (Definition 1.1) is defined as follows.
Definition 2.1 (Testing Localized Discrepancy). For set ID of distributions and DD over X' and > 0, we say that T is a (N, et-tstter for localized discrepancy from D with respect to DD if. T, upon receiving f E H and a set X of my i.i.d. examples from some distribution D' over X' satisfies:
(a) (Soundness.) With probability at least 3/4: If T accepts, then disc (D,D) S.
(b) (Completeness.) D' D, then T accepts with probability at least 3/4.
For a concept class C, a distribution D over X, e E (0, 1), we say that C has e-L, sandwiching degree é with respect to D if for any / E C, there exist polynomials Pups Pdoonn over X' with degree at most & such that (1) Pdown (x) S [(x S (x) for all x E X' and (2) ExpD ExwD(Pup (x) Pdoowl [x)] S 6.
Learning Setting. For X' C IRd the learner is given labeled samples from a training distribution Dirsin over X x } with X --marginaa Dirain = D and unlabeled examples from the marginal Diest of test distribution Diegt over X' x {+1}. For a concept class C S {X - {+1)). in the realizable setting, there is f E C that generates the labels for both x' and Diest. In the agnostic setting, the standard goal in domain adaptation is to achieve an error guarantee that is competitive with the information-theorttialll theoretically optimal joint error À = fec (crr(f: Dirain) ) crr(f; xoy) )), achieved by some f C, where err(f: (ff: "x IP (x.)) ly + f(x)] (and similarly for err (f: D )).
Definition 2.2 (Universal TDS Learning). Let C be a concept class over X S RRd, D a distribution over X and D some class of distributions over X. The algorithm A is said to D-universally TDS learn with respect to up to error & and probability of failure ö if, upon receiving Mitrai labeled samples from a training distribution Durain with X-marginal D and Meest. unlabeled samples from test distribution Diest, w.p. at least 5, algorithm A either rejects, accepts and outputs hypothesis h X [=1] such that:
(a) (Soundness.) If A accepts, then the output h satisfies err(h; Xxy) tb.
(b) (Completeness.) If Di E D then A accepts.
In the agnostic setting, parameter y may depend on À X(C; Dirain Diest), whereas in the realizable setting, 1/2 = e (0, 1). If TD = (D), then we simply say that A T-TDS learns w.r.t. D.
Note that the success probability for TDS learning can be amplified through repetition [KSV24b] and we will consider = 0.1 unless specified otherwise.
3 Classes with Low Sandwiching Degree
Prior work on TDS learning by [KSV24b] showed that the existence of degree-E Cz-sandwiching approximators implies TDS learning time do(e), A major question left open was whether the more traditional notion of L1 sandwiching (see Definition C. suffices for TDS learning. We answer this question in the affirmative, and as a consequence we obtain exponential improvements in the runtime of TDS learning for constant depth circuits (AC") and the first TDS learning results for degree-2 polynomial threshold functions (see Table 1). For more details, see Appendix C.
Theorem 3.1 (Li sandwichinn implies TDS learning). Let e, 8 E (0, 1) and lei C C (X {+1)} be concept class such that the e-approximate L sandwiiicii degree of C under D is E(e) e N.
5

---

Then, there exists TDS learning algorithm for C with respect to D up to ervor X + opt + O(e) and with probability at most ó with time and sample complexity poly(d 1 log(1/)).
Note that prior work [KSV24b] had only obtained bound of (()) in the above error guarantee. Our techniques allow us to achieve the optimal dependence of simply X.
Concept class
Training Marginal
Time
Prior Work
1
D PTFs PTFF
Na or Uni
d01/e)
None
2 Circuits of size depth t
Unif((=1}9)
(0oo(s/1))000
dv dV-oOllgee/e))
only for formulas
Table I: New results for TDS learning through Li sandwiching. For constant-depth formulas, we achieve exponential improvement compared to [KSV24b] (which used C2 (y-sandwiching), and our results work for circuits as well.
For Gaussian and uniform halfspaces, intersections and functions of halfspaces, as well as for decision trees over the uniform distribution, the L2-sandwiching approach of [KSV24b] provided TDS learning algorithms with similar runtime as the one obtained here, but their error guarantee was O(A) + e instead of À + opt + e (where optn = min rec err Dtrain)) )), which is the best known upper bound on the error, even information theoretically (see [BDBC* 10, DLLPIOJ).
Localized discrepancy testing via Chow matching. The improvements we obtain here are based on the idea of substituting the moment-matching matching tester of [KSV24b] with a more localized test, depending on a candidate output hypothesis f provided by a training algorithm run on samples from the training distribution. In particular, we estimate the Chow parameters [OS08] Ex-Dien [x(x)x
for all low-degree monomials x² = II x and reject if they do not match the corresponding quantities Ex~DIf (x)x under the training marginal. We obtain the following result.
Proposition 3.2 (Informal, see Theorem C.3). For any class C with low sandwiching degree under D, the low-de chow matching tester is tester for localized discrepancy for the neighborhood
N(F) = C. i.e. it certifies that Fx~Dy= [f(x # f(x)) S Px~Dlf(x # f(x)] + e all f C.
Proof Outline. The main observation for obtaining the localized discrepancy testing result is that the disagreement between two functions is a linear function of their correlation, i.c., 2 PP Die by two polynomials Pup: Pdown- which implies Ex-Dy= [x)) 2 (f
[(x)) + f(x)] = 1 -x [x)), and, because f E C, it is sandwiched
Ex~DxT (Pupp())) - (x))w(x)]. The latter quantity can be certified to be close to the corresponding quantity under the training marginal D by Chow (and moment) matching.
Although the notion of neighborhood we require here is quite generic, it is sufficient to provide significant improvements over prior work. The discrepancy tester is localized in the sense that it certifies properties of the tested marginal distribution that are related to particular candidate hypothesis f. but actually considers the whole concept class C to be inside the neighborhood of f. Since the concept l" that achieves À = min/ec (err(f D Daggit) + err(J; )) lies within by definition, the total test error of f is directly related to the error achieved by the training algorithm, whenever the Chow matching tester accepts.
Non-Parametric Low-Dimensional Classes
For non- non-parametric classes like convex sets over R& dimensiin-eefficiet TDS learning is impossible, even from an realizable setting. However, the best known upper bound on the Li sandwiching degree for convex sets is given indirectly by known results in approximation of convex sets by intersections of halfspaces (see, e-g.. [DNS23] and references therein) and implies TDS learning algorithm that runs in time doubly exponential in d. Improving on the doubly exponential bound based on Li -issandwich,ng,
theoretic perspective [KSV24b] and 20(() time is required even in the

---

we provide realizable TDS learner with singly exponential (in poly(d) runtime for convex sets that are e-balanced, meaning that the Gaussian mass of both the interior and the exterior of the convex set is at least 6. For convex sets with only few relevant dimensions, our results actually give dimension-efficientt TDS learners. For more details, see Appendix D.
Theorem 4.1 (TDS Learning of Convex Subspace Juntas). For e E (0, d, k E N, let C be the class of c-balanced convex sets over TRd with k relevant dimensions. There is an O(c)-TDS learner for C with respect to Na in the realizable setting, which, for the training phuse, uses poly coly(d)2poly)) (d)2poly(ke)) samples and time and, for the testing phase, uses pol)(d)(k/+))()) samples and time.
We note that the balancing assumption mild, since it can be tested by using examples from the training distribution and has been used in prior work on realizable TDS learning of intersections of halfspaces with respect to the Gaussian distribution [KSV24a].
Universal TDS Learners. Importandy, the TDS learner of Theorem 4.1 can be made universal with respect to a wide class of distributions that enjoy some mild concentration and anti-concentration properties. The cost is an exponential deterioration of the runtime of the training phase. In other words, finding a hypothesis with better performance on the training distribution suffices to give error guarantees for a wide range of test distributions, including, for example, multi-modal and heavy-tailed distributions. We believe that this result interesting even from an information theoretic perspective. In Table 2 in the appendix, we give a more precise trade-off between universality and training runtime.
Let WD be the class of distributions DD over Rd such that Ex-D [(v x)*] S C for any $ and for any subspace W C dd of dimension at most k, the marginal density of D on W is upper bounded by C*2 where C is some positive universal constant. Then the following is true.
Theorem 4.2 (Universal TDS Learning of Convex Subspace Juntas). There is a DD-universal O(c)-
TDS learner for k-dimensional e-balanced convex sets over Rdd with respect to Na in the realizuble setting, which, for the training phase, uses poly(d) exp(20 /0) samples and time and, for the samples and time.
testing phase, uses poly(d))
We remark that the testing time for the universal TDS learner of Theorem 4.2 is still singly exponential in (k)y although the dependence on is exponentially worse. Having lower testing runtime is desirable feature because the potential users of large machine learning models might have limited resources compared to those available during training. We provide a more thorough discussion about this feature in the following section.
Cylindrical grids tester for localized discrepancy. To obtain our TDS learning results of The- orems 4.1 and 4.2, we once more make use of the localized discrepancy testing framework. In particular, we identify low-dinensionality (Definition D.I) and boundary smoothness (Definition D.4) of the underlying concept class as sufficient conditions for efficient testing of localized discrepancy when the notion of localization is defined with respect the subspace neighborhood (Theorem D.7).
The subspace neighborhood Nf) contains cow-dimensional concepts f whose relevant subspace is geometrically close to the relevant subspace for î (see Definition D.2). For TDS learning, we combine such testers with known learning algorithms for subspace recovery of low-dimensional convex sets (see, e.g., [Vem 1 Oa, KSV24a] and Theorem 1313) to ensure that the training phase will output some hypothesis ff such that the ground truth f lies within (f).
In other words, we exploit the existence of training algorithms with stronger guarantees (i.e., ap- proximate subspace recovery) than merely training error bounds, to relax the discrepancy testing problem low-dimensional localized version, while still providing end-to-end results for TDS learning. This relaxation not only improves the testing runtime, but also enables universality, since the localized discrepancy between two distributions can be much smaller than the global discrepancy between them (see also [ZLWJ20] and references therein).
The idea behind the localized discrepancy tester for the subspace neighborhood is to split the disagreement between f and an arbitrary concept f = (f) under the test distribution in two parts: (1) the disagreement between ff and a rotated version f of f where the input x is projected on the relevant subspace of the given hypothesis ff instead of the actual, unknown relevant subspace of f and (2) the disagreement between f and f. For part (2), we use the fact that the relevant subspace of f is geometrically close to the relevant subspace for f (since f E N&(f)). We conclude that
7

---

and can only disagree far from the origin and, hence, testing that the test marginal is appropriately concentrated suffices give the desired bound.
Low-dimensional disagreement between concepts with smooth boundaries. For part (1), we use the fact that the k-dimensional relevant subspace V for ff is known. We construct grid on V and run tests to certify that the probability (under the test marginal) of falling inside each of the cells is not unreasonably large. In order to bound the size of the grid, we also test that the probability of falling far from the origin on the subspace V is appropriately bounded. We then argue that the disagreement region can be approximated reasonably well by discretizing with respect to an appropriately refined grid. To ensure that the discretization of the near- wear-boundary region does not introduce a significant error blow-up, it is important that ʃ and f have smooth boundaries (see Figure 2 in the appendix).
5 Fully Polynomial-Time Testers
Algorithms for TDS learning that are efficient in testing time, can be useful to check whether a pre-trained model can be applied to particular population, without the need for overly expensive resources. Here, we focus on the class of balanced intersections of halfspaces (see Definition E.9) and provide the first TDS learner for this class that runs in fully polynomial time during test time. Moreover, the proposed tester is universal with respect to a wide class of distributions that satisfy some concentration and anticoncentration properties.
Let WD be the class of distributions D over Ed such that for any v E S we have Ex-DD(v-x)]] I C and, also, that the one- me--imensional density of the projection v x where x ~ 'D is upper bounded by C, where is some positive universal constant. Then the following is true (see also Theorem E.))).
Theorem 5.1 (Universal TDS Learning of Balanced Intersections). For e 102), d, k E N, there is a DD1 universal D(c)-TDS learner for the class of e-balanced intersections of k halfspaces over B w.r.t Na in the realizable setting. which, for the training phase, uses poly(d) (d) exp(O(ke) /e)) samples and time and. for the testing phase, uses poly (d, k, 1/c) samples and time.
For comparison, the previous state-of-the-art TDS learning algorithm for halfspace intersec- tions by [KSV24a] had overall runtime (O(log(k/<) + poly exp(O(k") and testing runtime (O(ngg(/<))) + poly (d) (k/e)))) (although training and testing were not explicitly separated). Hence, the overall runtime of the algorithm of Theorem 5.1 is better than the previous stateoof-the-are but also enjoys two additional properties: (1) the testing time is fully polynomial and (2) the tester is universal with respect to wide class (of multimodal and even heavy-tailed distributions).
We note that it is not by chance that these two properties are satisfied simultancously: they both relate to the fact that it suffices to solve simple discrepancy testing problem. Since the tested property is relaxed, more distributions should satisfy it and testing the property can be made efficient. For comparison, as well as to provide a TDS learner with better overall runtime some regimes, we may trade-off universality and test-time efficiency to obtain the following result (see Theorem 10).
Theorem 5.2 (TDS Learning of Balanced Intersections). For e E 10,1 d, E N, there is an TeD)-TDS learner for the class of e-balanced intersections of k halfspaces over Id w.r.t Na in the realizable setting. which, for the training phase, uses poly(d)(k:cc0(()) samples and time and, for the testing phase, uses (lo))(())))))) samples and time.
Remark 5.3. The algorithms of Theorems 5.1 and 5.2 can both tolerate some amount of noise, i.e., provide an O(e) error guarantee even when X min min ([: Diggin) + Dre(t; is non-zero (but sufficiently small). For Theorem 5.1, the amount of noise that can be tolerated is = cxp(-O(k/e)) while for Theorem 5.2, the tolerated amount is A = (kt/)) The amount of noise tolerated by the non-universal tester is more, because the test is more expensive and, therefore, does better job in translating the guarantees of the training phase to guarantees for the test error. For comparison, the Chow matching tester of Theorem 3.1 runs much more expensive tests and can, therefore, tolerate much more noise, i.c., X O
(see Table 3).
Discrepancy testing through boundary proximity. We once more use the framework of localized discrepancy testing, in order obtain TDS learners with strong guarantees. In order to achieve fully polynomial-time performance, we aim to use a tester that is as simple as possible. In particular, for a given halfspace intersection f. we test whether the probability that an example drawn from the test
8

---

marginal falls close to the boundary of f. i.e., close to at least one of the defining halfspaces (see Lemma E. 13 and Definition E.3). We also test concentration the test distribution marginal.
Interestingly, we show that these two tests are sufficient for certifying low localized discrepancy from the Gaussian distribution with respect to the notion of disagreement neighborhood N e. i.e., if the Gaussian disagreement P [f(x * f(x)) between f and f is small enough
E TEN (f) (see Definition E.2). particular, we show that if f is a balanced intersection and f E (f).). then ʃ and I can only differ either (1) far from the origin or (2) close to the boundary of I (see Proposition E.4 and Lemma E.1 Importantly, this property is woint-wise: for any x E R such that f(x) + f(x), x will either satisfy (I) or (2) and, hence, no distribution over IR can fool our tester.
In the heart of our proof is geometric lemma which demonstrates that any balanced convex set is locally balanced as well (Lemma E.12), meaning that for any point x E R there is a large number of points near x with the same label as Therefore (unless the norm of x is large), any hypothesis with low Gaussian disagreement from the ground truth f*, must encode all of the local structure (or boundary) of f that is not very far from the origin. To show this, we use a geometric argument about convex sets (see Figure for the case when the label of x is 1. The other case is simpler and follows by the existence of separating hyperplane between convex set and any point outside it).
R
K
Figure I: x lies within a balanced convex set K., then many points close to x lie within IC as well, ie., there is cone R' with R' [xx, 2) n,, where B(x, g) is ball around x. The ball centered at x, exists due to the fact that IC is balanced: any balanced convex set contains some ball with non-negligible radius. The convex hull of and the ball at x. lies within K. (See also Fig. 3)
Since we have localized discrepancy tester with respect to the disagreement neighborhood, all we need from the training phase is to output some intersection of halfspaces f with low training error (so that the ground truth f* lies within (J). Hence, we may use any proper PAC learning algorithm for intersections of halfspaces under the Gaussian distribution. We use the algorithm by [DKS18] 1 (see also Theorem E11
Remark 5.4. We note that the three important properties we used to apply the method of boundary proximity are that (1) the hypothesis / returned by the learning algorithm admits an efficient boundary proximity tester and (2) the ground truth f* is locally balanced and (3) that ff and f are both low- dimensional. For more details, see Appendix E.
6 Limitations, Future Work and Broader Impacts
TDS learning beyond discrepancy testing, We show that all of the known results in TDS learning be achieved (and improved) by decoupling the training and testing phases. While separating training and testing phases is appealing and well-motivated by real-world scenarios, it is an interesting open question whether using the examples from the test marginal during training time could lead to improved TDS learning algorithms.
Characterizations of discrepancy testing complexity. We provide several positive results for local- ized discrepancy testing which imply new results in TDS learning. Moreover, on the lower bounds side, in Appendix F, show that global discrepancy testing is NP-hard even for simple classes under no further assumptions. is an interesting open question to explore tight characterizations for dimennionnefffcientt, universal or fully polynomial-time localized discrepancy testing.
Lifting the balancing assumption. testers), require that the underlying concept class only contains concepts that are not too biased
our universal TDS learners (and universal discrepancy

---

towards one of the two possible labels under the training distribution (so that the training examples include enough information for localization). This condition mild and can be easily tested by using training examples. However, better understanding of the importance of this condition for (universal) TDS learning could potentially lead to (or rule out) improved and/or universal algorithms for broader concept classes, e.g., polynomial threshold functions.
Relaxing assumptions on training marginal. Our main results in this work hold under the assump- tion that the marginal of the training distribution is either the Gaussian distribution or the uniform distribution over the hypereube. Such assumptions are standard in learning theory, as they serve as a concrete theoretical testbed for simplifying the analysis and presentation of the proposed algorithms and ideas. Relaxing those assumptions an important and obvious goal for future work and parts of our analysis hint towards such relaxations (see, e.g., Remarks D.10 and E.5).
Broader Impacts. We do not identify any direct potential negative societal impacts. In fact, although our results are of theoretical nature, our algorithms might, in principle, help mitigate potentially unfair outcomes of applying certain pre-trained models on populations that are misrepresented in training data. Our discrepancy testers will either certify low prediction error on the deployment population or signal that the model at hand might not be applicable the deployment population and another model should be considered.
References
[AGM03] Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise independence. Information Processing Letters, 88(3):107-110, 2003.
[Bal93] Keith Ball. The reverse isoperimetrie problem for gaussian measure. Discrete Comput. Geom., 10(4):41 1-420, dec 1993.
[Baz09] Louay MJ Bazzi. Polylogarithmii independence can fool dnf formulas. SIAM Journal on Computing, 3866)2220-2272,, 2009.
[BCK+07] John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman. Learning bounds for domain adaptation. Advances in neural information processing systems, 20, 2007.
[BDBC+ 10] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learming, 79:151-175, 2010.
[BDBCP06] Shai Ben-Davin John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
[BGS18] Arna Bhattacharyya, Suprovat Ghoshal, and Rishi Saket. Hardness of learning noisy halfspaces using polynomial thresholds. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 876-917. PMLR, 06-09 Jul 2018
[BK97] Avrim Blum and Ravindran Kannan. Learning an intersection of constant number of halfspaces over a uniform distribution. J. Comput. Syst. Sci., 54(2):371-38) 1997.
[Bog98] Vladimir Igorevich Bogachev. Gaussian measures. Number 62. American Mathemati- cal Soc., 1998.
[Bra10] Mark Braverman. Polylogarithmic independence fools AC circuits. Journal of the ACM (JACM), 100 2010.
[DKK*23] Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Effi- cient testable learning of halfspaces with adversarial label noise. Advances Neural Information Processing Systems, 36, 2023.
10

---

[DKN10] Ilias Diakonikolas, Daniel M Kane, and Jelani Nelson. Bounded independence fools degree-2 threshold functions. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 11-20. IEEE, 2010.
[DKS18a] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1061-1073. ACM, 201 8.
[DKS18b] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061-1073, 2018.
[DLLP10] 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, pages 129-136. JMLR Workshop and Conference Proceedings, 2010.
[DNS23] Anindya De. Shivam Nadimpalli, and Rocco A Servedio. Gaussian approximation of convex sets by intersections of halfspaces, arXiv preprint arXiv:2311.08575. 2023.
[DTK22] Ilias Diakonikolas, Christos Tzamos, and Daniel M Kane. A strongly polynomial algorithm for approximate forster transforms and its application halfspace learning. arXiv preprint 22.0::22 2022.
[GKK23] Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari. A moment-matching approach to testable learning and a new characterization of rademacher complexity. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Computing, 2023.
[GKKM20] 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: 13:15559-11 15859-15870, 2020.
[GKM12] Parikshit Gopalan, Adam R. Klivans, and Raghu Meka. Learning functions of halfs- paces using prefix covers. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 The 25th Annual Conference on Learning Theory, June 25- 27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 15.1-15.10. JMLR.org, 2012.
[GKSV23] Aravind Gollakota, Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Tester-learners for halfspaces: Universal algorithms. Advances in Neural Information Processing Systems, 36, 2023.
[GKSV24] Aravind Gollakota, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. An efficient tester-leamer for halfspaces. The Twelfth International Conference on Learning Representations, 2024.
[НKM23] Steve Hanneke, Samory Kpotufe, and Yasaman Mahdaviyeh. Limits model selection under transfer learning. In The Thirty Sixth Annual Conference Learning Theory, pages 5781-5812. 12. PMLR, 2023.
[HS19] Prahladh Harsha and Srikanth Srinivasan. On polynomial approximations to AC Random Structures & Algorithms, 54(2):289 00099933332200 2019.
[KK21] Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. Algorithmic Learning Theory, pages 850-864. PMLR, 2021.
[KM13]] Daniel M. Kane, Adam R. Klivans, and Raghu Meka. Learning halfspaces under log-concave densities: Polynomial approximations and moment matching. In Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14 14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 522-545. oLg. 2013.
11

---

[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio.
Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777-1855. 2008.
[KLT09] Adam Klivans, Philip Long, and Alex Tang. Baum's algorithm learns intersections of halfspaces with respect to log-concave distributions. pages 588-600) 01 2009.
[KM21a] Zander Kelley and Raghu Meka. Random restrictions and prgs for ptfs in gaussian space. arXiv preprint urXiv:2103.14136 2021.
[KM21b] Samory Kpotufe and Guillaume Martinet. Marginal singularity and the benefits of labels in covariate-shift. The Annals of Statistics, 49(6):329933323, 2021.
[KOS04] Adam R. Klivans, Ryan O' D'Donnell, and Rocco A. Servedio. Learning intersections and thresholds of halfspaces. Comput. Syst. Sci., 68(4):808-84)) 2004.
[KOS08a] Adam R. Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning geometric concepts via gaussian surface area. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 541-550. IEEE Computer Society, 2008
[KOS08b] Adam R Klivans, Ryan O'Donnell, and Rocco A Servedio. Learning geometric concepts via gaussian surface area. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 541-550. IEEE, 2008
[KSV24a] Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages PMLR, 30 Jun-03 Jul 2024.
[KSV24b] Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2887-2943. PMLR, 30 Jun-03 Jul 2024.
KZZ24] Alkis Kalavasis, Ilias Zadik, and Manolis Zampetakis, Transfer learning beyond bounded density ratios. arXiv preprint mrXiv:2403.11966 2024.
[LV07] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms, 30(3):307-358, 2007.
[LW94] Philip M. Long and Manfred K. Warmuth. Composite geometric concepts and polyno- mial predictabilityy. Inf. Comput., 113(2):230-22) 252, 1994.
[MMR09] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Proceedings of The 22nd Annual Conference on Learning Theory (COLT 2009), Montréal, Canada, 2009.
[Nel73] Edward Nelson. The free markoff field. Journal of Functional Analysis, 12(2):211-227,
1973.
[O'D14] Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
[OS08] Ryan O' O'Donell and Rocco A Servedio. The chow parameters problem. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 517-526, 2008.
[RMH 20] levgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani. A survey on domain adaptation theory: learning bounds and theoretical guarantees. arXiv preprint arXiv:2004. 1829, 2020.
[RV23] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learn- ing algorithms. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Computing, 2023.
12

---

[SSK12] Masashi Sugiyama, Tajji Suzuki, and Takafumi Kanamori. Density ratio estimation in machine learning. Cambridge University Press, 2012.
[Tal17] Avishay Tal. Tight bounds on the Fourier spectrum AC In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Lecinniz-Zentne fuer Infor- matik, 2017.
[Vem10a] Santosh S Vempala. Learning convex concepts from gaussian distributions with pea. In 2010 IEEE 51 Annual Symposium Foundations of Computer Science, pages 124-130. IEEE, 2010.
[Vem10b] Santosh S Vempala. A random-sampling- baaedd algorithm for learning intersections of halfspaces. Journal of the ACM (JACM), 57(6):1-14, 2010.
[Ver18] Roman Vershynin. High-dimensional probability: introduction with applications in data science, volume 47. Cambridge university press, 2018.
[ZLWJ20] Yuchen Zhang, Mingsheng Long, Jianmin Wang, and Michael I Jordan, On localized discrepancy for domain adaptation. arXiv preprint arXiv:2008.06222, 2020.
13

---

A Extended Preliminaries
We use standard big-O notation (and Ô to hide poly-logarithmic factors), I& is the d-dimensional euclidean space and Na the standard Gaussian over R {=1]² is the d-dimensional hypercube and Unif( {=1]d) the uniform distribution over {=1}². N is the set of natural numbers N {1, ........ and x Rd denotes vector with x (x1 1x....., X2) and inner products
For Nd. denote with x the product [[i x, , M. = [[xx] and ||a=|| = Lie(d] Qç. For polynomial
P over IRd and a E Nd, we denote with Pa the coefficient of p corresponding to x", i.e., we have p(x) = Eagga Pax". If is a polynomial over { then we express it in its multilinear form, using only coefficients Pa with E {0, i.e., p(x) Eo Xax". We define the degree of p and denote deg(p) the maximum degree of a monomial whose coefficient in p is non-zero. We use standard notations for norms ||x|| ExE(4) |x|| |X|| (EEja x²) and ||
maxie[d] |xs/- We denote with g the d - 1 dimensional sphere on IR and, for R and 0, (x,
{y E Rd ||x ylla r..
For any V1, V2 E Rdd we denote with V1 V2 the inner product between V1 and V2 and we let (V1,. V2) be the angle between the two vectors, i.e., the quantity 0 E [0, æ] such that || [Vill2//v2lle cos(0)
V1 V2. For F I. we call function of the form ++ sign(v x) origin- iegin-centered (or homogeneous) halfspace and function of the form x + sign v x r) a general halfspace over TR:
We let X C IR be either the d-dimensional hypercube [=1] or Rd For a distribution over X. Ep (or Ex~D) to refer the expectation over distribution D and for given set X, Ex (or Ex=x) ) to refer to the expectation over the uniform distribution on X (i.e., Ex~x(g(x)) = [X] ExEx (xx,, counting possible duplicates separately). We let R4 o0).
We detine the notion of balance as follows.
Definition A.1 (Balanced Concepts). For 3 E (0,1), we say that a function f Rd + {+1} is
(globally) 3-balanced if for any E IRd have P. Pa-N[((2) = [(x) > B.
B
Additional Tools
B.1
Boundary Smoothness of Structured Concepts
In this section, we prove that low dimensional polynomial threshold functions and convex sets have smooth boundary, i.e., non-asymptotic anticoncentration bounds that scales linearly with the distance from the boundary. We first prove that PTFs have smooth boundary.
Lemma B.1 (Smooth Boundary for PTFS). Let p be polynomial of degree E over TR. Let F R& > {+1} be the function defined as F(x) sign(p(x)). Then, F has a C k-soohhtth boundary with respect to for a large universal constant C.
Proof. Let C be a large universal constant that we fix later. Let 3C Define the set S:= [ Ei E p(xx]] 2 > (CE /0) (o)e//)))V>ppppppp 1|V'='((x)lle) Observe that F Px~NE [x E 0, < Px x S + Px-Ni x E 8 x & S). We bound these two terms separately. To bound the first term, we use the following theorem from [KM21a].
Lemma B.2 (Lemma 1.6 from [KM21a]). Let C be a large universal constant. For any polynomial p: R + R of degree l and x ~ N₁. the following event occurs with probability at least 1 8:
1''((x)12 < "=)x[('>>'>==xx)>>>>>> for all Sise.
Thus, we have that Px~ xx E S] < 6. Now consider a point expansion, have that p(x + z) pxx) Eaent,
x & S. From multivariate taylor
Iglaage 8º p(x) z Thus, for R with
In Appendices D and E, the notation p to denote natural numbers and use g for polynomials instead.
14

---

| S y, we obtain that
pp(x) p(x + z)1
10
p(x)
| =
1slasse st
tE|d
" p(x) S
Σ iE[l
y f (CE 16)")(()) S 1p(x)1/2.
The first inequality follows from the multivariate Taylor expansion. The third inequality follows from the fact that || I y and the bound on the number of monomials of size by kat The penultimate inequality follows from the definition of the S and the last inequality is true by our choice of 8.
Since (p(x) p(x + z)1 < 1/(x))/2, we have that F(x) = F(x + z) for all z E IR with ||z||2 S y
Thus, we have that Px X F.F x S] 0. Thus, we have that Px~NN [x E F, yyk
We now move to proving that low dimensional convex sets. To prove this, will crucially use the notion of Gaussian surface area (an asymptotic anticoncentration bound) that we will now define. Definition B.3 (Gaussian Surface Area). Let f be a boolean function. The Gaussian surface area T(f) is defined as
r(f) = lim inf 6-+0 8 (0..))
I I A/ \A]]
where A, = 1/x f(x) = 13, 47 = mou:minve,, ||u vll2 S 67.
We prove that convex sets have smooth boundary in two steps. We first prove that the set of points inside the set that are close to it's boundary have small mass. To do this, we use noise sensitivity argument (Lemma B.5). Then, we prove that points outside it that are close to the boundary (Lemma B.7). This will follow from argument the definition of Gaussian Surface area and bound on this quantity for convex sets due to [Bal93]. Together, these two lemmas imply that convex sets have smooth boundary.
The following lemma will be useful in proving the smooth boundary of the interior of the set.
Lemma B.4. Let E 1/2). Let be a convex set on R² and let f(x) = 1(x E S} be the indicator function of S. Then, we have that IP Px-NNlffss + f(x/vI- X) S kog
Proof. For any vector w E Re with ||w||2 1, let fw R R be the function defined as [w(r) = f(r w). Also, note that Jw is the indicator function of a one dimensional convex set. Observe that P Px~NN, (f()) + fxx/vI-X 1 < sup/|wlla= P (+> [fw( * fw( fw(Vr/vI- - from the fact that the dimensional Gaussian conditioned on pointing in direction w is distributed as vrw where x² (l)) Here, x (k) is the one dimensional Chi- Chi-squared distribution with mean k.
We have thus reduced the problem to one dimension. Consider a function g g IR - such that g(x) = {x E IVa((1 - )), b/(11 }}]} where a, b are from IR {U{oo)) All one dimensional indicators of convex sets are of this form. We will now prove that (M) # s(vF/v1 A)] < kA (k))))AA)
Observe that P Proya ( suffices to bound P P fr E [a, a/(1 - A)]] for E R+ as the claim then follows from a union bound. We bound this by splitting into two cases.
(r))(()) |r E a0 - X) U [b. b/(1 - X)]]-
Case 1: 2 2k (og( Since (k) is the distribution of the sum of squares of l indepen-
dent (0 1) Gaussian random variables, we have that P. (M)x"(")| 2 a) S k kP>=~N(o.,l1== z a/k] < ke (2(k), Thus, when a 2 22 log()/)),, we have that P (k)) [r E [a, aa,a/(11 - A)]] <
P Pro)a(k) [r 2 a) X.
Case < 2k log(k/A). Let vp be the density function for x² 2k)... It is a standard fact from probability that (xx) 2
2k/2-1 =/2, For ls = 1, it is a fact that (xx) < 1. For k 2 2, by taking
15

---

derivative, we can see that this density function is maximized at = h 2. We obtain that
(xx (1: 2) c R/2+1 - ( e
e 1/2++1 - 2
2k/2
25/2(k/2))//2-
where the second inequality follows from the fact that [(t) 2 (1) for all 2 and r(1) 1. We have that
[EE a/(a {)]] s 1 (1/(1- () 4kAlog(k/M) logogkv
(x)
We get the first inequality from the upper bound the density. The second follows from the fact that 1/(1 -) X) < 2λ when < 1/2. The third inequality follows from the assumption on a. The final inequality follows from the fact that æ log(1/z) S vz.
We are ready prove the set of points inside the convex set that close to it's boundary have small mass under the Gaussian.
Lemma B.5. Let S be a convex set on R.*, Lei @ E (0, 1). Then, we have that P. Px (x E Sna,s)) s Ck log kg where C is a large universal constant.
Proof. Define the function f R + a f(x) = 1fx E S}. We now use restatement of Corollary 12 from [KOS08b].
Lemma B.6. Let be boolean function Re. For any (0,1), it holds that
[((x) + (VI- vAy) s (V)
P x.y--N
for large universal constant C.
Let be the function 9(x) = f(x/ VI- A). Observe that is also an indicator of convex set. From [Bal93] we have that l'(g)= S 1/4/ Thus, applying Lemma B.6 to we obtain that for any 1)
IP N
/(x/VI-X)
x x+Vi=x>>
CVAA
where C' large constant. Combining the above expression with Lemma B.4, we obtain that for any À E (0, 1/2).
A f(x) + f x 1 1- x )
P x
CVTL2/A + 2k log KVA.
(B.1)
Now, consider any point in Sno,s. Since S is convex, there exists hyperplane f((x) = L [(w - - b > 0} for w E R with ||||2 and E R such that h(y) = 1 for all y E S and w p + S This hyperplane correponds to the tangential plane whose normal vector is the line joining p and the point closest to it in ØS. We have that for any ? > 0, PZ-AA [w-7z I -o] 2 1 27 as the Gaussian
density upper bounded by pointwise. Thus, for any 7 > O. P. P [f Combining this with Equation (B.1), we obtain that
f(p) ! 24
1_e 0 2
P. x~N
S CCVA S 2% log KVX.
Setting À = 40² and rearranging terms, we obtain that P Px~NN |x E Sna,s) S C'k kg where C" sufficiently large universal constant.
We now prove the smoothness result for points outside the set.
Lemma B.7. Let S be convex set R& Let E (0, 1). Then, have that P Px~Ni (x S n n < Ck3/2 where C is sufficiently large universal constant.
16

---

Proof. For t >> O, define the set St as St fx E IK
infyes||x - y112 S f}. We have that
P xm
X 5 nd = IP
IX So S]
x
N((: O, Ix) dt - C dt S SCK
CKV/4
xEaS.
where C' a large universal constant. We obtained the penultimate inequality using the definition of Gaussian surface area.
We now state our final result on the smooth boundary of convex sets.
Lemma B.8 (Smooth Boundary for Convex sets). Let S be convex set. Let F IR + {+1} be the function defined as F(x) 1(x S}. Then, F has a Ck log k-smooth boundary with respect to N₂ for a sufficiently large universal constant C.
Proof. The proof is immediate from Lemma B.5 and Lemma B.7.
B.2 Sandwiching Polynomials
In this section, present known results from pseudorandomness literature the existence of sandwiching polynomials for various function classes with respect to [ni and Na. Although previously known, these results are mostly not stated in the manner in which we need them. In particular, the coefficient bounds are not explicity stated in previous work. We state these results in terms of existence of sandwiching polynomials with coefficient bounds for completeness.
We now introduce the important notion of (6, f)-independent distributions.
Definition B.9 ((6, f--independent distribution). Let D, D' be distributions on Rdd For 8 > 0 and E N. we say that the distribution D' is (ő, (iindepennn with respect to D if Ex-D [x Ex-D [x < 5 for all a E Nd.
We drop the "with respect to D" when the distribution is clear from context. Let D. D'' be distributions on X' C Rd and X {+1}. For > 0, we say that D' c-fools f with respect to D (again, we drop the "with respect to" when the target distribution clear from context). For concept class C, we say that D' e-fools C with respect to D if D' e-fools f with respect to 'D for all functions f T C.
[Ex=D[((x) E Ex [[()]]
We will use the following result from [GKK23] which is generalization of a result from [Baz09]. will only need one direction of the result which we state below.
Lemma B.10. [Theorem 3.2 from [GKK23]] Let be distribution X C RRd, Let 8, > 0 and l E N. Let f : X - Rd be function that satisfies the following property: given any distribution D' that is (8, E)-independent with respect to D, we have that [x [x))] Ex~D [x)] S
Then, there exists degree polynomials Pdown, Pup such that Pdown E f S Pup and Ex (upp
Pdown (x)] + 8(1pupl + (Poowal) S e.
B.2.1 Sandwiching Polynomials: Boolean
In this section, the target distrbution is Unif We will find the following lemma useful. Lemma B.11. Let e. > O and E E N. Let f {=1]d + {+1} be a function such that all (0, indeepeendttt distributions c-fool Then, there exists polynomials Pup- Pdown of degree E and coefficients bounded by (d') such that Paown I Pup and Ex~Unif(+ (Pup(x) Pdowa (x)) S O(e).
Proof. We use the following theorem from [AGM03] that states that for any (6, didiiiiiibttion there exists (0, f) distribution that is e-close to TV distance.
Lemma B.12 (Theorem 2.1 from [AGM03]. For 8 0 and l M. let D be a (6, -iiinedpenn distribution {+1]d. Then, there exists distribution D' that is (0, () f)-ineependent such that the TV distance between D and D' is at most ōd
17

---

From the above claim, we have that any (e/d", f)-independent distribution 2e-fools f. Thus, from Lemma B. 10, there exists polynomials Pup- Pdown of degree with coefficients bounded by Odd) such that Unif [1ipe(Pupxx
Pdown (x) < 2e. This proves the claim.
Lemma B.13 (Sandwiching polynomials for degree 2 PTFs). Let C be the class of degree 2 PTFs. For e O, the ((e)-a(pp)) appprxximtee L1 sandwiching degree of C under [ is at most f ((1/e)) with coefficient bound )
Proof. From [DKN10], we have that (0, f--independent distributions c-fools C when e = ) Now, we apply Lemma B. B.11 to finish the proof.
Lemma B.14 (Sandwiching polynomials for depth-t ACa)- Let C be the class of depth-l ACo circuits of size s on {+1] For e >> O, the -apprxanie Lı sandwiching degree of C under Unif {+]] is at most & (log s) (1/e) with coefficient bound Odd)).
Proof. From [Bral0, Tal17, HS19], we have that (0, E)iindepend distributions e-fools f when i (log ()t) (og(1/c). Now, we apply Lemma B.11 finish the proof.
B.2.2 Sandwiching Polynomials: Gaussian
Lemma B.15. E O and l E N. Let f - {+1} be a function such that all (0, e)- independent distributions e-fool f. Then, there exists polynomials Pup Pdown of degree and coefficients bounded by (dd) such that pdown S f S Pup and Ex--N Pap ) Priown (x)] S (c)).
Proof. From Lemma 10, we have that there exists Pup- Pdown of degree such that Ex [Pup (x) Pdown (x)] S 2e and Pdown S f S Pup- The claim now follows from the following lemma(proof is included in the end of this section) that states that any sandwiching polynomial with respect to Na must have bounded coefficients.
Lemma B.16. Let J Rd + {+1} be function, and let Pup and Pdown be degree-l polyno- mials satisfying the following (i) for every E Hd we have Pup 2 f(x) > Paown (ii) (x, PPu (x) Pdown (x)] S 1. Then, the polynomials Pup and Pdown both have coefficients bounded by 2 (10d) in absolute value.
Lemma B.17 (Sandwiching polynomials for degree 2 PTFs). Let C be the class of degree PTFs. For e > O, the O(e) )apprxxpxxe Lı sandwiching degree of under Na is at most & = ((1 with coefficient bound )dd))
Proof. From [DKNI0], we have that (0, -)-independent distributions e-fools when E = Ō(1/e²).
Now, we apply Lemma B.15 finish the proof.
In the remainder of this section, we prove Lemma 1. We will use the notion of Hermite poly- nomials. Recall that for polynomials over R that are orthogonal with respect to Gaussian distribution. In other words (o, (H, Hx)) = 0 whenever # j. In this work, we normalize the Hermite polynomials to further satisfy (L,,) [H, (x)
0. 2, Hermite polynomials {H,} are the unique collection of
1. It standard fact from theory of orthogonal polyno- mials that Ho(x) = 1, H (I) and for i > 2 Hermite polynomials satisfy the following recursive identity:
- 1)! (x) li! = xH,(x)) Vil H,-1(x) Vii-1
Proposition B.18. Each coefficient of H2 is bounded by 2 in absolute value.
Proof. This follows immediately from the recursion relation.
Proposition B.19. All coefficients of multi-dimensional polynomial Hi, (x:) ... Hh, (xa) bounded by 2 +22
18

---

can be expressed as II my(x)) where each Proof. Each monomial of H,, (x))) -.. Hx,(Ka) mx(x;) monomial of Hi, (xz). But we know that the coefficient of mj is bounded by 2 in absolute value. Thus, each coefficient of Hi,
(xx)))) is at most 2 pitattatta,
Proposition B.20. Let p a polynomial over I of degree f. Suppose that p satisfies
E
[)(x))
11
XEN(O.,)
then every monomial of p has a coefficient of at most (2d) in absolute value.
xa) be its coordinates. We expand p(x) as a sum of Proof. For an element x E Rd we let (x1 multidimensional Hermite polynomials
p(x)
Σ
dn da Hi, (x
Hig
(B.2)
$1 $4.2
Due orthogonality of Hermite polynomials, have:
Σ
2 Pi di xEA(O..) [((())) s
E
$1.52 14420
particular, this implies that each coefficient 03,,d,," bounded by 1 in absolute value. Combin- ing this with Equation B.2, Proposition B.19 and the fact that there are at most dl ways to choose i ig. 12...-ia is 0 satisfying 2; I L, we that each coefficient of bounded by (2d)² in absolute value.
Finally, we need the following standard fact.
Fact B.21 (Gaussian Hypercontractivity [Nog98),[Ne173)). ifp Rrd R is polynomial of degree at most f, for every 2 2.
E
[p(x)) s (t 1)//2
E
[x²(x))
Vx
The following is a standard corollary:
Proposition B.22. p IRd + R is a polynomial of degree E, then
E XEV(O.1)
[((()))
ee
[p(x)]]
xEN(0.1)
Proof. The proof is standard, and is included here for completeness (a completely analogous proof for the Boolean case can be found in Theorem 9.22 from (14D).)). Let À > 0 be a parameter and let Using Generalized Holder's inequality and Gaussian Hypercontractivity, we have
0 2 1+x
E (1m(x)11) ( (NESFO.., [(((x))2+t) (Lex)o.,(oo(xx))))))
( [((()))}}
S
V xEV(..1)
xEV(O.1)
1-8
(1(x))))))) (1+
E xEN
2)
E Re.Foon(((( [(p()))]]
V xxvio..)
Overall,
(V E KeEi [((()))
< (1+1)
E XEN((..)
[|x(x))]]
"Note that the expansion below is always possible for a degree polynomials because polynomials of the form Hi, (x, H., (X2)..- ...-.-,,, H., (xa) are polynomials of degree at most that are linearly independent, because they orthonormal with respect the standard d-dimensional Gaussian.
19

---

Taking power 1/0 of both sides and recalling that 0 = 1+A
A
we get:
E V xxNV(,, [[x()))2] & (1+ 2/2
E xEN(O.1)
[[(xx]] (1 2)(+
I xEV(O,1)
[l((x)]]
Finally, taking À + 0 proves the proposition.
Finally, we are ready to prove Theorem B.16.
Proof of Theorem B.16. Without loss of generality", we bound the coefficients of (x). We have
E xEM(0,1)
Pup (x)]
E
[[((x]]+
+ E (x)p - f(x)]] -
xEN(0,1)
XEW
S
E xEV(0.1)
[[((x]]] +
xEV [Pup(x)
E
Pdown (x)] S 2.
Note that in the last inequality the value of (x [x](x)] is bounded by 1 because f is {+1}- valued, and ExeN((o,)) (x) Pdoww (x)] was bounded by by the premise of the theorem. Com- bining the equation above with Proposition B.22, we get
E xEV(0..)
( 52.
Finally, together with Proposition B.20 implies that each coefficient of Bug is bounded by (2d) in absolute value. This allows us to conclude that each coefficient Pup is bounded by 2 (10d) in absolute value.
C Chow Matching Tester
We now focus functions that have low-degree sandwiching polynomials approximators under the training distribution.
Definition C.1 (Ca-sandwiching polynomials). Consider X C Rd and a distribution D over X. For and f X' (+1), we say that the polynomials Pup: Pdown X e-approximate f fi-sandwiching polynomials for under D if the following are true.
1. Pdown (x) S fxx S (x), for all X.
2. E ExxDlpup - Paown (x) Se
We say that the e-approximate L -i-danwwihinng degree of C under D is at most E and with (coefficient) bound if for any f E C there are e-approximate L -ssaddwwchinng polynomials Pups Pdown for such that deg(Pup), deg (paown) < and each of the coefficients of Pup Pdown absolutely bounded by B.
It turns out that given function class C with low degree sandwiching approximators, can test localized discrepancy of hypothesis / with respect very global notion of neighbourhood: the entire concept class C! We state the definition here.
Definition C.2 (Global Neighborhood). The global (H. C') neighborhood is defined as N(f) C for all H. We denote this by Nc-
C.1 Discrepancy Testing Result
We now present our discrepancy tester for concept classes with bounded c-approximate C₁ sandwich- ing degree. The primary advantage of this tester is it's global nature: given hypothesis f. certifies low localized discrepancy with respect every function in the concept class.
This is indeed without loss of generality, because the function f bounded from above by -Pdown. and from below by Pup.
20

---

Theorem C.3 (Chow Matching Tester). Let DD be distribution over set X S R Ler C S {X + {=1}} be a concept class. Let O, Meone N. Let H. {=1]*. Assume that the following are true.
1. (L--sandwiching) The j-approximate L1 L1-sandwiching degree of w.r.t D is with bound B.
2. (Chow-concentration) For any function e H. if Dam with m 2 Meones then with probability at least 9/10, we have that for all a E No with ||a]1 S L |xlf(x) x*1 [xx[((x) x=1
S
BRZ..
Then, there exists a (Nc, -tesser T for localized discrepancy from D with respect to (D) that uses Meone (2²) samples and runs in time poly (Meone: d' 1
Proof. For an input distribution D' and function ʃ E H. the tester runs Algorithm with Meone samples X from D' and function f as input. We now prove it's correctness.
Soundness We first consider the case where T accepts D'. Let f arg fec PXNDD (f(x) *
[xx) Px~D fx) + f(x)) ). Since Ixxxx=(((x) + [x(x (1 (f* /(x)])/2,
is sufficient to prove a lower bound on the second term. From Chernoff bound, we have that
Ed [f*(xx f(x)] 2 Ex[f"
f(x)]
with probability least 3/4 when |X] > C/e² for
some universal constant C 1. We now bound Ex(f*(x) f(x)). Let Pup. Pdown be e-approximate
L -i-sandwiching polynomials for f under D. We have that
(x) f(x)] X [((ff(x) (x) - (x)( f(x)] +
1 [[Pup(x): f(x)]
X
2 ([ Pup (x)] + BlDup(X (x) [(x)] 2 E
P[Paown (x) Pup Pup(()) (x)) + Elpup(x) BBppp [(x)] 36
D
(x) F(x)] + [((Pap(x) - (x)) F(x)] - 4E 2 D
(xf(())) f(x)] - 5E.
The first inequality follows from the fact that Pdown (x) S (x) S Pop(()) To obtain the second inequality, we use the fact that the tester accepts if and only if Ex [x]] - Ep(xx) < A and N such that ||a|| S l. Since the
[x(](x)= - Ex(s(x) x*]| A for A BaaT and all coefficients of Pup- Pdown are bounded by B and each have at most de monomials, we obtain the second inequality. The last two inequalities use the fact that IE (Pup (x) Pdown (x)] S E.
Thus, we obtain that EE [E (x) -(x)) 2 Ex(s"(x) A(x] Ge with probability least 3/4. This implies that P Fx-Dil [x)) * f(x)] < (x= o f(x)] + 3e. From the definition of f*, we therefore have that disc7.N. (D, D') < 3E with probability least 3/4 when the tester accepts.
Completeness In this case, we have that D' = D. Clearly, from our assumption on Chow concentration, we have that with probability at least 4/5, [x [x*] Ep [x]]]]] < A and [x] x*] - Ep (E x²11 A for A Bår and all such that ||a]|2 S E. Thus, with probability least 4/5, the tester will accept.
Algorithm 1: Chow Matching Tester
Input: Set X from D', function f X + (+1), parameters e > 0, 0, E, B > 0 e Set A Bda
For each E Nd with |alli L, compute the quantity Ma =Ex(f(x) x*).
Accept if [Ma- ExIf(x) x²1| < A and Ex[x"] Ex[x"]] A for all with ||a||| S l.
Reject otherwise.
21

---

C.2 Applications to TDS Learning
In this section we prove that any concept class with L1 sandwiching polynomials can be TDS learned. This improves the results of Klivans et al. 2023 which proved that L3 sandwiching implies TDS learning. In particular, our result implies a new TDS learning algorithm for the class all constant depth circuits (CO) which unknown in prior work. We also achieve tight dependence the parameter À as compared to prior work which was off by constant factors.
Algorithm 2: TDS learning through Chow matching
Input: Sets Swrain from Digiin Xtest from Dxx Training Algorithm
e (0, (0,1),& 6 N,
Let f be the output of A when run on input Strain
Run the Chow matching tester(Algorithm 1) with imputs Xtest F. e, and B with source
distribution x
Accept and output f if the Chow matching tester accepts.
Reject otherwise.
We now state our general theorem about the connection between Li sandwiching and TDS learning. contrast to prior work, we completely decouple the training and testing phase the TDS learner.
Theorem C.4 sandwicinn implies TDS learning). Let D be distribution over a set X S Rd. Let C S {X' {=1}} be concept class. Let e, E (0. Let H {+1)x. Assume that the following are true.
(L1 -(i-swnwwihhing) The e-approximate Li sandwiching degree of under D is at most with bound B.
2. (Chow-concentration) For any function J H. if D&m with Meone. then with probability at least 9/10, we have that for all a E No with ||a|]] S E, [D]f(x) x*)
x (xx x=1 <
Bdd.
3. (Agnostic Learning Algorithm) There exists an algorithm A that takes Mhrain samples from Dirain, runs in time Terains and outputs w.p. least a hypothesis such that IP (x.)))DD'"" 'y + f(x)] < e.
Then, there exists an algorithm that takes Murain labelled samples from the training distribution, O + poly (Meone, d², (oool///0 (18) and TDS learns C. with respect to D up error X e and fails with probability at most 6.
unlabelled test sumples, runs in time Tirain
Proof. Let Dirain be the training distribution with marginal Dirain distribution with marginal equal Let Strain be set of Marain samples from xxy and let X be of meone 1/e² samples from Diest Run Algorithm 2 with inputs Strain, Xtest, A, e, l and B. We now prove it's correctness.
D and let Diest be the test
Soundness We first consider the case when the input distribution is accepted. This happens when Diast accepted by the Chow Matching tester from Algorithm From Theorem C.3, we have that with probability at least 3/4, disc7.Ne (Dirain Dtest) I This probability be boosted to 1 - 8/2 by repeating the Chow matching tester O( log(1/8)) times with independent samples and accepting if and only if majority of the tests accept. Let f* arg min (err(f: Dirain) err D(et)) That is, X err(J", P ( err([";; Dlest). From Definition C.2 and the fact that
disc DDrrain Drest) < e, we have that
P x Dios
(x) # f(x)
I D
(x)
f(x) Se
(C.I)
22

---

We also have that err m S A with probability at least 1 6/2 from the error guarantee of A. We are now ready to bound err Dxy)). We have that
err( D I err( (f=; ;
P
(f()))
+ f(x)]
x~Dx
I err(f f ;xx)))
P x~Di
(x) * f(x)] +E
< eer( ;Dx;)
P |1 (x) + y] +
P (x.
[xxx # v]
(x.))~
S <err(f"; + err( 1 Dxy)) + e S + e +
The first and third inequalities follow from the triangle inequality. The second inequality follows from Equation (C.1). The penultimate inequality follows from the error guarantee of A. The last inequality follows from the definition of X.
This follows immediately from the completeness guarantee of Theorem C.3. As seen before, the success probability can be boosted to 5/2. Thus, the tester accepts when Diset Dirain with probability at least 8/2.
Completeness
Remark C.5. The above theorem completely decouples training and testing. This is in contrast the Klivans et al. 2023 which don't 't make this distinction. In particular, this forces their output hypothesis to be polynomial threshold function. In our theorem, the hypothesis can be any function output by the training algorithm A that achieves low error. This is also in contrast with the other TDS learning algorithms in this paper that require additional structure from the hypothesis output by the training algorithm.
In fact, we can drop Assumption 3 from Theorem C,4 entirely, if we restrict our training algorithm. the following theorem from [KKMS08].
In particular,
Theorem C.6 (Theorem 5 from [KKMS08)). Let 'D be a distribution on X x {+1} for X C Rd with marginal Dx- Let e, E (0, 1). Let C be class of functions such that for all C, there exists polynomials of degree such that Ex~Dxllf(x (x)]] S e. Then there exists an agnostic learning algorithm A that has run time and sample complexity at most poly(d', 1/c, log(1/6) that oulputs hypothesis I such that with probability at least 1 - 6, we have that
Iy + f(x)) S inf P [f()) (x,9)~
P
P +y
SEC (x:9)~>
Armed with this, we give our end end result that Lı sandwiching implies TDS learning.
Theorem C.7 (an-swnwwinhing implies TDS learning). Let DD be distribution over a set X C Rd. Let C S (X' { be a concept class. Let e, E (0,1). Let H (=1)x. Assume that the following are true.
1. (L1 (Cn-swnwwihhing) The e-approximate Cn sandwiching degree C under D is at most with bound B.
2. (Chov-concentratioo) For any function E H. if ~ Dm with m 2 Moonee then with probability at least 9/10, we have that for all a E Nd with ||a]]] S L, [BD](x) x*]
x [x) x*1
BdZz.
Then, there exists an algorithm that takes poly(d', (//e) labelled samples from the training distribution, O (Meone + 1/e2) log(1/5)) unlabelled test samples, runs time poly (Meoney d' , L, log(1/1)) and TDS learns C with respect to D up to error X + opt + e and fails with probability at most ò.
Proof. Observe that L sandwiching polynomials are also L, approximating polynomials. Thus, satisfies the requirements of Theorem C.6. Thus, the algorithm from Theorem C.6. The proof of correctness follows from Algorithm
run Algorithm 2 with A instantiated to be
We now argue that when Dirain E [Unif[=1]' [Na). then we have that Assumption 2 of Theo- rem C.4 is always true with Moone S poly (d B/e).
23

---

Lemma C.8. Let E {Unif{+1)* Na). Let f be function taking values in {=1}. Let E N. Let X Dmmenne for Moone 2 poly(d (d' /e). Then, with probability atleast 9/10 over S, we have that for all a E N with ||a|1 I
[lf(x) x²1 - -x(((x) x²1 Se.
Proof. For E Nº, let 2 Bxlf(x) x=1 be the empirical mean the samples. Let Z Ep [x[ be the true mean. Clearly, [x [ Z. Thus, we have that Px Px| 7 2 Varx [2] We have that Varx [2]
e²
Var[f(x) x= We have that Varlf(x) x - Ex[x2a] from the fact that f takes values in {+1}. When D Unif x2n 1. When D Na. we have that
Ep 2x I poly(d") (see Proposition 2.5.2 [Ver18]). Thus, Thus, choosing Mcone poly(d' (d /c), we
have that Px Z c) बमा Taking union bound over all E No completes the proof. A
Applying Theorem C.7, Lemma C.8 and the bounds on the sandwiching degrees (Lemmas B.13, 1.14 and B.17) from Appendix B.2, immediately get the following results on TDS learning as corollaries.
Corollary C.9 (TDS learning for degree PTFs with respect to Unif{ or Na). Let C be the class of degree-2 PTFs. Let > 0 and f (11/e)) Then, there exists an algorithm that runs in time (0 and TDS learning C with respect to
or Na with error at most opt + X + C. Corollary C.10 (TDS learning for depth-t ACa). Let C be the class of depth-t tt ACo circuits of size on (=1]d. Let > and = (log s)0(0) (1/))))) Then, there exists an algorithm that runs in time (o(() and TDS learning C with respect to Unif (=1 with error at most opt + +
D Cylindrical Grids Tester
We focus functions whose values only depend the projection of the input on some low- dimensional subspace, i.e., we focus on the class of subspace juntas, which is formally defined as follows.
Definition D.1 (Subspace Junta). We say that function f Rd + {+1} } is k-subspace junta if there exists W E Rexd with [[]]]2 and WWT In as well as function F R + {+1} such that
f(x fw (x) F(Wx) for any RRd
Since such functions only depend on a low-dimensional subspace, one might hope to exploit this property obtain more efficient discrepancy testers. However, the relevant subspaces of different subspace juntas can be completely different and the low dimensional structure of a class of subspace juntas does not seem enough to provide significant improvements for global discrepancy testing. Nevertheless, turns out that testing the localized discrepancy with respect to notion of subspace neighborhood can be benefited by the low-dimensional structure. In particular, define the notion of subspace neighborhood as follows.
Definition D.2 (Subspace Neighborhood), Let H be the class of k-subspace juntas (see Definition D.1) and C be some concept class. We define the (Ya, To) -euussuae neighborhood N, H - PCw(C) as follows for any f = Jv E
N (fv) (fw E C|IW Vlla S Yo and IP If)(() N
# f(x)) s re)
To design efficient testers for localized discrepancy in terms of the subspace neighborhood, we also the notion of boundary of concepts and require the boundaries be smooth, meaning that the measure of the region close to the boundaries scales proportionally to its thickness. Formally, we provide the following definitions.
Definition D.3 (Boundary of Concept). Let F R* +
{+1} some concept. For 0, we denote O,F the g-boundary of F, i.c., the region {x E I 3z E IR with ||z||a S and F(x+z) * F(x)).

---

Definition D.4 (Smooth Boundary). Let F; IK + {=1}. For 2 1, we say that F has a-smooth boundary with respect to N₁. if for any 0 2
X E 0,F = P 3z ||||| o. o. F(x z) F(x) 0g X-
P
x~
As we will show shortly, the choice of the subspace neighborhood only enables obtaining faster localized discrepancy testers, but also testers that are guaranteed to accept much wider classes of distributions. This is because the properties of the test marginal that need to be tested in order to ensure low localized discrepancy are much simpler, compared to the properties required for global discrepancy. Such properties are not only easy to test, but are also satisfied by more distributions. The structural properties we will require for the completeness criteria of our algorithms are concentration in every direction and anti-concentration structured distributions to be follows.
low-dimensional marginals. More formally, we consider
Definition D.5 (Structured Distributions). For pe N + R Mac R4 RL, ki d N with k S d, we say that the distribution over I2 is (Mex -strucuue on k-dimensions (W.rt. Nss, the following are true.
1. (Concentration) For any v E S and E N, we have Ex [(v x) S pc(P).
2. (Anti-concentratioo)) For any subspace U of dimension k, if Q is the density of the marginal of 'D U we have 2(x) []a)(I) for any x E Ik* with |x||2 < R.
(x)
Moreover, if k = d, we simply say that D is (Me:Mac)-stmunne sttructured.
Remark D.6. We note that the two conditions of Definition D.5 are not always independent. For example, if Mae(I]) = (1). then the distribution Q of condition is subgaussian, which implies bound on (e(p) for all E N (i.e., implies some version of condition 1). However, the anti- concentration condition does not always imply the concentration condition (e.g.. (ac( = ((e"²(2)) (2)) and both conditions are important.
For example, isotropic log- concaee distributions are structured on k-dimensions with pc(p) S (O(p))²r and (ac(R) = (O(k))* (xc)))))xxx())))))))) B²).
D.1 Discrepancy Testing Result
We now provide our main localized discrepancy testing result for subspace juntas with smooth boundaries, where we use some free parameters R. p that can be chosen according to how structured the target accepted class of distribution is.
Theorem D.7 (Discrepancy Testing through Cylindrical Grids). Let pe - R21, Pac R.
R21, E N, R, ā 2 and Ts, To E (0, 1). Let also H (resp. C) be class whose elements are k-subspace juntas over Rd with 7-smooth (resp. o-smooth) boundaries. Consider TB to be the class of distributions over Rdd that are (Jes Pac) -atrutstruttured on k-dimensions and N₂ H. - Pow (C) the (%),, (e..te))oe -eu-supce neighborhood. For any E (0, 1). there is (N,, Vp + c)-tester (Algorithm 3) for localized discrepancy from Na with respect to with sample complexity
10p=(2)) dt [no(1]]
P (p)
14k(v27 (xp((1)"))) In( 3R) + O())) and time complexity O(md3 + mdd(([ where Mue (Rvk))
7
28 V (P((1)/ and the ervor parameter up is
3.
14k R2p
2kR22 po In Hao (RVK)) 1 Mac(RVVkooy + 2pac (RVB)ye Hp(p)
3
+ +12
2pac(RVR))
For different target distribution classes we obtain different results, that reveal trade-off between universality and the size of the subspace neighborhood tested. To accept wider classes of distribu- tions, we restrict to testing localized discrepancy with respect to narrower neighborhoods, which parameterized by 7s and %ee in the following corollary. Eventually, for applications in TDS learning, this will result into requiring the training algorithm to provide stronger error guarantees by using more training examples and time.
25

---

Algorithm 3: Cylindrical Grids Tester
Set X of points in RR matrix V E RR parameters p E N, R 1 0 Compute the matrix M Xx~x [x '] and reject if the largest eigenvalue is larger than 2n (1).
Input:
Compute the quantity Px~xX ||| [x x > R| and reject if the value is larger than (p) R
I
-1, 0, ................................ . R 1 and consider the grid GI {li1n, (i1 1)n] x x... 1., (ix- 1)m] i1, f,.-.., d I}
for each grid cell G E n do Compute the quantity P Vx G] and reject if the value is larger than
24a (Ryk) Px~N(VXE
end
Otherwise, accept.
Corollary D.S. Let E 1), let H,C, o, ō be as in Theorem D.7 and let N, H + Pow(C) be the (Tan7 subbpacee neighborhood (on k dimensions). For a class of distributions D over RR, there is (N eleste for localized discrepancy from Na with respect to ID in each of the following cases for appropriately large universal constants C1 C2 2 1.
1. mD = (Na), 07s S To S (0(R) (o))())
The tester has time and sample complexity
2. ID is the class of C-subgaussian and isotropic log-concave measures over Rd for some
C == =O((1 and a% S % S (g) The tester has time and sample complexity (oly())(+)000))
3. ID is the class of isotropic log-concave measures over Ted and also a7ss S Ye I (2))-Cak 1og2 (1/6) The tester has time and sample complexity
poly(d) log (o0)+.
4. TD is the class of distributions over RRd that are (Je, -sttucuueee on k-dimensions, with me(2)= < C and (R)(R) S Ck2² et12 for some C = 0(1) and o7 S Yo S (t))
The tester has time and sample complexity poly (1)) (oō)..
Proof. To apply Theorem D.7 in each case, it suffices to show bounds for (e(p) and Mao RRyk) for each of the choices for D. We then pick p log(1/e) in Cases 1,2 and and p 1 in Case 4 and R sufficiently small to achieve error guarantee c. For Case 1, (p( S (Cp)² and Mac Mac (Rvk) S For
case 2, (p) & (2Cp)' and Mae (Rvk) < ( Finally, for Case 3, mc(p) S (Cp)²² 2p and Moo (Rv)) < (C /2, These bounds follow from properties of log-concave and subgaussian distributions (see, c.g., [LV07, Ver18)).
In order to prove Theorem D.7, we first provide tester which can certify that the mass assigned by the tested distribution to the region near the boundary of any function with smooth boundary bounded. Structured distributions (Definition D.5) indeed have this property and the proposed tester can certify it universally over the class of such distributions.
This can be done by considering cover the now-dimensional space by grid of bounded size and checking whether the probability falling within each of the grid cells is appropriately bounded. To account for grid cells that are far from the origin, it suffices to check that the tested distribution is sufficiently concentrated. If these tests pass, then we have certificate that the mass of the tested distribution close to the boundary of any smooth function is appropriately bounded, because such regions can covered by the union of a relatively small number of grid cells (see Figure 2).
Lemma D.9 (Grids Tester). Let Pr : N RR,, Paa R. - RR,, p E N, R, 2 and Q E (0, 1). There is tester T which, upon receiving set X of vectors in B., and in time XI| (0( RVE )) either accepts rejects and satisfies the following.
8
26

---

(a) (Soundness.) I accepts, then.for any F FB + {+1} with a-smooth boundary we have x 0,F - R2
2kp
P x
+ 40 Mao
(b) (Completeness.) If X consists of at least 12 kp
14k(3W22k expp/ In (2Rk) i.i.d. exam- (Rr(R)))
ples from some (Per (aaee--ssrucuure distribution over R then T accepts with probability at least 99%.
Proof. Let 17 = 2 be some parameter, = {- R -,,0 ........ _ - 1} be set of indices 3vk
and R {[inn, (i1 + 1)ml x ... [i,,, (4x + 1)ml ......, d E I} the corresponding finite grid with cell length (each cell corresponds to hypercube in R2 the cartesian product of intervals each length 77). The tester does the following.
1. Computes the quantity [x R] and rejects if the computed value larger than (p))(p)
R
2. For each cell G in the grid Sy,n, computes the quantity X G] and rejects if the computed value is x [x E G] 2paclRVb Px~Ni e G].
3. Otherwise, the tester accepts.
Soundness. Suppose that the tester has accepted. This means that the quantities xx>x|||x]]s> > R] and xx G] appropriately bounded (for any G E 9n Let F be any function with a-smooth boundary with respect to Ni.
Consider ğ S R to the set of grid cells that have non-empty intersection with the set FzF (see Definition D.3), i.e., == {G E 9 G * 0}. Observe that x E F₂F then either ||x||> > R. or x E G for some G E G. because the grid covers the set {x ||x|| < R}. Moreover, if x E G, then there is a point y E 9 n m0 F that falls in the same cell as and, therefore, ||x yl12 S k because each cell has length y7. This implies that 0 We overall have the following (see also Figure 2).
0fF (x: |x RJ c U GCCPP where ū= e n
(D.I)
GEG
0,F
0,F GeG
Fix)
F(x) =1
Figure 2: Discretization of smooth boundary
27

---

Combining the first inclusion in expression (D.1) with the fact that the tester has accepted, the quantity Fx-x [x F) is bounded as follows.
P xxx
x E F
x 11x >
P.
Rj
EXPXEE
x
GEG
2kH R
22pao (Pvo
Σ
P. [ G) xmoV
GEO
For any G. G' Ô with G * G², the events that G and that G' mutually exclusive. Therefore Eces Px~Ni xx E G] = Px |x E G] S Px [x E 0,Fi, where the final inequality follows from the second inclusion expression (D.1). Since F has a-smooth boundary, we have Px~Ni [x E 02P I og. Overall, we have
2kpo(p)
P x 0, S x-x
+ 22
R2Dp
2kp
S
+ M (BV as desired.
Mao
R2p
Completeness. Suppose, now, that the examples X are drawn independently from a (Her Moc)- structured distribution Q. We first show that, with probability at least 1 200 we have I X |||
R] < (p)
125
We first bound the quantity IP Px~ |||x||oo
R]. by using Markov's inequality as follows.
P x
||x||>>0
R.
sup P
lIv x
> R.
vegi-1 x-
supvest-1 Ex~el(v 2 R2v
kpp(P)
since Q is structured. R2p
By the multiplicative Chernoff bound with probability at least exp(-IX
10 we have that P X [|x/| > R| 2P 2x > R (u)(() 2
200 since |X] kpo(p)
12R
We will show that for each G E Gy Px~x (x E GJ S 2pac (RVA) Panmi [x G). with probability
at least 1 exe(pp |X| Mao (aoo(R/))r (22me" 12 )b). The desired result then follows by a union bound over Gn (where 1r, & (3R/1)** and the fact that |X| 2
14k(y27 )*²2))) In (2R).
(Ro(RrR)
We first bound Px-o/x E G] as follows by using the fact that Q is structured and ||x||2 S ||x| S RV Te for all x E G (because G R.
/ N(x) dx Mac (RVk)
P
x E G
SXEG 2(x) dx (RV XxeG
IP P
xm x
By the multiplicative Chernoff bound, we once more have that Px>xX E G7 S 21 G] with probability at least 1 -exp(- [X]
Mao (RVK) Px~v(x G!) and conclude the proof by observing
that P.x [x E G exp exP )k
Remark D.10. We note that Lemma D.9 is not specialized to the Gaussian distribution. The only requirement that the distribution of the completeness criterion is structured with respect to the same distribution for which the functions F' of the soundness criterion have smooth boundary. In particular, in Definition D.5, the anti-concentration condition 2 is defined with respect to the Gaussian, but could also be defined with respect to some other distribution. The concentration condition is always the same.
We use the version of the Chernoff bound that uses an upper bound on the expectation rather than the exact value, through standard coupling argument.
28

---

3/E We are now ready to prove Theorem D.7. The idea is that if a function f lies within the subspace neighborhood of another function f. then the disagreement region between the two functions is bounded by the union of: (1) their disagreement after projecting the relevant subspace for I (since the subspace is known, it can be tested exhaustively, similarly to Lemma D.9) and (2) the region far from the origin (for which testing concentration suffices).
Proof of Theorem D.7. Let D' be the unknown distribution and X a set of m i.idd samples from D' and let 17 = // DR (see Definition 1.1). We run Algorithm 3 with input (X, V. p. R. n) and accept (or reject) accordingly.
pe(p)" Let Xfv be an instance of the localized discepancy testing problem
Me(l)
Soundness. Suppose that the algorithm accepts. We will show that xxx (f(xx(((x) * f(x)] & v for any f f (.. Since the event that f(x) * f(x) is independent for each x X, we may apply the Hoeffding bound show that PX-D'
f(x)] S & c with probability at least 3/4 whenever [X] 2 3. To bound the empirical quantity, we have the following, for R. RP (v (1) and @ = R.
P [F(Wx) + F(Vx)] x~x
P [F(Wx) + F(Vx)] P [F(Xx) # F(Vx)] x-x
A
For the term Pl, we observe that F(Wx) F((W -V)x + Vx) and therefore
Pi P (I - v) 2 7. R,) R.) x-x
P Ez R ||z||2 S Y, F(Vx x F(Vx))
x-X P (W x-X
x-X
P.Vx Vx E 0., R,
By applying Chebyshev's 's inequality for the first term in the above expression and Lemma D.9 for the second term (note that we have chosen S R.R, and Algorithm 3 runs the tester corresponding to Lemma D.9), we obtain the following bound for P1 (recall that | WW Vlla S % and II(W V)xl1a S
||W - V ||2l proje x||2, where U is the span of the columns of the matrix W - V).
k ksupvega- Ex~x[(v - x)2]
2kp 40%y RyPac (spaa(RVK))
Pi <
+
R
R2v
2kpp((1)
2kp((()
+
+ 400% RaMPR
R3
Rap
The last inequality follows from the spectral bound the empirical covariance matrix M Ex [xx implied by Algorithm 3 upon acceptance.
For the term Pz, consider the set of grid cells 9 with non-zero intersection with the disagreement region, i.e., ğ = {G E Gn : there is x with Vx E G and F(Vx) + F(Vx)). Recall that = mvK and let G. be the interior part of G. i.c., Im -G E G for any x with Vx e G' we have F(Vx) * F(Vx))).
Let x be such that || Vx|lo= R. F(Vx) F(VX) and Vx & U.FUU.FF. It must be that Vx lies within some grid cell in 9m. To see this, note that Vx must be exactly one grid cell G in & (by definition of 9) and this grid cell was in ② Gmm. this would imply that for some x' with Vx e G we would have either F(Vx) * F(Vx') ) or F(Vx) + F(Vx') (because F, F disagree on Vx but agree on Vx'), However, ||Vx - Vx S nvK = g. because they are in the same grid cell and we conclude that Vx E F U U.FF which is a contradiction. Overall, we have the following.
P₂ S
P x-xX
|X| > R +
P
Vx
0,F
P IVX 0, Σ
P x
G
x
x
GEG
Pa1
Piz
Prs
P24
29

---

For the term P21, we use the bound implied by Algorithm 3, for the terms P22. P23 we apply Lemma D.9 and for the term P24. we use the fact that (upon acceptance) Px- [Vx E G] Px) E G] to obtain the following.
P2s S 2pac (Rv))
Σ PP
P
x
GE
S 2pc (RVA) P [F(x)) # F(Vx))
We bound the quantity Px--N (F((x) + F(Vx)] as follows.
x (F(x)) +
F(Vx) S P (F(W)) + F(V))] + F. (F((x) + F(Vx) X
x
Se + x
P lll(W V)x > 7OR'I + P E
X-
%% + 4ke
2n
where the last inequality follows from Gaussian concentration and the fact that F has o-smooth boundary. By choosing R' (2k In(
R pndl (RvR)
)) 1)1/2
obtain that
Pc(p)
4kpo(p)
1800 pacl (ac((a)) (R(B)) 1/2
P24 S 2aa RV RRK)y +
20 RVk) 2k In Rap
(c(p)
Overall, for the term P2 we have the following bound.
10kspo(p) P2 <
2kHo(11)
+ 100 R2" V Help)
Ma
(RVK) (In pao pao (ac(RR + 2NoMaa (Rviaao(/// (Rvk)
1220
Combining the bounds for P1 and P2, we obtain the desired result.
Completeness. Suppose, now, that D' E D. It suffices to show that all the tests will accept with probability at least 3/4. For the quantity x Px~x E G). we apply the Chernoff Bound as described in the proof of completeness of the grid tester (see the proof of Lemma D.9). For the quantity M = Ex x [xxx] J. we use the Chebyshev's
R as well as the quantities
inequality on each of the random variables Mij Xx [x;x)], the fact that E[M3]] S (2(2) and union bound over j E [d].
D.2 Application to TDS Learning
Interestingly, in learning theory, there are algorithms that are guaranteed to recover the relevant subspace for certain classes of subspace juntas that have some additional properties. This enables us to use the discrepancy tester of Theorem D.7 to obtain end-to-end results for TDS learning, because the training phase can guarantee that the ground truth lies within the subspace neighborhood of the output hypothesis f. for which we have efficient localized discrepancy testers. Here, we present TDS learning result for balanced convex subspace juntas in the realizable setting. The class of balanced convex subspace juntas defined as follows.
Definition D.11 (Balanced Convex Subspace Juntas). A concept f: Rd - convex k-subspace junta if it is B-balanced (see Definition A.1), convex and a k-subspace junta (see Definition D.
(+1) is a 3-balanced
We make use of known algorithms from PAC learning that are guaranteed approximately recover the effective ground-truth subspace in terms of geometric distance, which is important since the tester of Theorem D.7 works with respect to the subspace neighborhood and obtain the following theorem, which underlines a trade-off between training time and universality.
Theorem D.12 (TDS Learning of Convex Subspace Juntas). For 10,1/2), d, k E N, let C be the class of 3-balanced convex k-subspace juntas over Rdd For any e E (0, 1), there a (decoupled) c-TDS learner for C with respect to Na in the realizable setting, which, for the learning phase, uses poly(d){ (poly(k/e) ( samples and time and, for the testing phase, uses poly (ol//d)k//)) Olk samples and time. Moreover, in the same setting, there is a TD-universal e-TDS learner for C for each of the cases listed in Table 2.
30

---

Class over R=
Training Time and Samples
Testing Time and Samples
I-subgaussian & Isotropic Log-Concave
poly(d) )
poly(d)(k/<c0003)
2
Isotropic Log- Log-Concave
poly(d) ( 2 mnft
poly(d))O(("1og log (1/e))
Fourth Moments Bound:
[V((v
x) S C & Dimension-k Marginals
poly(d) (2
poly(d)xow//3
Density Bound: C*²²
Table Specifications for D-universal (e, d)-TDS learning of 3-balanced convex k-subspace juntas. The properties that define the class DD in line 3. hold for some given universal constant C > 1, for all members of D, for all v IRd and the density bound holds for any projection on some k-dimensional subspace of any member of D.
In order to obtain TDS learner for some class C, one might hope to learn hypothesis f during the training phase, such that the subspace neighborhood of f (see Definition D.2) contains the ground truth. Then, the test error can be bounded simply by rumning the localized discrepancy tester of Theorem D.7, assuming that both and the class C. have smooth boundaries. In Appendix B. we show that, indeed, convex subspace juntas have smooth boundaries. However, for the learning guarantee, prior work in standard PAC learning implicitly provides the following weaker guarantee regarding subspace retrieval for convex subspace juntas, which, as we show, is, nevertheless, still sufficient for our purposes.
Theorem D.13 (Implicit in [Vem 00], see also [KSV24a])- For any 7 E (0, 1), B 10,,, there an algorithm that, upon receiving a number of ii.d. examples from No. labeled by some 3-balanced poly(d(())ool/// and returns, w.p. ar least 0.99, some polynomial q IR. - {+1} of degree at most poly(k/11) and some V E Bexd with VVT Ig such that the following are true for the hypothesis f(x) sigu(ğ(Vx)) x)) and some f(x) = F (WWx) with WWT Ig.
convex k- k-subspace junta f (x) F* (W**), runs in time poly(d) polly(k/1)
(a) f No(f). where N. is the k-dimensional - -tssspcee neighborhood, i.e., IW Vl2 y and (x + f(x)) S n.
(b) For any E Rd with | 1xll2 Vk/r, we have f(x) fx)
We are now ready prove Theorem D.12.
Proof of Theorem D.12. Our plan is to combine Theorem D.7 with Theorem D.13. We will use an additional test, account for the fact that Theorem D.13 does provide exact subspace recovery, but, rather, recovery of the effectively relevant subspace (see Item (b)).
Suppose that the training distribution Dirain has marginal Dirain Na and that the labels (both in training and in test distribution Diast well) are generated by some 3-balanced convex k-subspace junta f R2 + [+1], where (x) ("("*x) for some W* E Rxd with W W*W*T Ts-
Learning Phase. The learner runs the algorithm of Theorem D.13 for 7 chosen so that the error parameter e'(x)) of Theorem D.7 is most é' e/3 using labeled examples from D and
computes f(x) = sign(ğ(Vxx) with the corresponding specifications. For the particular choice of see Corollary D.8, where poly (k) according Lemma B.8.
Testing Phase. The tester first computes the maximum eigenvalue of the matrix Ex-XX [xx T] using samples X drawn from Diet and rejects if the quantity larger than Then, the tester runs the localized discrepancy tester of Theorem D.7 and rejects accepts accordingly.
31

---

Testing Run-Time. To bound the testing run-time we use Corollary D.8, where o - poly(k) (because C is the class of convex subspace juntas and due Lemma B.8) and poly(k/?). because f a polynomial threshold function of degree poly(k/7) and, therefore, has poly(k/77) smooth boundary according Lemma B.I.
Soundness. If the tester accepts and [eest > poly(1/e), then we have PX [ >
Vh/2l S P Xxex l| x||2 > vh/7l + e/6 (by the Hoeffding bound) and P Px (I [|'x> /k/ S 2y < <//6 6 for I e/12. Hence, overall, by combining Theorem D.13 with the guarantees from the fact that the testing phase has accepted, we have
crr(f: or(f:Dxx) Dxy)) = I (x) * f(x)]
xwDxy
IP
|| [| x|2>> vk/7l + P
M.DDpunl [f(x) # f(x)]
xwDx
xnD
p
[f(x) # f(x)] +
3 x~Na
$ + +
3
where we used the soundness property of the cylindrical grids tester (Theorem D.7 and Corollary D.8) and the fact that f is hypothesis with the properties specified in Theorem D.13 and, in particular, lies within the subspace neighborhood of f.
Completeness. Combine the completeness guarantee of Theorem D.7 and the fact that Ex-X [xxx] has, with probability at least 0.99, bounded maximum eigenvalue whenever Diest lies within DD (for any D in Table 2) and |Suet| 2 poly(d).
E Testing Boundary Proximity
We now focus on classes of low-dimensional concepts (see Definition D.1) that are locally structured. In particular, we consider subspace juntas that are locally balanced, meaning that near any point x in the domain, there are several points with the same label as x. This condition is important to ensure that there are, for example, zero measure regions over the (Gaussian) training distribution that contain significant information about the ground truth. We will show that this condition actually enables significant improvements for the testing runtime for TDS learning. More formally, we give the following definition.
Definition E.1 (Locally Balanced Concepts). For 2 and r, E (0, 1), we say that a function F R + {+1} is (Rocclly 3-balanced if for any e S r and R& with |x||2 R, the following is true.
[F(z) = F(x) 2 E B& e)] 3
z~N,,
For subspace junta f(x) F(Wx), we say that f is (R, loocally 6-balanced on the relevant subspace if F is (R, -loocalyy 3-balanced.
For locally balanced concepts, it is possible to obtain efficient localized discrepancy testers with respect to the disagreement neighborhood, i.e., the neighborhood of concepts that have low disagree- ment with the reference hypothesis f under the Gaussian distribution (or, in general, the reference distribution at hand).
Definition E.2 (Disagreement Neighborhood). Let H and be some concept classes. We define the (Gaussian) %e de-dissgreement neighborhood N H - Pow(C) as follows for any f E H.
N = (f CI P. Ix((() # f(x)) S 7e3
We also define the boundary proximity tester, which directly tests whether the probability of falling close to the boundary of some reference hypothesis is appropriately bounded. This testing problem can be solved efficiently, for example, for the fundamental class of halfspace intersections.
32

---

Definition E.3 (Boundary Proximity Tester). For For 1,0 e (0, 1). let H. be some class of functions from Rd to {+1) and let ID be some class of distributions over R2. The tester T is called a (e, -) boundary proximity tester for H with respect to ID if, upon receiving some ʃ E H and set X of points in R?, the tester either accepts or rejects and satisfies the following.
(a) (Soundness.) If accepts, then Px~x|e [x E 0gfl S ōg.
(b) (Completeness.) If X consists of (at least) mt i.id. examples from some distribution in D, then the tester T accepts with probability at least 99%.
Note that the complexity of boundary proximity testing depends on the simplicity of f and, therefore, considering applications in TDS learning, where f is the output of the learning algorithm, highlights the importance of proper learning algorithms that output some simple hypothesis with low error. Since the hypothesis is simple, dissareemeent-lcalliee is low, the ground truth is likely within the disagreement neighborhood and disagreemeent-ocallize discrepancy testing suffices to guarantee low test error.
discrepancy testing is tractable and since its error
E.1 Discrepancy Testing Result
In order to obtain a localized discrepancy tester assuming access to a boundary proximity tester, we first show simple proposition connecting local balance condition with boundary proximity testing. In particular, if two functions have low Gaussian disagreement, but one of them is locally balanced, then all of the points of disagreement are either close the boundary of the other function, or far from the origin.
Proposition E.4 (Localization of Disagreement from Locally Balanced Concepts). Let F, F R& + {+1}, where F is (R, e)-ocaly 3-balanced and F, F have disagreement 7 = (x, e)}. i.e, [F()) + F(z)) S Then, for any x with ||x||2 S R
iin |x Pa-Nill P and F(x) + Fxx), we have x E O.F.
Proof of Proposition E.4. Suppose, for contradiction, that there exists some x E R with ||x|| s R and F(x) + F(x), for which x & F.F. Then, it must be that F(z) = F(x) for all z E B, 0) (otherwise, x OgF). We have that Pe-Ni [F(z) + F(z)] > Pe- [z E Bx 2) and F(z) + F(z)] and also Fzz) * F(z) is equivalent F(z) * F(x) (because F(z) F(x)). which, in turn, is equivalent to F(z) = F(x) (because F(x) * F(x)). Overall, Pe-AV [F(z) + F(z)]
Pa-Ni [z E (x g) and F F(z) Fxx)] % by assumption, and reached contradiction.
Remark E.5. Note that Proposition E,4 is not specialized to the Gaussian disagreement between and F, but would also work for any distribution Q, if the local balance (Definition E.1) was also defined w.r.t. Q.
We combine the boundary proximity tester with a moment matching tester for concentration (to bound the probability of falling far from the origin) to obtain non-universal localized discrepancy tester (Theorem E.6). we instead use a spectral tester for concentration, we obtain a universal localized discrepancy tester (Theorem E.7).
Theorem E.6 (Discrepancy Testing through Boundary Proximity). Letp E N, R r, (0,1) and 0 < 7e < e -2R? Let also H. and C be classes whose elements are k-subspace juntas over ad and N H. - Pow(C) the re-disagreement neighborhood. Assume that the elements of C are (R, ri-locallyy 3-balanced on the relevant subspaces and let T be a (e, --bbunddryy proximity tester for H. w.r.t. Na. requiring my samples, with (2g // //e22) 2 For any (0, 1), there is (Ne, 1h e)-tester for localized discrepancy from Na with respect to Na with sample complexity m = my + Odd)) + O that calls T once and uses additional time O Ommd2+1) where the
error parameter v/
4kp R2
Ve exp(2R2)
1/k
+b = 2
+ōVk
1
33

---

(2kd) and let (f.X) be an instance of the localized discrepancy problem (see Definition 1.1). The algorithm does the following.
Proof of Theorem E. Let = (1e // exp(2222/)))) A
1. For each a E Na with ||a]] S 2p. compute the quantities Ma = Ex x xxx] = E x [[T x and reject if for some a as such, we have MMa -x (xxwv(>>]]]> A.
2. Run the boundary proximity tester T with inputs (e. (x) and reject if 7 rejects.
3. Otherwise, accept.
Soundness. Assume, first, that all of the tests have passed. We will show that for any S E N.()). we have Fx~x + [(x]] S 1b. Since the event that f(x) + f(x is independent for each x E X, we may apply the Hoeffding bound to show that PXx-D= * f(x)] s & + e with probability at least 3/4 whenever | 2 2. Since f and f are k-subspace juntas, we have that f(x) = F(Wx) and f(x) = F(Vx) for W.V V E R so that WWT = VVV = I.- Let U E 222 be a matrix such that UU = I2k and the span of the rows of U contains the span of the rows of W and of V taken together. This, together with the fact that WWT = Ig. imply that for any x E Rd we have Wx = WU Ux and. similarly, Vx VU Ux (the part of x that falls within the subspace spanned by the rows of W does not change by applying the projection matrix U UTU U and the remaining part irrelevant). Moreover, we have that |U]|2 = |UT 2|2 = [ = [V
Let
(((z) = F(WU 2) and (z) = ((VUTz).
We have that Ixx [x + [(X)))] S Te. by assumption. By Proposition E.4, applied on F", Fr, and since %o S 9r e-R", we have that for any x E Te such that F'(Ux) # F'(Ux) (i.... F(Wx)= * F(Vx))) at least one of the following is true: (a) ||Ux||2 2 R (b) Ux 0,F". According to Proposition E.8, Ux E Ogl" implies that TU E 0gf² which, in turn, implies that Vx E 0₂F, F, since Vx= = VUT Ux and therefore, by Proposition E.8 we also have that x E 0gf. Therefore, overall, we have
P x I(()) + f(x)] S TP 11Ux|12 2 R]+ P P P x-X
x~X
In order bound the term Px~x [|| 2 R), use the fact that the test of step I of the al- gorithm has passed. In particular, by applying Markov's inequality appropriately, we obtain that Fx-x [x-x/ 2 R] I Rer Ex=xl]Uxx 1. Note that the expression ||Ux||²" corresponds to a polynomial of degree at most 2p and corresponding coefficient vector whose absolute (E1) norm have that (for all E Rd) ||Ux||2" = Eneve Cax"
is bounded by (4kd2)p. In particular, (recall that x Iee x,',, where ELENU |cal I (4k=2)p and Ca whenever ||a=]] > 2p. Therefore, by linearity of expectation, we have Ex~x [ 2 E. ca Ex=x(x]] E. Ca (Exxv/xxx)) + Aa) Ex~v|||Ux||| + Ea Ca where Aal S (2Rd)ap for any a with ||a|| S 2p. Hence, overall, we have Ex~x |||Ux| S Ex Ux| 22 + 1 s 2(4kp)", which implies that Xx~xX||UXX]] 2 R] < 2 (4kp)"
1
For the term P [Vx E 0,F%. Px-x(x E 0 < ōe < 0 Th exp(222) 11/k We have shown that Px-x [x(x + f(x)) S v. as desired.
the fact that the tester T has accepted and hence have
Completeness. Suppose now that X consists of i..dd examples from the Gaussian distribution. Na. To ensure that with probability at least 9/10, the tests of step pass, we pick |X| > (Cdk) for some sufficiently large C. This because the Gaussian moments concentrate (e.g., due to Chebyshev's inequality) well as union bound. For step 2, it suffices that |X] > mT.
We now give our universal discrepancy tester though testing boundary proximity.
Theorem E.7 (Universal Discrepancy Testing through Boundary Proximity). In the setting of Theorem E.6, if the tester T works with respect class ID of distributions over Bd such that for
34

---

some pe 2 1 we have sup ExnD (v-x)] S pefor all D E D, then there is (Ne: (-----teste for localized discrepancy from Na with respect to DD with sample complexity m mT + 20d + 22. that calls T once and uses additional time O(md² + d.), where the enror parameter v5 is
Akpe R²
Ye (ccx((2R)) 1/k
+ =
+ +VVK
Proof of Theorem E.7. Let o = (1e/B)1/k Vh exp(2R2/K and let (f.X) )) be an instance of the localized discrepancy problem (see Definition 1.1). The algorithm is similar to the one used in Theorem E.6, but for the first step. instead of matching low degree moments, we compute the maximum eigenvalue of the second moment matrix.
1. Compute the maximum eigenvalue of the matrix M = Ex~x [xx and reject if the computed value is larger than 2p
2. Run the boundary proximity tester T with inputs (e. f.X) and reject if T rejects.
3. Otherwise, accept.
Soundness. For the proof of soundness, we use similar argument the one for Theorem E.6, but we instead bound the term x [1| for p and as follows
E x
Σ E x) 2k sup E (v [v](vx)) 4kpe x
vegé-1 rEgé-1XEX" XEX
where u' denotes the vector corresponding the i-th row Uf
Completeness. The completeness for step I follows by an application of Chebyshev's inequality to the random variables corresponding to each of the entries of the matrix and a union bound, to show that the Frobenius norm (and hence the operator norm) of the matrix M - Exx< xxx 1 is sufficiently small (where D is some distribution in ID and X consists independent draws from D).
In the proofs of Theorems E.6 and E.7 we have used the following usedul proposition. Proposition E.8. Let ff ::R" Rd + {1 be a k-subspace junta, i.e., f(x) = F(Wx), where F R + {+1} and W E exd with WWT T It. Then, we have x E 0g if and only if Wx E O.F.
Proof. Note, first that since WWT 4 and le S d, have that ||W]|2 1. Consider E O,S. Then, by Definition D.3, we have that there exists z Rd with ||z|| e and f(x + z) * f(x). Note that for the same x and z we have F(Wx x + Wz) + F(Wx). Since | WWll2 = 1, we have that ||Zz|] 2||2 < ||z||a < g. Let ă = Wz E Rt. We have | 22 I 0 and F(Wx + 2) * F(Wx), i.e.,
Wx E o.F.
For the other direction, suppose that Wx E O.F. Then, there is ž E R with || S o such that
F(Wx + ž) * F(Wx). We have that 2 = 1,2 = WW 2. Let z = W 2. We have ă = W z and
| 2 = | 2||2 < || ||2 2 ||||2| S e. We have that f(x + 2) = F(Wx + Wz)
F(Wx 2) F(Wx) f(x). Hence, Ö.5.
E.2 Application to TDS Learning
We now focus on the class balanced intersections of halfspaces, which formally defined as follows.
Definition E.9 (Balanced Halfspace Intersections). A concept f: Rdd + {+1) is called 3-balanced intersection of k halfspaces if it is 3-balanced (see Definition A.1) and there are w w2 w2...., w E
gd-1 and 71, . Tk I. such that f(x) II 1(w' n for all Rdd
35

---

We will now combine Theorems E.6 and E.7 with results from robust learning ([DKS18b) to obtain the following theorem regarding TDS learning balanced intersections of halfspaces with respect to Gaussian training marginals. Our results indicate a trade-off between the training runtime and testing runtime and are robust to some amount of noise (in terms the parameter A).
Theorem E.10 (TDS Learning of Balanced Halfspace Intersections). For B (0,1/2), d, E N, let
be the class of B-balanced intersections of k halfspaces R For any e E (0.1) with c = O ((2)), there is a D-universal 4/-TSS learner for w.r.l. Na in the agnostic setting for each of the cases listed in Table 3.
Class DD over Rd
Training Time
Testing Time
Error Guarantee de
Gaussian Na
( )o(k))
(dk)o(lo((/ee)
)00) +E
Fourth Moments Bound:
B[(( x) S [ / & Dimension-1 Marginal
( poly(d, k, 1/c)
( (1020())) +
Densities Bounded by C'
Table 3: Specifications for D-universal 4TTDS learning of 3-balanced k-halfspace intersections. The properties that define the class W in line 2, hold for some given universal constant C' 2 1, for all members of ID, for all v E IRd and the density bound holds for all one-dimensional projections of any member of IDD
For the learning phase of the algorithm of Theorem E. we use an algorithm from [DKS 18b] in the context of learning with nasty noise. Since the algorithm works under nasty noise, will also work in the agnostic setting. The following result follows from [DKS 18B, Theorem 5.1].
Theorem E.11 (Reformulation of Theorem 5.1 in [DKS18b]). Let C be some hypothesis class that consists of intersections of k halfspuces. For any 7 E (0, 1), there is an algorithm that, upon receiving a number of i..d, examples from some labeled distribution Xxy whose marginal is No. runs in time poly(d)( ())00)) and returns, w.p. at least 0.99, some intersection of k halfspaces f: Rd + {=1} such that for any distribution Dieyy over Rdd x (+1), if f E C. is the intersection that achieves À minsec(err(( Di + err(f: D2 then we have f Ne(f), where N is the (CkA 12 + 7) disagreeeel neighborhood (see Definition E.2), where C is some sufficiently large universal constant.
Note that for the above reformulation of Theorem 5.1 in [DKS18b], we used the following reasoning. Their algorithm returns î with the guarantee that err(f: (f: Dirain) S Okoptt 12 ++% where opt minsec (f D25"")) S :
S A. Therefore P PX~N, lf + f*(x)= I Dirsin) +
(rrgf")Dx I CRA +7, which implies that f N
Our plan is to use the discrepancy testers of Theorems E.6 and E.7. To this end, we have to show
that (1) balanced halfspace intersections are locally balanced and (2) there is a boundary proximity tester (see Definition E.3) for the class. turns out that any convex set that is globally balanced (see
Definition A.1), is also locally balanced (see Definition E. we show in the following lemma.
Lemma E.12 (Globally Balanced Convex Sets are Locally Balanced). For B (0, 1), let F
R {+1) be the indicator of a (globally) 8-balanced convex set K. C IRK, let C. > I some sufficiently large universal constant and let R 2 1. Then, F is (R, Cklog k --locally B 3'-balanced for
3' 8¹ 0'exp(-14 Rak D)
Proof of Lemma 12. Let 0 S Thlogh We will first show that for any x E with ||x||| S R and F(x)= = -1, we have PPa-N (F(z) and, therefore, there is separating hyperplane between x and K,, due to the convexity of K. This
8
E (x(x, e) > Je-eR, We have that x g IC
hyperplane does not pass through x and, hence, at least half of Bx e) is outside K. We obtain the
36

---

following.
Pa~Ne [F(z) and z B& Bx ø]
P. [F(z) -1 2 (x((x,)) 2) z^/2
P Pa~NN [2 E (x,(,, e)
( Ø)) in in N (z) BB (x. Q))
(x, Nx(z)
exp( - x + 2)
exp( 1 [|| 0)²
1 |x|2 30RR
For the case where F(x) = 1, we first prove the following claim, which states that when convex set is (globally) balanced, it must contain some Euclidean ball with negligglie mass.
Claim. Since K. is 3-balanced and convex, there is Xe E R such that Bx(Xe,T) E K. where r Chlog ||xe|12 < R. (2kln( ( )2122 and C 2 is sufficiently large universal constant.
g
Proof. Since K. is balanced, we have IP Px~NN [F(x) 1] B. We now use Lemma B.8 to obtain that Px~NG [x 0 F) < r log k. We have the following.
F [F(z) = 1, r]] P x-NN
[F(x) 1 and F(x + 2) = 1, Vz with ||z||2 S rl
x~NN
= P [F(x) = - IP
[((x = and 3z | S r and F(x + 2) + 1]
x
x~Na
> P [F(x)
IP
Ez ||z||2 S and F(x+ z) ن F(x)
x~Vi
X~>,
P [F(x)= = - PP
E O,F
X~Ni
X~N
C
B
> 3 - 2
rk loloogh k:
R²
Moreover, since P Nx |||||| Re] < 4ke
3/2, overall have that
P x~Vi
[F(z) = 1, Vz E (x and ||||| S Rc] > 0
Since the probability of such an x is positive, by the probabilistic method, there is some x, as desired.
We have shown that for some x, with |xel|2 S Re, we have B3 (x(x.,)) C K. Let now x E B& with ||x||2 & R and F(x) = (x E KO). Since IC is convex, if K' is the convex hull of (x] U B3 (x,,))) r). we have 1 C I.. We will show that X'' n (x, contains some cone R' with non-trivial mass (see Figure 3).
Let be any point on the surface of B& (x,x,, r) such that the tangent hyperplane of (x,, r) on passes from x. Then, if we let be the angle yxx,, we have sin f = IIy x x/|l/||x xellz r/llx- - 12,12, because xyx. = π 2/2, by definition of Note that the triangle defined by x, y and x, lies within K" and hence within as well. Since this true for any y as defined above, we have that K. contains rotational cone R with vertex x, angle 0 and height h E []|x Xall2 -r, ||x xall]. Note that the volume of KC' ( [x, @) is decreasing in ||x - x Xel12, as long as o S r. Therefore, we may Xell2 R + R. (which implics that h > 1 e coss 0). Let R' = R (x, g).
assume that ||x
37

---

R'
F(x)
Figure If E K., then there a cone R' C 0x
By observing that R' contains cone of angle height & cos where cos 0 2 1/2 and & 2 R, we overall have the following.
P P [F(z) and Bx e)
P [F(z) z~Ni
1 2 Bx 2)]
Pa~Ni 2 E B& 2)
vol(R')
inf (x. (x.,) g) No.
vol 2))
supzER. (x.2) Nx(2z)
o ( sin 0) k- (2 (A- (k- 1 ((k-1)/2+1)
exp(-9R/2)
e²( (2T//))//2
(sin 0)k
3
E ooRR
R/2
2//o
Ck22 CK2 Rln(1/3))
Combining the two cases considered (F(x) -1 and F(x) 1), obtain the desired result.
Finally, show that there is boundary proximity tester for the class of halfspace intersections.
Lemma E.13 (Boundary Proximity Tester for Halfspace Intersections). Let ID be some class of distributions over & such that for each distribution in 13, any one one-dimensional marginal has density upper bounded by C O. Then, for any o (0,1). there a (g, 3Ck) 3Ck)-boundary proximity tester for the class of intersections of k halfspaces over R&d with time and sample complexity poly (d, 1/
Proof. The tester receives some intersection of halfspaces f = = IT 1(w x- T,} and my samples X from some unknown distribution over TRd and does the following.
1. If for some i E [k] we have Px-x [/x - - Ti S el > 3C'g then reject.
2. Otherwise, accept.
Soundness then follows from the fact that Px~x E 0²fl Σiej Px~xl/w' - S and and
Hoeffding bound. Completeness follows from the fact that under any distribution D in ID, we have
Fx~D|| | x 7/| el S 2C', due the density upper bound in the direction w' and Chernoff bound.
All of the ingredients of the proof of Theorem E.1l are now in place.
Proof of Theorem E.11. The theorem follows by combining either Theorem E.6 Theorem E.7 with Theorem E. Lemma E. and Lemma 1. Note that since the parameter À is unknown the algorithm, we will run the corresponding discrepancy tester (either of Theorem E.6 of Theorem E.7) for all possible values of the parameter (of the discrepancy tester) within an O(e/k²)- net of the interval [0, Ck k where we know that the tester has to accept with high probability (we can amplify the success probability for each fixed value of @ through repetition). We accept if the (amplified) discrepancy tester accepts for the values of @ in the net. total, we will need poly(k: (k, 1/e) repetitions.
8
D
38

---

F NP-Hardness of Global Discrepancy Testing
In this section, we prove that there exist worst case pairs of distributions such that testing the globalized discrepancy between them with respect to the class of halfspaces is hard. These results also extend the class of constant degree polynomial threshol functions. This motivates our study of localized notions of discrepancy. We now define the notion of discrepancy (globalized).
Definition F.1 (Discrepancy). Let DI, D2 be two distributions on IR and let F be a set of boolean functions on IR.. We say that the discrepancy between D₁ and D2 with respect to F, denoted by (Ds, D2) is,
discr(Di D2)
sup f1.f2EF
PP [fi(x) + xnDD
P (1(()) x #1(x)) x- x-
We prove our hardness result by reducing the following problem of learning constant degree PTFs with noise to the problem of identifying if the discrepancy between two distributions is large/small.
Definition F2. For constants > 0, k E N. let PTF-MA(k: <) refers to the following promise problem: Given a set of tuples (x,, Vt Ne(n) where x; Rd and yı E {+1] for all [n]. distinguish between the following two cases:
There exists a halfspace such that n Ex= 1(h(x;) yi 2 c,
For every degree k PTF we have that 3 E.= (g yi s +
This problem known to be NP hard through a reduction from label cover.
Lemma F.3 ([BGS18)). For any constant k E N, e > 0, PTF-MA(K, e) is NP-hard.
Given set C IRd, let Us denote the uniform distribution on that set. We define decision version of the problem of discrepancy testing for which we prove our NP-hardness result.
Definition F.4. For constants > 0 and a class F of boolean functions on IRd let DISC(F, c) be the following promise problem: Given sets S, S" C R2, distinguish between the two cases:
* discy(Us, Us.) 2 1 -
* dUsc Us+) c
We are ready to state and prove result the NP-hardness of DISC(F, c) when F is the class of constant degree polynomial threshold functions.
Theorem F.5. Let k E N and e 0. Let be the class of PTFs of degree k. The problem DISC(F, is NP-hard.
Proof. We give a reduction from PTF-MA(2K, e) to DISC(F, 8E). The input PTF-MA(2K; e) is set of tuples (x,,y: yi (e())) where x; Rdd and y: (+1) for all E [m]. Let S
{x: 2/
+1,i [n]} and S {x; y/ -1, [n]]]. We assume that |
and |
Otherwise, there exists a trivial halfspace(ttaking constant value) that achieves success probability
n
greater than 1 + and this can easily be checked in polynomial time. We say that S+ S
e-unbiased if the above property holds. We now complete the proof by proving the following two claims and using Lemma F.3.
Claim (Completeness). Let St,S be e-umbiased, If there exists a halfspace h such that DE 1fh(x,,) v.)
e, then discr Us ) 8c.
Proof. We have that |s* Px~UUt [h(x)= 1]
IS a
PxwUut [x(x) 0) 2 c. Thus, simplifying
a some terms, we obtain that
S
|S+
[h(x)= 1] |-
1-e5
IP x-U gt
p [h(x) 1] x-U
71
n
n
1
+
[h(x) = 1] -
p
[h(x) = 11) + 3e
2
2
x g
x
39

---

where the last inequality follows from the fact that S are e-umbiased. Thus, we obtain that
(Px-Us+ + [h(x) 1] Ux~Ug- [h(x) 1]) z Se. Let g be the the halfspace that always outputs Clearly, we have that (Us1 Us 2 (UxxUUt st [b(x) # g(x)) xx- (h(x) o g(x))) 2 Sc.
Claim (Soundness). Let S S be e-unbiased. If there exists degree 2k PTF h. such that Di 1(h(x.)= = y.) 2 + c, then (Us---UU S 8c.
Proof. Say (Us+, Us-) Sc. Since F is closed under complements, we obtain without loss of generality that there exist two PTFs hi, l22 of degree d such that Px-UU [/ (x) # h2(x)]
Px~Uig+ (x) * hx)x)]= 2 1/2 + Consider the function g(x) h1 (x) h2(x). We have that is degree 2k PTF. Thus, we obtain that
Σ 71
1
1()(x)
v)
S
[g(x) = -1]
|
P x~Uss
[g(x)
n
X~U
|
|S
[11(x) * h2(x))
(1
F xwli
[11(x)) # h2(x)))
n
x~U
n
1
+
[11(x) h2(x)]
p xulis
[11(x) + h2(xx) -3e 3c
2 2
XxNUg-
1
+
2
where the penultimate inequality follows from the fact that S+ S are e-unbiased and the last inequality follows from our lower bound on the discrepancy. Since there exists no PTF of degree 2 that succeeds with probability + c, have contradiction.
This concludes the proof Theorem F.5.
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide detailed proofs and/or references for all the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include dedicated section in the end of the main paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
41

---

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

---

Answer: [NA]
Justification:
Our paper does not have any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ ColileeeesSSSSeeeiiiieiie.ea
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. wttpccccpppccccceeececceccccccct httpa///ggiieee/eeeuubuiiiiiiiii /CodeSubmic ssionnollll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
43

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eerrrp.peeeeeeeeee ctctp//.ccccpbbbcccciccccicieie
Answer: [Yes]
Justification: We read the code of ethics and strongly believe that our work conforms with stated code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: We include discussion on the broader impacts of our work at the end of the main paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data and models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our paper does not use any existing code, data models.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "5oALs7Yadc", "reviewer": "Reviewer_D9yX", "summary": "Distribution shift is a well known problem where the classifier is trained on a particular data distribution encounters an input distribution far from the training set(OOD).  In such a scenario it is desirable that the model performance not degrade too much, and one way to ensure this to estimate the discrepancy of the concept class wrt to the training and test distributions in the standard manner. \n\nReasoning over the exponentially many functions in a reasonable concept class is naturally not tractable in most cases, hence the authors define a localized variant that computes the discrepancy only over a small neighbourhood of a particular reference function. The intuition behind this is that the learned functions, are well behaved enough to be near the reference hypothesis with high probability. \n\nTo make the learned models robust to distribution shifts, it is essential to have learning processes that can give discrepancy guarantees and the paper takes a step towards this by providing an optimal test for a broad class of hypotheses.", "questions": "--", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) the problem relaxation of localized discrepancy is original and well motivated, and is likely to influence further research in the area. \n2) the examples are chosen well and make the paper easy to read\n3) The paper makes a timely and significant contribution to learning with discrepancy guarantees", "weaknesses": "1) Since the main claim is a polytime algorithm, in addition to various speedups in the learning process, it might be interesting to look at a toy experiments to get an idea of the performance. \n2) The localized discrepancy relaxation likely does not makes sense in a few situations. This needs to be a part of the paper, along the the list of cases where the notion does work. \n\nMinor typos -- 1399 (threshol)\n115 (chow)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the reviewer for their comments and for appreciating our work. \n\n- We agree that experimental evaluation of our algorithms would be interesting, but we believe that a thorough, dedicated evaluation would be preferable and more suitable for future work, since the scope of this paper is theoretical.\n\n- The appropriate localized discrepancy relaxation of the testing phase depends on the guarantees one can ensure during training. For example, if the training algorithm is guaranteed to approximately recover the relevant subspace (see Theorem D.13), then testing the localized discrepancy with respect to the subspace neighborhood (see Definition D.2) is appropriate. We refer the reviewer to lines 103–109 for a relevant discussion and lines 110–130 for examples of the appropriate relaxation in different scenarios. We will clarify this point in future revisions.", "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": "9qOwu8pd5d", "reviewer": "Reviewer_YUiz", "summary": "The paper investigates the problem of learning under distribution shift in the recently introduced framework of testable learning with distribution shifts (TDS) [Klivans et. al. 24]. In this framework, the learner receives labeled samples from the train distribution D and unlabeled samples from the test distribution D’,  and is expected to either output a hypothesis with low error on D’ or correctly identify that D’ is not equal to D when that is the case.  In other words, the learner runs a test to check whether D=D’ and outputs a hypothesis with low error on D’ when the test accepts.  She can abstain from outputting a hypothesis when the test rejects, but the test needs to accept whp when D=D’.\n\nThis paper introduces the notion of localized discrepancy test and uses it for efficient TDS learning. The localized discrepancy test estimates the discrepancy between two distributions with respect to a fixed hypothesis which makes it efficient to compute in many cases. This is in contrast to the prior notion of  (non-local)  discrepancy which is computed with respect to worst pair of hypotheses within a class and is therefore significantly harder to compute.\n\nSome of the salient results from the paper are as follows.\n1. The prior work by Klivan et. al. (’23) showed that any class admitting low-degree polynomial approximators in the L2 sense can be efficiently TDS learned. This paper extends this result to show that approximation in the L1 sense is enough for TDS learning, and uses this result to obtain improved algorithms for constant depth circuits.\n2. Gives universal TDS learner for convex sets with low intrinsic dimension and half-space intersection. The learner is universal in the sense that the corresponding test is guaranteed to accept even when the distribution D’ is not equal to D but has mild structural properties.", "questions": "My main concern is regarding the practical applicability of this line of work. While practical applicability is not the goal for all the theory work, in this case, the motivating question comes from practice, so connecting back to practical usefulness seems important. Could the authors explain if they see this research helping with learning under distribution shifts in real-world situations? It's okay if this paper doesn't immediately offer practical algorithms, but if the authors can discuss how this work might eventually lead to something practically useful, I would be happy to reconsider my evaluation of the paper. I might be missing something and am willing to seriously reconsider my assessment.", "limitations": "See the weaknesses section and the question for the authors above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper makes concrete improvements over the existing work on TDS learning.\n\nIt is reasonably well written.", "weaknesses": "While the TDS learning model was introduced from the practical motivation of learning under distribution shifts, the results in this paper (as well as the prior work) seem to be in settings far removed from practice, often relying on strong distributional assumptions. I am unsure about the significance and relevance of these results to general machine learning researchers concerned with distribution shifts in the real world.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your question about \"strong assumptions\". The goal of this line of work is precisely to remove the strong assumptions inherent in all prior work in the fields of distribution shift and domain adaptation.  More precisely, all prior work requires an assumption on both the train distribution D and test distribution D’, as it requires the discrepancy distance between D and D’ to be small to obtain meaningful generalization bounds.   Instead, we are able to come up with the first efficient algorithms to test a (localized) version of this quantity, without taking any assumptions on D’.  Additionally, we can remove assumptions on D as well by combining our work with so-called testable learning algorithms (effectively we can test the assumptions we need for D and reject if they are not satisfied).  Finally, it is possible to relax the assumptions we take on D to say bounded distributions, which is quite reasonable to assume in practice (this observation will appear in forthcoming work).\n\nLet us further explain why we think taking an assumption on D– the training distribution–  is practically reasonable: consider the following now extremely common scenario: someone trains a foundation model on a labeled data set.   In this scenario, the learner has a lot of control over the training set; for example, in the health or bio domains the training data can be subsampled from large databases to satisfy various properties. What we want to avoid is making an assumption about an unseen test set, as it may come from a radically different distribution.  The recent line of work on TDS learning and this paper in particular actually give efficient algorithms with meaningful guarantees in this scenario, whereas all prior work requires an assumption on some notion of distance between D and D’ that cannot be efficiently verified.   \n\nAnother practical example: assume we have built a foundation model and wish to determine if it will perform well on a new unseen test set.  We can view the last layer of this network as a linear classifier with respect to a distribution of weights on the next to last layer of the network.  We can even verify certain properties of this distribution (such as boundedness).  Then determining if this foundation model will succeed is precisely a TDS learning problem as described in the submission. \n\nOur work, in particular, makes three important contributions towards more practically relevant algorithms, by giving TDS learners that: (1) can handle more classes (i.e., degree-2 PTFs, constant-depth circuits and convex sets), (2) accept more often, since they are guaranteed to accept wide classes of benign distribution shifts (see the universal TDS learners of Theorems 4.2 and 5.1) and (3) run in fully polynomial time at test time, even for classes for which no fully polynomial learning algorithms are known (see section 5). \n\nTo summarize, we have removed the onerous assumptions prior work made on both the train and test distributions and have given a path forward for new efficient algorithms to determine if a foundation model will succeed on unseen test sets.  We therefore feel these ideas will have a major practical impact.  Distribution shift is certainly one of the most critical issues for trustworthy ML.", "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": "nBdTeHh6hr", "reviewer": "Reviewer_aevL", "summary": "This paper considers the problem of designing Testable Learning with Distribution Shift (TDS learning) algorithms. Through proposed algorithms for testing localized discrepancy distance, the authors give a set of efficient TDS learning algorithms. These algorithms improves all prior work in the sense that they give optimal error rates, provide universal TDS learners and have polynomial runtime.", "questions": "See weakness. My main questions are regarding the intuition behind your tester, and how your theorems in section 4 and 5 come from proposition 3.2.", "limitations": "No significant limitations are stated.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work consider the novel framework of TDS learning, under which provably efficient algorithms for learning with distribution shift for certain concept classes are introduced. This shows the high novelty of this work.\n\nFrom significance perspective, this work generalize beyond prior works in many aspects. \n\nAlso the proofs are solid, with clearly defined notations.", "weaknesses": "Although \"discrepancy testing\" appears in the title, the discussion for testing is relatively limited. Most of the results are given in the form of TDS learners rather than discrepancy testers. Readers need to refer to the appendix to see what is actually going on for testing. I would suggest the authors to explain their testing algorithm in more detail, and explain more intuition of why this testing may work. Also, it will be good if the authors could explain more on why their testers can induce TDS learners in section 4 and 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback.\n\nWe would like to clarify that we propose 3 different discrepancy testers, one for each of the sections 3, 4 and 5 (see proposition 3.2, appendix D.1 and appendix E1). The relevant discussion can be found in lines 103–109 and high-level descriptions for the three testers can be found in lines 110–116 (for chow matching tester), lines 117–123 (for cylindrical grids tester) and lines 124–130 (for boundary proximity tester). Moreover, in lines 285–316 we provide the intuition behind the cylindrical grids tester (used for the results of section 4) and in lines 354–378 we provide the intuition behind the boundary proximity tester (used for the results of section 5).\n\nDue to space limitations, we had to move formal statements regarding our discrepancy testers in the appendix, but, given the additional space of the camera ready version, we will add some more details in sections 4 and 5 accordingly.\n\nMoreover, to avoid confusion, we will explicitly state in section 1.2 that we propose three different testers.\n\nWe are happy to provide further clarifications regarding the testers of sections 4 and 5 if the reviewer has any questions not addressed in lines 285–316 and lines 354–378.", "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": "11t3LPOqz1", "reviewer": "Reviewer_hgSz", "summary": "Discrepancy distance is crucial in domain adaptation. The paper proposes the first set of provably efficient algorithms for testing localized discrepancy distance. This approach can generalize and improve prior work on TDS learning, and further extend to semi-parametric settings. By separating learning and testing phases, the authors obtain algorithms that run in fully polynomial time at test time.", "questions": "1.Does Definition 1.1 of localized discrepancy match the one with 0-1 loss described in (Zhang et al., 2020)?\n\n2.The abstract mentions, \"Our methods also extend to semi-parametric settings and yield the first positive results for low-dimensional convex sets.\" However, I couldn't locate this information in the main text of the paper.\n\n3.In line 65, it is stated, “we give the first TDS learners that are guaranteed to accept whenever the test marginal falls in a wide class of distributions that are not necessarily close to the training distribution (in say statistical distance) but, instead, share some mild structural properties.”\nThis raises the question of why emphasis is placed on some mild structural properties over statistical distance, and what exactly these mild structural properties are.\n\n4.In line 142, it is stated, “$\\lambda$ is the  standard (and necessary) benchmark for the error in domain adaptation when the training and test distributions are allowed to be arbitrary.” I would appreciate it if you provide further insights about $\\lambda$. For example, considering the training and test distributions are allowed to be arbitrary, is there an upper bound of $\\lambda$?\n\n[1] Zhang Y., Long M., Wang J., and Jordan M., On localized discrepancy for domain adaptation. arXiv. 2020.", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The article is well-written with clear logic, though it could benefit from improvements in some parts. \n\n2.The authors spent great effort delivering theorems of time and sample complexity for several fundamental concept classes: 1) Classes with Low Sandwiching Degree; 2) Non-Parametric Low-Dimensional Classes; 3) Class of balanced intersections of half spaces.\n\n3.The paper introduces algorithms for testing that run in fully polynomial time.", "weaknesses": "See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their feedback.\n\n1. Our Definition 1.1 is a generalization of the localized disparity discrepancy w.r.t. 0-1 loss as described in (Zhang et al., 2020). In particular, they use a specific notion of neighborhood (which corresponds to the disagreement neighborhood of definition E.2 we define in the appendix). However, we can also define the localized discrepancy with respect to other notions of neighborhood, like the global neighborhood (see definition C.2) or the subspace neighborhood (see definition D.2). Different notions of neighborhood correspond to different localized discrepancy testers.\n\n2. For the results on semi-parametric classes see section 4, where we propose TDS learners for low-dimensional convex sets (which is a semi-parametric class of functions).\n\n3. Line 65 emphasizes that our testers will certify low test error even in the presence of large amounts of distribution shift, as long as the distribution shift is benign in the sense that the test distribution is structured. The appropriate structural properties are described in lines 273–275 for Theorem 4.2 and in lines 324–326 for Theorem 5.1 and essentially correspond to (1) an upper bound on the fourth moment and (2) anti-concentration. In other words, while distributions with small statistical distance look similar, our testers will accept distributions that are very different from the training distribution, as long as they satisfy some structural properties.\n\n4. The error parameter $\\lambda$ encodes the relationship between the training and test labels. It is small when there is some classifier $f^*$ in the given concept class that has both low training and low test error, i.e., both the training and the test labels are approximately generated by $f^*$. Conversely, if the test labels are opposite from the training labels, $\\lambda$ will always be $1$.  Since there are no test labels available, we cannot hope for an error guarantee better than $\\lambda$ (see proposition 1 in [KSV’24]).\n\n*[KSV’24] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. The Thirty Seventh Annual Conference on Learning Theory, 2024*", "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": "TA0tUqgg26", "reviewer": "Reviewer_P6Ww", "summary": "The paper extends the recently introduced Testable Learning with Distribution Shift (TDS) model and makes contributions in three main aspects: Universal TDS Learners, Optimal Error Guarantees via L1 Sandwiching, and Fully Polynomial-Time Testing. It presents universal TDS learners that perform well across a wide range of test distributions, achieves nearly optimal error rates by leveraging L1 sandwiching techniques, and provides efficient testing algorithms that run in fully polynomial time, particularly for intersections of halfspaces. The paper also explores the implications of these methods for various concept classes and demonstrates their application in scenarios involving distribution shifts", "questions": "- Can you provide evidence showing that the efficiency improvements in the testing phase are significant for current large pre-trained models, or specify at what scale of models these improvements become substantial?\n- Generalization to Other Concept Classes: The paper focuses on specific concept classes like intersections of halfspaces. Do you have plans or ideas for extending these methods to other concept classes? It would be helpful to understand the potential for broader application.\n- Clarity in Algorithm Description: The descriptions of your algorithms are mathematically detailed but could benefit from pseudocode or flowcharts. Could you provide these to enhance clarity.", "limitations": "Yes, the authors use one section to discuss about the limitation, future work and broader impact of this paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- This paper extends the recently introduced Testable Learning with Distribution Shift (TDS) model by introducing Universal TDS Learners and employing L1 sandwiching techniques to achieve nearly optimal error rates. These advancements provide new methods for handling distribution shifts, particularly for intersections of halfspaces.\n- The theoretical foundations are robust and well-supported by detailed mathematical formulations. The use of extensive equations and rigorous proofs shows the depth of the research.\n- The paper is well-organized and clearly written, with each section logically building upon the previous one. Definitions, lemmas, and theorems are clearly presented, aiding in reader comprehension.\n- The development of efficient testing algorithms that run in fully polynomial time, especially for intersections of halfspaces, addresses significant limitations in prior work.", "weaknesses": "- Lack of Experimental Validation: The paper presents extensive theoretical work but lacks empirical validation, making it difficult to assess practical performance.\n- Assumptions on the need for efficient implementations of the testing phase: The paper assumes that efficiency is crucial for the testing phase, especially for large pre-trained models. However, it should address how much improvement this efficiency brings to current large models and if they are substantial enough to benefit from it.\n- Generalization to Other Concept Classes: The focus on specific concept classes like intersections of halfspaces limits the applicability of the methods to a broader range of problems.\n- Clarity in Algorithm Description: The algorithm descriptions could benefit from the inclusion of pseudocode or flowcharts to enhance understanding and reproducibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the reviewer for their constructive feedback and for appreciating our work.\n\n- The fully polynomial-time testers we propose in this work apply to the class of balanced halfspace intersections. There are two important implications of our results related to current large pre-trained models: (1) we can experimentally evaluate our proposed efficient testers through applying them to the last layers of large networks, since the last layers correspond to simple classes like halfspaces or halfspace intersections and (2) our localized discrepancy tester for halfspace intersections demonstrates that fully polynomial-time discrepancy testing is possible, even for classes for which there is no known fully polynomial-time provable learning algorithm. The second implication motivates further study of the localized discrepancy testing problem for more complex concept classes, like deep neural networks.\n\n- We agree with the reviewer that generalizing our results to broader concept classes is an interesting open direction. That said, our results capture several fundamental concept classes like constant-depth circuits, low-degree PTFs (see Table 1), low-dimensional convex sets (section 4) and halfspace intersections (section 5). As mentioned above, TDS learning of these classes can also be useful for neural networks, since the last layers typically correspond to some simpler class. Moreover, our work hints at potential end-to-end extensions to other classes by extracting the exact properties we used to obtain our results (see for example Remark 5.4 and lines 394–400).\n\n- Due to space limitations, we only provided pseudocode for our algorithms in the appendix (see Algorithms 1,2 and 3). Given the additional space for the camera-ready version, we will consider adding some pseudocode in the main paper for clarity. We can also add pseudocode for the boundary proximity tester in Appendix E.", "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:

Meta-review: The authors consider the framework of Testable learning with Distribution Shift (TDS). In this framework the goal is to have a computationally efficient learner that either rejects (if there is discrepancy between the source and target distributions) or outputs a hypothesis that works well on the target distribution. The challenge is that computing the discrepancy between distributions can be computationally challenging. The authors instead propose efficient testers for "localized" discripancy distance (intuitively, one can run an efficient PAC learner first, and then run the discripancy tester only for the output hypothesis of the PAC learner). The authors' results improve the prior work in terms of error rates and come up with "universal" learners that work with respect to a large class of distributions.

Overall, the authors make progress in an important question that is of interest to the learning theory community.
Decision: Accept (poster)