# Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 72 references that are in the map.
- First posted on arXiv 1 Oct 2025.

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

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Concurrent Composition of Differential Privacy](https://mlsanity.com/paper/2105.14427/) (2021)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Learning Privately with Labeled and Unlabeled Examples](https://mlsanity.com/paper/1407.2662/) (2014)
- [Private Learning Implies Online Learning: An Efficient Reduction](https://mlsanity.com/paper/1905.11311/) (2019)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Composition Theorems for Interactive Differential Privacy](https://mlsanity.com/paper/2207.09397/) (2022)
- [Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime](https://mlsanity.com/paper/2302.14154/) (2023)
- [Near-tight closure bounds for Littlestone and threshold dimensions](https://mlsanity.com/paper/2007.03668/) (2020)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [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 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)
- [Differentially Private Medians and Interior Points for Non-Pathological Data](https://mlsanity.com/paper/2305.13440/) (2023)
- [Concurrent Composition for Differentially Private Continual Mechanisms](https://mlsanity.com/paper/2411.03299/) (2024)

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

- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)

## Abstract (arXiv)

We revisit the problem of private online learning, in which a learner receives a sequence of T data points and has to respond at each time-step a hypothesis. It is required that the entire stream of output hypotheses should satisfy differential privacy. Prior work of Golowich and Livni [2021] established that every concept class H with finite Littlestone dimension d is privately online learnable in the realizable setting. In particular, they proposed an algorithm that achieves an Od(log T) mistake bound against an oblivious adversary. However, their approach yields a suboptimal tildeOd(√T) bound against an adaptive adversary. In this work, we present a new algorithm with a mistake bound of Od(log T) against an adaptive adversary, closing this gap. We further investigate the problem in the agnostic setting, which is more general than the realizable setting as it does not impose any assumptions on the data. We give an algorithm that obtains a sublinear regret of tildeOd(√T) for generic Littlestone classes, demonstrating that they are also privately online learnable in the agnostic setting.