论文标题
polyak动量的通用平均案例最优性
Universal Average-Case Optimality of Polyak Momentum
论文作者
论文摘要
Polyak动量（PM），也称为重球方法，是一种广泛使用的优化方法，在二次目标上具有渐近最佳的最坏情况复杂性。但是，这种最优性并不能完全解释其显着的经验成功，因为与平均案例相反的最坏情况分析并不代表算法的预期复杂性。在这项工作中，我们在PM和平均案例分析之间建立了一种新的联系。我们的主要贡献是证明在轻度假设下，任何最佳的平均方法在迭代次数中都会收敛于PM。这为这种经典方法带来了新的观点，表明PM在最佳案例和平均案例最佳上均为最佳案例。
Polyak momentum (PM), also known as the heavy-ball method, is a widely used optimization method that enjoys an asymptotic optimal worst-case complexity on quadratic objectives. However, its remarkable empirical success is not fully explained by this optimality, as the worst-case analysis -- contrary to the average-case -- is not representative of the expected complexity of an algorithm. In this work we establish a novel link between PM and the average-case analysis. Our main contribution is to prove that any optimal average-case method converges in the number of iterations to PM, under mild assumptions. This brings a new perspective on this classical method, showing that PM is asymptotically both worst-case and average-case optimal.
