Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning

arXiv:2605.29148v1 Announce Type: new Abstract: We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. A COLT open problem of Hu and Mehta asks to determine the optimal gap-dependent regret rate for stochastic decision-theoretic online learning under pure event-level differential privacy. For K actions, losses in [0,1], and a unique best action separated from the second-best action by gap Delta_{min}, the known lower bound is of order frac{log K}{min{Delta_{min},arepsilon}}, or equivalently, up to universal constants, of order [ frac{log K}{Delta_{min}}+frac{log K}{arepsilon}. ] We give a horizon-free pure-DP algorithm and prove the explicit regret bound [ operatorname{Reg}T le 1000 dot left(frac{log K}{Delta{min}}+frac{log K}{arepsilon}right) ] for every horizon T. The numerical constant is not optimized. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data-independent random prefix of the previous block. The random prefix converts block regret into a sum, over all prefix lengths, of softmax selection errors. A single entropy-potential argument controls all privacy-dominated large-gap actions at cost log K/arepsilon.

Source: arXiv cs.LG | 2026-05-29