# Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime

arXiv: https://arxiv.org/abs/2302.14154 · HTML: https://mlsanity.com/paper/2302.14154/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 27 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Private optimization in the interpolation regime: faster rates and hardness results](https://mlsanity.com/paper/2210.17070/) (2022)

## Built on by (most cited first, 9 of 9)

- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Private Online Learning via Lazy Algorithms](https://mlsanity.com/paper/2406.03620/) (2024)
- [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy](https://mlsanity.com/paper/2502.10997/) (2025)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Privately Learning Decision Lists and a Differentially Private Winnow](https://mlsanity.com/paper/2602.07370/) (2026)

## Abstract (arXiv)

We consider online learning problems in the realizable setting, where there is a zero-loss solution, and propose new Differentially Private (DP) algorithms that obtain near-optimal regret bounds. For the problem of online prediction from experts, we design new algorithms that obtain near-optimal regret O big( varepsilon-1 log1.5d big) where d is the number of experts. This significantly improves over the best existing regret bounds for the DP non-realizable setting which are O big( varepsilon-1 minbigd, T1/3log dbig big). We also develop an adaptive algorithm for the small-loss setting with regret O(L^starlog d + varepsilon-1 log1.5d) where L^star is the total loss of the best expert. Additionally, we consider DP online convex optimization in the realizable setting and propose an algorithm with near-optimal regret O big(varepsilon-1 d1.5 big), as well as an algorithm for the smooth case with regret O big( varepsilon-2/3 (dT)1/3 big), both significantly improving over existing bounds in the non-realizable regime.