ABSTRACT:

Stochastic optimization in the online setting often involves data distributions that change in reaction to the decision variables. This is the case for example when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction have identified an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision induces. Continuing this line of work, we show that typical stochastic algorithms — originally designed for static problems — can be applied directly for finding such equilibria with little loss in efficiency. The reason is simple to explain: the main consequence of the distributional shift is that it corrupts algorithms with a bias that decays linearly with the distance to the solution. Using this perspective, we obtain sharp convergence guarantees for popular algorithms, such as stochastic gradient, clipped gradient, proximal point, and dual averaging methods, along with their accelerated and proximal variants. This is joint work with Dmitriy Drusvyatskiy.

BIO:

Lin Xiao is a Research Scientist at Facebook AI Research (FAIR) in Seattle, Washington. He received PhD in Aeronautics and Astronautics from Stanford University, and was a postdoctoral fellow in the Center for the Mathematics of Information at California Institute of Technology. He spent 14 great years as a Researcher at Microsoft Research before joining Facebook in 2020. His current research interests include theory and algorithms for large-scale optimization and machine learning, reinforcement learning, and parallel and distributed computing.

 Hosted by Professor Quanquan Gu