# The Price of Differential Privacy For Online Learning

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2017.

## Built on by (most cited first, 30 of 45)

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Survey: Leakage and Privacy at Inference Time](https://mlsanity.com/paper/2107.01614/) (2021)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Differentially Private Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2201.07052/) (2022)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [No-Regret Algorithms for Private Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2102.12467/) (2021)
- [Privacy-Preserving Communication-Efficient Federated Multi-Armed Bandits](https://mlsanity.com/paper/2111.01570/) (2021)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime](https://mlsanity.com/paper/2302.14154/) (2023)
- [Improved Regret for Differentially Private Exploration in Linear MDP](https://mlsanity.com/paper/2202.01292/) (2022)
- [Dynamic Global Sensitivity for Differentially Private Contextual Bandits](https://mlsanity.com/paper/2208.14555/) (2022)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Do you pay for Privacy in Online learning?](https://mlsanity.com/paper/2210.04817/) (2022)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [On Differentially Private Online Predictions](https://mlsanity.com/paper/2302.14099/) (2023)
- [Improved Differentially Private and Lazy Online Convex Optimization](https://mlsanity.com/paper/2312.11534/) (2023)
- [Private Online Learning via Lazy Algorithms](https://mlsanity.com/paper/2406.03620/) (2024)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment](https://mlsanity.com/paper/2102.07929/) (2021)
- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)
- [On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Bandits](https://mlsanity.com/paper/2206.08111/) (2022)
- [Multitask Online Learning: Listen to the Neighborhood Buzz](https://mlsanity.com/paper/2310.17385/) (2023)
- [DP-Dueling: Learning from Preference Feedback without Compromising User Privacy](https://mlsanity.com/paper/2403.15045/) (2024)

## Abstract (arXiv)

We design differentially private algorithms for the problem of online linear optimization in the full information and bandit settings with optimal tildeO(√T) regret bounds. In the full-information setting, our results demonstrate that ε-differential privacy may be ensured for free -- in particular, the regret bounds scale as O(√T)+tildeOleft(frac1εright). For bandit linear optimization, and as a special case, for non-stochastic multi-armed bandits, the proposed algorithm achieves a regret of tildeOleft(frac1ε√Tright), while the previously known best regret bound was tildeOleft(frac1εT^frac23right).