Custom Gradient Estimators are Straight-Through Estimators in Disguise

## Abstract

Abstract Quantization-aware training comes with a fundamental challenge: the derivative of quantization functions such as rounding are zero almost everywhere and nonexistent elsewhere. Various differentiable approximations of quantization functions have been proposed to address this issue.
In this paper, we prove that a large class of weight gradient estimators is approximately equivalent with the straight through estimator (STE). Specifically, after swapping in the STE and adjusting both the weight initialization and the learning rate in SGD, the model will train in almost exactly the same way as it did with the original gradient estimator. Moreover, we show that for adaptive learning rate algorithms like Adam, the same result can be seen without any modifications to the weight initialization and learning rate. These results reduce the burden of hyperparameter tuning for practitioners of QAT, as they can now confidently choose the STE for gradient estimation and ignore more complex gradient estimators.
We experimentally show that these results hold for both a small convolutional model trained on the MNIST dataset and for a ResNet50 model trained on ImageNet.

## 1 Introduction

The importance of quantized deep learning. Quantized deep learning has gained significant attention as a means to address the demand for efficient deployment of deep neural networks on resource-constrained devices. Traditional deep learning models typically employ high-precision representations, consuming substantial computational resources and memory. Quantized deep learning techniques offer a compelling solution by reducing the precision of network parameters and activations. Although the Post-Training Quantization technique is easier to use to quantize any given model, Quantization-Aware Training (QAT) has been shown to provide higher quality results since quantized weights are updated throughout the training process [].

Gradient estimators are needed in QAT. QAT encounters a problem where
the derivatives of quantization functions are zero or nonexistent everywhere. To sidestep this problem, practitioners use approximations of the quantization functions (known as gradient estimators) for backpropagation. The straight-through estimator is a common choice for this, but many believe it is better for a gradient estimator to more closely approximate the rounding function.
We show that this belief is misguided.

Our main contributions are as follows:

- 1.
A proof under minimal assumptions that all nonzero weight gradient estimators lead to approximately equivalent weight movement for non-adaptive learning rate optimizers (SGD, SGD + Momentum, etc.) when the learning rate is sufficiently small, after a change to weight initialization and learning rates has been applied.
- 2.
A proof that for adaptive learning rate optimizers (Adam, RMSProp, etc.) the same result holds without any need for adjustment to the learning rate and weight initialization.
- 3.
Empirical evidence demonstrating this result on both a small deep neural networked train on MNIST and a larger ResNet50 model trained on ImageNet.

Value for practitioners: Our findings reduce the burden of hyperparameter tuning for QAT. Practitioners can now confidently choose the Straight Through Estimator [] for gradient estimation and allocate their attention on problems like choosing the weight initialization scheme, learning rate, and optimization method.

## 2 Background and Related Work

The standard quantizer function. The core operation in QAT is the application of a quantizer function to weights and activations, which transforms continuous, high-precision values into discrete, lower-precision representations. Quantization functions act elementwise on weight tensors $\mathbf{w}$, and can therefore be described by scalar functions on weights $w$. While there are many options for the arrangement of quantized values [, , , , ], we will be focused on the most popular formulation, uniform quantization functions, which are defined by

$$ $Q(x):=\Delta\cdot{\textrm{round}}\left(\textrm{clip}\left(\frac{x}{\Delta},l,u \right)\right)\qquad\mathrm{where}\qquad\textrm{clip}(x,l,u)=\begin{cases}l& \text{if }x<l,\\ x&\text{if }l\leq x\leq u,\\ u&\text{if }x>u.\end{cases}$ (1) $$

The problem of choosing $\Delta$, $l$, and $u$ is well-researched, and we cover common approaches in Appendix A.

Boundary points. We will refer to the sets of quantizer input values that map to a single output value as quantization bins. The boundaries of these bins are known as boundary points. We will use $w_{+}$ and $w_{-}$ to refer to the lower and upper boundary points for the bin containing weight $w$. One of these points must exist for each $w$, but outside of the representable range (see Appendix A) of the quantizer only one of the two will exist. Note that $w_{+}-w_{-}=\Delta$ for all weights in the representable range.

The Straight Through Estimator.
Because $Q^{\prime}(x)=dQ/dx$ is zero almost everywhere and nonexistent elsewhere, vanilla gradient descent would never update the weights of a quantized model. The standard approach for addressing this issue is to approximate $Q(x)$ by a differentiable surrogate function $\hat{Q}$ and use its gradient $\hat{Q}^{\prime}(x)$ for backpropagation.
The derivative $\hat{Q}^{\prime}$ is known as a gradient estimator (or gradient approximation). The earliest popular choice of gradient estimator is known as the straight-through estimator [, ] or STE, defined by $\hat{Q}(x)=x$, $\hat{Q}^{\prime}(x)=1$.

Piecewise linear estimators. Piecewise linear (PWL) estimators have derivative $I_{[w_{min},w_{max}]}$, where $I$ is the indicator function. They make $\hat{Q}$ more closely resemble $Q$ [, , ]. The simplest way to define a PWL estimator for a multi-bit quantizer is to simply use Equation 1 with the round step removed, and in this case $[w_{min},w_{max}]$ is exactly the representable range. This way, the behavior of PWL estimators more closely relate to the quantization function. In general, we will use $PWL_{w_{min},w_{max}}(x)=\textrm{clip}(x,w_{min},w_{max})$ to denote a PWL gradient estimator.

STE and PWL lead to “gradient error". The simple STE and PWL gradient estimators described above still leave a significant gap between the behavior of the forward pass and the surrogate forward pass. For this reason, researchers have proposed a large number of custom gradient estimators, often citing a high “gradient error" in the simpler choices of gradient estimators as motivation for their work. Gradient error is often described as the difference between $Q$ and $\hat{Q}$.

An abundance of custom gradient estimators. In order to solve the perceived problem of gradient error, many researchers have proposed gradient estimators that carry more complexity than the STE or PWL estimators. In Appendix B, we cite and describe 15 examples of custom gradient estimators in the quantization literature. Plots of some prominent examples are given in Figure 1.

Figure: Figure 1: Gradient Estimators from left to right: STE [], PWL [], MAD [], HTGE [], EDE []. The EDE is for binary quantization, and the others are for multi-bit quantization.
Refer to caption: extracted/2405.05171v3/figs/all_gradients.png

## 3 Gradient Descent Terminology for QAT

For a quantized model with gradient estimator $\hat{Q}$, the gradient value at step $t$ is $\nabla f(Q(w^{(t)}))\hat{Q}^{\prime}(w^{(t)})$, where $f$ is the loss function of the model. Of course $f$ depends on the dataset and all other network weights, but we suppress this for notational convenience. Going forward, we will abbreviate $\nabla f(Q(w^{(t)}))$ as $\nabla f^{(t)}$. The weight update is expressed as

$$ $w^{(t+1)}=w^{(t)}+g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots, \nabla f^{(t)}\hat{Q}^{\prime}(w^{(t)}),\eta).$ (2) $$

where $\eta$ is the learning rate.
The notation for $g^{(t)}$ is borrowed from [].
By defining $g^{(t)}$, we can recover all of the standard gradient descent algorithms, i.e. SGD, Adam, RMSProp, etc. In the simplest case, we have $g^{(t)}(\nabla f^{(t)}\hat{Q}^{\prime}(w^{(t)}),\eta)=-\eta\nabla f^{(t)}\hat{
Q}^{\prime}(w^{(t)})$, which gives us the common SGD learning rule

$$ $w^{(t+1)}=w^{(t)}-\eta\nabla f^{(t)}\hat{Q}^{\prime}(w^{(t)}).$ (3) $$

The definition of $g^{(t)}$ for SGD with momentum is given in Appendix D. A more complex but highly popular learning rule is the Adam [] optimizer, which is defined with the above notation in Appendix E.

Adaptive and non-adaptive algorithms. Adam is an example of an adaptive learning rate algorithm, since the weight update steps are normalized by a computation on past gradient values. Other examples of adaptive learning rate methods are RMSprop [], Adadelta [], AdaMax [], and AdamW [],
We refer to all other update rules, such SGD and SGD with momentum [],
as non-adaptive learning rate algorithms.

## 4 Intuition

To aid the reader in developing intuition about our main results, we tell a brief story below.

The Mirror Room story. Imagine you are in a room with a glass wall. On the other side of the glass wall, there is a person in another room, larger than yours. You are standing at different positions in your respective rooms. Any time you take a step, this other person takes a step in the same direction, albeit with a different step length. You continue to move around, and you are rarely exactly across from this person, but any time you try to leave, this person leaves the room on the same side at the same time.

You realize that the glass wall is not a wall, it’s a funhouse mirror. The person on the other side is you, but the picture is “warped" by the mirror.

The Mirror Room is the quantization bin for two equivalent models. The scenario described above is similar to the relationship between the motion of weights in a model ($\hat{Q}$-net) that uses a complex gradient estimator $\hat{Q}$ and another ($STE$-net) that uses the $STE$ with the proper reconfigurations to match $\hat{Q}$-net. In the analogy, you are a weight in $STE$-net, your reflection is the weight in $\hat{Q}$-net. The room is a quantization bin, and the doors are the boundary points. The simultaneous exit of you and your reflection from the room parallels the synchronized quantized weights in both models, leading to identical gradients and training outcomes.

Figure: Figure 2: The funhouse mirror. The blue figure represents you (a weight in $STE$-net), and the red figure represents your reflection (a weight in $\hat{Q}$-net) on the other side. The reflections line up at the edge of the room.
Refer to caption: extracted/2405.05171v3/figs/mirror_walk_stick_figures.png

The “Funhouse Mirror" effect of $M$ and ${\hat{Q}}$. In Section 5, we define a map $M$ that acts as a “funhouse mirror" mapping the weights of $\hat{Q}$-net to those of $STE$-net.
Any initial weight $w^{(0)}$ in $\hat{Q}$-net is re-initialized to $M(w^{(0)})$ in $STE$-net, and the relationship $M(w_{\hat{Q}})=w_{STE}$ approximately holds throughout training, where $w_{\hat{Q}}$ is a weight in $\hat{Q}$-net, and $w_{STE}$ is the corresponding weight in $STE$-net.
Thus after the $\hat{Q}$-net weight takes a step, the $STE$-net weight moves in near lockstep after passing through the “funhouse mirror" of $M$.
Furthermore, since $M(w)=w$ whenever $w$ is a boundary point, these two weights will cross the quantization boudaries at nearly the same time.
The bisimulation of the two models is justified by this property.

A visualization of the funhouse mirror is given in Figure 2.

## 5 Main Results

In this section we formalize the realizations of Section 4 and provide our main mathematical results (1 and 2). Furthermore, this will show that much of the concern about “gradient error" is unfounded. We provide Theorem statements for both the SGD update rule and the Adam update rule, with proofs and generalizations in the Appendices. Note that all of the below results apply to weight quantizers. We do not address activation quantizers in this work.

### 5.1 Definitions and Notation

Cyclical gradient estimators. We say that a gradient estimator $\hat{Q}$ for a uniform quantizer $Q$ is cyclical if $\hat{Q}$ is identical on each finite-length quantization bin, i.e.
$\hat{Q}^{\prime}(w)=\hat{Q}^{\prime}(w+\Delta)$
whenever $w$ and $w+\Delta$ are inside a finite-length quantization bin (i.e. within the representable range). Most multi-bit gradient estimators proposed in the literature are cyclical. Binary gradient estimators are cyclical by default, since they have no finite quantization bins. Unless otherwise specified, we will assume that all gradient estimators are cyclical.

Definitions of $\alpha$ and $M$. We give two more definitions before presenting the details of the models we are comparing. These objects ($\alpha$ and $M$) will allow us to succinctly express the learning rate update and weight initialization update needed to mimic the behavior of a positive gradient estimator $\hat{Q}$ using only the STE.
If $Q$ is a uniform multi-bit quantizer and $\hat{Q}$ is cyclical, we define the learning rate adjustment factor $\alpha$ and weight readjustment map $M$:

$$ $\alpha:=\frac{\Delta}{\int_{w_{-}}^{w_{+}}\frac{ds}{\hat{Q}^{\prime}(s)}} \qquad\qquad M(w):=w_{b}+\alpha\int_{w_{b}}^{w}\frac{ds}{\hat{Q}^{\prime}(s)}$ (4) $$

Here $w_{+}$ and $w_{-}$ are adjacent boundary points, and $w_{b}$ is any standalone boundary point. Since $Q$ is uniform and $\hat{Q}$ is cyclical, the definition of $\alpha$ is independent of the choice of boundary points. If $Q$ is a binary quantizer, then $Q$ has only one boundary point, and we define $\alpha:=1$. Note that $\alpha$ is defined entirely by $\hat{Q}$, and can be computed at the outset of training. It may vary per-layer if the parameters of $\hat{Q}$ do so. Intuitively it can be thought of as the ratio between the quantization bin size ($\Delta$) and the “effective bin size" of a gradient estimator $\hat{Q}$ (the denominator of Equation 4). The definition of $M$ is independent of the choice of $w_{b}$. We can think of $M$ as a function that maps a weight $w$ to a new point $M(w)$ whose relative distance from its left and right boundaries matches the relative “effective distance" (under $\hat{Q}$) between the boundary points and the original weight $w$.

Definition of $\hat{Q}$-net and $STE$-net. For both optimization techniques we consider (SGD and Adam) we will study two models, $\hat{Q}$-net and $STE$-net. The models can have any architecture, as long as they are equivalent. We will focus on corresponding weights $w_{\hat{Q}}^{(t)}$ and $w_{STE}^{(t)}$, respectively, at iteration $t$. We will denote the gradients of the loss function $f$ with respect to $Q(w_{\hat{Q}}^{(t)})$ and $Q(w_{STE}^{(t)})$ as $\nabla f_{\hat{Q}}^{(t)}$ and $\nabla f_{STE}^{(t)}$, respectively. The differences in gradient estimators, learning rates and weight initialization for both SGD and Adam are given in Tables 2 and 2, respectively.

**Table 1: $\hat{Q}$ and $STE$ Models for SGD**
| Model | $\hat{Q}$-net | $STE$-net |
| --- | --- | --- |
| Gradient Estimators | $\hat{Q}$ | $STE$ |
| Learning Rates | $\eta$ | $\alpha\eta$ |
| Initial Weights | $w_{\hat{Q}}^{(0)}$ | $M(w_{\hat{Q}}^{(0)})$ |

Comparison Metric.
We can quantify how the weights between $\hat{Q}$-net and $STE$-net differ using weight alignment error, which is defined as

$$ $E^{(t)}:=\left|M\left(w^{(t)}_{\hat{Q}}\right)-w^{(t)}_{STE}\right|\quad \mathrm{for\ SGD,\ and}\quad E^{(t)}:=\left|w^{(t)}_{\hat{Q}}-w^{(t)}_{STE} \right|\quad\mathrm{for\ Adam.}$ (5) $$

$E^{(t)}$ measures how far off the weights are between the two models at iteration $t$, and starts at $E^{(0)}=0$ due to our choice of initial weights in Tables 2 and 2. Furthermore, since $M$ preserves quantization bins, we have that $Q(w^{(t)}_{\hat{Q}})=Q(w^{(t)}_{\hat{Q}})$ whenever $E^{(t)}$ is small.

### 5.2 Theorem Statements

Theorem 5.1 rigorously states contribution 1 for the SGD update rule (Equation 3). It states that after adjusting the learning rate of a model by $\alpha$ and re-initializing the weights by applying $M(w)$, a positive gradient estimator $\hat{Q}$ can be replaced by the STE with minimal differences in training.

###### Theorem 5.1 .

Suppose that $E^{(t)}$ is the alignment error for $\hat{Q}$-net and $STE$-net with SGD (Table 2). Assume that the following hold:

- 5.1.1
$0<L_{-}\leq|\hat{Q}^{\prime}(w)|\leq L_{+}$ for all $w$. (Bounded, positive gradient estimator)
- 5.1.2
$\hat{Q}^{\prime}(w)$ is $L^{\prime}$-Lipschitz. (Well-behaved gradient estimator)

Then we have

$$ $E^{(t+1)}\leq E^{(t)}+\underbrace{\eta\alpha\left|\nabla f_{\hat{Q}}^{(t)}- \nabla f_{STE}^{(t)}\right|}_{\text{gradient error}}+\underbrace{\frac{L^{ \prime}}{2}\cdot\left(\frac{\eta L_{+}\nabla f_{\hat{Q}}^{(t)}}{L_{-}}\right)^ {2}}_{\text{convexity error}}$ (6) $$

See Appendix C.1 for a rigorous proof. The theorem only considers the standard gradient descent process. For a similar statement for a more general class of non-adaptive learning rate optimizers, see Appendix C.1. See Appendix D for a more specific result for SGD with momentum.

Theorem
5.2 rigorously proves contribution 2 for the Adam update rule (Equations 57-61). The result here is stronger than Theorem 5.1. When using the Adam update rule, the gradient estimator $\hat{Q}$ can be replaced by the STE without any update to the learning rate or weight initialization.

###### Theorem 5.2 .

Suppose that $E^{(t)}$ is the alignment error for $\hat{Q}$-net and $STE$-net with Adam (Table 2). Assume that the following hold:

- 5.2.1
$0<L_{-}\leq\hat{Q}^{\prime}(w)$ for all $w$. (Lower bounded positive gradient estimator)
- 5.2.2
$\hat{Q}^{\prime}(w)$ is $L^{\prime}$-Lipschitz. (Well-behaved gradient estimator)

Then we have

$$ $E^{(t+1)}\leq E^{(t)}+\underbrace{\left|g^{(t)}(\nabla f^{(0)}_{\hat{Q}}, \ldots,\nabla f^{(t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots, \nabla f^{(t)}_{STE},\eta)\right|}_{\text{gradient error}}+\underbrace{O(\eta^ {2})}_{\text{convexity error}},$ (7) $$

where $g^{(t)}$ is the gradient update rule for Adam (see Equation 2 and Equations 57-61).

See Appendix E for a rigorous proof. In Theorem 5.2, the exact definition of the $O(\eta^{2})$ term is omitted due to its complexity. For a similar statement for a more general class of non-adaptive learning rate optimizers (not just the Adam optimizer), see Appendix E. For a discussion of Theorems 5.1 and 5.2 for learning rate schedules, see Appendix F.

###### Theorem 5.1 .

###### Theorem 5.2 .

### 5.3 On the Assumptions and Implications of Theorems 5.1 and 5.2

Theorems 5.1 and 5.2 rely on specific assumptions about the gradient estimator $\hat{Q}$.
In this section, we break down these assumptions clearly.
Furthermore, we describe how these theorems imply contributions 1 and 2.

The assumptions are reasonable: The upper bound on $\hat{Q}^{\prime}$ in Assumption 5.1.1 is very mild. Gradient estimators with an unbounded derivative would likely cause training instability, and are not used in practice. Similarly, the authors are not aware of a gradient estimator that breaks Assumptions 5.1.2 and 5.2.2. In addition, the constants $L_{-}$, $L_{+}$, and $L^{\prime}$ are usually quite small in practice (see Appendix H for calculations).
The lower bound on $\hat{Q}^{\prime}$ in Assumptions 5.1.1 and 5.2.1, however, is often broken in practice. In Appendix G, we describe how the Theorems still support contributions 1 and 2 in these cases.

The bounds in Equations 6 and 7 are small: In order to see how Theorems 5.1 and 5.2 provide contributions 1 and 2, we can closely examine each term in Equations 6 and 7. The gradient and convexity error in each equation together give a worst-case increase to $E^{(t)}$ at each training step. That is, as long as these terms are small, $\hat{Q}$-net and $STE$-net will train in a very similar manner. The convexity error terms are unavoidable errors, and are extremely small ($O(\eta^{2})$) in practice. The gradient error terms, however, are $O(\eta)$, so they can be large if the gradients of the two models are misaligned. However, since the gradient terms $\nabla f_{\hat{Q}}^{(t)}$ and $\nabla f_{STE}^{(t)}$ only depend on quantized weights, these terms will be zero at the beginning of training and remain small as long as $E^{(t)}$ remains small.

The claim is nontrivial: Note that these theorems do not simply say that when the learning rate is small, the models change very little, and therefore $\hat{Q}$-net and $STE$-net are aligned. Since the irreducible error term is quadratic in $\eta$, the misalignment at each step is small relative to the learning rate itself.

The claim applies to networks of any size: The Theorems only give bounds for the error in a single network weight, but can be applied to each weight independently in a multi-weight network. Of course, the trajectories of weights in a neural network are not independent, but luckily in our case the weight trajectories only depend on the quantized versions of the other network weights. To see this, note that the only terms in Equations 6 and 7 that depend on other network weights are the gradient error terms. As stated earlier, these gradient terms only depend on quantized weights, so we do not need perfect alignment in other network weights in order to keep the error terms in these Equations small. Since the gradient error terms can depend on all other quantized weights in the network, larger models are at a greater risk of weight misalignment.
However, this is more a property of large models than of gradient estimators: any two large models that have only a small difference in hyperparameter configurations but otherwise equivalent training setups will have potentially large step-by-step divergences in weight alignment. And the fundamental difference in training induced by a gradient estimator is indeed small, since in Equations 6 and 7, the true source of all misalignment is an $O(\eta^{2})$ term. This is supported by our experiments in Section 6.

## 6 Experimental Results

Here we demonstrate our main results on practical models.
The general strategy we will take is to implement $\hat{Q}$-net and $STE$-net for a specific model architecture and compare on a variety of metrics to demonstrate the following:

- A.
$\hat{Q}$-net and $STE$-net train in almost exactly the same way.
- B.
If we do not apply the weight re-initialization of Theorem 5.1, we do not see the same results.

### 6.1 Models and Training Setup

Models and Quantizers. We use two model architecture/dataset pairs:

- 1.
A simple three-layer quantized convoluational archicture proposed in [] for image classification on the MNIST dataset,
which gives a uniform weight distribution with the variance recommended in [] trained on a CPU.
- 2.
ResNet50 [] on the ILSVRC 2012 ImageNet dataset [], which showcases generality to a more complex model and dataset trained on a TPU. We used a fully deterministic version of the Flax example library [].

Gradient estimator and Optimizers: We quantize weights using a 2-bit uniform quantizer, and for gradient estimation, we use the $\hat{Q}$ given by the HTGE formula []. See Appendix B for our justification of this choice. For optimization techniques on both models, we consider both SGD and Adam. We use a learning rate of 0.001 for SGD, and 0.0001 for Adam. All models are trained with weight initialization and learning rate adjustments given by Tables 2 and 2.
For more details on the training recipe and quantizers, see Appendix I.

### 6.2 Metrics.

We use two metrics in order to establish Points A and B. Both of these compare $STE$-net weights to $\hat{Q}$-net weights. In addition to the metrics below, we also report accuracy and loss statistics for all models.

Quantized Weight Agreement. At the end of training the complete set of quantized weights is calculated for both models and compared. We report the proportion of quantized weights that are the same for both models.

Normalized Weight Alignment Error ($\mathbf{\bar{E}}$). For each pair of models, we compute the average value of $E^{(T)}$ for the final training step $T$ over all weights. Note that Equation 5 gives two definitions of $E$, and for each model pair we use the version that matches the weight initialization setup, which gives $E^{(0)}=0$ for all model pairs. Each $E^{(T)}$ is normalized by the length of the representable range, so that a value of 100% indicates that the two models’ weights are on opposite sides of the representable range. We denote the average as $\bar{E}$ for all model pairs.

### 6.3 Results

**Table 3: Normalized weight alignment metric $\bar{E}$ for MNIST model with SGD + Momentum, including descriptions and interpretations for all four experiment types. This table serves as a guide for interpreting Table 4.**
| Experiment Name | Experiment Description | $\mathbf{\bar{E}}$ | Interpretation/Comparison to Baseline |
| --- | --- | --- | --- |
| baseline | $\hat{Q}$ vs. STE | 0.515% | Baseline |
| lr-tweak | $\hat{Q}$ vs. $\hat{Q}$ with 1% learning rate increase | 0.572% | Replacing $STE$-net with $\hat{Q}$-net is about as impactful as a small change to $\eta$ (A). |
| unadjusted | $\hat{Q}$ vs. STE without reinitializing weights | 2.52% | The two models only see the same weight movement if weights are re-initialized according to $M$ (B). |

**Table 4: Alignment metrics for SGD (S) and Adam (A). Results for the MNIST model are shown on the left, and results for ResNet50 trained on ImageNet are shown on the right.**
| Experiment Name | $\mathbf{\bar{E}}$ | Quantized Weight Agreement |
| --- | --- | --- |
| baseline (S) | 0.515% | 98.31% |
| lr-tweak (S) | 0.572% | 98.66% |
| unadjusted (S) | 2.52% | 96.53% |
| baseline (A) | 2.81% | 94.42% |
| lr-tweak (A) | 1.74% | 95.4% |

**Table 5: Loss and Accuracy differences between $\hat{Q}$-net and $STE$-net with SGD (S) and Adam (A). Results for the MNIST model are shown on the left, and results for ResNet50 trained on ImageNet are shown on the right. For both SGD (S) and Adam (A) and both models, differences are small.**
|  | Train acc | Train loss | Val acc | Val loss |
| --- | --- | --- | --- | --- |
| STE (S) | 97.05% | 0.1439 | 97.08% | 0.1417 |
| $\hat{Q}$ (S) | 96.98% | 0.1483 | 97.14% | 0.1468 |
| Diff | -0.06% | 0.0044 | 0.06% | 0.0051 |
| STE (A) | 97.56% | 0.1270 | 97.66% | 0.1257 |
| $\hat{Q}$ (A) | 97.63% | 0.1254 | 97.58% | 0.1245 |
| Diff | 0.07% | -0.0016 | -0.08% | -0.0013 |

Figure: (a) $\hat{Q}$-net weights vs $STE$-net weights for MNIST convolutional model at the conclusion of training for default SGD.
Refer to caption: extracted/2405.05171v3/figs/sgd_Weight_Alignment.png

Tables for Points A and B: We provide all metrics for both the default SGD and Adam models described in Section 6.1 within in Table 4, with detailed interpretations for the $\bar{E}$ metric in Table 3. Note that Adam does not have an “unadjusted" case, since there is no need for weight initialization adjustment when Adam is used.

Point A is validated. The standard comparison between $\hat{Q}$-net and $STE$-net is labeled as “baseline". We compute metrics between a $\hat{Q}$-net model and the same model with a learning rate increase of 1% (chosen arbitrarily and only once), reported with the label “lr-tweak". This serves as an example of a “small change" to a model that the reader may be more familiar with, providing additional context about the scale of the metric results and supporting Point A. For both the MNIST and ImageNet models, the alignment between $\hat{Q}$-net and $STE$-net is similar to the alignment expected from a 1% learning rate change.

Point B is validated. We report alignment measurements between $\hat{Q}$-net and $STE$-net without the weight and learning rate adjustments described in Theorem 5.1 using the label “unadjusted". The alignment worsens for both the MNIST model and the ResNet model when removing the weight reinitialization by $M$.

Weight Alignment. For a visual of the weight alignment phenomenon, see Figures 3(a) and 3(b).

There is almost no difference in training accuracy.
Standard training metrics for both $\hat{Q}$-net and $STE$-net are given in Table 5 for both optimizers and both models we consider. This table shows that the two models have very similar train and test metrics, indicating that replacing $\hat{Q}$ with the STE is of minimal impact after applying the appropriate weight initialization and learning rate adjustments. As expected, the alignment is stronger for the smaller model.

## 7 Implications

Here we discuss the implications of this work on the existing literature and future practice and research.

For practitioners. The main message for practitioners is simple, and depends on the optimization strategy used as follows:

- •
SGD and other non-adaptive optimizers: In this case, if the learning rate is sufficiently small and you wish to tweak the gradient estimator, you can instead apply a corresponding weight re-initialization and learning rate adjustment to a model with the STE or PWL estimator and see nearly the same training procedure. The proof and related assumptions are given in Theorem C.1.
- •
Adam and other adaptive optimizers: In this case, when the learning rate is sufficiently small, the only gradient estimators you need consider are the STE and PWL estimators. The proof and related assumptions are given in Theorem E.1.

For researchers. For future research, we hope that this work will inspire further study on processes for updating quantized model parameters that are fundamentally different from the use of gradient estimators, and therefore immune to the arguments of this paper. This may include novel computations on gradients that diverge from the standard chain rule [, ], optimizers specially designed for QAT [], or even methods that do not involve gradient computations at all []. As for the existing literature, our message is that
the concern about “gradient error" should not be considered in the future.

Why are so many gradient estimators published? A natural question that a reader may have concerning past research is this: If the choice of gradient estimator is so irrelevant, why is there so much research that proposes new gradient estimators and demonstrates improved performance with their aid? There are several potential answers to this.
The simplest explanation is that their gradient estimation techniques happen to have implictly uncovered a superior weight re-initialization and learning rate adjustment, as indicated by Theorem 5.1.
The more applicable answer is that
nearly all of these studies propose more than simply a new gradient estimator (as described in Appendix B), and so the results can be due to multiple different contributions.
Another answer could be that the performance improvements were due to changes in quantized activation gradient estimators, which cannot be equated to the STE. A final answer could be that the learning rates in their experiments were too high to see an equivalence between their gradient estimators and the STE. This is a limitation of our main argument, but we expect that this counter-argument will not stand the test of time, since by our main results, the higher learning rate masks the fact that models with novel $\hat{Q}$ and the STE are still approximating the same process.

## Appendix A Choosing Quantization Parameters

The clipping bounds $l$ and $u$ are determined by the number of bits $b$ in the quantized representation and the desired number of representable values in the positive and negative range of the quantizer. This range of weight values is referred to as the representable range (or quantization range) of the quantizer, and can be computed as $[\Delta\cdot l,\Delta\cdot u]$. Large $\Delta$ values allow for large $w$ values to avoid the clip step, whereas small values give small $w$ values a more granular representation. These parameters are either learned [, , ] or set by the user. For $b>1$, $l$ and $u$ are often chosen as $l=-2^{b-1}$, $u=2^{b-1}-1$ for symmetric quantization and $l=0$, $u=2^{b}-1$ for asymmetric quatization. $\Delta$ is often chosen uniformly per-channel or per-token, based off of latent weight data $W$. It is sometimes set as $\max(|W|)/(2^{b}-1)$, or is chosen to minimize a loss function (such as MSE or cross entropy []) comparing $W$ and $Q(W)$. For binary quantization $(b=1)$, $Q(w)$ is typically a sign function [, , ], and there is no representable range. For binary PWL estimators,a common choice is to use Equation 1 and simply set $\Delta=1$ and $[w_{min},w_{max}]=[-1,1]$ [].

## Appendix B Detailed Overview of Custom Gradient Estimators

Custom binary gradient estimators. A substantial amount of research has gone into custom gradient estimators. Many choices [, , , , , , ] for binary gradient estimators are described in [].
A popular estimator is the “Error Decay Estimator" (EDE) of [], which uses an evolving $\tanh$ function to approximate the sign function.

Custom gradient estimators. The hyperbolic tangent gradient estimator (HTGE) [] gives a piecewise function locally described by tanh functions. This approximation is used for both the forward and backward pass of $Q$ in Differentiable Soft Quantization (DSQ) []. Similar approaches to the HTGE use a sum of sigmoid functions [] and a distance-weighted piecewise linear combination of the outputs of $Q$ [] to approximate $Q$. These techniques make up the most common choices of gradient estimators, which justifies our choice of HTGE for our experiments. The gradient computation in [] leverages a special choice of $\hat{Q}$ based on the distance between the full-precision weight and its quantized version. [] proposes a gradient estimator that includes an extra parameter that attempts to allow the quantization strategy to work well for both low-bit and high-bit quantization. [] uses the STE for the round function, but replaces the clip function in the forward pass with a modified $\tanh$ function, which affects the gradient calculations as well. [] introduces a choice for $\hat{Q}$ known as “Magnitude Aware Differentiation" (MAD) that matches the STE on the representable range of the quantizer and a reciprocal function outside of this range. See Figure 1 for examples of several gradient estimators.

Gradient estimators are proposed alongside other innovations, making them hard to evaluate in isolation. Many papers that introduce a novel gradient estimator $\hat{Q}$ simultaneously introduce further changes to the learning recipe. Some allow the parameters of $Q$ and $\hat{Q}$ to be learnable through gradient descent or explicit computations on the weights, or adjust them on a schedule (See Appendix A). Others, such as DSQ [], use $\hat{Q}$ on the forward pass and gradually update $\hat{Q}$ to more closely approximate $Q$. [] contributes a process for rotating the entire weight vector to align with the binarized weight vector. Bi-Real Net [] also includes a trick with network activations to increase the representational capacity of the model. In addition to the Error Decay Estimator, [] describes a method for maximizing the entropy of quantized parameters to ensure higher parameter diversity.

Implications of our main results. In light of our results 1 and 2, we can sometimes equate these addition algorithms with more well-known training strategies. For example, [] proposes a schedule for a $\tanh$-based gradient estimator to gradually approach a sign function throughout training. Since they use SGD in their experiments, we can think of each update to sharpen the gradient estimator as an effective “shifting" of the weights according to the function defined in Equation 4. This particular shift will push most weights away from 0, which has an effect similar to slowing down the learning rate. Thus this adaptive gradient estimation technique is similar to a standard learning rate decay schedule.

## Appendix C Proof of Theorem 5.1

Proving Theorem 5.1 will require several steps. First, in Theorem C.1 we prove a general statement that allows us to bound the increase in weight alignment error at each training step for any non-adaptive learning rate optimization strategy. This will allow us to quickly prove Theorem 5.1, and will also simplify the proof of a similar statement for SGD with momentum, which will be given in Appendix D.

The proof in its full generality requires heavy notation and somewhat obscures the simple point of the Theorem. Because of this, we provide a less formal proof of the SGD case below.

###### Informal proof of Theorem 5.1 .

We have for all $t$,

$$ $\displaystyle E^{(t+1)}=$ $\displaystyle\left|M\left(w_{\hat{Q}}^{(t+1)}\right)-w_{STE}^{(t+1)}\right|$ (8) $\displaystyle\text{(Expand terms})=$ $\displaystyle\left|M\left(w_{\hat{Q}}^{(t)}-\eta\nabla f_{\hat{Q}}^{(t)}\hat{Q }^{\prime}\left(w_{\hat{Q}}^{(t)}\right)\right)-\left(w_{STE}^{(t)}-\eta\alpha f _{STE}^{(t)}\right)\right|$ (9) $\displaystyle\text{(Taylor's Thm.)}=$ $\displaystyle\left|M\left(w_{\hat{Q}}^{(t)}\right)-\eta\nabla f_{\hat{Q}}^{(t) }\hat{Q}^{\prime}\left(w_{\hat{Q}}^{(t)}\right)M^{\prime}\left(w_{\hat{Q}}^{(t )}\right)-\left(w_{STE}^{(t)}-\eta\alpha f_{STE}^{(t)}\right)+O(\eta^{2})\right|$ (10) $\displaystyle\text{(Apply Eq. \ref{eq:M_derivative})}=$ $\displaystyle\left|M\left(w_{\hat{Q}}^{(t)}\right)-\eta\alpha\nabla f_{\hat{Q} }^{(t)}-\left(w_{STE}^{(t)}-\eta\alpha f_{STE}^{(t)}\right)+O(\eta^{2})\right|$ (11) $\displaystyle\text{(Triangle Ineq.)}\leq$ $\displaystyle E^{(t)}+\eta\alpha\left|\nabla f_{\hat{Q}}^{(t)}-f_{STE}^{(t)} \right|+O(\eta)^{2}$ (12) $$

Here Equation 10 follows from Taylor’s Theorem. Equation 11 follows from Equation 13 below

$$ $\frac{\partial M}{\partial w}(w)=\alpha\cdot\frac{1}{\hat{Q}^{\prime}(w)},$ (13) $$

and Equation 12 follows from the triangle inequality. The complete proof simply requires writing out an explicit form for the $O(\eta^{2})$ term, and is given in detail below.
∎

Theorem C.1 applies to gradient update rules that satisfy a special property in Assumption C.1.3. We will show later in this section that this holds for the SGD formula defined in 3, and in Appendix D for SGD with momentum. Similar proofs show that it holds for a large class of non-adaptive learning rate gradient update rules.

###### Theorem C.1 .

Suppose that

$$ $E^{(t)}:=\left|M\left(w^{(t)}_{\hat{Q}}\right)-w^{(t)}_{STE}\right|$ (14) $$

is the alignment error for $\hat{Q}$-net and $STE$-net with gradient estimators, learning rates, and initial weights given by Table 2. Suppose that Assumptions 5.1.1 and 5.1.2 hold and the model weights are updated according to Equation 2 for some function $g^{(t)}$. In addition, suppose that

- C.1.3
For each $t$, the quantity
$\left|\frac{g^{(t)}(\nabla f^{(0)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,
\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(t)}),\eta)}{\hat{Q}^{\prime}(w^{(
t)})}-g^{(t)}(\nabla f^{(0)}_{\hat{Q}},\ldots,\nabla f^{(t)}_{\hat{Q}},\eta)
\right|=O(c(\eta)).$
(15)

Then we have

$$ $\displaystyle E^{(t+1)}\leq$ $\displaystyle E^{(t)}+\left|\alpha g^{(t)}(\alpha\nabla f^{(0)}_{\hat{Q}}, \ldots,\nabla f^{(t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots, \nabla f^{(t)}_{STE},\alpha\eta)\right|+$ (16) $\displaystyle\frac{L^{\prime}}{2}\cdot\left(\frac{g^{(t)}(\nabla f^{(0)}_{\hat {Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}( w^{(t)}),\eta)}{L_{-}}\right)^{2}+O(c(\eta))$ (17) $$

###### Proof.

By Equation 2, we have

$$ $\displaystyle E^{(t+1)}=$ $\displaystyle\left|M\left(w_{\hat{Q}}^{(t+1)}\right)-w_{STE}^{(t+1)}\right|$ (18) $\displaystyle=$ $\displaystyle\Big{|}M\left(w_{\hat{Q}}^{(t)}+g^{(t)}(\nabla f^{(0)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}(w^{( t)}),\eta)\right)-$ (19) $\displaystyle\left(w_{STE}^{(t)}+g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^ {(t)}_{STE},\alpha\eta)\right)\Big{|}$ (20) $\displaystyle=$ $\displaystyle\Big{|}M\left(w_{\hat{Q}}^{(t)}\right)+g^{(t)}(\nabla f^{(0)}_{ \hat{Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{ \prime}(w^{(t)}),\eta)M^{\prime}\left(w_{\hat{Q}}^{(t)}\right)-$ (21) $\displaystyle\left(w_{STE}^{(t)}+g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^ {(t)}_{STE},\alpha\eta)\right)+R\Big{|}$ (22) $\displaystyle=$ $\displaystyle\Big{|}M\left(w_{\hat{Q}}^{(t)}\right)+\alpha g^{(t)}(\nabla f^{( 0)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^ {\prime}(w^{(t)}),\eta)/\hat{Q}^{\prime}\left(w_{\hat{Q}}^{(t)}\right)-$ (23) $\displaystyle\left(w_{STE}^{(t)}+g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^ {(t)}_{STE},\alpha\eta)\right)+R\Big{|}$ (24) $\displaystyle=$ $\displaystyle\Big{|}M\left(w_{\hat{Q}}^{(t)}\right)+\alpha g^{(t)}(\nabla f^{( 0)}_{\hat{Q}},\ldots,\nabla f^{(t)}_{\hat{Q}},\eta)+O(c(\eta))-$ (25) $\displaystyle\left(w_{STE}^{(t)}+g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^ {(t)}_{STE},\alpha\eta)\right)+R\Big{|}$ (26) $\displaystyle\leq$ $\displaystyle E^{(t)}+\left|\alpha g^{(t)}(\nabla f^{(0)}_{\hat{Q}},\ldots, \nabla f^{(t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^{( t)}_{STE},\alpha\eta)\right|+$ (27) $\displaystyle|R|+O(c(\eta))$ (28) $$

Here Equation 22 follows from Taylor’s Theorem, where $R$ is the remainder term. Equation 24 follows from Equation 13 in the previous proof,
and Equation 26 follows from Assumption C.1.3. Equation 28 follows from the triangle inequality. By Lemma 2.1 of [], we can bound $R$ by

$$ $|R|\leq\frac{L^{\prime}}{2L_{-}^{2}}\left(g^{(t)}(\nabla f^{(0)}_{\hat{Q}}\hat {Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(t)}) ,\eta)\right)^{2},$ (29) $$

To see this, we need to show that $M^{\prime}$ is Lipschitz continuous with Lipschitz constant $L^{\prime}/L_{-}^{2}$. This holds since for any $w,v\in\mathbb{R}$,

$$ $|M^{\prime}(w)-M^{\prime}(v)|=\left|\frac{1}{Q^{\prime}(w)}-\frac{1}{Q^{\prime }(w)}\right|=\left|\frac{Q^{\prime}(v)-Q^{\prime}(w)}{Q^{\prime}(w)Q^{\prime}( v)}\right|\leq\frac{L^{\prime}}{L_{-}^{2}}|w-v|.$ $$

In the last step we use both Assumptions 5.1.1 and 5.1.2.
Putting this all together, we have Equation 17.
∎

We can now apply Theorem C.1 for the SGD update rule (Equation 3) to give a proof of Theorem 5.1.

###### Proof of Theorem 5.1 .

To prove Theorem 5.1, we first show that Assumption C.1.3 holds for the SGD update rule with $c(\eta)=0$. We have

$$ $\displaystyle\left|\frac{g^{(t)}(\nabla f^{(0)}_{\hat{Q}}\hat{Q}^{\prime}(w^{( 0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(t)}),\eta)}{\hat{Q}^{ \prime}(w^{(t)})}-g^{(t)}(\nabla f^{(0)}_{\hat{Q}},\ldots,\nabla f^{(t)}_{\hat {Q}},\eta)\right|=$ (30) $\displaystyle\left|\frac{\eta\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(t)}) }{\hat{Q}^{\prime}(w^{(t)})}-\eta\nabla f^{(t)}_{\hat{Q}}\right|=$ $\displaystyle 0.$ (31) $$

Now we can apply Theorem C.1. We have

$$ $\displaystyle E^{(t+1)}\leq$ $\displaystyle E^{(t)}+\left|\alpha g^{(t)}(\alpha\nabla f^{(0)}_{\hat{Q}}, \ldots,\nabla f^{(t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots, \nabla f^{(t)}_{STE},\alpha\eta)\right|+$ (32) $\displaystyle\frac{L^{\prime}}{2}\cdot\left(\frac{g^{(t)}(\nabla f^{(0)}_{\hat {Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}( w^{(t)}),\eta)}{L_{-}}\right)^{2}+O(c(\eta))$ (33) $\displaystyle=$ $\displaystyle E^{(t)}+\eta\alpha\left|\nabla f^{(t)}_{\hat{Q}}-\nabla f^{(t)}_ {STE}\right|+\frac{L^{\prime}}{2}\cdot\left(\frac{\eta\nabla f^{(t)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(t)})}{L_{-}}\right)^{2}+0$ (34) $\displaystyle\leq$ $\displaystyle E^{(t)}+\eta\alpha\left|\nabla f^{(t)}_{\hat{Q}}-\nabla f^{(t)}_ {STE}\right|+\frac{L^{\prime}}{2}\cdot\left(\frac{\eta L_{+}\nabla f^{(t)}_{ \hat{Q}}}{L_{-}}\right)^{2}$ (35) $$

This gives us Equation 6, as desired. ∎

###### Informal proof of Theorem 5.1 .

###### Theorem C.1 .

###### Proof.

###### Proof of Theorem 5.1 .

## Appendix D Theorem 5.1 for SGD with momentum

Here we give a version of Theorem 5.1 for stochastic gradient descent with momentum. The weight update rule for this learning algorithm is given by

$$ $g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}\hat{Q}^{ \prime}(w^{(t)}),\eta)=-\eta m_{t}$ (36) $$

where $m_{t}$ is defined recursively as

$$ $m_{t}=\beta m_{t-1}+(1-\beta)\nabla f^{(t)}\hat{Q}^{\prime}(w^{(t)})$ (37) $$

for a hyperparameter $\beta\in[0,1)$, which is often set to 0.9 or a similar value []. We can expand this recursive definition, and obtain the single rule

$$ $g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}\hat{Q}^{ \prime}(w^{(t)}),\eta)=-\eta(1-\beta)\sum_{i=0}^{t}\beta^{t-i}\nabla f^{(i)} \hat{Q}^{\prime}(w^{(i)})$ (38) $$

Theorems D.1 and D.2 show that Assumption C.1.3 holds for this update rule under mild conditions. From this we can apply Theorem C.1 for SGD with momentum to obtain Theorem D.3, a result similar to Theorem 5.1.

###### Theorem D.1 .

Define $g^{(t)}$ by Equation 38. Suppose that Assumption 5.1.1 holds. Further suppose that each $\nabla f^{(t)}$ is bounded by

$$ $|\nabla f^{(t)}|<\frac{g_{+}}{L_{+}(1-\beta^{t+1})}.$ (39) $$

Then

$$ $|g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}\hat{Q}^ {\prime}(w^{(t)}),\eta)|<\eta g_{+}$ $$

###### Proof.

By the triangle inequality and Assumption 5.1.1, we have

$$ $|g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}\hat{Q}^ {\prime}(w^{(t)}),\eta)|<\eta L_{+}(1-\beta)\sum_{i=0}^{t}\beta^{t-i}|\nabla f ^{(i)}|.$ $$

Now applying the bound given in Equation 39, we have

$$ $|g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}\hat{Q}^ {\prime}(w^{(t)}),\eta)|<\eta g_{+}\frac{1-\beta}{1-\beta^{t+1}}\sum_{i=0}^{t} \beta^{t-i}.$ $$

Since

$$ $\sum_{i=0}^{t}\beta^{t-i}=\frac{1-\beta^{t+1}}{1-\beta}$ $$

for all $\beta<1$, we have

$$ $|g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}\hat{Q}^ {\prime}(w^{(t)}),\eta)|<\eta g_{+}$ (40) $$

as desired.
∎

###### Theorem D.2 .

Define $g^{(t)}$ by Equation 38. Suppose that

- D.2.1
$0<L_{-}\leq\hat{Q}^{\prime}(w)$ for all $w$
- D.2.2
$\hat{Q}^{\prime}(w)$ is $L^{\prime}$-Lipschitz
- D.2.3
For each $t$, Each $g^{(t)}$ is bounded by $|w^{(t+1)}-w^{(t)}|<\eta g_{+}$.

Then for each $t$, we have

$$ $\left|\frac{g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{( t)}\hat{Q}^{\prime}(w^{(t)}),\eta)}{\hat{Q}^{\prime}(w^{(t)})}-g^{(t)}(\nabla f ^{(0)},\ldots,\nabla f^{(t)},\eta)\right|=O(\eta^{2}).$ (41) $$

so that Assumption C.1.3 holds with $c(\eta)=\eta^{2}$.

###### Proof.

We have by Equation 38

$$ $\frac{g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)} \hat{Q}^{\prime}(w^{(t)}),\eta)}{\hat{Q}^{\prime}(w^{(t)})}=-\eta(1-\beta)\sum _{i=0}^{t}\beta^{t-i}\nabla f^{(i)}\frac{\hat{Q}^{\prime}(w^{(i)})}{\hat{Q}^{ \prime}(w^{(t)})}.$ (42) $$

We would like to show that for each $i$,

$$ $\beta^{t-i}\frac{\hat{Q}^{\prime}(w^{(i)})}{\hat{Q}^{\prime}(w^{(t)})}=\beta^{ t-i}(1+O(\eta))$ $$

since then we would have

$$ $\displaystyle\left|\frac{g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}), \ldots,\nabla f^{(t)}\hat{Q}^{\prime}(w^{(t)}),\eta)}{\hat{Q}^{\prime}(w^{(t)} )}-g^{(t)}(\nabla f^{(0)},\ldots,\nabla f^{(t)},\eta)\right|=$ (43) $\displaystyle\left|-\eta(1-\beta)\sum_{i=0}^{t}\beta^{t-i}\nabla f^{(i)}\frac{ \hat{Q}^{\prime}(w^{(i)})}{\hat{Q}^{\prime}(w^{(t)})}+\eta(1-\beta)\sum_{i=0}^ {t}\beta^{t-i}\nabla f^{(i)}\right|=$ (44) $\displaystyle\left|-\eta(1-\beta)\sum_{i=0}^{t}\beta^{t-i}\nabla f^{(i)}(1+O( \eta))+\eta(1-\beta)\sum_{i=0}^{t}\beta^{t-i}\nabla f^{(i)}\right|=$ $\displaystyle O(\eta^{2})$ (45) $$

The first step is to note that $\log(\hat{Q}^{\prime})$ is Lipschitz with Lipschitz constant $L^{\prime}/L_{-}$. To see this, first note that $\log(x)$ is $1/L_{-}$-Lipschitz on the range $[L_{-},\infty]$. Then by Assumptions D.2.1 and D.2.2 and the fact that the composition of Lipschitz functions is Lipschitz with the product constant, we have

$$ $|\log(\hat{Q}^{\prime}(w))-\log(\hat{Q}^{\prime}(v))|\leq\frac{L^{\prime}}{L_{ -}}|w-v|$ $$

which is our desired Lipschitz property.
Making use of this property, Assumption D.2.3, and Equation 2, we have

$$ $\displaystyle|\log(\hat{Q}^{\prime}(w^{(i)}))-\log(\hat{Q}^{\prime}(w^{(t)}))|\leq$ $\displaystyle\frac{L^{\prime}}{L_{-}}|w^{(i)}-w^{(t)}|$ (47) $\displaystyle=$ $\displaystyle\frac{L^{\prime}}{L_{-}}\left|\sum_{j=i}^{t-1}w^{(i)}-w^{(i+1)}\right|$ (48) $\displaystyle\leq$ $\displaystyle\frac{L^{\prime}}{L_{-}}\sum_{j=i}^{t-1}\left|w^{(i)}-w^{(i+1)}\right|$ (49) $\displaystyle\leq$ $\displaystyle\eta\frac{L^{\prime}}{L_{-}}(t-i)g_{+}.$ (50) $$

Solving for the quotient $\hat{Q}^{\prime}(w^{(i)})/\hat{Q}^{\prime}(w^{(t)})$, we have

$$ $-\eta L^{\prime}(t-i)g_{+}/L_{-}\leq\log(\hat{Q}^{\prime}(w^{(i)}))-\log(\hat{ Q}^{\prime}(w^{(t)}))\leq\eta L^{\prime}(t-i)g_{+}/L_{-}$ $$

$$ $\exp(-\eta L^{\prime}(t-i)g_{+}/L_{-})\leq\frac{\hat{Q}^{\prime}(w^{(i)})}{ \hat{Q}^{\prime}(w^{(t)})}\leq\exp(\eta L^{\prime}(t-i)g_{+}/L_{-})$ $$

$$ $\beta^{-\eta L^{\prime}(t-i)g_{+}/(\log(\beta)L_{-})}\leq\frac{\hat{Q}^{\prime }(w^{(i)})}{\hat{Q}^{\prime}(w^{(t)})}\leq\beta^{\eta L^{\prime}(t-i)g_{+}/( \log(\beta)L_{-})}$ $$

Thus we have shown that

$$ $\frac{\hat{Q}^{\prime}(w^{(i)})}{\hat{Q}^{\prime}(w^{(t)})}=\left(\frac{\beta_ {t,i}}{\beta}\right)^{t-i}$ $$

where

$$ $\beta_{t,i}=\beta+O(\eta).$ $$

Therefore we have

$$ $\beta^{t-i}\frac{\hat{Q}^{\prime}(w^{(i)})}{\hat{Q}^{\prime}(w^{(t)})}=\beta_{ t,i}^{t-i}=(\beta+O(\eta))^{t-i}=\beta^{t-i}(1+O(\eta)),$ $$

as desired. The final equality holds since $(\beta+O(\eta))^{t-i}$ is a polynomial in $\beta$ and $O(\eta)$, which can be computed by expanding the product. Each term in the resulting sum is either $\beta^{t-i}$, $O(\eta)$, or $o(\eta)$.
∎

We now have all that we need to the following analog of Theorem 5.1 for gradient descent with momentum.

###### Theorem D.3 .

Suppose that $E^{(t)}$ is defined by Equation 14, for $\hat{Q}$-net and $STE$-net with gradient estimators, learning rates, and initial weights given by Table 2.
Suppose that Assumptions 5.1.1 and 5.1.2 hold and the model weights are updated according to Equation 2, where $g^{(t)}$ is defined by Equation 38. In addition, suppose that each $\nabla f^{(t)}_{\hat{Q}}$ is bounded by Equation 39.
Then we have

$$ $E^{(t+1)}\leq E^{(t)}+\alpha\eta\left|(1-\beta)\sum_{i=0}^{t}\beta^{t-i}( \nabla f^{(i)}_{\hat{Q}}-\nabla f^{(t)}_{STE})\right|+\frac{L^{\prime}}{2} \cdot\left(\frac{\eta g_{+}}{L_{-}}\right)^{2}+O(\eta^{2})$ (51) $$

###### Proof.

Assumption C.1.3 holds by Theorem D.2 with $c(\eta)=\eta^{2}$, so that Theorem C.1 holds. Note that Assumption D.2.3 holds by a combination of Theorem D.1 and Equation 2. We can now obtain Equation 51 from Equation 17 by simplifying terms and applying the appropriate bounds:

$$ $\displaystyle E^{(t+1)}\leq$ $\displaystyle E^{(t)}+\left|\alpha g^{(t)}(\alpha\nabla f^{(0)}_{\hat{Q}}, \ldots,\nabla f^{(t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots, \nabla f^{(t)}_{STE},\alpha\eta)\right|+$ (52) $\displaystyle\frac{L^{\prime}}{2}\cdot\left(\frac{g^{(t)}(\nabla f^{(0)}_{\hat {Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}}\hat{Q}^{\prime}( w^{(t)}),\eta)}{L_{-}}\right)^{2}+O(c(\eta))$ (53) $\displaystyle\leq$ $\displaystyle E^{(t)}+\left|-\alpha\eta(1-\beta)\sum_{i=0}^{t}\beta^{t-i} \nabla f^{(i)}_{\hat{Q}}+\alpha\eta(1-\beta)\sum_{i=0}^{t}\beta^{t-i}\nabla f^ {(i)}_{STE}\right|+$ (54) $\displaystyle\frac{L^{\prime}}{2}\cdot\left(\frac{\eta g_{+}}{L_{-}}\right)^{2 }+O(\eta^{2})$ (55) $\displaystyle=$ $\displaystyle E^{(t)}+\alpha\eta\left|(1-\beta)\sum_{i=0}^{t}\beta^{t-i}( \nabla f^{(i)}_{\hat{Q}}-\nabla f^{(t)}_{STE})\right|+\frac{L^{\prime}}{2} \cdot\left(\frac{\eta g_{+}}{L_{-}}\right)^{2}+O(\eta^{2}).$ (56) $$

∎

###### Theorem D.1 .

###### Proof.

###### Theorem D.2 .

###### Proof.

###### Theorem D.3 .

###### Proof.

## Appendix E Adam

In this Appendix we prove Theorem 5.2 in a manner similar to the proofs given in Appendix C.1. The weight update function for the Adam optimizer is defined by

$$ $\displaystyle m_{t}=$ $\displaystyle\beta_{1}m_{t-1}+(1-\beta_{1})\nabla f^{(t)}\hat{Q}^{\prime}(w^{( t)})$ (57) $\displaystyle v_{t}=$ $\displaystyle\beta_{2}v_{t-1}+(1-\beta_{2})(\nabla f^{(t)}\hat{Q}^{\prime}(w^{ (t)}))^{2}$ (58) $\displaystyle\hat{m}_{t}=$ $\displaystyle m_{t}/(1-\beta_{1}^{t})$ (59) $\displaystyle\hat{v}_{t}=$ $\displaystyle v_{t}/(1-\beta_{2}^{t})$ (60) $\displaystyle g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^ {(t)}\hat{Q}^{\prime}(w^{(t)}),\eta)=$ $\displaystyle-\eta\hat{m}_{t}/\left(\sqrt{\hat{v}_{t}}+\epsilon\right)$ (61) $$

where $\beta_{1},\beta_{2}\in[0,1)$ are hyperparameters and $\epsilon$ is a small constant.

We will first state and prove Theorem E.1, ageneral-purpose precursor to Theorem 5.2 that applies to a large class of adaptive learning rate optimizers. Then we will borrow work from the proof of Theorem D.2 to specify this result for the Adam optimizer and prove Theorem 5.2.

Throughout this section, we will follow [] and assume for the sake of mathematical argument that the constant $\epsilon$ in Equation 61 is zero.

###### Theorem E.1 .

Suppose that

$$ $E^{(t)}:=\left|w^{(t)}_{\hat{Q}}-w^{(t)}_{STE}\right|$ (62) $$

is the alignment error for $\hat{Q}$-net and $STE$-net with gradient estimators, learning rates, and initial weights given by Table 2. Suppose that the model weights are updated according to Equation 2 for some function $g^{(t)}$. In addition, suppose that

- E.1.3
For each $t$, the quantity
$\left|g^{(t)}(\nabla f^{(0)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f
^{(t)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(t)}),\eta)-g^{(t)}(\nabla f^{(0)}_{\hat{Q
}},\ldots,\nabla f^{(t)}_{\hat{Q}},\eta)\right|=O(c(\eta)).$
(63)

Then we have

$$ $\displaystyle E^{(t+1)}\leq$ $\displaystyle E^{(t)}+\left|g^{(t)}(\nabla f^{(0)}_{\hat{Q}},\ldots,\nabla f^{ (t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^{(t)}_{STE}, \eta)\right|+O(c(\eta))$ (64) $$

###### Proof.

By Equation 2, we have

$$ $\displaystyle E^{(t+1)}=$ $\displaystyle\left|w_{\hat{Q}}^{(t+1)}-w_{STE}^{(t+1)}\right|$ (65) $\displaystyle=$ $\displaystyle\Big{|}w_{\hat{Q}}^{(t)}+g^{(t)}(\nabla f^{(0)}_{\hat{Q}}\hat{Q}^ {\prime}(w^{(0)}),\ldots,\nabla f^{(t)}_{\hat{Q}},\eta)-$ (66) $\displaystyle\left(w_{STE}^{(t)}+g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^ {(t)}_{STE},\eta\right)\Big{|}$ (67) $\displaystyle=$ $\displaystyle\Big{|}w_{\hat{Q}}^{(t)}+g^{(t)}(\nabla f^{(0)}_{\hat{Q}},\ldots, \nabla f^{(t)}_{\hat{Q}},\eta)+O(c(\eta))-$ (68) $\displaystyle\left(w_{STE}^{(t)}+g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^ {(t)}_{STE},\eta)\right)\Big{|}$ (69) $\displaystyle\leq$ $\displaystyle E^{(t)}+\left|g^{(t)}(\nabla f^{(0)}_{\hat{Q}},\ldots,\nabla f^{ (t)}_{\hat{Q}},\eta)-g^{(t)}(\nabla f^{(0)}_{STE},\ldots,\nabla f^{(t)}_{STE}, \eta)\right|+O(c(\eta))$ (70) $$

Here Equation 70 follows from the triangle inequality, and Equation 69 follows from Assumption C.1.3. ∎

Now we can prove Theorem 5.2.

###### Proof of Theorem 5.2 .

To prove Theorem 5.2, we need to show that the assumptions of Theorem 5.2 imply the Assumption E.1.3 of Theorem E.1 with the Adam update rule defined in Equations 57-61 and $c(\eta)=\eta^{2}$.

We first
expand Equations 57 and 58, which will allow us to express $g^{(t)}$ more explicitly as a function of the $\nabla f^{(i)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(i)})$:

$$ $\displaystyle m_{t}=$ $\displaystyle(1-\beta_{1})\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q} }\hat{Q}^{\prime}(w^{(i)})$ (71) $\displaystyle v_{t}=$ $\displaystyle(1-\beta_{2})\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}_{\hat{Q }}\hat{Q}^{\prime}(w^{(i)}))^{2}$ (72) $$

$$ $\displaystyle g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^ {(t)}\hat{Q}^{\prime}(w^{(t)}),\eta)=$ $\displaystyle-\frac{1-\beta_{1}}{1-\beta_{1}^{t}}\cdot\sqrt{\frac{1-\beta_{2}^ {t}}{1-\beta_{2}}}\cdot$ (73) $\displaystyle\frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(i)})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}_ {\hat{Q}}\hat{Q}^{\prime}(w^{(i)}))^{2}}+\epsilon}$ (74) $$

Clearly the two fraction terms of Equation 73 are not dependent on $\hat{Q}^{\prime}$ in any way, so we need only concern ourselves with the final fraction term in Equation 74. As stated earlier, we are ignoring the $\epsilon$ term, which allows us to write the final fraction as

$$ $\displaystyle\frac{\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}}\hat{Q }^{\prime}(w^{(i)})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}_{\hat{ Q}}\hat{Q}^{\prime}(w^{(i)}))^{2}}}=$ $\displaystyle\frac{\hat{Q}^{\prime}(w^{(t)})}{\hat{Q}^{\prime}(w^{(t)})}\cdot \frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}}\hat{Q}^{\prime }(w^{(i)})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}_{\hat{Q}}\hat{Q }^{\prime}(w^{(i)}))^{2}}}$ (75) $\displaystyle=$ $\displaystyle\frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(i)})/\hat{Q}^{\prime}(w^{(t)})}{\sqrt{\sum_{i=0}^{t}\beta _{2}^{t-i}(\nabla f^{(i)}_{\hat{Q}}\hat{Q}^{\prime}(w^{(i)})/\hat{Q}^{\prime}( w^{(t)}))^{2}}}$ (76) $$

We would like to apply Theorem D.2 to both the numerator and denominator of the final term in the above Equation. Assumptions D.2.1 and D.2.2 are the same as Assumptions 5.2.1 and 5.2.2, respectively. By Equation 2, we can see that Assumption D.2.3 with $g_{+}=\max\{1,(1-\beta_{1})/\sqrt{(1-\beta_{2}}\}$ is an inherent property of the Adam optimizer []. Now by applying Theorem D.2 to the numerator, we have

$$ $\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}}\hat{Q}^{\prime}(w^{( i)})/\hat{Q}^{\prime}(w^{(t)})=\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)} +O(\eta^{2}).$ $$

we see that the numerator limits to $\sum_{i=0}^{t}\beta^{t-i}\nabla f^{(i)}$ as $\eta\to 0$. We can show via a very similar proof that the denominator can be approximated as

$$ $\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)})^{2}+O(\eta)}.$ $$

The only notable differences are that we are removing an $\eta$ term, and the exponent in the bound for $\hat{Q}^{\prime}(w^{(i)})/\hat{Q}^{\prime}(w^{(t)})$ has an extra 2 in it, which does not affect the result. Therefore we have

$$ $\displaystyle g^{(t)}(\nabla f^{(0)}\hat{Q}^{\prime}(w^{(0)}),\ldots,\nabla f^ {(t)}\hat{Q}^{\prime}(w^{(t)}),\eta)=$ $\displaystyle-\frac{1-\beta_{1}}{1-\beta_{1}^{t}}\cdot\sqrt{\frac{1-\beta_{2}^ {t}}{1-\beta_{2}}}\cdot$ (77) $\displaystyle\frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(i)})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}_ {\hat{Q}}\hat{Q}^{\prime}(w^{(i)}))^{2}}}$ (78) $\displaystyle=$ $\displaystyle-\frac{1-\beta_{1}}{1-\beta_{1}^{t}}\cdot\sqrt{\frac{1-\beta_{2}^ {t}}{1-\beta_{2}}}\cdot$ (79) $\displaystyle\frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(i)})+O(\eta^{2})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}( \nabla f^{(i)})^{2}+O(\eta)}}$ (80) $\displaystyle\frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(i)})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}_ {\hat{Q}}\hat{Q}^{\prime}(w^{(i)}))^{2}}}$ (81) $\displaystyle=$ $\displaystyle-\frac{1-\beta_{1}}{1-\beta_{1}^{t}}\cdot\sqrt{\frac{1-\beta_{2}^ {t}}{1-\beta_{2}}}\cdot$ (82) $\displaystyle\frac{\eta\sum_{i=0}^{t}\beta_{1}^{t-i}\nabla f^{(i)}_{\hat{Q}} \hat{Q}^{\prime}(w^{(i)})}{\sqrt{\sum_{i=0}^{t}\beta_{2}^{t-i}(\nabla f^{(i)}) ^{2}}}+O(\eta^{2})$ (83) $\displaystyle=$ $\displaystyle g^{(t)}(\nabla f^{(0)},\ldots,\nabla f^{(t)},\eta)+O(\eta^{2})$ (84) $$

so that Assumption E.1.3 holds with $c(\eta)=\eta^{2}$. The only potential issue with this derivation is in the removal of the denominator $O(\eta)$ term in Equation 83. In order for this to work, we need the denominator to be nonzero. However, if the denominator is zero, then Assumption E.1.3 holds trivially. This concludes the proof.

Note: The reader may be concerned as to why the $\hat{Q}^{\prime}(w^{(i)})$ terms disappeared from $g^{(t)}$ but the $\nabla f^{(i)}$ terms did not. The reason is that the $\hat{Q}^{\prime}(w^{(i)})$ terms vary continuously with the latent weight, whereas the $\nabla f^{(i)}$ terms are stochastic.
∎

###### Theorem E.1 .

###### Proof.

###### Proof of Theorem 5.2 .

## Appendix F Learning Rate Schedules

Learning rate schedules. All of the learning algorithms described in Section 3 can make use of a learning rate schedule [, ], [, , ]. A learning rate schedule essentially amounts to scaling each the gradient update steps $g^{(t)}$ by a pre-determined positive number $\eta_{t}$. In this case, the initial learning rate $\eta$ acts as a scale on the entire learning rate schedule.

Theorems C.1 and E.1 are general-purpose tools for proving results like Theorems 5.1 and 5.2 for non-adaptive learning rate optimizers and adaptive learning rate optimizers, respectively. Up until this point, we have only focused on fixed learning rate schedules, and here we describe how the theorems be applied to general learning rate schedules.

As stated in Section 3, a learning rate schedule applies a pre-determined scale $\eta_{t}$ to each of the gradient update steps $g^{(t)}$, which can effectively be absored into the $\nabla f^{(t)}$ terms for non-adaptive optimizers. This does not affect Assumptions 5.1.1, 5.1.2, 5.2.1, or 5.2.2 in any way. It may affect the bounds on $\nabla f^{(t)}_{\hat{Q}}$ in Theorem D.3, but this would simply require a different value of $g_{+}$.

Thus we can confidently generalize our main results to gradient update rules that take advantage of learning rate schedules.

## Appendix G On nonpositive gradient estimators

Here we describe the statements we can make that bear relation to Theorems 5.1 and 5.2 for gradient estimators that break the lower bound conditions in Assumptions 5.1.1 and 5.2.1.

The common case for nonpositive gradient estimators. Assumptions 5.1.1 and 5.2.1 are most commonly broken when $\hat{Q}^{\prime}$, like the PWL estimator (See Section 2), is positive on some range $[w_{min},w_{max}]$ and zero outside of this range. The behavior of these gradient estimators cannot be mimicked by any model that uses the STE, since the latent weight can reach a point where it no longer receives updates from gradients. However, this behavior can be mimicked by a model that uses PWL estimator. If we set

$$ $\displaystyle\tilde{w}_{min}:=$ $\displaystyle M(w_{min})$ (85) $\displaystyle\tilde{w}_{max}:=$ $\displaystyle M(w_{max}),$ (86) $$

then Theorems 5.1 and 5.2 clearly apply after replacing the STE with $PWL_{\tilde{w}_{min},\tilde{w}_{max}}$ (for SGD), $PWL_{w_{min},w_{max}}$ (for Adam), whenever $w^{(t)}_{\hat{Q}}$ and $w^{(t)}_{STE}$ are in the representable range. Technically, $M(w_{\hat{Q}}^{(0)})$ is only defined when $w^{(0)}_{\hat{Q}}\in[w_{min},w_{max}]$, but we can ignore this case under the assumption that no practitioner would initialize a weight to be untrainable. There are two remaining cases to consider. The first is where $w^{(t)}_{\hat{Q}}$ and $w^{(t)}_{STE}$ both lay outside of the representable range, in which case neither weight can move and there is no risk of increasing $E^{(t)}$. The second is where only one lies in this range, and one weight is “trapped" while the other is “free". This is unlikely to happen due to the bounds on $E^{(t)}$, but it could technically lead to high weight alignment errors.

Negative gradient estimators. The other way that the lower bound in Assumption 5.1.1 can be broken is if $\hat{Q}(w)$ is actually negative for some range of values of $w$. There is some work [, ] that proposes gradient estimators with negative derivatives, but most choose a nonnegative derivative to align with the nondecreasing behavior of the quantizer function. In the cases with negative $\hat{Q}^{\prime}$ values, slightly modified versions of Theorems 5.1 and 5.2 apply on the negative ranges, where the gradient estimator of $STE$-net is the negative of the STE. Since this is a rare choice for QAT, we do not provide the details here.

Thus almost all common gradient estimators can be replaced with the STE or a PWL estimator.

## Appendix H Calculating constants in Theorem 5.1

Many gradient estimators take the form

$$ $\hat{Q}(w)=\tanh(k\cdot(w-a)+a$ $$

for $w$ in the representable range, and $a$ is the center of the quantization bin $w$ is in. This is the case for [] and [], hence our choice of the gradient estimator from [] for the experiments. This is also very similar to the gradient estimator used in [].

Given this definition of $\hat{Q}(w)$, we want to provide lower and upper bounds on the first and second derivatives of $Q$ on the interval $[-\Delta/2,\Delta/2]$ with $a=0$. First note that we have

$$ $\hat{Q}^{\prime}(w)=\frac{k}{\cosh^{2}(kw)}$ $$

This obtains a maximum value at $w=1$, and a minimum value at $\pm\Delta/2$, so that $L_{+}=k$ and $L_{-}=k/\cosh^{2}(k\Delta/2)$.

$$ $\hat{Q}^{\prime\prime}(w)=-2k^{2}\frac{\tanh(kw)}{\cosh^{2}(kw)}$ $$

This obtains its maximum values at

$$ $w=\pm\frac{1}{2k}\log(2+\sqrt{3})$ $$

and is strictly decreasing on the interval between these points. Since a bound on $|\hat{Q}^{\prime\prime}(w)|$ is a Lipschitz constant for $\hat{Q}^{\prime}$, $L^{\prime}$ is given by

$$ $2k^{2}\frac{\tanh(kw)}{\cosh^{2}(kw)}$ $$

where

$$ $w=\min\left(\Delta/2,\frac{1}{2k}\log(2+\sqrt{3})\right)$ $$

In [], $k$ is set to to 8, 6, 4, and 2 for 8, 4, 3, and 2-bit quantization. They initialize $\Delta$ to $2/(2^{b}-1)$ where $b$ is the number of bits used for quantization. This gives us the following values for $L^{\prime}L_{+}/2L_{-}^{2}$: 0.25 (8 bits), 2.66 (4 bits), 2.82 (3 bits), 1.77 (2 bits).
These values are small relative to standard values of $1/\eta$, where $\eta$ is the learning rate.

For [], the quantizer is parametrized by a value $\alpha$ defined by

$$ $\alpha=1-\tanh(k\Delta/2).$ $$

This gives us convenient formulas:

$$ $\tanh(k\Delta/2)=1-\alpha$ $$

$$ $\frac{1}{\cosh(k\Delta/2)^{2}}=1-(1-\alpha)^{2}=2\alpha-\alpha^{2}$ $$

$$ $\frac{\tanh(k\Delta/2)}{\cosh(k\Delta/2)^{2}}=(1-\alpha)(2\alpha-\alpha^{2})$ $$

$$ $\frac{L_{+}}{L_{-}}=\frac{1}{2\alpha-\alpha^{2}}$ $$

$$ $\frac{L^{\prime}L_{+}}{L_{-}^{2}}\leq\frac{1-\alpha}{2\alpha-\alpha^{2}}$ $$

The constant of interest is then given by

$$ $\frac{L^{\prime}L_{+}}{L_{-}^{2}}\leq\frac{1-\alpha}{2\alpha-\alpha^{2}}$ $$

During training in [], $\alpha$ is varied for weight quantizers between $0.11$ and $0.25$, giving us

$$ $\frac{L^{\prime}L_{+}}{L_{-}^{2}}\in[1.71,4.28].$ $$

These values are again small relative to $1/\eta$.

## Appendix I Experiment Setup Details

Weight Initialization and Quantizers: We initialize the weights of $\hat{Q}$-net using He Uniform Initialization(^1^11[https://www.tensorflow.org/api_docs/python/tf/keras/initializers/HeNormal](https://www.tensorflow.org/api_docs/python/tf/keras/initializers/HeNormal)).
For quantization, we use a uniform weight quantizer with representable range limits given by bounds of the weight initialization distribution. We do not quantize activations. We focus primarily on two-bit weight quantization, and note that results are similar for 1-bit and 4-bit quantization. For gradient estimation, we use the $\hat{Q}$ given by the HTGE [] gradient estimator formula with shape parameter $t$ set to 5.5 times the maximum value from the weight initialization distribution. This value was chosen so that $\hat{Q}$ differs significantly from the STE, but not so significantly that parts of $\hat{Q}$ become essentially flat.

Optimization techniques. For optimization techniques on both models, we consider both SGD with momentum$=0.9$ and Adam with $\beta_{1}=0.9$ and $\beta_{2}=0.95$. For all experiments, we use a cosine decay learning rate schedule [] with a linear learning rate warmup [] for 2% of training epochs. The reported learning rate for each model is the initial learning rate for the cosine decay. We use a learning rate of 0.001 for our default MNIST SGD with momentum model, and 0.0001 for our default MNIST Adam model. For the ResNet50 on ImageNet model we apply the standard learning rate schedule implemented in [] with a configured learning rate of 0.0001, for Adam and 0.001 for SGD and otherwise default parameters.

Identical Initial Training period. For the ImageNet-ResNet setup, we ensured that the first 10% of training for $\hat{Q}$-net and $STE$-net were identical. To do this, we trained $STE$-net by first training $\hat{Q}$-net for the first 10 of 100 epochs, and then applied $M$ to the weights and optimizer state and switched the model’s quantizer for the STE before continuing training. This was applied for all model comparisons.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. Could you provide unadjusted(A) in Table 4?
2. Besides average error, could you draw a histogram which can better validate the claims?
3. How do you empirically decide when the weight difference is going to affect the conclusion? E.g., Adam shows larger weight difference, while ImageNet shows larger weight difference. It does not seem clear to me they all supports the claim that STE works the same as other gradient estimators on various settings.
soundness: 2
strengths: 1. The claim is strong that other gradient estimators works similar as STE in QAT.
2. Experiments show that the weight difference is small to support the claim.
summary: The authors theoretically analyze the weight difference in QAT when trained with different gradient estimators. Under certain conditions, the authors show that the weight difference is small which means that there's no need to try another gradient estimator other than STE. Empirical results show that the weight difference is small when adopting the proposed weight initialization.
weaknesses: 1. The mirror room story does not appear closely connected to the theoretical analysis.
2. Assumption 5.1.1 violates Figure 1 where the gradient could be zero.
3. From Table 4, Adam leads to larger weight difference.
4. For more complicated task like ImageNet, the weight difference is much larger than MNIST.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. In Eq. (5), why the $E^{(t)}$ is defined differently for SGD and Adam?

2. Line 200, "Most multi-bit gradient estimators proposed in the literature are cyclical." Can you specify exactly which estimators are cyclical?

3. Typos in Eq. (9)-(12), $f_{STE}^{(t)}$ should be $\nabla f_{STE}^{(t)}$.

4. In assumption 5.1.1, should $| \hat{Q}^\prime (w) |$ be $\hat{Q}^\prime (w)$ without the absolute value?

5. Does Table 4 suggest that more than 95% quantized weights from $\hat{Q}$-net and STE-net are *identical*? This finding seems counterintuitive.
soundness: 2
strengths: 1. The paper is overall well presented.
2. The concept of mirror effect is interesting.
summary: This paper studies behavior of gradient estimators, including straight through
estimator (STE), for weight quantization. It is shown that a large class of
weight gradient estimators is approximately equivalent to the STE during training using SGD and Adam.
weaknesses: A primary concern is that the key claims and several major concepts lack mathematical rigor. Additionally, the main theoretical results provided are too limited to substantiate the claims:

1. Contribution 1 states that '... all nonzero weight gradient estimators lead to approximately equivalent weight movement for non-adaptive learning rate optimizers ...'. However, the term 'approximately equivalent weight movement' lacks a precise mathematical definition. It would be helpful to formalize this concept, perhaps by specifying the conditions under which these movements are considered 'approximately equivalent.' 

2. According to Section 6.2, 'approximately equivalent weight movement' appears to refer to high 'Quantized Weight Agreement' or a small 'Normalized Weight Alignment Error ($\bar{E}$)'. Again, these metrics require explicit mathematical expressions for each. Additionally, this interpretation is not fully supported by the main theoretical results (e.g., Theorem 5.1), which only derive the increment in weight alignment error between two consecutive iterations, rather than a direct measure of agreement or alignment over the entire optimization trajectory. 

3. For the error bounds in Eq. (6) and (7), there is insufficient justification for why the gradient error terms should be small, nor any clear indication of how small these terms are. It is insufficient to merely claim that a term is 'small' and then disregard it. These errors could accumulate significantly over iterations, potentially undermining the main conclusions.

4. The use of mathematical notation is poor, which possibly lead to incorrect derivations. For example:
   - The Euclidean norm should be denoted by $\|| \cdot \||$ rather than $\| \cdot \|$ as in Eq. (5)-(12) and other instances.
   - It should be explicitly stated that  $Q$ and $M$ are applied *element-wise* to the weight vector. Additionally, it would be preferable to use bold letters to represent vectors and to distinguish them from scalars.
   - In Eq. (10), you have three vectors,  $\nabla f_{Q}^{(t)}$, $\hat{Q}^\prime$, $M^\prime$, how are they multiplied together? The manner in which they are multiplied together is unclear. Furthermore, the residual term in Eq. (10) should not be a scalar $O(\eta^2)$, but rather a vector. I believe that the second-order error term also depends on the *model size*, i.e., the dimension of $w$.

5. The experiments is only conducted for one instance of $\hat{Q}$ (HTGE Pei et al.), which is insufficient. Additionally, the expression of $\hat{Q}$ from HTGE is missing.

Minor comments:

1. A key reference on the theoretical analysis of STE is missing, specifically: *Yin et al., Understanding Straight-Through Estimator in Training Activation Quantized Neural Networks, ICLR2019.*

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See weaknesses
soundness: 3
strengths: - The theoretical insights are interesting, unexpected and (to my knowledge) novel. They offer better understanding and insight into how gradient estimators work, which appeals to me.
- The paper is generally well written and easy to read. I appreciate how the authors lead their result with an intuitive explanation and illustrative graphic. This makes the following theory much easier to intuit.
- The experiments shown in the paper provide good evidence for the theoretical results.
summary: This paper presents a theoretical analysis of gradient estimators used in quantization-aware training. The authors show that in the case of quantized weights (but full precision activations) many extant gradient estimators for the quantization operation are approximately equivalent, if the learning rate and weight initialization are adjusted, and the learning rate is small. They then verify empirically their theoretical results, on image classification benchmarks, demonstrating that models trained with different gradient estimators indeed show high weight agreement and similar accuracies.
weaknesses: Major

1. The claims relating to practical impact feel overstated ("practitioners can now confidently choose the STE"). The problem setting that the authors explore (full precision activations, quantized weights, uniform fixed point quantization, small learning rate) is rather specific, and practitioners may be interested in quantized activations, or low-precision floating point or larger learning rates etc. I would prefer if the authors tempered their claims.
2. The experiments, although they demonstrate the theory well, are limited. They do not show finetuning from a pretrained full precision checkpoint, as is common for QAT in practice (I would expect this setting to match well with the theory since 1. QAT finetuning is done with a lower learning rate typically and 2. the gradient norm is likely to be low after initializing from a pretrained model). They do not show results other than 2-bit weight quantization even though they say results are similar. They do not show the practical limits of their theory, e.g. how weight alignment degrades/evolves over training or how much the learning rate needs to be increased for the error terms to start having a large impact.

Minor
1. Presentation could be improved in a number of ways. 
    1. Use of booktabs for tables. Place all table captions above the tables.
    1. Tables are hard to parse when skimming -- would benefit from more descriptive captions/grouping table 3 with 4
    2. All quotation marks are incorrectly rendered by LaTeX.
    2. Fig. 3 would look better with the bins.
2. The choice of training recipes are not explained -- it is unclear why the first 10 epochs are done using the same gradient estimator. Is it because the gradient norm is too high at the start of training resulting in the weights quickly diverging?
3. I think the point made in line 305 should be made more prominent. I think it is quite important that the reader is made aware that the gradient error is small/zero since Q-net and STE net will quantize to similar weights.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: Lines 400-404: Why was the initial 10% of training for the ImageNet-ResNet setup kept identical? What would the results be without this measure?

Lines 527-528: Regarding the statement that high learning rates might be the reason the equivalence is not observed in other studies, the authors write, "we expect that this counter-argument will not stand the test of time, since by our main results, the higher learning rate masks the fact that models with novel $\hat{Q}$ and the STE are still approximating the same process." Could you elaborate on what you mean by "will not stand the test of time" given that equations (6) and (7) indicate learning-rate-squared errors? It seems that higher learning rates would increase these errors. Why should these differences not enable advantages for novel $\hat{Q}$?


Lines 530-539: Can the authors comment on the potential implications of their results for the studies mentioned in the last paragraph, which propose additional innovations alongside novel gradient estimators?
soundness: 3
strengths: Equations (6) and (7) provide a rigorous theoretical contribution regarding the small difference in weight movement for different gradient estimators.

The presentation and writing style is very clear with helpful intuition such as the analogy of the "funhouse mirror". Additionally, the learning rate tweak in the experiment provides a practical comparison for the magnitude of the differences.
summary: The authors examine how different gradient estimators affect quantization-aware training. They theoretically demonstrate that, in the limit of small learning rates and with minor adjustments to the initialization and the learning rate magnitude, most gradient estimators yield equivalent weight movements. Consequently, they suggest that the Straight-Through Estimator, treating the gradient as if no quantization occurred in the backward pass, performs as well as any other more sophisticated alternative. Their theoretical claims are complemented by an empirical investigation.
weaknesses: The authors themselves acknowledge in Section 8 that many publications introduce more than just a new gradient estimator, raising questions about the broader practical impact of their findings. Novel gradient estimators are often proposed with other techniques to enable any benefits. As a result, the findings may have limited applicability beyond specific configurations.

It is somewhat difficult to draw clear conclusions about practical applications from the experiments. While the learning rate tweak provides a useful comparison, the differences in Tables 4 and 5 are challenging to interpret, particularly without comparisons across different initializations. A convincing experiment could be, to find a custom gradient estimator in the literature, which has been shown to improve validation accuracy over STE, replicate the results and then demonstrate that both perform equally with proper adjustments. The authors do not provide such a comparison, raising questions about whether the custom estimator was applied correctly in their experiments or if its potential advantages were overlooked.


Minor comments:

line 245: Typo: $Q(w_{\hat{Q}}^{(t)})=Q(w_{\hat{Q}}^{(t)})$

lines 329-340: Equations (8) to (12): "$\nabla$" missing before $f^{(t)}_{STE}$

lines 502-504: Missing figure number for Figure 3

Meta-review: The authors analyze the impact of gradient estimators on quantization-aware training, concluding that with small learning rates and minor adjustments, most estimators result in similar weight updates. They also claim that the Straight-Through Estimator performs comparably to more complex methods, supporting this claim with theoretical and empirical evidence.

The main issue of this paper is that some main claims are not strongly supported by its theoretical results and its numerical experiments. For example, the authors claim that the weight movement differences will be small if the learning rate is small, so $STE$-net will behave similarly to $\hat Q$-net in SGD and Adam. However, as one of the reviewer pointed out, the error $E^t$ keep increasing as $t$ increases, no matter how small the learning rate is. For a large number of iteration, $E^t$ can still be very large. The review requested some analysis on the cumulative error. However, the authors just provide the formula of the cumulative error on page 7 which is basically $O(t\eta)$ and is not necessarily small for a large $t$. Moreover, $\eta$ is not necessarily always small when training a model. It may decrease with $t$ so it can be large for the first few iterations. 

Also, the authors claimed that practitioners only need to use the Straight-Through Estimator because other estimators are similar to STE after modifying the learning rate and initialization. However, one reviewer pointed out that this claim is not supported by the current experiments. It needs a direct comparison with ""custom gradient estimators in the settings where they were originally proposed"".

I also think this paper is not well written with many abuses of math notations and missing definitions. The review team has pointed out some but there are still many others. For example, what is the definition of "$round()$" function? Also, $STE$-net and $\hat Q$-net are defined in words rather than using clear math formula.

Decision: Reject