Halfspace learning gets differential privacy for free: in three agnostic settings the privacy cost folds into the statistical term

Agnostic learning of halfspaces under Gaussian marginals now has computationally efficient differentially private versions, covering improper learning whose output need not be a halfspace, proper learning whose output must be a halfspace, and semi-agnostic learning that permits a constant factor of the optimal error. Over infinite domains, distribution-free private halfspace learning was previously information-theoretically impossible, and existing private realizable-to-agnostic reductions, though statistically efficient, were not shown to be computationally efficient. The improper and proper settings give high-probability guarantees of error at most the best halfspace's error plus the accuracy parameter, the semi-agnostic setting gives error at most a constant factor of the optimal error plus the accuracy parameter, and all three algorithms run in time polynomial in the sample size for every fixed accuracy.

The route is to privatize the non-private polynomial regression approach: private polynomial L1 regression over clipped Hermite features, followed by private selection among thresholded candidate classifiers. The non-private route fits a low-degree polynomial to the labels and then thresholds its predictions, but adding noise directly requires bounded coefficients and bounded feature norms. Restricting coefficients to the Euclidean unit ball and clipping feature vectors to a norm cap makes clipping raise population loss only by the clipping probability, so private convex empirical risk minimization can fit the coefficients.

Proper learning first privately estimates a polynomial, then uses it to build a low-dimensional subspace containing a near-optimal halfspace, where a halfspace needs only O(d) parameters. The improper learner's output has on the order of d to the 1/α² coefficients, whereas a halfspace representation is more compact, easier to interpret and faster to evaluate. The subspace has dimension on the order of α to the minus fourth; discretizing unit normal vectors in it yields a finite class of halfspaces, and an exponential mechanism on an independent validation block selects the final halfspace.

Semi-agnostic learning instead uses a privatized non-convex gradient descent subroutine and searches over a geometric grid of upper bounds on the optimal error, reducing the dependence on 1/α from exponential to polynomial. The first two settings have sample complexity exponential in 1/α, while the semi-agnostic setting allows error a constant factor above optimal and thereby sidesteps that barrier. Given a known upper bound on the optimal error, the subroutine returns a halfspace with error a constant factor of that bound; after running it for each candidate bound, an exponential mechanism on a separate validation set picks the hypothesis.

The results concern distributions whose input marginal is Gaussian (with one section extending to known log-concave marginals) and whose labels may be arbitrary, with error guarantees holding with probability at least 1 minus the failure probability; the improper and proper settings also require the dimension to exceed a constant times the accuracy parameter to the minus fifth.

Privacy is free only when the privacy parameter is at least the accuracy parameter, the regime in which the privacy term is absorbed by the statistical term; the improper setting requires explicitly constructing an orthonormal polynomial basis for each known marginal family, and more versatile bases or privately learning a basis from data remain open directions.