分析梯度计算不精确下优化方法的鲁棒性，发现加速法意外更稳健。
Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization
- 用性能估计法分析三类一阶优化方法在梯度不精确下的表现
- 加速方法实际比理论预期更抗不精确，长步法经修正后显著提升
- 适合研究优化算法鲁棒性或工业级大规模优化的读者
本文通过性能估计方法，从理论与实验两方面评估不同一阶优化方法在梯度计算存在相对不精确时的鲁棒性。相对不精确常见于大规模问题中使用低比特压缩梯度（如GPU场景）。分析了三类方法：常步长梯度下降、长步法和加速法。理论表明后两者对不精确不鲁棒；随后引入半启发式缩短因子改进其理论保证。在具体不精确问题上测试两种不同类型的相对不精确，结果发现加速法实际表现远超预期，且缩短因子显著提升长步法性能。最终所有缩短方法在不精确环境下均表现良好，具有应用前景。
原文摘要 · Abstract (English)
This work assesses both empirically and theoretically, using the performance estimation methodology, how robust different first-order optimization methods are when subject to relative inexactness in their gradient computations. Relative inexactness occurs, for example, when compressing the gradient using fewer bits of information, which happens when dealing with large-scale problems on GPUs. Three major families of methods are analyzed: constant step gradient descent, long-step methods, and accelerated methods. The latter two are first shown to be theoretically not robust to inexactness. Then, a semi-heuristic shortening factor is introduced to improve their theoretical guarantees. All methods are subsequently tested on a concrete inexact problem, with two different types of relative inexactness, and it is observed that both accelerated methods are much more robust than expected, and that the shortening factor significantly helps the long-step methods. In the end, all shortened methods appear to be promising, even in this inexact setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。