Core-Halo Decomposition: Decentralizing Large-Scale Fixed-Point Problems

Authors: Haixiang, Yang Xu, Jiefu Zhang et al.

arXiv · PDF

Summary

The authors tackle decentralized solving of large fixed-point equations (like those in reinforcement learning or optimization) by splitting the problem across agents. Standard "strict decomposition" assigns each agent disjoint variables, but this creates structural bias because updating one block often depends on variables in other blocks. They propose Core-Halo decomposition: each agent owns a "core" (writes updates) but reads from an overlapping "halo" (neighbors' variables), eliminating bias while keeping parallelism.

Main takeaways:

• Strict decomposition (each agent owns disjoint variables and only uses those) changes the underlying fixed-point operator and creates bias that can't be fixed by more data or smaller stepsizes
• Core-Halo decomposition lets agents write to their own core but read from an overlapping halo, faithfully implementing the original centralized problem in a decentralized setting
• They characterize when strict decomposition fails via a "Bellman closure" condition and prove a bias lower bound
• Experiments across multiple settings show Core-Halo achieves near-centralized performance while retaining parallel speedup
• The method applies to reinforcement learning, consensus optimization, and other fixed-point problems

Relevance

Not directly related to my persona/midtraining work—this is about distributed computation and fixed-point iteration, not about language model behavior or conditioning.

Abstract

arXiv:2605.08681v1 Announce Type: new Abstract: We study solving large-scale fixed-point equation (x^\star=\bar F(x^\star)) with decomposition. Standard strict decomposition assigns each agent a disjoint block and evaluates updates using only owned coordinates. For most operators, however, a block update may depend on variables outside the block. Truncating these dependencies by strict decomposition changes the mean operator and creates structural bias that cannot be removed by more samples, smaller stepsizes, or additional consensus. We therefore propose Core-Halo decomposition, which separates write ownership from read-only evaluation context: each agent updates its own core and reads from an overlapping halo. By aligning the Core-Halo decomposition with the block-dependence structure of $\bar F$, the original fixed-point problem can be implemented faithfully in a decentralized multi-agent system. We further characterize the fundamental obstruction faced by strict decomposition through a Bellman closure condition and a blockwise bias lower bound, showing that local-only updates can alter the original fixed-point operator. Finally, we conduct extensive experiments across a range of application settings, and demonstrate that Core-Halo achieves near-centralized performance while retaining the parallelism benefits of decentralization.