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

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).