Timezone: »

 
Poster
Asymptotic Behaviors of Projected Stochastic Approximation: A Jump Diffusion Perspective
Jiadong Liang · Yuze Han · Xiang Li · Zhihua Zhang

@
In this paper, we consider linearly constrained stochastic approximation problems with federated learning (FL) as a special case. We propose a stochastic approximation algorithm named by LPSA with probabilistic projections to ensure feasibility so that projections are performed with probability $p_n$ at the $n$-th iteration. Considering a specific family of the probability $p_n$ and step size $\eta_n$, we analyze our algorithm from an asymptotic and continuous perspective. Using a novel jump diffusion approximation, we show that the trajectories consisting of properly rescaled last iterates weakly converge to the solution of specific SDEs. By analyzing the SDEs, we identify the asymptotic behaviors of LPSA for different choices of $(p_n, \eta_n)$. We find the algorithm presents an intriguing asymptotic bias-variance trade-off according to the relative magnitude of $p_n$ w.r.t. $\eta_n$. It provides insights on how to choose appropriate $\{(p_n, \eta_n)\}_{n \geq 1}$ to minimize the projection complexity.
Keywords: federated learning · Bias-variance Tradeoff · Asymptotic Normal · Diffusion Approximation · Loopless Algorithm · Asymptotic Biased · Jump Diffusion

Author Information

Jiadong Liang (Peking University)
Yuze Han (Peking University)
Xiang Li (Peking University)
Zhihua Zhang (Peking University)

More from the Same Authors