Reliable Learning of Halfspaces under Gaussian Marginals

We thank the reviewer for the time and effort in reviewing our paper and for the positive feedback.

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$?

Response: The point of our SQ lower bound is that the joint dependence between the dimension $d$ and the bias $\alpha$ of the target concept is inherently quasi-polynomial, namely $d^{\Omega(\log(1/\alpha))}$ (assuming that $\alpha \geq 2\epsilon$). This lower bound holds for any $2\epsilon \leq\alpha$. Importantly, we provide the first such lower bound for reliable learning of Gaussian halfspaces. We do not know of a super-polynomial lower bound on $\epsilon$ and leave this as an open question for future investigation.

At a more technical level, our construction establishes an SQ lower bound for a natural testing version of the problem (that is easier than learning). This testing problem is in fact solvable with SQ complexity $d^{\Theta(\log(1/\alpha))}$ (both upper and lower bound). The dependence on $\epsilon$ in our upper bound is due to the fact that we need to search for a good solution via a random walk, as explained in lines 108-130.

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?

Response: For agnostically learning Gaussian halfspaces, the $d^{\mathrm{poly}(1/\epsilon)}$ SQ lower bound holds even for $\alpha=1/2$, which suggests that the agnostic problem does not become harder with smaller $\alpha$. We show in our work that this is not the case for the reliable learning task. Intuitively, in the agnostic model, the adversary can corrupt an $\epsilon$-fraction of the labels anywhere on the entire domain. On the other hand, in the reliable setting, the adversary can only corrupt labels inside the region $c(\mathbf{x})=-1$ (where $c$ is the target concept). As a result, one needs degree-$\mathrm{poly}(1/\epsilon)$ polynomials to not be fooled by noise in agnostic learning. While in reliable learning, our Lemma 2.3 shows that a degree-$O(\log (1/\alpha))$ polynomial suffices (where $\alpha$ is the bias of concept $c$ and $\alpha\geq \epsilon$). It is also worth mentioning that for the special case of $\alpha=1/2$, we get $\mathrm{poly}(d/\epsilon)$ runtime for reliable learning via an easy algorithm (see Lemma B.3).

Finally, we remark that we do not assume anywhere that the parameter $\alpha$ is a constant. Our algorithm works for any value of $\alpha$ (even if it is not known a priori to the algorithm).

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?

Response: While SQ lower bounds are viewed as strong evidence of hardness in learning theory, we acknowledge that the SQ model is a restricted model of computation. So, in principle, it may possible to surpass SQ algorithms. On the other hand, there are very few such examples in the literature (and none for learning halfspaces with noise). Alternatively, one could try to prove reduction-based hardness (from a plausibly average-case hard problem, e.g., in cryptography). There are a few such reductions in the literature, and in some cases they have been directly inspired from the SQ-hard instances. A recent example that is relevant for us is for the task of agnostically learning Gaussian halfspaces, where [DKR23] (building on the SQ lower bounds of [DKZ20]) gives a cryptographic lower bound (assuming the subexponential hardness of LWE). Their technique requires a hard distribution whose marginal in the hidden direction is (roughly speaking) a mixture of periodic signals, which cannot be adapted for our hard distribution here. It remains an interesting open problem to establish reduction-based hardness for our problem.

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

Response: We agree with the reviewer that active learning does not seem to help with agnostic learning halfspaces under Gaussian marginals. It is not clear to us whether active learning can help in the reliable learning case. This is an interesting open question for future work.

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

Response: We are happy to add some future directions in the revised version. An immediate open question is whether one can improve the dependence of the runtime as a function of $\epsilon$ from quasi-polynomial down to polynomial.

the "corrupt negative labels are free" part is worth more insights.

Response: In fact, corrupting negative labels is not free, as the adversary has an $\epsilon$ budget to corrupt negative labels. However, the adversary is restricted to only corrupting the "true" negative labeled samples as compared to the agnostic model.

More explanation on the use of polynomial

Response: In lines 116-123, we explained the high-level idea of using polynomials to learn. We are happy to add further explanations to make the intution more transparent.

[DKZ20] I. Diakonikolas, D. Kane, and N. Zarifis. Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.

[DKR23] I. Diakonikolas, D. M. Kane, and L. Ren. Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. In International Conference on Machine Learning, ICML, 2023.

We thank the reviewer for the time and effort in reviewing our paper and for the positive feedback. We respond to the point raised by the reviewer regarding the significance of our result.

Our result is the first to establish a computational separation between reliable and agnostic learning in the distribution-specific setting for the class of halfspaces. While our algorithm has superpolynomial runtime (as a function of the excess error $\epsilon$ and the bias $\alpha$), it achieves an exponential improvement over the previous best-known algorithm for the problem. Moreover, the underlying algorithmic technique is likely to be useful for related reliable learning tasks. It it worth noting that our algorithm runs in $\mathrm{poly}(d)$ time for any constant $\alpha$ and moderately small values of the parameter $\epsilon$ (namely up to $1/\mathrm{polylog}(d)$). On the other hand, for agnostic learning, one incurs super-polynomial time for any $\epsilon= o(1)$ (even if $\alpha=1/2$). Finally, we believe that our work provides fundamental insights into the task of reliable learning and lays the foundations for the development of practical algorithms for the task.

We thank the reviewer for the time and effort in reviewing our paper and for the positive feedback. Below, we provide specific responses to the points and questions raised by the reviewer.

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?

Response: In Lemma 2.3, our goal is to show that $\mathbf{E}_D[y\,p(\mathbf{x})]$ is large. Therefore, ideally, we want the polynomial $p$ to be positive on regions with positive labels and negative on regions with negative labels.

How does the equality in line 241 follow from Lemma 2.5?

Response: There is a typo in the equality in line 241, where there should be an $\Omega(\cdot)$ in the right-hand side. This follows from the fact that the correlation between two random $d$-dimensional unit vectors is at least $\Omega(1/\sqrt{d})$ with high probability. Lemma 2.5 gives a lower bound on $||\mathrm{proj}_V(\mathbf{v}^*)||_2$, which implies $|\langle \mathbf{v},\mathbf{v}^*\rangle |$ is sufficiently large for a randomly chosen unit vector $\mathbf{v}$.

We thank the reviewer for the time and effort in reviewing our paper and for the positive feedback. Below, we provide specific responses to the points and questions raised by the reviewer.

Is it possible that for every small constant $c$, if $\alpha$ is promised to be at least a constant, then there is an algorithm running in time $\mathrm{poly}(d/\epsilon)$?

Response: Yes, it is possible in principle. Our lower bound does not rule out this possibility.

Is it correct that for these halfspaces, your algorithm runs in time $\mathrm{poly}(d)2^{\mathrm{polylog}(1/\epsilon)}$?

Response: Yes, for any constant $\alpha$, our algorithm runs in $\mathrm{poly}(d)2^{\mathrm{polylog}(1/\epsilon)}$ time.

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

Response: We want to remark that although the dependence of the running time on $\epsilon$ might not be the best possible, it is still an exponential improvement over the previously best-known algorithm for the problem. Moreover, fully polynomial dependence on all parameters seems unlikely, given our SQ lower bound. Specifically, the $d^{\Omega(\log(1/\alpha))}$ dependence is inherent for SQ algorithms.