Effect of Random Learning Rate: Theoretical Analysis of SGD Dynamics in Non-Convex Optimization via Stationary Distribution
Authors: Naoki Yoshida
Shogo Nakakita
Masaaki Imaizumi
Venue: Accepted by TMLR ()

Abstract: We consider a variant of the stochastic gradient descent (SGD) with a random learning rate and reveal its convergence properties. SGD is a widely used stochastic optimization algorithm in machine learning, especially deep learning. Numerous studies reveal the convergence properties of SGD and its theoretically favorable variants. Among these, the analysis of convergence using a stationary distribution of updated parameters provides generalizable results. However, to obtain a stationary distribution, the update direction of the parameters must not degenerate, which limits the applicable variants of SGD. In this study, we consider a novel SGD variant, Poisson SGD, which has degenerated parameter update directions and instead utilizes a random learning rate. Consequently, we demonstrate that a distribution of a parameter updated by Poisson SGD converges to a stationary distribution under weak assumptions on a loss function. Based on this, we further show that Poisson SGD finds global minima in non-convex optimization problems and also evaluate the generalization error using this method. As a proof technique, we approximate the distribution by Poisson SGD with that of the bouncy particle sampler (BPS) and derive its stationary distribution, using the theoretical advance of the piece-wise deterministic Markov process (PDMP).

Published in Transactions on Machine Learning Research (08/2025)
Effect of Random Learning Rate: Theoretical Analysis of SGD Dynamics in Non-Convex Optimization via Stationary Distribution
Naoki Yoshida
n-yoshida@g.cccd ecc. www.g./ky......ooooooooo....o... ac.jp
The University of Tokyo, Bunkyo, Tokyo, Japen.
Shogo Nakakita
nakakita wwkckkttallg.ecc..v-oko....oo
The University of Tokyo, Bunkyo, Tokyo, Japan.
Masaaki Imaizumi
mmaiiaumi@@g.ccc.utoooo
The University of Tokyo, Bunkyo, Tokyo, Japan.
RIKEN Center for Advanced Intelligence Project, Chuo, Tokyo, Japan
Reviewed on OpenReview: https: // http////ppereeeeeee//mee net/ forum? RPtKNNN9ZK
Abstract
We consider a variant of the stochastic gradient descent (SGD) with random learning rate and reveal its convergence properties. SGD is widely used stochastic optimization algorithm in machine learning, especially deep learning. Numerous studies reveal the conver- gence propertics SGD and its theoretically favorable variants. Among these, the analysis of convergence using a stalionary distribution updated parameters provides generalizable results. However, to obtain a stationary distribution, the update direction of the parameters must not degenerate, which limits the applicable variants of SGD. In this study, consider novel SGD variant, Poisson SGD, which has degenerated parameter update directions and instead utilizes random learning rate. Consequently, we demonstrate that a distribution of a parameter updated by Poisson SGD converges to a stationary distribution under weak assumptions on a loss function. Based on this, we further show that Poisson SGD finds global minima non-convex optimization problems and also evaluate the generalization error using this method. As proof technique, we approximate the distribution by Poisson SGD with that of the bouncy particle sampler (BPS) and derive its stationary distribution, using the theoretical advance of the piece-wise deterministic Markov process (PDMP).
1 Introduction
Stochastic gradient descent (SGD) stands out widely employed optimization algorithm in machine learn- ing. It falls under the category of stochastic optimization, where parameters are updated with randomness from the mini-batch sampling. SGD is valued for two main reasons in optimization: (i) it is memory-efiiiiet and requires only low computational resources by updating parameters from fraction of the training data at each itcration (Bottou] 1991), and (ii) models optimized with SGD have less generalization error than those optimized by other algorithms such as gradient descent (GD) for neural networks (Wu al. 2020; Zhu al. 2019). Owing to these advantages, SGD has been of the standard methods for training deep learning models (offer et al. 2017 Keskar et al. 2016 Zhu et al. 2019
To understand the properties of SGD, the characteristics of parameters updated by SGD or its variants have been actively studied. As for the usual SGD, Garrigos Gower (2023) surveyed the results about the convergence rate of SGD in convex and non-convex sottings. also mentions the global convergence property of SGD under the strong convexity setting, Li al. (2017): Jastrzebski et al. (2017) clarified that the parameter updating process of SGD be approximated by stochastic differential equation. Zhu

---

Published in Transactions on Machine Learning Research (08/2025)
Stationary distribution Hg (moderate temperature: small ()
Stationary distribution Pa (low temperature: large 3)
Non-convex Loss
L (0)
Density
Density
Figure 1: Approach using stationary distributions. Under the non-convex loss (g) of a parameter 0 (the left panel), we consider a distribution of parameters 0 generated from an algorithm with an inverse temperature B, which converges to the stationary distribution μ4s with sufficienlly large number of itcrations (the middle panel). ). By varying B, the distribution μą is concentrated on the global optimum of (0) (the right panel).
et al. (2019); Nguyen et al. (2019) discussed the relation between the random noise of SGD and the escape efficiency from the sharp minima of the loss function. One example of a variant of SGD is stochastic gradient Langevin dynamics (SGLD), which is an extension of SGD that adds Gaussian noise to the update formula of SGD. Raginsky et al. (2017) analyzed the dynamics of stochastic gradient Langevin dynamics (SGLD)
as a variant of SGD and proved the parameters optimized by SGLD converge to the global minima of the generalization error. As another example, Jastrzebski et al. (2017); He et al. (2019); Mandt et al. (2017) analyzed the dynamies of SGD with a constant learning rate under the assumptions that the noise of SGD
the gradient induced by the mini-batch sampling is isotropic, and derived the probability distribution of
the parameters obtained by SGD. Latz 2021 analyze SGD both in the case of the constant learning rate and of the decreasing learning rate.
Among the mothods analyzing the properties of SGD, one of the most general approaches to study a stationary distribution of parameters updated by SGD and its variants. The stationary distribution is a distributtio that remains unchanged when the parameter is updated by one step. Analysis based on stationary distributions is an approach that aims characterize the probability distribution rather than the exact values of the updated parameters. This method has been employed by researches such as Raginsky let al. 2017) or Dieuleveut et al. (2020) for analyzing machine learning models with non-convex loss functions. Specifically, it involves demonstrating that distribution of paramcters updated by the algorithm under sulficient iterations converges to a slationary distribution that assigns mass across the entire parameter space. Subsequently, by adjusting an inverse temperature parameter that affects its shape, the stationary distribution can be concentratod around the global minimum. See Figure [ for illustration. It useful in theoretical analysis, because (i) it can analyze the global convergence of the optimization algorithm, and (ii) it be applied to wide range of loss functions regardless of its convexity.
Despite the above advantages, there are not many SGD variants to which stationary distribution analysis can be applied. This is because, to use the analysis by a stationary distribution, it is required that the direction of parameter updates by an algorithm does not degenerate; in other words, there must be no directions that are not being explored, Examples such variants are (i) SGLD (Welling & Teh 2011 Dalalyan 2017 Durmus & Moulines 2016), which adds a Gaussian noise to the parameter update of SGD and (ii) Gaussian SGD (Jastreebski et. al.] 2017 He al. 2019; Mandt et al. 2017), which assumes that. the noise of SGD the gradient induced by the mini-batch sampling is non-degenerate Gaussian. In contrast, the parameter update of SGD degenerates in many practical cases, such as deep learning (Zhu et al. 2019 Nguyen et al. 2019 Simsekli et al.] 2019). We remark that we focus on the degeneracy of the update direction of SGD, not on the distribution of it since there is no clear agreement that gradient noise follows a particular distribution (the definition of degeneracy is in Remark 3p. Hence, there is a gap between the variants of SGD considered in the theoretical analysis and the empirical facts about. SGD. This gap fosters the following question:
Do parameters optimized by a variant of SGD have a stationary distribution even if the update direction degenerates and if so, what is the form of at
2

---

Published in Transactions on Machine Learning Research (08/2025)
1.1 Our Contribution
We theoretically prove that a variant of SGD has a stationary distribution even if the update direction degenerates. Specifically, we develop novel SGD variant with random learning rate, which follows the Poisson process depending on mini-batch gradient. We call the variant Poisson SGD, and prove that the distribution of parameter updated by Poisson SGD converges to stationary distribution. As result, we provide a positive answer to the question posed above: even with a degenerated parameter update, we can construct a variant of SGD that reaches a stationary distribution by using a random lcarning rate.
Our specific contributions are as follows. We consider the empirical risk minimization problem and prove the following results under weak assumptions on the loss function such as absolute continuity: (i) the distribution of the parameters updated by Poisson SGD converges to a stationary distribution, and (ii) output of Poisson SGD converges to the global minima of the empirical risk, applying the stationary distribution while controlling the inverse-temperature parameter. Furthermore, we evaluate the generalization error of the updated parameter for prediction with unseen data by studying an expectation of the risk function in terms of the obtained stationary distribution.
On the technical side, we utilize an algorithm called the Bouncy Particle Sampler (BPS) to demonstrate the convergence to the stationary distribution by Poisson SGD. BPS is piecewise deterministic Markov process (PDMP) that achieves ergodicity using stochastically occurring jumps (Daiis] 1984 1993). In our proof, we show that the distribution of parameters updated by Poisson SGD can be well approximated by that of BPS, and we concretely construct the stationary distribution using the theory of BPS.
1.2 Related Work
There are many works which investigate the stationary distribution of SGD) or its variants. Dieuleveut et al. (2200g Chen et al. (2022) derived the stationary distribution of the parameters obtained by SGD when the loss function is strongly-convex, through the theories about Markov processes. The parameters obtained through the SGLD algorithm are theoretically proven to converge to the Gibbs distribution and generalize well (Raginsky et al.) 2017). He et al. (2019) and Mandt et al. (2017) assumed the noise of SGD is Gaussian whose covariance matrix is constant and approximate the process of optimization through SGD by Ornstein- Uhlenbeck process and derive its stationary distribution. Gradient Langevin dynamics (GL.)) which is a full-batch version of SGLD, can also be seen as variant of SGD which assumes that the noise of SGD is Gaussian with covariance matrix of constant multiples of the identity matrix. Like SGLD, it converges to stationary distribution even in non-convex scenarios (Dalalyan 2017 Durmus & Moulines 2016).
In terms of a random learning rate, there are several empirical studies. Musso 2020 investigated the dynamics of SGD with a random learning rate by analyzing the stochastic differential equation and its Pokker-Planck equation. Blier et al. (2019) showed experimentally that SGD with random learning rates performs well in optimizing deep neural networks. Note that these studies and ours have several major differences. The first difference is in the design of learning rate. Our method considers Poisson processes, whereas existing methods consider uniform distributions and heterogeneous learning rates for each subneural network. The second difference is the objective of the study. We aim to evaluate global convergence, while existing studies aim at interpretability, speed of convergence, etc., and have very different motivations.
As for BPS, Deligiannidis et al. (2019) and Durmus et al. (2020) proved that the parameters updated by continuous-time BPS converge to a stationary distribution and derived the concrete form of the stationary distribution and its convergence rate. Shhellock & Thiery (2022) clarified the relation between discrete-time BPS and contimuous-time BPS.
1.3 Notation
For a natural number a e N, we define [a] := 2 which is no more than z. La is a d-dimensional identity matrix. (a, b) mcans the inner product in Euclidean space, i.e., sum of the product of each component. || |l and ||- mean the vector norms which represent 1-norm and 2-norm respectively. gd-1 is unit sphere in Rd. For probability measures P, P Rd and
.......,, a}. For a real 2 E R, [a] denotes the largest integer
3

---

Published in Transactions on Machine Learning Research (08/2025)
p E [1,00], the p- w-ssserstein distance is defined as (y P*) inf pe || ||= where [T, P') is set of coupling measures between P and P.. || - Pt pTV denotes the total variation of P - -P. For a compact set θ, we denote diam(@) = , 110 - 0211. For a random variable X E X, Ex [X] denotes the expected value with regard to X, i.c., Ix x (dx), where μxx is the probability measure of X. 1[] denotes an indicator function, which takes if the condition in the bracket is satisfied, and 0 otherwise. We denote a+ = max a0. For a E R and 0 E Rdd 0 mod a means calculating modulo a for every element of 0. B : R x R + I. denotes the beta function, i.e,, B(x, y) = So 1=11(1 - 1)w- r R -R-4 + denotes the gamma function, i.e., [(x) Jo d=-
=211ddT(2,2
2 Preliminary
2.1 Problem Setup: Empirical Risk Minimization
We consider the following stochastic optimization problem. Let Z be a compact sample space, and consider a probability measure P. on Z. Suppose that we observe n samples z {z..... 2n C Z, that are independently and identically generated from the measure P.. Using the samples, consider empirical risk with a loss function. Let θ C ng be parameter space. With non-convex loss function f Z θ + R, consider the following empirical risk with the samples:
(0)
1
Σ 2=1
((2))) 6 e.
(1)
In this study, we consider a torus (R/aZ)d as the parameter space O. Here, > 0 is a periodicity parameter. Also, we define W == (aaam())=av/
Our goal is find a global minimum of the empirical risk L,(,), which is defined as a parameter 8* that satisfies Lg(0)) E ming'ee Lz()).
Remark 1 (Motivation of torus parameter space). We discuss the motivation for employing the torus.
First, the use of a torus parameter space is a widely adopted technique for simplifying otherwise unnecessarily intricate arguments in the analysis of stationary distributions. Specifically, if we set θ as Euclidean spaces or hypercubes, the analysis often becomes technically cumbersome due to boundary effects or additional projection steps after updating the parameters. In contrast, the torus provides a setting in which these peripheral issues can be bypassed, enabling a focus the mathematically essential aspects of the argument. As result, the torus has been utilized in wide range of theoretical studies. In the context of stochastic processes, Nickl & Ray (0200) Faggionato et al. (2009); Peutrec et al. (2022) considers the torus parameter spaces, and Monmarchè (216)) does in the same way in the analysis of optimization. The generality of these assumptions has been broadly acknowledged in the literature.
Second, when the periodicity parameter of the torus is sufficiently large, the torus becomes practically indistinguishable from the Euclidean space in terms of behavior relevant to applications. As we will show later, our results hold for all values of a. Therefore, by choosing a to be sufficiently large, the analysis becomes nearly equivalent to that conducted in Rd Lee 2012)
2.2
Gradient Descent Algorithm and Variants
To find the global minimum 8* as defined in Section 2.1 stochastic gradient descent (SGD) with momentum.
we often use the optimization algorithm called
2.2.1 General Form of Stochastic Gradient Descent
We give a formal definition of SGD with a momentum term associated with empirical risk (0) in 1 Let K E N be the number of iterations. The SGD with momentum generates a sequence of O-valued random parameters 0,...., 0x and valued random vectors Uk. by the following procedure.
Let 8g be an arbitrary parameter for the initialization, uy E Id be an initial velocity vector, and m E [n] be number of sub-samples, i.e., the batch size. Suppose that observe samples {21,.. En i.e. the
4

---

Published in Transactions on Machine Learning Research (08/2025)
full-batch. For ls- = ...,, K, we uniformly sample integers _(A) = fi, km from [n] with replacement, which is called mini-batch sampling with the batch-size m. We define associated mini-batch risk
(0)
Σ (zz
m
Then, with initial values Bu E O and up R the SGD with momentum generates the parameter and the velocity vector by the following recursive formula for ko = K:
0₂ 8x- 0k-1 and Up Uk-1 ag (
(3)
where ?) 0 is learning rate and ag E I is momentum coefficient. This form is generic and be identical to other forms of SGD with momentum QQian 1999 Sutskever et al. 2013 by adjusting the parameters and a.
Remark 2 (Gradient Noise). For the sake of technical discussions below, define notion of gradient clm..) (0) = = (0) (0) for k = I,...,N N and 0 E O, which caused by sub-sampling of the noise Sk
SGD. If one assumes that <! (0) follows centered Gaussian distribution with idcntity covariance, the SGD corresponds to the gradient Langevin dynamics (GLD). However, it is empirically observed that the covariance matrix of the gradient noise often degenerates (Zhu et al., 2019 Cheng et al. 2020 HaoChen et al. 2021). In addition, there is still much discussion on a distribution that gradient noise follows, e.g. Simsekli ct al. 2019 and Battash et al. (2024) reports the Gon-Ganssyy of the gradient noise in empirical studies. Due to these situations, we do not consider a full-rank covariance matrix nor a particular distribution of the gradient noise.
Remark 3 (Degeneracy of the gradient noise). We briefly explain the degeneracy of the gradient noise. Since the covariance matrix of the gradient noise with the batch-size m is written as m ">=((((( (I)(()) 0) - (O)), where each term in the matrix is no greater than m. Hence, in the over parametermeee models like neural networks, the matrix becomes rank-deficient, which we refer to as degeneracy of the noise.
rank-1 matrix, the rank of a total covariance
3 Our SGD Variant: Poisson SGD
In this section, we introduce our algorithm, Poisson SGD, which is variant of SGD with random learning rate and momentum coefficient a. We design our method so that the parameter can search the whole parameter space owing to the design.
We describe the random learning rate. In preparation, we define the following exponential distribution function with function f: + Rd and parameters 0 O, E $d-1,
B((()0,0):= exp (-/ (m/ rr), 0),0) ())))))+))))))+))()))
where Cp is some constant. Then, for each update 1,.... K, we design the random learning rate me following the exponential distribution:
P(m 2 t) E(3VI (-), O2-1, 0R-1,
(4)
where 3 0 is the hyperparameter of Poisson SGD, called an inverse temperature parameter.
Second, select the momentum coefficient ay for each A L,.., as
(k) (8x), Uk-1)
= 2 (V((k) (0.))1
+ Ca.
(5)
where C. is the hyperparameter. While C. has the function of enhancing the effect of the gradient for practical use, we set. C.. 0 in the theoretical analysis of this paper (in experiments in Section 7 we set
5

---

Published in Transactions on Machine Learning Research (08/2025)
C > 0). This setup keeps the length of the velocity vector constant as ||eg]] for every k (See Proposition in Appendix), and only uses its angle to update the parameters. We update the parameter by changing ' and Og in every iteration. In updating 02, we consider modulo a, which means calculating modulo a for every clement of the vector, in order to restrict the parameter space to a torus T (R/aZ)) The pscudo-code of Poisson SGD shown Algorithm
Algorithm Poisson SGD
Initialize (fo, (1) as ||oo|| 1.
for k 2,.. K do
Sample ((k) c In] and obtain VL (6x) as 2
Sample The 4
Obtain 0g as 0g (0%-1 7 1) mod a.
Obtain &k as Up = uk-1 as VLg (0x) with og as (5]_
6:
7: end for
Return (0K, UK).
The algorithm is designed to effectively explore large regions of the parameter space e Specifically, the update direction is determined by the velocity vector Uk normalized by ar as (5, and the size of the update is randomly set by the random learning rate The 4 When the gradient vL2 is small, the learning rate Th is chosen to be large, thus the updated parameter tends to escape local minima or saddle points. Figure 2 illustrates that Poisson GD, which we refer to as the full-batch version of Poisson SGD, explores a wider parameter space and discovers the global minimum owing to the random learning rate, while the parameters updated by GD converge the local minimum. Here, we set the learning rate GD as 1j = 0.02 and the hyperparameter of Poisson GD as Cp 100 and 10000. We remark that a small amount of hyperparameter tuning was necessary to obtain this result.
Figure The comparison of the trajectories of GD (with a fixed learning rate) and Poisson GD (with the random learning rate) in optimizing the function x 4x 36z + y². Poisson GD represents replacing the mini-batch loss L. by the full-batch loss Lz in Poisson SGD, where we set Lg(2, (æ, y) = x - 4x 36x 36x2+y²² represents local minimum and the point (6, 0) identified as the global minimum. green point indicates the initial position, black line repre- sents the trajectory of GD, and red line repre- sents the trajectory of Poisson GD.
2
The point (-3.0)
-4
X
Remark (Moments of Poisson SGD). We claim that even if the learning rate is random, the actual updates are not too large, by studying its moments. That is, if Cp sufficiently large, there is little chance sampling large learning rate 77, since the first and second moments of m are given as [mm]] S Jo exp(-Cpt)dt J. and E[ng] E Eim < So 2s exp(-Cps)
1. By this property, we can avoid the case in which m diverges. In addition, even if large п is sampled, the parameter does not exit from the parameter space since consider torus the parameter space.
Ch. oz.

---

Published in Transactions on Machine Learning Research (08/2025)
4 Convergence Theory for Poisson SGD
We provide thcorctical results the convergence of Poisson SGD (Algorithm 1 Our main interest is distribution of the generated parameter 0x by Poisson SGD associated with the empirical risk minimization problem.
4.1 Stationary Distribution of Poisson SGD
In this section, we show that the parameter 8x by the Poisson SGD follows a stationary distribu- tion. Formally, we define the stationary distribution the Markov process. In preparation, we utilize the notion of transition probability Q00, dw) from a distribution po( to another pi( on O that is, pi(w) - Se Q00, (d)O holds.
Definition 1 (Stationary distribution). Let Q dw) be the transition probability of a Markov process in Tf the following equation holds, we call the probability distribution x =0) a stationary distribution of the Markov process:
r(dw) L Q(0, (wo)x
A stationary distribution is useful notion to represent limit of the parameter distribution, and it enables to analyze where the parameter converges by algorithms. For example, see the theoretical framework to analyze stochastic optimization algorithms by Raginsky et al. (2017).
4.1.1 Assumption
We provide several principal assumptions. First, we consider the basis assumptions on the loss function -(: The following conditions are fairly general for the analysis stochastic optimization algorithms, c.g. Bertazzi et. al. (2022).
Assumption 1 (Loss function). The loss function 8: Z x θ + Rzo satisfies the following conditions:
0) is absolutely continuous and differentiable with respect to 0 E O for every z E Z.
0) continuous in and for all 0 E and = Z.
These conditions satisfied by large class of models, such as linear regression model or deep neural networks whose activation function is a sigmoid function Tanh. We define an upper bound Me == max [|Vo[(2;)) (),, which is justified from the second condition on the compactness of θ and Z.
4.1.2 Statement of Convergence
Let Pa.K be a distribution of the output 0g from the Poisson SGD in Algorithm | with the given dataset We discuss the convergence of Pz,K as K increases.
In preparation, we define a probability measure on for arbitrary 3, O, whose density is written as
112 (d0) x (3Ms + 1 [a3 exp(=31x(0))d0,
(6)
where a, =
with r(2) = 1.0h 1------- The probability measure 16 is concen-
trated around the global minima of (z),), since the dominant exponential term (x)( in (6 increases in (0). In addition, as the inverse temperature parameter 3 increases, the measure Pz around the global minimum.
(8,=) concentrates
We show our results on the convergence the stationary distribution. The discrepancy mcasured by the Wasserstein distance -.)..). We remark that this theorem is the integration of Theorem and Theorem appearing later in Section 5 Recall that defined W == diam(O).
7

---

Published in Transactions on Machine Learning Research (08/2025)
Theorem 1 (Stationary distribution of Poisson SGD). Fir arbitrary B, O. Suppose Assumption holds. We set the Cp 1/e. Then, for any K E N, there erists k(8,e, e, d) E (0,1) such that we have
Wi(Mx,K -2 I <AVoKe+ B.iieetWwKBBBB.. kK(,E,,)),
(7)
Moreover, if H(B,e,d) d) satisfies limx- k(B, (,8B8/KK)) = 0 with some 8 > 0, there crists a sequence E = EK 0 as K + oo such that Wi (M (8.c) (1) as K -+ holds.
This theorem shows that the parameter distribution Mz.K by Poisson SGD converges to the stationary distribution Uiz (B.cc) owing to the random learning rate 4 This is contrast to ordinary SGD, which is not shown to converge to stationary distribution. Further, Poisson SGD does not make any assumptions on the gradient noise Sk e(n.m) in Remark unlike SGLD, which converges to stationary distribution by introducing Gaussianity in the gradient noise.
The right-hand side in 7 shows an approxinatóon-coplettti trade-off of Poisson SGD described as follows.
In preparation, we will introduce a certain stochastic process to achieve the stationary distribution pz (8.e) (detail is in Section 5 The first. term of (7) describes an approximation error of Poisson SGD to the stochastic process. The second term of ! denotes convergence error of the stochastic process to the stationary distribution _,3,2,, which reflects the complexity of the stochastic process. the stochastic process and controls the balance between the approximation error and the complexity error.
a parameter for
We further discuss the additional assumption limx- <3, K, d)k 0. This condition is related to the convergence rate of the approximated stochastic process of Poisson SGD, Although the explicit form of x(3, 8/K, is not clarified in our case, there is common example having its explicit form. One example is SGLD: Raginsky et al. (0177) shows that a form of x(3, K, d) can be calculated, because SGLD is reduced to the Langevin process.
Remark 5 (Form of k(3,e,d)). We discuss form of k(8, d) of other related algorithms, although we could not achieve the explicit form of s<B, d) of Poisson SGD. In the case of Langevin dynamics with the setting of Raginsky et al. (2017), s(3,s, d) is Mcr.sky/8(2 + d)), where cLs is the logarithmic Sobolev constant. On the other hand, explicitly deriving a(3,e.d) for a class PDMPs a challenging task as described in Deligiannidis et al. (2019); Durmus et al. (2020), as well as that of Poisson-SGD.
Remark 6 (Comparison with SGLD). We discuss the difference between Poisson SGD and SGLD, which is another method achieving stationary distribution. First, while SGLD adds Gaussian noise to the update formula of SGD, Poisson SGD does not have additive noise. The second difference is the form of the stationary distribution. A sstationayy distribution of SGLD the Gibbs distribution, and that of Poisson SGD has a different form 6). This difference derived from the random learning rate of Poisson SGD.
Remark 7 (Relation to flat minima). From Theorem 1 we can state the property of Poisson SGD being easier to go to the flat minima than the sharp minima. We consider the probability of existence around a flat minimum 0 E ④ and a sharp minimum 82 E θ, when we find that, due to the shape of the distribution, measure of an e-neighborhood of 0g is greater than that within e-neighborhood of 0z. Hence, we claim that Poisson SGD also tends to favor flat minima.
4.2 Global Convergence
We discuss the global convergence statement, that is, the empirical risk (0x) with Poisson SGD is mini- mized with high probability, We consider the additional assumption for the loss function &: Assumption 2. With some c > 0, supzez
ve(=; 02)1 ca 10: -2ll holds for every 01 8g O.
Then, we obtain the following global convergence theorem.
Theorem 2 (Global convergence of Poisson SGD on empirical risk). Fix arbitrary 8, > 0. Consider Poisson SGD in which Cp 1/e. Let the upper bound of Wi Wi(psk pzz ((+z)) obtained in Theorem 1 be dx (B, Suppose Assumption and hold, and define B == supzez [[][(=))] and c2 a + B.
8

---

Published in Transactions on Machine Learning Research (08/2025)
Then, it holds that
eW2 log (1+ min L2(0) S Wor d) log dEB
/d
adC2 Mr
B (4x0k))
(8)
Theorem states that we can make [[xx((0x)] be arbitrarily close to mingee (0) by selecting large 3, provided that we can make dx e,,e,d) arbitrarily small by the choice of and K in spite of f.. Intuitively, Poisson SGD achieves global convergence by appropriately adjusting the learning rate and momentun co- efficient based the shape of the loss function at the current location. Poisson SGD achieves the global convergence by the similar approach of global convergence of SGLD by Raginsky et al. 2017
The right-hand side of S is divided into two terms. The first term expresses the distance between the parameter and its stationary distribution. The second represents the degree of concentration the stationary distribution f (0,s) on the global optima. The higher the inverse temperature B, the more the term decrcases.
5
Proof Outline
5.1
Overview
We give an overview a proof of Theorem [ property of the piece-wise deterministic Markou process (PDMP) (Davis 1984 1993), and (ii) the ergodicity of bouncy particle sampler (BPS) (Peters & de With 2012). The PDMP is class of Markov processes that behave deterministically for some period and jump randomly, which easily converges to stationary distribution. BPS is a stochastic algorithm in the class of the PDMP. This BPS is virtually constructed to prove the convergence of PSGD and is not actually computed in this study. Therefore, there is no need to consider the computational cost of this BPS.
preparation, we present several key concepts: (i) the
We show the statement by the following steps: (I) We show that the distribution of the parameter by Poisson SGD is sufficiently close to that of parameter by BPS. We show this claim by using the approximation theory PDMP (Theorem 3 and (II) We derive stationary distribution and the ergodicity of BPS, following previous researches (Theorem
5.2 Design of BPS
We introduce BPS, which one of the most popular algorithms in PDMPs, and actively studied terms of MCMC algorithm (Deligiannidis et al. 2019 Bouchard-Cött et al. 2018 BPS generates a sequence of parameters | C θ and velocity vectors [0x] C IRd in its recursive manner, as shown in Algorithm 2 Let (0o, 00) be the initialization. For the k-th iteration, BPS generates a learning rate îl from an exponential distribution whose intensity depends on the previous pair (0k-1, 6)-1) and the positive constants Ayel and Cg. In the same way as Poisson SGD, we calculate modulo a when updating 0g for restricting the parameter space to a torus. After obtaining the parameter Ōx, we consider the stochastic update of the velocity vector. That is, with the probability
B V 0p-1) CB Pk B(VL,(Oa), Bx-1)+ Aref + CB
(9)
update the velocity vector with the gradient of the full-batch loss VLz, otherwise with the sample from the uniform distribution on gd-1, The former update is called reflection, and the latter is refreshment. We
remark that || is constant for k = 1,2, ...,, K in the same way as Poisson SGD (See Proposition 7 in
Appendix).
5.3 Connect Poisson SGD and BPS
We show that the output distribution of Poisson SGD and that of BPS sufficiently close as follows:
9

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm 2 Bouncy Particle Sampler
1: Initialize (0,, 0o) as | = 1.
2: for k == 1,,, ..... K do
Sample 7h as πi P(ñk 21)= exp (- (1 + 0x-1) + Aret + CB )dr)
Update 02 O2 (Ox-1- 7 Oh- mod
5: With probability P&e as 19) update og as
(L (0k), 0k-1) Lo (0x)
8h Uh-1
1 (0x))1²
Otherwise, update ih as Dg Unif(S end for Return (0x, Rk)
Theorem 3 (Distance belween Poisson SGD and BPS). Fir arbilrary B, > As for Poisson SGD, sel Cp = 1/s. As for BPS, we set Are and CB as Azet + CB BM + 1/2. Let the distribution of the obtained parameter by Poisson SGD and BPS be PzK and Pz,K respectively. We set the same initial value between Poisson SGD and BPS. Then, the Jollowing holds:
Wilpa, PaR)) S dVdKe.
For proving this theorem, we calculate the distance between Poisson SGD and BPS by one-step update. Then, we simply accumulate this error for times. In this discussion, we mainly use the property that if learning rate 77 and fi are small, the difference of vg and Ū. is also made to be small. This type of discussion is also used in Raginsky et al. (2017).
5.4 The Stationary Distribution and Ergodicity BPS
We investigate the stationary distribution and ergodicity of BPS. First, we define the term ergodicity. Definition (Frgodicity). We consider the discrete-time Markov process. Tf the process converges unique stationary distribution, call the process has the ergodicity. Especially, if the ergodic process converges to its stationary distribution by the exponential rate about the number of iteration k, the process is called exponentially ergodic.
Without ergodicity, the stochastic process may converge to more than one stationary distribution, or not converge to any stationary distribution due stacking to a saddle point in the parameter space. So we have to prove this property when we try to analyze the stationary distribution of stochastic process.
Now, we show our result about BPS.
Theorem 4 (Stationary Distribution of BPS). Suppose that Assumplion holds. Sel the parometer of BPS, Aret and CB in Theorem Then, the distribution Pa,K of the obtained parameters 0g by BPS satisfies the following inequality with some constant k(8,e,) E (0,
(P,6) 1a 11
| I n(8,e,d)
In its proof, we use the discussion in Deligiannidis et al. 2019 which showed that continuous-time BPS converges to the unique stationary distribution =0) x exp (U))) by the exponential rate in TV distance.
6 Generalization Error Analysis
We define an expected risk of f E O, also known the generalization error L(0) = E. [[(2; which measures a prediction performance with unseen data. We calculate the generalization error of the parameter obtained by the Poisson SGD, using the discussion in Raginsky al. 2017
10

---

Published in Transactions on Machine Learning Research (08/2025)
Now, we give results. We define A s [e(200) by following Assumption 1
Theorem (Generalization Error of Poisson SGD). Suppose that Assumption 7 and
& hold. Let Oz be the
parameter obtained by Poisson SGD with Cp 1/E. Then, we obtain the following bound:
Px [B [L(0)]] min L(0)
C² n2
1/2
C²
))
1/4
+ ( log d
eW
+ log (1 1 Mr
all))
c2 (3, 2W
+
3
where dx (3, the upper bound of the Wasserslein distance in Theorem Ca= and C= c, 2BW 2A.
7 Ca 4aalei W + B)/Mr
Theorem 5 states that the expected value of the generalization error of Poisson SGD can be arbitrarily close to its global optima in O by selecting small e, large K, large B, and large n, provided that dx(3,e, e, dd) can be arbitrarily small only by the choice of e and K.
We further discuss a way of improve an order of the generalization bound in Theorem While our bound has the order (((1/n)//4 we can obtain an order O(1/n) by using the dissipativity condition of the loss function, which is used in Raaiinky et al. (2017) for SGLD. The dissipativity condition allows us to derive log-Sobolev inequality for (0),,, which leads the improved sample complexity. We state this fact in the following proposition.
Proposition 6. Suppose that the same condition and selling as Theorem 5 hoold. addition, we assume that the Gibbs distribution U x exp(-3Lz(0)) satisfies the Sobooeye inequality for any dataset == (z,, znb that is, (0) log (() { log (0) S f holds for all smooth functions f and ony (8)
dala z = (=1,..,, )n); where 0 ~ uz and CLS < c:: is constant. Then, the following holds:
B [Bo [T(0x))] min ((0)
6EB
20(3) 3M
(eW2ca,3)
0 (Wixx(3,edd)
W V 20( log (1 + Be + log
n
2
7
Experiments
We give several experimental results to validate our theoretical claim. For all experiments, the detailed set such as the choice of the hyperparameter is described in Section A.2
7.1 Convergence to Stationary Distribution
We consider a distribution of parameters updated by Poisson SGD, then experimentally validate whether the distribution converges to the derived stationary distribution as the number of updates increascs. Specifically, we numerically study whether the distribution Pa,K of parameters generated by Poisson SGD converges to the theoretical stationary distribution fzz (8,c) we have derived.
We describe an outline of the setup. We set d= 2 and consider a parameter 0 == (0,, 02) in the 2-dimensional torus θ (R/aZ)² with a = 20. The loss function is set as ((2;0) = ((0p - 03)=² + (0)- y)), then the stationary distribution (2 (8.e) is well approximated by exp(-3'(00) 02 - 1))), where B' is a constant multiple of B. Hence, the stationary distribution (3.6) concentrates around a set {(0,, 02) θ 0f 02 - 1 = 00. We obtain the numerical distribution He.K of the parameter 0 by Poisson SGD for 10, 100, and 1000 epoch.
Figure 3 shows the distribution M2,K the parameter space θ. We remark that the value of the parameter is in [0. 20) since the parameter space is the torus (R/aZ)² and the tick starts from 10 instead of 0 for the sake of clarity. The contour shows the value of (0} - 03 1)2. As the epoch increases, the parameter sampled from Poisson SGD distributed around a set {0),, 02) E θ 0 - - 11 =0. This shows that the parameter distribution by Poisson SGD converges to the stationary distribution fz
(8.e)
11

---

Published in Transactions on Machine Learning Research (08/2025)
10 epoch
100 epoch
1000 epoch
10
10
10
5
5
5
0
0
15
15
15
10
10
10 10
10
15
10
15
Figure 3: Sample from Poisson SGD for 10 (left), 100 (middle), and 1000 (right) epochs.
(B.s) and the distribution Also, Figure shows the Wasserstein distance between the stationary distribution μ of parameters learned by SGD Poisson SGD. The horizontal axis represents the epochs and the vertical axis shows the Wasserstein distance. While the Wasserstein distance does not converge in the SGD case, it converges toward zero in the Poisson SGD case. This result indicates that the parameter learned by Poisson SGD has the distribution Hz.K which converges to the stationary distribution # (8,6)
7.2 Optimization and Generalization Performance
25
We verify the training and generalization performance of Pois- son SGD a practical situation. Note that our aim is not to develop effective method with high generalization per- formance, but to develop method that guarantee global convergence.
Poisson SGD
Wassersven
15
10
0
100
800
We conducted experiments with several datasets and models. First is the MNIST dataset (Deng. 2012 on a fully connected neural network of 4 layers, and each layer has 200 units and the sigmoid activation function. Second the CIFAR-10 dataset [Krizheskyy et al. 2009)
Figure 4: Wasserstein distance from the dis- tribution of paramcters updated by SGD (orange) and Poisson SGD (blue) to (z (3.e)
convolutional neural network of 3 layers with the ReLU activation function, 3 kernel, and the dropout rate 0.25. Third is the CIFAR-100 dataset (Krizhevsky et al. 2009) VGG16
(Simonyan & Zisserman 2015). And the last is the CIFAR-100 dalaset on ResNet18 (He el al. 2015). We compared the performance of Poisson SGD with several existing optimization methods.
We display the overall result in Figure 5 In all the cases, the performance of Poisson SGD is better or comparable that of other methods.
8 Conclusion
We developed a new variant of SGD, Poisson SGD, whose search direction degenerates and derived its stationary distribution by incorporating a modification on the learning rate. The parameters trained by Poisson SGD are close enough to the global minima take advantage of convergence to the stationary distribution. The gencralization error is also evaluated. Our study suggests that even local scarch methods such as SGD may be able achieve global convergence by adding certain randommess. Since our work largely depends the modification of the learning rate, eliminating this dependence is interesting open question. Hence, the dynamics of constant learning rate SGD should be clarified as a future direction.
References
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators. Springer, 2014.
12

---

Published in Transactions on Machine Learning Research (08/2025)
CNN CIFAR1O
DNN MNIST
80
80
Error Rate
60
60
40
40
20
20
0
50
100
150
200
250
300
350
25
50
75
100
125
150
Step
Step
ResNet18 CIFAR100
VGG16 CIFAR100
100
80
Error Rate
60
Error Rate
50
25
0
50
100
150
200
250
50
100
150
Step
Step
(train)
SGD-M (train)
(train)
SGLD (train)
Adam (train)
SGD (valid)
SGD-M (valid)
PSGD (valid)
SGLD (valid)
Adam (valid)
Figure Error rates against the update steps for cach datasct/nctworf nntwork.
Barak Battash, Lior Wolf, and Ofir Lindenbaum. Revisiting the noise model of stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, 2024.
Andrea Bertazzi, Joris Bierkens, and Paul Dobson. Approximations of piecewise deterministic markov processes and their convergence properties. Stochastic Processes and their Applications, 154:91-153, 2022.
Léonard Blier, Pierre Wolinski, and Yann Ollivier. Learning with random learning rates. In ECML PKDD, 2019.
François Bolley and Cédric Villani. Weighted csiszär-kullbackk-nnkke inequalities and applications to trans- portation inequalities. Annales de la Faculté des sciences de Toulouse: Mathématiques, 14(3):331 352, 2005.
Léon Bottou. Stochastic gradient learning in neural networks. Proceedings of Newro-Nmmes, 91(8))12, 1991.
Alexandre Bouchard- Côté,, Sebastian J Vollmer, and Arnaud Doucet. The bouncy particle sampler: A nonre- versible rejection-free markov chain monte carlo method. Journal of the American Statistical Association, 113(522):8555 867, 2018.
Zaiwei Chen, Shancong Mou, and Siva Theja Maguluri. Stationary behavior of constant stepsize sgd type algorithms: An asymptotic characterization. Proceedings of the ACM on Measurement and Analysis of Compaling Systems, 6(1)(19):1-24) 2022.
Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan. Stochastic gradient and langevin processes.
In International Conference on Machine Learning, 2020.
Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. In Conference on Learning Theory, 2017.
M.H.A Davis. Pierewise-determnnssie markov processes: A general class of non-diffusion stochastic models. Journal of the Royal Statistical Society, Series B (Methodological) (46):333 353-3333-338, 1984.
M.H.A Davis. Markov Models and Oplimization. Chapman & Hall/CRC Monographs Statistics & Applied Probability. Taylor& & Francis, 1993.
George Deligiannidis, Alexandre Bouchard-C6re and Arnaud Doucet. Exponential ergodicity of the bouncy particle sampler. The Arnals of Slatistics, 77.1268-1235 2019.
13

---

Published in Transactions on Machine Learning Research (08/2025)
Li Deng. The mnist database of handwritten digit images for machine learning rescarch. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals of Statistics, 48(3):1348 1382, 2020.
Alain Durmus and Eric Moulines. Sampling from a strongly log-concave distribution with the unadjusted langevin algorithm. HAL preprint bal-01304/3011, 2016.
Alain Durmus, Arnaud Guillin, and Pierre Monmarché. Geometric ergodicity of the bouncy particle sampler. 2098, 2020.
Annals of Applied Probability,
Alessandra Faggionato, Davide Gabrielli, and Marco Ribezzi-Crivellai. Non-equilirrium thermodynamics piecewise deterministic markov processes. Journal of Statistical Physics, 137:259 304, 2009.
Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301111283 2023.
Alison L. Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International Statistical Review / Revue Internationale de Statistique, 70(3):419 144419-44,,,-, 2002.
Jeff Z. HaoChen, Colin Wei, Jason D. Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. Conference On Learning Theory, 2021.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv preprint 1r1i::1512. 5133855 2015.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. Advances neural information processing systems, 30, 2017.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXi::111.006623, 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On largo-batch training for deep learning: Generalization gap and sharp minima. In International Con- [erence on Learning Representations, 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Jonas Latz. Analysis of stochastic gradient descent in continuous time. Statistics and Computing, 31(3)). 2021.
John M. Lee. Introduction to Smooth Manifolds, volume 218 of Graduate Texts in Mathematics. Springer, 2012.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference Machine Learning, 2017.
Stephan Mandt, Matthew D. Hoffman, and David M. Blei. Stochastic gradient descent approximate bayesian inference. Journal of Machine Learning Research, 18:1-35, 2017.
Pierre Monmarché. Piecewise deterministic simulated annealing. Latin American Journal of Probability and Mathematical Statistics, 13:357 398, 2016.
Daniele Musso. Stochastic gradient descent with random learning rate. arXiv preprint orXiv:2003.06990 2020.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Thanh Huy Nguyen, Umut Simsekli, Mert Gürbüzzalaban, and Gael Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. Advances in neural information processing systems, 32, 2019.
Richard Nickl and Kolyan Ray. Nonparametric statistical inference for drift vector fields of multi-dimennionall diffusions. The Annols of Statistics, 141388--4408 2020.
E. A. J. F. Peters and G. de With. Rejection-free monte carlo sampling for general potentials. Physical Review E, 2012.
Dorian Le Peutrec, Laurent Michel, and Boris Nectoux. Eyring-kramers type formulas for some piecewise deterministic markov processes. orXiv preprint ar orXio:2202.01465, 2022.
Feng Qi and Qiu-Ming Luo. Bounds for the ratio of two gamma functions: from Wendel's asymptotic relation to Elezović- Elezovié-Giordaan--P Eiordano-PPcaarie theorem. Journal of Inequalities and Applications, 20:44) November 2013.
Ning Qian. On the momentun term in gradient descent. learning algorithms. Neural Networks, pp. 145 151, 1999.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymplolic analysis. In Conference On Learning Theory, 2017.
Chris Sherlock and Alexandre H. Thiery, A discrete bouncy particle sampler. Biometrika, 109:335-33 349, 2022.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Umut Simsckli, Levent Sagun, and Mort Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference Machine Learning, pp. 5827 5837. PMLR, 2019.
lly Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International Conference on Machine Learning, 2013.
Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In Interna- tional Conference on Machine Learning, 2011.
Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing Zhu. On the noisy gradient descent that generalizes as sgd. In International Conference on Machine Learning, 2020.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference on Machine Learning, 2019.
A Supportive Information
A.1 Normalization by Momentum Coefficient
We verify that. the velocity vector is normalized by the choice of the momentum coefficient for Poisson SGD and BPS.
Proposition 7. Consider the update 3 for un with momentum coefficient
5 Then, for Vk e
21, K), we have ||vell 1. Further, for oy defined in Algorithm we obtain | for every k 1,,,,.. K.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Proof. We first consider og with the Poisson SGD case. Simply, have
Uk 2 VLz (K) (0k), uk-1) VD (0k)
|
V (0x)
(1) (0x) VLL (Oa)
la 2
(k) (0x))12
Vk-1
VT. (0x) ( (LL) (0k)
7)
kk- Ia -
I (k) (0:)
Dk-1
-1-1-
Since we set ||عu|| = for initialization, the statement holds.
For Te with the BPS case; the reflection does not change the norm of 8.2 in the same way, and the refreshment also keeps ||0x|] || 1, which completes the proof.
A.2 Details of Experiments in Section 7
A.2.1 Details of Section 7.1
As a design of the experiment, we set a distribution of a sample = = (xr, y) as x = (2), ~ (Unif(-5, (2) and g|ı ~ Wx + 2². 1) hold. For training, we set d = 2 and consider a parameter 0 = (0,, 02) and a loss function ((2;6)
((0? 8))z + (0} 0z)23 - y)² then update the paramcters by Poisson SGD with 10000 samples, batch size m 100. For the training of SGD, we its learning rate as 0.002. Since the empirical risk (0) is approximated by (==-)(0.1)),,===1((00
0z)x² + (0) G) (o + 2 + +)} (8.2) is
(0)), the stationary (8.e) is approximated by 3xp(-33(00 - 03 - 1))², where f is a constant multiple of B. distribution pz
(0f - 02 - 2 mz [( + 2 (const) and the dominant term of nr
A.2.2 Details of MNIST Experiment in Section 7.2
We consider fully connected neural network of 4 layers, and each layer has 200 units and the sigmoid activation function. We compare the performance of Poisson SGD with SGD, SGD with Momentun, and SGLD. We set the batch size as 256, the learning rate of the SGD, the SGD with momentum and SGLD as 0.01, and the momentum coefficient as 0.9. We choose the hyperparameter of Poisson SGD as Cp = 100, C. = 100, and B = 10000. We also use 3 = 10000 for SGLDD. We use 60000 images for training and 10000 images for validation.
A.2.3 Details of CIFAR10 Experiment in Section 7.2
We trained a convolutional neural network of 3 layers with the ReLU activation function, a 3 x 3 kernel, and the dropout rate 0.25. We compare the performance of Poisson SGD with SGD, SGD with Momentum, SGLD. We set the batch size as 256, the learning rate SGD, SGD with momentum, and SGLD as 0.01, and the momentum coefficient as 0.9. We choose the hyperparameter of Poisson SGD as Cp 100, C. 1, and 3 10000. We also use 10000 for SGLD. We use 45000 data points for training and 5000 data points for validation.
A.2.4 Details of CIFAR100 Experiment for VGG16 in Section 7.2
We adapted the VGG16 (Simonyan Zisscrman 2015) for training. We set the batch size as 128 and the learning rate of SGD as 0.01. We select the hyperparameter of Poisson SGD as Cp 100, Ca 0.01, and 3 = 10000. We use 50000 data points for training and 10000 data, points for validation.
16

---

Published in Transactions on Machine Learning Research (08/2025)
A.2.5 Details of CIFAR100 Experiment for ResNet18 in Section 7.2
We adapted the ResNet18 (He et al. 2015) for training. We set the batch size as 128 and the learning rate
of SGD and Adam as 0.01. As for the hyperparameter for Adam, we set B1 = 0.9, Bg = 0.999 and 10- We select the hyperparameter of Poisson SGD =p=100 Ca = 0.01, and & 10000. We 50000 data points for training and 10000 data points for validation.
B Proof of Theorem
Proof. By Theorem
3 and we can bound the approximation error
WiluaKKPP.. s 4vdks,
and the convergence error of BPS as
M2.K - f1 (B.5)) 1Tv S s(B,
From Theorem 4 in Gibbs & Su 2002 (explicit form is Theorem
13 in Appendix H].
bound the
Wasserstein distance by the total variation, then obtain
(8.5) ||V S &x( Wi 1 (B)))) < W,,, u1
The triangle inequality completes the proof.
C Proof of Theorem 3
Proof. From the definition of Wasserstein distance,
(1 Pa,kk) inf MEI( (...)
B. [1]
holds, so we study the distance between 6g and 0g terms of the norm | holds by Proposition we have
||- Since || = ||%--/l = |6
1 0z [1] [ MAUk-1 (0x-1 Th -
< < 0 [11] + E [l 7h T + (ux-1 11-1)
<E, 11 0e-1l1 |11] Ex liie mn - [1 + E. [l| (ūx-1 1]
<E,11|0 1 v de, [Ime ne 2 2 [ytel
(10)
where we use ||- vdll || in the last inequality.
We first evaluate the second term of 10 There exists coupling such that
Ez(1a- - nx || = (i
holds, where Pap and Pa denote the distribution 7h and the respectively. We use such a coupling as n. In evaluating Wi P. we consider the following analysis. ma and îi are 1-dimensional and their cumulative distribution function is written
(i(t) 1- exp (- (B(VI + re), u)+ r0) Cp)dr)
Ft(t) = 1 exp (B(VI. + +CB + Arrt)dr).
respectively, and we also have
3 B(V rr), +C 2 Cr.
17

---

Published in Transactions on Machine Learning Research (08/2023)
B(VL + u)+ CB Ane 2 CB Aret, and
( + ru), u)+ + Cp) - (3 + ru),,)+ + CB + Azar]
< max 3M Cp - (CB +
+ Cp (On + Act)
Hence, we can use Lemma and obtain
max 3M+ + Cp (CB + Aret)),, + Cp (CB Aret)
Wi P
(11)
Cp(Cn + Aret)
Next, we evaluate the third term of 10 We have
E Emm]
P( 2 t)dt
exp (-f(
(3(VT (02 + rlx-1); wk-1)) + Cr-cdry di
exp (-Opt) dt
1
(12)
Cp
Substituting
11 and 12 into
10
we have
10 0x1 1|] et |||0,= - 1111
(13)
Vdmaxll BM, + Cp - (CB + Aror)l.1BM, + Cp (CB + Aboi)l 2vd
Cp(CB + Aret)
Cp
Since we take Cp in Poisson SGD as Cp 1/e and CB and Aref in BPS as CB + Are 3M, + 1/E, can be written as
13
E. 0xll1] SB, [10 - - +V
Hence, solving this recursive inequality with du = fu we have
Eg ||00 0x [l1] s 4vdKe,
which is the desired conclusion.
Lemma 8. Let aj and a2 R-valued random variables whose cumulative distribution functions are (i(t) = = exp (-f, (rrrar)) and F2(t) = - -eep (atrrar)))
respectively, where J2 + R are continuous functions. Let the distributiinss of ai and 02 be Pı and P2 respectively. Suppose that there exists M, m1, m2 > such that (f2(t) - f((t] I M, my S fi(t), and ma S f2(1) hold for VL R. Then, the Wasserstein distance between Pi and P2 satisfies
WiPP, M
m2
Proof. Since and are 1-dimensional, we have
WIP,, P2) = -f[" (PT -Fz dg.
18

---

Published in Transactions on Machine Learning Research (08/2025)
We introduce several notation 8(r) = f2(r) - -f(r), t= t= and t' = (g). then
! f((r)rr= = =log 1-1
L (fi(r) + 8(r))dr log
1
holds. So, we obtain
S( f((r)dr= [(06))dr.
8(r)dr.
Hence, we have
1Te Si [(()ar)
- fi(r)dr MP.
min((e,9
In addition, ( (i(r)dr milt 1'| holds, so have
Mt
1-1 m2
We have the upper bound of t'
1
L fa(r)dr 2 mal',
log
have
M
1
1--1% 11 m1122
log
Since So |log(1 - q)]dg holds, we obtain
[ FT (g) F0 1g)
M
m2
D Proof of Theorem 4
(9.2) one of its stationary distributions We prove this theorem by two steps. First, we prove that BPS has fz in section D.I. At this stage, BPS may have other forms of stationary distribution may not converge to its stationary distribution. Second, we prove that BPS has unique stationary distribution and converges to its stationary distribution at exponential rate, in other words, it has the exponential ergodicity, in section
D.2
D.1 The form of the stationary distribution
(9,6) stationary distribution. In the proof, define X(0, := In this section, check that BPS has μz ((V v)+, X(0, v) = 106, +Art and (g) = I [[ (.) We remark that R2 is symmctric
matrix and satisfies (0) = La, so it is also an orthogonal matrix.
From the proof of Lemma in the supplementary material of Deligiannidis et al. 2019). we can write the transition probability Q of BPS as following for arbitrary measurable sets A O and c gd-1,
Q(00v),Ax Ax B) = 1m exp {-f," (5(0 + un, v) + CB) du
19

---

Published in Transactions on Machine Learning Research (08/2025)
x (Ā(0 + uw, v) + CB) K((@ su, v), A x B)ds,
(14)
where a transition kernel K is expressed as
1(0,0) + CB 1.0 A]][Ra e B]
K((0,)),
(15)
100, v) + +CB
Arof 1 v) + CB
10 Alpanit
where Munif is the uniform probability measure on gd-1
Lemma 9. Under Assumption 1 probability measure θ gd-1
S
B)x x
AAB
is the stationary distribution induced from the transilion probability Q as 14
Proof. Our proof is almost the same as the proof of Lemma in Deligiannidis et al. (019)) Let Tx(d0, = (e)
First, we prove
/ + Cn) do) ((0,) v), B) x Ax B).
(16)
Substituting
15
the left side of (16) is rewritten as
Tzz (d0, du) CB) A E B| + / Tz (d0,, A 10 A] (B).
We consider changing the variable as (0)v.. Since R2) = R2) holds, we get A(0, (2)) = X(0,-u/) -1)). In addition, since |det R2 (0)) = 1, and Mumit (0) (du)) = Pumit (du') hold due the rotational invariance of Munif, we obtain
J Tz du' (A(0, + CB)
/ JAXB
Tz(d8, du' du')Azof:
AxB
which is proportional to the right side of [66 from the definition of P.z. Second, we prove f ((0,,, v), (dy, dw (z) (d0, du) (dyy dw). We have
/ @(10, v), (dy,
du)
x
exp (-f (A(0
wv, wv, v) + Cn)du) {A(o + sv, v) + Cn
x K((O + sc, u). (dy, (ā() + Cp CC (x(0,, do)ds.
If we change 0 t = 0 + sv, then this integral becomes
l exp (-f (A(1 (x (u 8)v, v) + Cnjdu (T(1, v) + Cn)
x (dy, (dy, su. -v) + CB n (d00, du ds.
Since (0) is absolutely continuous,
exp(-BIz(( - (s))) = exp (3TTz(1)- 1- X(t www -v) + 1 Nlt - wov v)dw
20

---

Published in Transactions on Machine Learning Research (08/2025)
holds in the same way Deligiannidis et al. 20199 w0
Substituting it into Tz(dr, do) and changing
L exp (-N6 (A(t [(((((tt- u) + CB)K((t, v),, (dy, dw)) (dt, du)
we, u) + CB Jdw
{A(t - su, -v) + CB\ds
holds. The first line can be calculated as exp (- (X(t - wv, -u) + CB]dd)] 1, so it is equal to
/ C((l,))+C>)K( (dy, dw) )r (dl, du).
Using [6 it is proportional to (dyy,, dw), which completes the proof.
By the following proposition, prove that 12 we defined 0d := [(d/))/w/T((d2++
(8.z) is one of the stationary distributions of BPS. Recall that
Proposition 10. The morginal distribution of the stationary distribution expressed in Lemma is written
(_(df) & (Arof + Cn + a.3
Hence, if we pul Agef and CB as Aeef + CB = 3M, + 1/e, il corvesponds to μuz (9.6)
Proof. We only need to integrate with the distribution ee expressed in Lemma We have
(d00 x / + CB + -ot
= (Ane + CB) exp((=xz((())))
(V (VLz(0),
We can calculate the expected value in the last term as
Eurapam (V), w)+1 - Ee L2 (O]((ccoss)))) (1V (cos +1+
where o E R is random variable dependent v which satisfies
cos Φ = V (L)
(17)
[
From the symmetry of the uniform distribution, we can calculate Eu-poait [coos Φ)+1 by replacing VL,(0) in
[9)]
17 by (1,0, (..,,...,))) 0). Hence,
Ev +] Eewopennt [v1)+] =E
F
holds, where 2n is the first component of u and z;(i = I,,.,, d) is i.idd. standard Gaussian variables.
For (# ra) ~ NO0, Ia), we have
z
2 +... z
E
2
x
Rd
27
23 (2x)) (27))/2
d/2
exp
2
d2i dzd
1/2 exp (-r/2) (dd-1)/2-1 exp (-s/2) drds
[.,0) V r V2T
l'(d - 1)/2)2(d-1)/?
=fon $1/2 1/221//21(1 (1-+)(dd (d-
dt
B(1/2, (d - 1)/2)
21

---

Published in Transactions on Machine Learning Research (08/2025)
(d/122)
(d-
(11/))(((d-1//2]((( 1/2)
T(d/2)
(nf(d/2+11)
Note that for all d23 2,
r(d/2)
vd/2 r(d/2 + 1/2) Vd/2- 1/2
holds (o.g., see Qi & Luo (0133
Therefore, for all d 2, we have
T(d/2)
+ 2 +
(dTT(d/2+1/2)
V2ndd 2 - 1)
D.2 The exponential ergodicity of BPS
The next proposition is on the minorization condition the 2-skeletons of BPS on the restricted domains. In short, minorization means that the stochastic process can go from any measurable set. to any measurable set in the parameter space, which sufficient condition for the exponential ergodicity in the compact parameter space. 2-Skeleton mcans 2 step of the stochastic process. This proposition completes the proof of Theorem 4
Proposition 11. Under Assumption the 2-skeletons of BPS satisfies the ménorization condition; that is, for some e > 0, for all (0,v) E x and all measurable E C θ 8d-1, we have
((0,0) J 11(0,))
Moreover, BPS is exponentially ergodic in total variation distance.
Proof. We partially follow the proof of Lemma in Deligiannidis et al. 20099)
Let f θ x gd-1 + [0, oo) be non-negative and bounded function. We also use the notation M' sup(e,))exx=-11
< co. By considering the event where the first update of v is refreshment from Unif(Sd-1) ), we see that for any vo) E gd-1
J 1(0, ((0,)) vo), (d0, du))
- JoYSH. (
1(0, 1(0,0)((01, (d0, ((b)) vo). (d0), du;))
2 Arof inf
M B1e0 Texes-1 f(0, ((,,))(((8)) uz), (d8 (dB, do) Puni
holds. We also obtain that for T Exp(M'), V1. V/2 l.d. Unir(Sd-1), we have
inf / 0,60
f(0, v) ((00,, v1), d0dr (uni((de))
Jexgr-1
Azef
inf 0,60
E [1 TV, E (0) TV,, Vz)]
M
A2 M x,00)x80 1x84
inf 0,
1 + tu - θle Ar' f(0: + tuz, dtdt (dv, Muntt (dv)
22

---

Published in Transactions on Machine Learning Research (08/2025)
A Agee M' (+)
inf 1,
1 + tu E f) + tui, undt (dv1) 0,00)x84 1x84
M'
A M' (id
inf 0.
1 f)
01 || d000 (dv)
M
@x84
[(0, (0,00)dpummtt (d)))
Mddia(()jd-1 @x8d-1
where the second last equality uses a change of coordinates. Since f is generic, the minorization condition holds. Harris's theorem thus gives the exponential ergodicity of BPS.
E Proof of Theorem 5
Proof.
We prove in the same way as the proof of Theorem 2.1 in Raginsky et al. (2017). Let f2. be random
variable satisfying 0g pa ((8.c) where jzz (8.c) is defined in 6 We denote 0K K the output of Poisson
SGD (Algorithm 1.. We have
Eg Ex [[(0x]]] inf L( DE5
= =Ex[Eox [[(Ok]] - Eo, [I(6,]]] + { Eo, [L(0,)]] inf L(0)),
and the second term of right-hand side is written
Eg (L(0,)] inf L(O) BEB
[I(0=]]] - Es [0,)]] + [o, [L,(0,]]
inf L(A)
Letting argmingeo L(0), the second part of the right- hand side in the equation above is
Lz(0) L=((0))
Eg Eg, [Ln (0w)]l inf L(O) -E, [EE,, [L (0,)) - inf Lz) + 606
Ex
inf dEE
OEE
< Ex Eo, [L (0p))
inf Lz(0)).
AEE
As result, we have
Ey [Eg [T[0x)]]]
inf I(O) STZ [E [1(0k)] Eg,, [I(O))]]
(18)
DE0
+Ez EE, [0,))) ] - Es, [L (0,))l + Ex [e, (0,.) inf (z)).
(19)
(20)
BEB
19 and (20g, prepare the following lemma to calculate the upper bound of the difference between two expected value by the Wasserstein distance.
To evaluate the terms 18
Lemma 12. Consider probability measures μ and v on θ Suppose that sup [(220) < A and
supzez [[V[(z; 0)] < B hold. Then, we oblain
Eg, ~ [((2 Egg ((): ((220)))] S (q /)/ and
(21)
Es ~ [(0))] Ee, ((2))] (q + B) /)W((
(22)
Proof. Under the assumption, Lemma 3.1 in Raginsky et al. 2017 holds. Hence, have
[V S |0|| B, E θ V2
(23)
23

---

Published in Transactions on Machine Learning Research (08/2025)
Ci (2;0) < 2 11012 + B|Jo| A, 20,
(24)
Moreover, from Lemma 3.5
Raginsky el al. 2017 for arbitrary two probability measures j and v, we
let
a² max [B -~ [10 E0g~v/ []]]]]]]]
then we have
-R (((;0))) - R (((2;0))] - (c10 + (),
Obviously, also holds that
Es ~ [L())]] Ed | S (c10 B)22
Since we have 1 W and W2(p,)) v) inf inf (Sg || d21 2)) 1/2 I infremowe (o Wi|z z' 2211 (w, we obtain the statement.
We start evaluating each of the terms 18 First, we study
19
and
20
18 From in Lemma 12
we have
Eø [[(0)]] Ee, (0w) S(aW + B)y WWw (p2k. 2aa))
S(q W (3g,(dd)ec.
(25)
Second, evaluate
19 using the same approach as Raginsky et al. 2017 Here, need to evaluate
Eg, [8(2;; 0w)] - Ee, [e(=; 0m:)].
(8,6) and Hz (.,55) is the stationary distribution of BPS when where e Z is an arbitrary sampled data, 0 Hx
one of the data is changed to arbitrary 2, Z and z' is dataset with replacing 2; to EΦ, and Le be its corresponding empirical risk. From [21 in Lemma 12 we have
Eg [((2;00)) Egg, [[(=;0w)]] S(, + B)Wa(ulae)) Px (3.2))
D(ub (1
W(W + B)C,
D(u
011080001100000 (3.2) +
where D(-II-) is KT-divergence and
/3
Cp 2 inf A5O
x + log
A1101 (B.c)) uz
(do)
which from Corollary 2.3 in Bolley & Villani (2005) (explicit form Theorem
Section
H Also,
since have |0| < W, Cp < 2W holds. We denote the density functions of μix
(9,e)
(8.e)
Ps. Pe', and the
normalization constants as Az, Ag respectively. Let us calculate D( 11 (8.2)). We have
(3.z)
(0) Az BM: 1/E VL2, (0) A 3M, + 1/s + aq [L) exp (-)((((())) (0)) (3.e)
(26)
so in order to obtain the upper bound of D( 12 (2:2)), we suppress each of the three terms of the right-hand side of 26 First, suppress the second term.
[VL,(00
V (0) + (V vi(;; 0)
L2 + VV((200 v((2;6)
24

---

Published in Transactions on Machine Learning Research (08/2025)
2 (cr |10|| B) VL (0)1
where the last inequality is from
23
Hence,
BM + 1/5 a. VL2)
3M 1/E + aaB (IIVIzz 3 (a |0| B))
3M, 1/e oz
BM, + 1/8 + ag3l V4.2 (0)
+ 20.3(ci W + B)
n(BM + +1/E)
20a(c1 W + B)
S1+
(27)
mMe
holds. Second, we suppress the third term. We have
exp (-B(La(0) - L (0))) exp
-3
(l(zz; 0) -((E;
11011
exxp
C1
+ B1|0| + +A)
2
C1W2
+ BW + A 1))
eexp
(28)
2
where we use (24
Finally, we suppress the first term.
Using
27
and
28
we have
Ax'
Seea (BMe + 1/e + ax3 ( exp (z (0) d0
Ag Seee (BMe 1/E + ag3 (L, exp (- dB
1 1 1
2al(c; W B)
exp
cj Q
+ BW + A
(29)
n.M.
2
Combining
27
28
and
29
we have
Pa
11 20a(c W + +B)
+ 2B
( (2W2
log
2 log
+ BW + +A
Pe (0)
nMe
2
1
Waalci + +B)
+ B W + 2BW + +24)).
-
Mr
SO
[4aale] + B)
D(1 (B.c) (3.e)) S
11
+ f(c W2 + 2BW + 24)
Me
holds. We set C. = 4a + B)/Me and C = c2W2 + 2BW + 2A, then we have
(Cxt $ +
(Ca+ BC #)
19
2W(c W +
(30)
n
Finally, we evaluate 20
Let us denote
A 3M, 1/8 VL.
Ax
A =
(BMz + 11 (
JEE
Since the distribution of 02 is
( (d8) x
(3M + + / [I)( exp(-33..
25

---

Published in Transactions on Machine Learning Research (08/2025)
have
c-3ba(Or)
E0, (02(0)
B Bg log A2()
+ Es, [log A=(0))))
(Eo, lall-loghe log (O,)] Eg, log (0
Since we have Eg, [II0 & W we can calculate the upper bound Es |- log Pa Pa(O,)) by the differential entropy of Gaussian distribution in the same way as the discussion of Section 3.5 Raginsky et al. (2017):
d 2me d
Ea - log Pa)))(())) log
W2
Using 23
we have
A BM, + 1/5 (3 + B))
log A2) 2 log
In addition,
log A = log / (BMr + 1/e + a. L. (0 (0
0EE
2 log /
(3M, + 1/e)e (0)
BEE
=log(3Mr + 1/5) + log
e
-BL.(00) d0
ME
d
2m
2log(BMe+ + 1/E) 3L2 2
log
c15
holds, where the last inequality is from the equation (3.21) in Raginsky et al. L = inface (0). Hence, we have
2017 Here, we denote
1
d 2Te W2 +log
BM, + 1/e anB(e, W + B)
d
2
20
log
BL log 2
L
3
BMc + 1/E
c1
1
eW2c c, + log
1 aala + B)
log
(31)
3
d
M₁
We combine the result
25
30
and
31 then obtain the statement.
F Proof of Proposition 6
Proof. Let 0, and 0, be the random variable which obey the distributions f (B.c) and ( respectively.
In the same way as Theorem we have
E. Box [[(0x)]]
inf I(O) [Eo [[(0))] E.g, [I(0,)]]
(32)
BEe
+ +Ez EEg, [L(),)] - Eg, [0,)]]
(33)
+ E. Ee, [L(,,)] - Eg, [L,(),,]]
(34)
+ +E, [E. (Lz( (B.))
inf (z))
(35)
BEO
32
can be ovaluated in the same way as Theorem
First, we evaluate
33
We have
EA, (T,)) Ra, Ra, [T(O-)] WWa(1(3.)) (100)
26

---

Published in Transactions on Machine Learning Research (08/2025)
from the same discussion in the proof of Theorem 5
Since both 8n and 0, satisfy the log-Sobolev inequality,
can use Otto- Otto-Villani theorem (Bakry et al. 2014) (explicit form is Theorem 15 in Section and
W2(u (0,6) ( S v 22 D(
(8.5) 1122
(9) holds, where D denotes the KL-divergence and Gs is the log- Sog-Soooeev constant of v()) We have
(3Me 1/e + a23 V (L)(0))) exp
D(11 -Ewng log
exp (O)
Ag
log(B.M. 1/E + 3a3 An
where Au and A are normalizing constants of the density functions of uz ((.,c) and (() respectively, We have
A Ag
Jo (0))
(BM + 1/e VLz()) exp (- (L do 3M, 1/s²
hence we have
D(u 0(1180111(0)) S log ax)
As a result, we obtain
ES, [L(0,)] Eo, (L(,)] WV 2013 log (1 a.GeMe).
(36)
Second, we evaluate (34 Let v be the Gibbs distribution when one of the data 2; is replaced by of. In the same way as Section 3.6 in Raginsky et al. (2017). we have
(0(9) BMc
(9)
We(1!1 (10))
n
Hence, we have
20 BMc (3)
Eg, [I().)] Eg, [Lz( (q B)
(37)
n
Finally, we evaluate (2017) and we have
35
This term can be evaluated the same way as Proposition 3.4 Raginsky ot al.
(d
log (2TeW2 d log 2T c13
Es, (B,))
inf Lz(0)
BEO
8
cW2ag8)
log
(38)
23
We combine the result (36).
37
and
38
then obtain the statement.
G Proof of Theorem 2
(8.e) Proof. Let 0x, Op be the random variables whose distribution is 1 and (3.c) respectively, Let b mingee (0). We have
Eøg [0x)))) LE =(Eex (0x)] Ee, LL (0w))) + (Lz LT).
27

---

Published in Transactions on Machine Learning Research (08/2025)
As the first term of the right-hand side, the Wasserstein distance in the same way the proof
of Theorem 5 as in 25 Hence, we have
Exx [0x)) Eg, (L,,01 S W. B)v B)y
Further, using
31 in the Proof of Theorem
eW2c c1. + log 1+ aa(e W + B) b )) + 1
Re TT2 (0p)] - log
d
Mf
holds, which completes the proof.
Explicit citation of the existing theorems
Theorem 13 (Theorem 4, Gibbs & Su (2022) On the compact set Q2 the Wasserstein metric dw and the total variation distance drv satisfy the following relation:
dw S diam( dTv.
where diam(()) = sup(d(x,y)zz, D).
Theorem 14 (Corollary 2.3, Bolley & Villani (005 Let X be measurable space equipped with mea- surable distance d, let 2 and let v be a probability measure on X. Assume that there erist xy E X and a > O such that f cad(2o12)) dv(x) finâte. Then, Ay P(X),
w,(,nv) S [((n))}
H H(Hlv) 2
ip
where
1 (3 + log / endtoosa du(x)) dolce)) ao.
C = inf 2xEX,
Theorem 15 (Theorem 9.6.1, Bakry et al (2014)). Let be probability measure on M. If μ satisfies logarithmic Soboley inequality LS(C) for some constant C > 0, then it satisfies following for every probability measure v on M:
Wa(u, v/2 2C D(vllu),
where Wz denotes the Wasserstein-2 distance and denotes the Kullback-Leiie divergence.
28


Reviews:
[{"review_id": "CpX1Lr1KcZ", "reviewer": "Reviewer_BBPe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n- The problem of showing SGD with random learning rate can achieve stationary distribution is a challenging problem and the paper is able to do so with Poisson SGD.\n- The key contribution of the paper is the design of Poisson SGD where the learning rate is sampled from an exponential distribution.\n- All the claims in the paper are backed by theoretical analyses. I have gone through all the proofs and find no problem.\n- The results in this paper indeed pushes the frontier of the research direction of SGD with random learning rate.\n\n**Weakness**\n- I believe the paper relies on a strong assumption that the parameter space is a torus. Per the experiments, I do not think this assumption holds for the numerical experiments conducted in Section 7.2.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Poisson SGD which is a variant of SGD that uses random learning rate samples from an exponential distribution depending on the current gradient and a hyper-parameter. The paper shows that Poisson SGD can reach a stationary distribution by using a random learning rate even with a degenerated parameter update. Under certain assumptions, the authors show that the distribution of parameters updated by Poisson SGD converges to a stationary distribution and the output of Poisson SGD converges to the global minima. These can be done by approximating the parameter distribution of Poisson SGD by Bouncy Particle Sampler (BPS) and use its theory to construct the stationary distribution.\n\nNumerical experiments are provided to illustrate the stationary distribution of parameters updated by Poisson SGD and performance of Poisson SGD using image classification datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have several suggestions:\n- It would be great to relax the assumption that the parameter space has to be a torus. Relaxing this condition would greatly strengthen the contribution of the paper.\n- How about validating the choice of the hyperparameter chosen in Theorem 2 by having an example where it is possible to compute the Lipschitz constant.", "broader_impact_concerns": "I have no concerns about this.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1MKI0lznQ7", "reviewer": "Reviewer_nQ3k", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n* The paper introduces a novel perspective on SGD by incorporating a random learning rate through Poisson SGD.\n* The theoretical contributions regarding stationary distributions and global convergence in non-convex settings are interesting and relevant; examples shows it relevance,\n\n# Weaknesses\n* The assumptions on the loss function are very restrictive. Both having a lower bound on the loss function and an upper bound on it gradient is an unusual assumption in the stochastic optimisation literature. The authors should take a look at e.g. [1] for assumptions such as *expected smoothness* (a.k.a. the ABC-assumption). The authors should also summerize their assumption the loss function in a more clear way instead of they are placed in text through the paper. In addition, after loosening their assumptions the authors could add some examples where they validate their conditions.\n* The authors should clearly summarize all assumptions on the loss function in one section instead of spreading them throughout the paper. This would improve readability and allow for easier verification of their theoretical results.\n* It would be beneficial to provide concrete examples that validate the assumptions, particularly after loosening them to make the analysis more applicable to practical settings.\n\n# References\n* [1] A. Khaled and P. Richt{\\'a}rik. Better Theory for {SGD} in the  Nonconvex World. TMLR, 2023", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Poisson SGD, a novel variant of SGD with a random learning rate. The authors show that this Poisson SGD estimates will convergence to a stationary distribution even under degenerate updates, which does not hold for its baselines. The authors analyze its theoretical properties; stationarity distribution, global convergence, and generalization error, and show empirical finding that validate them.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Requested changes\n* See Weaknesses section above.\n\n# Additional comments\n* Define the parameter space $\\Theta$ more clearly the first time it is mentioned (and e.g., refer to the remark).\n* In section 2, the authors could state more clearly that they consider non-convex losses, instead of saying that the loss function $l$ is potentially non-convex.\n* In eq. (2) you define $L_{z}(\\theta*)=\\min_{\\theta'\\in\\Theta} L_{z}(\\theta')$, but should this not be $L_{z}(\\theta*) \\in \\min_{\\theta'\\in\\Theta} L_{z}(\\theta')$?\n* Specify with or without replacement in \"... we uniformly sample $m$ integers...\".\n* Should eq. (4) not be $\\theta_{k}=\\theta_{k-1} + \\alpha_{k}v_{k}$ with $v_{k} = v_{k-1} - \\eta_{k} \\nabla_{\\theta} \\hat{L}^{(k)} (\\theta_{k-1})$ with $z$, or else you don't have the correct $k$ in the loss for each iteration?\n* $\\eta_{k}$ satisfies the usual Robbins&Monro conditions? \n* $\\nabla_{?}$ Some times it is specified and sometimes not.\n* I find Remark 2 and 3 closer to Definitions?\n* I would make the example with Figure 1 into a \"Example 1\", such that you can refer to this (good example!).\n* Moreover, for this example, comment whether it holds for a large number of hyper-parameters for Poisson GD? Or does one have to fine-tune these a lot?\n* Section 4. \"the generated parameter $\\theta_{K}$ by eq. (4)\"\n* I find Assumption 1 weirdly formulated. The authors should be explicit that they assume lower bounded losses instant of simply $\\mathbb{R}_{\\geq0}$. Moreover, after the assumption they assume the gradients (of the losses) are upper bounded. This should be made into an Assumption.\n* Theorem 1. $\\mu_{z,K}$ is the distribution of $\\theta_K$ from the Poisson SGD. In the proof of Theorem 1 you have have \\hat{} on your distribution, but this quantity is not defined?\n* About Theorem 1. Can you add a discussion on how one practically can use this? Which quantities are known and can computed explicitly?\n* In section 5.2, and algo. 1, the authors have $L$ without hat? Should this not be $\\hat{L}$ to be consistent with eq. (6)? Or else you have to access the hole dataset, which is computation heavy (or even unfeasible).\n* Alg. 1. Add input line in the top, maybe use if-else-statement for probability in your pseudo code.\n* Thm. 3. \"we set $\\Lambda$ and $C_{B}$ such that \\dots\"\n* In Thm. 2, and 5, and prop 6, the authors continues to add assumptions on the losses, which seems questionable.\n* I find the language somewhat confusing, which makes the statements appear imprecise. The paper should be revised to enhance readability, improve notation consistency, ensure clarity in assumptions and definitions, and eliminate ambiguities in both theoretical statements and explanations. Here are some examples:\n  * The abstract somehow reads strangely:\n    * The authors write \"Numerous studies reveal the convergence properties of SGD and its simplified variants\". Do the authors not mean \"Numerous studies reveal the convergence properties of SGD and its more advanced variants, e.g., AdaGrad, ADAM etc\"?\n    * The authors also write \"..to obtain a stationary distribution, the update direction of the parameters must *not degenerate*, which limits the applicable variants of SGD\". Afterwards they write \"...we consider a novel SGD variant, Poisson SGD, which has *degenerated* parameter update...\", but does the authors not want to say that their novel SGD variant, Poisson SGD, convergences to a stationary distribution *even under degenerated* parameter update directions?\n  * Second sentence of introduction says \"...the category of stochastic optimization, where parameters are updated with randomness\nfrom the mini-batch sampling.\" You could add a sentence about you don't know the *true* underlying (data generating) distribution.\n  * Last sentence of first paragraph states \"...SGD has been one of the standard methods for training deep learning models...\". I believe that most people think of Adam/RMSprop as the standard?\n  * Second paragraph of introduction, you define SGLD twice.\n  * Correct references; be careful about \\citep{} vs. \\citet{}.\n  * Maybe emphasise your answer as with your question? i.e. \"Even with a degenerated...\".\n  * Section 2.2, citation for momentum?\n  * Alg. 1. \"with $\\lVert \\dots =1$.\"", "broader_impact_concerns": "N\\A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5rAhThoDyW", "reviewer": "Reviewer_hiiB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**  \n\n- The paper is well-written and easy to follow, making it accessible to readers familiar with stochastic optimization.  \n- The literature review is thorough, with relevant references properly cited and placed within the context of the study.  \n- All theorems, lemmas, and definitions are carefully and rigorously stated, ensuring clarity in the theoretical framework.  \n- While I am not an expert in stationary distribution analysis, the arguments presented appear logically sound. My evaluation is based on general reasoning rather than a deep verification of the proofs.  \n\n**Weaknesses:**  \n\n- The importance of stationary distribution analysis for SGD is not clearly explained for a broader audience. Readers who are not experts in this area may struggle to understand its practical significance and implications. A more intuitive discussion on why this perspective matters would improve accessibility.  \n- The reasoning behind the choice of parameter space as a torus \\((\\mathbb{R}/a\\mathbb{Z})^d\\) is not well explained. Providing more context and motivation for this assumption would enhance clarity.  \n- The third condition in the loss function assumptions is not clearly stated. Specifically, the requirement for the loss function to be periodic lacks justification. A more detailed discussion on why this assumption is necessary and how it affects the analysis would be beneficial.  \n- The empirical evaluation is quite limited. The experiments are conducted only on the MNIST dataset using a four-layer fully connected model and on CIFAR-10 using a three-layer convolutional model. This evaluation is insufficient to fully understand the practical behavior of the proposed method, especially in more complex and large-scale settings. Additional experiments on larger datasets and more diverse architectures would strengthen the empirical claims.  \n- The conclusion section is brief and lacks a discussion on potential future directions. Expanding on open questions, possible extensions of the method, and its broader impact would provide a more complete perspective on the study’s contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study introduces **Poisson SGD**, a variant of stochastic gradient descent (SGD) that employs a random learning rate instead of a fixed step size. Unlike traditional SGD, which requires non-degenerate parameter updates to ensure convergence, Poisson SGD overcomes this limitation while still achieving a stationary distribution under weak assumptions on the loss function. The authors establish that Poisson SGD can find global minima in non-convex optimization problems and analyze its generalization error. Using techniques from piecewise deterministic Markov processes (PDMP), they approximate Poisson SGD’s behavior with the **bouncy particle sampler (BPS)** to derive its stationary distribution. Additionally, the authors provide some experiments to validate their theoretical findings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Please check the weaknesses section carefully.**\n\n I would appreciate a more thorough explanation and justification for the concerns raised, particularly regarding the assumptions and limitations of the proposed approach. If possible, addressing these points in the revision would significantly improve the clarity and impact of the paper.  \n\nAdditionally, I have a specific request regarding the presentation of the experimental results. To improve the readability of the plots for all readers, including those who are colorblind, I suggest adding a grid and using distinct markers for different curves. This will make it easier to interpret the results, especially in cases where color differentiation alone may not be sufficient. A clearer visual representation would enhance the accessibility and overall presentation of the empirical findings.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)