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

Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy

  • Mohammad Afzali
  • Hassan Ashtiani
  • Sivan Sabato
Open at sourcePDFDOICite

Abstract

We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].

Related

  1. Privacy for Free in Efficient Agnostic Halfspace Learning
    Giorgio Racca, Amartya Sanyal, Vikrant Singhal
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  2. Efficient Proper Agnostic Learning of Halfspaces
    Anindya De, Elchanan Mossel, Shivam Nadimpalli +1
    arXivPreprintCC BY-NC-ND 4.0Full textStatisticsarXiv
  3. Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
    Sasha Voitovych, Adam Block, Alexander Rakhlin +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Deep operator learning for efficient sampling from invariant measures of stochastic differential equations
    Ling Guo, Lei Li, Jingtong Zhang
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  5. Agnostic Model-Assisted Estimation with Machine Learning for Survey Data
    Ziming An, Mehdi Dagdoug, David Haziza +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{afzali2026efficient,
  title = {{Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy}},
  author = {Mohammad Afzali and Hassan Ashtiani and Sivan Sabato},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21033},
  eprint = {2610.21033},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21033},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
AU  - Mohammad Afzali
AU  - Hassan Ashtiani
AU  - Sivan Sabato
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21033
UR  - https://arxiv.org/abs/2610.21033
AB  - We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].
ER  -