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-indeeeneenn
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 iistributionnspeciiff 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 poolydd)-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/ |/z||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 characteristic function of f on V, i... (v(f) V + {0, 13 and (v( iff f(x) + 0, V.
R. we use (f) for the
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,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 LATw: w- (c=|||xx|22) s (dim(V)/n) Σ |AT w. (v/l)A/laa)?" WES
that [ (Az/ | < (dim(V)/n) m) Eyes 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
Victi 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) (dmmVV-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) + Σ (Ac))
lv SNV
E fA(x)SA(x)²)
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 inequaaity, 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=
B\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, 1/ /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) 2
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)0
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/po/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- timommmilltimeee 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": "iBPRJaAxDkP", "reviewer": "Reviewer_91N9", "summary": "This paper provides an algorithm that can efficiently decompose a distribution into a disjoint mixture of a few distributions for which Forster transforms exist and can be computed efficiently. They then use this to obtain the first polynomial-time algorithm for distribution independent PAC learning of halfspaces in the Massart noise model. This is the first algorithm to actually obtain a result that scales independent of the bit complexity of the examples. \n\nThe authors demonstrate that it is either possible to find a transformation c(x) such that while the distribution on the x's itself might not be transformable via a Forster transform, c(x) x is; or to identify a subspace W of V (the space in which the x's exist) which contains more than a dim(W)/dim(V) fraction of the samples. In the latter case, one can then focus on the subspace and then rescale appropriately within the subspace. \n\nTo solve the problem of learning halfspaces with Massart noise, the authors repeatedly apply the Forster decomposition theorem to ensure that no large outliers exist on a heavy subspace, and train partial classifiers at each step of the algorithmic transformation. \n", "questions": "", "limitations": "", "rating": 8, "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": "I find this result very interesting. I think it is clear, original as well as significant. I think the algorithmic version of the result from [HKLM20] is a very nice contribution. \n\nI have read the author response and I did not have any questions for the authors.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical result and of limited societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ar4Hq4RQfK", "reviewer": "Reviewer_48Ey", "summary": "This paper addresses the problem of distribution-independent improper learning of halfspaces under the Massart noise model. The prior work [DGT19], in a breakthrough, provided the first algorithm with time and samples $\\text{poly}(d, 1/\\epsilon, b)$ where $d$ is dimension, $\\epsilon$ is excess error (compared to the Massart noise bound $\\eta$), and $b$ is the bit complexity of the samples. The dependence of runtime on the bit complexity $b$ is necessary, barring a breakthrough in solving LPs, but the sample dependence on $b$ is information-theoretically unnecessary, leaving a statistical/computational gap. The main result of this paper is to close this gap, providing an algorithm with same time complexity as before, but sample complexity only $\\text{poly}(d, 1/\\epsilon)$.\n\nThe innovation of the current work which enables this result is an efficient algorithm for decomposing a set of points into subsets each of which has a Forster transform (a linear transformation such that if the points are rescaled to the unit sphere, the covariance is lower bounded by $1/\\text{poly}(d))$. Recent work [HKLM20] showed that every set of points either has lots of points lying in a subspace, or has a Forster transform. This work uses that result to provide polynomial-time algorithms both for finding a heavy subspace (if it exists) and finding the Forster transform (otherwise); applying these recursively yields the decomposition. Finally, the halfspace learning result follows by applying an algorithm from [DGT19] for learning halfspaces when the data has a large margin (more precisely, [DGT19] provides a partial learning algorithm, and the main algorithm recurses on the points which the partial learner doesn't label).", "questions": "", "limitations": "", "rating": 8, "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": "This work provides an improvement on the long-standing problem of learning halfspaces with semi-adversarial noise. The main idea is a simple synthesis of the results of [DGT19] and [HKLM20], but the execution is non-trivial; the authors claim that prior algorithms for finding Forster transforms and heavy subspaces do not apply in the needed generality. The technique of recursive Forster decomposition may have other applications in learning theory.\n\nThe paper is very clearly written and a pleasure to read.\n\nNOTES\n- Why do the results of [AKS20] and [HM13] not apply in the needed generality? Explaining this would clarify a main part of the novelty of the paper.\n- I appreciate the intuition about the Forster transform but I'm not sure why lines 208-221 are helpful. It seems to me that lines 222-223 are the crucial part and the rest is making it seem more complicated than it needs to be?", "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": "5"}, "extra_text": {}}, {"review_id": "am8tyQRbdbQ", "reviewer": "Reviewer_Nd9v", "summary": "The paper studies learning halfspaces with Massart noise. The main contribution is a new data preprocessing scheme that results in bit-independent sample complexity.", "questions": "", "limitations": "", "rating": 7, "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": "+ Authors clearly state the root of bit dependence in prior works which well motivates a new data preprocessing scheme.\n\n+ The intuition underlying the approach is clearly explained. In particular, the problem boils down to finding a linear transformation of the data such that each data point has unit norm and the covariance matrix is nearly identity.\n\nBelow are my concerns.\n\n- It was argued that Theorem 1.4 is more general than [AKS20]. Can you clarify the difference and why such algorithmic extension is crucial for the problem of interest?\n\n- Section 2 is hard to follow, especially for those not familiar with [For02].\n\n- Why does the running time still depend on the bit complexity?\n\n- Are there other applications of the improved Forster decomposition beyond learning halfspaces?", "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": "5"}, "extra_text": {}}, {"review_id": "W8ojEmQ5Zk8", "reviewer": "Reviewer_px8j", "summary": "The paper presents an algorithm for halfspace-learning with data supported on points with integer coordinates of bounded bit complexity under partially adversarial noise conditions. A related result in the literature is improved insofar as the sample complexity of the algorithm is shown to be independent of the bit complexity of the support.\nThe principal technical contribution is an iterative method of deconcentration of the data. ", "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": "The paper contains some interesting ideas, but I found it very hard to understand, partly because I am not an expert specializing on this subject, but mainly because the presentation is very unclear. \n\nThe assumption that the input marginal is concentrated on points with integral coordinates is hidden from the reader until page 4, and up to this point one remains bewildered by the frequent use of the term \"bit-complexity\". \n\nThe paper leans very heavily on the reference DGT19, without consultation of which it  would be nearly impossible to understand. \n\nThe same applies to the reference HKLM20, cited in Theorem 2.1. As given the citation is meaningless, because the transformation A, whose existence is asserted, does not appear in the conclusion. This may be a simple typo, but it makes it impossible to follow the proof of Proposition 2.2. After consultation of HKLM20 Proposition 2.2 becomes trivial.\n\nHalfspaces are denoted h on page one and f in Theorem 1.2, but then f is also used in the definition of the normalized transformations in Definition 1.3.\n\nThe proposed method depends crucially on the assumption that the halfspaces are homogeneous. In line 79 this is assumed \"without loss of generality\", \"since we are working in the distribution-independent setting\". Could this be explained a little more? How do you find a point on the separating hyperplane to be used as an origin?\n\nAnother important ingredient of the final algorithm is Theorem 3.3, attributed to DGT19. Where can we find it in DGT19?\n\nThe page limit is not to blame for the lack of clarity in the paper. The introduction could be a lot less verbose to make ample room for necessary definitions and explanations. \n\nPOST REBUTTAL\n----------------------\n\nThe authors addressed most of my concerns in a clear and satisfactory way, and I will raise my score accordingly. \nNevertheless I still believe that the presentation should be more transparent.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes a foundational advance following-up on the recent breakthrough on learning halfspaces with Massart noise. The algorithms of Diakonikolas, Gouleakis, Tzamos from 2019 learns halfspaces with Massart noise but due to an LP solving step (and the absence of a strongly polynomial algorithm for LP), runs in time and samples that grows polynomially in the bit complexity of the coefficients of the underlying halfspace. A polynomial dependence on bit complexity in running time is reasonable but one could hope for an algorithm where the sample complexity is independent of it. 

This paper cleverly uses (an algorithmic version) of Forster decomposition of points in order to resolve this question. The idea, in retrospect, is simple but elegant and (the algorithmic variant of Forster decomposition can potentially find new applications. We recommend acceptance.  
Decision: Accept (Spotlight)