Nerve-Skeleton Message Passing for Federated Optimization with Overlapping Parameters

Existing federated learning setups assume either a single global model or a fixed decomposition with one globally shared parameter block and one client-specific private block. In this paper, we study a generalized federated optimization setting where each client optimizes a local coordinate block, and two clients interact only when their blocks overlap. We encode these coordinate overlaps by a graph on clients, called the nerve skeleton. Based on this structure, we propose Nerve-Skeleton Message Passing (NSMP), a two-phase protocol on a spanning tree: a leaf-to-root pass composes reduced objectives by partial minimization, and a root-to-leaf pass reconstructs a joint assignment. We further show that, under the tree-elimination schedule in the paper, NSMP is equivalent to minimizing the joint objective, where the leaf-to-root phase evaluates the optimal objective value, and the root-to-leaf phase recovers a globally optimal assignment. Experiments show that NSMP solves federated optimization with overlapping parameters using only efficient neighbor-to-neighbor message passing.