Asymptotic Behaviors of Projected Stochastic Approximation: A Jump Diffusion Perspective

In this paper we consider linearly constrained stochastic approximation problems with federated learning as a special case. We propose a loopless projection stochastic approximation algorithm (LPSA) to ensure feasibility by performing the projection with probability p n at the n -th iteration. Considering a specific family of the probability p n and step size η n , we analyze our algorithm from an asymptotic and continuous perspective. Using a novel jump diffusion approximation, we show that the trajectories connecting those properly rescaled last iterates weakly converge to the solution of specific stochastic differential equations (SDEs). By analyzing SDEs, we identify the asymptotic behaviors of LPSA for different choices of ( p n , η n ) . We find the algorithm presents an intriguing asymptotic bias-variance trade-off according to the relative magnitude of p n w.r.t. η n . It brings insights on how to choose appropriate ( p n , η n ) n ≥ 1 to minimize the projection complexity.