arXiv preprint ·
Low-Bit Distributed Constrained Optimization with Application to Optimal Scheduling and Allocation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Systems & Control
Koi: Evidence-Guided, Self-Calibrating Planning for Multi-Cloud, Heterogeneous LLM Inference Fleets
Conjugate Compilation: Self-Improving Agentic Co-Compilation for Speculative Decoding
Adding Heavy-Ball Momentum to Distributed Constrained Optimization for Energy Resource Management Subject to Time-Delays and Quantization
An Information-Geometric Framework for OCS-Reconfigurable Interconnect Topology in Large-Scale AI Clusters
DROD: Dual-Ratio Ordered Dropout for Federated Continual Learning on Heterogeneous Devices
Get the few papers worth your time in Systems & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.