From Mixing to Tearing: Graph Decomposition in Decentralized Optimization (GATE Algorithm)

Paper Overview

• Field: Machine Learning / Optimization
• Authors: Kuangyu Ding, Gesualdo Scutari
• Published: 2026-10-02
• arXiv: 2610.03709

Summary

The paper studies the minimization of sums of smooth strongly convex functions over undirected graphs, where each function is held by one agent and communication is restricted to graph neighbors.

Motivation

Existing decentralized methods—whether gossip-based or spanning-tree routing-based—typically use the network to mix or aggregate information in service of *prescribed* local optimization updates. This communication-centered viewpoint lacks a general framework that leverages graph structure to *jointly* design:

1. The linear representation of agreement constraints, 2. The block partitioning of the resulting dual variables, 3. The connected agent clusters that cooperatively solve each block subproblem.

Proposed Framework: GATE

The authors build such a framework from first principles. GATE (Graph Tearing Message Passing) is its first instance, characterized by:

• One optimization variable per edge of the graph;
• Tree-based block partitions of dual variables;
• Per-iteration updates where each agent minimizes the sum of cost-to-go messages from both endpoints of its assigned edge and relaxes the result;
• Messages updated via local minimizations following tree recursion.

GATE-S Surrogate Variant

To reduce per-iteration computation and communication cost, the paper develops GATE-S, which uses:

• Tractable surrogate local models;
• Lightweight message parameterizations.

Theory and Experiments

The authors establish linear convergence rates with explicit dependence on:

• Function regularity;
• Network topology;
• The chosen partition.

These rates reveal the effect of graph decomposition on optimization performance. Numerical experiments validate the theoretical results and evaluate algorithmic efficiency.

*Source: arXiv:2610.03709*