Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters

# 概要
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…

# 原典
https://arxiv.org/abs/2610.33835

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。