提出新型查询策略，让优化算法更快收敛且更稳定。
Stochastic Gradient Descent with Strategic Querying
- 通过动态选择最有价值的梯度信息进行更新
- 在平滑函数上实现比SGD更快的初期收敛速度
- 适合需要快速响应的分布式优化场景
本文研究在仅能进行一阶查询的有限求和优化问题中，相比均匀查询策略，战略性查询对基于随机梯度的方法带来的优势。我们首先引入理想化的最优梯度查询（OGQ）算法，该算法每步选择能带来最大期望改进的用户梯度。但OGQ需访问所有用户的梯度，不切实际。为此，我们提出实用的策略性梯度查询（SGQ）算法，每轮仅需一次查询，即可优于标准SGD的瞬态性能。对于满足Polyak-Lojasiewicz条件的光滑目标函数，在期望改进异质性的假设下，我们证明OGQ可提升瞬态性能并降低稳态方差，而SGQ亦优于SGD。数值实验验证了理论结果。
原文摘要 · Abstract (English)
This paper considers a finite-sum optimization problem under first-order queries and investigates the benefits of strategic querying on stochastic gradient-based methods compared to uniform querying strategy. We first introduce Oracle Gradient Querying (OGQ), an idealized algorithm that selects one user's gradient yielding the largest possible expected improvement (EI) at each step. However, OGQ assumes oracle access to the gradients of all users to make such a selection, which is impractical in real-world scenarios. To address this limitation, we propose Strategic Gradient Querying (SGQ), a practical algorithm that has better transient-state performance than SGD while making only one query per iteration. For smooth objective functions satisfying the Polyak-Lojasiewicz condition, we show that under the assumption of EI heterogeneity, OGQ enhances transient-state performance and reduces steady-state variance, while SGQ improves transient-state performance over SGD. Our numerical experiments validate our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。