TAMUNA Doubly Accelerated Distributed Optimization with Local Training, Compression, and Partial Participation

A federated and distributed optimization algorithm introduced by Condat, Agarský, Malinovsky, and Richtárik (2023) that simultaneously combines Local Training (LT), Communication Compression (CC), and Partial Client Participation (PP) to minimize f(x) = (1/n) sum_{i=1}^n f_i(x) across n clients without suffering from client drift. In each communication round r, the server broadcasts the global model x_bar^{(r)} to a uniformly sampled cohort Omega^{(r)} subset [n] of size c in {2, ..., n}; active clients perform L^{(r)} ~ Geom(p) drift-corrected local steps x_i^{(r, ell+1)} = x_i^{(r, ell)} - gamma g_i^{(r, ell)} + gamma h_i^{(r)} from x_i^{(r, 0)} = x_bar^{(r)}, apply a correlated column-permuted binary mask compressor C_i^{(r)} that selects exactly s in {2, ..., c} active clients per coordinate j in {1, ..., d}, and the server aggregates x_bar^{(r+1)} = (1/s) sum_{i in Omega^{(r)}} C_i^{(r)}(x_i^{(r, L^{(r)})}) while active clients update their control variates via h_i^{(r+1)} = h_i^{(r)} + (eta/gamma)(C_i^{(r)}(x_bar^{(r+1)}) - C_i^{(r)}(x_i^{(r, L^{(r)})})) and idle clients retain h_i^{(r+1)} = h_i^{(r)}.