On the Convergence of Stochastic Gradient Descent in Low-precision Number Formats

• URL: http://arxiv.org/abs/2301.01651v1
• Date: Wed, 4 Jan 2023 14:54:15 GMT
• Title: On the Convergence of Stochastic Gradient Descent in Low-precision Number Formats
• Abstract summary: The convergence of single-precision Gradient Descent (SGD) is normally aligned with the theoretical results of real numbers. However, the numerical error increases when the computations are performed in low-precision number formats. This provides compelling reasons to study the SGD convergence adapted for low-precision computations.
• Score: 3.408623772471354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep learning models are dominating almost all artificial intelligence tasks such as vision, text, and speech processing. Stochastic Gradient Descent (SGD) is the main tool for training such models, where the computations are usually performed in single-precision floating-point number format. The convergence of single-precision SGD is normally aligned with the theoretical results of real numbers since they exhibit negligible error. However, the numerical error increases when the computations are performed in low-precision number formats. This provides compelling reasons to study the SGD convergence adapted for low-precision computations. We present both deterministic and stochastic analysis of the SGD algorithm, obtaining bounds that show the effect of number format. Such bounds can provide guidelines as to how SGD convergence is affected when constraints render the possibility of performing high-precision computations remote.

Related papers

• FPScan: An Automated Constraint-Based Analyzer for Floating-Point Anomaly Detection [0.0]
  FPScan is a novel tool to formally define and detect catastrophic cancellation and absorption in floating-point programs.<n>Our approach starts with a custom static analyzer based on abstract interpretation to infer the order of magnitude of all program variables.<n>Off-the-shelf SMT solver is used to determine whether the program exhibits any of these critical numerical pitfalls.
  arXiv  Detail & Related papers  (2026-09-07T13:41:01Z)
• DEL: Digit Entropy Loss for Numerical Learning of Large Language Models [63.37357414497361]
  Number prediction is a fundamental capability of large language models (LLMs) in mathematical problem-solving and code generation.<n>We present Digit Entropy Loss (DEL) for auto-regressive numerical learning.<n>Our formulation can incorporate integers, decimals, and decimal points, expanding the learning objective from a single digit to the floating-point number domain.
  arXiv  Detail & Related papers  (2026-05-19T18:18:59Z)
• A Convergence Analysis of Adaptive Optimizers under Floating-point Quantization [32.97211471008323]
  We introduce the first theoretical framework of adaptive convergences, including Adam and Muon, under floating-point quantization of gradients, weights, and states.<n>We show that both algorithms retain convergence rates close to their full-precision counterparts provided mantissa length scales only logarithmically with the number of iterations.<n>Our analysis further reveals that Adam is highly sensitive to and second-moment quantization weights due to its reliance on $beta to 1$, while Muon requires weaker error control and is thus potentially more robust.
  arXiv  Detail & Related papers  (2025-10-24T10:16:23Z)
• Dimension-adapted Momentum Outscales SGD [22.487084876365213]
  We investigate scaling laws for momentum algorithms with small batch on the power law random model.<n>When trained with a momentum algorithm, our analysis reveals four distinct loss curve determined by varying data-target complexities.<n>While traditional gradient descent with momentum (SGDM) yields identical scaling law exponents to SGD, dimension-adapted Nesterov acceleration (DANA) improves these exponents.
  arXiv  Detail & Related papers  (2025-05-22T00:58:50Z)
• Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference [55.150117654242706]
  We show that model selection for computation-aware GPs trained on 1.8 million data points can be done within a few hours on a single GPU. As a result of this work, Gaussian processes can be trained on large-scale datasets without significantly compromising their ability to quantify uncertainty.
  arXiv  Detail & Related papers  (2024-11-01T21:11:48Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• Guaranteed Approximation Bounds for Mixed-Precision Neural Operators [83.64404557466528]
  We build on intuition that neural operator learning inherently induces an approximation error. We show that our approach reduces GPU memory usage by up to 50% and improves throughput by 58% with little or no reduction in accuracy.
  arXiv  Detail & Related papers  (2023-07-27T17:42:06Z)
• Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo Line Search [0.8158530638728501]
  We show that SGD performs better than other deep learning networks when it uses deep numerical line. The results indicate that the number of steps needed for SFO as the batch size grows can be estimated.
  arXiv  Detail & Related papers  (2023-07-25T21:59:17Z)
• Variants of SGD for Lipschitz Continuous Loss Functions in Low-Precision Environments [6.418044102466421]
  It is assumed that only an approximation of the loss function's gradient can be computed in addition to error in computing the SGD step itself. Different variants of SGD are tested empirically, where improved test set accuracy is observed compared to SGD for two image recognition tasks.
  arXiv  Detail & Related papers  (2022-11-09T03:04:34Z)
• Low-Precision Arithmetic for Fast Gaussian Processes [39.720581185327816]
  Low-precision arithmetic has had a transformative effect on the training of neural networks. We propose a multi-faceted approach involving conjugate gradients with re-orthogonalization, mixed precision, and preconditioning. Our approach significantly improves the numerical stability and practical performance of conjugate gradients in low-precision over a wide range of settings.
  arXiv  Detail & Related papers  (2022-07-14T12:20:46Z)
• Low-Precision Stochastic Gradient Langevin Dynamics [70.69923368584588]
  We provide the first study of low-precision Gradient Langevin Dynamics, showing that its costs can be significantly reduced without sacrificing performance. We develop a new quantization function for SGLD that preserves the variance in each update step. We demonstrate that low-precision SGLD achieves comparable performance to full-precision SGLD with only 8 bits on a variety of deep learning tasks.
  arXiv  Detail & Related papers  (2022-06-20T17:25:41Z)
• An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models [37.63410634069547]
  We propose to exponentially increase the step-size of the Gaussian descent (GD) algorithm. We then consider using the EGD algorithm for solving parameter estimation under non-regular statistical models. The total computational complexity of the EGD algorithm is emphoptimal and exponentially cheaper than that of the GD for solving parameter estimation in non-regular statistical models.
  arXiv  Detail & Related papers  (2022-05-16T21:36:22Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
  arXiv  Detail & Related papers  (2022-02-26T19:10:48Z)
• Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits [21.353189917487512]
  gradient descent (SGD) and its variants have established themselves as the go-to algorithms for machine learning problems. We take a step forward by proving minibatch SGD converges to a critical point of the full log-likelihood loss function. Our theoretical guarantees hold provided that the kernel functions exhibit exponential or eigendecay.
  arXiv  Detail & Related papers  (2021-11-19T22:28:47Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.