Research map / Bandits and online learning / Online convex optimization and games
Tracking The Best Expert Privately
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.
Designs differentially private algorithms for prediction with expert advice under dynamic regret (tracking the best expert), with sub-linear bounds for shifting stochastic, oblivious, and adaptive adversaries and a separation between oblivious and adaptive adversaries.
Problem
Differentially private prediction with expert advice where the comparator may switch best expert up to S times (dynamic regret), under stochastic, oblivious, and adaptive adversaries.
Approach
Combines a lazy report-noisy-max private static learner with sparse vector technique to detect distribution shifts for the stochastic case; reduces private dynamic regret to private static regret over a meta-expert class of size (NT)^{2S} for oblivious adversaries; and shows a sharp separation for adaptive adversaries at epsilon ~ sqrt(S/T) via lower bound and a noisy entropic mirror descent algor
Key results
- Shifting stochastic adversary: epsilon-DP algorithm with expected dynamic regret O(sqrt(ST log(NT)) + S log(NT)/epsilon), with a matching-up-to-constants lower bound Omega(sqrt(ST log N) + S log(N/S)/epsilon).
- Oblivious adversary: reduction from static to dynamic regret yields O(sqrt(ST log(NT)) + S T^{1/3} log(T/delta) log(NT)/epsilon^{2/3}), but the construction is inefficient (exponentially many meta-experts).
- Adaptive adversary: any (epsilon,delta)-DP algorithm suffers Omega(T) dynamic regret for epsilon <= sqrt(S/T); an efficient epsilon-DP algorithm achieves O(sqrt(ST) log^{1.5}(NT)/epsilon + S log(NT)/epsilon) for the adaptive case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sparse vector technique to detect shifts and restart the learner | Private dynamic prediction with expert advice · Shifting stochastic adversary | expected dynamic regret: O\left(\sqrt{ST \log(NT)} + \frac{S\log(NT)}{\varepsilon}\right) | Helped |
| Reduce dynamic regret to static regret over a class of meta-experts | Private online learning under oblivious adversaries · Oblivious adversary | expected dynamic regret: O\Big(\sqrt{ST \log(NT)} + \frac{S T^{1/3}\log(T/\delta) \log(NT)}{\varepsilon^{2/3}}\Big) | Helped |
| Add independent Laplace noise to loss vectors before updating the expert distribution | Adaptive dynamic-regret learner · Adaptive adversary | expected dynamic regret: O\left(\frac{\sqrt{ST} \log^{1.5}(NT)}{\varepsilon} + \frac{S \log(NT)}{\varepsilon} \right) | Helped |
| Allow an adaptive adversary instead of an oblivious adversary when ε ≤ √(S/T) | Private dynamic-regret learning · Adaptive adversary | expected dynamic regret: \Omega(T) | Hurt |
Surprising findings
- Under adaptive adversaries, privacy at epsilon <= sqrt(S/T) forces linear dynamic regret, a sharp threshold separating oblivious from adaptive adversaries.
Limitations
- Oblivious-adversary algorithm is computationally inefficient, constructing exponentially many meta-experts.
- Gap between oblivious upper bound and lower bound remains open.
- Adaptive upper bound has extra log factors and is weaker than the oblivious bound.
Experimental setup
Metrics: expected dynamic regret
Baselines: Multiplicative Weights Algorithm Private static-regret algorithms for oblivious adversaries Adaptive-adversary lower bound of Golowich and Livni
Builds on: report-noisy-max mechanism sparse vector technique multiplicative weights algorithm Private online learning with experts (Agarwal and Singh 2017 style) Adaptive regret to dynamic regret connection
Closest papers by meaning
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups (NeurIPS 2024 · similarity 0.90)
- Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.89)
- Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret (ICML 2025 · similarity 0.87)
- Private Online Learning via Lazy Algorithms (NeurIPS 2024 · similarity 0.87)
- Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits (NeurIPS 2026 · similarity 0.87)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.86)
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.