acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

We study gradient descent on quadratic objectives whose iterates are constrained to a fixed-point grid with spacing 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 in the dimension with high probability, and the Hamming distance to the grid minimizer and the optimization error remain of order and , respectively, e.g., for Gaussian least squares with samples. In contrast, a diagonal Hessian with the same spectrum gives an hitting time, which we generalize to a sufficient condition satisfied by diagonally dominant Hessians and by Gaussian least squares with . This logarithmic upper bound matches an lower bound that holds for all Hessians with a unique grid minimizer when the initial Hamming distance is . 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 , the optimization error drops to within iterations while the Hamming distance remains of order for a number of iterations polynomial in . 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.

Primary area:
learning theory
Keywords:
Gradient Descent, Fixed-Point Grid, Stochastic Rounding

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_XJxDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the convergence behavior of gradient descent with stochastic rounding (SR-GD) for quadratic optimization problems over fixed-point grids. Unlike classical gradient descent over continuous domains, where convergence is largely characterized by the eigenvalues of the Hessian, the authors demonstrate that the convergence behavior of SR-GD depends critically on the eigenbasis of the Hessian and the location of the minimizer relative to the grid. The paper establishes several theoretical results. First, for positive definite Hessians with a fixed spectrum and a randomly rotated eigenbasis, SR-GD can require exponentially many iterations in the dimension to reach the grid minimizer, even when the condition number is bounded. In contrast, diagonal and certain diagonally dominant Hessians admit logarithmic hitting times. Second, the authors characterize different convergence regimes for Gaussian least-squares problems, showing how the number of samples affects the hitting time. Third, for rank-deficient Hessians, they demonstrate that the optimization error can become small while the iterates remain far from the grid minimizer in Hamming distance. Finally, the paper extends the analysis to off-grid minimizers and shows that the location of the continuous minimizer can fundamentally change the hitting-time complexity. Overall, the paper provides a theoretical investigation of how stochastic rounding changes the optimization dynamics of gradient descent, highlighting phenomena that are not captured by classical spectral convergence analysis.

Critical strengths

The authors proposed a novel and interesting theoretical perspective in this submission. The paper identifies a fundamental distinction between classical gradient descent and stochastic-rounding gradient descent. In particular, the result that two Hessians with identical eigenvalues can exhibit logarithmic versus exponential hitting times is interesting and provides insight into the limitations of spectral convergence analysis in finite-precision optimization. These are strong theoretical contributions. The paper develops several nontrivial convergence results, including exponential lower bounds, logarithmic upper bounds, and matching bounds in important regimes. Theorem 1 establishes exponential hitting times for randomly rotated Hessians, while Theorem 2 shows that this exponential dependence is tight up to constants in the exponent. Theorem 6 further establishes a logarithmic lower bound for initializations with large Hamming distance.

The authors also presented comprehensive analysis of different problem settings. The authors consider positive definite, rank-deficient, and off-grid quadratic optimization problems. These different settings help distinguish convergence in optimization error from convergence to an exact grid minimizer. The results for Gaussian least squares also provide concrete examples illustrating the theoretical phenomena. The authors provided insightful characterization of the role of Hessian structure. The sufficient contraction conditions in Section 3.2 provide a useful explanation of why some Hessians lead to fast convergence despite stochastic rounding. The comparison between the conditions $|J|_2<14 and ∥∣J∣∥2<1\||J|\|_2<1 is particularly informative because it highlights how coordinate-wise rounding makes the orientation of the Hessian relevant.

Finally, this submission has clear organization with substantial mathematical analysis. The paper is logically structured, with the main theoretical contributions presented in Sections 3 and 4 and supporting proofs provided in the appendices. The use of Hamming distance, hitting-time analysis, and potential functions provides a coherent framework for studying the stochastic optimization dynamics.

Critical weaknesses

The most significant weakness of this submission is the lack of numerical experiments to validate the theoretical findings. The paper is entirely theoretical and does not provide numerical experiments illustrating the proposed convergence phenomena. Although the theoretical results are interesting, empirical validation would strengthen the paper significantly. In particular, experiments comparing diagonal Hessians, randomly rotated Hessians, and Gaussian least-squares problems would help demonstrate the predicted logarithmic and exponential hitting-time regimes. Furthermore, numerical experiments could investigate whether the theoretical bounds accurately characterize practical convergence behavior at moderate dimensions.

Moreover, the analysis on pure quadratic optimization problems has limited applications. The theoretical analysis focuses exclusively on convex quadratic objectives with constant Hessians. While this setting is mathematically convenient and allows precise characterization of stochastic rounding, practical machine learning problems generally involve nonlinear and non-convex objectives. It remains unclear whether the exponential hitting-time phenomena persist for more general strongly convex smooth functions or for non-convex optimization problems. The paper would benefit from discussing potential extensions and the main technical difficulties involved.

Also, the practical significance of hitting-time complexity needs further justification. The primary convergence measure is the hitting time to an exact grid minimizer. However, in practical machine learning, optimization algorithms are typically evaluated according to their objective values, gradient norms, or predictive performance rather than the time required to reach an exact minimizer. In particular, Theorem 8 demonstrates that optimization error can become small even when the hitting time is large. This raises an important question about whether exponential hitting times necessarily indicate poor optimization performance. The authors should more explicitly distinguish between the complexity of reaching an exact grid minimizer and the complexity of achieving an approximately optimal objective value. Moreover, some assumptions are restrictive. Several main results require specific assumptions on the Hessian, including Haar-random eigenbases, bounded condition numbers, and prescribed eigenvalue variance. The logarithmic upper bounds also rely on particular contraction conditions. Although these assumptions are mathematically meaningful, their prevalence in practical optimization problems is unclear. A discussion of how frequently these conditions arise in real machine learning applications would strengthen the significance of the results.

Questions for authors

Can the exponential hitting-time lower bound in Theorem 1 be extended to general strongly convex and smooth functions? Would Hessian Lipschitz continuity be sufficient for establishing analogous results locally?

6 comments

We thank the reviewer for their valuable comments. We address the reviewer's comments below and revised our draft accordingly, where all the updates are colored in blue.

C1. Numerical experiments.

R1. Following the reviewer's comment, we added numerical experiments in Appendix H of the revised draft. In our basic setup, we run SR-GD on the 8-bit fixed-point grid on [−4,4][-4,4], i.e., M=127M=127 and Δ=4/127\Delta=4/127, with the step size η=0.8/λmax⁡(A)\eta=0.8/\lambda_{\max}(\mathbf{A}) (Appendix H.1). We then extend this setup to fixed-point grids with 44, 88, 1616, and 3232 bits and to floating-point grids in the FP8, FP16, and FP32 formats. We consider three classes of objectives.

  • Quadratic objectives, including Hessians with a Haar-random or diagonal eigenbasis, Gaussian least squares, rank-deficient Hessians, and off-grid minimizers.
  • Smooth non-quadratic objectives, including a nonconvex one.
  • Logistic regression on the Gisette dataset, softmax regression on the MNIST dataset, and a two-layer network that learns a teacher model on MNIST images.

For each experiment, we run multiple trajectories, i.e., independent runs of SR-GD, which differ in the stochastic rounding. For a random Hessian, we sample multiple Hessians and run multiple trajectories for each of them. We report the hitting time, the Hamming distance, and the optimization error over these trajectories. These include pathwise statistics, which show how many trajectories satisfy the high-probability events in our theorems.

We first observe our theoretical results on quadratic objectives, using the settings of the corresponding theorems. In all these experiments, SR-GD behaves as our theory predicts, already at moderate dimensions (up to d=1024d=1024).

  • Diagonal and randomly rotated Hessians (Appendix H.3). For the same spectrum, a Haar-random eigenbasis makes SR-GD slow. Even from an initializer that differs from the grid minimizer in a single coordinate, the Hamming distance and the optimization error quickly increase, and their values divided by dd and Δ2d\Delta^2d stay at almost the same levels for the larger tested dimensions, whereas GD over the reals decreases the optimization error rapidly. For large dd, almost every trajectory keeps a Hamming distance of order dd and an optimization error of order Δ2d\Delta^2d. Moreover, the median hitting time increases rapidly with dd and exceeds our time horizon for d>64d>64. This coincides with Theorems 1 and 2, and the quick increase of the Hamming distance is consistent with Proposition 3. In contrast, for the diagonal Hessian, SR-GD reaches the grid minimizer within a few iterations, as in Proposition 5.
  • Gaussian least squares (Appendix H.4). For a sample size proportional to dd, SR-GD behaves as for the Haar-random eigenbasis, as in Theorem 4. As the sample size increases to d2d^2, the hitting time decreases: it grows rapidly with dd for small sample sizes, grows slowly for intermediate ones, and stays almost constant in dd for sample sizes close to d2d^2. This is consistent with the transition from exponential through polynomial to logarithmic hitting times given by Theorems 4, 6, and 7.
  • Rank-deficient Hessians (Appendix H.5). For every tested dd and rr, the optimization error divided by Δ2r\Delta^2r quickly becomes small, while the mean Hamming distance divided by dd stays large, as in Theorem 8 and Corollary 9. That is, the optimization error can be small even if the Hamming distance is large.
  • Off-grid solutions (Appendix H.6). For A=Id\mathbf{A}=\mathbf{I}_d and an initializer that differs from the grid minimizer in every coordinate, SR-GD reaches the grid minimizer quickly, and the number of iterations grows slowly with dd, if the minimizer lies on the grid or very close to it. This is consistent with Case (i) of Theorem 12. However, moving the minimizer away from the grid by a quarter of the grid spacing in every coordinate makes the hitting time increase rapidly with dd, as in Case (ii) of Theorem 12. The Haar-random eigenbasis also remains slow for an off-grid solution, as in Theorem 10.
  • Fixed-point precision (Appendix H.7). The above observations hold at every tested precision, i.e., for 44, 88, 1616, and 3232 bits, as our results hold for every Δ>0\Delta>0.

We then examine whether our main observations extend beyond the assumptions of our theory. Here, our main observations from theory are that (a) the hitting time of SR-GD depends on the eigenbasis of the Hessian, not only on its spectrum, (b) even from an initializer that differs from the minimizer in a single coordinate, the optimization error can increase and persist, and (c) the hitting time also depends on the location of the minimizer relative to the grid. We observe that they extend to the following settings.

  • Floating-point grids (Appendix H.8). We repeat the experiments on the eigenbasis and on the location of the minimizer, where each coordinate is stochastically rounded to the values representable in FP8, FP16, or FP32, whose spacing varies with the magnitude. Here, the hitting time still depends on both (a) the eigenbasis and (c) the location of the minimizer.
  • Smooth non-quadratic objectives (Appendix H.9). We consider f(w)=∑j=1dcjρ(qj⊤w)+λ2∥∥w∥∥22f(\mathbf{w})=\sum_{j=1}^d c_j\rho(\mathbf{q}_j^\top\mathbf{w})+\frac{\lambda}{2}\|\|\mathbf{w}\|\|_2^2, where ρ\rho is a logistic or Cauchy loss with ρ(0)=ρ′(0)=0\rho(0)=\rho'(0)=0 and ρ′′(0)=1\rho''(0)=1, half of the coefficients cjc_j are 44 and the others are 11, and [q1,…,qd][\mathbf{q}_1,\ldots,\mathbf{q}_d] is a Haar-random orthogonal matrix or the identity matrix. Here, the logistic loss with λ=0\lambda=0 and λ=1/4\lambda=1/4 and the Cauchy loss with λ=1/4\lambda=1/4 give convex, strongly convex, and nonconvex objectives, respectively, which are not quadratic in any neighborhood of their minimizer 0\mathbf{0}. For both eigenbases, 0\mathbf{0} is the unique grid minimizer, and the Hessian at 0\mathbf{0} has the same eigenvalues cj+λc_j+\lambda. We run SR-GD from an initializer that differs from 0\mathbf{0} in every coordinate. For (a), SR-GD is slow for the Haar-random eigenbasis and fast for the identity eigenbasis, as for quadratic objectives. Since the strongly convex and nonconvex objectives, which have the same Hessian at the minimizer, behave similarly, the behavior of SR-GD depends on the Hessian at the minimizer rather than on convexity. For (b), the optimization error of the Haar-random eigenbasis persists at the order of Δ2d\Delta^2d for large dd, whereas GD decreases it rapidly. For (c), translating the objective by a quarter of the grid spacing in every coordinate makes SR-GD slow for the identity eigenbasis, as in Case (ii) of Theorem 12.
  • Non-quadratic objectives on real data (Appendix H.10). We consider three models with ℓ2\ell_2-regularization: logistic regression on the Gisette dataset (d=5,000d=5{,}000), softmax regression on the MNIST dataset (d=7,850d=7{,}850), and a two-layer network with 88 hidden units and tanh⁡\tanh activations that learns a teacher model on 2,0002{,}000 MNIST images (d=6,370d=6{,}370). Here, objectives and gradients are computed in FP32. For each model, we first compute a stationary point u\mathbf{u} numerically. We then compare the original grid {u+z:z∈W}\{\mathbf{u}+\mathbf{z}:\mathbf{z}\in\mathcal{W}\} with the aligned grid {u+Qz:z∈W}\{\mathbf{u}+\mathbf{Q}\mathbf{z}:\mathbf{z}\in\mathcal{W}\}, where the columns of Q\mathbf{Q} are the eigenvectors of the Hessian at u\mathbf{u}. That is, the aligned grid makes the Hessian at u\mathbf{u} diagonal in the grid coordinates, as for the diagonal Hessian in Section 3.2. We also translate both grids slightly, so that u\mathbf{u} lies off the grid. SR-GD starts from initializers that differ from u\mathbf{u} by the grid spacing in a single coordinate, by the grid spacing in many coordinates, or by random multiples of the grid spacing. For (a), on the original grid, SR-GD from initializers that differ from u\mathbf{u} in many coordinates does not reach it within our time horizon, whereas on the aligned grid, SR-GD reaches u\mathbf{u} from every initializer. For (b), on the original grid, even from initializers that differ in a single coordinate, the Hamming distance spreads to many coordinates, and for logistic and softmax regression, the optimization error increases. For (c), the translation of the aligned grid slows down SR-GD.

We refer to Appendix H for the full details of the setup and the detailed discussions of each experiment.

C2. Extensions beyond quadratic objectives (e.g., to general strongly convex and smooth functions, or under Hessian Lipschitz continuity) and the main technical difficulties.

R2. We thank the reviewer for this valuable comment. We would like to note that, as a worst-case lower bound, our result in Theorem 1 already holds for the classes of strongly convex, convex, and smooth (possibly nonconvex) functions, since the quadratic objectives in Theorem 1 belong to these classes. Furthermore, our lower bounds extend to the following non-quadratic objectives, which we added to the revised draft (the paragraph "Extensions to non-quadratic objectives" in Section 3.1 and Appendix G).

  • Locally quadratic objectives. Consider an objective that coincides with a quadratic objective satisfying the assumptions of Theorem 1 in a ball of radius CΔdC\Delta\sqrt{d} around an interior grid point v\mathbf{v} for a sufficiently large constant CC, while it can be any differentiable function outside the ball, convex or nonconvex. We show that SR-GD initialized in this ball does not leave it for eΩ(d)e^{\Omega(d)} iterations with high probability, due to the contraction of GD and the bounded rounding noise. Since the objective coincides with the quadratic objective inside the ball, the same lower bounds hold, where v\mathbf{v} need not be a global minimizer (Corollary 59).
  • Separable perturbations. Consider an objective f(w)+∑i=1dpi(wi−wi⋆)f(\mathbf{w})+\sum_{i=1}^d p_i(w_i-w_i^{\star}), where ff is a quadratic objective satisfying the assumptions of Theorem 1 and each pip_i is differentiable with pi(0)=pi′(0)=0p_i(0)=p_i'(0)=0, pi≥0p_i\ge0, and ∣pi′(t)∣≤P∣t∣|p_i'(t)|\le P|t| for a constant P≥0P\ge0, e.g., the Cauchy penalty pi(t)=λσ22log⁡(1+t2/σ2)p_i(t)=\frac{\lambda\sigma^2}{2}\log(1+t^2/\sigma^2) with P=λP=\lambda. With the Cauchy penalty, this objective is not quadratic in any neighborhood of its minimizer. However, since pi′(0)=0p_i'(0)=0, the added term does not change the gradient on the coordinates that already match the minimizer, and hence, the mechanism creating new coordinate errors (Proposition 3) is unchanged. Hence, the same lower bounds hold with η=S/(λmax⁡(A)+P)\eta=S/(\lambda_{\max}(\mathbf{A})+P) (Corollary 60). For the Cauchy penalty, the objective is strongly convex if λ<8λmin⁡(A)\lambda<8\lambda_{\min}(\mathbf{A}), convex but not strongly convex if λ=8λmin⁡(A)\lambda=8\lambda_{\min}(\mathbf{A}), and nonconvex otherwise.

For more general objectives, the main technical difficulty is to preserve the spreading of coordinate errors in Proposition 3. Our proof of Theorem 1 relies on the linearity of the gradient. In particular, the spreading condition in Proposition 3 is homogeneous in the displacement z=w−w⋆\mathbf{z}=\mathbf{w}-\mathbf{w}^{\star}, and hence it suffices to verify it once, uniformly over sparse displacements, regardless of their magnitudes. However, for non-quadratic objectives, the gradient on the coordinates that match the minimizer depends nonlinearly on both the direction and the magnitude of z\mathbf{z}. Hence, the nonlinear terms can reduce the spreading, e.g., when the gradient at w⋆+z\mathbf{w}^{\star}+\mathbf{z} becomes nearly parallel to z\mathbf{z} at some scale, in which case it nearly vanishes on the coordinates that match the minimizer. We think that a natural next step is rotated separable objectives ∑jgj(qj⊤(w−w⋆))\sum_{j}g_j(\mathbf{q}_j^\top(\mathbf{w}-\mathbf{w}^{\star})) with smooth gjg_j and a Haar-random orthogonal matrix [q1,…,qd][\mathbf{q}_1,\ldots,\mathbf{q}_d], which reduce to Theorem 1 when each gjg_j is quadratic. We observe similar behaviors for such objectives with logistic and Cauchy losses in our experiments (Appendix H.9; see also our response to C1).

For the Hessian Lipschitz continuity, we think that it is not sufficient for an analogous local result if the Lipschitz constant HH does not depend on dd. That is, the iterates stay at distance of order Δd\Delta\sqrt{d} from the minimizer, where the nonlinear part of the gradient need not be small. Nevertheless, we expect that our argument for locally quadratic objectives can be extended if the nonlinear part of the gradient is sufficiently small. Specifically, suppose that an objective FF has a minimizer w⋆\mathbf{w}^{\star} in the interior of the grid such that A=∇2F(w⋆)\mathbf{A}=\nabla^2F(\mathbf{w}^{\star}) satisfies the assumptions of Theorem 1 and ∇2F\nabla^2F is HH-Lipschitz in a ball of radius R=CΔdR=C\Delta\sqrt{d} around w⋆\mathbf{w}^{\star}. Then, ∇F(w⋆+z)=Az+r(z)\nabla F(\mathbf{w}^{\star}+\mathbf{z})=\mathbf{A}\mathbf{z}+\mathbf{r}(\mathbf{z}) with ∥r(z)∥2≤HR2∥z∥2\|\mathbf{r}(\mathbf{z})\|_2\le\frac{HR}{2}\|\mathbf{z}\|_2 in the ball. Hence, we believe that the same lower bound holds for SR-GD initialized in the ball if HRHR, i.e., HΔdH\Delta\sqrt{d}, is sufficiently small.

Reviewer_3ZhzOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies gradient descent with stochastic rounding on fixed-point grids for convex quadratic objectives, focusing primarily on the hitting time to reach a grid minimizer. The main result shows that convergence depends strongly on the eigenbasis of the Hessian, rather than only its spectrum as in standard gradient descent. For identical eigenvalues, a diagonal Hessian yields an O(log⁡d)O(\log d) hitting time, whereas a randomly rotated Hessian can lead to an eΩ(d)e^{\Omega(d)} hitting time. The authors also establish that the optimization error can remain Ω(Δ2d)\Omega(\Delta^2 d) for exponentially many iterations. Additional results cover Gaussian least squares, rank-deficient Hessians, where optimization error and hitting time can behave differently, and the case where the continuous minimizer is off-grid. The paper is theoretical, with proofs provided in the appendices.

Critical strengths
  1. Strong eigenbasis dependence: The main contribution is the striking separation between logarithmic and exponential hitting times for Hessians with identical eigenvalues and bounded condition numbers. This contrasts with standard gradient descent, whose convergence rate depends on the spectrum. The exponential lower bound is also matched by an eO(d)e^{O(d)} upper bound, making the result tight in the exponent.

  2. Persistent optimization error: The phenomenon extends beyond the exact hitting time. Starting from a single incorrect coordinate, stochastic rounding can produce Ω(d)\Omega(d) incorrect coordinates, with an optimization error of Ω(Δ2d)\Omega(\Delta^2 d) persisting for exponentially many iterations. The extensions to Gaussian least squares and rank-deficient Hessians, where objective error and Hamming distance can exhibit different behaviors, further strengthen the theoretical contribution.

Critical weaknesses
  1. Unclear practical relevance: The analysis focuses on quadratic objectives with exact gradients, constant stepsizes, fixed-point grids, and independent coordinate-wise rounding. It remains unclear whether the exponential hitting times arise at practically relevant dimensions and numerical precisions. The absence of numerical experiments also makes it difficult to assess the practical implications, although the paper is primarily theoretical.

  2. Some claims require qualification: The comparison with Li et al. (2017) is not entirely precise. The authors suggest that their persistent Ω(Δ2d)\Omega(\Delta^2 d) error establishes the tightness of previous upper bounds, but Li et al. analyze averaged iterates with decreasing stepsizes, rather than individual iterates with constant stepsizes. Thus, the lower bound does not directly establish tightness of those guarantees. Similarly, the off-grid upper bound eO(dlog⁡d)e^{O(d\log d)} stated in Section 4 appears more general than Proposition 45, which assumes that w⋆w^\star lies within the grid's bounding box. These issues do not undermine the main result but call for more precise statements.

Questions for authors
  1. Theorem 1 establishes a persistent Ω(Δ2d)\Omega(\Delta^2 d) error for individual iterates, whereas Li et al. (2017) consider averaged iterates with decreasing stepsizes. In what sense does this lower bound establish the tightness of their upper bounds?

  2. Section 4 states an eO(dlog⁡d)e^{O(d\log d)} upper bound for the off-grid case, but Proposition 45 assumes that w⋆w^\star lies within the grid's bounding box. Does the bound also hold when the minimizer lies outside this box, or should the statement be restricted?

5 comments

We thank the reviewer for their positive evaluation and valuable feedback. We address the reviewer's comments below and revised our draft accordingly, where all the updates are colored in blue.

C1. Unclear practical relevance.

R1. Following the reviewer's comment, we added numerical experiments in Appendix H of the revised draft. In our basic setup, we run SR-GD on the 8-bit fixed-point grid on [−4,4][-4,4], i.e., M=127M=127 and Δ=4/127\Delta=4/127, with the step size η=0.8/λmax⁡(A)\eta=0.8/\lambda_{\max}(\mathbf{A}) (Appendix H.1). We then extend this setup to fixed-point grids with 44, 88, 1616, and 3232 bits, to floating-point grids in the FP8, FP16, and FP32 formats, and to non-quadratic objectives, including logistic regression on the Gisette dataset, softmax regression on the MNIST dataset, and a two-layer network that learns a teacher model on MNIST images. For each experiment, we run multiple trajectories, i.e., independent runs of SR-GD, which differ in the stochastic rounding. For a random Hessian, we sample multiple Hessians and run multiple trajectories for each of them.

Our main observations from theory are that (a) the hitting time of SR-GD depends on the eigenbasis of the Hessian, not only on its spectrum, (b) even from an initializer that differs from the minimizer in a single coordinate, the optimization error can increase and persist, and (c) the hitting time also depends on the location of the minimizer relative to the grid. We observe that they already appear at moderate dimensions (up to d=1024d=1024) and extend to other precisions and to non-quadratic objectives as follows.

  • Dimensions (Appendices H.3, H.4, and H.6). For (a), for the same spectrum, the median hitting time of a Haar-random eigenbasis increases rapidly with dd and exceeds our time horizon for d>64d>64, whereas SR-GD reaches the grid minimizer within a few iterations for the diagonal Hessian. For (b), even from an initializer that differs from the grid minimizer in a single coordinate, almost every trajectory keeps a Hamming distance of order dd and an optimization error of order Δ2d\Delta^2d for large dd, as in Theorem 1. We observe the same for Gaussian least squares with a sample size proportional to dd, as in Theorem 4. For (c), for A=Id\mathbf{A}=\mathbf{I}_d, moving the minimizer away from the grid by a quarter of the grid spacing in every coordinate makes the hitting time increase rapidly with dd, as in Case (ii) of Theorem 12. That is, these phenomena already arise at dimensions much smaller than those of practical models.
  • Precisions (Appendices H.7 and H.8). All of (a)–(c) hold at every tested precision, i.e., for 44, 88, 1616, and 3232 bits, as our results hold for every Δ>0\Delta>0. We also repeat the experiments on the eigenbasis and on the location of the minimizer, where each coordinate is stochastically rounded to the values representable in FP8, FP16, or FP32, whose spacing varies with the magnitude. Here, the hitting time still depends on both (a) the eigenbasis and (c) the location of the minimizer.
  • Smooth non-quadratic objectives (Appendix H.9). We consider f(w)=∑j=1dcjρ(qj⊤w)+λ2∥∥w∥∥22f(\mathbf{w})=\sum_{j=1}^d c_j\rho(\mathbf{q}_j^\top\mathbf{w})+\frac{\lambda}{2}\|\|\mathbf{w}\|\|_2^2, where ρ\rho is a logistic or Cauchy loss with ρ(0)=ρ′(0)=0\rho(0)=\rho'(0)=0 and ρ′′(0)=1\rho''(0)=1, half of the coefficients cjc_j are 44 and the others are 11, and [q1,…,qd][\mathbf{q}_1,\ldots,\mathbf{q}_d] is a Haar-random orthogonal matrix or the identity matrix. Here, the logistic loss with λ=0\lambda=0 and λ=1/4\lambda=1/4 and the Cauchy loss with λ=1/4\lambda=1/4 give convex, strongly convex, and nonconvex objectives, respectively, which are not quadratic in any neighborhood of their minimizer 0\mathbf{0}. For both eigenbases, 0\mathbf{0} is the unique grid minimizer, and the Hessian at 0\mathbf{0} has the same eigenvalues cj+λc_j+\lambda. We run SR-GD from an initializer that differs from 0\mathbf{0} in every coordinate. For (a), SR-GD is slow for the Haar-random eigenbasis and fast for the identity eigenbasis. For (b), the optimization error of the Haar-random eigenbasis persists at the order of Δ2d\Delta^2d for large dd, whereas GD decreases it rapidly. For (c), translating the objective by a quarter of the grid spacing in every coordinate makes SR-GD slow for the identity eigenbasis.
  • Non-quadratic objectives on real data (Appendix H.10). We consider three models with ℓ2\ell_2-regularization: logistic regression on the Gisette dataset (d=5,000d=5{,}000), softmax regression on the MNIST dataset (d=7,850d=7{,}850), and a two-layer network with 88 hidden units and tanh⁡\tanh activations that learns a teacher model on 2,0002{,}000 MNIST images (d=6,370d=6{,}370). Here, objectives and gradients are computed in FP32. For each model, we first compute a stationary point u\mathbf{u} numerically. We then compare the original grid {u+z:z∈W}\{\mathbf{u}+\mathbf{z}:\mathbf{z}\in\mathcal{W}\} with the aligned grid {u+Qz:z∈W}\{\mathbf{u}+\mathbf{Q}\mathbf{z}:\mathbf{z}\in\mathcal{W}\}, where the columns of Q\mathbf{Q} are the eigenvectors of the Hessian at u\mathbf{u}. That is, the aligned grid makes the Hessian at u\mathbf{u} diagonal in the grid coordinates. We also translate both grids slightly, so that u\mathbf{u} lies off the grid. SR-GD starts from initializers that differ from u\mathbf{u} by the grid spacing in a single coordinate, by the grid spacing in many coordinates, or by random multiples of the grid spacing. For (a), on the original grid, SR-GD from initializers that differ from u\mathbf{u} in many coordinates does not reach it within our time horizon, whereas on the aligned grid, SR-GD reaches u\mathbf{u} from every initializer. For (b), on the original grid, even from initializers that differ in a single coordinate, the Hamming distance spreads to many coordinates, and for logistic and softmax regression, the optimization error increases. For (c), the translation of the aligned grid slows down SR-GD.

These results suggest that, in low-precision training with stochastic rounding, the convergence can depend on how the eigenbasis of the Hessian is aligned with the coordinate grid and where the minimizer lies relative to the grid, not only on the spectrum of the Hessian. We refer to Appendix H for the full details of the setup and the detailed discussions of each experiment.

C2. The comparison with Li et al. (2017) is not entirely precise. In what sense does this lower bound establish the tightness of their upper bounds?

R2. We thank the reviewer for pointing this out. As the reviewer mentioned, Li et al. (2017) consider averaged iterates with decreasing step sizes, and hence our lower bound does not establish the tightness of their bound. On the other hand, Li and De Sa (2019) consider a uniformly selected iterate with a constant step size. In our setting with exact gradients and a sufficiently small constant step size, their upper bound becomes O(Δ2d)O(\Delta^2d), while Theorem 1 shows that, with high probability, the optimization error is Ω(Δ2d)\Omega(\Delta^2d) from O(log⁡log⁡d)O(\log\log d) iterations up to eρde^{\rho d} iterations. Hence, their bound is tight up to a constant factor for every horizon TT with Ω(log⁡log⁡d)≤T≤eρd\Omega(\log\log d)\le T\le e^{\rho d}, even though the minimizer lies on the grid. We note that this is not the case as T→∞T\to\infty, since the on-grid minimizer is absorbing and SR-GD reaches it within eO(d)e^{O(d)} iterations with high probability (Theorem 2).

Following the reviewer's comment, we revised the corresponding statements in the introduction and Section 3.1 as follows.

  • Introduction.
    • Original: "Hence, even from an initial Hamming distance of O(1)O(1), the optimization error increases from O(Δ2)O(\Delta^2) to Ω(Δ2d)\Omega(\Delta^2d) and stays there over this horizon, i.e., the Δ2d\Delta^2d error in the existing upper bounds of Li et al. (2017) and Li and De Sa (2019) can be attained."
    • Revised: "Hence, even from an initial Hamming distance of O(1)O(1), the optimization error increases from O(Δ2)O(\Delta^2) to Ω(Δ2d)\Omega(\Delta^2d) and stays there over this horizon. In particular, for a small constant step size, the Δ2d\Delta^2d error in the upper bound of Li and De Sa (2019) for a uniformly selected iterate is tight up to a constant factor over this horizon."
  • Section 3.1.
    • Original: "This shows that the Δ2d\Delta^2d error in the upper bounds of Li et al. (2017) and Li and De Sa (2019) can be attained and persist for exponentially many iterations."
    • Revised: "In particular, for a small constant step size and exact gradients, the bound of Li and De Sa (2019, Theorem 1) on a uniformly selected iterate is O(Δ2d)O(\Delta^2d). Hence, it is tight up to a constant factor for every horizon TT with Ω(log⁡log⁡d)≤T≤eρd\Omega(\log\log d)\le T\le e^{\rho d}, even though the minimizer w⋆\mathbf{w}^{\star} lies on the grid. We note that Li et al. (2017) also give an upper bound of the same order, but for averaged iterates with decreasing step sizes."

C3. The off-grid upper bound eO(dlog⁡d)e^{O(d\log d)} stated in Section 4 appears more general than Proposition 45.

R3. We thank the reviewer for pointing this out. The reviewer is correct, and the statement in Section 4 should be restricted, since Proposition 45 assumes w⋆∈[−MΔ,MΔ]d\mathbf{w}^{\star}\in[-M\Delta,M\Delta]^d in addition to κ(A)≤K\kappa(\mathbf{A})\le K. Following the reviewer's comment, we revised Section 4 as follows.

  • Original: "The upper bound in Theorem 2 also extends up to a logarithmic factor in the exponent: τM≤eO(dlog⁡d)\tau_{\mathcal M}\le e^{O(d\log d)} with probability at least 1−e−d1-e^{-d} over rounding (Proposition 45 in Appendix)."
  • Revised: "The upper bound in Theorem 2 also extends up to a logarithmic factor in the exponent: for w⋆∈[−MΔ,MΔ]d\mathbf{w}^{\star}\in[-M\Delta,M\Delta]^d, τM≤eO(dlog⁡d)\tau_{\mathcal M}\le e^{O(d\log d)} with probability at least 1−e−d1-e^{-d} over rounding (Proposition 45 in Appendix)."

We would be happy to clarify any concerns or answer any questions that may come up during the discussion period.

[Li et al., 2017] Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. NeurIPS, 2017.

[Li and De Sa, 2019] Zheng Li and Christopher De Sa. Dimension-free bounds for low-precision training. NeurIPS, 2019.

Reviewer_FyozOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the convergence behavior of gradient descent with stochastic rounding (SR-GD) when iterates are constrained to a finite fixed-point grid. The analysis focuses on convex quadratic objectives

f(w)=12(w−w⋆)⊤A(w−w∗),A⪰0,f(w)=\frac12(w-w^\star)^\top A(w-w^*), \qquad A\succeq 0,

with a fixed step size η=S/λmax⁡(A)\eta=S/\lambda_{\max}(A), where S∈(0,1)S\in(0,1).

Rather than studying the usual convergence rate in function values, the authors investigate the hitting time: the first iteration at which SR-GD reaches a minimizer of the objective over the discrete grid.

The contributions of the paper are theoretical ones : exponential hitting times are proven on a discrete gris, as well as fast convergence for strctured Hessians.

Critical strengths

The mathematical analysis of the paper seems to be correct (at least all the proofs I checked are correct). Tight lower and upper bounds are given.

Critical weaknesses

Is the hitting time a relevant convergence criterion? The authors even show in Theorem 8 that the optimization error may become small much eerlier than the hitting time. This questions the interest/relevance of such a convergence criterion.

The setting of the paper is very limited (quadratic functions), and there is no numercial study. I am not convinced that such a paper will have much interest among ICLR attendees.

Questions for authors

The authors should comment about their choice of convergence criterion. Could they also provide some numerical experiments to show that their theoretical findings can be enlarged to functions beyond the quadratic case ?

7 comments

We thank the reviewer for their valuable comments. We address the reviewer's comments below and revised our draft accordingly, where all the updates are colored in blue.

C1. Is the hitting time a relevant convergence criterion?

R1. We would like to clarify that our hitting time analysis follows the classical convergence analysis in convex optimization. Specifically, it is often said that the iterates w(t)\mathbf{w}^{(t)} of an optimization algorithm converge if the following condition holds (with high probability):

for any ε>0, there exists T such that min⁡0≤t≤Tf(w(t))−f∗≤ε,\text{for any } \varepsilon>0, \text{ there exists } T \text{ such that } \min_{0\le t\le T} f(\mathbf{w}^{(t)})-f^*\le\varepsilon,

where f∗f^* is the optimal objective value. Here, the upper and lower bounds on TT as functions of ε\varepsilon, the dimension, etc. determine the speed of convergence.

In our setting, the iterates lie on the grid, and hence f∗f^* is replaced by the minimum objective value fW⋆f^{\star}_{\mathcal{W}} over the grid. Since the gap between the smallest and the second smallest objective values on the grid is strictly positive, the above condition reduces to

there exists T such that w(t)∈M for some 0≤t≤T,\text{there exists } T \text{ such that } \mathbf{w}^{(t)}\in\mathcal{M} \text{ for some } 0\le t\le T,

where M\mathcal{M} is the set of grid minimizers. That is, SR-GD converges if and only if it hits a grid minimizer, and for sufficiently small ε\varepsilon, the number of iterations required to achieve f(w(t))−fW⋆≤εf(\mathbf{w}^{(t)})-f^{\star}_{\mathcal{W}}\le\varepsilon is exactly the hitting time. In this sense, the hitting time determines the speed of convergence in our setting, and understanding it is the primary objective of our paper.

C2. In Theorem 8, the optimization error may become small much earlier than the hitting time.

R2. Following our response to C1, the hitting time is the number of iterations required to reach the exact minimum on the grid, i.e., to achieve an optimization error smaller than the gap between the smallest and the second smallest objective values on the grid. Hence, the hitting time characterizes the speed of convergence only for such small ε\varepsilon, and the number of iterations required to achieve a moderately small ε\varepsilon can be much smaller. Theorem 8 shows this difference: for r=o(d)r=o(d) and an initial Hamming distance Ω(d)\Omega(d), SR-GD achieves an optimization error of O(Δ2r)O(\Delta^2 r) within O(log⁡(d/r))O(\log(d/r)) iterations, while reaching the exact minimum, i.e., achieving an optimization error smaller than the gap, requires more than (d/r)1−ϵ(d/r)^{1-\epsilon} iterations for any constant ϵ∈(0,1)\epsilon\in(0,1) with probability 1−o(1)1-o(1). Following the reviewer's comment, we revised our draft to clearly distinguish these two notions (the paragraph "Hitting time, Hamming distance, and optimization error" in Section 2).

This phenomenon is analogous to the distance to the optimum in gradient descent on ill-conditioned quadratic objectives over the reals. In this case, the objective lower bounds the squared distance to the optimum only up to the smallest eigenvalue of the Hessian, i.e., f(u)−f(w⋆)≥12λmin⁡(A)∥u−w⋆∥22f(\mathbf{u})-f(\mathbf{w}^{\star})\ge\frac{1}{2}\lambda_{\min}(\mathbf{A})\lVert\mathbf{u}-\mathbf{w}^{\star}\rVert_2^2. Hence, if the smallest eigenvalue is very small, the objective can become small quickly while the iterate stays far from the optimum for a long time. On the grid, Eq. (3) plays the same role, where the distance to the optimum and the smallest eigenvalue are replaced by the Hamming distance and the restricted eigenvalue λmin⁡(A;W−w⋆)\lambda_{\min}(\mathbf{A};\mathcal{W}-\mathbf{w}^{\star}), respectively. If the restricted eigenvalue is bounded below, a large Hamming distance implies a large optimization error. For example, in Theorem 1, if the initial Hamming distance is Ω(d)\Omega(d), the optimization error itself stays Ω(Δ2d)\Omega(\Delta^2 d) for exponentially many iterations, i.e., even a moderately small ε\varepsilon requires exponentially many iterations. On the other hand, in Theorem 8, SR-GD achieves an optimization error of O(Δ2r)O(\Delta^2r) while the Hamming distance stays Ω(d)\Omega(d). Hence, by Eq. (3), the restricted eigenvalue is O(r/d)O(r/d). We added this discussion in Section 3.3 of the revised draft.

C3. The setting of the paper is very limited (quadratic functions).

R3. We believe that our results are of interest to the ICLR community. Low-precision training reduces the memory and computation costs of large models, and stochastic rounding is widely used when updates are applied in low precision (see Section 1). However, since existing analyses of stochastic rounding provide only upper bounds, it was unclear whether the intuition from GD over the reals, e.g., that the spectrum of the Hessian determines the convergence speed, remains valid. Our results show that it does not, even for quadratic objectives, which are often considered one of the easiest cases: for a bounded condition number and an eigenvalue variance bounded below, the hitting time is exponential in dd for most Hessians with a given spectrum (Theorem 1), and also for Gaussian least squares with a sample size proportional to dd (Theorem 4). In contrast, it is O(log⁡d)O(\log d) for the diagonal Hessian with the same spectrum (Section 3.2). That is, the hitting time depends on the eigenbasis of the Hessian.

Furthermore, although our results are shown for quadratic objectives, they also apply to broader classes of objectives, including convex and nonconvex ones. In optimization theory, upper bounds are usually shown for all objectives in a class, while lower bounds are usually shown by specific hard examples. This is because a lower bound on the worst case over a class of interest (e.g., smooth objectives) only requires hard examples in the class, which typically contains both easy examples (e.g., strongly convex objectives for GD) and hard examples (e.g., Nesterov, 2013; Du et al., 2017). Our main results, i.e., the lower bounds on the hitting time and the dependence of the hitting time on the eigenbasis, are shown in the same way, but for a large class of quadratic objectives rather than a few specific examples. This class is contained in many classes of interest. For example, since the quadratic objectives in Theorem 1 are strongly convex and smooth, our results directly hold for the classes of strongly convex, convex, and smooth (possibly nonconvex) objectives.

Finally, our hard examples can also be extended to non-quadratic objectives. Following the reviewer's comment, we added the following results to the revised draft (the paragraph "Extensions to non-quadratic objectives" in Section 3.1 and Appendix G).

  • Locally quadratic objectives (Corollary 59). If an objective coincides with a quadratic objective satisfying the assumptions of Theorem 1 in a ball of radius CΔdC\Delta\sqrt{d} around an interior grid point v\mathbf{v} for a sufficiently large constant CC, then SR-GD initialized in the ball stays there for eΩ(d)e^{\Omega(d)} iterations with high probability, and the same lower bounds hold. Outside the ball, the objective can be any differentiable function, convex or nonconvex.
  • Separable perturbations (Corollary 60). For f(w)+∑i=1dpi(wi−wi⋆)f(\mathbf{w})+\sum_{i=1}^d p_i(w_i-w_i^{\star}), where ff is a quadratic objective satisfying the assumptions of Theorem 1 and each pip_i is differentiable with pi(0)=pi′(0)=0p_i(0)=p_i'(0)=0, pi≥0p_i\ge0, and ∣pi′(t)∣≤P∣t∣|p_i'(t)|\le P|t| for a constant P≥0P\ge0, the same lower bounds hold with η=S/(λmax⁡(A)+P)\eta=S/(\lambda_{\max}(\mathbf{A})+P). For example, with the Cauchy penalty pi(t)=λσ22log⁡(1+t2/σ2)p_i(t)=\frac{\lambda\sigma^2}{2}\log(1+t^2/\sigma^2), this objective is not quadratic in any neighborhood of its minimizer, and it is strongly convex, convex, or nonconvex depending on λ\lambda.

C4. On numerical experiments.

R4. Following the reviewer's comment, we added numerical experiments in Appendix H of the revised draft. In our basic setup, we run SR-GD on the 8-bit fixed-point grid on [−4,4][-4,4], i.e., M=127M=127 and Δ=4/127\Delta=4/127, with the step size η=0.8/λmax⁡(A)\eta=0.8/\lambda_{\max}(\mathbf{A}) (Appendix H.1). For each experiment, we run multiple trajectories, i.e., independent runs of SR-GD, which differ in the stochastic rounding. For a random Hessian, we sample multiple Hessians and run multiple trajectories for each of them.

We first examine whether our main observations extend beyond the quadratic case. Here, our main observations from theory are that (a) the hitting time of SR-GD depends on the eigenbasis of the Hessian, not only on its spectrum, (b) even from an initializer that differs from the minimizer in a single coordinate, the optimization error can increase and persist, and (c) the hitting time also depends on the location of the minimizer relative to the grid. We observe that they extend to the following non-quadratic objectives.

  • Smooth non-quadratic objectives (Appendix H.9). We consider f(w)=∑j=1dcjρ(qj⊤w)+λ2∥∥w∥∥22f(\mathbf{w})=\sum_{j=1}^d c_j\rho(\mathbf{q}_j^\top\mathbf{w})+\frac{\lambda}{2}\|\|\mathbf{w}\|\|_2^2, where ρ\rho is a logistic or Cauchy loss with ρ(0)=ρ′(0)=0\rho(0)=\rho'(0)=0 and ρ′′(0)=1\rho''(0)=1, half of the coefficients cjc_j are 44 and the others are 11, and [q1,…,qd][\mathbf{q}_1,\ldots,\mathbf{q}_d] is a Haar-random orthogonal matrix or the identity matrix. Here, the logistic loss with λ=0\lambda=0 and λ=1/4\lambda=1/4 and the Cauchy loss with λ=1/4\lambda=1/4 give convex, strongly convex, and nonconvex objectives, respectively, which are not quadratic in any neighborhood of their minimizer 0\mathbf{0}. For both eigenbases, 0\mathbf{0} is the unique grid minimizer, and the Hessian at 0\mathbf{0} has the same eigenvalues cj+λc_j+\lambda. We run SR-GD from an initializer that differs from 0\mathbf{0} in every coordinate. For (a), SR-GD is slow for the Haar-random eigenbasis and fast for the identity eigenbasis, as for quadratic objectives. In particular, the median hitting time of the Haar-random eigenbasis increases rapidly with dd. Since the strongly convex and nonconvex objectives, which have the same Hessian at the minimizer, behave similarly, the behavior of SR-GD depends on the Hessian at the minimizer rather than on convexity. For (b), the optimization error of the Haar-random eigenbasis persists at the order of Δ2d\Delta^2d for large dd, whereas GD decreases it rapidly. For (c), translating the objective by a quarter of the grid spacing in every coordinate makes SR-GD slow for the identity eigenbasis, as in Case (ii) of Theorem 12.
  • Non-quadratic objectives on real data (Appendix H.10). We consider three models with ℓ2\ell_2-regularization: logistic regression on the Gisette dataset (d=5,000d=5{,}000), softmax regression on the MNIST dataset (d=7,850d=7{,}850), and a two-layer network with 88 hidden units and tanh⁡\tanh activations that learns a teacher model on 2,0002{,}000 MNIST images (d=6,370d=6{,}370). Here, objectives and gradients are computed in FP32. For each model, we first compute a stationary point u\mathbf{u} numerically. We then compare the original grid {u+z:z∈W}\{\mathbf{u}+\mathbf{z}:\mathbf{z}\in\mathcal{W}\} with the aligned grid {u+Qz:z∈W}\{\mathbf{u}+\mathbf{Q}\mathbf{z}:\mathbf{z}\in\mathcal{W}\}, where the columns of Q\mathbf{Q} are the eigenvectors of the Hessian at u\mathbf{u}. That is, the aligned grid makes the Hessian at u\mathbf{u} diagonal in the grid coordinates, as for the diagonal Hessian in Section 3.2. We also translate both grids slightly, so that u\mathbf{u} lies off the grid. SR-GD starts from initializers that differ from u\mathbf{u} by the grid spacing in a single coordinate, by the grid spacing in many coordinates, or by random multiples of the grid spacing. For (a), on the original grid, SR-GD from initializers that differ from u\mathbf{u} in many coordinates does not reach it within our time horizon, whereas on the aligned grid, SR-GD reaches u\mathbf{u} from every initializer. For (b), on the original grid, even from initializers that differ in a single coordinate, the Hamming distance spreads to many coordinates, and for logistic and softmax regression, the optimization error increases. For (c), the translation of the aligned grid slows down SR-GD.

We note that these objectives are not covered by our extensions in our response to C3 (Corollaries 59 and 60). That is, our experiments suggest that our main observations extend to broader classes of non-quadratic objectives, including nonconvex ones and those on real data.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.