aiqbench analysis
This is theoretical statistical learning work: it gives sample-efficient, computationally efficient algorithms for learning Gaussian mixtures and related distributions while satisfying local differential privacy, which means no trusted curator ever sees raw user data. It also tightens the known lower bound for GMMs under LDP, so readers get a clearer picture of what privacy costs in sample complexity. The results are relevant to anyone building privacy-preserving ML pipelines, though they are not yet a practical system or a benchmark result.
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
arXiv:2610.21033v1 Announce Type: cross 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].
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].
Machine Learning (stat.ML); Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG)
arXiv:2610.21033 [stat.ML]
(or arXiv:2610.21033v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2610.21033 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 158 words
