Year: 2018

Abstract:
Low-precision training is a promising way of decreasing the time and energy cost of training machine learning models. Previous work has analyzed low-precision training algorithms, such as low-precision stochastic gradient descent, and derived theoretical bounds on their convergence rates. These bounds tend to depend on the dimension of the model d in that the number of bits needed to achieve a particular error bound increases as d increases. This is undesirable because a motivating application for low-precision training is large-scale models, such as deep learning, where d can be huge. In this paper, we prove dimension-independent bounds for low-precision training algorithms that use fixed-point arithmetic, which lets us better understand what affects the convergence of these algorithms as parameters scale. Our methods also generalize naturally to let us prove new convergence bounds on low-precision training with other quantization schemes, such as lowprecision floating-point computation and logarithmic quantization.

heading: 1 INTRODUCTION
text: As machine learning models continue to scale to target larger problems on bigger data, the task of training these models quickly and efficiently becomes an ever-more-important problem. One promising technique for doing this is low-precision computation, which replaces the 32-bit or 64-bit floating point numbers that are usually used in ML computations with smaller numbers, often 8-bit or 16-bit fixed point numbers. Low-precision computation is a broadly applicable technique that has received a lot of attention, especially for deep learning, and specialized hardware accelerators have been developed to support it (Jouppi et al., 2017; Burger, 2017; Caulfield et al., 2017).
A major application for low-precision computation is the training of ML models using empirical risk minimization. This training is usually done using stochastic gradient descent (SGD), and most research in low-precision training has focused on low-precision versions of SGD. While most of this work is empirical (Wu et al., 2018; Das et al., 2018; Zhu et al., 2016; Köster et al., 2017; Lee et al., 2017; Hubara et al., 2016; Rastegari et al., 2016; Zhou et al., 2016; Gupta et al., 2015; Courbariaux et al., 2014; 2015; De Sa et al., 2017), significant research has also been done in the theoretical analysis of low-precision training. This theoretical work has succeeded in proving bounds on the convergence rate of low-precision SGD and related low-precision methods in various settings, including for convex (De Sa et al., 2018; Zhang et al., 2017) and non-convex objectives (De Sa et al., 2015; Li et al., 2017; Alistarh et al., 2017). One common characteristic of these results is that the bounds tend to depend on the dimension d of the model being learned (equivalently, d is the number of parameters). For example, (Li et al., 2017) gives the convergence bound
E [f(w̄T )− f(w∗)] ≤ (1 + log(T + 1))σ2max 2µT + σmaxδ
√ d
2 , (1)
where the objective f is strongly convex with parameter µ, low-precision SGD outputs w̄T after T iterations, w∗ is the true global minimizer of the objective, σ2max is an upper bound on the second moment of the stochastic gradient samples E[‖f̃(w)‖22] ≤ σ2max, and δ is the quantization step, the difference between adjacent numbers in the low-precision format. Notice that, as T → ∞, this bound shows convergence down to a level of error that increases with the dimension d. Equivalently, in order to achieve the same level of error as d increases, we would need to use more bits of quantization to make δ smaller. Similar dimension-dependent results, where either the error or the number of bits needed increases with d, can also be seen in other work on low-precision training algorithms (Alistarh et al., 2017; Zhang et al., 2017; De Sa et al., 2018). This dependence on d is unsatisfying because the motivation for low-precision training is to tackle large-scale problems on big data, where d can range up to 108 or more for commonly used models (Simonyan and Zisserman,
Table 1: Summary of our dimension-free results compared with prior work. The values report the number of bits needed, according to the theoretical bound, for the LP-SGD (Li et al., 2017) algorithm to achieve an expected objective gap (f(w) − f(w∗)) of when we let step size α → 0, epoch length T →∞. Here we let R denote the radius of the range of numbers representable in the low-precision format and assume ‖w∗‖2 = Θ(R). The rest of the parameters can be found in the assumptions to be introduced later.
NUMBER OF BITS NEEDED FOR E [f(w)− f(w∗)] ≤
PRIOR DIMENSION-DEPENDENT BOUND log2O ( Rσmax √ d/ε ) OUR DIMENSION-FREE BOUND log2O ( Rσ1/ε
) DIMENSION-FREE WITH LOGARITHMIC QUANTIZATION log2O ( (Rσ/ε) · log ( 1 + σ1/σ
)) 2014). For example, to compensate for a factor of d = 108 in (1), we could add bits to decrease the quantization step δ by a factor of √ d, but this would require adding log2(10
4) ≈ 13 bits, which is significant compared to the 8 or 16 bits that are commonly used in low-precision training.
In this paper, we address this problem by proving dimension-free bounds on the convergence of LP-SGD Li et al. (2017). Our main technique for doing so is a tight dimension-independent bound on the expected quantization error of the low-precision stochastic gradients in terms of the `1-norm. Our results are summarized in Table 1, and we make the following contributions:
• We describe conditions under which we can prove a dimension-free bound on the convergence of SGD with fixed-point, quantized iterates on strongly convex problems.
• We study non-linear quantization schemes, in which the representable low-precision numbers are distributed non-uniformly. We prove dimension-free convergence bounds for SGD using logarithmic quantization (Lee et al., 2017), and we show that using logarithmic quantization can reduce the number of bits needed for LP-SPG to provably converge.
• We study quantization using low-precision floating-point numbers, and we present theoretical analyis that suggests how to assign a given number of bits to exponent and mantissa to optimize the accuracy of training algorithms. We validate our results experimentally.

heading: 2 RELATED WORK
text: Motivated by the practical implications of faster machine learning, much work has been done on low-precision training. This work can be roughly divided into two groups. The first focuses on training deep models with low-precision weights, to be later used for faster inference. For some applications, methods of this type have achieved good results with very low-precision models: for example, binarized (Courbariaux et al., 2015; Hubara et al., 2016; Rastegari et al., 2016) and ternary networks (Zhu et al., 2016) have been observed to be effective (although as is usual for deep learning they lack theoretical convergence results). However, these approaches are still typically trained with full-precision iterates: the goal is faster inference, not faster training (although faster training is often achieved as a bonus side-effect). A second line of work on low-precision training, which is applied to both DNN training and nondeep-learning tasks, focuses on making various aspects of SGD low-precision, while still trying to solve the same optimization problem as the full-precision version. The most common way to do this is to make the iterates of SGD (the wt in the SGD update step wt+1 = wt − αt∇ft(wt)) stored and computed in low-precision arithmetic (Courbariaux et al., 2014; Gupta et al., 2015; De Sa et al., 2018; 2015; Li et al., 2017). This is the setting we will focus on most in this paper, because it has substantial theoretical prior work which exhibits the dimension-dependence we set out to study (Li et al., 2017; Zhang et al., 2017; Alistarh et al., 2017; De Sa et al., 2018). The only paper we found with a bound that was not dimension-dependent was De Sa et al. (2015), but in that paper the authors required that the gradient samples be 1-sparse (have only one nonzero entry), which is not a realistic assumption for most ML training tasks. In addition to quantizing the iterates, other work has studied quantizing the training set (Zhang et al., 2017) and numbers used to communicate among parallel workers (Alistarh et al., 2017). We expect that our results on dimension-free bounds will be complementary with these existing theoretical approaches, and we hope that they can help to explain the success of the exciting empirical work in this area.

heading: 3 DIMENSION-FREE BOUNDS FOR SGD
text: In this section, we analyze the performance of stochastic gradient descent (SGD) using low-precision training. Though there are numerous variants of this algorithm, SGD remains the de facto algorithm
used most for machine learning. We will start by describing SGD and how it can be made lowprecision. Suppose we are trying to solve the problem
minimize: f(w) = 1
n n∑ i=1 f̃i(w) over: w ∈ Rd. (2)
SGD solves this problem iteratively by repeatedly running the update step wt+1 = wt − α∇f̃it(wt) (3) where α is the step size1 or learning rate, and it is the index of a component function chosen randomly and uniformly at each iteration from {1, . . . , n}. To make this algorithm low-precision, we quantize the iterates (the vectors wt) and store them in a low-precision format. The standard format to use lets us represent numbers in a set
dom(δ, b) = {−δ · 2b−1, · · · ,−δ, 0, δ, · · · , δ · (2b−1 − 1)} with δ > 0 being the quantization gap, the distance between adjacent representable numbers, and b ∈ N being the number of bits we use (De Sa et al., 2018). Usually, δ is a power of 2, and this scheme is called fixed-point arithmetic. It is straightforward to encode numbers in this set as b-bit signed integers, by just multiplying or dividing by δ to convert to or from the encoded format— and we can even do many arithmetic computations on these numbers directly as integers. This is sometimes called linear quantization because the representable points are distributed uniformly throughout their range. However, as the gradient samples will produce numbers outside this set during iteration, we need some way to map these numbers to the set of numbers that we can represent. The standard way to do this is with a quantization function Q(x) : R → dom(δ, b). While many quantization functions have been proposed, the one typically used in theoretical analysis (which we will continue to use here) is randomized rounding. Randomized rounding, also known as unbiased rounding or stochastic rounding, rounds up or down at random such that E [Q(x)] = x whenever x is within the range of representable numbers (i.e. when −δ · 2b−1 ≤ x ≤ δ · (2b−1 − 1)). When x is outside that range, we quantize it to the closest representable point. When we apply Q(δ,b) to a vector argument, it quantizes each of its components independently.
Using this quantization function, we can write the update step for low-precision SGD (LP-SGD), which is a simple quantization of (3), wt+1 = Q ( wt − α∇f̃it(wt) ) (4)
As mentioned before, one common feature of prior bounds on the convergence of LP-SGD is that they depend on the number of dimensions d, whereas bounds on full precision SGD under the same conditions do not do so. This difference is due to the fact that, when we use a quantization function Q to quantize a number w, it increases its variance by E [ (Q(w)− w)2 ] ≤ δ2/4. Observe that this inequality is tight since it holds as an equality when w is in the middle of two quantization points, e.g. w = δ/2, as illustrated in Figure 1(a). When quantizing a vector w ∈ Rd, the squared error can be increased by
E [ ‖Q(w)− w‖22 ] = d∑ k=1 E [ (Q(wk)− wk)2 ] ≤ δ 2d 4 , (5)
and this bound is again tight. This variance inequality is the source of the d term in analyses of LP-SGD, and the tightness of the bound leads to the natural belief that the d term is inherent, and that low-precision results are inevitably dimension-dependent.
However, we propose that if we can instead bound the variance in (5) with some properties of the problem itself that do not change as d changes, we can achieve a result that is dimensionindependent. One way to do this is to look at the variance graphically. Figure 3 plots the quantization error as a function of w along with the bound in (5). Notice that the squared error looks like a series of parabolas, and the bound in (5) is tight at the top of those parabolas, but loose elsewhere. Instead, suppose we want to do the opposite and produce a bound that is tight when the error is zero (at points in dom(δ, b)). To do this, we observe that E [ (Q(w)− w)2 ] ≤ δ|w−z| for any z ∈ dom(δ, b). This bound is also tight when z is adjacent to w, and we plot it in Figure 3 as well. The natural vector analog of this is
E [ ‖Q(w)− w‖22 ] ≤ ∑d k=1 δ|wk − zk| = δ ‖w − z‖1 , ∀z ∈ dom(δ, b)d (6)
1Usually in SGD the step size is decreased over time, but here for simplicity we consider a constant learning rate schedule.
where ‖·‖1 denotes the L1 norm. This is a dimension-independent bound we can use to replace (5) to bound the convergence of LP-SGD and other algorithms. However, this replacement is nontrivial as our bound is now non-constant: it depends on w, which is a variable updated each iteration. Also, in order to bound this new L1 norm term, we will need some new assumptions about the problem. Next, we will state these assumptions, along with the standard assumptions used in the analysis of SGD for convex objectives, and then we will use them to present our dimension-free bound on the convergence of SGD. Assumption 1. All the loss functions f̃i are differentiable, and their gradients are L-Lipschitz continuous in the sense of 2-norm, that is,
∀i ∈ {1, 2, · · · , n}, ∀x, y ∈ Rd, ‖∇f̃i(x)−∇f̃i(y)‖2 ≤ L ‖x− y‖2 Assumption 2. All the gradients of the loss functions f̃i are L1-Lipschitz continuous in the sense of 1-norm to 2-norm, that is,
∀i ∈ {1, 2, · · · , n}, ∀x, y ∈ Rd, ‖∇f̃i(x)−∇f̃i(y)‖1 ≤ L1 ‖x− y‖2 These two assumptions are simply expressing of Lipschitz continuity in different norms. Assumption 1 is a standard assumption in the analysis of SGD on convex objectives, and has been applied in the low-precision case as well in prior work (De Sa et al., 2018). Assumption 2 is analogous to 1, except we are bounding the L1 norm instead of the L2 norm. This holds naturally (with a reasonable value of L1) for many problems, in particular problems for which the gradient samples are sparse. Assumption 3. The gradient of the total loss function f is µ-strongly convex for some µ > 0:
∀w, v, f(w)− f(v)− µ 2 ‖w − v‖22 ≥ (w − v) T∇f(v)
Assumption 3 is a standard assumption that bounds the curvature of the loss function f , and is satisfied for many classes of convex objectives. For example, any convex loss with L2 regularization will always be strongly convex. When an objective is strongly convex and Lipschitz continuous, it is standard to say it has condition number κ = L/µ, and here we extend this to say it has L1 condition number κ1 = L1/µ. Assumption 4. The gradient of each loss function is bounded by some constant σ near the optimal point in the sense of l1 and l2 norm, that is,
E [∥∥∥∇f̃i(w∗)∥∥∥2 2 ] ≤ σ2, E [∥∥∥∇f̃i(w∗)∥∥∥ 1 ] ≤ σ1
This assumption constrains the gradient for each loss function at the optimal point. We know ∇f(w∗) = 1n ∑ i ∇̃fi(w∗) = 0, so it is intuitive that each ∇f̃i(w∗) can be bounded by some value. Therefore this is a natural assumption to make and it has been used in a lot of other work in this area. Note that this assumption only needs to hold under the expectation over all f̃i. With these assumptions, we proved the following theorem for low-precision SGD: Theorem 1. Suppose that we run LP-SGD on an objective that satisfies Assumptions 1–4, and with step size α < 1/(2κ2µ). After T LP-SGD update steps (4), select w̄T uniformly at random from {w0, w1, . . . , wT−1}. Then, the expected objective gap of w̄T is bounded by
E [f(w̄T )− f(w∗)] ≤ 1
2αT ‖w0 − w∗‖22 + ασ2 + δσ1 2 + δ2κ21µ 4
This theorem shows a bound of the expected distance between the result we get at K-th iteration and the optimal value. By choosing an appropriate step size we can achieve convergence at a 1/T rate, while the limit we converge to is only dependent on dimension-free factors. Meanwhile, as mentioned in the first section, previous work gives a dimension-dependent bound (1) for the problem, which also converges at a 1/T rate.2 Therefore our result guarantees a dimension-independent convergence limit without weakening the convergence rate.
It is important to note that, because the dimension-dependent bound in (5) was tight, we should not expect our new result to improve upon the previous theory in all cases. In the worst case, κ1 = √ d·κ
and similarly σ1 = √ d · σ; this follows from the fact that for vectors in Rd, the norms are related by
the inequality ‖x‖1 ≤ √ d · ‖x‖2. Substituting this into our result produces a dimension-dependent bound again. This illustrates the importance of introducing the new parameters κ1 and σ1 and requiring that they be bounded; if we could not express our bound in terms of these parameters, the best we could do here is recover a dimension-dependent bound.
Experiments Next, we validate our theoretical results experimentally. To do this, we analyzed how the size of the noise floor of convergence of SGD and LP-SGD varies as the dimension is changed for a class of synthetic problems. Importantly, we needed to pick a class of problems for which the parameters L, L1, µ, σ, and σ1, did not change as we changed the dimension d. To do this, we chose a class of synthetic linear regression models with loss components sampled independently and identically as
f̃i(w) = 1
2 (x̃Tw − ỹ)2
where x̃ is a sparse vector sampled to have s nonzero entries each of which is sampled uniformly from {−1, 1}, and ỹ is sampled fromN (x̃Tw∗, β2) for some variance parameter β. Importantly, the nonzero entries of x̃ were chosen non-uniformly such that Pr[x̃i 6= 0] = pi for some probabilities pi which decrease as i increases; this lets us ensure that µ remains constant as d is increased. For simplicity, we sampled a fresh loss component of this form at each SGD iteration, which is sometimes called the online setting. It is straightforward to derive that for this problem
µ = pd L = s L1 = s √ s σ2 = β2s σ1 = √ 2s/πσ.
We set α = 0.01, β = 0.2, p1 = 0.9, pd = 0.001, and s = 16, we chose each entry of w∗ uniformly from [−1/2, 1/2], and we set δ such that the low-precision numbers would range from −1 to 1. Figure 1(b) shows the convergence of SGD and LP-SGD as the dimension d is changed, for both 8-bit and 6-bit quantization. Notice that while changing d has an effect on the initial convergence rate for both SGD and LP-SGD, it has no effect on the noise ball size, the eventual loss gap that the algorithm converges to. Figure 2(a) measures this noise ball size more explicitly as the dimension is changed: it reports the loss gap averaged across the second half of the iterates. Notice that as the dimension d is changed, the average loss gap is almost unchanged, even for very low-precision methods for which the precision does significantly affect the size of the noise ball. This validates our dimension-free bounds, and shows that they can describe the actual dependence on d in at least one case.
Figure 2(b) validates our results in the opposite way: it looks at how this gap changes as our new parameters σ1 and L1 change while d, µ, and σ are kept fixed. To do this, we fixed d = 1024 and changed s across a range, setting β = 0.8/ √ s, which keeps σ2 constant as s is changed: this has the effect of changing σ1 (and, as a side effect, L1 and L). We can see from figure 2(b) that changing σ1 in this way has a much greater effect on LP-SGD than it does on SGD. This validates our theoretical results, and suggests that σ1 and L1 can effectively determine the effect of low-precision compute on SGD.

heading: 4 NON-LINEAR QUANTIZATION
text: Up till now, most theoretical work in the area of low-precision machine learning has been on linear quantization, where the distance between adjacent quantization points is a constant value δ. Another option is non-linear quantization (NLQ), in which we quantize to a set of points that are nonuniformly distributed. This approach has been shown to be effective for accelerating deep learning
2Previous work (1) used a decaying step size while ours uses a constant step size to achieve a better result.
in some settings (Lee et al., 2017). In general, we can quantize to a set of points
D = {−qn, · · · ,−q1, q0, q1, · · · , qn−1},
and, just like with linear quantization, we can still use a quantization functionQ(w) with randomized rounding that rounds up or down to a number in D in such a way that E [Q(w)] = w for w ∈ [−qn, qn−1]. When we consider the quantization variance here, the natural dimension-dependent bound would be
E [ ‖Q(w)− w‖22 ] ≤ d
4 max i
(qi − qi−1)2.
This is still a tight bound since it holds with equality for a number in the middle of two most distant quantization points. However, when applied in the analysis of LP-SGD, this bound induces poor performance and often under-represents the actual result.
Here we discuss a specific NLQ method and use it to introduce a tight bound on the quantization variance. This method has been previously studied as logarithmic quantization or µ−law quantization, and is defined recursively by
q0 = 0, qi+1 − qi = δ + ζqi (7)
where δ > 0 and ζ > 0 are fixed parameters. Note that this includes linear quantization as a special case by setting ζ = 0. It turns out that we can prove a tight dimension-independent bound on the quantization variance of this scheme. First, we introduce the following definition. Definition 1. An unbiased quantization functionQ satisfies the dimension-free variance bound with parameters δ, ζ, and η if for all w ∈ [−qn, qn−1] and all z ∈ D,
E [ ‖Q(w)− w‖22 ] ≤ δ ‖w − z‖1 + ζ ‖z‖2 · ‖w − z‖2 + η ‖w − z‖ 2 2 .
We can prove that our logarithmic quantization scheme satisfies this bound. Lemma 1. The logarithmic quantization scheme (7) satisfies the dimension-free variance bound with parameters δ, ζ, and η = ζ 2
4(ζ+1) < ζ 4 .
Notice that this bound becomes identical to the linear quantization bound (6) when ζ = 0, so this result is a strict generalization of our results from the linear quantization case. With this setup, we can apply NLQ to the low-precision training algorithms we have studied earlier in this paper. Theorem 2. Suppose that we run LP-SGD on an objective that satisfies Assumptions 1–4, and using a quantization scheme that satisfies the dimension-free variance bound. If ζ < 1κ , then
E [(f(w̄T )− f(w∗))] ≤ ‖w0 − w∗‖22
2αT + (1 + η)ασ2 + δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
This theorem is consistent with Theorem 1 in that, if we set ζ = η = 0, which makes logarithmic quantization linear, they would have an identical result. If we fix the representable range R (the largest-magnitude values representable in the low-precision format) and choose our quantization
parameters optimally, we get the result that the number of bits we need to achieve objective gap is log2O ( (Rσ/ε) · log ( 1+σ1/σ )) . This bound is notable because even in the worst case where we do not have a bound on σ1 and must use σ1 ≤ √ d·σ, this bound gives us log2O ( (Rσ/ε)·log ( 1+ √ d )) . That is, while a dimension-dependent factor still remains, it is now “hidden” within a log term. This greatly decreases the effect of the dimension, and suggests that NLQ may be a promising technique to use for low-precision training at scale. Also note that, although this bound holds only when we set ζ < 1κ = µ L , which to some extent limits the acceleration of the strides in logarithmic quantization, the bound µL is independent of σ and σ1, thus this effect of “pushing ” σ1 into a log term is independent of the setting of ζ.
Floating point. Next, we look at another type of non-linear quantization that is of great practical use: floating-point quantization (FPQ). Here, the quantization points are simply floating-point numbers with some fixed number of exponential bits be and mantissa bits bm. Floating-point numbers are represented in the form
(−1)sign bit · 2exponent−bias · (1.m1m2m3 . . .mbm) (8)
where “exponent” is a be-bit unsigned number, the mi are the bm bits of the mantissa, and “bias” is a term that sets the range of the representable numbers by determining the range of the exponent. In standard floating point numbers, the exponent ranges from [−2be−1 + 2, 2be−1 − 1], which corresponds to a bias of 2be−1− 1. To make our results more general, we also consider non-standard bias by defining a scaling factor s = 2−(bias−standard bias); the standard bias setting corresponds to s = 1. We also consider the case of denormal floating point numbers, which tries to address underflow by replacing the 1 in (8) with a 0 for the smallest exponent value. Under these conditions, we can prove that floating-point quantization satisfies the bound in Definition 1. Lemma 2. The FPQ scheme using randomized rounding satisfies the dimension-free variance bound with parameters δnormal, ζ, and η for normal FPQ and δdenormal, ζ, and η for denormal FPQ where
δnormal = 4s
22 be , δdenormal =
8s
22 be+bm
, ζ = 2−bm , η = ζ 2
4(ζ+1) .
This bound can be immediately combined with Theorem 2 to produce dimension-independent bounds on the convergence rate of low-precision floating-point SGD. If we are given a fixed number of total bits b = be + bm, we can minimize this upper bound on the objective gap to try to predict the best way to allocate our bits between the exponent and the mantissa. Unfortunately, there is no analytical expression for this optimal choice of be. To give a sense of the asymptotic behavior of this optimal allocation, we present upper and lower bounds on it. Theorem 3. When using FPQ without denormal numbers, given b total bits, the optimal number of exponential bits be such that the asymptotic upper bound on the objective gap given by Theorem 2 is minimized is in the interval between:
log2 [ 2 log2 ( 2(ln 2)sσ1 σ‖w∗‖2 ) + 2b ] and log2 [ 2 log2 ( 2(ln 2)sL1 L‖w∗‖2+σ ) + 2b ] .
Theorem 4. When using denormal FPQ, given b total bits, the optimal number of exponential bits be such that the asymptotic upper bound on the objective gap, as T → ∞ and α → 0, given by Theorem 2 is minimized is in the interval between:
log2 [ 1− 2ln 2W ( eσ‖w∗‖2
8sσ1
)] and log2 [ 1− 2ln 2W ( e(L‖w∗‖2+σ)
8sL1 )] where e denotes the base of the natural logarithm and W stands for the Lambert W function. In cases where neither of these two values exists, the noise ball size increases as be, thus be = 2 would be the optimal setting, which is equivalent to linear quantization. These theorems give us an idea of where the optimal setting of be lies such that the theoretical asymptotic error is minimized. When using normal FPQ, this optimal assignment of be isO(log(b)), and for denormal FPQ the result is independent of b. This suggests that once the total number of bits grows past a threshold, we should assign most of or all the extra bits to the mantissa.
Experiments For FPQ, we ran experiments on two different data sets. First, we ran LP-SGD on the same synthetic data set that we used for linear regression. Here we used normal FPQ with 20 bits in total, and we get the result in Figure 4(a). In this diagram, we plotted the empirical noise ball size, its theoretical upper bound, and the optimal interval for be as Theorem 3 predicts. As the figure shows, our theorem accurately predicts the optimal setting of exponential bits, which is 5 in this case, to minimize both the theoretical upper bound and the actual empirical result of the noise ball size, despite the theoretical upper bound being loose.
Second, we ran LP-SGD on the MNIST dataset (Deng, 2012). To set up the experiment, we normalized the MNIST data to be in [0, 1] by dividing by 255, then subtracted out the mean for each features. We ran multiclass logistic regression using an L2 regularization constant of 10−4 and a step size of α = 10−4, running for 500 total epochs (passes through the dataset) to be sure we converged. For this task, our (measured) problem parameters were L = 37.41, L1 = 685.27, σ = 2.38, σ1 = 29.11, and d = 784. In Figure 4(b), we plotted the observed loss gap, averaged across the last ten epochs, for LP-SGD using various 16-bit floating point formats. We also plot our theoretical bound on the loss gap, and the predicted optimal number of exponential bits to use based on that bound. Our results show that even though our bound is very loose for this task, it still predicts the right number of bits to use with reasonable accuracy. This experiment also validates the use of IEEE standard half-precision floating-point numbers, which have 5 exponential bits, for this sort of task.

heading: 5 CONCLUSION
text: In this paper, we present dimension-independent bounds on the convergence of SGD when applied to low-precision training. We point out the conditions under which such bounds hold. We further extend our results to non-linear methods of quantization: logarithmic quantization and floating point quantization. We analyze the performance of SGD under logarithmic quantization and demonstrate that NLQ is a promising method for reducing the number of bits required in low-precision training. We also presented ways in which our theory could be used to suggest how to allocate bits between exponent and mantissa when FPQ is used. We hope that our work will encourage further investigation of non-linear quantization techniques.

heading: A ALGORITHM
text: In our work, we presented dimension-free bounds on the performance of low-precision SGD, here we present the algorithm in detail.
Algorithm 1 LP-SGD: Low-Precision Stochastic Gradient Descent given: n loss functions f̃i, number of epochs T , step size α, and initial iterate w0. given: low-precision quantization function Q. for t = 0 to T − 1 do
sample it uniformly from {1, 2, · · · , n}, quantize wt+1 ← Q ( wt − α∇f̃it(wt) ) end for return wT

heading: B PROOF FOR RESULTS IN TABLE 1
text: As mentioned in the caption of Table 1, here only we consider the convergence limit, that is, we assume α → 0, T → ∞, and we compute the minimum number of bits b we would require in order for the limit to be less than some small positive ε. Meanwhile, we denote the radius of the representable range by R and we assume R = ‖w∗‖2 without loss of generality, as this is the worst case for all our bounds that depend on ‖w∗‖2. Then in linear quantization, we have:
q2b−1−1 = δ · ( 2b−1 − 1 ) ≥ R
and in non-linear quantization, we need:
q2b−1−1 = δ
ζ
( (1 + ζ)(2 b−1−1) − 1 ) ≥ R (9)
In the following proof we’ll take the equality for these two inequalities.
B.1 LP-SGD IN PREVIOUS WORK
In previous work Li et al. (2017), we have
f(w̄T )− f(w∗) ≤ (1 + log(T + 1))G2 2µT + Gδ √ d 2
here we re-denote G as σmax for concordance with our result. Here σ2max is an upper bound on the second moment of the stochastic gradient samples E [ ‖f̃(w)‖22 ] ≤ σ2max. Substitute δ with R2b−1−1 and set the limit (as α→ 0 and T →∞) to be ≤ ε, and notice that 2b−1 − 1 > 2b−2, then we have:
σmaxR √ d
2 (2b−1 − 1) = O (ε) ⇒ b ≤ log2
( σmaxR √ d
ε
) + 1 = log2O ( σmaxR √ d
ε
)
B.2 LP-SGD IN OUR WORK
In Theorem 1, we know that
E [f(w̃)− f(w∗)] ≤ 1 2αT ‖w0 − w∗‖22 + ασ2 + δσ1 2 + δ2κ21µ 4
Set the limit (as α→ 0 and T →∞) to be ≤ ε, then we need: δσ1 2 = O (ε) , δ 2κ21µ 4 = O (ε) .
Then for sufficiently small ε, more explicitly, ε that satisfies L 2 1
µσ21 O(ε) < 1, setting δ = O ( ε
σ1
)
will satisfy the requirements, and we will get
R
2b−1 − 1 = δ = O
( ε
σ1
) ⇒ b = log2O ( σ1R
ε ) This is the expression that we wanted. Notice that even if we did not invoke small ε in the above big-O analysis, we can set
δ = O ( min ( ε
σ1 ,
√ εµ
L1 )) Then our number of bits would look like
b = log2O ( max ( σ1R
ε , RL1√ εµ
)) ,
which shows explicitly that we have replaced the dimension factor with parameters of the loss functions.
B.3 LP-SGD IN OUR WORK USING NLQ
In Theorem 2, we know that, if ζ < 1κ , then
E [(f(w̃)− f(w∗))] ≤ 1 2αT ‖w0 − w∗‖22+ (1 + η)ασ2 + δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
Set the limit (as α→ 0 and T →∞) to be ≤ ε and replace ‖w∗‖2 with R; then we get
δσ1 + ζσR
2 +
(δL1 + ζLR+ ζσ) 2
4µ = O (ε) .
So, in addition to our requirement that ζ ≤ κ−1, it suffices to have
δσ1 = O (ε) , ζσR = O (ε) , δ2L21 µ = O (ε) , ζ 2(LR+ σ)2 µ = O (ε) .
If we set
δ = O (ε) σ1 , ζ = O (ε) σR ,
then all our other requirements will be satisfied for sufficiently small ε. Specifically, we need ε to be small enough that
κ σR O (ε) ≤ 1, L
2 1
σ21µ O (ε) ≤ 1, (LR+ σ)
2
σ2R2µ O (ε) ≤ 1.
As is standard in big-O analysis, we assume that ε is small enough that these requirements are satisfied, in which case our assignment of δ and ζ, combined with the results of Theorem 2, is sufficient to ensure an objective gap of ε. Next, starting from (9), the number of bits we need for non-linear quantization must satisfy
(1 + ζ)(2 b−1−1) − 1 ≥ ζR
δ
which happens only when ( 2b−1 − 1 ) log(1 + ζ) ≥ log ( 1 + ζR
δ
) .
Since we know that 0 ≤ ζ < 1, it follows that log(1 + ζ) ≥ ζ/2. So in order for the above to be true, it suffices to have (
2b−1 − 1 ) · ζ
2 ≥ log
( 1 + ζR
δ
) .
Since 2b−1 − 1 > 2b−2, it follows that it suffices to have
2b · ζ 8 ≥ log
( 1 + ζR
δ
) .
And this will be true if
b = log2O ( 1
ζ log
( 1 + ζR
δ
)) .
Finally, using our assignment of δ and ζ gives us b = log2O ( σR log (
1 + σ1 σ
)) .
This is the expression that we wanted. Notice that even if we did not invoke small ε in the above big-O analysis, we would still get a rate in which all of our `1-dependent terms are inside the doublelogarithm, because none of the requirements above that constrain ζ are `1-dependent. To be explicit, to do this we would set δ and ζ to be
δ = O ( min ( ε
σ1 ,
√ εµ
L1
)) , ζ = O ( min ( ε
σR ,
√ εµ
LR+ σ ,
1
κ
)) .
Then our number of bits would look like b = log2O ( max ( σR
ε , LR+ σ √ εµ , κ
) · log ( 1 + ζR
δ
)) ,
which shows explicitly that any `1-dependent terms are inside the double logarithm.

heading: C PROOF FOR THEOREMS
text: Before we prove the main theorems presented in the paper, we will prove the following lemmas that will be useful later, as well as the lemmas we presented before.
The proof of lemma 1 can be extracted from the proof of lemma 5 that we will show later.
Proof of Lemma 2. Here we consider the positive case first, then symmetrically the negative case also holds. First, for normal FPQ, the set of quantization points are:
D = {0} ∪ { s · ( 1 + x
nm
) · 2y | x = 0, 1, · · · , nm − 1, y = −
ne 2 + 2, · · · , ne 2 − 1 }
and we set the parameters for the nonlinear quantization bound to be:
δ = s · 2− ne 2 +2 = 4s(√ 2 )ne , ζ = 1nm , η = ζ 2 4(1 + ζ) =
1
4nm(nm + 1)
For any w within representable range, we can assume it is in [qi, qi+1), then
E [ [Q(w)− w]2 ] =
qi+1 − w qi+1 − qi · (w − qi)2 + w − qi qi+1 − qi · (qi+1 − w)2
= (w − qi)(qi+1 − w)
So now we only need to prove that
∀v ∈ D, (w − qi)(qi+1 − w) ≤ δ · |w − v|+ ζ · |v| · |w − v|+ η · |w − v|2
First, we consider a special case where qi = 0. In this case, qi+1 = s · 1 · 2− ne 2 +2 = δ. If v = 0, it is obvious that LHS = (w − qi)(qi+1 − w) = w(δ − w) ≤ δw ≤ RHS
and similarly for v = δ,
LHS = (w − qi)(qi+1 − w) = w(δ − w) ≤ δ(δ − w) ≤ RHS
and for v > δ, RHS ≥ δ(v − w) ≥ δ(δ − w) ≥ w(δ − w) = LHS
Next, we consider the case where qi 6= 0. In this case, we can assume qi = s · (
1 + xnm
) · 2y , then
qi+1 − qi = s · 2y ≤ 1nm qi = ζqi.
If v ≥ qi+1, denote y = qi+1 − w, then LHS = (w − qi)(qi+1 − w) = y · (qi+1 − qi − y) = y · (ζqi − y) RHS ≥ ζ · qi+1 · (qi+1 − w) = ζqi+1y ≥ ζqiy ≥ LHS
Secondly, if 0 ≤ v ≤ qi, denote y = w − qi, then LHS = (w − qi)(qi+1 − w) = y · (qi+1 − qi − y) = y · (ζqi − y) RHS = δ · (w − v) + ζ · v · (w − v) + η · (w − v)2
= − (ζ − η) · v2 + (−δ + ζw − 2ηw) · v + δw − δ2
observe that ζ − η > 0, so the right hand side is a concave function of v, thus it achieves minimum at either v = 0 or v = qi. At v = qi:
RHS = δy + ζqiy + ηy 2 ≥ ζqiy ≥ LHS
and at v = 0, since qi+1 ≤ (1 + ζ)qi and qi ≤ w,
RHS − LHS = δ · w + ζ · 0 · w + η · w2 − (w − qi)(qi+1 − w) = (1 + η)w2 + (δ − qi − qi+1)w + qiqi+1 ≥ (1 + η)w2 − (qi + qi+1) · w + qiqi+1 = (1 + η)w2 − [(2 + ζ)qiw + (qi+1 − (1 + ζ)qi)w] + [(1 + ζ)q2i + (qi+1 − (1 + ζ)qi)qi] = (1 + η)w2 − (2 + ζ)qi · w + (1 + ζ)q2i + (qi+1 − (1 + ζ)qi)(qi − w) ≥ (1 + η)w2 − (2 + ζ)qi · w + (1 + ζ)q2i
which is a positive parabola. Recall that η = ζ 2 4(ζ+1) = (ζ+2)2
4(ζ+1) − 1, thus the determinant is (2 + ζ)2q2i − 4(1 + η)(1 + ζ)q2i = 0, therefore RHS − LHS ≥ 0. Now we extend this conclusion to the case where v ≤ 0. In this case,
RHS = δ · (w − v) + ζ · (−v) · (w − v) + η · (w − v)2
since w, ζ, δ, η are all positive, this is apparently a decreasing function of v, thus it achieves minimum at v = 0, which is what we have already proven.
So far, we’ve proven the lemma in the case of w ≥ 0, v ≥ 0 and w ≥ 0, v ≤ 0, and symmetrically it holds for w ≤ 0, v ≤ 0 and w ≤ 0, v ≥ 0, which indicates that we can extend D to be a set containing both positive and negative numbers.
In the de-normal FPQ case, the set of quantization points are:
D = { s · x
nm · 2− ne 2 +3 | x = 0, 1, · · · , nm − 1 } ∪ { s · ( 1 + x
nm
) · 2y | x = 0, 1, · · · , nm − 1, y = −
ne 2 + 3, · · · , ne 2 − 1 }
and we set the parameters for the nonlinear quantization bound to be:
δ = s · 1 nm · 2− ne 2 +3 = 8 C · sne(√ 2 )ne , ζ = 1nm , η = ζ 2 4(1 + ζ) =
1
4nm(nm + 1)
The proof for this case follows the exact same structure as the normal FPQ case.
Lemma 3. Under condition of linear quantization when using low-precision representation (δ, b), for any w, v ∈ Rd where Q(δ,b)(w) = w,
E [∥∥Q(δ,b)(w + v)− w∗∥∥22] ≤ ‖(w + v)− w∗‖22 + δ ‖v‖1 .
where Q is the linear quantization function.
Proof of Lemma 3. (This proof follows the same structure as the proof for lemma 1 in (De Sa et al., 2018)) First, observe that this lemma holds if it holds for each dimension, so we only need to prove that for any w, v ∈ R where Q(δ,b)(w) = w, i.e. w ∈ dom(δ, b),
E [ (Q(δ,b)(w + v)− w∗)2 ] ≤ (w + v − w∗)2 + δ|v|
then we can sum up all the dimensions to get the result.
Now we consider the problem in two situations. First, if w + v is within the range representable by (δ, b), then E [ Q(δ,b)(w + v) ] = w + v. In this case,
E [ (Q(δ,b)(w + v)− w∗)2 ] = E [ [(Q(δ,b)(w + v)− (w + v))− ((w + v)− w∗)]2
] = E [ [Q(δ,b)(w + v)− (w + v)]2 − 2[Q(δ,b)(w + v)− (w + v)][(w + v)− w∗]
] + [(w + v)− w∗]2
= E [ [Q(δ,b)(w + v)− (w + v)]2 ] − 2[(w + v)− (w + v)][(w + v)− w∗]
+ [(w + v)− w∗]2 = [(w + v)− w∗]2 + E [ [Q(δ,b)(w + v)− (w + v)]2 ] Since (w + v) is within representable range, E [ [Q(δ,b)(w + v)− (w + v)]2 ] is equivalent to
E [ [Q(δ,∞)(v) + w − (w + v)]2 ] , which equals E [ [Q(δ,∞)(v)− v]2 ] since Q(δ,b)(w) = w.
Now we only need to prove that E [ [Q(δ,∞)(v)− v]2 ] ≤ δ|v|. Observe that this trivially holds for v = 0, and is symmetrical for positive and negative v. Without loss of generality we assume v > 0, let z be the rounded-down quantization of v, then we have z ≥ 0. Then Q(δ,b)(v) will round to z+ δ (the rounded-up quantization of v) with probability v−zδ , and it will round to z with probability z+δ−v δ . This quantization is unbiased because
E [ Q(δ,∞)(w) ] = v − z δ (z + δ) + z + δ − v δ z = vz − z2 + vδ − zδ δ + z2 + zδ − vz δ = v.
Thus, its variance will be E [ (Q(δ,∞)(v)− v)2 ] = v − z δ (z + δ − v)2 + z + δ − v δ (z − v)2
= (v − z)(z + δ − v) ( z + δ − v
δ + v − z δ ) = δ(v − z)− (v − z)2
≤ δ(v − z) ≤ δv. therefore
E [ (Q(δ,b)(w + v)− w∗)2 ] ≤ (w + v − w∗)2 + δ|v|
In the other case, when w+v is on the exterior of the representable region, the quantization function Q(δ,b) just maps it to the nearest representable value. Since w∗ is in the interior of the representable region, this operation will make w + v closer to w∗. Thus,
(Q(δ,b)(w + v)− w∗)2 ≤ (w + v − w∗)2, and so it will certainly be the case that
E [ (Q(δ,b)(w + v)− w∗)2 ] ≤ (w + v − w∗)2 + δ|v|.
Now that we’ve proven the inequality for one dimension, we can sum up all d dimensions and get E [∥∥Q(δ,b)(w + v)− w∗∥∥22] ≤ ‖(w + v)− w∗‖22 + δ ‖v‖1 .
For completeness, we also re-state the proof of following lemma, which was presented as equation (8) in (Johnson and Zhang, 2013), and here we present the proof for this lemma used in (De Sa et al., 2018).
Lemma 4. Under the standard condition of Lipschitz continuity, if i is sampled uniformly at random from {1, . . . , N}, then for any w,
E [ ‖∇fi(w)−∇fi(w∗)‖22 ] ≤ 2L (f(w)− f(w∗)) .
Proof of Lemma 4. For any i, define
gi(w) = fi(w)− fi(w∗)− (w − w∗)T∇fi(w∗).
Clearly, if i is sampled randomly as in the lemma statement, E [gi(w)] = f(w). But also, w∗ must be the minimizer of gi, so for any w
gi(w ∗) ≤ min η gi(w − η∇gi(w))
≤ min η
( gi(w)− η ‖∇gi(w)‖22 + η2L
2 ‖∇gi(w)‖22 ) = gi(w)− 1
2L ‖∇gi(w)‖22 .
where the second inequality follows from the Lipschitz continuity property. Re-writing this in terms of fi and averaging over all the i now proves the lemma statement.
Lemma 5. Under the condition of logarithmic quantization, for any w, v ∈ Rd where v ∈ Dd, E [ ‖Q(w)− w∗‖22 ] ≤ ‖w − w∗‖22 + δ ‖w − v‖1 + ζ ‖v‖2 ‖w − v‖2 + η ‖w − v‖ 2 2
where Q is the non-linear quantization function.
Note that the proof this lemma naturally extends to lemma 1, thus we omitted the proof for lemma 1 and just present the proof for lemma 5.
Proof of Lemma 5. Here we only consider the positive case first, where
D = {q0, q1, · · · , qn−1}
with [0, qn−1] being the representable range of D. As for the negative case, we will show later that it holds symmetrically.
Observe that this lemma holds if it holds for each dimension, so we only need to prove that for any w, v ∈ R where v ∈ D,
E [ [Q(w)− w∗]2 ] ≤ |w − w∗|2 + δ · |w − v|+ ζ · |v| · |w − v|+ η · |w − v|2
then we can sum up all the dimensions and use Cauchy-Schwarz inequality to get the result.
Now we consider the problem in two situations.
First, if w is outside the representable range, the quantization function Q just maps it to the nearest representable value. Since w∗ is in the interior of the representable range, this operation will make w closer to w∗. Thus, [Q(w)− w∗]2 ≤ (w − w∗)2, and so it will certainly be the case that
E [ [Q(w)− w∗]2 ] ≤ |w − w∗|2 + δ · |w − v|+ ζ · |v| · |w − v|+ η · |w − v|2
Second, if w is within the representable range, then E [Q(w)] = w. In this case, E [ [Q(w)− w∗]2 ] = E [ [(Q(w)− w)− (w − w∗)]2
] = E [ [Q(w)− w]2 − 2[Q(w)− w](w − w∗) ] + (w − w∗)2
= E [ [Q(w)− w]2 ] − 2(w − w)(w − w∗) + (w − w∗)2
= (w − w∗)2 + E [ [Q(w)− w]2 ]
Since w is within representable range, we can assume it is in [qi, qi+1), then
E [ [Q(w)− w]2 ] =
qi+1 − w qi+1 − qi · (w − qi)2 + w − qi qi+1 − qi · (qi+1 − w)2
= (w − qi)(qi+1 − w)
So now we only need to prove that
(w − qi)(qi+1 − w) ≤ δ · |w − v|+ ζ · |v| · |w − v|+ η · |w − v|2
Note that v ∈ D, so it is either v ≥ qi+1 or v ≤ qi. Firstly, if v ≥ qi+1, denote y = qi+1 − w, then
LHS = (w − qi)(qi+1 − w) = y · (qi+1 − qi − y) = y · (δ + ζqi − y) RHS = δ · (v − w) + ζ · v · (v − w) + η · (v − w)2
≥ δ · (qi+1 − w) + ζ · qi+1 · (qi+1 − w) + η · (qi+1 − w)2
= δy + ζqi+1y + ηy 2
≥ δy + ζqiy − y2 = LHS
Secondly, if 0 ≤ v ≤ qi, denote y = w − qi, then
LHS = (w − qi)(qi+1 − w) = y · (qi+1 − qi − y) = y · (δ + ζqi − y) RHS = δ · (w − v) + ζ · v · (w − v) + η · (w − v)2
= − (ζ − η) · v2 + (−δ + ζw − 2ηw) · v + δw − δ2
observe that ζ − η > 0, so the right hand side is a concave function of v, thus it achieves minimum at either v = 0 or v = qi. At v = qi:
RHS = δy + ζqiy + ηy 2 ≥ δy + ζqiy − y2 = LHS
and at v = 0:
RHS − LHS = δ · w + ζ · 0 · w + η · w2 − (w − qi)(qi+1 − w) = (1 + η)w2 + (δ − qi − qi+1)w + qiqi+1 = (1 + η)w2 − (2 + ζ)qi · w + qiqi+1 ≥ (1 + η)w2 − (2 + ζ)qi · w + (1 + ζ)q2i
which is a positive parabola. Recall that η = ζ 2 4(ζ+1) = (ζ+2)2
4(ζ+1) − 1, thus the determinant is (2 + ζ)2q2i − 4(1 + η)(1 + ζ)q2i = 0, therefore RHS − LHS ≥ 0. Now we extend this conclusion to the case where v ≤ 0. In this case,
RHS = δ · (w − v) + ζ · (−v) · (w − v) + η · (w − v)2
since w, ζ, δ, η are all positive, this is apparently a decreasing function of v, thus it achieves minimum at v = 0, which is what we have already proven.
So far, we’ve proven the lemma in the case of w ≥ 0, v ≥ 0 and w ≥ 0, v ≤ 0, and symmetrically it holds for w ≤ 0, v ≤ 0 and w ≤ 0, v ≥ 0, which indicates that we can extend D to be a set containing both positive and negative numbers, and we can reset D to be
D = {−qn, · · · ,−q1, q0, q1, · · · , qn−1}
where q0 = 0, qi+1 − qi = δ + ζqi
Now we have proven all the lemmas we need. Next, we make some small modifications to the assumptions (weakening them) so that our theorems are shown in a more general sense. For assumption 2, we change it to:
Assumption 5. All the gradients of the loss functions fi are L1-Lipschitz continuous in the sense of 1-norm to p-norm, that is,
∀i ∈ {1, 2, · · ·n}, ∀x, y, ‖∇fi(x)−∇fi(y)‖1 ≤ L1 ||x− y||p
While in the body of the paper and in our experiments we choose p = 2 for simplicity, here we are going to prove that a generalization of Theorem 1 holds for all real numbers p. We also need a similar generalization of Assumption 3. Assumption 6. The average of the loss functions f = 1n ∑ i fi is µ1− strongly convex near the optimal point in the sense of p-norm, that is,
∀w, µ1 2 ||w − w∗||2p ≤ f(w)− f(w ∗)
with p being any real number.
This assumption is essentially the same as the assumption for strong convexity that we stated before, since in practice we would choose p = 2 and then µ1 and µ would be the same. But here we are actually presenting our result in a stronger sense in that we can choose any real number p and the proof goes the same.
Now we are ready to prove the theorems. Note that the result of the following proof contains µ1 since we are proving a more general version of our theorems; substituting them with µ will lead to the same result that we stated before.
Proof of Theorem 1. In low-precision SGD, we have:
ut+1 = wt − α∇f̃t(wt), wt+1 = Q(ut+1) by lemma 3, we know that
E [ ‖wt+1 − w∗‖22 ] = E [∥∥∥Q(wt − α∇f̃t(wt))− w∗∥∥∥2 2 ] ≤ E [∥∥∥wt − α∇f̃t(wt)− w∗∥∥∥2 2 ] + δE [∥∥∥α∇f̃t(wt)∥∥∥ 1
] = E [ ‖wt − w∗‖22 ] − 2αE [ (wt − w∗)T∇f̃t(wt)
] + α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1
] ≤ E [ ‖wt − w∗‖22 ] − 2αE [ (f(wt)− f(w∗)) + µ
2 ‖wt − w∗‖22 ] + α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1
] = (1− αµ)E [ ‖wt − w∗‖22 ] + α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1
] − 2αE [(f(wt)− f(w∗))]
where the second inequality holds due to the strongly convexity assumption. According to the assumptions we had, we have: E [ ‖∇fi(w)‖22 ] = E [ ‖∇fi(w)−∇fi(w∗) +∇fi(w∗)‖22
] = E [ ‖∇fi(w)−∇fi(w∗)‖22 + 2(∇fi(w)−∇fi(w ∗))T∇fi(w∗) + ‖∇fi(w∗)‖22 ]
= E [ ‖∇fi(w)−∇fi(w∗)‖22 + ‖∇fi(w ∗)‖22 ]
≤ L2 ·E [ ‖w − w∗‖22 ] + σ2
E [‖∇fi(w)‖1] = E [‖∇fi(w)−∇fi(w ∗) +∇fi(w∗)‖1]
≤ E [‖∇fi(w)−∇fi(w∗)‖1 + ‖∇fi(w ∗)‖1] ≤ L1 ·E [‖w − w∗‖2] + σ1
where the last inequality holds due to assumption 2 where we let p = 2. Applying this result to the previous formula and we will have:
E [ ‖wt+1 − w∗‖22 ] ≤ (1− αµ)E [ ‖wt − w∗‖22 ] + α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1 ] − 2αE [(f(wt)− f(w∗))]
≤ (1− αµ+ α2L2)E [ ‖wt − w∗‖22 ] + αδL1E [‖wt − w∗‖2]
− 2αE [(f(wt)− f(w∗))] + α2σ2 + αδσ1
Here we introduce a positive constant C that we’ll set later, and by basic inequality we get
αδL1E [‖wt − w∗‖2] ≤ CE [‖wt − w ∗‖2]
2 + α2δ2L21
4C ≤ CE
[ ‖wt − w∗‖22 ] + α2δ2L21
4C
thus
E [ ‖wt+1 − w∗‖22 ] ≤ (1− αµ+ α2L2 + C)E [ ‖wt − w∗‖22 ] − 2αE [(f(wt)− f(w∗))]
+ α2σ2 + αδσ1 + α2δ2L21
4C
one setting C to be αµ− α2L2, we will have: 2αE [(f(wt)− f(w∗))] ≤ E [ ‖wt − w∗‖22 ] −E [ ‖wt+1 − w∗‖22 ] +α2σ2+αδσ1+ α2δ2L21 4(αµ− α2L2)
since we can set α to be small enough such that αL2 ≤ µ2 , then the result will become:
2αE [(f(wt)− f(w∗))] ≤ E [ ‖wt − w∗‖22 ] −E [ ‖wt+1 − w∗‖22 ] + α2σ2 + αδσ1 + αδ2L21 2µ
now we sum up this inequality from t = 0 to t = T − 1 and divide by 2αT , then we get:
1
T T−1∑ t=o E [(f(wt)− f(w∗))] ≤ ‖w0 − w∗‖22 −E
[ ‖wT − w∗‖22 ] 2αT + ασ2 + δσ1 2 + δ2L21 4µ
≤ ‖w0 − w∗‖22 2αT + ασ2 + δσ1 2 + δ2κ21µ 4
and since we sample w̃ uniformly from (wo, w1, · · · , wT−1), we get
E [(f(w̃)− f(w∗))] ≤ 1 2αT ‖w0 − w∗‖22 + ασ2 + δσ1 2 + δ2κ21µ 4
Proof of Theorem 2 . In low-precision SGD, we have:
ut+1 = wt − α∇f̃t(wt), wt+1 = Q(ut+1)
by lemma 5, we know that
E [ ‖wt+1 − w∗‖22 ] = E [∥∥∥Q(wt − α∇f̃t(wt))− w∗∥∥∥2 2 ] ≤ E [∥∥∥wt − α∇f̃t(wt)− w∗∥∥∥2 2
] + δE [∥∥∥α∇f̃t(wt)∥∥∥ 1 ] + ζE [ ‖wt‖2 ∥∥∥α∇f̃t(wt)∥∥∥ 2 ] + ηE [∥∥∥α∇f̃t(wt)∥∥∥2 2
] ≤ E [ ‖wt − w∗‖22 ] − 2αE [ (wt − w∗)T∇f̃t(wt) ] + α2E [∥∥∥∇f̃t(wt)∥∥∥2 2
] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1 ] + ζE [ (‖wt − w∗‖2 + ‖w ∗‖2) · α ∥∥∥∇f̃t(wt)∥∥∥ 2 ] + ηα2E [∥∥∥∇f̃t(wt)∥∥∥2 2
] ≤ E [ ‖wt − w∗‖22 ] − 2αE [ (f(wt)− f(w∗)) + µ
2 ‖wt − w∗‖22
] + α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1 ] + αζE [ (‖wt − w∗‖2 + ‖w ∗‖2) ∥∥∥∇f̃t(wt)∥∥∥ 2 ] + ηα2E [∥∥∥∇f̃t(wt)∥∥∥2 2
] = (1− αµ)E [ ‖wt − w∗‖22 ] + (1 + η)α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] − 2αE [(f(wt)− f(w∗))]
+ αζE [ (‖wt − w∗‖2 + ‖w ∗‖2) ∥∥∥∇f̃t(wt)∥∥∥
2
] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1 ] where the third inequality holds due to the strongly convexity assumption. According to the assumptions we had, we have:
E [ ‖∇fi(w)‖22 ] = E [ ‖∇fi(w)−∇fi(w∗) +∇fi(w∗)‖22 ] = E [ ‖∇fi(w)−∇fi(w∗)‖22 + 2(∇fi(w)−∇fi(w ∗))T∇fi(w∗) + ‖∇fi(w∗)‖22 ]
= E [ ‖∇fi(w)−∇fi(w∗)‖22 + ‖∇fi(w ∗)‖22 ]
≤ L2 ·E [ ‖w − w∗‖22 ] + σ2
‖∇fi(w)‖2 = ‖∇fi(w)−∇fi(w ∗) +∇fi(w∗)‖2
≤ ‖∇fi(w)−∇fi(w∗)‖2 + ‖∇fi(w ∗)‖2
≤ L · ‖w − w∗‖2 + σ ‖∇fi(w)‖1 = ‖∇fi(w)−∇fi(w
∗) +∇fi(w∗)‖1 ≤ ‖∇fi(w)−∇fi(w∗)‖1 + ‖∇fi(w
∗)‖1 ≤ L1 · ‖w − w∗‖2 + σ1
where the last inequality holds due to assumption 2 where we let p = 2. Apply this result to the previous formula, denote η′ = 1 + η, and then we will have:
E [ ‖wt+1 − w∗‖22 ] ≤ (1− αµ)E [ ‖wt − w∗‖22 ] + η′α2E [∥∥∥∇f̃t(wt)∥∥∥2 2 ] − 2αE [(f(wt)− f(w∗))]
+ αζE [ (‖wt − w∗‖2 + ‖w ∗‖2) ∥∥∥∇f̃t(wt)∥∥∥
2
] + αδE [∥∥∥∇f̃t(wt)∥∥∥ 1 ] ≤ (1− αµ+ η′α2L2)E [ ‖wt − w∗‖22 ] + αδL1E [‖wt − w∗‖2] + η ′α2σ2 + αδσ1
+ αζE [(‖wt − w∗‖2 + ‖w ∗‖2)(L · ‖w − w ∗‖2 + σ)]− 2αE [(f(wt)− f(w ∗))] = (1− αµ+ αζL+ η′α2L2)E [ ‖wt − w∗‖22 ] − 2αE [(f(wt)− f(w∗))]
+ (αδL1 + αζL ‖w∗‖2 + αζσ)E [‖wt − w ∗‖2] + η ′α2σ2 + αδσ1 + αζσ ‖w∗‖2
Here we introduce a positive constant C that we’ll set later, and by basic inequality we get
(αδL1 + αζL ‖w∗‖2 + αζσ)E [‖wt − w ∗‖2]
≤ CE [‖wt − w∗‖2] 2
+ (αδL1 + αζL ‖w∗‖2 + αζσ)2
4C ≤ CE [ ‖wt − w∗‖22 ] + α2(δL1 + ζL ‖w∗‖2 + ζσ)2
4C
thus E [ ‖wt+1 − w∗‖22 ] ≤ (1− αµ+ αζL+ η′α2L2 + C)E [ ‖wt − w∗‖22 ] − 2αE [(f(wt)− f(w∗))]
+ η′α2σ2 + αδσ1 + αζσ ‖w∗‖2 + α2(δL1 + ζL ‖w∗‖2 + ζσ)2
4C
one setting C to be αµ− αζL− η′α2L2, we will have: 2αE [(f(wt)− f(w∗))] ≤ E [ ‖wt − w∗‖22 ] −E [ ‖wt+1 − w∗‖22 ] + η′α2σ2 + αδσ1 + αζσ ‖w∗‖2 + α2(δL1 + ζL ‖w∗‖2 + ζσ)2
4(αµ− αζL− η′α2L2)
since we can set α to be small enough such that αµ − αζL − η′α2L2 ≥ 12αµ, then the result will become:
2αE [(f(wt)− f(w∗))] ≤ E [ ‖wt − w∗‖22 ] −E [ ‖wt+1 − w∗‖22 ] + η′α2σ2 + αδσ1 + αζσ ‖w∗‖2 + α(δL1 + ζL ‖w∗‖2 + ζσ)2
2µ
now we sum up this inequality from t = 0 to t = T − 1 and divide by 2αT , then we get:
1
T T−1∑ t=o E [(f(wt)− f(w∗))]
≤ ‖w0 − w∗‖22 −E
[ ‖wT − w∗‖22 ] 2αT + η′ασ2 + δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
≤ ‖w0 − w∗‖22 2αT + η′ασ2 + δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
and since we sample w̃ uniformly from (wo, w1, · · · , wT−1), we get
E [(f(w̃)− f(w∗))] ≤ 1 2αT ‖w0 − w∗‖22+ η′ασ2 + δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
Proof of Theorem 3. In the normal FPQ case, the set of quantization points are: D = {0} ∪ { s · ( 1 + x
nm
) · 2y | x = 0, 1, · · · , nm − 1, y = −
ne 2 + 2, · · · , ne 2 − 1 }
then the parameters for the nonlinear quantization bound can be computed as:
δ = s · 2− ne 2 +2 = 4s(√ 2 )ne , ζ = 1nm , η = ζ 2 4(1 + ζ) =
1
4nm(nm + 1)
For NLQ-SGD, the noise ball size according to theorem 2 is:
δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
Denote this as 12A+ 1 4µB 2. When b is large, δ, ζ, η are small, then the dominating term for the noise ball is
A = δσ1 + ζσ ‖w∗‖2 = 4sσ1 1(√ 2 )ne + σ ‖w∗‖2 1nm = 4sσ1 1(√2)ne + σ ‖w∗‖2 neC
let the derivative over ne to be 0 and we get:
∂A ∂ne = −2(ln 2)sσ1 1(√ 2 )ne + σ ‖w∗‖2 1C = 0, (√2)ne = 2(ln 2)sσ1Cσ ‖w∗‖2
ne = 2 log2
( 2(ln 2)sσ1C
σ ‖w∗‖2
) , be = log2 ( 2b+ 2 log2 ( 2(ln 2)sσ1 σ ‖w∗‖2 )) And when b is small, δ, ζ, η are large and the dominating term for the noise ball is
B = δL1+ζL ‖w∗‖2+ζσ = 4sL1 1(√ 2 )ne +(L ‖w∗‖2+σ) 1nm = 4sL1 1(√2)ne +(L ‖w∗‖2+σ)neC
let the derivative of ne to be 0 and we get:
∂B ∂ne = −2(ln 2)sL1 1(√ 2 )ne + (L ‖w∗‖2 + σ) 1C = 0, (√2)ne = 2(ln 2)sL1CL ‖w∗‖2 + σ
ne = 2 log2
( 2(ln 2)sL1C
L ‖w∗‖2 + σ
) , be = log2 ( 2b+ 2 log2 ( 2(ln 2)sL1 L ‖w∗‖2 + σ )) For b such that neither the terms dominates the result, we know the noise ball size is:
1 2 A+ 1 4µ B2 = δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
then the derivative of ne is:
∂
∂ne
( 1
2 A+
1 4µ B2 ) = 1 2 ∂A ∂ne + B 2µ ∂B ∂ne
and since both ∂A∂ne and ∂B ∂ne are increasing functions and we know that:
∂A
∂ne ∣∣∣∣∣ ne=2 log2 ( 2(ln 2)sσ1C
σ‖w∗‖2
) = 0, ∂B∂ne ∣∣∣∣∣ ne=2 log2 ( 2(ln 2)sL1C
L‖w∗‖2+σ
) = 0
then we know the solution of ∂∂ne ( 1 2A+ 1 4µB 2 ) = 0 is in the interval between 2 log2 ( 2(ln 2)sσ1C σ‖w∗‖2 ) and 2 log2 ( 2(ln 2)sL1C L‖w∗‖2+σ ) .
Proof of Theorem 4. In the denormal FPQ case, the set of quantization points are:
D = { s · x
nm · 2− ne 2 +3 | x = 0, 1, · · · , nm − 1 } ∪ { s · ( 1 + x
nm
) · 2y | x = 0, 1, · · · , nm − 1, y = −
ne 2 + 3, · · · , ne 2 − 1 }
then the parameters for the nonlinear quantization bound is:
δ = s · 1 nm · 2− ne 2 +3 = 8 C · sne(√ 2 )ne , ζ = 1nm , η = ζ 2 4(1 + ζ) =
1
4nm(nm + 1)
For NLQ-SGD, the noise ball size according to theorem 2 is:
δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
Denote this as 12A+ 1 4µB 2. When b is large, δ, ζ, η are small and the dominating term for the noise ball is
A = δσ1 + ζσ ‖w∗‖2 = 8sσ1 C ne(√ 2 )ne + σ ‖w∗‖2 1nm = 8sσ1C ne(√2)ne + σ ‖w∗‖2 neC
let the derivative over ne to be 0 and we get:
∂A ∂ne = 8sσ1 C
1− (ln √
2)ne(√ 2 )ne + σ ‖w∗‖2 1C = 0
denote V (x) = x · ex, and Lambert W function W (y) = V −1(y), y ≥ − 1e . then we need
∂A ∂ne = 8sσ1 C
1− (ln √
2)ne(√ 2 )ne + σ ‖w∗‖2 1C = 8sσ1eC V (1− (ln√2)ne) + σ ‖w∗‖2 1C = 0
thus we have:
ne = 1− 2
ln 2 W
( eσ ‖w∗‖2
8sσ1
) , be = log2 [ 1− 2
ln 2 W
( eσ ‖w∗‖2
8sσ1 )] And when b is small, δ, ζ, η are large and the dominating term for the noise ball is
B = δL1 + ζL ‖w∗‖2 + ζσ = 8sL1 C · ne(√ 2 )ne + (L ‖w∗‖2 + σ)neC
let the derivative of ne to be 0 and we get:
∂B ∂ne = 8sL1 C
1− (ln √
2)ne(√ 2 )ne +(L ‖w∗‖2+σ) 1C = 8sL1eC V (1−(ln√2)ne)+(L ‖w∗‖2+σ) 1C = 0
thus we have:
ne = 1− 2
ln 2 W
( e(L ‖w∗‖2 + σ)
8sL1
) be = 2 log2 [ 1− 2
ln 2 W
( e(L ‖w∗‖2 + σ)
8sL1 )] For b such that neither the terms dominates the result, we know the noise ball size is:
1 2 A+ 1 4µ B2 = δσ1 + ζσ ‖w∗‖2 2 + (δL1 + ζL ‖w∗‖2 + ζσ)2 4µ
then the derivative of ne is:
∂
∂ne
( 1
2 A+
1 4µ B2 ) = 1 2 ∂A ∂ne + B 2µ ∂B ∂ne
and since both ∂A∂ne and ∂B ∂ne are increasing functions and we know that:
∂A
∂ne ∣∣∣∣∣ ne=1− 2ln 2W ( eσ‖w∗‖2
8sσ1
) = 0, ∂B∂ne ∣∣∣∣∣ ne=1− 2ln 2W ( e(L‖w∗‖2+σ)
8sL1
) = 0
then we know the solution of ∂∂ne ( 1 2A+ 1 4µB 2 )
= 0 is in the interval between 1 − 2 ln 2W ( eσ‖w∗‖2
8sσ1
) and 1− 2ln 2W ( e(L‖w∗‖2+σ)
8sL1
) .

Review summaries:
This paper discusses conditions under which  the convergence of training models with low-precision weights do not rely on model dimension. Extensions to two kinds of non-linear quantization methods are also provided. The dimension-free bound of the this paper is achieved through a tighter bound on the variance of the quantized gradients.  Experiments are performed on synthetic sparse data and small-scale image classification dataset MNIST.

The paper considers the problem of low precision stochastic gradient descent. Specifically, they study updates of the form x_{t + 1} = Q (x_t - alpha * g_t), where g_t is a stochastic gradient, and Q is a quantization function. The goal is to produce quantization functions that simultaneously increase the convergence rate as little as possible, while also requiring few bits to represent. This is motivated by the desire to perform SGD on low precision machines.