Optimization limits and new methods for partial client participation
Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters
Machine Learning
Summary
This paper studies how quickly certain optimization tasks can be done when only a limited number of clients can participate each round, instead of everyone joining all the time. The authors identify a mathematical lower bound showing that many rounds are needed in some cases. They then propose a new method called Virtual-master SVRS that works better under these strict limits by cleverly mixing information. Their approach often reduces the number of rounds needed compared to previous methods, especially when client differences are large.
What this means in practice
- •For distributed machine learning engineers: Optimize federated learning workflows when communication bandwidth limits the number of clients contacted each round.
- •For cloud system architects: Design scalable optimization protocols for strongly convex problems with partial client participation to reduce round delays in distributed environments.
Authors
Rui Wang
Abstract
What is the round complexity of Hessian-similar optimization when each round can contact at most $s$ of $m$ clients? Prior rates permit a free master or full participation and do not characterize strict caps. We count every one-vector query and reply. A hidden-client chain gives a lower bound for zero-respecting local algorithms with adaptive cohorts and random stopping: on strongly convex quadratics, the required rounds are $Ω((m/s)\sqrt{\min\{δ_a,\barδ/\sqrt m\}/μ}\,\log(1/ε))$ for $s\leq(m-2)/2$ in the high-accuracy, high-dissimilarity regime. Here $μ$ is strong convexity, while $δ_a$ and $\barδ$ bound anchor and average Hessian variation. To remove dependence on a poor anchor, virtual-master SVRS uses independent estimator and proximal cohorts and averages the proximal replies. With Catalyst, it reaches relative gap $ε$ in $\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\barδ/μ})$ expected rounds on quadratics with strongly convex clients, independent of $δ_a$. Combining this method with charged analyses of existing algorithms matches the lower bound's polynomial dependence for $s\leq\sqrt m$ and $s=Ω(m)$; the worst gap is $O(m^{1/8})$. A held-out 12-seed synthetic study finds fewer rounds than tuned SVRP in nine of ten dip-family incomplete-cohort cells, versus two of 30 other cells. The lower bounds concern zero-respecting algorithms and do not cover unrestricted messages.