# Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2018.

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

- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [Practical Vertical Federated Learning with Unsupervised Representation Learning](https://mlsanity.com/paper/2208.10278/) (2022)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [Differentially Private Decentralized Learning with Random Walks](https://mlsanity.com/paper/2402.07471/) (2024)
- [On the Fairness Impacts of Private Ensembles Models](https://mlsanity.com/paper/2305.11807/) (2023)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [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)
- [Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy](https://mlsanity.com/paper/2510.19934/) (2025)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [One-bit Submission for Locally Private Quasi-MLE: Its Asymptotic Normality and Limitation](https://mlsanity.com/paper/2202.07194/) (2022)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)
- [Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping](https://mlsanity.com/paper/2206.13011/) (2022)
- [Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approach](https://mlsanity.com/paper/2508.07505/) (2025)
- [Learning with Locally Private Examples by Inverse Weierstrass Private Stochastic Gradient Descent](https://mlsanity.com/paper/2602.16436/) (2026)
- [Integrating Feature Correlation in Differential Privacy with Applications in DP-ERM](https://mlsanity.com/paper/2605.03945/) (2026)

## Abstract (arXiv)

In this paper, we study the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. In the case of constant or low dimensionality (pll n), we first show that if the ERM loss function is (∞, T)-smooth, then we can avoid a dependence of the sample complexity, to achieve error α, on the exponential of the dimensionality p with base 1/α (i.e., α-p), which answers a question in [smith 2017 interaction]. Our approach is based on polynomial approximation. Then, we propose player-efficient algorithms with 1-bit communication complexity and O(1) computation cost for each player. The error bound is asymptotically the same as the original one. Also with additional assumptions we show a server efficient algorithm. Next we consider the high dimensional case (nll p), we show that if the loss function is Generalized Linear function and convex, then we could get an error bound which is dependent on the Gaussian width of the underlying constrained set instead of p, which is lower than that in [smith 2017 interaction].