research
Agnostic Halfspaces Get Privacy Without Extra Sample Order
New efficient algorithms match the order of non-private sample complexity while adding differential privacy in three Gaussian or log-concave settings.
Summary
New efficient algorithms match the order of non-private sample complexity while adding differential privacy in three Gaussian or log-concave settings.
The theoretical result covers improper agnostic learning under Gaussian and log-concave marginals, proper learning under Gaussian marginals and semi-agnostic learning under Gaussian marginals. In each setting, the privacy-related sample cost matches the respective non-private sample-complexity order, which the authors describe as privacy for free. The contribution is computational and asymptotic: it does not mean privacy has zero constant cost, applies to arbitrary distributions or removes the need to choose a privacy budget.
Why it matters
New efficient algorithms match the order of non-private sample complexity while adding differential privacy in three Gaussian or log-concave settings.
Limits and context
- The contribution is computational and asymptotic: it does not mean privacy has zero constant cost, applies to arbitrary distributions or removes the need to choose a privacy budget.
Key claims
New efficient algorithms match the order of non-private sample complexity while adding differential privacy in three Gaussian or log-concave settings.
Qualification: The contribution is computational and asymptotic: it does not mean privacy has zero constant cost, applies to arbitrary distributions or removes the need to choose a privacy budget.
Evidence: source-2026-11-04-016
Sources
- arXiv preprint 2611.05208, original v1arXiv · primary research
Corrections
No corrections have been recorded for this story.