On Gradient Descent with Stochastic Rounding on Fixed-Point Grids for Quadratic Objectives

We study gradient descent on quadratic objectives whose iterates are constrained to a fixed-point grid with spacing $\Delta$ via stochastic rounding, by analyzing the hitting time to reach a grid minimizer, i.e., a minimizer over the grid. We first consider objectives whose minimizer lies on the grid and show that unlike gradient descent over the reals, the hitting time is not determined by the spectrum of the Hessian. Specifically, for a Hessian with a fixed spectrum and a random eigenbasis, the hitting time is $e^{\Omega (d)}$ in the dimension $d$ with high probability, and the Hamming distance to the grid minimizer and the optimization error remain of order $d$ and ${\Delta }^{2}d$, respectively, e.g., for Gaussian least squares with $n=\Theta (d)$ samples. In contrast, a diagonal Hessian with the same spectrum gives an $O(\log d)$ hitting time, which we generalize to a sufficient condition satisfied by diagonally dominant Hessians and by Gaussian least squares with $n=\Omega (d^2/\log \log d)$. This logarithmic upper bound matches an $\Omega (\log d)$ lower bound that holds for all Hessians with a unique grid minimizer when the initial Hamming distance is $\Omega (d)$. However, a large Hamming distance does not always imply a large optimization error: for a class of rank-deficient Hessians, e.g., Gaussian least squares with $n=o(d)$, the optimization error drops to $O({\Delta }^{2}n)$ within $O(\log (d/n))$ iterations while the Hamming distance remains of order $d$ for a number of iterations polynomial in $d/n$. Finally, if the minimizer of the objective lies off the grid, the exponential lower bound can persist, whereas the location of the minimizer alone can change the hitting time from logarithmic to exponential.