# Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 16 Feb 2025.

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

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Achieving Privacy in the Adversarial Multi-Armed Bandit](https://mlsanity.com/paper/1701.04222/) (2017)
- [Permute-and-Flip: A new mechanism for differentially private selection](https://mlsanity.com/paper/2010.12603/) (2020)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime](https://mlsanity.com/paper/2302.14154/) (2023)

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

- [Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning](https://mlsanity.com/paper/2605.29148/) (2026)

## Abstract (arXiv)

Hu and Mehta (2024) posed an open problem: what is the optimal instance-dependent rate for the stochastic decision-theoretic online learning (with K actions and T rounds) under varepsilon-differential privacy? Before, the best known upper bound and lower bound are Oleft(fraclog KDeltamin + fraclog Klog Tvarepsilonright) and Omegaleft(fraclog KDeltamin + fraclog Kvarepsilonright) (where Deltamin is the gap between the optimal and the second actions). In this paper, we partially address this open problem by having two new results. First, we provide an improved upper bound for this problem Oleft(fraclog KDeltamin + fraclog2Kvarepsilonright), which is T-independent and only has a log dependency in K. Second, to further understand the gap, we introduce the textitdeterministic setting, a weaker setting of this open problem, where the received loss vector is deterministic. At this weaker setting, a direct application of the analysis and algorithms from the original setting still leads to an extra log factor. We conduct a novel analysis which proves upper and lower bounds that match at Theta(fraclog Kvarepsilon).