On Averaging and Extrapolation for Gradient Descent
研究了光滑凸优化中梯度下降迭代的均值化与外推法，发现均值化无法改善最差情况性能，而一种简单外推方案能严格提升收敛速度，效果相当于多进行若干步梯度下降。
This work considers the effect of averaging, and more generally extrapolation, of the iterates of gradient descent in smooth convex optimization. After running the method, rather than reporting the final iterate, one can report either a convex combination of the iterates (averaging) or a generic combination of the iterates (extrapolation). For several common stepsize sequences, including recently developed accelerated periodically long stepsize schemes, we show averaging cannot improve gradient descent’s worst-case performance and is, in fact, strictly worse than simply returning the last iterate. In contrast, we prove a conceptually simple and computationally cheap extrapolation scheme strictly improves the worst-case convergence rate: when initialized at the origin, reporting [Formula: see text] rather than [Formula: see text] improves the best possible worst-case performance by the same amount as conducting [Formula: see text] more gradient steps. Our analysis and characterizations of the best possible convergence guarantees are computer-aided, using performance estimation problems. Numerically, we find similar (small) benefits from such simple extrapolation for a range of gradient methods. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-23-1-0531].