Convergence diagnostics for stochastic gradient descent with constant learning rate
Jerry Chee University of Chicago Panos Toulis University of Chicago, Booth School of Business
Abstract
Many iterative procedures in stochastic optimization exhibit a transient phase followed by a stationary phase. During the transient phase the procedure converges towards a region of interest, and during the stationary phase the procedure oscillates in that region, commonly around a single point. In this paper, we develop a statistical diagnostic test to detect such phase transition in the context of stochastic gradient descent with constant learning rate. We present theory and experiments suggesting that the region where the proposed diagnostic is activated coincides with the convergence region. For a class of loss functions, we derive a closed-form solution describing such region. Finally, we suggest an application to speed up convergence of stochastic gradient descent by halving the learning rate each time stationarity is detected. This leads to a new variant of stochastic gradient descent, which in many settings is comparable to state-of-art.
中文速览
随机梯度下降（SGD）在训练过程中普遍存在"先收敛、后震荡"的两阶段现象：算法从初始点出发经历一段瞬态阶段逼近最优解附近，然后进入稳态阶段在该区域内持续抖动，但实践中很难判断何时完成了这一转变。本文借鉴Pflug停止准则的思路，设计了一个统计诊断测试：追踪相邻两步随机梯度内积的累积和，当该累积和由正变负时，即判定SGD已从瞬态进入稳态——因为瞬态阶段梯度方向大体一致（内积为正），稳态阶段梯度方向随机散乱（内积为负）。理论分析证明该诊断几乎必然触发，并在二次损失函数下给出了稳态区域的解析表达式；实验也表明诊断激活时刻与真实收敛区域高度吻合。在此基础上，作者提出SGD½算法——每次检测到稳态就将学习率减半，从而在不依赖人工调参的情况下自动加速收敛，性能可与方差缩减SGD等当前最优方法媲美，为深度学习和大规模优化中的学习率自适应调整提供了有理论保障的新思路。
原文 arXiv:1710.06382;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1710.06382v2