Privacy for Free in Efficient Agnostic Halfspace Learning

Giorgio Racca; Amartya Sanyal; Vikrant Singhal

cs.LGNov 3, 2026

Privacy for Free in Efficient Agnostic Halfspace Learning

Authors: Giorgio Racca, Amartya Sanyal, Vikrant Singhal

Organizations: Department of Computer Science, University of Copenhagen

Abstract

We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces. In particular, we study three different settings of agnostic learning: improper learning under Gaussian and log-concave marginals; proper learning under Gaussian marginals; and semi-agnostic learning under Gaussian marginals. In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.

Figures & tables

Marginal	Learner	Error	Sample complexity $\widetilde{{\mathcal{O}}}\left({{\cdot}}\right)$
Gaussian	Improper	$\operatorname{OPT}+\alpha$	$\displaystyle\frac{D_{\mathrm{G}}}{\alpha^{2}}+\frac{D_{\mathrm{G}}}{\varepsilon_{\mathrm{DP}}\alpha}$
Log-concave	Improper	$\operatorname{OPT}+\alpha$	$\displaystyle\frac{D_{\mathrm{L}}}{\alpha^{2}}+\frac{D_{\mathrm{L}}}{\varepsilon_{\mathrm{DP}}\alpha^{3/2}}$
Gaussian	Proper	$\operatorname{OPT}+\alpha$	$\displaystyle\frac{D_{\mathrm{G}}}{\alpha^{2}}+\frac{D_{\mathrm{G}}}{\varepsilon_{\mathrm{DP}}\alpha}+\frac{1}{\alpha^{6}}+\frac{1}{\varepsilon_{\mathrm{DP}}\alpha^{5}}$
Gaussian	Proper	$C\!\cdot\!\operatorname{OPT}+\alpha$	$\displaystyle\frac{d}{\alpha^{2}}+\frac{d}{\varepsilon_{\mathrm{DP}}\alpha}$

Table 1: The rows correspond, respectively, to Theorem 2.1 , Theorem D.1 , Theorem 3.1 , and Theorem 4.1 . Here,

D_{\mathrm{G}}\asymp d^{{\mathcal{O}}\left({1/\alpha^{2}}\right)}

and

D_{\mathrm{L}}\asymp d^{\exp\left({{\mathcal{O}}\left({1/\alpha}\right)}\right)}

match known rates in the non-private setting ( Diakonikolas et al., 2010 ; Kalai et al., 2008 ) , and

\widetilde{{\mathcal{O}}}

suppresses polylogarithmic factors.

Halfspace Learning

See all 17 papers

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals
May 26, 2026Sergei Tikhonov, Arsen VasilyanAgnostic Learning Boolean Function Learning
UT Austin
Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
Nov 3, 2026Zhijie ZhengHalfspace Learning Statistical Learning Theory
Peking University
Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
Apr 29, 2026Jizhou Huang, Brendan JubaAgnostic Learning Statistical Learning Theory
Meta · Washington Universtiy in St. Louis

May 26, 2026J/K move · Enter open · S save

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

Sergei Tikhonov, Arsen Vasilyan

UT Austin

Agnostic Learning Boolean Function Learning Statistical Learning Theory Halfspace Learning

Open paper AskPDF arXiv

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over

\mathbb{R}^d \times \{\pm 1\}

whose marginal on

\mathbb{R}^d

is Gaussian, the goal is to output a hypothesis from a target class

\mathcal{F}

whose 0-1 loss is within

ε

of that of the best classifier in

\mathcal{F}

. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of

K

halfspaces under Gaussian marginals. Our algorithm runs in time

d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}

. Prior to our work, the only known algorithm for

K \geq 2

was brute-force search, with run-time exponential in

d

. Moreover, the dependence of our run-time on the dimension

d

matches that of the best known improper learning algorithm, namely

d^{\widetilde{O}(K^2/ε^2)}

. For the special case of a single halfspace (

K=1

), the best previous run-time was

d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}

. Our algorithm improves this to

d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}

. Once again, the dependence on

d

matches that of the best known improper algorithm, namely

d^{O(1/ε^2)}

. Furthermore, the dependence of our run-time on the dimension

d

is essentially optimal in the statistical query model.

Abstract

Halfspace Learning

Explore similar work

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals