Robust learning of halfspaces under log-concave marginals

Thank you for suggesting that we mention that our algorithm is improper earlier in the introduction, add “with high probability” and forward references to the improper statements, and change the name “deterministic robustness” to “deterministic verifiability.” We will address these points in the final version of this paper.

Thank you for pointing out as well that the function signature of Verify and the input description do not match. The intended inputs are $g, x, r, \epsilon, data$. We will fix this inaccuracy in the final version of this paper.

Regarding the behavior of the randomized verifier, consecutive runs of the verifier on different points are not supposed to be independent; our guarantee is stronger than that. Rather, with probability $\ge 1 - \delta$ (over the choice of the samples of $N(0,I_d)$ used to implement the $\hat{\phi}$ estimator), soundness holds simultaneously for all points in $\mathbb{R}^d$.

The condition $\epsilon > d^{-1/7}$ is indeed used for the partitioning step; it is because the failure probability of the concentration of projections has large powers of $\epsilon$. It may be possible with tighter analysis to decrease this power, but not below $\epsilon^4$, since that is the dependence given in [DHV ’06]. We would like to emphasize that when $\epsilon = d^{-1/7}$ the run-time is $2^{d^{O(1)}}$ which is exponential in $d$. Furthermore, for such small values of $\epsilon$, run-times of this form are believed to be necessary (even for regular improper learning) due to statistical query lower bounds we cite in this work. Since one of the main goals of this paper is to develop algorithms with run-times much faster than $2^{d^{O(1)}}$, we do not focus on the parameter regime where $\epsilon < d^{-1/7}$.

Thank you for suggesting that the introduction be reorganized for clarity. In the final version of this paper, we will state our definitions of isolation probability and noise sensitivity early in the technical overview so that it can be self-contained. We can also use an alternative term such as “perturbation sensitivity” to avoid confusion between our notion and the standard definition of noise sensitivity.

The current work focuses on the highly natural and basic class of halfspaces. Halfspaces are a fundamental class of functions, and there has been a large number of works that exclusively focus on this class of functions. Historically, algorithms designed for halfspaces have frequently yielded algorithms for further hypothesis classes with further technical work, but for this paper we did not directly aim to develop algorithms for other hypothesis classes.

One generalization we had in mind was simple polytopes, which have low boundary volume and low noise sensitivity in the sense presented in this paper. Currently, robustly learning even intersections of two halfspaces remains an open problem, and we think that techniques similar to ours may be useful for this problem.

We agree that the class of low-degree PTFs are a natural target for future work. It is correct that using our definition of local noise sensitivity there is a large volume of points for which the local noise sensitivity is large. However, one could potentially try to sidestep this by considering a noise distribution that uses rescaling similar to the more standard Ornstein–Uhlenbeck process, together with ideas presented in this work.

Thank you for suggesting a more thorough discussion of the relationship between adversarial robustness and noise sensitivity. Intuitively, a function can have low global noise sensitivity and not be adversarially robust, when the classification boundary lies near many “isolated” points scattered throughout the domain. Each such isolated region has high local noise sensitivity; thus by using local noise sensitivity as the proxy for local correction, we eliminate these regions. We will add a discussion of this to the final version of this paper.

Regarding Question 1, we repeat the discussion given in response to reviewer 7bYh:

Some distributional assumptions are necessary to evade NP-hardness results, and furthermore some assumptions are necessary for the class of halfspaces itself to be adversarially robust – without anticoncentration, a distribution could place a lot of mass on the classification boundary.

The assumption that the distribution is isotropic is not crucial: if the covariance matrix has all eigenvalues between a pair of positive constants $C_1$ and $C_2$, one can perform a change basis and reduce the problem to the isotropic case (while preserving adversarial robustness). If covariance has eigenvalues very close to zero, halfspaces stop being adversarially robust under such distributions.

Regarding the other assumptions, not much is known about learning halfspaces without these assumptions even in the non-robust improper setting, and not much is known about how learning algorithms perform when the assumptions are slightly violated. If log-concavity is assumed but subgaussianity is not assumed, the best run-time given in [KKMS ‘08] is doubly exponential in $1/\epsilon$ (which is much slower than the algorithms on which our work focuses). No non-trivial algorithms are known if only sub-Gaussianity is assumed.

Regarding Questions 2 and 3, we agree that experimental results would be interesting and consider this an avenue for future work. Analyzing the effects of local correction on other models is an interesting direction for future work as well.

Indeed our running time is exponential in $1/\epsilon$, as is all previous work on learning halfspaces up to error $opt+\epsilon$, and thus it is meant for settings where $d$ is the limiting parameter. We note that prior to our work, no algorithm with run-time better than $2^{\Omega(d)}$ was known for the task we consider.

An exponential dependence on $1/\epsilon^2$ in the running time is believed to be necessary due to the statistical query lower bound for agnostically learning halfspaces [Diakonikolas, Kane, Pittas, Zarifis ‘21] which is also exponential in $1/\epsilon^2$. There are also run-time lower bounds based on commonly accepted cryptographic hardness assumptions [Diakonikolas, Kane, Ren ICML 2023].

Regarding the novelty of our techniques:

• The use of low-degree approximating polynomials for learning is a well-established technique; however this work introduces a proxy for adversarial robustness and shows that polynomial optimization under this constraint is feasible. This type of analysis is new in this work.
• The use of local correction for learning continues a line of work that is a few years old (introduced in [LRV22]). Previous work uses local correction only to ensure monotonicity of a hypothesis; this is the first application of this technique outside of that setting.
• The randomized partitioning and rounding strategy is, to the best of our knowledge, new in this work.

Thank you for pointing out the incomplete footnote. It should say “The algorithm of [Dan15] also applies only to the Gaussian distribution, and not to general sub-Gaussian log-concave distributions.”

Indeed improperness is a limitation of our algorithm. Agnostic proper learning in this setting is a longstanding open problem.

Some distributional assumptions are necessary to evade NP-hardness results, and furthermore some assumptions are necessary for the class of halfspaces itself to be adversarially robust – without anticoncentration, a distribution could place a lot of mass on the classification boundary.

The assumption that the distribution is isotropic is not crucial: if the covariance matrix has all eigenvalues between a pair of positive constants $C_1$ and $C_2$, one can perform a change basis and reduce the problem to the isotropic case (while preserving adversarial robustness). If covariance has eigenvalues very close to zero, halfspaces stop being adversarially robust under such distributions.

Regarding the other assumptions, not much is known about learning halfspaces without these assumptions even in the non-robust improper setting, and not much is known about how learning algorithms perform when the assumptions are slightly violated. If log-concavity is assumed but subgaussianity is not assumed, the best run-time given in [KKMS ‘08] is doubly exponential in $1/\epsilon$ (which is much slower than the algorithms on which our work focuses). No non-trivial algorithms are known if only subgaussianity is assumed.

The question of slightly relaxing the log-concavity assumption is currently an active area of research, but is not fully understood even for regular (non-robust) agnostic learning. Though there are algorithms that handle distributions $\epsilon$-close in TV distance to specific distributions [Goel, Shetty, Stavropoulos, Vasilyan NeurIPS 2024], there is no non-trivial algorithm known that achieves error $opt+O(\epsilon)$ for all distributions $\epsilon$-close to log-concave in TV distance (outside of the brute-force $2^d$ time algorithms).