Stochastic Optimization with Decision-dependent Distributions

Abstract: Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. For example, deployment of a classifier by a learning system, when made public, often causes the population to adapt their attributes in order to increase the likelihood of being favorably labeled---a process called ``gaming''. Even when the population is agnostic to the classifier, the decisions made by the learning system (e.g. loan approval) may inadvertently alter the profile of the population (e.g. credit score). Recent works have identified an intriguing solution concept for such problems as an ``equilibrium'' of a certain game. 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 the 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.

Joint work with Lin Xiao (Facebook AI Research)

optimization and control

Audience: researchers in the discipline

Comments: The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---

One World Optimization seminar

Series comments: Description: Online seminar on optimization and related areas

The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---