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},\varepsilon\}}, $ or equivalently, up to universal c
Source: arXiv cs.LG — read the full report at the original publisher.