Gradient Tracking Methods for Distributed Stochastic Optimization Problems with Decision-dependent Distributions

This paper aims to seek the performative stable solution and the stationary point of the distributed stochastic optimization problem with decision-dependent distributions, which is a finite-sum stochastic optimization problem over a network and the distribution depends on the decision variables. For the performative stable solution, we propose a distributed algorithm, DSGTD-GD, which combines the distributed stochastic gradient tracking descent method with the greedy deployment scheme. Under a constant step size policy, we show that the iterates generated by DSGTD-GD converge linearly in expectation to a neighborhood of the performative stable solution. Under a diminishing step size policy, we show that the iterates generated by DSGTD-GD converge to the performative stable solution with a rate of $\mathcal{O}\left(\frac{1}{k^a}\right)$, where $a\in(\frac{1}{2},1]$. Moreover, we establish that the deviation between the averaged iterates of DSGTD-GD and the performative stable solution converges in distribution to a normal random vector. For the stationary point, we propose a distributed algorithm, DSGTD-AG, which combines the distributed stochastic gradient tracking descent method with the adaptive gradient scheme. Under a constant step size, we show that the iterates generated by DSGTD-AG converge to a stationary point with a rate of $\mathcal{O}(\frac{\ln K}{K^{\frac{2}{3}}})$, where $K$ is the number of iterates. The effectiveness of DSGTD-GD and DSGTD-AG is further demonstrated numerically with synthetic and real-world data.

Article

Download

View PDF