Efficient Discrepancy Testing for Learning with Distribution Shift

Authors: gautam  chandrasekaran
adam r klivans
vasilis  kontonis
konstantinos  stavropoulos
arsen  vasilyan
u c berkeley
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:54:23

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.

Main paper: 
 introduction: 
 Distribution shift remains a central challenge in machine learning. While practitioners may exert some level of control over a 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 on an unseen test set is therefore critical to the widescale deployment of modern foundation models.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 on the test distribution. Over the last twenty years, researchers in domain adaptation and related fields [BDBCP06, BCK + 07, MMR09, BDBC + 10, RMH + 20, 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:disc C (D, D ′ ) = sup f1,f2∈C P x∼D [f 1 (x) ̸ = f 2 (x)] -P x∼D ′ [f 1 (x) ̸ = f 2 (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-time guarantees).In search of efficient algorithms for learning with distribution shift with certifiable error guarantees, recent work by [KSV24b] It is straightforward to see that if algorithm A learns concept class C 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 is nontrivial in part because we cannot make any assumptions on the test distribution D ′ (our test has to always accept or reject correctly). Nevertheless, our main contribution is a suite of new discrepancy testers for well-studied function class/training distribution pairs that unifies and greatly expands all prior work on TDS learning.Optimal Error Guarantees via L 1 Sandwiching. The work of [KSV24b] followed a momentmatching approach to show that the existence of L 2 sandwiching polynomial approximators implies TDS learning up to a constant factor of the optimum error. Although their result implies TDS learning for several fundamental concept classes, the L 2 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 L 1 sandwiching, resolving one of the main questions left open in [KSV24b] . As such, we obtain exponential improvements for TDS learning constant depth circuits (AC 0 ), 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 L 1 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.1, 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 anti-concentrated 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's overall runtime is polynomial in the dimension d, while the time complexity of the TDS learner given by [KSV24a] involved a factor of d O(log(1/ϵ)) , where ϵ is the error parameter.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 ⊆ R d and let H, C ⊆ {±1} X be hypothesis and concept classes respectively. Define neighborhood N to be a function N : H → 2 C . For f ∈ H, the ( f , N)-localized discrepancy from D to D ′ is defined as:disc f ,N (D, D ′ ) = sup f ∈N( f ) P x∼D ′ [ f (x) ̸ = f (x)] -P x∼D [ f (x) ̸ = f (x)]Testing localized discrepancy is clearly easier than testing the traditional (global) discrepancy distance, since global discrepancy is defined with respect to 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 a moment that we have fixed a neighborhood function N and have obtained a learner that always outputs a classifier close to the ground truth function f * (i.e., f * ∈ N( f )). 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 f is close to the ground truth for both training and test distributions).The algorithmic challenge is finding a definition of neighborhood that admits both an efficient learner (for outputting a 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 one 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 we give a different discrepancy tester for each of the following cases.Classes with Low-Degree Sandwiching Approximators. We show that the existence of degree-ℓ L 1 -sandwiching approximators for a class C over X ⊆ R d turns out to be sufficient to design a localized discrepancy tester that runs in time d O(ℓ) where the notion of neighborhood is widest possible, i.e., N( f ) = C. 6 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 f under the test marginal and checking whether they closely match the chow parameters of f under the training marginal. For more details, see Section 3.Convex Sets with Low Intrinsic Dimension. For convex sets with few relevant dimensions, there are 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 still ensuring that f * ∈ N( f ). The appropriate notion of neighborhood contains low-dimensional concepts whose relevant subspace is geometrically close to 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.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.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 distributions. Other important notions of distribution similarity include bounded density ratios [SSK12] 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-time) 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-ℓ L 2 -sandwiching approximators can be TDS learned in time d O(ℓ) 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 1 -sandwiching approximators suffices for TDS learning and we improve the error guarantee to nearly-match the information-theoretically optimal λ (see Section 3). For intersections of halfspaces under Gaussian training marginals, [KSV24a] gave TDS learners with improved guarantees compared to those given by [KSV24b] through L 2 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 to certify a near-optimal error guarantee. Testable agnostic learning was defined by [RV23] and there are several subsequent works in this framework [GKK23, GKSV24, GKSV23, DKK + 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 is 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.e., realizable learning).PAC Learning. In the standard framework of PAC learning, there is an abundance of algorithmic ideas and techniques that aim to achieve efficient learning, under various assumptions (see e.g., [LW94, BK97, KOS04, KLT09, KOS08a, Vem10b, Vem10a, GKM12, KKM13, DKS18a, DTK22]). In this work, we make use of polynomial regression [KKMS08] , dimension reduction techniques [Vem10a] , as well as techniques for robustly learning geometric concepts [DKS18b] , in order to obtain efficient TDS learners. In fact, our approach of designing TDS learning algorithms through localized discrepancy testing sheds a 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.α ∈ N d with ∥α∥ 1 ≤ 2p, compute the quantities M α = E x∼X [x α ] = E x∼X [ i∈[d]x αi i ] and reject if for some α as such, we have|M α -E x∼N [x α ]| > ∆.2. Run the boundary proximity tester T with inputs (ϱ, f , X) and reject if T rejects.3. Otherwise, accept.Soundness. Assume, first, that all of the tests have passed. We will show that for any f ∈ N e ( f ), we have P x∼X [f (x) ̸ = f (x)] ≤ ψ. Since the event that f (x) ̸ = f (x) is independent for each x ∈ X,(x) = F (W x) and f (x) = F (V x) for W, V ∈ R k×d so that W W ⊤ = V V ⊤ = I k . Let U ∈ R 2k×dbe a matrix such that U U ⊤ = I 2k 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 W W ⊤ = I k , imply that for any x ∈ R d we have W x = W U ⊤ U x and, similarly, V x = V U ⊤ U x (the part of x that falls within the subspace spanned by the rows of W does not change by applying the projection matrix U ⊤ U and the remaining part is irrelevant). Moreover, we have that ∥U∥ 2 = ∥U ⊤ ∥ 2 = ∥W ∥ 2 = ∥V ∥ ⊤ 2 = 1. Let F ′ (z) = F (W U ⊤ z) and F ′ (z) = F (V U ⊤ z). We have that P x∼N [F ′ (U x) ̸ = F ′ (U x)]≤ γ e , by assumption. By Proposition E.4, applied on F ′ , F ′ , and since γ e ≤ βr k k k/2 e -2R 2 , we have that for anyx ∈ R d such that F ′ (U x) ̸ = F ′ (U x) (i.e., F (W x) ̸ = F (V x))) at least one of the following is true: (a) ∥U x∥ 2 ≥ R or (b) U x ∈ ∂ ϱ F ′ . According to Proposition E.8, U x ∈ ∂ϱ F ′ implies that V U ⊤ U x ∈ ∂ ϱ F , which, in turn, implies that V x ∈ ∂ ϱ F , since V x = V U ⊤ U xand therefore, by Proposition E.8 we also have that x ∈ ∂ ϱ f . Therefore, overall, we haveP x∼X [f (x) ̸ = f (x)] ≤ P x∼X [∥U x∥ 2 ≥ R] + P x∼X [x ∈ ∂ ϱ f ]In order to bound the term P x∼X [∥U x∥ 2 ≥ R], we use the fact that the test of step 1 of the algorithm has passed. In particular, by applying Markov's inequality appropriately, we obtain thatP x∼X [∥U x∥ 2 ≥ R] ≤ 1 R 2p E x∼X [∥U x∥ 2p 2 ]. Note that the expression ∥U x∥ 2p 2 corresponds to a polynomial of degree at most 2p and corresponding to coefficient vector whose absolute (ℓ 1 ) norm is bounded by (4kd 2 ) p . In particular, we have that (for allx ∈ R d ) ∥U x∥ 2p 2 = α∈N d c α x α (recall that x α = i∈[d] x αi i ), where α∈N d |c α | ≤ (4kd 2 ) p and c α = 0 whenever ∥α∥ 1 > 2p. Therefore, by linearity of expectation, we haveE x∼X [∥U x∥ 2p 2 ] = α c α E x∼X [x α ] = α c α (E x∼N [x α ] + ∆ α ) = E x∼N [∥U x∥ 2p 2 ] + α c α ∆ α , where |∆ α | ≤ 1 (2kd) 2p for any α with ∥α∥ 1 ≤ 2p. Hence, overall, we have E x∼X [∥U x∥ 2p 2 ] ≤ E x∼N [∥U x∥ 2p 2 ] + 1 ≤ 2(4kp) p , which implies that P x∼X [∥U x∥ 2 ≥ R] ≤ 2 (4kp) p R 2p . For the term P x∼X [V x ∈ ∂ ϱ F ],we use the fact that the tester T has accepted and hence we haveP x∼X [x ∈ ∂ ϱ f ] ≤ σϱ ≤ σ( γe exp(2R 2 ) βk -k/2 ) 1/k . We have shown that P x∼X [f (x) ̸ = f (x)] ≤ ψ, as desired.Completeness. Suppose now that X consists of i.i.d. examples from the Gaussian distribution N d . To ensure that with probability at least 9/10, the tests of step 1 pass, we pick |X| ≥ (Cdk) ∆ 2 , for some sufficiently large C. This is because the Gaussian moments concentrate (e.g., due to Chebyshev's inequality) as well as a union bound. For step 2, it suffices that |X| ≥ m T .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 to a class D of distributions over R d such that for some µ c ≥ 1 we have sup v∈S d-1 E x∼D [(v•x) 4 ] ≤ µ c for all D ∈ D, then there is a (N e , ψ+ϵ)-tester for localized discrepancy from N d with respect to D with sample complexity m = m T + 20d 4 + 3 ϵ 2 , that calls T once and uses additional time O(md 2 + d 3 ), where the error parameter ψ isψ = 4kµ c R 2 + σ √ k γ e exp(2R 2 ) β 1/kProof of Theorem E.7. Let ϱ = (γ e /β) 1/k √ k exp(2R 2 /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. ] = 2k i=1 E x∼X [(u i • x) 2 ] ≤ 2k sup v∈S d-1 E x∈X [(v • x) 2 ] ≤ 4kµ c ,where u i denotes the vector corresponding to the i-th row of U .Completeness. The completeness for step 1 follows by an application of Chebyshev's inequality to the random variables corresponding to each of the entries of the matrix M and a union bound, to show that the Frobenius norm (and hence the operator norm) of the matrix M -E x∼D [xx ⊤ ] is sufficiently small (where D is some distribution in D and X consists of independent draws from D).In the proofs of Theorems E.6 and E.7 we have used the following usedul proposition. Note that for the same x and z we haveF (W x + W z) ̸ = F (W x). Since ∥W ∥ 2 = 1, we have that ∥W z∥ 2 ≤ ∥z∥ 2 ≤ ϱ. Let z = W z ∈ R k . We have ∥z∥ 2 ≤ ϱ and F (W x + z) ̸ = F (W x), i.e., W x ∈ ∂ ϱ F .For the other direction, suppose thatW x ∈ ∂ ϱ F . Then, there is z ∈ R k with ∥z∥ 2 ≤ ϱ such that F (W x + z) ̸ = F (W x). We have that z = I k z = W W ⊤ z. Let z = W ⊤ z. We have z = W z and ∥z∥ 2 = ∥W ⊤ z∥ 2 ≤ ∥W ⊤ ∥ 2 ∥z∥ 2 = ∥W ∥ 2 ∥z∥ 2 ≤ ϱ. We have that f (x + z) = F (W x + W z) = F (W x + z) ̸ = F (W x) = f (x). Hence, x ∈ ∂ ϱ f .We now focus on the class of balanced intersections of halfspaces, which is formally defined as follows.Definition E.9 (Balanced Halfspace Intersections). A concept f : R d → {±1} is called a β-balanced intersection of k halfspaces if it is β-balanced (see Definition A.1) and there are w 1 , w 2 , . . . ,w k ∈ S d-1 and τ 1 , τ 2 , . . . , τ k ∈ R such that f (x) = 2 k i=1 1{w i • x ≥ τ i } -1 for all x ∈ R d .following.P z∼N k [F (z) = -1 | z ∈ B k (x, ϱ)] = P z∼N k [F (z) = -1 and z ∈ B k (x, ϱ)] P z∼N k [z ∈ B k (x, ϱ)] ≥ 1 2 vol(B k (x, ϱ)) vol(B k (x, ϱ)) • inf z∈B k (x,ϱ) N k (z) sup z∈B k (x,ϱ) N k (z) ≥ 1 2 • exp(-1 2 (∥x∥ 2 + ϱ) 2 ) exp(-1 2 (∥x∥ 2 -ϱ) 2 ≥ 1 2 e -1 2 ϱ∥x∥2 ≥ 1 2 e -1 2 ϱRFor the case where F (x) = 1, we first prove the following claim, which states that when a convex set is (globally) balanced, it must contain some Euclidean ball with non-negligible mass.Claim. Since K is β-balanced and convex, there isx c ∈ R k such that B k (x c , r) ⊆ K, where r = β Ck log k , ∥x c ∥ 2 ≤ R c = (2k ln( 8k β )) 1/2 and C ≥ 1 is a sufficiently large universal constant.Proof. Since K is balanced, we haveP x∼N k [F (x) = 1] > β. We now use Lemma B.8 to obtain that P x∼N k [x ∈ ∂ r F ] ≤ C 2 rk log k.We have the following.P x∼N k [F (z) = 1, ∀z ∈ B k (x, r)] = P x∼N k [F (x) = 1 and F (x + z) = 1, ∀z with ∥z∥ 2 ≤ r] = P x∼N k [F (x) = 1] -P x∼N k [F (x) = 1 and ∃z : ∥z∥ 2 ≤ r and F (x + z) ̸ = 1] ≥ P x∼N k [F (x) = 1] -P x∼N k [∃z : ∥z∥ 2 ≤ r and F (x + z) ̸ = F (x)] = P x∼N k [F (x) = 1] -P x∼N k [x ∈ ∂ r F ] > β - C 2 rk log k = β 2 Moreover, since P x∼N k [∥x∥ 2 > R c ] ≤ 4ke -R 2 c 2k = β/2, we overall have that P x∼N k [F (z) = 1, ∀z ∈ B k (x, r) and ∥x∥ 2 ≤ R c ] > 0Since the probability of such an x is positive, by the probabilistic method, there is some x c as desired.We have shown that for somex c with ∥x c ∥ 2 ≤ R c , we have B k (x c , r) ⊆ K. Let now x ∈ R k with ∥x∥ 2 ≤ R and F (x) = 1 (x ∈ K). Since K is convex, if K ′ is the convex hull of {x} ∪ B k (x c , r),we have K ′ ⊆ K. We will show that K ′ ∩ B k (x, ϱ) contains some cone R ′ with non-trivial mass (see Figure 3 ).Let y be any point on the surface of B k (x c , r) such that the tangent hyperplane of B k (x c , r) on y passes from x. Then, if we let θ to be the angle yxx c , we have sin θ = ∥y -x c ∥/∥x -x c ∥ 2 = r/∥x -x c ∥ 2 , because xyx c = π/2, by definition of y. Note that the triangle defined by x, y and x c lies within K ′ and hence within K as well. Since this is true for any y as defined above, we have that K contains a rotational cone R with vertex x, angle θ and height h ∈[∥x -x c ∥ 2 -r, ∥x -x c ∥]. Note that the volume of K ′ ∩ B k (x, ϱ) is decreasing in ∥x -x c ∥ 2 ,as long as ϱ ≤ r. Therefore, we may assume that ∥x - x c ∥ 2 = R + R c (which implies that h ≥ 1 ≥ ϱ ≥ ϱ cos θ). Let R ′ = R ∩ B k (x, ϱ).P z∼N k [F (z) = 1 | z ∈ B k (x, ϱ)] = P z∼N k [F (z) = 1 and z ∈ B k (x, ϱ)] P z∼N k [z ∈ B k (x, ϱ)] ≥ vol(R ′ ) vol(B k (x, ϱ)) • inf z∈B k (x,ϱ) N k (z) sup z∈B k (x,ϱ) N k (z)≥ ϱ cos θ(ϱ sin θ) k-1 (2π) (k-1)/2 k -((k-1)/2+1) ϱ k (2π/k) k/2• exp(-ϱR/2)≥ (sin θ) k-1 2 √ 2πk • e -1 2 ϱR ≥ β Ck 2 R ln(1/β) k e -R/2Combining the two cases considered (F (x) = -1 and F (x) = 1), we obtain the desired result.Finally, we show that there is a boundary proximity tester for the class of halfspace intersections. Proof of Theorem E.11. The theorem follows by combining either Theorem E.6 or Theorem E.7 with Theorem E.11, Lemma E.12 and Lemma E.13. Note that since the parameter λ is unknown to the algorithm, we will run the corresponding discrepancy tester (either of Theorem E.6 or of Theorem E.7) for all possible values of the parameter ϱ (of the discrepancy tester) within an O(ϵ/k 2 )net of the interval [0, β Ck log 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 all the values of ϱ in the net. In total, we will need poly(k, 1/ϵ) repetitions.where the last inequality follows from the fact that S + , S -are ϵ-unbiased. Thus, we obtain that (P x∼U S + [h(x) = 1] -P x∼U S -[h(x) = 1]) ≥ 1 -8ϵ. Let g be the the halfspace that always outputs -1. Clearly, we have that disc F (U S + , U S -) ≥ (P x∼U S + [h(x) ̸ = g(x)] -P x∼U S -[h(x) ̸ = g(x)]) ≥ 1 -8ϵ.Claim (Soundness). Let S + , S -be ϵ-unbiased. If there exists no degree 2k PTF h such that 1 n n i=1 1{h(x i ) = y i } ≥ 1 2 + ϵ, then disc F (U S + , U S -) ≤ 8ϵ.Proof. Say disc F (U S + , U S -) ≥ 8ϵ. Since F is closed under complements, we obtain without loss of generality that there exist two PTFs h 1 , h 2 of degree d such that P x∼U S -[h 1 (x) ̸ = h 2 (x)] -P x∼U S + [h 1 (x) ̸ = h 2 (x)] ≥ 1 2 + ϵ. Consider the function g(x) = h 1 (x) • h 2 (x). We have that g is a degree 2k PTF. Thus, we obtain that1 n n i=1 1{g(x) = y} = |S -| n • P x∼U S - [g(x) = -1] + |S + | n • P x∼U S + [g(x) = 1] = |S -| n • P x∼U S - [h 1 (x) ̸ = h 2 (x)] + |S + | n • (1 -P x∼U S + [h 1 (x) ̸ = h 2 (x)]) ≥ 1 2 + 1 2 P x∼U S - [h 1 (x) ̸ = h 2 (x)] -P x∼U S + [h 1 (x) ̸ = h 2 (x) -3ϵ ≥ 1 2 + ϵwhere the penultimate inequality follows from the fact that S + , S -are ϵ-unbiased and the last inequality follows from our lower bound on the discrepancy. Since there exists no PTF of degree 2k that succeeds with probability 1 2 + ϵ, we have a contradiction.This concludes the proof of Theorem F.5.• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
preliminaries: 
 We For a concept class C, a distribution D over X , ϵ ∈ (0, 1), we say that C has ϵ-L 1 sandwiching degree ℓ with respect to D if for any f ∈ C, there exist polynomials p up , p down over X with degree at most ℓ such that (1)p down (x) ≤ f (x) ≤ p up (x) for all x ∈ X and (2) E x∼D [p up (x) -p down (x)] ≤ ϵ. Learning Setting. For X ⊆ R d , the learner is given labeled samples from a training distribution D train X Y over X × {±1} with X -marginal D train X = D and unlabeled examples from the marginal D test X of a test distribution D test X Y over X × {±1}. For a concept class C ⊆ {X → {±1}}, in the realizable setting, there is f * ∈ C that generates the labels for both D train X Y and D test X Y . In the agnostic setting, the standard goal in domain adaptation is to achieve an error guarantee that is competitive with the information-theoretically optimal joint error λ = min f ∈C (err(f ; Note that the success probability for TDS learning can be amplified through repetition [KSV24b] and we will consider δ = 0.1 unless specified otherwise.D train X Y ) + err(f ; D test X Y )),For any function f ∈ H, if X ∼ D ⊗m with m ≥ m conc , then with probability at least 9/10, we have that for all α ∈ N d with ∥α∥ 1 ≤ ℓ, E D [ f (x) • x α ] - E X [ f (x) • x α ] ≤ ϵ Bd 2ℓ .For any function f ∈ H, if X ∼ D ⊗m with m ≥ m conc , then with probability at least 9/10, we have that for all α ∈ N d with ∥α∥1 ≤ ℓ, E D [ f (x) • x α ] - E X [ f (x) • x α ] ≤ ϵ Bd 2ℓ .Then, there exists an algorithm that takes poly(d ℓ , 1/ϵ) labelled samples from the training distribution, O (m conc + 1/ϵ 2 ) • log(1/δ) unlabelled test samples, runs in time poly m conc , d ℓ , 1 ϵ , log(1/δ) and TDS learns C with respect to D up to error λ + opt train + ϵ and fails with probability at most δ.Proof. Observe that L 1 sandwiching polynomials are also L 1 approximating polynomials. Thus, C satisfies the requirements of Theorem C.6. Thus, we can run Algorithm 2 with A instantiated to be the algorithm from Theorem C.6. The proof of correctness follows from Algorithm 2.We now argue that when D train X ∈ {Unif{±1} d , N d }, then we have that Assumption 2 of Theorem C.4 is always true with m conc ≤ poly(d ℓ B/ϵ).Lemma C.8. Let D ∈ {Unif{±1} d , N d }. Let f be a function taking values in {±1}. Let ℓ ∈ N. Let X ∼ D ⊗mconc for m conc ≥ poly(d ℓ /ϵ). Then, with probability atleast 9/10 over S, we have that for all α ∈ N d with ∥α∥ 1 ≤ ℓ,E D [f (x) • x α ] -E X [f (x) • x α ] ≤ ϵ. Proof. For α ∈ N d , let Z = E X [f (x) • x α ] be the empirical mean over the samples. Let Z = E D [f (x)•x α ] be the true mean. Clearly, E X [ Z] = Z. Thus, we have that P X [| Z -Z| ≥ ϵ] ≤ Var X [ Z] ϵ 2 . We have that Var X [ Z] ≤ 1 mconc Var[f (x) • x α ]. We have that Var[f (x) • x α ] ≤ E D [x 2α ] from the fact that f takes values in {±1}. When D = Unif{±1} d , x 2α = 1. When D = N d , we have that E D [x 2α ] ≤ poly(d ℓ )(see Proposition 2.5.2 [Ver18]). Thus, Thus, choosing m conc = poly(d ℓ /ϵ), we have that P X [| Z -Z| ≥ ϵ] ≤ ϵ d Ω(ℓ) .We focus on functions whose values only depend on the projection of the input on some lowdimensional 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 a function f : R d → {±1} is a k-subspace junta if there exists W ∈ R k×d with ∥W ∥ 2 = 1 and W W ⊤ = I k as well as a functionF : R k → {±1} such that f (x) = f W (x) = F (W x) for any x ∈ R dSince such functions only depend on a low-dimensional subspace, one might hope to exploit this property to 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, it turns out that testing the localized discrepancy with respect to a notion of subspace neighborhood can be benefited by the low-dimensional structure. In particular, we 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 (γ s , γ e )-subspace neighborhood N s : H → Pow(C) as follows for any f = f V ∈ H.N s ( f V ) = {f W ∈ C | ∥W -V ∥ 2 ≤ γ s and P x∼N [f (x) ̸ = f (x)] ≤ γ e }To design efficient testers for localized discrepancy in terms of the subspace neighborhood, we also use the notion of boundary of concepts and we require the boundaries to be smooth, meaning that the measure of the region close to the boundaries scales proportionally to its thickness. Formally, we provide the following definitions.). Let F : R k → {±1} some concept. For ϱ ≥ 0, we denote ∂ ϱ F the ϱ-boundary of F , i.e., the region {x ∈ R k : ∃z ∈ R k with ∥z∥ 2 ≤ ϱ and F (x+z) ̸ = F (x)}.Definition D.4 (Smooth Boundary). Let F : R k → {±1}. For σ ≥ 1, we say that F has σ-smooth boundary with respect to N k if for any ϱ ≥ 0P x∼N k [x ∈ ∂ ϱ F ] := P x∼N k [∃z : ∥z∥ 2 ≤ ϱ, F (x + z) ̸ = F (x)] ≤ σϱAs we will show shortly, the choice of the subspace neighborhood not 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 of low-dimensional marginals. More formally, we consider structured distributions to be as follows. E x∼D ′ [(v • x) 2p ] ≤ µ c (p).U of dimension k, if Q is the density of the marginal of D on U we have Q(x) N k (x) ≤ µ ac (R) for any x ∈ R k with ∥x∥ 2 ≤ R.Moreover, if k = d, we simply say that D is (µ c , µ ac )-structured.Remark D.6. We note that the two conditions of Definition D.5 are not always independent. For example, if µ ac (R) = O(1), then the distribution Q of condition 2 is subgaussian, which implies a bound on µ c (p) for all p ∈ N (i.e., implies some version of condition 1). However, the anticoncentration condition does not always imply the concentration condition (e.g., if µ ac (R) = Θ(e R 2 /2 )) and both conditions are important.For example, isotropic log-concave distributions are structured on k-dimensions with µ c (p) ≤ (O(p)) 2p and µ ac (R) = (O(k)) k exp( R 2 2 ).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 µ c : N → R ≥1 , µ ac : R + → R ≥1 , p ∈ N, R, σ, σ ≥ 1 and γ s , γ e ∈ (0, 1). Let also H (resp. C) be a class whose elements are k-subspace juntas over R d with σ-smooth (resp. σ-smooth) boundaries. Consider D to be the class of distributions over R d that are (µ c , µ ac )-structured on k-dimensions and N s : H → Pow(C) the (γ s , γ e )-subspace neighborhood. For any ϵ ∈ (0, 1), there is a (N s , ψ + ϵ)-tester (Algorithm 3) for localized discrepancy from N d with respect to D with sample complexity m = 10µc(2) (µc(1))2 d 4 + 12R 2p kµc(p) + 14k( √ 2π exp(R 2 )) k µac(R √ k)η k ln( 3R η ) + O( 1 ϵ 2 ) and time complexity O(md 3 + mdk(2⌈ R η ⌉) k ), where η = γsR p 2 σ √ k µ c(1)/µ c (p) and the error parameter ψ isψ = 14kµ c (p) R 2p + 12 2kR 2p µ c (1) ln µ ac (R √ k) µ c (p) 1 2 µ ac (R √ k)σγ s + 2µ ac (R √ k)γ eFor different target distribution classes we obtain different results, that reveal a trade-off between universality and the size of the subspace neighborhood tested. To accept wider classes of distributions, we restrict to testing localized discrepancy with respect to narrower neighborhoods, which is parameterized by γ s and γ e 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.Algorithm 3: Cylindrical Grids Tester Input: Set X of points in R d , matrix V ∈ R k×d , parameters p ∈ N, R ≥ 1, η > 0 Compute the matrix M = E x∼X [xx ⊤ ]G η,R = {[i 1 η, (i 1 + 1)η] × • • • × [i k η, (i k + 1)η] : i 1 , . . . , i k ∈ I} for each grid cell G ∈ G η,R doCompute the quantity P x∼X [V x ∈ G] and reject if the value is larger than2µ ac (R √ k) P x∼N [V x ∈ G]. end Otherwise, accept.Corollary D.8. Let ϵ ∈ (0, 1), let H, C, σ, σ be as in Theorem D.7 and let N s : H → Pow(C) be the (γ s , γ e )-subspace neighborhood (on k dimensions). For a class of distributions D over R d , there is a (N s , ϵ)-tester for localized discrepancy from N d with respect to D in each of the following cases for appropriately large universal constants C 1 , C 2 ≥ 1.1. D = {N d }, σγ s ≤ γ e ≤ ( ϵ C1k ) C2. The tester has time and sample complexitypoly(d)( k ϵ ) O(k) (σ σ) k .2. D is the class of C-subgaussian and isotropic log-concave measures over R d for some C = O(1) and σγ s ≤ γ e ≤ ( ϵ C1 ) C2k . The tester has time and sample complexitypoly(d)( k ϵ ) O(k 2 ) (σ σ) k .3. D is the class of isotropic log-concave measures over R d and alsoσγ s ≤ γ e ≤ ( 1 C1 ) -C2k 2 log 2 (1/ϵ) .The tester has time and sample complexity Proof. To apply Theorem D.7 in each case, it suffices to show bounds for µ c (p) and µ ac (R √ k) for each of the choices for D. We then pick p = log(1/ϵ) in Cases 1,2 and 3 and p = 1 in Case 4 and R sufficiently small to achieve error guarantee ϵ. For Case 1, µ c (p) ≤ (Cp) p and µ ac (Rpoly(d)k O(k 3 log 2 (1/ϵ)) (σ σ) k .√ k) ≤ 1. For case 2, µ c (p) ≤ (2Cp) p and µ ac (R √ k) ≤ (Ck) k e kR 2 /2 . Finally, for Case 3, µ c (p) ≤ (Cp) 2p and µ ac (R √ k) ≤ (Ck) k e kR 2 /2. These bounds follow from properties of log-concave and subgaussian distributions (see, e.g., [LV07, Ver18] ).In order to prove Theorem D.7, we first provide a tester which can certify that the mass assigned by the tested distribution to the region near the boundary of any function with smooth boundary is 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 a cover the low-dimensional space by a grid of bounded size and checking whether the probability of 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 a certificate that the mass of the tested distribution close to the boundary of any smooth function is appropriately bounded, because such regions can be covered by the union of a relatively small number of grid cells (see Figure 2 ). Lemma D.9 (Grids Tester). Let µ c : N → R + , µ ac : R + → R + , p ∈ N, R, σ ≥ 1 and ϱ ∈ (0, 1). There is a tester T which, upon receiving a set X of vectors in R k , and in time |X| • (O( R √ k ϱ )) k , either accepts or rejects and satisfies the following.(a) (Soundness.) If T accepts, then for any F : R k → {±1} with σ-smooth boundary we haveP x∼X [x ∈ ∂ ϱ F ] ≤ 2kµ c (p) R 2p + 4σϱ µ ac (R √ k) (b) (Completeness.) If X consists of at least 12R 2p kµc(p) + 14k(3 √ 2πk exp(R 2 )) k µac(R √ k)ϱ k ln( 9Rk ϱ ) i.i.d. examples from some (µ c , µ ac )-structured distribution over R k , then T accepts with probability at least 99%.Proof. Let η = ϱ 3 √ k be some parameter, I = {-⌈ R η ⌉, . . . , -1, 0, . . . , ⌈ R η ⌉ -1} be a set of indices and G η,R = {[i 1 η, (i 1 + 1)η] × • • • × [i k η, (i k + 1)η] : i 1 , .. . , i k ∈ I} the corresponding finite grid with cell length η (each cell corresponds to a hypercube in R k , the cartesian product of k intervals each of length η). The tester does the following.1. Computes the quantity P x∼X [∥x∥ ∞ > R] and rejects if the computed value is larger than2kµc(p) R 2p .2. For each cell G in the grid G η,R , computes the quantity P x∼X [x ∈ G] and rejects if the computed value isP x∼X [x ∈ G] > 2µ ac (R √ k) P x∼N k [x ∈ G].3. Otherwise, the tester accepts. Combining the first inclusion in expression (D.1) with the fact that the tester has accepted, the quantityP x∼X [x ∈ ∂ ϱ F ] is bounded as follows. P x∼X [x ∈ ∂ ϱ F ] ≤ P x∼X [∥x∥ ∞ > R] + G∈ G P x∼X [x ∈ G] ≤ 2kµ c (p) R 2p + 2µ ac (R √ k) G∈ G P x∼N k [x ∈ G]For any G, G ′ ∈ G with G ̸ = G ′ , the events that x ∈ G and that x ∈ G ′ are mutually exclusive.Therefore G∈ G P x∼N k [x ∈ G] = P x∼N k [x ∈ ∪ G∈ G G] ≤ P x∼N k [x ∈ ∂ ρF ],where the final inequality follows from the second inclusion in expression (D.1). Since F has σ-smooth boundary, we haveP x∼N k [x ∈ ∂ ρF ] ≤ σ ρ.Overall, we haveP x∼X [x ∈ ∂ ϱ F ] ≤ 2kµ c (p) R 2p + 2σ(ϱ + η √ k)µ ac (R √ k) ≤ 2kµ c (p) R 2p + 4σϱ µ ac (R √ k) , as desired.Completeness. Suppose, now, that the examples X are drawn independently from a (µ c , µ ac )structured distribution Q. We first show that, with probability at least 1-1 200 , we haveP x∼X [∥x∥ ∞ > R] ≤ 2kµc(p)R 2p . We first bound the quantity P x∼Q [∥x∥ ∞ > R], by using Markov's inequality as follows.P x∼Q [∥x∥ ∞ > R] ≤ k sup v∈S k-1 P x∼Q [|v • x| > R] ≤ k sup v∈S k-1 E x∼Q [(v • x) 2p ] R 2p ≤ kµ c (p) R 2p , since Q is structured.By the multiplicative Chernoff bound10 , we have thatP x∼X [∥x∥ ∞ > R] ≤ 2 P x∼Q [∥x∥ ∞ > R] with probability at least 1 -exp(-|X| kµc(p) 2R 2p ) ≥ 1 -1 200 , since |X| ≥ 12R 2p kµc(p) .We will show that for eachG ∈ G η,R , P x∼X [x ∈ G] ≤ 2µ ac (R √ k) P x∼N k [x ∈ G], with probability at least 1 -exp(-|X| 2 µ ac (R √ k)η k /( √ 2πe R 2 ) k ).The desired result then follows by a union bound over G η,R (where|G η,R | ≤ (3R/η) k ) and the fact that |X| ≥ 14k( √ 2π exp(R 2 )) k µac(R √ k)η k ln( 3R η ).We first bound P x∼Q [x ∈ G] as follows by using the fact that Q is structured and∥x∥ 2 ≤ ∥x∥ ∞ √ k ≤ R √ k for all x ∈ G (because G ∈ G η,R ). P x∼Q [x ∈ G] = x∈G Q(x) dx ≤ µ ac (R √ k) x∈G N (x) dx = µ ac (R √ k) P x∼N [x ∈ G]By the multiplicative Chernoff bound, we once more have thatP x∼X [x ∈ G] ≤ 2 P x∼Q [x ∈ G] with probability at least 1 -exp(-|X| 2 µ ac (R √ k) P x∼N [x ∈ G]) and conclude the proof by observing thatP x∼N [x ∈ G] ≥ ( η √ 2π exp(R 2 ) ) k .Remark D.10. We note that Lemma D.9 is not specialized to the Gaussian distribution. The only requirement is 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 it could also be defined with respect to some other distribution. The concentration condition 1 is always the same.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 on the relevant subspace for f (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.i.d. samples from D ′ and let η = γsR p 2 σ √ k µc(1) µc(p) . Let ( f V , X) be an instance of the localized discepancy testing problem (see Definition 1.1). We run Algorithm 3 with input (X, V, p, R, η) and accept (or reject) accordingly.Soundness. Suppose that the algorithm accepts. We will show thatP x∼X [ f (x) ̸ = f (x)] ≤ ψ for any f ∈ N s ( f ).Since the event that f (x) ̸ = f (x) is independent for each x ∈ X, we may apply the Hoeffding bound to show thatP x∼D ′ [ f (x) ̸ = f (x)] ≤ ψ + ϵ with probability at least 3/4 whenever |X| ≥ 3 ϵ 2 .To bound the empirical quantity, we have the following, for R s = R p (µ c (1)/µ c (p)) 1/2 and ϱ = γsRs σ .P x∼X [F (W x) ̸ = F (V x)] ≤ P x∼X [F (W x) ̸ = F (V x)] P1 + P x∼X [F (V x) ̸ = F (V x)] P2For the term P 1 , we observe that F (W x) = F ((W -V )x + V x) and thereforeP 1 ≤ P x∼X [∥(W -V )x∥ 2 ≥ γ s R s ] + P x∼X [∃z ∈ R k : ∥z∥ 2 ≤ γ s R s , F (V x + z) ̸ = F (V x)] = P x∼X [∥(W -V )x∥ 2 ≥ γ s R s ] + P x∼X [V x ∈ ∂ γsRs F ]By applying Chebyshev's inequality for the first term in the above expression and Lemma D.9 for the second term (note that we have chosen η ≤ γsRs 3 √ k and Algorithm 3 runs the tester corresponding to Lemma D.9), we obtain the following bound for P 1 (recall that ∥W -V ∥ 2 ≤ γ s and ∥(W -V )x∥ 2 ≤ ∥W -V ∥ 2 ∥ proj U x∥ 2 , where U is the span of the columns of the matrix W -V ).P 1 ≤ k sup v∈S d-1 E x∼X [(v • x) 2 ] R 2 s + 2kµ c (p) R 2p + 4σγ s R s µ ac (R √ k) ≤ 2kµ c (1) R 2 s + 2kµ c (p) R 2p + 4σγ s R s µ ac (R √ k)The last inequality follows from the spectral bound on the empirical covariance matrix M = E x∼X [xx ⊤ ] implied by Algorithm 3 upon acceptance.For the term P 2 , consider the set of grid cells G with non-zero intersection with the disagreement region, i.e., G = {G ∈ G η,R : there isx with V x ∈ G and F (V x) ̸ = F (V x)}. Recall that ϱ = η √ k and let Gin be the interior part of G, i.e., Gin = {G ∈ G : for any x with V x ∈ G we have F (V x) ̸ = F (V x)}}. Let x be such that ∥V x∥ ∞ ≤ R, F (V x) ̸ = F (V x) and V x / ∈ ∂ ϱ F ∪ ∂ ϱ F .It must be that V x lies within some grid cell in Gin . To see this, note that V x must be in exactly one grid cell G in G (by definition of G) and if this grid cell was in G \ Gin , this would imply that for some x ′ with V x ′ ∈ G we would have eitherF (V x) ̸ = F (V x ′ ) or F (V x) ̸ = F (V x ′ ) (because F, F disagree on V x but agree on V x ′ ). However, ∥V x -V x ′ ∥ 2 ≤ η √ k = ϱ,because they are in the same grid cell and we conclude that V x ∈ ∂ ϱ F ∪ ∂ ϱ F , which is a contradiction. Overall, we have the following.P 2 ≤ P x∼X [∥V x∥ ∞ > R] P21 + P x∼X [V x ∈ ∂ ϱ F ] P22 + P x∼X [V x ∈ ∂ ϱ F ] P23 + G∈ Gin P x∼X [V x ∈ G] P24For the term P 21 , we use the bound implied by Algorithm 3, for the terms P 22 , P 23 we apply Lemma D.9 and for the term P 24 , we use the fact that (upon acceptance)P x∼X [V x ∈ G] ≤ 2µ ac (R √ k) P x∼N [V x ∈ G]to obtain the following.P 24 ≤ 2µ ac (R √ k) G∈ Gin P x∼N [V x ∈ G] ≤ 2µ ac (R √ k) P x∼N [F (V x) ̸ = F (V x)]We bound the quantityP x∼N [F (V x) ̸ = F (V x)] as follows. P x∼N [F (V x) ̸ = F (V x)] ≤ P x∼N [F (W x) ̸ = F (V x)] + P x∼N [F (W x) ̸ = F (V x)] ≤ γ e + P x∼N [∥(W -V )x∥ 2 > γ s R ′ ] + P x∼N [V x ∈ ∂ γsR ′ F ]≤ γ e + 4ke -R ′2 2k + σγ s R ′ where the last inequality follows from Gaussian concentration and the fact that F has σ-smooth boundary. By choosingR ′ = (2k ln( R 2p µac(R √ k) µc(p))) 1/2 , we obtain thatP 24 ≤ 2µ ac (R √ k)γ e + 4kµ c (p) R 2p + 2σγ s µ ac (R √ k) 2k ln R 2p µ ac (R √ k) µ c (p) 1/2Overall, for the term P 2 we have the following bound.P 2 ≤ 10kµ c (p) R 2p + 10σγ s R p 2kµ c (1) µ c (p) µ ac (R √ k)(ln µ ac (R √ k)) 1/2 + 2γ e µ ac (R √ k)Combining the bounds for P 1 and P 2 , we obtain the desired result. 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 a TDS learning result for balanced convex subspace juntas in the realizable setting. The class of balanced convex subspace juntas is defined as follows. Definition D.11 (Balanced Convex Subspace Juntas). A concept f : R d → {±1} is a β-balanced convex k-subspace junta if it is β-balanced (see Definition A.1), convex and a k-subspace junta (see Definition D.1).We make use of known algorithms from PAC learning that are guaranteed to 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 β ∈ (0, 1/2), d, k ∈ N, let C be the class of β-balanced convex k-subspace juntas over R d . For any ϵ ∈ (0, 1), there is a (decoupled) ϵ-TDS learner for C with respect to N d in the realizable setting, which, for the learning phase, uses poly(d)( 1 β ) poly(k/ϵ) samples and time and, for the testing phase, uses poly(d)(k/ϵ) O(k) samples and time. Moreover, in the same setting, there is a D-universal ϵ-TDS learner for C for each of the cases listed in Table 2 .Testing Run-Time. To bound the testing run-time we use Corollary D.8, where σ = poly(k) (because C is the class of convex subspace juntas and due to Lemma B.8) and σ = poly(k/γ), because f is a polynomial threshold function of degree poly(k/γ) and, therefore, has poly(k/γ)smooth boundary according to Lemma B.1. err( f ; D test X Y ) = P x∼D test X Y [f * (x) ̸ = f (x)] ≤ P x∼D test X [∥W * x∥ 2 > k/γ] + P x∼D test X [ f (x) ̸ = f (x)] ≤ ϵ 3 + P x∼N d [ f (x) ̸ = f (x)] + ϵ 3 ≤ 2ϵ 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 a hypothesis with the properties specified in Theorem D.13 and, in particular, lies within the subspace neighborhood of f . 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, no 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 R ≥ 1 and r, β ∈ (0, 1), we say that a function F : R k → {±1} is (R, r)-locally β-balanced if for any ϱ ≤ r and x ∈ R k with ∥x∥ 2 ≤ R, the following is true.P z∼N k [F (z) = F (x) | z ∈ B k (x, ϱ)] > βFor a subspace junta f (x) = F (W x), we say that f is (R, r)-locally β-balanced on the relevant subspace if F is (R, r)-locally β-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 disagreement 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 C be some concept classes. We define the (Gaussian) γ e -disagreement neighborhood N e : H → Pow(C) as follows for any f ∈ H.N e ( f ) = {f ∈ C | P x∼N [f (x) ̸ = f (x)] ≤ γ e }We also define the boundary proximity tester, which directly tests whether the probability of falling close to the boundary of some reference hypothesis f is appropriately bounded. This testing problem can be solved efficiently, for example, for the fundamental class of halfspace intersections.Definition E.3 (Boundary Proximity Tester). For σ ≥ 1, ϱ ∈ (0, 1), let H be some class of functions from R d to {±1} and let D be some class of distributions over R d . The tester T is called a (ϱ, σ)boundary proximity tester for H with respect to D if, upon receiving some f ∈ H and a set X of points in R d , the tester either accepts or rejects and satisfies the following.(a) (Soundness.) If T accepts, thenP x∼X [x ∈ ∂ ϱ f ] ≤ σϱ.(b) (Completeness.) If X consists of (at least) m T i.i.d. 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, disagreement-localized discrepancy testing is tractable and since its error is low, the ground truth is likely within the disagreement neighborhood and disagreement-localized discrepancy testing suffices to guarantee low test error.In order to obtain a localized discrepancy tester assuming access to a boundary proximity tester, we first show a 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 to 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 k → {±1}, where F is (R, ϱ)-locally β-balanced and F, F have disagreement γ = β inf ∥x∥2≤R P z∼N k [z ∈ B k (x, ϱ)], i.e., P z∼N k [F (z) ̸ = F (z)] ≤ γ.Then, for any x with ∥x∥ 2 ≤ R and F (x) ̸ = F (x), we have x ∈ ∂ ϱ F .Proof of Proposition E.4. Suppose, for contradiction, that there exists some x ∈ R k with ∥x∥ 2 ≤ R and F (x) ̸ = F (x), for which x / ∈ ∂ ϱ F . Then, it must be that F (z) = F (x) for all z ∈ B k (x, ϱ) (otherwise, x ∈ ∂ ϱ F ). We have thatP z∼N k [F (z) ̸ = F (z)] ≥ P z∼N k [z ∈ B k (x, ϱ) and F (z) ̸ = F (z)] and also F (z) ̸ = F (z) is equivalent to 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, P z∼N k [F (z) ̸ = F (z)] ≥ P z∼N k [z ∈ B k (x, ϱ) and F (z) = F (x)] > γ,by assumption, and we reached contradiction.Remark E.5. Note that Proposition E.4 is not specialized to the Gaussian disagreement between F 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 a non-universal localized discrepancy tester (Theorem E.6). If 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). Let p ∈ N, R, σ ≥ 1, r, β ∈ (0, 1) and 0 ≤ γ e ≤ βr k k k/2 e -2R 2 . Let also H and C be a classes whose elements are k-subspace juntas over R d and N e : H → Pow(C) the γ e -disagreement neighborhood. Assume that the elements of C are (R, r)-locally β-balanced on the relevant subspaces and let T be a (ϱ, σ)-boundary proximity tester for H w.r.t. N d , requiring m T samples, with ϱ = ( γe β ) 1/k √ ke 2R 2 /k . For any ϵ ∈ (0, 1), there is a (N e , ψ + ϵ)-tester for localized discrepancy from N d with respect to N d with sample complexity m = m T + O(dk) 4p+1 + O( 1 ϵ 2 ), that calls T once and uses additional time O(md 2p+1 ), where the error parameter ψ isψ = 2 4kp R 2 p + σ √ k γ e exp(2R 2 ) β 1/kProof of Theorem E.6. Let ϱ = (γ e /β) 1/k √ k exp(2R 2 /k), ∆ = 1 (2kd) 2p and let ( f , X) be an instance of the localized discrepancy problem (see Definition 1.1). The algorithm does the following. 
classes with low sandwiching degree: 
 Prior work on TDS learning by [KSV24b] showed that the existence of degree-ℓ L 2 -sandwiching approximators implies TDS learning in time d O(ℓ) . A major question left open was whether the more traditional notion of L 1 sandwiching (see Definition C.1) 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 0 ) and the first TDS learning results for degree-2 polynomial threshold functions (see Table 1 ). For more details, see Appendix C. Theorem 3.1 (L 1 -sandwiching implies TDS learning). Let ϵ, δ ∈ (0, 1) and let C ⊆ {X → {±1}} be a concept class such that the ϵ-approximate L 1 -sandwiching degree of C under D is ℓ(ϵ) ∈ N.Then, there exists a TDS learning algorithm for C with respect to D up to error λ + opt train + O(ϵ) and fails with probability at most δ with time and sample complexity poly(d ℓ(ϵ) , 1 ϵ ) log(1/δ). Note that prior work [KSV24b] had only obtained a bound of O(λ) in the above error guarantee. Our techniques allow us to achieve the optimal dependence of simply λ.Training Marginal Time Prior Work1 Degree-2 PTFs N d or Unif({±1} d ) d O(1/ϵ 9 ) None 2 Circuits of size s, depth t Unif({±1} d ) d O(log(s/ϵ)) O(t) d √ s•O(log(s/ϵ)) O(t)only for formulas Table 1 : New results for TDS learning through L 1 sandwiching. For constant-depth formulas, we achieve an exponential improvement compared to [KSV24b] (which used L 2 -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 L 2 -sandwiching approach of [KSV24b] provided TDS learning algorithms with similar runtime as the one obtained here, but their error guarantee was O(λ) + ϵ instead of λ + opt train + ϵ (where opt train = min f ∈C err(f ; D train X Y )), which is the best known upper bound on the error, even information theoretically (see [BDBC + 10, DLLP10]).Localized discrepancy testing via Chow matching. The improvements we obtain here are based on the idea of substituting the moment-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] E x∼D test X [ f (x)x α ] for all low-degree monomials x α = d i=1x αi i and reject if they do not match the corresponding quantities E x∼D [ f (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-degree chow matching tester is a tester for localized discrepancy for the neighborhood N( f ) = C, i.e., it certifies thatP x∼D test X [ f (x) ̸ = f (x)] ≤ P x∼D [ f (x) ̸ = f (x)] + ϵ for 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.e., 2P x∼D test X [ f (x) ̸ = f (x)] = 1 -E x∼D test X [ f (x)f (x)],and, because f ∈ C, it is sandwiched by two polynomials p up , p down , which impliesE x∼D test X [ f (x)f (x)] ≥ E x∼D test X [ f (x)p up (x)] - E x∼D test X [p up (x) -p down (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 a particular candidate hypothesis f , but actually considers the whole concept class C to be inside the neighborhood of f . Since the concept f * that achieves λ = min f ∈C (err(f ; D train X Y ) + err(f ; D test X Y )) lies within C 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.P x∼D test X [f * (x) ̸ = f (x)] - P x∼D train X [f * (x) ̸ = f (x)] ≤ ϵ (C.1)We also have that err( f ; D train X Y ) ≤ err A with probability at least 1 -δ/2 from the error guarantee of A. We are now ready to bound err( f ; D test X Y ). We have thaterr( f ; D test X Y ) ≤ err(f * ; D test X Y ) + P x∼D test X [f * (x) ̸ = f (x)] ≤ err(f * ; D test X Y ) + P x∼D train X [f * (x) ̸ = f (x)] + ϵ ≤ err(f * ; D test X Y ) + P (x,y)∼D train X Y [f * (x) ̸ = y] + P (x,y)∼D train X Y [ f (x) ̸ = y] ≤ err(f * ; D train X Y ) + err(f * ; D test X Y ) + err A ≤ λ + err A + ϵ .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 λ.Completeness This follows immediately from the completeness guarantee of Theorem C.3. As seen before, the success probability can be boosted to 1 -δ/2. Thus, the tester accepts when D test X = D train X with probability at least 1 -δ/2.Remark C.5. The above theorem completely decouples training and testing. This is in contrast to the Klivans et al. 2023 which don'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. In particular, we use the following theorem from [KKMS08] . Theorem C.6 (Theorem 5 from [KKMS08] ). Let D be a distribution on X × {±1} for X ⊆ R d with marginal D X . Let ϵ, δ ∈ (0, 1). Let C be a class of functions such that for all f ∈ C, there exists polynomials p of degree ℓ such that E x∼Dx [|f (x) -p(x)|] ≤ ϵ. Then there exists an agnostic learning algorithm A that has run time and sample complexity at most poly(d ℓ , 1/ϵ, log(1/δ)) that outputs a hypothesis f such that with probability at least 1 -δ, we have thatP (x,y)∼D [y ̸ = f (x)] ≤ inf f ∈C P (x,y)∼D [f (x) ̸ = y]Armed with this, we give our end to end result that L 1 sandwiching implies TDS learning. Theorem C.7 (L 1 -sandwiching implies TDS learning). Let D be a distribution over a set X ⊆ R d . Let C ⊆ {X → {±1}} be a concept class. Let ϵ, δ ∈ (0, 1). Let H = {±1} X . Assume that the following are true.1. (L 1 -sandwiching) The ϵ-approximate L 1 sandwiching degree of C under D is at most ℓ with bound B. 
non-parametric low-dimensional classes: 
 For non-parametric classes like convex sets over R d , dimension-efficient TDS learning is impossible, even from an information-theoretic perspective [KSV24b] and 2 Ω(d) time is required even in the realizable setting. However, the best known upper bound on the L 1 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 a TDS learning algorithm that runs in time doubly exponential in d. Improving on the doubly exponential bound based on L 1 -sandwiching, we provide a realizable TDS learner with singly exponential (in poly(d)) runtime for convex sets that are ϵ-balanced, meaning that the Gaussian mass of both the interior and the exterior of the convex set is at least ϵ. For convex sets with only a few relevant dimensions, our results actually give dimension-efficient TDS learners. For more details, see Appendix D. Theorem 4.1 (TDS Learning of Convex Subspace Juntas). For ϵ ∈ (0, 1/2), d, k ∈ N, let C be the class of ϵ-balanced convex sets over R d with k relevant dimensions. There is an O(ϵ)-TDS learner for C with respect to N d in the realizable setting, which, for the training phase, uses poly(d)2 poly(k/ϵ) samples and time and, for the testing phase, uses poly(d)(k/ϵ) O(k) samples and time.We note that the balancing assumption is 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. Importantly, 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 is 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 D k be the class of distributions D over R d such that E x∼D [(v • x) 4 ] ≤ C for any v ∈ S d-1 and for any subspace W ⊆ R d of dimension at most k, the marginal density of D on W is upper bounded by C k 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 D k -universal O(ϵ)-TDS learner for k-dimensional ϵ-balanced convex sets over R d with respect to N d in the realizable setting, which, for the training phase, uses poly(d) exp(2 -O(k 2 /ϵ) ) samples and time and, for the testing phase, uses poly(d)k O(k 3 /ϵ 2 ) samples and time.We remark that the testing time for the universal TDS learner of Theorem 4.2 is still singly exponential in poly(k), although the dependence on ϵ is exponentially worse. Having lower testing runtime is a 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 Theorems 4.1 and 4.2, we once more make use of the localized discrepancy testing framework. In particular, we identify low-dimensionality (Definition D.1) 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 to the subspace neighborhood (Theorem D.7). The subspace neighborhood N s ( f ) contains low-dimensional concepts f whose relevant subspace is geometrically close to the relevant subspace for f (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., [Vem10a, KSV24a] and Theorem D.13) to ensure that the training phase will output some hypothesis f such that the ground truth f * lies within N s ( f ).In other words, we exploit the existence of training algorithms with stronger guarantees (i.e., approximate subspace recovery) than merely training error bounds, to relax the discrepancy testing problem to a 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 ∈ N s ( f ) under the test distribution in two parts:(1) the disagreement between f and a rotated version f of f where the input x is projected on the relevant subspace of the given hypothesis f 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 ∈ N s ( f )). We conclude that f and f can only disagree far from the origin and, hence, testing that the test marginal is appropriately concentrated suffices to 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 f is known. We construct a 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-boundary region does not introduce a significant error blow-up, it is important that f and f have smooth boundaries (see Figure 2 in the appendix). 
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 a 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 D 1 be the class of distributions D over R d such that for any v ∈ S d-1 we have E x∼D [(v•x) 4 ] ≤ Cand, also, that the one-dimensional density of the projection v • x where x ∼ D is upper bounded by C, where C is some positive universal constant. Then the following is true (see also Theorem E.10). Theorem 5.1 (Universal TDS Learning of Balanced Intersections). For ϵ ∈ (0, 1/2), d, k ∈ N, there is a D 1 -universal O(ϵ)-TDS learner for the class of ϵ-balanced intersections of k halfspaces over R d w.r.t. N d in the realizable setting, which, for the training phase, uses poly(d) exp(O(k 5 /ϵ)) samples and time and, for the testing phase, uses poly(d, k, 1/ϵ) samples and time.For comparison, the previous state-of-the-art TDS learning algorithm for halfspace intersections by [KSV24a] had overall runtime d O(log(k/ϵ)) + poly(d) exp(O(k 6 /ϵ 8 )) and testing runtime d O(log(k/ϵ)) +poly(d)(k/ϵ) O(k 2 ) (although training and testing were not explicitly separated). Hence, the overall runtime of the algorithm of Theorem 5.1 is better than the previous state-of-the-art, but also enjoys two additional properties: (1) the testing time is fully polynomial and (2) the tester is universal with respect to a wide class (of multimodal and even heavy-tailed distributions).We note that it is not by chance that these two properties are satisfied simultaneously: they both relate to the fact that it suffices to solve a 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 in some regimes, we may trade-off universality and test-time efficiency to obtain the following result (see Theorem E.10). Theorem 5.2 (TDS Learning of Balanced Intersections). For ϵ ∈ (0, 1/2), d, k ∈ N, there is an O(ϵ)-TDS learner for the class of ϵ-balanced intersections of k halfspaces over R d w.r.t. N d in the realizable setting, which, for the training phase, uses poly(d)(k/ϵ) O(k 3 ) samples and time and, for the testing phase, uses (dk) O(log(1/ϵ)) 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(ϵ) error guarantee even when λ = min f ∈C (err(f ;D train X Y ) + err(f ; D test X Y )) is non-zero (but sufficiently small). For Theorem 5.1, the amount of noise that can be tolerated is λ = exp(-Õ(k/ϵ)), while for Theorem 5.2, the tolerated amount is λ = (k/ϵ) -O(k) (see Table 3 ). The amount of noise tolerated by the non-universal tester is more, because the test is more expensive and, therefore, does a 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.e., λ = O(ϵ).Discrepancy testing through boundary proximity. We once more use the framework of localized discrepancy testing, in order to 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 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 of 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., f ∈ N e ( f ) if the Gaussian disagreement P x∼N d [f (x) ̸ = f (x)] between f and f is small enough (see Definition E.2). In particular, we show that if f is a balanced intersection and f ∈ N e ( f ), then f and f can only differ either (1) far from the origin or (2) close to the boundary of f (see Proposition E.4 and Lemma E.12). Importantly, this property is point-wise: for any x ∈ R d such that f (x) ̸ = f (x), x will either satisfy (1) or (2) and, hence, no distribution over R d can fool our tester.In the heart of our proof is a geometric lemma which demonstrates that any balanced convex set is locally balanced as well (Lemma E.12), meaning that for any point x ∈ R d , there is a large number of points near x with the same label as x. Therefore (unless the norm of x is large), any hypothesis f 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 1 for the case when the label of x is 1. The other case is simpler and follows by the existence of a separating hyperplane between a convex set and any point outside it).Figure 1 : If x lies within a balanced convex set K, then many points close to x lie within K as well, i.e., there is a cone R ′ with R ′ ⊆ B(x, ϱ) ∩ K, where B(x, ϱ) is a ball around x. The ball centered at x c exists due to the fact that K is balanced: any balanced convex set contains some ball with non-negligible radius. The convex hull of x and the ball at x c lies within K. (See also Fig. 3 ) Since we have a 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 N e ( f )). Hence, we may use any proper PAC learning algorithm for intersections of halfspaces under the Gaussian distribution. We use the algorithm by [DKS18b] (see also Theorem E.11). Remark 5.4. We note that the three important properties we used to apply the method of boundary proximity are that (1) the hypothesis f returned by the learning algorithm admits an efficient boundary proximity tester and (2) the ground truth f * is locally balanced and (3) that f and f * are both lowdimensional. 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 can 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 localized discrepancy testing which imply new results in TDS learning. Moreover, on the lower bounds side, in Appendix F, we show that global discrepancy testing is NP-hard even for simple classes under no further assumptions. It is an interesting open question to explore tight characterizations for dimension-efficient, universal or fully polynomial-time localized discrepancy testing.Lifting the balancing assumption. For our universal TDS learners (and universal discrepancy testers), we require that the underlying concept class only contains concepts that are not too biased towards one of the two possible labels under the training distribution (so that the training examples include enough information for localization). This condition is 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 assumption that the marginal of the training distribution is either the Gaussian distribution or the uniform distribution over the hypercube. 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 is 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 to the deployment population and another model should be considered.We use standard big-O notation (and Õ to hide poly-logarithmic factors), R d is the d-dimensional euclidean space and N d the standard Gaussian over R d , {±1} d is the d-dimensional hypercube and Unif({±1} d ) the uniform distribution over {±1} d , N is the set of natural numbers N = {1, 2, . . . } and x ∈ R d denotes a vector with x = (x 1 , . . . , x d ) and inner products x • v. For α ∈ N d , we denote with x α the product i∈[d] x αi i , M α = E[x α ] and ∥α∥ 1 = i∈[d] α i .For a polynomial7 p over R d and α ∈ N d , we denote with p α the coefficient of p corresponding to x α , i.e., we have p(x) = α∈N d p α x α . If p is a polynomial over {±1} d , then we express it in its multilinear form, using only coefficients p α with α ∈ {0, 1} d , i.e., p(x) = α∈{0,1} d p α x α . 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∥ 1 = i∈[d] |x i |, ∥x∥ 2 = ( i∈[d] x 2 i ) 1/2 and ∥x∥ ∞ = max i∈[d] |x i |. We denote with S d-1 the d -1 dimensional sphere on R d and, for x ∈ R k and r > 0, B k (x, r) = {y ∈ R d : ∥x -y∥ 2 ≤ r}.For any v 1 , v 2 ∈ R d , we denote with v 1 •v 2 the inner product between v 1 and v 2 and we let ∡(v 1 , v 2 ) be the angle between the two vectors, i.e., the quantity θ∈ [0, π] such that ∥v 1 ∥ 2 ∥v 2 ∥ 2 cos(θ) = v 1 • v 2 . For v ∈ R d , τ ∈ R, we call a function of the form x → sign(v • x) an origin-centered (or homogeneous) halfspace and a function of the form x → sign(v • x + τ ) a general halfspace over R d .We let X ⊆ R d be either the d-dimensional hypercube {±1} d or R d . For a distribution D over X , we use E D (or E x∼D ) to refer to the expectation over distribution D and for a given set X, we use E X (or E x∼X ) to refer to the expectation over the uniform distribution onX (i.e., E x∼X [g(x)] = 1 |X| x∈X g(x), counting possible duplicates separately). We let R + = (0, ∞). We define the notion of balance as follows.Definition A.1 (Balanced Concepts). For β ∈ (0, 1), we say that a function f :R d → {±1} is (globally) β-balanced if for any x ∈ R d we have P z∼N [f (z) = f (x)] > β.In this section, we prove that low dimensional polynomial threshold functions and convex sets have smooth boundary, i.e., a 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 a polynomial of degree ℓ over R k . Let F : R k → {±1} be the function defined as F (x) = sign(p(x)). Then, F has a Cℓ 3 k-smooth boundary with respect to N k for a large universal constant C.Proof. Let C be a large universal constant that we fix later. Let δ = 3Cℓ 3 γk. Define the setS := {x | ∃i ∈ [ℓ], ∥∇ i p(x)∥ 2 > (Cℓ 3 /δ) • ∥∇ i-1 p(x)∥ 2 }. Observe that P x∼N k [x ∈ ∂ γ F ] ≤ P x∼N k [x ∈ S] + P x∼N k [x ∈ ∂ γ f | 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 k → R of degree ℓ and x ∼ N k , the following event occurs with probability at least 1 -δ:∥∇ i p(x)∥ 2 ≤ (Cℓ 3 /δ)∥∇ i-1 p(x)∥ 2 , for all 1 ≤ i ≤ ℓ.Thus, we have thatP x∼N k [x ∈ S] ≤ δ. Now consider a point x / ∈ S.From a multivariate taylor expansion, we have that p(x+ z) = p(x) + α∈N k ,1≤|α|≤ℓ ∥z∥ 2 ≤ γ, we obtain that |p(x) -p(x + z)| ≤ 1≤|α|≤ℓ ∂ α p(x) • ∥z∥ |α| ∞ ≤ i∈[ℓ] ∥z∥ i 2 • ∥∇ i p(x)∥ 1 ≤ i∈[ℓ] γ i k i ∥∇ i p(x)∥ 2 ≤ i∈[l] γ i k i (Cℓ 3 /δ) i |p(x)| ≤ |p(x)|/2 .The first inequality follows from the multivariate Taylor expansion. The third inequality follows from the fact that ∥z∥ 2 ≤ γ and the bound on the number of monomials of size i by k 2i . The penultimate inequality follows from the definition of the set S and the last inequality is true by our choice of δ.Since |p(x) -p(x + z)| ≤ |p(x)|/2, we have that F (x) = F (x + z) for all z ∈ R k with ∥z∥ 2 ≤ γ.Thus, we have thatP x∼N k [x ∈ ∂ γ F | x / ∈ S] = 0. Thus, we have that P x∼N k [x ∈ ∂ γ F ] ≤ 3Cℓ 3 γk.We now move on to proving that low dimensional convex sets. To prove this, we 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 Γ(f ) is defined asΓ(f ) = lim inf δ→0 1 δ P z∼N (0,I k ) z ∈ A δ f \ A f ,whereA f = 1{x | f (x) = 1}, A δ f = {u : min v∈A f ∥u -v∥ 2 ≤ δ}.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 a 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 an argument uses the definition of Gaussian Surface area and a 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 λ ∈ (0, 1/2). Let S be a convex set on R k and let f (x) = 1{x ∈ S} be the indicator function of S. Then, we have thatP x∼N k [f (x) ̸ = f (x/ √ 1 -λ)] ≤ k log k √ λ.Proof. For any vector w ∈ R k with ∥w∥ 2 = 1, let f w : R + → R be the function defined as f w (r) = f (r • w). Also, note that f w is the indicator function of a one dimensional convex set.Observe thatP x∼N k [f (x) ̸ = f (x/ √ 1 -λ)] ≤ sup ∥w∥2=1 P r∼χ 2 (k) [f w ( √ r) ̸ = f w ( √ r/ √ 1 -λ)] from the fact that the k dimensional Gaussian conditioned on pointing in direction w is distributed as √ rw where r ∼ χ 2 (k). Here, χ 2 (k) is the one dimensional Chi-squared distribution with mean k.We have thus reduced the problem to one dimension. Consider a function g :R → R such that g(x) = 1{x ∈ [ a/(1 -λ), b/(1 -λ)]} where a, b are from R + ∪{+∞}. All one dimensional indicatorsof convex sets are of this form. We will now prove thatP r∼χ 2 (k) [g( √ r) ̸ = g( √ r/ 1 -λ)] ≤ kλ log(k/λ). Observe that P r∼χ 2 (k) [g( √ r) ̸ = g( r/1 -λ)] ≤ P r∼χ 2 (k) [r ∈ [a, a/(1 -λ)] ∪ [b, b/(1 -λ)]]. It suffices to bound P r∼χ 2 (k) [r ∈ [a, a/(1 -λ)]] for a ∈ R + as the claim then follows from a union bound. We bound this by splitting into two cases.Case 1: a ≥ 2k log(k/λ). Since χ 2 (k) is the distribution of the sum of squares of k independent N (0, 1) Gaussian random variables, we have that 2k) . Thus, when a ≥ 2k log(k/λ), we have thatP r∼χ 2 (k) [r ≥ a] ≤ k P x∼N (0,1) [|x| 2 ≥ a/k] ≤ ke -a/(P r∼χ 2 (k) r ∈ [a, a/(1 -λ)] ≤ P r∼χ 2 (k) r ≥ a ≤ λ.Case 2: a < 2k log(k/λ). Let ψ be the density function for χ 2 (k). It is a standard fact from probability that ψ(x) = x k/2-1 2 k/2 Γ(k/2) e -x/2 . For k = 1, it is a fact that ψ(x) ≤ 1. For k ≥ 2, by taking a derivative, we can see that this density function is maximized at x = k -2. We obtain thatψ(x) = (k -2) k/2-1 2 k/2 Γ(k/2) e -k/2+1 ≤ ((k -2) • e) k/2-1 2 k/2 (k/2) k/2-1 e -k/2+1 ≤ 1 2where the second inequality follows from the fact that Γ(t) ≥ t e t-1 for all t ≥ 2 and Γ(1) = 1.We have thatP r∼χ 2 (k) r ∈ [a, a/(1 -λ)] ≤ ∥ψ∥ ∞ • a (1/(1 -λ) -1) ≤ 4kλ log(k/λ) ≤ 4k log k √ λ .We get the first inequality from the upper bound on the density. The second follows from the fact that 1/(1 -λ) ≤ 1 + 2λ when λ < 1/2. The third inequality follows from the assumption on a. The final inequality follows from the fact that x log(1/x) ≤ √ x.We are now ready to prove the set of points inside the convex set that are close to it's boundary have small mass under the Gaussian. Lemma B.5. Let S be a convex set on R k . Let ϱ ∈ (0, 1). Then, we have thatP x∼N k [x ∈ S ∩∂ ϱ S] ≤ Ck log kϱ where C is a large universal constant.Proof. Define the function f : R k → R as f (x) = 1{x ∈ S}. We now use a restatement of Corollary 12 from [KOS08b] .Lemma B.6. Let g be a boolean function on R k . For any λ ∈ (0, 1), it holds thatP x,y∼N k g (x) ̸ = g √ 1 -λx + √ λy ≤ C √ λΓ(g)for large universal constant C.Let g be the function g(x) = f (x/ √ 1 -λ).Observe that g is also an indicator of a convex set. From [Bal93] we have that Γ(g) ≤ 4k 1/4 . Thus, applying Lemma B.6 to g, we obtain that for any λ ∈ (0, 1)P x,y∼N k f (x/ √ 1 -λ) ̸ = f x + λ 1 -λ y ≤ C √ λk 1/4where C is a large constant. Combining the above expression with Lemma B.4, we obtain that for any λ ∈ (0, 1/2),P x,y∼N k f (x) ̸ = f x + λ 1 -λ y ≤ C √ λk 1/4 + 2k log k √ λ . (B.1) Now, consider any point p in S ∩ ∂ ϱ S. Since S is convex, there exists a hyperplane h(x) = 1{w • x + b ≥ 0} for w ∈ R k with ∥w∥ 2 = 1 and b ∈ R such that h(y) = 1 for all y ∈ S and w • p + b ≤ ϱ.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,P z∼N k [w • γz ≤ -ϱ] ≥ 1 2 -ϱ 2γas the Gaussian density is upper bounded by 1 pointwise. Thus, for any γ > 0,P z∼N k [f (p + γz) ̸ = f (p)] ≥ 1 2 -ϱ 2γ .Combining this with Equation (B.1), we obtain that1 2 - ϱ 2 • 1 -λ λ • P x∼N k [x ∈ S ∩ ∂ ϱ S] ≤ C √ λk 1/4 + 2k log k √ λ .Setting λ = 4ϱ 2 and rearranging terms, we obtain thatP x∼N k [x ∈ S ∩ ∂ ϱ S] ≤ C ′ k log kϱ where C ′ is a sufficiently large universal constant.We now prove the smoothness result for points outside the set. Lemma B.7. Let S be a convex set on R k . Let ϱ ∈ (0, 1). Then, we have thatP x∼N k [x ∈ S c ∩ ∂ ϱ S] ≤ Ck 1/4 ϱwhere C is a sufficiently large universal constant.Proof. For t > 0, define the set S t as S t = {x ∈ R k | inf y∈S ∥x -y∥ 2 ≤ t}. We have thatP x∼N k [x ∈ S c ∩ ∂ ϱ ] = P x∼N k [x ∈ S ϱ \ S] = ϱ t=0 x∈∂St N (x; 0, I k )dx dt ≤ ϱ t=0 Ck 1/4 dt ≤ Ck 1/4 ϱwhere C is 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. Proof. The proof is immediate from Lemma B.5 and Lemma B.7.In this section, we present known results from pseudorandomness literature on the existence of sandwiching polynomials for various function classes with respect to Unif{±1} d and N d . 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 (δ, ℓ)-independent distributions.Definition B.9 ((δ, ℓ)-independent distribution). Let D, D ′ be distributions on R d . For δ > 0 and ℓ ∈ N, we say that the distributionD ′ is (δ, ℓ)-independent with respect to D if E x∼D [x α ] - E x∼D ′ [x α ] ≤ δ for all α ∈ N d .We drop the "with respect to D" when the distribution is clear from context. Let D, D ′ be distributions on X ⊆ R d and f : X → {±1}. For ϵ > 0, we say that D ′ ϵ-fools f with respect toD if E x∼D [f (x)] -E x∼D ′ [f (x)] ≤ ϵ (again, we drop the "with respect to" when the target distribution is clear from context). For a concept class C, we say that D ′ ϵ-fools C with respect to D if D ′ ϵ-fools f with respect to D for all functions f ∈ C.We will use the following result from [GKK23] which is a generalization of a result from [Baz09] . We will only need one direction of the result which we state below. Lemma B.10. [Theorem 3.2 from [GKK23] ] Let D be a distribution on X ⊆ R d . Let δ, ϵ > 0 and ℓ ∈ N. Let f : X → R d be a function that satisfies the following property: given any distribution D ′ that is (δ, ℓ)-independent with respect to D, we have thatE x∼D [f (x)] -E x∼D ′ [f (x)] ≤ ϵ.Then, there exists degree ℓ polynomials p down , p up such thatp down ≤ f ≤ p up and E x∼D [p up (x) - p down (x)] + δ(|p up | + |p down |) ≤ ϵ.In this section, the target distrbution is Unif{±1} d . We will find the following lemma useful.Lemma B.11. Let ϵ > 0 and ℓ ∈ N. Let f : {±1} d → {±1} be a function such that all (0, ℓ)-independent distributions ϵ-fool f . Then, there exists polynomials p up , p down of degree ℓ and coefficients bounded byO(d ℓ ) such that p down ≤ f ≤ p up and E x∼Unif{±1} d [p up (x) -p down (x)] ≤ O(ϵ).Proof. We use the following theorem from [AGM03] that states that for any (δ, ℓ)-distribution , there exists a (0, ℓ) distribution that is ϵ-close to it in TV distance.Lemma B.12 (Theorem 2.1 from [AGM03] ). For δ > 0 and ℓ ∈ N, let D be a (δ, ℓ)-independent distribution on {±1} d . Then, there exists a distribution D ′ that is (0, ℓ)-independent such that the TV distance between D and D ′ is at most δd ℓ .From the above claim, we have that any (ϵ/d ℓ , ℓ)-independent distribution 2ϵ-fools f . Thus, from Lemma B.10, there exists polynomials p up , p down of degree ℓ with coefficients bounded by O(d ℓ ) such that E x∼Unif{±1} d [p up (x) -p down (x)] ≤ 2ϵ. This proves the claim. Lemma B.13 (Sandwiching polynomials for degree 2 PTFs). Let C be the class of degree 2 PTFs. For ϵ > 0, the O(ϵ)-approximate L 1 sandwiching degree of C under Unif{±1} d is at most ℓ = Õ(1/ϵ 9 ) with coefficient bound O(d ℓ ).Proof. From [DKN10], we have that (0, ℓ)-independent distributions ϵ-fools C when ℓ = Õ(1/ϵ 9 ). Now, we apply Lemma B.11 to finish the proof.Lemma B.14 (Sandwiching polynomials for depth-t AC 0 ). Let C be the class of depth-t AC 0 circuits of size s on {±1} d . For ϵ > 0, the O(ϵ)-approximateL 1 sandwiching degree of C under Unif{±1} d is at most ℓ = (log s) O(t) log(1/ϵ) with coefficient bound O(d ℓ ).Proof. From [Bra10, Tal17, HS19], we have that (0, ℓ)-independent distributions ϵ-fools f when ℓ = (log s) O(t) log(1/ϵ). Now, we apply Lemma B.11 to finish the proof.Lemma B.15. Let ϵ > 0 and ℓ ∈ N. Let f : R d → {±1} be a function such that all (0, ℓ)independent distributions ϵ-fool f . Then, there exists polynomials p up , p down of degree ℓ and coefficients bounded byO(d ℓ ) such that p down ≤ f ≤ p up and E x∼N d [p up (x) -p down (x)] ≤ O(ϵ).Proof. From Lemma B.10, we have that there exists p up , p down of degree ℓ such that E x∼N d [p up (x)p down (x)] ≤ 2ϵ and p down ≤ f ≤ p up . 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 N d must have bounded coefficients. Lemma B.16. Let f : R d → {±1} be a function, and let p up and p down be degree-ℓ polynomials satisfying the following (i) for every x ∈ R d we have p up (x) ≥ f (x) ≥ p down (x). (ii) E x∈N (0,I) [p up (x) -p down (x)] ≤ 1. Then, the polynomials p up and p down 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 2 PTFs. For ϵ > 0, the O(ϵ)-approximate L 1 sandwiching degree of C under N d is at most ℓ = Õ(1/ϵ 8 ) with coefficient bound O(d ℓ ).Proof. From [DKN10], we have that (0, ℓ)-independent distributions ϵ-fools C when ℓ = Õ(1/ϵ 8 ). Now, we apply Lemma B.15 to finish the proof.In the remainder of this section, we prove Lemma B.16. We will use the notion of Hermite polynomials. Recall that for i = 0, 1, 2, • Hermite polynomials {H i } are the unique collection of polynomials over R that are orthogonal with respect to Gaussian distribution. In other words E x∈N (0,1) [H i (x)H j (x)] = 0 whenever i ̸ = j. In this work, we normalize the Hermite polynomials to further satisfy E x∈N (0,1) [H i (x)H i (x)] = 1. It is a standard fact from theory of orthogonal polynomials that H 0 (x) = 1, H 1 (x) = x and for i ≥ 2 Hermite polynomials satisfy the following recursive identity:H i+1 (x) • (i + 1)! = xH i (x) • √ i! -i • H i-1 (x) • (i -1)! Proposition B.18. Each coefficient of H i is bounded by 2 i in absolute value.Proof. This follows immediately from the recursion relation.Proposition B.19. All coefficients of multi-dimensional polynomial H i1 (x 1 )H i2 (x 2 ) • • • H i d (x d ) are bounded by 2 i1+i2+•••+i d . Proof. Each monomial of H i1 (x 1 )H i2 (x 2 ) • • • H i d (x d) can be expressed as j m j (x j ) where each m j (x j ) is a monomial of H ij (x j ). But we know that the coefficient of m j is bounded by 2 ij in absolute value. Thus, each coefficient ofH i1 (x 1 )H i2 (x 2 ) • • • H i d (x d ) is at most 2 i1+i2+•••+i d .Proposition B.20. Let p be a polynomial over R d of degree ℓ. Suppose that p satisfiesE x∈N (0,I) [(p(x)) 2 ] ≤ 1,then every monomial of p has a coefficient of at most (2d) ℓ in absolute value.Proof. For an element x ∈ R d we let (x 1 , • • • , x d ) be its coordinates. We expand p(x) as a sum of multidimensional Hermite polynomials8 :p(x) = i1,i2,•••i d ≥0 i1+i2+•••i d ≤ℓ α i1,i2,••• ,i d H i1 (x 1 )H i2 (x 2 ) • • • H i d (x d ) (B.2)Due to orthogonality of Hermite polynomials, we have:i1,i2,•••i d ≥0 i1+i2+•••i d ≤ℓ α 2 i1,i2,••• ,i d = E x∈N (0,I) [(p(x)) 2 ] ≤ 1In particular, this implies that each coefficient α i1,i2 [|p(x)| t ] 1 t ≤ (t -1) ℓ/2 E x∼N d [p 2 (x)] .The following is a standard corollary:Proposition B.22. If p : R d → R is a polynomial of degree ℓ, then E x∈N (0,I) [(p(x)) 2 ] ≤ e ℓ E x∈N (0,I) [|p(x)|]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 [O'D14]). Let λ > 0 be a parameter and let θ = 1 2 λ 1+λ . Using Generalized Holder's inequality and Gaussian Hypercontractivity, we haveE x∈N (0,I) [(p(x)) 2 ] ≤ E x∈N (0,I) [|p(x)|] θ E x∈N (0,I) [(p(x)) 2+λ ] 1-θ 2+λ ≤ ≤ E x∈N (0,I) [|p(x)|] θ (1 + λ) ℓ/2 E x∈N (0,I) [(p(x)) 2 ] 1-θOverall,E x∈N (0,I) [(p(x)) 2 ] θ ≤ (1 + λ) (1-θ)ℓ/2 E x∈N (0,I) [|p(x)|] θTaking power 1/θ of both sides and recalling that θ = 1 2 λ 1+λ we get:E x∈N (0,I) [(p(x)) 2 ] ≤ (1 + λ) (1-θ) θ ℓ/2 E x∈N (0,I) [|p(x)|] = (1 + λ) ( 1 λ -1 2 )ℓ E x∈N (0,I) [|p(x)|].Finally, taking λ → 0 proves the proposition.Finally, we are ready to prove Theorem B.16.Proof of Theorem B.16. Without loss of generality9 , we bound the coefficients of p up (x). We haveE x∈N (0,I) [|p up (x)|] ≤ E x∈N (0,I) [|f (x)|] + E x∈N (0,I) [|p up (x) -f (x)|] ≤ ≤ E x∈N (0,I) [|f (x)|] + E x∈N (0,I) [p up (x) -p down (x)] ≤ 2.Note that in the last inequality the value of E x∈N (0,I) [|f (x)|] is bounded by 1 because f is {±1}- valued,[(p up (x)) 2 ] ≤ 2 • e ℓ .Finally, together with Proposition B.20 implies that each coefficient of pup 2•e ℓ is bounded by (2d) ℓ in absolute value. This allows us to conclude that each coefficient of p up is bounded by 2 • (10d) ℓ in absolute value.We now focus on functions that have low-degree sandwiching polynomials approximators under the training distribution. Definition C.1 (L 1 -sandwiching polynomials). Consider X ⊆ R d and a distribution D over X . For ϵ > 0 and f : X → {±1}, we say that the polynomials p up , p down : X → R are ϵ-approximate L 1 -sandwiching polynomials for f under D if the following are true.1. p down (x) ≤ f (x) ≤ p up (x), for all x ∈ X . 2. E x∼D [p up (x) -p down (x)] ≤ ϵWe say that the ϵ-approximate L 1 -sandwiching degree of C under D is at most ℓ and with (coefficient) bound B if for any f ∈ C there are ϵ-approximate L 1 -sandwiching polynomials p up , p down for f such that deg(p up ), deg(p down ) ≤ ℓ and each of the coefficients of p up , p down are absolutely bounded by B.It turns out that given a function class C with low degree sandwiching approximators, we can test localized discrepancy of a hypothesis f with respect to a 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 f ∈ H. We denote this by N C .We now present our discrepancy tester for concept classes with bounded ϵ-approximate L 1 sandwiching degree. The primary advantage of this tester is it's global nature: given a hypothesis f , it certifies low localized discrepancy with respect to every function in the concept class. 2. (Chow-concentration) For any function f ∈ H, if X ∼ D ⊗m with m ≥ m conc , then with probability at least 9/10, we have that for all α ∈ N d with ∥α∥1 ≤ ℓ, E D [ f (x) • x α ] - E X [ f (x) • x α ] ≤ ϵ Bd 2ℓ .Then, there exists a (N C , ϵ)-tester T for localized discrepancy from D with respect to {D} that uses m conc + O( 1 ϵ 2 ) samples and runs in time poly m conc , d ℓ , 1 ϵ .Proof. For an input distribution D ′ and function f ∈ H, the tester runs Algorithm 1 with m conc samples X from D ′ and function f as input. We now prove it's correctness.Soundness We first consider the case where T acceptsD ′ . Let f * = arg max f ∈C P x∼D ′ f (x) ̸ = f (x) -P x∼D f (x) ̸ = f (x) . Since P x∼D ′ [ f (x) ̸ = f * (x)] = (1 -E D ′ [f * (x) • f (x)])/2, it is sufficient to prove a lower bound on the second term. From a Chernoff bound, we have thatE D ′ [f * (x) • f (x)] ≥ E X [f * (x) • f (x)] -ϵ with probability at least 3/4 when |X| ≥ C/ϵ 2 for some universal constant C ≥ 1. We now bound E X [f * (x) • f (x)]. Let p up , p down be ϵ-approximate L 1 -sandwiching polynomials for f * under D. We have that E X [f * (x) • f (x)] = E X [(f * (x) -p up (x)) • f (x)] + E X [p up (x) • f (x)] ≥ E X [p down (x) -p up (x)] + E X [p up (x) • f (x)] ≥ E D [p down (x) -p up (x)] + E D [p up (x) • f (x)] -3ϵ ≥ E D [f * (x) • f (x)] + E D [(p up (x) -f * (x)) • f (x)] -4ϵ ≥ E D [f * (x) • f (x)] -5ϵ .The first inequality follows from the fact that p down (x) ≤ f * (x) ≤ p up (x). To obtain the second inequality, we use the fact that the tester accepts if and only if| E X [x α ] -E D [x α ]| < ∆ and | E X [ f (x) • x α ] -E D [ f (x) • x α ]| < ∆ for ∆ = ϵBd 2ℓ and all α ∈ N such that ∥α∥ 1 ≤ ℓ. Since the coefficients of p up , p down are bounded by B and each have at most d 2ℓ monomials, we obtain the second inequality. The last two inequalities use the fact that E D [p up (x) -p down (x)] ≤ ϵ.E D ′ [f * (x) • f (x)] ≥ E D [f * (x) • f (x)] -6ϵ with probability at least 3/4. This implies that P x∼D ′ [f * (x) ̸ = f (x)] ≤ P x∼D [f * (x) ̸ = f (x)] + 3ϵ.From the definition of f * , we therefore have that disc f ,N C (D, D ′ ) ≤ 3ϵ with probability at 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 least4/5, | E X [x α ] -E D [x α ]| < ∆ and | E X [ f (x) • x α ] -E D [ f (x) • x α ]| < ∆ for ∆ = ϵBd 2ℓ and all α ∈ N such that ∥α∥ 1 ≤ ℓ. Thus, with probability at least 4/5, the tester will accept.Input: Set X from D ′ , function f : X → {±1}, parameters ϵ > 0, ℓ ∈ N, B > 0 Set ∆ = ϵ Bd 2ℓ For each α ∈ N d with ∥α∥ 1 ≤ ℓ, compute the quantity M α = E X [ f (x) • x α ]. Accept if | M α -E D [ f (x) • x α ]| < ∆ and | E X [x α ] -E D [x α ]| < ∆ for all α with ∥α∥ 1 ≤ ℓ. Reject otherwise.In this section we prove that any concept class with L 1 sandwiching polynomials can be TDS learned. This improves on the results of Klivans et al. 2023 which proved that L 2 sandwiching implies TDS learning. In particular, our result implies a new TDS learning algorithm for the class of all constant depth circuits(AC0) which was unknown in prior work. We also achieve tight dependence on the parameter λ as compared to prior work which was off by constant factors. We now state our general theorem about the connection between L 1 sandwiching and TDS learning. In contrast to prior work, we completely decouple the training and testing phase of the TDS learner.Theorem C.4 (L 1 -sandwiching implies TDS learning). Let D be a distribution over a set X ⊆ R d . Let C ⊆ {X → {±1}} be a concept class. Let ϵ, δ ∈ (0, 1). Let H = {±1} X . Assume that the following are true.1. (L 1 -sandwiching) The ϵ-approximate L 1 sandwiching degree of C under D is at most ℓ with bound B. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: We include a discussion on the broader impacts of our work at the end of the main paper.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not release any data and models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses 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 or models.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.The discrepancy is still localized, since it is defined with respect to a reference hypothesis f .∂ α p(x) α!In Appendices D and E, we use the notation p to denote natural numbers and use q for polynomials instead.Note that the expansion below is always possible for a degree ℓ polynomials because polynomials of the form Hi 1 (x1)Hi 2 (x2) • • • Hi d (x d ) are polynomials of degree at most ℓ that are linearly independent, because they are orthonormal with respect to the standard d-dimensional Gaussian.This is indeed without loss of generality, because the function -f is bounded from above by -p down and from below by -pup.We use the version of the Chernoff bound that uses an upper bound on the expectation rather than the exact value, through a standard coupling argument. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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. 

Reasoning 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. 

To 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.
strength_weakness: strength_weakness: 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. 
2) 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. 

Minor typos -- 1399 (threshol)
115 (chow)
questions: questions: --
limitations: limitations: NA
paper_summary: paper_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’.

This 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.

Some of the salient results from the paper are as follows.
1. 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.
2. 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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: See the weaknesses section and the question for the authors above.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: No significant limitations are stated.
paper_summary: paper_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.
strength_weakness: strength_weakness: See the questions below.
questions: questions: 1.Does Definition 1.1 of localized discrepancy match the one with 0-1 loss described in (Zhang et al., 2020)?

2.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.

3.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.”
This raises the question of why emphasis is placed on some mild structural properties over statistical distance, and what exactly these mild structural properties are.

4.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$?

[1] Zhang Y., Long M., Wang J., and Jordan M., On localized discrepancy for domain adaptation. arXiv. 2020.
limitations: limitations: N/A
paper_summary: paper_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
strength_weakness: strength_weakness: - Lack of Experimental Validation: The paper presents extensive theoretical work but lacks empirical validation, making it difficult to assess practical performance.
- 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.
- 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.
- Clarity in Algorithm Description: The algorithm descriptions could benefit from the inclusion of pseudocode or flowcharts to enhance understanding and reproducibility.
questions: 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?
- 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.
- 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: limitations: Yes, the authors use one section to discuss about the limitation, future work and broader impact of this paper.

Comments: comment: Thank you for response.
I thank the authors for their detailed and convincing response. Based on this, I have increased my score. I would encourage the authors to include a thorough discussion on practical applicability in the final version, clearly outlining areas where practitioners can learn from this line of results, as well as remaining major bottlenecks.
Thanks for the explanation.
Thank you for your thorough response. My concerns are addressed well and I have decided to increase the rating. Please revise the paper accordingly if it is get in.