分析多轮预条件SGD的泛化能力，揭示预处理对有效维度的影响。
On-Average Stability of Multipass Preconditioned SGD and Effective Dimension
- 提出多轮SGD的平均稳定性分析，处理数据重复使用带来的相关性。
- 证明不当预处理会恶化有效维度，导致优化与泛化性能下降。
- 给出上下界匹配的实例依赖下界，验证理论完备性。
我们研究多轮预条件随机梯度下降（PSGD）在泛化能力上的权衡问题，关注总体风险曲率、噪声几何结构与预处理之间的关系。实际优化策略常隐式地在这些因素间做权衡——例如，一些方法试图使梯度噪声白化，另一些则试图使更新方向与期望损失曲率对齐。当总体风险曲率几何与梯度噪声几何不匹配时，激进的选择可能改善某一方面却放大另一方面的不稳定性，导致次优统计表现。本文利用平均算法稳定性，将PSGD的泛化能力与依赖于这些曲率源的有效维度关联起来。现有平均稳定性分析仅限单轮情形；作为首个贡献，我们发展了适用于多轮SGD的平均稳定性分析，能处理数据重用引发的相关性。由此推导出依赖于有效维度的过量风险上界。特别地，我们表明不当选择的预处理器会导致优化与泛化中有效维度依赖性的次优表现。最后，我们通过匹配的、实例相关的下界来补充上界。
原文摘要 · Abstract (English)
We study trade-offs between the population risk curvature, geometry of the noise, and preconditioning on the generalisation ability of the multipass Preconditioned Stochastic Gradient Descent (PSGD). Many practical optimisation heuristics implicitly navigate this trade-off in different ways -- for instance, some aim to whiten gradient noise, while others aim to align updates with expected loss curvature. When the geometry of the population risk curvature and the geometry of the gradient noise do not match, an aggressive choice that improves one aspect can amplify instability along the other, leading to suboptimal statistical behavior. In this paper we employ on-average algorithmic stability to connect generalisation of PSGD to the effective dimension that depends on these sources of curvature. While existing techniques for on-average stability of SGD are limited to a single pass, as first contribution we develop a new on-average stability analysis for multipass SGD that handles the correlations induced by data reuse. This allows us to derive excess risk bounds that depend on the effective dimension. In particular, we show that an improperly chosen preconditioner can yield suboptimal effective dimension dependence in both optimisation and generalisation. Finally, we complement our upper bounds with matching, instance-dependent lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。