We study the discrete dynamics of mini-batch gradient descent for least squares regression when sampling without replacement. We show that the dynamics and generalization error of mini-batch gradient descent depends on a sample cross-covariance matrix $Z$ between the original features $X$ and a set of new features $\widetilde{X}$, in which each feature is modified by the mini-batches that appear before it during the learning process in an averaged way. Using this representation, we rigorously establish that the dynamics of mini-batch and full-batch gradient descent agree up to leading order with respect to the step size using the linear scaling rule. We also study discretization effects that a continuous-time gradient flow analysis cannot detect, and show that mini-batch gradient descent converges to a step-size dependent solution, in contrast with full-batch gradient descent. Finally, we investigate the effects of batching, assuming a random matrix model, by using tools from free probability theory to numerically compute the spectrum of $Z$.

我们研究了无重复抽样的最小批量梯度下降在最小二乘回归中的离散动力学。我们证明最小批量梯度下降的动力学和泛化误差取决于原始特征X和一组新特征X̃之间的样本交叉协方差矩阵Z，在学习过程中每个特征都被之前出现的最小批次平均修改。利用这个表示，我们严格证明了最小批量梯度下降的动力学与全批量梯度下降在步长的线性尺度规则下达到了一致的主导阶。我们还研究了连续时间梯度流分析不能检测到的离散化效应，并显示最小批量梯度下降收敛到与步长相关的解，与全批量梯度下降相反。最后，我们利用自由概率理论工具，在假设随机矩阵模型的情况下，数值计算了Z的谱。

最小二乘法回归的小批量梯度下降离散误差动态