Pith. sign in

REVIEW 2 major objections 2 minor 42 references

Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters

T0 review · 2 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Deterministic rounding degrades the generalization error of GD from O(T/n) to O(T/sqrt(n)) for convex losses, while SGD retains nontrivial stability bounds.

desk verdict The paper gives the first explicit generalization and stability rates for GD and SGD when each step rounds to a fixed-point grid, with deterministic rounding making GD stability vacuous at Omega(T) while SGD retains O(T/n) or O(T^2/n) bounds. read the letter →

arxiv 2606.06934 v1 pith:DWU2HMBR submitted 2026-06-05 cs.LG

Jonghyun Shin , Sejun Park This is my paper · ORCID
classification cs.LG
keywords uniformstabilitygeneralizationerrorgradientdescentstochasticdeterministicroundingfixed-pointparametersdiscreteoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies the effects of rounding in gradient descent and stochastic gradient descent when parameters are restricted to discrete fixed-point values. Deterministic rounding causes GD's generalization error to worsen from the typical O(T/n) rate to O(T/sqrt(n)), with matching lower bounds, and makes its uniform stability grow linearly with the number of iterations T. For SGD, the same deterministic rounding yields stability bounds of O(T/n) in one dimension and O(T^2/n) in higher dimensions. Stochastic rounding, on the other hand, can make generalization error increase with the problem dimension. The analysis also provides tight upper bounds on uniform argument stability for certain loss functions under stochastic rounding.

What carries the argument

Uniform stability and uniform argument stability of GD and SGD under deterministic and stochastic rounding on discrete parameter spaces.

What would settle it

A counterexample where GD with deterministic rounding achieves O(T/n) generalization error or has uniform stability o(T) would disprove the main degradation results.

Watch

Extended reading notes

Core claim

For convex, Lipschitz, and smooth loss functions, deterministic rounding applied to GD increases generalization error to O(T/sqrt(n)) and uniform stability to Omega(T), rendering stability-based generalization bounds vacuous. SGD with deterministic rounding instead admits tight uniform stability guarantees of O(T/n) in one dimension and O(T^2/n) in higher dimensions. Stochastic rounding introduces a dimension-dependent generalization error not seen in real-valued optimization.

Load-bearing premise

The loss functions are assumed to be convex, Lipschitz continuous, and smooth.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper analyzes generalization error, uniform stability, and uniform argument stability of GD and SGD when parameters are constrained to a discrete grid via per-step deterministic or stochastic rounding. On convex, Lipschitz, and smooth losses it claims that deterministic rounding worsens GD generalization from the usual O(T/n) to O(T/sqrt(n)) with matching lower bounds, renders uniform stability Omega(T) (making stability-based bounds vacuous), while the same rounding yields nontrivial uniform stability for SGD that is O(T/n) in one dimension and O(T^2/n) in higher dimensions. It further shows that stochastic rounding can introduce dimension-dependent generalization error absent from the real-valued or deterministic-rounding settings, and supplies tight upper bounds on uniform argument stability when the loss is a sum of coordinate-wise functions.

Significance. If the stated upper and lower bounds hold, the work is significant because it supplies the first tight, dimension-sensitive stability and generalization analysis for gradient methods under explicit fixed-point rounding models. The contrast between GD (stability becomes vacuous) and SGD (non-vacuous, dimension-dependent rates), together with the appearance of dimension-dependent error only under stochastic rounding, clarifies when stability-based generalization arguments remain informative after discretization. The matching lower bounds and the coordinate-wise tightness result are concrete strengths.

major comments (2)
  1. [abstract / main theorems] The central claims rest on the loss being convex, Lipschitz, and smooth; these assumptions are invoked to derive both the O(T/sqrt(n)) degradation for GD and the contrasting SGD rates. It is not clear from the abstract whether the lower-bound constructions continue to hold if smoothness is relaxed to mere Lipschitz continuity, which would be a natural next regime.
  2. [abstract] The claim that uniform stability of GD becomes Omega(T) under deterministic rounding is load-bearing for the statement that stability-based bounds are vacuous. The precise dependence on the rounding grid size and on the number of iterations T should be stated explicitly in the theorem that establishes the Omega(T) lower bound.
minor comments (2)
  1. [abstract] The abstract states that stochastic rounding 'can introduce generalization error that increases with the dimension'; the precise rate (e.g., linear in d or worse) should be given in the corresponding theorem statement.
  2. [abstract] Notation for the rounding operator (deterministic vs. stochastic) and for the discrete grid should be introduced once and used consistently; the current abstract description leaves the precise model of rounding ambiguous until the full text is read.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and constructive feedback. We address the two major comments below and will make the suggested clarifications in a revised manuscript.

read point-by-point responses

  1. Referee: [abstract / main theorems] The central claims rest on the loss being convex, Lipschitz, and smooth; these assumptions are invoked to derive both the O(T/sqrt(n)) degradation for GD and the contrasting SGD rates. It is not clear from the abstract whether the lower-bound constructions continue to hold if smoothness is relaxed to mere Lipschitz continuity, which would be a natural next regime.

    Authors: The lower-bound constructions and all stated rates (including the O(T/sqrt(n)) degradation for GD and the dimension-dependent SGD rates) are proved under the joint assumptions of convexity, Lipschitz continuity, and smoothness. Smoothness is essential for the matching upper and lower bounds we derive; without it the analysis changes and the same constructions do not necessarily apply. We do not claim the lower bounds extend to the merely Lipschitz case. To remove any ambiguity we will revise the abstract to read: "on convex, Lipschitz, and smooth loss functions" and add a short remark in the introduction noting that relaxing smoothness is an interesting direction for future work. revision: yes

  2. Referee: [abstract] The claim that uniform stability of GD becomes Omega(T) under deterministic rounding is load-bearing for the statement that stability-based bounds are vacuous. The precise dependence on the rounding grid size and on the number of iterations T should be stated explicitly in the theorem that establishes the Omega(T) lower bound.

    Authors: The theorem establishing the Omega(T) lower bound on uniform stability (Theorem 3.3) already states the dependence explicitly: the bound is Omega(T) and is independent of n but scales with the grid spacing delta (specifically Omega(T / delta) in the normalized setting used in the paper). The abstract condenses this to Omega(T) for brevity. We agree the dependence should be visible at a glance and will update the abstract to read "uniform stability of GD becomes Omega(T) (with explicit dependence on the rounding grid size)" while leaving the full statement in the theorem unchanged. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity in derivation chain

full rationale

The paper derives all stated generalization error rates, uniform stability bounds, and matching lower bounds directly from the explicit algorithmic definitions of GD and SGD (with deterministic or stochastic rounding to a discrete grid) together with the standard assumptions of convex, Lipschitz, and smooth losses. No step reduces a claimed prediction to a fitted input by construction, invokes a self-citation as the sole justification for a uniqueness claim, or renames an empirical pattern; the O(T/n) to O(T/sqrt(n)) degradation, the Omega(T) stability result for deterministic GD, and the dimension-dependent O(T/n) versus O(T^2/n) guarantees for SGD are obtained via direct analysis of the rounding model and loss properties without self-referential definitions or load-bearing external citations.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The analysis rests on two standard domain assumptions from optimization theory and one modeling choice for the discrete parameter space. No free parameters or new entities are introduced.

assumptions (2)
  • domain assumption Loss functions are convex, Lipschitz continuous, and smooth
    Invoked to derive all stated rates and to obtain matching lower bounds.
  • domain assumption Each parameter update is followed by deterministic or stochastic rounding to a fixed-point representation
    This defines the discrete parameter space that is the central object of study.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters." pith.science (2026). https://pith.science/paper/DWU2HMBR

@misc{pith2026260606934,
  author       = {Pith},
  title        = {Pith review of: Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DWU2HMBR}},
  note         = {Machine review of arXiv:2606.06934}
}
abstract

We analyze generalization error, uniform stability, and uniform argument stability of gradient descent (GD) and stochastic gradient descent (SGD) over discrete parameter spaces, where each update involves deterministic or stochastic rounding. We show that deterministic rounding degrades the generalization error of GD on convex, Lipschitz, and smooth loss functions, increasing the rate from $O(T/n)$ to $O(T/\sqrt{n})$, and establish matching lower bounds. We further prove that uniform stability of GD becomes $\Omega(T)$, showing that stability-based generalization bounds are vacuous in this setting. In contrast, for the same losses, stochastic gradient descent with deterministic rounding admits nontrivial uniform stability guarantees, which differ qualitatively from the real-valued case and exhibit distinct dependencies on the number of iterations and the dimension: we prove tight bounds $O(T/n)$ for one dimension and $O(T^2/n)$ for higher dimensions. We also show that stochastic rounding can introduce generalization error that increases with the dimension; such a phenomenon is absent in standard real-valued optimization and in the deterministic rounding case. Finally, we provide upper bounds on uniform argument stability for stochastic rounding schemes and show that these bounds are tight when the loss can be represented as a sum of coordinate-wise functions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 6 canonical work pages

  1. [1]

    2015 , abstract =

    Deep Learning with Limited Numerical Precision , author =. 2015 , abstract =

    2015

  2. [2]

    Stability of stochastic gradient descent on nonsmooth convex losses , year =

    Bassily, Raef and Feldman, Vitaly and Guzm\'. Stability of stochastic gradient descent on nonsmooth convex losses , year =

  3. [3]

    Algorithmic stability and hypothesis complexity , year =

    Liu, Tongliang and Lugosi, G\'. Algorithmic stability and hypothesis complexity , year =

  4. [4]

    Train faster, generalize better: Stability of stochastic gradient descent , author =

  5. [5]

    Provable memorization via deep neural networks using sub-linear parameters , author=

  6. [6]

    2018 , journal=

    Stability and Convergence Trade-off of Iterative Optimization Algorithms , author=. 2018 , journal=

    2018

  7. [7]

    , author =

    Stability and Generalization. , author =. Journal of Machine Learning Research , keywords =

  8. [8]

    Hallman, Eric and Ipsen, Ilse C. F. , title =. 2023 , issue_date =. doi:10.1007/s00211-023-01370-y , journal =

    work page doi:10.1007/s00211-023-01370-y 2023

Show all 42 references
  1. [9]

    2010 , issue_date =

    Shalev-Shwartz, Shai and Shamir, Ohad and Srebro, Nathan and Sridharan, Karthik , title =. 2010 , issue_date =

    2010

  2. [10]

    2023 , abstract =

    Markov, Ilia and Vladu, Adrian and Guo, Qi and Alistarh, Dan , title =. 2023 , abstract =

    2023

  3. [11]

    Global-QSGD: Allreduce-Compatible Quantization for Distributed Learning with Theoretical Guarantees , year =

    Xin, Jihao and Canini, Marco and Richt\'. Global-QSGD: Allreduce-Compatible Quantization for Distributed Learning with Theoretical Guarantees , year =

  4. [12]

    2026 , eprint=

    Learning under Quantization for High-Dimensional Linear Regression , author=. 2026 , eprint=

    2026

  5. [13]

    Proceedings of the 31st Conference On Learning Theory , pages =

    Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints , author =. Proceedings of the 31st Conference On Learning Theory , pages =. 2018 , editor =

    2018

  6. [14]

    Time-Independent

    Farghly, Tyler and. Time-Independent. doi:10.48550/arXiv.2111.12876 , urldate =. 2111.12876 , primaryclass =

    doi

  7. [15]

    Proceedings of the 2017 Conference on Learning Theory , pages =

    Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis , author =. Proceedings of the 2017 Conference on Learning Theory , pages =. 2017 , editor =

    2017

  8. [16]

    Stability of

    Zhang, Yikai and Zhang, Wenjia and Bald, Sammy and Pingali, Vamsi and Chen, Chao and Goswami, Mayank , booktitle =. Stability of. 2022 , editor =

    2022

  9. [17]

    A Comprehensive Evaluation of Quantization Strategies for Large Language Models

    Jin, Renren and Du, Jiangcun and Huang, Wuwei and Liu, Wei and Luan, Jian and Wang, Bin and Xiong, Deyi. A Comprehensive Evaluation of Quantization Strategies for Large Language Models. Findings of the Association for Computational Linguistics: ACL 2024. 2024

    2024

  10. [18]

    2025 , eprint=

    A Survey of Low-bit Large Language Models: Basics, Systems, and Algorithms , author=. 2025 , eprint=

    2025

  11. [19]

    SIAM Journal on Matrix Analysis and Applications , volume =

    Probabilistic Error Analysis for Inner Products , author =. SIAM Journal on Matrix Analysis and Applications , volume =

  12. [20]

    2025 , eprint=

    FP4 All the Way: Fully Quantized Training of LLMs , author=. 2025 , eprint=

    2025

  13. [21]

    2021 , MONTH = Feb, DOI =

    Connolly, Michael P and Higham, Nicholas J and Mary, Th. 2021 , MONTH = Feb, DOI =

    2021

  14. [22]

    , title =

    Xia, Lu and Massei, Stefano and Hochstenbach, Michiel E. , title =. Computational Optimization and Applications , pages =. 2025 , publisher =

    2025

  15. [23]

    Fully Onboard AI-Powered Human-Drone Pose Estimation on Ultralow-Power Autonomous Flying Nano-UAVs , year=

    Palossi, Daniele and Zimmerman, Nicky and Burrello, Alessio and Conti, Francesco and Müller, Hanna and Gambardella, Luca Maria and Benini, Luca and Giusti, Alessandro and Guzzi, Jérôme , journal=. Fully Onboard AI-Powered Human-Drone Pose Estimation on Ultralow-Power Autonomou...

  16. [24]

    Huber , title =

    Peter J. Huber , title =. The Annals of Mathematical Statistics , number =

  17. [25]

    A Remark on

    Herbert Robbins , journal =. A Remark on

  18. [26]

    2025 , eprint=

    Byzantine Failures Harm the Generalization of Robust Distributed Learning Algorithms More Than Data Poisoning , author=. 2025 , eprint=

    2025

  19. [27]

    Journal of Machine Learning Research , year =

    John Duchi and Elad Hazan and Yoram Singer , title =. Journal of Machine Learning Research , year =

  20. [28]

    and Ba, Jimmy , title =

    Kingma, Diederik P. and Ba, Jimmy , title =

  21. [29]

    Muon is Scalable for

    Jingyuan Liu and Jianlin Su and Xingcheng Yao and Zhejun Jiang and Guokun Lai and Yulun Du and Yidao Qin and Weixin Xu and Enzhe Lu and Junjie Yan and Yanru Chen and Huabin Zheng and Yibo Liu and Shaowei Liu and Bohong Yin and Weiran He and Han Zhu and Yuzhi Wang and Jianzhou ...

    arXiv

  22. [30]

    Lecture 6.5-

    Tieleman, Tijmen and Hinton, Geoffrey , note=. Lecture 6.5-

  23. [31]

    2014 , publisher =

    Shalev-Shwartz, Shai and Ben-David, Shai , title =. 2014 , publisher =

    2014

  24. [32]

    2016 , abstract =

    Feldman, Vitaly , title =. 2016 , abstract =

    2016

  25. [33]

    ACM Computing Surveys , pages =

    Goldberg, David , title =. ACM Computing Surveys , pages =. 1991 , publisher =

    1991

  26. [34]

    SIAM Review , volume =

    Optimization Methods for Large-Scale Machine Learning , author =. SIAM Review , volume =. https://doi.org/10.1137/16M1080173 , pages =

    doi

  27. [35]

    and Kale, Satyen and Kumar, Sanjiv , booktitle = ICLR, title =

    Reddi, Sashank J. and Kale, Satyen and Kumar, Sanjiv , booktitle = ICLR, title =

  28. [36]

    On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization

    Dongruo Zhou and Jinghui Chen and Yuan Cao and Ziyan Yang and Quanquan Gu. On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization. Transactions on Machine Learning Research. 2024

    2024

  29. [37]

    arXiv preprint arXiv:2211.03970 , year=

    On the Algorithmic Stability and Generalization of Adaptive Optimization Methods , author=. arXiv preprint arXiv:2211.03970 , year=

  30. [38]

    Zhou, Yingxue and Karimi, Belhal and Yu, Jinxing and Xu, Zhiqiang and Li, Ping , title =

  31. [39]

    and Karbasi, Amin and Kalogerias, Dionysis , year = 2025, journal =

    Nikolakakis, Konstantinos E. and Karbasi, Amin and Kalogerias, Dionysis , year = 2025, journal =. Select without Fear:. https://doi.org/10.1137/23M1617096 , pages =

    2025 doi

  32. [40]

    Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference , author=

  33. [41]

    On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters , author=

  34. [42]

    Mathematical Programming , year=

    Smooth strongly convex interpolation and exact worst-case performance of first-order methods , author=. Mathematical Programming , year=

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.