Zhirayr Tovmasyan, Slavomír Hanzely, Egor Shulgin, Peter Richtárik, Sebastian U. Stich
One of the main challenges of federated learning is heterogeneous data split among the clients, leading to biased local updates called client drift. The SCAFFOLD algorithm (Karimireddy et al., 2020) corrects client drift with control variates, but its relation to the similarity of client data is not yet fully understood: the original similarity-based guarantees cover only quadratics with a stronger second-order similarity assumption, and a follow-up weakly convex analysis (Luo et al., 2025) obtains a $\sqrt{Lδ}$ dependence for $L$-smooth losses with averaged Hessian similarity $δ$. We analyze SCAFFOLD with minibatch-based control variates and establish linear dependence on Hessian similarity beyond quadratics, for both convex and nonconvex objectives. In particular, for convex objectives with exact gradients, $R$ SCAFFOLD rounds with $K$ local steps lead to an objective gap of order $(L/K+δ)D_0^2/R$, where $D_0$ is the initial distance to a minimizer. When $K=Θ(L/δ)$, it improves the minibatch SGD rate by a factor $Θ(L/δ)$. For nonconvex objectives, we prove an analogous stationarity guarantee under uniform Hessian similarity for a client-selection variant. In both settings, we extend these guarantees to stochastic gradients and prove matching lower bounds for the analyzed methods with constant local stepsizes. We also show that, under partial participation, even identical clients need not obtain the full communication benefit of additional local steps.
Modern machine learning relies on practical optimization methods that often differ from the algorithms studied in classical analyses: they train submodels, clip or normalize gradients, use layer-wise non-Euclidean directions, or approximate costly inner computations. This thesis analyzes the objective, assumptions, update, and computation defined by these procedures, rather than those of simplified proxies. For submodel training, we show that Independent Subnetwork Training can converge to a shifted fixed point because sketching before differentiation biases the update for the original objective. Model-Agnostic Sparsified Training instead incorporates the sketch distribution into its objective, which makes sketched gradients unbiased and admits convergence guarantees. For private optimization, we show that adaptive quantile clipping retains bias at any fixed quantile, while suitable quantile schedules recover near-optimal nonconvex rates under heavy-tailed noise. We then combine smoothed normalization with error compensation and obtain distributed private convergence guarantees under standard assumptions, without assuming bounded gradients. For optimizers based on linear minimization oracles, we develop and validate a layer-wise generalized smoothness model and build on it the Gluon framework for Muon- and Scion-style methods. We also show that the approximate orthogonalization in Muon matters: less precise orthogonalization calls for smaller stepsizes, so its precision should be tuned together with the learning rate. Overall, practical methods are better understood when theory retains the features that determine their optimization behavior.