Research map / Bandits and online learning / Online convex optimization and games
Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements
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 POMER, a differentially private online convex optimization algorithm that samples from strongly log-concave Gibbs densities with an ℓ2 regularizer, achieving improved regret without smoothness and also improved lazy-OCO switching bounds.
Problem
Differentially private online convex optimization (DP-OCO) and lazy OCO with limited switches; prior best DP regret bounds required smoothness or had suboptimal dimension dependence for non-smooth Lipschitz losses.
Approach
Sample the played point from a Gibbs density proportional to exp(-β·cumulative loss − λ/2·||x||²), so the ℓ2 regularizer makes stability controlled by λ via Log-Sobolev concentration rather than by the volume-dependent temperature β; combined with rejection-sampled switching this gives regret Õ(√T + √d T^{1/3}/ε) without smoothness.
Key results
- Theorem 4.4 gives DP-OCO regret Õ(GD√T + GD·(√d T^{1/3}/ε + T^{3/8}/ε^{3/4})) for Lipschitz non-smooth losses, improving on prior best bounds in all practical privacy regimes (ε ≥ dT^{-1/3}).
- Theorem 4.5 gives lazy OCO regret Õ(GD√T + GD√d·T/S) with expected switches at most S for Lipschitz losses, improving the known switching-budget bounds for smooth and non-smooth losses in some regimes.
- The stability term in the regret analysis becomes independent of the temperature β once an ℓ2 regularizer is added, removing the √d factor from the leading-order dimension dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add Euclidean regularization to the sampling log-density | POMER for DP-OCO · DP-OCO, Lipschitz convex losses | regret: \tilde{O}\left(\sqrt{T} + \frac{dT^{1/3}}{\varepsilon}\right) -> \tilde{O}\left(\sqrt{T} + \frac{\sqrt{d}T^{1/3}}{\varep | Helped |
| use POMER without requiring smoothness | POMER · DP-OCO, non-smooth losses | regret: \tilde{O}\left(\sqrt{dT} + \frac{dT^{1/3}}{\varepsilon}\right) -> \tilde{O}\left(\sqrt{T} + \frac{\sqrt{d}T^{1/3}}{\vare | Helped |
| use POMER with a switching budget | POMER · Lazy OCO, Lipschitz convex losses | regret: \tilde{O}\left(\sqrt{dT} + \frac{dT}{S}\right) -> GD\sqrt{2T} + 16GD\log(T)\cdot\sqrt{d}\cdot\frac{T}{S} + 13GD | Helped |
Surprising findings
- Adding an ℓ2 regularizer to the sampling density yields optimal regret even in the non-private setting, a simple modification not previously known to achieve this.
Limitations
- Analysis for strongly convex (lazy OCO) setting does not yield improvements with the current techniques.
- Regret for very small epsilon regime (ε between T^{-1/6} and d^{2/3}T^{-1/6}) retains an extra √d T^{3/8}/ε^{3/4} term.
- Requires oblivious adversaries; privacy guarantee does not, but regret bounds rely on obliviousness.
Experimental setup
Metrics: expected regret bound privacy (epsilon, delta) expected number of switches
Baselines: Agarwal et al. 2023 Asi et al. 2023 Kairouz et al. 2021 Sherman & Koren 2023 Anava et al. 2015 Chen et al. 2020
Builds on: Private Shrinking Dartboard Agarwal et al. 2023 DP-OCO Gopi et al. 2022 Gibbs sampling for DP stochastic optimization Ganesh et al. 2023
Closest papers by meaning
- Private Online Learning via Lazy Algorithms (NeurIPS 2024 · similarity 0.91)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.90)
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.89)
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.89)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
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.