2021/10/02 by Q. Li, Li, Qiang, Hoi-To Wai +1 · 4 citations
Computer Science · Decision Sciences · #Stochastic Gradient Optimization Techniques #Advanced Bandit Algorithms Research #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2110.00800
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.