State Dependent Performative Prediction with Stochastic Approximation

Qiang Li, Hoi-To Wai
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:3164-3186, 2022.

Abstract

This paper studies the performative prediction problem which optimizes a stochastic loss function with data distribution that depends on the decision variable. We consider a setting where the agent(s) provides samples adapted to both the learner’s and agent’s previous states. The samples are then used by the learner to update his/her state to optimize a loss function. Such closed loop update dynamics is studied as a state dependent stochastic approximation (SA) algorithm, which is shown to find a fixed point known as the performative stable solution. Our setting captures the unforgetful nature and reliance on past experiences of agents. Our contributions are three-fold. First, we present a framework for state dependent performative prediction with biased stochastic gradients driven by a controlled Markov chain whose transition probability depends on the learner’s state. Second, we present a new finite-time performance analysis of the SA algorithm. We show that the expected squared distance to the performative stable solution decreases as O(1/k), where k is the iteration number. Third, numerical experiments verify our findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-li22c, title = { State Dependent Performative Prediction with Stochastic Approximation }, author = {Li, Qiang and Wai, Hoi-To}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {3164--3186}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/li22c/li22c.pdf}, url = {https://proceedings.mlr.press/v151/li22c.html}, abstract = { This paper studies the performative prediction problem which optimizes a stochastic loss function with data distribution that depends on the decision variable. We consider a setting where the agent(s) provides samples adapted to both the learner’s and agent’s previous states. The samples are then used by the learner to update his/her state to optimize a loss function. Such closed loop update dynamics is studied as a state dependent stochastic approximation (SA) algorithm, which is shown to find a fixed point known as the performative stable solution. Our setting captures the unforgetful nature and reliance on past experiences of agents. Our contributions are three-fold. First, we present a framework for state dependent performative prediction with biased stochastic gradients driven by a controlled Markov chain whose transition probability depends on the learner’s state. Second, we present a new finite-time performance analysis of the SA algorithm. We show that the expected squared distance to the performative stable solution decreases as O(1/k), where k is the iteration number. Third, numerical experiments verify our findings. } }
Endnote
%0 Conference Paper %T State Dependent Performative Prediction with Stochastic Approximation %A Qiang Li %A Hoi-To Wai %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-li22c %I PMLR %P 3164--3186 %U https://proceedings.mlr.press/v151/li22c.html %V 151 %X This paper studies the performative prediction problem which optimizes a stochastic loss function with data distribution that depends on the decision variable. We consider a setting where the agent(s) provides samples adapted to both the learner’s and agent’s previous states. The samples are then used by the learner to update his/her state to optimize a loss function. Such closed loop update dynamics is studied as a state dependent stochastic approximation (SA) algorithm, which is shown to find a fixed point known as the performative stable solution. Our setting captures the unforgetful nature and reliance on past experiences of agents. Our contributions are three-fold. First, we present a framework for state dependent performative prediction with biased stochastic gradients driven by a controlled Markov chain whose transition probability depends on the learner’s state. Second, we present a new finite-time performance analysis of the SA algorithm. We show that the expected squared distance to the performative stable solution decreases as O(1/k), where k is the iteration number. Third, numerical experiments verify our findings.
APA
Li, Q. & Wai, H.. (2022). State Dependent Performative Prediction with Stochastic Approximation . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:3164-3186 Available from https://proceedings.mlr.press/v151/li22c.html.

Related Material