研究分布式学习中恶意扰动梯度的最优误差与查询次数关系
Distributed Learning with Adversarial Gradient Perturbations
- 构建对抗性梯度扰动下的优化模型，分析误差下界
- 证明最小可实现误差与查询次数呈反比关系
- 适合关注隐私保护与鲁棒优化的研究者
分布式学习中的隐私问题常导致客户端返回被有意篡改的梯度信息。本文研究在对抗性梯度扰动下学习凸且L-光滑函数的问题，其中客户端对服务器查询的梯度响应可在距离约束范围内任意偏离真实梯度。重点探讨两个基本问题：(i) 在此类响应下可达到的最小次优间隙（即优化中的超额误差）是多少？(ii) 需要多少轮查询才能保证给定的次优间隙？本文建立了次优间隙的紧致可行性阈值，并提出可实现该阈值的算法，同时提供可证明的查询复杂度保证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。