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.
Author Information
Jiadong Liang (Peking University)
Yuze Han (Peking University)
Xiang Li (Peking University)
Zhihua Zhang (Peking University)
More from the Same Authors
-
2022 Poster: Personalized Federated Learning towards Communication Efficiency, Robustness and Fairness »
Shiyun Lin · Yuze Han · Xiang Li · Zhihua Zhang -
2022 Poster: Semi-infinitely Constrained Markov Decision Processes »
Liangyu Zhang · Yang Peng · Wenhao Yang · Zhihua Zhang -
2023 Poster: Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis »
Dachao Lin · Yuze Han · Haishan Ye · Zhihua Zhang -
2023 Poster: Entropy-based Training Methods for Scalable Neural Implicit Samplers »
William Luo · Boya Zhang · Zhihua Zhang -
2023 Poster: Enhancing Adversarial Robustness via Score-Based Optimization »
Boya Zhang · William Luo · Zhihua Zhang -
2023 Poster: Diff-Instruct: A Universal Approach for Transferring Knowledge From Pre-trained Diffusion Models »
William Luo · Tianyang Hu · Shifeng Zhang · Jiacheng Sun · Zhenguo Li · Zhihua Zhang -
2022 Spotlight: Personalized Federated Learning towards Communication Efficiency, Robustness and Fairness »
Shiyun Lin · Yuze Han · Xiang Li · Zhihua Zhang -
2022 Spotlight: Lightning Talks 3A-1 »
Shu Ding · Wanxing Chang · Jiyang Guan · Mouxiang Chen · Guan Gui · Yue Tan · Shiyun Lin · Guodong Long · Yuze Han · Wei Wang · Zhen Zhao · Ye Shi · Jian Liang · Chenghao Liu · Lei Qi · Ran He · Jie Ma · Zemin Liu · Xiang Li · Hoang Tuan · Luping Zhou · Zhihua Zhang · Jianling Sun · Jingya Wang · LU LIU · Tianyi Zhou · Lei Wang · Jing Jiang · Yinghuan Shi -
2022 Panel: Panel 2A-3: DPM-Solver: A Fast… & Asymptotic Behaviors of… »
Jiadong Liang · Cheng Lu -
2022 Poster: A Statistical Online Inference Approach in Averaged Stochastic Approximation »
Chuhan Xie · Zhihua Zhang -
2019 Poster: A Regularized Approach to Sparse Optimal Policy in Reinforcement Learning »
Wenhao Yang · Xiang Li · Zhihua Zhang