cs.LGstat.ML

Privacy for Free in Efficient Agnostic Halfspace Learning

📅 👥 3 authors arXiv:2611.05208v1

Authors

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.

Paper Information

arXiv ID:
2611.05208v1
Published:

Related Categories

cs.LGstat.ML