Overview

Distributed optimization studies how multiple machines, clients, or robots can solve a shared problem using local data and limited communication. Common approaches include consensus and decentralized gradient methods, local or federated SGD, ADMM and primal-dual algorithms, and asynchronous updates; communication can be reduced through compression, quantization, or less frequent synchronization. These methods support settings from large-model training and statistical learning to robot coordination, energy systems, and networked control. A central challenge is balancing communication and computation against convergence when data and worker speeds differ, messages are delayed, or participants may be unreliable or adversarial.

Latest papers

99 papers9 papers in the last four weeks, down 10% on the four weeks before. 0.1% of all new papers.

Nov 12, 2026

Fair and Efficient Distributed EV Charging Coordination Using Threshold Cryptography and Machine Learning

Distributed coordination of electric vehicle (EV) charging with the alternating direction method of multipliers (ADMM) keeps EV constraints private but assumes that every participant follows the algorithm. This assumption fails in practice, where a biased operator or a man-in-the-middle (MITM) attacker can send inconsistent signals to different EVs, and compromised EVs can deviate from their prescribed updates. We first prove that attacks by such arbitrarily malicious, i.e., Byzantine, participants do not prevent convergence and therefore remain undetected, and derive the most damaging attack in closed form. We then propose a framework that combines a threshold-signed broadcast with upload recomputation, which detects every deviation without false alarms at linear instead of quadratic communication cost. To keep the optimization running, each affected EV recovers locally with a certified, fleet-aware machine learning price forecast, and we prove that the optimization remains convergent with a recovery cost bounded by the shape of the forecast error. Simulation results with real-world load, price, and charging data show that a biased operator raises the annual cost of disadvantaged EVs by 132.7% and lowers that of advantaged EVs by 49.3% without changing the aggregate load, whereas the defense limits all cost changes to 2.6%. An external MITM attacker raises the cost of its victims by 57.6%, the peak load by 5.8%, and the grid cost by 15.8%, whereas the defense keeps them within 1.1%, 0.2%, and 0.3% of benign operation. With up to 70% of the EVs attacked, the recovery converges in at least 97.8% of the runs.
Nov 9, 2026

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

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(T2/3)O({T}^{2/3}) expected static regret and O(T2/3)O({T}^{2/3}) expected cumulative constraint violation. Numerical experiments demonstrate improved learning and constraint-enforcement performance per transmitted bit over belief consensus baselines.
Nov 6, 2026

DisMUSE: An Efficient Distributed Singular-Spectrum-Based Optimization Approach with Theoretical Convergence Guarantee

In recent years, singular-spectrum-based optimizers have attracted increasing attention due to their ability to preserve the matrix structure of neural network gradients, thereby enabling geometry-aware optimization. However, most singular-spectrum-based (SSB) approaches remain centralized, limiting their use in distributed learning infrastructures that exploit massive parallelism. Distributed SSB optimization is still at an early stage, with open questions about convergence guarantees and communication efficiency. To fill this gap, we propose the Distributed Momentum-based Spectral Estimator (DisMUSE), an efficient distributed SSB optimization framework for both data-center and federated settings. Using Muon-style exact orthogonalized momentum as the spectral update, DisMUSE integrates a recursive variance-reduced momentum estimator and achieves an O((KT)−1/3)O((KT)^{-1/3}) convergence rate, where KK and TT denote the number of nodes and local iterations per node, respectively. This rate matches the best-known rates for variance-reduced nonconvex distributed optimization. Building on this variance-reduced framework, we study two extensions. First, our DisMUSE method with finite Newton-Schulz (NS) iterations preserves the same convergence order under a uniform normalized support-spectrum condition, up to a multiplicative factor. Second, we develop a communication-efficient variant based on low-rank (LR) momentum transmission and quantify the error it introduces to the stationarity bound, characterizing the trade-off between accuracy and communication cost.
Nov 5, 2026

Projection-Free Gradient Tracking Neurodynamic for Distributed Nonnegative Sparse Optimization

This paper proposes a continuous-time, projection-free neurodynamic system based on gradient tracking for distributed nonnegative sparse optimization. Unlike traditional methods, our approach avoids projecting states onto the feasible set. Instead, it employs gradient tracking to estimate average gradients under heterogeneous costs, coupling primal and dual dynamics such that feasibility and sparsity emerge naturally from the equilibrium conditions. The system ensures unique solutions through a locally Lipschitz vector field and guarantees that every equilibrium corresponds to an exact KKT point. We establish rigorous convergence guarantees for convex objectives through three distinct analytical layers. These include a centralized kernel rate, a computable distributed rate derived from Jacobian analysis without restrictive stability assumptions, and a global exponential stability proof based on Lur'e system theory. Our analysis quantitatively separates these layers, revealing that the convergence rate is primarily limited by graph sparsity and remains robust to variations in momentum time scales. Numerical experiments on strongly convex quadratic problems validate the theoretical rates, demonstrate effective active set recovery, and show that the system maintains stable tail convergence rates even under strong local heterogeneity.
Nov 5, 2026

A Bilevel Neurodynamic Approach for Distributed SCAD-Regularized Sparse Least Squares

This paper proposes a bilevel particle swarm optimization (PSO)-neurodynamic method for solving the distributed sparse least-squares problem regularized by the smoothly clipped absolute deviation (SCAD) penalty to global optimality. The SCAD penalty is nonsmooth and nonconvex, so existing distributed neurodynamic methods have not been extended to it directly. Through two-time-scale singular perturbation analysis, a rigorous full-trajectory convergence theory with explicit convergence rates is established for the inner collaborative multi-agent neurodynamic system without requiring the second-order sufficient condition. A theory-guided inner-outer collaborative optimization framework is further developed, in which a red-light green-light sensitivity mechanism is embedded in the outer PSO search to enhance global search while concentrating computational effort on the SCAD shape parameters, thereby improving recovery accuracy and computational efficiency. Simulation results on four sparse-recovery scenarios demonstrate that the proposed method accurately recovers the true sparsity pattern and achieves faster convergence and lower relative error than competing neurodynamic methods.
Oct 30, 2026

Distributed Grid Search for Hyperparameter Tuning

The performance of many distributed optimization algorithms over peer-to-peer networks strongly depends on the choice of their hyperparameters. However, existing selection rules often require global quantities, yield conservative choices, or are tied to specific algorithms and hyperparameters. We propose Distributed Grid Search (D-GS), a consensus-based search method that evaluates and selects hyperparameter configurations across the network, requiring only the ability to run the tuned algorithm and evaluate local gradients. We also propose a zoom-in variant, Distributed Zoom Grid Search (D-ZGS), which improves empirical performance at a reduced cost. We prove that both methods terminate in finite time with all agents holding the same hyperparameter configuration, and quantify the (sub)optimality of this configuration. Numerical experiments on linear and logistic regression show that D-GS closely matches a centralized reference and that tuning and deployment cost a fraction of deploying algorithms with hyperparameters tuned using theoretical results.
Oct 29, 2026

Dobb: Shard-Local Preconditioning in Block-Diagonal Eigenbases

Training language models whose parameters and optimizer state exceed a single node's memory requires sharding these tensors across devices. Under tensor parallelism (TP) or fully sharded data parallelism (FSDP), matrix-aware optimizers such as Muon introduce communication to perform global matrix operations across shards. We propose Dobb (Distributed Optimizer with Block-diagonal Eigenbases), a matrix-aware optimizer designed to compute updates locally within parameter shards. Dobb approximates the input-activation second moment with diagonal blocks and tracks a complete basis within each block. It projects momentum into these bases, applies sign normalization to the coefficients, and reconstructs the update. When each block lies within one shard under TP or FSDP, Dobb applies its matrix update locally, requiring no communication beyond data-parallel synchronization of the activation second moments. We benchmark Dobb against Dion, a distributed matrix-aware optimizer designed to retain the benefits of orthonormalized updates while reducing communication. On GPT-2 XL (1.56B parameters), Dobb with 16 blocks reaches a validation loss of 2.476, compared with 2.511 for Dion at rank fraction 1/16. Under FSDP on 32 H100 GPUs, Dobb reduces the amortized optimizer-call time from 124.1 ms for Dion to 9.2 ms.
Oct 21, 2026

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Parallel AI agents can produce useful local edits yet degrade a shared solution when their edits are combined. We model this coordination problem as discrete block optimization with an exactly evaluable objective and a known dependency graph. Independent sets certify compatible edits whose verified gains, measured against the same current solution, add exactly. A coordinator constructs a safe compatible candidate and can also evaluate interacting edits to capture favorable interactions. We prove that an optimal fractional coloring yields a merger that preserves a 1/χf(G)1/χ_f(G) fraction of the total verified local improvement, where χf(G)χ_f(G) is the graph's fractional chromatic number. This guarantee is tight among mergers that select a subset of the same proposals. Under conditional local-improvement guarantees and a block error-bound condition, repeated collaboration converges geometrically in the objective gap. The rate separates task structure, agent allocation, and computation cost, yielding a linear program for agent assignment and an explicit time-cost trade-off. Code-repair experiments show that verified merging resolves conflicts between individually useful edits that cause naive merging to fail. On larger conflict-free tasks, parallel agents reduce modeled completion time at higher input-token-equivalent cost. On three public road networks, fractional integration retains 922 units of verified graph-cut improvement across 90 paired runs. For route-search agents sharing exclusive access to vehicle routes, fractional scheduling reduces measured wall time by a median of 15% across twelve paired runs, with route-cost changes varying across runs.
Oct 20, 2026

On Johnson-Lindenstrauss Transforms for Byzantine-Robust Optimization

The growing scale of data and models in machine learning calls for efficient optimization methods. Distributed optimization addresses this challenge, with compression mechanisms helping to reduce communication costs. A classical tool for dimensionality reduction is the Johnson-Lindenstrauss (JL) transform, which is simple to implement and offers strong geometric guarantees. In particular, JL transforms approximately preserve inner products and pairwise distances between vectors with high probability. In this paper, we exploit this property in Byzantine-robust optimization, where worker messages are weighted according to their alignment with a trusted reference gradient. We further support our theoretical findings with experimental results.
Oct 17, 2026

Low-Bit Distributed Constrained Optimization with Application to Optimal Scheduling and Allocation

This paper proposes a distributed resource allocation algorithm in which each agent communicates only the sign of its local cost gradient, a single bit per directed link per iteration. The algorithm is based on Laplacian-gradient dynamics and preserves the equality (demand) constraint at every iterate, guaranteeing anytime feasibility irrespective of termination time. First, we provide a complete Lyapunov-based convergence analysis for the fixed-step-size regime: the iterates are shown to enter, in at most O(1/\varepsilon^2) iterations, a neighborhood of the optimizer whose radius scales as O(τ) in the decision variable and O(τ^2) in the cost residual, where ττ is the step-size. Crucially, the step-size bound is a time-invariant network constant (depending only on the graph Laplacian spectrum and the cost curvature bounds), so no adaptive tuning is required. Second, we characterize the invariant set under B-connected, weight-balanced digraphs, strictly weaker than the all-time connectivity and doubly-stochastic weights assumed in most prior work, and show that any odd, sign-preserving nonlinearity yields the same invariant-set and descent structure, with the single-bit protocol being the extreme communication-minimizing instance of a broader nonlinear class. Third, we address local box constraints via smooth penalty relaxation and quantify explicitly how the penalty weight interacts with the step-size bound and the optimality gap. Simulations on economic dispatch (1000 generators) and CPU scheduling (500 servers) demonstrate that the single-bit protocol achieves 5-60 times reduction in total communication cost relative to multi-bit baselines, at the price of a tunable and explicitly bounded optimality gap. A diminishing step-size schedule is shown empirically to eliminate this gap; its formal convergence analysis is identified as an open problem.
Oct 17, 2026

Adding Heavy-Ball Momentum to Distributed Constrained Optimization for Energy Resource Management Subject to Time-Delays and Quantization

This paper studies a hybrid discrete-time signed gradient-consensus method with heavy-ball momentum, paired communication delays, and fixed logarithmic quantization. The method preserves the aggregate supply-demand equality at every iteration. For a static connected undirected graph and bounded delays, a Lyapunov-Krasovskii analysis establishes practical stability by isolating the discontinuous quantization error as an additive disturbance and closing a computable invariant-sublevel argument. The resulting ergodic residual bound is quadratic in the quantization resolution, and exact convergence to the smooth penalized equality-constrained optimizer is recovered in the unquantized case. For delay-free unquantized quadratic costs, an exact modal analysis identifies the heavy-ball stability region and optimal parameters, with the predicted rate validated on a fixed sparse network. A reproducible delayed experiment reports all constants and a certificate whose guaranteed steady-state level lies below the reported initialization. A separate mixed generator-battery experiment exercises the signed update directly. Finite smooth penalties approximate, but do not generally enforce, the local box constraints exactly.
Oct 11, 2026

Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning

We study federated learning from continuously arriving data: each client samples from its own distribution, these distributions drift over time, and the server must track the minimizer of the clients' weighted average loss. Clients are not alike as they collect data at different rates, with different noise, and change at different speeds. The main question is how much history should each one keep? A single shared window must serve every client at once, and so makes a fast-changing client carry the sampling noise of a slow, nearly stationary one. We give each client a memory of its own, sized to that client's noise, arrival rate, and drift, and refresh it by restarted accelerated method that starts from a common point. The tracking error is then bounded by R(∑mwm3/2 σmγm/λm)2/3,R\left(\sum_m w_m^{3/2}\,σ_m\sqrt{γ_m/λ_m}\right)^{2/3}, for clients with weight wmw_m, noise σmσ_m, arrival rate λmλ_m, and drift rate γmγ_m on a domain of diameter RR. This is never worse than what any common window can achieve, and strictly better whenever noise and drift are spread unevenly across clients. A lower bound that puts different groups of clients on different drift clocks shows this quantity is the right one. The two bounds agree up to a constant whenever the clients occupy boundedly many refresh scales, and in general differ only by the sixth root of the number of scales. Experiments show the gain comes from the memory rather than from the solver: it persists across accelerated, stochastic-gradient, and one-step methods, and against a separately tuned common-memory baseline.
Oct 10, 2026

Data-Topology Compatibility Enables Personalization in Decentralized Learning

Decentralized learning must balance collaboration with personalization across heterogeneous agents. This paper studies when cooperation can support statistically coherent groups of personalized models. We show that data-topology compatibility enables robust orbit-wise personalization: when local objectives and communication topology have (approximately) compatible automorphisms, agents within an orbit share (approximately) equal limiting distributions, while different orbits remain distinct without explicit personalization. This creates a new intermediate regime between global consensus and independent local learning. Under exact data-topology compatibility, as a reference system, we decompose the stochastic learning dynamics into orbit-level and transverse components, derive a necessary and sufficient stability criterion for distributional synchronization, and characterize the orbit-structured stationary law. Modelling an approximate data-topology compatible system as an ε\varepsilon-perturbed reference system, we prove the introduced errors have uniform-in-time and stationary O(ε)O(\varepsilon) bounds in 2-Wasserstein distance. We also prove sufficient conditions for lower stationary average excess risk than both independent local training and the best single shared parameter. Experiments on synthetic data, MNIST, and CIFAR-10 are in full agreement with the theory. The code is available at https://github.com/Veronicaaa1/orbit-personalization.
Oct 5, 2026

Scalar Communication via Random Direction Refreshing for Distributed Optimization

Distributed optimization over networks requires agents to repeatedly exchange decision variables with their neighbors. When the decision dimension dd 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 dd 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 dd. 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.
Oct 4, 2026

Distributed Learning of αα-Potential Functions in Strategic Multi-agent Systems

We study the problem of computing the tightest αα-potential approximation of a general-sum game over continuous action spaces, within a prescribed class of potential functions and when each player has access only to its own utility function. The difficulty is twofold: the approximation error involves a worst-case search over an infinite set of unilateral deviations, and the required utility information is distributed across players. For a linear-in-parameters potential class, we use an exact finite-tuple reformulation that separates the problem into a global outer search over deviation tuples and distributed convex inner problems. We develop a primal--dual inner oracle tailored to this structure and establish a uniform one-sided accuracy guarantee. This oracle can be combined with global outer search to obtain an end-to-end guarantee on the outer optimization error. We also develop a projected zeroth-order outer method as a computationally lighter alternative for higher-dimensional problems. Numerical experiments illustrate the accuracy--computation tradeoff between the two outer-search methods and show that the proposed optimization framework can improve upon analytical αα-potential constructions.
Oct 4, 2026

Population Scaling or Data Dilution? Dynamics of Local Topology Evolution in Decentralized Learning

Scaling decentralized learning changes not only the number of clients NN, but also the dynamics of information propagation and consensus. We argue that the effect of increasing NN cannot be understood in isolation, because data allocation, topology-dependent mixing, and communication capacity may change simultaneously. We study these coupled effects on CIFAR-10 with N∈{10,50,100,200}N\in\{10,50,100,200\}, comparing a degree-two Ring, a Static Random graph, and Local-First Heuristic Evolution (LFHE), a locally adaptive topology process based on friend-of-friend discovery. The Ring provides an analytically transparent failure mode: its Metropolis spectral gap decays as Θ(N−2)Θ(N^{-2}), implying progressively slower contraction of model disagreement as the population grows. Experiments show that holding the nominal local dataset size fixed substantially reduces the apparent population penalty observed when a fixed total dataset is divided among more clients. The remaining degradation depends strongly on communication structure: Ring enters a high-disagreement regime, whereas Static Random and LFHE remain close to consensus. Increasing LFHE's degree threshold further improves accuracy and consensus, but at a substantially higher model-transmission cost. These results show that decentralized scaling is governed by coupled learning and communication dynamics, rather than by the number of clients alone.
Sep 30, 2026

Robustifying Asynchronous SGD via Soft Throttling

Asynchronous SGD is a popular algorithm for distributed learning where each client's gradient update is applied on arrival. This leads to a speed-up, but also an increased vulnerability to attacks, as fast clients can dominate the total update. We introduce Throttle, a Byzantine-robust generalization of asynchronous SGD where the key idea is to exponentially down-weight updates from faster clients by a factor qq. Both asynchronous SGD (q=1q=1) and synchronous Byzantine-robust SGD (q→∞q\to\infty) correspond to specific settings of Throttle. We provide a theoretical analysis of the convergence rate and validate the robustness to attacks both theoretically and empirically. Remarkably, our experiments show that this down-weighting mechanism can also improve performance over standard asynchronous SGD even in the non-Byzantine setting.
Sep 28, 2026

MegaGraph: Towards Efficient Training of Large-Scale Graph Transformers with Automated Hybrid Parallelism

Graph Transformers (GTs) offer superior representation capabilities by overcoming the depth limitations and over-smoothing issues of traditional Graph Neural Networks (GNNs). However, scaling GTs to large graphs poses critical bottlenecks. Specifically, the attention score matrix and its associated topology-aware bias matrix jointly incur significant per-layer memory overhead, and heavy graph embedding layers result in severe workload imbalances. These characteristics are unique to GT training and are not addressed by parallelism techniques designed for either conventional GNNs or Transformers, making a dedicated solution necessary. This paper introduces MegaGraph, the first automated hybrid parallelism framework designed for efficient GT training. MegaGraph designs three specialized strategies, namely graph-aware context parallelism, heterogeneous pipeline parallelism, and hybrid data parallelism, to support efficient training on large-scale graphs. However, coordinating these three parallelism strategies yields an exponentially large configuration space. To address this complexity, an automatic search engine leverages precise cost models via a Profile - Model - Search workflow to identify the optimal parallelism configuration. Evaluations demonstrate that MegaGraph enables training on large-scale graphs where state-of-the-art baselines fail due to out-of-memory (OOM) errors. The framework reduces per-device peak memory by up to 77.8% and achieves up to 4.51×\times training speedup while maintaining model accuracy.
Sep 22, 2026

Resource-Efficient Distributed Recursive Gaussian Processes

Gaussian processes (GPs) provide a flexible framework for learning unknown functions from noisy measurements while quantifying predictive uncertainty, making them well suited for estimation in multi-agent systems. However, when measurements are collected by multiple agents, maintaining a unified GP model without centralized processing requires efficient distributed algorithms that can operate using local measurements and communication with neighboring agents. In this work, we develop two distributed recursive GP (RGP) algorithms for multi-output GP regression: ADMM-RGP and PDMM-RGP. We analyze the stability and convergence of both algorithms and develop parameter selection strategies to accelerate convergence, thus reducing the communication burden. The proposed methods are validated on a real-world multi-output wind dataset, and their convergence behavior is examined across communication graphs with varying connectivity. Numerical experiments demonstrate that ADMM-RGP and PDMM-RGP can significantly reduce communication relative to the state of the art, while maintaining comparable estimation accuracy and network-wide consensus.
Sep 16, 2026

Revisiting Distributed Sign-Based Variance Reduction

Sign-based methods reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction methods fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both nonconvex stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. As a result, we can obtain the convergence rates of O(d/K+d(a/(nK))1/3)O(\sqrt{d/K}+\sqrt d (a/(nK))^{1/3}) for the ℓ1\ell_1-norm and O(a/K+a/(nK)1/3)O(\sqrt{a/K}+\sqrt a/(nK)^{1/3}) for the ℓ2\ell_2-norm. Here, KK is the iteration number, nn is the number of workers, dd is the dimension, and a=1+ωa=1+ω, with ωω denoting the compressor's relative variance. For finite-sum problems with MM components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are O(M+daMε−2)O(M+d\sqrt{aM}ε^{-2}) and O(M+aM epsilon−2)O(M+a\sqrt M\ epsilon^{-2}) for ℓ1\ell_1 and ℓ2\ell_2 gradient norms at most εε, matching the corresponding bounds in centralized settings.
Sep 15, 2026

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.
Aug 29, 2026

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

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.
Aug 26, 2026

Distributed Training using an Intelligent Network

Distributed training across a wide area network (WAN) is challenging, as continuous parameter exchange by islands of compute is constrained by limited bandwidth, high latency, and uneven topology. We propose making the network an active participant in training. On the systems side, such networks should leverage (i) multicast technology to replicate outbound traffic and (ii) in-line FPGAs to aggregate inbound traffic, to ease egress and ingress bottlenecks. These technologies are used for training across workers within a data center, but this paper extends them to the WAN. On the algorithms side, we develop an optimization framework that produces rich synchronization schedules (namely, rotating cliques of islands) around the underlying network topology and these technologies, to maximize information exchange. Finally, we illustrate this on a nine-city topology modeled on the DoubleZero network, a live programmable WAN equipped with both technologies, and show how the optimal schedules shift with the network's capabilities. Together, these can narrow the gap to the gold standard of colocated training.
Aug 5, 2026

SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant

Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, rely on high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines a bounded Kashin representation, data-independent coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: (1) a Flat Randomized Response variant that is unbiased and, for a fixed codebook bit-width, frame redundancy, and dimension-independent Kashin level, achieves reconstruction MSE that scales linearly with the ambient dimension dd, while using only ⌈log⁡2N⌉+b\lceil \log_2 N \rceil + b bits per message. Here, N=Θ(d)N = Θ(d) denotes the frame size in the Kashin transform and bb is the codebook bit-width; and (2) a metric-aware truncated-Laplace variant that removes the exponential dependence on bit-width at the cost of a non-vanishing bias. We also derive a convex uniform-surrogate codebook objective whose worst-case codebook-dependent upper bound improves from O(4b)O(4^b) to O(2b)O(2^b). Experiments on synthetic regression, Fashion-MNIST, and CIFAR-10 compare the per-message privacy-utility and uplink-communication trade-offs of SSTQ with those of established baselines, demonstrating favorable utility and communication efficiency.
Aug 3, 2026

A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems

This paper studies the distributed online control problem over a network of linear time-invariant (LTI) systems in the presence of adversarial disturbances and time-varying convex costs. The network cost is characterized by the summation of local cost functions, where each local function is sequentially revealed only to the corresponding agent. The goal of each agent is to generate a control sequence, using only local observations and neighbor communication, that competes with the best {\it centralized} linear policy in hindsight. We extend the recently proposed Online Spectral Control framework from the centralized setting to the distributed setting. In particular, each agent applies a spectral controller obtained by convolving past disturbances with the leading eigenvectors of a Hankel matrix, while the controller parameters are updated through a distributed online gradient descent step over the local surrogate costs. We formulate this problem this problem as a {\it regret} minimization problem based on the spectral parameterization, and under standard assumptions, we establish a sublinear regret bound of O(Tpoly(log⁡T)γ3)O(\frac{\sqrt{T}\text{poly}(\log T)}{γ^3}), where TT is the time horizon and γγ denotes the stability margin. The resulting bound also captures the dependence on the network size and connectivity.
Aug 2, 2026

Using Non-Lipschitz Signum-based Functions for Distributed Optimization and Machine Learning: Trade-off Between Con-vergence Rate and Optimality Gap

In recent years, the prevalence of large-scale data-sets and the demand for sophisti-cated learning models have necessitated the development of efficient distributed ma-chine learning (ML) solutions. Convergence speed is a critical factor influencing the practicality and effectiveness of these distributed frameworks. Recently, non-Lipschitz continuous optimization algorithms have been proposed to improve the slow conver-gence rate of the existing linear solutions. The use of signum-based functions is previ-ously considered in consensus and control literature to reach fast convergence in the prescribed time and also to provide robust algorithms to noisy/outlier data. However, as shown in this work, these algorithms lead to an optimality gap and steady-state re-sidual of the objective function in discrete-time setup. This motivates us to investigate the distributed optimization and ML algorithms in terms of trade-off between conver-gence rate and optimality gap. In this direction, we specifically consider the distributed regression problem and check its convergence rate by applying both linear and non-Lipschitz signum-based functions. We check our distributed regression approach by extensive simulations. Our results show that although adopting signum-based func-tions may give faster convergence, it results in large optimality gaps. The findings pre-sented in this paper may contribute to and advance the ongoing discourse of similar distributed algorithms, e.g., for distributed constrained optimization and distributed estimation.
Aug 2, 2026

Data-Driven Pinball-Loss Selection for Vertically Distributed Elastic-Net SVMs

The pinball-loss support vector machine is robust, but its asymmetry parameter is usually fixed in advance. We propose a data-driven elastic-net support vector machine that learns simplex-constrained weights over candidate pinball losses while retaining one classifier. The weighted loss is equivalent to a pinball loss with a data-dependent effective parameter. An empirical oracle inequality shows that, when weight regularization and simplex truncation vanish, the classifier objective at a global minimizer does not exceed that of the best fixed candidate; otherwise, the excess is explicitly bounded. For high-dimensional data, we develop a column-partitioned variable-splitting solver. It converges with a best-iterate O(1/T)O(1/T) squared-step residual rate. Under common initialization and global parameters, any column partition produces, in exact arithmetic, the same iterates and solution as centralized training. Experiments assess predictive behavior, numerical equivalence, and multi-process scalability.
Jul 30, 2026

First-order Constrained Trilevel Optimization Over Distributed Networks for Robust Coreset Selection

With the rapid advancement of the Internet of Things (IoT), massive amounts of data are generated across distributed edge networks. Training models on full data incurs significant computational overhead and storage bottlenecks, rendering coreset selection a critical paradigm. Furthermore, given the privacy-sensitive nature of local data and the escalating demand for model robustness in real-world deployments, developing an effective distributed optimization framework for robust coreset selection is vital, yet remains largely unexplored. To this end, this work first characterizes the hierarchical dependencies among coreset selection, robust optimization, and distributed learning, and formulates the distributed robust coreset selection as a trilevel optimization problem with level-wise constraints. Furthermore, to effectively solve the trilevel problem in a distributed manner, the Federated First-order Constrained Trilevel Optimization (F2^2CTO) is proposed, which synergistically integrates a hierarchical composite value-function reformulation and a distributed alternating projected gradient algorithm. To the best of our knowledge, F2^2CTO is the first method developed for distributed robust coreset selection, as well as the first distributed optimization approach for trilevel optimization problems with level-wise constraints. Additionally, we prove that the proposed method achieves a non-asymptotic convergence rate of O(ε−3/2)\mathcal{O}(ε^{-3/2}) for finding an εε-stationary point. Extensive empirical evaluations on reliable continual learning demonstrate the effectiveness and efficiency of the proposed F2^2CTO.
Jul 28, 2026

Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.
Jul 23, 2026

Distributed Model-Based Diffusion For Scalable Multi-Robot Trajectory Optimization

Trajectory optimization for multi-robot systems remains a critical challenge, particularly when navigating highly non-convex, non-linear, and non-differentiable environments. While Model-Based Diffusion (MBD) has recently emerged as a promising sampling-based optimization paradigm for single-robot trajectory generation, extending it to multi-robot systems results in a centralized, high-dimensional inference problem that (i) suffers from poor sample efficiency due to the curse of dimensionality and (ii) requires global access to all robots' dynamics, constraints, and objectives. To address this, we propose Distributed Model-Based Diffusion (DMBD), a distributed server-robot method that decomposes the reverse diffusion process into local conditional reverse diffusion processes. This decomposition enables each robot to iteratively perform denoising independently within its own control subspace while conditioning on the current trajectory estimates of the other robots that are aggregated and broadcast by the server. Extensive simulations in goal swapping, multi-floor coverage, parking, and rush-hour scenarios demonstrate that DMBD achieves strong scalability, solving many challenging coordination tasks with sub-second computation time and outperforming existing baselines.