Enhancing Low-Precision Sampling via Stochastic Gradient Hamiltonian Monte Carlo
Authors: Ziyi Wang
Yujie Chen
Qifan Song
Ruqi Zhang
Venue: Accepted by TMLR ()

Abstract: Low-precision training has emerged as a promising low-cost technique to enhance the training efficiency of deep neural networks without sacrificing much accuracy. Its Bayesian counterpart can further provide uncertainty quantification and improved generalization accuracy.
This paper investigates low-precision sampling via Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) with low-precision and full-precision gradient accumulators for both strongly log-concave and non-log-concave distributions. Theoretically, our results show that to achieve $\epsilon$-error in the 2-Wasserstein distance for non-log-concave distributions, low-precision SGHMC achieves quadratic improvement ($\tilde{\mathcal{O}}\left({\epsilon^{-2}{\mu^*}^{-2}\log^2\left({\epsilon^{-1}}\right)}\right)$) compared to the state-of-the-art low-precision sampler, Stochastic Gradient Langevin Dynamics (SGLD) ($\tilde{\mathcal{O}}\left({{\epsilon}^{-4}{\lambda^{*}}^{-1}\log^5\left({\epsilon^{-1}}\right)}\right)$). Moreover, we prove that low-precision SGHMC is more robust to the quantization error compared to low-precision SGLD due to the robustness of the momentum-based update w.r.t. gradient noise. 
Empirically, we conduct experiments on synthetic data, and MNIST, CIFAR-10 \& CIFAR-100 datasets, which validate our theoretical findings. Our study highlights the potential of low-precision SGHMC as an efficient and accurate sampling method for large-scale and resource-limited machine learning.

Published in Transactions on Machine Learning Research (04/2024)
Enhancing Low-Precision Sampling via Stochastic Gradient Hamiltonian Monte Carlo
Ziyi Wang
wong/5888purdue.edl
Department of Statistics
Purdue Universily
Yujic Chen
166 edu
Department Statistics
Purdue University
Qifan Song"
afsong@purdue... edu
Department of Statistics
Purdue University
Ruqi Zhang"
rugizSpurdue.c edu
Department Computer Science
Purdue Universily
Reviewed on OpenReview: https: // openrevie.. net/ forum?? id= uSLNzzuiDJ
Abstract
training has emerged as a promising low-cost technique to enhance the train- ing efficiency of deep neural networks without sacrificing much accuracy. Tts Bayesian counterpart can further provide uncertainty quantification and improved generalization ac- curacy. This paper investigates low-precision sampling via Stochastic Gradient Hamilto- nian Monte Carlo (SGHMC) with low-precision and full-precision gradient accumulators for both strongly log-concave and non-log-concave distributions. Thcoretically, our results show that to achieve e-error in the 2-Wasserstein distance for non-log-concave distributions, low- precision SGHMC achieves quadratic improvement (0 log² (c-1)) compared to the state-of-tho-art low-precision sampler, Stochastic Gradient Langevin Dynamics (SGLD) (Ō (e-- log (E)) Moreover, we prove that low-precision SGHMC is more robust to the quantization error compared to low-precision SGLD due to the robustness of the momentum-beet based update w.r.t. gradient noise. Empirically, we conduct experiments synthetic data, and MNIST, CIFAR-10 & CIFAR-100 datascts, which validate our thcoreti- cal findings. Our study highlights the potential of low-precision SGHMC as an efficient and accurate sampling method for large-scale and snource-limited machine learning.
1 Introduction
In recent years, while deep neural networks (DNNs) stand out for their statc-of-art performance across various AI tasks, accompanied by an increase in model and computation complexity (Simonyan & Zisserman, 2014 He et al. 2016 Vaswani et al.] 22017 Radford et al. 2018 Chen et al. 2023). Addressing this challenge, techniques that enable efficient DNN processing become imperative to enhance efficiency and facilitate the widespread deployment of DNNs in AI systems (Courbariaux et al. 2015 Sze et al. 2017). Consequently, there is growing intersst in ut utilizing low-precision optimization techniques to address the computational and memory costs associated with these complex models (Sze et al.
2017) By employing reduced precision for
"Equal advising

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Theoretical results of the achieved 2- Wasserstein distance and the required gradient complexity for both log-concave (italic) and non-log-concave (bold) target distributions, where is any sufficiently small constant, A is the quantization error, and μ¹ and X denote the contraction rate of underdamped and overdamped Langevin dynamics respectively (Definition D Under non-log-concayy target distributions, low-precision SGHMC achieves a better upper bound within shorter iterations compared with low-precision SGLD.
Condition
Gradient Complexity
Achieved 2 Wassserstein
Full-precision gradient accumulators
SGLD/SGIIMC (Theorem
Strongly log-coneave
(log E-2) (E 4x- "log" (E (E"1)
Ô + A) c+ log (E VA
SGLD (Theorem
Non-log-concave
SGHMC (Theorem
Non-log-concave
(c 20 "log" (c-1)
c Vlog (c
Low-precision gradient accumulators
SGLD/SGIING (Theorem
Strongly log-coneave
① (log (e 1) 2)
Ô Ō
VC SGLD/VC SGHMC (Theorem
Strongly log- coneave
(log (e )-
0
SGLD (Theorem
Non-log-concave
x--xx-1 log (c-t)
c
+ log ((t)) [vV
VC SGLD (Theorem
9
Non-log-concave
δ (E -x-x--11 log" (e"))
0
c e (c)) (/34
SGHMC (Theorem
Non-log-concave
Ô (e 3p" log" (E11)
+ log 3/2 (c 11)) (3/3
VC SGHMC (Theorem
3
Non-log-concave
Ô 2522x= log² (c1))
θ
(e log (c 1 (1V
both model and data representations ( (e.g mixed-preeision, low-bits fixed-point, low-bit block floating point), significant imprvementss can be achieved in terms of DNN training speed and resource efficiency (Micikevicius
let al. 2017 Gupla et al. 2015 Li et al.
De Sa el al. 2017 Zhou et al. 2016). Notably, several recent 2018 Lin et al. 2019 Sun et al. 2019) demonstrated the successful application of 8-bit training techniques in accelerating the training of different models, such
2017
studies (Wang et al. 2018 Banner et al.
2018
Wu et al.
as VGG (Wu et al.) 2018), ResNet (Banner et al., 2018), LSTMs, Transformers (Sun et al.] 2019). and vision-language models (Wortsman al.) 2023).
With the increasing demand and huge success of complicated architecture such as Large Languages Mod- els (LLMs) and Vision-transfen transformers, a wide range of quantization methods are adopted to reduce the com- puting and memory consumption while retaining acceptable performances et al. 2023 Zhao et al. 2023)
Li et al. 2023 Xu et al. 2023 Xiao et al.) 2023). Readers can find more information on low-precision
optimization and model compression in the survey papers (Sze el al. 2017 Deng el al. 2020 Liang el al. 2021).
As a counterpart of low-precision optimization, low-precision sampling is relatively unexplored but has shown promising preliminary results. Zhhang et al. (2022) studied the effectiveness of Stochastic Gradient
Langevin Dynamics (SGLD) (Welling & Teh 2011 in the context of low-precision arithmetic, highlighting its superiority over the optimization counterpart, Stochastic Gradient Descent (SGD). This superiority stems from SGLD's inherent robustness to system noise compared with SGD.
Other than SGLD, Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) (Chen et al. 2014) is another popular gradient-based sampling method closely related to the underdamped Langevin dynamics. Recently, Cheng et al. (0188); Gao et al. (0022) showed that SGHMC converges to its target distribution faster than the best-known convergence rate of SGLD in the Wasscrsttnin distance under both strongly log-concave and non-log-concave assumptions. Beyond this, SGHMC is analogous to stochastic gradient methods augmented with momentum, which is shown to have more robust updates w.r.t. gradient estimation noise (Liu et al., 2020). Since the quantization inducedd stochastic error in low preeriiiioon updates acts as extra gradient noise, we believe SGHMC is particularly suited for low-precision arithmotic.
Our main ribuuionoo in this paper are threefold:
2

---

Published in Transactions on Machine Learning Research (04/2024)
We conduct the first study of low-precision SGHMC, adopting the low-precision arithmetic (in- cluding full- and low-precision gradient accumulators and the variance correction (VC) version of low-precision gradient accumulators) to SGHMC.
We present a thorough theoretical analysis of low-precision SGHMC for both strongly log-concave and non-log-concave target distributions. Beyond Zhang et al (2022) 's analysis for strongly log- concave distributions, we introduce an intermediale process for quantization noise management to facilitate the analysis of non-log-concave target distributions. All our theoretical results are summarized in Table [ where we compare the 2-Wasserstein convergence limit and the required gradient complexity. The table highlights the superiority of HMC-based now-precision algorithms over SGLD counterpart w.r.t. convergence speed and robustness to quantization error, especially under the non-log concave distributions.
We provide promising empirical results across various datasets and models. We show the sampling capabilitios HMC-basod low-prccision algorithms and the effoctiveness of the VC function in both strongly log-concave and non-log-concave larget distributions. We also demonstrate the superior performance of HMC-based low-precision algorithms compared to SGLD in deep learning tasks. Our code available here)
In summary, low-precision SGHMC emerges compelling alternative to standard SGHMC due to its ability to enhance speed and memory efficiency without sacrificing accuracy. These advantages position low-precision SGHMC as an attractive option for efficient and accurate sampling in scenarios where reduced precision representations are employed.
It is worth mentioning that precision gradient representations are also used in Federated Learning (FL) for either optimization (Gorbunov et al. 2021 Tyurin & Richtárik 2022) or sampling tasks {Vono et al. 2022 Sun et al., 2022 Karagulyan & Richtárik 2023). These methods low-precision representations for between-node communication, aiming to mitigate communication bottlenecks, but still utilize full-precision
arithmetic for local training. Thus these methods do not apply to the low-precision sampling challenge studied in this paper.
2 Preliminaries
2.1 Low-Precision Quantization
Two popular low-prccision number representation formats are known as the fized point (FP) and block floating point (BFP) (Song al. 2018). Theoretical investigation of this paper only considers the fixed point case, where the quantization error (i.e., the gap between two adjacent representable numbers) is denoted as A. For example, if we use 8 bits to represent a number where bit is assigned for the sign, 2 bits for the integer part, and bits for the fractional part, then the gap between two consocutive low-precision numbers is 2 2 i.e., A 2-5, Furthermore, all representable numbers are truncated to an upper limit 0 and a lower limit L.
Given the low-precision number representation, quantization function is desired to round real-valued mum- bers to their low- precision counterparts. Two common quantization functions deterministic rounding and stochastic rounding. The deterministic rounding function, denoted as Q", quantizes a number to its nearest representable neighbor. The stochastic rounding, denoted as Q* (refer to (19) in Appendix D randomly quantizes number to its close representable neighbor satisfying the unbiased condition, i.e. E() = 8. what follows, Qw and QG denote stochastic rounding quantizers for the weights and gradients respoctively, allowing different quantization errors (i.e., different A's for Qw and QG). For simplicity in the analysis and experiments, use the same number of bits to represent the weights and gradients.
3

---

Published in Transactions on Machine Learning Research (04/2024)
2.2 www-precision Stochastic Gradient Langevin Dynamics
When performing gradient updates in low-precision training, there are two common choices, full-precision and low-precision gradient accumulators depending whether we store an additional copy of full-precision weights. Low-precision SGLD (Zhng et al. 2022) considers both choices.
Low-precision SGLD with full-precision gradient accumulators (SGLDDL-FF) only quantizes weights before computing the gradient. The update rule can be defined as:
Xk+1 Xk 7 (VU(QW(ZH))) + 2nEx+1,
(1)
VU is the unbiased gradient estimation of U. Zhang et al. (2022) showed that the SGLDLP-F outperforms its counterpart low-precision SGD with full-gradient accumulators (SGDLP-F). The computation costs be further reduced using low-precision gradient accumulators by only keeping low-pree low-precision weights. Low- precision SGLD with low-precision gradient accumulators (SGLDIP--I) can be defined as the following:
X++1 = Qw (xx (Qaa(U((U))) + 22nEx+1).
(2)
Zhang et al. 2022) studied the convergence property of both SGLDLP-F and SGLDLP-T. under strongly- log-concave distributions and showed that small step size deteriorates the performance of SGLDLP-L. To mitigate this problem, Zhhnng et al. 2022 proposed variance-correeted quantization function (Algorithm in Appendix D)
2.3 Stochastic Gradient Hamiltonian Monte Carlo
Given dataset D, model with weights (i.e., model parameters) x Rd, and prior p(x), we are inter- ested in sampling from the posterior p(x[D) x exp(-U(x)), where U(x) = llg x - log p(x) is the energy function. In order to sample from the target distribution, SGHMC (Chen et al. 2014) is proposed
and strongly related to the underdamped Langevin dynamics. Cheng et al. (2018) proposed the following discretization of underdamped Langevin dynamics (10) with stochastic gradient:
Vk+1 V&e 70 uy -1 -1 VU(e) E%
(3)
Xk+1 = X + 1 >'> + my (mm + - (xx) + 5x
where u, y denote the hyperparameters of the inverse mass and friction respectively, and EX, & are normal distributed in IEd satisfying that
(EX =u[1 - 219)
(X) T = =uy =2ym 4e-ee-00 "" 27m 33 (EX) -uy- -u (1-- 20- + 22) I.
(4)
3 Low-Precision Stochastic Gradient Hamiltonian Monte Carlo
In this section, we investigate the convergence property of low-precision SGHMC under non-log-concave target distributions. We defer the convergence analysis of low-precision SGHMC under strongly log-concave target distributions, well the extension analysis under non-log-concan target distributions of low- precision SGLD (Zhang et al., 2022 to Appendix A and B respectively. All of our theorems based the fixed point representation and omit the clipping effect. We show that low-prccision SGHMC exhibits superior convergence rates and mitigates the performance degradation caused by the quantization error than low-precision SGLD, especially for non-log-concave target distributions. Similar to Zhang et al. (2022), we also observe an overdispersion phenomenon in sampling distributions obtained by SGHMC with low- precision gradient accumulators, and we examine the effectiveness of variance-correctdd quantization function in resolving this overdispersion problem.
4

---

Published in Transactions on Machine Learning Research (04/2024)
In the statement of theorems, the big-O O notation Ô gives explicit dependence on the quantization error A and concentration parameters (X", ux") but hides multiplicative terms that polynomially depend on the other parameters (e.g,, dimension d, friction inverse mass u and gradients variance o²). We refer readers to the appendix for all the theorems' proof. Before diving into theorems, we first introduce necessary assumptions
for the convergence analysis as follows:
Assumption (Smoothness). The energy function U is M-smooth, i.e, there exists a posilive conslant M such that
(x)
S M x yll?, for any ER.
Assumption 2 (Dissaptiveness). There exist constants m2, b > 0, such that the following holds (VU(x),x) 2 m2 ||x| -b, for any x E ERC
Assumption (Bounded Variance). There exists a constant o² > 0, such that the following holds
(U) - VU(x) S oo,, for any x E Rd.
Beyond the above assumptions, we further define K1 M/m (refer to Assumption in Appendix A and K2 = M/mz as the condition numbers for strongly log-concave and non-log-concave target distribution, respectively, and denote the global minimum of (x) as x*. All of our assumptions are standard and commonly used in the sampling literature. In particular, Assumption 2 is standard assumption (Raginsky et al. 2017 Zou et al. 2019; Gao et al. 2022) in the analysis of sampling from non-log-concave distributions and is essential to guarantee the convergence underdamped Langevin dynamics. Assumption can be further relaxed, allowing the variance of VU (x) scale up w.r.t x. Please refer to the appendix
Definition 1. Let and μr denote the contraction rates for continuous-time overdamped Longevin dy- namics and underdamped Langevin dynamics respectively. In other words, let It follow the overdamped (or underdamped) Langevin dynamics initialized at Ia = 0, n. be the invariant distribution, pt be the marginal distribution It, then X² and μ¹ salisfy
Wh n.) Ce-Aiu or Wi(p), S C/d
for some constant C.
The contraction rates μ² and X" are related to the nature of the Langevin dynamics. In general, the contraction rates exponentially depend on the dimension d. For example, two popular approaches to analyze the Wasserstein distance convergence property are the couplings method (Dalalyan & Riou-Durand] 2020)
Eberle el al. 2019) and Bakry Emery method based which the exponential convergence of the kinetic Bokker-Plance equation is proved (Bakry & Emery 2006 Baudoin 2016 2017). Unfortunately, both rates lead to exponential dependency dimension in general. It raises a crucial open question of whether restricted models can exhibit improved dimensional dependence. While overdamped Langevin diffusions have seen corresponding advancements, as evidenced in (Eberle et al., 2019 Zimmer 2017), analogous progress for underdamped Langevin diffusions remains underexplored. More detailed discussions of μ* and X* (and their uniform bounds) can be found in the Appendix C
3.1 Full-Precision Gradient Accumulators
Adopting the update rule in equations (SGHMCLP-F) as the following:
we propose low-precision SGHMC with full gradient accumulators
Vk+1 V&ū -M uy 1 1 ("UU))QVVUUUQWWW (xx))) + +
(5)
X X + (1-e-" uy uy + - - (VU (Xw()))) + Ex
which keeps full-precision parameters V3, Xg at each itcration and quantizes them to low-precision represen- tations before taking the gradient. Our analysis for non-log-concant distributions utilizes similar techniques in Raginsky et al. (207)). We are now ready to present our first theorem:
5

---

Published in Transactions on Machine Learning Research (04/2024)
Theorem 1. Assuming
1
2 and
3
hold. Let p" denote the target distribution of vx. If 4Mu and satisfying
setting the step size 7 O
14
log(1/e)
7 min {
4u2
6ybb
1
70
8(72 + 2u)
(8Mu + uy 227/2''
V
4Mu 3y2² (4Mu+ 372) d' 8Y 12(21u 7) (20u + 7/7
then after steps starting at the initial point Xo = vo = 0, the output (xK, of SGHMCLP-F in 15 satisfies
(c A Avios ())).
for some K salisfying
K K=O 0 (0=0())-
22 (2p0 log² )))
where conslants are defined as: Ā max {VA'd+o> VAdd+o')
Similar to the convergence result of full-precision SGHMC or SGLD RRaiinsky et al. 2017 Gao et al. 2022), the above upper bound of the 2- 2-Wasserstein distance contains an term and log(e" term. The difference is that for the SGHMCLP-F algorithm, the quantization error A affects the multiplicative constant of the log(e-1) term. Focusing on the effect of quantization error A, due to the fact that log(z) I x///, one can tune the choice of and 7 and obtain a Ô (A*/0+2ee) 2- 2-Wassesstein bound. As for the non- note that for full-precision sample algorithms, the best non-asymptotic convergence result in the 2- Wasserstein distance (Zou et al. 2019 Raginsky et al. 2017 Gao et al. 2022) also contain a log(s-1) factor which is brought by stochastic gradient noise, and diverge as E O. The non-convergence of our Wasserstein upper bound is due to the accumulation of stochastic gradient noise and stochastic discrction error. Conceptually, these random errors may average out over iterations when the ileration number increases Lo infinity (i.e., the law of large numbers), as the classical ergodic theory of Markov chain (Theorem 17.25, 17.28 of Kallenberg Kallenberg (997)). However, our mathematical tools lead to an upper bound that involves some weighted summation of the norm of these random errors over iterations rather than the summation of these random errors. Under strongly log-concave target distributions with no discretion error, this sum is bounded as (. -> oo and proportional to the stepsize, allowing for a sufficiently small step size to zero the bound Dalalyan & Karagulyan (2019); Cheng et al. (2018). However, for general cases, this sum grows to infinity. It is yet an open question to sharpen this type of analysis.
convergence of our result (i.e, log(e-1) term),
With the same technical tools, we conduct a similar convergence analysis of SGLDLF-P for non- log-concave larget distributions. The details are deferred in Theorem 7 of Appendix Compar- ing Theorems ! and Ô 1/2 (6-1) (10g)2((-11)
show that SGHMCLP-F can achieve lower 2- Wasserstein distance (i.e., 2/2 versus Ô (log (c-) (1/2) for non-log-concave larget distribution within fewer itera- tions (i.e., Ô 2 log² 10= the previous paragraph, after carefully choosing the stepsize n, the 2- 2-Wasserstein distance of the SGLDLF-P algorithm can be further bounded by Ô (A<((+22)) which is worse than the bound Ô (D=///tee (A<(++)))) obtained by SGHMC. We verify the advantage of SGHMCLF-P over SGLDLF-P by our simulations in section
(c-)) versus Ô (6-1x--1ogg log" (6-)) Furthermore, by the same argument in
3.2 Low-Precision Gradient Accumulators
The storage and computation costs of low-precision algorithms can be further reduced by low-precision gradient accumulators. We can adopt low-precision SGHMC with low-precision gradient accumulators (SGHMCLP-L) as
Vk+1 Qw (vie-m uy -1 -e + +
(6)
X Qw (xx + + -77)// + uy 2m + ~m - +
6

---

Published in Transactions on Machine Learning Research (04/2024)
Similar to the observation of Zhang et al. (0022 has larger variance than the target distribution (see Figures 1 (a) and 2 (a)), as the update rule (
also empirically find that the output Xx's distribution
introduces extra rounding noise. Our theorem in the section aims to support this argument. We present the convergence theorem SGHMCLP-L under con-log-concave target distributions.
Theorem 2. Assuming
1 and 3
hold. Let p" denote the target distribution of (x.v). If & 4Mu and satisfying
setting the step size r = O
log(1/e)
{
4u
6ybu
1
7y12
8(72 + 2n)
S min
(88M my 22
4Mu 372 (4Mu+ + 3)2) d' 8yy 12(21u 7)M2' (20u + ?)1
then after K steps starting at the initial point X = vo = 0, the output (xK, vK) of SGHMCLP-L, in satisfies
6
We(p(x vk).p") = ( (et max (o?, o0 log (
log (:) VA V2)
for some K satisfying
K K= ( log² )))
For con-log-concave target distribution, the output of the naive SGHMCLP-L has a worse convergence upper bound than Theorem ! The souree of the observed problem is the variance introduced by the quantization Qw, causing actual variances of (X&, V&) to be larger than the variances needed. In Theorem g generalize the result of the naïve SGLDLP-L in (Zhang et al. 2022 to non-log-concave target distributions, and we defer this theorem to appendix B Similarly, we observe that SGHMCLP-L needs fewer iterations than SGLDLP. L in terms of the order w.r.t. 6 and log(e-1) (Ó
(c22
t log² (c-1) versus Ô (c--x=11 log (s-1)) and (c- (o (A)
achieves better upper bound Ô Ôc-22log") (c-) VA versus δ
By the same argument in Theorem Ds discussion, after carefully choosing the stepsize 7, the 2- 2-Wasserstein distance between samples obtained by SGHMCLP-L and non-log-concans target distributions can be further bounded Ô (Ae/3366)), whilst the distance between the samples obtained by SGLDLP-L to the target can be bounded as Ô (As/10()=))) Thus, low-precision SGHMC more robust to the quantization error than SGLD.
3.3 Variance Correction
To resolve the overdispersion caused by low-precision gradient accumulators, Zhang et al. (2022) proposed quantization function Q"e (refer to Algorithm 2 in Appendix DD that directly samples from the discrete weight space instead of quantizing real-valued Gaussian sample. This quantization function aims to reduce the discrepancy between the ideal sampling variance (i.., the required variance of full-precision counterpart algorithms) and the actual sampling variance in our low-precisio algorithms. We adopt the variance- corrected quantization function to low-precision SGHMC (VC SGHMCLP-L) and study its convergence We extend the convergence analysis VC SGLDLP-L in Zhang el. al. (2022) to the case of the non-log-concave ributtiio as well. The details are deferred to Appendix B for comparison purposes. Let Vartme u(1---219 and Var -uy -2 which are the variances added by the underdamped Langevin dynamics in be done follows:
property for non-log-concay target distributions.
-00--e-2mm--0 23).)). The VC SGHMCLP-L can
Vk+1 = n
VRe V4 - -9
-uy -1-e (1==="))a((VVx Var Ame A).
(8)
X + -1 - e > + uy uy (17 + - 1)Qa Var hmc ))
Xk+1 = Que
The variance corrected quantization function " aims to output a low-precision random variable with the desired mean and variance. When the desired variance is larger than A2/4, which is the largest possible

---

Published in Transactions on Machine Learning Research (04/2024)
variance introduced by the quantization Q", the mariance-corrected quantization first adds small Gaussian noise to compensate for the variance and then adds a categorical random variable with desired variance. When v is less than / the cariance-correeteed quantization computes the actual variance introduced by Q". If it is larger than v, a categorical random variable is added to the weights to match the desired variance v. If it. is less than v, we will not be able to match the variance after quantization. However, this case arises only with exceptionally small step sizes. With the variance-correctoll quantization Que in hand, we now present the convergence analysis of the VC SGHMCLP-L for Non-log-concawy distributions.
Theorem 3. Assuming
1 and hold and F. (o(VU())) SPO
Let p" be the target distrituttion of salisfying
7/ S 4Mu and selling the slep size n Ô log(1/e)
x²
4u2
6ybu
1
7012
8(72 + 2u)
S min 488M + my 22-22² V
4Mu 372² (4Mu + 3x2) d' By 12(21u + 7) (20u + +)7
then after K steps starting at the inátial point Xa vo = 0 the output (xx) of the VC SGHMCLP-L in satisfies
Wx(p(xx);p')= (c(
c+ 0(ct(
1 max fo?, log (:) + log (2) VA
(9)
for some K satisfying
K K= Ō 22 ( log² (t)
Compared with Theorem cannot show that the variance corrected quantization fully resolves the overdispersion problem observed for non-log-concave target distributions. However comparing with Theo- 2 we show in Theorem 3 that the variance-corrected quantization can improve the upper bound w.r.t. from δ (2-2 (c V to Ô ( (c-) VA) In Theorem we generalize the result of the 2022) to non-log-concen concave target distributions, and we defer this theorem
rem
VC SGLDLP-L in ZZhang to appendix B Similarly, observe that VC SGHMCLP-L needs fewer iterations than VC SGLDLP-L in terms of the order w.r.t. and log(e-1) (0(e-2p-- log (c- versus Ô (c-1>>-110g (t))
Beyond the above analysis, we apply similar mathematical tools and study the convergence property of VC SGHMCLP-L and VC SGLDLP-L in terms of for non-log-concave target distributions. Based on the Theorem and 3 the variance-corrected quantization can improve the upper bound from Ô (AA-/(466)) to (A (e))) Compared with VC SGLDLP-L, the VC SGHMCLP-L has a better upper bound (i.e. δ (2=(()+))) versus Ô (A</((++))). Interestingly, the naive SGHMCLP-L has similar dependence the quantization error A with VC SGLDLP-L but saves more computation resources since the variance corrected quantization requires sampling discrete random variables. We verify our findings in Table 4
4 Experiments
We evaluate the performance of the proposed low- www-precision SGHMC algorithms across various experiments: Gaussian and Gaussian mixture distributions (Section 4.1 Logistic Regression and Multi-Layer Perceptron (MLP) applied to the MNIST dataset (Section 4.2 and ResNet-11 both CIFAR-10 and CIFAR-100 datasets (Section 4.3 Additionally, compare the accuracy of our proposed algorithms with their SGLD counterparts. Throughout all experiments, low-precision arithmetic is implemented using gtorch (Zhang et al. 2019). Beyond our theoretical settings, our experiments encompass a range of low-precision setups, in- cluding fixed point, block floating point, as well as quantization of weights, gradients, errors, and activations. For more details of our low-precision settings used in experiments, please refer to Appendix [
4.1 Sampling from standard Gaussian and Gaussian mixture distributions
We first demonstrate the performance of low-precision SGHMC for fitting synthetic distributions. We use the standard Gaussian distribution and Gaussian mixture distribution to represent strongly log-concave and
8

---

Published in Transactions on Machine Learning Research (04/2024)
0.4
Tuee SGHMCLP-
0.4
Thu
VC SCHNCLLLL
0.4
Tru SGHMMLLI-F
Devecty
Denetty
Dondty
0.2
0.2
0.2
0.3
0.0
0.0
(a)
(b)
(c)
Figure 1: Low-precision SGHMC on a Gaussian distribution. (a): SGHMCLP-L. (b): VC SGHMCLP-L. (c): SGHMCLP-F. VC SGHMCLP-L and SGHMCLP-F converge to the true distribution, whereas naïve SGHMCLP-L suffers a larger variance.
0.4
SCHMCLFFL
True
0.4
Thue
SCHMCLFFL
0.4
Trie
SCHMCLE-F
0.3
0.3
Denetty
Donnty
Dundly
0.2
0.1
0.1
0.5
0.0
(a)
(b)
Figure 2: Low-precision SGHMC with Gaussian mixture distribution. (a): SGHMCLP-L. (b): VO
SCHMCLP-L. (c): SGHMCLP-F. VC SCHMCLP-T, and SGHMCLP-F converge to the true distribution, whereas naïve SGHMCLP-L suffers larger variance.
0.8
SGHMCLP-L
SGHMCLP-P SGLDLP-F'
Log 1:2 Distance of Donsit
VC SGIIMCLP-
Log Distance Density
SGLDLF-L
0.6
0.6
VC SGLDIP-LL
0.4
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Iteration
x10
Iteration
x10"
(a)
(b)
Figure 3: Log L2 distance from sample density estimation obtained by low fow-precision SGHMC and SGLD to the Gaussian mixture distribution. (a) Low-precision gradient accumulators. (b): Full-precision gradient accumulators. Overall, SGHMC methods enjoy a faster convergence speed. In particular, SGHMCLP-L
achieves a lower distance compared to SGLDLP-L and VC SGLDLP-L.
non-log-concave distribution, respectively. The density of the Gaussian mixture example is defined as
U() 2 111 1| 2|x++11?
We use bit fixed point representation with of them representing the fractional part. For
please the Appendix D The simulation results shown in Figure 1 and 2 From Figure [(a) and 2 aa.

---

Published in Transactions on Machine Learning Research (04/2024)
see that the sample from naive SGHMCLP-L has larger variance than the target distribution. This verifies the results we prove in Theorem 2 In Figure [bb and [b,, we verify that the variance-corrected quantizer mitigates this problem by matching variance of the quantizer to the variance Var defined by the underdamped Langevin dynamics 10 Figure we compare the performance of low-precision SGHMC with low-precision SGLD for sampling from Gaussian mixture distributtin. Since calculating the Wasserstein distance over long iterations is time-consuming, instead of computing the Wasserstein distance, we resort L2 distance of the sample density estimation the true density function. It shows that low- precision SGHMC enjoys faster convergence speed and smaller distance, especially SGHMCLP-L compared to SGLDLP-L. and VC SGLDLP-I.
We also study in which case the variance- corrected quantizer is advantageous over the naïve stochastic quantization function. We test the 2- Wasserstein sampling error of VC SCHMCLP-L and SGHMCLP-L, over differ- ent variances. The result is shown in Figure
1.0
0.9
We find that when the variance Var hmc is close to the largest quantization variance A2/4, the variance corrected quantization func- tion shows the largest advantage over the naïve quantization. When the variance Vark is less than 2 the correction has a chance to fail. When the variance Var the quantization variance, the advantage of variance-correeted quantizer shows less advan- tage. One possible reason is that the quan- tization variance eliminated by the variance- corrected quantizer not critical compared Varcmm which is the intrinsic variance for SGHMC. We advocate for the adoption of variance-correcled quantization under the specific condition where the ideal variance approximates 22/4. Our observations indicate that this scenario yields the most significant performance gains. Conversely, in other situations, we suggest employing naïve low-precision gradient accumulators, as they offer comparable performance while conserving computational resources.
Datance
0.7
80
Variance Ratio
Aie is 100 times
Figure 4: Mean (dotted line) and 95% confidence inter- val (shaded area) of 2- 2-ssssesttein error ratio between VC SCHMCLP-L. & SGHMCIP-LI (Smaller means the variance correction is more effective), computed over 5 experimental runs. The x-axis represents the ratio between Var Ame and A2/4.
4.2 MNIST
In this section, we further examine the sampling performance of low- now-precision SGHMC and SGLD on strongly log-concave distributions and non-log-concave distributions real-world data. We use logistic and multilayer perceptron (MLP) models to represent the class of strongly log-concave and non-log-concave distributions, respectively. The results are shown in Figure and 6 We use N (0, 10-2) as the prior distribution and fixed point number representation, where we set 2 integer bits and various fractional bits. A smaller number of fractional bits corresponds to a larger quantization gap A. For MLP model, we use two-layer MLP with 100 hidden units and ReLu nonlinearities. We report the training negative log-likelihood (NLL.) with different numbers of fractional bits in Figure and For detailed hyperparameters and experiment sctup, please see Appendix D
From the results MNIST, we see that when using full-precision gradient accumulators, wwwpprecisinn SGHMC are robust to the quantization error. Even when we use only 2 fractional bits, SGHMCLP-F can still converge to a distribution with a small and stable NLL but with more iterations. However, regarding low-precision gradient accumulators, SGHMCLP-L and SGLDLP-L are less robust to the quantization error. As the precision error increases, both SGHMCLP-L and SGLDLP-L have worse convergence pattern com- pared to SGHMCLP-F and SGLDLP-F. We showed empirically that SGHMCLP-L and VC SGHMCLP-L outperform SGLDLP-L. and VC SGLDI.P-L. As shown in Figure 5 and 6 when increase the quanti-
10

---

Published in Transactions on Machine Learning Research (04/2024)
3.5
SCHMCLL-LL VC SCHMCLP-L S VC SCLDLF-L
3.0
SCHECCLF-P SGLDLP-F
S SCLDLP-L
Log Thnis N1.
2.5
Log Toais NLL
1og Train NLT.
62
1.5
1.0
0.0
oF
500
1500
1000
1000
1500
Iseration
Ineration
Exraatio
(a)
(b)
Figure 5: Training NLL of low-precision SGHMC and SGLD logistic model with MNIST in terms of different numbers of fractional bits. (a): Full-precision gradient accumulators. (b): Low-preciste gradient accumulators. (c): Variance-corrected quantizer. SGHMCLP-F achieves comparable results with SGLDLP- F. However, both SGHMCLP-L and VC SGHMCLP-L show more robustness to quantization error, especially when the number of representable bits low. Please be aware of the different scales y-axis across three figures.
30
SCHIMCLP-F 4
SCHMCLF-L SCHMCLF-L
VO SCHMCLP-L
30
10
VC SCHMCLP-L2
SGLDLP-F
SOLDLP-L
VO SOLDLP
Log Thain NLL
SGLDLE-F
Leg Train NL.
SCLDLP-L
Log Train NLL
VC SCLDLP-L
2.0
1.5
0.5
0.0
500
1000
1500
500
1000
1500
500
1000
1500
Iraration
Iterratio
Iteration
(a)
(b)
(c)
Figure 6: Training NLL of low- www-precision SGHMC and SGLD on MLP with MNIST in terms of different mum- bers of fractional bits. (a): Full-precision gradient accumulators. (b): Low-precision gradient accumulators. (c): Variance-correetedd quantizer. SGHMCLP-F achieves comparable results with SGLDLP-F. However, both SGHMCLP-L. and VC SCHMCLP-L, show robustness to quantization error, especially when the number of representable bits is low. Please be aware of the different scales of y-axis across three figures.
zation error, SGHMCLP-L and VC SGHMCLP-L are more robust than SGLDLP-L and VC SGLDLP-L, respectively.
4.3 CIFAR-10 & CIFAR-100
We consider image tasks CIFAR-10 and CIFAR-100 the ResNet-18. We 8-bit number representation following Zhang et al. 20222. We report the test errors averaging over runs in Tables and For detailed hyperparameters and experiment setup, please see Appendix D
Fixed Point We employ fixed point representations for both weights and gradients while retaining full precision for activations and errors following previous work (Zhang al. 2022). From the figure, unsur- prisingly the full-precision algorithms outperform their low-precision counterparts. But with long enough iterations the performance gap between SGHMC/SGII and WWWMMCCP-F//GLLLEE zero. Similar to the results in previous sections, SGHMCLP-F is comparable with SGDLP-F, and the naive SGHMCLP-L significantly outperforms naïve SGLDLP-L and SGDLP-L across datasets and architectures. For example, SGHMCLP-L outperforms SGLDLP-L by 1.19% on CIFAR-10, 10, and SGHMCLP-L outperforms SGLDLP-L. by 0.58% on CIFAR-100. Furthermore, from the result in Figure
converges toward
we empirically show that
11

---

Published in Transactions on Machine Learning Research (04/2024)
2
2
Log Train NLL
Log Train NLL
-1
-1
-2
SGLDLE-F
-2
SGLDLEE FF
SGLDEP
SGLIE P.P-
3
-3
SCHMC
SCHMC
SGHMELF-F
SGHMOLP-P
SCHMCLESE
SGHMCLESL
20000
40000
60000
80000
20000
40000
60000
80000
Iteration
Iteration
(a)
(b)
Figure 7: Log of training NLL of low-precision SGHMC and SGLD on ResNet-18 with CLEAR-100. (a): 8-bits Fixed Point. (b): &-bits Block Floating Point. For fixed point representations, low-precision SGHMC shows faster convergence and SGHMCTP-L, outperfsms SGLDLP-L and VC SGLDLP-LL
the convergence speed of SGHMC is way better than the convergence speed of SGLD. SGHMCLP-L even achieves faster convergence than SGLDLP-F. When the variance Var is comparable with or less than A we recommend implementing SGHMCLP-L rather than VC SGHMCLP-L. This is the case when we assess the performance of low-precision SGHMC on CIFAR-10 and CIFAR-100. Notably, even in the absence of the performance enhancereent provided by the variance-corrected quantization function, the test results indicate that SGHMCLP-L's performance is on par with its SGLD counterpart with variance correction. This result verifies our findings in Theorems 2 and g
We also consider the block floating point (BFP) representation adopted with deep models, which causes less quantization error and thus performs better compared with fixed point represen- tation (Song et al. 2018). Given sufficient iterations, the performance differences between SCHMC/SGLD and SGHMCLP-F SGLDLP-F almost disappear. As illustrated in plot b) of Figure 7 SGHMCLP-F out- performs full-precision SGLD in block floating point low-prccision format. By using BFP, the performance of all low-precision methods improves over fixed point representation. The naive SGHMCLP-L outperforms the naïve SGLDLP-L 0.82%. Moreover, the naïve SGHMCLP-L achieves comparable results with the VC SGLDLP-L method, and SGHMCLP-L can save more computation resources since the variance-corrected quantization function would need to sample additional categorical random vector с E Rd at each iter- ation. Let Vargeld 2n denote the variance added by overdamped Langevin dynamics in 14p. For most deep learning tasks, a small step size is preferred, and thus there is large chance that Var which case we recommend running the naïve SGHMCLP-L to achieve comparable accuracy and save more computation resources.
Block Floating Point
aytal < A2/4 in
Expected Calibration Error To study the model calibration of low precisieci SGHMC, we further report the results of expected calibration error (ECF) (Guo et al. 2017) Table and We observe that sometimes SGLDLP-L and SGLDLP-F achieve lower ECE than the full-precision SGLD counterpart, implying that the corresponding sample distributions deviate from the true target posterior. We conjecture that it is caused by the implicit regularization effect of the operator Qw. On the other hand, observe that SGHMCLP-F and SGHMCLP-L have almost the same ECE as full-precision SGHMC in CIFAR-10, showing that low-precision arithmetic does not degrade the calibration ability of SGHMC. In the CIFAR-100 dataset, HMC-based www-precision algorithms outperform their SGLD counterparts, especially SGHMCLP. F, which outperforms SGL.LLP-F around 1.4% fixed point representation for the CIFAR-100 task. For the low-precision gradient a ccumulators method, SGHMCLP-L and VC SGHMCLP-L achieve comparable better ECE with SGLDL.P-L. and VC SGLDLPP-L and dramatically outperform low-precision SGD.
12

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Test errors (%) of full-precision gradient ac- cumulators on CIFAR with ResNct-18. SGHMCLP-F achieves comparable results with SGLDLP-F.
Table 3: FCE (%) of full-precision gradient accu-
mulators on CIFAR with ResNet-18. SGHMCLP-F
achieves comparable ECE with SGLDLP-E.
CIFAR-10 CIFAR-100
CIFAR-10 CIFAR-100
32-bit Float
32-bit Float
SGD
4.73
22.34
SGD
2.50
4.97
SGLD
4.52 + 0.07
22.40
+ 0.04
SGLD
1.12
3.71
SGHMC
4.78 0.08
22.37
à 0.04
SGHMC
0.72
1.52
8-bit Fixed Point
8-bit Fixed Point
SGD
5.19 0.09
23.71
+ 0.18
SGD
2.79
7.11
SGLD
5.07 + 0.04
23.36
0.10
SGLD
0.86
3.57
SGHMC
5.08
23.54
SGHMC
1.11
1.92
8-bit Block Floating Point
8-bit Block Floating Point
SGD
4.75 = 0.21
22.86 + 0.14
SCD
2.43
5.97
SGLD
4.58 0.07
22.70
SGLD
1.01
3.87
SGHMC
4.93 # 0.09
22.39 0.11
SCHMC
1.12
3.65
Table 4: Test errors (%) of low-precision gradient accumn-
Table 5: ECE (%) of low-precision gradient ac-
lators on CIFAR with ResNet-18. SGHMCLP-L and VC SGHMCLP-L outperform SGLDLP-L and VC SGLDLP-
cumulators on CIFAR with ResNet-18. Low-
precision SGHMC are less affected by the quan- Lization error.
L, respectively. SGHMCLP-L achieves comparable results with VC SGLDLP-L.
CIFAR-10 CIFAR-100
CIFAR-10
CIFAR-100
32-bit Float
bit Float
SGD
2.50
4.97
SGLD
1.12
3.71
SGD
4.73 0.10
22.34
0.22
SCHMC
0.72
1.52
SGLD
4.52 0.07
22.40
+: 0.04
8-bii Fixed Point
SGHMC
4.78 + 0.08
22.37
+ 0.04
SGD
5.12
12.92
8-bit Fixed Point
SGLD
1.67
1.11
SGD
8.50 +: 0.22
28.42 + 0.35
VC SGLD
0.60
2.89
SGLD
7.81
27.15 + 0.35
SGHMC
0.72
2.46
VC SGHMC
0.70
2.44
VC SGLD
7.03 #0.23
26.73
=0.12
SCHMC
6.63 0.10
26.57
1: 0.10
8-bit Block Floating Point
VC SGHMC
6.60 0.06
26.43
0.19
SGD
4.62
13.93
SGLD
0.67
8-bit Block Floating Point
VC SGLD
0.60
5.09
SGD
5.86
26.75
SCHMC
0.78
4.94
SGLD
5.75 #0.05
26.11#0.38
VC SGHMC
0.67
5.02
VC SGLD
5.51 20.0
24.14 20.11
SGHMC
5.38
25.29
VC SCHMC
5.15 10.08
24.45 10.16
5
Conclusion
We provide the first comprehensive investigation for low-precision SGHMC in both strongly log-concave and non-log-concave target distributions with several variants of low-precision training. In particular, we prove that for non-log-concave distributions, low-precision SGHMC with full-precision, low-precision, and variance- corrected gradient accumulators all achieve an acceleration in iterations and have a better convergence upper bound w.r.t. the quantization error compared to low-precision SGLD counterparts. Morcover, we study the improvement of variance-correcter quantization applied low-precision SGHMC under different cases. Under certain conditions, the naïve SGHMCLP-LI replace the VC SGLDLP-L, to get comparable results,
13

---

Published in Transactions on Machine Learning Research (04/2024)
saving computation resources. We conduct empirical experiments Gaussian, Gaussian mixture distribution, logistic regression, and Bayesian deep learning tasks to justify our theoretical findings.
References
Dominique Bakry and Michel Emery. Diffusions hypercontractives. In Séminaire de Probabilités XIX 198 Proceedings, pp. 177-206. Springer, 2006.
Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. Scalable methods for 8-bit training of neural networks. Advances in neural information processing systems, 31, 2018.
Fabrice Baudoin. Wasserstein contraction properties for hypoelliptic diffusions.
arXiv preprint
arXiv:1602.n 17777 2016.
Fabrice Bandoin. Bakry émery meet villani. Journal of functional analysis, 273 2291, 2017.
François Bolley and Cédric Villani. Weighted portation inequalities. In Annales de la Faculté des sciences de Toulouse: Malhémaliques, volume 14, pp. 331- 151-352,20 2005.
inequalities and applications to trans-
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient hamiltonian monte carlo. In International conference on machine learning, 1683-1631 1691. PMLR, 2014.
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, et al. Symbolic discovery of optimization algorithms. arXiv preprint arXiv:2302.0667. 2023.
Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael I Jordan. Underdamped langevin meme: A non-asymptotic analysis. In Conference on learning theory, pp. 300-323. PMLR, 2018.
Matthieu Courbariaux, Yoshua. Bengio, and Jean-Pierre David. Binaryconnect: Training deep neural net- works with binary weights during propagations. Advances in neural information processing systems, 28, 2015.
Matteo Croci, Massimiliano Fasi, Nicholas J Higham, Theo Mary, and Mantas Mikaitis. Stochastic rounding: implementation, error analysis and applications. Royal Society Open Science, (33):211631, 2022.
Arnak S Dalalyan and Avetik Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):5278-533 5311, 2019.
Arnak S. Dalalyan and Lionel Riou-Durand. On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli, 26(3):1956 1988, 2020. doi: 10.3150/19- 1.3150/19-BEJJIN BEJ1178 URL http:::/ddoi.org////
3150/19-BEJ1178
Christopher De Sa, Matthew Feldman, Christopher Ré, and Kunle Olukotun. Understanding and optimizing asynchronous low-precision stochastic gradient descent. In Proceedings of the 44th Annual International Symposium on Computer Architecture, pp. 561-574, 2017.
Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108(4):485-53,, 2020.
Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. Couplings and quantitative contraction rates for Langovin dynamics. The Annals of Probability, 47(4):1982 2010, 2019.
Xuefeng Gao, Mert Gürbüzbalaban, and Lingjiong Zhu. Global convergence of stochastic gradient hamil- tonian monte carlo for nonconvex stochastic optimization: Nonasymptotic performance bounds and momentum-based acceleration. Operations Research, 70(5) 2022.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non-convex distributed learning with compression. In International Conference on Machine Learning, pp. PMLR, 2021.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical procision. In International conference on machine learning, pp. 1737-1746. PMLR, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE conference on compuler vision and paltern recognilion, pp. 770 778, 2016.
Olav Kallenberg and Olav Kallenberg. Foundations of modern probability, volume Springer, 1997.
Avetik Karagulyan and Peter Richtárik. Elf: Federated langevin algorithms with primal, dual and bidirec- tional compression. arXiv preprint arXiv:2303.cm 0ete2290004622,, 2023.
Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. Advances in neural information processing systems, 2017.
Zheng Li and Christopher M De Sa. Dimension-fre free bounds for low-precision training, Advonces in Neural Information Processing Systems, 32, 2019.
Zhikai Li, Junrui Xiao, Lianwei Yang, and Qingyi Gu. Repq-vit: Scale reparameterization for post-training quantization of vision transformers. In Proceedings of the IEEE/CVF International Conference on Com- puter Vision, pp. 17227-17236, 2023.
Tailin Liang, John Glossner, Lei Wang, Shaobo Shi, and Xiaotong Zhang. Pruning and quantization for deep neural network acceleration: A survey. Neurocomputing, 461:370 403, 2021.
Po-Chen Lin, Mu-Kai Sun, Chuking Kung, and Tzi-Dar Chiuch. Floatsd: A new weight representation and associated update method for efficient convolutional neural network training. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 922)2267-279 2019.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271, 2020.
Yijiang Liu, Huanrui Yang, Zhen Dong, Kurt Keutzer, Li Du, and Shanghang Zhang. Noisyquant: Noisy bias- enhanced post-training activation quantization for vision transformers. Tn Proceedings of the IRFE/CVF Conference Computer Vision and Pattern Recognition, pp. 20321 20330, 2023.
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al. Mixed precision training, arXiv preprint vrXiu:1710.037/00 2017.
Alec Radford, Karthik Narasimhan, Tim Salimans, Llya Sutskever, et al. Improving language understanding by gencrative pre-training. 2018.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pp. 1674-1703, PMT.R, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXio: 1556, 2014.
Zhourui Song, Zhenyu Liu, and Dongsheng Wang. Computation error analysis of block floating point arithmetic oriented convolution neural network accelerator design. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Lukang Sun, Adil Salim, and Peter Richtárik. Federated learning with sampling algorithm under isoperime- try. Xiu preprint arXio:2206. 200:220000090, 2022.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Xiao Sun, Jungwook Choi, Chia-Yu Chen, Naigang Wang, Swagath Venkataramani, Vijayalakshmi Viji Srinivasan, Xiaodong Cui, Wei Zhang, and Kailash Gopalakrishnan. Hybrid 8-bit floating point (hfp8) training and inference for deep neural networks. Advances in neural information processing systems, 32, 2019.
Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S Emer. Efficient processing of doep neural networks: A tutorial and survey. Proceedings of the IEEE, 105(12):2295 2329, 2017.
Alexander Tyurin and Peter Richtárik. Dasha: Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization. arXiv preprint arXiv:2202.c 0628, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Maxime Vono, Vincent Plassier, Alain Durmus, Aymeric Dieuleveut, and Eric Moulines. Qlsd: Quantised langevin stochastic dynamics for bayesian federated learning. Tn International Conference on Artificial Intelligence and Statistics, pp. 6459 6500. PMLR, 2022.
Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yo Yu Chen, and Kailash Gopalakrishnan. Training deep neural networks with 8-bit floating point nunbers. Advances in neurol informalion processing systems, 31, 2018.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICMI-111, pp. 681-688, 2011.
Mitchell Wortsman, Tim Dettmers, Luke Zettlemoyer, Ari Morcos, Ali Farhadi, and Ludwig Schmidt. Stable and low-procision training for large-scale vision-language models. arXiv preprint arXiv:2304.13013 2023.
Shuang Wu, Guoqi Li, Feng Chen, and Luping Shi. Training and inference with integers deep neural networks. Xiv preprint arXic:1802.04 04680, 2018
Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models. In International Conference on Machine Learning, pp. 38087 38099. PMLR, 2023.
Yuhui Xu, Lingxi Xie, Xiaotao Gu, Xin Chen, Heng Chang, Hengheng Zhang, Zhensu Chen, Xiaopeng Zhang, and Qi Tian. Qa-lora: Quantization-aware low-rank adaptation of large language models. arXiv preprinl ar Xiv: 14717, 2023.
Guandao Yang, Tianyi Zhang, Polina Kirichenko, Junwen Bai, Andrew Gordon Wilson, and Chris De Sa. Swalp: Stochastic weight averaging in low precision training. In International Conference on Machine Learning, pp. 7015 7024. PMLR, 2019.
Ruqi Zhang, Andrew Gordon Wilson, and Christopher De Sa. Low-precision stochastic gradient langevin dynamics. In International Conference on Machine Learning, pp. 26624-26644. PMLR, 2022.
Tianyi Zhang, Zhiqiu Lin, Guandao Yang, and Christopher De Sa. Qpytorch: A low-precision arithmetic simulation framework. In 2019 Fifth Workshop on Energy Efficient Machine Learning and Cognâtive Compaling-NurrPP5 Edition (EMC2-NIPS), pp. 13. IEFF, 2019.
Yilong Zhao, Chien-Yo Yu Lin, Kan Zhu, Zihao Ye, Lequn Chen, Size Zheng, Luis Ceze, Arvind Krishnamurthy, Tianqi Chen, and Baris Kasikci. Atom: Low-bit quantization for efficient and accurate Ilm serving. ar preprint XrXio:2310. 19102, 2023.
Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-nct: Training low bitwidth convolutional neural networks with low bitwidth gradients. orXiv preprint orXiv:1606. 0666066666666. 2016.
16

---

Published in Transactions on Machine Learning Research (04/2024)
Raphael Zimmer. Explicit contraction rates for class of degenerate and infinite-dimensionall diffusions.
Stochaslics and Partial Differential Equalions: Analysis and Compulalions, 5:368- (0088-39,,-9 2017.
Difan Zou, Pan Xu, and Quanquan Gu. Stochastic gradient hamiltonian monte carlo methods with recursive variance reduction. Advances in Neural Information Processing Systems, 32, 2019.
17

---

Published in Transactions on Machine Learning Research (04/2024)
A Additional Results for Low-precision Stochastic Gradients Hamiltonian Monte Carlo
In this section, we mainly summarize the theoretical results of Low-precision SGHMC under strongly log- concave target distribution. The underdamped Langevin dynamics be defined as:
dv, = VV vV (x,) + /2yudB,
(10)
dx, Vadl,
where (x,, vo) E R2dd and u, 7 denole the hyperparameters of inverse mass and friction respectively. We introduce the the strongly-log-conean concavee assumption as: Assumption 4 (Strongly Log- Log-Convex). The eneryy function U is m-strongly log-convez, i.e, there exists positive constant such that,
Uly) +VU())) x) yy x|? for any x. E RRd
Once we introduce the continuous underdamped Langevin dynamics 10 we are ready to find a contraction
rate for 110. According to
Theorem 4. Suppose Assumptions let p' denote the target distribution of x and v. Given any sufficiently small c, if we set the step size to be
and 4 hold and the minimam satisfies ||x* < D2. Furthermore,
2²
= min 4 D 1440k u² [[M2 + 1) Add + +
then after K steps starting with initial points Xy vo vo=0, 0, the output (xK. vK) of the SGHMCLP-F salisfies
vK), s (6
for some K satisfying
36
D2 mi
<
K1
log
= - =Ō (E-2log (c A²).
Theorem 1 in Zhang et al. SGLD with full-precision gradient accumulators can achieve e accuracy within Ô (c log (c-l) }) itera- tions. Thus, the theorem of SGHMCLP-F does not showcase any advantage over SGLDLP-F. This is not surprising, since the quantization applied to the gradients in the full-preeision gradient accumulator algo- rithun is equivalent to adding extra noise to the stochastic gradients. As theoretically shown by [Cheng et al.) (2018) for strongly-log-coneee concave target distribution, SGHMC doesn't exhibit any advantage over the over- damped Langevin algorithm when stochastic gradients are used. Now we present the convergence analysis of SGHMCLP-L under strongly log-concave target distributions.
(002 implies that for strongly log-concave target distribution, the low-precision
Theorem 5. Let Assumption and hold and the minimum satisfies ||x*1] < DD2 Purthermore, let p denote the larget distvibution of and Given any sufficienlly small e, we set the step size n to be
EKi
17 = min
2880k u AAd
σ2)
663552/5 /
+ D2)
mi
then after K steps starting with inūtial points Xy vo = 0, the output (XK, vx) of the SGHMCLP-L satisfies
(6)
Wa(p(xk, -0((= -
(11)
18

---

Published in Transactions on Machine Learning Research (04/2024)
for some K such that
36
+ D2
log K 5
K1 !
O (E (E-2 (c=1) A2).
show that for strongly log-coneave target distribution the naïve SGHMCLP-L has worse convergence upper bound than SGHMCLP-F, Since SGHMCLP-L directly quantizes the weights after each update, small stepsize update is often quantized to zero, resulting in the sample distribution converging to a Dirac distribution at the initial point. In such cases, ensuring convergence becomes challenging. Compared with Theorem in Zhang et al. (2022), We cannot show the advantages of low-precision SGHMC over SGLD. Next, we present the theorem for VC SGHMCLP-L under strongly log-concave target distribution.
Comparing Theorem 4 and Theorem
Theorem 6. Let Assumption and hold and the minimum satisfies ||x < DD, Furthermore, let p denote the target distribution of and Given any sufficiently small e, set the stepsize to be
2
7) min
479232/5
d + D2
K1
90m2 + 300
mi
after K steps starting from the initial point Xo = vo satisfies
the output (xx, vx) of the VC SGHMCLP-I, in
Wa(p(xx.vk).pt) = Ō VD+)
(12)
for some K satisfied
36 d + D2
K 5 1
11
log
- (c-2log (6'))
Theorem shows that the variance corrected quantization function can solve the overdispersion problem observe for the naïve SGHMCIP-LL algorithm for strongly log-coneave distribution. The W2 distance between the sample distribution and target distribution can be arbitrarily close to Ó(VA). Compared to the Theorem 3 in Zhang et al. (2022), the VC SGHMCLP-L docsn't showcase its advantage over VC SGLDLP-L for strongly log- oog-concave distribution.
B Stochastic Gradient Langevin Dynamics Result
In order to sample from the target. distribution, Langevin dynamics-based samplers, such as overdamped Langevin MCMC and underdamped Langevin MCMC methods, are widely used when the evaluation of (xx is expansive due to large sample size. The contimuous-time overdampod Langevin MCMC can be represented by the following stochastic differential eQuation(SDE):
(13) where B, represents the slandard Brownian motion in Rd. Under some mild conditions, can be proved that the invariant distribution of (13 converges the target distribution exp(-U(x)). To reduce the com- putational cost of evaluating VU(x), Welling & Teh (2011) proposed the Stochastic Gradient Langevin
dx, = -VUx)) + V2dB:.
Dynamics (SGLD) and updates the weights using stochastic gradients:
X X (xx) 2nER+1,
(14)
where 1j is the stepsize, the Ex+1 is a standard Gaussian noise, and vū(x;) is an unbiased estimation of (xx). Despite the additional noise induced by stochastic gradient estimations, SGLD can still converge the target distribution.
In this section, present the theoretical result. for SGLD. We start from the SGLDLP-F'ss result.
19

---

Published in Transactions on Machine Learning Research (04/2024)
Theorem 7. Suppose Assumptions and hold. Let denote the target distribution of x, À have the same definition in Theorem 7 After K steps starling with inätial point = 0, if we set the stepsize to be
= δ (mTT(T)))
The output xk of SGLDLP-F in satisfies
Wa(p(xk).p') Ö c Ālog (t)
(15)
for some K satisfied
log )
K - δ
11-=
Theorem 7 shows that the low-precision SGLD with full-precision gradient accumulators converge to the non-log-concave target distribution if provided small gradient variance and quantization error. Next, we present the SGLDLP-L's result.
Theorem 8. Let Assumptions
and hold. Let p* denote the target distribution of x. If we set the step size to be 17 170 Tog(i/e) after steps starting at the initial point X = the output xx of the
SGLDLP-L in (2) satisfies
Wa(v(xk))p")= = ( c+ max fo2, of log (:)
log (t) VA
(16)
el
for some K satisfied
- log )1)
K Ō (1)=
The VC SGLDLP-L can be done as:
Xk+1 QTe (x: - NO 2n, A)
(17)
We present the convergence analysis of VC SGLDLP-L in the following theorem:
Theorem 9. Let Assumption and 3 hold. Let pt denote the target distribution of x. If we set the stepsize to be 1) = Ô
after K steps from the initial point xo = O the output xx of VC SGLDLP-L
log (1) !))
in 17 satisfies
Wa(p(xx),p")= E / max (02,01 log (
log (2)
VA
(18)
22
for some satisfied
(1) log ()))
K δ -2-
C Uniform Bound of Contraction Rate
According to reference (Raginsky et al. 2017), under Assumptions uniform lower bound the contraction rate, i.c.,
and 2 one can choose A to be the
Sqw [ dp Jae dd
g " C³ (Rd) n (2(p))) 0, / gdp" = =o]
x inf
which satisfied
4C + b)
(M + B)(b + d) + (A +B))
exp
m2(d bb)
m2
m2
20

---

Published in Transactions on Machine Learning Research (04/2024)
where A, B denote bounds such that (U(0) & (,V(((() - B. In other words, asymptotically w.r.t. the dimension, we have X² exp(O(d))
Similarly, Zou et al.
2019 derives a contraction rate as
2d
min (MMeu* / Nu,,,uA, 7A4/2)
y
where the constants are defined as:
2m1
X 4M + u-1
A 12(1 + 2ax + 20 A)Mu
5-22(1 22)
A (U M M| b
4M u-
Note that the above rate also satisfies 1 exp(O(d)).
D Technical Detail
In this section, we disclose more details of empirical experiments. We can define the stochastic quantization function Q" as:
8 A
w.p. _
(7( =
A
A w.p. 1 ([ 2)
(19)
A
0
In practice, to implement stochastic rounding based on the rule (9), the computer still needs a full-precision Unif(0, 1) random number generator (note that we ignore the discretization gap between full precision values and real values), then compares this random number with the residual and rounds up if is smaller otherwise rounds down. This full precision random number generator can be shared for all rounding steps, hence won't 't affect memory usage too much. For more details about the implementation of stochastic rounding, please refer to (Gupta et al. 2015 Croci et al. 2022
Now, we show the details of the experiment setup. For the standard normal distribution experiment, we use 8-bit fixed point low- pwe-iiicioon representation with 4 of them representing fractional parts. Moreover, we set the step size 17 = 0.09, inverse mass u = 2, and friction y = Similarly, for Gaussian mixture distribution, we also use 8-bit fixed point low-precision representation with 4 of them representing fractional parts for both low-precision SGHMC and SGLD, but we the step size r 0.1, inverse mass u 1, and friction y 3.
Next, for both logistic, MLP models, low-precision SGLD and SGHMC in MNIST task, we set N (0. 10-2) as the prior distribution, and step size 0.01. Moreover, for SGHMC, we set the inverse mass u = 2, and friction 2
Then we introduce the training detail of low-precision SGHMC for CIFAR-10 CIFAR-100. We adopt the quantization framework from previous research Wu et al. (2018); Wang al. (2018); Yang et al. (2019) apply quantization to weights, activations, backpropagation errors, and gradients. Please the Algorithm We use N (0, 40 the prior distribution. Furthermore, we set the set the step size 7 0.1, and == 2 = 2 for low-precision SGHMC.
Algorithm 1 is a practical version of the three different types of low-precision SGHMC updates proposed in our main text, i.e. equations 5 6 and 9 Additional components in the algorithm include (i) How compute the stochastic gradient forward http://aac-pppppgatttiee box). Due to the low-precision nature of the algorithm, we also quantize all intermediate results along the propagation process by proper quantizers QA and QE- (ii) Additional optional scale/re-scake step (colored
(steps colored by rod in the Algorithm
21

---

Published in Transactions on Machine Learning Research (04/2024)
by blue in the Algorithm box). The reason for adding this step is that: in practice, found that the momentum term VE tends to be close to O. When V& is represented in the low-precision fixed-point format, the information carried by Vk is lost since the low-precision fixed-point is loose around 0, and only 2 or 3 bits are used representing the momentum (i..,, the other bits are wasted). With this observation, we store scaled-up momentum to fully utilize all bits, thus the information carried will be kept in an optimal way.
Algorithm 2 is proposed by (Zhang al,, 2022). The rationale behind Algorithm is that: we directly quantize the SGLD update result, i.c. the mean shift plus Gaussian noise variable, it essentially introduces additional quantization noise to the sample, leading to larger sampling variance. Instead of quantizing the mean shift plus Gaussian noise, we can first quantize the mean shift, then plus a low-precision discrete random variable. In this way, we guarantee the sampler yields low-precision values and have the freedom to design the variance the low-precision discrete random variable, such that overall sampling variance (i.e., variance due to stochastic round and low-precision discrete random variable) matches the idea sampling variance of full-precision Langevin update.
When implementing low- preciiiciionn SGHMC on classification tasks in the MNIST, CIFAR-10 and CIFAR- 100 dataset, observed that the momentum term tend to gather in small range around zero in which case the low-precision representations of v end up in using few bits, thus the momentum information is seriously lost and cause in performance degradation. In order to tackle this problem and fully utilize all the low-precision representations, we borrowed the idea of rescaling from the bit-centering trick and adopted the low-precision SGHMC method. The detailed algorithm listed in Algorithms |
Now, we give brief introduction of the variance-correetedd quantization function Q"C Instead of adding real value Gaussian noise and quantizing the weights, space (A, -A, 0} with the desired expectation μ and variance u as
design categorical sampler that samples from the
A
w.p. ーー
24
Cat(u, v)
A
w.p. リー 24
(20)
0,
otherwise.
Based on the sampler 20 one can design the varianco-correctedl quantization function Q in the Algo- rithm
E Proof of Main Theorems
E.1 Proof of Theorem
In this section we analyze the Wasscrstein distance between the sample (xk. uK) in (5) and the target distribution, given the target distribution satisfies the assumption Tand] 2 We follow the proof Raginsky et al. (2017). To analyze the Wasserstein distance, we first calculate the distance between solutions of low-precision discrete underdamped Langevin dynamics and solutions of the ideal continuous underdamped Langevin dynamics, also the distance between solutions of the ideal continuous underdamped Langevin dynamics and the target distribution.
Again let Pa = (Xs, vk) denote the low-precision sample from (5) at k-th iteration, let f.. = (æe, 0z)) denote the sample from the ideal continuous underdamped Langevin dynamics in (41) at time t. Then the Wasserstein distance between the Pt and the target distribution p² can be bounded as:
W2(pK. p²) S W2(pk. W2(6kn,p").
Then we bound the first term W2(pK. pKn) by invoking the weighted CKP inequality Bolley & Villani (0055)
W2(pk S A (WDrLOX(IEEN) + VDL((Klllxx))
22

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Low-Precision Training for SGHMC.
given: layers DNN (L....;f.). Weight, gradient, activation, and error quantizers Qw Qa: Qa QE Variance-corrocted quantization Q"s, and quantization gap of weights A. Data batch sequence {(0k, hx)) h+)]==>> where the Og is the input, and hy is the target. The loss function L(a, h) measures the loss between the prediction and target h. And xf" denotes the full-pree coll-precision buffer of the weight. Let Var u(1 e 22)) and Var Vameme = uy 2 + 4e 79 - e -2n - 3) and Sy = 1. {Initialize the scaling parameter)
for 1: do
Forward Propagation:
a -0 02
(1) Qa(fi(a (1-1) x [1
ag
2. Backward Propagation:
e(L) V Laa ,,,)
[Si(al") (1) (111-))
e(1-1) = QE
Ck
[1,
1 = QG Ck
85 00
V L]
3. SGHMC Update:
full-precision gradient accumulators:
Vell f vg wy u (1--""") ->>")a + sv E LJ.
(0fF (0.fP (1-e x++1 +-
- +u (ttee (m +5%
x + Qw (x(1).1)) .Vl E
xk
[
low-precision gradient accumulators:
(!) ve * ((l)) VI E [] {Restore the velocity before update] (1)
Vk
((v (1) t V e- uy e ">>)gk VI [1,
Vl [1 {Update the Scaling)
Ve+1 Qw (w((u(v)))) + [% //
(1)
L]
x k+1 t Qw x (1 (1- 11- + +u + 2nn --- 1)9g + Gz) e [1,
Variance-correeted low-precision gradient accumulators:
(()) * !! VI E [] (Restore the velocity before updatc)
u(v (1) (1)
k+1 v
- 77 uy
(1 (1-e 11---770 (1) VI E []
(1)
+ e (1) wy P(n + 1)9h (1) v [1,4]
((++1))
Xx
5(())
VV [1, {Update the Scaling)
U
Vi- Q
(u(v (N(v++1//S**
1// Vartmo /(s()) A) VI [1,4]
x Q (M(x Varkme A) Vl [1
end for output: samples
[(v[),x00 ("))
where A = 2 infoso V 1/0 (3/2 + logEEKK [ezp(0([| + [1))1. We define a Lyapunov function for every (z) E Rd x Rd
E(x, v) = ||x|] + ||x + 2v/711
Note that ||a]2 + |1b112 2 |la b1l2 /2 and U(x) 2 U(r*), we can have:
E(x,0) 2 ||||| ||ا| 2 + j + 20/>11 max(11>]12 3 1111//113)
23

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 2 Carianco-Correcte Quantization Function Q"c. (Zhang et al. 2022)
input: (μi A) {Qee returns variable with mean and variance e}
Up f 22/4 (A2/4 is the largest possible variance that stochastic rounding can cause]
> vo then {add a small Gaussian noise and sample from the discrete grid to make up the remaining
variance)
I 1 + V UoS, where & ~~ (V,, T (x)
for all do sample c; from Cat(Irsl, 2b) as in 20 end for
0 + (z(x) + sign(r) O
clse fsample from the discrete grid achieve the target variance) r r 1 --
for all do
+- [ (1- (1-
[xd
r Iral (-r; sign(r:)A)²
if v > Us then
sample o; from Cat(O, v - vs) as
20
0, +x)
else
0, + (u); end if
end for
end if
clip 0 if outside representable range return /
Given assumptions 4 and 2 hold and apply Lemma B.4 in Zou et al. (019)) we can get
2 + 20E(Xo, Vo) + 32M 12M0u(( Ou(d (dd + 2b + m2 ||xx
A 2 inf 1ieu
72m2
32M0n((Ad + 2b + m2 | - 16(12um2 + 3 A.
22 28 20. Vo)
72m²
Tt remains to bound the divergence between the distribution pk and pKn- We first define a continuous interpolation the low-precision sample (Xx. vk),
dv: VVddt - uG,dt + / 2rddBB
(21)
dx; = vedt,
(22)
K where G, = Σ 1 (c((k)(k(+))))) Integrating this equation from time 0 to t, we can get
k=0
Vo [ yv L uG + S/' V
X X0 + f Veds.
Notice that when t lnn, the solution of 21 has the same distribution with the low-precision sample (Xt. VR). Now by Girsanov formula, compute the Radon-Nikodym derivative of fx,, with respect to
24

---

Published in Transactions on Machine Learning Research (04/2024)
Pk follows:
It follows that [ [IV((x.) G.llds
dØиn exp (V 2
yu
S (VU(x.)- G.)dBs n
dpk
døKn
PKI(PKllkK))
= Exx
log
(23)
dpk
y
E
-
K-1
(1+1)n
y
E - - Goll'] ds
km
K-1
(k+1)7
yu
E [[VV(xx)) - ds. ds.
R=0
km
Furthermore, in the k-th interval, we have
E [VU()) [(x))) 2B
[VU(xx VU(x))1 + 2E [IV((x) o(xx)1
(24)
We now bound the first term in the RHS of the 24h. By the smooth Assumption we have
E [[VU(xx)) Vu (xx)) s M
[|x, xx
Notice that
I vrdr
X, Xx +
Jnn
Xx + I km
Vkne Vane-o(r-kon - (f -((+)))((())d) + 22 (" c-((r=)) dr.
This further implics that:
= =11-10 VAne (tmp--(0-kn)) - (ff e->(r-s) g(xx))) + 227u I e-(lo-s) dB, dr
|x.- xx112
km
kn
dr l'd (
2
dzdr 1 I' ue(x))e (0 dzdr
+ Gru 1 1 ->((-=) dB,dr
<3
+3
km
km kn
<3n² 1| + 3u²n" 111(x))11
(27(s kn) + 4e 7(o-kn))) 27(00ko)) - 3) a)
?2
53n7² (Ivxll n² [0x + 2du)
(25)
where we use inequality 1 x & e- < 1 - x x² /2 for x > 0 and lnn S 8 < (k+ 1)n to get the last inequality.
Given this analysis we can bound the first term in the RHS of (24]
E [VV((x)) vU(x))] < ,,
E |1
E
+2du)
By lemma 12 the second term in the RHS of 24 can be bounded as:
g(xx))) S (M2 + 1) Ad + o².
E VUX(x)
We need to introduce a lemma to bound the sup
||** 2 sup || 1 and sup (lz(x;)) )l
&
&
25

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 10. Under Assumptions 1 and 2 if we set the step size statisfied the following condition:
4u2
67lu
1j S min
4 (8Mu + wy 22
V
4Mu + 322¹ (4M
3 d'
70
8(7² + 2u)
8y
12(21u + ?)M (20u + 7)7
then for all 1s 2 the E
|xx ||xx
E || and E [
can be bounded as
[|xx|1]]] s 3 Co+ (CMP + 1) Add + 0²
S //22/2 + 7220 (M2 + - A2d + 0²
E || ||]
[1(()))] $2 22(N + 1) A2d + 0²) + 4M + 4G
where & and Co are defined as:
24(21u + 7))M
96(d + bjuM mz?
E = E [x0o vo)l +
G²
G = [VU()
m2?3
Co 96u (7² + 2u)
m2?4
The proof of Lemma
10 can be found in Appendix F.3
We now ready to bound E |IVU(x - -0(xx))11 as:
E -
- 3(xx)]]
s 21E [xx)) [xx))] + 2 (U(x)) - [(x))11
)1 + +ddu + 22(122 + +1 A2d + +0²
6,
(Ar²
(Mr² + A2d
<6A/29 (n²//2+
+ +0²²
+ 42211²2²² + +2du
+2 (MM2 +1) +1 A'd +o2
< 7/ (02/2+444' 422 + 2du]
+ (6N/::/(726//2+222)))+ (M + 1) A2d
4 + 0²
Thus the divergence can be bounded as:
3yu
DKI(PK((kK)) < M²
+ G2 + 2du]
2
(IM2+ 22d
+ yu Kn (
+
4
By the weighted CKP inequality and given Kn 2 1,
Wa(pk, (KT) T v DKI(PKlkKN) + / DrI(pKllkx))
< π (oon)+TiA) Vkn.
26

---

Published in Transactions on Machine Learning Research (04/2024)
where the constants Co: Ō1 and À are defined as:
3y M ( + G22
3 M2 [62//2 G2 + 2du)
Co V 2
4m + 2du] + V
G = V yu (0MP))(79C6/2++ 2u² 2) +
Tu
4
Ā max {
(1 1) A2 A2d + 0²) ). (MM
+
Add
+ 02
4
Finally by the Lemma A.2 in Zou et al. (2019), we can have
We(fkmpp") S To
where 1¹ O(d) denotes the concentration rate of the underdamped Langevin dynamics and To is a constant of order O(1/μ²). Combining this incquality with the previous analysis we prove:
W2(PK.P3 S A (CovT+ GIA) v Kn + Toe 1 knn
(26)
To bound the Wasserstein distance, we need to set
ACoVKy² c
and Dhe Kn c
(27)
2
2
Solving the equation 27 we can have
log 2
2
Kn
and n ==
10
4 Co Kn
Combining these two we can have
22
4A Cu log² (2T0)
2
=
and
K
4A C log
(2C))
2 211²)
Plugging
226 completes the proof.
E.2 Proof of Theorem
In this section, we analyze the convergence of SGHMCLP-L when the target distribution is non-log-concans In this proof, unlike the SGHMCLP-F algorithm where gradients are unbiased, additional noise applied to the state x causes deviation from the underdamped Langevin dynamics, leading us to establish an inter- mediate process to address this noise.
Recall the continuous interpolation of the SGHMCLP-L,
V: Vo ' yv,ds - u S G'dss /2ru / (- + S ao(s)ds
x = Xo + f Vods+ + L' (s)dss
where G. = Σ
Qa (VU(2()) 1 (k+ And we define an intermediate process by let vi = + at(:::
k=0
{// 70', (s)) ds / Gods + /2 f' e e-llt-)) dB. + //' (aml6)++
1 taall) ds
0/ v/- -
2/ 10 + dsds.
(28)
27

---

Published in Transactions on Machine Learning Research (04/2024)
By integrating the underdamped Langevin dynamic 10
can have:
V1 = vo I/¹ (v. az(()) - u S. (x.)x) + 2 ' (
x, = X0 + / v,ds.
(29)
Notice that the process zy has the same distribution with X thus in the following analysis we study the convergence of the intermediate process P/. = (1% "/n)) By taking the difference of equation (28 with (9
and the Girsanov formula, we can derive the Radon- MoloonNikodym derivative of PKn, w.r.t px:
dpкn exp dp'k
u
I' (1az(s) + a.)s)) + t + vU(x)) - G.)
1
(V 27
1 47 L' (s) + tc)(s)+ + ax) (T) + vU(x.) - Gallds
Thus the divergence can be bouned as:
DKL(PKl (pk(PI(pK)) = Epx
log
dpk
1
VU(x)) - -G. { ds
ya + aa(s))
+ T a
4y J
K
1)n
E
[Ta((2)11))
[I)aa(s) + ax(ss) + (U(x)) G. ds
477
47
kn
K
(k+1)n
K
(k+1)n
<
"
E
|1axX11
+
E
ds + [1aa(s))1]]
u
E
[|ac(())]
ds
TTT
47
k=0
kn
R=
km
K
(N+++ 1)m
u
E
(xx))
Gall²) ds
47
Jmn
K
(R+1)0
K
(R+1))
W
E
||0211
+
E
| /nll/ ds
+
u
E
|| a '1|
Ty
4
4Y k=0
k=0
kn
kn
K
(k+1)
+
u1
E
V (x.)
Qc(VUUXx)))] ds
4-
k=
km
(K+1)0
(K+12m
<
E
[|aaXI
+
E
|/aa /nll ds +
E
|| /nll//l ds
(30)
TTT
4y
k=
kn
4n
k=0
kn
K
K
(1++))
u
E
(x.)) VU(x))11
ds +
u
[ - (c(VVUX)))11 ds.
47
47
k=
Jon
k=
km
By assumption
we know that:
E [x,()))) VU(xx))
< M
||x, - xx xx]
From the same analysis in 25
derive:
E [Vx(x))
vU(xx)) < 3M²; (E [[]]1]]
+ u [[XO((U(Xx))) + 2du).
Now we need lo derive a uniform bound of E [|x=Il and [[v]|]]]
28

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 11. Let Assumptions and 1 hold. If we set the step size to the following condition
4u
6
7M2
S min-
4 (8Mu + wy 2272) V 4Mu 3-2
(4Mu+ + 372) d' 6 (22u 7) M
then for all le > 0 E [|xx||]]] and E [1wx11]] can be bouned as follow:
E [|xx||]] SE+CARd
E [|&k|l] S ///2/2+"2028/1
where constants & and C are defined as:
E E [x voll 54 (4u + 72) 002
12(22n 7)uM3
96 (d uM
C
m2y1
m27
m2y
C 27 (Au + 72)
2m274
The proof of Lemma 11 can be found in Appendix F.5 Thus,
Add + o² + 2M ||>x||]²]
E [xx,))
[U(x))] < r2
E
+ u22
+2G²) + 2du
A
+2222 + 222 20²)
+2du
$ 3/2 ((1* 22 & (7² 2n M²) Ca²d 2²0² 22 + +2du)
Now we go back to the divergence of pk and pkn
DRL(pKIPKN))
(k+1)n
(k+1)n
E [1a021]]
E
hha//ml ds +
Σ
E
| /nl 2
ds
TyTrp
4 k=
4y k=0
Add o²
+ 3M" (o2++u²MM)) 8 (7² 2x² Ca 2²022 22 + +2du)
+ Kn
47
47
12d
$ 3m ((22 & & (22 C 2202 + 26 + +2du) + Kn
+ σ²
47
47
4
ud2d uKA2d
+ 16
8711
2u2 + 2du) + " I 3M2 (()2 + 2u 22) E + u202
Kno²
4y
4n
uKn
16y 16yTn? + uk add
+
KTp (7² +
4
8ym
=: CoKy2 Kno2 + C
where the constants Co. C1 and C2 are defined as:
Co 3M2 ((>2 + 2a2 & + u2o0 + 2u2 2du)
47
C 47
O2 = u 3 NN2 +
u
u
+ u
d.
47
16y
16y72n
8ym
By the weighted CKP inequality and given Kn > 1,
29

---

have Published in Transactions on Machine Learning Research (04/2024)
Wo(pk,Pun) s A (KLLDKKIDRN) + V DKL(PKllkK))
<Covr+ +
(31)
where the constants are defined
To (Vo++ + V06
G (VG+ + Va
C - (VT++ + V0z)
Ā = max fo, vō).
From the same analysis in 26 we can have:
W2(pk. s A (Cov GT) Kn Kn Doe - "n Ky.
(32)
In order to bound the Wasserstein distance, we need to set
Krj = 2 and Tbe be a- Kn 6 2
(33)
Solving the equation 33
we can have
log
2a
2
K1
and
2
4A Co Co Kn
Combining these two have
2
4A Co log² (2L0)
2m
and
K
4A Co log (2
2
e2 (1x²²
Plugging
32
completes the proof.
E.3 Proof of Theorem
In this section, we analyze the convergence of VC SGHMCLP-L when the target distribution is non-log- concave. Similarly, the gradients are unbiased, additional noise applied to the state x causes deviation from the underdamped Langevin dynamics. This proof is similar to the proof of Theorem 2 however, the variance-correctedd quantization function gives bound for the difference between the quantized value and the full-precision value. This bound can scale with the learning rate. This fact leads to the advantage of variance-corrected quantization over naive stochastic rounding.
Similarily, from the analysis in
57 we know that
E
||xx||]]
S mA.
(34)
where A= max (AVa ()) Aud By the analysis in
55
know that if Var Amc
4
E [|ax|]]]
Audy
(35)
by 58 if Var hime
4
E
|a
< nB
(36)
30

---

U Published in Transactions on Machine Learning Research (04/2024)
where = max (2Avd'' + un/ Audn3. Thus, we can define the following:
E |ati1
=nB,
(37)
where defined as:
Audn, Var
2 A² 4
B =
B,
else.
Combining the bound of IE
|a
[1ax11]] with 30 we can show,
(k+1)n
(k+1)n
$
E |10081
[1aa ds +
E
[laß/nll" ds
4yTr7
4"
km
47 k=0
kn
+
u 47
3M ((12 + 22) 8 2u CA + u²0² + 2n 22 + 2du)
+
u Kn
A2d
+ +
47
4
$ u
3MM2Kn ((>² + 222 & 2 1202 + 22 + 2du)
+ 4n
u Kn
Add
+
4n
uB
uKA
uKB
4-/
4
47
Add
S 3M2 "MM2Kn" ((>2 + 2u E 2u
()))) C o²02 + 2u² + 2duu
Kn
+ 0²
4n
47
uKA
uKB
27
< 3MM K1) ((>2 + 22² &
( + 2u" + 2du) + "
Kno² + u
Knd²d
2d
uKA
+
uKB
47
4y
167
4
27
=: CoKp' + CnKno² + C2KnA² CCKAAA+ C,B,
where the constants are defined as
Co
3. ((>2 2=² E + 2du)
4
C "
47
u
C2 167
2 C3 4
C4 27
By the weighted CKP inequality and given Kn 2 1,
Walpx, PKn) ST (ASVVVVDDVenn DKLlex(lixa) + V/ Drr.(Pkllxx
$ ((ovi+TA++vo ( OUK
31

---

Published in Transactions on Machine Learning Research (04/2024)
where the constants are defined as:
O= [Vo+ 1/
G - V (VG+ VG
02 - A (V02+ V0,)
T A (Vo++ VC,)
G A (VC+ Va
A Amax 0²² Vo²
From the same analysis of 26
can have:
W2(pk.p') Covn+ -
+ Toe Kn.
(38)
To bound the Wasserstein distance, we need to set
ACo/Krp= and The - Kn=
(39)
2
Solving the equation 39
we can have
log
( ([
2
Kn
10 and
4A Co K1
Combining these two we can have
e²p²
2 4A Co log"
(T0
and
K
2
2² (1r²²
4A Co
log
Plugging
38
completes the proof.
E.4 Proof of Theorem
In this section, we analyze the convergence of full-precision gradient accumulators (SGHMCLP-F) introduced in Scction 3.1 when the target distribution is strongly log- log-concave. Again SGHMCLP-F uses biased gradients because we quantize the parameter before taking the gradients. We need to derive the upper bound given biased gradients.
The SGHMCLP-F update follows
vVk+1 V&g 79 uy e (0l1===))[(VV((@xx)))))))))) + Ex
VX++1 X4 + 11 c my uy 2 + - 7M 1)Qa ()Q + Ex
In this section, we prove the convergence of SGHMCLP-F in terms of 2- Wassersstnin distance for strongly- log-concave target distribution via coupling argument. To simplify the notation we define the quantized stochastic gradients at X as:
o(x) = (x)((((() =: VU((() +
(40)
32

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 12. For any E Rd, the random noise of the low- low-precision gradients defined in
40 satisfies:
A
|| < M²
4
Add
(M² + 1)
4 0²
We follow the proof in Cheng et al. (2018). Denote by B(IR)) the Borel a-filld of Rd. Given probability measures μ and v on (I B(RR)), we define transference plan Ç between j and v probability measure on (R' x R B(R" R))) such that for all sets A E R C(A x IR4) = μ{A) and C(R A) AA). We denote T(H, as the set of all transference plans A pair of random variables (x,y) is called a coupling if there exists a Ç E I(u, v) such that (x,y) is distributed according to Ç. (With some abuse of notation, we will also refer to Ç as the coupling.)
The proof of Lemma 12 can be found in Appendix F.1
To calculate the Wasserstein distance from the proposed sample (xx, Vx) and the target distribution sample (x*, v"), we define sample Qk (X,, + v&) and the target distribution sample q" (x", x* + +v*). Let ps: = (xk, v&) and b be the operator that maps from pke to Pk+1 i.c.
Pk+1 L
The solution (x,, ve) of the continuous underdamped Langevin dynamics with exact gradient satisfies the following equations:
-w (L, (->X---)VU(XX + //27 1 e-llt-s)
Vt = =V0 voe-n-
(41)
xo + S/' Vads.
Let 1 denote the operator that maps Po to the solution of continuous underdamped Langevin dynamics 41 after time step y). Notice the solution (V,, &2) of the discrete underdamped Langevin dynamies in
10 with exact gradient can be written
V. Voe -he u ( + /27u f 7-lt-
(42)
& = Xo + / Vads.
We also define similar operator for the discrete underdamped Langevin dynamics solution ýr (Xx, Ve), o be the operator that maps Po to Pt. Furthermore the SGHMCLP-P can be written as:
V: Voe Voe- (f-
+ 2 S: ==-(tt-)
(43)
Xt = No + f Vads.
Given g(xo) VU(xx) + Eo and No = Nu, we know:
V. v. u (S. (((e-(t-o)ds))
(44)
X1 = 8, ( dr dr)
Lemma 13. Let qu be some initial distribution and o, and Dy be the operator we defined above for discrete Langevin dynamics with eract full-precision gradients and tow-precision gradients respectively. If the stepszie >> 0, then the Wasserstein distance satisfies
W2 )²) & (W2( V3/2mNVaMA) + 5u2rp ( + Add + 0²
Add
33

---

Published in Transactions on Machine Learning Research (04/2024)
The proof of Lemma distribution after one step of low-precision update the Wasserstein distance from the target distribution is bounded by the distance after one step of exact gradients plus On7²23) Furthermore from the corollary 7 in Cheng et al. 2018) we know that for any i f1,...................... ,K}:
13 can be found in Appendix F.2 The lemma 13 says that if starting from the same
( 9²) S 7//m/ W (4:: 9");
(45)
where M/mj is the condtion number. Let EK denote the 26 (d mi + D2), and from the discretization error bound from Theorem 9 and Lemma 8 (sandwich inequality) in Cheng el al. (0118) we gel
88K W2 T, s 2W2( p.p)) s n²
5
By triangle inequality:
Wa 9²) S W2( pn + V12 pngiis 9¹)
s = EEK +e 1/2 W2 9¹).
Combine this with the result in Lemma 13 we have,
2 (M/2 5u²17² (M/² + +)
(2( s (-n//m Wa n
8 5
A2d + + (46)
By invoking the Lemma in Dalalyan & Karagulyan
2019
we can bound the 2-ssserstnnin distance by:
n²
8Ex 5
unMAvdd
W2(ak, (²) Se Kn/22n 2m1 W2(go. +
2
1
c n/2k1
2u2n?
(112 1) 2 0²
KE
unMAv5d
v1 - v Su22p ((M2 + 12 o2)
Finally, by sandwich incquality we have:
172 BE unMAv5d
Wa(pK.p") p") S 4e Waspo
e-n/2x
20n2n2
((12 + 1) APd
1)2
86K + unM4v5d
vI VI-e-nik 5u2n? ((M² + + 1) Aid + +z)
Now we let the first term less than 3/3, from the lemma 13 in CCeng et al. 2018 know that W2(PK <
d + D2). So we can choose K as the following,
m1
K < 2k
+ Dz) D²
log 36
Next, we choose a step size I
to ensure the second term is controlled below c/3 +
/479232//5(d /d0/2///mm/mmmmmmmmm +2)
16k; aMd Av5d
Since - e- n/2m 2 //Kz and definition of EK,
8Ex unMAv5d
BEK + und
112
2
17
EE mV 5
uM A v
5d
S 16K1
+
e n1/2x
1//Kk
2
16k UM A 5d
< e/3 +
2
34

---

Published in Transactions on Machine Learning Research (04/2024)
Finally by choosing the step size satisfied that,
cMAv /5d
120u [M2 + 1) 42d + 0
the third term can be bounded as:
20u217² (M2 + 1) 02)
BEN 5
anMAvbd 2
+ v1 6-0/K 552217 ((M2 + 1) 2ad + oZ)
20u211
((M² +
1)
- 02)
(M² + 1) A-d + 02
= =00m
1 c/3.
unMAv5d
M A 5d
2
This complete the proof.
E.5 Proof of Theorem 5
In this section, analyze the convergence of SGHMCLP-L when the target distribution is strongly log- concave. We mainly follow the proof in Cheng et al. 2018 the difference is need to handle the noise. Recall the SCHMCLP-L update rule:
Vk+1 Qw (vVRe 77 uy uy (1- (c + 5%
Xk+1 Qw (xx 7 ( + uy tmm -)Q
If we let ox and o% denote the quantization error,
ox Qw (vze m -y- (1 e² Qc(") + Ex) -v
- ((( + +
ax Qw (x, + -1 e 7 ) uu uy " m - 1))c(V(( + +
Xx + + (1 - ) + un 27 + - (1)(((x + +
we can rewrite the update rule as:
Vi+1 = VRg - (1e"e111)0oVUssx.....) +5% + +
Xk+1 = Xx + (1 e >')x + wy (mm + e 10 - 1))aa + St + oz.
(47)
Similarly, we can define a continuous interpolation of 47 for E (0,
V: = Voe vo ef (VU(xo) + (VU( + 2 ( e e dBs + / ar(s)ds
dBs
X + 1'' vado+ + ( (s(sssss
(48)
where the < Qa (VU(tn)) - (20) the function (8), az (5) are defined as:
(s)))=
/ (1e)
(s)))
Σ
Ss 1)0))
0=0
35

---

Published in Transactions on Machine Learning Research (04/2024)
If we let Po (øo, Bu) be the initial sample and Pt. (#t, 0x) be the sample that satisfies the previous equations, we can define an operator &, that maps Po to Pt i.e., Pr = -.f0- Notice that since Prr is the continuous interpolation of (6), thus アkn = Pk = (xx. Us). Similarly, we define q = (Xt: Uk + xx) =; (Xk, wk)
as a tool to analyze the convergence of pk-
We are now ready to compute the Wasserstein distance between $, and q² Let TT be all of the couplings between P,990 and g², and 12 be all of the couplings between 8,790 and q². Let be the optimal coupling between 2, and g², By taking the difference between
48 and 42
S (oo E (--(s-rrds ds) dr) S So (s)dss
+
LU6 (o e dr + ds 5 + So az(s) + as)(s)
Let us now analyze the Wasserstein distance between 20 and q²:
W3 ② (2,00.9") 0*)
(49)
U (h' e- dr) 5 Sod (s(ds
< Er
+ u
(J6" (S e e->(s-r) ds) dr + + e 76)- + fo (ar(s) + ar(s)) ds
< Er
x="
2
+ u
[(.00 (So e x- ds) dr + + x o ds) 5 So (ax + a.) ds)
U (So - dr) ( + Sh (s)
(1%0 (1o
2
I W (Th (00000")) 9-)
+ 4n²
( ( ar) +
e e->l0-0) ds
A
+ +0²
4
+ 2 11%6" (a=())) do
[16% (ax()) + tc(())) ds
27
+ uu2B
< W
(ā (0)00.9))
+ 4n²
11a
+ n²)
AAd
4 + 0²)
+ + [|071]]
+ uFE llat + ax [?]
4
Add
< w3 (o (0,00.97 9¹)
+ +5u27?
+
+ 2u²
[B|aaE1 E laaXl²))
4
Add
< <wZ
T (0,90.9') 9¹)
+ +5u2n²²
+ 0²
+ + (A+B),
(50)
4
where the constant A, B are the uniform bounds of E [|| |II and E [| respectively. Furthermore from the corollary in Cheng al. (2018) we know that for any i {L, (1,...,A. KK:
( 9²) < e W (q. 9*),
(51)
where K1 M/m3 is the condtion number. From the discretization error bound from theorem and lemma 8(sandwich inequality) in Cheng et al. 20188), we get
8E Wa ,,)) S 222( T.))) S 12
5
By triangle inequality:
Wa( S W2(D ( + W2
8E c 2 Wa 1²
further implics the following incquality:
W3 (d)()rr)) < 1/20/2 (gi, (g: (-) 112
gE
+ 2u
Add
+ +02
+ + (A (A+B).
(52)
5
36

---

Published in Transactions on Machine Learning Research (04/2024)
By invoking the Lemma 7 in Dalalyan & Karagulyan
2019
can bound the Wasserstein distance by:
11
SÊ 5
W2(ak, ( Se-Kn/2n W2
C 7//2K1
"u A + +
+ 2u² (A+ B)
REK + v1 - e-n/
2011 v 12 (7/ o2) + 2u (A + B)
Finally, by sandwich incquality we have:
4072 RE
W2(pk,p") S de -Kn/2m Wa 9²) + 1 - c-n1/mm
W2(go.
5
(53)
20n2,12
A'dd 0²) Su² (A+ + B)
4
8Ek
v1 n//2m1 522 (iid o2) 2u (A + B)
Add And in this case, we know that E [||a and E [I can be bouned by 4
Finally, we can have:
3Ex 4n7² V
WalpK,p") S 4e KK//2K1 KK//2m 9²)
-1/2Kk
20u2,1²
AAd
+ 0²)
+ 4u=
(
172 V
BEK + vI e- 0-7/2m1 v 5u2272 ( + 0²) + A2d
Now we lot the first term less than c/3, from the lemma 13 in (Cheng al., 2018 we know that Wa(go, 9²) 5
d + D2). So we can choose K as the following,
my
2k1 K
d
+ D2 )+
log
36
mi
Next, we choose a step size 17 S
to ensure the second term is controlled below e/3. Since
/4 m/dm////p))) D2)
e n1/km 2 11/4xI and definition of EK,
172
88 5
172
|8EK 5
E
< 4
& 16k1
m
- e/3.
1/
2m
n/4ki
Finally by choosing the step size satisfied that,
2880k1u u
Add + 02)²
37

---

Published in Transactions on Machine Learning Research (04/2024)
the third term can be bounded as:
20=2n2² (M1 1) + 02 + 4uA
12 DEK + vI - E v 15 ((M2 + 1) +
20u217 (M² + +1) + 0²) + A22dd
20u²n)² ( + 11 + x²2) + Ad
v1 1//2 512212 (MM² + 1) Aid +02)
V1/Aki / 552212 ((M2 1) 2 + +
(M/2+ 1) A2d + d2)
8u 8u²A2d/Ki
41
20mmn2n
17112 17//2 /u227 ((M2 + 1) 1 + +
8u² 2
S 51/3+
1212 / 5u²?? ((M2 + 1) ARd + 02)
This completes the prool.
E.6 Proof of Theorem 6
In this section, we analyze the convergence of VC SGHMCLP-L when the target distribution is strongly log-concave. This proof similar to the proof of Theorem 5 however, the variance-corrected quantization function gives us a bound for the difference between the quantized value and the full-precision value. This bound can scale with the learning rate. This fact leads to the advantage of variance-corrocted quantization over naive stochastic rounding. Recall the VC SGHMCLP-L updale rule is the following,
Vk+1 Q" ( - uy --u-- (1- e) Qc (VÚ(x)) Var.. 4)
Xk+1 Que
- (1 e m) + uz u² (m1 e 77 - - Qc((U(xx)) Var.. 4). Xx -
(54)
If we let ax and a% denote the quantization error,
ax -p0 (uke-m uy-1 (1 (1-6 - QG (VU(x)) varr.)) (vze-m - -1- Qo(Vxx( +
ox Q (xx + - (1 - E ~1)) us + - (71 + E 1y - 1) (Xx:))) Varz.
- xx + x (1 e er + my pm - -m)))c((((x))) - +
can rewrite the update rule as:
Vk- V&G 770 uy 1 (1 e " 5% +
X X + 1 (1 )u) + uy ((m)) + e 7 - 1)Qa (VU(()))))) + 5 + oz.
Next, we first derive uniform bound of E ||aX| 2 assume the norm of quantized stochastic gradients are bounded.
In this section and the following section, we further
Assumption 5. For any x E Rd, there exists a constant g and the quantized stochaslic gradients al x satisfies the following
E [[\o((U(aa))) s
38

---

Published in Transactions on Machine Learning Research (04/2024)
By the definition of the variance corrected quantization function Q"T, when Var, > Po =4= if we let the denole oge 79 -u (1 -0) Qe (xU(x)),
||ao|| || ( |i
use m - 1y- (1 - Qa ([((((()))) + VVariš
Qd 12 - -/ 1 (1 - - - Qa Qo((U((x)) + VVar. - PoEs) sign(r)e 112
1ba
Let
11y 344 Q²
- -. (1 - 3 ( Qa(VU(x))) + /Var. - PuŠN
u. 1 (1 - - 1.) Qa + VVar. - -PšE))
then
|| 1| (2
(1( 12e -m uy (1-e Q6 -1= + Varook
URe px "n uy (1 - Qa (XU()) + Varr - -uEk) - sign(r)dl
1/20
Varrok VVare- - PUEx - - sign(r)c
4/
/] + E [1o- + sign(r)c) 1b))
<R Warola VVar. - PoEE MoSe
$2
Vardd - Pod + pod
4yyudn.
(55)
When Var < Age 4
a
EE
13]
V&G 71 - uyy 11 (1- Qo(U(x(e) - Vk+i + v Varaee 27
= E
[1 uy (1 - - m Qa (((V(()))) - /atil/?] +E ||VVariieul " 11]
E
(vve - - 1 (1 ~ Qa (o(VU((a))) Q" (vae - (1- (1- Qa(VU (xx)) 1|]
< max 2
VV or
(56)
Using the bound equation (6) in Li & De Sa 2019 gives us,
E [ Vie VA -n (1 (1-e - Qa (VU()))) - Q² (vee-m- - un- ( (1- Qo (VU(()))))
< (1 - E ||| 11 QUU
A (1 (9) Vd | 11 + E [Q((((x)))))
39

---

Published in Transactions on Machine Learning Research (04/2024)
Now we need to derive uniform bound of E |/ II, by the update rule, we know that,
E [|va+zal? = Vae - uy - Qc + + + ox xx1
$ (1 + -m/22) (1 - -mmm222 || +
( 717
+1 u²'1²E
+ yyudy + E ||aX1
s1 111mm/2) IE
[|vi|*] IP] 3u2nn/ n//g² + 2yudn + E |IxX1]]
When E ||aaX| 2V Vrr 4yudn, the incquality can be further written as:
E ||v
- (1 1-m/))
E
||uall
3u²n// + 6yydn
$ E ||vol|
6u2ng9
12nudn
+
721
m
nu2ng
$ E [|voll"]]
+ 12dd.
y2
F [|,X|]] s 2E || (vze-m-u-- r-) Q6 Qo(QQQ((VUUU (VU(x))) Q" (vxe-m- uy (1 - Qa (x(V)( [|]]
the incuqality can be wirtten as:
E || ||] s (1 m E ||0x|| ?
+ 3u3nn 0/ + +yuudn + 2A (1 -- Vdl (E + [|| (Q(((((ss))
$ (1 - 2m/2) E ||ux|]?)
+ 3u +-3un// n/ + 2yud1 + 224nIV ( [1ca|]]] +
11 v TE [|0x11]] + /1 11/2// mm/2 )
Anva
+ +3u2n/gg² + 2yudy +2AnTVdg.
Thus,
AnnVd d
3u 3u2n/186 //2 + 2yudn + 22Aynvdg
E [|
E |
vM-m/2
Annva
7m/2 (3u2n/702 + 2yudn + 24 dg)
1//
Amva
E
vol
2
1-m/22 m1/2 + V 6622/72022 Aud + 44A
=
+ +AVd + /622/22g2 + 4ud + 4Avig.
Finally, we can have:
[|low/1 [] S max V
E
[voll
+ Avd+ Vbu² /622/222 /2222 + Aud + 44 ddg
Gu2ng22 72
R
[1vol13]]
+V
+ v 12nd
A'.
Thus, we can have,
||( m- un - (1- (ot""))(((((((e ((U((()))) - QQ (vee-m-w - u1 (1- Qc (v(())))))) ||]
E
< AAmvd(A'+ ())
40

---

Published in Transactions on Machine Learning Research (04/2024)
and we can bound the E ||a [ as,
E ||ax [|] S max {ArIaa +9) 4rudd) }
7mma AAV 99) 4ud]
=:M
(57)
Now we bound the ||a When Var, 2 Pos as the same analysis in 55 we can show,
E
||01|p| - 2Var s 4udr"².
If Var, < Po. and let Mx x + (1 - -e --) uk uy (>n + - - 1) Qo Q)V(((()))) by the same analysis
in 56 we can have:
E ||a21
S max 2F [Iue Q" (mm))l 2Varad
Again using the bound equation (6) in Li & De Sa 2019) gives us,
E Ilux Q'(mm))
< AE
(1 e (1)
Uk + uy (E + + Qo QV(U(xx)))
+ un
[[((U(())) [
I AnElluull
2
s AnVaE [NV]/] + un/²
de
(c(V(())))
2
s AnVdA' + un/
Vdg.
Thus, we can have,
E
||0011] max 22 dA' + unj Vdg, Audr?
22V/A' wnVd 4udn
< 1) max
=: nB.
(58)
Then follow the same analysis of 53 we can show
4nj² SEK
We(pK.p') < 4e 4c- KK//22 Sac + 1 n/2k1
(59)
70 Add + 0²)
+ suun (7A+ BB) B)
(60)
122
BEK
+ - 11--e-n/m 5
Add / 2222p 4
+ 02) + ( B)
Now we let the first term less than e/3, from the Lemma 13 Cheng et al.
2018 we know that We(go. 9²) <
mi + DD). So we can choose K as the following,
K < 2k1 log 36 + DD))
41

---

Published in Transactions on Machine Learning Research (04/2024)
Next, we choose a step size S
v /7 +DF) to ensure the second term is controlled below e/3. Since
e -n/2n1 2 n/4KK1 and definition of &k,
172 BE
T
SEK
SE "V
S 1661
S 51/3.
1 e 7/2ML
n/ 1/4K1
5
Finally choosing the step size satisfied that,
e²
2880
(A'd + 0²)
the third term can be bounded as:
20 Ad + 0²) + 8u22 (7A B)
112y V 88K v1
n/133 y 5u22p Add + 02) + +2u2n (7A B)
Add
4 + o²)
8u²n (7A A + B)
20n2,/² (Add
4 + 0² + 8u (7 A + B)
V1
e 5/ms
5u2n2 ( + + 2 (nA B)
Vn/4K1 5u21p2 (A'd + + 2u²n (74 1 B
A2d
< 1/ 2012xin
+ 02
u (xA+ + B)
S e/3 + 2x
/ 2² (7A + B).
This completes the proof.
E.7 Proof of Thoerem 7
In this section we generalize the convergence analysis of LPSGLDLP-F in Zhang et al. 2022 to non-log- concave target distribution. We prove a more general version of theorem 7 following the same proof outlines in Raginsky et al. (2017). We further introduce an assumption about the initial distribution po-
A Assumption 6. The probabilily po of the inilial hypothesis Xy has a bounded and striclly posilive densily and satisfies the following:
/ c!l=1 /gd
Ki = log
po(x)dx < oc.
Note that the for initial distribution Xy = 0, the value Ki = is bounded and the assumption satisfied. Recall the Overdamped Langevin dynamics
dx+ VX;(x) + VddB
(61)
We further define the value of the energy function and the gradient at point 0 at the following: |VU(())] = G1.
[U(0] = Gu,
In order to analyze the convergence of SGLD for non-log-concave distribution, need to introduce extra assumptions.
Then the solution of the Langevin dynamics should satisfies
X; - 1. (x.)dsss + v2 ( dB..
(62)
To analyze the LPSSLDDLPFF in
we define continuous interpolation of the low-precision sample as:
Pt = ào - S. G,ds V2 1 dB.
ddd
(63)
42

---

Published in Transactions on Machine Learning Research (04/2024)
K Σ g(tx)) 1 (k+1))) The Wasserstein distance can be bounded as
where G2
k=0
We(pk.p") S W2(PK.PKo W2(PKn.P
(64)
Now, we are ready to introduce the contraction rate X of the overdamped Langevin dynamics 13 By
borrowing the proposition RRaiissyy et al. 2017 we can have:
Lemma 14 (Proposittion 9 in Raginsky et al. 2017 7
Suppose Assumptions and hold. Then
d log + ( We(Dkr,,) S 20 log loolloo +
(Ma0
[M60 3
b + +Bvro + Go + log3 )) Kn/Cze
2
S Cze TggeCkn
(65)
with constant
CLS & 2m3 + 8M²
1 X-
6Md
+
+
m
m2
where the X" = = -O(d) denotes the contraction rate of overdamped Langevin dynamics.
Here, X acts a contraction rate of the Markov process initiated by (13 with an exponential dependency the dimension d being inescapable in the worst-case scenario proved in Appendix B in (Raginsky et. al. 2017).
The first term of equation 64 can be bounded via the weighted CKP inequality
DKL (px (pkll)kn) 1/4
W2lKK pKn) s Oaxn (pkllkk)))) (DEZ
2
+ log c\lli Pko((u)) ))
where the constant Cøx,, = inf A5O
}
By Lemma Raginsky et al. (2017)
nd
and assuming Kn 1, can wrtie:
W (pk, (12 (Noo + +b 2d) Kn) (DKe (pkllxx)) + v DEz (oxllxx))
Now we bound the term DKL (pKllpKn). The Radon-Nikodym derivative of the Pkn, w.r.t pk is the following
dpkn
I'
G.)dBs 1 [1V[V G. Gallds
dpk
exp
2 /
43

---

Published in Transactions on Machine Learning Research (04/2024)
Thus, we have:
dfKn
]
(RI(PK((кK)) = Ppx
log
dpk
Kn
[IVU(x)) - G.ll²) ds
K
K-1
(k+1)n
E
| - =xxx)]]] ds
4
Am
K
(k+1)
[VU(xx)) - (U(xx)11
E
2
Ann
(R+
E
(xx) {xxx)11
kn
M
K-1
(k+1)
||x= xx xP]
2
k=0
K-1
(R-++
(R++1)
E [IV((x)) - x(xx)1
(66)
2
k=0
km
We now bound the first term in the RHS of the equation
66
from the update rule in 63
know:
X, X1= = ((s k)))(()))))))))))))))))))))))>)) + / (B. Bka)
= --(s (Uxs) + (s kn)) (VU(xx) x(xx)) V2 Ban)
thus,
E ||x xell"]
33n"EB
+ 311²B (U(())) 0((x+)11) + 6nd
3n (ME x 111 +||||++++0 GG² 37/ (A1² + 1) Add
4 + +0²)
+ 6nd.
(67)
Similarly, we need a uniform bound of E
[xx]] |l
Lemma 15. Under assumptions
2 and if we set the step size 1j (0, 1 m22
then for all k 2 0, the
E ||vxx|| [?] can be bounded
S 2 (M2 + +1 Add
E 1|?
4mz
provided -E
[xn|
+ M (2b + Gn + 2d).
The proof of Lemma 15 can be found in Appendix
Using this bound, we can further bound
E
|X,
x,11
2 2MM 1)
A2d
+ Gr + +37? (IM2 + +1) A'd
-)
|xx - x312 E
< 617 M²
++
+ +0²) + +nd
m2
4
4
12n M² (M² +1)
172 A2d
I 617² M + +n12 + 6nd +
+ +3(M2 + +1)
+ 2,
m2
E. + Cn 2d
+ 37200
44

---

Published in Transactions on Machine Learning Research (04/2024)
where the costant & and C' are defined as:
& = 6M 6G + 6d
M2 (M² + 11)
C
+ 33M + +1).
m2
Thus the divergence can be bounded as:
M
Add
(M2 + -
A2d
DRI(PK]ÍKи)
C+Cn
+ 3700
Ki}² + 2
+ 0²) Kn
2
4
M
EKn +
M2 CT²² +
1
(MP +1)
A2d Kn+
3M2 +1
o²Kn
2
2
2
M
EKT
2
( C (M2 +1)
1
Add Kn +
3M² +
0 Kn
2
A
CoKi) C1
Kn + C202Kn.
We are ready to bound the Wasserstein distance,
Wh (px: (px) S (12 + (12+8(km)) + + 2d)) (Co + VolVi+ (Ci Vā) A+ +C22 VO5) B) (Kn)²
=: (Co vī -
A C2 B) (Kn)²
where the constants are defined as:
A
Add
A max
2 Vo²
max
C. = (12 + 8 (Ko + 26 + 2d))
2
(Co+ + VC,
2 = (12 8 (No + 26 + 2d))
(1 VC
C (12 8 (No + 2b + 2d))
(C2+ + VC2)
From Proposition 9 in the paper Raginsky et al.
2017], we know that
Wa(dky, 20ss log lpolllo + log +
d
3x
(MAD + +BVro + Go + b
(Mo
log 3
Kn/C2S
2
3
Uge- -Kn/CLS
Finally, have
Wa(pk.p") + Kn + CeeKKn/Cus
(68)
To bound the Wasserstein distance, we need set
5/4 = and Tze Kn/COL 2
(69)
Solving the 69
we can have
2C e
Kn = CLs log
and 17 ==
16C (Kn)**
45

---

Published in Transactions on Machine Learning Research (04/2024)
Combining these two can have
16Cp Cts log (20g
and K
160g Ctss log'
2Ca
d
Plugging K and into 668 completes the proof.
E.8 Proof of Theorem
In this section we generalize the convergence analysis of SGLDLP-L in Zhang et al. 2022 to non-log-concawe
larget distribution. Following the same proof outlines Raginsky et (2017 Recall the SGLDLP-I. update rule 2 is the following,
Xk+1 Qw ( + 22
X: () + 21 + ax:
where ag is defined as:
0g = Qw - (xx)) + 22tk++1 - X₁: [x((((x)) + 21ER+I
Thus, we can define a continuous interpolation of the SGLDLP-T. as:
x, Xo - x
[''C.da G,ds v2
v2f. aB(s) S( a((s)sss
where G2 Σ ll (Ec, and a(s) Σ 2a//n/eckknn(+u00 By taking the difference
of the interpolation with the discrete estimation of Langevin process in equation
we can derive the
Radon- Medon-Nikodym derivative of the PKn w.r. PK
{1 { 2 I. (v.(x.) G. a(s)))) 1 {" [VU((x,) G. a(s)]
deкn erp dpk
Thus, the divergence can be computed as:
Kn
1
E
|VU(xs) GG a(())] ds
4
1
K
1K+
VU(x))) Qc(VU(())) - aa/n/| -au/n| /m|] ds
E
(k+1)g
K-1
(k+1)n
E
(U((x)) - Qa(VU(X))) ds +
|laa/nll /nl]] ds
Jon
k=0
kn
(k+1)m
K-1
(k+11)
E
[Vx()x - v((xx))1
ds
E
VU(x)) Qo Qo(VU( ds
Jen
k=
(k+1)y
E
[|au/n11?] ds
kg
2
11+
K-
(k+1)g
||x.- xx
ds +
Σ
E
V((x)) -o ds
k=
Am
(k++1)m
E [las/nll]
ds.
(70)
kn
46

---

Published in Transactions on Machine Learning Research (04/2024)
From the same analysis in
25 know that
||x, x
| s " [IVU((x))]
+ +31/² (U((x)) Qo(VU(X))) + 6nd
S 3n²
ME ||xx||||
11?
+ +G) + 3n7
(At +0²) + 6nd.
4
Again, we need to derive uniform bound of E [|xx||]].
E
1|
=E
X na (VU((()))))) [1]
+ 2E [1E++211? 11] +E ||ax 1?²
X v)V(((x)) + Vx())) - NQc(vV (xx) )x/) /|
=B
+ 2nd + E | 1l?
X ,x++((x))))))) + V)V() - (VT((V((x )) 11
+ E [|oaall]] + 2nd
E
=E
||x:
nxU()+)) + |U((A)) Qa (VU())))
|2] + E ||ax [2]
+ 2nd.
By plugging in the inequality we derived before:
[Ixx - vvxxx=) (1 21m2 21y² (2) E [|xx|]]] + 2np G22
E
we can have:
172A2d
E 1|]] $(1 122m2 + 27)² E [|xx|(]] + +mpb + 22 +
+ 1000² +E ||az [2] + 2nd. (71)
4
Thus for any 17 E (0, 1 A m122 and
2mm2 + 222 > 0, we can bound E
||xx|]?] for any de > 0 as:
||axx 11²)
Add
| [?]
SE [|xo||?] 2]
+
2b + 2G2 +
+ + + 2d +
2 (m2 722)
4
2n (mz n22)
E ||x
1
Ad
<B
||xo||?]
26 + 20
+
+
0² + 2d
+
m2
4
17122
E ||axll
?
Ad
<8
4mz
1722
where the constant is defined as:
=
E
|
2]
+ m2
(2b + 202 + 02 + +2d)
Thus, we can have,
E ||a 12
E [|x, xxl1?]
<6n²
E
3d
+ G2 + -n7
(4/
(1dd
4 + +0²
+ 6nd
4mn
19112
6nL ||au11?
6 + 3m2
<En
31/20
17²
2d +
4mg
m2
47

---

Published in Transactions on Machine Learning Research (04/2024)
Plugging this into the equation 70
can have,
3M DRI(PKllpKo) S - Kn²²
ME
(6 + 3mm2) MARd
6ME
|| 1
Kn
A
KE
+
K1j² +
+
+ +0²
Kn +
4
16m²
4m2
4
4
4n
ME
3M +
(66 + 3m2) M - m2) d
6M1n
1
Knp² +
o² Kn
A
Kn +
+
KB
|
4
16m²
4m7
4n
By the fact that E ||ax|| 1
Add
we can further bound the divergence as:
4
ME
3M +
((12 + 3m2) M m2) d
d
DKL(PK((RK)) S 4
4 o² + =:CKKn + C2 2 Kn + C,A*K,
Kip²
+
16m2
16n
where the constants are defined as:
ME
Co 4
C 3M +1
C2 = ((12 + 3m2) M m2) d
d
16m2
16n
We are ready to bound the Wasserstein distance,
(pk. pkn) & (12 + 8 (No + 2b + 2d)) [(co VG (c+ (CL+Va) A) (Kn)² + +022 + VCz+
=: =:(c" - - (Kn)² + To' AK?
where the constants are defined as:
max 0² Vo²
Go = (12 +8 (8 + 2b + 2d))
(Co+ VCo
G = (12 8 (No + 2b + 2d))
(G VC
C2 (12 (No + 26 + 2d))
2
(C2+ + VC2
From Proposition in the paper Raginsky et al. 2017), we know that
Wa(pkn, 20 log logllpolle + d log +
3x
(Moo
+o+ + ++22log log +B GG
b
Kn/Crs
2
3
Kn/Cus -Kn//rC
Finally, we can have
Wa(pk.p') & (Cont/'+ Kn+ T
(72)
To bound the 2- Wasserstein distance, we need to set
5/K - and Kn/CkL
(73)
2
48

---

Published in Transactions on Machine Learning Research (04/2024)
Solving the 73
have
2C'
c²
Kn Ls log
and
71 -
16Co (Kn))
Combining these two we can have
160D CL, log"
(20h)
and K>
160g Cts log"
2C
Ed
Plugging K and into 72 completes the proof.
E.9 Proof of Theorem
In this scction we generalize the convergence analysis of VC SGLDLP-F in Zhang al. 2022 to non-log- concave target distribution. The proof is similar to the proof of Theorem g but the variance corrected- quantization function The variance-corrocted quantization technique establishes scalable bound for the discrepancy between quantized and full-precision values, contingent on the learning rate. This enables variance-corrected quantization advantage over simple stochastic rounding.
Recall that the update of VC SGLDLP-L
Xk+1 = Q (Xx
211, A)
Xx (C-(o((U((())) + 21tEx + ak:
where aş is defined as
ag = Que Xx - 1/ (VU()))UUX)))))))))))))))))))))) 2n, 2n: Xx - 1 (VUxx)) + 22ER.
From analysis in Zhang et al. 2022 we know that
E
||ax1| ||]
max (2ArG,, 5md)
Combining the analysis in section E.8 we can show,
ME
3M +
Kn + ((6 3m2) M + m2) d
6M
PxI(pkllkkn) 5
Ki²
+
A²K1 +
+
KE
|| 11)
4
16mz
4mz
4n
ME
3M + 1
(16 + 3m2) M + +m2) d
6M1
+
o² K1
A 2
KnA
16mz
4mn2
41j
ME
3M +1
o²Kn + ((6 + 3m2) M + m2)
6M + m2
Ki² +
2
KA
4
16mz
=0, C1 Kno² + C2KrA² + C2KA,
where the constant Co, C₁, C2 and Cg are defined as:
Co ME
3M +
C 4
C2 ((6 + 3m2) M + m2) d
16m²
C 6M + m2
712
49

---

Published in Transactions on Machine Learning Research (04/2024)
We ready to bound the Wasserstein distance,
Wa(p, 1 (12 + 8 (No + 2b + 2d))
[( VC6)+ + (a a))
(kn) + -C2= (C2+ (C2+v(2) A(Kn)²
+ CCa VCaa AK21)
=: (o 1 + Ci 1 C2 (Kn))* + +Cg AK'n
where the constants are defined as:
Ā max 02, Vo²
A = max
A, V
Co (12 8 8(o + 2b + 2d))
2
(Co VC)
G (12 8 + 2b + 2d))
2² 2
(G VCi
C = (12 (Ko + 2b + 2d))
(22+ VO3
T = (12 + 8 (no + 26 + 2d))
(C3+ VCa)
From Proposition in the paper Raginsky et al. 2017), we know that
We(Okm,)")) S
201s log lpooll + log
d
3 + ( (Mro + BBrro + Go + 2 log 3
Kn/Cus
3
C4e -Kn/Cus
Finally, we can have
Wa(pK.p") (Gv++vVA+VvV Kn K KV+CVVVK*, K2n + -nn/OSs
(74)
Too bound the 2-Wasserstein distance, we need to set
SoK and Tze-Kn/ Kn/CLe
(75)
2
Solving the 75
have
2Css and
4
Kn CL. log
16C, (Kn)*
Combining these two we can have
16C Ch logs (20g
e1
and K
160, Cts log"
(20g
e4
Plugging K and n into 74 completes the proof.
50

---

Published in Transactions on Machine Learning Research (04/2024)
F Techinical Proofs
F.1 Proof of Lemma 12
Proof. By the definition of f
E.4
| = |Bğ(x) - EXU(
(EVU(Q - (x)(1)
S E (I - [
s M [11@((x) - VU(x))
A 2d
- M
4
We also know that from the definition that
E I (xx() (x)x
[o (x))) ViLQ + VV(Qw()))))))) -U((W(x)))) VU(Qw vU(x))1
= =E]]Qo(VV(QW (x))) VO(QW + || (U)) -VU(xx))))
A2d + + M Qw (x) x|1
< (M² + 1) A2d
4 +
where in the first inequality, we apply Assumptions I and 3
F.2 Proof of Lemma 13
Proof. Let P1 be the set of all couplings between P0 and q" and I2 be the set of all couplings between 8,10 adn q² Let ry be the optimal coupling between 9, and q", i.e.
E( 1110 - = o d²)
Let
T1. We define the random variable
[
W
xr
( (o6 e->(0-))ss dr) g (Jo" (55 -- -sss-)dss) dr + for x(s- ds) &
+
By equation
44
20 w
define a valid coupling between 2,90 and q² Now we can analyze the
Wasserstein distance between 4 90 and 9²
51

---

Published in Transactions on Machine Learning Research (04/2024)
(Lo ( ( ds) dr) 5
[x*]
27
22 4¹) < Er,,
+ u
[Io (So d dr + -o - ds E
(76)
[ + +w ((10 (1o e -5 ds) dr + So e ( dss
(66 (S x ds) dr) LEg
1 x²
< Er,
e w"
IDE
(66" (J e (- ds) dr) (E BE)
Eri
(05" (fo 7( (() ds) dr + So - 1) ds) (E IEE)
WW Wa q²) + 2u / 1/2 / + 1/2 ||REI]) + 4u (1²² /4 IB,,
[1I - |
q²) + 35/2 VdM2 + 5u²17² (M1² + 1) Add
2
+ +
(77)
4
F.3 Proof of Lemma 10
Proof. In order to get the upper bound of ||xx|] and ||væll, we bound the Lyapunov function E(xE, v&). By the smooth Assumption
! we know
U(x++1) ((=)) Ux+))+ + (VU(x:), Xx+1 xx) + M2 [|xx+| - xell²~U(x')
Recall the definition of the Lyapunov function
E(x++1, Vk+1) ||x + ||xx+1 + 2Vx+1/7/11 + Su -
For the first two terms we have
1x++111 = ||x1| + 2(xxE, X1++1 - xb) + ||*x+1 - xx112
Xk+1 + 1//+1/ = ||x: + 2V1/>11² + 2(xx + 2/1/ Xx+1 - + 2(V+++1- - -v))/1
+ +||x++1 - Xx + 2(vx+1 - vz)/>/12.
This implies the following:
4 vx)] + [Xx, Xk+1 xx)] + - [(xx) - vn)l+ - - E(( Xx+1 - xx))
E| (1(X)))))444)) S E[
(78)
8u E (VU((x)) Xx+1 - -xx) + M/2 ||x++1 - xxl1²]
E ((VA, Va+1 - vai]=
22
72
+ E ||x++ - Xx 12]
+ EE
||x*+1 - Xx + - va)/v11].
By the update rule in
55 know that
1
--70 797
E [[ vR)1 + u(mm + e- - 1)
E
[xx, Xt+1 x+)1
E [(x,, (xx))).
7
72
21
e -
E (Xx, Vh++1 vN)l -(1
M- ((X,, vR)]
[(x,, 0 (xx) ))],
E [VV, 1 xx+) 1 - 2
γ E [|va|]]]
u(nm + e- - 1)
13 [(v.. (xx)),
722
E (VV,, Ve+1 -wil = -11 - e MH
[[]
u(1
e --
E [VV (xx)))
?
52

---

Published in Transactions on Machine Learning Research (04/2024)
Plug into the 78 yields:
E (x Vk+1 ) S E (E vie]] 4u(2- -m -2)
4(1 -
E [(X 9 (xxx))
||
72
9/2
4u(?m + e-7 1) E [(v kv ( [xxx))]
+ 8u(1 - E -777
E [(VK: VU (x(x)) -xxx)MI
73 817) + e - 1) 1E (VU (VU(xx))
73
4MM
3 B ||x xull"]
(
74
[IvA+1 - vall -val
+ 72
(79)
By Assumption
2 we know that (xx, (x(x))) 2 m2 |xx1| b. We then assume nj S 1/((8) and use the x²2 /2 for any 0, it follows that
inequality - S
(2 - -m- 26 "7
E [xx: 1 (x++))]
72
Au(2 711 - 22 -21
(T. (xx: [U(x)))] [(x:: [(xx) - (Uxx)))))
7/2
4u(2
2e -22-77 m 191
m2ll |||x|| []] -b) 4u(2 -11 717
22 mm)
( [|xx1]1]]
21E [10(xx) [U(()))
72
722
<
3m2uum
E
[xxl1]]
Aumb
8um
E [1Ø(xx) vU(xx))?
where the first inequality is because of the Young's inequaltiy and Assumption D and the last inequality is
based on the inequality that ynn (mm)² < - -m1) 2e~ 70 S mn- Again by Young's 's inequality and the update
rule in 5 we have:
E |x++1 - xx(|²]
s 21 [|v
+ +u2n" 2/214/21 /2E
[|x(x)))1 + E [[SE|]]]
E
||v++1 - vall"]
< ,,""11BB ||vx||]] + 2u² 2n²r,²
[l |[r]
+ E [I<E|]]
It is easy to verify the fact that E [|E]|]]
< 2yudy and E [|EE|]]
s 2udrI². Thus,
E [E(x VK+1]]
< E [[ vk)l
3umn?
E
||xx|] 12]
3(1 --- 17 uy + +2272)
E [[vall]]
722
36 2yun2 + (4Mu 372) 11
2u2r2
E [1x(x))1
[xx(()))
27
722
Sun(22 +2u) E
(xxx)) - s(xx))p]
(8Mu + +672)662)
4 4(4d + b)umm
73
1/2
If we set
4u
6ybu
17 S min
4 18MMu+ + uy + 22>2)' V
4Mu + 3-y²'
(4Mu + 37 d
we can obtain the following,
E (E(x+11 < E [E vR)]
3um2 γ
E
||xxe] 12]
2n E ?
[|val]?] (20u + ?uun?
E [10(xx))] [1?]
72
n2 22
Sun
(72 + 2u)
16(d + b)un
[VU((x))]]]]
|VU((x))
0(xx))12
(80)
3
53

---

Published in Transactions on Machine Learning Research (04/2024)
Furthermore we can bound E
[1x(xx))]* by the following analysis:
E [xx
< 2B [1x(xx))
(x(x))1 + 2E [xx(())))))
(81)
2 (M² + 1) A2d
+ +0²) + 4M [xxul]]]] + 4G
4
where G2 is the bound of the gradient at 0, i.e.
||U( S G². Thus we can have:
E [x(x++1, Ve+1)l s (xx, v&)]
3ummn
E
||xx|(]]
2 [|vx|(]
+
(2lu + 7)4M2)23)) uun?
E
||xA| |2]
(82)
y/2
2(20u + ?
Surj (7 + +2) )
A2d
+
+
(M12 + 1)
+ o²)
(83)
72
7.
4
(2lu + Aum
16(d + b)wn
G²
(84)
72
If we set the stepsize
7/m2
8(72 + 2u)
7 S min
12(21u + ?)M
(20u + 7>y
then we have:
E [8 V.+1 v++1)] < E [E(x)) Vn3]]
8umma
E
||xx=|| 1?2
211 2
[|vell
37
7
16un (72 + 2u)
)
A2d
(M²² + 1)
+ 0²
7:3
4
(2lu + 4)u?? @² + 16(d + b)um
72
Furthermore by Young's inequality and Assumption
we can bound the Lyapunov function by the following:
E(r,u) < 5/2
+
12
+
2uM
3 [||1r]|| + 6 || 11)²
72
72
Then if y2 < 4Mu, we have
16uM
12
12uM
E(x,0) -
||a||/
||0|
||00
(85)
72
72
722
Thus,
16un (7²+20) +2uu) ) ( + 1)
EE [E( v++1) < (1- m2
E Ex v&)l +
+
1)
A2d
+ 0²
6M
7/3
(21u + 7)n
G2 + 16(d + b)wn
72
?
Finally we show that
6M
16um (7² + +u)
(M1 (1) A2d
sup E [x(x,, vw)l
< E [8(0,, uo)1 +
4 +02
k20
7m221)
7:3
6M (2lu + 4um?
6M 16(d+ + +bjn
G2 +
7m27
72
7m2n
?
96n (72 + 2n)
Ad
24(21u + +
96(d + b)uM mz?
< E (E(0,, Hb)]
(M 1)
+
0²
62
mzy4
4
m
<E+C3
((NP++)) 112+11
Ad
+ 0² 02
(86)
4
54

---

Published in Transactions on Machine Learning Research (04/2024)
where & [( vo)l + Laypunov function, we know E(x, v) 2 max|||=1 2 ||//11/}, This further implies that
p G² + S and Co
96u(=2+2u)
Moreover by the definition of
mz?²
m2?*
S E Co ( + 11 A +0²
E X |
4
E
v
S 2/28/+7206/
(DA22 + +1)
A
+ 0²
4
Combining with equation
we can bound E
[1x(xx)] as:
+1) A2d
B | (xxxx))
52
4 + +0²) + 4M 4G
(87)
F.4
Proof of Lemma 15
Proof.
By the update rule in we have:
E | |13]
=E X (xxx))
2 + /8 ( -n)())) 2n [1sc+1 11
E
X n5(x)) 11
+ -2d
E
| 7VU (0(x*)
( (xx) VU (xx))111 + 2nd
E
||CC (xx)) (QW (xx)) VU(x)))) 1 [1x(x)) - VU(Qw
(xx)))1 vU(@w(x)))1
2nd
[||x (xx))) + (Qw (VUx)) |//0://)))XXX//////////////////0 (A-d +0²) + 2nd.
(E
We know the fact that:
||xx -
(NNx-vVU((xx))))) (xxx)1
= ||xx| 11 2r/B [(xx, [x(x)))) + 1 [ [x=
| ?
+ 2n1 mzlE ||xx|| (1)) + 2n7 ( ( ||xx| 12 + G22
= (1 22mm2 + 2n7² M²) E [|xx11]] + +mp + G2
For any 7 (0,1A TM"
if0 < 20m2 2nj² M² and
1-2mm+2y M77 then we have:
9mg 1y² 2,2 asa
[ ( + (1+ B [IVU(QW(x)) VU +n² ( + +02
E |1x*+11| 11] s (1+c) =====1]][[+000)00
+ +nd
(88)
1 11m2 + + M 22
1 - 1111 +
< (1 1mm2 M TE. [|x]
(2n + GP)
1m222 M
21m² + +27 1/2
(89)
2d
+ n
0² 2nd.
(90)
55

---

Published in Transactions on Machine Learning Research (04/2024)
For any we can bound the recursive equations as:
1- 1-mm2 + 17 M2 M2
1712 + 11²M²
E
x |??
S
|
+
71 21ym2 + ( (2nb 21)
1) -n
1
112
Add
4 + 2nd
mmm22- -mM)
1 - 1m12 + MM2 M2
17m2 + 12²
= E [12011?]
+
(26 + 2m
(1122 1/22)²
4
21mz + 2y² (12 71122)
Add
m2 77122
17
+ n1o²² 2d
2.M² 2 A
2
2
A2d
$
||00|| 11
+
+
(26 + 2n)
+
1] 4
+ 1100 + 2d
4
112
M2
Now if we let - E ||000|
(2b + 2n + 2d), then we can write:
ma
2 (M +1)
A
20
|xx1|?
E-+
m2
4
F.5 Proof of Lemma 11
Proof. From the same analysis in 80 if we set
4u
6ybu
S min
4 (8Mu + uy + 22-2)
4Mu + 3-2²
(4Mu + 372)
we can obtain the following,
E [x(x++1, Vk+1)] S [x(,, v1:)
3umm2
xx [2]
211
Vi + (20u 7)mn?
E
72
2u 2n² 21
E [IVU(x))]?
Sun (72 + 2u)
16(d + b)un
+
+
2
3/3
7
(91)
By assumption 1 we can bound E [[(x)(V(()))]]] by the following,
E [[Qo((U(
[| VU((+) VU((x) VU(O) + -0
E [QQ (xxx || 2E [Xx))) - vc(())]]] + 2E [V
< Add + 0²) + 2M/2
|| ||
+ 2G2
56

---

Published in Transactions on Machine Learning Research (04/2024)
Plugging this bound into equation
91
we can have:
E E (X4+1, VR+1)l & E (x(x, vR)]
3um27
[1xx|11]
27
|| 11
+
2(20u + +7)unp M²
EE
| 1l
72
(20h= u)?
<d2d
2n²nn²
+ 0² + 2G2
(2M
[|xx||?] + +20²)
+
72
4
7/
+ Sun (72 + 2n)
Add
16 (d + b) wn
+
+
+
73
4
7
< E (xxxx, vk)]]
3wm2nl
[1xx|11]]
2 FF
[|val]²]
2(22u + 7))nn² M
IE ||xx|| [|]
?
72
(20u 7) yun? 2 + 8 (n² + 2u) wn
<dd +
2(22u ?)un? M2
16 (d + 6) wn
+02)
+
G²
73
4
73
$ E [x v+))
3umm?1
[|xx|11))
2m
[|val?]]
+
2(22u + wuu
E
[
72
(36u 972) un ( (A9 + +0o)
2(22u + 7)un M2
16 (d - b) wm
G²
73
72
7
If we set the step size 1) S
2m G(22u-1)MP
we can have:
E (xK+1, Vk+1)] S 18| (XX,,
vt+]]
Sum2n
E ||xX||]]
2 1
[1vall
(92)
37
7
(36u + 9-22 w//
AAdd
2(22u + ?)U? M
16 (d + b) wy
+
+ +00)
C² +
(93)
7/3
4
72
Again from the same analysis in 85
if g2 < 4Ma u, we have
16uM
12
12uM
E(x,0)= S 72
|| +
|1011
2 +
1|
112
22
72
Thus,
E [ V++1)] S (1- 7m22
E [XE, vI.)]
(36u + gh²2) un
/12d
+ 0²
6M
33
2(22u 7) um? M²
16 (d + un
G2 +
72
Finally, we show that for any k > 0,
6M (36u + 177) un
Add
[[(K,, vk)] s E [Z(0 un)] +
+ 0²)
mm2
73
+ 6.M 2(22u + 7) un? M
6M
16 (d + b) un
6²
mm2
72
7/2271
54 (Au+ + 72) u
(Add
+ 12(22u + 7)MM
96 (d + b) UM
- E [E(0, (0))
+
( + +02
G²
m274
mz73
mzy
= + Cddd.
Finally by the fact that E [|xx||²] < < v&)] and E [[vva]]]] S 3 (E(x,, va)] /2 we can get our claim
in Lemma
57

---

Published in Transactions on Machine Learning Research (04/2024)
34
HG
30
SEANCELL
2.3
VESRANN
24-
1.5
0.5
45-
250
150
730
1000
1233
1500
1750
250
500
755
1000
1250
15:0
3753
250
903
150
1000
3290
1500
1950
Be
Danaton
(a)
(b)
(c)
Figure 8: Train NLL low-precision SGHMC on logistic model with MNIST terms of different numbers of fractional bits. (a): Methods with full-precision gradient accumulators. (b): Methods with Low-precision gradients accumulators. (c): Variance corrected quantization.
MCLF Sta MELFN
SOHNELPL SCANCEPLL
SOHNCLLLL
VC SUAIELLFLL
11-
10-
250
250
720
12:0 Be vila
1250
1750
220
722
1000
1500 3753
200
1000
1250
1500
1350
(b)
(c)
Figure 9: Train NLL of low-precision SGHMC on MLP with MNIST in terms of different numbers of fractional bits. (a): Methods with full-precision gradient accumulators. (b): Methods with low-precision gradient accumulators. (c): Variance corrected quantization.
G Additional experiment results
In this section, we provide additional experiment results.
G.1 Logistic model
In this section, we present the low-precision SGHMC with logistic models the MNIST dataset. The results are shown in Figure 8 We see that SGHMCLP-F is robust to the quantization error, even though only 2 bits are used to represent the fractional part the SGHMCLP-F can converge to a good point.
G.2 Multi-layer perception
We present the low-precision SGHMC with MTP MNTST dataset in Figure the low-precision SGHMC with the logistic model.
We observe similar results
H Generalization of Theorem 4 under Relaxed Variance Assumption 7
All thcorems presented in the paper assume bounded variance for the stochastic variance (i.e., Assumption
Another more flexible yet commonly used variance assumption (e.g., Raginsky et al.) 2017 Gao et al.
58

---

Published in Transactions on Machine Learning Research (04/2024)
2022) allows the variance scales with ||x|] In the rest of this supplementary material (Sections G-O), generalize all the theorems in the main text to such variance assumption, i.e. Assumption 7 Note that most of the arguments used in the proofs under Assumption 3 still hold, necessitating only slight modifications. Hence for the sake of readability, we only present the key changes due to the differences in the variance assumptions.
Assumption (Bouned Variance). There evists conslant B 2 O, such that |U(0) < B. And there
erists a constant å E [0,1) such that:
B (x(x)
vU(x) -UXx) 28 (M |x|| + B2), for any x R.
Let Assumption 7 be true, we can then derive the following lemma.
Lemma 16. For any Rd, the random noise of the low- nuu-prccssion gradients defined in
40 satisfies:
|| & M A2d
(94)
4
Ad
|| < (2M² + 1)
+ 28M |xx| + 2812.
(95)
Now, ready to present the Theorem 4 after revision.
Theorem 17. Suppose Assumptions and hold and the minimam satisfies ||x*11 < D2. Furthermore, let pt denole the largel distrilulion of x and v. Given any sufficienlly small e, if we set the slep size to be
CIT
e!((m)))
min
47 D2)" 72 (20n25M>ns(d/mm D2) 5 ((M 11) +8B2)
10udM2
then after K steps starting with initial points xo vo - 0, the output (xx, vx) of the SGHMCLP-E in satisfies
for some K satisfying
36
+ D2)
Kg K
= (v36-= 2 (e-1))) 42).
< log
Proof. For strongly log- log-concave target distributions, the equation the following.
in Lemma 10 needs to be updated
59

---

Published in Transactions on Machine Learning Research (04/2024)
Add
W3 ( q²) - (Wz( 1-) + V//2 + 5 (2M²
+ +1)
+ 52 ||x1| + 55B²
4
- (22(0n00000 9²) + v5/2un
10u2n/6M2 |x x + 10u² 10 6 ||x||
A2d
+ 5²
4 + +8822
(96)
- -(W2(5000:))) + v5/2un/ VuMA) 2
100"1"5M2" 4²) + 10u²n/66 ||x||
+ 5u?r7 (2M²²
+1) Ad + 68B²
(97)
4
W2 ( qo. 9") + v5/2umvdMA) + 5u²1/ (B2M2 + A2d
$ ((1 10u?n/5M²)
|x|
+ RB²
(98)
In the second inequality, Ç is an optimal coupling between to and qs- x/x' are from the distributions 0//4"
Then we choose 17 S
2/(4m1)-1
10a6M1 and following the same argument for deriving equation 46
we can have:
(ona + v BEK + +V5/2un/aM))
W3 (((0))))0))
10 E.p ||x|
(99)
=52272 (2M2
+ (1er/2222
-1 A2d 5M B2
(100)
Morcover, we know the fact that
Epp
|x||
-Ep- ||x xol1
(101)
< 2E |x 111
+ 2 2|1x - xol
(102)
2d
+ 2D2
(103)
Thus plug it into the equation 99 we have
2 Vun (ma) )²
W S enn/an 9¹) + n²V
8E
+ +10u2,72MM*
(2d
22d
+ 2D²
(104)
m
5u²n? (221 (2M +1)
Add
+ 8B2
(105)
4
Finally, by invoking Lemma 7 Dalalyan & Karagulyan 2019), we can have
1/2
8x 5
5d
Welgk.97 9¹) S e KK//4x W2 (*) +
(106)
n/2mmmm
10 10
2dd 2D²) + 5u
(2M² 1) 1) +882
8EK unMAvad
vI V 2/2 v 10u21 (2d + 2D2) + 5u ((2M² + 1) A2d
+ +8B²)
2
(107)
60

---

Published in Transactions on Machine Learning Research (04/2024)
Thus for some K satisfied
261 K
d
+ D2 )
log
36
m1
can get the following
sc+ 16 uM A 5d
Wo(pk.p")
(108)
Generalization of Theorem 5 under Relaxed Variance Assumption
Now, we are ready present the Theorem 5 after revision.
Thcorem 18. Suppose Assumptions i and hold and the minimam satisfics ||x* D2. Furthermore, lel p' denole the largel distribulion of and v. Given any sufficienlly small e, if we set the slep size to be
EKG 663552/5(d/ + D 144 (240266MPp1 + D2) + 5u ((2M² + 11) + +B2))
e²
e el/(4k))
7 min
10u6M²
then after K steps starting with invitial points Xo vo 0, the outpul (xK, vx) of the SGHMCLP-L in satisfies
Wa(p(xk, vk),p" S ① c (e+ 4
for some K satisfying
36
d mi
+ D2) +
Ō -vVov 2log (e (6'))²)
K
log
Proof. Now we revise the proof of Theorem
5
'The revision is similar to the revision for Theorem 5
By similar argument in
98
equation
52 need to be changed as the following:
Add
W3 (2,00.9')
W3( )²) + 1
S ||x|| + B2) + 2u (A + B)
(109)
$ W2 + 60 ||x - x'12 -x12 1002 ||x||
(110)
+ 2 + n7 2d
+ 2u (A+ B)
(111)
2d
Add
(1 + 10 2 W 1 -0 "0 0²) 2 5M2 25M²
D2
2
2u (A
B).
m
4
(112)
Then we choose 7 $
- 10ubM/2 and following the same argument for
52 we can have
W (2ng)
e-n/Ami (9:, + 172
8E
+ 10w² 10 T6M2
2d
m + D2
(113)
5
1u² 5u²2n² 2d + 2n (A B).
(114)
Then the remaining analysis follows the proof in the original Thcorem
61

---

Published in Transactions on Machine Learning Research (04/2024)
J
Generalization of Theorem 6 under Relaxed Variance Assumption 7
Theorem 19. Let Assumption and hold and the minimoum satisfies ||x*|
11 < D² Purthermore, let p denote the target distribution of v and x. Given any sufficiently small e, if we set the step size r to be
2²
e2/(xx))
ERi
1/ = min
144 (dd/ D + 5 ((2 1) A4 + +8B2)
10u6M2
663552/5
d D2
then after K steps starting with initial points xo vo = 0, the output (xK, vx) of the SGHMCLP-L in 6 satisfies
Wa(p(xx. - (c+ VD).
(115)
for some K such that
36 d.
+ D22
K1 K
=Ō =Ō(e=log (Vōe-1) 42)
log
7
The revision closely mirrors the revised proof of Theorem based on the assumption that Assumption 3 holds.
The only equation we need to revise is 60 Given the similar argument in 98 s we can have
4n²²
&
Wa(pK. & 4e Kn/4k Wo(go, (")
(116)
c 7/ Ax1
40n²n28M2
2d
+ 2D2)
+ 20x2,2
Add + +0B²)
+ Su²n (7A+) +B)
88 + +v1 5
a/m n/mi
17
2d mi + +2D2
+ 5u2'72
(Add + 5BB2) - 2u2n (7A+ + B)
(117)
K
Generalization of Theorem under Relaxed Variance Assumption 7
This section updates Theorem 8 proof, replacing Assumption 3 with 7 and introduces the revised theorem.
Theorem 20. Assuming i and hold. Let p" denote the target distribution of (x, v). If < 4Mu and setting the step size
e² Tog(1/e)
satisfying
4u²
6ybu
1
7m222
8(>2 + 2u)
m2?7
n S min (8Mu + uy + 2272)'
4Mu + 32 (4Mu 3y2) 87" 12(21u M2 (20u + 7)7 12( + M2 M2
then after steps starting at the initial point xo vo 0, the output (XK, vK) of SGHMCLP-F in satisfies
No(p(xk.vx))p') (++ A A log (1)
for some K salisfying
2 K K= ( log² )
where constants are defined as: Ā max + 2d 81/4 and constant 1/p" exp (O(d)
denotes the contraction rale of underdamped Langevin dynamics
10
62

---

Published in Transactions on Machine Learning Research (04/2024)
We first need to introduce further assumption on the variance parameter å as the following assump- tion.
Proof.
Assumption 8. Given Assumption
7 we further assume the satisfies the following condition:
8 S min {
m2
8(7² + 2u) m27
m2?²
12(21u M2 (20u + 7)y 3(20u + 7) 12(7 22)
We need to revise the 84] as the following:
E [x(+++1, va-1)) s E (xx,, v&))
3ummn7
EE
||xx|?]
27 E
||vx||]]
(21u 7)4MM)2r un,
||xx||]]
(118)
?
?
72
2(20u + wum?
Sun (7² + 2u)
(Nr + 1)
Add
+
+ 8M | 11 + +6B²
(119)
72
73
4
(2lu + 7)4mm
G² + 16(d + b)wn
(120)
?
If we choose 17 satisfy the following condition
ym2
8(>² + 2u)
m2?
m2
8 5 n < min
(121)
12((1lu + ?2
(20u + 7)> 3(20u + 7)) 12(n2 + M
then we can have
E E[E(xe+1, S E [E(X); vx]]
4umm
E ||x:| [2]
2n E [[vell]] 7
(122)
37
16un (72 2u)
)
(ANP² + A2d + +82
(123)
73
(2lu + Aun
16(d + b)mm
6² +
(124)
The remainder of the analysis is unchanged.
L Generalization of Theorem 2 under Relaxed Variance Assumption 7
This section updates Theorem s proof, replacing Assumption 3 with 7 and introduces the revised theorem.
Theorem 21. Assuming 1
g 7 and & hold. Let p" denote the target distribution of (x, v). If If < 4Mu
and setting the step size 1 δ
2=
satisfying
[og[1/e]
8(72 + 2u) 4Mu + 322' (4Mu+ 372) d' 8y 12(21u + 22 (20u + 7)r 12(r² + 22) M
4u
6ybu
1
7m2
mz?
S min (8MM + wy + 22y2)'
V
then after K steps starting at the inétial point xo vo 0, the output (XK, VK) of SGHMCLP-L in 6 satisfies
Wa(p(xK, v=()") (0
(+00 /lo8
3/2 3/2 (1)
log
VA
(125)
2
for some K satisfying
K = δ
1
log?
)
63

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. We need to revise the equation
93 as the following:
Sum27
- - [[vall?]
E E (XK+1, Vk+1)] & [E V*]]
E ||Xx||]]
(126)
37
7
(36u + 972) wn
Ad
+ 8M
|xx|| 1 +8B2)
2(22u +
?)
C +
16 (d + b) un
7
7/2
(127)
4-
If we further choose 1)
3136u+ty"* JMT and assume 8 S 17, then we can have
E 18411V4410 E (x vı)]
4um22
E
|xx]|²]
2n E [
||vall?
(128)
37
7
(36u + 9 w7
Add
2(22u
T)un M
G² 16 (d + b) un
0132
(129)
73
4
7?
7
M Generalization of Theorem 3
under Relaxed Variance Assumption 7
In this section, we present Theorem
3 after revision.
Theorem 22. Assuming 1
2
7 and
8
hold. Let p* denote the larget distribrution of (x, v). 15 = 4Mu
and selling the slep size
A4 e²
salisfying
Tog(1/e)
7 4 (8Mu + wy + 22y2)'
6ydu 4Mu + -322 (4Mu+ + 3y2) d' 8y" 12(21u + M2 (20u + 7)y 12( + 2w) M2
4u2
7722
8(72 + 2u)
m2?
n S min
then after sleps starting at the initial point Xo = vo = 0, the output (XK, vK) of SGHMCLP-L, in 6 satisfies
(ct V 'log ()) log (2)
We(p(xK, Wa(p(xx,vx).p') vk).p")
VA
(130)
e
for some K satisfying
(1)
K K= δ (Z log²
The revision of Theorem is the same the revision for Theorem 2
N Generalization of Theorem 7 under Relaxed Variance Assumption 7
In this proof, we revise the proof of Theorem 7 if the Assumption 3 is replaced by Assumption 7 Theorem 23. Suppose Assumptions
and 7 hold. Let p denote the target distribution of x, À have the same definition in Theorem 1 and 1/X* (O()) be the concentration number of 13 After
steps starting with initial point No 0, set the slepsize to be 1 =0 =Ö - ((oar)/a)))) The oulput xx of
SGLDLP-F in 1 salisfies
Wa(p(xx))p") c+ (VA+ (VA+ +1/11) log )
(0(+
(131)
for some K satisfied
1 1
)
1ogs
---
64

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. We need to revise the equation (00 as the following:
1 1mm + 1
M2
1m2 1)²M
E ||xx+1| 11 S (1
1812 + M) E |xp| |
(2mb
2n/ G2)
1/112 - 1
4
27mm2 + -212 M22
(132)
+ xp (A+
+ 2nd. + 58²2
(133)
4
Then we can have the following:
2 22M + +1)
Add
20
E
||xx|]]
SE+
112
m2
Moreover, the equation
67 also needed to revised as the accordingly:
Add
E I|x - xel12 < 3r/ (ME x|| |I] + G)2 +31/²
(M2 +1)
4 + 8M ||x 2 +8B²)
+ 61d
(M² + 1) Add
s 3 (2ME X ||] + +G² + 37²²
+ 8B² + 6rdd.
(134)
4
The remaining analysis should be the same as the proof of Theorem
Generalization of Theorem 8 under Relaxed Variance Assumption 7
In this proof, revise the proof of Theorem g if the Assumption 3 is replaced by Assumption 7
Theorem 24. Let Assumptions and 7 hold. Let p² denote the target distriluution of and 1/2*
ezp (O()) be the concentration number of 11 If we set the step size to be n Ō 0 ((ogriza)) after K
steps starting at the initial point Xo = O the output XK of the SGLDLP-L in (2) satisfies
Wa(p(xk))pp) (+
log (0(
(1)
log (1) VA
(135)
c
for some K satisfied
K = δ (
logs 1
We need to revise the 71
1222d
E ||x++1l??
[1] < (1 2mm2 + 2n M2)) E ||xx|| + 2nb + 2n +
+ (25M- + 28B2
4
(136)
E ||ax|1?] 2nd.
(137)
1/A2d
$ (1 27m2 + 4r7² 22) TE ||xx||]
+ 2np 22 +
+ 282 + [|axxl1]] 2rdd.
4
(138)
65

---

Published in Transactions on Machine Learning Research (04/2024)
P Generalization of Theorem 9 under Relaxed Variance Assumption 7
In this proof, we update Theorem if the Assumption 3 is replaced by Assumption 7
Theorem 25. Let Assumptions and hold. Let p" denote the target distribution of and 1/2²
exp (O()) be the concentration number of (13 If we set the step size to be 11 e-= ((ToRiv3) ))) after K
steps starting at the initial point Xo = O the output xx of the SGLDLP-L in (2 satisfies
Wa(p(xk),p")= (c+81/4
( log ())
log (2)
VA
(139)
e²
for some K satisfied
K K= Ō
1
log 2 )
11
The key revision is the same as the Theorem 8
66


Reviews:
[{"review_id": "75eZhV193A", "reviewer": "Reviewer_Xnd4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n - There is a large collection of results. \n\nWeaknesses \n - It is unclear to me that the applications are convincing motivation for the theory, given the exponential dependence on dimension are hidden. \n - Several mathematical details should be made precise, in particular with regards with spectral gaps. \n - The guarantees are given in a form where the achieved Wasserstein distance cannot be driven to zero in e.g. Theorem 1.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors studied a collection of both full precision and low precision versions of stochastic gradient based samplers, provided various convergence guarantees in terms of the 2-Wasserstein metric.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### On the Vacuous Nature of the Guarantees \n\nFirstly, I would like the authors to discuss the connection between the theory and the applications here. In particular, if the theoretical results rely on spectral gap constants $\\lambda^*, \\mu^*$, which are known to have exponential dependence on dimension, then we would expect the results to be consistently vacuous for large dimensional problems. For example, in Theorem 1, we would require $(\\mu^*)^{-2} = O( e^{O(d)} )$ number of steps to reach the convergence result. A quick Google search led me to find that ResNet-18 has about 11 million trainable parameters, which would require an astronomical number of steps to achieve this guarantee. In fact, even for 50 parameters, this value would be close to number of atoms in the universe at 10^50. \n\nGiven this enormous gap, I don't believe the application here is so relevant for the theory. Can the authors provide some discussion towards where this theory can be contributing towards if the dependence on dimension here is so critical? \n\n### On the Definition of Spectral Gaps\n\nTwo key quantities used in all of the results are $\\mu^*, \\lambda^*$, which the authors have called the \"spectral gap\" constants, and occasionally \"concentration parameter\", \"concentration number\", or \"concentration rate.\" I hope the author can first of all introduce a consistent name for these important constants. \n\nMore importantly, I believe it is absolutely critical to precisely define these constants, which is nowhere found within this article. In fact, it is not even found in the Zou et al. (2019) citation. Not only do these coefficients often end up having an exponential dependence on dimension, I believe the typical definition of spectral gap does not exist for the underdamped Langevin diffusion! Here's a quote from Villani's seminal work on Hypocoercivity: \n\n\"In many fields of applied mathematics, one is led to study dissipative evolution equations involving (i) a degenerate dissipative operator, and (ii) a conservative operator presenting certain symmetry properties, such that the combination of both operators implies convergence to a uniquely determined equilibrium state. Typically, the dissipative part is not coercive, in the sense that **it does not admit a spectral gap**; instead, it may possess a huge kernel, which is not stable under the action of the conservative part.\"\n\nInstead, what I believe the authors are referring to is an exponential contraction rate of a Lyapunov function, which implies an exponential convergence in terms of the Wasserstein distance. I believe this is a **particularly important detail**, and it should not be swept under the rug. So here, I request the authors make the definitions precise, use a consistent naming convention, and provide a related discussion to the vacuous nature on dimension. \n\n### Wasserstein Distance is Non-Vanishing \n\nI found the statement in Theorem 1 somewhat peculiar, where the guarantee is stated to reach the goal of \n\n$$ \\mathcal{W}_2 \\leq \\tilde O \\left( \\epsilon + \\tilde A \\sqrt{ \\log \\frac{1}{\\epsilon} } \\right) . $$\n\nHowever, this expression on the right hand side when treated as a function of $\\epsilon$, cannot reach zero ($\\log \\frac{1}{\\epsilon}$ increases as we decreases $\\epsilon$). In my opinion, this is strange, because the point of a convergence guarantee is that we should be able to minimize the error due to our sampler being an approximation, so we should be able to arbitrarily improve our sample quality at the cost of additional computational power. \n\nThis also implies the stated result in Table 1 is misleading, as additional dependence on $\\sigma$ is hidden, which cannot be driven to zero, unlike $\\Delta$ as a quantization error. I believe this should be fixed in order for a correct representation of your results. \n\nOn a fundamental level, I am questioning whether or not Assumption 3 is the best assumption on stochastic gradients, which is likely the core reason that the authors are dealing with this issue. First of all, I don't think this is true for minibatch SGD with shifted quadratic loss, where the variance scales with $\\|x\\|^2$. But that aside, I believe it's fair to assume that the stochastic gradient is unbiased, e.g. $\\mathbb{E} \\nabla \\tilde U = \\mathbb{E} \\nabla U$. In which case, we would have that the discretization SGLD (or the underdamped version) will converge to the **unbiased** Langevin dynamics as the step size $\\eta\\to 0$. This heuristically implies that the sampler should be able to approximate the Langevin diffusion arbitrarily well, and hence $\\mathcal{W}_2$ should be driven to zero with a decreased step size. \n\nCan the authors incorporate this condition into their proof, so that we can achieve a result that actually drives the Wasserstein distance to zero? I understand this may not be easy to do, if that's the case, can the authors instead provide a discussion on which part of the proof is difficult to adapt? I believe this is a rather unfortunate set of assumptions and results passed down, and should be fixed at some point.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fYReiEk8ly", "reviewer": "Reviewer_arQG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe authors asymptotic convergence guarantees for all the methods, that allows to compare to each other. \n\nThe experimental setting is rather strong, as they apply their methods on simple Neural Networks. \n \n### Weaknesses\n\n- The problem formulation is not clear. The notation is not clear. See the **requested changes** section for specifics. \n- It is hard to follow the storyline of the paper, without having the very specific background on low-precision sampling schemes. \n- There is a line of work on federated sampling. In these algorithms, compression of the gradients and the iterates plays a crucial role, as communication complexity is the bottleneck. The suggested algorithms SGLDLP-(P,F), are very similar to these methods and the comparison with these methods should be made clearly. See Bibliography. \n- In addition, in optimization, direct compression of the gradient and/or the iterate are by far not the most efficient methods in terms of communication(quantization) and iteration complexities. There are methods based on Markov compressors /momentum variance reduction etc. that are much faster and achieve convergence without quantization neighborhood $\\Delta$.\n- Table 1 is not informative. Using quantization as the compression mechanism, one can save only a fixed portion the memory. That means the memory only multiples by a constant. Thus, if the LP sampling algorithms achieve the same **asymptotic** complexity guarantees as the FP methods, it does not necessarily mean that they improve on them. In order for this comparison be meaningful, the complexities need to be explicit. \n- Furthermore the Wasserstein error for all the low-precision methods, depend polynomially on the inverse precision error $\\epsilon$, which can be large if the precision is low. This also raises questions about the theoretical efficiency of the methods. \n- In addition to the previous point, the use of these methods can justified only if they are compared to the non-compressed LMC,HLMC etc. Again, compressing the gradients, one loses in the accuracy and/or iteration complexity. None of the plots show this comparison of the algorithms.\n- The intuition of both Algorithm 1 and 2 is not presented. There is no explanation on why the methods are designed that way.\n\n\n**Bibliography**\n- M. Vono, V. Plassier, A. Durmus, A. Dieuleveut, and E. Moulines. QLSD: Quantised Langevin Stochastic Dynamics for Bayesian Federated Learning . 2022\n- W. Deng, Y.-A. Ma, Z. Song, Q. Zhang, and G. Lin. On convergence of federated averaging langevin dynamics. arXiv preprint arXiv:2112.05120, 2021.\n- L. Sun, A. Salim, and P. Richtárik. Federated learning with a sampling algorithm under isoperimetry, 2022. URL https://arxiv.org/abs/2206.00920.\n- Karagulyan, Avetik, and Peter Richtárik. \"ELF: Federated Langevin Algorithms with Primal, Dual and Bidirectional Compression.\" _arXiv preprint arXiv:2303.04622_ (2023).\n- MARINA: Faster non-convex distributed learning with compression. E Gorbunov, KP Burlachenko, Z Li, P Richtárik. *International Conference on Machine Learning, 3788-3798*\n- DASHA: Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization. A Tyurin, P Richtárik. *In International Conference on Learning Representations. 2023. (ICLR 2023)*", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies low-precision sampling algorithms, based on HMC with a stochastic gradient estimator. Theoretical asymptotic convergence guarantees in Wasserstein distance are provided. The complexity of the methods are obtained for a variety of methods. Comparison is performed also experimentally.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In (1), the function $\\tilde{U}$ and the sequence $\\xi_k$ are not introduced.\n- The quantization error $\\Delta$ is not defined. \n- The literature review needs  to be made more complete and the proposed methods need to be put in perspective with the existing work on federated learning and federated sampling. \n- The mathematical notation should be better introduced. \n- The comparison of the methods does not reflect the theory and is not thus informative. In addition, there are no plots comparing with the \"regular\" sampling algorithms without quantization. \n- For the rest, please refer to the weaknesses section, above.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kkuGyxOjhM", "reviewer": "Reviewer_59sv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In terms of strengths, the study of low-precision sampling algorithms is of general interest because low-precision is an important factor for training machine learning models when saving cost. It is nice to see that the authors are able to go through the analyses and achieve theoretical guarantees for SGHMC even with low-precision gradients. The proofs are solid and the theories applies to various settings. In addition, the paper also conducted extensive numerical experiments, which are convincing and provide evidence for the correctness of the theory results.\n\nIn terms of weaknesses, from my perspective the paper has significant space to improve in presentation because many places are unclear. See my comments in “requested changes”. In addition, technically the paper follows very closely to Zhang et al. (2022), especially the analysis related to low-precision gradients. More detailed comparisons between this paper and the current submission can be very helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied sampling with low-precision gradients, in particular it conducted a thorough analysis of Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) with low-precision and full-precision gradient accumulators for both strongly log-concave and non-log-concave distributions. The results suggested that low-precision SGHMC has priority over stochastic gradient Langevin dynamics (SGLD). Numerical experiments are also performed, which support the theoretical claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "From my perspective, there are quite a few places that the writing of the paper is not clear enough. I think the paper needs major revision before being accepted to TMLR.\n\n- The introduction does not have a high-level discussion about the technical contributions. I believe that for the TMLR audiences, some are familiar with theoretical analysis of sampling algorithms and some are familiar with low-precision algorithms, but few are familiar with applying low-precision gradients to sampling algorithms. It will be very helpful if the authors can highlight how the analysis of sampling algorithms can still go through with low-precision gradients. It will also be good if the authors can highlight the technical contributions on this compared to Zhang et al. (2022) - since this paper is the first one that analyzed low-precision sampling algorithms, does the current paper mostly follow Zhang et al. (2022), or it has novelties when analyzing SGHMC? In addition, is it possible to put the result of Zhang et al. (2022) in the table for a more direct comparison?\n\n- The settings of the problem can be better explained in many places. \n\n- - In the table, it will be very helpful if the authors can add a column titled “Settings”, and briefly explain which settings these theorems apply to. Apparently, the results are written in different parameters, and it is worth highlighting the specific settings they concern.\n\n- - I found the definitions of mu* and lambda* not clear enough. For mu*, Theorem 1 mentions it as the spectral gap of the underdamped Langevin dynamics and points it to Zou et al. (2019). It will be much better if this can be written down explicitly so that it is self-contained for readers to check. For lambda*, the caption of the table mentions is as the spectral gap of the overdamped Langevin dynamics, whereas Theorem 7 mentions it as the concentration number of (13). Do they share the same definition here?\n\n- - The definition of “low-precision” can also be better explained. In the table it is denoted by a parameter Delta - quantization error, but which type of quantization error does it refer to? There are deterministic rounding, stochastic rounding, and variance correction rounding. It would be helpful to explain in the main body which rounding methods can be applied in the proposed theorems.\n\n- It would be helpful to explain the relationship between the proofs of different theorems. Currently, Appendix D has 9 subsections going through the proofs of Theorem 1 to Theorem 9. The section is very long, but from reading the proofs share some similarities. It would be very helpful if the authors can explain at the beginning of the subsections the similarity and difference between these proofs.\n\n- In practice, if we only have a low-precision computer say with 8-bit digit numbers, how to do the stochastic rounding? I can imagine that for deterministic rounding to the nearest neighbor, the last bit after precision point may be stored so that if it’s .1, it is rounded to the integer right above, and if it’s .0 it is rounded to the current integer, i.e., simply omit the digits after the precision point. But how in practice can we make an unbiased random variable with low-precision?\n\n- I’m confused about Page 5 and 6 that use log(x)<=x^{1/e} and obtain subsequent bounds with powers expressed by e. Isn’t it the case that log(x)<=x^c for any constant c>0 in asymptotic bounds?", "broader_impact_concerns": "From my perspective, this paper does not have broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies low-precision sampling algorithms, focusing on stochastic gradient Hamiltonian Monte Carlo (SGHMC) with both low-precision and full-precision gradient accumulators. It provides theoretical convergence guarantees of these algorithms in the Wasserstein distance for both strongly log-concave and non-log-concave distributions. The numerical experiments show that low-precision SGHMC can outperform stochastic gradient Langevin dynamics (SGLD) in certain scenarios.

Reviewers expressed concerns about the clear picture of the paper, and suggest adding the definitions of lambda* and mu*, explaining that the Wasserstein distance bound is non-vanishing, and spectral gaps can be exponential. I agree with reviewers that the limitation of the results shall be clearly explained. After the authors modified accordingly, reviewers have agreed to accept the paper. I suggest acceptance.
Decision: Accept (poster)