CS Paper Radar

KKT-Perturbation-Aware Communication for Fully Distributed Online Convex Optimization with Nonseparable Coupling

Zhaoye Pan, Tao Li, Yunjie Guo, Guanpu Chen

cs.LG ·submitted 2026-11-09 03:45 UTC · v1

Abstract

Nonseparable costs and coupled constraints in distributed online convex optimization often arise when system performance and operational constraints depend on the joint configuration of all agents and cannot be decomposed into individual contributions. Such nonseparability leads to fully distributed decision-making with challenging partial local information, where each agent evaluates its local primal-dual update using estimated global information via a local belief of the joint action and the shared Lagrange multiplier to be exchanged with neighbors. While the belief consensus established by prior works ensures no-regret learning, exchanging beliefs comprising full-dimensional primal and dual states at every round imposes a communication overhead that scales with both the joint decision dimension and the network size. Existing event-triggered schemes typically activate communication according to state variation or consensus error. Under nonseparable coupling, however, errors of equal magnitude can produce markedly different perturbations after passing through the KKT operator. We therefore propose a randomized KKT-perturbation-aware communication mechanism, where the triggering of each agent's primal and dual communication channels depends on their impact on the KKT operator. The proposed mechanism transfers the adaptive-sampling principle of coordinate descent from allocating computation across decision blocks to allocating communication across information channels: channels with larger estimated perturbations receive greater priority for refresh. Under standard regularity assumptions, the resulting algorithm achieves $O({T}^{2/3})$ expected static regret and $O({T}^{2/3})$ expected cumulative constraint violation. Numerical experiments demonstrate improved learning and constraint-enforcement performance per transmitted bit over belief consensus baselines.

Closest papers

Nearest neighbours by meaning across the whole index.

Scalar Communication via Random Direction Refreshing for Distributed Optimization

cs.MA ·2026-10-05 ·Mohammadreza Rostami, Solmaz S. Kia
similarity 0.72
Abstract

Distributed optimization over networks requires agents to repeatedly exchange decision variables with their neighbors. When the decision dimension $d$ is large, these exchanges dominate the communication cost, which is critical for bandwidth-constrained agents. Existing remedies quantize or sparsify the exchanged vectors, yet each message still scales with $d$ and the compression error must be compensated by additional states. To address this limitation, we propose a scalar-communication mechanism in which every neighbor message carries a single real number regardless of $d$. Agents regenerate a common random direction from a shared seed, transmit only the inner product of their state with that direction, and act on the resulting rank-one surrogate of their neighbors' states while retaining full local gradients. We develop and analyze the mechanism for an existing continuous-time distributed optimization algorithm. For strongly convex local costs with Lipschitz gradients, we show that the optimizer remains the unique consensus equilibrium, that a fixed direction admits spurious equilibria, and that refreshing the direction at a sufficiently high rate yields exponential mean-square and almost-sure convergence with constant gains and no residual error. The framework admits any isotropic fixed-norm direction distribution, including Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions; all three attain lower fresh-encoding variance than unnormalized Gaussian directions. The effects of the direction distribution and the refresh interval are illustrated in~simulations.

0.53

Budget-Constrained Multi-Consensus Decentralized Gradient Descent

eess.SY math.OC ·2026-10-06 ·Shuyi Ren, Nicol`o Michelusi, Erik G. Larsson
hot direction similarity 0.68
Abstract

We investigate decentralized gradient descent (DGD) with emphasis on efficient communication and computation resource utilization under budget constraints. As a first step toward the broader communication-computation allocation problem, we consider and analyze a \textit{multi-consensus decentralized gradient descent} (mcDGD) scheme, where the number of consensus rounds and the stepsize are allowed to vary across iterations. Building on a unified analytical framework for DGD, we derive finite-time convergence bounds that explicitly characterize the interaction between consensus quality and optimization dynamics. Our analysis requires only convexity of the local objective functions while assuming smoothness and strong convexity of the global objective. The resulting bounds enable a principled consensus-allocation strategy under resource constraints, for which we show that equal allocation of consensus rounds across iterations is optimal under our stepsize rule, up to integer rounding. Numerical experiments corroborate the theoretical findings and demonstrate favorable communication-computation tradeoffs compared with existing multi-consensus decentralized optimization baselines.

0.30

Distributed Consensus, Optimization, and Learning under Communication Constraints

cs.IT cs.DCeess.SP ·2026-11-04 ·Zheng Chen, Nicolò Michelusi, Themistoklis Charalambous, Kaibin Huang
published similarity 0.67
Abstract · 20 pages, 3 figures, to appear in IEEE JSAC

Many modern engineering applications require distributed problem-solving in which multiple nodes in a network cooperate to achieve a common optimization objective. Numerous distributed optimization and learning algorithms rely on consensus-based distributed coordination to ensure network-wide agreement via iterative local interactions. In these algorithms, the accuracy, frequency, and reliability of information exchange among network nodes directly influence system performance, including convergence behavior, training delay, and model accuracy. This tutorial article adopts a bottom-up approach to present the fundamentals of consensus averaging and distributed optimization methods, and highlights the impact of network connectivity, information flow, and communication uncertainty on network cooperation and optimization performance. Building on these theoretical insights, we discuss key design principles for communication-constrained distributed learning across diverse network topologies and review common approaches to communication-efficient learning, particularly in wireless networks. Despite substantial progress, further efforts are needed to bridge the gap between theory and practice and fully realize the potential of cooperative and networked intelligence.

0.32

Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost

cs.AI stat.MLcs.LG ·2026-08-31 ·Zihang Liang, Haochen Zhang, Lingzhou Xue
theory similarity 0.67
Abstract

We study federated online reinforcement learning with linear function approximation. While recent multi-agent reinforcement learning algorithms achieve strong regret guarantees, they typically require sharing raw trajectories. This reliance incurs a communication cost that scales linearly with the number of episodes and violates the privacy constraints of federated settings. To address these limitations, we propose Fed-LSVI, the first provably efficient federated algorithm for online reinforcement learning with linear function approximation in episodic Markov decision processes. By integrating a determinant-based event-triggered synchronization with a stepwise backward update mechanism, Fed-LSVI enables agents to collaboratively learn an optimal policy by exchanging only compressed sufficient statistics. We prove that Fed-LSVI achieves a regret bound of $\widetilde{\mathcal O}(\sqrt{Md^3H^4T})$, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the number of agents, and $T$ is the number of episodes per agent, matching the best-known regret for multi-agent online reinforcement learning with linear function approximation. Moreover, by following the stringent communication and privacy constraints of the federated setting, Fed-LSVI reduces the communication cost to only logarithmic dependence on $T$, representing a significant improvement over prior methods.

0.08

Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always

cs.LG ·2026-10-08 ·Safwan Labbi, Paul Mangold, Eric Moulines
theory similarity 0.66
Abstract

We study personalized federated linear stochastic approximation (LSA), a framework which notably encompass personalized temporal difference learning. In this setting, heterogeneous agents collaborate to solve distinct linear fixed-point equations, each corresponding to an agent-specific learning problem. A central open question in personalized learning is whether a single method can adapt to an unknown level of heterogeneity by converging to each agent's personalized solution in all regimes while achieving a linear speedup in the number of agents when their learning problems are sufficiently similar. We answer this question affirmatively by introducing PF-LSA, a minimalist algorithm that mixes each agent's local stochastic update with the average update across agents, at no additional computational cost relative to standard federated methods. We prove that PF-LSA, achieves best-of-both-worlds guarantees without any prior knowledge on the level of heterogeneity. Our analysis is based on a sharp decomposition of the error into consensus and disagreement components. The consensus error decays rapidly, whereas the disagreement error decays more slowly but becomes negligible in low-heterogeneity regimes.

0.24

NBCLT: Parameter-Agnostic Norm-Ball Clipped Local Training

cs.LG ·2026-10-13 ·Linxuan Pan, Shucheng Yang, Junchi Yang
similarity 0.66
Abstract

Distributed learning with multiple local steps reduces communication but aggravates drift, and its practical performance often depends on carefully tuned hyperparameters under heterogeneous data and communication constraints. At the same time, recent Muon-type optimizers suggest that constraining updates within suitable norm balls provides a simple way to encode geometric priors into optimization. In this work, we propose NBCLT (Norm-Ball Clipped Local Training), a unified local-training framework for both federated learning (FL) and decentralized learning (DL). NBCLT combines a predict-and-correct local update rule with Euclidean projections onto flexible norm balls, thereby performing norm-ball clipping under flexible update geometries while retaining a simple implementation. In FL, its problem-parameter-free regime achieves $\mathcal{O}(ε^{-2})$ communication complexity and $\mathcal{O}(ε^{-4})$ total stochastic-gradient complexity without assuming bounded heterogeneity, when the per-round local-computation budget is scaled appropriately with the horizon. In DL, NBCLT is compatible with both static and time-varying mixing and preserves these accuracy exponents under the analogous computation scaling, up to fixed network constants and an additive initialization cost.

0.20

A Unified Framework for Fair and Personalized Decentralized Learning under Communication Constraints

cs.LG ·2026-08-27 ·Krishnendu S. Tharakan, Carlo Fischione
top venue similarity 0.66
Abstract · accepted for publication in IEEE Transactions on Communications

Decentralized learning systems aim to collaboratively train models across multiple clients without relying on a central coordinator. While decentralization improves scalability, privacy, and robustness, it also exacerbates three fundamental challenges: statistical heterogeneity across clients, fairness in client-level performance, and stringent communication constraints. This raises a natural question: \emph{how fair can decentralized learning be under limited communication?} We address this question by presenting a unified framework for decentralized learning under communication constraints, bringing together graph-based personalization, agnostic fairness, and compressed event-triggered communication. Specifically, we propose a new algorithm DMFL-SQ, a decentralized multi-task learning algorithm that couples personalized model training over a communication graph with an agnostic mixture fairness objective, while reducing communication through sparsification, quantization, and event-triggered synchronization. We establish convergence guarantees for general non-convex objectives and show that DMFL-SQ achieves an $\mathcal{O}(T^{-1/2})$ rate in expected squared Moreau-envelope stationarity despite sparse, quantized, and event-triggered communication. We further derive PAC-Bayes generalization guarantees for the fairness-aware mixture objective. Experiments on CIFAR-10 and the real heterogeneous MUSMET EEG dataset demonstrate that DMFL-SQ substantially reduces communication while maintaining predictive performance and improving fairness across clients. Together, our theoretical and empirical results show that personalization, fairness, and communication efficiency can be jointly achieved in decentralized learning while preserving the dominant convergence rate.

0.35

GUIDE-FBO: Guidance via Uncertainty Intervention and Distributional Exchange for Federated Bayesian Optimization

cs.LG stat.ML ·2026-09-28 ·Jintao Wei, Chenxi Li, Songhao Wang
theory similarity 0.65
Abstract

Federated Bayesian Optimization (FBO) enables distributed agents to collaboratively optimize expensive black-box objectives without sharing raw local observations. However, effective knowledge transfer remains challenging under communication constraints and task heterogeneity. We propose GUIDE-FBO, in which agents exchange compact distributions over the locations of their respective optima inferred from local Gaussian process (GP) posteriors, rather than raw observations, query points, or surrogate parameters. The server merges and reweights these distributional components before returning a subset to each agent. Each agent then constructs a Federated Interventional GP (FI-GP), which preserves the local posterior mean and spatially rescales its covariance for local decision making. For the upper confidence bound (UCB) instantiation, GUIDE-UCB, we prove that any bounded FI-GP uncertainty intervention preserves the leading-order cumulative regret rate of standard GP-UCB. When the transferred distributions place greater support near an optimum than in a suboptimal region, selecting the latter requires greater local posterior uncertainty. Experiments on 12 synthetic benchmarks and three real-world optimization tasks show that GUIDE-FBO remains effective across settings ranging from homogeneous to severely heterogeneous. Ablation results highlight the importance of spatially localized uncertainty intervention, while the communication analysis shows that GUIDE-FBO exchanges only compact distributional messages.

0.16