# Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy

arXiv: https://arxiv.org/abs/2011.05934 · HTML: https://mlsanity.com/paper/2011.05934/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2020.

## Built on by (most cited first, 16 of 16)

- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Machine Unlearning: A Survey](https://mlsanity.com/paper/2306.03558/) (2023)
- [Practical Differentially Private and Byzantine-resilient Federated Learning](https://mlsanity.com/paper/2304.09762/) (2023)
- [A Survey on Machine Unlearning: Techniques and New Emerged Privacy Risks](https://mlsanity.com/paper/2406.06186/) (2024)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [Task-aware Privacy Preservation for Multi-dimensional Data](https://mlsanity.com/paper/2110.02329/) (2021)
- [Private Language Models via Truncated Laplacian Mechanism](https://mlsanity.com/paper/2410.08027/) (2024)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Locally Differentially Private Bayesian Inference](https://mlsanity.com/paper/2110.14426/) (2021)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Differentially Private Sparse Linear Regression with Heavy-tailed Responses](https://mlsanity.com/paper/2506.06861/) (2025)
- [Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Data](https://mlsanity.com/paper/2602.03872/) (2026)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)
- [Enhancing Generative Class Incremental Learning Performance with Model Forgetting Approach](https://mlsanity.com/paper/2403.18258/) (2024)
- [Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness](https://mlsanity.com/paper/2607.01492/) (2026)

## Abstract (arXiv)

In this paper, we study the Empirical Risk Minimization (ERM) problem in the non-interactive Local Differential Privacy (LDP) model. Previous research on this problem citepsmith2017interaction indicates that the sample complexity, to achieve error α, needs to be exponentially depending on the dimensionality p for general loss functions. In this paper, we make two attempts to resolve this issue by investigating conditions on the loss functions that allow us to remove such a limit. In our first attempt, we show that if the loss function is (∞, T)-smooth, by using the Bernstein polynomial approximation we can avoid the exponential dependency in the term of α. We then propose player-efficient algorithms with 1-bit communication complexity and O(1) computation cost for each player. The error bound of these algorithms is asymptotically the same as the original one. With some additional assumptions, we also give an algorithm which is more efficient for the server. In our second attempt, we show that for any 1-Lipschitz generalized linear convex loss function, there is an (ε, δ)-LDP algorithm whose sample complexity for achieving error α is only linear in the dimensionality p. Our results use a polynomial of inner product approximation technique. Finally, motivated by the idea of using polynomial approximation and based on different types of polynomial approximations, we propose (efficient) non-interactive locally differentially private algorithms for learning the set of k-way marginal queries and the set of smooth queries.