Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

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

I 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?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents an algorithm to compute a certain decomposition of a point set known as a Forster decomposition. Roughly speaking this guarantees 
1. mean 0 and  close identity covariance
2. all points with norm close to one.
Each of these conditions is easy to achieve (via PCA and rescaling respectively),  the challenge is getting them to hold simultaneously.
The kind of mapping they seeks is an invertiable linear transformation followed by rescaling. 

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

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

main_review: **Pros:**
1. 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. 

2. It gives an improvement in the sample complexity for learning halfspaces with Massart noise, getting rid of the bit-size dependence. 

**Cons:**
1. 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. 

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

- Using $\sigma$ for number of standard deviations is a strange choice with potential for confusion.
- 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.
- 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. 
- The paper points  to Theorem 3.4 for a detailed statement of 1.4. But Theorem 3.4 talks about the learning application. 
- 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.




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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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].

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

Unfortunately, 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.

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

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

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

Overall, 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.

Minor typos:
Line 210: should be Bv^T \cdot \Sigma v
Lines 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)
Line 283: x^{(i_d)} should be x^{(i_k)}
Line 288: contradiction -contradiction-
Display above Line 288: \sum_{x_i\in \mathcal{B}} instead of \sum_{x_i\in B}
limitations_and_societal_impact: Yes, this work does not have any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

As 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.
main_review: **Originality**
The 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.

**Quality**
The 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.

**Clarity**
The 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.

**Significance**
The 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.

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

**Other comments**
I 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.
limitations_and_societal_impact: Yes
review_title: null

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)