Differentially private (DP) stochastic convex optimization (SCO) is ubiquitous in trustworthy machine learning algorithm design. This paper studies the DP-SCO problem with streaming data sampled from a distribution and arrives sequentially. We also consider the continual release model where parameters related to private information are updated and released upon each new data, often known as the online algorithms. Despite that numerous algorithms have been developed to achieve the optimal excess risks in different $\ell_p$ norm geometries, yet none of the existing ones can be adapted to the streaming and continual release setting. To address such a challenge as the online convex optimization with privacy protection, we propose a private variant of online Frank-Wolfe algorithm with recursive gradients for variance reduction to update and reveal the parameters upon each data. Combined with the adaptive differential privacy analysis, our online algorithm achieves in linear time the optimal excess risk when $1<p\leq 2$ and the state-of-the-art excess risk meeting the non-private lower ones when $2<p\leq\infty$. Our algorithm can also be extended to the case $p=1$ to achieve nearly dimension-independent excess risk. While previous variance reduction results on recursive gradient have theoretical guarantee only in the independent and identically distributed sample setting, we establish such a guarantee in a non-stationary setting. To demonstrate the virtues of our method, we design the first DP algorithm for high-dimensional generalized linear bandits with logarithmic regret. Comparative experiments with a variety of DP-SCO and DP-Bandit algorithms exhibit the efficacy and utility of the proposed algorithms.
翻译:不同的私人(DP) 相异 convex 优化( SCO) 在可信赖的机器学习算法设计中是无处不在的。 本文研究DP- SCO问题, 包括从发行中采集流数据, 并按顺序到达 。 我们还考虑持续发布模式, 与私人信息有关的参数更新并发布于每个新数据, 通常称为在线算法 。 尽管已经开发了许多算法, 以在不同的 $\ ell_ p$ 标准地理座标中达到最佳超额风险, 但现有的算法都无法适应流动和连续发布设置。 为了应对在线流动流动和连续发布算法的优化等挑战, 我们提议了一个名为 Frank- Wolfe 的在线 Frank- Wolfe 算法的私人变式, 以递增递减变量更新和显示每项数据的参数 。 结合适应差异的隐私分析, 我们的在线算法在线上实现了最佳超额超额超额超额风险, 当2美元时, 我们的轨算法的递减法的递增率值的比值将显示我们之前的比值 。