Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters (arxiv.org)
arXiv:2610.33835v1 Announce Type: cross
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 $\Omega((m/s)\sqrt{\min\{\delta_a,\bar\delta/\sqrt m\}/\mu}\,\log(1/\epsilon))$ for $s\leq(m-2)/2$ in the high-accuracy, high-dissimilarity regime. Here $\mu$ is strong convexity, while $\delta_a$ and $\bar\delta$ 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 $\epsilon$ in $\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\bar\delta/\mu})$ expected rounds on quadratics with strongly convex clients, independent of $\delta_a$. Combining this method with charged analyses of existing algorithms matches the lower bound's polynomial dependence for $s\leq\sqrt m$ and $s=\Omega(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.
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 $\Omega((m/s)\sqrt{\min\{\delta_a,\bar\delta/\sqrt m\}/\mu}\,\log(1/\epsilon))$ for $s\leq(m-2)/2$ in the high-accuracy, high-dissimilarity regime. Here $\mu$ is strong convexity, while $\delta_a$ and $\bar\delta$ 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 $\epsilon$ in $\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\bar\delta/\mu})$ expected rounds on quadratics with strongly convex clients, independent of $\delta_a$. Combining this method with charged analyses of existing algorithms matches the lower bound's polynomial dependence for $s\leq\sqrt m$ and $s=\Omega(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.
Comments