분산 최적화 (Distributed Optimization)에서의 오차 피드백 (Error Feedback) 알고리즘에 관한 엄밀한 이론

통신 비용 (Communication costs)은 분산 학습 (Distributed learning) 및 1차 최적화 (First-order optimization)에서 주요한 병목 현상입니다. 이 문제를 완화하기 위한 일반적인 접근 방식은 에이전트 (Agents) 간에 교환되는 그래디언트 (Gradient) 정보를 압축하는 것입니다. 그러나 이러한 압축은 일반적으로 그래디언트 기반 방법론의 수렴 보장 (Convergence guarantees)을 저하시킵니다. 오차 피드백 (Error feedback) 메커니즘은 이 문제에 대해 간단하고 계산 비용이 저렴한 해결책을 제공하지만, 수많은 변형 방식들이 제안되었으며 이들의 상대적 성능은 여전히 명확히 이해되지 않은 상태로 남아 있습니다. 본 논문은 최적의 스텝 사이즈 (Step-size) 선택을 식별하고 각 방법에 맞춤화된 최적의 리아푸노프 함수 (Lyapunov functions)를 구축함으로써, 기존 문헌에 등장하는 두 가지 주요 오차 피드백 알고리즘인 클래식 오차 피드백 (Error Feedback, EF) 방식과 EF21에 대한 엄밀한 수렴 분석을 제공합니다. 연구 결과는 에이전트의 수와 무관하게 성립하며, 단일 에이전트 환경 (Single-agent regime)에서 가능한 알려진 최선의 보장 수치들을 회복합니다.