(Nearly) Optimal Algorithm for Private Online Learning

A Google TechTalk, presented by Abhradeep Guha Thakurta, 2020/0814 Full Title: (Nearly) Optimal Algorithm for Private Online Learning, with Applications to Private Empirical Risk Minimization Abstract: In this talk I will review some of the initial results on differentially private online learning, and then discuss potential approaches towards adopting some of the ideas in the context of private federated learning. Concretely, I will show a differentially private algorithm for online convex optimization (OCO) with nearly optimal regret. Along the way, I will revisit some of the classic ideas from OCO like Follow-the-approximate-leader, and from differential privacy like tree aggregation. I will conclude with relating these ideas to differentially private empirical risk minimization (ERM), and show an SGD based private algorithm that does not rely on any privacy amplification theorems, yet achieves optimal excess empirical risk for convex problems. It is going to be a board (on an ipad talk) where I will try to cover most of the necessary background on online learning, and ERM. Bio: Abhradeep Guha Thakurta is a Senior Research Scientist at Google Research - Brain, and an Assistant Professor in the Department of Computer Science at University of California Santa Cruz. His primary research interest is in the intersection of data privacy and machine learning. He focuses on demonstrating, both theoretically and in practice, that privacy enables designing better machine learning algorithms and vice versa. The notion of privacy he is currently interested in is differential privacy. Prior to joining the academia, Abhradeep was Senior Machine Learning at Apple, where he was the primary algorithm designer in deploying differential privacy on iOS 10. The project is possibly one of the largest industrial deployment of differential privacy and has resulted in at least 200+ press articles, and two granted patents. Before Apple, Abhradeep worked as a post-doctoral researcher at Microsoft Research Silicon Valley and Stanford University, and then he worked as a Research Scientist at Yahoo Research. He did his Ph.D. from The Pennsylvania State University with Prof. Adam Smith.