Paper: Private Online Learning and Prediction for Littlestone Classes

Forum topic · 小凯 · 2026-10-07

Summary

This post introduces an arXiv paper (2610.06822) by Amartya Sanyal in ML theory, proving a separation between differentially private online learning and private online prediction for Littlestone classes under forgetful realizable adversaries. Online learning requires the learner to publish a hypothesis at each step, whereas online prediction only requires predictions. The author establishes a new lower bound for private online learning and an upper bound for private prediction, showing the sample complexities differ by a factor growing with the time horizon T for every finite Littlestone dimension d. Specifically, any (ε,δ)-differentially private online learner incurs at least Ω(d/ε · log(T)^(2/3)) mistakes on some deterministic realizable stream — the first nontrivial lower bound in the regime 1/T < δ < 1/log T, resolving an open problem. In contrast, there exists an (ε,δ)-jointly private predictor with expected mistake bound 2^(2^(cd²)) · ε^(-2) · log²(2/(εδ)), independent of T. When δ = Θ(1/log T), private learning needs Ω((log T)^(2/3)) mistakes while private prediction achieves O((log log T)²).

Paper Overview

Research Area: ML Theory Author: Amartya Sanyal Published: 2026-10-05 arXiv: 2610.06822

Abstract

We study mistake bounds for differentially private online learning and online prediction under forgetful realizable adversaries. Online learning requires the learner to publish a hypothesis at every time step, while online prediction only requires making predictions without publishing a hypothesis. Through a new lower bound for private online learning and an upper bound for private prediction, we show that the sample complexities of these two problems differ by a factor growing with the time horizon, for every class of finite Littlestone dimension d.

First, we prove that every (ε,δ)-differentially private online learner admits a deterministic realizable stream on which it makes at least Ω(d/ε · log(T)^(2/3)) mistakes. This is the first nontrivial lower bound in the regime 1/T < δ < 1/log T, resolving an open problem left by prior work.

Second, we prove that for every class of Littlestone dimension d, there exists an (ε,δ)-jointly private predictor with expected mistakes at most

2^(2^(cd²)) · ε^(-2) · log²(2/(εδ)),

independent of the time horizon T. Consequently, when δ = Θ(1/log T), private learning requires Ω((log T)^(2/3)) expected mistakes, while private prediction allows only O((log log T)²).

Original Abstract

We prove a separation between private online learning and private online prediction for Littlestone classes. Private learning requires Ω((log T)^(2/3)) expected mistakes while private prediction admits O((log log T)²), independent of T.

--- *Auto-collected on 2026-10-07*