Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime
In collaboration with Tel Aviv University
AuthorsHilal Asi*, Vitaly Feldman*, Tomer Koren*, Kunal Talwar*
In collaboration with Tel Aviv University
AuthorsHilal Asi*, Vitaly Feldman*, Tomer Koren*, Kunal Talwar*
*=Equal Contributors
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 near-optimal regret bounds. For the problem of online prediction from experts, we design new algorithms that obtain near-optimal regret where is the number of experts. This significantly improves over the best existing regret bounds for the DP non-realizable setting which are . We also develop an adaptive algorithm for the small-loss setting with regret where is the total loss of the best expert. Additionally, we consider DP online convex optimization in the realizable setting and propose an algorithm with near-optimal regret , as well as an algorithm for the smooth case with regret , both significantly improving over existing bounds in the non-realizable regime.
November 20, 2024research area Methods and Algorithms, research area Privacyconference NeurIPS
We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO). We propose a new transformation that transforms lazy online learning algorithms into private algorithms. We apply our transformation for differentially private OPE and OCO using existing lazy algorithms for these problems. Our final algorithms obtain regret which significantly improves the regret in the high...
June 20, 2023research area Methods and Algorithms, research area Privacyconference COLT
*= Equal Contributors
Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algorithms for this problem that improve over the regret bounds of the best existing algorithms for non-adaptive adversaries. For approximate differential privacy, our algorithms achieve regret bounds of for...