2021/10/02 by Q. Li, Qiang Li, Li, Qiang +2 · 7 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Algorithm #Applied mathematics #Computer science #Function (biology) #Machine Learning and Algorithms #Markov chain #Markov decision process #Markov process #Mathematical optimization #Mathematics #Performative utterance #State (computer science) #State variable #Statistics #Stochastic Gradient Optimization Techniques #math.OC
paper · pdf · doi:10.48550/arxiv.2110.00800
published in arXiv (Cornell University) (Cornell University) · 24 pages, 9 figures
arxiv created 2021/10/02 · openalex publication_date 2021/10/02 · arxiv updated 2021/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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 the learner's and agent's previous states. The said samples are used by the learner to optimize a loss function. This closed loop algorithm is studied as a state-dependent stochastic approximation (SA) algorithm, where we show that it finds a fixed point known as the performative stable solution. Our setting models the unforgetful nature and the reliance on past experiences of agent(s). Our contributions are three-fold. First, we demonstrate that the SA algorithm can be modeled with biased stochastic gradients driven by a controlled Markov chain (MC) whose transition probability is adapted to the learner's state. Second, we present a novel finite-time performance analysis of the state-dependent SA algorithm. We show that the expected squared distance to the performative stable solution decreases as \cal O(1/k), where k is the iteration number. Third, numerical experiments are conducted to verify our findings.