重新解读Polyak步长，揭示其本质是代理损失优化。
New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
- 将Polyak步长统一视为代理损失上的梯度下降。
- 证明某些变体存在真实非收敛性，上界误差并非理论缺陷。
- 为不同假设下的变体提供统一分析框架，适合优化理论研究者。
Polyak步长在凸优化中被证明是基础性步长，能在多种假设下实现接近最优的梯度下降速率。其普适性也催生了诸多随机变体，兼具理论保证与强大实验表现。尽管已有大量理论成果，但对其收敛性质及局限性的理解仍不完整且分散于不同分析中。本文提出一种新的、统一且简洁的视角：将Polyak步长及其变体视为在代理损失上的梯度下降。我们证明每个变体等价于最小化一个代理函数，其步长自适应于保证的局部曲率。该通用代理损失视角被用于对现有变体在不同假设下的统一分析。此外，我们揭示若干负面结果，证明部分上界中的非收敛现象确为真实存在。
原文摘要 · Abstract (English)
The Polyak stepsize has been proven to be a fundamental stepsize in convex optimization, giving near optimal gradient descent rates across a wide range of assumptions. The universality of the Polyak stepsize has also inspired many stochastic variants, with theoretical guarantees and strong empirical performance. Despite the many theoretical results, our understanding of the convergence properties and shortcomings of the Polyak stepsize or its variants is both incomplete and fractured across different analyses. We propose a new, unified, and simple perspective for the Polyak stepsize and its variants as gradient descent on a surrogate loss. We show that each variant is equivalent to minimize a surrogate function with stepsizes that adapt to a guaranteed local curvature. Our general surrogate loss perspective is then used to provide a unified analysis of existing variants across different assumptions. Moreover, we show a number of negative results proving that the non-convergence results in some of the upper bounds is indeed real.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。