Forster Decomposition and Learning Halfspaces with Noise
Authors: Ilias Diakonikolas
Daniel Kane
Christos Tzamos
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: learning theory
Forster transform
halfspaces
Massart noise

Abstract: A Forster transform is an operation that turns a multivariate distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any distribution can be efficiently decomposed as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently. As the main application of this result, we obtain the first polynomial-time algorithm for distribution-independent PAC learning of halfspaces in the Massart noise model with strongly polynomial sample complexity, i.e., independent of the bit complexity of the examples. Previous algorithms for this learning problem incurred sample complexity scaling polynomially with the bit complexity, even though such a dependence is not information-theoretically necessary.


Forster Decomposition and Learning Halfspaces with Noise
Ilias Diakonikolas University of Wisconsin- Madison ilias@cs. wisc. edu
Daniel M. Kane
University of California, San Diego dakane@cs. ucsd.
Christos Tzamos
University of Miacconsin-Madionn tzamos@wiscc edu
Abstract
A Forster transform is an operation that turns distribution into one with good anti- concentration properties. While Forster transform does not always exist, we show that any distribution can be efficiently decomposed as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently. As the main application of this result, we obtain the first polynomial-tine for distribution distribution-indeeeeeen PAC learning of halfspaces in the Massart noise model with strongly polynomial sample complexity, i.e., independent of the bit complexity of the examples. Previous algorithms for this learning problem incurred sample complexity scaling polynomially with the bit complexity, even though such a dependence is not colommttion-hhooeticaall necessary.
algorithm
Introduction
The motivating application for this paper is the problem of (distribution independent) PAC learning of halfspaces in the presence label noise, and more specifically in the Massart (or bounded noise) model. Recent work [DGTI9] obtained the first computationally efficient learning algorithm with non-trivial error guarantee for this problem. Interestingly, the sample complexity of the [DGT19] algorithm scales polynomially with the bit complexity of the examples (in addition, of course, to the dimension and the inverse of desired accuracy). This bit-complexity dependence in the sample complexity is an artifact of the algorithmic approach in (DGT19]. information-theoretiealll -hw.reticcally.....omoe..... no such dependence is needed - alas, the standard VC-dimension-basse sample upper bound (MN06) is non- constructive. Motivated by this qualitative gap in our understanding, here we develop methodology that leads to a computationally efficient learning algorithm for Massart halfspaces (matching the error guarantee of [DGT19) with "strongly polynomial" sample complexity, i.c., sample complexity completely independent of the bit complexity of the examples.
(distribution-indeeeneeen
Halfspaces and Efficient Learnability We study the binary classification setting, where the goal is to learn a Boolean function from random labeled examples with noisy labels. Our focus on the problem of learning halfspaces in Valiant's PAC learning model [Val84] when the labels have been corrupted by Massart noise [MN06].
A halfspace is any function h Rd + {=1} of the form h(x) sign w -)). where the vector
E IRd is called the weight vector, 0 E IR. is called the threshold, and sign IR + {+1} is defined by sign(t) = 1 if 2 and sign(t) = -1 otherwise. Halfspaces (or Linear Threshold Functions) are central concept class in learning theory, starting with early work in the 1950s [Ro558 Nov62 MP68]
and leading to fundamental and practically important techniques [Vap98) FS97. Learning halfspaces
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

is known to be efficiently solvable without noise (see, e.g., [M994] and computationally hard with adversarial (aka, agmostic) noise [GR06] FG [6 The Massart model is natural compromise, in the sense that it is realistic noise model that may allow for efficient algorithms without distributional assumptions. An essentially equivalent formulation of this model was already defined in the 80s by Sloan and Rivest [Sl088, [Slo92 RS94 Slo96], and very similar definition had been considered even earlier by Vapnik [Vap82].
Definition 1.1 (Massart Noise). Let be a class of Boolean functions over X = R2 Dx be a distribution over X, and 0 S 7 < 1/2. Let be unknown target function in C. A noisy example oracle, ExMass( D n)) works as follows: Each time ExM"*(f, (f. Dx,n) is invoked, it returns labeled example (xr, y). where x ~ Dx, f(x) with probability - 17(2)) and = - f() with probability (a)) for unknown parameter 7yx)) S nn Let 'D denote the joint distribution on (1r, y)
generated by the above oracle. The learner is given i.i.d. samples from 'D and wants to output a hypothesis & such that with high probability the error Pr(x.))>((((r) * y] is small.
In recent years, the algorithmic task of learning halfspacee in the Massart model has attracted significant attention in the learning theory community. In the iistributionnspeciiffi PAC model, where structural assumptions the study of learning homogeneous halfspaces with Massart noise. Since this work, a sequence of papers [ABHZI6] YZ17 ZLCI7 DKTZ20) ZSA20 [ZL21] developed efficient algorithms for this problem, achieving error OPT 6, for various classes of structured distributions.
imposed on the marginal distribution Dx, the work of [ABHUI5] initiated
In the fistributtoo-indeeeeete setting, where no assumptions are made on the distribution Dx. progress has been slow. The existence of an efficient PAC learning algorithm for Massart halfspaces had been long-standing open question posed in number of works [Slo88] Coh97 [Bu033, with no algorithmic progress until recently. Recent work [DGT19] gave the first polynomial-time algorithm with non-trivial error guarantees for this problem, specifically achieving enror + where v) is the upper bound on the noise rate. Since the dissemination of [DGT19, a number of works have studied the complexity of learning halfspaces and other concept classes in the presence of Massart noise. CCMY200 gave a proper learning algorithm for Massart halfspaces matching the error guarantee of [GTT99] On the lower bound side, hardness results were established for both exact [CKMY20 and approximate learning (DK20). Specifically, (DK20) gave a Statistical Query (SQ) lower bound ruling out efficient SQ learning algorithms achieving any polynomial relative approximation for Massart halfspaces. Interestingly, the [DGT19] approach also motivated the design of the first boosting algorithm for Massart PAC learning [DI+ 21). The boosting algorithm of [DIK + 21 efficiently achieves error + e, for any concept class, starting from a black-box Massart weak learner.
To motivate our results, we state the guarantees of the [DGT19] algorithm in more detail. (The proper algorithm of (CKMY20) builds on the same ideas and has qualitatively similar guarantees.) Let Dx R be the marginal distribution on the examples and 6 be an upper bound the bit complexity of points x in the support of Dx. Then, the algorithm of [DGT19 requires n = poly (d, h, 1/e) labeled examples, runs in time poly(n, b) and achieves misclassification error da + e. The dependence on b in the runtime is likely to be inherent. (Learning halfspaces without noise amounts to solving a general linear program (LP); removing the b dependence from the runtime would yield strongly polynomial algorithm for general LP.) On the other hand, there is no a priori reason to believe that the poly(b) dependence is needed in the sample complexity. In fact, is known (MN06) that (dly(d/e) samples information-theoretica sample complexity bound constrrstre,,,ee in the sense that the sample upper bound argument does not yield sub-exponential time learning algorithm. The above discussion motivates the following natural question: Is there an efficient learning algorithm for Massart halfspaces using only poly(d/e) samples? ? The main result of this paper provides an affirmative answer to this question.
suffice to achieve optimal misclassification error. Of course, this
1.1 Our Results and Techniques
The main learning theory result of this paper is the following.
Theorem 1.2 (Main Learning Result), There is an algorithm that for all 0 < 1) < 1/2, on input set of n poly (d, i..d examples from a distribution D Ex (f, Dx 17) on Rd+1, where I is an unknown halfspace on Rd, it runs in poly(n, (n,b,11 1e) time, where b is upper bound on the bit complexity of the examples, and outputs a hypothesis h that with high probability satisfies
Pr Pr(x.) [x(z) + v) I +e.
2

---

Brief Overview of [GT19] Algorithm To explain the source of our qualitative improvement, we start with high-level description of the previous algorithm from [GGT19. At a high-level, this algorithm works in two steps: First, one designs an efficient learner for the special case where the target halfspace has some non-trivial anti-concentration (aka "large" margin). Then, one develops an efficient reduction of the general (no margin) case to the large-margin case. Formally speaking, such a reduction is not entirely "black-box"; this description is for the purpose of intuition.
First, we note that without loss of generality the target halfspace is homogeneous (since we are working in the crnrriutioo-indpeendde setting). The aforementioned reduction, used in [DGT19], relies on method from [BFK (refined in (DV04).. The idea is to slightly modify the distribution on the unlabeled points to guarantee a (weak) margin property. After this modification, there exists an explicit margin parameter o (211/ply(dd d, b)), such that any hyperplane through the origin has a non-trivial mass of the distribution at distance at least a standard deviations from it. a is a bound on the margin, the a algorithm developed in step one has sample complexity (and running time) poly(d, /a, 1/c). This is the source of the "I-dependence" the sample complexity of the [DGTT9] algorithm (recalling that 10(1poly(( 6))).
As we will explain below, the approach of [BFKV9 DV04 inherently leads to "0-dependence" in the margin parameter o. At a very high-level, the key to our improvement is to develop new efficient preprocessing routine that achieves o = ((1/poly(d)) This leads the desired strongly polynomial sample complexity.
Preprocessing Requirements Before we can get into the details of these preprocessing algorithms, we first need to specify the anti-concentration property that we need to guarantee. Essentially, our algorithms need there to be a decent fraction of points that are reasonably far from the defining hyperplane. More specifically, if the true separating hyperplane is defined by a linear function [(x) = w" x (for some weight vector with ||w* 112 1), we need that non- non-trivial fraction of points x (say, 1/ 1/poly (rolydd)-frase (d)-fraction) should have [[x]] be non-trivial fraction of ET]2(x))
One might ask how we can hope to achieve such a guarantee without knowing the true separator [(x) ahead of time. This can be guaranteed if, for example, the points are in radial isotoopic position. In particular, this means that for every point æ in the support of our distribution it holds that ||0||2 = 1 (1/d) Ia. where La is the d x d identity matrix. The latter condition implies that and that E (xxx"" E]]²(x)) = 1/d. Combining this with the fact that [[x) S 1 for all points x in the support, it is not hard to see that with probability at least 1/d we have that L'(x) is at least 1/d - implying an appropriate anti-concentration bound. In fact, it will suffice to have our point set be in approximate radial isotropic position, allowing Exxx") to merely be proportional to (1/d) La and allowing ||>||| to be more than one, as long as it satisfies some polynomial upper bound. We note that the size of this upper bound will affect the quality of the anti-concentration result, and hence the performance of the remainder of the algorithm.
Unfortunately, not all point sets in radial isotropic position. However, there is a natural way to try to fix this issue. It is not hard to see that our original halfspace learning problem is invariant under linear transformations, and it is standard result that (unless our support lies in a proper subspace) there always exists a linear transformation that can be applied to ensure that E B[zz"] = (1/d) Ia. However, after applying this transformation, we may still have points whose norms are too large. Essentially, we need to ensure that no point is too large in terms of Mahalanobis distance. Namely, that if Σ E(zz"), ]. we want to ensure that z-n-aa 20] is never too large. Unfortunately, in the data set we are given, this might still not be the case.
Preprocessing Routine of [BFKV% DV04 The key idea in [BFKV96 and [DV04] is to find a core set S of sample points such that the Mahalanobis distance of the points in S (with respect to the second-moment matrix of S) is not too large. This will correspond to a reasonable sized sub--istribution of our original data distribution on which our desired cnteeconcentration bounds hold, allowing our learning algorithm to learn the classifier at least on this subset. In (9F, it is shown that this can be achieved by simple iterative approach, where points with loo- Mahalanobis norm are repeatedly thrown away. This step needs to be performed in several stages, as throwing away points will alter the second-moment matrix, and thus change the norm in question. Interestingly, [BFK V96] show that the number of iterations required by this procedure can bounded in terms of the numerical complexity of the points involved.
3

---

Unfortunately. in order to avoid throwing away too many of the original samples, the procedure in [BFKV96] needs to sacrifice the quality of the resulting anti-concentration bound. This reduced quality will result in an increased sample complexity of the resulting algorithm, in particular causing to scale polynomially with the bit complexity of the samples. The subsequent work [DV04) makes some quantitative improvements to the "outlier removal" procedure, however the final anti- concentration quality still has polynomial dependence on the bit complexity of the inputs, which is then passed on to the sample complexity of the resulting algorithm. What is worse is that (DV04) prove a lower bound showing that any outlier removal algorithm must have a similar dependence on the bit complexity.
Our Approach The aforementioned lower bound of [V04]] shows that no combination of point removal and linear transformation can put the input points into approximate radial isotropic position without losing polynomial factors of the bit complexity in either the quality or the fraction of remaining points. However, there is another operation that we can apply to the data without affecting the underlying learning problem.
In particular, since we are dealing with homogeneous halfspaces (without loss of generality), the problem will be unaffected by replacing a sample point x with the point A x for any scaling factor A 0 (since sign(L (<x)) sign( x)) matter what L is). This gives another tool to leverage in our preprocessing step.
In particular, by applying an appropriate linear combination to our points, we can ensure that they are in isotropic position (i.e., having second-mone momeettt matrix (1/d) I2). Similarly, by rescaling individual points, we can ensure that our points are in radial position (i.e.. that | = 1 for all x). The question we need to ask is whether by applying some combination of these two operations, we can ensure that both of these conditions hold simultaneously. In other words, we would like to find an invertible linear transformation A such that after replacing each point x by the point Az/ Ax/l| (in order to make it unit-norm), the resulting points are in (approximate) isotropic position.
The problem of finding such transformations was studied in early work by Forster [Frr22 (see also (Bar98) who showed that it is possible to achieve under certain assumptions, including for example the natural setting where the points are drawn from a continuous distribution. Unfortunately, there are cases where appropriate linear transformations A do not exist. In particular, if there was some d/3 -3-dimensional subspace that contained half of the points, then after applying any such transformation to our dataset, this will still be the case, and thus there will be d/ 3/3-ddmmnsiooall subspace over which the trace of the covariance matrix is at least 1/2. Interestingly, Forster's ' work, the recent work [HKLM20) showed that this is the only thing that can go wrong. That is, a matrix exists unless there a k-dimensional subspace containing more than k/ é/d-fraction of the points.
a refinement of
Suppose that we end-up in the latter case. Then, by restricting our attention to only the points of this subspace (and a subspace of that, if necessary), we can always find a relatively large subset of our initial dataset so that after applying a combination of linear transformations and pointwise-rescaling. they can be put into radial isotropic position.
Of course, to take advantage of such transformation, one must be able to find it efficiently. While prior work [HM13 AKS20 has obtained algorithmic results for this problem, none appear to apply in quite the generality that we require. Our main algorithmic result is that such transformations exist and can be efficiently (approximately computed. We start with the following simple definition:
Definition 1.3. Given an inner product space V and an invertible linear transformation A V + V. we define the mapping FA (V((0)) - (V) (()) by fa(x) = Az/ |/zl|2.
We can now state our main algorithmic result (see Theorem 3.4 for a more detailed statement):
Theorem 1.4 (Algorithmic Generalized Forster Transform). There exists an algorithm that, given set S of points in Zd\(0) {0} of bit complexity most b and 6 > 0, runs in poly(n, d, b, log (1)) time and returns a subspace V TRd containing at least a linear transformation A V V such that [SNV Exesnv f fa(x)fa(x)) = (1/ dim(V)) Iv +
ddffaccinnnn of the points in S and
O()) where the error is in spectral norm.
By applying Theorem 1.4 iteratively to the points of S (S V), we obtain a decomposition of S into not too many subsets T, so that each I has Forster transform over the subspace which it spans.
4

---

1.2 Preliminaries
For n. E 2,, we denote [n] def {l....,n) n... We write E 2 F to denote that E 2 cF, where e > 0 is sufficiently large universal constant. For V - g and f Re + R. we use (f) for the characteristic function of f on V, i... (v(f) V + {0, 13 and (v( iff f(x) + 0, V.
For a vector I E IRS, and i E [d]. xa denotes the i-th coordinate of z, and | def EE x?)1 denotes the by 22-norm of z. We will use 2 y for the inner product between y. E RR., For (linear) subspace V C RRd we use (V) to denote its dimension. For a set S C RR span(S) will denote its linear span. For matrix A Rddd we use ||Al|2 for its spectral norm and tr( for its trace. For A, B E Raxd we use A = B for the Loewner order, indicating that A - B is positive semidefinite (PSD). We denote by Ia the d x d identity matrix and by Iv the identity matrix on subspace V.
We use E for the expectation of X and Pr[E] for the probability of event &. For finite set S, we will use x mu S to denote that x drawn uniformly at random from S.
2 Algorithmic Forster Decomposition: Proof of Theorem 1.4
Given a distribution X on Rd, our goal is to transform X so that the transformed distribution has good anti-concentration properties. Specifically, we would like it to the case that for any direction there is non-trivial probability that Jv. X is at least a constant multiple of E[[v- X It is easy to see that this condition can be achieved as long as no particular value in the support of X contributes too much to E V x] In particular, it suffices that there exists some constant B > 0 such that Iu x|2 < B El e- x|] for all vectors v and all æ in the support of X. If this holds, it is easy to see that with at least ((1/B) B) probability randomly chosen ~ X satisfies lo x1² > Ello X x/2//2.
Unfortunately, a given distribution X may not have this desired property. However, seems in principle possible that one can modify X so that it satisfies this property. In particular, for any given weighting function : Rd + I... we can replace the distribution ~ X with the distribution c(x)x without affecting our linear classifier. Intuitively, by scaling down the outliers, we might hope that this kind of scaling would have the desired properties. This naturally leads us to a number of questions to be addressed:
1. How do we know that such a weighting function exists?
2. If such function exists, (how) can efficiently compute function c, even for discrete distribution X?
3. If X has continuous support, how can we find a function e that works for X, given access to a small set of i..dd samples?
To address these questions, it will be useful understand the second moment (autocorrelation) matrix of the transformed random variable c(X)X, i.e., Σ = (((c(X)))<(X))))) Observe that our desired condition boils down to je- c(x)x12 < Bv Ev, or equivalently
c(x) S B inf V /(TT ((TEo)//E x/2 o/0
(1)
for all points x in the support of X. We note that this setup forces us to strike a balance between c(x) being large and c(x) being small. On the one hand, if c(x) is too large, will violate Equation (T.. On the other hand, if c(x) is too small, the expectation of of (xX)xX" X will fail to add up to Σ. However, it is easy see that making Σ larger never to our detriment; that is, given Σ, we might as well take e(z) so that equality holds in Equation (I)
An additional technical difficulty here is related to the infimum term in Equation I This issue is somewhat simplified by making a change of variables so that the transformed autocorrelation matrix becomes equal to the identity, i.e., Σ = T. In this case, Equation ① reduces the condition c(x) S B /||//|/,, for x in the support of X. Changing variables back, we can see that the original equation is equivalent to c(x) < B/ [[[_E=//2zz) 1/2r:lp; however, making the change of variables explicitly will make it easier to relate this problem existing work on Forster's theorem (For02).
If we find a linear transformation A such that the matrix Σn := (XIA(XXAxxX))) satisfies Ea 2 (L/B) I, then since each value of fx(X) is unit vector, the distribution fx(X will satisfy
5

---

our anti-concentration condition. Also observe that since (r(Ea) = 1, we cannot expect the parameter B > 0 to be smaller than dim(V). Moreover, even this may not be possible in general. In particular, if a large fraction of the points in the support of X lie on some proper subspace W, most of the mass of (x(X will lie in the subspace AW. Therefore, the trace of ΣA along this subspace will be more than (im(W)/ (V), forcing some of the other eigenvalues to be smaller than 1/ dim (V).
Interestingly, Forster [For02] showed that unless many points of X have these kinds of linear dependencies, then a linear transformation A with the desired properties always exists. This condition was refined in a recent work [HKLM20] who proved the following existence theorem.
Theorem 2.1 (Generalized Forster Transform). Let X be a distribution with finite support on an inner product space V. Then, unless there is a proper subspace W of V so that Pr(X
W| 2 dim(W)/ dim((), there exists an invertible linear transformation A : V + V such that Ey (1/ (//diiV)) I.
Theorem 1.4 is an algorithmic version of the above theorem. The proof has two main ingredients. We start by handling the case of rescaling points rather than finding a linear transformation. It turns out that handling this case is quite simple, shown in the following result.
Proposition 2.2. There is an algorithm that, given a set S of n points in zd each of bit complexity at most b, lying in a subspace V C R.a. and a parameter ò >> O, runs in poly(n, d, b, log(1 time and, unless there is a proper subspace W C V containing at least a dim(W) dim (V) V-rrcttion of the points in S, returns weight function C S - .R.t such that for every E S we have that
di) Σ 22(vv""
(x))
(2)
n1
WEB
Moreover, the function 6² takes integral values of bit complexity poly (n, d, b, log(1/))).
Proof. We start by showing that such a weight function e exists. By Theorem 2.1 under the given condition on subspaces. there must exist an invertible linear transformation A
V such that (L/n) yEe fA (v) (z))" = (1/ (imm(V) Iv. This means that for any E V and x E S, we have Rearranging, this implies that LATT w- (c=|||xx||2) s (dim(V)/n) Σ |AT w. (v/l)A/laa)?" WES
that [ (Az/ | < (dim(V)/n) m) Eves ww (Ay/llAylia)
Thus, letting c(z) 1/|l/ causes our desired Equation 2 hold for all vectors AT w. Since A is invertible, this covers all vectors in V. Moreover. since all points in S lie in V, that is sufficient to check in order to ensure that we satisfy Equation (2) in general.
We will show that we can efficiently compute values c(x) > 0 for each x E 5, such that Equation (2) holds. We note that this is just a semidefinite program (SDP) in the variables (x)). The constraints can be written as: c² (xx))= 3 (dim (V)/n) Eyes (v)Dv"", for all x E S, and the positivity constraint can be written c(z)² 2 1 for all E S. It remains to argue that the above SDP can be solved efficiently in time poly(n, d, b, (1))), after relaxing the constraints by å as in the theorem statement, via the Ellipsoid algorithm. This argument is somewhat technical and is deferred to the supplementary material.
It remains to handle the case when proper subspace W exists. We show that one can identify such a subspace efficiently.
Proposition 2.3. There is a polynomial-timg algorithm that, given a set S of n points in zd of bit complexity all lying in a subspace VC Rd, determines whether or not there exists a proper subspace W C V containing at least a dim(WW) -fraftctioonn of the points in S, and if so returns such subspace.
CR4, V sSan(S), and k: = dim(V). We will first show that if n is multiple of ks we can efficiently find a "heavy" subspace W of dimension x- = dim(W), i.e., one with at least & x + 1 points, if one exists. To achieve this, we set up the following feasibility linear program (L.P,, with variable n; E [0. 1] for every point 2.((), We require that for any subset S" S of l linearly independent vectors the following linear inequality is satisfied
Proof. Let S - -2
n
Σ
Σ 2/ +1 BEES'
(3)

---

Efficient Computation We note that even though there are exponentially many constraints, the above LP can be solved efficiently via the Ellipsoid algorithm. To show this, we provide a separation oracle that given any guess WE [0, 1j" efficiently identifies violating constraint. In more detail, given any vector v, the linear independent basis B that maximizes the RHS of (3) can be efficiently computed by greedy algorithm. Starting from the empty set, we repeatedly add one point at time, at each step choosing a point 21()) of maximum V/ among the elements whose addition would preserve the independence of the augmented set. The greedy algorithm correctly identifies a basis of maximum weight, as the family of linearly independent subsets of points forms a matroid.
Feasibility We now show that the above LP will be feasible if and only if there exists a heavy subspace W. We start with the forward direction, i.c., assume the existence of heavy subspace W. In this case, setting = 1 if x0)) E W and = 0 otherwise, we can see that all constraints of the LP are satisfied:
The LHS of 3 is always at least # + 1, since there at least these many points the subspace W.
The RHS of is at most F + 1, as one can pick at most is points (+) with corresponding values 1.
For the reverse direction, if the LP is feasible and we can find a feasible vector v, we can efficiently identify heavy subspace W. To do this we proceed as follows: Assume w.l.o.g. that 01 2 0/ 2 ... on. Run the greedy algorithm described above find the basis B with points 2,(+), (f2)) (64)) where 1 = i1 < ig < < is. that maximizes the RHS of (3) Then, we find some A such that Rx+1 Fx + 1. As will soon show, such x. must always exist. Having such means that the first * + 1 points lie in x-dimennional subspace W, since otherwise the greedy algorithm would have picked the (x 1)-th point in the basis earlier in the sequence.
We now argue by contradiction that some K E [0, k - 1] such that ix+1 > 1 K + 1 must always exist. Indeed, suppose that for all ix+1 I c K + 1. Then, we have that
Ej Ug
Viuti 2 u2x+1
n/k
Summing the above, over all x E 10 h: 1]. we get that
Σ42 Σ U/3
B
which leads to the desired contradiction contradiction, as this implies that is infeasible.
In summary, we have shown that when n is a multiple of k, we can find a "heavy" subspace W of dimension were hoping for, which was to find a subspace with at least " points. We can address this issue by running our algorithm on a modified point-set after replacing one point outside the subspace of interest with one inside to increase the number of inliers by 1. Even though we do not know which pair of points change, we can run the algorithm for all pairs of points until solution is found. We can also handle the general case where n is not multiple of k. by making k copies of every point and running the algorithm above.
dim(W) with at least Fx + points. This is off-by-one by the guarantee
We are now ready prove Theorem 1.4
Proof of Theorem 1.4 The algorithm begins by iteratively applying the algorithm from Proposition
2.3 until it finds a subspace V containing at least a k/ ddfractioon of the points in S, such that no proper subspace W V contains at least a dim(w) (immVV-ffactton of the points in S V.
We then apply the scaling algorithm of Proposition 2.2 to find a weight function c: Snv + R², and consider the matrix
1/2
A
Σ ZESHV
7

---

We note that Equation now reduces to the following
(x))| x1² (dim(V) + 6)|1 1|
for all vectors w. Setting w = A²x, we obtain
(1) - (V) + 0)|1Ax|1
which gives
(1)) 5 dim(V) +
|Axx
On the other hand, we have that
dim V) + E fA(x)SA(x)²)
lv SNV
Σ (Ac))
snS
zESRIV
zESNIV
By the above inequality, it follows that all eigenvalues A....., Adim(V) of the matrix [SnV Exesnv fa(=)fa(x)) are at least dim(V)+5 However, since |snv] Σmesrv fa(x)fa(z)) has trace 1, we also have that E A= This means that the maximum eigenvalue of this ma- 1
1
1-6 trix is at most d Therefore, [snV] Ezesny (A()) is within (6)) of (1/ dim(V)) Iv in spectral norm. This completes the proof Theorem 1.4
The final ingredient that will be important for us is showing that if we can find a subspace V and linear transformation A (as specified in the statement of Theorem 1.4) that works for sufficiently large set of i..d. samples from the distribution X, then the same transtorm will work nearly as well for X. This is established the following proposition.
Proposition 2.4. Let X be any distribution on IR \ {0} and S be multiset of 2 dle²² i.i.d. samples from X. Then with high probability over the choice of S the following holds: For every subspace V of IRd, every invertible linear transformation A V + V, and any unit vector V, we have that:
1. |SnVI/IS = Pr|X E VJ O(e).
2. (1/ISI) ExEshv ww- fa(2)] + O(c).
Proof. The proof by a simple application of the VC inequality (see, e-g.. (LO1 stated below.
Fact 2.5 (VC Inequality). Let F be class of Boolean functions with finite VC dimension VC(F) and let a probability distribution D over the domain of these functions. For a set S of n independent samples from D, we have that
VC(F) n
log(1/T)
sup [Prx=s[((X) -Prx- fEF
with probability at least 1 1-7
Item I follows directly by noting that the set of vector subspaces of Idd has VC-dimension d. Item follows from the fact that the collection of sets
Fv.A, {x V ww fx(x) 2 t}
has VC-dimension O(d)). This holds for the following reason: A set of this form is the intersection of the subspace V (which comes from class of VC-dimension at most d), with the set of points such that the quadratic polynomial (w- (Az))² 2 threshold functions is class of VC-dimension ((d)). Therefore, by the VC inequaaitt, with high probability, for each such F we have that the fraction of S in F is within O(e) of the probability that a random element of X lies in F. The claim now follows by noting that for a distribution Y (either X or the uniform distribution over S) we have that
Ax] is non neg-negaeive Recall that the space of
[' t=
E\lv(Y) [A(Y)
Pr(Y E Fv.A.w:ldl.
This completes the proof of Proposition 2.4
8

---

3 Application: Learning Halfspaces with Massart Noise
In this section, we show how to apply the machinery of Forster decompositions from Section 2 to PAC learn halfspacces with Massart noise. Specifically, we will show how to adapt the algorithm of [DGT19] by appropriately transforming the set of points it run on, to obtain a new algorithm with strongly polynomial sample complexity guarantees.
To that end, we will need the definition of outlier and a partial classifier:
Definition 3.1. (T--Outlier A point x in the support of a distribution X over a vector-space V is called a -outlier, r > O, if there exists a vector v & V such that |v æ|| > r Elju x
Definition 3.2. (Partial Classifier) A partial classifier is function h IRd {-1, * 1). It can be thought of as acting as a classifier that for some input values returns an output in [+1], and for the remaining values returns *, as way of saying "I don't 't know".
A key step of the algorithm in DGT19 for learning halfspaces with Massart noise, is computing a partial classifier that returns an output on a non-trivial fraction of inputs for which its error rate is at most 7) + c. The sample complexity and moning-ttme of this algorithm depends polynomially on the size of the largest outlier in the distribution and the inverse of the accuracy parameter 1/c. More specifically, the following theorem is implicit in the work of [GGT19.
Theorem 3.3 (IDGTI9). Let V be vector space and (X, Y) a distribution over V x {=1), where X does not have any -oouliiess in its support. Suppose that there is a vector w and nj E (0, 1/2) such that for any given value x it holds Pr(Y- = sign( w x²) X 2] 2 1- n) In particular, Y is given by a homogeneous halfspace with at most 1) Massart noise. Then there exists an algorithm that, given nj I, and parameters é', 8' > O, draws poly(dim(V), runs in poople-polynomial time, and returns a partial classifier h on V such that with probability at least 1 8' the following holds: (i) Pr[l(X)= + +] //ppoyydii(( r, 1/ee, /l/////g(]]]))) 1og(1/8)), and (ii) Pr(M(X)= # Y I(X) + *] < 6'.
l/c(/oog(//8)) samples from (X, Y).
The main idea behind obtaining efficient algorithm with strongly polynomial sample complex- ity is to repeatedly apply the Forster decomposition theorem from Section to ensure that no large outliers exist a "heavy" subspace. Then, using Theorem 3.3 we can identify a partial classifier that has small misclassification error on a non-trivial fraction of the probability mass for which it outputs {+1} prediction. By recursing on the remaining probability mass, we can ensure that we accurately predict the label for nearly all the distribution of points. This yields a misclassification error of at most 7) + in the entire space.
The following theorem summarizes the main algorithmic learning result of this paper.
Theorem 3.4 (Main Learning Result). Let (X,Y) distribution over Rd x {+1}, where Y is given by a homogeneous halfspace in X with at most n < 1/2 rate of Massart noise, and where the elements in the support of X are all integers with bit complexity at most b. For parameters 6,8 > 0, there exists an algorithm that draws poly(d, (d, 1/e, log(1/6)) samples from (X, Y),, runs in poly(d, b, /ee log(1/8) time, and with probability at least 1 8 returns a classifier h RR. - {+1} with misclassification error at most n) +
Proof. In order to analyze Algorithm [ we will say that an event happens with "high probability" if happens with probability at least 1 8/ poly (d log(1, /e) for a sufficiently high degree polynomial. There are a number of events each iteration of our while loop that we will want to show happen with high probability, and we will later claim that if they do for each iteration of the loop, then our algorithm will return an appropriate answer after (d poly(dlog(1) (lg((//)/e) iterations of the while loop. This will imply that with probability at least 1 - 8 all high probability events occur and that our algorithm will return an appropriate answer.
We start by noting that with high probability the sample set chosen in the check of the while statement approximates the true probability that h₂ = * to additive error at most c/6. This means that, with high probability, (1) we will not break out of the while loop unless this probability is less than e/2, and that (2) while we are in the while loop, l((X) = * with probability at least e/6. This latter statement implies that the expected number of samples from (X, Y) needed in order to find one with h(X)= = * is O()/e). Assuming this holds, the set S in the next line can be found with high probability by taking a polynomial number of samples from the original distribution.

---

Line 6 runs in deterministic poly(db (ol//dolog((////// time and, by Proposition 2.4 2.4 with high proba- bility finds pair A such that:
1. Pr[X E E (x(x) x
2. E(fa(X)fa(X)) E (X) = (1/(4dim(V)) Iv.
If Condition | holds, then with high probability only polynomially many samples from (X, Y) are needed to run the algorithm in Line 7 If Condition holds. then the conditional distribution has no (4 dim V) -ouulierss Since (fa(X) Y) is linear classifier with Massart noise with high probability we have that (r(g(fa(X)) #
E V. h (X) + +) (/poly(dlog(1//)/e and Pr (X)) # Y (x) +, V. * 17 c/2.
The former statement implies along with Condition 1that
Pr(h++ # * (xx = *] > (00))ddoog((0//44
and the latter implies that
Pr[het (X) | (X) ++ max(n+ + (r +))
If the above hold for every iteration of the while loop, then after T = poly (d log( 1/0)/e) iterations, we will have that Pr[hT (X) = *] < e/6 (and thus with high probability we will break out of the loop in the next iteration), and when we do break out, it holds that
(X) Y < (X) # Y (X) * + Pr(A(()) = = s ( c/2) (e/2) = =
This completes the proof of Theorem 3.4
Algorithm 1 Learning Algorithm for Massart Halfspaces
1: Let C be sufficiently large universal constant.
2: Let ho IRd {-1,*, *, 1} always return 8.
3: Let =
4: while Se....//,,46 = *| > e/3 for a random sample of C'log(de/0)/ points (X,Y) do
5: Let S be set of Cdt log(1/6) samples from X conditioned on (x()
6:
Run the algorithm from Theorem I.4 on to find subspace V and linear transformation
A: V + V with Eev,,nv (f [=)
(x) (1/(2 dim(V)) Iv.
7: Obtain a partial classifier by running the algorithm from Theorem 3.3 with:
8' b/p0/y/dlog(1//)//) d'= and r= 4
the distribution (X)( Y) over all (X, (X,Y) conditioned on X E V and h; 8: Define a new partial classifier
[(([(()))
if h. = and x E V (1(x)) otherwise
hx+1(x)=
9: Set i 1.
10: Return the classifier hi.
10

---

References
[ABHU15] P. Awasthi, M. F. Balcan, N. Haghtalab, and R. Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, pages 167-190, 2015.
[ABHZI6] P. Awasthi, M. F. Balcan, N. Haghtalab, and H. Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, pages 152-192, 2016.
[AKS20] S. Artstein-Avidan, H. Kaplan, and M. Sharir. On radial isotropic position: Theory and algorithms. CoRR, abs/2005.0491 2020.
[Bar98] F. Barthe. On reverse form of the brascamp-lieb inequality. Inventiones mathematicae, 134:335- 361, 1998.
[BFKV96] A. Blum, A. M. Frieze, Kannan, and S. Vempala. A polynomial- timommmilltimee algorithm for learning noisy linear threshold functions. In 37th Anmual Symposium on Foundations of Computer Science, FOCS '96, pages 330-338, 1996.
[Blu03] Blum. Machine learning: My favorite results, directions, and open problems. In 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 1 11-14, 2003.
[BZ17] M.-F. Balcan and H. Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. In Advances in Neural Information Processing Systems, pages 4796-4805, 2017.
[CKMY20) S. Chen, F. Koehler, A. Moitra, and M. Yau. Classification under misspecification: Half- spaces, generalized linear models, and evolvability. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[Coh97] E. Cohen. Learning noisy perceptrons by perceptron in polynomial time. In Pro- ceedings of the Thirty-Eighth Symposium on Foundations of Computer Science, pages 514-521, 1997.
[Dan16] A. Daniely. Complexity theoretic limitations learning halfspaces. In Proceedings of the 48th Annual Symposium on Theory of Computing, STOC 2016, pages 105-117, 2016.
[DGT19] I. Diakonikolas, T. Gouleakis, and C. Tzamos. Distribution-indepennl PAC learning of halfspaces with massart noise. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 4751-4762, 2019.
[DIK+21] I. Diakonikolas, R. Impagliazzo, D. Kane, R. Lei, J. Sorrell, and C. Tzamos. Boosting in the presence of massart noise. CoRR, fiss/2006.07779 2021.
[DK20] I. Diakonikolas and D. M. Kane. Hardness of learning halfspaces with massart noise. CoRR, abs/2012.09720, 2020.
[DKTZ20] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 1486-1513. PMLR, 2020.
[DL01] L. Devroye and G. Lugosi. Combinatorial methods in density estimation. Springer Series in Statisties, Springer, 2001.
[DV04] J. Dunagan and S. Vempala. Optimal outlier removal in high-dimensional spaces. J. Computer & System Sciences, 68(2):335-373, 2004.
[FGKP06] V. Feldman, P. Gopalan, Khot, and A. Ponnuswami. New results for learning noisy parities and halfspaces. In Proc. FOCS, pages 563-576, 2006.

---

[For02] J. Forster. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci., 65(4):612 625, 2002.
[FS97] Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1): 1997.
[GR06] V. Guruswami and Raghavendra. Hardness of learning halfspaces with noise. In Proc. 47th IEEE Symposium Foundations of Computer Science (FOCS), pages 543-552. IEEE Computer Society, 2006.
[HKLM20] M. Hopkins, D. Kane, S. Lovett, and G. Mahajan. Point location and active learning: Learning halfspaces almost optimally. In 6/st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 1034-1044. IEEE, 2020.
[НM13] M. Hardt and A. Moitra. Algorithms and hardness for robust subspace recovery. In COLT 2013, pages 354-375, 2013.
[MN06] P. Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326- 2366, 10 2006.
[MP68] M. Minsky and S. Papert. Perceptrons: an introduction to computational geometry. MIT Press, Cambridge, MA, 1968.
[MT94] W. Maass and G. Turan. How fast can threshold gate learn? In S. Hanson, G. Drastal, and R. Rivest, editors, Computational Learning Theory and Natural Learning Systems, pages 381-414. MIT Press, 1994.
[Nov62] A. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium Mathematical Theory of Automata, volume XII, pages 615-622 1962.
[Ros58] F. Rosenblatt. The Perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65:386-407, 1958.
[RS94] R. Rivest and R. Sloan. A formal model of hierarchical concept learning, Information and Computation, 114(1):88-114, 1994.
[Slo88] R. H. Sloan. Types of noise in data for concept learning. In Proceedings of the First Annual Workshop on Computational Learning Theory, COLT '88, pages 91-96, San Francisco, CA, USA. 1988. Morgan Kaufmann Publishers Inc.
[Slo92] H. Sloan. Corrigendum to types of noise in data for concept learning. Proceedings of the Fifth Anmual ACM Conference on Compulational Learning Theory, COLT 1992, page 450, 1992.
[Slo96] R. H. Sloan. Pac Learning, Noise, and Geometry, pages 21-41. Birkhäuser Boston, Boston, MA, 1996.
[Va184] L. G. Valiant. A theory of the learnable. In Proc. 16th Anmual ACM Symposium Theory of Computing (STOC), pages 436-445, ACM Press, 1984.
[Vap82] V. Vapnik. Estimation of Dependences Based Empirical Data: Springer Seriex in Statistics. Springer- Verlag, Berlin, Heidelberg, 1982.
[Vap98] V. Vapnik. Statistical Learning Theory. Wiley-Interscience,, New York, 1998.
[YZ17] S. Yan and C. Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Information P Processing Systems 2017, pages 1056-1066, 2017.
[71.2]] Zhang and Y. Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. CoRR, abs/2102.05312, 2021. 2021.
12

---

[ZLC17] Y. Zhang, P. Liang, and M. Charikar. A hitting time analysis of stochastic gradient langevin dynamics. Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 1980-2022, 2017.
[ZSA20] C. Zhang, J. Shen, and P. Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
13


Reviews:
[{"review_id": "Rn0kZU4HJtC", "reviewer": "Reviewer_AuTG", "summary": "This paper studies the problem of learning halfspaces under Massart noise in the absence of distributional assumptions on the x's. Previous works have given algorithms for this problem which achieve error eta + eps in time and sample complexity polynomial in d, 1/eps, and the bit complexity b of the x's. Removing the dependence on bit complexity in the runtime for the closely related problem of linear programming is a major open question, but more modestly one could hope to remove this dependence in the sample complexity, and this is the main result of this paper, which it achieves using a modification of the improper learner from [DGT19].\n\nThe main bottleneck that leads to the b dependence in previous algorithms is a preprocessing step due to Dunagan-Vempala that essentially reduces to the large margin case by removing some outliers so that no point among the remaining points S is far from S in Mahalanobis. The present work circumvents this as follows. For the preprocessing step, instead of outlier removal, one could also just try placing the dataset in approximate radial isotropic position. This is a technique that has been useful in a variety of other applications like subspace recovery, the Paulsen problem, communication complexity, etc. \n\nUnfortunately, not every dataset can be placed in radial isotropic position, for instance if some m-dimensional subspace is \"heavy\" in the sense that it contains more than an m/d fraction of the points. As shown in [HKLM20], this is the only obstruction, and the main contribution of the present work is to make this fact algorithmic, i.e. to give an algorithm for finding a heavy subspace such that the part of the dataset in that subspace can be placed in radial isotropic position.\n\nThen to get the application to learning under Massart noise, whenever one needs to run the outlier removal step, just use the above algorithmic result to identify a heavy subspace, place those points in radial isotropic position, and run one step of the algorithm for learning large-margin halfspaces under Massart noise on those points to make progress.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "If I understand correctly, the new ideas in this paper are the following. First is identifying the connection between radial isotropic position (more specifically the structural result in [HKLM20]) and preprocessing algorithms like Dunagan-Vempala for learning halfspaces without margin.\n\nThe second is the following observation about [HKLM20]. For context, the [HKLM20] paper was non-constructive in the sense that for the \"hard\" direction (failure of a dataset to be placed in radial isotropic position implies existence of a hard subspace), they invoked Barthe's theorem, together with separating hyperplane theorem, to conclude that the LP in eq. 3 of the submission is feasible. From there, [HKLM20] showed how to identify a heavy subspace from a feasible point using essentially the same argument as in lines 281-288 of the submission. The main innovation, in Proposition 2.3, is to realize that this latter part of the argument in [HKLM20] yields an efficient algorithm for identifying heavy subspaces/certifying none exist. \n\nOnce you have this, you can find a heavy subspace W with no heavy subspaces of its own (which the authors do in Lines 298-300). At this point though, couldn't you also just run the algorithm of Hardt-Moitra to put the points in W in radial isotropic position, because you're guaranteed by [HKLM20] that such a transformation exists? I'm not sure if Proposition 2.2 or Lines 300-305 are needed, but perhaps I'm missing something.\n\nOverall, I think the application of Theorem 1.4 to learning halfspaces under Massart noise is a nice observation. In terms of Theorem 1.4 however, I would regard the main contribution of that result as primarily synthesizing existing ideas (in a clever way). This is not necessarily a weakness, but I think the submission could be strengthened if the authors spelled out more clearly where the ideas in the proof of their main Theorem 1.4 come from and, e.g., clarified the connection to Hardt-Moitra.\n\nMinor typos:\nLine 210: should be Bv^T \\cdot \\Sigma v\nLines 211-215 \"if c(x) is too small, the expectation of c(X)^2XX^T will fail to add up to Sigma\" -> this was a bit hard to parse because Sigma is defined in terms of c(x)\nLine 283: x^{(i_d)} should be x^{(i_k)}\nLine 288: contradiction -contradiction-\nDisplay above Line 288: \\sum_{x_i\\in \\mathcal{B}} instead of \\sum_{x_i\\in B}", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, this work does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Fz5J9Hv-jV_", "reviewer": "Reviewer_UuHj", "summary": "This paper studies the problem of finding a Forster transformation of a given distribution. The goal of a Foster transform is to transform an arbitrary distribution into a distribution that has good anti-concentration properties: in particular, one would like the transformed distribution to have its second moment matrix equal to a scaled identity matrix and the points from the distribution should also have Euclidean norm 1. For this problem, they give an algorithm that runs in weakly polynomial time. The algorithm itself uses the ellipsoid algorithm to solve SDPs and LPs.\n\nAs an application of their algorithm for finding Forster transforms, they consider the problem of PAC learning halfspaces under Massart noise. They show that there is an algorithm whose sample complexity is strongly polynomial and running time is weakly polynomial. Previously, the work of Diakonikolas et al. showed that there is an algorithm whose sample complexity and running are both weakly polynomial whereas, information-theoretically, it is known that the sample complexity can be strongly polynomial. So the present paper closes this gap up to polynomial factors.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\nThe results in this paper are certainly novel and is an important improvement over prior works. The techniques are nice and I am not aware of other works which make use of Forster transformations. The techniques may also warrant further study and see where it may also be applicable.\n\n**Quality**\nThe submission is technically sound as far as I can tell although I did not carefully verify any of the arguments. All the claims have been justified either in the main body or in the appendix.\n\n**Clarity**\nThe paper is written quite well. There are quite a few ideas in the paper including the various aspects of the Forster transform and its application to PAC learning halfspaces with Massart noise. However, the authors did a pretty decent job explaining their approach.\n\n**Significance**\nThe results are quite nice and make a significant contribution to the literature on learning under Massart noise. Previously, a strongly polynomial sample complexity was known but only information theoretically and this paper makes it (weakly) algorithmic. They also point out that obtaining a (strongly) polynomial time algorithm for the problem would also result in a strongly polynomial time algorithm for linear programming.\n\nThe results in the paper may be of interest to researchers working in learning theory and, in particular, researchers that are working on robust PAC learning algorithms. The techniques are also very nice and may also interest other researchers working in the area.\n\n**Other comments**\nI would appreciate if the authors compared the actual sample complexity. In particular, what are the lower bounds, what they achieve, and perhaps compare this to previous works.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "35t8aNABfI", "reviewer": "Reviewer_3GRx", "summary": "This paper presents an algorithm to compute a certain decomposition of a point set known as a Forster decomposition. Roughly speaking this guarantees \n1. mean 0 and  close identity covariance\n2. all points with norm close to one.\nEach of these conditions is easy to achieve (via PCA and rescaling respectively),  the challenge is getting them to hold simultaneously.\nThe kind of mapping they seeks is an invertiable linear transformation followed by rescaling. \n\nWhile such a mapping may not always exist, it was known that the only \"obstructions\" are dense subspaces (in the extreme think of the same point repeated many times). The main algorithm in this paper allows one to find these obstructions efficiently. One can then iteratively  remove these points and keep going. This gives a decomposition into O(d) many subspaces and a good mapping for the points within each subspace.\n\nThe main application of this result is a learning algorithm for halfspaces in the Massart noise model whose sample complexity is independent of the bit-length of the inputs. The running time still depends polynomially on the bit lengths (inevitable by a reduction from LP). They key idea is that the mapping they use preserves the existance of a good homogenous halfspace classifier.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Pros:**\n1. The result is technically strong, probably among the top theory papers submitted in this axis. The Forster decomposition it computes seems like a natural object that might be used elsewhere. The idea that on can always rescale for homogenous halfspaces is simple and nice. \n\n2. It gives an improvement in the sample complexity for learning halfspaces with Massart noise, getting rid of the bit-size dependence. \n\n**Cons:**\n1. The result is rather technical and narrowly focused. I am not sure how many people who weren't working on this problem were aware of the dependence of the sample complexity on bit size in the previous work.  This will be exciting to the experts in the area, but I have a hard time imaging a broader audience. It is not the kind of theory result that I would want the broader ML community to hear about, which in my opinion makes it a better fit for a more theory-focused venue like STOC/FOCS/COLT. Having said that, I know NeurIPS aims to have a broad tent, so perhaps the PC would like to make room for a few more narrowly focused papers. \n\n2. The quality of writing leaves a lot to be desired. The high level explanations are ok, but the choice of notation and technical writing seems rather hurried. See some concrete suggestions below:\n\n- Using $\\sigma$ for number of standard deviations is a strange choice with potential for confusion.\n- The definition of radial position reads as though we want $E[xx^T] = I/d$ for every point $x$. You should separate  out the conditions that are needed in expectation from those that must hold pointwise.\n- In the statement of Theorem 1.4, do you need any non-trivial lower bound on $dim(V)$? Or would $dim(V) =1$ be fine? I suspect it is the latter, but you should make this explicit. \n- The paper points  to Theorem 3.4 for a detailed statement of 1.4. But Theorem 3.4 talks about the learning application. \n- I would have liked to see a Theorem statement where you unwind the recursive use of 1.4 and state the decomposition of the original point set into subspaces.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Given the very abstract nature of the problem they are addressing, I don't think there is much to say. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "1-3PJZIrJyO", "reviewer": "Reviewer_rK8U", "summary": "This paper shows that any distribution can be decomposed into a number of disjoint distributions, each admitting a Forster transform, which has anti-concentration properties. An application of this decomposition is to learning halfspaces in the Massart noice model.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Underlying the algorithms in this paper is a line of work wherein many points are guaranteed to be far from the separating hyperplane. Without knowledge of the true separator, this can still be ensured by alinear transform which ensures some bound on the expectation of dot products, while their absolute values are still bounded. While previous approaches used a combination of linear transforms and removal of bad points, the approach here is slightly different: joining a linear transform and a scaling step, resulting in the points being approximate in a radial isotropic formation. This transformation can be computed, and applied iteratively to the point set in order to ensure that many points are far from the final separating hyperplane.\n\nA central step in the proof gives an LP, which can be solved efficiently using the ellipsoid method. This gives a dependence on the bit precision in runtime (as observed to sample complexity), but is likely unavoidable.\n\nI found this paper to be an enjoyable and interesting read, as well as mathematically challenging. My reservations are based on the application, that is eliminating sample complexity dependence on bit precision within a very specific noise model. This seems to be a lot of work to achieve a relatively minor improvement. Are there other applications for these techniques?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes Forster decomposition, a new analysis tool for learning linear classifiers and applies it to derive an algorithm that learns halfspaces with Massart noise without the dependence on bit complexity (which was necessary for previous algorithms). The contributions is very strong technically and addresses one of the classical problems in ML. While it has downsides, such as being technically rather complex and likely to be fully appreciated by a handful of experts, I recommend acceptance.
Decision: Accept (Spotlight)