acceptodds
Desk rejected at ICLR 2027

Sum-Rate Constraint induces Partial Participation and Bidirectional Compression

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

210 views

Abstract

Communication-efficient distributed optimization typically treats compression, partial worker participation, and downlink communication as separate design choices. We show that they can instead arise from a single resource constraint: a hard per-round sum-rate () constraint on the aggregate communication rate of the workers, . The budget creates a direct tradeoff between participation and compression fidelity: involving more workers leaves fewer bits available for each update. Under a common-broadcast downlink of rate , the server can then rebroadcast the received worker codewords so that all workers reconstruct the global state without an additional lossy server-side compressor. We instantiate this principle in , a resource-constrained variant of the popular EF21 error-feedback method. We establish convergence to stationarity under heterogeneous compression. Experiments show that EF21-SR requires the least cumulative communication to approach the target among the compared methods with tuned stepsizes on both classification and least-squares problems.

Primary area:
optimization
Keywords:
distributed optimization, sum-rate constraint, partial participation, bidirectional compression, gradient compression, error feedback, rate allocation

Related papers

Discussion (0)

Sign in to comment.