Research map / Bandits and online learning / Online convex optimization and games
Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a differentially private online learner for Littlestone classes with O_d(log T) mistake bound against adaptive adversaries (realizable), and a private agnostic learner with Õ_d(√T) regret via private expert construction.
Problem
Private online learning of generic concept classes with finite Littlestone dimension: prior work achieved only Õ(√T) mistakes against adaptive adversaries in the realizable setting, and no sublinear-regret guarantee was known in the agnostic setting.
Approach
A lazy layer-wise update that delays tournament-style updates until enough collisions accumulate, combined with random permutations and uniform convergence over the class, makes the oblivious-adversary random-permutation argument valid against adaptive adversaries; for agnostic settings, privately constructed SOA-based experts are fed to a private OPE algorithm, with sanitization via a binary mech
Key results
- Realizable setting: (ε,δ)-DP online learner with expected mistake bound O(2^{2^{O(d)}}(log T + log(1/δ))/ε) against adaptive adversaries, closing the gap to the optimal log T dependence.
- Agnostic setting: DP learner with expected regret Õ(d√T/ε) + Õ_d(T^{1/3}/ε^{2/3}) against adaptive adversaries; oblivious adversary gives O(√(dT log T)) + Õ_d(T^{1/3}/ε^{2/3}).
- A simple proper agnostic learner attains Õ(T^{3/4}) regret via sanitization of H^label and a sample complexity improvement for sanitizers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private learner instead of the prior adaptive-adversary approach | Private realizable online learning · Realizable, adaptive adversary | mistake bound: \tilde{O}_{d}(\sqrt{T}) -> O_{d}(2^{2^{O(d)}}(\log T + \log (1/\delta)) / \varepsilon) | Helped |
| Use the proposed private learner for general Littlestone classes | Private agnostic online learning · Agnostic, adaptive adversary | regret: \tilde{O}_d(T^{3/4}) -> \tilde{O}(d\sqrt{T}/\varepsilon) + \tilde{O}_d(T^{1/3}/\varepsilon^{2/3}) | Helped |
Surprising findings
- The agnostic regret for oblivious adversaries matches the best known non-private constructive rate when ε ≥ Ω̃(1/T^{1/4}), a 'privacy is free' phenomenon.
Limitations
- Double exponential dependence on the Littlestone dimension d.
- Algorithms are improper; proper private online learning with log T mistakes is open.
- Agnostic proper learner has suboptimal Õ(T^{3/4}) regret; horizon T assumed known (doubling trick raises realizable bound to log^2 T).
Experimental setup
Metrics: expected mistake bound expected regret
Baselines: Golowich and Livni 2021
Builds on: Golowich and Livni 2021 private online learning Standard Optimal Algorithm (Littlestone) AboveThreshold private histogram private online prediction from experts
Closest papers by meaning
- The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.91)
- Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.89)
- Revisiting Differentially Private Algorithms for Decentralized Online Learning (ICML 2025 · similarity 0.87)
- Private Online Learning via Lazy Algorithms (NeurIPS 2024 · similarity 0.87)
- On the Learnability of Distribution Classes with Adaptive Adversaries (ICML 2025 · similarity 0.87)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.