혼합에서 분리(Tearing)로: 메시지 전달을 통한 분산 최적화에서의 그래프 분해

우리는 무방향 그래프 위에서 부드럽고 강하게 볼록한 함수들의 합을 최소화하는 문제를 연구한다. 여기서 각 함수는 하나의 에이전트가 보유하며, 통신은 그래프의 이웃으로 제한된다. 기존의 분산 방법들은 가십(gossip) 기반이든 스패닝 트리(spanning tree) 위에서의 라우팅 기반이든 관계없이, 일반적으로 네트워크를 사용하여 정보를 혼합하거나 집계함으로써 { t prescribed} 로컬 최적화 업데이트가 가능하도록 한다. 이러한 통신 중심적인 관점은 그래프 구조를 활용하여 최적화 하위 문제와 에이전트들이 협력적으로 이를 해결하는 공동 계산 및 통신을 { t jointly} 설계하는 일반적인 프레임워크가 부족하다는 한계가 있다. 우리는 원리(first principles)로부터 이러한 프레임워크를 개발하며, 합의 제약 조건의 선형 표현, 결과로 나오는 쌍대 변수 블록들(공동 최적화), 그리고 할당된 부분 그래프 위에서 각 블록 하위 문제를 협력적으로 해결하는 에이전트들의 연결된 클러스터를 공동으로 설계한다. GATE (Graph-Tearing message passing)는 이 프레임워크의 첫 번째 사례이다: 이는 엣지(edge)마다 하나의 변수와 트리 블록을 사용한다. 각 반복에서, 에이전트들은 양 끝점 비용-투-고 메시지의 합을 최소화하고 그 결과를 완화함으로써 할당된 엣지 변수를 업데이트한다. 메시지들은 트리의 재귀를 따르는 로컬 최소화를 통해 업데이트된다. 반복당 계산 및 통신 비용을 줄이기 위해, 우리는 다루기 쉬운(tractable) 로컬 모델과 경량의 메시지 매개변수화(message parametrizations)를 사용하는 대리 변형인 GATE-S를 개발한다. 우리는 함수 정규성, 네트워크 토폴로지, 그리고 선택된 분할 간의 상호작용에 명시적인 속도를 가진 선형 수렴을 확립하며, 이는 그래프 분해의 효과를 보여준다. 이론적 결과를 검증하고 알고리즘의 효율성을 평가하기 위해 수치 실험을 수행한다.