Sum-Rate Constraint induces Partial Participation and Bidirectional Compression

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 ($\text{SR}$) constraint on the aggregate communication rate of the workers, ${\sum }_{i=1}^n{R}_t^i\le R$. The budget $R$ 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 $R$, 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 $\text{EF21-SR}$, a resource-constrained variant of the popular EF21 error-feedback method. We establish $\mathcal{O}(1/T)$ 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.