论文标题
关于数据同质性在多代理非凸随机优化中的作用
On the Role of Data Homogeneity in Multi-Agent Non-convex Stochastic Optimization
论文作者
论文摘要
本文研究了数据同质性在多代理优化中的作用。专注于分散的随机梯度（DSGD）算法，我们表征了瞬态时间，定义为所需的最小迭代次数，以便DSGD可以实现可比的性能与其集中式对应物。当目标函数在不同的代理下的Hessians相同时，我们表明DSGD的瞬态时间为$ O（N^{4/3}/ρ^{8/3} {8/3}）$，用于光滑（可能是非convex）客观函数，其中$ n $是代理的数量，$ρ$是连接图的频谱。没有Hessian同质性假设，这将超过$ O（n^2 /ρ^4）$的限制。我们的分析利用了目标函数连续两次可区分的属性。提出了数值实验，以说明数据同质性与DSGD快速收敛的本质。
This paper studies the role of data homogeneity on multi-agent optimization. Concentrating on the decentralized stochastic gradient (DSGD) algorithm, we characterize the transient time, defined as the minimum number of iterations required such that DSGD can achieve comparable performance as its centralized counterpart. When the Hessians for the objective functions are identical at different agents, we show that the transient time of DSGD is $O( n^{4/3} / ρ^{8/3})$ for smooth (possibly non-convex) objective functions, where $n$ is the number of agents and $ρ$ is the spectral gap of connectivity graph. This is improved over the bound of $O( n^2 / ρ^4 )$ without the Hessian homogeneity assumption. Our analysis leverages a property that the objective function is twice continuously differentiable. Numerical experiments are presented to illustrate the essence of data homogeneity to fast convergence of DSGD.
