Discrete error dynamics of mini-batch gradient descent for least squares regression
<|reference_start|>Discrete error dynamics of mini-batch gradient descent for least squares regression: 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$.<|reference_end|>
@article{lok2024discrete,
    title={Discrete error dynamics of mini-batch gradient descent for least squares
  regression},
    author={Jackie Lok, Rishi Sonthalia, Elizaveta Rebrova},
    journal={arXiv preprint arXiv:2406.03696},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.03696},
    primaryClass={stat.ML cs.LG math.OC}
}