Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters
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)√(min{δa,δ̅/√m}/μ) log(1/ε)) for s≤(m−2)/2 in the high-accuracy, high-dissimilarity regime. Here μ is strong convexity, while δa and δ̅ 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 Õ(m/s+(√(m/s)+m3/4/s)√(δ̅/μ)) 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≤√m and s=Ω(m); the worst gap is O(m1/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.
Related
- Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
- Efficient Hessian-Free Methods for Multi-Objective Bilevel Optimization with Nonconvex Lower Level
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- PDE-constrained optimization for virtual sensing in structural dynamics: Full-field displacement and force recovery from sparse sensors
BibTeX
@misc{wang2026hessiansimilar,
title = {{Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters}},
author = {Rui Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33835},
eprint = {2610.33835},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33835},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters
AU - Rui Wang
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33835
UR - https://arxiv.org/abs/2610.33835
AB - 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)√(min{δ_a,δ̅/√m}/μ) log(1/ε)) for s≤(m−2)/2 in the high-accuracy, high-dissimilarity regime. Here μ is strong convexity, while δ_a and δ̅ 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 Õ(m/s+(√(m/s)+m^3/4/s)√(δ̅/μ)) 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≤√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.
ER -