Differentially Private Online-to-Batch for Smooth Losses
This work provides a solution for privacy-preserving machine learning with optimal convergence, addressing the need for differential privacy in online-to-batch conversions, though it is incremental as it builds on existing online optimization techniques.
The paper tackles the problem of converting online convex optimization algorithms into differentially private stochastic convex optimization algorithms, achieving the optimal convergence rate of $ ilde O(1/\sqrt{T} + \sqrt{d}/εT)$ on smooth losses in linear time, analogous to classical non-private methods.
We develop a new reduction that converts any online convex optimization algorithm suffering $O(\sqrt{T})$ regret into an $ε$-differentially private stochastic convex optimization algorithm with the optimal convergence rate $\tilde O(1/\sqrt{T} + \sqrt{d}/εT)$ on smooth losses in linear time, forming a direct analogy to the classical non-private "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.