Research map / Bandits and online learning / Online convex optimization and games
Private Online Learning via Lazy Algorithms
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.
Proposes L2P, a transformation that converts lazy online learning algorithms (with a per-round likelihood-ratio structure) into differentially private ones via batched, correlated-sampling switching, yielding improved DP-OPE and DP-OCO regret and a low-switching lower bound.
Problem
Differentially private online prediction from experts (DP-OPE) and differentially private online convex optimization (DP-OCO) with high-privacy (small epsilon) regimes where prior regret rates are suboptimal.
Approach
A transformation that switches models via correlated sampling where each loss affects the switching probability only in its own round (using a parallel sequence of auxiliary models y_t), combined with batching whose regret cost is analyzed as T B^2 eta^2, so that fewer fake switches are needed for privacy.
Key results
- DP-OPE regret sqrt(T log d) + T^{1/3} log(d)/eps^{2/3}, improving over prior T^{1/3} log(d)/eps in the high-dimensional regime.
- DP-OCO regret sqrt(T) + T^{1/3} sqrt(d)/eps^{2/3}, improving over prior sqrt(T) + T^{1/3} sqrt(d)/eps + T^{3/8} sqrt(d)/eps^{3/4}.
- Lower bound Omega(sqrt(T) + T^{1/3}/eps^{2/3}) for DP-OPE for low-switching private algorithms under concentrated DP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the prior DP-OPE approach with L2P applied to multiplicative weights | DP-OPE · DP-OPE | regret: \sqrt{T \log d } + \frac{ \min \{\sqrt{d} \, ,\, T^{1/3}\} \log d}{\varepsilon} -> O\left( \sqrt{T \log d}+\frac{T^{1/3} | Helped |
| Replace the prior DP-OCO approach with L2P applied to regularized multiplicative weights | DP-OCO · DP-OCO | regret: \min\left\{\frac{d^{1/4}\sqrt{T}}{\sqrt{\varepsilon}} ,\sqrt{T} + \frac{T^{1/3} \sqrt{d} }{\varepsilon}+\frac{T^{3/8}\sq | Helped |
| Use L2P to transform a lazy online learning algorithm into a private algorithm | Online learning algorithms satisfying the stated assumption · Online learning | regret: O(B/\eta) -> O(T B^2 \eta^2) | Helped |
Surprising findings
- Low-switching private algorithms are provably limited: the lower bound matches the upper bound for this family, suggesting new techniques beyond switching are needed.
- For high-dimensional DP-OPE, the L2P rate with eps >= T^{-1/4} matches the non-private regret, versus eps >= T^{-1/6} for prior work.
Limitations
- Lower bound holds only for the natural family of low-switching algorithms, not all private algorithms.
- DP-OCO normalized rate sqrt(d)/(eps T)^{2/3} is not known to be optimal; the binary-tree approach is better in the low-dimensional regime.
- Results are for oblivious adversaries; adaptive-adversary privacy is only mentioned in a footnote.
Experimental setup
Metrics: regret privacy parameter epsilon
Baselines: shrinking dartboard DP-OPE DP-FTRL for DP-OCO regularized follow-the-perturbed-leader DP-OCO lazy regularized multiplicative weights DP-OCO
Builds on: shrinking dartboard regularized multiplicative weights low-switching private online learning (Yu et al.-style correlated sampling) advanced composition
Closest papers by meaning
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.91)
- Revisiting Differentially Private Algorithms for Decentralized Online Learning (ICML 2025 · similarity 0.88)
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups (NeurIPS 2024 · similarity 0.88)
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.87)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.87)
- Tracking The Best Expert Privately (ICML 2025 · 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.