Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate

Understanding the algorithmic bias of \\emph{stochastic gradient descent}\n(SGD) is one of the key challenges in modern machine learning and deep learning\ntheory. Most of the existing works, however, focus on \\emph{very small or even\ninfinitesimal} learning rate regime, and fail to cover practical scenarios\nwhere the learning rate is \\emph{moderate and annealing}. In this paper, we\nmake an initial attempt to characterize the particular regularization effect of\nSGD in the moderate learning rate regime by studying its behavior for\noptimizing an overparameterized linear regression problem. In this case, SGD\nand GD are known to converge to the unique minimum-norm solution; however, with\nthe moderate and annealing learning rate, we show that they exhibit different\n\\emph{directional bias}: SGD converges along the large eigenvalue directions of\nthe data matrix, while GD goes after the small eigenvalue directions.\nFurthermore, we show that such directional bias does matter when early stopping\nis adopted, where the SGD output is nearly optimal but the GD output is\nsuboptimal. Finally, our theory explains several folk arts in practice used for\nSGD hyperparameter tuning, such as (1) linearly scaling the initial learning\nrate with batch size; and (2) overrunning SGD with high learning rate even when\nthe loss stops decreasing.\n