On ergodicity of the SAGA-LD algorithm
Miklós Rásonyi · 2026
Read On ergodicity of the SAGA-LD algorithm by Miklós Rásonyi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12815.txt.
Introduction
Miklós Rásonyi proves ergodicity for the SAGA-LD sampling algorithm. SAGA-LD draws samples for machine learning from high-dimensional distributions. Its tangled dynamics resist standard Markov chain theory. A model-specific method shows the chain converges to a limiting distribution. A law of large numbers holds as well.
Catalog record
| CREATOR | Miklós Rásonyi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31733 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.12815
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On ergodicity of the SAGA-LD algorithm Thanks: The author gratefully acknowledges the support of the National Research, Development and Innovation Office (NKFIH) through grants K 143529 and KKP 137490. Miklós Rásonyi Abstract The so-called SAGA-LD algorithm is used for efficient sampling from high-dimensional distributions in machine learning. Its intricate dynamics resists standard approaches of Markov chain theory. We prove, using a model-specific method, that SAGA-LD converges to a limiting distribution and a law of large numbers holds. 1 Introduction Non-convex optimization procedures in machine learning are often based on the Langevin equation dL_{t}=-F(L_{t})\,dt+\sqrt{2}dB_{t}, (1) where B_{t} is some high-dimensional standard Brownian motion and F=\nabla U for some function U\geq 0 . Under mild conditions, the process L_{t} has an invariant density proportional to \exp(-U) . A simple way of (approximate) sampling from this density would be Euler-Maruyama approximations of ( 1 ). In practice, however, F is not available or prohibitively expensive to evaluate. We consider the case where F(x) is of the form \frac{1}{N}\sum_{i=1}^{N}F_{i}(x) for some functions F_{i}:\mathbb{R}^{d}\to\mathbb{R}^{d} , i=1,\ldots,N . An often used sampling algorithm was first proposed in [ 11 ] : Stochastic Gradient Langevin Dynamics (SGLD), initialized from some \tilde{X}_{0}\in\mathbb{R}^{d} , and given by the recursion \tilde{X}_{n+1}=\tilde{X}_{n}-\eta F_{S_{n}}(\tilde{X}_{n})+\sqrt{2\eta}\xi_{n+1}, (2) where \xi_{n} are an i.i.d. sequence of d -dimensional standard Gaussian variables, \eta>0 is the step size, and S_{n} are a sequence of i.i.d. uniform draws from the set \{1,2,\ldots,N\} . In practice, i.i.d. minibatches are drawn from the F_{i} and their average is used in ( 2 ) instead of just F_{S_{n}}(X_{n}) . For the present, theoretical study we contend with this simplified version of SGLD. Variance-reduction techniques produced several variants of SGLD, most notably SAGA-LD and SVRG-LD, see e.g. [ 5 ] . They show superior performance at the price of a more involved dynamics. In the present paper we concentrate on the SAGA-LD algorithm, to be defined in Section 2 below. That algorithm is mathematically challenging. SAGA-LD, as a Markov chain, does not seem to satisfy either of the two standard hypotheses of stochastic stability theory for general state space Markov chains: Foster-Lyapunov-type drift condtion and minorization on a small set, see e.g. [ 10 ] . As these two standard criteria fail, we take an unusual route in this paper, originating from [ 7 ] , that establishes stochastic stability and the convergence of ergodic averages via showing a strong mixing property. In doing so we do not (and cannot) rely on, say, Harris recurrence, but on the construction of specific couplings based on the dynamics of SAGA-LD. In Section 2 we formulate precisely our hypotheses and main result Theorem 2.4 : ergodic averages of functionals of the SAGA-LD iterates converge in probability. The latter result provides a reassuring theoretical guarantee for numerical work with SAGA-LD. Remark 2.5 explains its significance while Remark 2.6 discusses possible future directions. Section 3 contains the proofs. Section 4 presents background material about strongly mixing processes. 2 Definitions and results Fix our probability space (\Omega,\mathcal{F},P) , E[\cdot] denotes the corresponding expectation. Let an i.i.d. sequence \xi_{n} , n\in\mathbb{N} of d -dimensional standard Gaussian random variables be given. Furthermore, let a sequence of i.i.d. random variables S_{n} , n\in\mathbb{N} be drawn uniformly from the set \mathcal{N}:=\{1,2,\ldots,N\} . The initial state of the sampling algorithm is a random variable (or just a constant) X_{0}\in\mathbb{R}^{d} . We assume that X_{0} , (\xi_{n})_{n\in\mathbb{N}} , (S_{n})_{n\in\mathbb{N}} are independent. Scalar product in \mathbb{R}^{d} is denoted \langle\cdot,\cdot\rangle ; |\cdot| is the Euclidean norm in \mathbb{R}^{m} , where m is always clear from the context. \mathcal{B}(\mathbb{R}^{m}) are the Borel sets of \mathbb{R}^{m} . The “Stochastic Average Gradient Langevin Dynamics” (SAGA-LD) is then defined as follows: there is an N\times d -dimensional process G_{n} , n\in\mathbb{N} which stores the current estimates for the respective functions F_{i} , i=1,\ldots,N . Indeed, initialize this process by G_{0}^{i}:=F_{i}(X_{0}) , i=1,\ldots,N and set G^{i}_{n+1}=1_{\{S_{n}\neq i\}}G^{i}_{n}+1_{\{S_{n}=i\}}F_{i}(X_{n}),\ n\in\mathbb{N}. (3) The d -dimensional state variable for sampling is defined by the recursion X_{n+1}=X_{n}-\frac{\eta}{N}\sum_{i=1}^{N}G^{i}_{n}-\eta(F_{S_{n}}(X_{n})-G^{S_{n}}_{n})+\sqrt{2\eta}\xi_{n+1},\ n\in\mathbb{N}. (4) Here the updates \frac{\eta}{N}\sum_{i=1}^{N}G^{i}_{n}+\eta(F_{S_{n}}(X_{n})-G^{S_{n}}_{n}) (5) replace the term \eta F_{S_{n}}(\tilde{X}_{n}) appearing in the SGLD algorithm ( 2 ) above. Our assumptions are listed below. They essentially coincide with those of [ 12 ] and are weaker than those of [ 5 ] (they do not imply convexity of the function U in Section 1 ). Assumption 2.1 . E[|X_{0}|^{2}]<\infty. Assumption 2.2 . There exist c_{1},c_{2}>0 such that \left\langle\frac{1}{N}\sum_{i=1}^{N}F_{i}(x),x\right\rangle\geq c_{2}|x|^{2}-c_{1},\ x\in\mathbb{R}^{d}. We may and will assume c_{2}\leq 1 . Assumption 2.3 . For each 1\leq i\leq N , F_{i} is Lipschitz continuous, that is, there is M>0 such that |F_{i}(x)-F_{i}(y)|\leq M|x-y| for each i , and for all x,y\in\mathbb{R}^{d} . We may and will assume M\geq 1 . The total variation distance of two probabilities \mu_{1},\mu_{2} on \mathcal{B}(\mathbb{R}^{d}) is defined as d_{TV}(\mu_{1},\mu_{2}):=\inf_{X_{1}\sim\mu_{1},X_{2}\sim\mu_{2}}P(X_{1}\neq X_{2}), here the infimum ranges over all random variables X_{1} (resp. X_{2} ) with law \mu_{1} (resp. \mu_{2} ). The main achievement of the current paper is stated now. Theorem 2.4 . Let Assumptions 2.1 , 2.2 and 2.3 hold. There is \eta_{0}>0 such that, for 0<\eta\leq\eta_{0} there exists a probability \mu_{*}=\mu_{*}(\eta) on \mathbb{R}^{d}\times\mathbb{R}^{Nd} such that d_{TV}(\mathrm{Law}(X_{n},G_{n}),\mu_{*})\to 0,\ n\to\infty. For all measurable functions \phi:\mathbb{R}^{(N+1)d}\to\mathbb{R} such that |\phi(u)|\leq C(1+|u|) (6) with some C>0 , E\left[\left|\frac{\phi(X_{1},G_{1})+\ldots+\phi(X_{n},G_{n})}{n}-\int_{\mathbb{R}^{(N+1)d}}\phi(u)\mu_{*}(du)\right|\right]\to 0,\ n\to\infty. (7) A fortiori, the averages converge in probability. Remark 2.5 . It can be shown under suitable assumptions, see e.g. [ 5 ] , that \mu_{*}(\eta) is close to the invariant law \mu of ( 1 ), for \eta small enough. Then, for large n , the law of X_{n} should approximate \mu_{*}(\eta) , hence also \mu . In practice, however, what we need is approximating quantities like \Phi:=\int_{\mathbb{R}^{d}}\phi(x)\mu(dx) for some function \phi , using only one generated realization of X_{n} , n\in\mathbb{N} . In other words, we need that averages like \frac{\phi(X_{m+1})+\ldots+\phi(X_{m+n})}{n} are close to \Phi^{*}(\eta):=\int_{\mathbb{R}^{d}}\phi(x)\mu_{*}(\eta)(dx) for n large. ( \Phi^{*}(\eta) will be close to \Phi for \eta small enough since \mu_{*}(\eta) is close to \mu .) To sum up, in order to use SAGA-LD in numerical work with confidence, a law of large numbers should be established. This is precisely the content of ( 7 ) in Theorem 2.4 . Remark 2.6 . Determining the convergence rate of (X_{n},G_{n}) to \mu_{*} is an open problem of interest. It would also be desirable to have almost sure convergence in ( 7 ). We expect that other variance-reduced schemes could be treated along the same lines. 3 Coupling construction Indicator of an event A\in\mathcal{F} is denoted 1_{A} . Define the filtration \mathcal{H}_{n}:=\sigma(X_{0},\xi_{j},\ 0\leq j\leq n,S_{j},0\leq j<n),\ n\in\mathbb{N}. Clearly, the process (X_{n})_{n\in\mathbb{N}} is adapted to (\mathcal{H}_{n})_{n\in\mathbb{N}} and S_{n} is independent of \mathcal{H}_{n} , for all n\geq 0 . Assumptions 2.1 , 2.2 and 2.3 remain in force in the rest of the paper. 3.1 Moment estimates Denote \hat{M}:=\max_{i=1,\ldots,N}|F_{i}(0)| . It follows from Assumption 2.3 that, for all i , x , |F_{i}(x)|\leq\hat{M}+M|x|. (8) A key initial observation is that the process X_{n} , n\in\mathbb{N} remains bounded in L^{2} . This was already noticed in Lemma C.7 of [ 12 ] (in the case X_{0}=0 ). Lemma 3.1 . If \eta is small enough then \sup_{n\in\mathbb{N}}E[|X_{n}|^{2}+|G_{n}|^{2}]<\infty, Proof. We set L_{n}:=\sup_{0\leq l\leq n}E[|X_{l}|^{2}] . Let \eta\leq 1 . We will prove by induction that