Differentially Private Online-to-batch for Smooth Losses

We develop a new reduction that converts any online convex optimization algorithm suffering O( √ T ) regret into an ǫ-differentially private stochastic convex optimization algorithm with the optimal convergence rate Õ(1/ √ T + √ d/ǫT ) on smooth losses in linear time, forming a direct analogy to the classical nonprivate "online-to-batch" conversion. By applying our techniques to more advanced adaptive online algorithms, we produce adaptive differentially private counterparts whose convergence rates depend on apriori unknown variances or parameter norms. Let • be a norm on R d , with dual norm • * defined by g * = sup x ≤1 g, x . By definition, g, x ≤ g * x , (Fenchel-Young's inequality). We make the following assumptions: 2 * . We showed (Lemma 15) that δ t * ≤ (k + 1)(G + H w tx t-1 )t k-1 ≤ (k + 1)(G + DH)t k-1 .