- 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 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 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 , where is a logistic or Cauchy loss with and , half of the coefficients are and the others are , and is a Haar-random orthogonal matrix or the identity matrix. Here, the logistic loss with and and the Cauchy loss with give convex, strongly convex, and nonconvex objectives, respectively, which are not quadratic in any neighborhood of their minimizer . For both eigenbases, is the unique grid minimizer, and the Hessian at has the same eigenvalues . We run SR-GD from an initializer that differs from 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 for large , 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 -regularization: logistic regression on the Gisette dataset (), softmax regression on the MNIST dataset (), and a two-layer network with hidden units and activations that learns a teacher model on MNIST images (). Here, objectives and gradients are computed in FP32. For each model, we first compute a stationary point numerically. We then compare the original grid with the aligned grid , where the columns of are the eigenvectors of the Hessian at . That is, the aligned grid makes the Hessian at diagonal in the grid coordinates, as for the diagonal Hessian in Section 3.2. We also translate both grids slightly, so that lies off the grid. SR-GD starts from initializers that differ from 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 in many coordinates does not reach it within our time horizon, whereas on the aligned grid, SR-GD reaches 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 around an interior grid point for a sufficiently large constant , 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 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 need not be a global minimizer (Corollary 59).
- Separable perturbations. Consider an objective , where is a quadratic objective satisfying the assumptions of Theorem 1 and each is differentiable with , , and for a constant , e.g., the Cauchy penalty with . With the Cauchy penalty, this objective is not quadratic in any neighborhood of its minimizer. However, since , 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 (Corollary 60). For the Cauchy penalty, the objective is strongly convex if , convex but not strongly convex if , 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 , 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 . Hence, the nonlinear terms can reduce the spreading, e.g., when the gradient at becomes nearly parallel to 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 with smooth and a Haar-random orthogonal matrix , which reduce to Theorem 1 when each 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 does not depend on . That is, the iterates stay at distance of order 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 has a minimizer in the interior of the grid such that satisfies the assumptions of Theorem 1 and is -Lipschitz in a ball of radius around . Then, with in the ball. Hence, we believe that the same lower bound holds for SR-GD initialized in the ball if , i.e., , is sufficiently small.
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], i.e., M=127 and Δ=4/127, with the step size η=0.8/λmax(A) (Appendix H.1). We then extend this setup to fixed-point grids with 4, 8, 16, and 32 bits and to floating-point grids in the FP8, FP16, and FP32 formats. We consider three classes of objectives.
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=1024).