arxiv6.0 / 10

Privacy for Free in Efficient Agnostic Halfspace Learning

Giorgio Racca, Amartya Sanyal, Vikrant 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.

Research area

computational learning theorydifferential privacyprivacy
Published
3 Nov 2026
Source
arxiv
Org
University of Copenhagen
View paper
Sign in to read and join the discussion.