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 privacy regime ε≪1varepsilon ll 1ε≪1, obtaining Tlogd+T1/3log(d)/ε2/3sqrt{T log d} + T^{1/3} log(d)/varepsilon^{2/3}Tlogd+T1/3log(d)/ε2/3 for…Apple Machine Learning Research