


























Abstract:Privacy concerns in distributed learning often lead clients to return intentionally altered gradient information. We consider the problem of learning convex and $L$-smooth functions under adversarial gradient perturbation, where a client's gradient reply to a server query can deviate arbitrarily from the true gradient subject to a distance bound. Our study focuses on two fundamental questions: (i) what is the smallest achievable sub-optimality gap (i.e., excess error in optimization) under such responses, and (ii) how many queries are sufficient to guarantee a given sub-optimality gap? We establish tight feasibility thresholds on the sub-optimality gap and provide algorithms that achieve these thresholds with provable query complexity guarantees.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.03313 [cs.LG] |
| (or arXiv:2605.03313v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.03313 arXiv-issued DOI via DataCite (pending registration) |
From: Nawapon Sangsiri [view email]
[v1]
Tue, 5 May 2026 02:57:46 UTC (2,115 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。