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 low-precision floating-point computation and logarithmic quantization. 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 DISPLAYFORM0 where the objective f is strongly convex with parameter µ, low-precision SGD outputsw T 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. log 2 O (Rσ/ε) · log 1 + σ1/σ 2014). 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 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 ALGORITHMIn our work, we presented dimension-free bounds on the performance of low-precision SGD, here we present the algorithm in detail.
we proved dimension-independent bounds for low-precision training algorithms This paper discusses conditions under which the convergence of training models with low-precision weights do not rely on model dimension.