Tester-Learners for Halfspaces: Universal Algorithms
Authors: Aravind Gollakota
Adam Klivans
Konstantinos Stavropoulos
Arsen Vasilyan
Venue: NeurIPS 2023 oral (2023)
Keywords: testable learning
pac learning
agnostic learning
Massart label noise
adversarial label noise
distribution testing

Abstract: We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time and has the following guarantee: the learner achieves error $O(\mathrm{opt}) + \epsilon$ on any labeled distribution that the tester accepts, and moreover, the tester accepts whenever the marginal is any distribution that satisfies a Poincare inequality. In contrast to prior work on testable learning, our tester is not tailored to any single target distribution but rather succeeds for an entire target class of distributions. The class of Poincare distributions includes all strongly log-concave distributions, and, assuming the Kannan--Lovasz--Simonovits (KLS) conjecture, includes all log-concave distributions. In the special case where the label noise is known to be Massart, our tester-learner achieves error $\mathrm{opt} + \epsilon$ while accepting all log-concave distributions unconditionally (without assuming KLS).
Our tests rely on checking hypercontractivity of the unknown distribution using a sum-of-squares (SOS) program, and crucially make use of the fact that Poincare distributions are certifiably hypercontractive in the SOS framework.

Tester-Learners for Halfspaces: Universal Algorithms
Aravind Gollakota
Adam R. Klivans UT Austin klivans@cs wtw.usteedeeee edu
Konstantinos Stavropoulos
Apple aravindgács. wtw..s.eeeas...eo
UT Austin
katavropecs utexas. edu
Arsen Vasilyan
MIT vasilyanomit.edi
Abstract
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polyno- mial time and has the following guarantee: the learner achieves error ( c any labeled distribution that the tester accepts, and moreover, the tester accepts whenever the marginal is any distribution that satisfies a Poincaré inequality. contrast prior work on testable learning, our tester is not tailored to any single target distribution but rather succeeds for an entire target class of distributions. The class of Poincaré distributions includes all strongly log-concave distributions, and, assuming the Lóvaazz-óóvszz Lóvasz-Simoooviitt (KLS) conjecture, includes all log-concave distributions. In the special case where the label noise is known to be Massart, our tester-learner achieves error opt + while accepting all log-concave distributions unconditionally (without assuming KLS). Our tests rely checking hypercontractivity of the unknown distribution using a aum-of-squares (SOS) pro- gram, and crucially make use of the fact that Poincaré distributions are certifiably hypercontractive in the SOS framework.
Introduction
In this paper study the recent model of testable learning, due Rubinfeld and Vasilyan [RV23]. Testable learning addresses a key issue with essentially all known algorithms for the basic problem of agnostic learning, in which a learner is required to produce hypothesis competitive with the best-fitting hypothesis in concept class C. The issue is that these algorithms make distributional assumptions (such Gaussianity or log-concavity) that in the absence of any prior information about the distribution or the optimal achievable error, it can be hard to check that the learner has even succeeded meeting its guarantee.
general hard verify. This means that
In the testable learning model, the learning algorithm, or tester-learner, is given access to labeled examples from unknown distribution and may either reject accept the unknown distribution. accepts, must successfully produce a near-optimal hypothesis. Moreover, to accept whenever the unknown distribution truly has certain target marginal D Work of [RV23, GKK23, GKSV23, DKK +23] provided tester-learners for a range of basic classes (including halfspaces, intersections of halfspaces, and more) with respect to particular target marginals D* (such as the standard Gaussian). All of these algorithms, however, have the shortcoming that they are closely tailored the particular target marginal D* that chosen. Indeed, their tests would reject many well-behaved distributions that are appreciably far from D*. A highly natural question from both theoretical and practical perspective is: can design tester-learners that accept a wide class of distributions simultaneously, without being tailored to any particular one?
also required
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this work we answer this question in the affirmative by introducing and studying universally testable learning. We formally define this model as follows.
Definition 1.1 (Universally Testable Learning). Let C be concept class mapping R to {+:1). Let D be family of distributions over R. Let e, > 0 be parameters, and let & [0. + [0. 1] be some function. We say C can be universally testably learned w.r.t. DD up to error (ppt) + 6 with failure probability 8 if there exists a tester-learner A meeting the following specification. For any distribution Dxy on Rdd x [+1]. takes in large sample S drawn from Dxy, and either rejects or accepts and produces a hypothesis h Rd + {=1} such that:
(a) (Soundness.) With probability at least - 5 over the sample S the following is true:
If A accepts, then the output h satisfies IP (P(x.))>Dxs) [h(x) + u] S (Topt(C,Dxx))) + E, where opt(C, Dxy) inf P (xx))~Dxy [h(x) * y).
(b) (Completeness.) Whenever the marginal of Dxy lies within D, A accepts with probability at least å over the sample S.
In this terminology, the original definition of testable learning reduces to the special case where D = =.').. We stress that while the prior work of [GKK23] allowed D to be, say, any fixed strongly log-concave distribution, their tester-learners are still tailored to the particular D that is selected. This is because their tests rely on checking that the unknown distribution closely matches moments with D By contrast, a universal tester-leamer must accept all marginals in family D.
Our main contribution in this paper is the first universal tester-learner for the class of halfspaces with respect to a broad family of structured continuous distributions. This family is the set of all distributions with bounded Poincaré constant (see Definition 2.4) and some mild concentration and anti-concentration properties (see Definition 2.1). It captures all strongly log-concave distributions, and in fact, under the well-known it captures all log-concave distributions as well. Our universal tester-learner significantly generalizes the main result of [2KSV23], who showed comparable guarantees only for the case where the target marginal is the standard Gaussian.
(KLS) conjecture (see Conjecture 2.6),
Theorem 1.2 (Universal Rester-Learner for Halfspaces; formally stated as Theorem 4.1). Let be the class of origin- centeee halfspaces over Bd Let 'D be the class of (1))-nice and O(i)-Poincaré distributions (see Desinitions 2.1 and 2.4), which includes all isotropic strongly log-concave and, under KLS, all isotropic log-concuve distributions. Then C can be universally lestably learned w.r.l. D up to error (opt)) + in poly(d, )) time and sample complexity.
A special and well-studied case of interest is when the label noise follows the Massart model, i.e. the label of every example is flipped by an adversary with probability at most 17. In this case we are able to handle a considerably larger class D while also providing stronger guarantee.
Theorem 1.3 (Universal Tester-Learner for Massart Halfspaces; formally stated as Theorem 4.1). Let C be the class of origin-centered halfspaces over Rd. Let D be the class of poly(d))nin and poly Poincaré distributions, which includes all isotropic log log-concave distributions (unconditionallly. Suppose the label noise follows the Massart model with noise rate at most 1 < 1/2 Then C can be universally testably learned w.r.t. D up to error opt + in poly(d, L. T-2-7 24 1_) time and sample complexity.
Technical Overview. We first describe the key reasons why prior tester-learners were tailored to a specific target D* All known polynomial-time algorithms for agnostically learning halfspaces up to error (opt) + require some concentration and anti-connenntattin properties from the input marginal distribution (encapsulated e.g. in Definition 2..). While concentration is relatively straightforward to check (e.g. by checking that the moments do not grow at too fast a rate), the key challenge in designing tester-learners for halfspaces to check anti-concentration. All prior tester-learners [RV23, GKK23, GKSV23, DKK +33 use the heavy machinery of moment-matching to achieve this. This approach relies on establishing structural properties of the following type: if D well- behaved distribution (e.g. strongly oog-concave distribution), and D approximately matches D" in its low-degree moments, then D is also well-behaved (in particular, anti-concentrated.. A canonical statement of such property is the main pseudorandomness result of [GKK23] (see Theorem 5.6 therein), which establishes that approximate noment-matching fools functions of a constant number of halfspaces. Applying this property inherently requires comparing the low-degree moments of

---

D with those of D Such tests do (implicitly) succeed universally for the class of all distributions that match low-degree moments with D (e.g.. if D is the uniform distribution over the hypercube, moment matching would accept all k-wise independent distributions). Definition 1.1, however, seeks a far broader kind of universality. Our tests are not tailored to a single target in any way, and are intended to succeed over practical classes of distributions that are commonly considered in learning theory (e.g., log-concave distributions).
We overcome this hurdle and design a conceptually simple way of checking anti-concentration without requiring the hammer of moment momeen-matching. Our approach follows and improves on the roadmap used by [GKSV23] to design efficient tester-learners for halfspaces using non-convex SGD (building on [DKTZ20a,, DKTZ20bl). Let us outline this approach at a high level (a more detailed technical overview may be found in [GKSV23, See 1.2). The tester-learner first computes a stationary point w of a certain smooth version of the ramp loss, a surrogate for the 0-1 loss. Let w" be any solution achieving 0-1 error opt. The tester-learner now checks distributional properties of the unknown marginal D that ensure that w close in angular distance to w (specifically, they ensure the contrapositive, namely that any w that has large gradient norm must have large angle with w*). By a more careful analysis of the gradient norm than in [GKSV23] (see Proposition 4.2), we are able to reduce to showing the following weak anti-concentration property. Let v denote any unit vector orthogonal to w. and let Dr denote D restricted to the band T = (x [ww, x)1 I o} (where the width is carefully selected according to certain constraints). Then the property we need is that
([v x) 2 0(1) 2 @(1)
D~Dr
Our key observation is that the classical Paley-Zygmun inequality applied to the random variable Z = (v.x)² where x ~ Dr, already gives us the following type anti-concentration:
Z 2
E E|Za]*
IP Z
This turns out suffice for our purposes provided we show hypercontractivity property for Z, namely that E[Z²]= S @11) 2 (as well as that [[ = @(1), which is just a second moment constraint).
Our main algorithmic idea is to use a sum-of-squares (SOS) program to check hypercontractivity of the random variable Z. To do so, we crucially leverage result due to [KS17] stating that any D that has bounded Poincaré constant is certifiably hypercontractive in the SOS framework (and it turns out this extends to Dr well). This means that program that checks hypercontractivity of Z over the sample, and whenever D is in fact Poincaré, we guaranteed that the test will pass with high probability (see Proposition 3.5). This is sufficient to ensure that the stationary point w we have computed is indeed close in angular distance to w
certain polynomial
semidefinite
In order to finally arrive at our main results, we need to run further tests which ensure that the disagreement between our computed w and any (unknown) optimum w is bounded by the angle between them, i.e., Px~DD (Piinssin((( (w, x) jf sign(("* , x))] S O(<(w, w")) (see Lemma 3.1). This in turn guarantees that w has error O(opt) + We stress that while [GKSV23] introduced similar testers for the special case of Gaussian marginals, our tests succeed universally with respect to broad family of distributions including some heavy-tailed distributions (see Definition 2.1). From a technical perspective, prior to our work, such tests either produced suboptimal bound, required estimating the operator norms of a polynomial number of random matrices formed using rejection sampling. We significantly simplify this approach by showing that it is sufficient to estimate the operator norm of a single random matrix. Finally, to obtain our improved results for the Massart setting, it turns out that the proof admits certain simplifications that guarantee final error opt + while also allowing a wider range of Poincaré distributions.
Related Work. There is a large body of work on agnostic learning algorithms for halfspaces that run in fully polynomial time. We briefly mention only those that are most closely relevant to our work; please see [BH21] for survey well [KKSV33, See 1.1] for further related work. Following
'One may wonder if it is possible test whether the low-degree moments of the input marginal D match any distribution a family D (e.g.. all strongly log-concave distributions) without directly comparing to a specific D This is a reduction to testing whether given (approximate) low-degree moment tensor lies within a large set of target lowree moment tensors, and would indeed suffice for universally testable learning. This general problem, however, seems highly challenging to solve directly.
3

---

Notation and Terminology. For what follows, consider Dxy be unknown joint distribution over X' x y from which we receive independent samples, and its marginal on X' will be denoted by Dx. In particular X' = Rd. and labels will lie y {=1}. We will use C to denote a concept class mapping Rd to {+1}, which throughout this paper will be the class of halfspaces or functions of halfspaces over IRd. We use opt(C. Dxy) to denote the optimal error inc IP (xx,))>Dxx [[(x) + w), or just opt when C and Dxy are clear from context. We recall that in Massart noise model, the labels satisfy P Py-DDyylx adversarial noise (i.e., when we are in the agnostic model), the labels can be completely arbitrary. In both cases, the goal is to produce hypothesis whose error is competitive with opt. We use E to denote the expectation of a random variable in brackets (or, correspondingly, P for the probability of the empirical distribution with respect to long line of work on cetrriuution-speciine agnostic learners for halfspaccs [KLS09, ABL17, Dan15, BZ17, YZ17, Zhal8, ZSA20. ZL21], the work of [DKTZ20a] introduced a particularly simple approach for the Massart setting, based solely on non-convex SGD. This work, which sets the template that our approach also follows, achieved the inoommttion-thoorttinn
optimal error of opt + for origin-centered Massart halfspaces over wide range of structured distributions (and was later extended to general halfspaces by [DKK* 22]). The non-convex SGD approach was then generalized by [DKTZ20b] to show an O(opt) + guarantee for the fully agnostic setting.
The testable learning model was introduced by the work of [RV23], who showed tester-learner for halfspaces achieving error opt + 6 in time d0(1/=)) for the case where the target marginal is Gaussian. Subsequently, [GKK23] provided general algorithmic framework based on moment-matching for this problem. and showed a tester-learner for halfspaces only requiring time d0(1/²) with respect to any fixed strongly log-concave marginal (matching known lower bounds for ordinary agnostic learning over Gaussian marginals [GGK20, DKZ20, DKP221, DKR23)).
The most closely relevant work to the present one is that of [GKSV23] (see also 231), who showed fully polynomial-time tester-learners for halfspaces achieving error ( + e in the agnostic setting and opt + in the Massart setting for the case where the target marginal is the Gaussian. As detailed the technical overview, their tests rely crucially on moment-matching and are tailored to a specific target marginal. By contrast, our tests check hypercontractivity using an SOS program and succeed universally for a wide class of certifiably hypercontractive distributions.
Certifying distributional properties such as bypercontractivity is an important aspect of large body of work on robust algorithmic statistics using the SOS framework. We will not attempt to summarize this literature here and direct the reader to [KS17, BK21] for overviews of related work, as well as to [FKP+19 19] for a textbook treatment. The notion of certifiable anti-concentration has also been studied (see e.g. [KKK 19, RY20, BK21J), but it turns out not to be directly useful for our purposes as it is only known to hold for distributions satisfying very strong conditions such as rotational symmetry.
Limitations and Further Work. Open directions in testable learning (and universally testable learning) include the design of (efficient) lester-larnees for concept classes other than the class of halfspaces, e.g., functions of halfspaces or neurons with other activations (like ReLU or sigmoid).
2 Preliminaries
# sign( (w", x)) x] n)(x), with r7(x) 1 < for all x. When we have
an event), either over the unknown joint distribution a sample S (e.g.. Ezes [Z]] si Σzes fZ)).
!
Definitions and Distributional Assumptions. For the problem of learning halfspaces in the agnostic and in Massart noise models, any of the known polynomial algorithms that achieve computationally optimal guarantees require that the marginal distribution has at least the following nice properties previously defined by, e.g., [DKTZ20b].
Definition 2.1 (Nice Distributions). For given constant À Z 1, we consider the class of X-nice distributions over Rd to be the distributions that satisfy the following properties:
1. For any unit vector in Fd the distribution satisfies x) E 13 (b.unndd spectrum)
2. For any two dimensional subspace V, the corresponding marginal density qv (x) satisfies qv (x( 2 1/A for any ||x||2 < 1/2.
(anti-anti-conceettaiio))

---

3. For any two dimensional subspace V. the corresponding marginal density qv (x) satisfies (v(x) S Q 112) for some function Q : R+ + R_ such that sup,20 Q(r) S À and also
1,=0 Q(())(()) dr S X, for any k = 1,3,5. 5.
(anti-concentration and concentration)
In the testable learning framework, however, corresponding results provide testable guarantees with respect to target marginals that are isotropic strongly log-concave [GKSV23], which is strictly stronger condition than the one of Definition 2.1 (see Proposition 2.3 below). We now provide the standard definition of (strongly) log-concave distributions.
Definition 2.2 ((Strongly) Log- Log-Concave Distributions [SW 14]. We say that a distribution over R (3-strongly) log-concave, if its density can be written as e e-,, where yp is a (8-strongly) convex function on IR (for some 3 > 0).
Proposition 2.3 (Log-Concave Distributions are Nice [LV07]). There exists universal constant À 2 such that any isotropic log-concave distribution is X-nice.
In this work, we provide universally testable guarantees with respect to the class of nice distributions with bounded Poincaré constant (see Definition 2.4 below).
Definition 2.4 (Poincaré Distributions). For a given value y > O, we say that a distribution over IR 7-Poincaré, if Var(f S T fx) for any differentiable function f: R + IR
Although it not clear whether one can efficiently obtain testable guarantees for the problem of learning noisy halfspaces under nice marginals (which is known to be an efficiently solvable problem in the non non-testable setting [DKTZ20a, DKTZ20b]), by restricting our attention to nice distributions that, additionally, have bounded Poincaré constant, we obtain efficient learning results, even in the universally testable setting. Our results are strictly stronger than the ones in [GKSV23], since we capture isotropic strongly log-concave distributions universally, due to Proposition 2.3 and the fact that strongly log-coneave distributions are also Poincaré, as per Proposition 2.5 below.
Proposition 2.5 (Strongly
Distributions are Poincaré, [SW14 14, Proposition 10.1]). Any -strongly log-concave distribution y PoPonncaré.
Furthermore, under long-standing conjecture about the geometry of convex bodies [KLS95], our results capture the family of all isotropic log- concave distributions.
Conjecture 2.6 -Kannan-Lovász -Stnonviiimoosiiss Conjecture [KLS95] reformulation from [LV18]). There a universal constant y > O for which any isotropic log-concave distribution is "y-Poincaré
3 Universal Testers
In this section, we present two basic testers that constitute the basic building blocks of the universal tester-learners we provide in the next section. The testers in this section might be of independent interest and their appeal is that they succeed even when the distribution in their input is unspecified up to certain bounds on number of its statistics. In fact, the family of distributions for which each such tester succeeds is of infinite size, even non-parametric.
3.1 Universal Tester for Bounding Local Halfspace Disagreement
First, we present a universal tester that checks, given a parameter vector w. whether a set of samples such that bounding the angular distance of w from an optimum parameter vector, implies that the corresponding halfspace disagrees with the (unknown) optimum halfspace only on bounded fraction of points in S. This property ensures that if w is close to the optimum parameter vector, then it is also approximate empirical risk minimizer. The tester universally accepts samples from nice distributions with high probability (Definition 2.1).
Lemma 3.1 (Universally Testable Bound for Local Halfspace Disagreement). Let Dxy be distri- bution over Rdd [=1), w E 1d-1, 0 (0, π /4,, À Z and 8 E (0, Then, for a sufficiently large constant C, there is tester that given 5, 0, w and a set S of samples from Dx with size at least 8r 2) and satisfies the following specifications:
C. (5 runs in time poly (d, 1
(a) the tester accepts S, then for every unit vector w' E R satisfying L(w, w') S 0 we have IP [sign(( (w', x)) # sign((w, SC 0. x
x~.
5

---

(b) the distribution Dx is X-nice, the tester accepts S with probability 1 - 8.
The proof of Lemma 3.1 simplifies and improves the proof of similar but weaker result in [GKSV23] (see their Proposition 4.5). The initial tester exploited the observation that the probability of disagree- ment between two halfspaces can be upper bounded by sum of products, where each product has two terms: one corresponding to the probability of falling in a (known) strip orthogonal to w and one corresponding the probability of having large enough inner product with some unknown vector orthogonal to w, conditioned in the (known) strip. The first term can be controlled by estimating the probability of falling in a (known) strip, while the second follows by Chebyshev's inequality, after estimating the largest eigenvalue of the covariance matrix conditioned in the known strip. This approach introduces number of complications, including the fact that conditioning requires rejection sampling, which, in turn requires a lower bound on the probability of falling inside each strip. We propose simpler tester that controls all of the terms of the sum simultaneously by estimating the largest eigenvalue of a single covariance matrix (without conditioning). Upper and lower bounds on the eigenvalues of random symmetric matrices can be universally tested with testers that are guaranteed to accept when the elements of the matrix have bounded second moments (spectral tester of Proposition A.2). We present our full proof in Appendix B.1.
3.2 Universally Testable Weak Inti-Concentration
We now provide an important universal tester, which ensures that for a given vector w, a sample set S and any unknown unit vector v orthogonal to w, among the samples falling within a (known) strip orthogonal to w, at least a constant fraction is absolutely correlated with v by a constant. In other words, the tester ensures that the conditional empirical distribution is weakly amti-concentrated in every direction. The tester universally accepts nice distributions that have bounded Poincaré constant.
Lemma 3.2 (Universally Testable Weak Anti-Concentration). Let D be distribution over Rd Then, there is a universal constant C >> and tester that given a unit vector w
E R 8 E (0, 1), 7 > O, o28 ( runs in time
221 1, S 1 and a set S of i..dd samples from D with size at least C. d' poly(d, X, 1og()))) and satisfies the following specifications
2X
(a) the tester accepts S. then any unit vector V E Rd with (v. w) we have
Kv x)
xES
CXC
C2Caa
(b) If D'D is "-Poincaré and X-nice, then the tester accepts S with probability at least 1 - 8.
The proof of Lemma 3.2 is based on a simple fact from probability that is true for any non-negative random variable and ensures that the mass assigned to the tails lower bounded by the ratio of the square of its expectation to the second moment. Proposition 3.3
Inequality). For any non-negative random variable Z. we have
1 E|Z|2
PIZ > B|Z1/21
4
E|
In the special case where Z follows the distribution of x)² conditioned on ((w,)) S. for some unitary orthogonal vectors v, w, some o > O and some random variable x whose distribution is, say, 1-nice (see Definition 2.1). one can show that E [Z] is lower bounded by a constant and E 2 upper bounded by another constant, so Z assigns a non-trivial mass to a set that is bounded away from zero. This property is useful in the context of learning noisy halfspaces, as we show in the following section (see Proposition 4.2 and Lemma 4.3). However, testing algorithms that check whether such a property holds for given w and a, are guaranteed to succeed when the marginal distribution has, additionally, bounded Poincaré constant. The main part of the proof that requires a bounded Poincaré constant, is testing whether [ is bounded uniformly over the set of unit vectors v orthogonal to w, since Z = (v,x)*, where v is unknown. We use the following result from [KS17].
Proposition 3.4 (Certifiable Hypercontractivity of Poincaré Distributions, Theorem 4.1 in [KS17]) Let ê E (0. 1), 7 > 0 and let D be a ry-PPincaaa distribution over Rdd Let S be set of independent samples from D with size at least (2dlog( 44/ 8))a Consider the constrained maximization problem
arg max E [(v,x))))
(3.1)
||

---

Then, the optinum solution of the degree-4 sum-of-squares relaxation the the problem (3.1) has value at most C*²* for some universal constant C. with probability least over the sample S.
Using Proposition 3.4, we are able to provide a universal tester for bounding the empirical fourth moments. The tester solves an appropriate SDP relaxation of the (hard) problem [HL13] of finding the direction with maximum fourth moment and is guaranteed to succeed if x has Poincaré parameter bounded by a known value.
Proposition 3.5 (Hypercontractivity Tester). Let D a distribution over Red Then, there is a tester that given å E (0, 1), > 0 and set S i..d samples from D) with size at least (2d Hollog(A))) ()) runs in time poly(d, log J.
8. log " and satisfies the following specifications
(a) the tester accepts S, then any unit vector R we have
E XES
[vv C. where C' is some universal constant.
(b) If the distribution D is P--Poincaré, then the tester accepts S with probability at least 1 8.
Proof. The tester does the following:
1. Solves a degree-4 ofm-of-squares relaxation of problem (3.1) up accuracy y (For a formal definition of the relaxed problem, see Problem (2.3) in [KS17].)
2. If the solution has value larger than (C - 1)n1, then reject. Otherwise accept.
The computational complexity of the tester is poly(IS), d, log 4), since the problem it solves can be written semidefinite program [Sho87, Par00, Nes00, Las01].
the tester accepts S, then we know that the optimal solution of the relaxed problem is at most Ch+ and we also know that any solution of the initial problem (3.1) has value at most equal to the value of the relaxation. Therefore E[(v, x} I Cy²,, for any V E Sd-1
On the other hand, if the true distribution D is --Ponncaré, then, with probability at least 1 5, we have that the solution found in step 3.2 has, with probability at least 1 8, value at most C' for some universal constant C", due to Proposition 3.4. In order to ensure that the tester will accept with probability at least 1 - 8, it suffices to pick C. C" +1.
We provide the full proof of Lemma 3.2, in Appendix B.2. The tests we perform include spectral tester that accepts with high probability when the distribution of x is nice (similar to the spectral tester used for Lemma 3.1), a tester of the probability that ((w, x)| S and the hypercontractivity tester of Proposition 3.5.
4 Universal Tester-Learners for Halfspaces
In this section, we present our main result on universally testable learning of halfspaces.
Theorem 4.1 (Efficient Universal Tester-Leamerr for Halfspaces). Let Dxy be any distribution over Rd x [1. Let C be the class of origin centered halfspaces in RR. Then, for any X 2 1, 7 > 0, c >> 0 and 8 (0, 1), there exists an universal tester-learner for w.r.t. the class of X-nice and PPioncar where opt miin PD [v # sign( (w, x))], and error probubility at most ö, using number of samples and running time poly X, 7, 7: log 4
marginals up to error poly(A) (X) (1+ (+tff))-ppp - +
Moreover, if the noise is Massart with given rate 1) < 1/2, then the algorithm achieves error opt + with time and sample complexity poly X, 7, 2: 1-27 log }))
Our proof follows surrogate loss minimization approach that has been used for classical learning of noisy halfspaces [DKTZ20a, DKTZ20b) as well as classical uni-ersivessal) testable learning [GKSV23]. In particular, the algorithm runs Projected Stochastic Gradient Descent (see A.5) on surrogate loss whose stationary points are shown to be close to optimum parameter vectors under certain distributional assumptions. In the regular testable learning setting, given a stationary point, the above property can be tested with respect to any (fixed and known) target strongly log-concave marginal as shown by [GKSV23]. For such stationary point, more tests used in order to ensure
7

---

bounds on local halfspace disagreement. We provide some delicate refinements of the proofs in [GKSV23] that enable us to substitute their testers with the universal testers of Section 3.
We use the following surrogate loss function which was also used in [GKSV23].
{<(
(w.x) x)
(w;
E
lo
(4.1)
(x,y)~Dxy
In Equation (4.1), the function & is a smoothed version of the step function as in Proposition A.4,
In order to analyze the properties of the stationary points of the surrogate loss, we provide the following refinement of results implicit in [GKSV23, DKTZ20a, DKTZ20b]. We show that the gradient of the surrogate loss is lower bounded by the difference between certain quantities that are controlled by the marginal distribution (see Figure 1). We stress that we do not use any assumptions for the marginal distribution in this step. Prior work included similar bounds, but the corresponding quantities were different. We need to be more precise and provide the following result, whose proof is based on two dimensional geometry and can be found in Appendix C.I.
Proposition 4.2 (Modification from [GKSV23, DKTZ20a, DKTZ20bl). For distribution Dxy over F x } let opt be the minimum error achieved by some origin-centered halfspace and w E sd-1 a corresponding vector. Consider Cg as in Equation (4.1) for >> 0 and let < 1/2. Let w E g I and E span(w, w, w*) such that (v, w) and (v, w-) ) 0. Then, for some universal constant C > O and any a Z where
with <(w, w*)
2 tan 0 we have || w Lo (w; Dxv)ll2 2 A A A3.
A o
a
P
[(v,x)]
2 a and 1(w, x) S 6
C
2 and A3 σ Vopt V (v, x)2. ( [[(l
C
A2 tan
-P
Moreover, if the noise is Massari with rate 1,, then Ww Dxy))l2 2 (1 (1-21) 21) A2-
If the marginal distribution is nice, then the quantities A1 A2 and Ag such that be chosen accordingly so that stationary points of the surrogate loss (or their inverses) are close to some optimum vector (see Proposition A.3 for properties of nice distributions). We use some simple tests (e.g., estimate the probability of falling in a strip, (l] x) I a/2] and appropriate spectral testers) as well as universal tester for weak anti-concentration (see 3.2) establish bounds on quantities 11 A2 and A3 which ensure that the desired property holds for a given vector w, under no distributional assumptions. The tester in the following result universally accepts nice distributions with bounded Poincaré parameter. The formal proof can be found in Appendix C.2.
Lemma 4.3 (Universally Testable Structure of Surrogate Loss). Let Dxy be any distribution over Rd x [+1]. Consider La as in Equation (4.1). Then there is a universal constant C >> O and a tester that given a unit vector w E gd, E (0, 1), 1) < 1/2, 7 > 0, Z 1, o S I and a set S of i.i.d. samples from Dxy with size at least C
exe dt oe8 log(d) runs in time polyíd, X, 1 J log( )
and satisfies the following specifications
(a) If the tester accepts S. then, the following statements are true for the minimum error opts achieved by some origin-centered halfspace on S and the optimum vector w's E 3d-1
If the noise Massart with associated rate 1) and W/ S)ll2 S either L(w, w's) S CX²(1+7))
1-2n, then eX
d(-w, S C1
1-2n
I-2n J..
If the noise is adversarial with opts CXC and V Co S)Il < exaz then either Z(w, w's) S C a or <(-w, w's) < (1
(b) the marginal Dx is X-nice and 7- Poinncar then the tester accepts with probability at least 1 1-8. 8.
We now give the algorithm for 8 <- 1/3 since we can reduce the probability of failure with repetition (repeat Olog })) times, accept if the rate of acceptance is 2(1) and output the halfspace achieving the minimum test error among the halfspaces returned).
The algorithm receives À 2 1, > 0, e > and 1) E 1/2) (1) (say n = 1 when we are in the agnostic case) and does the following for some appropriately large universal constants C1, C22 > 0.
8

---

1. First, initialize E = C,AST and let E be a list of real numbers and A be positive real number, where and A are defined as follows. 7 = 1, then is an C1A-T cover the interval [0, cite,] and A = Cix91as- Otherwise, let E = (1+7)) 1-2n C1A
E-(1-2n) and
2. Draw a set S1 of C2 Ad C2
i..d. samples from Dxy and run PSGD, as specified in Proposition A.5 with + A, 8 t on the loss La for each or E Σ.
3. Form list L with all the pairs of the form (w, o) where sd-1 is some iterate of the PSGD subroutine performed on Lg.
4. Draw fresh set S2 of C2 (dd) Cs i.d. samples from Dxy and compute for each (w, o) E
L the value || W S2) 122. If, for some E, V (w; S2)ll2 > for (w.o)
L, then reject.
5. Update by keeping for each E E only one pair of the form (w,o) for which we have (w; I A.
6. Run the following tests for each (w, a) E L. (This will ensure that part (a) of Lemma 4.3 holds for each of the elements of L,, i.e., that any stationary point of the loss La that lies in L is angularly close to the empirical risk minimizer".) .).
If (x (lw, x)1 < S cx or (xx.w)ss,lkw. x)1 S 1 C1Aa, then reject.
Compute the (d 1) (d matrices M and M5, as follows:
M 52
E (x.
(proj x) x)" (1(wx)))sg)
M
E (x,9)E8
(proj (proj x)T 1 [((lwx))(H)
Reject if the maximum singular value of M is greater than C11ss
Reject if the minimum singular value of M2, is less than C,
Run the hypercontractivity tester on S' = [proj w x (x, v) E S2 and ((w, x) & a). i.., solve an appropriate SDP (see Prop. 3.5 with 7 7, t 8/C,) and reject if the solution is larger than a specified threshold.
7. Set (1+>")e and run the following tests for each pair of the form (w.r) and (-w, a) A-da Ay1 where (w,a) L. (This will ensure that part (a) of Lemma 3.1 activated, i.e., that the distance of a vector from the empirical risk minimizer is an accurate proxy for the error of the corresponding halfspace.)
If Es ([,, x) S > C1 C1 @ then reject.
Compute the 1) (d 1) matrix Ms, follows:*
(proj i () x)" (i (1-1)² 1)3
Ms. (x
1[[(w, x)| E [(i- 110, 10)}
If l| > C,O.C, then reject.
8. Otherwise, accept and output the vector w that achieves the smallest empirical error on S₂ among the vectors the list L.
This concludes the algorithm. The full proof of Theorem 4.1 may be found in Appendix C.3.
2rr the same holds for the inverse vector.
"The operator proj w Rd - R projects vectors on the hyperplane orthogonal to w.
"Note that only at most [S2] many terms below non-zero, hence Ms, be computed efficiently.

---

Acknowledgments and Disclosure of Funding
We wish to thank the anonymous reviewers of NeurIPS 2023 for their constructive feedback. Aravind Gollakota was at UT Austin while this work was done, supported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Adam R. Klivans was supported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Konstantinos Stavropoulos was supported by NSF award AF- 1909204, the NSF AI Institute for Foundations of Machine Learning (IFML.) and by scholarships from Bodossaki Foundation and Leventis Foundation. Arsen Vasilyan was supported in part by NSF awards CCF-2006664, DMS- 2022448, CCF-1565235, CCF-1955217, CCF-23 10818, Big George Fellowship and Cintech@CCSAl Part of this work was done while Arsen Vasilyan was visiting UT Austin.
References
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
[BH21] Maria-Florina Balcan and Nika Haghtalab. Noise in classification. Beyond the Worst- Case Analysis of Algorithms, page 361, 2021.
[BK21] Ainesh Bakshi and Pravesh K Kothari. List-decodable subspace recovery: Dimen- sion independent error in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1279-1297. SIAM, 2021.
[BZ17] Maria-Florina F Balcan and Hongyang Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. Advances Neural Information Processing Systems, 30, 2017.1
[Dan15] Amit Daniely. A ptas for agnostically learning halfspaces. In Conference on Learning Theory, pages 484-502. PMLR, 2015.
[DKK 22] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 874-885, 2022.
[DKK*23] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Efficient testable learning of halfspaces with adversarial label noise. arXiv preprint arXiv:2303.00545, 2023. 1,
[DKP721] Ilias Diakonikolas, Daniel M Kane, Thanasis Pittas, and Nikos Zarifis. The optimality of polynomial regression for agnostic learning under gaussian marginals in the sq model. In Conference on Learning Theory, pages 1552- 1584. PMLR, 2021. 1
[DKR23] Ilias Diakonikolas, Daniel M Kane, and Lisheng Ren. Near-optimal cryptographic hard- ness of agnostically learning halfspaces and relu regression under gaussian marginals. arXiv preprint arXiv:2302.06512. 2023. 1
[DKTZ20a] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference Learning Theory, pages 1486-1513. PMLR, 2020. 1, 2, 4, 4, 4.2, A.5,
[DKTZ20b] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Non-convex sgd learns halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 1188050088949 2020. 1, 2, 2, 4, 4, 4.2,
[DKZ20] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems,
2020. 1
10

---

[FKP* 19] Noah Fleming, Pravesh Kothari, Toniann Pitassi, et al. Semialgebraic proofs and efficient algorithm design. Foundations and Trends@ in Theoretical Computer Science, (4(1-)):1-221,200
[GGK20] Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147- 2158, 2020. 1
[GKK23] Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari. A moment- approach to testable learning and new characterization of rademacher complexity, Proceedings of the fifty-fifth annual ACM Symposium Theory of Computing, 2023. To appear. 1, 1,
[GKSV23] Aravind Gollakota, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. An efficient lester-learee for halfspaces. arXiv preprint wrXiv2232..14855 2023. 1, 2, 3.1, 4, 4, 4.2, A.4, A.5, C.I
[HL13] Christopher J Hillar and Lek-Heng Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-39, 2013. 3.2
[KKK19] Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regres- sion. Advances in neural information processing systems, 32, 2019.
[KLS95] Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and localization lemma. Discrete & Computational Geometry, 13:541- 559, 1995. 2, 2.6
[KLS09] Adam R Klivans, Philip M Long, and Rocco A Servedio. Learning halfspaces with malicious noise. Journal of Machine Learning Research, 10(12), 2009.
[KS17] Pravesh K Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor norms. arXiv preprini arXiv: 1711:: 2017. 1, 3.2, 3.4, 3.2
[Las01] Jean Lasserre. New positive semidefinite relaxations for nonconvex quadratic pro- grams. Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873-1950), pages 319-331, 2001. 3.2
[LV07] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithmss, 30(3):307-355 2007. 2.3
[LV18] Yin Tat Lee and Santosh S Vempala. The Kannan-Lovász-Smmonn preprint arXiv: 00.40006..65,... 2018. 2.6
conjecture. arXiv
[Nes00] Yurii Nesterov. Squared functional systems and optimization problems. High perfor-
mance optimization, pages 405-440, 2000. 3.2
[Par00] Pablo A Parrilo. Stractured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000. 3.2
[RV23] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning al- gorithms. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Computing. 2023. To appear. 1,
[RY20] Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares, In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 161-180. SIAM, 2020.
[Sho87] N.7.. Shor. Quadratic optimization problems. Izv. Akad. Nauk SSSR Tekhn. Kibernet., 1987(1):128-13,, 222, 1987. 3.2
[SW14] Adrien Saumard and Jon A Wellner. Log-concavity and strong log-concavity: a review. Statistics surveys, 8:45, 2014. 2.2, 2.5

---

[YZ17] Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.
[Zha18] Chicheng Zhang. Efficient active learning of sparse halfspaces. In Conference Learning Theory, pages (856-1880) PMLR, 2018.
[ZL21] Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Conference Learning Theory, pages 4526-4527. PMLR, 2021.
[ZSA20] Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances in Neural Information Processing Systems, 33:7184 14-7197,7 2020.
12

---

A Technical Lemmas
In this section, we provide a list of technical results that we use in our proofs.
Lemma A.1 (Preservation of Poincaré constant). Let be an open interval and g IRd + R.- the density of "y- P--Poincaré distribution. Let v E S and dy B - R.+ be the density of the distribution resulting from conditioning to x v and projecting on the subspace perpendicular v. Then, the distribution corresponding to dy is "yPoincarré
Proof. Assume, without loss of generality, that v = eg. We have that
(xca) = Sayer ((x=2, Ra) daa
for any Xxd E IRd-1
Sxca Saaes ((x) dx
Let f 12-1 - R any differentiable function. In order to show that gv is 7-Poincaré, it is sufficient to show that under no further assumptions on f, the quantity Varg, (f(xe))) is upper bounded by the product of and Egg (xxx)( follows
We expand the quantity Varge (f(xe)) as
Varg (f(xxa)) inf I (f(xed) - -7) (x)(((x))))) dx
xea
I (f(xcd)-1 - -T) Iayer ((Xxd, IT) dx
=inf inf
IkcaJase g(xx do dx
xxed
inf, Sxece Saeedseer (f(xo) - -T)² ((x) dx dxeed
Sxca Seaer ((x) dx
7 Sxea Saner (xf(x<c)) 1/2 q(x) dx
(since g ?-Poincaré)
Ixea SeaeS ((x) dx
=7. I V (xxx) dxed
af = 0) (since
=7 4
which concludes the proof.
Proposition A.2 (Spectral Tester). Let D be distribution over RR., Then, there is tester that given
E (0, 1), A 2 1, > O and a set S of i.i.d. samples from with size at least 026 runs in time poly(d, 8. (S]) and satisfies the following specifications
22d
I
(a) If the tester accepts, then, for S, Es[zz') 2 L (resp. Es(zz" - 201a).
[zz²] (b) If. for D, En((Z,2;) < X and Ep|zz") > 0Ia (resp. Ep En|zz" 0Ia), then the tester accepts with probability at least
Proof. The tester receives X, set S and å (0, and does the following:
1. Compute the matrix Mg Es [zz")
2. If the minimum (resp. maximum) eigenvalue of Mg is larger than (resp. smaller than 20), then accept. Otherwise reject.
Clearly, if the tester accepts, then the desired property is satisfied by construction. If the distribution D satisfies the conditions of part (b), show that for MD EEzzD (zz have
Ms MD ll S 2'
with probability least
8
13

---

which implies that Ms = Ia (and Ms N (0 (Ms), = Es|z,z,], and by Chebyshev's inequality have
+
② Ld = 201a). In particular, we have that
P (Mss)ss - (MD)ul
>
0
4d
E 2~D
(2,22))
4dd
2d
S1
8 S
By a union bound, we get that ||Ms MD MDllmax S 2d
with probability least ô and hence 2. which concludes the proof.
[|Ms MDllop 1 Ms Mp max
Proposition A.3. Lef c 2 0, À 2 1, S and D be a X-nice distribution over Rd. Then, for any
2X unit vectors W, v, v', u, u R with (w,v) (w, v') = 0 and for some universal constant C we have
(1) (([ x) oj 20 a o some 1txx CA2.
(i) (V, x)² 1 (w. x/))) - o 20 - a., for some E Ic CA).
(iii) [x u | for some a S CA.
(iv) [V [[ [>| E (c, + +o)) S 2a a., for some a S C..
Proof. We start by deriving property (i). Recall the function from the definition of X-nice distri- bution, which upper-bounds the density of any two-dimensional projection of a X-nice distribution see that:
PlKw,, S so
Ispan(v w) (21, da dr2
=
$
00
Q
@(Vatt
2 +
dr dxz
=
Now, note that the region {(<1,, x2) |ai| < o is a subset of the set
{<11, : [22|| S < U (x11 x2) |=1l s o & |22 s 1}.
Therefore:
Q (VV xb² de dr12 S
darcsin(o). f 2nr (r) dr + S Q (Ve7+ +
23 x33) drıdoz S O(oA)
Note that in the last line above, we bounded the first via the bound f (r) dr < À from the definition of X-nice distributions. Likewise, we bounded the second term via the inequality Q(r) A from the definition of X-nice distributions. Overall, we get
Bl(v. x)² 1[Kw, x) S [o)l S((o)
Now, we shall lower- bound the same quantity. We have
P[l(w, x S 5
(w) x22) da dx2
Ispan(v, (1 x22) dx 1x2
$1=-0 22
Now, since S 2X via the premise of the lemma, we see that the whole region of integration on the right side of the set { x2) / 2 + zz < } From the definition of X-nice distributions, the density vw) lower-bounded by 1/A in this region. Therefore, we have
20
2a
P|[(w, S <o
X
14

---

which finishes the proof of property (i).
Now, derive property (ii). Recall the function Q from the definition of a X-nice distribution, which upper-bounds the density of any two-dimensional projection of a X-nice distribution we see that:
B((vx))² ( [[( x| S |
22 Ispao(v (onpoovwww)/o (111 da daz
=-=-0 0
12 Q (V29 22 drydr2
#1=-0 22=-00
Now, note that the region ((x1, 322 |mn|| S o is subset of the
{(11. x2) : 222 S < U ((11.2)) las S o & |22 1 11..
Therefore:
2 22 S
1 (eavi +3²
dæidæz I
4arcsin(a): 2 dr l S
2 Q
(Voi+ 2B
dr dr,drz S ((
Note that in the last line above, we bounded the first term via the bound on ن Q²(()) dr from the definition of X-nice distributions. Likewise, we bounded the second term via the inequality Q(r) s from the definition of X-nice distributions. Therefore, we get
x) 1[( x) S s s O(AA)
Now, we shall lower-bound the same quantity. We have
El(v, fl(w, x) S [0}]=
x2 Ospan w) (21, day dx
=1=-0 =2=-00 00
x2 Ispan( (w (11, dx dx²
21 22=
Now, since via the premise of the lemma, right side of the set {(11, x2) / 2 + 23 S }- From the definition of A-nice distributions, the density (spa(vv,w) is lower-bounded by 1/A in this region. Therefore, we have
that the whole region of integration on the
2x
(V x)2 (l(w, x) < sall 2
A
4x2
X
2X
which finishes the proof of property (ii).
We proceed to property (iii). We will denote the angle between v and v' as 3, which allows us to write
El v) (x,
o (z) cos B + x2 sin 8)2 Vs (2), x22) dæ dxs
F2=-00
o (1) cos B + x2 sin 3/2 Q @VV + 23 doidez
21 31=-0 00
00 00
(x + +z²)2 Q (VVP+ +13 dz
21=-00 00 12=-00
2nr
2mr Q(r) dr S 2
r=0
which finishes the proof of property (iii).
15

---

Finally, we prove property (iv). For 3 2 0 we have
dr [ , [Q(
2Q( +2)) dr+ + / PQQ(12 + 3) dr
r=
+Y
QQ(v (1122 r2 +2+ +33 dr
(since supro0 Q(r) X)
(r - -rr))((r)) dr'
(by setting r' v +
N=VI++
Qr) dr
(since BrQ(r) for any 2 0)
21
Applying the above inequality to the quantity of property (iv), get the desired result.
B x)² -il(w, x)1
[c o|Hl
2 (span(v.w) 10
10=-00
12 Q x9 + +x²) da doz
la |el.ctooo 12=-00
[ Mellelocto)
2 2
7². Q(V o9 + 12) dr dx
rr=0
(41) dr S a
|aL|E|aota]
This concludes the proof of Proposition A.3.
Proposition A.4 (Proposition 4.2 of [GKSV23J). There is a universal constant C > O, such that for any O, there exists a continuously differentiable function Ey - [0. 1] with the following properties.
1. For any e ( (o) -
2. For any 1> 0/2, = annd any < -0/2, (t) = -.
3. For any t E R, (t) C/o)), (t) ( and (t) S C/O²
Proposition A.S (PSGD Convergence [DKTZ20a), restated in [GKSV23]) Let Co be as in Equation and Dxy such that the marginal D and E (0, 1), there is X log(1/8) which, having access to
(4.1) with (0, 1), l, as described Proposition A.4, on Rd is X-nice. Then for some universal constant C and for any an algorithm whose time and sample complexity is 0 Ad samples from Dxy, outputs list L of vectors w gd-1 with | 0 x log(11/8) so that there exists W with
g +
co
VV Dxy))l2 I e, with probability at least
5
In particular, the algorithm performs Stochastic Gradient Descent L. Projected on Sd-1 (PSGD).
B Proofs from Section
B.1 Proof of Lemma 3.1
We restate Lemma 3.1 here for convenience.
Lemma B.1 (Lemma 3.1). Let Dxy be distribution over pd [+1), E Sd-1, and E (0, 1). Then, for sufficiently large constant C, there is tester that given d, w and set of samples from Dx with size at least C. (055) runs in time poly (d. 8: 1) and satisfies the following specifications:
1, 0 (0, 7 /4]
16

---

(a) the tester accepts S. then for every unit vector w' E R" satisfying 2(w, w') S 0 we have
IP [sign(((' x)) + sign((w, x))] - C. 0 C. A
x--g"
(b) If the distribution Dx is X-nice, the tester accepts S with probability 1- 8.
Proof. The testing algorithm receives integer d, set S C R4, w E E 0 /0, À 2 1 and ò E (0, 1) and does the following for some sufficiently large universal constant C₁ 0:
1. If Pxes (l x) E [0, 0]] > Ciexs then reject.
2. Let proj.. 1w : RR + Rd denote the operator that given any vector in R it outputs its projection into the (d - ddimensional subspace of Rdd that is orthogonal to w.
3. Compute the (d - 1) x (d - 1) matrix Ms as follows::
(proj x) w x)T
Ms = E
1 [[(ww x\I E [[i - 1)8,
1]0, 10)}
XES
(i-
4. Run the spectral tester of Proposition A.2 on Ms given + 6, C i.e., compute ||Ms llop and if || > C,0x0, then reject. Otherwise, accept.
GACht and e
First, suppose the test accepts. For the following, consider the vector w' E Fd to be arbitrary unit vector and v E RRd to be the unit vector that is perpendicular to w, lies within the plane defined by w and w' and (v, w') O. Then have:
P [sign( (w', x)) A sign((w (e)((( x-8
xv,x))
(2 (1-1)
& 1(w, E [(t 1)0, i0]
x
tan 0
Implies
[(vixx) (6-1)/2
0c Ex [(v, x1 (ww ()-))((((()))_.1))
S IP (l,,, xES
x)) E [0, 01] +4
(i 1)2
50,000
(projiw v. proj w MI
S ch
For part (b), we suppose that the distribution Dx is indeed X-nice. We will show that with probability at least 1 - 6, the tester will accept, i.e., that
IP xES
[I(,, x) E [0,
0] s C1 and
(B.1)
|Ms llop S C,8AC=
(B.2)
We first observe that the corresponding quantities under distribution Dx due to Proposition A.3. In particular, we have that for some universal constant C' > 0
P
|| (w, x) E [0, 0] S C' and
(B.3)
xEDx
[(v', x)2 1 (w x) E [ 0 < C' for any v' E Sd-1 and c 2 0
(B.4)
x
If we let MD Dx EDx [Ms]. we get that
| llop = sup T Mp u=
(proj v' Max (projuw v')
sup
uE84-2
W w)
<
Σ
E w'E8--1EE XXDX
sup
lIV x/2 1[l x)| [c 0]]
(i 1)2
C'O < C OX
sup v
'Note that only at most
[S] many terms below non-zero, hence Ass be computed efficiently.
17

---

By Proposition A.2, in order to satisfy expression (B.2), it remains to show that PgnD((Zez) $ C1 for any Ł E [d], where z is defined as follows
proj X
Since Fg-D((Z,zz)) S (u, x) ( 2) for some unit vectors u, u' gd-1 (orthogonal to w), the desired bound follows from Proposition A.3.
(u,
It remains bound the absolute distance between the quantities of the left hand side of expressions (B.1) and (B.3). This can be achieved by an application of the Hoeffding bound, since the empirical version of the quantity is the average of independent Bernoulli random variables.
B.2 Proof of Lemma 3.2
We restate Lemma 3.2 here for convenience.
Lemma B.2 (Universally Testable Weak Anti-Concentration) Let D be a distribution over IR. Then, there is universal constant C and tester that given unit vector Rd 8 (0, 1). 7 >
x 1, S L and a set S i.i.d. samples from D with size at least C. G6 log(d)) runs in time 2X
poly(d, X, i_
a' 8. 1o)( and satisfies the following specifications
(a) If the tester accepts S, then for any unit vector Rdd with (v, w)
we have
Kv Kv,x)) x) 2 CXC
[(w, S 2 CXC
[(w,
1
XES
(b) If D PPPoincaré and X-nice, then the lester accepts S with probability at least 1 8.
Proof. The testing algorithm receives a set S C Rd, w E Sd-1, ,5 (), 0, and a S 2x and does the following for some sufficiently large C1 > 0:
1. If PxPesll (w. x $ a) 20 C1AC1, then reject.
2. Compute the (d 1) x (d - 1) matrix Ms as follows:
Ms = E [(proj x)(proj w x)" 1f x) s a]} xES
3. Run the spectral tester of Proposition A.2 on My given 8, X C12 i.e., reject if the minimum singular value of Mg is less than
and 0 + C
2a CI
4. Run the hypercontractivity tester (Prop. 3.5) on S' = (projiw x x E 5 and ((w, x) I ), i.e., solve appropriate SDP and reject if the solution is larger than specified threshold. Otherwise, accept.
For part (a), we apply the Paley-Zygman inequality to the random variable Z = (v. condtitioned on (, x)| S a and get
P xES
(v.x)²
1
E XES
(v,x)
kww x) S of [( [ww,)) x) S So
(Exes ((, x)² (w, 1 < o])²
2
4 Exxs (v, x) [
Note that since (v, w) = O, we have (v, (proj v, proj w x) (where ||v||2 || proj w v (|2)). Therefore, since has passed the spectral tester as well as the tester for the probability of lying within the strip [ (w, x) S a. we have that
EXES [(v, 1 (l(w, x) S [o
(v, x
(ww x3| $ so] o]=
2 20
xES
PxEs| (w. x)) < al
Moreover, {x E 5 | (w, x < of has passed the hypercontractivity tester, and therefore, according Proposition 3.5 we have
(v,
kw, kw,x)lsa SC.
XES
18

---

Combining the above inequalities we conclude the proof of part (a).
For part (b), assume that D is indeed X-nice and 7-Poincaré. We first Proposition A.3 well as Hoeffding bound, get that [x [[ (w,))
x)| - a] E __ 20 C' with probability least 1- 8/3 over S (since [S] large enough), for some universal constant C' 0. Then, we use part (ii) of Proposition A.3 to lower bound the minimum eigenvalue of M, = E [n[]s] by CXxCr. Using part (iii) of Proposition A.3 to bound the second moment of each of the elements of MD, we may use Proposition A.2 get that Ms = C' l (and our spectral test passes) with probability at least - 8/3. It remains to show that the hypercontractivity tester will accept with probability at least 1 5/3 (since, then, the result follows from union bound).
4ir
We acquire samples from the hypercontractivity tester through rejection sampling (we keep only 2n the samples within the strip). Since the probability of falling inside the strip is at least CYxe7, the
number of samples we will keep is at least |S* > CPxCT for some large enough constant C" > 0 (due to Chernoff bound) and with probability at least 1 - 5/6. We now apply Lemma A.1 to get that the distribution of projiw x conditioned on the strip (ww, x) S a y-Poincaré, since D is also y-Poincaré. Hence, the hypercontractivity tester accepts with probability at least 6/6 due to Proposition 3.5.
|8|r
C Proofs from Section 4
C.1 Proof of Proposition 4.2
We restate Proposition 4.2 here for completeness.
Proposition C.1 (Modification from [GKSV23, DKTZ20a, DKTZ20b]). For distribution Dxy over I x {+1} let opt be the minimum error achieved by some origin-centered halfspace and w Sd-1 a corresponding vector, Consider La as in Equation (4.1) for a > 0 and 1j < 1/2. Let I and v E span (wan(w, w*) such that (v. w and (v, w") 2
W E gd-1 with <(w,w*)=
Then, for some universal constant C > and any a 2 Ztand we have V W. (w: xxy 2 2
A A2 A3, where
A o
P [(v, 2 and ((w, x) S 6
C
C'
A2 lan
P [(w,))
S 2 and A3 Vopt v (v, [1((w.))13)
Moreover, if the noise is Massart with rate n,, then Ww (xy))l (1 11n)AA) Ag.
Proof. The proof is slight modification of a part of the proof of Lemma 4.4 in [GKSV23], but we present it here for completeness.
For any vector E IRd let: Xw = (w,x) x) and x. (v, x). It follows that projy (x) x e2, where projy is the operator that orthogonally projects vectors on V. Using the fact that Vw((w, x)/l|w||a) = x (w, x)
Xww for any E Sd-1 the interchangeability of the gradient and expectation operators and the fact that E' is an even function we get that
Ww E l. (I(w,))) y (x Xw xw
Since the projection operator projv is contraction, we have V Co 2 l[projv (w) and we can therefore restrict our attention to simpler, two dimensional problem. In particular, since projy (x) = x,er + 02, we get
prooj V FwCo(w)l = LE
E' ([xw<l l) .y -V-x]]
E
Ey (Ixwl) 1) siig((w"", xx) (1 fy a sign((w", ,x)))) Xxy
Let Fly, x) denote 1-21 {y # sign((w*, (w)).))) We may write x, as |xv| sign(xy) and let g C R2 such that sign(x.) sign((w" xx) =-1 iff x G.
19

---

W
G
G
A
A2
A
G
G
Figure The Gaussian mass in each of the regions labelled A and A2 is proportional to the corresponding term appearing in the statement of Proposition 4.2. As tends to 0, the Gaussian mass of region A2 shrinks faster than the one of region A1, since both the height (or) and the width ( (1ang) of A2 are proportional to while the width of A is not affected (the height is o/3). Lemma 4.3 demonstrates that similar property universally testable under any nice Poincaré distribution.
sign((w",xx x)) 1(x 9} 1(x G}. We get Then, sigu(x.).ssin(((
projy (w)o(w)llz
E (xxl) (1fx E =9] 1(x & 9}) F(y,x) x) [xxvl_]
2 E (1xwl) 1(x E 9} F(y.x) [x]]] E l (xwl) 11 [x E 9) Fly. x) [xv|
Let A = EEC (Ixw]] -) 1xx E G) Fly, x) (xx]] and A22 = E(C, (xwl) 1/x & g) F(y,x) |x,]] 0. Therefore, () 1 G) [xv]]. When the noise is adversarial, we have A 2 E[C. ([xw )) 1 E 9}- x (E 1(x E G} 1 * bign((w,,. x))} [xy]].
In the Massart noise case Eyyx F x = 1 (x) E [1 2n, 1]. where 1
we have that A > (1 2ny) E E Xw
For any a 2 o we have that
E ((xwl) 1(x [x/]]
2 E c ((xwl)) 1(x E g} 1 (xx1s)) [xx]]
(since terms are positive)
E
1(x 1f1 |xwl S ØJ
(by Proposition A.4)
E
1(x E 9] 1 (1xx 1 [1xx/2a)
0
a
E
[xx 1(1x/220)
(see Figure 1)
p
Xw
S σ 6
and
|x, 2
def A
20

---

Moreover, for some universal constant C" > O. we similarly have
(xxl) 1(x $ F)),)
[xv|
- B E [Xw] 1)
1(x $ 9) [xv|] (since F(y,x) S 1)
- B
[1xwlsg] 1 $ 9) |xv]
(by Proposition A.4)
C²
[[(xmls (53) 1 11x0s am Xxv <
0
(see Figure 1)
S C¹
E
1
(1xw
[5 [1x0ls 21mn))
tan
C²
def
Σ 2 tan
Xw S
A2
2
Hence, we have shown that, in the Massart noise case, we have V (w) 2 (1 (1-211) 21) A desired. For the adversarial noise case, it remains bound the following quantity
2 EB lo (Xwl) 11 (xEE) 1 (yzsigul (w x))] |xx1] -
20"
E
[(xE] - 1(xxwls)) 1 (ustiigu (wr x))1 -
20
E [[1xwli5)) [ (ww 20113 [xv]
M
20'
VVpp V E [xxl 11 ((x1lg))
del As
where the final inequality follows from Cauchy-Schwarz inequality.
C.2 Proof of Lemma 4.3
We restate Lemma 4.3 here for convenience.
Lemma C.2 (Universally Testable Structure of Surrogate Loss). Let Dxy be any distribution over
Rd {=1}. Consider C. as in Equation (4.1). Then, there is a universal constant > 0 and tester that given a unit vector w E Rd, E (0, 1), 1j < 1/2, 7 > 2 1, a S cxe and a set S of i.i.d. samples from Dxy with size least C dt 048 log(d)AC, runs in time poly(d, X, t. log()))
and satisfies the following specifications
(a) If the tester accepts then, the following statements are true for the minimum error opt. achieved by some origin-centered halfspace on and the oplimum vector w's E Sd-1
If the noise is Massart with associated rate and Wo (w:S)) S Exo then b( w, w3) (1+7))))
either L(w, wy') (x=(1+=*)
1-2n -0.
1-2n
If the noise is adversarial with opts S CX and V Wo S)Il2 < exa then either L(w, w's) S CXC or L(-w, w'') S CX (1+(1+ (1+
(b) If the marginal Dx is X-nice and Pooincar then the tester accepts S with probability at least 8.
Proof of Lemma 4.3, The testing algorithm receives w E Sd-1 E (0, < 1/2, 7 > 0, > 1, and a set Rd {+1} and does the following for some sufficiently large C1 > 0
a < 2X
1. If P (sl.)sssklww..... x)| S नरश or Pix.viesl
> cC then reject.
21

---

2. Compute the (d - 1) x (d - 1) matrices Mÿ and Mg as follows:
M
IR (x,y)88
(projel (p(oro x)" 11 ((wx))ss)
Mg
E (x.y)ES
(p (proj w x)" ([wx)))))
3. Run the (maximum singular value) spectral tester of Proposition A.2 M given ó 4
À C1 and + Cias i... reject if the maximum singular value of Mg is greater than C1
4. Run the (minimum singular value) spectral tester of Proposition A.2 on Mg given 8 i 20 À Ci2C and 0 T.x.. i... reject if the minimum singular value of Mg is less than
5. Run the hypercontractivity tester S = (proj ww (x,y) y) S and (w.x)) o0 i... solve an appropriate SDP (see Prop. 3.5 with y f- 7, + 8/4) and reject if the solution is larger than specified threshold. Otherwise, accept.
For part (a), we suppose that the testing algorithm has accepted Therefore, S has passed all the tests required for part (a) of Lemma 3.2 and there exists universal constant C" > 0 such that
TP (x.W)ES
Kv, 2 C'AC"
(w.x)) $ 2 C'Xo'a
Moreover, have
IP
(ixx)ss(((WW (w, - -
P P(xx)esslkw x)| S 5 <o C'XC" and
E (x
xv)
[w,
0
- C'''0
2
E (x.8)ES
(v,x)
0 [(w,x)
2
6
C'Xo'
Since Proposition 4.2 holds for any distribution, it will also hold for the empirical distribution (uniform on 5). We apply Proposition with a = dxxer to lower bound (w; (or (WWco(-;:5)) as follows
V (w; S)112 (1 Ag A3
(adversarial noise case)
Cw (w: S)1l2 2 (1 2n) (a) - Aa
(Massart noise case)
Combining the above inequalities with bounds implied by the fact that has passed the tests, concludes the proof of part (a), since (after observing that lan 0 2 0) we get
VCA
opt C.
V Wo (w; S)ll2 2 CXC
(adversarial noise case)
0
3(1 1)
VCa2c12
[w S1122
(Massart noise case)
CXC
0
For part (b), we follow similar recipe as the used to prove part (b) of Lemma 3.2, i.c. the following reasoning to show that the tests will pass with probability at least
1. We assume that the marginal distribution Dx is X-nice and PPioncarr.
2. We use Proposition A.3 to bound the values of the tested quantities under the true distribution.
3. We use appropriate concentration results (Hoeffding/Chhenll Bounds and Proposition A.2) show that, since |S| large enough, each of the empirical quantities at hand does deviate a lot from its mean.
This concludes the proof of Lemma 4.3.
22

---

C.3 Proof of Main Theorem
We restate the main Theorem here for convenience.
Theorem C.3 (Efficient Universal Tester-Learne for Halfsspcces), Let Dxy be any distribution over
R x {+1]. ). Let be the class of origin centered halfspaces R. Then, for any X z 1, 7 > 0, c and 6 E (0,1) 1), there exists an universal tester-learner for C w.r.t. the class of X-nice and y-Poincaré marginals up to error poly(A) (1+?4) -opt c, where opt min P PDx + sign (w. x ]]. and error probability most using a number of samples and running time poly X, 7 ē: log 8)
Moreover, if the noise is Massart with given rate < 1/2, then the algorithm achieves error opt + with time and sample complexity poly d,, X, 7, 1-2n) log 4)-
Proof of Theorem 4.1. Note that we will give the algorithm for 5 t 8' =1/3 since we can reduce the probability of failure with repetition (repeat Oloog {) times, accept if the rate of acceptance is (11) and output the halfspace achieving the minimum test error among the halfspaces returned).
For reader's convenience, we now restate the algorithm on page (note that together with the algorithm we include additional detail relevant to the analysis). The algorithm receives À 2 1, Y > e > 0 and 1) E (0, 1/2) U {1} (say 1 when we are in the agnostic case) and does the following for some appropriately large universal constant C1, C2 0.
1. First, create a set of parameters D and parameters E C and A 0 as follows.
" = 1, then Σ is 0 -cover of the interval [0, पमे.T and A TÍ Otherwise,
E
1-2n let Σ = E- 2n) and C1A
2. Then, draw a set S1 of C2 (Ad) C2
vr) i.i.d. samples from Dxy and run PSGD, as specified in
Proposition A.5 with + A. 8 +
5' on the loss La for each a E Σ.
3. Form a list L with all the pairs of the form (w, o) where w E gd-1 is some iterate of the PSGD subroutine performed on far.
C2 i.i.d samples from Dxy and compute for each (w,o) E
4. Draw fresh set S2 of C2
Ad
ye L the value WW S2) 1|2. If, for some E E, Co S2)112 > A for all (w, o)
L, then reject.
5. Update I. by keeping for each a E E only one pair of the form (w,o) for which we have Ww (w)S)]ll S A.
6. Run the following tests for each (w, o) E L to ensure that part (a) of Lemma 4.3 holds for each of the elements of L, i..., that any stationary point of the surrogate loss that lies in L is angularly close to the empirical risk minimizer (or the same holds for the inverse vector).
If P ((x.))sss (lw,, x) < A reject.
<
GIAOT or ((x.)ess (Kw,, x)1 S] o CiACt, then
Compute the (d - 1) x (d 1) matrices M and M3, as follows:
M E (x.))
(proju ()roj x)" L [[(
M5.- E (proj i (proj x)" (((w))
(x,
Run the (maximum singular value) spectral tester of Proposition A.2 on M given 8 & A C1 and Ci
2 i... reject if the maximum singular value of
M is greater than a- - C,AC:
Run the (minimum singular value) spectral tester of Proposition A.2 on M5, given C1 and f c, i.e. reject if the minimum singular value of M s, is less than ŌzPo5.
8 _ x
23

---

Run the hypercontractivity tester on S' = {proj w x: (x,y) E Sy and (w, S a). i.e., solve an appropriate SDP (see Prop. 3.5 with ? t 7/ + 80/C1) and reject if the solution is larger than a specified threshold.
7. Run the following tests for each pair of the form (w.o) and (-w, where (w,o) a) E to ensure that part (a) of Lemma 3.1 activated, i.e., that the distance of vector from the empirical risk minimizer is an accurate proxy for the error of the corresponding halfspacc. Set (()) (1+7')e A7"
If (x..)) [((,,)) x) S > C1AC1 A then reject.
Compute the (d 1) (d - 1) matrix Ms. follows
(proj 1 x) x)² 1[[(w, x)| E [(i 1000 2013
Ms.
(x
(i 1)²
Run the spectral tester of Proposition A.2 Ms given å cT. X t C1 and
+ G i... compute || llop and if ||Mls > C Ci then reject.
8. Otherwise, accept and output the vector w that achieves the smallest empirical error on S2 among the vectors in the list L.
For the following, let 1 in the Massart noise case and a = Ci in the adversarial noise case. Consider also opts, to be the error of the origin- ientereentered halfspace with the minimum empirical error on S2 and w the corresponding optimum vector.
Soundness. We first prove the soundness condition, i.e., that the following implication holds with probability least 1 8' over the samples:
the tester accepts, then P ly + sign((w. x))] S a opt + Dxy
The tester accepts only if for every a E Σ, we have some w E with (w: S2)l12 S A (step 4) and for which part (a) of each of Lemmas 4.3 (step 6) and 3.1 (step 7) is activated. Therefore, in the Massart noise case, for any E 2, there is some w such that either (w, E L (-w,o) E L and also
L(w, (w,) S
+ 7
def
0
(C.1)
74 A
P & sign((w, x))] < opts,
C" C²
(C.2)
Sq
In the adversarial noise case, the above are true conditional on a being such that opty, S C'xer. Therefore, in the Massart noise case, the above true for C which gives
E(1-2n)
p + sign( (w, x))] S opts, C² E S1
In the agnostic case, condition C.2 is true for some [0, c, such that
C S opts, S C'XC'
C'Xe'
unless opt > 1 in which any halfspace has error most opt (C(C")C1TC)
Hence get
Plu + (wg S poly(A) (1 7 opts, + C'' E
Soundness follows from the fact that if |S2] is sufficiently large (but still polynomial in every parameter, since the VC dimension of the class of halfspaces in Rd is d + 1), then lopts, opt s αx with probability at least 1 8'.
'Note that only at most |S2] many terms below
hence Ms, be computed efficiently.
24

---

Completeness. Suppose now that the marginal is indeed X-nice and 7-Poincaré. Then, for suffi- ciently large S,, after step 3, will contain a stationary point of Cx( - Dxy) for each o Σ, due to Proposition A.5. If S2 is large enough, then steps 4, 6 and 7 will each accept with probability least 8 /C, due to part (b) of Lemmas 4.3 and 3.1, as well as the fact that each coordinate of W (w; has bounded second moment (Proposition A.3) and therefore W (w; S2) is concentrated around C. (w; Dxy) for any fixed w such that (w, σ) E L (we also need union bound over L). Hence, in total, the tester will accept with probability at least 1 8'.
25


Reviews:
[{"review_id": "pPqJtq4U0w", "reviewer": "Reviewer_AEBD", "summary": "Learning halfspaces is a very well studied problem in machine learning. In the agnostic (adversarial label noise) and distribution free setting, this problem has been known to be computationally intractable. As a result, there have been several works of agnostic learning in distribution specific settings (where the marginal distribution belongs to a particular family of distributions, say Gaussian or log-concave). In this scenario, the learner has an error of the form $OPT + \\epsilon$, where OPT denotes the optimal 0-1 error. This however has complexity $d^{1/\\epsilon^2}$, and the exponential dependency on $1/\\epsilon$ is tight. This motivates the designing of learning algorithms that have better sample complexity with respect to $1/\\epsilon$, whereas the error becomes $f(OPT) + \\epsilon$ for some function f.\n\nOften these works use a single distribution as the target marginal distribution. In this work, the authors studied this problem with respect to a set of marginal distributions (Universal testable learning, Definition 1.1). The authors studied this problem in the newly introduced Testable learning framework  by Rubinfeld and Vasilyan. Here the goal is if the tester accepts, then with high probability the output of the learning is close to some function of OPT, and if the data satisfies the distributional assumptions, the algorithm accepts with high probability.\n\nHere the authors design a universal tester learner for Halfspaces with respect to distributions with bounded Poincare constant (Definition 2.4) and concentration and anti-concentration properties (Definition 2.1) in Theorem 1.2. Moreover, this class of distributions contains strongly log-concave distributions, and assuming Kannan–Lovasz–Simonovits (KLS) conjecture, contains all log-concave distributions (Definition 2.2-2.6). Later in theorem 1.3, they design a universal tester learner for Halfspaces with Massart noise (the labels are flipped by an adversary with probability $\\eta <1/2$).\n\nSome previous and concurrent works for single distribution D^* assumption use approximate moment matching techniques, where the algorithm tests if the low moments of the input distribution D approximately matches with that of D^*. However it is not clear if this same approach can be applied for a collection of distributions. This has also been discussed in the introduction.\n\nThe authors first design testers for testing bounded disagreement (Lemma 3.1) and of testing anti-concentration properties (Lemma 3.2) which uses a tester for testing hypercontrctivity. It is known that any distribution $D$ with bounded Poincare constant is hypercontractive in Sum-of-Squares (SOS) framework. Thus the authors run a polynomial time semidefinite program for the later purpose. Next in Section 4, the authors design the final tester (Theorem 4.1). They use a surrogate loss minimization technique for the surrogate loss function defined in Equation 4.1. The main idea is that stationary points of surrogate loss are close to some optimal vector corresponding to the halfspace (the related lemma is Lemma 4.3). Lemma 4.3 contains bounds for both Massart and adversarial noise settings.\n\nIt would be interesting if tester-learners can be designed for function classes other than halfspaces. The authors also discusses this at the end of Section 1.\n", "questions": "None", "limitations": "It would be interesting if tester-learners can be designed for function classes other than halfspaces. The authors also discusses this at the end of Section 1.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Overall this is a nice result which generalizes several previous works designed for a single marginal distribution assumption and studies for the setting of a collection of marginal distributions. ", "weaknesses": "What is the usefulness of the tester-learner model in real life applications. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "QwKUDStVtP", "reviewer": "Reviewer_9R84", "summary": "The paper proposes the first tester-learner for learning the class of halfspaces universally over a class of strongly log-concave distributions (or the class of all log-concave distributions under the KLS assumption). Unlike prior works that crucially rely on testing a specific given marginal distribution while rejecting other well-behaved distributions, the proposed algorithm can accept the marginal distribution as long as it is in the family $\\mathcal{D}$. The proposed algorithm is motivated by the tester-learner using non-convex SGD [GKSV23] but with a more careful analysis on the anti-concentration property. The algorithm is powered by the SOS program to check the hypercontractivity of the desired random variable $Z$ that exhibits certain anti-concentration properties, which is known suffices for identifying the Poincare distributions ([KS17]).\n", "questions": "While Massart noise is considered in this paper, is it possible to directly apply the techniques to other more challenging types of noise? ", "limitations": "No concerns.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Designing provable tester-learners addresses the issue that traditional learning algorithms crucially rely on distribution assumptions which could be stringent in practice, which is of importance both from the practical and theoretical sides. This paper proposes the first tester-learner that universally accepts any distribution from a broad family of distributions that satisfy a Poincare inequality, largely generalizing those algorithms that only accepts a certain distribution. The technical contribution lies in identifying the Poincare distributions by applying SoS framework to certify a hypercontractive property of the constructed random variable, which generalizes the known results for standard Gaussian to distributions with weak anti-concentration properties. The technique could be of independent interest for testable weak anti-concentration.\n", "weaknesses": "From the technical side, the SoS program for checking the hypercontractive already exists in [KS17]. The contrition of this paper is more on the application side of such a framework on the problem of testing-learning halfspaces with additional assumptions of certain concentration and anti-concentration. That being said, it is a novel application of such a framework given that it solves a very interesting and important problem.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their feedback and for appreciating our work!\n\nThe reviewer is right that it is an interesting open question whether our techniques can be applied to achieve optimal guarantees (i.e., $\\mathrm{opt}+\\epsilon$) for testably learning halfspaces when the noise model is more challenging than Massart. We believe that such results could conceivably be accomplished by future work for other types of noise, e.g., for Tsybakov noise (by adapting Proposition 4.2). But as the reviewer is likely aware, at least under adversarial noise (where we achieve $O(\\mathrm{opt})+\\epsilon$), there is evidence (e.g. see [1], [2], [3], [4]) that achieving optimal guarantees in polynomial time is impossible. \n\n\n[1] Diakonikolas, I., Kane, D.M., & Zarifis, N. (2020). Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. NeurIPS 2020.\n\n[2] Goel, S., Gollakota, A., & Klivans, A.R. (2020). Statistical-Query Lower Bounds via Functional Gradients. NeurIPS 2020.\n\n[3] Diakonikolas, I., Kane D.M., & Ren, L. (2023). Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. ICML 2023.\n\n[4] Tiegel, S. (2023). Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems. COLT 2023."}, {"review_id": "s8BIfIwM5l", "reviewer": "Reviewer_EFhK", "summary": "The paper develops a tester-learner for halfspaces in the recently proposed testable learning framework of [RV23]. A recent work [GKSV23] had studied the same problem and proposed tester-learners for halfspaces with Massart noise and in the agnostic setting, for any particular strongly-log concave distribution. This work qualitatively improves upon [GKSV23] by developing a tester-learner for a class of strongly log-concave distributions rather than a fixed strongly log-concave distribution, and also provides better algorithmic complexity for the agnostic case. In fact, this work captures $\\gamma$-Poincare distributions which contain strongly log-concave distributions and under the [KLS95] conjecture also all log-concave distributions. In the Massart noise case, their algorithm works for log-concave distributions unconditionally.\n While following the recently developed approach (and used by [GKSV23]) of non-convex SGD for learning halfspaces over certain good distributions, this paper does a more careful analysis of the gradient lower bound leading to the requirement of a certain hypercontractivity property (which holds for Poincare distributions). The paper uses techniques for previous work [KS17] to show that sum-of-squares (SoS) SDP can be used to certify this hypercontractivity which is a main technical novelty.\n", "questions": "1. It may be helpful to clarify why the main Theorem 4.1 also captures log-concave distributions unconditionally for the case with Massart noise, while only capturing strongly log-concave distributions in the agnostic setting. \n\n2. Is it clear that the previous work of [GKSV23] cannot be tweaked (e.g. by discretizing the space of the vector of moments to be matched) to work for the class of strongly log-concave distributions? \n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper proves better and qualitatively more general and stronger bounds for testable learning of halfspaces over a general class of distributions. The technical contributions - the use of properties of Poincare distributions and using SoS to certify hypercontractivity -  are interesting and novel in the context of this problem, and provide for universal tester-learners. The paper is well written and effectively conveys its main contributions and the techniques used. Overall, the paper is technically solid.", "weaknesses": "The paper follows the same roadmap of [GKSV23] with better analysis and a new tester (based on previous work [KS17]) for hypercontractivity, and in that sense feels somewhat incremental. The results are also moderate improvements and generalizations of previous results and not entirely unexpected. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback. Here are our responses to the questions, which we will aim to incorporate in a future revision:\n\nTheorem 4.1 states that in the Massart noise case, we can achieve the optimal $\\mathrm{opt}+\\epsilon$ guarantee, while in the agnostic setting, we get an approximately optimal guarantee which is proportional to a polynomial of the Poincare parameter ($\\gamma$) of the target class of marginal distributions. Therefore, in the agnostic setting, we obtain a constant approximation factor only when $\\gamma$ is constant (which is true for strongly log-concave distributions and conditionally true for log-concave distributions). In the Massart noise case, however, even when $\\gamma$ is polynomial in the dimension, the guarantee is optimal (and the runtime is still polynomial in the dimension). It is known that the parameter $\\gamma$ that corresponds to isotropic log-concave distributions is indeed bounded by a polynomial in the ambient dimension (see, e.g., [1]). We will add such a discussion in the final version of the paper.\n\nIt is not clear whether there is a more direct approach to providing results in the universal setting based on prior work. Recall that (roughly) the work of [GKSV23] considers the distribution of examples conditioned to a number of strips perpendicular to vector w and compares the moments of each of these conditional distributions to what these moments should be (under a specific distribution). Now, even for a single one of these strips, it is unknown how to determine whether a set of moments indeed matches those that would arise from a strongly log-concave distribution (which is not given to us in advance). \n\nEven the seemingly simpler task of determining whether a set of low-degree moments of a distribution matches those of some unknown strongly log-concave distribution is not known to be achievable efficiently (using a method employing some form of discretization, or any other method). Indeed, such an algorithm would in particular give a novel alternative method for certifying hypercontractivity of an unknown strongly log-concave distribution, which is a task that is only known to be achievable using a highly sophisticated sum-of-squares approach [3].\nHowever, the moment discretization approach might conceivably be useful towards generalizing the results of [2] in the universal setting.\n\n[1] Chen, Y. (2021). An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geometric and Functional Analysis, 31, 34-61.\n\n[2] Gollakota, A., Klivans, A. R., & Kothari, P. K. (2023). A moment-matching approach to testable learning and a new characterization of rademacher complexity. STOC 2023.\n\n[3] Pravesh K Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor\nnorms. arXiv preprint arXiv:1711.07465, 2017.\n"}, {"review_id": "W9BSJo9aKd", "reviewer": "Reviewer_eYN2", "summary": "This work studies the problem of designing tester-learners for halfspaces in the agnostic setting and under Massart noise. In the setting of tester-learners, we do not make distributional assumptions on our samples, but rather require that our algorithm produces an accurate output whenever the input satisfies a sequence of efficiently computable tests. Further, if the samples actually come from a specific target distribution, it is required that the tests pass with high probability.\n\nPrevious tester-learners for noisy halfspaces used tests tailored towards a *specific* distribution, e.g., a specific strongly log-concave distribution. As a consequence, these testers might reject samples from a different strongly log-concave distribution although algorithmically it would have been possible to learn the underlying halfspace. The authors propose a tester which simultaneously accepts for all Poincaré distributions that satisfy some natural niceness conditions. This class includes all isotropic strongly log-concave distributions. When their tester accepts, the tester-learner outputs a halfspace achieving error $O(\\mathrm{opt}) + \\varepsilon$, where $\\mathrm{opt}$ is the error of the optimal halfspace on the distribution of the input. For the Massart setting they can handle all isotropic log-concave distributions and achieve error $\\mathrm{opt} + \\varepsilon$.\n\nThe authors argue that previous works were inherently limited to work with only a single distribution since they were matching moments with this specific distribution. In their work, they overcome this issue by only checking the actual properties they need in the proof of accuracy which are not tied to any specific distribution.", "questions": "Related to the above: In the agnostic setting, your error bound scales as $\\mathrm{poly}(\\lambda) (1+\\gamma^4) \\mathrm{opt} + \\varepsilon$, where $\\lambda$ is the niceness parameter of the marginal distribution and $\\gamma$ the Poincaré constant. How does this compare to the non-testable learning error?", "limitations": "Limitations were addressed appropriately.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In my eyes, designing tester learners which simultaneously accept for a large class of distribution is an important step for bringing the framework of testable learning closer to practice. The motivation for testable learning was that designing algorithms that only work under specific distributional assumptions has little value in practice since likely these assumptions will not be met. Thus, we would at least like to know if we can trust the output of our algorithm when we run it on actual data or not. While previous tester-learners did have this benefit, it seems that the proposed testers \"overfit\" to specific distributions. However, the chances that real world data comes from any specific distribution are rather small. Thus, providing testers which work for larger classes of distributions is an important step.\n\nOn a technical level, their tester has a natural explanation that I like: It simply checks the properties that are need in the proof in the non-testable setting. Further, the paper is very well-written (except the point below).", "weaknesses": "I feel that the technical overview that the authors provide might be hard to understand if the reader is not familiar with the arguments in previous work or at least the general area. It would be nice if it could be adjusted slightly to make it more accessible to a wider audience.\n\nAlso, specifically for the agnostic setting, it would be useful to compare your approximation factor to (a) testable learners that only work for one specific (or a more restricted class of distributions) and (b) non-testable learners for the same distribution class you consider.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their suggestions and comments!\n\nPrior work in the area has demonstrated that, in the distribution specific setting, assuming that the marginals are “nice” (i.e., that $\\lambda$ is some constant) is sufficient and there is no dependence of the error bound on the Poincare parameter (hence, the error bound would be in that case $\\mathrm{poly}(\\lambda)\\mathrm{opt} + \\epsilon$). We note that the precise dependence on the niceness parameter $\\lambda$ was not stated explicitly in prior work. As for the dependence on the Poincare parameter, it arises due to the need to provide efficiently testable bounds to certain quantities (see Lemma 3.2) which, in the non-testable setting, admit tighter bounds; in other words, the bounds we use involve some slackness due to testability requirements. \n\n  Regarding prior work on regular (non universal) testable learning, prior work only provides results with respect to strongly log-concave marginals (based on the technology of fooling halfspaces via moment matching), where $\\gamma$ is always a constant (see also lines 200-206).\n"}]

Author rebuttal:

Meta-review: This is a strong result about a fundamental, well-motivated problem, requiring interesting and non-trivial ideas.
Decision: Accept (oral)