The increasing ubiquity of large-scale infrastructures for surveillance and data analysis has made understanding the impact of privacy a pressing priority. We propose a framework for studying a fundamental query complexity versus privacy tradeoff in sequential learning. The central question is: how can one perform learning in such a manner that makes sure that an overseeing adversary cannot obtain the learned model by observing the queries. We will examine two formulations of the model (deterministic and Bayesian), and in both cases establish matching upper and lower bounds on the optimal query complexity, for a given level of privacy guarantees. The analysis will exploit on some essential combinatorial as well as information theoretic structures of the problem, which we will also discuss.
Bio: Kuang Xu is an Associate Professor of Operations, Information and Technology at Stanford Graduate School of Business, and Associate Professor by courtesy with the Electrical Engineering Department, Stanford University. Born in Suzhou, China, he received the B.S. degree in Electrical Engineering (2009) from the University of Illinois at Urbana-Champaign, and the Ph.D. degree in Electrical Engineering and Computer Science (2014) from the Massachusetts Institute of Technology. His research focuses on understanding fundamental properties and design principles of large-scale stochastic systems using tools from probability theory and optimization, with applications in queueing networks, privacy and machine learning. He is a recipient of the First Place in the INFORMS George E. Nicholson Student Paper Competition (2011), the Best Paper Award, as well as the Kenneth C. Sevcik Outstanding Student Paper Award at ACM SIGMETRICS (2013), and the ACM SIGMETRICS Rising Star Research Award (2020). He currently serves as an Associate Editor for Operations Research.