CS Paper Radar

Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus

Shao-An Yin

cs.AI math.OCcs.GTcs.LGcs.MA ·submitted 2026-09-07 03:19 UTC · v2
published

Abstract

Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms. Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy. As a result, different initializations can lead to different GNEs, including non-variational ones. We establish convergence under sufficient conditions using an input-to-state stability (ISS) framework.

Comment
6 pages, 1 figure. Accepted to CDC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers

cs.LG cs.AIcs.GTcs.MA+1 ·2026-08-29 ·Shao-An Yin, Mingyi Hong, Nicola Elia
published similarity 0.66
Abstract · 6 pages, 3 figures. Published in the 2026 American Control Conference (ACC), pp. 3633--3638

Recent machine learning research has increasingly focused on equilibrium analysis in non-cooperative games rather than solely on optimal solutions. Many such problems involve shared constraints and can be formulated as Generalized Nash Equilibrium Problems (GNEPs). For strongly monotone games, existing methods compute consensus-based variational GNEs (v-GNEs) by exchanging Lagrange multipliers. We propose a fully distributed continuous-time algorithm for shared linear equality constraints that converges without multiplier exchange and reaches any GNE, reducing communication overhead and improving privacy. Discrete-time schemes are also provided, and the method is validated on a multi-robot placement task.

0.67

Provably Safe Decentralized Contingency MPC under State-Only Information and Limited Sensing for Nonlinear Multi-agent Systems

cs.MA math.OCcs.ROeess.SY ·2026-08-31 ·Max Studt, Georg Schildbach
similarity 0.61
Abstract

This paper considers decentralized contingency MPC for multi-agent control under a state-only information pattern, with particular focus on limited sensing and plug-and-play operation. The objective is to retain recursive feasibility, safety, and Lyapunov-type convergence while reducing conservatism in local interaction handling. The framework relies on agent-wise fallback regions (safe sets) in which a feasible contingency maneuver to a safe equilibrium is always available. A novel safe-set update mechanism is introduced that supports less conservative decentralized interaction while preserving the underlying guarantees. This, in turn, enables memory-free local interaction and finite sensing ranges without requiring agents to reconstruct the exact neighbor geometry. The resulting scheme remains fully decentralized and preserves the shared-first-input contingency MPC structure. Theoretical guarantees and simulation results illustrate the effectiveness of the approach in dense multi-agent scenarios.

0.24

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.61
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

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

cs.LG ·2026-11-09 ·Zhaoye Pan, Tao Li, Yunjie Guo, Guanpu Chen
similarity 0.60
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.

0.15

Byzantine-Robust Muon: Resilient Momentum Orthogonalization for Distributed Learning

cs.LG ·2026-11-09 ·Grigory Malinovsky, Yury Demidovich, Peter Richtárik
similarity 0.59
Abstract · 51 pages

Optimization methods, including the Muon optimizer based on the Linear Minimization Oracle (LMO) and momentum orthogonalization, have shown strong empirical performance in large-scale and distributed learning, yet their robustness to adversarial behavior and data heterogeneity is not well understood. We study these methods within a unified first-order trust-region framework and analyze Muon-based updates with robust aggregation for Byzantine-robust distributed and federated learning. Our analysis does not rely on the i.i.d. assumption and introduces a non-Euclidean notion of heterogeneity consistent with the trust-region geometry. Under this framework, we establish convergence guarantees for both general non-convex and star-convex objectives. Our results provide a theoretical characterization of Byzantine-robust Muon-based optimization, with an additive heterogeneity error floor consistent with known impossibility results, under explicit aggregation assumptions. Under an explicit additive oracle-error condition, the guarantees also cover inexact orthogonalization, with the non-convex Byzantine terms in the bound's numerator unchanged but a smaller progress denominator. In simulated federated training with ResNet-18 and ViT-Tiny on CIFAR-10, additional image benchmarks, and a 38M-parameter byte-level language model on TinyStories, the tested Muon configuration attains higher attacked accuracy (lower perplexity) than the tested SGD and normalized-SGD configurations, and than sign updates on CIFAR-10. Fixed-honest controls further show a substantial RFA advantage over averaging under a bounded RFA-query attack, higher attacked accuracy for Muon-NS than tensorwise Euclidean normalization from shared checkpoints, and lower held-out TinyStories perplexity than a tuned AdamW baseline.

0.16

Distributed Optimization Involving Non-Lipschitzian, Linear Composite Functions: Unified Algorithm Design and Convergence Analysis

cs.GT ·2026-11-05 ·Liang Ran, Huaqing Li, Lifeng Zheng, Jun Li, Run Tang
similarity 0.58
Abstract · 15 pages; 3 figures

This paper formulates a generic distributed nonsmooth optimization problem subject to edge-based equality constraints, local inequality constraints characterized by general convex functions, as well as globally coupling constraints including affine equality and nonlinear inequality. The terminal goal is to minimize the sum of local non-differentiable convex functions and proximable nonsmooth convex composite terms attached to linear operators, over networked multi-agent systems. This formulated framework not only applies in complex practical problems but also reduces to existing distributed optimization structures. To cope with technical issues caused by local linear mappings, potential multiple nonsmooth functions and coupling nonlinear constraints, we first derive a new local first-order condition, and further present a novel fully distributed optimization algorithm based on variable decompositions and proximal operators. Specifically, the proposed algorithm allows each agent to update states via local information exchange and through {locally fixed step-sizes}, and to find inexact solutions of subproblems without loss of convergence speed. In contrast to existing tailor-made algorithms for the bounded gradients of objective functions or affine constraints, our algorithm is capable of solving more practical cases involving general convex functions and nonlinear constraints. Under mild assumptions, the convergence rate $o(1/k)$ in terms of the optimality and successive-difference metrics is achieved, by constructing the equivalent variational inequalities of the proposed algorithm. Finally, numerical experiments on practical application problems illustrate the theoretical results.

0.26

Distributed Model Predictive Control for Optimal Consensus of Constrained Heterogeneous Multi-agent Systems

eess.SY ·2026-08-28 ·Nan Bai, Tao Liu, Qishao Wang, Zhisheng Duan
similarity 0.58
Abstract

This paper investigates the distributed optimal consensus control problem of constrained heterogeneous multi-agent systems within a model predictive control (MPC) scheme. Both the control input sequence and the dynamically feasible consensus equilibrium are optimized simultaneously within the proposed MPC framework to improve consensus performance, yielding a coupled constrained optimization problem at each prediction time. A distributed primal--dual algorithm is developed to solve the resulting optimization problem, and locally verifiable conditions are derived to guarantee its convergence. Furthermore, sufficient terminal conditions are established for the proposed MPC framework to guarantee the recursive feasibility and asymptotic consensus of the closed-loop heterogeneous multi-agent systems. Finally, numerical simulations verify the effectiveness of the proposed approach.

0.31

Toward a decentralized design framework for discrete-time distributed algorithms via their emergent dynamics

eess.SY ·2026-10-21 ·Jinwook Heo, Hyungbo Shim, Jin Gyu Lee
similarity 0.58
Abstract

This paper develops a procedure for designing discrete-time distributed algorithms to achieve a desired collective behavior. Each agent combines its node and coupling updates at every iteration, in either explicit or implicit form. For this structure, we derive necessary and sufficient conditions on the local parameters for realizing a desired continuous-time blended dynamics. These conditions yield a decentralized procedure for computing the parameters. A Tikhonov-type approximation result relates the resulting agent trajectories to the blended dynamics on a rescaled time axis. Under a stability condition imposed only on the blended dynamics, we further establish uniform-in-time approximation bounds. We also characterize the trade-off between approximation accuracy and the iteration count guaranteed by these bounds. The framework is illustrated through four applications in distributed computation and estimation.

0.20