Title: DIMENSION-FREE BOUNDS FOR LOW-PRECISION TRAINING

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.

1. INTRODUCTION:

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; Kö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

EQUATION

where the objective f is strongly convex with parameter µ, low-precision SGD outputs wT after T iterations, w * is the true global minimizer of the objective, σ 2 max is an upper bound on the second moment of the stochastic gradient samples E[ f (w) 2 2 ] ≤ σ 2 max , 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 10 8 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. . For example, to compensate for a factor of d = 10 8 in (1), we could add bits to decrease the quantization step δ by a factor of √ d, but this would require adding log 2 (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.

2. RELATED WORK:

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 w t in the SGD update step w t+1 = w t -α t ∇f t (w t )) 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.

3. DIMENSION-FREE BOUNDS FOR SGD:

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:

EQUATION

SGD solves this problem iteratively by repeatedly running the update step w t+1 = w t -α∇ fit (w t )

(3) where α is the step size1 or learning rate, and i t 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 w t ) and store them in a low-precision format. The standard format to use lets us represent numbers in a set

dom(δ, b) = {-δ • 2 b-1 , • • • , -δ, 0, δ, • • • , δ • (2 b-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 formatand 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 -δ

• 2 b-1 ≤ x ≤ δ • (2 b-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),

EQUATION

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 ∈ R d , the squared error can be increased by

EQUATION

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 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.

EQUATION

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 fi are differentiable, and their gradients are L-Lipschitz continuous in the sense of 2-norm, that is,

∀i ∈ {1, 2, • • • , n}, ∀x, y ∈ R d , ∇ fi (x) -∇ fi (y) 2 ≤ L x -y 2 Assumption 2. All the gradients of the loss functions fi are L 1 -Lipschitz continuous in the sense of 1-norm to 2-norm, that is, ∀i ∈ {1, 2, • • • , n}, ∀x, y ∈ R d , ∇ fi (x) -∇ fi (y) 1 ≤ L 1 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 L 1 ) 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 2 2 ≥ (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 = L 1 /µ. Assumption 4. The gradient of each loss function is bounded by some constant σ near the optimal point in the sense of l 1 and l 2 norm, that is,

E ∇ fi (w * ) 2 2 ≤ σ 2 , E ∇ fi (w * ) 1 ≤ σ 1

This assumption constrains the gradient for each loss function at the optimal point. We know ∇f (w * ) = 1 n i ∇f i (w * ) = 0, so it is intuitive that each ∇ fi (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 fi . 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 wT uniformly at random from {w 0 , w 1 , . . . , w T -1 }. Then, the expected objective gap of wT is bounded by

EQUATION

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 R d , 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, L 1 , µ, σ, 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 fi

(w) = 1 2 (x T w -ỹ) 2

where x is a sparse vector sampled to have s nonzero entries each of which is sampled uniformly from {-1, 1}, and ỹ is sampled from N (x T w * , β 2 ) for some variance parameter β. Importantly, the nonzero entries of x were chosen non-uniformly such that Pr[x i = 0] = p i for some probabilities p i 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

µ = p d L = s L 1 = s √ s σ 2 = β 2 s σ 1 = 2s/πσ.

We set α = 0.01, β = 0.2, p 1 = 0.9, p d = 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 L 1 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, L 1 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 L 1 can effectively determine the effect of low-precision compute on SGD. in some settings (Lee et al., 2017) . In general, we can quantize to a set of points

D = {-q n , • • • , -q 1 , q 0 , q 1 , • • • , q n-1 },

and, just like with linear quantization, we can still use a quantization function Q(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 ∈ [-q n , q n-1 ]. When we consider the quantization variance here, the natural dimension-dependent bound would be

E Q(w) -w 2 2 ≤ d 4 max i (q i -q i-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 q 0 = 0, q i+1 -q i = δ + ζq i (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 function Q satisfies the dimension-free variance bound with parameters δ, ζ, and η if for all w ∈ [-q n , q n-1 ] and all z ∈ D,

E Q(w) -w 2 2 ≤ δ 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 ( wT ) -f (w * ))] ≤ w 0 -w * 2 2 2αT + (1 + η)ασ 2 + δσ 1 + ζσ w * 2 2 + (δL 1 + ζ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 log 2 O (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 log 2 O (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 b e and mantissa bits b m . Floating-point numbers are represented in the form

EQUATION

where "exponent" is a b e -bit unsigned number, the m i are the b m 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 [-2 be-1 + 2, 2 be-1 -1], which corresponds to a bias of 2 be-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 2 2 be , δ denormal = 8s 2 2 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 = b e + b m , 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 b e . 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 b e such that the asymptotic upper bound on the objective gap given by Theorem 2 is minimized is in the interval between: Theorem 4. When using denormal FPQ, given b total bits, the optimal number of exponential bits b e 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:

log 2 1 -2 ln 2 W eσ w * 2 8sσ1 and log 2 1 -2 ln 2 W 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 b e , thus b e = 2 would be the optimal setting, which is equivalent to linear quantization. These theorems give us an idea of where the optimal setting of b e lies such that the theoretical asymptotic error is minimized. When using normal FPQ, this optimal assignment of b e is O(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 b e 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, L 1 = 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.

5. CONCLUSION:

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.

A ALGORITHM:

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 fi, 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 -α∇ fi t (wt) end for return wT

B PROOF FOR RESULTS IN TABLE 1:

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:

q 2 b-1 -1 = δ • 2 b-1 -1 ≥ R

and in non-linear quantization, we need:

EQUATION

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 ( wT ) -f (w * ) ≤ (1 + log(T + 1))G 2 2µT + Gδ √ d 2

here we re-denote G as σ max for concordance with our result. Here σ 2 max is an upper bound on the second moment of the stochastic gradient samples E f (w) 2 2 ≤ σ 2 max . Substitute δ with R 2 b-1 -1

and set the limit (as α → 0 and T → ∞) to be ≤ ε, and notice that 2 b-1 -1 > 2 b-2 , then we have:

σ max R √ d 2 (2 b-1 -1) = O (ε) ⇒ b ≤ log 2 σ max R √ d ε + 1 = log 2 O σ max R √ d ε B.2 LP-SGD IN OUR WORK

In Theorem 1, we know that

E [f ( w) -f (w * )] ≤ 1 2αT w 0 -w * 2 2 +

ασ 2 + δσ 1 2 + δ 2 κ 2 1 µ 4 Set the limit (as α → 0 and T → ∞) to be ≤ ε, then we need:

δσ 1 2 = O (ε) , δ 2 κ 2 1 µ 4 = O (ε) .

Then for sufficiently small ε, more explicitly, ε that satisfies

L 2 1 µσ 2 1 O(ε) < 1, setting δ = O ε σ 1

will satisfy the requirements, and we will get

R 2 b-1 -1 = δ = O ε σ 1 ⇒ b = log 2 O σ 1 R ε

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 , √ εµ L 1 Then our number of bits would look like b = log 2 O max σ 1 R ε , RL 1 √ εµ ,

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 w 0 -w * 2 2 + (1 + η)ασ 2 + δσ 1 + ζσ w * 2 2 + (δL 1 + ζ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 + (δL 1 + ζLR + ζσ) 2 4µ = O (ε) .

So, in addition to our requirement that ζ ≤ κ -1 , it suffices to have

δσ 1 = O (ε) , ζσR = O (ε) , δ 2 L 2 1 µ = 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 σ 2 1 µ O (ε) ≤ 1, (LR + σ) 2 σ 2 R 2 µ 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 2 b-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

2 b-1 -1 • ζ 2 ≥ log 1 + ζR δ . Since 2 b-1 -1 > 2 b-2

, it follows that it suffices to have

2 b • ζ 8 ≥ log 1 + ζR δ .

And this will be true if

b = log 2 O 1 ζ log 1 + ζR δ .

Finally, using our assignment of δ and ζ gives us

b = log 2 O σ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 -dependent. To be explicit, to do this we would set δ and ζ to be

δ = O min ε σ 1 , √ εµ L 1 , ζ = O min ε σR , √ εµ LR + σ , 1 κ .

Then our number of bits would look like

b = log 2 O max σR ε , LR + σ √ εµ , κ • log 1 + ζR δ ,

which shows explicitly that any 1 -dependent terms are inside the double logarithm.

C PROOF FOR THEOREMS:

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 n m • 2 y | x = 0, 1, • • • , n m -1, y = - n e 2 + 2, • • • , n e 2 -1

and we set the parameters for the nonlinear quantization bound to be:

δ = s • 2 -ne 2 +2 = 4s √ 2 ne , ζ = 1 n m , η = ζ 2 4(1 + ζ) = 1 4n m (n m + 1)

For any w within representable range, we can assume it is in [q i , q i+1 ), then

E [Q(w) -w] 2 = q i+1 -w q i+1 -q i • (w -q i ) 2 + w -q i q i+1 -q i • (q i+1 -w) 2 = (w -q i )(q i+1 -w)

So now we only need to prove that

∀v ∈ D, (w -q i )(q i+1 -w) ≤ δ • |w -v| + ζ • |v| • |w -v| + η • |w -v| 2

First, we consider a special case where q i = 0. In this case,

q i+1 = s • 1 • 2 -ne 2 +2 = δ. If v = 0, it is obvious that LHS = (w -q i )(q i+1 -w) = w(δ -w) ≤ δw ≤ RHS and similarly for v = δ, LHS = (w -q i )(q i+1 -w) = w(δ -w) ≤ δ(δ -w) ≤ RHS and for v > δ, RHS ≥ δ(v -w) ≥ δ(δ -w) ≥ w(δ -w) = LHS

Next, we consider the case where q i = 0. In this case, we can assume

q i = s • 1 + x nm • 2 y , then q i+1 -q i = s • 2 y ≤ 1 nm q i = ζq i . If v ≥ q i+1 , denote y = q i+1 -w, then LHS = (w -q i )(q i+1 -w) = y • (q i+1 -q i -y) = y • (ζq i -y) RHS ≥ ζ • i+1 • (q i+1 -w) = ζq i+1 y ≥ ζq i y ≥ LHS Secondly, if 0 ≤ v ≤ q i , denote y = w -q i , then LHS = (w -q i )(q i+1 -w) = y • (q i+1 -q i -y) = y • (ζq i -y) RHS = δ • (w -v) + ζ • v • (w -v) + η • (w -v) 2 = -(ζ -η) • v 2 + (-δ + ζ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 = q i . At v = q i : RHS = δy + ζq i y + ηy 2 ≥ ζq i y ≥ LHS and at v = 0, since q i+1 ≤ (1 + ζ)q i and q i ≤ w, RHS -LHS = δ • w + ζ • 0 • w + η • w 2 -(w -q i )(q i+1 -w) = (1 + η)w 2 + (δ -q i -q i+1 )w + q i q i+1 ≥ (1 + η)w 2 -(q i + q i+1 ) • w + q i q i+1 = (1 + η)w 2 -[(2 + ζ)q i w + (q i+1 -(1 + ζ)q i )w] + [(1 + ζ)q 2 i + (q i+1 -(1 + ζ)q i )q i ] = (1 + η)w 2 -(2 + ζ)q i • w + (1 + ζ)q 2 i + (q i+1 -(1 + ζ)q i )(q i -w) ≥ (1 + η)w 2 -(2 + ζ)q i • w + (1 + ζ)q 2 i which is a positive parabola. Recall that η = ζ 2 4(ζ+1) = (ζ+2) 2 4(ζ+1) -1, thus the determinant is (2 + ζ) 2 q 2 i -4(1 + η)(1 + ζ)q 2 i

= 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 n m • 2 -ne 2 +3 | x = 0, 1, • • • , n m -1 ∪ s • 1 + x n m • 2 y | x = 0, 1, • • • , n m -1, y = - n e 2 + 3, • • • , n e 2 -1

and we set the parameters for the nonlinear quantization bound to be:

δ = s • 1 n m • 2 -ne 2 +3 = 8 C • sn e √ 2 ne , ζ = 1 n m , η = ζ 2 4(1 + ζ) = 1 4n m (n m + 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 ∈ R d where Q (δ,b) (w) = w, E Q (δ,b) (w + v) -w * 2 2 ≤ (w + v) -w * 2 2 + δ 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 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 -z 2 + vδ -zδ δ + z 2 + 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 * 2 2 ≤ (w + v) -w * 2 2 + δ 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 ∇f i (w) -∇f i (w * ) 2 2 ≤ 2L (f (w) -f (w * )) .

Proof of Lemma 4. For any i, define

g i (w) = f i (w) -f i (w * ) -(w -w * ) T ∇f i (w * ).

Clearly, if i is sampled randomly as in the lemma statement, [g i (w)] = f (w). But also, w * must be the minimizer of g i , so for any w

g i (w * ) ≤ min η g i (w -η∇g i (w)) ≤ min η g i (w) -η ∇g i (w) 2 2 + η 2 L 2 ∇g i (w) 2 2 = g i (w) - 1 2L ∇g i (w) 2 2 .

where the second inequality follows from the Lipschitz continuity property. Re-writing this in terms of f i and averaging over all the i now proves the lemma statement.

Lemma 5. Under the condition of logarithmic quantization, for any

w, v ∈ R d where v ∈ D d , E Q(w) -w * 2 2 ≤ w -w * 2 2 + δ 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 = {q 0 , q 1 , • • • , q n-1 }

with [0, q n-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 [q i , q i+1 ), then

E [Q(w) -w] 2 = q i+1 -w q i+1 -q i • (w -q i ) 2 + w -q i q i+1 -q i • (q i+1 -w) 2 = (w -q i )(q i+1 -w)

So now we only need to prove that

(w -q i )(q i+1 -w) ≤ δ • |w -v| + ζ • |v| • |w v| + η • |w -v| 2 Note that v ∈ D, so it is either v ≥ q i+1 or v ≤ q i .

Firstly, if v ≥ q i+1 , denote y = q i+1 -w, then

LHS = (w -q i )(q i+1 -w) = y • (q i+1 -q i -y) = y • (δ + ζq i -y) RHS = δ • (v -w) + ζ • v • (v -w) + η • (v -w) 2 ≥ δ • (q i+1 -w) + ζ • q i+1 • (q i+1 -w) + η • (q i+1 -w) 2 = δy + ζq i+1 y + ηy 2 ≥ δy + ζq i y -y 2 = LHS Secondly, if 0 ≤ v ≤ q i , denote y = w -q i , then LHS = (w -q i )(q i+1 -w) = y • (q i+1 -q i -y) = y • (δ + ζq i -y) RHS = δ • (w -v) + ζ • v • (w -v) + η • (w -v) 2 = -(ζ -η) • v 2 + (-δ + ζ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 = q i . At v = q i : RHS = δy + ζq i y + ηy 2 ≥ δy + ζq i y -y 2 = LHS and at v = 0:

RHS -LHS = δ • w + ζ • 0 • w + η • w 2 -(w -q i )(q i+1 -w) = (1 + η)w 2 + (δ -q i -q i+1 )w + q i q i+1 = (1 + η)w 2 -(2 + ζ)q i • w + q i q i+1 ≥ (1 + η)w 2 -(2 + ζ)q i • w + (1 + ζ)q 2 i which is a positive parabola. Recall that η = ζ 2 4(ζ+1) = (ζ+2) 2 4(ζ+1) -1, thus the determinant is (2 + ζ) 2 q 2 i -4(1 + η)(1 + ζ)q 2 i

= 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 = {-q n , • • • , -q 1 , q 0 , q 1 , • • • , q n-1 }

where q 0 = 0, q i+1 -q i = δ + ζq i 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 f i are L 1 -Lipschitz continuous in the sense of 1-norm to p-norm, that is,

∀i ∈ {1, 2, • • • n}, ∀x, y, ∇f i (x) -∇f i (y) 1 ≤ L 1 ||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 = 1 n i f i is µ 1strongly convex near the optimal point in the sense of p-norm, that is,

∀w, µ 1 2 ||w -w * || 2 p ≤ 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:

u t+1 = w t -α∇ ft (w t ), w t+1 = Q(u t+1 ) by lemma 3, we know that E w t+1 -w * 2 2 = E Q(w t -α∇ ft (w t )) -w * 2 2 ≤ E w t -α∇ ft (w t ) -w * 2 2 + δE α∇ ft (w t ) 1 = E w t -w * 2 2 -2αE (w t -w * ) T ∇ ft (w t ) + α 2 E ∇ ft (w t ) 2 2 + αδE ∇ ft (w t ) 1 ≤ E w t -w * 2 2 -2αE (f (w t ) -f (w * )) + µ 2 w t -w * 2 2 + α 2 E ∇ ft (w t ) 2 2 + αδE ∇ ft (w t ) 1 = (1 -αµ)E w t -w * 2 2 + α 2 E ∇ ft (w t ) 2 2 + αδE ∇ ft (w t ) 1 -2αE [(f (w t ) -f (w * ))]

where the second inequality holds due to the strongly convexity assumption. According to the assumptions we had, we have:

E ∇f i (w) 2 2 = E ∇f i (w) -∇f i (w * ) + ∇f i (w * ) 2 2 = E ∇f i (w) -∇f i (w * ) 2 2 + 2(∇f i (w) -∇f i (w * )) T ∇f i (w * ) + ∇f i (w * ) 2 2 = E ∇f i (w) -∇f i (w * ) 2 2 + ∇f i (w * ) 2 2 ≤ L 2 • E w -w * 2 2 + σ 2 E [ ∇f i (w) 1 ] = E [ ∇f i (w) -∇f i (w * ) + ∇f i (w * ) 1 ] ≤ E [ ∇f i (w) -∇f i (w * ) 1 + ∇f i (w * ) 1 ] ≤ L 1 • 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 w t+1 -w * 2 2 ≤ (1 -αµ)E w t -w * 2 2 + α 2 E ∇ ft (w t ) 2 2 + αδE ∇ ft (w t ) 1 -2αE [(f (w t ) -f (w * ))] ≤ (1 -αµ + α 2 L 2 )E w t -w * 2 2 + αδL 1 E [ w t -w * 2 ] -2αE [(f (w t ) -f (w * ))] + α 2 σ 2 + αδσ 1

Here we introduce a positive constant C that we'll set later, and by basic inequality we get

αδL 1 E [ w t -w * 2 ] ≤ CE [ w t -w * 2 ] 2 + α 2 δ 2 L 2 1 4C ≤ CE w t -w * 2 2 + α 2 δ 2 L 2 1 4C thus E w t+1 -w * 2 2 ≤ (1 -αµ + α 2 L 2 + C)E w t -w * 2 2 -2αE [(f (w t ) -f (w * ))] + α 2 σ 2 + αδσ 1 + α 2 δ 2 L 2 1 4C

one setting C to be αµ -α 2 L 2 , we will have:

2αE [(f (w t ) -f (w * ))] ≤ E w t -w * 2 2 -E w t+1 -w * 2 2 +α 2 σ 2 +αδσ 1 + α 2 δ 2 L 2 1 4(αµ -α 2 L 2 )

since we can set α to be small enough such that αL 2 ≤ µ 2 , then the result will become:

2αE [(f (w t ) -f (w * ))] ≤ E w t -w * 2 2 -E w t+1 -w * 2 2 + α 2 σ 2 + αδσ 1 + αδ 2 L 2 1 2µ

now we sum up this inequality from t = 0 to t = T -1 and divide by 2αT , then we get:

EQUATION

and since we sample w uniformly from

EQUATION

Proof of Theorem 2 . In low-precision SGD, we have:

u t+1 = w t -α∇ ft (w t ), w t+1 = Q(u t+1 )

by lemma 5, we know that

E w t+1 -w * 2 2 = E Q(w t -α∇ ft (w t )) -w * 2 2 ≤ E w t -α∇ ft (w t ) -w * 2 2 + δE α∇ ft (w t ) 1 + ζE w t 2 α∇ ft (w t ) 2 + ηE α∇ ft (w t ) 2 2 ≤ E w t -w * 2 2 -2αE (w t -w * ) T ∇ ft (w t ) + α 2 E ∇ ft (w t ) 2 2 + αδE ∇ ft (w t ) 1 + ζE ( w t -w * 2 + w * 2 ) • α ∇ ft (w t ) 2 + ηα 2 E ∇ ft (w t ) 2 2 ≤ E w t -w * 2 2 -2αE (f (w t ) -f (w * )) + µ 2 w t -w * 2 2 + α 2 E ∇ ft (w t ) 2 2 + αδE ∇ ft (w t ) 1 + αζE ( w t -w * 2 + w * 2 ) ∇ ft (w t ) 2 + ηα 2 E ∇ ft (w t ) 2 2 = (1 -αµ)E w t -w * 2 2 + (1 + η)α 2 E ∇ ft (w t ) 2 2 -2αE [(f (w t ) -f (w * ))] + αζE ( w t -w * 2 + w * 2 ) ∇ ft (w t ) 2 + αδE ∇ ft (w t ) 1

where the third inequality holds due to the strongly convexity assumption. According to the assumptions we had, we have:

E ∇f i (w) 2 2 = E ∇f i (w) -∇f i (w * ) + ∇f i (w * ) 2 2 = E ∇f i (w) -∇f i (w * ) 2 2 + 2(∇f i (w) -∇f i (w * )) T ∇f i (w * ) + ∇f i (w * ) 2 2 = E ∇f i (w) -∇f i (w * ) 2 2 + ∇f i (w * ) 2 2 ≤ L 2 • E w -w * 2 2 + σ 2 ∇f i (w) 2 = ∇f i (w) -∇f i (w * ) + ∇f i (w * ) 2 ≤ ∇f i (w) -∇f i (w * ) 2 + ∇f i (w * ) 2 ≤ L • w -w * 2 + σ ∇f i (w) 1 = ∇f i (w) -∇f i (w * ) + ∇f i (w * ) 1 ≤ ∇f i (w) -∇f i (w * ) 1 + ∇f i (w * ) 1 ≤ L 1 • 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 w t+1 -w * 2 2 ≤ (1 -αµ)E w t -w * 2 2 + η α 2 E ∇ ft (w t ) 2 2 -2αE [(f (w t ) -f (w * ))] + αζE ( w t -w * 2 + w * 2 ) ∇ ft (w t ) 2 + αδE ∇ ft (w t ) 1 ≤ (1 -αµ + η α 2 L 2 )E w t -w * 2 2 + αδL 1 E [ w t -w * 2 ] + η α 2 σ 2 + αδσ 1 + αζE [( w t -w * 2 + w * 2 )(L • w -w * 2 + σ)] -2αE [(f (w t ) -f (w * ))] = (1 -αµ + αζL + η α 2 L 2 )E w t -w * 2 2 -2αE [(f (w t ) -f (w * ))] + (αδL 1 + αζL w * 2 + αζσ)E [ w t -w * 2 ] + η α 2 σ 2 + αδσ 1 + αζσ w *

Here we introduce a positive constant C that we'll set later, and by basic inequality we get

(αδL 1 + αζL w * 2 + αζσ)E [ w t -w * 2 ] ≤ CE [ w t -w * 2 ] 2 + (αδL 1 + αζL w * 2 + αζσ) 2 4C ≤ CE w t -w * 2 2 + α 2 (δL 1 + ζL w * 2 + ζσ) 2 4C thus E w t+1 -w * 2 2 ≤ (1 -αµ + αζL + η α 2 L 2 + C)E w t -w * 2 2 -2αE [(f (w t ) -f (w * ))] + η α 2 σ 2 + αδσ 1 + αζσ w * 2 + α 2 (δL 1 + ζL w * 2 + ζσ) 2 4C

one setting C to be αµ -αζL -η α 2 L 2 , we will have:

2αE [(f (w t ) -f (w * ))] ≤ E w t -w * 2 2 -E w t+1 -w * 2 2 + η α 2 σ 2 + αδσ 1 + αζσ w * 2 + α 2 (δL 1 + ζL w * 2 + ζσ) 2 4(αµ -αζL -η α 2 L 2 )

since we can set α to be small enough such that αµ -αζL -η α 2 L 2 ≥ 1 2 αµ, then the result will become:

2αE [(f (w t ) -f (w * ))] ≤ E w t -w * 2 2 -E w t+1 -w * 2 2 + η α 2 σ 2 + αδσ 1 + αζσ w * 2 + α(δL 1 + ζ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: Proof of Theorem 3. In the normal FPQ case, the set of quantization points are:

D = {0} ∪ s • 1 + x n m • 2 y | x = 0, 1, • • • , n m -1, y = - n e 2 + 2, • • • , n e 2 -1

then the parameters for the nonlinear quantization bound can be computed as:

δ = s • 2 -ne 2 +2 = 4s √ 2 ne , ζ = 1 n m , η = ζ 2 4(1 + ζ) = 1 4n m (n m + 1)

For NLQ-SGD, the noise ball size according to theorem 2 is: Proof of Theorem 4. In the denormal FPQ case, the set of quantization points are:

δσ 1 +

D = s • x n m • 2 -ne 2 +3 | x = 0, 1, • • • , n m -1 ∪ s • 1 + x n m • 2 y | x = 0, 1, • • • , n m -1, y = - n e 2 + 3, • • • , n e 2 -1

then the parameters for the nonlinear quantization bound is:

δ = s • 1 n m • 2 -ne 2 +3 = 8 C • sn e √ 2 ne , ζ = 1 n m , η = ζ 2 4(1 + ζ) = 1 4n m (n m + 1)

For NLQ-SGD, the noise ball size according to theorem 2 is: For b such that neither the terms dominates the result, we know the noise ball size is: .

1 2 A + 1 4µ B 2 = δσ 1 +

:

Usually in SGD the step size is decreased over time, but here for simplicity we consider a constant learning rate schedule.

NON-LINEAR QUANTIZATIONUp 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 2 Previous work (1) used a decaying step size while ours uses a constant step size to achieve a better result.

+σ + 2b .

Figures and Tables:

NUMBER OF BITS NEEDEDFOR E [f (w) -f (w * )] ≤ PRIOR DIMENSION-DEPENDENT BOUND log 2 O Rσmax √ d/ε OUR DIMENSION-FREE BOUND log 2 O Rσ1/ε DIMENSION-FREE WITH LOGARITHMIC QUANTIZATION log 2 O (Rσ/ε) • log 1 + σ1/σ 2014)

convergence of training loss gap f (w)f (w * ) as we train low-precision SGD, showing the effect of different model sizes and precision.

Figure 1: (a) Quantization error bounds; (b) Convergence of full-precision (fp) SGD and LP-SGD.

The size of the noise ball is not significantly affected by model size d. The size of the noise ball does depend on σ1, especially when precision is low.

Figure 2: Plots of the asymptotic loss gap from Figure 1(b) as a function of model size d and σ 1 .

Variance and Bound for de-normal FPQ actual variance our bound (b) variance and bound for FPQ

Figure 3: A figure showing the actual quantization variance E Q(w) -w 2 2 and the tight upper bound that we introduced in one dimension. Similarly to 1(a) we plot this bound when taking the minimum over all possible z.

Figure 4: Plots of noise ball size vs. b e when running SGD with 16 bits FPQ on synthetic data set and MNIST. Note the use of two y-axes in Figure 4(b) to make the series fit in one figure.

f (w t ) -f (w * ))] ≤ w 0 -w * 2 2 -E w T -1 + ζL w * 2 + ζσ) 2 4µand since we sample w uniformly from(w o , w 1 , • • • , w T -1 ), we get E [(f ( w) -f (w * ))]

B 2 . When b is large, δ, ζ, η are small and the dominating term for the noise ball isA = δσ 1 + ζσ w * 2 x) = x • e x ,and Lambert W function W (y) = V -1 (y), y ≥ -1 e . then we need ∂A ∂n And when b is small, δ, ζ, η are large and the dominating term for the noise ball is B = δL 1 + ζL w * 2

ζσ w * Denote this as 1 2 A + 1 4µ B 2 . When b is large, δ, ζ, η are small, then the dominating term for the noise ball isA = δσ 1 + ζσ w * 2 = 4sσ 1And when b is small, δ, ζ, η are large and the dominating term for the noise ball isB = δL 1 +ζL w * 2 +ζσ = 4sL 1let the derivative of n e to be 0 and we get:For b such that neither the terms dominates the result, we know the noise ball size is:

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">√</td><td>1 2</td><td>ne + σ w  *</td><td>2</td><td>1 n m</td><td>= 4sσ 1</td><td>√</td><td>1 2</td><td>ne + σ w  *</td><td>2</td><td>n e C</td></tr><tr><td colspan="14">let the derivative over n e to be 0 and we get:</td></tr><tr><td colspan="2">∂A ∂n e</td><td colspan="5">= -2(ln 2)sσ 1</td><td colspan="2">√</td><td colspan="2">1 2</td><td colspan="3">ne + σ w  *</td><td>2</td><td>1 C</td><td>= 0,</td><td>√</td><td>2</td><td>ne</td><td>=</td><td>2(ln 2)sσ 1 C σ w  *  2</td></tr><tr><td/><td colspan="4">n e = 2 log 2</td><td colspan="9">2(ln 2)sσ 1 C σ w  *  2</td><td>, b e = log 2 2b + 2 log 2</td><td>2(ln 2)sσ 1 σ w  *  2</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="3">√</td><td>1 2</td><td>ne +(L w  *</td><td>2 +σ)</td><td>1 n m</td><td>= 4sL 1</td><td>√</td><td>1 2</td><td>ne +(L w  *</td><td>2 +σ)</td><td>n e C</td></tr><tr><td>∂B ∂n e</td><td colspan="5">= -2(ln 2)sL 1</td><td>√</td><td>1 2</td><td colspan="6">ne + (L w  *</td><td>2 + σ)</td><td>1 C</td><td>= 0,</td><td>√</td><td>2</td><td>ne</td><td>=</td><td>2(ln 2)sL 1 C L w  *  2 + σ</td></tr><tr><td colspan="4">n e = 2 log 2</td><td colspan="9">2(ln 2)sL 1 C L w  *  2 + σ</td><td>, b e = log 2 2b + 2 log 2</td><td>2(ln 2)sL 1 L w  *  2 + σ</td></tr><tr><td/><td/><td>1 2</td><td>A +</td><td>1 4µ</td><td colspan="3">B 2 =</td><td colspan="6">δσ 1 + ζσ w  *  2</td><td>2</td><td>+</td><td>(δL 1 + ζL w  *  4µ</td><td>2 + ζσ) 2</td></tr><tr><td colspan="5">then the derivative of n e is:</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td colspan="3">∂ ∂n e</td><td colspan="2">1 2</td><td colspan="4">A +</td><td>1 4µ</td><td>B 2 =</td><td>1 2</td><td>∂A ∂n e</td><td>+</td><td>B 2µ</td><td>∂B ∂n e</td></tr><tr><td colspan="14">and since both ∂A ∂ne and ∂B ∂ne are increasing functions and we know that:</td></tr><tr><td/><td/><td colspan="5">∂A ∂n e ne=2 log 2</td><td colspan="7">2(ln 2)sσ 1 C σ w  *  2</td><td>= 0,</td><td>∂B ∂n e ne=2 log 2</td><td>2(ln 2)sL 1 C L w  *  2 +σ</td><td>= 0</td></tr><tr><td colspan="8">then we know the solution of ∂ ∂ne</td><td colspan="6">1 2 A + 1 4µ B 2 = 0 is in the interval between 2 log 2</td><td>2(ln 2)sσ1C σ w  *  2</td></tr><tr><td>and 2 log 2</td><td colspan="4">2(ln 2)sL1C L w  *  2 +σ .</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td>2</td><td/><td/><td/><td/><td>2</td><td>+</td><td>(δL 1 + ζL w  *  4µ</td><td>2 + ζσ) 2</td></tr></table>

ζσ w *

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td>2</td><td/><td>2</td><td>+</td><td>(δL 1 + ζL w  *  4µ</td><td>2 + ζσ) 2</td></tr><tr><td colspan="4">then the derivative of n e is:</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td>∂ ∂n e</td><td/><td>1 2</td><td>A +</td><td>1 4µ</td><td colspan="3">B 2 =</td><td>1 2</td><td>∂A ∂n e</td><td>+</td><td>B 2µ</td><td>∂B ∂n e</td></tr><tr><td colspan="11">and since both ∂A ∂ne and ∂B ∂ne are increasing functions and we know that:</td></tr><tr><td/><td/><td colspan="2">∂A ∂n e ne=1-2 ln 2 W</td><td colspan="3">eσ w  *  2 8sσ 1</td><td colspan="2">= 0,</td><td colspan="2">∂B ∂n e ne=1-2 ln 2 W</td><td>e(L w  *  2 +σ) 8sL 1</td><td>= 0</td></tr><tr><td colspan="7">then we know the solution of ∂ ∂ne</td><td colspan="4">1 2 A + 1 4µ B 2</td><td>= 0 is in the interval between 1 -</td></tr><tr><td>2 ln 2 W</td><td>eσ w  *  8sσ1</td><td>2</td><td colspan="2">and 1 -2 ln 2 W</td><td colspan="4">e(L w  *  8sL1 2 +σ)</td><td/></tr></table>

Peer review (iclr2019):
 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. The paper shows that under a set of somewhat nonstandard assumptions, previously studied quantization functions as well as other low precision training algorithms are able to match the performance of non-quantized SGD, specifically, losing no additional dimension factors. Previous papers, to the best of my knowledge, did not prove such bounds, except under strong sparsity conditions on the gradients. I did not check their proofs line-by-line however they seem correct at a high level. I think the main discussion about the paper should be about the assumptions made in the analysis. As the authors point out, besides the standard smoothness and variance conditions on the functions, some additional assumptions about the function must be made for such dimension independent bounds to hold. Therefore I believe the main contribution of this paper is to identify a set of conditions under which these sorts of bounds can be proven. Specifically, I wish to highlight Assumption 2, namely, that the ell_1 smoothness of the gradients can be controlled by the ell_2 difference between the points, and Assumption 4, which states that each individual function (not just the overall average), has gradients with bounded ell_2 and ell_1 norm at the optimal point. I believe that Assumption 2 is a natural condition to consider, although it does already pose some limitations on the applicability of the analysis. I am less sold on Assumption 4; it is unclear how natural this bound is, or how necessary it is to the analysis. The main pros of these assumptions are that they are quite natural conditions from a theoretical perspective (at least, Assumption 2 is). For instance, as the authors point out, this gives very good results for sparse updates. Given these assumptions, I don’t think it’s surprising that such bounds can be proven, although it appears somewhat nontrivial. The main downside is that these assumptions are somewhat limiting, and don’t seem to be able to explain why quantization works well for neural network training. If I understand Figure 4b correctly, the bound is quite loose for even logistic regression on MNIST. However, despite this, I think formalizing these assumptions is a solid contribution. The paper is generally well-written (at least the first 8 pages) but the supplementary material has various minor issues. Smaller comments / questions: - While I understand it is somewhat standard in optimization, I find the term “dimension-independent“ here somewhat misleading, as in many cases in practice (for instance, vanilla SGD on deep nets), the parameters L and kappa (not to mention L_1 and kappa_1) will grow with the dimension. - Do these assumptions hold with good constants for training neural networks? I would be somewhat surprised if they did. - Can one get dimension independent bounds for quantized gradients under these assumptions? - The proofs after page 22 are all italicized. - The brackets around expectations are too small in comparison to the rest of the expressions.