분산형 확률적 최적화 (Decentralized stochastic optimization)는 에이전트들이 오직 이웃들과만 통신하며 중앙 조정자가 필요하지 않은 네트워크 기반의 대규모 학습을 위한 근본적인 패러다임입니다. 강한 볼록 (Strongly convex) 문제의 경우, 통신 효율성은 주로 조건수 (Condition number) $\kappa=L/\mu$와 네트워크 스펙트럼 간극 (Network spectral gap) $1-\beta$에 의해 결정됩니다. 결정론적 분산 방법 (Deterministic decentralized methods)은 가속화된 $\sqrt{\kappa}$ 및 $1/\sqrt{1-\beta}$ 의존성을 동시에 달성할 수 있지만, 기존의 확률적 방법 중 두 가지 개선 사항을 동시에 달성하는 방법은 없습니다. 본 논문에서는 Nesterov 유형의 원-쌍대 외삽 (Primal--dual extrapolation)과 다회차 고속 가십 평균화 (Multi-round fast gossip averaging)를 결합한 분산형 확률적 알고리즘인 Multi-Gossip Accelerated DSGD (MG-ADSGD)를 제안합니다. 핵심 아이디어는 가십 깊이 (Gossip depth)를 미니 배치 크기 (Mini-batch size)와 결합하여, 추가적인 통신 라운드가 합의 정확도 (Consensus accuracy)를 향상시키는 동시에 경사 분산 (Gradient variance)을 줄이도록 하는 것입니다. 우리는 MG-ADSGD가 다음과 같은 통신 복잡도 (Communication complexity)를 달성함을 보여줍니다:

[ \widetilde{\mathcal O}!\left( \frac{{\sigma}^2}{{\mu}n\epsilon}\log\frac{1}{\epsilon} + \sqrt{\frac{\kappa}{1-\beta}}\log\frac{1}{\epsilon} \right), ]

여기서 $\epsilon$은 목표 정확도 (Target accuracy), $n$은 노드 수, $\sigma^2$은 경사 분산 (Gradient variance)을 나타냅니다. 우리가 알고 있는 바로는, 이 경계값은 $\epsilon$과 무관한 로그 인자 (Logarithmic factors)를 제외하면 현재 사용 가능한 분산형 확률적 강한 볼록 최적화 (Decentralized stochastic strongly convex optimization)에 대해 가장 우수한 통신 복잡도를 제공합니다.