Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 59 min ago
PreprintCC BY 4.0arXiv

Privacy for Free in Efficient Agnostic Halfspace Learning

  • Giorgio Racca
  • Amartya Sanyal
  • Vikrant Singhal
Open at sourcePDFDOICite

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.

Related

  1. Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
    Mohammad Afzali, Hassan Ashtiani, Sivan Sabato
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
    Sasha Voitovych, Adam Block, Alexander Rakhlin +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Efficient Proper Agnostic Learning of Halfspaces
    Anindya De, Elchanan Mossel, Shivam Nadimpalli +1
    arXivPreprintCC BY-NC-ND 4.0Full textStatisticsarXiv
  4. FedCap-Priv: Geometry-Aware Privacy and Bandwidth-Efficient Routing for Federated Capsule Learning
    Yantao Li, Zijie Pan
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  5. Privacy-Preserving Over-the-Air Federated Learning over Cell-Free Massive MIMO System with User-Centric Clustering
    Manobendu Sarker, Soumaya Cherkaoui
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{racca2026privacy,
  title = {{Privacy for Free in Efficient Agnostic Halfspace Learning}},
  author = {Giorgio Racca and Amartya Sanyal and Vikrant Singhal},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05208},
  eprint = {2611.05208},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05208},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Privacy for Free in Efficient Agnostic Halfspace Learning
AU  - Giorgio Racca
AU  - Amartya Sanyal
AU  - Vikrant Singhal
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05208
UR  - https://arxiv.org/abs/2611.05208
AB  - 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.
ER  -