cs.LGstat.ML
Privacy for Free in Efficient Agnostic Halfspace Learning
📅
👥 3 authors
arXiv:2611.05208v1
Authors
Giorgio RaccaAmartya SanyalVikrant Singhal
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