  There is an increasing realization that algorithmic inductive biases are
central in preventing overfitting; empirically, we often see a benign
overfitting phenomenon in overparameterized settings for natural learning
algorithms, such as stochastic gradient descent (SGD), where little to no
explicit regularization has been employed. This work considers this issue in
arguably the most basic setting: constant-stepsize SGD (with iterate averaging)
for linear regression in the overparameterized regime. Our main result provides
a sharp excess risk bound, stated in terms of the full eigenspectrum of the
data covariance matrix, that reveals a bias-variance decomposition
characterizing when generalization is possible: (i) the variance bound is
characterized in terms of an effective dimension (specific for SGD) and (ii)
the bias bound provides a sharp geometric characterization in terms of the
location of the initial iterate (and how it aligns with the data covariance
matrix). We reflect on a number of notable differences between the algorithmic
regularization afforded by (unregularized) SGD in comparison to ordinary least
squares (minimum-norm interpolation) and ridge regression.
