Distributed Local Two-Time-Scale Stochastic Approximation

In this paper, we consider a distributed variant of the popular two-time-scale stochastic approximation, where there are a group of agents communicating with a centralized coordinator. The goal of the agents is to find the roots of two coupling operators composed of the local operators at the agents. Such a framework models many practical problems in different areas, including those in federated learning and reinforcement learning. Over a series of time epoch, each agent runs a number of local two-time-scale stochastic approximation steps based on its own data, whose results are then aggregated at the centralized coordinator. Our main contribution is to characterize the finite-time performance of the local two-time-scale stochastic approximation, where we provide explicit formulas for the rate of this method.