Timezone: »
Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
Gautam Kamath · Xingtu Liu · Huanyu Zhang
We study stochastic convex optimization with heavy-tailed data under the constraint of differential privacy.
Most prior work on this problem is restricted to the case where the loss function is Lipschitz.
Instead, as introduced by Wang, Xiao, Devadas, and Xu~\cite{WangXDX20}, we study general convex loss functions with the assumption that the distribution of gradients has bounded $k$-th moments.
We provide improved upper bounds on the excess population risk under approximate differential privacy of $\tilde{O}\left(\sqrt{\frac{d}{n}}+\left(\frac{d}{\epsilon n}\right)^{\frac{k-1}{k}}\right)$ and $\tilde{O}\left(\frac{d}{n}+\left(\frac{d}{\epsilon n}\right)^{\frac{2k-2}{k}}\right)$ for convex and strongly convex loss functions, respectively.
We also prove nearly-matching lower bounds under the constraint of pure differential privacy, giving strong evidence that our bounds are tight.
Author Information
Gautam Kamath (University of Waterloo)
Xingtu Liu (University of Waterloo)
Huanyu Zhang (Facebook)
More from the Same Authors
-
2021 : Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization »
Pranav Subramani · Nicholas Vadivelu · Gautam Kamath -
2021 : Remember What You Want to Forget: Algorithms for Machine Unlearning »
Ayush Sekhari · Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh -
2021 : The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection »
Shubhankar Mohapatra · Shubhankar Mohapatra · Sajin Sasy · Gautam Kamath · Xi He · Om Dipakbhai Thakkar -
2021 : Unbiased Statistical Estimation and Valid Confidence Sets Under Differential Privacy »
Christian Covington · Xi He · James Honaker · Gautam Kamath -
2021 : Wide Network Learning with Differential Privacy »
Huanyu Zhang · Ilya Mironov · Meisam Hejazinia -
2023 Social: Black in AI »
Black in AI Events · Kalesha Bullard · Stacy Fay Hobson · Gautam Kamath -
2023 Poster: Exploring the Limits of Model-Targeted Indiscriminate Data Poisoning Attacks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
2023 Poster: Federated Linear Contextual Bandits with User-level Differential Privacy »
Ruiquan Huang · Huanyu Zhang · Luca Melis · Milan Shen · Meisam Hejazinia · Jing Yang -
2022 Workshop: Updatable Machine Learning »
Ayush Sekhari · Gautam Kamath · Jayadev Acharya -
2022 Workshop: Theory and Practice of Differential Privacy »
Gautam Kamath · Audra McMillan -
2022 Poster: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2022 Oral: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2021 Workshop: Theory and Practice of Differential Privacy »
Rachel Cummings · Gautam Kamath -
2021 : Opening Remarks »
Gautam Kamath · Rachel Cummings -
2021 Poster: PAPRIKA: Private Online False Discovery Rate Control »
Wanrong Zhang · Gautam Kamath · Rachel Cummings -
2021 Spotlight: PAPRIKA: Private Online False Discovery Rate Control »
Wanrong Zhang · Gautam Kamath · Rachel Cummings -
2020 Poster: Privately Learning Markov Random Fields »
Huanyu Zhang · Gautam Kamath · Janardhan Kulkarni · Steven Wu -
2019 Poster: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
2019 Oral: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
2018 Poster: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2018 Oral: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2017 Poster: Priv’IT: Private and Sample Efficient Identity Testing »
Bryan Cai · Constantinos Daskalakis · Gautam Kamath -
2017 Poster: Being Robust (in High Dimensions) Can Be Practical »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Ankur Moitra · Alistair Stewart -
2017 Talk: Priv’IT: Private and Sample Efficient Identity Testing »
Bryan Cai · Constantinos Daskalakis · Gautam Kamath -
2017 Talk: Being Robust (in High Dimensions) Can Be Practical »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Ankur Moitra · Alistair Stewart