A Convergence Analysis of Adaptive Optimizers under Floating-point Quantization

## Abstract

Abstract The rapid scaling of large language models (LLMs) has made low-precision training essential for reducing memory, improving efficiency, and enabling larger models and datasets. Existing convergence theories for adaptive optimizers, however, assume all components are exact and neglect hardware-aware quantization, leaving open the question of why low-precision training remains effective. We introduce the first theoretical framework for analyzing the convergence of adaptive optimizers, including Adam and Muon, under floating-point quantization of gradients, weights, and optimizer states (e.g., moment estimates). Within this framework, we derive convergence rates on smooth non-convex objectives under standard stochastic gradient assumptions, explicitly characterizing how quantization errors from different components affect convergence. We show that both algorithms retain rates close to their full-precision counterparts provided mantissa length scales only logarithmically with the number of iterations. Our analysis further reveals that Adam is highly sensitive to weights and second-moment quantization due to its reliance on β 2 → 1 \beta_{2}\to 1 , while Muon requires weaker error control and is thus potentially more robust. These results narrow the gap between empirical success and theoretical understanding of low-precision training methods. Numerical experiments on synthetic and real-world data corroborate our theory.

## 1 Introduction

The rapid scaling of large language models (LLMs) has made low-precision training indispensable for modern deep learning. By reducing memory usage and improving computational efficiency, low-precision formats such as bfloat16 (BF16) and FP8 enable training with larger models and datasets on contemporary hardware accelerators (Peng et al., 2023; Fishman et al., 2025). The introduction of FP8 in Nvidia’s Hopper GPU architecture (NVIDIA, 2022; Micikevicius et al., 2022) further cements its role as a practical datatype for the next generation of LLM training. In practice, numerous frameworks now leverage mixed- or low-precision formats to quantize gradients, weights, and optimizer states (Liu et al., 2024, 2025), showing that aggressively quantized training can scale to trillion-token workloads without loss of accuracy.

Despite its empirical success, a rigorous theoretical understanding of quantization, particularly for adaptive optimizers like Adam (Kingma, 2014) with decoupled weight decay (Loshchilov and Hutter, 2019) and Muon (Jordan et al., 2024), which are widely used in practice, remain largely underdeveloped. Existing theoretical work on the non-convex optimization analysis under quantization has primarily focused on Stochastic Gradient Descent with quantized gradients (QSGD) (Alistarh et al., 2017). For example, Jiang and Agrawal (2018) established $\mathcal{O}(1/T^{1/4})$ convergence under unbiased quantization, while error-feedback mechanisms (Karimireddy et al., 2019) were later introduced to handle biased quantization with the same guarantees. Extensions to QSGD and Quantized SGDM with error feedback have been analyzed in various settings (Tang et al., 2019; Zheng et al., 2019; Koloskova et al., 2020), again achieving $\mathcal{O}(1/T^{1/4})$ rates. More recent efforts target Quantized Adam (Chen et al., 2021; Modoranu et al., 2024). Chen et al. (2021) proved convergence of Adam with quantized gradients and weights under error feedback achieves $\mathcal{O}(1/T^{1/4})$, but the method requires storing error terms for every parameter, which is memory-intensive and impractical for modern low-precision LLM training. Modoranu et al. (2024) reduced this cost by compressing error feedback with unbiased compression, proving $\mathcal{O}(1/T^{1/4})$ convergence for Adam with quantized gradients; however, their analysis omits optimizer state quantization and practical floating-point formats, which are increasingly central to low-bit LLM optimization (Dettmers et al., 2021; Xi et al., 2025; Fishman et al., 2025). This leaves a critical gap: practical low-bit training crucially involves the quantization of optimizer states (e.g., momentum and second-moment estimates), a component these analyses omit. Furthermore, these studies often rely on assumptions like unbiased quantization or error-feedback mechanisms that are not consistent with modern large-scale LLM training. Consequently, the community lacks a theoretical framework to explain the robust convergence observed when adaptive optimizers are quantized in all components during LLM training.

#### This paper.

The objective of this work is to develop the convergence analysis of adaptive optimization algorithms with a more practical quantization configuration. In particular, we develop the first analytical framework for quantized adaptive optimizers under floating-point quantization. More importantly, following the practical configuration (Liu et al., 2024), our framework explicitly models the quantization of all key components: gradients, weights, momentum, and second moments. We then establish convergence guarantees for both Adam and Muon optimizers, expressing the results as a function of the quantization errors in these components. This clearly reveals how each type of error individually affects convergence. Crucially, rather than relying on unbiased quantization assumptions or storing per-parameter error feedback, we require only relative error control, which aligns with the behavior of standard floating-point formats (FP32 $\to$ BF16 or FP8; Section [3](https://arxiv.org/html/2510.21314v1#S3), Figure [5](https://arxiv.org/html/2510.21314v1#A3.F5), [6](https://arxiv.org/html/2510.21314v1#A3.F6), [9](https://arxiv.org/html/2510.21314v1#A3.F9), [10](https://arxiv.org/html/2510.21314v1#A3.F10); see also (Kuzmin et al., 2022)).

We then summarize the main contributions of this work as follows:

- •
We introduce a rigorous analytical framework for adaptive optimizers under hardware-aware low-precision training, explicitly modeling the quantization of weights, gradients, and optimizer states (Section [3](https://arxiv.org/html/2510.21314v1#S3)). Unlike prior works that rely on unbiased quantization assumptions or error-feedback mechanisms, which are impractical in large-scale LLM training, we adopt a relative error model (Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1)) that faithfully captures the behavior of floating-point quantization. This facilitates a formal and rigorous convergence analysis for quantized adaptive optimization algorithms that closely align with real-world implementations.
- •
We provide the first convergence guarantees for quantized Adam (Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5)) and Muon (Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6)) on smooth non-convex objectives under the relative error quantization model (Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1)), which closely reflects the behavior of floating-point quantization. Our analysis shows that both methods attain the same convergence rates as their full-precision counterparts (Défossez et al., 2022; Shen et al., 2025), provided the mantissa length increases only logarithmically with the number of iterations, which is consistent with practical hardware precision.
- •
Our analysis in Theorems [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) and [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6) precisely characterizes how quantization errors in different components impact convergence.
Notably, we show that Adam is particularly sensitive to quantization of weights and second moments due to their dependence on $\beta_{2}$, which is typically set close to 1 for convergence in practice and theory. This aligns with empirical observations from Peng et al. (2023), where weights and second moments require slightly higher precision than gradients or the momentum. Our experiments (Figures [3](https://arxiv.org/html/2510.21314v1#S4.F3), [5](https://arxiv.org/html/2510.21314v1#A3.F5), [7](https://arxiv.org/html/2510.21314v1#A3.F7), [9](https://arxiv.org/html/2510.21314v1#A3.F9)) corroborate this, demonstrating graceful degradation with reduced precision and near full-precision performance at moderate mantissa lengths. In contrast, Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6) reveals that Muon is more tolerant to quantization, requiring weaker relative error conditions (e.g., $1/T^{1/2}$ versus $1/T^{2}$ for Adam). This robustness stems from the SVD-based sign operator in Muon, which avoids the amplification of quantization errors by the inverse square root of historical gradient variances. This theoretical insight also explains empirical findings in Liu et al. (2025) that Muon exhibits superior robustness to low-precision training compared to Adam.

Overall, our results narrow the gap between the empirical success of quantized adaptive training and its theoretical understanding, providing a foundation for analyzing and designing future low-precision optimization algorithms.

#### Notations.

Scalars are denoted by lowercase letters ($x,\ldots$), vectors by bold lowercase ($\mathbf{x},\ldots$), and matrices by bold uppercase ($\mathbf{X},\ldots$).
The $i$-th entry of $\mathbf{x}$ is $x_{i}$, and the $(i,j)$-th entry of $\mathbf{X}$ is $X_{ij}$.
The $\ell_{2}$ norm of $\mathbf{x}$ is $\|\mathbf{x}\|_{2}=\sqrt{\sum_{i}x_{i}^{2}}$, the Frobenius norm of $\mathbf{X}$ is $\|\mathbf{X}\|_{F}=\sqrt{\sum_{i,j}X_{ij}^{2}}$,
and the nuclear norm of $\mathbf{X}$ is $\|\mathbf{X}\|_{*}=\sum_{i}\sigma_{i}(\mathbf{X})$, where $\sigma_{i}(\mathbf{X})$ denotes the $i$-th singular value.
For $d\in\mathbb{N}^{+}$, let $[d]=\{1,2,\ldots,d\}$.
For real sequences $\{a_{t}\}$ and $\{b_{t}\}$, we write $a_{t}=O(b_{t})$ if there exist constants $C,N>0$ such that $a_{t}\leq Cb_{t}$ for all $t\geq N$;
$a_{t}=\Omega(b_{t})$ if $b_{t}=O(a_{t})$;
$a_{t}=\Theta(b_{t})$ if both $a_{t}=O(b_{t})$ and $a_{t}=\Omega(b_{t})$;
and we use $\tilde{O}(\cdot)$ and $\tilde{\Omega}(\cdot)$ to suppress logarithmic factors.
The quantization operator is $\mathcal{Q}(\cdot)$, with $x^{Q}$ denoting the quantized version of $x$.

## 2 Related Work

#### Adaptive Optimization.

Adaptive optimizers are a key part of deep learning because they can automatically respond to changes in the data. The progression of modern adaptive optimizers began with Adagrad (Duchi et al., 2011), which scales learning rates based on the accumulated sum of past squared gradients. Despite extensive convergence analysis (Zou et al., 2019; Chen et al., 2018; Shi et al., 2020; Li and Orabona, 2019; Faw et al., 2022), its aggressive learning rate decay often leads to premature stalling. RMSProp (Hinton et al., 2012) addressed this issue by using an exponentially decaying average of squared gradients instead, a method whose convergence has also been well-studied (Zaheer et al., 2018; De et al., 2018; Shi et al., 2020; Li et al., 2025). Adam (Kingma, 2014) then synthesized these ideas by incorporating momentum, effectively combining the adaptive learning rates of RMSProp with first-moment estimates. Its widespread success has motivated a vast body of theoretical work analyzing its convergence and implicit bias generalization under various settings (Reddi et al., 2018; Défossez et al., 2022; Zou et al., 2019; Chen et al., 2018; Zhang et al., 2022; Wang et al., 2022; Guo et al., 2021; Hong and Lin, 2023; Li et al., 2023; Wang et al., 2023; Zhang et al., 2025, 2024; Zou et al., 2023; Cattaneo et al., 2024; Tang et al., 2025). More recently, the Muon optimizer (Jordan et al., 2024) was proposed, which leverages a matrix-based perspective for optimization, with its convergence guarantees established by concurrent works (Shen et al., 2025; Sato et al., 2025).
While convergence guarantees for these methods have been established in high-precision settings, their behavior under the low-precision quantization common in modern large model training is not well understood, a gap that this paper aims to address.

#### Low-bit Training.

As the field of deep learning continues to advance rapidly, the scale of models, particularly Large Language Models (LLMs), has grown exponentially. Low precision training (Wang et al., 2018; Wortsman et al., 2023; Liu et al., 2023; Xi et al., 2024; Liu et al., 2024) has become a prominent technique in modern deep learning, offering reductions in both computational costs and memory requirements. Mixed-precision training typically performs forward and backward passes in low-precision formats like FP16 (Micikevicius et al., 2017) or the more stable, wider-range BF16 (Kalamkar et al., 2019), while maintaining master weights and optimizer states in FP32. The advent of hardware like NVIDIA’s Hopper GPU architecture (NVIDIA, 2022) has made 8-bit floating-point (FP8) training a practical reality for further efficiency gains (Micikevicius et al., 2022; Peng et al., 2023; Xi et al., 2025; Fishman et al., 2025). Even more aggressive approaches now extend to 4-bit (FP4) training (Wang et al., 2025; Zhou et al., 2025). Especially in adaptive optimization, the optimizer states can consume as much memory as the model parameters themselves. This has motivated a class of methods that specifically compresses these states, decompressing them to a higher precision just-in-time for the weight update to save memory (Dettmers et al., 2021; Peng et al., 2023; Li et al., 2024; Fishman et al., 2025; Xi et al., 2025). Despite the empirical success of these techniques, a comprehensive theory explaining their convergence behavior remains absent. Our work addresses this gap by establishing an analytical framework that formally incorporates quantization errors from all parts of a realistic low-bit training pipeline, from gradients and weights to the crucial optimizer states themselves.

#### Quantization Convergence.

Most convergence guarantees for optimizers assume ideal, high-precision arithmetic, failing to account for the quantization effects inherent in modern large-scale training. Much of the existing theoretical work in this area has therefore focused on the convergence of Quantized Stochastic Gradient Descent (SGD). Early analyses established convergence rates for SGD with quantized gradients, often relying on the strong assumption of an unbiased quantizer (Alistarh et al., 2017; Jiang and Agrawal, 2018; Wen et al., 2017). To handle more practical, biased quantization schemes, subsequent work introduced error-feedback mechanisms to compensate for the quantization bias and still guarantee convergence (Karimireddy et al., 2019; Zheng et al., 2019; Tang et al., 2019; Koloskova et al., 2020). Beyond SGD, analyzing quantized adaptive optimizers is a more recent challenge. Initial work successfully applied error-feedback to ensure the convergence of Adam with quantized weights and gradients (Chen et al., 2021). More recently, methods tackling the memory bottleneck of error-feedback mechanism, such as MicroAdam (Modoranu et al., 2024) and LDAdam (Robert et al., 2025), use novel error-feedback schemes to retain provable convergence. However, these existing analyses for adaptive methods rely heavily on error-feedback mechanisms, which are often impractical in state-of-the-art LLM training pipelines (Xi et al., 2025; Fishman et al., 2025). Our work addresses this critical gap by providing the first convergence framework for adaptive optimizers under a realistic floating-point error model that covers all components of the training process, without resorting to error-feedback or unbiasedness assumptions.

## 3 Preliminaries and Problem Setup

### 3.1 Preliminaries

We begin by formalizing the quantization operator and its error properties.
Our focus is on floating-point quantization, which is widely adopted in practice.
Compared to integer quantization, floating-point formats achieve strictly smaller reconstruction errors due to their exponent scaling (Kuzmin et al., 2022).
This explains why most large-scale low-precision training frameworks rely on floating-point representations, including recent FP8 and mixed-precision systems (Peng et al., 2023; Liu et al., 2024; Fishman et al., 2025).

#### Floating-point quantization.

Let $\mathcal{Q}:\mathbb{R}\to\mathbb{R}$ be a scalar quantization operator applied elementwise to vectors and matrices.
We illustrate $\mathcal{Q}$ through the common case of quantizing from single precision (fp32) to brain floating-point (bf16).
The fp32 format uses $1$ sign bit, $8$ exponent bits, and $23$ mantissa bits (total $32$ bits) (IEEE, 2019), while bf16 keeps the same sign and exponent layout but truncates the mantissa to $7$ bits (Wang and Kanwar, 2019).
Thus, FP32 can be written as

$$ $x_{\text{fp32}}=(-1)^{S}\times 2^{E-127}\times(1.M_{0:22}),$ $$

where $S$ is the sign bit, $E$ the exponent, and $M_{0:22}$ the mantissa bits.
Quantization discards the low-order $16$ mantissa bits $M_{7:22}$, possibly with rounding or truncation.
The BF16 number becomes

$$ $x_{\text{bf16}}=(-1)^{S}\times 2^{E-127}\times\big(1.M_{0:6}+C\cdot 2^{-7}\big),$ $$

where $C\in\{0,1\}$ is a carry bit from rounding. Dequantization pads the truncated mantissa with zeros to recover an fp32 value.
Figure [1](https://arxiv.org/html/2510.21314v1#S3.F1) visualizes this process.

#### Relative error.

The above construction implies that the quantization error satisfies

$$ $|x_{\text{bf16}}-x_{\text{fp32}}|=\big|C\cdot 2^{-7}-0.M_{7:22}\cdot 2^{-7}\big|\cdot 2^{E-127}\;\leq\;2^{-7}\cdot 2^{E-127}\;\leq\;q|x_{\text{fp32}}|,$ $$

where $q=\Theta(2^{-M})$ and $M$ is the mantissa length of the target format (here $M=7$ for bf16). More generally, we assume the absence of underflow and overflow, so that the sign and exponent remain unchanged after quantization. This prevents large quantization errors and guarantees convergence of the quantization process. In practice, this assumption is well justified: low-precision LLM training commonly employs engineering techniques such as per-tensor or per-channel scaling, which ensure that post-quantization values remain within the representable range (Peng et al., 2023; Fishman et al., 2025).
Under this condition, the relative quantization error decays exponentially with the number of mantissa bits—a property that is intrinsic to floating-point representations.
This observation motivates the following assumption.

###### Assumption 3.1 (Quantization Error) .

Let $\mathcal{Q}:\mathbb{R}\to\mathbb{R}$ be a scalar quantization operator applied elementwise.
Then, for any $x\in\mathbb{R}$, the quantization error is relatively bounded:

$$ $|x^{Q}-x|\leq q|x|,$ $$

where $q=\Theta(2^{-M})$, and $M$ is the mantissa length of the target floating-point format.

Figure: Figure 1: Floating-point quantization from fp32 to bf16. Only the mantissa is truncated, while sign and exponent remain unchanged.
Refer to caption: x1.png

###### Assumption 3.1 (Quantization Error) .

### 3.2 Problem Setup

We study stochastic optimization ([3.1](https://arxiv.org/html/2510.21314v1#S3.E1)) with low-precision training under an analytical quantization framework shown in Figure [2](https://arxiv.org/html/2510.21314v1#S3.F2). Formally, the goal is to minimize the loss:

$$ $\displaystyle\min_{\mathbf{W}\in\mathbb{R}^{m\times n}}F(\mathbf{W})=\mathbb{E}_{\bm{\xi}}[f(\mathbf{W};\bm{\xi})],$ (3.1) $$

where $\mathbf{W}$ denotes the model parameters, $\bm{\xi}$ is a random variable representing the data, and $f(\mathbf{W};\bm{\xi})$ is the sample loss.
We denote $F^{*}=\inf_{\mathbf{W}}F(\mathbf{W})>-\infty$ as the optimal objective value.

#### Low-precision training framework.

During training, both computation and communication are constrained by memory and bandwidth.
Modern practice therefore quantizes weights, gradients, and optimizer states into lower-precision formats (e.g., BF16, FP8) to accelerate training (Peng et al., 2023; Liu et al., 2024; Fishman et al., 2025).
We model this process with the analytical framework shown in Figure [2](https://arxiv.org/html/2510.21314v1#S3.F2).
The key steps are:

- 1.
The master maintains full-precision weights $\mathbf{W}_{t}$ but transmits their quantized version $\mathbf{W}_{t}^{Q}$ to workers.
- 2.
Workers perform forward and backward passes with $\mathbf{W}_{t}^{Q}$, compute gradients $\nabla f(\mathbf{W}_{t}^{Q};\bm{\xi})$, quantize them, and send quantized gradients back.
- 3.
The master dequantizes gradients, updates quantized optimizer states (e.g., momentum, second moment), and applies the optimizer update. Updated states are re-quantized for storage.

The first two steps can be illustrated by Algorithm [1](https://arxiv.org/html/2510.21314v1#alg1), while the third step depends on the choice of optimizer (e.g., Adam in Algorithm [2](https://arxiv.org/html/2510.21314v1#alg2) or Muon in Algorithm [3](https://arxiv.org/html/2510.21314v1#alg3)). The dashed arrows in Figure [2](https://arxiv.org/html/2510.21314v1#S3.F2) highlight the quantization operations applied to weights, gradients, and optimizer states within the proposed framework.

#### Relative errors.

We denote the relative errors $q$ of different components after applying $\mathcal{Q}$ as

$$ $q_{W}\quad\text{(weights)},\qquad q_{G}\quad\text{(gradients)},\qquad q_{M}\quad\text{(first moment)},\qquad q_{V}\quad\text{(second moment)}.$ $$

Each error term arises from applying a floating-point quantization operator $\mathcal{Q}$ that satisfies Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1).
This framework is more general than most prior theoretical analyses, which typically consider quantization of only a subset of components (e.g., gradients).

#### Optimizers.

We focus on two adaptive optimizers: Adam (Kingma, 2014) and Muon (Jordan et al., 2024).
Algorithm [1](https://arxiv.org/html/2510.21314v1#alg1) outlines the general quantized training loop, while Algorithms [2](https://arxiv.org/html/2510.21314v1#alg2) and [3](https://arxiv.org/html/2510.21314v1#alg3) detail the specific update rules for Adam and Muon, respectively.
Note that the quantization operator $\mathcal{Q}$ can represent any floating-point quantization (e.g., fp32 $\to$ bf16 or fp8) satisfying Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1).

In the following sections, we will analyze the convergence of quantized Adam (^1^11Our Algorithm slightly differs from the standard Adam, but will not affect the proof. We provide a detailed discussion in Appendix [A.1](https://arxiv.org/html/2510.21314v1#A1.SS1).) and Muon under this framework with relative quantization errors $(q_{W},q_{G},q_{M},q_{V})$.

Figure: Figure 2: An analytical low-precision training framework
Refer to caption: x2.png

Figure: Algorithm 1 Analytical Adaptive Method Quantization Training Framework

## 4 Main Results

We now present our main theoretical results on the convergence of quantized Adam and Muon under the analytical framework in Section [3](https://arxiv.org/html/2510.21314v1#S3). We begin by stating the assumptions required for our analysis, followed by the convergence theorems for each optimizer.

###### Assumption 4.1 (Unbiased Stochastic Gradient) .

The stochastic gradient $\nabla f(\mathbf{W};\bm{\xi})$ is an unbiased estimator of the true gradient $\nabla F(\mathbf{W})$, i.e., $\mathbb{E}[\nabla f(\mathbf{W};\bm{\xi})]=\nabla F(\mathbf{W})$.

###### Assumption 4.2 (Stochastic Gradient Bounds) .

The stochastic gradient $\nabla f(\mathbf{W};\bm{\xi})$ satisfies the following bounds depending on the algorithm:

- •
Adam: The stochastic gradient is $\ell_{\infty}$ uniformly almost surely bounded, i.e., there exists a constant $R>\sqrt{\epsilon}$ (where $\epsilon>0$ is the stability constant used to simplify the final bounds) such that
$\displaystyle\|\nabla f(\mathbf{W};\bm{\xi})\|_{\infty}=\max_{i,j}|[\nabla f(\mathbf{W};\bm{\xi})]_{ij}|\leq R-\sqrt{\epsilon},\quad\text{a.s.}.$
- •
Muon: The stochastic gradient has bounded variance, i.e., there exists a constant $\sigma>0$ such that
$\displaystyle\mathbb{E}[\|\nabla f(\mathbf{W};\bm{\xi})-\nabla F(\mathbf{W})\|_{F}^{2}]\leq\sigma^{2}.$

###### Assumption 4.3 (Smoothness) .

The objective function $F:\mathbb{R}^{m\times n}\to\mathbb{R}$ is $L$-smooth, i.e., for any $\mathbf{X},\mathbf{Y}\in\mathbb{R}^{m\times n}$, we have

$$ $\displaystyle\|\nabla F(\mathbf{X})-\nabla F(\mathbf{Y})\|_{F}\;\leq\;L\|\mathbf{X}-\mathbf{Y}\|_{F}.$ $$

Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1), [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2) and [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) are standard in the analysis of smooth non-convex stochastic optimization (Zaheer et al., 2018; Chen et al., 2019; Zou et al., 2019; Défossez et al., 2022; Chen et al., 2022; Zhang et al., 2022; Wang et al., 2023). They are usually employed to control the stochastic gradient noise and the local geometry of the objective function.

We remark that a more general $(L_{0},L_{1})$-smoothness condition (Zhang et al., 2020), which has been adopted in recent analyses of Adam (Li et al., 2023; Wang et al., 2024; Hong and Lin, 2024), allows the smoothness constant to depend on the gradient norm: $\|\nabla F(\mathbf{X})-\nabla F(\mathbf{Y})\|_{F}\leq(L_{0}+L_{1}\|\nabla F(\mathbf{Y})\|_{F})\|\mathbf{X}-\mathbf{Y}\|_{F}$. While this condition can better capture practical deep learning scenarios, since our focus is on characterizing how quantization errors influence the convergence behavior of Adam and Muon, we adopt the standard $L$-smoothness assumption for simplicity. Extending our results to $(L_{0},L_{1})$-smoothness remains an interesting direction for future work.

Finally, we assume the optimization begins from a controlled initialization:

###### Assumption 4.4 (Bounded Initialization) .

The initial parameter matrix $\mathbf{W}_{0}$ and its gradient are bounded in Frobenius norm, i.e., $\|\mathbf{W}_{0}\|_{F}\leq D,\ \|\nabla F(\mathbf{W}_{0})\|_{F}\leq G$, for some constants $D,G>0$.

Bounding the initialization ensures that quantization errors remain controlled and their propagation through the optimization iterations can be rigorously analyzed, which is crucial for establishing convergence guarantees under low-precision training.

###### Assumption 4.1 (Unbiased Stochastic Gradient) .

###### Assumption 4.2 (Stochastic Gradient Bounds) .

###### Assumption 4.3 (Smoothness) .

###### Assumption 4.4 (Bounded Initialization) .

### 4.1 Theoretical results of Adam

Figure: Figure 3: Rosenbrock: Adam gradient norms under different mantissa precisions $M$ (left: full $10{,}000$ iterations; right: last $100$ iterations). Larger mantissa bit-lengths yield smaller converged gradient norms. Together with Figure [5](https://arxiv.org/html/2510.21314v1#A3.F5), this shows that higher precision reduces quantization error and improves convergence, consistent with Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5).
Refer to caption: x3.png

We first present the convergence result of Adam under FP quantization in the following theorem.

###### Theorem 4.5 (Convergence of Quantized Adam) .

Suppose Assumptions [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1), [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1)–[4.4](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem4) hold. Let $d=mn$ be the number of trainable parameters, consider the Quantized Adam algorithm defined in [1](https://arxiv.org/html/2510.21314v1#alg1) run for $T$ iterations with $\eta_{t}=(1-\beta_{1})\Omega_{t}\eta$, where $\Omega_{t}=\sqrt{\sum_{j=0}^{t-1}\beta_{2}^{j}}$. Suppose $\beta_{1}^{2}(1+q_{M})^{2}<\beta_{2}(1-q_{V})$, $\beta_{1}(1+q_{M})<\beta_{2}(1-q_{V})$, and $2\beta_{1}/(1-\beta_{1})\leq T$, then for an iteration index $\tau$ chosen randomly from $\{0,\dots,T-1\}$ with $P(\tau=j)\propto(1-\beta_{1}^{T-j})$, we have:

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathbf{W}_{\tau})\|_{F}^{2}\right]\leq 4(1+q_{G})R\frac{F_{0}-F_{*}}{\eta T}+\frac{\tilde{Q}(T)}{T}+\frac{2q_{W}T\eta\cdot(1-\beta_{1})d^{\frac{3}{2}}\eta L(1+q_{G})R^{2}}{\sqrt{\epsilon}(1-\beta_{2})\sqrt{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}$ $\displaystyle+\frac{4(1+q_{G})d}{\sqrt{\epsilon(1-\beta_{2})}}\left(q_{G}R^{3}+Lq_{W}R^{2}D\right)+\frac{C}{T}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right),$ $$

where $C$ is a constant depending on the problem hyperparameters, and $\tilde{Q}(T)$ is a function with respect to $T$, $q_{V}$, $q_{G}$, and $q_{M}$, which approaches zero when $q_{V},q_{M}\rightarrow 0$ (please refer to Equation [A.43](https://arxiv.org/html/2510.21314v1#A1.E43) for their detailed formula).

Moreover, by setting $\eta=\Theta(1/\sqrt{T})$, $1-\beta_{2}=\Theta(1/T)$, $q_{G}=\mathcal{O}(1/T)$, $q_{M}=\mathcal{O}(1/T)$, $q_{V}=\mathcal{O}(1/T^{2})$, and $q_{W}=\mathcal{O}(1/T^{2})$, then

$$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{\tau})\|_{F}]=\tilde{\mathcal{O}}\left(T^{-1/4}\right).$ $$

Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) provides the first convergence guarantee for Adam under a practical floating-point quantization model (Peng et al., 2023; Liu et al., 2024; Fishman et al., 2025), in contrast to prior works that assume unbiased quantization or error-feedback mechanisms (Jiang and Agrawal, 2018; Chen et al., 2021; Modoranu et al., 2024). Our analysis demonstrates that by setting the hyperparameters as $\eta=\Theta(1/\sqrt{T})$ and $1-\beta_{2}=\Theta(1/T)$, and ensuring the relative quantization errors satisfy $q_{G},q_{M}=\mathcal{O}(1/T)$ and $q_{W},q_{V}=\mathcal{O}(1/T^{2})$, Quantized Adam achieves a convergence rate of $\tilde{\mathcal{O}}(T^{-1/4})$, which successfully matches the established one for its full-precision counterpart in smooth non-convex optimization (Guo et al., 2021; Défossez et al., 2022; Wang et al., 2023; Hong and Lin, 2024).

Our theorem further reveals a nuanced sensitivity to different types of quantization error. The required precision for the second moment ($q_{V}$) is stricter than for the first moment ($q_{M}$). This sensitivity arises because accumulated errors in the second-moment estimate $\mathbf{V}_{t}$ are non-linearly amplified by the update step’s inverse square root. This theoretical finding provides a rigorous explanation for the empirical observation that the second moment often require higher precision than the first moment in low-bit training setups (Peng et al., 2023; Fishman et al., 2025). Similarly, the stricter precision requirement for weights ($q_{W}=\mathcal{O}(1/T^{2})$) is necessary to control error accumulation over the entire training trajectory. Our analysis must account for the potential growth of weight magnitudes throughout training, which acts as an amplification factor for the relative quantization error. To guarantee convergence under this worst-case scenario of unbounded weight growth, the proof requires $q_{W}$ to decay rapidly to counteract this amplification. However, this strict condition is a consequence of the proof’s generality. In practice, where weight norms often remain bounded, this error amplification is less severe, and the precision requirement for $q_{W}$ could be relaxed to $\mathcal{O}(1/T)$.

###### Theorem 4.5 (Convergence of Quantized Adam) .

### 4.2 Theoretical results of Muon

Figure: Figure 4: Rosenbrock: Muon gradient norms under different mantissa precisions $M$ (left: full $10{,}000$ iterations; right: last $100$ iterations). Larger mantissa bit-lengths yield smaller converged gradient norms. Together with Figure [6](https://arxiv.org/html/2510.21314v1#A3.F6), this shows that higher precision reduces quantization error and improves convergence, consistent with Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6).
Refer to caption: x4.png

Then, we present the convergence result of quantized Muon in the following theorem.

###### Theorem 4.6 (Convergence of Quantized Muon) .

Suppose Assumptions [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1), [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1)–[4.4](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem4) hold. Consider the Quantized Muon algorithm in [1](https://arxiv.org/html/2510.21314v1#alg1) and [3](https://arxiv.org/html/2510.21314v1#alg3) run for $T$ iterations with $\eta_{t}=\eta,\beta(1+q_{M})<1$, then

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})\|_{F}]$ $\displaystyle\leq\frac{\mathbb{E}[F(\mathbf{W}_{0})-F(\mathbf{W}_{T})]}{\eta T}+\frac{2\beta L\eta r}{1-\beta}+\frac{6\sigma\sqrt{r}}{T(1-\beta)\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{6\sigma\sqrt{r}}{\sqrt{B}}+$ $\displaystyle\frac{L\eta r}{2}+C_{2}\cdot\bigg(q_{G}+q_{W}+q_{G}T\eta+q_{W}T\eta+\frac{q_{M}\beta}{1-\beta(1+q_{M})}(1+T\eta)\bigg),$ $$

where $C_{2}$ is absolute constant, $r=\min\{m,n\}$.
Moreover, suppose $F(\mathbf{W}_{0})-F^{*}\leq\Delta$ for constant $\Delta>0$, set $1-\beta=\Theta(T^{-1/2})$, $\eta=\Theta(T^{-3/4})$, and $B=1$, if $q_{G}=q_{W}=q_{M}=\mathcal{O}(T^{-1/2})$, then

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})\|_{F}]=\mathcal{O}(T^{-1/4}).$ $$

Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6) establishes the convergence of Quantized Muon under relative quantization errors $(q_{W},q_{G},q_{M})$ for weights, gradients, and momentum, respectively—a practical setting for low-precision training (Peng et al., 2023; Liu et al., 2024; Fishman et al., 2025), in contrast to prior works that assume unbiased quantization or error-feedback mechanisms (Jiang and Agrawal, 2018; Chen et al., 2021; Modoranu et al., 2024). As a sanity check, when $q_{W}=q_{G}=q_{M}=0$, our result recovers the exact convergence rate $\mathcal{O}(1/T^{1/4})$ of Shen et al. (2025) up to constant factors. More importantly, as long as the mantissa length of the floating-point format scales logarithmically with $T$, i.e., $M=\Omega(\log T)$, the quantization errors decay as $q_{W}=q_{G}=q_{M}=\mathcal{O}(T^{-1/2})$. With appropriate choices of $\eta$ and $\beta$ (as in Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6)), the full-precision convergence rate $\mathcal{O}(T^{-1/4})$ is preserved.

Finally, we highlight a sharp contrast with quantized Adam. Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6) requires only relative errors on the order of $q=\mathcal{O}(T^{-1/2})$, whereas Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) demands stricter conditions, at least $q=\mathcal{O}(T^{-1})$ and in some cases $q=\mathcal{O}(T^{-2})$. This theoretical distinction explains why Muon adapts more efficiently to low-precision settings than Adam, corroborating the empirical observations of Liu et al. (2025).

###### Theorem 4.6 (Convergence of Quantized Muon) .

#### Experiments.

We evaluate our theory on both synthetic and real-data tasks.

Synthetic setup.
For the synthetic benchmark, we adopt the classical Rosenbrock function (Rosenbrock, 1960). Let $\mathbf{W}\in\mathbb{R}^{m\times n}$, and define $F(\mathbf{W})=\sum_{j=1}^{n-1}\Big(100\|\mathbf{W}_{j+1}-\mathbf{W}_{j}^{2}\|_{F}^{2}+\|\mathbf{1}_{m}-\mathbf{W}_{j}\|_{F}^{2}\Big)$, where $\mathbf{W}_{j}$ denotes the $j$-th column of $\mathbf{W}$ and $\mathbf{1}_{m}$ is the $m$-dimensional all-ones vector.
We set $m=50$, $n=100$, and run $T=10{,}000$ iterations with learning rate $\eta=5\times 10^{-4}$. Mantissa bit-lengths are selected from $M={4,8,16,24,32,52}$ to quantize gradients, weights, and optimizer states. For Adam, we use $\beta_{1}=0.9$, $\beta_{2}=0.999$, and $\epsilon=10^{-8}$; for Muon, we set $\beta=0.9$ and employ $n_{s}=10$ power iterations, following Jordan et al. (2024).

Real-data setup.
For real-data experiments, we train a 4-layer fully connected network $[\mathrm{FC}(512)-\mathrm{ReLU}-\mathrm{FC}(256)-\mathrm{ReLU}-\mathrm{FC}(64)-\mathrm{ReLU}-\mathrm{FC}(10)]$ on CIFAR-10 using Adam and Muon. Additional implementation details are provided in Appendix [C](https://arxiv.org/html/2510.21314v1#A3).

Empirical validation of theory.
Figures [3](https://arxiv.org/html/2510.21314v1#S4.F3), [7](https://arxiv.org/html/2510.21314v1#A3.F7) and [4](https://arxiv.org/html/2510.21314v1#S4.F4), [8](https://arxiv.org/html/2510.21314v1#A3.F8) (some of them are deferred to Appendix [C](https://arxiv.org/html/2510.21314v1#A3) due to the page limit) show the convergence behavior of Adam and Muon. With very low mantissa lengths, quantization errors dominate the dynamics (see Figures [5](https://arxiv.org/html/2510.21314v1#A3.F5), [9](https://arxiv.org/html/2510.21314v1#A3.F9), [6](https://arxiv.org/html/2510.21314v1#A3.F6), [10](https://arxiv.org/html/2510.21314v1#A3.F10)), leading to slow convergence and traps optimization at sharp stationary points with large gradient norms. In contrast, moderate mantissa lengths yield sufficiently small errors, resulting in convergence nearly identical to the full-precision baseline. These observations validate Theorems [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) and [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6), confirming that mantissa lengths growing only logarithmically with $T$ are sufficient to maintain full-precision convergence rates, and rigorously explain the empirical success of low-precision training with Adam and Muon (Liu et al., 2024, 2025).

## 5 Conclusion and Limitations

We introduced the first theoretical framework for analyzing adaptive optimizers under realistic floating-point quantization, jointly modeling the quantization of gradients, parameters, and optimizer states. Unlike prior work, our analysis does not rely on unbiased quantization or error feedback—assumptions that are impractical in modern large-scale low-precision training. Within this framework, we derived the first convergence guarantees for Adam and Muon, with rates expressed explicitly in terms of component-wise quantization errors. Our results highlight that Adam is highly sensitive to parameter and second-moment quantization due to its reliance on $\beta_{2}\to 1$, whereas Muon requires weaker error control and is therefore more robust. These findings explain empirical observations in large-scale LLM training and narrow the gap between practice and theory.

#### Limitations and Future Directions.

Several challenges remain. Our analysis assumes smoothness and bounded variance, while practical objectives may satisfy only weaker conditions; extending the framework to $(L_{0},L_{1})$-smoothness is a natural direction. We also model quantized states under exact arithmetic, leaving open the integration of low-precision operations such as FP8 matrix multiplications. Finally, we do not consider communication efficiency, a key motivation for low-precision methods in distributed training. Incorporating these aspects would provide a more complete theoretical account of large-scale low-precision optimization.

## References

- Alistarh et al. (2017)
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic.
Qsgd: Communication-efficient sgd via gradient quantization and encoding.
*Advances in neural information processing systems*, 30, 2017.
URL [https://proceedings.neurips.cc/paper_files/paper/2017/file/6c340f25839e6acdc73414517203f5f0-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2017/file/6c340f25839e6acdc73414517203f5f0-Paper.pdf).
- Cattaneo et al. (2024)
Matias D Cattaneo, Jason Matthew Klusowski, and Boris Shigida.
On the implicit bias of adam.
In *International Conference on Machine Learning*, pages 5862–5906. PMLR, 2024.
- Chen et al. (2021)
Congliang Chen, Li Shen, Haozhi Huang, and Wei Liu.
Quantized adam with error feedback.
*ACM Transactions on Intelligent Systems and Technology (TIST)*, 12(5):1–26, 2021.
- Chen et al. (2022)
Congliang Chen, Li Shen, Fangyu Zou, and Wei Liu.
Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration.
*Journal of Machine Learning Research*, 23(229):1–47, 2022.
- Chen et al. (2018)
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong.
On the convergence of a class of Adam-type algorithms for non-convex optimization.
*arXiv preprint arXiv:1808.02941*, 2018.
- Chen et al. (2019)
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong.
On the convergence of a class of adam-type algorithms for non-convex optimization.
In *International Conference on Learning Representations*, 2019.
URL [https://openreview.net/forum?id=H1x-x309tm](https://openreview.net/forum?id=H1x-x309tm).
- De et al. (2018)
Soham De, Anirbit Mukherjee, and Enayat Ullah.
Convergence guarantees for RMSProp and Adam in non-convex optimization and an empirical comparison to Nesterov acceleration.
*arXiv preprint arXiv:1807.06766*, 2018.
- Défossez et al. (2022)
Alexandre Défossez, Leon Bottou, Francis Bach, and Nicolas Usunier.
A simple convergence proof of adam and adagrad.
*Transactions on Machine Learning Research*, 2022.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=ZPQhzTSWA7](https://openreview.net/forum?id=ZPQhzTSWA7).
- Dettmers et al. (2021)
Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer.
8-bit optimizers via block-wise quantization.
*arXiv preprint arXiv:2110.02861*, 2021.
- Duchi et al. (2011)
John Duchi, Elad Hazan, and Yoram Singer.
Adaptive subgradient methods for online learning and stochastic pptimization.
*Journal of Machine Learning Research*, 12(7), 2011.
- Faw et al. (2022)
Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward.
The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance.
In Po-Ling Loh and Maxim Raginsky, editors, *Proceedings of Thirty Fifth Conference on Learning Theory*, Proceedings of Machine Learning Research. PMLR, 2022.
- Fishman et al. (2025)
Maxim Fishman, Brian Chmiel, Ron Banner, and Daniel Soudry.
Scaling FP8 training to trillion-token LLMs.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=E1EHO0imOb](https://openreview.net/forum?id=E1EHO0imOb).
- Guo et al. (2021)
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang.
A novel convergence analysis for algorithms of the Adam family and beyond.
*arXiv preprint arXiv:2104.14840*, 2021.
- Hinton et al. (2012)
G Hinton, N Srivastava, and K Swersky.
Lecture 6d-a separate, adaptive learning rate for each connection.
*Slides of Lecture Neural Networks for Machine Learning*, 1:1–31, 2012.
- Hong and Lin (2023)
Yusu Hong and Junhong Lin.
High probability convergence of Adam under unbounded gradients and affine variance noise.
*arXiv preprint arXiv:2311.02000*, 2023.
- Hong and Lin (2024)
Yusu Hong and Junhong Lin.
On convergence of adam for stochastic optimization under relaxed assumptions.
*Advances in Neural Information Processing Systems*, 37:10827–10877, 2024.
- IEEE (2019)
IEEE.
Ieee standard for floating-point arithmetic.
*IEEE Std 754-2019 (Revision of IEEE 754-2008)*, pages 1–84, 2019.
doi: 10.1109/IEEESTD.2019.8766229.
- Jiang and Agrawal (2018)
Peng Jiang and Gagan Agrawal.
A linear speedup analysis of distributed deep learning with sparse and quantized communication.
In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 31. Curran Associates, Inc., 2018.
URL [https://proceedings.neurips.cc/paper_files/paper/2018/file/17326d10d511828f6b34fa6d751739e2-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2018/file/17326d10d511828f6b34fa6d751739e2-Paper.pdf).
- Jordan et al. (2024)
Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein.
Muon: An optimizer for hidden layers in neural networks, 2024.
URL [https://kellerjordan.github.io/posts/muon/](https://kellerjordan.github.io/posts/muon/).
- Kalamkar et al. (2019)
Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha, Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, et al.
A study of bfloat16 for deep learning training.
*arXiv preprint arXiv:1905.12322*, 2019.
- Karimireddy et al. (2019)
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi.
Error feedback fixes signsgd and other gradient compression schemes.
In *International conference on machine learning*, pages 3252–3261. PMLR, 2019.
- Kingma (2014)
Diederik P Kingma.
Adam: A method for stochastic optimization.
*arXiv preprint arXiv:1412.6980*, 2014.
- Koloskova et al. (2020)
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi.
Decentralized deep learning with arbitrary communication compression.
In *International Conference on Learning Representations*, 2020.
URL [https://openreview.net/forum?id=SkgGCkrKvH](https://openreview.net/forum?id=SkgGCkrKvH).
- Krizhevsky et al. (2009)
Alex Krizhevsky, Geoffrey Hinton, et al.
Learning multiple layers of features from tiny images.
2009.
- Kuzmin et al. (2022)
Andrey Kuzmin, Mart Van Baalen, Yuwei Ren, Markus Nagel, Jorn Peters, and Tijmen Blankevoort.
Fp8 quantization: The power of the exponent.
*Advances in Neural Information Processing Systems*, 35:14651–14662, 2022.
- Li et al. (2024)
Bingrui Li, Jianfei Chen, and Jun Zhu.
Memory efficient optimizers with 4-bit states.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Li et al. (2023)
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie.
Convergence of adam under relaxed assumptions.
*Advances in Neural Information Processing Systems*, 36:52166–52196, 2023.
- Li et al. (2025)
Huan Li, Yiming Dong, and Zhouchen Lin.
On the $O(\sqrt{d}/T^{1/4})$ convergence rate of RMSProp and its momentum extension measured by $l_{1}$ norm.
*Journal of Machine Learning Research*, 26(131):1–25, 2025.
URL [http://jmlr.org/papers/v26/24-0523.html](http://jmlr.org/papers/v26/24-0523.html).
- Li and Orabona (2019)
Xiaoyu Li and Francesco Orabona.
On the convergence of stochastic gradient descent with adaptive stepsizes.
In *AI Stats*, 2019.
- Liu et al. (2024)
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al.
Deepseek-v3 technical report.
*arXiv preprint arXiv:2412.19437*, 2024.
- Liu et al. (2025)
Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al.
Muon is scalable for llm training.
*arXiv preprint arXiv:2502.16982*, 2025.
- Liu et al. (2023)
Shih-yang Liu, Zechun Liu, Xijie Huang, Pingcheng Dong, and Kwang-Ting Cheng.
Llm-fp4: 4-bit floating-point quantized transformers.
*arXiv preprint arXiv:2310.16836*, 2023.
- Loshchilov and Hutter (2019)
Ilya Loshchilov and Frank Hutter.
Decoupled weight decay regularization.
In *International Conference on Learning Representations*, 2019.
URL [https://openreview.net/forum?id=Bkg6RiCqY7](https://openreview.net/forum?id=Bkg6RiCqY7).
- Micikevicius et al. (2017)
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al.
Mixed precision training.
*arXiv preprint arXiv:1710.03740*, 2017.
- Micikevicius et al. (2022)
Paulius Micikevicius, Dusan Stosic, Neil Burgess, Marius Cornea, Pradeep Dubey, Richard Grisenthwaite, Sangwon Ha, Alexander Heinecke, Patrick Judd, John Kamalu, et al.
Fp8 formats for deep learning.
*arXiv preprint arXiv:2209.05433*, 2022.
- Modoranu et al. (2024)
Ionut-Vlad Modoranu, Mher Safaryan, Grigory Malinovsky, Eldar Kurtić, Thomas Robert, Peter Richtárik, and Dan Alistarh.
Microadam: Accurate adaptive optimization with low space overhead and provable convergence.
*Advances in Neural Information Processing Systems*, 37:1–43, 2024.
- NVIDIA (2022)
NVIDIA.
Nvidia h100 tensor core gpu architecture, 2022.
URL [https://resources.nvidia.com/en-us-tensor-core](https://resources.nvidia.com/en-us-tensor-core).
- Peng et al. (2023)
Houwen Peng, Kan Wu, Yixuan Wei, Guoshuai Zhao, Yuxiang Yang, Ze Liu, Yifan Xiong, Ziyue Yang, Bolin Ni, Jingcheng Hu, et al.
Fp8-lm: Training fp8 large language models.
*arXiv preprint arXiv:2310.18313*, 2023.
- Reddi et al. (2018)
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar.
On the convergence of Adam and beyond.
In *Proc. of the International Conference on Learning Representations (ICLR)*, 2018.
- Robert et al. (2025)
Thomas Robert, Mher Safaryan, Ionut-Vlad Modoranu, and Dan Alistarh.
Ldadam: Adaptive optimization from low-dimensional gradient statistics.
*arXiv preprint arXiv:2410.16103*, 2025.
- Rosenbrock (1960)
HoHo Rosenbrock.
An automatic method for finding the greatest or least value of a function.
*The computer journal*, 3(3):175–184, 1960.
- Sato et al. (2025)
Naoki Sato, Hiroki Naganuma, and Hideaki Iiduka.
Convergence bound and critical batch size of muon optimizer, 2025.
URL [https://arxiv.org/abs/2507.01598](https://arxiv.org/abs/2507.01598).
- Shen et al. (2025)
Wei Shen, Ruichuan Huang, Minhui Huang, Cong Shen, and Jiawei Zhang.
On the convergence analysis of muon.
*arXiv preprint arXiv:2505.23737*, 2025.
- Shi et al. (2020)
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun.
RMSProp converges with proper hyper-parameter.
In *International Conference on Learning Representations*, 2020.
- Tang et al. (2019)
Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu.
Deepsqueeze: Decentralization meets error-compensated compression.
*arXiv preprint arXiv:1907.07346*, 2019.
- Tang et al. (2025)
Xuan Tang, Han Zhang, Yuan Cao, and Difan Zou.
Understanding the generalization of stochastic gradient adam in learning neural networks.
*arXiv preprint arXiv:2510.11354*, 2025.
URL [https://arxiv.org/abs/2510.11354](https://arxiv.org/abs/2510.11354).
- Wang et al. (2022)
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie-Yan Liu, and Wei Chen.
Provable adaptivity in Adam.
*arXiv preprint arXiv:2208.09900*, 2022.
- Wang et al. (2023)
Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen.
Closing the gap between the upper bound and lower bound of adam’s iteration complexity.
In *Thirty-seventh Conference on Neural Information Processing Systems*, 2023.
URL [https://openreview.net/forum?id=yDvb3mlogA](https://openreview.net/forum?id=yDvb3mlogA).
- Wang et al. (2024)
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, Tie-Yan Liu, Zhi-Quan Luo, and Wei Chen.
Provable adaptivity of adam under non-uniform smoothness.
In *Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining*, pages 2960–2969, 2024.
- Wang et al. (2018)
Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakrishnan.
Training deep neural networks with 8-bit floating point numbers.
*Advances in neural information processing systems*, 31, 2018.
- Wang et al. (2025)
Ruizhe Wang, Yeyun Gong, Xiao Liu, Guoshuai Zhao, Ziyue Yang, Baining Guo, Zhengjun Zha, and Peng Cheng.
Optimizing large language model training using fp4 quantization.
In *Forty-second International Conference on Machine Learning*, 2025.
- Wang and Kanwar (2019)
Shibo Wang and Pankaj Kanwar.
Bfloat16: The secret to high performance on cloud tpus.
*Google Cloud Blog*, 2019.
URL [https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus](https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus).
Accessed: 2025-09-21.
- Wen et al. (2017)
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.
Terngrad: Ternary gradients to reduce communication in distributed deep learning.
*Advances in neural information processing systems*, 30, 2017.
- Wortsman et al. (2023)
Mitchell Wortsman, Tim Dettmers, Luke Zettlemoyer, Ari Morcos, Ali Farhadi, and Ludwig Schmidt.
Stable and low-precision training for large-scale vision-language models.
*Advances in Neural Information Processing Systems*, 36:10271–10298, 2023.
- Xi et al. (2024)
Haocheng Xi, Yuxiang Chen, Kang Zhao, Kaijun Zheng, Jianfei Chen, and Jun Zhu.
Jetfire: Efficient and accurate transformer pretraining with int8 data flow and per-block quantization.
*arXiv preprint arXiv:2403.12422*, 2024.
- Xi et al. (2025)
Haocheng Xi, Han Cai, Ligeng Zhu, Yao Lu, Kurt Keutzer, Jianfei Chen, and Song Han.
COAT: Compressing optimizer states and activations for memory-efficient FP8 training.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=XfKSDgqIRj](https://openreview.net/forum?id=XfKSDgqIRj).
- Zaheer et al. (2018)
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar.
Adaptive methods for nonconvex optimization.
*Advances in Neural Information Processing Systems*, 31, 2018.
- Zhang et al. (2024)
Chenyang Zhang, Difan Zou, and Yuan Cao.
The implicit bias of adam on separable data.
*Advances in Neural Information Processing Systems*, 37:23988–24021, 2024.
- Zhang et al. (2020)
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie.
Why gradient clipping accelerates training: A theoretical justification for adaptivity.
In *International Conference on Learning Representations*, 2020.
URL [https://openreview.net/forum?id=BJgnXpVYwS](https://openreview.net/forum?id=BJgnXpVYwS).
- Zhang et al. (2025)
Qi Zhang, Yi Zhou, and Shaofeng Zou.
Convergence guarantees for rmsprop and adam in generalized-smooth non-convex optimization with affine noise variance, 2025.
URL [https://arxiv.org/abs/2404.01436](https://arxiv.org/abs/2404.01436).
- Zhang et al. (2022)
Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo.
Adam can converge without any modification on update rules.
*Advances in Neural Information Processing Systems*, 35:28386–28399, 2022.
- Zheng et al. (2019)
Shuai Zheng, Ziyue Huang, and James Kwok.
Communication-efficient distributed blockwise momentum sgd with error-feedback.
*Advances in Neural Information Processing Systems*, 32, 2019.
- Zhou et al. (2025)
Jiecheng Zhou, Ding Tang, Rong Fu, Boni Hu, Haoran Xu, Yi Wang, Zhilin Pei, Zhongling Su, Liang Liu, Xingcheng Zhang, and Weiming Zhang.
Towards efficient pre-training: Exploring fp4 precision in large language models.
*arXiv preprint arXiv:2502.11458*, 2025.
- Zou et al. (2023)
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu.
Understanding the generalization of adam in learning neural networks with proper regularization.
In *The Eleventh International Conference on Learning Representations*, 2023.
URL [https://openreview.net/forum?id=iUYpN14qjTF](https://openreview.net/forum?id=iUYpN14qjTF).
- Zou et al. (2019)
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu.
A sufficient condition for convergences of Adam and RMSProp.
In *Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition*, pages 11127–11135, 2019.

## Appendix: Proof Dependency Graph

The following proof dependency graph visually encapsulates the logical structure and organization of the theoretical results in the paper, detailed in Appendix [A](https://arxiv.org/html/2510.21314v1#A1) (Proof of Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5)) and Appendix [B](https://arxiv.org/html/2510.21314v1#A2) (Proof of Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6)).

The graph is organized into two main, independent clusters:

Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) (Quantized Adam): This cluster, shown on the left, illustrates the proof for Quantized Adam. The main theorem (Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5)) is supported by a series of lemmas from Appendix [A](https://arxiv.org/html/2510.21314v1#A1). These lemmas provide the bounds for the core proof structure, including the main descent and gradient drift terms (Lemmas [A.9](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem9), [A.8](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem8)), the analysis of quantization error arising from a one-step decomposition of the algorithm(Lemmas [A.2](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem2), [A.3](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem3), [A.5](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem5)), the cumulative bounds on update norms and bias (Lemmas [A.13](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem13), [A.14](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem14)), and the key mathematical tools used to bound the specific types of sums and geometric series arising from the analysis (Lemmas [A.4](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem4), [A.10](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem10), [A.11](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem11), [A.12](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem12)).

Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6) (Quantized Muon): This cluster, shown on the right, illustrates the proof for Quantized Muon. This theorem relies on a separate set of lemmas from Appendix [B](https://arxiv.org/html/2510.21314v1#A2). These lemmas bound the various error components specific to Muon’s update rule, including the bound of the weight norm and the gradient norm (Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1)), relative quantization error (Lemma [B.2](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem2)), the momentum bias (Lemma [B.3](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem3)), stochastic variance (Lemma [B.4](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem4)), and errors introduced by quantizing stochastic gradients, weights and the momentum state (Lemmas [B.5](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem5), [B.6](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem6), [B.7](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem7)).

The arrows in the graph indicate dependency. An arrow from a lemma to a theorem (or another lemma) signifies that the proof of the latter relies on the result of the former.

Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5)Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6)Lemma [A.9](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem9)Lemma [A.13](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem13)Lemma [A.14](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem14)Lemma [A.2](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem2)Lemma [A.3](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem3)Lemma [A.12](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem12)Lemma [A.5](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem5)Lemma [A.8](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem8)Lemma [A.11](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem11)Lemma [A.10](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem10)Lemma [A.7](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem7)Lemma [A.6](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem6)Lemma [A.4](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem4)Lemma [B.7](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem7)Lemma [B.6](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem6)Lemma [B.5](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem5)Lemma [B.3](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem3)Lemma [B.4](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem4)Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1)Lemma [B.2](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem2)

## Appendix A Proof of Theorem 4.5

### A.1 Preliminaries

We consider an optimization problem in a $d$-dimensional space (let $d=mn$ be the number of trainable parameters), where coordinates are indexed by $i\in[d]=\{1,2,\ldots,d\}$. Our algorithm generates a sequence of vectors $(\mathbf{u}_{t})_{t\in\mathbb{N}}$, with the $i$-th component of $\mathbf{u}_{t}$ denoted by $u_{t,i}$. The objective is to find a critical point of a global function $F:\mathbb{R}^{d}\rightarrow\mathbb{R}$ within a stochastic framework, where we have access to a sequence of i.i.d. sample functions $(f_{t})_{t\in\mathbb{N}^{*}}$ (e.g., the loss on a data minibatch). For any differentiable function $h:\mathbb{R}^{d}\rightarrow\mathbb{R}$, we denote its gradient by $\nabla h$ and its $i$-th component by $\nabla_{i}h$. Finally, we use a small constant $\epsilon>0$ for numerical stability and let $\mathbb{E}_{t}[\cdot]$ denote the conditional expectation given the history of samples $f_{1},\ldots,f_{t-1}$. We use $\mathrm{vec}(\cdot)$ to vectorize a matrix and $\mathrm{mat}(\cdot)$ for the inverse operation.

Recall the dynamic system of our theoretical Quantized Adam. In the proof, we denote $\mathbf{w}_{t}=\mathrm{vec}(\mathbf{W}_{t})$, $\hat{\mathbf{g}_{t}}=\mathrm{vec}(\mathbf{G}_{t})$ and the dimension $d=m\cdot n$. For an iteration $t\in\mathbb{N}^{*}$, we define:

$$ $\displaystyle\begin{cases}m_{t,i}&=\beta_{1}m_{t-1,i}^{Q}+\hat{g}_{t,i}=\beta_{1}(m_{t-1,i}+\xi_{t-1,i})+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i}),\\ v_{t,i}&=\beta_{2}v_{t-1,i}^{Q}+\hat{g}_{t,i}^{2}=\beta_{2}(v_{t-1,i}+\theta_{t-1,i})+\left(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i}\right)^{2},\\ w_{t,i}&=w_{t-1,i}-\eta_{t}\frac{m_{t,i}}{\sqrt{\epsilon+v_{t,i}}}.\end{cases}$ (A.1) $$

with the step size given by

$$ $\displaystyle\eta_{t}=\eta(1-\beta_{1})\sqrt{\frac{1-\beta_{2}^{t}}{1-\beta_{2}}}.$ (A.2) $$

Here, $\delta_{t,i}$, $\xi_{t-1,i}$, and $\theta_{t-1,i}$ represent the quantization errors for the gradient, first moment, and second moment, respectively. Especially,

$$ $\displaystyle\nabla_{i}f_{t}(\mathbf{w}_{t-1})$ $\displaystyle=\frac{1}{B}\sum_{j=1}^{B}\nabla_{i}f(\mathbf{w}_{t-1};\gamma_{t,j}),$ $\displaystyle\delta_{t,i}$ $\displaystyle=\frac{1}{B}\sum_{j=1}^{B}\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})-\frac{1}{B}\sum_{j=1}^{B}\nabla_{i}f_{t}(\mathbf{w}_{t-1};\gamma_{t,j}).$ $$

We have $\mathbb{E}\left[\nabla_{i}f_{t}(\mathbf{w}_{t-1})\right]=\nabla_{i}F(\mathbf{w}_{t-1})$

Our convergence analysis for Quantized Adam is predicated on a specific, analytically convenient formulation of the algorithm. This section serves to rigorously justify our theoretical framework by establishing two foundational equivalences. First, we demonstrate that our representation of the Adam update is equivalent to the standard formulation. Following the methodology of Défossez et al. [2022], we absorb the scaling factor into the learning rate, which simplifies the recursive structure of the momentum term. Second, and more critically for our work, we prove that the theoretical analysis of quantizing these weighted-sum states is directly applicable to the practical scenario of quantizing the standard weighted-average states.

#### Equivalence with Standard Adam

Our formulation in ([A.1](https://arxiv.org/html/2510.21314v1#A1.E1)) utilizes a weighted sum for the moments, which differs slightly from the standard weighted-average approach in the original Adam algorithm [Kingma, 2014]. The standard first moment, often expressed as $\tilde{m}_{t,i}=(1-\beta_{1})\sum_{k=1}^{t}\beta_{1}^{t-k}\hat{g}_{k,i}$, is simply a scaled version of our definition, i.e., $\tilde{m}_{t,i}=(1-\beta_{1})m_{t,i}$. This constant scaling factor can be directly absorbed into the learning rate.

Furthermore, the standard Adam algorithm includes bias correction terms to counteract the zero-initialization of moments. These corrections are equivalent to using a time-dependent step size of the form:

$$ $\eta_{t,\text{Adam}}=\eta\cdot\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}}\cdot\frac{\sqrt{1-\beta_{2}^{t}}}{1-\beta_{1}^{t}}.$ (A.3) $$

For analytical tractability, our analysis adopts the simplified step size $\eta_{t}$ from ([A.2](https://arxiv.org/html/2510.21314v1#A1.E2)), which omits the bias correction for the first moment ($m_{t,i}$). This simplification is motivated by several practical and theoretical considerations. First, it ensures that our step size $\eta_{t}$ is monotonic with respect to $t$, which is advantageous for the convergence proof. Second, for typical hyperparameter values (e.g., $\beta_{1}=0.9$, $\beta_{2}=0.999$), the omitted term $1/(1-\beta_{1}^{t})$ converges to its limit of 1 much more rapidly than the retained term $\sqrt{1-\beta_{2}^{t}}$. Finally, removing this term effectively implements a learning rate warm-up, a common and beneficial practice, while retaining the correction for $v_{t,i}$ prevents an undesirably large initial step size that could lead to training instability.

#### Equivalence of Quantization Schemes.

A subtle but crucial aspect of our setup is the object of quantization. Our theoretical framework analyzes the quantization of weighted-sum moments ($\mathbf{m}_{t},\mathbf{v}_{t}$), while a practical implementation would quantize the standard weighted-average moments ($\tilde{\mathbf{m}}_{t},\tilde{\mathbf{v}}_{t}$). We now prove that these two approaches are, in fact, analytically equivalent.

To establish this rigorously, we first abstract the core dynamic behavior into a general mathematical lemma. We will show that two discrete-time systems, representing the weighted-sum and weighted-average accumulation methods under relative error perturbations, are analytically indistinguishable. We will then apply this result to the specific case of Quantized Adam.

###### Lemma A.1 (Equivalence of Perturbed Dynamical Systems) .

Consider two scalar sequences $\{a_{k}\}_{k\geq 0}$ and $\{c_{k}\}_{k\geq 0}$ evolving according to the following dynamics for $k\geq 1$, with initial conditions $a_{0}=c_{0}=0$:

$$ $\displaystyle a_{k}$ $\displaystyle=\beta(a_{k-1}+d_{k-1})+b_{k}$ (A.4) $\displaystyle c_{k}$ $\displaystyle=\beta(c_{k-1}+e_{k-1})+(1-\beta)b_{k}$ (A.5) $$

where $\beta\in(0,1)$ is a decay factor, $\{b_{k}\}$ is an external input sequence, and $\{d_{k}\},\{e_{k}\}$ are perturbation sequences. These perturbations are bounded by a relative error model with factor $q\in[0,1)$:

$$ $\displaystyle|d_{k-1}|\leq q|a_{k-1}|\quad\text{and}\quad|e_{k-1}|\leq q|c_{k-1}|.$ (A.6) $$

Then, the sequence $\{c_{k}\}$ and the scaled sequence $\{a^{\prime}_{k}\}\triangleq(1-\beta)a_{k}$ are analytically equivalent. Specifically, they follow identical recurrence relations where their respective perturbation terms satisfy identical relative error bounds with respect to their own states.

###### Proof.

To prove the equivalence, we derive the recurrence relation for the scaled sequence $\{a^{\prime}_{k}\}$ and compare its structure and error properties to that of $\{c_{k}\}$.

Step 1: Derive the recurrence for $\{a^{\prime}_{k}\}$.
Starting from the definition $a^{\prime}_{k}=(1-\beta)a_{k}$ and substituting the dynamics from ([A.4](https://arxiv.org/html/2510.21314v1#A1.E4)):

$$ $\displaystyle a^{\prime}_{k}$ $\displaystyle=(1-\beta)\left[\beta(a_{k-1}+d_{k-1})+b_{k}\right]$ $\displaystyle=\beta(1-\beta)a_{k-1}+\beta(1-\beta)d_{k-1}+(1-\beta)b_{k}.$ $$

Now, we replace $a_{k-1}$ with $a^{\prime}_{k-1}/(1-\beta)$:

$$ $\displaystyle a^{\prime}_{k}$ $\displaystyle=\beta(1-\beta)\left(\frac{a^{\prime}_{k-1}}{1-\beta}\right)+\beta(1-\beta)d_{k-1}+(1-\beta)b_{k}$ $\displaystyle=\beta a^{\prime}_{k-1}+\beta(1-\beta)d_{k-1}+(1-\beta)b_{k}.$ $$

Step 2: Compare recurrence structures.
Let us place the recurrence relations for $\{c_{k}\}$ and $\{a^{\prime}_{k}\}$ side-by-side:

$$ $\displaystyle c_{k}$ $\displaystyle=\beta c_{k-1}+\beta e_{k-1}+(1-\beta)b_{k}$ $\displaystyle a^{\prime}_{k}$ $\displaystyle=\beta a^{\prime}_{k-1}+\beta(1-\beta)d_{k-1}+(1-\beta)b_{k}.$ $$

Both sequences share the identical structure: $X_{k}=\beta X_{k-1}+\text{Perturbation}_{k}+(1-\beta)b_{k}$. The only difference lies in the form of their respective perturbation terms.

Step 3: Compare relative bounds of the perturbation terms.
The equivalence hinges on whether these different perturbation terms satisfy the same relative error property with respect to their own system’s state.

For system $\{c_{k}\}$, the perturbation term is $\beta e_{k-1}$. Using the bound from ([A.6](https://arxiv.org/html/2510.21314v1#A1.E6)):

$$ $|\text{Perturbation}_{c}|=|\beta e_{k-1}|=\beta|e_{k-1}|\leq\beta q|c_{k-1}|.$ $$

For system $\{a^{\prime}_{k}\}$, the effective perturbation term is $\beta(1-\beta)d_{k-1}$. Using the bound from ([A.6](https://arxiv.org/html/2510.21314v1#A1.E6)) and the scaling relationship $a_{k-1}=a^{\prime}_{k-1}/(1-\beta)$:

$$ $|\text{Perturbation}_{a}|=|\beta(1-\beta)d_{k-1}|=\beta(1-\beta)|d_{k-1}|\leq\beta(1-\beta)q|a_{k-1}|=\beta(1-\beta)q\frac{|a^{\prime}_{k-1}|}{1-\beta}=\beta q|a^{\prime}_{k-1}|.$ $$

Conclusion of Proof.
Both systems, $\{c_{k}\}$ and the scaled $\{a^{\prime}_{k}\}$, adhere to the same mathematical dynamics. Their evolution is governed by an identical recurrence structure, and their respective perturbation terms are bounded by the exact same relative factor $\beta q$ with respect to their own previous state. Therefore, from an analytical standpoint, the two systems are indistinguishable. Any conclusion regarding the long-term behavior (e.g., convergence, stability) of $\{c_{k}\}$ under its perturbation model will apply directly to $\{a^{\prime}_{k}\}$ (and thus proportionally to $\{a_{k}\}$) under its own perturbation model.
∎

With Lemma [A.1](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem1) established, we can now apply this general result to our specific case of Quantized Adam. The weighted-sum moment $\mathbf{m}_{t}$ from our analysis corresponds to the abstract sequence $\{a_{k}\}$, while the standard weighted-average moment $\tilde{\mathbf{m}}_{t}$ corresponds to $\{c_{k}\}$. The gradient term $\mathbf{g}_{t}$ corresponds to $\{b_{k}\}$, and the relative quantization errors in both schemes are modeled by the perturbations $\{d_{k}\}$ and $\{e_{k}\}$ with the bound factor $q$.

Lemma [A.1](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem1) thus formally proves that analyzing the quantization of our weighted-sum moment $\mathbf{m}_{t}$ is analytically equivalent to analyzing the quantization of the standard weighted-average moment $\tilde{\mathbf{m}}_{t}$. This rigorously justifies our proof strategy and ensures that our theoretical findings are directly relevant to practical implementations of Quantized Adam. A parallel argument holds for the second moments $\mathbf{v}_{t}$ and $\tilde{\mathbf{v}}_{t}$ with decay factor $\beta_{2}$.

###### Lemma A.1 (Equivalence of Perturbed Dynamical Systems) .

###### Proof.

### A.2 Detailed Proof

To systematically analyze the effects of quantization, we begin by isolating the different sources of error. We introduce auxiliary moment estimates, $m^{\prime}_{t,i}$ and $v^{\prime}_{t,i}$, which are defined to incorporate the quantization error from the stochastic gradient, $\delta_{t,i}$, but are themselves assumed to be stored with perfect precision. Their dynamics are given by:

$$ $\displaystyle m^{\prime}_{t,i}$ $\displaystyle=\beta_{1}m^{\prime}_{t-1,i}+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i})$ (A.7) $\displaystyle v^{\prime}_{t,i}$ $\displaystyle=\beta_{2}v^{\prime}_{t-1,i}+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i})^{2}$ $$

Throughout the following proof we note $\mathbb{E}_{t-1}\left[\cdot\right]$ the conditional expectation with respect to $f_{1},\ldots,f_{t-1}$. In particular, $\mathbf{w}_{t-1}$, $\mathbf{v}_{t-1}$ is deterministic knowing $f_{1},\ldots,f_{t-1}$.
With slightly abuse of notation in the detailed proof, We introduce

$$ $\mathcal{G}_{t}=\nabla F(\mathbf{w}_{t-1})\quad\text{and}\quad\mathbf{g}_{t}=\nabla f_{t}(\mathbf{w}_{t-1}).$ (A.8) $$

We introduce the update $\mathbf{u}_{t}\in\mathbb{R}^{d}$, as well as the update without momentum $\mathbf{U}_{t}\in\mathbb{R}^{d}$:

$$ $u_{t,i}=\frac{m_{t,i}}{\sqrt{\epsilon+v_{t,i}}}\quad\text{and}\quad U_{t,i}=\frac{g_{t,i}+\delta_{t,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}.$ (A.9) $$

For any $k\in\mathbb{N}$ with $k<t$, we define $\tilde{v}_{t,k}\in\mathbb{R}^{d}$ by

$$ $\tilde{v}_{t,k,i}=\beta_{2}^{k}v^{\prime}_{t-k,i}+\mathbb{E}_{t-k}\left[\sum_{j=t-k+1}^{t}\beta_{2}^{t-j}(g_{j,i}+\delta_{j,i})^{2}\right],$ (A.10) $$

i.e. the contribution from the $k$ last gradients are replaced by their expected value for know values of $f_{1},\ldots,f_{t-k-1}$.

Using the smoothness of $F$, we have

$$ $\displaystyle F(\mathbf{w}_{t})\leq F(\mathbf{w}_{t-1})-\eta_{t}\mathcal{G}_{t}^{T}\mathbf{u}_{t}+\frac{\eta_{t}^{2}L}{2}\|\mathbf{u}_{t}\|^{2}_{2}.$ $$

The overall motivation of our proof is to find a lower bound for $\eta_{t}\mathcal{G}_{t}^{T}\mathbf{u}_{t}$.

$$ $\displaystyle\mathcal{G}_{t}^{T}\mathbf{u}_{t}=\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m_{t,i}}{\sqrt{\epsilon+v_{t,i}}}$ (A.11) $$

We can rewrite $\mathcal{G}_{t}^{T}\mathbf{u}_{t}$ as:

$$ $\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m_{t,i}}{\sqrt{\epsilon+v_{t,i}}}=\underbrace{(\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m_{t,i}}{\sqrt{\epsilon+v_{t,i}}}-\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m^{\prime}_{t,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}})}_{A}+\underbrace{\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m^{\prime}_{t,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}}_{B}$ (A.12) $$

Here, Term A represents the error component arising from the quantization of the momentum accumulators ($\mathbf{m}_{t},\mathbf{v}_{t}$), while Term B represents the behavior of the update driven by an ideal accumulator.

Now we can bound term A. We split A into two parts as before:

$$ $|A|\leq\underbrace{\left|\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m_{t,i}-m^{\prime}_{t,i}}{\sqrt{\epsilon+v_{t,i}}}\right|}_{A_{1}}+\underbrace{\left|\sum_{i\in[d]}\mathcal{G}_{t,i}\left(\frac{m^{\prime}_{t,i}}{\sqrt{\epsilon+v_{t,i}}}-\frac{m^{\prime}_{t,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right)\right|}_{A_{2}}$ (A.13) $$

The first term, $A_{1}$, which arises from the quantization noise on the first moment $\mathbf{m}$, is bounded using Lemma [A.3](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem3) (with $q=q_{M}$) and Lemma [A.5](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem5):

$$ $\displaystyle|A_{1}|$ $\displaystyle\leq\sum_{i\in[d]}R\frac{|m_{t,i}-m^{\prime}_{t,i}|}{\sqrt{v_{t,i}}}$ $\displaystyle\leq R\sum_{i\in[d]}\frac{\sum_{k=0}^{t}(\beta_{1}^{t-k}((1+q_{M})^{t-k}-1))|\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i}|}{\sqrt{\sum_{k=0}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}}}\leq q_{M}\cdot dR\cdot C_{q}$ (A.14) $$

where $C_{q}=\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}$ and $r^{\prime}=\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}$.

For the second term, $A_{2}$, we use the bound on the gradient $\|\mathcal{G}_{t}\|_{\infty}\leq R$ and apply Lemma [A.2](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem2), which requires a case analysis.

$$ $\displaystyle|A_{2}|$ $\displaystyle\leq\sum_{i\in[d]}R|m^{\prime}_{t,i}|\left|\frac{1}{\sqrt{\epsilon+v_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right|$ $\displaystyle\leq\sum_{i\in[d]}R|m^{\prime}_{t,i}|\max\left\{\frac{1}{\sqrt{\epsilon+LB_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}},\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}-\frac{1}{\sqrt{\epsilon+UB_{t,i}}}\right\}$ (A.15) $$

Let $g_{k,i}=\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i}$. We analyze the two terms inside the $\max$ for a single coordinate $i$.

Case I (Deviation from Lower Bound): Following the approximation in the provided sketch, we have

$$ $\displaystyle|m^{\prime}_{t,i}|\left(\frac{1}{\sqrt{\epsilon+LB_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right)$ $\displaystyle=|m^{\prime}_{t,i}|\left(\frac{v^{\prime}_{t,i}-LB_{t,i}}{\sqrt{\epsilon+LB_{t,i}}\sqrt{\epsilon+v^{\prime}_{t,i}}(\sqrt{\epsilon+LB_{t,i}}+\sqrt{\epsilon+v^{\prime}_{t,i}})}\right)$ $\displaystyle=\frac{|m^{\prime}_{t,i}|}{\sqrt{\epsilon+LB_{t,i}}}\frac{v^{\prime}_{t,i}-LB_{t,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}(\sqrt{\epsilon+LB_{t,i}}+\sqrt{\epsilon+v^{\prime}_{t,i}})}$ $\displaystyle\leq\frac{|m^{\prime}_{t,i}|}{\sqrt{\epsilon+LB_{t,i}}}\frac{v^{\prime}_{t,i}-LB_{t,i}}{\epsilon+v^{\prime}_{t,i}}$ $\displaystyle\hskip-56.9055pt=\frac{\sum_{k=0}^{t}\beta_{1}^{t-k}|g_{k,i}+\delta_{k,i}|}{\sqrt{\epsilon+\sum_{k=0}^{t}(\beta_{2}(1-q_{V}))^{t-k}(g_{k,i}+\delta_{k,i})^{2}}}\cdot\frac{\sum_{k=0}^{t}(\beta_{2}^{t-k}-(\beta_{2}(1-q_{V}))^{t-k})(g_{k,i}+\delta_{k,i})^{2}}{\epsilon+\sum_{k=0}^{t}\beta_{2}^{t-k}(g_{k,i}+\delta_{k,i})^{2}}$ (A.16) $$

The first fraction is bounded by Lemma [A.4](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem4): $\frac{\sum_{k=0}^{t}\beta_{1}^{k}|a_{t-k,i}|}{\sqrt{\epsilon+\sum_{k=0}^{t}(\beta_{2}(1-q_{V}))^{k}a_{t-k,i}}}\leq\frac{1}{\sqrt{1-\beta_{1}^{2}/(\beta_{2}(1-q_{V}))}}$.
The second fraction is a ratio of weighted sums $\frac{\sum_{k=0}^{t}(\beta_{2}^{k}-(\beta_{2}(1-q_{V}))^{k})a_{t-k,i}}{\epsilon+\sum_{k=0}^{t}\beta_{2}^{k}a_{t-k,i}}$. This ratio is bounded by the maximum ratio of its coefficients:

$$ $\max_{k\in\{0,\dots,t\}}\frac{\beta_{2}^{k}-(\beta_{2}(1-q_{V}))^{k}}{\beta_{2}^{k}}=\max_{k\in\{0,\dots,t\}}(1-(1-q_{V})^{k})=1-(1-q_{V})^{t}.$ $$

Combining these bounds, the term for Case I is bounded by $\frac{1}{\sqrt{1-\beta_{1}^{2}/(\beta_{2}(1-q_{V}))}}(1-(1-q_{V})^{t})$.

Case II (Deviation from Upper Bound): Similarly, we bound the second term:

$$ $\displaystyle|m^{\prime}_{t,i}|\left(\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}-\frac{1}{\sqrt{\epsilon+UB_{t,i}}}\right)$ $\displaystyle\leq\frac{|m^{\prime}_{t,i}|}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\frac{UB_{t,i}-v^{\prime}_{t,i}}{\epsilon+UB_{t,i}}$ $$

Applying Lemma [A.4](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem4) and the maximum ratio:

$$ $\leq\frac{1}{\sqrt{1-\beta_{1}^{2}/\beta_{2}}}\cdot\left(1-(1+q_{V})^{-t}\right)$ $$

Comparing the bounds from the two cases, the bound from Case I is larger since $1-(1-q_{V})^{t}>1-(1+q_{V})^{-t}$ and the denominator term $\sqrt{1-\beta_{1}^{2}/(\beta_{2}(1-q_{V}))}$ is smaller than $\sqrt{1-\beta_{1}^{2}/\beta_{2}}$. Therefore, taking the maximum and summing over $d$ dimensions:

$$ $\displaystyle|A_{2}|\leq\sum_{i\in[d]}R\frac{1-(1-q_{V})^{t}}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}=\frac{dR(1-(1-q_{V})^{t})}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}$ (A.17) $$

Combining the bounds for $|A_{1}|$ and $|A_{2}|$, we can get the bound for term A:

$$ $|A|\leq|A_{1}|+|A_{2}|\leq q_{M}\cdot dR\cdot C_{q}+\frac{dR(1-(1-q_{V})^{t})}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\triangleq Q(t)$ (A.18) $$

Now we move on to bound Term B. Let us now focus on bounding Term B from ([A.12](https://arxiv.org/html/2510.21314v1#A1.E12)). By expanding the definition of the first moment estimate $m^{\prime}_{t,i}$, we can decompose Term B into two parts, which we will call Term C and Term D:

$$ $\displaystyle\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m^{\prime}_{t,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}$ $\displaystyle=\sum_{i\in[d]}\mathcal{G}_{t,i}\sum_{k=0}^{t-1}\beta_{1}^{k}\frac{g_{t-k,i}+\delta_{t-k,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}$ (A.19) $\displaystyle=\underbrace{\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathcal{G}_{t-k,i}\frac{g_{t-k,i}+\delta_{t-k,i}}{\sqrt{\epsilon+{v^{\prime}_{t,i}}}}}_{C}+\underbrace{\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\left(\mathcal{G}_{t,i}-\mathcal{G}_{t-k,i}\right)\frac{g_{t-k,i}+\delta_{t-k,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}}_{D}.$ (A.20) $$

The magnitude of Term D, which captures the error from gradient drift, is bounded by Lemma [A.8](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem8):

$$ $\displaystyle|D|\leq\frac{\eta_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4(1+q_{G})R}\left(\sum_{l=1}^{t-1}\|\mathbf{u}_{t-l}\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}\right)+\frac{(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}.$ (A.21) $$

For Term C, we establish a lower bound on its expectation in Lemma [A.9](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem9):

$$ $\displaystyle\mathbb{E}\left[C\right]$ $\displaystyle\geq\frac{1}{2}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]\right)-\frac{2(1+q_{G})R}{\sqrt{1-\beta_{1}}}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\mathbb{E}\left[\|\mathbf{U}_{t-k}\|_{2}^{2}\right]\right)$ $\displaystyle\quad-d\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}.$ (A.22) $$

where $M_{t-k}=\frac{q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{t-k-1}\|_{2}}{\sqrt{\epsilon}}$. Injecting ([A.22](https://arxiv.org/html/2510.21314v1#A1.E22)) ,([A.21](https://arxiv.org/html/2510.21314v1#A1.E21))and ([A.20](https://arxiv.org/html/2510.21314v1#A1.E20)) into ([A.12](https://arxiv.org/html/2510.21314v1#A1.E12)) . We get the final lower bound for $\mathcal{G}_{t}^{T}\mathbf{u}_{t}$:

$$ $\displaystyle\mathbb{E}\left[\sum_{i\in[d]}\mathcal{G}_{t,i}\frac{m_{t,i}}{\sqrt{\epsilon+v_{t,i}}}\right]\geq\frac{1}{2}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]\right)-Q(t)-d\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}$ (A.23) $\displaystyle\qquad-\frac{\eta_{t}^{2}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\left(\sum_{l=1}^{t-1}\|\mathbf{u}_{t-l}\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}\right)-\frac{3(1+q_{G})R}{\sqrt{1-\beta_{1}}}\left(\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}\right).$ $$

Now lets look back at:

$$ $\displaystyle F(\mathbf{w}_{t})\leq F(\mathbf{w}_{t-1})-\eta_{t}\mathcal{G}_{t}^{T}\mathbf{u}_{t}+\frac{\eta_{t}^{2}L}{2}\|\mathbf{u}_{t}\|^{2}_{2}.$ $$

inject ([A.23](https://arxiv.org/html/2510.21314v1#A1.E23)) into it:

$$ $\displaystyle\mathbb{E}\left[F(\mathbf{w}_{t})\right]\leq\mathbb{E}\left[F(\mathbf{w}_{t-1})\right]-\frac{\eta_{t}}{2}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]\right)+\frac{\eta_{t}^{2}L}{2}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]+\eta_{t}Q(t)+\eta_{t}d\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}$ $\displaystyle\quad+\frac{\eta_{t}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\left(\sum_{l=1}^{t-1}\|\mathbf{u}_{t-l}\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}\right)+\frac{3\eta_{t}(1+q_{G})R}{\sqrt{1-\beta_{1}}}\left(\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}\right).$ (A.24) $$

We have for any $k\in\mathbb{N}$, $k<t$, and any coordinate $i\in[d]$,
$\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}\leq(1+q_{G})R\sqrt{\sum_{j=0}^{t-1}\beta_{2}^{j}}$.
Introducing $\Omega_{t}=\sqrt{\sum_{j=0}^{t-1}\beta_{2}^{j}}$,
we have

$$ $\displaystyle\mathbb{E}\left[F(\mathbf{w}_{t})\right]\leq\mathbb{E}\left[F(\mathbf{w}_{t-1})\right]-\frac{\eta_{t}}{2(1+q_{G})R\Omega_{t}}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\|\mathcal{G}_{t-k}\|_{2}^{2}\right]+\frac{\eta_{t}^{2}L}{2}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]+\eta_{t}Q(t)+\eta_{t}d\mathbb{E}\left[\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}\right]$ $\displaystyle\quad+\frac{\eta_{t}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\left(\sum_{l=1}^{t-1}\|\mathbf{u}_{t-l}\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}\right)+\frac{3\eta_{t}(1+q_{G})R}{\sqrt{1-\beta_{1}}}\left(\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}\right).$ (A.25) $$

Now summing over all iterations $t\in[T]$ for $T\in\mathbb{N}^{*}$, and $\eta_{t}$ is non-decreasing, as well the fact that $F$ is bounded below by $F_{*}$, we get

$$ $\displaystyle\underbrace{\frac{1}{2(1+q_{G})R}\sum_{t=1}^{T}\frac{\eta_{t}}{\Omega_{t}}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\|\mathcal{G}_{t-k}\|_{2}^{2}\right]}_{\tilde{A}}\leq F(\mathbf{w}_{0})-F_{*}+\underbrace{\frac{\eta_{T}^{2}L}{2}\sum_{t=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]}_{\tilde{B}}+\underbrace{\eta_{T}\sum_{t=1}^{T}Q(t)}_{E_{Q}}+\underbrace{\eta_{T}d\sum_{t=1}^{T}\mathbb{E}\left[\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}\right]}_{M}$ $\displaystyle\quad+\underbrace{\frac{\eta_{T}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\sum_{t=1}^{T}\sum_{l=1}^{t-1}\mathbb{E}\left[\|\mathbf{u}_{t-l}\|^{2}_{2}\right]\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}}_{\tilde{C}}+\underbrace{\frac{3\eta_{T}(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{t=1}^{T}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\mathbb{E}\left[\|\mathbf{U}_{t-k}\|^{2}_{2}\right]}_{\tilde{D}}.$ (A.26) $$

First lets bound Term $\tilde{A}$. We have $\eta_{t}=(1-\beta_{1})\Omega_{t}\eta$. Thus, we can simplify the $\tilde{A}$ term from ([A.26](https://arxiv.org/html/2510.21314v1#A1.E26)), also using the usual change of index $j=t-k$, to get

$$ $\displaystyle\tilde{A}$ $\displaystyle=\frac{1}{2(1+q_{G})R}\sum_{t=1}^{T}\frac{\eta_{t}}{\Omega_{t}}\sum_{j=1}^{t}\beta_{1}^{t-j}\mathbb{E}\left[\|\mathcal{G}_{j}\|_{2}^{2}\right]$ $\displaystyle=\frac{\eta(1-\beta_{1})}{2(1+q_{G})R}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathcal{G}_{j}\|_{2}^{2}\right]\sum_{t=j}^{T}\beta_{1}^{t-j}$ $\displaystyle=\frac{\eta}{2(1+q_{G})R}\sum_{j=1}^{T}(1-\beta_{1}^{T-j+1})\mathbb{E}\left[\|\mathcal{G}_{j}\|_{2}^{2}\right]$ $\displaystyle=\frac{\eta}{2(1+q_{G})R}\sum_{j=1}^{T}(1-\beta_{1}^{T-j+1})\mathbb{E}\left[\|\nabla F(\mathbf{w}_{j-1})\|_{2}^{2}\right]$ $\displaystyle=\frac{\eta}{2(1+q_{G})R}\sum_{j=0}^{T-1}(1-\beta_{1}^{T-j})\mathbb{E}\left[\|\nabla F(\mathbf{w}_{j})\|_{2}^{2}\right].$ (A.27) $$

To establish our convergence guarantee, we analyze the expected gradient norm at a randomly selected iteration $\tau$, drawn from the set $\{0,\ldots,T-1\}$. The selection is not uniform but is instead weighted to properly account for the influence of the momentum term over the iterations. The probability of selecting a specific iteration $t$ is defined as:

$$ $\displaystyle\forall t\in\{0,\ldots,T-1\},\quad\mathbb{P}(\tau=t)\propto 1-\beta_{1}^{T-t}.$ (A.28) $$

We can notice that

$$ $\displaystyle\sum_{j=0}^{T-1}(1-\beta_{1}^{T-j})=T-\beta_{1}\frac{1-\beta_{1}^{T}}{1-\beta_{1}}\geq T-\frac{\beta_{1}}{1-\beta_{1}}.$ (A.29) $$

Introducing

$$ $\tilde{T}=T-\frac{\beta_{1}}{1-\beta_{1}},$ (A.30) $$

we then have

$$ $\displaystyle\tilde{A}\geq\frac{\eta\tilde{T}}{2(1+q_{G})R}\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}^{2}\right].$ (A.31) $$

Next looking at $\tilde{B}$, we apply Lemma [A.13](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem13),

$$ $\displaystyle\tilde{B}\leq B^{\prime}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right)$ (A.32) $$

with

$$ $\displaystyle B^{\prime}=\frac{d\eta_{T}^{2}L}{2(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})}.$ (A.33) $$

Then looking at $\tilde{C}$ and introducing the change of index $j=t-l$,

$$ $\displaystyle\tilde{C}$ $\displaystyle=\frac{\eta_{T}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\sum_{t=1}^{T}\sum_{j=1}^{t}\mathbb{E}\left[\|\mathbf{u}_{j}\|^{2}_{2}\right]\sum_{k=t-j}^{t-1}\beta_{1}^{k}\sqrt{k}$ $\displaystyle=\frac{\eta_{T}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{j}\|^{2}_{2}\right]\sum_{t=j}^{T}\sum_{k=t-j}^{t-1}\beta_{1}^{k}\sqrt{k}$ $\displaystyle=\frac{\eta_{T}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{j}\|^{2}_{2}\right]\sum_{k=0}^{T-1}\beta_{1}^{k}\sqrt{k}\sum_{t=j}^{j+k}1$ $\displaystyle=\frac{\eta_{T}^{3}L^{2}}{4(1+q_{G})R}\sqrt{1-\beta_{1}}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{j}\|^{2}_{2}\right]\sum_{k=0}^{T-1}\beta_{1}^{k}\sqrt{k}(k+1)$ $\displaystyle\leq\frac{\eta_{T}^{3}L^{2}}{(1+q_{G})R}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{j}\|^{2}_{2}\right]\frac{\beta_{1}}{(1-\beta_{1})^{2}}.$ (A.34) $$

using Lemma [A.12](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem12). Finally, using Lemma [A.13](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem13), we get

$$ $\tilde{C}\leq C^{\prime}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right).$ (A.35) $$

with

$$ $\displaystyle C^{\prime}=\frac{d\eta_{T}^{3}L^{2}\beta_{1}}{(1+q_{G})R(1-\beta_{1})^{2}(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})}.$ (A.36) $$

introducing the same change of index $j=t-k$ for $\tilde{D}$, we get

$$ $\displaystyle\tilde{D}$ $\displaystyle=\frac{3\eta_{T}(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{t=1}^{T}\sum_{j=1}^{t}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{t-j}\sqrt{1+t-j}\mathbb{E}\left[\|\mathbf{U}_{j}\|_{2}^{2}\right]$ $\displaystyle=\frac{3\eta_{T}(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathbf{U}_{j}\|_{2}^{2}\right]\sum_{t=j}^{T}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{t-j}\sqrt{1+t-j}$ $\displaystyle\leq\frac{6\eta_{T}(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{j=1}^{T}\mathbb{E}\left[\|\mathbf{U}_{j}\|_{2}^{2}\right]\frac{1}{(1-\beta_{1}/\beta_{2})^{3/2}},$ (A.37) $$

using Lemma [A.11](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem11). Finally, using Lemma [A.10](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem10), we get

$$ $\displaystyle\tilde{D}$ $\displaystyle\leq\frac{6\eta_{T}(1+q_{G})R}{\sqrt{1-\beta_{1}}(1-\beta_{1}/\beta_{2})^{3/2}}\sum_{i\in[d]}\left(\ln\left(1+\frac{v^{\prime}_{T,i}}{\epsilon}\right)-T\ln(\beta_{2})\right)$ $\displaystyle\leq\frac{6d\eta_{T}(1+q_{G})R}{\sqrt{1-\beta_{1}}(1-\beta_{1}/\beta_{2})^{3/2}}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right)$ (A.38) $$

Then we rewrite the quantization error term $E_{Q}$:

$$ $\displaystyle E_{Q}$ $\displaystyle=\eta_{T}\sum_{t=1}^{T}\left(q_{M}\cdot dR\cdot C_{q}+\frac{dR(1-(1-q_{V})^{t})}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\right)$ $\displaystyle=\eta_{T}\left(\sum_{t=1}^{T}\left(q_{M}\cdot dR\cdot C_{q}+\frac{dR}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\right)-\sum_{t=1}^{T}\frac{dR(1-q_{V})^{t}}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\right)$ $\displaystyle=\eta_{T}\left(T\left(q_{M}\cdot dR\cdot C_{q}+\frac{dR}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\right)-\frac{dR}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\sum_{t=1}^{T}(1-q_{V})^{t}\right)$ $\displaystyle=\eta_{T}\left(T\cdot q_{M}\cdot dR\cdot C_{q}+\frac{TdR}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}-\frac{dR}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\left(\frac{1-q_{V}}{q_{V}}(1-(1-q_{V})^{T})\right)\right)$ $$

Finally, we bound Term M using Lemma [A.14](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem14):

$$ $\displaystyle M\leq\frac{\eta_{T}dT}{\sqrt{\epsilon}(1-\beta_{1})}\left(q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{0}\|_{2}\right)+\frac{\eta_{T}^{2}d^{\frac{3}{2}}Lq_{W}RT^{2}}{2\sqrt{\epsilon}(1-\beta_{1})\sqrt{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}},$ (A.40) $$

Now putting ([A.31](https://arxiv.org/html/2510.21314v1#A1.E31)), ([A.32](https://arxiv.org/html/2510.21314v1#A1.E32)), ([A.35](https://arxiv.org/html/2510.21314v1#A1.E35)), ([A.38](https://arxiv.org/html/2510.21314v1#A1.E38)), (LABEL:app:eq:common_eq_bound_exact_main) and ([A.40](https://arxiv.org/html/2510.21314v1#A1.E40)) together into ([A.26](https://arxiv.org/html/2510.21314v1#A1.E26)) and noting that $\eta_{T}\leq\eta\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}}$, we get:

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}^{2}\right]$ $\displaystyle\leq 2(1+q_{G})R\frac{F_{0}-F_{*}}{\eta\tilde{T}}+\frac{E}{\tilde{T}}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right)$ $\displaystyle+\frac{H}{\tilde{T}}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right)+\frac{Q(T)}{\tilde{T}}$ $\displaystyle+\frac{2(1+q_{G})dT}{\tilde{T}\sqrt{\epsilon(1-\beta_{2})}}\left(q_{G}R^{3}+Lq_{W}R^{2}\|\mathbf{w}_{0}\|_{2}\right)+\frac{(1-\beta_{1})d^{\frac{3}{2}}\eta Lq_{W}(1+q_{G})R^{2}T^{2}}{\tilde{T}\sqrt{\epsilon}(1-\beta_{2})\sqrt{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}.$ (A.41) $$

with

$$ $\begin{gathered}E=\frac{12d((1+q_{G})R)^{2}\sqrt{1-\beta_{1}}}{(1-\beta_{1}/\beta_{2})^{3/2}\sqrt{1-\beta_{2}}}\\ H=\frac{d\eta L(1+q_{G})R(1-\beta_{1})^{2}}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})(1-\beta_{2})}+\frac{2d\eta^{2}L^{2}\beta_{1}(1-\beta_{1})}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})(1-\beta_{2})^{\frac{3}{2}}}\\ Q(T)=\frac{2(1+q_{G})q_{M}dR^{2}(1-\beta_{1})T}{\sqrt{1-\beta_{2}}}\cdot\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}+\frac{2(1+q_{G})dR^{2}(1-\beta_{1})T}{\sqrt{(1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})})(1-\beta_{2})}}\\ -\frac{2(1+q_{G})dR^{2}(1-\beta_{1})}{\sqrt{(1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})})(1-\beta_{2})}}\left(\frac{1-q_{V}}{q_{V}}(1-(1-q_{V})^{T})\right)\\ \text{where}\quad r^{\prime}=\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}\end{gathered}$ (A.42) $$

For clarity in the main theorem statement, we can present a slightly looser but more accessible version of this bound. By noting that for a sufficiently large $T$, we have $\tilde{T}\geq T/2$, and

$$ $\displaystyle\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right)<\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right),$ $$

we can state the simplified bound presented in Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5):

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}^{2}\right]\leq 4(1+q_{G})R\frac{F_{0}-F_{*}}{\eta T}+\frac{C}{T}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right)$ $\displaystyle+\frac{\tilde{Q}(T)}{T}+\frac{4(1+q_{G})d}{\sqrt{\epsilon(1-\beta_{2})}}\left(q_{G}R^{3}+Lq_{W}R^{2}D\right)+\frac{2(1-\beta_{1})d^{\frac{3}{2}}\eta Lq_{W}(1+q_{G})R^{2}T}{\sqrt{\epsilon}(1-\beta_{2})\sqrt{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}},$ $$

with

$$ $\begin{gathered}C=\frac{24d((1+q_{G})R)^{2}\sqrt{1-\beta_{1}}}{(1-\beta_{1}/\beta_{2})^{3/2}\sqrt{1-\beta_{2}}}+\frac{2d\eta L(1+q_{G})R(1-\beta_{1})^{2}}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})(1-\beta_{2})}\\ +\frac{4d\eta^{2}L^{2}\beta_{1}(1-\beta_{1})}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})(1-\beta_{2})^{\frac{3}{2}}},\\ \tilde{Q}(T)=\frac{4(1+q_{G})q_{M}dR^{2}(1-\beta_{1})T}{\sqrt{1-\beta_{2}}}\cdot\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}+\frac{4(1+q_{G})dR^{2}(1-\beta_{1})T}{\sqrt{(1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})})(1-\beta_{2})}}\\ -\frac{4(1+q_{G})dR^{2}(1-\beta_{1})}{\sqrt{(1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})})(1-\beta_{2})}}\left(\frac{1-q_{V}}{q_{V}}(1-(1-q_{V})^{T})\right)\\ \text{where}\quad r^{\prime}=\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}\end{gathered}$ (A.43) $$

Theory [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) states that under a specific schedule for the hyperparameters and a gradual reduction in quantization error, Quantized Adam achieves the same convergence rate as its full-precision counterpart. We prove this by performing a detailed asymptotic analysis of each term in the main bound from Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5) as the total number of iterations $T\to\infty$.

However, to perform a precise asymptotic analysis and derive the tightest possible convergence rate from our framework, we will now analyze the order of each component from the more detailed bound in  [A.2](https://arxiv.org/html/2510.21314v1#A1.Ex41):

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathrm{vec}(\mathbf{W})_{\tau})\|_{2}^{2}\right]$ $\displaystyle\leq \underbrace{2(1+q_{G})R\frac{F_{0}-F_{*}}{\eta\tilde{T}}}_{\text{Term 1}}$ $\displaystyle+\underbrace{\frac{12d((1+q_{G})R)^{2}\sqrt{1-\beta_{1}}}{\tilde{T}(1-\beta_{1}/\beta_{2})^{3/2}\sqrt{1-\beta_{2}}}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right)}_{\text{Term 2}}$ $\displaystyle+\underbrace{\frac{E}{\tilde{T}}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right)}_{\text{Term 3}}$ $\displaystyle+\underbrace{\frac{Q(T)}{\tilde{T}}}_{\text{Term 4}}+\underbrace{\frac{2(1+q_{G})dT}{\tilde{T}\sqrt{\epsilon(1-\beta_{2})}}\left(q_{G}R^{3}+Lq_{W}R^{2}\|\mathrm{vec}(\mathbf{W}_{0})\|_{2}\right)}_{\text{Term 5}}$ $\displaystyle+\underbrace{\frac{(1-\beta_{1})d^{\frac{3}{2}}\eta Lq_{W}(1+q_{G})R^{2}T^{2}}{\tilde{T}\sqrt{\epsilon}(1-\beta_{2})\sqrt{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}}_{\text{Term 6}}.$ $$

Our proof strategy is to analyze the asymptotic order of each term under the following scaling assumptions.

#### Scaling Assumptions.

We adopt the scaling assumptions provided in the Theorem:

- •
Quantization Error Schedules: The quantization errors are annealed over time such that $q_{G}=\mathcal{O}(T^{-1})$, $q_{M}=\mathcal{O}(T^{-1})$, $q_{W}=\mathcal{O}(T^{-2})$, and $q_{V}=\mathcal{O}(T^{-2})$.
- •
Adam Hyperparameters: The learning rate and second-moment decay are set as $\eta=\Theta(T^{-1/2})$ and $1-\beta_{2}=\Theta(1/T)$, while $\beta_{1}$ is treated as a constant.

#### Asymptotic Analysis of Bound Terms.

We now analyze the order of magnitude for each of the six terms.

Term 1 (Initial Condition Term): This term is given by $T_{1}=2(1+q_{G})R\frac{F_{0}-F_{*}}{\eta\tilde{T}}$.
We analyze the components of its denominator. The effective number of iterations is $\tilde{T}=T-\frac{\beta_{1}}{1-\beta_{1}}=\Theta(T)$. The learning rate scales as $\eta=\Theta(T^{-1/2})$. The denominator thus scales as $\eta\tilde{T}=\Theta(T^{-1/2})\Theta(T)=\Theta(T^{1/2})$. Since all other quantities are constants and $q_{G}\to 0$, the entire term scales as:

$$ $\displaystyle T_{1}=\Theta\left(\frac{1}{\eta\tilde{T}}\right)=\Theta\left(\frac{1}{T^{1/2}}\right)=\Theta(T^{-1/2}).$ $$

Term 2 (First Logarithmic Term): This term is:

$$ $\displaystyle T_{2}=\frac{12d((1+q_{G})R)^{2}\sqrt{1-\beta_{1}}}{\tilde{T}(1-\beta_{1}/\beta_{2})^{3/2}\sqrt{1-\beta_{2}}}\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right)$ $$

The leading fraction’s order is determined by its denominator, $\tilde{T}\sqrt{1-\beta_{2}}$. With $\tilde{T}=\Theta(T)$ and $1-\beta_{2}=\Theta(1/T)$, we have $\sqrt{1-\beta_{2}}=\Theta(T^{-1/2})$. Thus, the fraction scales as $\Theta(\frac{1}{T\cdot T^{-1/2}})=\Theta(T^{-1/2})$. The term in the parenthesis scales as $\ln(1+\Theta(T))-\Theta(1)=\Theta(\ln T)$. The overall order is:

$$ $\displaystyle T_{2}=\Theta\left(\frac{1}{\tilde{T}\sqrt{1-\beta_{2}}}\right)\cdot\Theta(\ln T)=\Theta\left(T^{-1/2}\right)\cdot\Theta(\ln T)=\Theta\left(\frac{\ln T}{\sqrt{T}}\right).$ $$

Term 3 (Second Logarithmic Term): This term is $T_{3}=\frac{E}{\tilde{T}}\left(\ln(...)-T\ln(...)\right)$.
First, we determine the asymptotic order of $E$, which is defined as:

$$ $E=\frac{d\eta L(1+q_{G})R(1-\beta_{1})^{2}}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})(1-\beta_{2})}+\frac{2d\eta^{2}L^{2}\beta_{1}(1-\beta_{1})}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})(1-\beta_{2})^{\frac{3}{2}}}.$ $$

For the first part of $E$, the numerator scales as $\eta=\Theta(T^{-1/2})$ and the denominator is dominated by $(1-\beta_{2})=\Theta(T^{-1})$. This part is $\Theta(T^{-1/2})/\Theta(T^{-1})=\Theta(T^{1/2})$. For the second part, the numerator scales as $\eta^{2}=\Theta(T^{-1})$ and the denominator is dominated by $(1-\beta_{2})^{3/2}=\Theta(T^{-3/2})$. This part is $\Theta(T^{-1})/\Theta(T^{-3/2})=\Theta(T^{1/2})$. Thus, $E=\Theta(T^{1/2})$. The logarithmic part scales as $\Theta(\ln T)$, so the entire term scales as:

$$ $\displaystyle T_{3}=\Theta\left(\frac{E}{\tilde{T}}\right)\cdot\Theta(\ln T)=\Theta\left(\frac{T^{1/2}}{T}\right)\cdot\Theta(\ln T)=\Theta\left(\frac{\ln T}{\sqrt{T}}\right).$ $$

Term 4 (Moment Quantization Error): We rewrite this term as:

$$ $\displaystyle T_{4}=\frac{2(1+q_{G})dR^{2}T(1-\beta_{1})}{\tilde{T}\sqrt{1-\beta_{2}}}Q,$ $$

where $Q=q_{M}\cdot\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}+\frac{1}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}-\frac{1}{T}\frac{1}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\left(\frac{1-q_{V}}{q_{V}}(1-(1-q_{V})^{T})\right)$.

Our goal is to show that $T_{4}=\mathcal{O}(T^{-1/2})$.

First, the pre-factor has an asymptotic order of:

$$ $\displaystyle\frac{2(1+q_{G})dR^{2}T(1-\beta_{1})}{\tilde{T}\sqrt{1-\beta_{2}}}=\Theta\left(\frac{T}{T\cdot T^{-1/2}}\right)=\Theta(T^{1/2}).$ $$

The core of the analysis thus lies in determining the order of $Q$. We can rewrite $Q$ by combining its second and third components:

$$ $\displaystyle Q=q_{M}\cdot\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}+\frac{1}{\sqrt{1-\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}}}\left[1-\frac{1}{T}\left(\frac{1-q_{V}}{q_{V}}(1-(1-q_{V})^{T})\right)\right].$ $$

The first part of $Q$ is clearly $\mathcal{O}(q_{M})=\mathcal{O}(T^{-1})$. The common factor in the second part, $\frac{1}{\sqrt{1-\dots}}$, converges to a constant as $T\to\infty$, so it is $\mathcal{O}(1)$. The analysis therefore simplifies to finding the order of the bracketed term.

Let $x=q_{V}=\mathcal{O}(T^{-2})$. We perform a Taylor expansion on $(1-x)^{T}$:

$$ $\displaystyle(1-x)^{T}=1-Tx+\frac{T(T-1)}{2}x^{2}+\mathcal{O}(T^{3}x^{3}).$ $$

This allows us to analyze the term inside the bracket:

$$ $\displaystyle 1-\frac{1}{T}\left(\frac{1-x}{x}(1-(1-x)^{T})\right)$ $\displaystyle=1-\frac{1}{T}\frac{1-x}{x}\left(Tx-\frac{T(T-1)}{2}x^{2}+\mathcal{O}(T^{3}x^{3})\right)$ $\displaystyle=1-\frac{1}{T}(1-x)\left(T-\frac{T(T-1)}{2}x+\mathcal{O}(T^{3}x^{2})\right)$ $\displaystyle=1-\frac{1}{T}\left(T-\frac{T(T-1)}{2}x-Tx+\mathcal{O}(T^{2}x^{2})\right)$ $\displaystyle=1-\left(1-\frac{T(T+1)}{2T}x+\mathcal{O}(T^{2}x^{2})\right)$ $\displaystyle=\frac{T+1}{2}x-\mathcal{O}(T^{2}x^{2}).$ $$

Substituting back $x=q_{V}=\mathcal{O}(T^{-2})$, the bracketed term has an order of:

$$ $\displaystyle\mathcal{O}(T\cdot q_{V})=\mathcal{O}(T\cdot T^{-2})=\mathcal{O}(T^{-1}).$ $$

Therefore, the entire second component of $Q$ is $\mathcal{O}(1)\cdot\mathcal{O}(T^{-1})=\mathcal{O}(T^{-1})$.
Combining both components of $Q$, we find its overall order:

$$ $\displaystyle Q=\mathcal{O}(T^{-1})+\mathcal{O}(T^{-1})=\mathcal{O}(T^{-1}).$ $$

Finally, we compute the order of Term 4 by combining the pre-factor and $Q$:

$$ $\displaystyle T_{4}=\Theta(T^{1/2})\cdot\mathcal{O}(T^{-1})=\mathcal{O}(T^{-1/2}).$ $$

Term 5 (Initial W/G Quantization Error): This term is:

$$ $\displaystyle T_{5}=\frac{2(1+q_{G})dT}{\tilde{T}\sqrt{\epsilon(1-\beta_{2})}}\left(q_{G}R^{3}+Lq_{W}R^{2}\|\mathrm{vec}(\mathbf{W}_{0})\|_{2}\right)$ $$

The leading fraction scales as $\frac{T}{\tilde{T}\sqrt{1-\beta_{2}}}=\frac{\Theta(T)}{\Theta(T)\Theta(T^{-1/2})}=\Theta(T^{1/2})$. The parenthesis scales with its dominant term $q_{G}=\mathcal{O}(T^{-1})$. The total order is:

$$ $\displaystyle T_{5}=\Theta(T^{1/2})\cdot\mathcal{O}(q_{G}+q_{W})=\Theta(T^{1/2})\cdot(\mathcal{O}(T^{-1})+\mathcal{O}(T^{-2}))=\mathcal{O}(T^{-1/2}).$ $$

Term 6 (Weight Growth Quantization Error): This term is $T_{6}=\frac{(1-\beta_{1})d^{\frac{3}{2}}\eta Lq_{W}(1+q_{G})R^{2}T^{2}}{\tilde{T}\sqrt{\epsilon}(1-\beta_{2})\sqrt{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}$.
First, we analyze $\sqrt{\frac{1}{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}$. As $T\to\infty$, the denominator converges to the constant $1-\beta_{1}^{2}$, so its contribution is $\mathcal{O}(1)$. The term’s order is determined by the scaling of its other components: $\eta=\Theta(T^{-1/2})$, $q_{W}=\mathcal{O}(T^{-2})$, $\tilde{T}=\Theta(T)$, and $(1-\beta_{2})=\Theta(T^{-1})$. The total order is:

$$ $\displaystyle T_{6}=\Theta\left(\frac{\eta\cdot q_{W}\cdot T^{2}}{\tilde{T}\cdot(1-\beta_{2})}\right)=\Theta\left(\frac{T^{-1/2}\cdot T^{-2}\cdot T^{2}}{T\cdot T^{-1}}\right)=\Theta(T^{-1/2}).$ $$

#### Conclusion.

By comparing the asymptotic orders of all terms, we identify those that converge to zero at the slowest rate, as they will dominate the overall convergence bound. The orders are:

- •
Term 1, 4, 5, 6: $\mathcal{O}(T^{-1/2})$ or $\Theta(T^{-1/2})$.
- •
Term 2, 3: $\Theta(T^{-1/2}\ln T)$.

The dominant terms are the second and third, which are of order $\Theta(T^{-1/2}\ln T)$. These terms form the bottleneck that determines the overall convergence rate. Thus, under the specified parameter schedule, the expected squared gradient norm converges to zero at the following rate:

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}^{2}\right]=\Theta\left(\frac{\ln T}{\sqrt{T}}\right)=\tilde{\mathcal{O}}\left(\frac{1}{\sqrt{T}}\right).$ $$

This matches the known convergence rate for full-precision Adam.

Furthermore, we derive the convergence rate for the expected gradient norm, $\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}\right]$, from the rate of its squared value. We use Jensen’s inequality, which states that for a convex function $\phi$ and a random variable $X$, $\phi(\mathbb{E}[X])\leq\mathbb{E}[\phi(X)]$.

Let the random variable be $X=\|\nabla F(\mathbf{w}_{\tau})\|_{2}$ and the convex function be $\phi(x)=x^{2}$. Applying Jensen’s inequality yields:

$$ $\displaystyle\left(\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}\right]\right)^{2}\leq\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}^{2}\right].$ $$

By taking the square root of both sides, we obtain a bound on the expected norm:

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}\right]\leq\sqrt{\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}^{2}\right]}.$ $$

Substituting our previously derived convergence rate:

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\mathbf{w}_{\tau})\|_{2}\right]$ $\displaystyle\leq\sqrt{\tilde{\mathcal{O}}\left(\frac{1}{\sqrt{T}}\right)}$ $\displaystyle=\tilde{\mathcal{O}}\left(\sqrt{T^{-1/2}}\right)$ $\displaystyle=\tilde{\mathcal{O}}\left(T^{-1/4}\right).$ $$

Thus, the expected gradient norm converges to zero at a rate of $\tilde{\mathcal{O}}(T^{-1/4})$. This finalizes the proof of the theorem.

### A.3 Proof of Lemma A.2

###### Lemma A.2 (The value range of $v_{t,i}$ and the upper bound of $|\frac{1}{\sqrt{\epsilon+v_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}|$ ) .

Let $LB_{t,i}=\sum_{k=0}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}$ and $UB_{t,i}=\sum_{k=0}^{t}\beta_{2}^{t-k}(1+q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}$. We have:

$$ $\displaystyle\sum_{k=0}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}\leq v_{t,i}\leq\sum_{k=0}^{t}\beta_{2}^{t-k}(1+q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}$ (A.44) $$

$$ $\displaystyle\left|\frac{1}{\sqrt{\epsilon+v_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right|\leq\max\left\{\frac{1}{\sqrt{\epsilon+LB_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}},\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}-\frac{1}{\sqrt{\epsilon+UB_{t,i}}}\right\}$ (A.45) $$

###### Proof.

The proof consists of two parts.

Part 1: Bounding $v_{t,i}$

The update rule for the second moment estimate is $v_{t,i}=\beta_{2}(v_{t-1,i}+\theta_{t-1,i})+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i})^{2}$. The quantization noise is assumed to be a relative error, bounded by $|\theta_{t-1,i}|\leq q_{V}|v_{t-1,i}|$. This implies that $(1-q_{V})v_{t-1,i}\leq v_{t-1,i}+\theta_{t-1,i}\leq(1+q_{V})v_{t-1,i}$.

Applying this to the update rule, we can establish the lower bound by recursively unrolling the inequality:

$$ $\displaystyle v_{t,i}$ $\displaystyle\geq\beta_{2}(1-q_{V})v_{t-1,i}+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i})^{2}$ $\displaystyle\geq\beta_{2}(1-q_{V})\left[\beta_{2}(1-q_{V})v_{t-2,i}+(\nabla_{i}f_{t-1}(\mathbf{w}_{t-2})+\delta_{t-1,i})^{2}\right]+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i})^{2}$ $\displaystyle=\dots$ $\displaystyle=\sum_{k=0}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}$ (A.46) $$

Similarly, we can establish the upper bound:

$$ $\displaystyle v_{t,i}$ $\displaystyle\leq\beta_{2}(1+q_{V})v_{t-1,i}+(\nabla_{i}f_{t}(\mathbf{w}_{t-1})+\delta_{t,i})^{2}$ $\displaystyle=\sum_{k=0}^{t}\beta_{2}^{t-k}(1+q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}$ (A.47) $$

This completes the proof of the first statement in the lemma.

Part 2: Bounding the difference of the inverse square roots

Let $v^{\prime}_{t,i}$ be the idealized second moment estimate, updated without the quantization noise $\theta$. Its explicit form is:

$$ $\displaystyle v^{\prime}_{t,i}=\sum_{k=0}^{t}\beta_{2}^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}$ (A.48) $$

From Part 1, we know that $v_{t,i}$ is in the interval $[LB_{t,i},UB_{t,i}]$, where $LB_{t,i}$ and $UB_{t,i}$ are the bounds established.

Now, we compare $v^{\prime}_{t,i}$ with these bounds. Since $0<\beta_{2}<1$ and we assume $0<q_{V}<1$, we have $\beta_{2}(1-q_{V})<\beta_{2}<\beta_{2}(1+q_{V})$. This implies a term-by-term inequality, leading to:

$$ $\displaystyle LB_{t,i}<v^{\prime}_{t,i}<UB_{t,i}$ (A.49) $$

Consider the function $f(y)=1/\sqrt{\epsilon+y}$ for $y\geq 0$. This function is monotonically decreasing and convex. The value $v_{t,i}$ lies in the interval $[LB_{t,i},UB_{t,i}]$, and $v^{\prime}_{t,i}$ is a point within this interval. The maximum absolute difference $|f(v_{t,i})-f(v^{\prime}_{t,i})|$ must occur when $v_{t,i}$ is at one of the endpoints of the interval. Therefore, we can bound the difference as:

$$ $\displaystyle\left|\frac{1}{\sqrt{\epsilon+v_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right|$ $\displaystyle\leq\max\left\{\left|\frac{1}{\sqrt{\epsilon+LB_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right|,\left|\frac{1}{\sqrt{\epsilon+UB_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right|\right\}$ (A.50) $$

Since $LB_{t,i}<v^{\prime}_{t,i}<UB_{t,i}$ and the function is decreasing, we have $1/\sqrt{\epsilon+UB_{t,i}}<1/\sqrt{\epsilon+v^{\prime}_{t,i}}<1/\sqrt{\epsilon+LB_{t,i}}$. We can therefore remove the absolute value signs:

$$ $\displaystyle\left|\frac{1}{\sqrt{\epsilon+v_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}\right|$ $\displaystyle\leq\max\left\{\frac{1}{\sqrt{\epsilon+LB_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}},\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}-\frac{1}{\sqrt{\epsilon+UB_{t,i}}}\right\}$ (A.51) $$

This completes the proof of the second statement.
∎

###### Lemma A.2 (The value range of v t , i v_{t,i} and the upper bound of | 1 ϵ + v t , i − 1 ϵ + v t , i ′ | |\frac{1}{\sqrt{\epsilon+v_{t,i}}}-\frac{1}{\sqrt{\epsilon+v^{\prime}_{t,i}}}| ) .

###### Proof.

### A.4 Proof of Lemma A.3

###### Lemma A.3 (Bound on Discrete Error) .

Given two discrete-time systems defined for $t\geq 1$:

- •
System A: $a_{t}=k(a_{t-1}+c_{t-1})+d_{t}$
- •
System B: $b_{t}=kb_{t-1}+d_{t}$

where the perturbation term $c_{t}$ is bounded by $|c_{t}|\leq q|a_{t}|$ for all $t$, and the constants $k,q$ satisfy $0<k<1$ and $q<k$.

Under zero initial conditions, where $a_{0}=b_{0}=0$, the absolute error between the states of the two systems is bounded by:

$$ $\displaystyle|a_{t}-b_{t}|\leq\sum_{j=1}^{t-1}\left[(k(1+q))^{t-j}-k^{t-j}\right]|d_{j}|$ (A.52) $$

###### Proof.

First, define the error as $e_{t}=a_{t}-b_{t}$. Subtracting the two system equations yields the error recurrence relation:

$$ $\displaystyle e_{t}=ke_{t-1}+kc_{t-1}$ (A.53) $$

The explicit solution to this recurrence is $e_{t}=k^{t}e_{0}+\sum_{j=0}^{t-1}k^{t-j}c_{j}$. Under the zero initial condition $a_{0}=b_{0}=0$, this simplifies to:

$$ $\displaystyle e_{t}=\sum_{j=0}^{t-1}k^{t-j}c_{j}$ (A.54) $$

Taking the absolute value and applying the given condition $|c_{j}|\leq q|a_{j}|$, we have:

$$ $\displaystyle|e_{t}|\leq\sum_{j=0}^{t-1}k^{t-j}|c_{j}|\leq q\sum_{j=0}^{t-1}k^{t-j}|a_{j}|$ (A.55) $$

Since $a_{0}=0$, the sum starts from $j=1$. The state $|a_{j}|$ can be bounded from its own recurrence $|a_{t}|\leq k(1+q)|a_{t-1}|+|d_{t}|$, which for $a_{0}=0$ unrolls to:

$$ $\displaystyle|a_{j}|\leq\sum_{i=1}^{j}(k(1+q))^{j-i}|d_{i}|$ (A.56) $$

Substituting the bound for $|a_{j}|$ into the inequality for $|e_{t}|$ gives a double summation:

$$ $\displaystyle|e_{t}|\leq q\sum_{j=1}^{t-1}k^{t-j}\left(\sum_{i=1}^{j}(k(1+q))^{j-i}|d_{i}|\right)$ (A.57) $$

By swapping the order of summation and evaluating the inner geometric series, we obtain the final result:

$$ $\displaystyle|a_{t}-b_{t}|\leq\sum_{j=1}^{t-1}\left[(k(1+q))^{t-j}-k^{t-j}\right]|d_{j}|$ (A.58) $$

∎

###### Lemma A.3 (Bound on Discrete Error) .

###### Proof.

### A.5 Proof of Lemma A.4

###### Lemma A.4 (Finite Geometric Series Ratio Bounded by Infinite Sum) .

Let $(g_{k})_{k=0}^{t}$ be a sequence of scalars for any finite $t\in\mathbb{N}$. Let the weights be terms of two geometric series, $A_{k}=a^{k}$ and $B_{k}=b^{k}$, where $a,b\in(0,1)$ are the base ratios.

If the condition $a^{2}<b$ holds, then the ratio of the weighted sum is bounded by a constant derived from the corresponding infinite series:

$$ $\displaystyle\frac{\sum_{k=0}^{t}a^{k}|g_{k}|}{\sqrt{\sum_{k=0}^{t}b^{k}g_{k}^{2}}}\leq\sqrt{\frac{1}{1-a^{2}/b}}$ (A.59) $$

###### Proof.

Let the numerator be $N_{t}=\sum_{k=0}^{t}a^{k}|g_{k}|$ and the denominator be $D_{t}=\sqrt{\sum_{k=0}^{t}b^{k}g_{k}^{2}}$.

We rewrite the numerator as:

$$ $\displaystyle N_{t}=\sum_{k=0}^{t}\left(\frac{a^{k}}{\sqrt{b^{k}}}\right)\cdot\left(\sqrt{b^{k}}|g_{k}|\right)$ (A.60) $$

Applying the Cauchy-Schwarz inequality to these finite sums, we get:

$$ $\displaystyle N_{t}^{2}$ $\displaystyle\leq\left(\sum_{k=0}^{t}\left(\frac{a^{k}}{\sqrt{b^{k}}}\right)^{2}\right)\cdot\left(\sum_{k=0}^{t}\left(\sqrt{b^{k}}|g_{k}|\right)^{2}\right)$ $\displaystyle=\left(\sum_{k=0}^{t}\frac{a^{2k}}{b^{k}}\right)\cdot\left(\sum_{k=0}^{t}b^{k}g_{k}^{2}\right)$ $\displaystyle=\left(\sum_{k=0}^{t}\left(\frac{a^{2}}{b}\right)^{k}\right)\cdot D_{t}^{2}$ (A.61) $$

The first term is a finite geometric series. Since the condition $a^{2}<b$ implies that the ratio $r=a^{2}/b$ is positive and less than 1, all terms in the series are positive. Therefore, the finite sum is always less than or equal to the sum of the infinite series:

$$ $\displaystyle\sum_{k=0}^{t}\left(\frac{a^{2}}{b}\right)^{k}\leq\sum_{k=0}^{\infty}\left(\frac{a^{2}}{b}\right)^{k}=\frac{1}{1-a^{2}/b}$ (A.62) $$

Substituting this upper bound back into the inequality for $N_{t}^{2}$, we have:

$$ $\displaystyle N_{t}^{2}\leq\left(\frac{1}{1-a^{2}/b}\right)\cdot D_{t}^{2}$ (A.63) $$

Taking the square root of both sides gives:

$$ $\displaystyle N_{t}\leq\sqrt{\frac{1}{1-a^{2}/b}}\cdot D_{t}$ (A.64) $$

Finally, dividing by $D_{t}$ yields the desired result for any finite $t$:

$$ $\displaystyle\frac{N_{t}}{D_{t}}=\frac{\sum_{k=0}^{t}a^{k}|g_{k}|}{\sqrt{\sum_{k=0}^{t}b^{k}g_{k}^{2}}}\leq\sqrt{\frac{1}{1-a^{2}/b}}$ (A.65) $$

∎

###### Lemma A.4 (Finite Geometric Series Ratio Bounded by Infinite Sum) .

###### Proof.

### A.6 Proof of Lemma A.5

###### Lemma A.5 (Bound on the Quantized Momentum Error Ratio) .

Let $(g_{k})_{k=0}^{t}$ be a sequence of scalars. Let the weights be $A_{k}=\beta_{1}^{k}((1+q_{M})^{k}-1)$ and $B_{k}=(\beta_{2}(1-q_{V}))^{k}$.
If the condition $\beta_{1}^{2}(1+q_{M})^{2}<\beta_{2}(1-q_{V})$ holds, then the ratio of the weighted sum is bounded by:

$$ $\frac{\sum_{k=0}^{t}A_{k}|g_{k}|}{\sqrt{\sum_{k=0}^{t}B_{k}g_{k}^{2}}}\leq q_{M}\cdot\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}$ $$

where $r^{\prime}=\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}$.

###### Proof.

Following the proof of Lemma [A.4](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem4), we apply the Cauchy-Schwarz inequality to get:

$$ $\displaystyle\left(\sum_{k=0}^{t}A_{k}|g_{k}|\right)^{2}\leq\left(\sum_{k=0}^{t}\frac{A_{k}^{2}}{B_{k}}\right)\cdot\left(\sum_{k=0}^{t}B_{k}g_{k}^{2}\right).$ (A.66) $$

This implies that the ratio is bounded by the square root of the first term on the right-hand side. We now focus on bounding the term $\sum_{k=0}^{t}\frac{A_{k}^{2}}{B_{k}}$. First, we express the ratio $\frac{A_{k}^{2}}{B_{k}}$ as:

$$ $\displaystyle\frac{A_{k}^{2}}{B_{k}}$ $\displaystyle=\frac{(\beta_{1}^{k}((1+q_{M})^{k}-1))^{2}}{(\beta_{2}(1-q_{V}))^{k}}$ $\displaystyle=\left(\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}\right)^{k}((1+q_{M})^{k}-1)^{2}.$ (A.67) $$

To bound the term $((1+q_{M})^{k}-1)^{2}$, we first establish an inequality for $(1+q_{M})^{k}-1$ using the Mean Value Theorem. Let $f(x)=x^{k}$. For $q_{M}>0$, by the Mean Value Theorem, there exists a $c\in(1,1+q_{M})$ such that:

$$ $\displaystyle\frac{f(1+q_{M})-f(1)}{(1+q_{M})-1}=f^{\prime}(c)\implies(1+q_{M})^{k}-1=q_{M}\cdot(kc^{k-1}).$ (A.68) $$

Since $c<1+q_{M}$, and for $k\geq 1$, we have $c^{k-1}\leq(1+q_{M})^{k-1}$. This leads to the inequality:

$$ $\displaystyle(1+q_{M})^{k}-1\leq k\cdot q_{M}\cdot(1+q_{M})^{k-1}.$ (A.69) $$

Squaring both sides of ([A.69](https://arxiv.org/html/2510.21314v1#A1.E69)) gives:

$$ $\displaystyle((1+q_{M})^{k}-1)^{2}$ $\displaystyle\leq k^{2}q_{M}^{2}(1+q_{M})^{2(k-1)}$ $\displaystyle=\frac{k^{2}q_{M}^{2}}{(1+q_{M})^{2}}(1+q_{M})^{2k}.$ (A.70) $$

Substituting this back into ([A.67](https://arxiv.org/html/2510.21314v1#A1.E67)), and using the definition $r^{\prime}=\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}$, we get:

$$ $\displaystyle\frac{A_{k}^{2}}{B_{k}}$ $\displaystyle\leq\left(\frac{\beta_{1}^{2}}{\beta_{2}(1-q_{V})}\right)^{k}\frac{k^{2}q_{M}^{2}}{(1+q_{M})^{2}}(1+q_{M})^{2k}$ $\displaystyle=\frac{q_{M}^{2}}{(1+q_{M})^{2}}k^{2}\left(\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}\right)^{k}$ $\displaystyle=\frac{q_{M}^{2}}{(1+q_{M})^{2}}k^{2}(r^{\prime})^{k}.$ (A.71) $$

Now we sum this term. The condition $r^{\prime}<1$ ensures the convergence of the infinite series. We first derive the closed-form expression for $\sum_{k=0}^{\infty}k^{2}x^{k}$ for $|x|<1$. We start with the geometric series:

$$ $\displaystyle\sum_{k=0}^{\infty}x^{k}=\frac{1}{1-x}.$ (A.72) $$

Differentiating with respect to $x$ and multiplying by $x$ gives:

$$ $\displaystyle\sum_{k=0}^{\infty}kx^{k}=x\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{x}{(1-x)^{2}}.$ (A.73) $$

Differentiating one more time and multiplying by $x$ yields:

$$ $\displaystyle\sum_{k=0}^{\infty}k^{2}x^{k}=x\frac{d}{dx}\left(\frac{x}{(1-x)^{2}}\right)=x\frac{1(1-x)^{2}-x(2(1-x)(-1))}{(1-x)^{4}}=\frac{x(1+x)}{(1-x)^{3}}.$ (A.74) $$

Using this result with $x=r^{\prime}$, we can bound the sum $\sum_{k=0}^{t}\frac{A_{k}^{2}}{B_{k}}$ by extending it to an infinite series:

$$ $\displaystyle\sum_{k=0}^{t}\frac{A_{k}^{2}}{B_{k}}$ $\displaystyle\leq\sum_{k=0}^{\infty}\frac{A_{k}^{2}}{B_{k}}$ $\displaystyle\leq\sum_{k=0}^{\infty}\frac{q_{M}^{2}}{(1+q_{M})^{2}}k^{2}(r^{\prime})^{k}$ $\displaystyle=\frac{q_{M}^{2}}{(1+q_{M})^{2}}\sum_{k=0}^{\infty}k^{2}(r^{\prime})^{k}$ $\displaystyle=\frac{q_{M}^{2}}{(1+q_{M})^{2}}\frac{r^{\prime}(1+r^{\prime})}{(1-r^{\prime})^{3}}.$ (A.75) $$

Finally, taking the square root of ([A.75](https://arxiv.org/html/2510.21314v1#A1.E75)) and substituting it back into the result from the Cauchy-Schwarz inequality ([A.66](https://arxiv.org/html/2510.21314v1#A1.E66)) gives the desired bound:

$$ $\displaystyle\frac{\sum_{k=0}^{t}A_{k}|g_{k}|}{\sqrt{\sum_{k=0}^{t}B_{k}g_{k}^{2}}}\leq\sqrt{\sum_{k=0}^{t}\frac{A_{k}^{2}}{B_{k}}}\leq\sqrt{\frac{q_{M}^{2}}{(1+q_{M})^{2}}\frac{r^{\prime}(1+r^{\prime})}{(1-r^{\prime})^{3}}}=q_{M}\cdot\frac{\sqrt{r^{\prime}(1+r^{\prime})}}{(1+q_{M})(1-r^{\prime})^{3/2}}.$ (A.76) $$

∎

###### Lemma A.5 (Bound on the Quantized Momentum Error Ratio) .

###### Proof.

### A.7 Proof of Lemma A.6

###### Lemma A.6 (Bound on the Quantized Gradient Estimator) .

Let the stochastic gradient be bounded in infinity norm almost surely by $\|\nabla f_{t}(\mathbf{w};\gamma)\|_{\infty}\leq R-\sqrt{\epsilon}$ for any parameters $\mathbf{w}$. Let the gradient quantization operator satisfy the relative error model $|Q(z)-z|\leq q_{G}|z|$ for any scalar $z$. The quantized gradient estimator $\hat{\mathbf{g}_{t}}$ is defined component-wise for $i\in[d]$ as:

$$ $\displaystyle\hat{g}_{t,i}=\frac{1}{B}\sum_{j=1}^{B}[\nabla^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})]_{i},$ (A.77) $$

where we use $\nabla^{Q}f(\cdot)$ as shorthand for $Q(\nabla f(\cdot))$ and $[\cdot]_{i}$ to denote the i-th component. Then, the infinity norm of the estimator is bounded almost surely:

$$ $\displaystyle\|\hat{\mathbf{g}_{t}}\|_{\infty}\leq(1+q_{G})(R-\sqrt{\epsilon}).$ (A.78) $$

For notational simplicity in subsequent proofs, we will use the slightly looser bound $\|\hat{\mathbf{g}_{t}}\|_{\infty}\leq(1+q_{G})R$.

###### Proof.

We first bound the infinity norm of a single quantized gradient vector $\nabla^{Q}f(\cdot)$. For any component $i\in[d]$, we have:

$$ $\displaystyle\left|\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right|$ $\displaystyle=\left|\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})+\left(\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})-\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right)\right|$ $\displaystyle\leq\left|\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right|+\left|\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})-\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right|$ $\displaystyle\leq\left|\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right|+q_{G}\left|\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right|$ $\displaystyle=(1+q_{G})\left|\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\right|.$ (A.79) $$

Since this holds for any component, it also holds for the component with the maximum absolute value. Therefore, by taking the maximum over $i\in[d]$, we can bound the infinity norm:

$$ $\displaystyle\|\nabla^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\|_{\infty}$ $\displaystyle\leq(1+q_{G})\|\nabla f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\|_{\infty}$ $\displaystyle\leq(1+q_{G})(R-\sqrt{\epsilon}).$ (A.80) $$

Finally, we apply the triangle inequality to the full estimator $\hat{\mathbf{g}_{t}}$, which is the average over $B$ such vectors:

$$ $\displaystyle\|\hat{\mathbf{g}_{t}}\|_{\infty}$ $\displaystyle=\|\frac{1}{B}\sum_{j=1}^{B}\nabla^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\|_{\infty}$ $\displaystyle\leq\frac{1}{B}\sum_{j=1}^{B}\|\nabla^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma_{t,j})\|_{\infty}$ $\displaystyle\leq\frac{1}{B}\sum_{j=1}^{B}(1+q_{G})(R-\sqrt{\epsilon})$ $\displaystyle=(1+q_{G})(R-\sqrt{\epsilon}).$ (A.81) $$

This concludes the proof.
∎

###### Lemma A.6 (Bound on the Quantized Gradient Estimator) .

###### Proof.

### A.8 Proof of Lemma A.7

###### Lemma A.7 (Bound on the Expected Gradient Error with Biased Quantization) .

Under the assumptions that the infinity norm of stochastic gradient is up bounded (Assumption [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2)), the objective $F$ is L-smooth (Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3)), and the quantization relative error model holds (Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1)), the magnitude of the conditional expectation of the total error term $\delta_{t,i}$ is bounded by:

$$ $|\mathbb{E}_{t-1}\left[\delta_{t,i}\right]|\leq q_{G}R+Lq_{W}\|\mathbf{w}_{t-1}\|_{2}.$ $$

###### Proof.

We start from the decomposition of the conditional expectation of $\delta_{t,i}$, which we derived previously:

$$ $\displaystyle\mathbb{E}_{t-1}\left[\delta_{t,i}\right]$ $\displaystyle=\mathbb{E}_{\gamma}\left[\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma)-\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma)\right]+\mathbb{E}_{\gamma}\left[\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma)-\nabla_{i}f(\mathbf{w}_{t-1};\gamma)\right]$ $\displaystyle=\underbrace{\mathbb{E}_{\gamma}\left[\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma)-\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma)\right]}_{\text{Term I: Gradient Quantization Bias}}+\underbrace{\left(\nabla_{i}F(\mathbf{w}_{t-1}^{Q})-\nabla_{i}F(\mathbf{w}_{t-1})\right)}_{\text{Term II: Weight Quantization Bias}}$ (A.82) $$

Using the triangle inequality, we can bound the magnitude as:

$$ $\displaystyle|\mathbb{E}_{t-1}\left[\delta_{t,i}\right]|\leq|\text{Term I}|+|\text{Term II}|.$ (A.83) $$

We bound each term separately.

Bounding Term I:
This term is the expected bias from the (potentially biased) gradient quantization. We first apply Jensen’s inequality for absolute values, i.e., $|\mathbb{E}[X]|\leq\mathbb{E}[|X|]$:

$$ $\displaystyle|\text{Term I}|$ $\displaystyle=\left|\mathbb{E}_{\gamma}\left[\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma)-\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma)\right]\right|$ $\displaystyle\leq\mathbb{E}_{\gamma}\left[\left|\nabla_{i}^{Q}f(\mathbf{w}_{t-1}^{Q};\gamma)-\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma)\right|\right].$ (A.84) $$

By the relative error model for gradient quantization (Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1) with factor $q_{G}$):

$$ $\displaystyle|\text{Term I}|\leq\mathbb{E}_{\gamma}\left[q_{G}\left|\nabla_{i}f(\mathbf{w}_{t-1}^{Q};\gamma)\right|\right]\leq q_{G}R.$ (A.85) $$

Bounding Term II:
This term represents the bias from weight quantization. Using the L-smoothness of $F$ (Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3)) and the relative error for weights (Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1)):

$$ $\displaystyle|\text{Term II}|=|\nabla_{i}F(\mathbf{w}_{t-1}^{Q})-\nabla_{i}F(\mathbf{w}_{t-1})|\leq\|\nabla F(\mathbf{w}_{t-1}^{Q})-\nabla F(\mathbf{w}_{t-1})\|_{2}\leq Lq_{W}\|\mathbf{w}_{t-1}\|_{2}.$ (A.86) $$

Combining the Bounds:
Summing the bounds for Term I and Term II, we arrive at the final result:

$$ $\displaystyle|\mathbb{E}_{t-1}\left[\delta_{t,i}\right]|\leq|\text{Term I}|+|\text{Term II}|\leq q_{G}R+Lq_{W}\|\mathbf{w}_{t-1}\|_{2}.$ (A.87) $$

∎

###### Lemma A.7 (Bound on the Expected Gradient Error with Biased Quantization) .

###### Proof.

### A.9 Proof of Lemma A.8 (Bound on Term D)

###### Lemma A.8 (Bound on Term D) .

The term D, which captures the error from gradient drift as defined in ([A.20](https://arxiv.org/html/2510.21314v1#A1.E20)), is bounded by:

$$ $\displaystyle|D|\leq\frac{\eta_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4(1+q_{G})R}\left(\sum_{l=1}^{t-1}\|\mathbf{u}_{t-l}\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}\right)+\frac{(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}.$ (A.88) $$

###### Proof.

We start with the definition of Term D:

$$ $D=\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\left(\mathcal{G}_{t,i}-\mathcal{G}_{t-k,i}\right)\frac{g_{t-k,i}+\delta_{t-k,i}}{\sqrt{\epsilon+v^{\prime}_{t,i}}}$ $$

To tackle this, we employ the weighted Young’s inequality, which states that for any $\lambda>0$,

$$ $xy\leq\frac{\lambda}{2}x^{2}+\frac{1}{2\lambda}y^{2}$ (A.89) $$

We apply this inequality to each product within the summation for Term D, setting

$$ $x=|{\mathcal{G}_{t,i}-\mathcal{G}_{t-k,i}}|,\quad y=\frac{|{g_{t-k,i}+\delta_{t-k,i}}|}{\sqrt{\epsilon+v^{\prime}_{t,i}}},\quad\text{and}\quad\lambda=\frac{\sqrt{1-\beta_{1}}}{2(1+q_{G})R\sqrt{k+1}}.$ $$

This application gives us an initial bound on the magnitude of D:

$$ $\displaystyle|D|$ $\displaystyle\leq\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\left(\frac{\sqrt{1-\beta_{1}}}{4(1+q_{G})R\sqrt{k+1}}\left(\mathcal{G}_{t,i}-\mathcal{G}_{t-k,i}\right)^{2}+\frac{(1+q_{G})R\sqrt{k+1}}{\sqrt{1-\beta_{1}}}\frac{(g_{t-k,i}+\delta_{t-k,i})^{2}}{\epsilon+v^{\prime}_{t,i}}\right).$ (A.90) $$

To simplify this expression further, we must establish bounds for two of its key components.

First, we can find a lower bound for the denominator term. For any coordinate $i\in[d]$, the recursive definition of $v^{\prime}_{t,i}$ implies that $\epsilon+v^{\prime}_{t,i}\geq\epsilon+\beta_{2}^{k}v^{\prime}_{t-k,i}\geq\beta_{2}^{k}(\epsilon+v^{\prime}_{t-k,i})$. This allows us to bound the fraction as:

$$ $\frac{(g_{t-k,i}+\delta_{t-k,i})^{2}}{\epsilon+v^{\prime}_{t,i}}\leq\frac{1}{\beta_{2}^{k}}U_{t-k,i}^{2}.$ (A.91) $$

Second, we bound the squared gradient difference using the L-smoothness of the objective function $F$.

$$ $\displaystyle\|\mathcal{G}_{t}-\mathcal{G}_{t-k}\|_{2}^{2}$ $\displaystyle\leq L^{2}\|\mathbf{w}_{t-1}-\mathbf{w}_{t-k-1}\|_{2}^{2}=L^{2}\left\|\sum_{l=1}^{k}\eta_{t-l}\mathbf{u}_{t-l}\right\|_{2}^{2}$ $\displaystyle\leq\eta_{t}^{2}L^{2}k\sum_{l=1}^{k}\|\mathbf{u}_{t-l}\|^{2}_{2}.$ (A.92) $$

The final step above follows from Jensen’s inequality and the fact that the step size schedule $\eta_{t}$ is non-decreasing.

With these two intermediate results, ([A.91](https://arxiv.org/html/2510.21314v1#A1.E91)) and ([A.92](https://arxiv.org/html/2510.21314v1#A1.E92)), we can return to our main inequality ([A.90](https://arxiv.org/html/2510.21314v1#A1.E90)). Substituting these bounds yields:

$$ $\displaystyle|D|$ $\displaystyle\leq\left(\sum_{k=0}^{t-1}\frac{\eta_{t}^{2}L^{2}\sqrt{1-\beta_{1}}\beta_{1}^{k}}{4(1+q_{G})R\sqrt{k+1}}\left(k\sum_{l=1}^{k}\|\mathbf{u}_{t-l}\|^{2}_{2}\right)\right)+\left(\sum_{k=0}^{t-1}\frac{(1+q_{G})R\beta_{1}^{k}\sqrt{k+1}}{\sqrt{1-\beta_{1}}\beta_{2}^{k}}\|\mathbf{U}_{t-k}\|_{2}^{2}\right)$ $\displaystyle\leq\frac{\eta_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4(1+q_{G})R}\left(\sum_{k=0}^{t-1}\beta_{1}^{k}\sqrt{k}\sum_{l=1}^{k}\|\mathbf{u}_{t-l}\|^{2}_{2}\right)+\frac{(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}.$ $$

Finally, by rearranging the order of summation in the first term, we arrive at our desired bound:

$$ $\displaystyle|D|\leq\frac{\eta_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4(1+q_{G})R}\left(\sum_{l=1}^{t-1}\|\mathbf{u}_{t-l}\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}\right)+\frac{(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\|\mathbf{U}_{t-k}\|_{2}^{2}.$ (A.93) $$

∎

###### Lemma A.8 (Bound on Term D) .

###### Proof.

### A.10 Proof of Lemma A.9 (Lower Bound on Term C)

###### Lemma A.9 (Lower Bound on the Expectation of Term C) .

The expectation of term C, defined in ([A.20](https://arxiv.org/html/2510.21314v1#A1.E20)), is lower-bounded by:

$$ $\displaystyle\mathbb{E}\left[C\right]$ $\displaystyle\geq\frac{1}{2}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]\right)-\frac{2(1+q_{G})R}{\sqrt{1-\beta_{1}}}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\mathbb{E}\left[\|\mathbf{U}_{t-k}\|_{2}^{2}\right]\right)$ $\displaystyle\quad-d\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}.$ (A.94) $$

where $M_{t-k}=\frac{q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{t-k-1}\|_{2}}{\sqrt{\epsilon}}$.

###### Proof.

We study the main term of the summation in C, i.e. for $i\in[d]$ and $k<t$:

$$ $\displaystyle\mathbb{E}\left[\mathcal{G}_{t-k,i}\frac{g_{t-k,i}+\delta_{t-k,i}}{\sqrt{\epsilon+v_{t,i}}}\right]=\mathbb{E}\left[\nabla_{i}F(\mathbf{w}_{t-k-1})\frac{\nabla_{i}f_{t-k}(\mathbf{w}_{t-k-1})+\delta_{t-k,i}}{\sqrt{\epsilon+v_{t,i}}}\right].$ (A.95) $$

We will further drop indices in the rest of the proof, noting $\mathcal{G}=\mathcal{G}_{t-k,i}$,
$g=g_{t-k,i}$, $\delta=\delta_{t-k,i}$,$\tilde{v}=\tilde{v}_{t,k+1,i}$ and $v=v^{\prime}_{t,i}$. Finally, let us note

$$ $s^{2}=\sum_{j=t-k}^{t}\beta_{2}^{t-j}(g_{j,i}+\delta_{j,i})^{2}\qquad\text{and}\qquad r^{2}=\mathbb{E}_{t-k-1}\left[s^{2}\right].$ (A.96) $$

In particular we have $\tilde{v}-v=r^{2}-s^{2}$. With our new notations, we can rewrite ([A.95](https://arxiv.org/html/2510.21314v1#A1.E95)) as

$$ $\displaystyle\mathbb{E}\left[\mathcal{G}\frac{g+\delta}{\sqrt{\epsilon+v}}\right]$ $\displaystyle=\mathbb{E}\left[\mathcal{G}\frac{g+\delta}{\sqrt{\epsilon+\tilde{v}}}+\mathcal{G}(g+\delta)\left(\frac{1}{\sqrt{\epsilon+v}}-\frac{1}{\sqrt{\epsilon+\tilde{v}}}\right)\right]$ $\displaystyle=\mathbb{E}\left[\mathbb{E}_{t-k-1}\left[\mathcal{G}\frac{g+\delta}{\sqrt{\epsilon+\tilde{v}}}\right]+\mathcal{G}(g+\delta)\frac{r^{2}-s^{2}}{\sqrt{\epsilon+v}\sqrt{\epsilon+\tilde{v}}(\sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}})}\right]$ $\displaystyle=\mathbb{E}\left[\frac{\mathcal{G}^{2}}{\sqrt{\epsilon+\tilde{v}}}\right]+\mathbb{E}\left[\frac{\mathcal{G}\mathbb{E}_{t-k-1}\left[\delta\right]}{\sqrt{\epsilon+\tilde{v}}}\right]+\mathbb{E}\left[\underbrace{\mathcal{G}(g+\delta)\frac{r^{2}-s^{2}}{\sqrt{\epsilon+v}\sqrt{\epsilon+\tilde{v}}(\sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}})}}_{E}\right]$ $\displaystyle\geq\mathbb{E}\left[\frac{\mathcal{G}^{2}}{\sqrt{\epsilon+\tilde{v}}}\right]-\frac{q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{t-k-1}\|_{2}}{\sqrt{\epsilon}}+\mathbb{E}\left[E\right].$ (A.97) $$

The inequality uses Lemma [A.7](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem7) and the bound for $\|\nabla F(\cdot)\|_{\infty}$. We denote $\frac{q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{t-k-1}\|_{2}}{\sqrt{\epsilon}}\triangleq M_{t-k}$.

Then we focus on $E$:

$$ $\displaystyle|E|$ $\displaystyle\leq\underbrace{|\mathcal{G}(g+\delta)|\frac{r^{2}}{\sqrt{\epsilon+v}(\epsilon+\tilde{v})}}_{\kappa}+\underbrace{|\mathcal{G}(g+\delta)|\frac{s^{2}}{(\epsilon+v)\sqrt{\epsilon+\tilde{v}}}}_{\rho},$ $$

due to the fact that $\sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}}\geq\max(\sqrt{\epsilon+v},\sqrt{\epsilon+\tilde{v}})$ and
$|r^{2}-s^{2}|\leq r^{2}+s^{2}$.

Applying Young’s inequality to $\kappa$ with

$$ $\lambda=\frac{\sqrt{1-\beta_{1}}\sqrt{\epsilon+\tilde{v}}}{2},\;x=\frac{|\mathcal{G}|}{\sqrt{\epsilon+\tilde{v}}},\;y=\frac{|g+\delta|r^{2}}{\sqrt{\epsilon+\tilde{v}}\sqrt{\epsilon+v}},$ $$

we obtain

$$ $\displaystyle\kappa\leq\frac{\mathcal{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{1}{\sqrt{1-\beta_{1}}}\frac{(g+\delta)^{2}r^{4}}{(\epsilon+\tilde{v})^{3/2}(\epsilon+v)}.$ $$

Given that $\epsilon+\tilde{v}\geq r^{2}$ and taking the conditional expectation, we can simplify as

$$ $\displaystyle\mathbb{E}_{t-k-1}\left[\kappa\right]\leq\frac{\mathcal{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{1}{\sqrt{1-\beta_{1}}}\frac{r^{2}}{\sqrt{\epsilon+\tilde{v}}}\mathbb{E}_{t-k-1}\left[\frac{(g+\delta)^{2}}{\epsilon+v}\right].$ (A.98) $$

Now turning to $\rho$, we use Young’s inequality with

$$ $\lambda=\frac{\sqrt{1-\beta_{1}}\sqrt{\epsilon+\tilde{v}}}{2r^{2}},\;x=\frac{|\mathcal{G}s|}{\sqrt{\epsilon+\tilde{v}}},\;y=\frac{|s(g+\delta)|}{\epsilon+v},$ $$

we obtain

$$ $\displaystyle\rho\leq\frac{\mathcal{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}\frac{s^{2}}{r^{2}}+\frac{1}{\sqrt{1-\beta_{1}}}\frac{r^{2}}{\sqrt{\epsilon+\tilde{v}}}\frac{(g+\delta)^{2}s^{2}}{(\epsilon+v)^{2}}.$ (A.99) $$

Given that $\epsilon+v\geq s^{2}$, and $\mathbb{E}_{t-k-1}\left[\frac{s^{2}}{r^{2}}\right]=1$, we obtain after taking the conditional expectation,

$$ $\displaystyle\mathbb{E}_{t-k-1}\left[\rho\right]\leq\frac{\mathcal{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{1}{\sqrt{1-\beta_{1}}}\frac{r^{2}}{\sqrt{\epsilon+\tilde{v}}}\mathbb{E}_{t-k-1}\left[\frac{(g+\delta)^{2}}{\epsilon+v}\right].$ (A.100) $$

Notice that in ([A.99](https://arxiv.org/html/2510.21314v1#A1.E99)), we possibly divide by zero. It suffice to notice that if $r^{2}=0$ then $s^{2}=0$ a.s. so that $\rho=0$ and ([A.100](https://arxiv.org/html/2510.21314v1#A1.E100)) is still verified.
Summing ([A.98](https://arxiv.org/html/2510.21314v1#A1.E98)) and ([A.100](https://arxiv.org/html/2510.21314v1#A1.E100)), we get

$$ $\displaystyle\mathbb{E}_{t-k-1}\left[|E|\right]\leq\frac{\mathcal{G}^{2}}{2\sqrt{\epsilon+\tilde{v}}}+\frac{2}{\sqrt{1-\beta_{1}}}\frac{r^{2}}{\sqrt{\epsilon+\tilde{v}}}\mathbb{E}_{t-k-1}\left[\frac{(g+\delta)^{2}}{\epsilon+v}\right].$ (A.101) $$

Given that $r\leq\sqrt{\epsilon+\tilde{v}}$ by definition of $\tilde{v}$, and that $r\leq\sqrt{k+1}(1+q_{G})R$, reintroducing the indices we had dropped

$$ $\displaystyle\mathbb{E}_{t-k-1}\left[|E|\right]\leq\frac{\mathcal{G}_{t-k,i}^{2}}{2\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}+\frac{2(1+q_{G})R}{\sqrt{1-\beta_{1}}}\sqrt{k+1}\mathbb{E}_{t-k-1}\left[\frac{(g_{t-k,i}+\delta_{t-k,i})^{2}}{\epsilon+v^{\prime}_{t,i}}\right].$ (A.102) $$

Taking the complete expectation and using that by definition $\epsilon+v^{\prime}_{t,i}\geq\epsilon+\beta_{2}^{k}v^{\prime}_{t-k,i}\geq\beta_{2}^{k}(\epsilon+v^{\prime}_{t-k,i})$ we get

$$ $\displaystyle\mathbb{E}\left[|E|\right]\leq\frac{1}{2}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]+\frac{2(1+q_{G})R}{\sqrt{1-\beta_{1}}\beta_{2}^{k}}\sqrt{k+1}\mathbb{E}\left[\frac{(g_{t-k,i}+\delta_{t-k,i})^{2}}{\epsilon+v^{\prime}_{t-k,i}}\right].$ (A.103) $$

Injecting ([A.103](https://arxiv.org/html/2510.21314v1#A1.E103)) into ([A.97](https://arxiv.org/html/2510.21314v1#A1.E97)) gives us

$$ $\displaystyle\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\mathcal{G}_{t-k,i}\frac{g_{t-k,i}+\delta_{t-k,i}}{\sqrt{\epsilon+v_{t,i}}}\right]$ $\displaystyle\geq\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\left(\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]-\mathbb{E}\left[|E|\right]-M_{t-k}\right)$ (A.104) $\displaystyle\geq\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\left(\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]-\left(\frac{1}{2}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k,i}}}\right]+\frac{2(1+q_{G})R\sqrt{k+1}}{\sqrt{1-\beta_{1}}\beta_{2}^{k}}\mathbb{E}\left[\frac{(g_{t-k,i}+\delta_{t-k,i})^{2}}{\epsilon+v^{\prime}_{t-k,i}}\right]+M_{t-k}\right)\right)$ $\displaystyle\geq\frac{1}{2}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\frac{\mathcal{G}_{t-k,i}^{2}}{\sqrt{\epsilon+\tilde{v}_{t,k+1,i}}}\right]\right)-\frac{2(1+q_{G})R}{\sqrt{1-\beta_{1}}}\left(\sum_{i\in[d]}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\mathbb{E}\left[\|\mathbf{U}_{t-k}\|_{2}^{2}\right]\right)-d\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}.$ (A.105) $$

This is the desired lower bound for $\mathbb{E}\left[C\right]$.
∎

###### Lemma A.9 (Lower Bound on the Expectation of Term C) .

###### Proof.

### A.11 Proof of Lemma A.10

###### Lemma A.10 (Lemma A.2 in Défossez et al. [ 2022 ] ) .

Assume we have $0<\beta_{1}<\beta_{2}\leq 1$ and a sequence of real numbers $(a_{n})_{n\in\mathbb{N}^{*}}$. We define for all $n\in\mathbb{N}^{*}$:

$$ $b_{n}=\sum_{j=1}^{n}\beta_{2}^{n-j}a_{j}^{2}\quad\text{and}\quad c_{n}=\sum_{j=1}^{n}\beta_{1}^{n-j}a_{j}.$ $$

Then for any $\epsilon>0$, we have the following inequality:

$$ $\sum_{j=1}^{n}\frac{c_{j}^{2}}{\epsilon+b_{j}}\leq\frac{1}{(1-\beta_{1})(1-\beta_{1}/\beta_{2})}\left(\ln\left(1+\frac{b_{n}}{\epsilon}\right)-n\ln(\beta_{2})\right).$ (A.106) $$

###### Proof.

First, we use Jensen’s inequality on $c_{j}^{2}$, noting that $\sum_{l=1}^{j}\beta_{1}^{j-l}=\frac{1-\beta_{1}^{j}}{1-\beta_{1}}\leq\frac{1}{1-\beta_{1}}$, to get:

$$ $\displaystyle c_{j}^{2}=\left(\sum_{l=1}^{j}\beta_{1}^{j-l}a_{l}\right)^{2}\leq\left(\sum_{l=1}^{j}\beta_{1}^{j-l}\right)\left(\sum_{l=1}^{j}\beta_{1}^{j-l}a_{l}^{2}\right)\leq\frac{1}{1-\beta_{1}}\sum_{l=1}^{j}\beta_{1}^{j-l}a_{l}^{2}.$ $$

Dividing by $\epsilon+b_{j}$ and using the fact that for $l\leq j$, $b_{j}\geq\beta_{2}^{j-l}b_{l}$, which implies $\epsilon+b_{j}\geq\beta_{2}^{j-l}(\epsilon+b_{l})$, we obtain:

$$ $\displaystyle\frac{c_{j}^{2}}{\epsilon+b_{j}}\leq\frac{1}{1-\beta_{1}}\sum_{l=1}^{j}\beta_{1}^{j-l}\frac{a_{l}^{2}}{\epsilon+b_{j}}\leq\frac{1}{1-\beta_{1}}\sum_{l=1}^{j}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{j-l}\frac{a_{l}^{2}}{\epsilon+b_{l}}.$ (A.107) $$

Now, we sum over $j\in[n]$ and swap the order of summation:

$$ $\displaystyle\sum_{j=1}^{n}\frac{c_{j}^{2}}{\epsilon+b_{j}}$ $\displaystyle\leq\frac{1}{1-\beta_{1}}\sum_{j=1}^{n}\sum_{l=1}^{j}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{j-l}\frac{a_{l}^{2}}{\epsilon+b_{l}}=\frac{1}{1-\beta_{1}}\sum_{l=1}^{n}\frac{a_{l}^{2}}{\epsilon+b_{l}}\sum_{j=l}^{n}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{j-l}$ $\displaystyle\leq\frac{1}{(1-\beta_{1})(1-\beta_{1}/\beta_{2})}\sum_{l=1}^{n}\frac{a_{l}^{2}}{\epsilon+b_{l}},$ (A.108) $$

where the last step uses the sum of a geometric series, since $\beta_{1}/\beta_{2}<1$.

The next step is to bound the final sum. Let’s denote $x_{l}=a_{l}^{2}$. The sum is $\sum_{l=1}^{n}\frac{x_{l}}{\epsilon+b_{l}}$, where $b_{l}=\sum_{k=1}^{l}\beta_{2}^{l-k}x_{k}$. Note that $b_{l}-x_{l}=\beta_{2}b_{l-1}$ (with $b_{0}=0$). Using the inequality $\frac{x}{y}\leq\ln(y)-\ln(y-x)$ for $0<x<y$, we have:

$$ $\displaystyle\frac{x_{l}}{\epsilon+b_{l}}$ $\displaystyle\leq\ln(\epsilon+b_{l})-\ln(\epsilon+b_{l}-x_{l})$ $\displaystyle=\ln(\epsilon+b_{l})-\ln(\epsilon+\beta_{2}b_{l-1})$ $\displaystyle=\ln\left(\frac{\epsilon+b_{l}}{\epsilon+b_{l-1}}\right)+\ln\left(\frac{\epsilon+b_{l-1}}{\epsilon+\beta_{2}b_{l-1}}\right).$ $$

Summing from $l=1$ to $n$, the first term forms a telescoping series equal to $\ln(\epsilon+b_{n})-\ln(\epsilon)=\ln(1+b_{n}/\epsilon)$. For the second term, since $\beta_{2}\leq 1$ and $b_{l-1}\geq 0$, we have $\frac{\epsilon+\beta_{2}b_{l-1}}{\epsilon+b_{l-1}}\geq\beta_{2}$, which implies $\ln\left(\frac{\epsilon+b_{l-1}}{\epsilon+\beta_{2}b_{l-1}}\right)\leq-\ln(\beta_{2})$. Thus, summing over $l$ gives:

$$ $\sum_{l=1}^{n}\frac{a_{l}^{2}}{\epsilon+b_{l}}\leq\ln\left(1+\frac{b_{n}}{\epsilon}\right)-n\ln(\beta_{2}).$ (A.109) $$

This inequality is a useful result in itself, corresponding to the special case where $c_{j}^{2}$ is replaced by $a_{j}^{2}$ (or equivalently $\beta_{1}\to 0$ and $a_{j}$ is replaced by $a_{j}^{2}$).

Finally, substituting the bound from ([A.109](https://arxiv.org/html/2510.21314v1#A1.E109)) into ([A.108](https://arxiv.org/html/2510.21314v1#A1.E108)) yields the desired result.
∎

###### Lemma A.10 (Lemma A.2 in Défossez et al. [ 2022 ] ) .

###### Proof.

### A.12 Proof of Lemma A.11

###### Lemma A.11 (Lemma A.3 in Défossez et al. [ 2022 ] ) .

For any scalar $\rho\in(0,1)$ and any integer $K\in\mathbb{N}$, the following bound holds for the finite geometric sum:

$$ $\sum_{k=0}^{K-1}\rho^{k}\sqrt{k+1}\leq\frac{2}{(1-\rho)^{3/2}}.$ (A.110) $$

###### Proof.

Let the sum be denoted by $S_{K}=\sum_{k=0}^{K-1}\rho^{k}\sqrt{k+1}$. We analyze the term $(1-\rho)S_{K}$:

$$ $\displaystyle(1-\rho)S_{K}$ $\displaystyle=\sum_{k=0}^{K-1}\rho^{k}\sqrt{k+1}-\sum_{j=1}^{K}\rho^{j}\sqrt{j}$ $\displaystyle=1+\sum_{k=1}^{K-1}\rho^{k}(\sqrt{k+1}-\sqrt{k})-\rho^{K}\sqrt{K}.$ $$

By the concavity of the square root function, $\sqrt{k+1}-\sqrt{k}\leq\frac{1}{2\sqrt{k}}$. This implies:

$$ $\displaystyle(1-\rho)S_{K}$ $\displaystyle\leq 1+\sum_{k=1}^{K-1}\frac{\rho^{k}}{2\sqrt{k}}\leq 1+\int_{0}^{\infty}\frac{\rho^{t}}{2\sqrt{t}}\mathrm{d}t.$ $$

The integral is a standard Gaussian integral form which evaluates to $\frac{\sqrt{\pi}}{2\sqrt{-\ln(\rho)}}$. Using the inequality $-\ln(\rho)\geq 1-\rho$, we have:

$$ $\displaystyle(1-\rho)S_{K}\leq 1+\frac{\sqrt{\pi}}{2\sqrt{1-\rho}}\leq\frac{2}{\sqrt{1-\rho}}.$ $$

Dividing by $(1-\rho)$ yields the desired result.
∎

###### Lemma A.11 (Lemma A.3 in Défossez et al. [ 2022 ] ) .

###### Proof.

### A.13 Proof of Lemma A.12

###### Lemma A.12 (Lemma A.4 in Défossez et al. [ 2022 ] ) .

For any scalar $\rho\in(0,1)$ and any integer $K\in\mathbb{N}$, the following bound holds:

$$ $\sum_{k=0}^{K-1}\rho^{k}\sqrt{k}(k+1)\leq\frac{4\rho}{(1-\rho)^{5/2}}.$ (A.111) $$

###### Proof.

Let the sum be denoted by $S_{K}=\sum_{k=0}^{K-1}\rho^{k}\sqrt{k}(k+1)$. We proceed by analyzing $(1-\rho)S_{K}$:

$$ $\displaystyle(1-\rho)S_{K}$ $\displaystyle=\sum_{k=1}^{K-1}\rho^{k}\left[\sqrt{k}(k+1)-k\sqrt{k-1}\right]-\rho^{K}k\sqrt{K-1}$ $\displaystyle\leq\sum_{k=1}^{K-1}\rho^{k}(2\sqrt{k}),$ $$

where the inequality holds because $\sqrt{k}(k+1)-k\sqrt{k-1}\leq 2\sqrt{k}$. Re-indexing the sum gives:

$$ $\displaystyle(1-\rho)S_{K}$ $\displaystyle\leq 2\rho\sum_{k=1}^{K-1}\rho^{k-1}\sqrt{k}=2\rho\sum_{j=0}^{K-2}\rho^{j}\sqrt{j+1}.$ $$

Applying the result from Lemma [A.11](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem11) to the final sum, we get:

$$ $\displaystyle(1-\rho)S_{K}\leq 2\rho\left(\frac{2}{(1-\rho)^{3/2}}\right)=\frac{4\rho}{(1-\rho)^{3/2}}.$ $$

Dividing both sides by $(1-\rho)$ completes the proof.
∎

###### Lemma A.12 (Lemma A.4 in Défossez et al. [ 2022 ] ) .

###### Proof.

### A.14 Proof of Lemma A.13

###### Lemma A.13 (Upper bound of $\sum_{t=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]$ ) .

Under the condition that $\beta_{1}(1+q_{M})<\beta_{2}(1-q_{V})$, the expected sum of squared updates over $T$ iterations is bounded by:

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]$ $\displaystyle\leq\frac{d}{(1-\beta_{1}(1+q_{M}))(1-\frac{\beta_{1}(1+q_{M})}{\beta_{2}(1-q_{V})})}$ $\displaystyle\quad\times\left(\ln\left(1+\frac{((1+q_{G})R)^{2}}{\epsilon(1-\beta_{2}(1-q_{V}))}\right)-T\ln(\beta_{2}(1-q_{V}))\right).$ (A.112) $$

###### Proof.

The proof proceeds by first expanding the term of interest, applying bounds on the moment estimates derived from their recurrence relations, and then leveraging Lemma [A.10](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem10) to bound the resulting sum.

We begin by expanding the definition of $\|\mathbf{u}_{t}\|_{2}^{2}$, separating the sum over the dimension $d$, and taking the expectation:

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]=\sum_{t=1}^{T}\mathbb{E}\left[\sum_{i\in[d]}\frac{m^{2}_{t,i}}{\epsilon+v_{t,i}}\right]=\sum_{i\in[d]}\sum_{t=1}^{T}\mathbb{E}\left[\frac{m^{2}_{t,i}}{\epsilon+v_{t,i}}\right].$ (A.113) $$

For each coordinate $i$, we bound the numerator $m_{t,i}^{2}$ from above and the denominator $\epsilon+v_{t,i}$ from below. By unrolling the recurrence for $m_{t,i}$ and applying the triangle inequality along with the relative error model, we get an upper bound on its magnitude:

$$ $\displaystyle|m_{t,i}|\leq\sum_{k=1}^{t}\beta_{1}^{t-k}(1+q_{M})^{t-k}|\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i}|.$ (A.114) $$

For the denominator, Lemma [A.2](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem2) provides a lower bound for $v_{t,i}$:

$$ $\displaystyle v_{t,i}\geq\sum_{k=1}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2}.$ (A.115) $$

Substituting these into the sum gives the inequality:

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right]\leq\sum_{i\in[d]}\sum_{t=1}^{T}\mathbb{E}\left[\frac{\left(\sum_{k=1}^{t}\beta_{1}^{t-k}(1+q_{M})^{t-k}|\hat{g}_{k,i}|\right)^{2}}{\epsilon+\sum_{k=1}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}\hat{g}_{k,i}^{2}}\right],$ (A.116) $$

where for brevity we denote $\hat{g}_{k,i}=\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i}$.

The inner sum over $t$ for each coordinate $i$ in ([A.116](https://arxiv.org/html/2510.21314v1#A1.E116)) perfectly matches the form required by Lemma [A.10](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem10). To apply it, we make the following substitutions into the lemma’s notation:

- •
Let the sequence $(a_{j})_{j\in\mathbb{N}^{*}}$ be $a_{k}=|\hat{g}_{k,i}|$.
- •
Let the effective decay factors be $\beta^{\prime}_{1}=\beta_{1}(1+q_{M})$ and $\beta^{\prime}_{2}=\beta_{2}(1-q_{V})$. The lemma’s condition $\beta^{\prime}_{1}<\beta^{\prime}_{2}$ is satisfied by our assumption.

With these substitutions, the numerator term becomes $\left(\sum_{k=1}^{t}(\beta^{\prime}_{1})^{t-k}a_{k}\right)^{2}=c_{t}^{2}$ and the sum in the denominator becomes $\sum_{k=1}^{t}(\beta^{\prime}_{2})^{t-k}a_{k}^{2}=b_{t}$. Applying Lemma [A.10](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem10) to the sum over $t$ for a fixed $i$ yields:

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\frac{c_{t}^{2}}{\epsilon+b_{t}}\right]\leq\frac{1}{(1-\beta^{\prime}_{1})(1-\beta^{\prime}_{1}/\beta^{\prime}_{2})}\left(\ln\left(1+\frac{b_{T}}{\epsilon}\right)-T\ln(\beta^{\prime}_{2})\right).$ (A.117) $$

The final step is to find an upper bound for $b_{T}$. By definition:

$$ $\displaystyle b_{T}=\sum_{k=1}^{T}(\beta^{\prime}_{2})^{T-k}a_{k}^{2}=\sum_{k=1}^{T}(\beta_{2}(1-q_{V}))^{T-k}\hat{g}_{k,i}^{2}.$ (A.118) $$

From Lemma [A.6](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem6), we have a uniform bound on the quantized gradient estimator, $|\hat{g}_{k,i}|\leq(1+q_{G})R$. Therefore:

$$ $\displaystyle b_{T}$ $\displaystyle\leq\sum_{k=1}^{T}(\beta_{2}(1-q_{V}))^{T-k}((1+q_{G})R)^{2}$ $\displaystyle=((1+q_{G})R)^{2}\sum_{j=0}^{T-1}(\beta_{2}(1-q_{V}))^{j}$ $\displaystyle\leq((1+q_{G})R)^{2}\frac{1}{1-\beta_{2}(1-q_{V})}.$ (A.119) $$

Substituting the bound for $b_{T}$ back into ([A.117](https://arxiv.org/html/2510.21314v1#A1.E117)), and re-inserting the definitions of $\beta^{\prime}_{1}$ and $\beta^{\prime}_{2}$, we obtain the bound for a single coordinate $i$. As this bound is identical for all $d$ coordinates, we multiply by $d$ to get the final result stated in ([A.112](https://arxiv.org/html/2510.21314v1#A1.E112)). This completes the proof.
∎

###### Lemma A.13 (Upper bound of ∑ t = 1 T 𝔼 ​ [ ‖ 𝐮 t ‖ 2 2 ] \sum_{t=1}^{T}\mathbb{E}\left[\|\mathbf{u}_{t}\|^{2}_{2}\right] ) .

###### Proof.

### A.15 Proof of Lemma A.14 (Bound on Term M)

###### Lemma A.14 (Bound on Term M) .

The term M, representing the accumulated quantization bias from ([A.26](https://arxiv.org/html/2510.21314v1#A1.E26)), is bounded by:

$$ $\displaystyle M\leq\frac{\eta_{T}dT}{\sqrt{\epsilon}(1-\beta_{1})}\left(q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{0}\|_{2}\right)+\frac{\eta_{T}^{2}dLq_{W}URT^{2}}{2\sqrt{\epsilon}(1-\beta_{1})},$ (A.120) $$

where $U=\sqrt{\frac{d}{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}$.

###### Proof.

First, we establish a uniform bound on the update norm $\|\mathbf{u}_{t}\|_{2}$ using Lemma [A.4](https://arxiv.org/html/2510.21314v1#A1.Thmtheorem4):

$$ $\displaystyle\|\mathbf{u}_{t}\|_{2}$ $\displaystyle=\sqrt{\sum_{i\in[d]}\frac{m_{t,i}^{2}}{\epsilon+v_{t,i}}}$ $\displaystyle\leq\sqrt{\sum_{i\in[d]}\frac{(\sum_{k=0}^{t}\beta_{1}^{t-k}(1+q_{M})^{t-k}|\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i}|)^{2}}{(\sum_{k=0}^{t}\beta_{2}^{t-k}(1-q_{V})^{t-k}(\nabla_{i}f_{k}(\mathbf{w}_{k-1})+\delta_{k,i})^{2})}}$ $\displaystyle\leq\sqrt{\frac{d}{1-\frac{\beta_{1}^{2}(1+q_{M})^{2}}{\beta_{2}(1-q_{V})}}}\triangleq U$ (A.121) $$

Now, let’s recall the definition of $M$:

$$ $M=\eta_{T}d\sum_{t=1}^{T}\mathbb{E}\left[\sum_{k=0}^{t-1}\beta_{1}^{k}M_{t-k}\right],\quad\text{where}\quad M_{t-k}=\frac{q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{t-k-1}\|_{2}}{\sqrt{\epsilon}}.$ $$

We can split $M$ into two components: a constant part $M_{\text{const}}$ and a weight-dependent part $M_{\text{weights}}$.

$$ $\displaystyle M_{\text{const}}$ $\displaystyle=\frac{\eta_{T}dq_{G}R^{2}}{\sqrt{\epsilon}}\sum_{t=1}^{T}\sum_{k=0}^{t-1}\beta_{1}^{k}$ $\displaystyle M_{\text{weights}}$ $\displaystyle=\frac{\eta_{T}dLq_{W}R}{\sqrt{\epsilon}}\sum_{t=1}^{T}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\|\mathbf{w}_{t-k-1}\|_{2}\right]$ $$

Bounding $M_{\text{const}}$ is straightforward. The inner sum is a geometric series bounded by $\frac{1}{1-\beta_{1}}$, so the double summation is bounded by $\frac{T}{1-\beta_{1}}$.

$$ $M_{\text{const}}\leq\frac{\eta_{T}dq_{G}R^{2}T}{\sqrt{\epsilon}(1-\beta_{1})}.$ (A.122) $$

The main challenge is to bound $M_{\text{weights}}$. To do this, we first need a bound on the expected weight norm $\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]$. From the update rule $\mathbf{w}_{j}=\mathbf{w}_{j-1}-\eta_{j}\mathbf{u}_{j}$, we can unroll the recursion:

$$ $\mathbf{w}_{j}=\mathbf{w}_{0}-\sum_{l=1}^{j}\eta_{l}\mathbf{u}_{l}.$ $$

Applying the triangle inequality and taking the expectation, we get:

$$ $\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]\leq\|\mathbf{w}_{0}\|_{2}+\mathbb{E}\left[\sum_{l=1}^{j}\eta_{l}\|\mathbf{u}_{l}\|_{2}\right].$ $$

Using the uniform bound $\|\mathbf{u}_{l}\|_{2}\leq U$, we have:

$$ $\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]\leq\|\mathbf{w}_{0}\|_{2}+U\sum_{l=1}^{j}\eta_{l}\leq\|\mathbf{w}_{0}\|_{2}+Uj\eta_{T}.$ $$

Now we substitute this bound back into the expression for $M_{\text{weights}}$. We first swap the order of summation. Let $j=t-k-1$. For a fixed $j\in\{0,\dots,T-1\}$, the term $\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]$ appears when $k=t-j-1$. This is valid for $t$ from $j+1$ to $T$.

$$ $\displaystyle\sum_{t=1}^{T}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\|\mathbf{w}_{t-k-1}\|_{2}\right]$ $\displaystyle=\sum_{j=0}^{T-1}\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]\sum_{t=j+1}^{T}\beta_{1}^{t-j-1}$ $\displaystyle=\sum_{j=0}^{T-1}\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]\sum_{m=0}^{T-j-1}\beta_{1}^{m}$ $\displaystyle\leq\frac{1}{1-\beta_{1}}\sum_{j=0}^{T-1}\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right].$ $$

Next, we substitute the linear bound:

$$ $\displaystyle\frac{1}{1-\beta_{1}}\sum_{j=0}^{T-1}\mathbb{E}\left[\|\mathbf{w}_{j}\|_{2}\right]$ $\displaystyle\leq\frac{1}{1-\beta_{1}}\sum_{j=0}^{T-1}\left(\|\mathbf{w}_{0}\|_{2}+j\cdot U\cdot\eta_{T}\right)$ $\displaystyle=\frac{1}{1-\beta_{1}}\left(T\|\mathbf{w}_{0}\|_{2}+U\eta_{T}\sum_{j=0}^{T-1}j\right).$ $$

The sum of the first $T-1$ integers is $\frac{(T-1)T}{2}<\frac{T^{2}}{2}$. This gives:

$$ $\leq\frac{1}{1-\beta_{1}}\left(T\|\mathbf{w}_{0}\|_{2}+\frac{T^{2}}{2}U\eta_{T}\right).$ $$

Finally, we assemble the complete bound for $M_{\text{weights}}$:

$$ $M_{\text{weights}}\leq\frac{\eta_{T}dLq_{W}R}{\sqrt{\epsilon}(1-\beta_{1})}\left(T\|\mathbf{w}_{0}\|_{2}+\frac{T^{2}}{2}U\eta_{T}\right).$ $$

Combining $M_{\text{const}}$ with $M_{\text{weights}}$, we get the final bound for $M$.

$$ $\displaystyle M$ $\displaystyle\leq\frac{\eta_{T}dT}{\sqrt{\epsilon}(1-\beta_{1})}\left(q_{G}R^{2}+Lq_{W}R\|\mathbf{w}_{0}\|_{2}\right)+\frac{\eta_{T}^{2}dLq_{W}URT^{2}}{2\sqrt{\epsilon}(1-\beta_{1})}$ $$

∎

###### Lemma A.14 (Bound on Term M) .

###### Proof.

## Appendix B Proof of Theorem 4.6

### B.1 Preliminaries

The momentum of the quantized Muon (Algorithm [1](https://arxiv.org/html/2510.21314v1#alg1), [3](https://arxiv.org/html/2510.21314v1#alg3)) is defined as

$$ $\displaystyle\mathbf{M}_{t}=$ $\displaystyle\beta\mathbf{M}_{t-1}^{Q}+(1-\beta)\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{t}^{Q};\bm{\xi}_{t,i}),$ $\displaystyle\mathbf{M}_{0}=\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i}).$ (B.1) $$

We define the following auxiliary variables for analysis:

$$ $\displaystyle\mathbf{C}_{t}=$ $\displaystyle\beta\mathbf{C}_{t-1}+(1-\beta)\nabla F(\mathbf{W}_{t}),$ $\displaystyle\mathbf{C}_{0}=\nabla F(\mathbf{W}_{0})$ (B.2) $\displaystyle\mathbf{X}_{t}=$ $\displaystyle\beta\mathbf{X}_{t-1}+(1-\beta)\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{t};\bm{\xi}_{t,i}),$ $\displaystyle\mathbf{X}_{0}=\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{0};\bm{\xi}_{0,i})$ (B.3) $\displaystyle\mathbf{Y}_{t}=$ $\displaystyle\beta\mathbf{Y}_{t-1}+(1-\beta)\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{t};\bm{\xi}_{t,i}),$ $\displaystyle\mathbf{Y}_{0}=\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0};\bm{\xi}_{0,i})$ (B.4) $\displaystyle\mathbf{Z}_{t}=$ $\displaystyle\beta\mathbf{Z}_{t-1}+(1-\beta)\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{t}^{Q};\bm{\xi}_{t,i}),$ $\displaystyle\mathbf{Z}_{0}=\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i}).$ (B.5) $$

We also define the following relative quantization errors $q_{G},q_{W},q_{M}$ according to Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1) and Lemma [B.2](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem2), i.e., for any $t\in\{0,1,\ldots,T-1\}$ and $i\in\{1,2,\ldots,B\}$,

$$ $\displaystyle\|\nabla^{Q}f(\mathbf{W}_{t};\bm{\xi}_{t,i})-\nabla f(\mathbf{W}_{t};\bm{\xi}_{t,i})\|_{F}$ $\displaystyle\leq q_{G}\|\nabla f(\mathbf{W}_{t};\bm{\xi}_{t,i})\|_{F},$ $\displaystyle\|\nabla^{Q}F(\mathbf{W}_{t})-\nabla F(\mathbf{W}_{t})\|_{F}$ $\displaystyle\leq q_{G}\|\nabla F(\mathbf{W}_{t})\|_{F},$ $\displaystyle\|\nabla^{Q}f(\mathbf{W}_{t}^{Q};\bm{\xi}_{t,i})-\nabla f(\mathbf{W}_{t}^{Q};\bm{\xi}_{t,i})\|_{F}$ $\displaystyle\leq q_{G}\|\nabla f(\mathbf{W}_{t}^{Q};\bm{\xi}_{t,i})\|_{F},$ $\displaystyle\|\nabla^{Q}F(\mathbf{W}_{t}^{Q})-\nabla F(\mathbf{W}_{t}^{Q})\|_{F}$ $\displaystyle\leq q_{G}\|\nabla F(\mathbf{W}_{t}^{Q})\|_{F},$ $\displaystyle\|\mathbf{W}_{t}^{Q}-\mathbf{W}_{t}\|_{F}$ $\displaystyle\leq q_{W}\|\mathbf{W}_{t}\|_{F},$ $\displaystyle\|\mathbf{M}_{t}^{Q}-\mathbf{M}_{t}\|_{F}$ $\displaystyle\leq q_{M}\|\mathbf{M}_{t}\|_{F}.$ (B.6) $$

### B.2 Proof of Theorem 4.6

###### Proof.

Set $\eta_{t}=\eta$, denote $r=\min\{m,n\}$, and according to the $L$-smoothness of $F(\cdot)$, we have

$$ $\displaystyle\mathbb{E}[F(\mathbf{W}_{t})-F(\mathbf{W}_{t+1})]$ $\displaystyle\geq$ $\displaystyle\mathbb{E}[\langle\nabla F(\mathbf{W}_{t}),\mathbf{W}_{t}-\mathbf{W}_{t+1}\rangle-\frac{L}{2}\|\mathbf{W}_{t}-\mathbf{W}_{t+1}\|_{F}^{2}]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\eta\langle\nabla F(\mathbf{W}_{t}),\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\rangle-\frac{L}{2}\eta^{2}\|\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\|_{F}^{2}]$ $\displaystyle\geq$ $\displaystyle\mathbb{E}[\eta\langle\nabla F(\mathbf{W}_{t}),\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\rangle]-\frac{L}{2}\eta^{2}r$ $\displaystyle=$ $\displaystyle\mathbb{E}[\eta\langle\mathbf{M}_{t},\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\rangle+\eta\langle\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t},\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\rangle]-\frac{L}{2}\eta^{2}r$ $\displaystyle\geq$ $\displaystyle\mathbb{E}[\eta\|\mathbf{M}_{t}\|_{*}-\eta\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}\cdot\|\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\|_{F}]-\frac{L}{2}\eta^{2}r$ $\displaystyle\geq$ $\displaystyle\mathbb{E}[\eta\|\nabla F(\mathbf{W}_{t})\|_{*}-\eta\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{*}-\eta\sqrt{r}\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]-\frac{L}{2}\eta^{2}r$ $\displaystyle\geq$ $\displaystyle\mathbb{E}[\eta\|\nabla F(\mathbf{W}_{t})\|_{*}-2\eta\sqrt{r}\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]-\frac{L}{2}\eta^{2}r.$ (B.7) $$

The second inequality is due to $\|\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\|_{F}^{2}=\mathop{\mathrm{Tr}}(\mathbf{V}_{t}\mathbf{U}_{t}^{\top}\mathbf{U}_{t}\mathbf{V}_{t}^{\top})\leq r=\min\{m,n\}$. The third inequality is due to $\mathbf{M}_{t}=\mathbf{U}_{t}\mathbf{S}_{t}\mathbf{V}_{t}^{\top}$ and Cauchy-Schwarz inequality. The last inequality we used the fact that $\|\mathbf{A}\|_{*}\leq\sqrt{r}\|\mathbf{A}\|_{F}$ for any $\mathbf{A}\in\mathbb{R}^{m\times n}$.

Summing Eq. ([B.2](https://arxiv.org/html/2510.21314v1#A2.Ex6)) over $t=0,1,\ldots,T-1$, we get

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})\|_{*}]$ $\displaystyle\leq$ $\displaystyle\frac{\mathbb{E}[F(\mathbf{W}_{0})-F^{(}\mathbf{W}_{T})]}{T\eta}+\frac{2\sqrt{r}}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]+\frac{\eta Lr}{2}.$ (B.8) $$

Next, we focus on term $\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]$. With auxiliary variables defined in Eq. ([B.2](https://arxiv.org/html/2510.21314v1#A2.E2))-([B.5](https://arxiv.org/html/2510.21314v1#A2.E5)), we have

$$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{C}_{t}\|_{F}+\|\mathbf{C}_{t}-\mathbf{X}_{t}\|_{F}+\|\mathbf{X}_{t}-\mathbf{Y}_{t}\|_{F}+\|\mathbf{Y}_{t}-\mathbf{Z}_{t}\|_{F}+\|\mathbf{Z}_{t}-\mathbf{M}_{t}\|_{F}].$ $$

By Lemmas [B.3](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem3), [B.4](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem4), [B.5](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem5), [B.6](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem6), and [B.7](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem7), we have

$$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{C}_{t}\|_{F}+\|\mathbf{C}_{t}-\mathbf{X}_{t}\|_{F}+\|\mathbf{X}_{t}-\mathbf{Y}_{t}\|_{F}+\|\mathbf{Y}_{t}-\mathbf{Z}_{t}\|_{F}+\|\mathbf{Z}_{t}-\mathbf{M}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\frac{\beta L\eta\sqrt{r}}{1-\beta}+\beta^{t}\frac{3\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{3\sigma}{\sqrt{B}}+3q_{G}(\sigma+G)+3q_{G}T\eta\sqrt{r}L+q_{W}(1+q_{G})DL+$ $\displaystyle q_{W}(1+q_{G})T\eta\sqrt{r}L+\frac{q_{M}\beta}{1-\beta(1+q_{M})}\bigg(\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+\bigg.$ $\displaystyle\bigg.q_{W}(1+q_{G})DL+(1+q_{W})(1+q_{G})T\eta\sqrt{r}L\bigg).$ $$

Summing over $t=0,1,\ldots,T-1$, we get

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\frac{\beta L\eta\sqrt{r}}{1-\beta}+\frac{3\sigma}{T(1-\beta)\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{3\sigma}{\sqrt{B}}+3q_{G}(\sigma+G)+3q_{G}T\eta\sqrt{r}L+q_{W}(1+q_{G})DL+$ $\displaystyle q_{W}(1+q_{G})T\eta\sqrt{r}L+\frac{q_{M}\beta}{1-\beta(1+q_{M})}\bigg(\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+\bigg.$ $\displaystyle\bigg.q_{W}(1+q_{G})DL+(1+q_{W})(1+q_{G})T\eta\sqrt{r}L\bigg).$ (B.9) $$

Substitute ([B.2](https://arxiv.org/html/2510.21314v1#A2.Ex21)) into ([B.2](https://arxiv.org/html/2510.21314v1#A2.Ex13)), with Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1), we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})\|_{*}]$ $\displaystyle\leq$ $\displaystyle\frac{\mathbb{E}[F(\mathbf{W}_{0})-F(\mathbf{W}_{T})]}{\eta T}+\frac{L\eta r}{2}+\frac{2\sqrt{r}}{T}\sum_{t=0}^{T-1}\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{M}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\frac{\mathbb{E}[F(\mathbf{W}_{0})-F(\mathbf{W}_{T})]}{\eta T}+\frac{L\eta r}{2}+\frac{2\beta L\eta r}{1-\beta}+\frac{6\sigma\sqrt{r}}{T(1-\beta)\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{6\sigma\sqrt{r}}{\sqrt{B}}+$ $\displaystyle 6q_{G}\sqrt{r}(\sigma+G)+6q_{G}T\eta rL+2q_{W}(1+q_{G})DL\sqrt{r}+2q_{W}(1+q_{G})T\eta rL+$ $\displaystyle\frac{2q_{M}\beta\sqrt{r}}{1-\beta(1+q_{M})}\bigg(\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+\bigg.$ $\displaystyle\bigg.q_{W}(1+q_{G})DL+(1+q_{W})(1+q_{G})T\eta\sqrt{r}L\bigg)$ $\displaystyle\leq$ $\displaystyle\frac{\mathbb{E}[F(\mathbf{W}_{0})-F(\mathbf{W}_{T})]}{\eta T}+\frac{L\eta r}{2}+\frac{2\beta L\eta r}{1-\beta}+\frac{6\sigma\sqrt{r}}{T(1-\beta)\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{6\sigma\sqrt{r}}{\sqrt{B}}+$ $\displaystyle\Theta\Bigg(q_{G}+q_{W}+q_{G}T\eta+q_{W}T\eta+\frac{q_{M}\beta}{1-\beta(1+q_{M})}\bigg(1+\sqrt{1-\beta}+q_{G}+q_{W}+T\eta\bigg)\Bigg).$ $$

Let $F(\mathbf{W}_{0})-F^{*}\leq\Delta$, where $\Delta>0$ is a constant. By setting $B=1$, $1-\beta=\Theta(T^{-1/2})$, $\eta=\Theta((1-\beta)^{1/2}T^{-1/2})$, we have $T\eta=\Theta(T^{1/4})$. Then we have

$$ $\displaystyle\frac{\mathbb{E}[F(\mathbf{W}_{0})-F(\mathbf{W}_{T})]}{\eta T}+\frac{L\eta r}{2}+\frac{2\beta L\eta r}{1-\beta}+\frac{6\sigma\sqrt{r}}{T(1-\beta)\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{6\sigma\sqrt{r}}{\sqrt{B}}=\mathcal{O}(\frac{1}{T^{1/4}}).$ $$

Moreover, with condition $\beta(1+q_{M})<1$, suppose $1-\beta=C_{\beta}T^{-1/2}$, $C_{\beta}>0$ is a constant. Choose $q_{M}=C_{M}T^{-1/2}$, where $C_{M}<C_{\beta},C_{M}>0$ is a constant, then we have

$$ $\displaystyle\beta(1+q_{M})=(1-C_{\beta}T^{-1/2})(1+C_{M}T^{-1/2})=1-(C_{\beta}-C_{M})T^{-1/2}-C_{\beta}C_{M}T^{-1}<1.$ $$

Thus, by setting $q_{G}=\mathcal{O}(T^{-1/2})$, $q_{W}=\mathcal{O}(T^{-1/2})$, $q_{M}=\mathcal{O}(T^{-1/2})$, we have

$$ $\displaystyle q_{G}+q_{W}+q_{G}T\eta+q_{W}T\eta+\frac{q_{M}\beta}{1-\beta(1+q_{M})}\bigg(1+\sqrt{1-\beta}+q_{G}+q_{W}+T\eta\bigg)$ $\displaystyle=$ $\displaystyle\mathcal{O}(T^{-1/2}+T^{-1/2}T^{1/4}+T^{-1/2}(1+T^{-1/4}+T^{-1/2}+T^{1/4}))$ $\displaystyle=$ $\displaystyle\mathcal{O}(T^{-1/4}),$ $$

where we used the fact $\frac{q_{M}\beta}{1-\beta(1+q_{M})}=\mathcal{O}(q_{M}\beta(1+\beta(1+q_{M})))=\mathcal{O}(T^{-1/2})$, and $\beta(1+q_{M})<1$.

Combining the above results, with the fact that $\|\mathbf{A}\|_{*}\geq\|\mathbf{A}\|_{F}$ for any matrix $\mathbf{A}$, we complete the proof.

∎

###### Proof.

### B.3 Proof of Lemma B.1

###### Lemma B.1 (Bound of $\|\mathbf{W}\|_{F}$ and $\|\nabla F(\mathbf{W})\|_{F}$ for Muon) .

Suppose Assumptions [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and [4.4](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem4) hold. The iterates of Muon satisfy that for any $t\geq 0$,

$$ $\displaystyle\|\mathbf{W}_{t}\|_{F}\leq D+t\eta\sqrt{r},\quad\|\nabla F(\mathbf{W}_{t})\|_{F}\leq G+t\eta\sqrt{r}L.$ $$

###### Proof of Lemma B.1 .

According to the update of Muon, we have

$$ $\displaystyle\|\mathbf{W}_{t}\|_{F}$ $\displaystyle=$ $\displaystyle\|\mathbf{W}_{t-1}-\eta\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\|_{F}$ $\displaystyle\leq$ $\displaystyle\|\mathbf{W}_{t-1}\|_{F}+\eta\|\mathbf{U}_{t}\mathbf{V}_{t}^{\top}\|_{F}$ $\displaystyle=$ $\displaystyle\|\mathbf{W}_{t-1}\|_{F}+\eta\sqrt{\mathop{\mathrm{Tr}}(\mathbf{V}_{t}\mathbf{U}_{t}^{\top}\mathbf{U}_{t}\mathbf{V}_{t}^{\top})}$ $\displaystyle\leq$ $\displaystyle\|\mathbf{W}_{t-1}\|_{F}+\eta\sqrt{r}$ $\displaystyle\leq$ $\displaystyle\|\mathbf{W}_{0}\|_{F}+t\eta\sqrt{r}$ $\displaystyle\leq$ $\displaystyle D+t\eta\sqrt{r}.$ $$

The third inequality is because $\mathbf{U}_{t}$ and $\mathbf{V}_{t}$ are orthogonal matrices, and the last inequality is due to Assumption [4.4](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem4).

$$ $\displaystyle\|\nabla F(\mathbf{W}_{t})\|_{F}$ $\displaystyle\leq$ $\displaystyle\|\nabla F(\mathbf{W}_{0})\|_{F}+\sum_{k=0}^{t-1}\|\nabla F(\mathbf{W}_{k+1})-\nabla F(\mathbf{W}_{k})\|_{F}$ $\displaystyle\leq$ $\displaystyle G+\sum_{k=0}^{t-1}L\|\mathbf{W}_{k+1}-\mathbf{W}_{k}\|_{F}$ $\displaystyle\leq$ $\displaystyle G+\sum_{k=0}^{t-1}L\eta\sqrt{r}$ $\displaystyle=$ $\displaystyle G+t\eta\sqrt{r}L.$ $$

The first inequality is due to the triangle inequality, the second inequality is due to Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3), and the last inequality is due to the update of Muon.
∎

###### Lemma B.1 (Bound of ‖ 𝐖 ‖ F \|\mathbf{W}\|_{F} and ‖ ∇ F ​ ( 𝐖 ) ‖ F \|\nabla F(\mathbf{W})\|_{F} for Muon) .

###### Proof of Lemma B.1 .

### B.4 Proof of Lemma B.2

###### Lemma B.2 .

Suppose Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1) holds. For any matrix $\mathbf{X}\in\mathbb{R}^{m\times n}$ and its quantized version $\mathbf{X}^{Q}$, we have

$$ $\displaystyle\|\mathbf{X}^{Q}-\mathbf{X}\|_{F}\leq q\|\mathbf{X}\|_{F}.$ $$

###### Proof of Lemma B.2 .

According to Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1), we have

$$ $\displaystyle\|\mathbf{X}^{Q}-\mathbf{X}\|_{F}^{2}=$ $\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n}|X_{ij}^{Q}-X_{ij}|^{2}$ $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n}q^{2}|X_{ij}|^{2}$ $\displaystyle=$ $\displaystyle q^{2}\|\mathbf{X}\|_{F}^{2}.$ $$

Taking the square root on both sides, we complete the proof.
∎

###### Lemma B.2 .

###### Proof of Lemma B.2 .

### B.5 Proof of Lemma B.3

###### Lemma B.3 .

Suppose Assumptions [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and [4.4](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem4) hold. For any $t\geq 0$, we have

$$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{C}_{t}\|_{F}]\leq\frac{\beta L\eta\sqrt{r}}{1-\beta}.$ $$

###### Proof of Lemma B.3 .

This proof is a standard technique for bounding the bias term of momentum. We have

$$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-\mathbf{C}_{t}\|_{F}]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\|\nabla F(\mathbf{W}_{t})-(\beta\mathbf{C}_{t-1}+(1-\beta)\nabla F(\mathbf{W}_{t}))\|_{F}]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\beta\|\nabla F(\mathbf{W}_{t})-\mathbf{C}_{t-1}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\nabla F(\mathbf{W}_{t-1})-\mathbf{C}_{t-1}\|_{F}+\beta\|\nabla F(\mathbf{W}_{t-1})-\nabla F(\mathbf{W}_{t})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\nabla F(\mathbf{W}_{t-1})-\mathbf{C}_{t-1}\|_{F}+\beta L\|\mathbf{W}_{t-1}-\mathbf{W}_{t}\|_{F}]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\beta\|\nabla F(\mathbf{W}_{t-1})-\mathbf{C}_{t-1}\|_{F}+\beta L\eta\|\mathbf{U}_{t-1}\mathbf{V}_{t-1}^{\top}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\nabla F(\mathbf{W}_{t-1})-\mathbf{C}_{t-1}\|_{F}+\beta L\eta\sqrt{r}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\|\nabla F(\mathbf{W}_{0})-\mathbf{C}_{0}\|_{F}+\sum_{i=1}^{t}\beta^{i}L\eta\sqrt{r}$ $\displaystyle\leq$ $\displaystyle\frac{\beta L\eta\sqrt{r}}{1-\beta}.$ $$

∎

###### Lemma B.3 .

###### Proof of Lemma B.3 .

### B.6 Proof of Lemma B.4

###### Lemma B.4 .

Suppose Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1) and [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2) hold. For any $t\geq 0$, we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{C}_{t}-\mathbf{X}_{t}\|_{F}]\leq\beta^{t}\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{\sigma}{\sqrt{B}}.$ $$

###### Proof of Lemma B.4 .

Expanding $\mathbf{C}_{t}$ and $\mathbf{X}_{t}$ by their definitions in ([B.2](https://arxiv.org/html/2510.21314v1#A2.E2)) and ([B.3](https://arxiv.org/html/2510.21314v1#A2.E3)), we have

$$ $\displaystyle\mathbf{C}_{t}=$ $\displaystyle\beta^{t}\mathbf{C}_{0}+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\nabla F(\mathbf{W}_{k}),$ $\displaystyle\mathbf{X}_{t}=$ $\displaystyle\beta^{t}\mathbf{X}_{0}+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i}).$ $$

Thus, we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{C}_{t}-\mathbf{X}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\|\beta^{t}(\mathbf{C}_{0}-\mathbf{X}_{0})\|_{F}]+\mathbb{E}[(1-\beta)\|\sum_{k=1}^{t}\beta^{t-k}(\nabla F(\mathbf{W}_{k})-\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i}))\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{C}_{0}-\mathbf{X}_{0}\|_{F}]+\sqrt{\mathbb{E}[(1-\beta)^{2}\|\sum_{k=1}^{t}\beta^{t-k}(\nabla F(\mathbf{W}_{k})-\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i}))\|_{F}^{2}]}$ $\displaystyle=$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{C}_{0}-\mathbf{X}_{0}\|_{F}]+\sqrt{\mathbb{E}[(1-\beta)^{2}\sum_{k=1}^{t}\beta^{2(t-k)}\frac{1}{B^{2}}\sum_{i=1}^{B}\|\nabla F(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k})\|_{F}^{2}]}$ $\displaystyle\leq$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{C}_{0}-\mathbf{X}_{0}\|_{F}]+\sqrt{(1-\beta)^{2}\sum_{k=1}^{t}\beta^{2(t-k)}\frac{\sigma^{2}}{B}}$ $\displaystyle\leq$ $\displaystyle\beta^{t}\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\frac{\sigma}{\sqrt{B}}.$ $$

The second inequality is due to Jensen’s inequality, the first equality is due to the independence of $\bm{\xi}_{k,i}$ for different $k$ or $i$, and the third inequality is due to Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1) and [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2).
∎

###### Lemma B.4 .

###### Proof of Lemma B.4 .

### B.7 Proof of Lemma B.5

###### Lemma B.5 .

Suppose Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1), [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2) and [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1) hold. For any $t\geq 0$, we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{X}_{t}-\mathbf{Y}_{t}\|_{F}]\leq q_{G}(\sigma+G+t\eta\sqrt{r}L).$ $$

###### Proof of Lemma B.5 .

By the definition of $\mathbf{X}_{t}$ and $\mathbf{Y}_{t}$ in ([B.3](https://arxiv.org/html/2510.21314v1#A2.E3)) and ([B.4](https://arxiv.org/html/2510.21314v1#A2.E4)), we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{X}_{t}-\mathbf{Y}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{X}_{t-1}-\mathbf{Y}_{t-1}\|_{F}]+(1-\beta)\frac{1}{B}\sum_{i=1}^{B}\mathbb{E}[\|\nabla f(\mathbf{W}_{t};\bm{\xi}_{t,i})-\nabla^{Q}f(\mathbf{W}_{t};\bm{\xi}_{t,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{X}_{t-1}-\mathbf{Y}_{t-1}\|_{F}]+(1-\beta)\frac{1}{B}\sum_{i=1}^{B}\mathbb{E}[q_{G}\|\nabla f(\mathbf{W}_{t};\bm{\xi}_{t,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{X}_{t-1}-\mathbf{Y}_{t-1}\|_{F}]+(1-\beta)\mathbb{E}[q_{G}(\sigma+\|\nabla F(\mathbf{W}_{t})\|_{F})]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{X}_{t-1}-\mathbf{Y}_{t-1}\|_{F}]+(1-\beta)q_{G}(\sigma+G+t\eta\sqrt{r}L)$ $\displaystyle\leq$ $\displaystyle\beta^{t}\|\mathbf{X}_{0}-\mathbf{Y}_{0}\|_{F}+(1-\beta)q_{G}(\sigma+G+t\eta\sqrt{r}L)\sum_{k=0}^{t-1}\beta^{k}$ $\displaystyle\leq$ $\displaystyle\beta^{t}q_{G}(\sigma+G)+(1-\beta^{t})q_{G}(\sigma+G+t\eta\sqrt{r}L)$ $\displaystyle\leq$ $\displaystyle q_{G}(\sigma+G)+(1-\beta^{t})q_{G}t\eta\sqrt{r}L$ $\displaystyle\leq$ $\displaystyle q_{G}(\sigma+G+t\eta\sqrt{r}L).$ $$

The second inequality is due to Assumption [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1), Lemma [B.2](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem2) and Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1). The third inequality is due to Assumption [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2). The fourth inequality is due to Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1).
∎

###### Lemma B.5 .

###### Proof of Lemma B.5 .

### B.8 Proof of Lemma B.6

###### Lemma B.6 .

Suppose Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1), [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2), [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1) hold. For any $t\geq 0$, we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{Y}_{t}-\mathbf{Z}_{t}\|_{F}]\leq$ $\displaystyle\beta^{t}\cdot\frac{2\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{2\sigma}{\sqrt{B}}+2q_{G}(\sigma+G)+2q_{G}t\eta\sqrt{r}L+$ $\displaystyle q_{W}(1+q_{G})DL+q_{W}(1+q_{G})t\eta\sqrt{r}L,$ $\displaystyle\mathbb{E}[\|\mathbf{Z}_{t}\|_{F}]\leq$ $\displaystyle\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+q_{W}(1+q_{G})DL+$ $\displaystyle(1+q_{W})(1+q_{G})t\eta\sqrt{r}L.$ $$

###### Proof of Lemma B.6 .

By the definition of $\mathbf{Y}_{t}$ and $\mathbf{Z}_{t}$ in ([B.4](https://arxiv.org/html/2510.21314v1#A2.E4)) and ([B.5](https://arxiv.org/html/2510.21314v1#A2.E5)), we have

$$ $\displaystyle\mathbf{Y}_{t}=$ $\displaystyle\beta^{t}\mathbf{Y}_{0}+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{k};\bm{\xi}_{k,i}),$ $\displaystyle\mathbf{Z}_{t}=$ $\displaystyle\beta^{t}\mathbf{Z}_{0}+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}).$ $$

Thus, by the triangle inequality, we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{Y}_{t}-\mathbf{Z}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta^{t}\|\mathbf{Y}_{0}-\mathbf{Z}_{0}\|_{F}]+(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla^{Q}f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}))\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta^{t}\|\mathbf{Y}_{0}-\mathbf{Z}_{0}\|_{F}]+\underbrace{(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})\|_{F}]}_{\text{\large A}}+$ $\displaystyle\underbrace{(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k}))\|_{F}]}_{\text{\large C}}+$ $\displaystyle\underbrace{(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\nabla F(\mathbf{W}_{k})-\nabla F(\mathbf{W}_{k}^{Q}))\|_{F}]}_{\text{\large H}}+$ $\displaystyle\underbrace{(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\nabla F(\mathbf{W}_{k}^{Q})-\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}))\|_{F}]}_{\text{\large I}}+$ $\displaystyle\underbrace{(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})-\nabla^{Q}f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}))\|_{F}]}_{\text{\large J}}.$ (B.10) $$

Next, we bound each term in ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex90)) one by one.

###### Lemma B.6 .

###### Proof of Lemma B.6 .

#### Bound on β t ​ 𝔼 ​ [ ‖ 𝐘 0 − 𝐙 0 ‖ F ] \beta^{t}\mathbb{E}[\|\mathbf{Y}_{0}-\mathbf{Z}_{0}\|_{F}] .

By the definitions of $\mathbf{Y}_{0}$ and $\mathbf{Z}_{0}$ in ([B.4](https://arxiv.org/html/2510.21314v1#A2.E4)) and ([B.5](https://arxiv.org/html/2510.21314v1#A2.E5)), we have

$$ $\displaystyle\mathbf{Y}_{0}=$ $\displaystyle\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0};\bm{\xi}_{0,i}),$ $\displaystyle\mathbf{Z}_{0}=$ $\displaystyle\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i}).$ $$

Thus, we have

$$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{Y}_{0}-\mathbf{Z}_{0}\|_{F}]$ $\displaystyle=$ $\displaystyle\beta^{t}\mathbb{E}[\|\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0};\bm{\xi}_{0,i})-\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\frac{1}{B}\sum_{i=1}^{B}\mathbb{E}[\|\nabla^{Q}f(\mathbf{W}_{0};\bm{\xi}_{0,i})-\nabla f(\mathbf{W}_{0};\bm{\xi}_{0,i})\|_{F}]+$ $\displaystyle\beta^{t}\mathbb{E}[\|\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{0};\bm{\xi}_{0,i})-\nabla F(\mathbf{W}_{0})\|_{F}]+$ $\displaystyle\beta^{t}\mathbb{E}[\|\nabla F(\mathbf{W}_{0})-\nabla F(\mathbf{W}_{0}^{Q})\|_{F}]+$ $\displaystyle\beta^{t}\mathbb{E}[\|\frac{1}{B}\sum_{i=1}^{B}\nabla F(\mathbf{W}_{0}^{Q})-\nabla f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i})\|_{F}]+$ $\displaystyle\beta^{t}\frac{1}{B}\sum_{i=1}^{B}\mathbb{E}[\|\nabla f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i})-\nabla^{Q}f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\frac{1}{B}\sum_{i=1}^{B}q_{G}\mathbb{E}[\|\nabla f(\mathbf{W}_{0};\bm{\xi}_{0,i})\|_{F}]+\beta^{t}\frac{\sigma}{\sqrt{B}}+\beta^{t}Lq_{W}\mathbb{E}[\|\mathbf{W}_{0}\|_{F}]+\beta^{t}\frac{\sigma}{\sqrt{B}}+$ $\displaystyle\beta^{t}\frac{1}{B}\sum_{i=1}^{B}q_{G}\mathbb{E}[\|\nabla f(\mathbf{W}_{0}^{Q};\bm{\xi}_{0,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+G)+\beta^{t}\frac{2\sigma}{\sqrt{B}}+\beta^{t}q_{W}DL+\beta^{t}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+q_{W}DL+G)$ $\displaystyle=$ $\displaystyle\beta^{t}(2q_{G}(\sigma+G)+q_{W}DL(1+q_{G})+\frac{2\sigma}{\sqrt{B}}).$ (B.11) $$

The first inequality is due to the triangle inequality. The second inequality we used Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1) for the first and last terms, Assumption [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1), [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2) and Jensen’s inequality for the second and fourth terms, and Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1) for the third term. The third inequality is due to Assumption [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2), [4.4](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem4) and Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1).

#### Bound on A .

$$ $\displaystyle A=$ $\displaystyle(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}\mathbb{E}[\|\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+\mathbb{E}[\|\nabla F(\mathbf{W}_{k})\|_{F}])$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+G+t\eta\sqrt{r}L)$ $\displaystyle=$ $\displaystyle(1-\beta^{t})q_{G}(\sigma+G+t\eta\sqrt{r}L).$ (B.12) $$

The first inequality is due to Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1) and the triangle inequality. The second inequality is due to Assumption [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2). The third inequality is due to Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1).

#### Bound on C .

Similar to Lemma [B.4](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem4), we have

$$ $\displaystyle C=$ $\displaystyle(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k}))\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sqrt{\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k}))\|_{F}^{2}]}$ $\displaystyle=$ $\displaystyle(1-\beta)\sqrt{\sum_{k=1}^{t}\beta^{2(t-k)}\frac{1}{B^{2}}\sum_{i=1}^{B}\mathbb{E}[\|\nabla f(\mathbf{W}_{k};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k})\|_{F}^{2}]}$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sqrt{\sum_{k=1}^{t}\beta^{2(t-k)}\frac{1}{B^{2}}\sum_{i=1}^{B}\sigma^{2}}$ $\displaystyle=$ $\displaystyle(1-\beta)\sqrt{\frac{1-\beta^{2t}}{1-\beta^{2}}\cdot\frac{\sigma^{2}}{B}}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}.$ (B.13) $$

#### Bound on H .

$$ $\displaystyle H=$ $\displaystyle(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\nabla F(\mathbf{W}_{k})-\nabla F(\mathbf{W}_{k}^{Q}))\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\mathbb{E}[\|\nabla F(\mathbf{W}_{k})-\nabla F(\mathbf{W}_{k}^{Q})\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}L\mathbb{E}[\|\mathbf{W}_{k}-\mathbf{W}_{k}^{Q}\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}Lq_{W}\mathbb{E}[\|\mathbf{W}_{k}\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}Lq_{W}(D+t\eta\sqrt{r})$ $\displaystyle\leq$ $\displaystyle(1-\beta^{t})q_{W}L(D+t\eta\sqrt{r}).$ (B.14) $$

The first inequality is due to the triangle inequality. The second inequality is due to Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3). The third inequality is due to Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1). The fourth inequality is due to Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1).

#### Bound on I .

Similar to Lemma [B.4](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem4), we have

$$ $\displaystyle I=$ $\displaystyle(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\nabla F(\mathbf{W}_{k}^{Q})-\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}))\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sqrt{\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\nabla F(\mathbf{W}_{k}^{Q})-\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}))\|_{F}^{2}]}$ $\displaystyle=$ $\displaystyle(1-\beta)\sqrt{\sum_{k=1}^{t}\beta^{2(t-k)}\frac{1}{B^{2}}\sum_{i=1}^{B}\mathbb{E}[\|\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k}^{Q})\|_{F}^{2}]}$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sqrt{\sum_{k=1}^{t}\beta^{2(t-k)}\frac{1}{B^{2}}\sum_{i=1}^{B}\sigma^{2}}$ $\displaystyle=$ $\displaystyle(1-\beta)\sqrt{\frac{1-\beta^{2t}}{1-\beta^{2}}\cdot\frac{\sigma^{2}}{B}}$ $\displaystyle\leq$ $\displaystyle\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}.$ (B.15) $$

#### Bound on J .

$$ $\displaystyle J=$ $\displaystyle(1-\beta)\mathbb{E}[\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})-\nabla^{Q}f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i}))\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}\mathbb{E}[\|\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+\mathbb{E}[\|\nabla F(\mathbf{W}_{k}^{Q})\|_{F}])$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+L\mathbb{E}[\|\mathbf{W}_{k}^{Q}-\mathbf{W}_{k}\|_{F}]+\mathbb{E}[\|\nabla F(\mathbf{W}_{k})\|_{F}])$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+Lq_{W}\mathbb{E}[\|\mathbf{W}_{k}\|_{F}]+\mathbb{E}[\|\nabla F(\mathbf{W}_{k})\|_{F}])$ $\displaystyle\leq$ $\displaystyle(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+Lq_{W}(D+t\eta\sqrt{r})+G+t\eta\sqrt{r}L)$ $\displaystyle\leq$ $\displaystyle(1-\beta^{t})q_{G}(\sigma+G+q_{W}DL+(1+q_{W})t\eta\sqrt{r}L).$ (B.16) $$

The first inequality is due to Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1) and the triangle inequality. The second inequality is due to Assumption [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2). The third inequality is due to Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and the triangle inequality. The fourth inequality is due to Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1). The fifth inequality is due to Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1).

#### Bound on 𝔼 ​ [ ‖ 𝐘 t − 𝐙 t ‖ F ] \mathbb{E}[\|\mathbf{Y}_{t}-\mathbf{Z}_{t}\|_{F}] .

Substituting ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex98)), ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex108)), ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex112)), ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex117)), ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex122)) and ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex127)) into ([B.8](https://arxiv.org/html/2510.21314v1#A2.Ex90)), we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{Y}_{t}-\mathbf{Z}_{t}\|_{F}]\leq$ $\displaystyle\beta^{t}\cdot\frac{2\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{2\sigma}{\sqrt{B}}+2q_{G}(\sigma+G)+(1-\beta^{t})2q_{G}t\eta\sqrt{r}L+$ $\displaystyle q_{W}(1+q_{G})DL+(1-\beta^{t})q_{W}(1+q_{G})t\eta\sqrt{r}L.$ $\displaystyle\leq$ $\displaystyle\beta^{t}\cdot\frac{2\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{2\sigma}{\sqrt{B}}+2q_{G}(\sigma+G)+2q_{G}t\eta\sqrt{r}L+$ $\displaystyle q_{W}(1+q_{G})DL+q_{W}(1+q_{G})t\eta\sqrt{r}L.$ $$

#### Bound on 𝔼 ​ [ ‖ 𝐙 t ‖ F ] \mathbb{E}[\|\mathbf{Z}_{t}\|_{F}] .

By the definition of $\mathbf{Z}_{t}$ in ([B.5](https://arxiv.org/html/2510.21314v1#A2.E5)), we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{Z}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta^{t}\|\mathbf{Z}_{0}\|_{F}]+\mathbb{E}[(1-\beta)\|\sum_{k=1}^{t}\beta^{t-k}\cdot\frac{1}{B}\sum_{i=1}^{B}\nabla^{Q}f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{Z}_{0}\|_{F}]+\mathbb{E}[(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\cdot\frac{1}{B}\sum_{i=1}^{B}\|\nabla^{Q}f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})-\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})\|_{F}]+$ $\displaystyle\mathbb{E}[(1-\beta)\|\sum_{k=1}^{t}\beta^{t-k}\cdot(\frac{1}{B}\sum_{i=1}^{B}\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})-\nabla F(\mathbf{W}_{k}^{Q}))\|_{F}]+$ $\displaystyle\mathbb{E}[(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\cdot(\|\nabla F(\mathbf{W}_{k}^{Q})-\nabla F(\mathbf{W}_{k})\|_{F}+\|\nabla F(\mathbf{W}_{k})\|_{F})]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{Z}_{0}\|_{F}]+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}\mathbb{E}[\|\nabla f(\mathbf{W}_{k}^{Q};\bm{\xi}_{k,i})\|_{F}]+$ $\displaystyle\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+(1-\beta)q_{W}L\sum_{k=1}^{t}\beta^{t-k}\mathbb{E}[\|\mathbf{W}_{k}\|_{F}]+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\mathbb{E}[\|\nabla F(\mathbf{W}_{k})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{Z}_{0}\|_{F}]+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\frac{1}{B}\sum_{i=1}^{B}q_{G}(\sigma+q_{W}L\mathbb{E}[\|\mathbf{W}_{k}\|_{F}]+\mathbb{E}[\|\nabla F(\mathbf{W}_{k})\|_{F}])+$ $\displaystyle\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+(1-\beta)q_{W}L\sum_{k=1}^{t}\beta^{t-k}\mathbb{E}[\|\mathbf{W}_{k}\|_{F}]+(1-\beta)\sum_{k=1}^{t}\beta^{t-k}\mathbb{E}[\|\nabla F(\mathbf{W}_{k})\|_{F}]$ $\displaystyle\leq$ $\displaystyle\beta^{t}\mathbb{E}[\|\mathbf{Z}_{0}\|_{F}]+(1-\beta^{t})q_{G}(\sigma+q_{W}L(D+t\eta\sqrt{r})+G+t\eta\sqrt{r}L)+$ $\displaystyle\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+(1-\beta^{t})q_{W}L(D+t\eta\sqrt{r})+(1-\beta^{t})(G+t\eta\sqrt{r}L)$ $\displaystyle\leq$ $\displaystyle\beta^{t}(q_{G}(\sigma+q_{W}DL+G)+\frac{\sigma}{\sqrt{B}}+q_{W}DL+G)+$ $\displaystyle(1-\beta^{t})q_{G}(\sigma+q_{W}L(D+t\eta\sqrt{r})+G+t\eta\sqrt{r}L)+$ $\displaystyle\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+(1-\beta^{t})q_{W}L(D+t\eta\sqrt{r})+(1-\beta^{t})(G+t\eta\sqrt{r}L)$ $\displaystyle\leq$ $\displaystyle\beta^{t}\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+q_{W}(1+q_{G})DL+$ $\displaystyle(1-\beta^{t})(1+q_{W})(1+q_{G})t\eta\sqrt{r}L$ $\displaystyle\leq$ $\displaystyle\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+q_{W}(1+q_{G})DL+(1+q_{W})(1+q_{G})t\eta\sqrt{r}L.$ $$

The first and second inequalities are due to the triangle inequality. The third inequality we used Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1) for the second term, Jensen’s inequality, Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1), [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2) for the third term, Assumption [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1) for the fourth term. The fourth inequality we used triangle inequality, Assumptions [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2), [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3), Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1). The fifth inequality is due to Lemma [B.1](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem1).

∎

### B.9 Proof of Lemma B.7

###### Lemma B.7 .

Suppose Assumptions [4.1](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem1), [4.2](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem2), [4.3](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem3) and [3.1](https://arxiv.org/html/2510.21314v1#S3.Thmtheorem1) hold. For any $t\geq 0$, if $\beta(1+q_{M})<1$, we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{Z}_{t}-\mathbf{M}_{t}\|_{F}]\leq$ $\displaystyle\frac{q_{M}\beta}{1-\beta(1+q_{M})}\bigg(\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{1+\beta}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+\bigg.$ $\displaystyle\bigg.q_{W}(1+q_{G})DL+(1+q_{W})(1+q_{G})t\eta\sqrt{r}L\bigg).$ $$

###### Proof of Lemma B.7 .

By the definitions of $\mathbf{Z}_{t}$ and $\mathbf{M}_{t}$ in ([B.5](https://arxiv.org/html/2510.21314v1#A2.E5)) and ([B.1](https://arxiv.org/html/2510.21314v1#A2.E1)), we have

$$ $\displaystyle\mathbb{E}[\|\mathbf{Z}_{t}-\mathbf{M}_{t}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{Z}_{t-1}-\mathbf{M}_{t-1}^{Q}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{Z}_{t-1}-\mathbf{M}_{t-1}\|_{F}+\beta\|\mathbf{M}_{t-1}-\mathbf{M}_{t-1}^{Q}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta\|\mathbf{Z}_{t-1}-\mathbf{M}_{t-1}\|_{F}+q_{M}\beta\|\mathbf{M}_{t-1}\|_{F}]$ $\displaystyle\leq$ $\displaystyle\mathbb{E}[\beta(1+q_{M})\|\mathbf{Z}_{t-1}-\mathbf{M}_{t-1}\|_{F}+q_{M}\beta\|\mathbf{Z}_{t-1}\|_{F}]$ $\displaystyle\leq$ $\displaystyle q_{M}\beta\sum_{k=0}^{t-1}\beta^{k}(1+q_{M})^{k}\|\mathbf{Z}_{t-k-1}\|_{F}$ $\displaystyle\leq$ $\displaystyle\frac{q_{M}\beta}{1-\beta(1+q_{M})}\bigg(\frac{\sigma}{\sqrt{B}}+\sqrt{\frac{1-\beta}{(1+\beta)}}\cdot\frac{\sigma}{\sqrt{B}}+G+q_{G}(\sigma+G)+\bigg.$ $\displaystyle\bigg.q_{W}(1+q_{G})DL+(1+q_{W})(1+q_{G})t\eta\sqrt{r}L\bigg).$ (B.17) $$

The second inequality is due to the triangle inequality. The third inequality is due to Definition [B.1](https://arxiv.org/html/2510.21314v1#A2.Ex1). The fourth inequality is due to the triangle inequality. The fifth inequality is due to $\mathbf{Z}_{0}=\mathbf{M}_{0}$. The last inequality we used Lemma [B.6](https://arxiv.org/html/2510.21314v1#A2.Thmtheorem6)
∎

###### Lemma B.7 .

###### Proof of Lemma B.7 .

## Appendix C Additional Experiments and Details

### C.1 Imitating Quantization and Dequantization

We emulate floating-point quantization and dequantization by reducing the mantissa length from its original precision (52 bits for float64 and 23 bits for float32) to $M$ bits, while keeping the exponent and sign bits unchanged.
This design choice is motivated by the fact that practical scaling techniques can effectively prevent overflow and underflow [Peng et al., 2023].
After truncating the mantissa, we apply stochastic rounding to the nearest two representable values, and then dequantize the result back to standard float32 or float64.

### C.2 Synthetic Experiments

We conduct synthetic experiments on the Rosenbrock function, defined as

$$ $\displaystyle F(\mathbf{W})=\sum_{j=1}^{n-1}\Big(100\|\mathbf{W}_{j+1}-\mathbf{W}_{j}^{2}\|_{F}^{2}+\|\mathbf{1}_{m}-\mathbf{W}_{j}\|_{F}^{2}\Big),$ $$

where $\mathbf{W}=[\mathbf{W}_{1},\mathbf{W}_{2},\dots,\mathbf{W}_{d}]\in\mathbb{R}^{m\times n}$ is the weight matrix.
The global minimum is at $\mathbf{W}^{*}=[\mathbf{1}_{m},\mathbf{1}_{m},\dots,\mathbf{1}_{m}]$ with $F(\mathbf{W}^{*})=0$.
We set $m=50$, $d=100$, and initialize $\mathbf{W}_{0}\sim\mathcal{N}(\mathbf{1}_{m\times n},0.1^{2}\mathbf{I})$.
For Muon, we apply the default hyperparameters in the Newton-Schulz iteration to compute the zeroth power / orthogonalization of $G$ [Jordan et al., 2024], using double precision.

Figure [3](https://arxiv.org/html/2510.21314v1#S4.F3) shows the gradient norms of Adam with different quantization errors on the Rosenbrock function. Figure [4](https://arxiv.org/html/2510.21314v1#S4.F4) shows the gradient norms of Muon with different quantization errors on the Rosenbrock function.

Figure [5](https://arxiv.org/html/2510.21314v1#A3.F5) shows the function values of Adam with different quantization errors on the Rosenbrock function. Figure [6](https://arxiv.org/html/2510.21314v1#A3.F6) shows the function values of Muon with different quantization errors on the Rosenbrock function. The relative quantization error is defined as $\frac{\|\mathbf{X}-Q(\mathbf{X})\|_{F}}{\|\mathbf{X}\|_{F}}$, measuring the average quantization error of $\mathbf{X}$, where $Q(\cdot)$ is the quantization operator.

Figure: Figure 5: Rosenbrock: Adam relative quantization error of different mantissa bits ($M$). Weights error (top left), Gradient error (top right), First moment error (bottom left), Second moment error (bottom right). These results show that the more mantissa bits, the smaller the relative quantization error. Combining with Figure [3](https://arxiv.org/html/2510.21314v1#S4.F3), we can see that the more mantissa bits, the smaller quantization error, the better convergence performance (Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5)).
Refer to caption: x5.png

Figure: Figure 6: Rosenbrock: Muon relative quantization error of different mantissa bits ($M$). Weights error (left), Gradient error (middle), Momentum error (right). These results show that the more mantissa bits, the smaller the relative quantization error. Combining with Figure [4](https://arxiv.org/html/2510.21314v1#S4.F4), we can see that the more mantissa bits, the smaller quantization error, the better convergence performance (Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6)).
Refer to caption: x6.png

### C.3 Real-data Experiments

We conduct real-data experiments on the CIFAR-10 dataset [Krizhevsky et al., 2009] using a 4-layer fully connected network (FCN).
The architecture is as follows: an input layer with 3072 neurons (corresponding to $32\times 32\times 3$ images), followed by three hidden layers with 512, 256, and 64 neurons, respectively, and an output layer with 10 neurons for classification.
ReLU activations are used for all hidden layers, and the network is trained with the cross-entropy loss for 100 epochs.
We evaluate both Adam and Muon under varying quantization precisions.

For Adam, we use mantissa bit-lengths $M\in\{1,2,3,7,10,23\}$, batch size $B=256$, learning rate $\eta=1.5\times 10^{-4}$, $\beta_{1}=0.95$, $\beta_{2}=0.999$, $\epsilon=10^{-8}$, and weight decay $0.1$.
For Muon, vector parameters are updated using Adam, while matrix parameters are updated with Muon’s orthogonalization step.
We choose mantissa bit-lengths $M\in\{2,3,7,10,23\}$, batch size $B=512$, learning rate $\eta=0.001$, $\beta=0.99$, weight decay $0.1$, and 5 Newton–Schulz iterations, following the iteration hyperparameters in Jordan et al. [2024]. The auxiliary Adam optimizer in Muon uses learning rate $\eta=2\times 10^{-4}$, $\beta_{1}=0.9$, $\beta_{2}=0.999$, $\epsilon=10^{-8}$, and weight decay $0.05$.

Figure [7](https://arxiv.org/html/2510.21314v1#A3.F7) shows the gradient norms of Adam with different quantization errors on CIFAR-10. Figure [8](https://arxiv.org/html/2510.21314v1#A3.F8) shows the gradient norms of Muon with different quantization errors on CIFAR-10.
Figure [9](https://arxiv.org/html/2510.21314v1#A3.F9) shows the quantization errors of Adam with different precision on CIFAR-10. Figure [10](https://arxiv.org/html/2510.21314v1#A3.F10) shows the quantization errors of Muon with different precision on CIFAR-10. The relative quantization error is defined as $\frac{\|\mathbf{X}-Q(\mathbf{X})\|_{F}}{\|\mathbf{X}\|_{F}}$, measuring the average quantization error of $\mathbf{X}$, where $Q(\cdot)$ is the quantization operator.

Figure: Figure 7: CIFAR-10: Adam gradient norms under different mantissa precisions $M$. Larger mantissa bit-lengths lead to smaller converged gradient norms. Together with Figure [9](https://arxiv.org/html/2510.21314v1#A3.F9), this demonstrates that higher precision reduces quantization error and improves convergence, consistent with Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5).
Refer to caption: x7.png

Figure: Figure 8: CIFAR-10: Muon gradient norms under different mantissa precisions $M$. Larger mantissa bit-lengths lead to smaller converged gradient norms. Together with Figure [10](https://arxiv.org/html/2510.21314v1#A3.F10), this demonstrates that higher precision reduces quantization error and improves convergence, consistent with Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6).
Refer to caption: x8.png

Figure: Figure 9: CIFAR-10: Adam relative quantization error of different mantissa bits ($M$). Weights error (top left), Gradient error (top right), First moment error (bottom left), Second moment error (bottom right). These results show that the more mantissa bits, the smaller the relative quantization error. Combining with Figure [7](https://arxiv.org/html/2510.21314v1#A3.F7), we can see that the more mantissa bits, the smaller quantization error, the better convergence performance (Theorem [4.5](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem5)).
Refer to caption: x9.png

Figure: Figure 10: CIFAR-10: Muon with auxiliary Adam relative quantization error of different mantissa bits ($M$). Weights error (top left), Gradient error (top middle), Momentum error (top right), Auxiliary Adam first moment error (bottom left), Auxiliary Adam second moment error (bottom middle). These results show that the more mantissa bits, the smaller the relative quantization error. Combining with Figure [8](https://arxiv.org/html/2510.21314v1#A3.F8), we can see that the more mantissa bits, the smaller quantization error, the better convergence performance (Theorem [4.6](https://arxiv.org/html/2510.21314v1#S4.Thmtheorem6)).
Refer to caption: x10.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 2
presentation: 3
questions: See weakness
soundness: 2
strengths: complete quantization error analysis under certain settings, both for Adam and Muon
summary: This paper presents the first theoretical framework analyzing the convergence of adaptive optimizers like Adam and Muon under floating-point quantization of gradients, weights, and optimizer states. It shows that both can maintain near full-precision convergence rates if mantissa precision scales logarithmically with iterations, with Muon proving more robust to quantization errors than Adam.
weaknesses: Basically experiments are limited, theory is not that informative either in proving practicality. The novelty and contribution is limited.

- line 402 "the second moment (qV) is stricter than for the first moment (qM)" -> there are well known fact existing works e.g., https://arxiv.org/abs/2405.03637 and https://arxiv.org/abs/2405.03637
- many missing connection with stochastic rounding work where it give unbiased estimation, but brining higher variance. In modern low bit training like 4 bits, SR is widely adopted. for 8 bit, MX and NV leads to minimal quantization errors in computing gradient. Moreover  thm3 https://arxiv.org/pdf/2502.20566 has some simpler Adam analysis under quantization error of q_V . better compare.
- experiments are very limited, not covering practical scenarios like LLM, missing of which does not affect any practicality
- more through theoretical analysis is needed, otherwise, it is just naive extension. For example, for β_12(1 + qM)2 <β2(1−qV),the effect of qM and qV is real? any toy example to test? 
- for "ensuring the relative quantization errors satisfy qG,qM = O(1/T)", need more explanation as, although theretical understandable, qG is not controllable as a function of T in practice, also dependency on W, W_Q. 
- which quantization is most important between weight, gradient, M1, M2? are these supported from theory and aligned with empirical studies?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Se the **Weaknesses** part
soundness: 3
strengths: **Rigorous analysis and theoretical insights that align with recent practice.** Providing clear statements (Th. 4.5 and Th. 4.6), the work explains why Muon tolerates quantization better than Adam --- mostly due to an important assumption of $\beta_2\to1$ in the Adam analysis. This theoretical insight matches practitioners’ observations [1], narrowing the theory–empirical gap.

**Empiritical validation confirms theory.** Experiments on the Rosenbrock function and small  fully connected models confirm theory. For instance, Figs. 3–4 show that increasing mantissa bits reduces final gradient norms, consistent with the $\Omega(\log T)$-bit requirement 

**Framework.** The idea of analyzing jointly quantized gradients, weights, and optimizer states, whereas prior work focused mainly on gradient-only quantization sounds promising for future research.

[1] "Beyond Outliers: A Study of Optimizers Under Quantization", 2025
summary: In summary, the paper fills an important gap: it builds on existing convergence results for adaptive optimizers but in a new setting --- floating-point errors. The authors establish new converge guarantees for Muon and Adam, showing that both methods retain rates close to their full-precision counterparts. The key assumption --- the boundedness of the relative quantization error is quite realistic and achievable in low-precision-aware architectural designs. To the best of my knowledge, no previous paper has offered similar full-precision-vs-quantization convergence rates for adaptive methods.
weaknesses: **Missing research on convergence of matrix-based optimizers, leaving a room for improvement.**  Unlike Kovalev et al. [2] who handles constrained/composite and star-convex settings, or Shen et al. [3], who exploits Hessian structure in several assumptions, the presented theory is only for unconstrained smooth non-convex functions. Also discussions with the results on constrained / unconstrained LMO optimization [4] --- resulting in the Scion optimizer --- would benefit the theoretical flavor of the work. Please, offer any ideas on how to extend your findings to assumptions in mentioned works.
Additionally, can you provide an idea of how to extend your results to another, promising setting regarding --- non-smooth, convex functions? As it is demonstrated to be a setup which explains LLMs fairly well [5,6].

**Mantissa growth requirement.** For Muon, to retain the rate of the full-precision training, you assume the logarithmic grows of mantissa $M = \Omega(\log{T})$. However, in practice, the bit-width is typically fixed (e.g., 8-bit). This means convergence is to a neighborhood in fixed precision. The paper does show empirically that moderate precision suffices, but the theory only covers the increasing-bit regime. So there is a mismatch that can be left for future research. If this issue is not solved, I recommend to live it as a limitation. Otherwise, it would be nice to offer some discussion regarding this topic in the paper.

**Missing research on optimizers trained in low precision formats.** Naturally, the state-of-the-art LLM training is held in the mixed-precision format --- when optimizer states, softmax, normalization layers are in float32 and other parameters are in bfloat16. Recent work [1] studies optimizer behavior in quantization-aware training paradigms, running models in precisions of up to 4 bits. A notable takeaway --- Shampoo consistently yields the lowest accuracy drop. I believe this can be helpful because studying convergence (in the low-precision setup) of other matrix-based optimizers that emerge as a steepest descent under the spectral norm can be a direct consequence of your research. Moreover, two concurrent works [7,8] have benchmarked a zoo of optimizers at scale, showing that matrix-whitening methods are highly performant.
Naturally, extending your theoretical findings to other "matrix" optimizers would be very useful for the community. Can you give a couple of comments regarding how it is possible to extend you framework to optimizers validated in the works above?

[1] "Beyond Outliers: A Study of Optimizers Under Quantization", 2025

[2] "Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization", 2025

[3] "On the Convergence Analysis of Muon", 2025

[4] "Training Deep Learning Models with Norm-Constrained LMOs", 2025

[5] "The Road Less Scheduled", 2024

[6] "Prodigy: An Expeditiously Adaptive Parameter-Free Learner", 2023

[7] "Benchmarking Optimizers for Large Language Model Pretraining", 2025

[8] "Fantastic Pretraining Optimizers and Where to Find Them", 2025

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - Around assumption 3.1, isn’t the definition of relative error and quantization error (via mantissa length) essentially the definition of machine epsilon for the underlying floating-point format? If not, what distinguishes it?

- [Ozkara et al., 2025] derives a bound involving error term $T\sqrt{\log(1/\beta_2)}$, while this paper presents one with $-T\log(\beta_2)$. what causes this discrepancy, and could the authors provide a direct comparison? The difference implies distinct requirements for the quantization-error schedule.

- In real training, the actual gradients come with end-to-end training , a compound effect of quantization across multiple layers, how does that correlate or concludes to the quantization error or machine epsilon $q_W$, they are different. 
In real mixed-precision training, gradients are perturbed by end-to-end quantization and matmul across multiple layers, leading to compounded effects. How does this aggregate behavior appear in the end to only the relative error (machine epsilon) $q_G$ term from single quantization function?
soundness: 3
strengths: - The paper extends prior work with a rigorous convergence analysis of adaptive optimizers under quantization of gradients, weights, and momentum terms.

- It proposes a quantization schedule that aligns the behavior of quantized optimizers with their full-precision counterparts, offering insights into the sensitivity of different components to quantization error.

- The inclusion of the Muon optimizer broadens the analysis and enhances the paper’s practical relevance.
summary: The paper presents a theoretical framework analyzing the convergence of adaptive optimizers (Adam and Muon) under quantization of gradients, weights, and optimizer states, extending prior work that studied only partial components. It quantifies how these errors influence convergence and when performance remains close to full precision. Adam is shown to be more sensitive to quantization, while Muon is more robust. Results are mainly supported by synthetic experiments.
weaknesses: The paper omits key references and makes inaccurate claims about prior work. For instance, 

- [Hou et al. 2019] analyzed not only SGD but also adaptive optimizers such as Adam under weight and gradient quantization (without the first-order momentum term, i.e., $\beta_1=0$). As shown by [D´efossez et al. 2022], omitting momentum only introduces a multiplicative slowdown term, which should be acknowledged unless the new quantization error model changes this relationship.

- Another closely related but uncited work is [Ozkara et al., 2025], which studies the convergence rate of Adam under weight quantization (again without first-order momentum) and analyzes the effect of stochastic rounding, an increasingly important direction. It remains unclear whether the proposed framework can naturally incorporate stochastic rounding into analysis.

Some theoretical setups are impractical. For example, 
- assuming $\beta_2 \to 1$ is unrealistic, in practice a fixed $\beta_2 < 1$ is used, when the term $T \log(\beta_2)$ would diverge. Besides, [Ozkara et al., 2025] already emphasizes the reliance of convergence on $\beta_2 \to 1$. 

- even accepting the assumption, the proposed quantization error schedule that makes the error term vanish is infeasible in practice, as precision cannot be controlled dynamically without effectively reverting to full-precision training. In reality, quantization error is bounded by the machine epsilon of the floating-point format unless altering the format during training

The experimental validation is limited and basic. There are no studies examining the influence of (\beta_2 \to 1) or verifying how the proposed quantization error schedule aligns with theoretical predictions.

Lu Hou et al., Analysis of quantized models. In International Conference on Learning Representations, 2019.

Ozkara et al., Stochastic rounding for LLM training: Theory and practice. In The 28th International Conference on Artificial Intelligence and Statistics.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Q1: Could you provide more detailed analysis of the practical trade-offs between precision (bit-length) and computational efficiency in Quantized Adam? Specifically, how does the convergence rate $O(T^{-1/4})$ translate to practical training time and memory usage?

Q2: The empirical evaluation appears limited to a single dataset (Rosenbrock). Could you expand the experiments to include more diverse optimization problems and model architectures to better validate the theoretical results?

Q3: How does Quantized Adam compare to other quantization techniques for optimization algorithms (e.g., error-feedback mechanisms, stochastic rounding) in terms of convergence rate and practical performance? A comparative study would strengthen the paper's contribution.

Q4: Could you elaborate on how the theoretical convergence rate $O(T^{-1/4})$ translates to practical training performance (e.g., final model accuracy) for different quantization levels? This would help bridge the gap between theory and practice.

Q6: The paper mentions "we use a small constant $\epsilon>0$ for numerical stability" but doesn't discuss the impact of  $\epsilon$ on convergence. Could you analyze how the choice of $\epsilon$ affects the convergence rate and practical performance?
soundness: 3
strengths: S1: The paper provides the first convergence guarantee for Adam under a practical floating-point quantization model, addressing a significant gap in the literature.

S2: The theoretical analysis is rigorous and well-structured, with careful handling of quantization errors and their impact on convergence.

S3: The paper establishes concrete hyperparameter settings that ensure convergence at the same rate as full-precision Adam, making the theoretical results practically applicable.

S4: The empirical results (Figure 4) provide strong validation of the theoretical findings, showing that increased precision (larger mantissa bit-lengths) leads to smaller converged gradient norms.

S5: The paper carefully justifies the theoretical framework by establishing two foundational equivalences, demonstrating that the analysis of quantizing weighted-sum states is directly applicable to practical quantization scenarios.
summary: This paper presents a theoretical analysis of the convergence properties of Adam-type optimization algorithms. The authors propose a unified framework to analyze convergence rates and provide theoretical guarantees for both convex and non-convex settings. The work includes detailed proofs in the appendix and experiments on synthetic datasets and CIFAR-10 to validate the theoretical claims. The paper also discusses practical implications for hyperparameter selection and algorithm design.
weaknesses: W1: The paper does not sufficiently discuss the practical implications of the theoretical results for real-world applications, particularly regarding the trade-off between precision (bit-length) and computational efficiency.

W2: The convergence analysis assumes certain conditions that might be restrictive in practice, but the paper doesn't fully explore how these conditions affect real-world implementation.

W3: The empirical evaluation appears limited to a single dataset (Rosenbrock) in Figure 4, which may not be sufficient to generalize the findings across different optimization problems and model architectures.

W4: The paper doesn't provide a comprehensive comparison with other quantization techniques for optimization algorithms, making it difficult to assess how Quantized Adam compares to alternative approaches.

W5: The connection between the theoretical convergence rate and practical training performance (e.g., final model accuracy) is not explicitly established, which would strengthen the practical relevance of the results.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: - Literatures such as [1] and [2] usually consider the constant compressed coefficient. Could the convergence results be extended to a broader range of compressed coefficients, such as any constant within $(0,1)$?
soundness: 3
strengths: (a). To my best knowledge, this seems to be the first theoretical convergence result for Adam under the quantization of two EMA moment estimations, and for Muon.  

(b). The results somehow reflect the effects of quantization on the convergence rate. In addition, the results seem to provide the insight that Adam is sensitive to weights and second-moment quantization, while Muon is potentially more robust, as Muon allows for a weaker quantization error control than Adam.
summary: This paper provides the theoretical convergence results for Adam and Muon, under floating-point quantization of gradients, weights, and optimizer states (e.g., the EMA moment estimation in Adam). They show that both Adam and Muon can derive convergence rates of $O(1/T^{1/4})$ on smooth non-convex objectives, even under the quantization.
weaknesses: My major concerns lie in the theoretical part.

- The term $\tilde{Q}(T)$ in the convergence bound of Theorem 4.5 is not very clear. Although the authors provide a detailed expression in Eq. A.43, it's still very complicated and lacks of detailed discussion with regard to the dependency on $T$. The dependency on $T$ is crucial since it is the dominating order in the convergence rate. I suggest providing a detailed calculation on the order of $\tilde{Q}(T)$, particularly when $\eta,\beta_2$ and terms like $q_G,q_W$ are set as in Line 372.

- Assumptions 3.1 requires the compressed coefficient to be $2^{-M}$, where $M$ is the mantissa length of the target floating-point format. It seems that $M$ is an important parameter to quantify the accuracy of quantization, which, however, does not appear in the convergence bound. 

- The convergence results are heavily relied on sufficiently small $q_G,q_W,q_M,q_V$ (relative quantization errors), which assembles the case of non-quantization. Based on the existing convergence results for non-quantization of Adam and Muon, it seems that the results in this paper are not very novel. In addition, it lacks very clear definitions of these terms in the main body of the paper. 

- The convergence results require relative quantization errors to be $O(1/T)$ or $O(1/T^2)$ order. However, under the quantization error made in Assumption 3.1, is it possible to achieve a sufficiently small relative quantization error, such as $O(1/T)$ order?


Decision: Accept (Poster)