Reliable Learning of Halfspaces under Gaussian Marginals

Summary

This paper studies the problem of agnostic reliable learning with Gaussian margin. It gives a novel algorithm with improved running time and sample complexity bound and this suggests that agnostic reliable learning is easier than agnostic learning. It also gives a Statistical Query lower bound matching some terms of the upper bound as an evidence that the upper bound is tight.

Strengths

1. The result of this paper is novel and complete. a. The running time and sample complexity of the proposed algorithm is a big improvement from the previous $d^{O(1/\epsilon^2)}$ and the algorithm is completely new. b. The algorithm, lower bound and analysis are all highly non-trivial and technically sophisticated, showing a deep understanding of the problem. I think there's lots of technical novelties in the paper. c. The fact that there's a separation between agnostic reliable learning and agnostic learning is interesting and it's a contribution to formally establish this. d. The paper gives a non-trivial SQ lower bound matching some terms of the upper bound, suggesting its tightness. 2. The writing of the paper is decent. Enough background knowledge is given. Math related parts is clearly defined and the proof is rigorous. The paper is organized and non-technical part is not hard to follow.

Weaknesses

1. There are some room for improvement in writing. a) As someone who is quite familiar with PAC and many classical learning problems but not familiar with reliable learning/learning Gaussian margin halfspaces, I find the introduction to the problem could be more clear, especially I think you can do a better job explaining the adversary's strategy and behavior, the "corrupt negative labels are free" part is worth more insights. b) I do find the paper really technical, but I think it is intrinsic. As someone who is not familiar with your algorithmic framework [DKK+22] and some technical parts (for example, the use of polynomials), I think more explanation could be helpful. c) Some parts of the writing could be more clear, like "with high probability" in the definition. 2. I do find the SQ lower bound a bit weak. It doesn't have a dependence on $\epsilon$, is there any known lower bounds on $\epsilon$? 3. The agnostic learning lower bound doesn't have a dependence on $\alpha$, but the agnostic reliable learning bound has such a dependence, why? You assumed that $\alpha$ is a constant, if it's not, is there any complications in your conclusion?

Questions

1. In this paper and some other papers, the lower bounds are SQ lower bounds. As far as I know, SQ lower bounds are weaker than PAC lower bounds (SQ learnable implies PAC learnable but not the other way around), is there some difficulty to get a PAC lower bound for the problem? 2. As far as I know, active learning doesn't seem to help with agnostic learning halfspaces (Gaussian margin, arbitrary noise), could it improve the sample complexity bound for agnostic reliable learning (with Gaussian margin).

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

I think the authors could give some future directions and potential improvements.

Summary

This paper considers learning halfspaces with Gaussian marginals in a reliable learning setting, where the learner has to guarantee that the error of the output classifier is less than $\epsilon$ (and we assume such a classifier exists). It is known that the reliable learning problem can be efficiently reduced to agnostic learning, but the sample complexity for agnostic learning is high ($d^{O(1/\epsilon)}$). This paper proposes an algorithm that has a much better sample complexity (polynomial in d, but still quasi-polynomial in $1/\epsilon$), and it provides a lower bound showing that one cannot do much better w.r.t. d.

Strengths

- This paper considers an interesting learning theory problem. - The results look nontrivial. - The methods look sound, though I'm not familiar with the techniques used here and did not check the proofs. - It is written clearly, and explains the intuition well.

Weaknesses

- Though this is an interesting theory problem, it is not entirely clear to me how significant the results are. Specifically, what is the importance or implication of the computational separation between agnostic and reliable learning found in this paper, especially given that the proposed algorithm is still super-polynomial.

Questions

N/A

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This work studies agnostic learning of halfspaces in the reliable learning model, which guarantees a halfspace with nearly no false positives and a nearly optimal false negative rate, where the optimal false negative rate is defined relative to a class of halfspaces with no false positives. The authors prove sample and computational bounds for this learning task under a standard Gaussian distributional assumption, dramatically improving the previously known bounds that followed from reduction to general agnostic learning under the same distributional assumption. They also show a statistical query lower bound of $d^{\Omega(\log(1/\alpha))}$.

Strengths

This work furthers our understanding of the sample and computational complexity of learning halfspaces under challenging noise models. The techniques used to obtain the algorithmic result are very interesting, and while technically involved, the overview of the proof approach in the main body is well-structured and modular (if still hard to follow as someone with little familiarity with the related work).

Weaknesses

While the page-limits are restrictive, I would have benefited from some additional handholding even in the overview. The introduction of Lemma 2.5 was particularly opaque, for instance. Typos/suggested edits: Line 14. “The problem of learning halfspaces is one the classical” Line 40. “has since been extensively studies” Line 53. “minimizing a lost function” Line 69. “as a reliable agnostic learning for Gaussian halfspaces” Line 84. missing close parens line 94. “reduce the fully reliable learning” line 105. “This implies that that” line 214. “Let D be joint distribution” Algorithm 1 caption “General Halspaces” Line 511/525 “Reliable learning halfspaces”

Questions

In line 222, I’m confused about the signs. Doesn’t the interval $[t^*, \infty]$ correspond to positive labels, and don’t we want the expectation of p within this region to be negative? How does the equality in line 241 follow from Lemma 2.5?

Rating

8

Confidence

2

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes, the authors address the limitations of the work.

Summary

This paper studies reliable learning of halfspaces in $d$ dimensions. Reliable learning is a framework in learning theory in which the learning algorithm is required to output a classifier $f$ satisfying: - the probability that f makes a false-positive error is at most $\epsilon$ - The probability that f makes a false-negative error is at most $opt+ \epsilon$, where $opt$ is the smallest error rate achievable by a classifier in the class $\mathcal{G}$ that has zero false-positive error. The work gives a reliable learning algorithm for the class of $\alpha$-biased halfspaces when the data marginal is the standard Gaussian distribution. A halfspace is $\alpha$-biased if on a Gaussian input it has probability at least $\alpha$ to take either of the two possible output values. The run-time of the algorithm is $d^{O(\log(min(1/\alpha,1/\epsilon)))}min(2^{\log(1/\epsilon)^{O(log(1/\alpha))}} , 2^{poly(1/\epsilon)})$. The algorithm first finds a candidate direction by estimating the Chow tensor. Consequently, the algorithm improves this hypothesis by performing a certain random walk. It is shown that any statistical-query algorithm has to take at least $d^{\log 1/\alpha}$ time for this task. Statistical-query algorithm are a wide family of algorithms that includes virtually all algorithms studied in learning theory.

Strengths

- Reliable learning is a natural framework asking for approximately-best classifier that makes false positive rarely. Considering halfspaces over Gaussian data is arguably the most natural setting to study. However, prior to this work little was known about this question. - The run-time compares favorably with the run-time of $d^{poly(1/\epsilon}$ that is known to be best for the more challenging agnostic model. This is true for all values of bias $\alpha$, but is especially true when $\alpha$ is a small constant. - The methods developed in this work seem potentially interesting in their own right.

Weaknesses

- Not clear that the dependence on $\epsilon$ is best it can be. - None of the algorithms run in fully polynomial time in all parameters.

Questions

- I think there is a missing parenthesis in the end of Theorem 1.3 - Is it possible that for every small constant $c$, if $\alpha$ is promised to be at least $c$, then there is an algorithm running in time $\poly(d/\epsilon)$? - Is it correct that for these halfspaces your algorithm runs in time $d^{O(1} 2^{\log(1/\epsilon)^{O(1)}}$?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Limitations are discussed adequately.