# Private Online Learning via Lazy Algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 5 Jun 2024.

## Builds on (most cited first, 16 of 16)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition](https://mlsanity.com/paper/1910.10873/) (2019)
- [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)
- [Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime](https://mlsanity.com/paper/2302.14154/) (2023)
- [Improved Differentially Private and Lazy Online Convex Optimization](https://mlsanity.com/paper/2312.11534/) (2023)

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

- [Faster Rates for Private Adversarial Bandits](https://mlsanity.com/paper/2505.21790/) (2025)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Prediction with Expert Advice under Local Differential Privacy](https://mlsanity.com/paper/2512.06971/) (2025)

## Abstract (arXiv)

We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO). We propose a new transformation that transforms lazy online learning algorithms into private algorithms. We apply our transformation for differentially private OPE and OCO using existing lazy algorithms for these problems. Our final algorithms obtain regret, which significantly improves the regret in the high privacy regime varepsilon ll 1, obtaining √T log d + T1/3 log(d)/varepsilon2/3 for DP-OPE and √T + T1/3 √d/varepsilon2/3 for DP-OCO. We also complement our results with a lower bound for DP-OPE, showing that these rates are optimal for a natural family of low-switching private algorithms.