mlsanityData to 14 Oct 2026

The Price of Differential Privacy For Online Learning

arXiv 1701.07953 ↗First posted 27 Jan 2017cs.LG stat.MLcited by 45

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 12; 2023: 6; 2024: 8; 2025: 8; 2026: 3.

45 papers.

Sort:

By area:

  1. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 170
  2. 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
  3. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  4. 2021Survey: Leakage and Privacy at Inference Timecited by 44
  5. 2022Shuffle Private Linear Contextual Banditscited by 27
  6. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  7. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  8. 2022Offline Reinforcement Learning with Differential Privacycited by 20
  9. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
  10. 2021Lazy OCO: Online Convex Optimization on a Switching Budgetcited by 14
  11. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  12. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
33 more
  1. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  2. 2021Littlestone Classes are Privately Online Learnablecited by 10
  3. 2023Near-Optimal Algorithms for Private Online Optimization in the Realizable Regimecited by 9
  4. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  5. 2022Dynamic Global Sensitivity for Differentially Private Contextual Banditscited by 5
  6. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5
  7. 2024The Limits of Differential Privacy in Online Learningcited by 5
  8. 2022Do you pay for Privacy in Online learning?cited by 4
  9. 2024Private PAC Learning May be Harder than Online Learningcited by 4
  10. 2023On Differentially Private Online Predictionscited by 3
  11. 2023Improved Differentially Private and Lazy Online Convex Optimizationcited by 3
  12. 2024Private Online Learning via Lazy Algorithmscited by 3
  13. 2025Private Learning of Littlestone Classes, Revisitedcited by 3
  14. 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
  15. 2025Private Continual Counting of Unbounded Streamscited by 2
  16. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  17. 2023Multitask Online Learning: Listen to the Neighborhood Buzzcited by 1
  18. 2024DP-Dueling: Learning from Preference Feedback without Compromising User Privacycited by 1
  19. 2024Bridging Privacy and Robustness for Trustworthy Machine Learningcited by 1
  20. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  21. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  22. 2024DP-CDA: An Algorithm for Enhanced Privacy Preservation in Dataset Synthesis Through Randomized Mixingcited by 1
  23. 2025Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacycited by 1
  24. 2025Faster Rates for Private Adversarial Banditscited by 1
  25. 2025Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settingscited by 1
  26. 2026Privately Learning Decision Lists and a Differentially Private Winnowcited by 1
  27. 2026The Binary Tree Mechanism is Optimal for Differentially Private Continual Countingcited by 1
  28. 2022Continual and Sliding Window Release for Private Empirical Risk Minimizationcited by 0
  29. 2023Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noisecited by 0
  30. 2025Differentially Private Equilibrium Finding in Polymatrix Gamescited by 0
  31. 2025Optimal Regret of Bernoulli Bandits under Global Differential Privacycited by 0
  32. 2025Prediction with Expert Advice under Local Differential Privacycited by 0
  33. 2026CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplacescited by 0