# Stochastic Gradient Langevin Dynamics Based on Quantized Optimization

Jinwuk Seok
Future Computing Research Division, Artificial Intelligence Research Lab
ETRI
Daejeon, South KOREA, 34129
<EMAIL_ADDRESS>
&Changsik Cho
Future Computing Research Division, Artificial Intelligence Research Lab
ETRI
Daejeon, South KOREA, 34129
<EMAIL_ADDRESS>

###### Abstract

Stochastic learning dynamics based on Langevin or Levy stochastic differential
equations (SDEs) in deep neural networks control the variance of noise by
varying the size of the mini-batch or directly those of injecting noise. Since
the noise variance affects the approximation performance, the design of the
additive noise is significant in SDE-based learning and practical
implementation. In this paper, we propose an alternative stochastic descent
learning equation based on quantized optimization for non-convex objective
functions, adopting a stochastic analysis perspective. The proposed method
employs a quantized optimization approach that utilizes Langevin SDE dynamics,
allowing for controllable noise with an identical distribution without the
need for additive noise or adjusting the mini-batch size. Numerical
experiments demonstrate the effectiveness of the proposed algorithm on vanilla
convolution neural network(CNN) models and the ResNet-50 architecture across
various data sets. Furthermore, we provide a simple PyTorch implementation of
the proposed algorithm.

##  1 Introduction

Stochastic analysis for a learning equation based on stochastic gradient
descent (SGD) with a finite or an infinitesimal learning rate has been an
essential research topic to improve machine learning performance.
Particularly, the linear scaling rule(LSR) for SGD discovered by Krizhevsky
[2014], Chaudhari and Soatto [2018] and Goyal et al. [2018] independently
provides an essential guide to select or control the learning rate
corresponding to the size of the mini-batch. More crucially, it gives a
fundamental framework of stochastic analysis for the learning equation in
current deep neural networks(DNN). However, the early analysis of SDE-based
SGD encountered counterexamples, as demonstrated by Hoffer et al. [2017],
Shallue et al. [2018], Zhang et al. [2019]. Those works claim that the SGD
with a momentum term or an appropriate learning rate represents superior
performance to the SGD with a varying size mini-batch (Mandt et al. [2017],
Kidambi et al. [2018], Liu and Belkin [2020] ), even though the noise term
gives improved classification performance. As related research progresses,
recent studies reached the following consensus: for an objective function
being close to a standard convex, the SGD with mini-batch represents better
performance, while for an objective function being a non-convex or curvature
dominated, the SGD with momentum is better (Ma et al. [2018], Zhang et al.
[2019], Smith et al. [2019] and Smith et al. [2020]).

The other research topic of the stochastic analysis for SGD is whether or not
the induced SGD noise is Gaussian. Simsekli et al. [2019], Nguyen et al.
[2019] suggested that SGD noise is heavy-tailed distribution. This argument
means that if SGD noise is not Gaussian, we should analyze SGD as a Levy
process-based SDE instead of the standard SDE frame. For these claims, Wu et
al. [2020], Cheng et al. [2020b] and Li et al. [2022] revealed that the third
or higher order moments in SGD noise have minimal effect on accuracy
performance, while the second moment has a significant impact. In other words,
the standard SDE is still valid for the stochastic analysis of SGD noise in
the learning equation because the second moment of noise is the core component
of the standard SDE. As the recent researches substantiate the validation of
the stochastic analysis for SGD noise based on the standard SDE, Li et al.
[2019], Granziol et al. [2022], Malladi et al. [2022], Kalil Lauand and Meyn
[2022] and Li et al. [2022] reinterpreted the conventional algorithm based on
the standard SDE. Moreover, with the advent of novel algorithms and
comprehensive analyses in noisy SGD research (e.g., the works of Fonseca and
Saporito [2022], Masiha et al. [2022] and Altschuler and Talwar [2022]),
standard SDE-based noisy SGD algorithm is gaining widespread popularity.

Another research is stochastic gradient Langevin dynamics(SGLD), which injects
an isotropic noise, such as the Wiener process, into SGD (Welling and Teh
[2011], Brosse et al. [2018], Dalalyan and Karagulyan [2019], Cheng et al.
[2020a] and Zhang et al. [2022]). Unlike the noise derived from LSR, the noise
introduced by SGLD, which originates from Markov Chain Monte Carlo, consists
of independent and identically distributed (I.I.D.) components. As a result,
we can readily apply this noise to a conventional learning algorithm to
enhance its performance by robustness to non-convex optimization((Raginsky et
al. [2017], Xu et al. [2018], Mou et al. [2018] and Wang et al. [2021]).

However, LSR-based SGD and SGLD require additional processes such as warm-
up(Goyal et al. [2018]), extra computation according to stochastic variance
amplified gradient(SVAG)(Li et al. [2021] and Malladi et al. [2022]), or an
identical random number generator for SGLD. Furthermore, with the advancement
of research on distribution/federated learning, there is growing opposition to
increasing the size of mini-batches due to practical considerations in
optimization techniques. Lin et al. [2020] argued that in a distributed system
with a heterogeneous hardware environment, including small computational
devices, we could not expect a model learned using generalized large-batch SGD
to be suitable. Therefore, they advocate for using small-sized batch SGD in
such environments.

This paper introduces an alternative learning algorithm based on quantized
optimization for Stochastic Gradient Langevin Dynamics (SGLD), to address the
practical issues related to LSR-based SGD and SGLD. The proposed methodology
makes the following contributions.

  1. 1.

We present the learning equation based on standard SDE, which utilizes an
independent identical distributed noise without additional noise. The proposed
algorithm is based on the quantized optimization theory, incorporating the
white noise hypothesis (WHN) as suggested by Zamir and Feder [1996], Benedetto
et al. [2004], Gray and Neuhoff [2006] and Jiménez et al. [2007]. The WHN
posits that the quantization error follows an independent and identically
distributed (I.I.D.) white noise under regular conditions with sufficiently
large sample data. While the primary goal of quantization is to reduce
computational burden by simplifying data processing in conventional artificial
intelligence and another signal engineering(Seide et al. [2014], De Sa et al.
[2015], Han et al. [2015], Wen et al. [2016], Jung et al. [2019] and Li and Li
[2019]), in our work, quantization serves as the core technology for enhancing
optimization performance during the learning process. Additionally, the
quantization error effectively incorporates the various noise generated by the
algorithm and establishes it as additive white noise according to the white
noise hypothesis (WNH), thereby facilitating the SDE analysis for
optimization.

  2. 2.

By defining the quantization resolution function based on time and other
parameters, we propose an algorithm that computes the quantization level.
Controlling the noise variance induced by the quantization error is essential
to apply the quantization error to an optimizer effectively. While the white
noise hypothesis (WNH) allows us to treat the quantization error as I.I.D.
white noise, it alone does not guarantee optimal results if the uncontrolled
variance exists. Thereby, learning based on SGLD becomes feasible without a
random number generator required by SGLD or MCMC. Furthermore, similar to
increasing the mini-batch size in LSR-based SGD, we can develop a scheduler
using controlled quantization resolution for optimization.

  3. 3.

The proposed optimization algorithm demonstrates robust optimization
characteristics for non-convex objective functions. The quantized optimization
algorithm outperforms MCMC-based optimization methods in combinatorial
optimization problems, such as simulated and quantum annealing. Although
further empirical evidence is needed, this result indicates that quantized
optimization is a viable approach for non-convex optimization problems. We
analyze the proposed algorithm’s weak and local convergence to substantiate
this claim.

##  2 Preliminaries and Overview

We set the following definitions and assumptions of quantization to describe
the proposed analysis. Moreover, we provide a detailed notation for the
equations discussed in section 2, which is included in the supplementary
material.

###  2.1 Standard Assumptions for Stochastic Analysis

We establish the objective function in the paper, such as
$f:\mathbf{R}^{d}\rightarrow\mathbf{R},\;f\in C^{2}$, and define the
optimization problem for a given parameter(e.g., weight vectors in DNN)
$\boldsymbol{x}\in\mathbf{R}^{d}$ such that

$\min_{\boldsymbol{x}\in\mathcal{D}\subseteq\mathbf{R}^{d}}f(\boldsymbol{x})=\frac{1}{B}\sum_{k=1}^{B}\bar{f}_{k}(\boldsymbol{x}),\quad\bar{f}_{k}:\mathbf{R}^{d}\rightarrow\mathbf{R}$
(1)

, where $\mathcal{D}\subseteq\mathbf{R}^{d}$ is a domain of $f$, $\bar{f}_{k}$
denotes a loss function in a mini-batch. If $\mathcal{D}=\mathbf{R}^{d}$, the
optimization problem denoted by (1) is a strong global optimization problem.
However, if there exist a sequence
$\\{\bar{\boldsymbol{x}}_{k}\\}_{k\in\mathbf{Z}^{+}}$ such that
$\nabla_{\boldsymbol{x}}f(\bar{\boldsymbol{x}}_{k})=0$ for all
$\boldsymbol{x}_{k}\in\mathcal{D}$ where $\mathcal{D}\subset\mathbf{R}^{d}$,
then we refer to (1) as a weak global optimization. From a practical
perspective, the distinction between strong and weak global optimization is
meaningless. Therefore, in this paper, we use the term ’global optimization’
to encompass both concepts without differentiation. We establish the following
assumptions for the objective function $f$:

######  Assumption 1.

For $\boldsymbol{x}_{t}\in\mathcal{D}\subseteq
B^{o}(\boldsymbol{x}^{*},\rho)$, there exists a positive value $L_{0}$ with
respect to $f$ such that

$|f(\boldsymbol{x}_{t})-f(\boldsymbol{x}^{*})|\leq
L_{0}\|\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\|,\quad\forall t>t_{0},$ (2)

where $B^{o}(\boldsymbol{x}^{*},\rho)$ denotes an open ball
$B^{o}(\boldsymbol{x}^{*},\rho)=\\{\boldsymbol{x}|\|\boldsymbol{x}-\boldsymbol{x}^{*}\|<\rho\\}$
for all $\rho\in\mathbf{R}^{++}$, and $\boldsymbol{x}^{*}\in\mathbf{R}^{d}$
denotes the globally optimal point.

Furthermore, holding $f\in C^{2}$ and
$\boldsymbol{x}_{t}\in\mathcal{D}\subseteq B^{o}(\boldsymbol{x}^{*},\rho)$, we
can determine the Lipschitz constants $L_{1},L_{2}$ for the first-order and
the second-order derivation of $f$ respectively, such that

$\|\nabla_{\boldsymbol{x}}f(\boldsymbol{x}_{t})-\nabla_{\boldsymbol{x}}f(\boldsymbol{x}^{*})\|\leq
L_{1}\|\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\|,\;\;\|H_{\boldsymbol{x}}f(\boldsymbol{x}_{t})-H_{\boldsymbol{x}}f(\boldsymbol{x}^{*})\|_{\mathbf{R}^{d\times
d}}\leq L_{2}\|\boldsymbol{x}_{t}-\boldsymbol{x}^{*}\|,\quad\forall t>t_{0},$
(3)

, where $H_{\boldsymbol{x}}f\in\mathbf{R}^{d\times d}$ is the Hessian of $f$.
$\|\boldsymbol{A}\|_{\mathbf{R}^{m\times m}}$ denotes a matrix norm defined
as:

######  Definition 1.

For $\boldsymbol{A}\in\mathbf{R}^{m\times m},m\in\mathbf{N}$, we define a
metric for a matrix $A$ as follows:

$\left(\boldsymbol{A}\right)_{\mathbf{R}^{m\times
m}}\triangleq\langle\boldsymbol{v},\boldsymbol{Av}\rangle,\quad\boldsymbol{v}\in\mathbf{R}^{m},\;\|\boldsymbol{v}\|=1.$
(4)

We define the matrix norm of $\boldsymbol{A}$, denoted as
$\|\boldsymbol{A}\|_{\mathbf{R}^{m\times m}}$, using the absolute value of the
metric in (4) such that $\|\boldsymbol{A}\|_{\mathbf{R}^{m\times
m}}\triangleq|(\boldsymbol{A})_{\mathbf{R}^{m\times m}}|$.

###  2.2 Definition of Quantization

Most of the works describing WNH define a quantization such that
$x^{Q}\triangleq\lfloor\frac{x}{\Delta}+\frac{1}{2}\rfloor\Delta$ for
$x\in\mathbf{R}$, where $\Delta\in\mathbf{Q}^{+}$ denotes a fixed valued
quantization parameter. We provide a more detailed definition of quantization
to explore the impact of the quantization error and the quantization
parameter.

######  Definition 2.

For $z\in\mathbf{R}$, we define the quantization of $z$ as follows:

$z^{Q}\triangleq\frac{1}{Q_{p}}\lfloor Q_{p}\cdot(z+0.5\cdot
Q_{p}^{-1})\rfloor=\frac{1}{Q_{p}}\left(Q_{p}\cdot
z+\varepsilon^{q}\right)=z+\varepsilon^{q}Q_{p}^{-1},\quad z^{Q}\in\mathbf{Q}$
(5)

, where $\lfloor z\rfloor\in\mathbf{Z}$ denotes the floor function such that
$\lfloor z\rfloor\leq z$ for all $z\in\mathbf{R}$, $Q_{p}\in\mathbf{Q}^{+}$
denotes the quantization parameter, and $\varepsilon^{q}\in\mathbf{R}$ is the
quantization error.

######  Definition 3.

We define the quantization parameter $Q_{p}\in\mathbf{Q}^{+}$ to be a monotone
increasing function $Q_{p}:\mathbf{R}^{++}\mapsto\mathbf{Z}^{+}$ such that

$Q_{p}(t)=\eta\cdot b^{\bar{p}(t)}$ (6)

, where $\eta\in\mathbf{Q}^{++}$ denotes the fixed constant parameter of the
quantization parameter, $b$ is the base, and
$\bar{p}:\mathbf{R}^{++}\mapsto\mathbf{Z}^{+}$ denotes the power function such
that $\bar{p}(t)\uparrow\infty\;\text{ as }\;t\rightarrow\infty$.

In definition 3, we establish the power function $\bar{p}(\cdot)$ as a
function only depending on the time parameter $t$. However, if required, we
can modify $\bar{p}(\cdot)$ to involve multiple parameters.

######  Assumption 2 (WNH from Jiménez et al. [2007]).

The quantization error $\varepsilon^{q}$ is uniformly distributed in
$\mathbf{R}[-Q_{p}^{-1}/2,Q_{p}^{-1}/2]$, and random variables
$\\{\varepsilon_{t}^{q}\\}_{k\in\mathbf{t}^{+}}$ are independent.

By Assumption 2 and the quantization parameter as a time-dependent function,
we can assume that a probability space induced by WNH as follows:

######  Assumption 3.

Consider a numerical sequence a numerical sequence
$\\{z_{t}^{Q}\\}_{t=0}^{\infty}$ where each
$z_{t}^{Q}\in\mathbf{R}^{+}\;\forall t>0$. Suppose that $z_{t}^{Q}$ is defined
on a dense topology space. According to WNH and Definition 3, the quantization
error $\varepsilon_{t}^{q}$ corresponding to $t>0$ is i.i.d. white noise
defined on the probability space
$(\Omega,\mathcal{F}_{t},\mathbb{P}_{\varepsilon^{q}})$.

As a next step, to analyze the properties of the stochastic process
$\\{z_{t}^{Q}\\}_{t=0}^{\infty}$, we calculate the mean and variance of the
quantization error as follows:

$\forall\varepsilon_{t}\in\mathbf{R},\quad\mathbb{E}_{\mathcal{F}_{t}}Q_{p}^{-1}(t)\varepsilon_{t}^{q}=0,\quad\mathbb{E}_{\mathcal{F}_{t}}Q_{p}^{-2}(t){\varepsilon^{q}}_{t}^{2}=Q_{p}^{-2}(t)\cdot\mathbb{E}_{\mathcal{F}_{t}}{\varepsilon^{q}}_{t}^{2}=1/12\cdot
Q_{p}^{-2}(t).$ (7)

By controlling the quantization step using the quantization parameter
$Q_{p}(t)$, as defined in (6) and (7), we can establish the variance of SDE
for the learning equations more conveniently.

For the verification of the SDE approximation to a discrete learning equation,
we establish the following definition.

######  Definition 4 (Order-1 Weak Approximation, Li et al. [2019] and Malladi
et al. [2022]).

Let $\\{\boldsymbol{X}_{t}:t\in\mathbf{[}0,T]\\}$ and
$\\{\boldsymbol{X}_{\tau}^{\lambda}\\}_{\tau=0}^{\lfloor T/\lambda\rfloor}$ be
families of continuous and discrete stochastic processes parameterized by
$\lambda$. We regard $\\{\boldsymbol{X}_{t}\\}$ and $\boldsymbol{X}_{\tau}$
are order-1 weak approximations of each other if for all test function $g$
with polynomial growth, there exists a constant $C>0$ independent of $\lambda$
such that

$\max_{\tau\in\mathbf{Z}[0,\lfloor
T/\lambda\rfloor]}|\mathbb{E}g(\boldsymbol{X}_{\tau})-\mathbb{E}g(\boldsymbol{X}_{\tau\lambda})|\leq
C_{o1}\lambda^{2}.$ (8)

We provide additional definitions required in Definition 4, such as the
polynomial growth of the test function in the supplementary material.

###  2.3 Brief Review of SGLD learning equation

In the early 1980s, Kirkpatrick et al. [1983] developed a simulated annealing
algorithm known as the first emerged global optimization algorithm as an
advanced MCMC-based stochastic optimizer. The acceptance probability for
$x_{t}\in\mathbf{R}^{d}$ in SA is a simplified version of the Gibbs
distribution such that

$\bar{p}(\boldsymbol{x}_{t})=\frac{1}{Z_{t}}\exp\left(-\frac{U(\boldsymbol{x}_{t})}{T(t)}\right),\quad
Z_{t}\triangleq\int_{\mathbf{R}^{d}}\exp\left(-\frac{U(\boldsymbol{x}_{t})}{T(t)}\right)d\boldsymbol{x}_{t}$
(9)

where $T(t)\in\mathbf{R}$ is a simulated temperature that controls the
fluctuation decreasing $T\downarrow 0$ as $t,\uparrow\infty$, for the optimal
point $\boldsymbol{x}^{*}\in\mathbf{R}^{d}$, The function,
$U(\boldsymbol{x}_{t}):\mathbf{R}^{d}\rightarrow\mathbf{R}$, is defined as
$U(\boldsymbol{x}_{t})\triangleq f(\boldsymbol{x}_{t})-f(\boldsymbol{x}^{*})$.
If we consider $\bar{p}(\boldsymbol{x}_{t})$ in (9) as a stationary solution
of a partial differential equation with respect to the time-dependent
probability $p(\boldsymbol{x}_{t};t)$, we can derive a following Fokker-Planck
equation whose solution is given by $\eqref{eq_08}$:

$\frac{\partial}{\partial
t}p(\boldsymbol{x}_{t};t)=\sum_{i=0}^{d-1}\frac{\partial}{\partial
x_{i}}\nabla
f(\boldsymbol{x}_{t})p(\boldsymbol{x}_{t};t)+T(t)\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}\frac{\partial}{\partial
x_{i}}\frac{\partial}{\partial
x_{j}}p(\boldsymbol{x}_{t};t),\boldsymbol{x}_{t}\in\mathbf{R}^{d}.$ (10)

Accordingly, we can obtain the corresponding SDE to (10) such that

$d\boldsymbol{X}_{t}=-\nabla
f(\boldsymbol{X}_{t})dt+\sqrt{2T(t)}d\boldsymbol{B}_{t},\quad
t\in\mathbf{R}^{+}$ (11)

, where $\boldsymbol{X}_{t}\in\mathbf{R}^{d}$ is a random variable
corresponding to $\boldsymbol{x}_{t}$ in $\eqref{eq_07}$, and
$\boldsymbol{B}_{t}\in\mathbf{R}^{d}$ is a vector-valued standard Brownian
motion process(Gardiner [1985]). To approximate the Langevin diffusion
represented as $\eqref{eq_08}$, we can obtain the following difference
equation by the Euler-Maruyama scheme:

$\boldsymbol{X}_{\tau+1}=\boldsymbol{X}_{\tau}-\lambda\nabla
f(\boldsymbol{X}_{\tau})+\sqrt{2T(\tau)}\boldsymbol{\epsilon}_{\tau},\quad\tau\in\mathbf{Z}^{+}$
(12)

, where $\boldsymbol{\epsilon}_{\tau}\in\mathbf{R}^{d}$ is a vector valued
standard Gaussian noise such as
$\boldsymbol{\epsilon}_{\tau}\sim\mathcal{(}0,\boldsymbol{I}\in\mathbf{R}^{d\times
d})$, and $\lambda\in\mathbf{R}^{+}$ is a step-size or a learning rate.

##  3 Related Work

Applications of the SDE Approximation. As mentioned in the introduction, the
SDE approximation based on the SGD with LSR is one of the major approaches. Li
et al. [2019] developed the mathematical foundations of the stochastic
modified equations (SME) framework for analyzing the dynamics of stochastic
gradient algorithms. Granziol et al. [2022] studied the effect of mini-
batching on the loss landscape of deep neural networks using spiked, field-
dependent random matrix theory. Malladi et al. [2022] applied the SDE based on
LSR theory to the represented learning algorithms such as ADAM(ADAptive Moment
estimation: Kingma and Ba [2015]), RMSProp, and Nestrov(Su et al. [2014]
learning equations. Li et al. [2022] provided an effective mixing method for
SDE with Normalization and Weight Decay, and Kalil Lauand and Meyn [2022]
applied the quasi-SDE approximation to gradient-free optimization problems.

SGLD induced by MCMC. Another significant approach of the SDE approximation is
SGLD. SGLD is based on the theoretical foundation of MCMC methods and is
primarily used as a stochastic optimizer for non-convex problems in Deep
Neural Networks (DNNs). Raginsky et al. [2017] provided a non-asymptotic
analysis of non-convex learning problems, giving finite-time guarantees for
SGLD. Xu et al. [2018] introduced a unified framework for analyzing the global
convergence of SGLD in non-convex optimization by comparing the classification
performance of standard SGD, SGLD, and SVRG-LD. Mou et al. [2018] presented
the bounds of SGLD for non-convex learning, and Wang et al. [2021] analyzed
the generalization capability of SGLD using Gaussian channel properties.

Quantization and Optimization. Since quantization is not a prominent
optimization scheme, we rarely find previous similar research. One of the
similar optimization techniques is Generating Set Search (GSS), an intuitive
direct search or pattern search method (Hooke and Jeeves [1961] and Lewis and
Torczon [1996]). GSS controls the grid size, which resembles the quantization
parameter, and finds the global minima with an intuitively defined search
direction. Much of the research on quantization in artificial intelligence
focuses on reducing inference computations on limited hardware platforms(Han
et al. [2016], Li and Li [2019], Bai et al. [2022], Frantar and Alistarh
[2022] and Kuzmin et al. [2022]).

##  4 Learning Equation based on Quantized Optimization

(a) Small valued $Q_{p}(\tau)$

(b) Large valued $Q_{p}(\tau)$

(c) Search vectors

Figure 1: The concept diagram of the proposed quantization: (a) In the early
stage of learning, with a small value of $Q_{p}(\tau)$, the search points
generated by quantization are widely spaced, indicating a significant
quantization error or Brownian motion process affecting the learning process.
(b) As the learning process progresses, the quantization parameter
$Q_{p}(\tau)$ increases, resulting in smaller grid sizes. This process
resembles an annealing-type stochastic optimization. (c) When considering a
general search vector $\alpha,h(\boldsymbol{X}_{\tau})$, quantization
introduces an additional search vector, as shown.

Consider that the learning equation given by:

$\boldsymbol{X}_{\tau+1}=\boldsymbol{X}_{\tau}+\lambda
h(\boldsymbol{X}_{\tau})$ (13)

, where $h:\mathbf{R}^{d}\rightarrow\mathbf{R}^{d}$ represents the search
direction.

Main Idea of the Proposed Quantized Optimization The learning equation,
represented as equation $\eqref{ch04-eq01}$, searches for a local minimum
along a line defined by a directional vector or a conjugate direction when the
equation incorporates momentum. In the proposed quantized optimization, we
create a grid on the objective function’s domain and sample a point near the
feasible point generated by the learning equation. The grid size is adjustable
through the quantization parameter. By regarding the quantization error as a
Brownian motion following WNH, we can reduce the variance of the quantization
error by increasing the quantization parameter’s size. This adjustment is
equivalent to the dynamics of Langevin SDE in stochastic approximation. From
an optimization perspective, stochastic gradient-based learning can be
considered stochastic sampling.

###  4.1 Fundamental Learning Equation based on Quantization

Applying the quantization defined as $\eqref{define_eq01}$ to the learning
equation $\eqref{ch04-eq01}$, we can obtain the quantization-based learning
equation presented in the following theorem.

######  Theorem 4.1 (Quantized Stochastic Langevin Dynamics(QSLD)).

Suppose an initial parameter is quantized as $\boldsymbol{X}_{0}^{Q}$. To
ensure the consistency of quantization for all $\tau$, we establish the
quantization-based learning equation with the search direction
$h(\boldsymbol{X}_{\tau})$ as follows:

$\boldsymbol{X}_{\tau+1}^{Q}=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left[Q_{p}(\tau)\cdot\lambda
h(\boldsymbol{X}_{\tau})\right]^{Q}$ (14)

, where $\tau\in\mathbf{Z}^{+}$ is a discrete time index. According to the
definition of quantization, We can derived the discrete Langevine equation of
$\eqref{ch04-eq02}$ such that

$\boldsymbol{X}_{\tau+1}^{Q}=\boldsymbol{X}_{\tau}^{Q}+\lambda\,h(\boldsymbol{X}_{\tau})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}^{q}.$
(15)

, where $\boldsymbol{\epsilon}_{\tau}^{q}\in\mathbf{R}^{d}$ denotes the
quantization error, which is a Brownian motion process evaluated as
$\boldsymbol{\epsilon}_{\tau}\triangleq\sqrt{\lambda}\int_{\tau}^{\tau+1}d\boldsymbol{B}_{t}$
according to WNH.

Sketch of proof By employing Definition 2 and quantization equation
$\eqref{define_eq01}$, we can easily derive Theorem $\eqref{theorem_01}$ by
quantizing the learning equation $\eqref{ch04-eq01}$.

As demonstrated in $\eqref{ch04-eq02}$ and $\eqref{ch04-eq03}$, the
quantization process automatically incorporates a vector-valued Brownian
motion process. When the search direction $h(\boldsymbol{X}{\tau})$ is
$-\nabla f(\boldsymbol{X}{\tau})$ such that

$\boldsymbol{X}_{\tau+1}^{Q}=\boldsymbol{X}_{\tau}^{Q}-\lambda\nabla
f(\boldsymbol{X}_{\tau})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}^{q}.$
(16)

, we name the equation $\eqref{ch04-eq04}$ as a quantized stochastic gradient
Langevin dynamics (QSGLD). Furthermore, equation $\eqref{ch04-eq03}$ and
$\eqref{ch04-eq04}$ of the quantization-based Langevin equation reveals that
the squared variance of the Brownian motion process is equal to the
quantization parameter. Thus, by adjusting the quantization parameter in
accordance with the discrete-time index $\tau$, we can enhance the
optimization performance. In the following section, we describe the properties
of the quantization parameter and the variance by analyzing weak convergence.

Appliance to Other Learning Algorithms In QSLD, the search direction is not
fixed as the opposite direction of the gradient vector, allowing for the
application of various learning methods such as ADAM (Kingma and Ba [2015])
and alternative versions of ADAM such as ADAMW(Loshchilov and Hutter [2019]),
NADAM(Dozat [2016]), and RADAM(Liu et al. [2020]).

Avoid Early Paralysis of the proposed algorithm The initial gradient tends to
vanish if the initial search point is far from optimal, especially for
objective functions in deep neural networks that utilize entropy-based loss
functions such as the Kullback-Leibler divergence (KL-Divergence). The small
gradient in the early stage becomes zero after the quantization process,
potentially causing the deep neural network (DNN) to fall into a state of
paralysis, as illustrated below: Assume that $\max\|\lambda
h\|<0.5\,Q_{p}^{-1}(\tau)-\delta$ for $\tau<\tau_{0}$, where $\delta$ denotes
a positive value such that $\delta Q_{p}^{-1}<1$, and $\tau_{0}$ denotes a
small positive integer. Then, we have

$1/Q_{p}\cdot\|\lfloor Q_{p}(\lambda h+0.5\,Q_{p}^{-1})\rfloor\|\leq
1/Q_{p}\cdot\lfloor Q_{p}(\max\|\lambda
h\|+0.5\,Q_{p}^{-1})\rfloor=1/Q_{p}\cdot\lfloor 1-\delta Q_{p}^{-1}\rfloor=0.$
(17)

To prevent the paralysis depicted in $\eqref{avoid-eq01}$, a straightforward
solution is to re-establish the quantized search direction by incorporating a
compensation function $r(\tau)=\lfloor r(\tau)\rfloor$ into $h$, as shown:

$\displaystyle Q_{p}^{-1}(\tau)\cdot\|\left[Q_{p}(\tau)(\lambda
h+r(\tau))\right]^{Q}\|_{\max\|\lambda h\|<0.5\,Q_{p}^{-1}(\tau)-\delta}$ (18)
$\displaystyle=Q_{p}^{-1}(\tau)\cdot\|\lfloor Q_{p}\cdot(\lambda
h+0.5\,Q_{p}^{-1}+r(\tau))\rfloor\|_{\max\|\lambda
h\|<0.5\,Q_{p}^{-1}(\tau)-\delta}$ $\displaystyle\leq
Q_{p}^{-1}(\tau)\cdot\|\lfloor Q_{p}\cdot(\lambda
h+0.5\,Q_{p}^{-1}\rfloor\|_{\max\|\lambda
h\|<0.5\,Q_{p}^{-1}(\tau)-\delta}+\|\lfloor Q_{p}r(\tau))\rfloor\|$
$\displaystyle\leq 0+Q_{p}^{-1}(\tau)\cdot\|\lfloor Q_{p}r(\tau)\rfloor\|.$

In equation $\eqref{avoid-eq02}$, the compensation function is responsible for
increasing the magnitude of the search direction during an initial finite
period. To address this, we propose the compensation function $r(\tau)$ given
by:

$r(\tau)=\left\lfloor\lambda\cdot\frac{\exp(-\varkappa(\tau-\tau_{0}))}{1+\exp(-\varkappa(\tau-\tau_{0}))}\cdot\frac{h(\boldsymbol{X}_{\tau})}{\|h(\boldsymbol{X}_{\tau})\|}\right\rfloor,\quad\tau_{0}\in\mathbf{Z}^{d}$
(19)

, $\varkappa>0$ is a determining parameter for the working period, and
$\tau_{0}$ represents the half-time of the compensation.

###  4.2 Convergence Property of QSGLD

Weak Convergence without Convex Assumption Before the weak convergence
analysis of QSGLD, we establish the following lemma for the approximated SDE.

######  Lemma 4.2.

The approximated Langevin SDE for QSGLD (15) derived by the Euler-Maruyama
method is as follows:

$d\boldsymbol{X}_{t}=-\nabla
f(\boldsymbol{X}_{t})dt+\sqrt{2}Q_{p}^{-1}(t)d\boldsymbol{B}_{t},\quad\forall
t>t_{0}.$ (20)

The approximation $\eqref{lemma01_eq01}$ satisfies the order-1 weak
approximation described in Definition 4.

Sketch of proof Li et al. [2019] introduced a rigorous analytical framework
for approximating stochastic difference equations with stochastic differential
equations (SDEs). Building upon this framework, Malladi et al. [2022] extended
the analysis for more general search directions. We leverage the
aforementioned framework to establish Lemma 4.2. We impose several bounded
assumptions described in the supplementary material to derive the moment of
the one-step difference in $\eqref{lemma01_eq01}$. Subsequently, by utilizing
the bound of the moment, we prove the order-1 weak approximation of QSGLD to
the Langevin SDE.

######  Theorem 4.3.

Consider the transition probability, denoted as $p(t_{0},x;t+\tau,x^{*})$,
from an arbitrary state ${x}_{t}$ to the optimal point $x^{*}$ after a time
interval $\tau$. Using the given notation, we define the stationary transition
probability such that $\pi(\bar{x}_{t},t;t+\tau,x^{*})\triangleq
p(\bar{x}_{t},t;t+\tau,x^{*})$. If the quantization parameter is bounded as
follows:

$\sup_{t\geq 0}Q_{p}=\frac{1}{C}\cdot{\log(t+2)},\quad C\in\mathbf{R}^{++},$
(21)

QSGLD represented as $\eqref{ch04-eq04}$ converges with distribution such that

$\overline{\lim_{\tau\rightarrow\infty}}\sup_{x_{t},x_{t+\tau}\in\mathbf{R}^{n}}\|\pi(t,\bar{x}_{t};t+\tau,x^{*})-p(t,x_{t};t+\tau,x^{*})\|\leq\tilde{C}\cdot\exp\left(-\sum_{k=0}^{\infty}\delta_{t+\tau}\right)$
(22)

where $\delta_{t}$ a positive valued function satisfying
$\sum_{k=0}^{\infty}\delta_{t}=\infty$, and $\tilde{C}$ denotes a positive
value.

Sketch of proof First, we define $\delta_{t}$ as the infimum of the transition
probability from time $t$ to $t+1$, given by
$\delta_{t}=\inf_{x,y\in\mathbf{R}^{d}}p(t,x;t+\tau,x^{*})$. Next, we analyze
the limit supremum of the difference between the stationary transition
probability and the transition probability expressed by the infimum
$\delta_{t}$. Then, according to the Girsanov theorem (Øksendal [2003] and
Klebaner [2012]), we calculate the Radon-Nykodym derivative of the probability
measure induced by the approximated Langevin SDE of QSGLD with respect to the
probability of a standard Gaussian. Using the obtained Radon-Nykodym
derivative, we derive a lower bound for $\delta_{t}$ and provide proof for the
theorem.

Local Convergence under Convex Assumption For local convergence analysis, we
suppose that the objective function around the optimal point is strictly
convex.

######  Assumption 4.

The Hessian of the objective function around the optimal point denoted as
$\nabla f(\boldsymbol{X}^{*})=0$ is non-singular and satisfies that
$\min\left(\frac{\partial^{2}f}{\partial x^{2}}\right)_{\mathbf{R}^{d\times
d}}\geq 0$. Thus, the minimum eigenvalue of the Hessian is positive or zero.

######  Theorem 4.4.

The proposed QSGLD converges an optimal point in order-1 weak approximation
under the assumption stated in Assumption 4.

Sketch of proof Intuitively, the proof of the theorem follows a similar
structure to the conventional proof of gradient descent under the convex
assumption. However, with the existence of the Brownian motion process, we
apply the stationary probability from Theorem 4.3 into the proof. Accordingly,
we prove the convergence not on the point-wise vector space, but on the
function space induced by a stationary expectation.

Algorithm 1 QSLD/QSGLD with the proposed quantization scheme

1:Initialization $\tau\leftarrow 0$ $\triangleright$ Set Initialize Discrete
Time Index

2:repeat

3: Compute $h(\boldsymbol{X}_{\tau})$ at $\tau$ $\triangleright$ Compute a
Search Direction Vector

4: Compute $Q_{p}(\tau)$, and $r(\tau)$ $\triangleright$ Compute Quantization
Parameter and $r(\tau)$

5: $h_{\tau}^{Q}\leftarrow\frac{1}{Q_{p}}[Q_{p}\cdot(-\lambda
h(\boldsymbol{X}_{\tau})+r(\tau))]$ $\triangleright$ Quantization of the
Search Direction Vector

6: $\boldsymbol{X}_{\tau}\leftarrow\boldsymbol{X}_{\tau}+h_{\tau}^{Q}$
$\triangleright$ General Updating Rule for Learning

7: $\tau\leftarrow\tau+1$ $\triangleright$ General Update Discrete Time Index

8:until Stopping criterion is met

##  5 Experimental Results

Table 1: Comparison of test performance among optimizers with a fixed learning rate 0.01. Evaluation is based on the Top-1 accuracy of the training and testing data. Data Set | FashionMNIST | CIFAR10 | CIFAR100
---|---|---|---
Model | CNN with 8-Lsyers | ResNet-50
Algorithms | Training | Testing | Training Error | Training | Testing | Training Error | Training | Testing | Training Error
QSGD | 97.10 | 91.59 | 0.085426 | 99.90 | 73.80 | 0.009253 | 99.04 | 37.77 | 0.030104
QADAM | 98.43 | 89.29 | 0.059952 | 99.99 | 85.09 | 0.000001 | 98.62 | 49.60 | 0.037855
SGD | 95.59 | 91.47 | 0.132747 | 99.99 | 63.31 | 0.001042 | 98.24 | 25.90 | 0.005478
ASGD | 95.60 | 91.42 | 0.130992 | 99.99 | 63.46 | 0.001166 | 98.36 | 26.43 | 0.004981
ADAM | 92.45 | 87.12 | 0.176379 | 99.75 | 82.08 | 0.012421 | 98.85 | 46.32 | 0.038741
ADAMW | 91.72 | 86.81 | 0.182867 | 99.57 | 82.20 | 0.012551 | 98.86 | 47.01 | 0.038002
NADAM | 96.25 | 87.55 | 0.140066 | 99.56 | 82.46 | 0.014377 | 98.62 | 48.56 | 0.037409
RADAM | 95.03 | 87.75 | 0.146404 | 99.65 | 82.26 | 0.010526 | 98.17 | 48.61 | 0.044193

###  5.1 Configuration of Experiments

From a practical point of view, as both the updated state
$\boldsymbol{X}_{\tau+1}$ and the current state $\boldsymbol{X}{\tau}$ are
quantized vectors, the quantization parameter should be a power of the base
defined in equation $\eqref{def_eq02}$. Although Theorem 4.3 provides an upper
bound for the quantization parameter as a real value, we constrain the
quantization parameter to be a rational number within a bounded range of real
values. Specifically, we set the quantization parameter $Q_{p}$ as follows:

$Q_{p}=\left\lfloor\frac{1}{C}\log(t_{e}+2)\right\rfloor$ (23)

, where $t_{e}$ represents a unit epoch defined as
$t_{e}=\lfloor\tau/B\rfloor$ when $N_{B}$ denotes a dataset’s total number of
mini-batches as per epoch. In the supplementary material, we provide detailed
explanations and methods for calculating and establishing the remaining hyper-
parameters.

###  5.2 Brief Information of Experiments

We conducted experiments to compare QSGLD with standard SGD and ASGD (Shamir
and Zhang [2013]). Additionally, we compared the performance of QSLD to the
proposed method with ADAM, ADAMW, NADAM, and RADAM in terms of convergence
speed and generalization. These results provide an empirical analysis and
demonstrate the effectiveness of the proposed algorithms. The network models
used are ResNet-50 and a small-sized CNN network with 3-layer blocks, of which
two former blocks are a bottle-neck network, and one block is a fully
connected network for classification. Data sets used for the experiments are
FashionMNIST(Xiao et al. [2017]), CIFAR-10, and CIFAR-100. We give detailed
information about the experiments, such as hyper-parameters of each algorithm,
in the supplementary material.

###  5.3 Empirical Analysis of the Proposed Algorithm

Test for FashionMNIST For the experiment, we employed a small-sized CNN to
evaluate the performance of the test algorithms. The FashionMNIST dataset
consists of black-and-white images that are similar to MNIST data. Figure 2
illustrates that SGD algorithms demonstrate superior generalization
performance on the test data, even though their convergence speed is slower
than ADAM-based algorithms. Table 1 shows that the proposed quantization
algorithms achieve a superior final accuracy error. Notably, the quantization
algorithm applied to ADAM algorithms surpasses the error bound and achieves
even lower accuracy error. As a result, the proposed quantization algorithm
demonstrates improved classification performance for test data.

Test for CIFAR-10 and CIFAR-100 For the CIFAR-10 and CIFAR-100 tests, we
utilized ResNet-50 as the model architecture. As shown in Table 1, when
classifying the CIFAR-10 dataset using ResNet-50, QSGLD outperformed SGD by 8%
in terms of test accuracy. As depicted in Figure 2, QSGLD exhibited
significant improvements in convergence speed and error reduction compared to
conventional SGD methods. On the other hand, Adam-Based QSLD showed a
performance advantage of approximately 3% for test accuracy for CIFAR-10
dataset. Similar trends were observed for the CIFAR-100 dataset. QSGLD
demonstrated a performance advantage of around 11% over conventional SGD
methods for test accuracy. In contrast, Adam-Based QSLD showed an improvement
of approximately 3.0% compared to Adam optimizers and 1.0% compared to NAdam
and RAdam.

##  6 Conclusion

(a) FashionMNIST via CNN

(b) CIFAR10 via ResNet50

(c) CIFAR100 via ResNet50

Figure 2: The error trends of test algorithms to dataset and neural models:
(a) Training error trends of the CNN model on FashionMNIST dataset.(b)
Training error trends of ResNet-50 on CIFAR-10 dataset. (c) Training error
trends of ResNet-50 on CIFAR-100 dataset.

We introduce two stochastic descent learning equations, QSLD and QSGLD, based
on quantized optimization. Empirical results demonstrate that the error trends
of the quantization-based stochastic learning equations exhibit stability
compared to other noise-injecting algorithms. We provide the proposed
algorithm’s weak and local convergence properties with the Langevin SDE
perspective. In our view, exploring the potential of quantization techniques
applied to the range of objective functions may offer limited performance
gains. Hence, future research will investigate the quantization technique in
the context of objective function domains. Furthermore, we have not conducted
an analysis of a more generalized version of the proposed method, QSLD,
despite the empirical results suggesting its satisfactory consistency.
Analyzing QSLD requires studying the properties of the general search
direction, which we reserve for future investigations.

##  7 Acknowledgement

This work was supported by Institute for Information and Communications
Technology Promotion(IITP) grant funded by the Korea government(MSIP) (2021-0-
00766, Development of Integrated Development Framework that supports Automatic
Neural Network Generation and Deployment optimized for Runtime Environment)

## References

## References

  * Altschuler and Talwar [2022] Jason Altschuler and Kunal Talwar.  Privacy of noisy stochastic gradient descent: More iterations without more privacy loss.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 3788–3800. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/18561617ca0b4ffa293166b3186e04b0-Paper-Conference.pdf.
  * Bai et al. [2022] Haoli Bai, Lu Hou, Lifeng Shang, Xin Jiang, Irwin King, and Michael R Lyu.  Towards efficient post-training quantization of pre-trained language models.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 1405–1418. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/096347b4efc264ae7f07742fea34af1f-Paper-Conference.pdf.
  * Benedetto et al. [2004] J.J. Benedetto, O. Yilmaz, and A.M. Powell.  Sigma-delta quantization and finite frames.  In _2004 IEEE International Conference on Acoustics, Speech, and Signal Processing_ , volume 3, pages iii–937, 2004.  doi: 10.1109/ICASSP.2004.1326700.
  * Brosse et al. [2018] Nicolas Brosse, Alain Durmus, and Eric Moulines.  The promises and pitfalls of stochastic gradient langevin dynamics.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/335cd1b90bfa4ee70b39d08a4ae0cf2d-Paper.pdf.
  * Chaudhari and Soatto [2018] Pratik Chaudhari and Stefano Soatto.  Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks.  In _2018 Information Theory and Applications Workshop, ITA 2018, SanDiego, CA, USA, February 11-16, 2018_ , pages 1–10. IEEE, 2018.  doi: 10.1109/ITA.2018.8503224.  URL https://doi.org/10.1109/ITA.2018.8503224.
  * Cheng et al. [2020a] Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan.  Stochastic gradient and langevin processes.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org, 2020a.
  * Cheng et al. [2020b] Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan.  Stochastic gradient and Langevin processes.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1810–1819. PMLR, 13–18 Jul 2020b.  URL https://proceedings.mlr.press/v119/cheng20e.html.
  * Dalalyan and Karagulyan [2019] 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–5311, 2019.  ISSN 0304-4149.  doi: https://doi.org/10.1016/j.spa.2019.02.016.  URL https://www.sciencedirect.com/science/article/pii/S0304414918304824.
  * De Sa et al. [2015] Christopher M De Sa, Ce Zhang, Kunle Olukotun, Christopher Ré, and Christopher Ré.  Taming the wild: A unified analysis of hogwild-style algorithms.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 2674–2682. NIPS, 2015.
  * Dozat [2016] Timothy Dozat.  Incorporating Nesterov Momentum into Adam.  In _Proceedings of the 4th International Conference on Learning Representations: Workshop Track_ , pages 1–4, 2016.
  * Fonseca and Saporito [2022] Yuri Fonseca and Yuri Saporito.  Statistical learning and inverse problems: A stochastic gradient approach.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 9591–9602. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/3e8b1835833ef809059efa74b9df6805-Paper-Conference.pdf.
  * Frantar and Alistarh [2022] Elias Frantar and Dan Alistarh.  Optimal brain compression: A framework for accurate post-training quantization and pruning.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 4475–4488. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/1caf09c9f4e6b0150b06a07e77f2710c-Paper-Conference.pdf.
  * Gardiner [1985] Crispin Gardiner.  _Handbook of Stochastic Methods : for Physics, Chemistry and the Natural Sciences_.  Springer, 1985.
  * Goyal et al. [2018] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour, 2018.  URL https://arxiv.org/abs/1706.02677.
  * Granziol et al. [2022] Diego Granziol, Stefan Zohren, and Stephen Roberts.  Learning rates as a function of batch size: A random matrix theory approach to neural network training.  _Journal of Machine Learning Research_ , 23(173):1–65, 2022.  URL http://jmlr.org/papers/v23/20-1258.html.
  * Gray and Neuhoff [2006] Robert. M. Gray and David L. Neuhoff.  Quantization.  _IEEE Transactions on Information Theory_ , 44(6):2325–2383, 2006.
  * Han et al. [2015] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems 28_ , pages 1135–1143. Curran Associates, Inc., 2015.
  * Han et al. [2016] Song Han, Huizi Mao, and William J. Dally.  Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding.  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.
  * Hoffer et al. [2017] Elad Hoffer, Itay Hubara, and Daniel Soudry.  Train longer, generalize better: Closing the generalization gap in large batch training of neural networks.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 1729–1739, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Hooke and Jeeves [1961] Robert Hooke and T. A. Jeeves.  Direct search” solution of numerical and statistical problems.  _J. ACM_ , 8(2):212–229, apr 1961.  ISSN 0004-5411.
  * Jiménez et al. [2007] David Jiménez, Long Wang, and Yang Wang.  White noise hypothesis for uniform quantization errors.  _SIAM J. Math. Analysis_ , 38(6):2042–2056, 2007.
  * Jung et al. [2019] Sangil Jung, Changyong Son, Seohyung Lee, JinWoo Son, Jae-Joon Han, Youngjun Kwak, Sung Ju Hwang, and Changkyu Choi.  Learning to quantize deep networks by optimizing quantization intervals with task loss.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pages 4350–4359, 2019.
  * Kalil Lauand and Meyn [2022] Caio Kalil Lauand and Sean Meyn.  Approaching quartic convergence rates for quasi-stochastic approximation with application to gradient-free optimization.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 15743–15756. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/6530274c68e81047e1f4a2ceb0b8c0ef-Paper-Conference.pdf.
  * Kidambi et al. [2018] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M. Kakade.  On the insufficiency of existing momentum schemes for stochastic optimization.  In _ITA_ , pages 1–9. IEEE, 2018.  ISBN 978-1-7281-0124-8.  URL http://dblp.uni-trier.de/db/conf/ita/ita2018.html#KidambiN0K18.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Kirkpatrick et al. [1983] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.  Optimization by simulated annealing.  _SCIENCE_ , 220(4598):671–680, 1983.
  * Klebaner [2012] Fima C. Klebaner.  _Introduction To Stochastic Calculus With Applications_.  Imperial College Press, 3rd edition, 2012.  ISBN 1848168322.
  * Krizhevsky [2014] Alex Krizhevsky.  One weird trick for parallelizing convolutional neural networks, 2014\.  URL https://arxiv.org/abs/1404.5997.
  * Kuzmin et al. [2022] Andrey Kuzmin, Mart van Baalen, Yuwei Ren, Markus Nagel, Jorn Peters, and Tijmen Blankevoort.  Fp8 quantization: The power of the exponent.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 14651–14662. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/5e07476b6bd2497e1fbd11b8f0b2de3c-Paper-Conference.pdf.
  * Lewis and Torczon [1996] Robert M. Lewis and Virginia Torczon.  Rank ordering and positive bases in pattern search algorithms.  _Technical Report 96-71_ , Dec. 1996.
  * Li et al. [2019] Qianxiao Li, Cheng Tai, and Weinan E.  Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations.  _Journal of Machine Learning Research_ , 20(40):1–47, 2019.  URL http://jmlr.org/papers/v20/17-526.html.
  * Li and Li [2019] Xiaoyun Li and Ping Li.  Generalization error analysis of quantized compressive learning.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 15124–15134. NIPS, 2019.
  * Li et al. [2021] Zhiyuan Li, Sadhika Malladi, and Sanjeev Arora.  On the validity of modeling sgd with stochastic differential equations (sdes).  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 12712–12725. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper_files/paper/2021/file/69f62956429865909921fa916d61c1f8-Paper.pdf.
  * Li et al. [2022] Zhiyuan Li, Tianhao Wang, and Dingli Yu.  Fast mixing of stochastic gradient descent with normalization and weight decay.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 9233–9248. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/3c215225324f9988858602dc92219615-Paper-Conference.pdf.
  * Lin et al. [2020] Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi.  Don’t use large mini-batches, use local sgd.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=B1eyO1BFPr.
  * Liu and Belkin [2020] Chaoyue Liu and Mikhail Belkin.  Accelerating sgd with momentum for over-parameterized learning.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=r1gixp4FPH.
  * Liu et al. [2020] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han.  On the variance of the adaptive learning rate and beyond.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rkgz2aEKDr.
  * Loshchilov and Hutter [2019] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Bkg6RiCqY7.
  * Ma et al. [2018] Siyuan Ma, Raef Bassily, and Mikhail Belkin.  The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3325–3334. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/ma18a.html.
  * Malladi et al. [2022] Sadhika Malladi, Kaifeng Lyu, Abhishek Panigrahi, and Sanjeev Arora.  On the sdes and scaling rules for adaptive gradient algorithms.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 7697–7711. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/32ac710102f0620d0f28d5d05a44fe08-Paper-Conference.pdf.
  * Mandt et al. [2017] Stephan Mandt, Matthew D. Hoffman, and David M. Blei.  Stochastic gradient descent as approximate bayesian inference.  _Journal of Machine Learning Research_ , 18(134):1–35, 2017.  URL http://jmlr.org/papers/v18/17-214.html.
  * Masiha et al. [2022] Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran.  Stochastic second-order methods improve best-known sample complexity of sgd for gradient-dominated functions.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 10862–10875. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/46323351ebc2afa42b30a6122815cb95-Paper-Conference.pdf.
  * Mou et al. [2018] Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng.  Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints.  In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, _Proceedings of the 31st Conference On Learning Theory_ , volume 75 of _Proceedings of Machine Learning Research_ , pages 605–638. PMLR, 06–09 Jul 2018.  URL https://proceedings.mlr.press/v75/mou18a.html.
  * Nguyen et al. [2019] Thanh Huy Nguyen, Umut Simsekli, Mert Gurbuzbalaban, and Gaël RICHARD.  First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/a97da629b098b75c294dffdc3e463904-Paper.pdf.
  * Raginsky et al. [2017] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky.  Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.  In Satyen Kale and Ohad Shamir, editors, _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pages 1674–1703. PMLR, 07–10 Jul 2017.  URL https://proceedings.mlr.press/v65/raginsky17a.html.
  * Seide et al. [2014] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and application to data-parallel distributed training of speech dnns.  In _Interspeech 2014_ , September 2014.
  * Shallue et al. [2018] Chris Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl-dickstein, Roy Frostig, and George Dahl.  Measuring the effects of data parallelism on neural network training.  _Journal of Machine Learning Research (JMLR)_ , 2018.  URL https://arxiv.org/pdf/1811.03600.pdf.
  * Shamir and Zhang [2013] Ohad Shamir and Tong Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In Sanjoy Dasgupta and David McAllester, editors, _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pages 71–79, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.  URL https://proceedings.mlr.press/v28/shamir13.html.
  * Simsekli et al. [2019] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban.  A tail-index analysis of stochastic gradient noise in deep neural networks.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 5827–5837. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/simsekli19a.html.
  * Smith et al. [2019] Samuel L. Smith, Erich Elsen, and Soham De.  Momentum enables large batch training.  In _ICML workshop on Theoretical Physics in Deep Learning_ , 2019\.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/e0eacd983971634327ae1819ea8b6214-Paper.pdf.
  * Smith et al. [2020] Samuel L. Smith, Erich Elsen, and Soham De.  On the generalization benefit of noise in stochastic gradient descent.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org, 2020.
  * Su et al. [2014] Weijie Su, Stephen Boyd, and Emmanuel Candes.  A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.  URL https://proceedings.neurips.cc/paper_files/paper/2014/file/f09696910bdd874a99cd74c8f05b5c44-Paper.pdf.
  * Wang et al. [2021] Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon.  Analyzing the generalization capability of sgld using properties of gaussian channels.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 24222–24234. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper_files/paper/2021/file/cb77649f5d53798edfa0ff40dae46322-Paper.pdf.
  * Welling and Teh [2011] Max Welling and Yee Whye Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , ICML’11, page 681–688, Madison, WI, USA, 2011. Omnipress.  ISBN 9781450306195.
  * Wen et al. [2016] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Learning structured sparsity in deep neural networks.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems 29_ , pages 2074–2082. Curran Associates, Inc., 2016.
  * Wu et al. [2020] Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing Zhu.  On the noisy gradient descent that generalizes as sgd.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org, 2020.
  * Xiao et al. [2017] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
  * Xu et al. [2018] Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu.  Global convergence of langevin dynamics based algorithms for nonconvex optimization.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper_files/paper/2018/file/9c19a2aa1d84e04b0bd4bc888792bd1e-Paper.pdf.
  * Zamir and Feder [1996] R. Zamir and M. Feder.  On lattice quantization noise.  _IEEE Transactions on Information Theory_ , 42(4):1152–1159, 1996.  doi: 10.1109/18.508838.
  * Zhang et al. [2019] Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George Dahl, Chris Shallue, and Roger B Grosse.  Which algorithmic choices matter at which batch sizes? insights from a noisy quadratic model.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper_files/paper/2019/file/e0eacd983971634327ae1819ea8b6214-Paper.pdf.
  * Zhang et al. [2022] Ruqi Zhang, Andrew Gordon Wilson, and Christopher De Sa.  Low-precision stochastic gradient langevin dynamics.  In _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 26624–26644. PMLR, 2022.  URL https://proceedings.mlr.press/v162/zhang22ag.html.
  * Øksendal [2003] Bernt Øksendal.  _Stochastic Differential Equations:An Introduction with Applications_.  Springer-Verlag, 6th edition, 2003.  ISBN 978-3-540-04758-2.

##  Appendix A Introduction

We provide the proofs for the theorems and lemmas featured in this manuscript.
Firstly, we present the proof of Theorem 1, which introduces the fundamental
form of our idea and discussions in the paper. Although the proof is
straightforward, the learning equation described in Theorem 1 plays a crucial
role in our proposed approach.

Next, we provide the proof of Lemma 2, as the proposed learning equation is
discrete. Therefore, verifying the approximation of the stochastic
differential equation corresponding to the proposed equation is necessary. We
adopt the framework introduced by Li et al. [2019], Malladi et al. [2022] and
Kloeden_1992 to accomplish this. Using the approximated stochastic
differential equation, we give the proof of Theorem 3 about the weak
convergence of the proposed algorithm.

We also establish the proposed algorithm’s asymptotic convergence under a
convex assumption. Through the property of weak convergence, we posit that the
proposed algorithm possesses a stationary distribution of the transition
probability towards an optimal point, even in the presence of non-convex
objective functions. Despite the non-convexity assumptions, we provide proof
of local convergence by considering the feasibility of assuming strict local
convexity around an optimal point.

Furthermore, we provide detailed information regarding the experiments,
including comprehensive results of simulations for each dataset, network
models utilized, and the corresponding hyperparameters for each algorithm.
Finally, we offer further discussion and analysis of the specific empirical
findings in these experiments.

##  Appendix B Notations

  * •

$\mathbf{R}^{n}$ The n-dimensional space with real numbers

  * •

$\mathbf{R}$ $\mathbf{R}^{n}|_{n=1}$

  * •

$\mathbf{R}[\alpha,\beta]$ $\\{x\in\mathbf{R}|\alpha\leq
x\leq\beta,\;\alpha,\beta\in\mathbf{R}\\}$

  * •

$\mathbf{R}(\alpha,\beta]$
$\\{x\in\mathbf{R}|\alpha<x\leq\beta,\;\alpha,\beta\in\mathbf{R}\\}$

  * •

$\mathbf{R}[\alpha,\beta)$ $\\{x\in\mathbf{R}|\alpha\leq
x<\beta,\;\alpha,\beta\in\mathbf{R}\\}$

  * •

$\mathbf{R}(\alpha,\beta)$
$\\{x\in\mathbf{R}|\alpha<x<\beta,\;\alpha,\beta\in\mathbf{R}\\}$

  * •

$\mathbf{Q}^{n}$ The n-dimensional space with rational numbers

  * •

$\mathbf{Q}$ $\mathbf{Q}^{n}|_{n=1}$

  * •

$\mathbf{Z}$ The 1-dimensional space with integers.

  * •

$\mathbf{N}$ The 1-dimensional space with natural numbers.

  * •

$\mathbf{R}^{+}$ $\\{x|x\geq 0,\;x\in\mathbf{R}\\}$

  * •

$\mathbf{R}^{++}$ $\\{x|x>0,\;x\in\mathbf{R}\\}$

  * •

$\mathbf{Q}^{+}$ $\\{x|x\geq 0,\;x\in\mathbf{Q}\\}$

  * •

$\mathbf{Q}^{++}$ $\\{x|x>0,\;x\in\mathbf{Q}\\}$

  * •

$\mathbf{Z}^{+}$ $\\{x|x\geq 0,\;x\in\mathbf{Z}\\}$

  * •

$\mathbf{Z}^{++}$ $\\{x|x>0,\;x\in\mathbf{Z}\\}$, $\mathbf{Z}^{++}$ is equal
to $\mathbf{N}$.

  * •

$\lfloor x\rfloor$ $\max\\{y\in\mathbf{Z}|y\leq x,\forall x\in\mathbf{R}\\}$

  * •

$\lceil x\rceil$ $\min\\{y\in\mathbf{Z}|y\geq x,\forall x\in\mathbf{R}\\}$

  * •

$n_{B_{\tau}}$ The numbers of samples in the $\tau$-th mini-batch $B_{\tau}$.

  * •

$B$ The total numbers of mini-batches. If we have totally $N_{T}$ numbers of
samples for a dataset, we have $N_{T}=\sum_{\tau=1}^{B}n_{B_{\tau}}$.

  * •

$t\in\mathbf{R}^{+}$ Time index for stochastic analysis on a continuous time

  * •

$\tau\in\mathbf{Z}^{+}$ Discrete time index. Typically it denotes the index of
mini-batches

  * •

$t_{e}\in\mathbf{Z}^{+}$ Discrete time index. Typically it denotes the epoch,
corresponding to $\tau$ such that $t_{e}=\tau/B$

##  Appendix C Fundamental Learning Equation

###  C.1 Proof of Theorem 4.1

######  Theorem 1.

Suppose an initial parameter is quantized as $\boldsymbol{X}_{0}^{Q}$. To
ensure the consistency of quantization for all $\tau$, we establish the
quantization-based learning equation with the search direction
$h(\boldsymbol{X}_{\tau})$ as follows:

$\boldsymbol{X}_{\tau+1}^{Q}=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left[Q_{p}(\tau)\cdot\lambda
h(\boldsymbol{X}_{\tau}^{Q})\right]^{Q}$ (24)

, where $\tau\in\mathbf{Z}^{+}$ is a discrete time index. According to the
definition of quantization, We can derive the discrete Langevine equation of
$\eqref{ch04-eq02}$ such that

$\boldsymbol{X}_{\tau+1}^{Q}=\boldsymbol{X}_{\tau}^{Q}+\lambda\,h(\boldsymbol{X}_{\tau}^{Q})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}^{q}.$
(25)

, where $\boldsymbol{\epsilon}_{\tau}^{q}\in\mathbf{R}^{d}$ denotes the
quantization error, which is a Brownian motion process evaluated as
$\boldsymbol{\epsilon}_{\tau}\triangleq\sqrt{\lambda}\int_{\tau}^{\tau+1}d\boldsymbol{B}_{t}$
according to WNH.

###### Proof.

The proof of the theorem is straightforward. Referring to
$\eqref{define_eq01}$ in Definition 2, we can rewrite $\eqref{ack-eq301}$ as
follows:

$\displaystyle\boldsymbol{X}_{\tau+1}^{Q}$
$\displaystyle=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left[Q_{p}(\tau)\cdot\lambda
h(\boldsymbol{X}_{\tau}^{Q})\right]^{Q}$ (26)
$\displaystyle=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left\lfloor
Q_{p}(\tau)\cdot(\lambda
h(\boldsymbol{X}_{\tau}^{Q})+0.5\cdot\boldsymbol{1}\cdot
Q_{p}^{-1})\right\rfloor$
$\displaystyle=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left(Q_{p}(\tau)\cdot\lambda
h(\boldsymbol{X}_{\tau}^{Q})+\boldsymbol{\epsilon}_{\tau}^{q}\right)$
$\displaystyle=\boldsymbol{X}_{\tau}^{Q}+\lambda
h(\boldsymbol{X}_{\tau}^{Q})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}^{q}.$

∎

Although Theorem 1 is considered trivial, the equation $\eqref{thpf_ack-
eq301}$ gives a form of the Stochastic Gradient Langevin Dynamics (SGLD).
Suppose that the discrete-time index $\tau$ depends on the learning rate
$\lambda$ for some continuous time interval $T\triangleq\mathbf{R}[0,T]$ such
that $\tau=T/\lambda$. Then, we note that a unit increase of discrete time
$\tau+1$ is equal to $t+\lambda$ for a continuous time index
$t\in\mathbf{R}[0,T]$ Substituting the direction
$h(\boldsymbol{X}_{\tau}^{Q})$ to $-\nabla f(\boldsymbol{X}_{\tau}^{Q})$ and
the discrete-time index to the continuous time index $t$, we rewriting
$\eqref{thpf_ack-eq301}$ such that

$\displaystyle\boldsymbol{X}_{\tau+1}^{Q}-\boldsymbol{X}_{\tau}^{Q}=-\lambda\nabla
f(\boldsymbol{X}_{\tau}^{Q})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}^{q}.$
(27)
$\displaystyle\Rightarrow\frac{1}{\lambda}(\boldsymbol{X}_{t+\lambda}^{Q}-\boldsymbol{X}_{t}^{Q})=-\nabla
f(\boldsymbol{X}_{t}^{Q})+Q_{p}^{-1}(t)\frac{1}{\lambda}\boldsymbol{\epsilon}_{t}^{q}$

According to the WNH, we can interpret the quantization error in $\eqref{ack-
eq302}$ with respect to the discrete-time index as an integration with the
Wiener process $d\boldsymbol{B}t\in\mathbf{R}^{d}$, which follows a Gaussian
distribution $\mathcal{N}(0,t\boldsymbol{I}^{d\times d})$. Therefore, we can
express $\boldsymbol{\epsilon}_{\tau}^{q}$ as the integral of
$d\boldsymbol{B}_{t}$ over the interval $[\tau_{0},\tau]$, i.e.
$\boldsymbol{\epsilon}_{\tau}^{q}\triangleq\sqrt{\lambda}\int_{\tau}^{\tau+1}d\boldsymbol{B}_{t}$.
Consequently, we obtain the following:

$\displaystyle\boldsymbol{X}_{\tau+1}^{Q}-\boldsymbol{X}_{\tau}^{Q}=-\lambda\nabla
f(\boldsymbol{X}_{\tau}^{Q})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}^{q}.$
(28)
$\displaystyle\Rightarrow\frac{1}{\lambda}(\boldsymbol{X}_{t+\lambda}^{Q}-\boldsymbol{X}_{t}^{Q})=-\nabla
f(\boldsymbol{X}_{t}^{Q})+Q_{p}^{-1}(t)\frac{1}{\lambda}\boldsymbol{\epsilon}_{t}^{q}$
$\displaystyle\Rightarrow\lim_{\lambda\rightarrow
0}\frac{1}{\lambda}(\boldsymbol{X}_{t+\lambda}^{Q}-\boldsymbol{X}_{t}^{Q})=-\nabla
f(\boldsymbol{X}_{t}^{Q})+Q_{p}^{-1}(t)\lim_{\lambda\rightarrow
0}\frac{1}{\lambda}\boldsymbol{\epsilon}_{t}^{q}$
$\displaystyle\Rightarrow\frac{d}{dt}\int_{t}^{t+\lambda}d\boldsymbol{X}_{s}^{Q}=-\nabla
f(\boldsymbol{X}_{t}^{Q})+Q_{p}^{-1}(t)\frac{d}{dt}\int_{t}^{t+\lambda}d\boldsymbol{B}_{s}$
$\displaystyle\Rightarrow d\boldsymbol{X}_{t}^{Q}=-\nabla
f(\boldsymbol{X}_{t}^{Q})+\sqrt{\lambda}Q_{p}^{-1}(t)d\boldsymbol{B}_{t}.$

This intuitive approximation, $\eqref{ack-eq303}$, corresponds to the Langevin
stochastic equation. When comparing it to the Stochastic Differential Equation
(SDE) approximations of SGD presented in Xu et al. [2018], Li et al. [2019,
2021, 2022], Cheng et al. [2020b], and Malladi et al. [2022], we observe that
the variance of the noise differs from both LSR-SGD and the Noisy Stochastic
Gradient Descent (NSGD or NGD) represented by Li et al. [2021].

###  C.2 Brief Review of Related Works and Relation to the Proposed Method

When the LSR-SGD or the NSGD equation is given as follows:

$\boldsymbol{X}_{\tau+1}=\boldsymbol{X}_{\tau}-\lambda\,\nabla
f_{\gamma}(\boldsymbol{X}_{\tau})$ (29)

, the stochastic difference equation for LSR-SGD and NSGD is as follows (Li et
al. [2019] and Li et al. [2021]):

$\boldsymbol{X}_{\tau+1}=\boldsymbol{X}_{\tau}-\lambda\,\nabla
f(\boldsymbol{X}_{\tau})+\sqrt{\lambda}\boldsymbol{\bar{\epsilon}}_{\tau}(\boldsymbol{X}_{\tau})$
(30)

, where $\boldsymbol{\bar{\epsilon}}_{\tau}\triangleq\sqrt{\lambda}(\nabla
f_{\gamma}(\boldsymbol{X}_{\tau})-\nabla f(\boldsymbol{X}_{\tau}))$ is a
$d$-dimensional (i.i.d.) random vector. We can note that the variance of the
$\boldsymbol{\bar{\epsilon}}_{\tau}$ is
$\mathbb{E}(\boldsymbol{\bar{\epsilon}}_{\tau}\boldsymbol{\bar{\epsilon}}_{\tau}^{T})=\eta\Sigma(\boldsymbol{\bar{\epsilon}}_{\tau})$,
where $\Sigma(\boldsymbol{\bar{\epsilon}}_{\tau})\triangleq\mathbb{E}(\nabla
f_{\gamma}(\boldsymbol{X}_{\tau})-\nabla f(\boldsymbol{X}_{\tau}))(\nabla
f_{\gamma}(\boldsymbol{X}_{\tau})-\nabla f(\boldsymbol{X}_{\tau}))^{T}$. Li et
al. [2019, 2021] and Malladi et al. [2022] provided the SDE approximation of
$\eqref{ack-eq307}$ as follows:

$d\boldsymbol{X}_{t}=-\nabla
f(\boldsymbol{X}_{t})+\sqrt{\lambda}\Sigma(\boldsymbol{X}_{t})^{1/2}d\boldsymbol{B}_{t}.$
(31)

On the other hand, Xu et al. [2018] presents the stochastic difference
equation of SGLD as follows:

$\boldsymbol{X}_{\tau+1}=\boldsymbol{X}_{\tau}-\lambda\nabla
f(\boldsymbol{X}_{t})+\sqrt{2\lambda\beta^{-1}}d\boldsymbol{B}_{t}.$ (32)

, where $\beta^{-1}$ is the inverse value of a simulated temperature in MCMC
algorithm families. Comparing the variance terms of LSR-SGD, NSGD, and SGLD,
both LSR-SGD and NSGD rely on the Fisher Information Matrix (FIM) of the
objective function to achieve an effective learning process. In contrast, in
SGLD, the user determines the temperature parameter, allowing the algorithm’s
consistency to be obtained through a straightforward analysis.

The proposed quantized learning equation $\eqref{ack-eq301}$ incorporates a
controlled variance determined by the quantization parameter
$Q_{p}(\tau)\in\mathbf{R}$, which distinguishes it from LSR-SGD and NSGD.
Furthermore, unlike SLGD, our stochastic difference equation does not employ
injection noise via a random generator. Finally, our proposed algorithm yields
a quantized result regardless of the quantization resolution, facilitating a
straightforward additional quantization process for neural models.

##  Appendix D SDE Approximation

Without various boundness assumptions, we derive the SDE approximation for the
proposed QSLD/QSLGD. In contrast, approximating LSR-SGD and NSGD requires
additional boundedness assumptions, given that the derived variance relies on
the Fisher Information Matrix (FIM) of the objective function rather than
being an explicit parameter.

We follow the same proof strategy provided by Li et al. [2019] and Malladi et
al. [2022].

######  Lemma 2.

The approximated Langevin SDE for QSGLD (15) derived by the Euler-Maruyama
method is as follows:

$d\boldsymbol{X}_{t}=-\nabla
f(\boldsymbol{X}_{t})dt+\sqrt{2}Q_{p}^{-1}(t)d\boldsymbol{B}_{t},\quad\forall
t>t_{0}.$ (33)

The approximation $\eqref{lemma01_eq01}$ satisfies the order-1 weak
approximation described in Definition 4.

###### Proof.

Preparation Let the transition probability from $t=\tau$ to $t+1=\tau+\lambda$
such that $p(t,\boldsymbol{X}_{t}^{Q};t+1,\boldsymbol{X}_{t+1}^{Q})$. We
define the following one-step changes of QSLD/QSLGD from $\eqref{ack-eq302}$
and $\eqref{ack-eq304}$ such that

$\Delta(\boldsymbol{X}_{t})\triangleq\lambda\,h(\boldsymbol{X}_{\tau}^{Q}),\quad\tilde{\Delta}(\boldsymbol{X}_{t})\triangleq\boldsymbol{X}_{t+1}-\boldsymbol{X}_{\tau}^{Q},\quad\Delta,\tilde{\Delta}\in\mathbf{R}^{d}$
(34)

, where $\boldsymbol{X}_{t+1}^{Q}\sim
p(t,\boldsymbol{X}_{t}^{Q};t+1,\boldsymbol{X}_{t+1}^{Q})$, and
$\boldsymbol{X}_{t}^{Q}=\boldsymbol{X}_{\tau}^{Q}$.

By proving the following conditions presented in the theorems of SDE
approximation to the SGD equation as proposed by Li et al. [2019] and Malladi
et al. [2022], we validate the applicability of the SDE approximation to the
proposed equation.

Lipschitz continuity and continuous differentiability of the drift and
diffusion functions Assumption 1 in the manuscript provides that the drift
$\nabla f(\boldsymbol{X}_{t})$ is Lipschitz continuity. As the diffusion
function in QSLGD is the quantization parameter, it is Lipschitz continuity by
Definition 3.

Bounded moments condition The first order bounded moments condition is given
by:

$\left|\mathbb{E}(\Delta_{i}(\boldsymbol{X}_{t})-\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\right|\leq
K(\boldsymbol{X}_{t})\lambda^{2}$ (35)

From the definition of $\Delta,\,\tilde{\Delta}$, for the initial time
$t=\tau/N_{B}$, we get

$\displaystyle\Delta(\boldsymbol{X}_{t})-\tilde{\Delta}(\boldsymbol{X}_{t})=\lambda
h(\boldsymbol{X}_{t})-\lambda
h(\boldsymbol{X}_{t})-Q_{p}^{-1}(t)\boldsymbol{\epsilon}_{t}^{q}=-Q_{p}^{-1}(t)\boldsymbol{\epsilon}_{t}^{q}$
(36)
$\displaystyle\Rightarrow\mathbb{E}Q_{p}^{-1}(t)\boldsymbol{\epsilon}_{t}^{q}=Q_{p}^{-1}(t)\mathbb{E}\boldsymbol{\epsilon}_{t}^{q}=0.$

The equation $\eqref{lmpf_eq02}$ represents that the proposed algorithm
fulfills the first-order bounded moment condition.

For the bound of the second moment, we calculate the moment as follows:

$\displaystyle\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})$
$\displaystyle=\lambda^{2}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})$
(37)
$\displaystyle\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})$
$\displaystyle=(\lambda
h_{i}(\boldsymbol{X}_{t})+Q_{p}^{-1}(t){\epsilon_{i}}_{t}^{q})(\lambda
h_{j}(\boldsymbol{X}_{t})+Q_{p}^{-1}(t){\epsilon_{j}}_{t}^{q})$
$\displaystyle=\lambda^{2}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})+\lambda(h_{j}(\boldsymbol{X}_{t})Q_{p}^{-1}(t){\epsilon_{j}}_{t}^{q}+h_{i}(\boldsymbol{X}_{t})Q_{p}^{-1}(t){\epsilon_{i}}_{t}^{q}+Q_{p}^{-2}(t){\epsilon_{i}}_{t}^{q}{\epsilon_{j}}_{t}^{q}.$

$\eqref{lmpf_eq03}$ implies that

$\displaystyle\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})-\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})=-\lambda(h_{j}(\boldsymbol{X}_{t})Q_{p}^{-1}(t){\epsilon_{j}}_{t}^{q}+h_{i}(\boldsymbol{X}_{t})Q_{p}^{-1}(t){\epsilon_{i}}_{t}^{q})-Q_{p}^{-2}(t){\epsilon_{i}}_{t}^{q}{\epsilon_{j}}_{t}^{q}.$
(38)
$\displaystyle\Rightarrow\mathbb{E}(\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})-\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t}))$
$\displaystyle=\lambda(h_{j}(\boldsymbol{X}_{t})Q_{p}^{-1}(t)\mathbb{E}{\epsilon_{j}}_{t}^{q}+h_{i}(\boldsymbol{X}_{t})Q_{p}^{-1}(t)\mathbb{E}{\epsilon_{i}}_{t}^{q})-Q_{p}^{-2}(t)\mathbb{E}{\epsilon_{i}}_{t}^{q}{\epsilon_{j}}_{t}^{q}=-\frac{1}{12}Q_{p}^{-2}(t)\delta(i-j).$

, where $i,j\in\mathbf{N}[1,d]$ denotes the index of the vector components.

Thus, we can choose $t>t_{0}$ such that

$\left|\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})-\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\right|=\frac{1}{12}Q_{p}^{-2}(t)\delta(i-j)\leq
K_{1}(\boldsymbol{X}_{t})\lambda^{2}$ (39)

, where $K_{1}$ denotes a secondary differentiable function such that
$K_{1}:\mathbf{R}^{d}\rightarrow\mathbf{R},\;K_{1}\in C^{2}$.

Similarly, we calculate the third moment as follows:

$\displaystyle\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})\Delta_{k}(\boldsymbol{X}_{t})=\lambda^{3}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t})$
(40)

, and

$\displaystyle\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\tilde{\Delta}_{k}(\boldsymbol{X}_{t})=\lambda^{3}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t})$
(41)
$\displaystyle+\lambda^{2}Q_{p}^{-1}(t)\left(h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t}){\epsilon_{k}}_{t}^{q}+h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t}){\epsilon_{i}}_{t}^{q}+h_{k}(\boldsymbol{X}_{t})h_{i}(\boldsymbol{X}_{t}){\epsilon_{j}}_{t}^{q}\right)$
$\displaystyle+\lambda
Q_{p}^{-2}(t)\left(h_{i}(\boldsymbol{X}_{t}){\epsilon_{j}}_{t}^{q}{\epsilon_{k}}_{t}^{q}+h_{j}(\boldsymbol{X}_{t}){\epsilon_{k}}_{t}^{q}{\epsilon_{i}}_{t}^{q}+h_{k}(\boldsymbol{X}_{t}){\epsilon_{i}}_{t}^{q}{\epsilon_{j}}_{t}^{q}\right)+Q_{p}^{-3}(t){\epsilon_{i}}_{t}^{q}{\epsilon_{j}}_{t}^{q}{\epsilon_{k}}_{t}^{q}.$

Based on the white noise hypothesis(WNH) of the quantization error, we can
determin the expectation value of $\eqref{lmpf_eq06}$ such that

$\displaystyle\mathbb{E}\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\tilde{\Delta}_{k}(\boldsymbol{X}_{t})=\lambda^{3}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t})$
(42) $\displaystyle+\frac{1}{12}\lambda
Q_{p}^{-2}(t)\left(h_{i}(\boldsymbol{X}_{t})\delta(j-k)+h_{j}(\boldsymbol{X}_{t})\delta(k-i)+h_{k}(\boldsymbol{X}_{t})\delta(i-j)\right)$
$\displaystyle=\lambda^{3}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t})+\frac{1}{4}\lambda
Q_{p}^{-2}(t)h_{i}(\boldsymbol{X}_{t})|_{i=j=k}.$

By $\eqref{lmpf_eq07}$ and $\eqref{lmpf_eq05}$, we get

$\displaystyle\mathbb{E}\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\tilde{\Delta}_{k}(\boldsymbol{X}_{t})-\mathbb{E}\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})\Delta_{k}(\boldsymbol{X}_{t})$
(43)
$\displaystyle=\lambda^{3}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t})+\frac{1}{4}\lambda
Q_{p}^{-2}(t)h_{i}(\boldsymbol{X}_{t})|_{i=j=k}-\lambda^{3}h_{i}(\boldsymbol{X}_{t})h_{j}(\boldsymbol{X}_{t})h_{k}(\boldsymbol{X}_{t})$
$\displaystyle=\frac{1}{4}\lambda
Q_{p}^{-2}(t)h_{i}(\boldsymbol{X}_{t})|_{i=j=k}$

According to Assumption 1, there exists an optimal point
$\boldsymbol{X}^{*}\in\mathcal{D}\subset B^{o}(\boldsymbol{X}^{*},\rho)$ such
that $\nabla f(\boldsymbol{X}^{*})=0$ allowing us to obtain

$\displaystyle|\mathbb{E}\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\tilde{\Delta}_{k}(\boldsymbol{X}_{t})-\mathbb{E}\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})\Delta_{k}(\boldsymbol{X}_{t})|$
(44) $\displaystyle=\frac{1}{4}\lambda
Q_{p}^{-2}(t)|h_{i}(\boldsymbol{X}_{t})|_{i=j=k}=\frac{1}{4}\lambda
Q_{p}^{-2}(t)|h_{i}(\boldsymbol{X}_{t})+\nabla
f_{i}(\boldsymbol{X}^{*})|_{i=j=k}.$

In QSLGD, since $h(\boldsymbol{X}_{t})$ is equal to $-\nabla
f(\boldsymbol{X}_{t})$, we apply the $L_{1}$ Lipschitz condition to calculate
the bound as follows:

$\displaystyle|\mathbb{E}\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\tilde{\Delta}_{k}(\boldsymbol{X}_{t})-\mathbb{E}\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})\Delta_{k}(\boldsymbol{X}_{t})|$
$\displaystyle=\frac{1}{4}\lambda
Q_{p}^{-2}(t)|h_{i}(\boldsymbol{X}_{t})+\nabla
f_{i}(\boldsymbol{X}^{*})|_{i=j=k}$ (45) $\displaystyle=\frac{1}{4}\lambda
Q_{p}^{-2}(t)|\nabla f_{i}(\boldsymbol{X}^{*})-\nabla
f_{i}(\boldsymbol{X}_{t})|_{i=j=k}$ $\displaystyle\leq\frac{1}{4}\lambda
Q_{p}^{-2}(t)L_{1}|\boldsymbol{X}^{*}-\boldsymbol{X}_{t}|_{i=j=k}$
$\displaystyle\leq\frac{1}{4}\lambda Q_{p}^{-2}(t)L_{1}\rho$

By selecting $t>t_{0}$ such that $Q_{p}(t)^{-2}<\lambda$, the bound condition
of the third-order moment is satisfied, resulting in

$\displaystyle|\mathbb{E}\tilde{\Delta}_{i}(\boldsymbol{X}_{t})\tilde{\Delta}_{j}(\boldsymbol{X}_{t})\tilde{\Delta}_{k}(\boldsymbol{X}_{t})-\mathbb{E}\Delta_{i}(\boldsymbol{X}_{t})\Delta_{j}(\boldsymbol{X}_{t})\Delta_{k}(\boldsymbol{X}_{t})|\leq\frac{1}{4}\lambda
Q_{p}^{-2}(t)L_{1}\rho<\frac{1}{4}\lambda^{2}L_{1}=K_{1}(\boldsymbol{X}_{t})\lambda^{2}$
(46)

Adaptation Lemma by Li et al. [2019] and Malladi et al. [2022] Under the
verification of the bounded momentum condition
$\eqref{lmpf_eq02},\eqref{lmpf_eq04},\eqref{lmpf_eq10}$, we can establish the
following polynomial growth condition: There exists a subset $P$ of the index
set $\triangleq\\{1,2,\cdots,d\\}$ such that the following holds. Below we use
the notations $\|\boldsymbol{x}_{P}\|\triangleq\sqrt{\sum_{i\in P}x_{i}^{2}}$
and $\|\boldsymbol{x}_{R}\|\triangleq\sqrt{\sum_{i\notin P}x_{i}^{2}}$.

  1. 1.

There is a constant $C_{1}>0$, which is independent of $\lambda$, so that for
all $k\leq N$

$\displaystyle\|\mathbb{E}\Delta(\boldsymbol{X}_{\tau})\|_{P}$
$\displaystyle\leq C_{1}\lambda(1+\|\boldsymbol{X}_{\tau}\|_{P})$ (47)
$\displaystyle\|\mathbb{E}\Delta(\boldsymbol{X}_{\tau})\|_{R}$
$\displaystyle\leq
C_{1}\lambda(1+\|\boldsymbol{X}_{\tau}\|_{P}^{w_{1}})(1+\|\boldsymbol{X}_{\tau}\|_{R})$

  2. 2.

For all $m\geq 1$, there are constant $C_{2m},w_{2m}>0$ (independent of
$\lambda$) such that for all $k<N$

$\displaystyle\|\mathbb{E}\Delta(\boldsymbol{X}_{\tau})\|_{P}^{2m}$
$\displaystyle\leq C_{1}\lambda(1+\|\boldsymbol{X}_{\tau}\|_{P}^{2m})$ (48)
$\displaystyle\|\mathbb{E}\Delta(\boldsymbol{X}_{\tau})\|_{R}$
$\displaystyle\leq
C_{1}\lambda(1+\|\boldsymbol{X}_{\tau}\|_{P}^{w_{2m}})(1+\|\boldsymbol{X}_{\tau}\|_{R}^{2m})$

The analysis shows that the function $K_{1}$ is differentiable to the first
order, allowing for the bound on the third moment. Consequently, a function
$g$ twice differentiable ($g\in C^{2}$) is enough to achieve a first-order
weak approximation for QSLGD.

Adaptation Theorem 3 in by Li et al. [2019] Malladi et al. [2022] Since QSLGD
satisfies the Lipschitz continuity, the bounded moment conditions, and the
adaptation lemma, QSLGD fulfills a first-order weak approximation defined as
Definition 4 in the manuscript, by the theorem provided by Theorem 3 in by
Li_NEURIPS2019, as follows: For each function $g\in C^{2}$, there exists a
constant $C>0$ (independent of $\lambda$) such that

$\max_{0\leq k\leq
N}|\mathbb{E}g(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}g(\boldsymbol{X}_{t})|\leq
C\lambda$ (49)

∎

##  Appendix E Weak Convergence of the proposed algorithm

We use the following lemma to prove the theorems.

######  Lemma : Auxiliary 1.

For all $x\in\mathbf{R}$,

$(1-x)\leq\exp(-x).$ (50)

###### Proof.

By the definition of the exponent, we write the exponential function as the
following fundamental series :

$\exp(-x)=\sum_{n=0}^{\infty}\frac{1}{n!}(-1)^{n}x^{n}=\sum_{k=0}^{\infty}\left(\frac{1}{2k!}x^{2k}-\frac{1}{(2k+1)!}x^{2k+1}\right).$
(51)

Let $u_{k}$ as follows:

$u_{k}=\frac{1}{2k!}x^{2k}\left(1-\frac{1}{2k+1}x\right)$ (52)

then we can rewrite the series of exponents such that

$\exp(-x)=u_{0}+\sum_{k=1}^{\infty}u_{k}.$ (53)

For all $k>0$, since each $u_{k}$ is positive, we have

$1-x=u_{0}\leq u_{0}+\sum_{k=0}^{\infty}u_{k}.$ (54)

Alternatively, we can prove the lemma with differentiation. Let
$g(x)=(1-x)-\exp(-x)$. Differentiating $g(x)$ to $x$, we get

$\frac{dg}{dx}(x)=-1+exp(-x),\;\frac{d^{2}g}{dx^{2}}=-\exp(-x)$ (55)

We note that $g(x)$ is a concave function from the fact that
$\frac{d^{2}g}{dx^{2}}<0,\;\forall x\in\mathbf{R}$. In addition, the maximum
of $g(x)$ is zero at $x=0$ from which $\frac{dg}{dx}(x)=-1+exp(-x)=0$.
Therefore, $g(x)\leq 0$, so that it fulfills the Lemma. ∎

###  E.1 Proof of Theorem 4.3

We denote a continuous time interval $\bar{\tau}\in\mathbf{R}$ to distinguish
with the discrete-time index $\tau$. In this time indexes $t+1$ equals to
$\tau+\lambda$ when $t=\tau$. Thus, for arbitrary index $k\in\mathbf{Z}^{+}$,
we note that $t+k$ equals to $\tau+\lambda\,k$.

######  Theorem 3.

Consider the transition probability, denoted as
$p(t_{0},\boldsymbol{X}_{t_{0}};t+\bar{\tau},\boldsymbol{X}^{*})$, from an
arbitrary state $\boldsymbol{X}_{t}$ to the optimal point $\boldsymbol{X}^{*}$
after a time interval $\bar{\tau}$. Using the given notation, we define the
stationary transition probability such that
$\pi(t,\bar{\boldsymbol{X}}_{t},t;t+\bar{\tau},\boldsymbol{X}^{*})\triangleq
p(t,\bar{\boldsymbol{X}}_{t};t+\bar{\tau},\boldsymbol{X}^{*})$. If the
quantization parameter is bounded as follows:

$\sup_{t\geq 0}Q_{p}=\frac{1}{C}\cdot{\log(t+2)},\quad C\in\mathbf{R}^{++},$
(56)

QSGLD represented as $\eqref{ch04-eq04}$ converges with distribution such that

$\overline{\lim_{\bar{\tau}\rightarrow\infty}}\sup_{\boldsymbol{X}_{t},\boldsymbol{X}_{t+\bar{\tau}}\in\mathbf{R}^{n}}\|\pi(t,\bar{\boldsymbol{X}}_{t};t+\bar{\tau},\boldsymbol{X}^{*})-p(t,\boldsymbol{X}_{t};t+\bar{\tau},\boldsymbol{X}^{*})\|\leq\tilde{C}\cdot\exp\left(-\sum_{k=0}^{\infty}\delta_{t+\bar{\tau}}\right)$
(57)

where $\delta_{t}$ a positive valued function satisfying
$\sum_{k=0}^{\infty}\delta_{t}=\infty$, and $\tilde{C}$ denotes a positive
value.

###### Proof.

We depend on the lemmas in works of Geman-1986 to prove the theorem. First, we
prove the following convergence of the transition probability:

$\lim_{\bar{\tau}\rightarrow\infty}\sup_{\boldsymbol{X}_{t},\boldsymbol{X}_{t+\bar{\tau}}\in\mathbf{R}^{n}}\|p(t,\boldsymbol{X}_{t},t+\bar{\tau},\boldsymbol{X}^{*})-p(t,\boldsymbol{X}_{t},t+\tau,\boldsymbol{X}^{*})\|=0$
(58)

, where $t$ and $\tau$ is the current time index and the process time index,
respectively. $\boldsymbol{X}^{*}$ represents an global optimum for the
objective function $f(\boldsymbol{X}_{t})$.

Let the infimum of the transition probability from $t$ to $t+1$ such that

$\delta_{t}=\inf_{\boldsymbol{x},\boldsymbol{y}\in\mathbf{R}^{d}}p(t,\boldsymbol{x},t+1,\boldsymbol{y})$
(59)

According to the lemma in Geman-1986, we can evaluate the upper bound of
$\eqref{lmpf2.7_eq01}$ as follows: For state vectors
$\boldsymbol{v},\boldsymbol{w},\boldsymbol{z},\boldsymbol{f}\in\mathbf{R}^{d}$
and time indexes $s,t\in\mathbf{R}$,

$\displaystyle\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}|p(s,\boldsymbol{v};t,\boldsymbol{f})-p(s,\boldsymbol{\boldsymbol{w}};t,\boldsymbol{f})|$
(60)
$\displaystyle=\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}\left|\int
p(s,\boldsymbol{v};s+1,\boldsymbol{z})p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz-\int
p(s,\boldsymbol{w};s+1,\boldsymbol{z})p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz\right|$
$\displaystyle=\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}\left|\int
p(s,\boldsymbol{v};s+1,\boldsymbol{z})p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz-\int
p(s,\boldsymbol{w};s+1,\boldsymbol{z})p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz-(\delta_{s}-\delta_{s})p(s+1,\boldsymbol{z};t,\boldsymbol{f})\right|$
$\displaystyle=\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}\left|\int(p(s,\boldsymbol{v};s+1,\boldsymbol{z})-\delta_{s})p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz-\int(p(s,\boldsymbol{w};s+1,\boldsymbol{z})-\delta_{s})p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz\right|$
$\displaystyle\leq\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}\left|\int(p(s,\boldsymbol{v};s+1,\boldsymbol{z})-\delta_{s})\sup_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz-\int(p(s,\boldsymbol{w};,s+1,\boldsymbol{z})-\delta_{s})\inf_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})dz\right|$
$\displaystyle=\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}\left|\sup_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})\int(p(s,\boldsymbol{v};s+1,\boldsymbol{z})-\delta_{s})dz-\inf_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})\int(p(s,\boldsymbol{w};s+1,\boldsymbol{z})-\delta_{s})dz\right|$
$\displaystyle\leq\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}\left|(1-\delta_{s})\sup_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})-(1-\delta_{s})\inf_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})\right|$
$\displaystyle=\overline{\lim_{t\rightarrow\infty}}\sup_{\boldsymbol{v},\boldsymbol{w}}(1-\delta_{s})\left|\sup_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})-\inf_{z}p(s+1,\boldsymbol{z};t,\boldsymbol{f})\right|$
$\displaystyle\cdots$
$\displaystyle\leq\overline{\lim_{t\rightarrow\infty}}\left(\prod_{k=0}^{(t-s)-1}(1-\delta_{s+k})\right)\cdot\sup_{\boldsymbol{v},\boldsymbol{w}}\left|p(s+(t-s),\boldsymbol{v};t,\boldsymbol{f})-p(s+(t-s),\boldsymbol{w};t,\boldsymbol{f})\right|$
$\displaystyle\leq\overline{\lim_{t\rightarrow\infty}}\left(\prod_{k=0}^{(t-s)-1}(1-\delta_{s+k})\right)=\prod_{k=0}^{\infty}(1-\delta_{s+k}).$

Thus, we obtain

$\overline{\lim_{\tau\rightarrow\infty}}\sup_{\boldsymbol{X}_{t},\boldsymbol{X}_{t+\tau}\in\mathbf{R}^{d}}\|p(t,\boldsymbol{X}_{t};t+\tau,\boldsymbol{X}^{*})-p(t,\boldsymbol{X}_{t};t+\tau,\boldsymbol{X}^{*})\|\leq\prod_{k=0}^{\infty}(1-\delta_{t+k}).$
(61)

From the exponential approximation (1) in Lemma:Auxiliary, we rewrite
$\eqref{lmpf2.7_eq03}$ as follows:

$\overline{\lim_{\tau\rightarrow\infty}}\sup_{\boldsymbol{X}_{t},\boldsymbol{X}_{t+\tau}\in\mathbf{R}^{d}}\|p(t,\boldsymbol{X}_{t},t+\tau,\boldsymbol{X}^{*})-p(t,\boldsymbol{X}_{t},t+\tau,\boldsymbol{X}^{*})\|\leq\exp(-\sum_{k=0}^{\infty}\delta_{t+k})).$
(62)

To derive an upper bound for $\delta_{t+k}$, we rephrase the approximation SDE
governing the dynamics of the proposed algorithm, as stated in Lemma 2:

$d\boldsymbol{X}_{s}=-\nabla
f(\boldsymbol{X}_{s})ds+\sigma(s)\sqrt{C_{q}}d\boldsymbol{B}_{s},\quad
s\in\mathbf{R}(t,t+1).$ (63)

, where $\sigma(s)\triangleq 1/\sqrt{C_{q}}\,Q_{p}^{-1}(s)$.

Define a domain $\mathcal{F}\\{f:[t,t+1]\rightarrow\mathbf{R}^{d},f\in
C^{2}\\}$, Let $P_{x}$ be the probability measures on $\mathcal{F}$ induced by
$\eqref{lmpf2.7_eq05}$ and the probability distribution $Q_{x}$ given by the
following equation:

$d\bar{\boldsymbol{X}}_{s}=\sigma(s)\sqrt{C_{q}}d\boldsymbol{B}_{s},\quad
s\in\mathbf{R}(t,t+1).$ (64)

According to the Girsanov theorem (Øksendal [2003], Klebaner [2012]), we
obtain

$\frac{dP_{\boldsymbol{X}}}{dQ_{\bar{\boldsymbol{X}}}}=\exp\left\\{-\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\nabla
f(\boldsymbol{X}_{s})d\bar{\boldsymbol{X}}_{s}-\frac{1}{2}\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\|\nabla
f(\boldsymbol{X}_{s})\|^{2}ds\right\\}.$ (65)

To compute the upper bound of $\eqref{lmpf2.7_eq07}$, we will check the upper
bound of $\|\nabla f\|$. Considering Assumption 2, the gradient of
$f(\boldsymbol{X}_{t})\in C^{2}$ fulfills the Lipschitz continuous condition
as well. Thereby, there exists a positive value $L^{\prime}$ such that

$\|\nabla f(\boldsymbol{X}_{s})-\nabla f(\boldsymbol{X}^{*})\|\leq
L^{\prime}\|\boldsymbol{X}_{s}-\boldsymbol{X}^{*}\|,\quad\forall s>0.$ (66)

Successively, since $\nabla f(\boldsymbol{X}^{*})=0$, the Lipschitz condition
forms simply as follows :

$\|\nabla f(\boldsymbol{X}_{t})\|\leq L^{\prime}\rho=C_{0}$ (67)

, where $\rho=\|\boldsymbol{X}_{t}-\boldsymbol{X}^{*}\|$.

Consequently, for all $s\in\mathbf{R}[t,t+1)$, we compute the upper bound of
the first term in exponential function in $\eqref{lmpf2.7_eq07}$ as follows:

$\displaystyle\left\|\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\nabla
f(\boldsymbol{X}_{s})d\bar{\boldsymbol{X}}_{s}\right\|$
$\displaystyle\leq\int_{t}^{t+1}\left\|\frac{C_{q}^{-1}}{\sigma^{2}(s)}\nabla
f(\boldsymbol{X}_{s})d\bar{\boldsymbol{X}}_{s}\right\|$ (68)
$\displaystyle\leq\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\left\|\nabla
f(\boldsymbol{X}_{s})\right\|\sigma(s)\sqrt{C_{q}}d\boldsymbol{B}_{s}$
$\displaystyle\leq\frac{\sqrt{C_{q}^{-1}}}{\sigma(s)}\sup\left\|\nabla
f(\boldsymbol{X}_{s})\right\|\int_{t}^{t+1}d\boldsymbol{B}_{s}$
$\displaystyle\leq\frac{\sqrt{C_{q}^{-1}}}{\sigma(s)}C_{0}\left\|\boldsymbol{B}_{t}\right\|\leq\frac{1}{\sigma(s)}C_{0}\sqrt{C_{q}^{-1}}(\rho+\frac{1}{2}).$

It implies that

$\left\|-\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma(s)}\nabla
f(\boldsymbol{X}_{s})d\bar{\boldsymbol{X}}_{s}\right\|\leq\frac{C_{1}}{\sigma(s)}$
(69)

, where $C_{1}$ denotes positive value such that
$C_{1}>C_{0}\sqrt{C_{q}^{-1}}(\rho+\frac{1}{2})$.

In addition, the upper bound of the second term represents

$\displaystyle\frac{1}{2}\left\|\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\|\nabla
f(\boldsymbol{X}_{s})\|^{2}ds\right\|$
$\displaystyle\leq\frac{1}{2}\int_{t}^{t+1}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\|\nabla
f(\boldsymbol{X}_{s})\|^{2}ds$ (70)
$\displaystyle\leq\frac{1}{2}\frac{C_{q}^{-1}}{\sigma^{2}(s)}\sup\|\nabla_{x}f(\boldsymbol{X}_{s})\|^{2}\int_{t}^{t+1}ds$
$\displaystyle\leq\frac{1}{2\sigma^{2}(s)}C_{q}^{-1}\cdot
C_{0}^{2}\leq\frac{C_{2}}{2\sigma^{2}(s)},\quad\because C_{2}>C_{q}^{-1}\cdot
C_{0}^{2}.$

Because $\sigma(s)\triangleq 1/\sqrt{2}\,Q_{p}^{-1}(t)$ is monotone decreasing
function, the supremum of $\sigma(s)$ is $\sigma(0)$ for all
$s\in\mathbf{R}[0,\infty)$, i.e.
$\sup_{s\in\mathbf{R}[0,\infty]}\sigma(s)=\sigma(0)\triangleq\sigma$. With the
supremum of each term in $\eqref{lmpf2.7_eq07}$, we can obtain the lower bound
of the Radon-Nykodym derivative $\eqref{lmpf2.7_eq07}$ such that

$\frac{dP_{\boldsymbol{X}}}{dQ_{\bar{\boldsymbol{X}}}}\geq\exp\left(-\frac{1}{\sigma(s)}\left(C_{1}+\frac{C_{2}}{2\sigma(s)}\right)\right)\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right),\quad\because
C_{3}>2\sigma(0)C_{2}+C_{1}.$ (71)

Accordingly, for any $\varepsilon>0$ and
$\boldsymbol{X}_{t},\;\boldsymbol{X}^{*}\in\mathbf{R}^{d}$, the infimum of
$P_{x}(|X_{t+1}-\boldsymbol{X}^{*}|<\varepsilon)$ is

$P_{\boldsymbol{X}}(\left\|\boldsymbol{X}_{t+1}-\boldsymbol{X}^{*}\right\|<\varepsilon)\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)Q_{\bar{\boldsymbol{X}}}(\left\|\boldsymbol{X}_{t+1}-\boldsymbol{X}^{*}\right\|<\varepsilon).$
(72)

As $Q_{w}$ is a normal distribution based on $\eqref{lmpf2.7_eq06}$, we have

$\displaystyle
P_{\boldsymbol{X}}(|\boldsymbol{X}_{t+1}-\boldsymbol{X}^{*}|<\varepsilon)$
$\displaystyle\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\int_{\left\|\boldsymbol{X}-\boldsymbol{X}^{*}\right\|<\varepsilon}\frac{1}{\sigma\sqrt{2\pi\int_{t}^{t+1}C_{q}d\tau}}\exp\left(-\frac{(\boldsymbol{X}-\boldsymbol{X}^{*})^{2}}{2\int_{t}^{t+1}C_{q}d\tau}\right)d\boldsymbol{X}$
(73)
$\displaystyle\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\int_{\|\boldsymbol{X}-\boldsymbol{X}^{*}\|<\varepsilon}\frac{1}{\sigma\sqrt{2\pi
C_{q}\int_{t}^{t+1}d\tau}}\exp\left(-\frac{(\sqrt{\rho}+\varepsilon)^{2}}{2C_{q}\int_{t}^{t+1}d\tau}\right)d\boldsymbol{X}$
$\displaystyle\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\frac{1}{\sigma(0)\sqrt{2\pi
C_{q}}}\exp\left(-\frac{(\sqrt{\rho}+\varepsilon)^{2}}{2C_{q}}\right)\int_{\|\boldsymbol{X}-\boldsymbol{X}^{*}\|<\varepsilon}dx$
$\displaystyle=\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\frac{1}{\sigma(0)\sqrt{2\pi
C_{q}}}\exp\left(-\frac{(\sqrt{\rho}+\varepsilon)^{2}}{2C_{q}}\right)2\varepsilon$
$\displaystyle\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\frac{1}{\sigma(0)\sqrt{2\pi
C_{q}}}\left(1+\frac{(\sqrt{\rho}+\varepsilon)^{2}}{2C_{q}}\right)2\varepsilon$
$\displaystyle\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\frac{1}{\sigma(0)\sqrt{2\pi
C_{q}}}\left(\frac{2C_{q}+(\sqrt{\rho}+\varepsilon)^{2}}{C_{q}}\right)\Bigg{|}_{\rho=0,\varepsilon=0}\cdot\varepsilon$
$\displaystyle\geq\exp\left(-\frac{C_{3}}{\sigma(s)}\right)\cdot
C_{4}\cdot\varepsilon,\quad\because C_{4}=\frac{\sqrt{2}}{\sigma(0)\sqrt{\pi
C_{q}}}.$

Finally, we obtain the lower bound of the transition probability such that

$\displaystyle\delta_{t}$
$\displaystyle=\inf_{\boldsymbol{x},\boldsymbol{y}\in\mathbf{R}^{d}}p(t,\boldsymbol{x},t+1,\boldsymbol{y})\bigg{|}_{\boldsymbol{x}=\boldsymbol{X}_{t},\;y=\boldsymbol{X}^{*}}$
$\displaystyle=\inf_{\boldsymbol{x},\boldsymbol{y}\in\mathbf{R}^{d}}\lim_{\varepsilon\rightarrow
0}\frac{1}{\varepsilon}P_{\boldsymbol{X}}(\left\|\boldsymbol{X}_{t+1}-\boldsymbol{X}^{*}\right|<\varepsilon)$
$\displaystyle\geq\inf_{\boldsymbol{x},\boldsymbol{y}\in\mathbf{R}^{d}}\lim_{\varepsilon\rightarrow
0}\frac{1}{\varepsilon}\cdot
C_{4}\cdot\exp\left(-\frac{C_{3}}{\sigma(t)}\right)\cdot\cdot\varepsilon$
$\displaystyle\geq\exp\left(-\frac{C_{5}}{\sigma(t)}\right),\quad\because
C_{5}>C_{3}+\sigma(0)\cdot|\ln C_{4}|$

The above inequality implies that if there exists a monotone decreasing
function such that $\sigma(s)\geq\frac{C_{5}}{\log(t+2)}$, it satisfies that
the convergence condition given by $\eqref{lmpf2.7_eq04}$ such that

$\sum_{k=0}^{\infty}\delta_{t+k}\geq\sum_{k=0}^{\infty}\exp\left(-\frac{C_{5}}{C_{5}}\log(t+2+k)\right)=\sum_{k=0}^{\infty}\frac{1}{t+2+k}=\infty,\quad\forall
k\geq 0.$ (74)

Substitute $\eqref{lmpf2.7_eq21}$ into $\eqref{lmpf2.7_eq04}$, we obtain

$\overline{\lim_{\tau\rightarrow\infty}}\sup_{\boldsymbol{X}_{t},x_{t+\tau}\in\mathbf{R}^{d}}\|p(t,\boldsymbol{X}_{t},t+\tau,\boldsymbol{X}^{*})-p(t,\boldsymbol{X}_{t},t+\tau,\boldsymbol{X}^{*})\|\leq
2\|\boldsymbol{X}^{*}\|_{\infty}\exp(-\sum_{k=0}^{\infty}\delta_{t+k}))=0.$
(75)

∎

##  Appendix F Asymptotic Convergence Property

######  Theorem 4.

The proposed QSGLD converges an optimal point in order-1 weak approximation
under the assumption stated in Assumption 4.

###### Proof.

Given the approximation of the Stochastic Differential Equation (SDE) for
QSGLD as $\eqref{ack-eq302}$, we can calculate the one-step difference of the
objective function as follows:

$\displaystyle f(\boldsymbol{X}_{\tau+1}^{Q})-f(\boldsymbol{X}_{\tau}^{Q})$
$\displaystyle=\langle\nabla f(\boldsymbol{X}_{\tau}^{Q}),-\lambda\nabla
f(\boldsymbol{X}_{\tau}^{Q})+Q_{p}^{-1}(\tau)\boldsymbol{\epsilon}_{\tau}\rangle$
(76) $\displaystyle+\lambda^{2}\int_{0}^{1}(1-s)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),H(\boldsymbol{X}_{\tau}^{Q}+s(\boldsymbol{X}_{\tau+1}^{Q}-\boldsymbol{X}_{\tau}^{Q}))\nabla
f(\boldsymbol{X}_{\tau}^{Q})\rangle ds$

, where $H(\cdot):\mathbf{R}^{d}\rightarrow\mathbf{R}^{d\times d}$ denotes
Hessian of the objective function $f$.

Assumption 4 and Definition 1 indicates that there exists the eigenvalue
$M_{\max}\in\mathbf{R}^{+}+$ of the Hessian such that
$(H)_{\mathbf{R}^{d\times d}}\leq M_{\max}$. It implies

$\displaystyle f(\boldsymbol{X}_{\tau+1}^{Q})-f(\boldsymbol{X}_{\tau}^{Q})$
$\displaystyle\leq\langle\nabla f(\boldsymbol{X}_{\tau}^{Q}),-\lambda\nabla
f(\boldsymbol{X}_{\tau}^{Q})\rangle+Q_{p}^{-1}(\tau)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),\boldsymbol{\epsilon}_{\tau}\rangle+\frac{1}{2}\lambda^{2}M_{\max}\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}$ (77) $\displaystyle=-\lambda\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}+\frac{1}{2}\lambda^{2}M_{\max}\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}+Q_{p}^{-1}(\tau)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),\boldsymbol{\epsilon}_{\tau}\rangle$
$\displaystyle=\lambda\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}\left(\frac{1}{2}\lambda
M_{\max}-1\right)+Q_{p}^{-1}(\tau)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),\boldsymbol{\epsilon}_{\tau}\rangle.$

Furthermore, assuming the existence of the minimum eigenvalue
$m_{\min}\in\mathbf{R}$ of the Hessian matrix $H$ such that
$(H)_{\mathbf{R}^{d\times d}}\geq m_{\min}$, we can compute the difference
between the optimal point $\boldsymbol{X}^{*}$ and $\boldsymbol{X}_{\tau}$ as
follows:

$\displaystyle f(\boldsymbol{X}^{*})-f(\boldsymbol{X}_{\tau}^{Q})$
$\displaystyle\geq-\lambda\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}+\frac{1}{2}\lambda^{2}m_{\min}\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}$ (78)
$\displaystyle=\frac{1}{2}m_{\min}\|\nabla
f(\boldsymbol{X}_{\tau}^{Q})\|^{2}\left(\lambda^{2}-\frac{2}{m_{\min}}\lambda\right)$
$\displaystyle=\frac{1}{2}m_{\min}\|\nabla
f(\boldsymbol{X}_{\tau}^{Q}\|^{2})\left(\left(\lambda-\frac{1}{m_{\min}}\right)^{2}-\frac{1}{m_{\min}^{2}}\right)\geq-\frac{1}{2m_{min}}\|\nabla
f(\boldsymbol{X}_{\tau})\|^{2}.$

For convenience, we abbreviate $m_{\min}$ as $m$ and $M_{\max}$ as $M$.
$\eqref{thpf-eq05}$ implies that

$\|\nabla f(\boldsymbol{X}_{\tau})\|^{2}\geq
2m\left(f(\boldsymbol{X}^{*})-f(\boldsymbol{X}_{\tau})\right).$ (79)

Let us assume that the learning rate is sufficiently small, such that
$\lambda<\min\\{1,\frac{2}{M}\\}$. By substituting the inequality
$\eqref{thpf-eq06}$ into $\eqref{thpf-eq05}$, we can derive the following
equation:

$\displaystyle
f(\boldsymbol{X}_{\tau+1}^{Q})-f(\boldsymbol{X}^{*})+f(\boldsymbol{X}^{*})-f(\boldsymbol{X}_{\tau}^{Q})$
(80) $\displaystyle\leq\frac{1}{2}M\cdot
2m\left(f(\boldsymbol{X}_{\tau}^{Q})-f(\boldsymbol{X}^{*})\right)\left(\lambda^{2}-\frac{2}{M}\lambda\right)+Q_{p}^{-1}(\tau)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),\boldsymbol{\epsilon}_{\tau}\rangle$
$\displaystyle\Rightarrow
f(\boldsymbol{X}_{\tau+1}^{Q})-f(\boldsymbol{X}^{*})$
$\displaystyle\leq\left(1+M\cdot
m\left(\lambda^{2}-\frac{2}{M}\lambda\right)\right)\left(f(\boldsymbol{X}_{\tau}^{Q})-f(\boldsymbol{X}^{*})\right)+Q_{p}^{-1}(\tau)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),\boldsymbol{\epsilon}_{\tau}\rangle.$

Applying the expectation of the quantization to both terms, we obtain

$\displaystyle\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau+1}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})$
(81) $\displaystyle\leq\left(1+M\cdot
m\left(\lambda^{2}-\frac{2}{M}\lambda\right)\right)\left(\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})\right)$
$\displaystyle+Q_{p}^{-1}(\tau)\langle\nabla
f(\boldsymbol{X}_{\tau}^{Q}),\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}\boldsymbol{\epsilon}_{\tau}\rangle$
$\displaystyle=\left(1+M\cdot
m\left(\lambda^{2}-\frac{2}{M}\lambda\right)\right)\left(\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})\right).$

To assess the convergence, we extend the inequality $\eqref{thpf-eq07}$ to
$t+k$ for $k>0$.

$\displaystyle\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau+k}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})$
(82) $\displaystyle\leq\prod_{j=0}^{k-1}\left(1+M\cdot
m\left(\lambda^{2}-\frac{2}{M}\lambda\right)\right)\left(\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})\right).$

The exponential lemma $\eqref{eq02:lemma}$ to the (82) yields

$\displaystyle\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau+k}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})$
(83) $\displaystyle\leq\exp\left(M\cdot
m\cdot\lambda\cdot\sum_{j=0}^{k-1}\left(\lambda-\frac{2}{M}\right)\right)\left(\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})\right).$

The assumption on $\lambda$ such that $\lambda<\min\\{1,\frac{2}{M}\\}$
implies the existence of a negative value, denoted as $\delta^{-}(k)$, which
depends on $k$ and is defined as
$\delta^{-}(k)\triangleq\frac{1}{\lambda}\sum_{j=0}^{k-1}\left(\lambda-\frac{2}{M}\right)$.
Thus, we obtain

$\displaystyle\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau+k}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})$
(84) $\displaystyle\leq\exp\left(\lambda^{2}\cdot
C_{0}\cdot\delta^{-}(k)\right)\left(\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})\right).$

, where $C_{0}$ denotes $M\cdot m$. Consequently, applying an absolute value
to both terms, we get

$|\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau+k}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})|\leq\exp\left(\lambda^{2}C_{0}\cdot\delta^{-}(k)\right)|\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})|.$
(85)

Let
$C_{o1}=(\frac{1}{\lambda^{2}}+C_{0}+\sum_{k=2}^{\infty}(\lambda^{2})^{k-1}C_{0}^{k-1})|\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})|$.
It yields

$|\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}_{\tau+k}^{Q})-\mathbb{E}_{p\sim\boldsymbol{\epsilon_{\tau}}}f(\boldsymbol{X}^{*})|\leq
C_{o1}\lambda^{2}.$ (86)

The inequality $\eqref{thpf-eq12}$ fulfills the theorem. ∎

##  Appendix G Detailed information of Experimental Results

(a) FashionMNIST via CNN

(b) Enlarged plot

Figure 3: The error trends of test algorithms to the dataset and neural models: (a) Training error trends of the CNN model on FashionMNIST dataset.(b) Enlarged Training error trends Table 2: Experimental Environment PC Name | OS | GPU | CPU
---|---|---|---
PC-1 | Linux Ubuntu 22.0 | NVIDIA GeForce GTX 1080Ti | Intel i9 7900
PC-2 | Windows 11 | NVIDIA GeForce RTX 3050 | Intel i9 7900
PC-3 | Windows 11 | NVIDIA GeForce GTXTi | Intel i7 6700

(a) CIFAR10 via ResNet50

(b) Enlarged plot

Figure 4: The error trends of test algorithms to the dataset and neural models: (a) Training error trends of ResNet-50 on CIFAR-10 dataset.(b) Enlarged Training error trends Table 3: Comparison of test performance among optimizers with a fixed learning rate 0.01. Evaluation is based on the Top-1 accuracy of the training and testing data. Data Set | FashionMNIST | CIFAR10 | CIFAR100
---|---|---|---
Model | CNN with 3-Layer Blocks | ResNet-50 (56 Layer Blocks)
Algorithms | Training | Testing | Training Error | Training | Testing | Training Error | Training | Testing | Training Error
QSGD | 97.10 | 91.59 | 0.085426 | 99.90 | 73.80 | 0.009253 | 99.04 | 37.77 | 0.030104
QADAM | 98.43 | 89.29 | 0.059952 | 99.99 | 85.09 | 0.000001 | 98.62 | 49.60 | 0.037855
SGD | 95.59 | 91.47 | 0.132747 | 99.99 | 63.31 | 0.001042 | 98.24 | 25.90 | 0.005478
ASGD | 95.60 | 91.42 | 0.130992 | 99.99 | 63.46 | 0.001166 | 98.36 | 26.43 | 0.004981
ADAM | 92.45 | 87.12 | 0.176379 | 99.75 | 82.08 | 0.012421 | 98.85 | 46.32 | 0.038741
ADAMW | 91.72 | 86.81 | 0.182867 | 99.57 | 82.20 | 0.012551 | 98.86 | 47.01 | 0.038002
NADAM | 96.25 | 87.55 | 0.140066 | 99.56 | 82.46 | 0.014377 | 98.62 | 48.56 | 0.037409
RADAM | 95.03 | 87.75 | 0.146404 | 99.65 | 82.26 | 0.010526 | 98.17 | 48.61 | 0.044193

We conducted the experiments using a Python program based on the PyTorch
framework version 1.13.1. For the experiments, we utilized three computers,
and the detailed specifications of each computer are provided in Table 2. The
Python version used was 3.10.0, and the Anaconda version was 23.10. We
conducted the experiments for the FashionMNIST dataset using a vanilla CNN
with three-layer blocks. For the CIFAR-10 and CIFAR-100 datasets, we used the
ResNet-50 model with 56 layer blocks. The representative experimental results
are presented in Table 3. A fixed learning rate of 0.01 is utilized in all
experiments, and 200 epochs are conducted for all datasets. The batch sizes
for FashionMNIST, CIFAR-10, and CIFAR-100 are 100 samples, 128 samples, and
100 samples, respectively.

###  G.1 Learning Equations used in the Experiment

(a) CIFAR100 via ResNet50

(b) Enlarged plot

Figure 5: The error trends of test algorithms to the dataset and neural
models: (a) Training error trends of ResNet-50 on CIFAR-100 dataset.(b)
Enlarged Training error trends

QSGLD and QSLD-ADAM

The fundamental learning equation of the proposed algorithm is as follows:

$\boldsymbol{X}_{\tau+1}^{Q}=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left[Q_{p}(\tau)\cdot\lambda
h(\boldsymbol{X}_{\tau}^{Q})\right]^{Q}.$ (87)

, where $h(\boldsymbol{X}_{\tau})=-\nabla f((\boldsymbol{X}_{\tau})$ for
QSGLD, and
$h(\boldsymbol{X}_{\tau})=-\frac{\hat{\boldsymbol{m}}_{\tau}}{\sqrt{\hat{\boldsymbol{v}}_{\tau}}+\epsilon}$
for Adam-based QSLD, respectively.

The quantization parameter $Q_{p}$ is defined as follows:

$Q_{p}=\eta b^{\bar{p}(t_{e})}.$ (88)

where $t_{e}$ represents the time index of each epoch, given by
$t_{e}=\frac{\tau}{N_{B}}$ for the number of mini-batches per epoch $N_{B}$,
and $\bar{p}(t_{e})$ denotes the power function, derived as follows:"

$\displaystyle Q_{p}=\eta b^{\bar{p}(t_{e})}|_{t_{e}=\tau/N_{B}}$
$\displaystyle\leq\frac{1}{C}\log(\tau+2)$ (89) $\displaystyle
b^{\bar{p}(t_{e})}|_{t_{e}=\tau/N_{B}}$
$\displaystyle\leq\frac{1}{\eta\,C}\log(\tau+2)$
$\displaystyle\bar{p}(t_{e})|_{t_{e}=\tau/N_{B}}$
$\displaystyle\leq\log_{b}\left(\frac{1}{\eta\,C}\log(\tau+2)\right).$

For convenience, we define the constant $C$ in $\eqref{ack-ex03}$ as the
reciprocal value of $\eta$. Additionally, Considering the upper bound of the
quantization parameter, which needs to be a rational number, we apply the
floor function to the upper bound of the quantization parameter. Therefore,
the power function for the quantization parameter is as follows:

$\bar{p}(t_{e})|_{t_{e}=\tau/B}\triangleq\lfloor\log_{b}\log(\tau+2)\rfloor.$
(90)

Finally, we introduce an enforcement function to prevent early paralysis,
defined as follows:

$r(\tau,\boldsymbol{X}_{\tau})=\left\lfloor\lambda\cdot\frac{\exp(-\varkappa(\tau-\tau_{0}))}{1+\exp(-\varkappa(\tau-\tau_{0}))}\cdot\frac{h(\boldsymbol{X}_{\tau})}{\|h(\boldsymbol{X}_{\tau})\|}\right\rfloor,\quad\tau_{0}\in\mathbf{Z}^{d}$
(91)

, where $\tau_{0}$ is a parameter, measured in mini-batches, that determines
the interval for applying the enforcement function during the learning
process. The parameter $\varkappa$ represents the shape of the enforcement
function, with larger values causing a rapid decrease toward zero.

The followings are the summary of all the equations for the proposed
algorithm:

$\displaystyle t_{e}$ $\displaystyle=\tau/B$ (92)
$\displaystyle\bar{p}(t_{e})$
$\displaystyle=\lfloor\log_{b}\log(\tau+2)\rfloor$ $\displaystyle Q_{p}$
$\displaystyle=\eta b^{\bar{p}(t_{e})}$ $\displaystyle r(\tau)$
$\displaystyle=\left\lfloor\lambda\cdot\frac{\exp(-\varkappa(\tau-\tau_{0}))}{1+\exp(-\varkappa(\tau-\tau_{0}))}\cdot\frac{h(\boldsymbol{X}_{\tau}^{Q})}{\|h(\boldsymbol{X}_{\tau}^{Q})\|}\right\rfloor$
$\displaystyle\boldsymbol{X}_{\tau+1}^{Q}$
$\displaystyle=\boldsymbol{X}_{\tau}^{Q}+Q_{p}^{-1}(\tau)\left[Q_{p}(\tau)\cdot\left(\lambda
h(\boldsymbol{X}_{\tau}^{Q})+r(\tau,\boldsymbol{X}_{\tau}^{Q})\right)\right]^{Q}.$

We recommend the hyper-parameters represented as follows:

$\eta\in 2^{19}\approx 0.5\times 10^{6},\;C=1/\eta,\;b=2\;\kappa=2.0\text{ or
}4.0,\;t_{0}=5\text{ ~{} }20\text{\% of all epochs}.$ (93)

In the following section, we present an empirical analysis of the impact of
changing hyperparameters.

SGD We set the SGD for the experiments using standard gradient descent form,
as follows:

$\boldsymbol{X}_{\tau+1}=\boldsymbol{X}_{\tau}-\lambda\nabla
f(\boldsymbol{X}_{\tau}).$ (94)

ASGD (Average SGD by Shamir and Zhang [2013]) optimizer updates the parameters
using the following equation:

$\boldsymbol{X}_{\tau+1}=\frac{1}{t}\sum_{i=0}^{t-1}\nabla
f(\boldsymbol{X}_{\tau-i}),$ (95)

where $\boldsymbol{X}_{\tau}$ represents the updated parameter at time step
$\tau$.

ADAM (Adaptive Moment Estimation by Kingma and Ba [2015]) optimizer updates
the parameters using the following equations:

$\displaystyle\boldsymbol{m}_{\tau}$
$\displaystyle=\beta_{1}\cdot\boldsymbol{m}_{\tau-1}+(1-\beta_{1})\cdot\boldsymbol{g}_{\tau},$
(96) $\displaystyle\boldsymbol{v}_{\tau}$
$\displaystyle=\beta_{2}\cdot\boldsymbol{v}_{\tau-1}+(1-\beta_{2})\cdot\boldsymbol{g}_{\tau}^{2},$
$\displaystyle\hat{\boldsymbol{m}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{m}_{\tau}}{1-\beta_{1}^{\tau}},$
$\displaystyle\hat{\boldsymbol{v}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{v}_{\tau}}{1-\beta_{2}^{\tau}},$
$\displaystyle\boldsymbol{X}_{\tau}$
$\displaystyle=\boldsymbol{X}_{{\tau}-1}-\frac{\eta}{\sqrt{\hat{\boldsymbol{v}}_{\tau}}+\epsilon}\cdot\boldsymbol{\hat{m}}_{\tau},$

where $\boldsymbol{m}_{\tau}\in\mathbf{R}^{d}$ and
$\boldsymbol{v}_{\tau}\in\mathbf{R}^{d}$ are the first and second moment
estimates respectively, $\boldsymbol{g}_{\tau}\in\mathbf{R}^{d}$ is the
gradient at time step $t$ i.e. $-\nabla f(\boldsymbol{X}_{t})$, $\beta_{1}$
and $\beta_{2}$ are the decay rates for the moments,
$\hat{\boldsymbol{m}}_{\tau}\in\mathbf{R}^{d}$ and
$\hat{\boldsymbol{v}}_{\tau}\in\mathbf{R}^{d}$ are the bias-corrected moment
estimates, $\boldsymbol{X}_{\tau}$ represents the updated parameter at time
step $t$, $\eta$ is the learning rate, and $\epsilon$ is a small constant to
avoid division by zero. We set the hyperparameters for ADAM such that

$\beta_{1}=0.9,\;\beta_{2}=0.999,\;\epsilon=10^{-8}.$ (97)

We utilize the ADAMW optimizer implemented in PyTorch.

NADAM (Nestrov momentum incooperated ADAM by Dozat [2016])

$\displaystyle\mu_{\tau}$
$\displaystyle=\beta_{1}\left(1-\frac{1}{2}0.96^{\tau\psi})\right)$ (98)
$\displaystyle\mu_{\tau+1}$
$\displaystyle=\beta_{1}\left(1-\frac{1}{2}0.96^{(\tau+1)\psi}\right)$
$\displaystyle\boldsymbol{m}_{\tau}$
$\displaystyle=\beta_{1}\cdot\boldsymbol{m}_{\tau-1}+(1-\beta_{1})\cdot\boldsymbol{g}_{\tau},$
$\displaystyle\boldsymbol{v}_{\tau}$
$\displaystyle=\beta_{2}\cdot\boldsymbol{v}_{\tau-1}+(1-\beta_{2})\cdot\boldsymbol{g}_{\tau}^{2},$
$\displaystyle\hat{\boldsymbol{m}}_{\tau}$
$\displaystyle=\frac{\mu_{\tau+1}}{1-\prod_{i=1}^{t+1}}\boldsymbol{m}_{\tau}+\frac{1-\mu_{\tau}}{1-\prod_{i=1}^{t}}\boldsymbol{g}_{\tau},$
$\displaystyle\hat{\boldsymbol{v}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{v}_{\tau}}{1-\beta_{2}^{\tau}},$
$\displaystyle\boldsymbol{X}_{\tau}$
$\displaystyle=\boldsymbol{X}_{{\tau}-1}-\frac{\eta}{\sqrt{\hat{\boldsymbol{v}}_{\tau}}+\epsilon}\cdot\boldsymbol{\hat{m}}_{\tau},$

RADAM (Rectified Adam by Liu et al. [2020]) optimizer updates the parameters
using the following equations:

$\displaystyle\boldsymbol{m}_{\tau}$
$\displaystyle=\beta_{1}\cdot\boldsymbol{m}_{\tau-1}+(1-\beta_{1})\cdot\boldsymbol{g}_{\tau},$
(99) $\displaystyle\boldsymbol{v}_{\tau}$
$\displaystyle=\beta_{2}\cdot\boldsymbol{v}_{\tau-1}+(1-\beta_{2})\cdot\boldsymbol{g}_{\tau}^{2},$
$\displaystyle\hat{\boldsymbol{m}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{m}_{\tau}}{1-\beta_{1}^{\tau}},$
$\displaystyle\hat{\boldsymbol{v}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{v}_{\tau}}{1-\beta_{2}^{\tau}},$
$\displaystyle\rho_{\tau}$
$\displaystyle=\rho_{\infty}-\frac{2t\beta_{2}^{t}}{1-\beta_{2}^{t}}$
$\displaystyle\boldsymbol{r}_{\tau}$
$\displaystyle=\sqrt{\frac{(\rho_{\tau}-4)(\rho_{\tau}-2)\rho_{\infty}}{(\rho_{\infty}-4)(\rho_{\infty}-2)\rho_{\tau}}},$
$\displaystyle\boldsymbol{X}_{\tau}$
$\displaystyle=\boldsymbol{X}_{\tau-1}-\eta\,\boldsymbol{m}_{\tau}\cdot\begin{cases}\boldsymbol{r}_{\tau}\frac{\sqrt{1-\beta_{2}^{\tau}}}{\sqrt{\boldsymbol{v}_{\tau}}+\epsilon}&\rho_{t}>5\\\
1&\text{else}\end{cases}$

, where $\boldsymbol{r}_{\tau}\in\mathbf{R}^{d}$ is the "leaky" update term,
and $\rho_{\tau},\rho_{\infty}$ is an additional hyperparameter introduced in
RADAM. $\rho_{\infty}$ is initialized with
$\rho_{\infty}=\frac{2}{1-\beta_{2}}-1$. We utilize the RADAM optimizer
implemented in PyTorch.

ADAMW optimizer updates the parameters using the following equations:

$\displaystyle\boldsymbol{m}_{\tau}$
$\displaystyle=\beta_{1}\cdot\boldsymbol{m}_{\tau-1}+(1-\beta_{1})\cdot\boldsymbol{g}_{\tau},$
(100) $\displaystyle\boldsymbol{v}_{\tau}$
$\displaystyle=\beta_{2}\cdot\boldsymbol{v}_{\tau-1}+(1-\beta_{2})\cdot\boldsymbol{g}_{\tau}^{2},$
$\displaystyle\hat{\boldsymbol{m}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{m}_{\tau}}{1-\beta_{1}^{\tau}},$
$\displaystyle\hat{\boldsymbol{v}}_{\tau}$
$\displaystyle=\frac{\boldsymbol{v}_{\tau}}{1-\beta_{2}^{\tau}},$
$\displaystyle\boldsymbol{X}_{\tau}$
$\displaystyle=\boldsymbol{X}_{\tau-1}-\frac{\eta}{\sqrt{\hat{v}_{\tau}}+\epsilon}\cdot(\boldsymbol{\hat{m}}_{\tau}+\lambda\boldsymbol{X}_{\tau-1}),$

where $\lambda$ is a weight decay coefficient or regularization term added in
ADAMW. Loshchilov and Hutter [2019] provided the algorithm. We utilize the
ADAMW optimizer implemented in PyTorch.

###  G.2 Experimental Results According to Datasets

(a) Application Period of the Enforcement

(b) Enlarged plot

Figure 6: The error trends of performance Variation of Adam-Based QSLD based on the application period of the enforcement function: (a) Training error trends of Vanilla CNN on FashionMNIST dataset.(b) Enlarged Training error trends Table 4: Performance Variation of Adam-Based QSLD Based on the Application Period of the Enforcement Function  Period Ratio (%) | FashionMNIST | CIFAR-10 | CIFAR-100
---|---|---|---
| Training | Testing | Error | Training | Testing | Error | Training | Testing | Error
0.5 | 96.05 | 91.04 | 0.92853 | 99.74 | 83.61 | 0.007327 | 98.66 | 44.51 | 0.036558
1.0 | 96.11 | 91.59 | 0.118914 | 99.84 | 83.29 | 0.006766 | 98.62 | 44.38 | 0.032726
5.0 | 96.75 | 91.38 | 0.094954 | 99.87 | 83.39 | 0.006549 | 98.61 | 49.60 | 0.037855
10.0 | 96.95 | 91.59 | 0.090756 | 99.84 | 84.18 | 0.0 | 98.84 | 44.59 | 0.035554
20.0 | 97.05 | 90.84 | 0.084489 | 100.0 | 85.08 | 0.0 | 99.13 | 46.78 | 0.035354
50.0 | 97.82 | 90.64 | 0.051491 | 99.91 | 84.04 | 0.005456 | 98.94 | 48.49 | 0.029179
100.0 | 99.46 | 90.01 | 0.104510 | 99.87 | 83.39 | 0.010629 | 98.81 | 46.76 | 0.044370

FashionMNIST The FashionMNIST dataset is a drop-in replacement for the
original MNIST dataset, which consists of handwritten digits. The FashionMNIST
dataset contains 60,000 grayscale images of 10 different fashion categories,
each with a 28x28 pixel representation. The ten fashion categories in
FashionMNIST include T-shirts/tops, trousers, pullovers, dresses, coats,
sandals, shirts, sneakers, bags, and ankle boots. Each image in the dataset is
associated with a corresponding label indicating the category of the depicted
fashion item.

Simple vanilla multilayer networks, equipped with well-tuned optimizers and
moderately wide hidden layers, can achieve high accuracy in classifying each
category of the MNIST dataset, resulting in minimal accuracy errors. This
poses challenges in meaningfully evaluating the performance of different
optimizers.

However, while the classification test scores for FashionMNIST are higher than
CIFAR-10 and CIFAR-100, standard SGD performs superior to the ADAM optimizer
family in evaluation tests on the FashionMNIST dataset. This result suggests
that the objective function of FashionMNIST exhibits a more convex property
around the optimal point, and previous research (xie_ICLR_2021) has revealed
that the ADAM optimizer may struggle to select flat minima.

Experiments to FashionMNIST The experiments on the FashionMNIST dataset
yielded interesting results. Firstly, similar to the MNIST dataset, the
experimental results showed that the training classification performance
exceeded 90% for all models. However, there was a noticeable performance
difference between the SGD and ADAM optimizers. The SGD optimizer exhibited
better classification performance compared to the ADAM optimizer. As shown in
Figure 3, the error trend indicated that ADAM converged faster initially, but
as the number of epochs increased, SGD gradually reduced the error more
effectively than the ADAM optimizer. In general, once the number of epochs
exceeded 400, the SGD optimizer consistently achieved a training
classification accuracy of 100% regardless of the learning rate. However, the
test classification accuracy reached a limit of around 91.25%.

The proposed QSGLD and ADAM-based QSLD perform better than the conventional
SGD and ADAM optimizer, but they do not exhibit significant improvements on
the FashionMNIST dataset. QSGLD achieves a slight improvement of approximately
0.2% in classification accuracy for both training and testing, while Adam-
Based QSLD achieves an improvement of around 2%. In Figure 3(a), it can be
observed that QSGLD converges faster than SGD due to the similar learning
rate, although the convergence speed is similar. On the other hand, Adam-Based
QSLD exhibits a convergence trend similar to the Adam optimizer. Nevertheless,
Adam-Based QSLD shows lower error trends than conventional ADAM optimizers.

(a) Test for CIFAR-10 on ResNet-20

(b) Test for CIFAR-100 on ResNet-32

Figure 7: Performance Comparison of the Proposed Algorithm on Networks with
Different Depths: (a) When testing on CIFAR-10 dataset, the algorithm was
evaluated on ResNet-20.(b) When testing on CIFAR-100 dataset, the algorithm
was evaluated on ResNet-30.

CIFAR10 and CIFAR100 We don’t provide any specific explanation for the
CIFAR-10 and CIFAR-100 datasets. For the CIFAR datasets, separate experiments
were conducted based on the depth of ResNet. This was done to verify that the
proposed algorithm works effectively regardless of the depth of the neural
network model. The experimental results demonstrated the superiority of the
proposed algorithm for all depths of ResNet. As shown in Table 3, when
classifying the CIFAR-10 dataset using ResNet-50, QSGD outperformed SGD by 8%
in terms of test accuracy.

As depicted in Figure 4, QSGLD exhibited significant improvements in both
convergence speed and error reduction compared to the conventional SGD
methods. On the other hand, Adam-Based QSLD showed a performance advantage of
approximately 1.5% for test accuracy.

Similar trends were observed for the CIFAR-100 dataset. QSGD demonstrated a
performance advantage of around 11% over conventional SGD methods for test
accuracy. In contrast, Adam-Based QSLD showed an improvement of approximately
1.0% compared to conventional Adam-based optimizers.

The experiments on the CIFAR datasets revealed interesting characteristics of
QSGLD and Adam-based QSLD.

###  G.3 Experimental Results of Changing of Hyper-Parameters

Period Parameter for Enforcement Function  We conduct experiments to analyze
the effect of the period parameter $\tau_{0}$ for the enforcement function.
Regarding the quantization parameter, there were variations depending on the
algorithm, but generally, the size of the search vector was around $10^{-6}$,
so the eta value was set to half of it, which is 524288. Firstly, the optimal
application period of the enforcement function varied depending on the
dataset. For FashionMNIST and CIFAR-10, the best performance improvement was
observed when the enforcement function was applied for about 10-20% of the
epochs. Applying it for longer or shorter periods did not result in
significant performance improvement. On the other hand, for CIFAR-100, the
best performance improvement was achieved when the enforcement function was
applied throughout all the epochs. Since CIFAR-100 has a higher classification
complexity than FashionMNIST or CIFAR-10, it is considered optimal to
integrate the enforcement function with a measure that can assess problem
complexity, such as the Fisher Information Matrix, rather than using it as a
function of time. Regarding another hyperparameter, $\kappa$, no significant
performance variations were observed with changes in its value.

##  Appendix H Conclusion

In the supplementary material, we provide detailed proofs of the theorems and
additional propositions presented in the submitted manuscript. Additionally,
we present comprehensive information on the experiments conducted to validate
the proposed quantization algorithm.

Additionally, we intended to upload the test code to platforms like Github and
provide the link in the Supplementary Material. However, due to a recent
policy change on Github, anonymous uploads are no longer possible. Therefore,
we had no choice but to include the code in the Supplementary Material.

###  H.1 Paper Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope?

Answer

Yes

    2. (b)

Have you read the ethics review guidelines and ensured that your paper
conforms to them?

Answer

Yes

    3. (c)

Did you discuss any potential negative societal impacts of your work?

Answer

Yes : The submitted manuscript mainly illustrates a theoretical aspect of a
learning equation.

    4. (d)

Did you describe the limitations of your work?

Answer

Yes : More detailed, we describe the limitation of our work in the
supplementary material.

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results?

Answer

Yes

    2. (b)

Did you include complete proofs of all theoretical results?

Answer

Yes : In supplementary material, we provide.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)?

Answer

Yes : We provide the code and data on the Github. We write a correct URL about
the codes in the supplementary material. Moreover, we write the instructions
for reproduction of experimental results on "README.md" on the URL.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)?

Answer

Yes : In the manuscript and supplementary material, we specify the main
parameters for the model. More detailed information is in"README.md"

    3. (c)

Did you report error bars

Answer

No : It is unnecessary for the manuscript.

    4. (d)

Did you include the amount of compute and the type of resources used (e.g.,
type of GPUs, internal cluster, or cloud provider)

Answer

Yes : we write out those on the "README.md"

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators?

Answer

Yes : We wrote codes originally. We use the CIFAR-10 as experimental data set.
Additionally, we use the ResNet model and we cite the creator’s work in the
paper.

    2. (b)

Did you mention the license of the assets?

Answer

No : According to the illustration of the CIFAR-10 data (URL:
https://paperswithcode.com/dataset/cifar-10 ), there is not any information of
the license.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL?

Answer

No : There is not any new assets.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating?

Answer

No : Since we used CIFAR-10 data set and the well-known model ResNet, we
thought it is unnecessary to discuss.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content?

Answer

No : We did’nt use any data that contains personally identifiable information
or offensive content.

  5. 5.

If you used crowd sourcing or conducted research with human subjects…

Answer

No : We never used crowd sourcing or conducted with human subjects to our
work. Therefore, we disregard the following items.

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable?

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable?

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation?