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

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 <PRE_TAG>near-optimal regret</POST_TAG> bounds. For the problem of online prediction from experts, we design new algorithms that obtain <PRE_TAG>near-optimal regret</POST_TAG> {O} big( varepsilon^{-1} log^{1.5}{d} big) where d is the number of experts. This significantly improves over the best existing regret bounds for the DP non-<PRE_TAG>realizable setting</POST_TAG> which are {O} big( varepsilon^{-1} minbig{d, T^{1/3}log dbig} big). We also develop an adaptive algorithm for the small-loss setting with regret O(L^starlog d + varepsilon^{-1} log^{1.5}{d}) 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 <PRE_TAG>near-optimal regret</POST_TAG> O big(varepsilon^{-1} d^{1.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.