Private Streaming SCO in $\ell_p$ geometry with Applications in High Dimensional Online Decision Making

Yuxuan Han, Zhicong Liang, Zhipeng Liang, Yang Wang, Yuan Yao, Jiheng Zhang
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:8249-8279, 2022.

Abstract

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. Numerous algorithms have been developed to achieve optimal excess risks in different $\ell_p$ norm geometries, but none of the existing ones can be adapted to the streaming and continual release setting. We propose a private variant of the Frank-Wolfe algorithm with recursive gradients for variance reduction to update and reveal the parameters upon each data. Combined with the adaptive DP analysis, our algorithm achieves the first optimal excess risk in linear time in the case $1

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-han22d, title = {Private Streaming {SCO} in $\ell_p$ geometry with Applications in High Dimensional Online Decision Making}, author = {Han, Yuxuan and Liang, Zhicong and Liang, Zhipeng and Wang, Yang and Yao, Yuan and Zhang, Jiheng}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {8249--8279}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/han22d/han22d.pdf}, url = {https://proceedings.mlr.press/v162/han22d.html}, abstract = {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. Numerous algorithms have been developed to achieve optimal excess risks in different $\ell_p$ norm geometries, but none of the existing ones can be adapted to the streaming and continual release setting. We propose a private variant of the Frank-Wolfe algorithm with recursive gradients for variance reduction to update and reveal the parameters upon each data. Combined with the adaptive DP analysis, our algorithm achieves the first optimal excess risk in linear time in the case $1
Endnote
%0 Conference Paper %T Private Streaming SCO in $\ell_p$ geometry with Applications in High Dimensional Online Decision Making %A Yuxuan Han %A Zhicong Liang %A Zhipeng Liang %A Yang Wang %A Yuan Yao %A Jiheng Zhang %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-han22d %I PMLR %P 8249--8279 %U https://proceedings.mlr.press/v162/han22d.html %V 162 %X 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. Numerous algorithms have been developed to achieve optimal excess risks in different $\ell_p$ norm geometries, but none of the existing ones can be adapted to the streaming and continual release setting. We propose a private variant of the Frank-Wolfe algorithm with recursive gradients for variance reduction to update and reveal the parameters upon each data. Combined with the adaptive DP analysis, our algorithm achieves the first optimal excess risk in linear time in the case $1
APA
Han, Y., Liang, Z., Liang, Z., Wang, Y., Yao, Y. & Zhang, J.. (2022). Private Streaming SCO in $\ell_p$ geometry with Applications in High Dimensional Online Decision Making. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:8249-8279 Available from https://proceedings.mlr.press/v162/han22d.html.

Related Material