Faster Convergence of Riemannian Stochastic Gradient Descent with Increasing Batch Size
Kanata Oowada, Hideaki Iiduka · 2025
Read Faster Convergence of Riemannian Stochastic Gradient Descent with Increasing Batch Size by Kanata Oowada, Hideaki Iiduka (2025) 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-2501-18164.txt.
Introduction
Kanata Oowada and Hideaki Iiduka analyze optimization on manifolds in twenty twenty-five. Riemannian stochastic gradient descent trains models whose parameters live on curved spaces. Batch size is a key knob in that training. The authors study what happens when the batch grows over time instead of staying fixed.
Theory shows an increasing batch converges faster than a constant one. The gain holds for constant learning rates and for decaying ones, including cosine and polynomial schedules. The error term that lingers with constant batches vanishes in the increasing case. Tests on principal component analysis and low-rank matrix completion confirm the theory. Increasing batches also cut the total oracle cost. Readers get a simple schedule change with proven speed benefits.
Catalog record
| CREATOR | Kanata Oowada, Hideaki Iiduka |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18164
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster Convergence of Riemannian Stochastic Gradient Descent with Increasing Batch Size Kanata Oowada, Hideaki Iiduka Abstract We theoretically analyzed the convergence behavior of Riemannian stochastic gradient descent (RSGD) and found that using an increasing batch size leads to faster convergence than using a constant batch size, not only with a constant learning rate but also with a decaying learning rate, such as cosine annealing decay and polynomial decay. The convergence rate improves from O ( T − 1 + C ) O(T^{-1}+C) with a constant batch size to O ( T − 1 ) O(T^{-1}) with an increasing batch size, where T T denotes the total number of iterations and C C is a constant. Using principal component analysis and low-rank matrix completion, we investigated, both theoretically and numerically, how an increasing batch size affects computational time as quantified by stochastic first-order oracle (SFO) complexity. An increasing batch size was found to reduce the SFO complexity of RSGD. Furthermore, an increasing batch size was found to offer the advantages of both small and large constant batch sizes. keywords Batch Size; Stochastic First-order Oracle Complexity; Learning Rate; Riemannian Optimization; Riemannian Stochastic Gradient Descent 1 Introduction Study/Theorem Batch Size Learning Rate Convergence Analysis Bonnabel (2013) – s.a. LR \underset{t\to\infty}{\lim}\mathbb{E}[\mathrm{grad}f(x_{t})]=0\text{ a.s.} Zhang and Sra (2016) – \eta_{t}=O((L_{r}+\sqrt{t})^{-1}) \mathbb{E}[f(x_{T})-f^{\star}]=O(\sqrt{T}(C+T)^{-1}) Tripuraneni et al. (2018) Constant \eta_{t}=O(t^{-\alpha}) \mathbb{E}\|\Delta_{T}\|=O(T^{-\frac{1}{2}}) Hosseini and Sra (2020) Constant \eta=O(T^{-\frac{1}{2}}) \|G_{T}\|^{2}=O(T^{-\frac{1}{2}}) Durmus et al. (2021) Constant Constant \mathbb{E}[f(x_{T})-f^{\star}]=O(C_{1}^{T}+C_{2}) Sakai and Iiduka (2024) Constant \eta_{t}=O((t+1)^{-\frac{1}{2}}) \|G_{T}\|^{2}=O(T^{-\frac{1}{2}}\log T) Sakai and Iiduka (2025) Increasing Constant \|G_{T}\|^{2}=O(T^{-1}) Theorem 5 Constant Constant and Decay \|G_{T}\|^{2}=O(T^{-1}+C) Theorem 6 Increasing Constant and Decay \|G_{T}\|^{2}=O(T^{-1}) Theorem 7 Increasing Warm-up \|G_{T}\|^{2}=O((T-T_{w})^{-1}) Theorem 8 Constant Warm-up \|G_{T}\|^{2}=O((T-T_{w})^{-1}+C) Table 1: Comparison of RSGD convergence analyses, where \alpha\in(\frac{1}{2},1),C_{1}\in(0,1),C_{2} and C are constants, and (x_{t}) is a sequence generated by RSGD. The usual stochastic approximation LR (s.a. LR) is defined as \sum_{t=0}^{\infty}\eta_{t}=\infty,\sum_{t=0}^{\infty}\eta_{t}^{2}<\infty . \mathbb{E}[\|\Delta_{T}\|]\coloneq\mathbb{E}[\|R_{x^{\star}}^{-1}(x_{T})\|] . T is the total number of iterations, and T_{w} is the number of warm-up iterations (see Section 3.3 ). \|G_{T}\|^{2}\coloneq\min_{t\in\{0,\cdots,T-1\}}\mathbb{E}[\|\mathrm{grad}f(x_{t})\|^{2}_{x_{t}}] . ‘Decay’ includes LR schedules of the form \eta_{t}=O(t^{-\frac{1}{2}}) . More detailed explanations of the convergence criteria are provided in Appendix F . Stochastic gradient descent (SGD) ( Robbins and Monro, 1951 ) is a basic algorithm, widely used in machine learning ( Liu et al., 2021 ; He et al., 2016 ; Krizhevsky et al., 2012 ) . Riemannian stochastic gradient descent (RSGD) was introduced in Bonnabel (2013) . Riemannian optimization ( Absil et al., 2008 ; Boumal, 2023 ) , which addresses RSGD and its variants, has attracted attention due to its potential application in various tasks, including many machine learning tasks. For example, it has been used in principal components analysis (PCA) ( Breloy et al., 2021 ; Liu and Boumal, 2020 ; Roy et al., 2018 ) , low-rank matrix completion ( Vandereycken, 2013 ; Boumal and Absil, 2015 ; Kasai and Mishra, 2016 ) , convolutional neural networks ( Wang et al., 2020 ; Huang et al., 2017 ) , and graph neural networks ( Zhu et al., 2020 ; Chami et al., 2019 ; Liu et al., 2019 ) . It has also been used in applications of optimal transportation theory ( Lin et al., 2020b ; Weber and Sra, 2023 ) . It is well established that the performance of Euclidean SGD strongly depends on both the batch size (BS) and learning rate (LR) settings ( Goyal et al., 2017 ; Smith et al., 2018 ; Zhang et al., 2019 ; Lin et al., 2020a ) . In the context of Riemannian SGD, Ji et al. (2024) ; Bonnabel (2013) ; Kasai et al. (2019) ; Kasai et al. (2018) addressed the use of a constant BS, and Sakai and Iiduka (2025) ; Han and Gao (2022) addressed the use of an adaptive BS, although the latter did not consider RSGD specifically. In parallel, various decaying LR strategies, including cosine annealing ( Loshchilov and Hutter, 2017 ) and polynomial decay ( Chen et al., 2018 ) , have been devised, and their effectiveness has been demonstrated for the Euclidean case. Motivated by these previous studies, we developed a novel convergence analysis of RSGD, proved that the convergence rate is improved with an increasing BS, and showed that the stochastic first-order oracle (SFO) complexity is reduced with an increasing BS. Our numerical results support our theoretical results. 1.1 Previous Results and Our Contributions Constraint: Bonnabel (2013) ; Zhang and Sra (2016) ; Durmus et al. (2021) ; Sakai and Iiduka (2024) considered Hadamard manifolds or their submanifolds. Tripuraneni et al. (2018) treated Riemannian manifolds that satisfy the condition required to ensure a unique geodesic connecting any two points, including Hadamard manifolds. Sakai and Iiduka (2025) addressed embedded submanifolds of Euclidean space. In contrast, we considered general Riemannian manifolds that encompass all of the above conditions. Learning rate: Bonnabel (2013) considered s.a. LRs, and Zhang and Sra (2016) ; Tripuraneni et al. (2018) ; Sakai and Iiduka (2024) considered diminishing LRs of the form \eta_{t}=\frac{1}{t^{a}} . Hosseini and Sra (2020) ; Durmus et al. (2021) considered constant LRs. Sakai and Iiduka (2025) used both constant and diminishing LRs. We considered constant, diminishing, cosine annealing, and polynomial decay LRs, as well as their warm-up versions. Batch size: Because Bonnabel (2013) considered expected risk minimization using expectation instead of sample mean—as is customary in empirical risk minimization—the concept of BS is not generally applicable in the expected-risk-minimization setting. Zhang and Sra (2016) ; Tripuraneni et al. (2018) ; Hosseini and Sra (2020) ; Durmus et al. (2021) ; Sakai and Iiduka (2024) considered a constant BS. Sakai and Iiduka (2025) and this study considered an increasing BS. Furthermore, we numerically and theoretically compared using a constant BS with using an increasing BS on the basis of SFO complexity. Our contributions are as follows: (i) we theoretically showed that using an increasing BS yields a more favorable SFO complexity of O(\epsilon^{-2}) , whereas using a constant BS equal to the critical BS yields a rate of O(\epsilon^{-4}) ; (ii) we numerically observed that an increasing BS yields both a better optimal solution—in terms of attaining a smaller gradient norm—and a shorter computational time than either a small or a large constant BS (see Section 4.3 for more details). Objective function: Bonnabel (2013) considered three times continuously differentiable functions, with both the gradient and Hessian uniformly bounded. Tripuraneni et al. (2018) treated functions that are twice continuously differential, subject to additional conditions on the Hessian. Other studies considered only once continuously differentiable functions. Zhang and Sra (2016) addressed convex and smooth functions, while Durmus et al. (2021) considered strongly convex and smooth functions. Hosseini and Sra (2020) ; Sakai and Iiduka (2024) ; Sakai and Iiduka (2025) treated more general classes of functions, specifically nonconvex functions with bounded gradients. We treated nonconvex functions without bounded gradients. Convergence rate: A comparison of the previous and current RSGD convergence analyses is presented in Table 1 ; here we outline the key results. Tripuraneni et al. (2018) obtained a convergence rate of O(T^{-\frac{1}{2}}) (with a criterion other than the gradient norm) using an LR of \eta=O(T^{-\frac{1}{2}}) ; however, this rate decays to zero as T\to\infty , making it unsuitable for