betaFeedback

WorksMathematics

Online Covariance Estimation for Averaged Stochastic Gradient Descent on Riemannian Manifolds

Abstract

We study online inference for averaged Riemannian stochastic gradient descent (RSGD) when the unknown parameter lies on a manifold. Although the averaged RSGD iterate is asymptotically normal, practical inference requires estimating the unknown covariance operator in its limiting distribution. Existing online batch-means methods cannot be applied directly because a general Riemannian manifold lacks an addition operation, and the tangent space containing the Riemannian gradient varies across iterations. Through vector transport, we construct overlapping and non-overlapping covariance estimators that adaptively combine information from successive batches while accounting for the changing tangent spaces. The proposed estimators are online, require neither Riemannian Hessian computations nor a prespecified terminal sample size, and attain the same convergence rates as their Euclidean counterparts (Zhu et al., 2023). Together with asymptotic normality, these estimators enable online statistical inference for RSGD on manifolds. We illustrate the proposed framework through a detailed study of streaming principal component analysis on Grassmann manifolds.

Introduction

We study online statistical inference for a local minimizer of stochastic optimization problem on Riemannian manifold. Let ξ∼D\xi\sim\mathcal{D} be a random data sample, and let f(x,ξ)f(x,\xi) be the corresponding stochastic loss. We consider

min⁡x∈MF(x):=Eξ∼D[f(x,ξ)],(1)\min_{x \in\mathcal{M}} F(x) := \mathbb{E}_{\xi\sim\mathcal{D}}[f(x,\xi)], \tag*{(1)}

where the parameter of interest x⋆x_\star is a local minimizer of the population objective FF on the manifold M\mathcal{M}. Many problems in statistics, machine learning, and signal processing can be modeled on manifolds, such as principal component analysis with orthogonality constraints [15], dictionary learning on the sphere [37], low-rank matrix completion [10] and low multilinear rank tensor approximation [22, 42].

The classical theory for stochastic approximation is often restricted to Euclidean space. In this setting (M=Rd\mathcal{M} = \mathbb{R}^{d}), stochastic gradient descent (SGD) is one of the most standard methods for solving (1), which replaces the population gradient ∇F(x)\nabla F(x) with an unbiased estimate ∇f(x,ξ)\nabla f(x,\xi). In particular, given independent observations ξn∼D\xi_n \sim\mathcal{D}, an initial point x0x_0, and step sizes γn>0\gamma_n > 0, SGD performs the update

xn=xn−1−γn∇f(xn−1,ξn).(2)x_n = x_{n-1} - \gamma_n \nabla f(x_{n-1}, \xi_n). \tag*{(2)}

SGD is widely used for large-scale parameter estimation and online learning because of its low computational and memory cost [8]. Let xˉn=n−1∑i=1nxi\bar{x}_n = n^{-1}\sum_{i=1}^{n} x_i denote the averaged SGD iterate. Ruppert [35] and Polyak and Juditsky [33] showed that this averaged iterate is asymptotically normal and attains the optimal covariance in the local asymptotic minimax sense of Hájek and Le Cam [20, 27]. Specifically, consider step sizes γn=γn−α\gamma_n = \gamma n^{-\alpha} with γ>0\gamma> 0 and α∈(1/2,1)\alpha\in(1/2, 1). Under suitable conditions,

n(xˉn−x⋆)⟶dN(0,Σ),Σ=A−1SA−1,(3)\sqrt{n}(\bar{x}_n - x_\star) \mathrel{\mathop{\longrightarrow}^{\mathrm{d}}} \mathcal{N}(0,\Sigma), \qquad\Sigma= A^{-1} S A^{-1}, \tag*{(3)}

where

A:=∇2F(x⋆)andS:=E[∇f(x⋆,ξ)∇f(x⋆,ξ)T]A := \nabla^2 F(x_\star) \qquad\text{and} \qquad S := \mathbb{E}\left[\nabla f(x_\star,\xi)\nabla f(x_\star,\xi)^\mathsf{T}\right]

denote the Hessian of the population objective at x⋆x_\star and the covariance of the stochastic gradient noise, respectively. This result characterizes the estimation error at the n−1/2n^{-1/2} scale and provides the foundation for statistical inference.

To construct valid confidence intervals based on (3), one needs to estimate the asymptotic covariance Σ\Sigma. Chen et al. [11] proposed two consistent estimators: a plug-in estimator that requires Hessian information and a batch-means estimator that uses only SGD iterates. Zhu et al. [46] further developed overlapping (OL) and non-overlapping (NOL) variants of the batch-means estimator that can be updated without prior knowledge of the terminal sample size, thereby enabling fully online covariance estimation. The key idea is to divide the iterates into blocks of increasing size, with each block providing an approximately independent estimate of the covariance matrix. Specifically, let BjB_j denote a batch ending at iteration jj, with length ℓj=∣Bj∣\ell_j = |B_j| and average xˉjB=ℓj−1∑x∈Bjx\bar{x}_j^B = \ell_j^{-1}\sum_{x\in B_j} x, and let EnE_n index the batches used at iteration nn. Both the OL and NOL estimators take the form

Σ^n=∑j∈Enℓj2(xˉjB−xˉn)(xˉjB−xˉn)T∑j∈Enℓj.\widehat{\Sigma}_n = \frac{\sum_{j\in E_n} \ell_j^2(\bar{x}_j^B-\bar{x}_n)(\bar{x}_j^B-\bar{x}_n)^\mathsf{T}}{\sum_{j\in E_n}\ell_j}.

With a suitable choice of batch size sequence (see § 3.3), Zhu et al. [46] proved that, under suitable conditions, both estimators satisfy

E∥Σ^n−Σ∥≲n−(1−α)/4.\mathbb{E}\lVert\widehat{\Sigma}_n-\Sigma\rVert\lesssim n^{-(1-\alpha)/4}.

with the convergence rate approaching n−1/8n^{-1/8} as α→1/2\alpha\to1/2.

Despite these advances in online statistical inference in Euclidean space, stochastic approximation on a general Riemannian manifold is more complicated because the Euclidean SGD update in (2) does not, in general, preserve the manifold constraint. At a point x∈Mx \in\mathcal{M}, the Riemannian gradient grad⁡f(x,ξ)\operatorname{grad} f(x,\xi) lies in the tangent space TxMT_x\mathcal{M}. Riemannian stochastic gradient descent (RSGD) therefore uses a retraction RxR_x to map a tangent vector, such as a step along the negative Riemannian gradient, back onto the manifold. Precisely, the RSGD update takes the form

xn=Rxn−1(−γngrad⁡f(xn−1,ξn)).(4)x_n = R_{x_{n-1}}\left(-\gamma_n \operatorname{grad} f(x_{n-1},\xi_n)\right). \tag*{(4)}

Bonnabel [7] established the convergence of RSGD, while, more recently, Tripuraneni et al. [38] extended iterate averaging from SGD to RSGD for statistical inference. The authors used the retraction and its local inverse to recursively update the average as each new iterate becomes available, yielding

x~n=Rx~n−1(n−1Rx~n−1−1(xn)).(5)\widetilde{x}_n = R_{\widetilde{x}_{n-1}}\left(n^{-1}R_{\widetilde{x}_{n-1}}^{-1}(x_n)\right). \tag*{(5)}

The average thus moves toward the new iterate with weight 1/n1/n. For example, when M=Rd\mathcal{M} = \mathbb{R}^d, we can take Rx(v)=x+vR_x(v) = x + v and Rx−1(y)=y−xR_x^{-1}(y) = y - x. Then, (4) reduces to the standard SGD update xn=xn−1−γn∇f(xn−1,ξn)x_n = x_{n-1} - \gamma_n \nabla f(x_{n-1}, \xi_n), and (5) reduces to the ordinary recursive average x~n=x~n−1+n−1(xn−x~n−1)\widetilde{x}_n = \widetilde{x}_{n-1} + n^{-1}(x_n - \widetilde{x}_{n-1}). Section 22 provides the geometric definitions and assumptions used throughout this paper.

Under suitable local smoothness and stability assumptions, Tripuraneni et al. [38] proved asymptotic normality of the average x~n\widetilde{x}_n in (5). Mapping the averaged point back to the tangent space Tx⋆MT_{x_\star}\mathcal{M} via Rx⋆−1R_{x_\star}^{-1} and expressing the resulting tangent vector in an orthonormal basis of the tangent space gives

nRx⋆−1(x~n)⟶dN(0,Σ),Σ=A−1SA−1.\sqrt{n}R_{x_\star}^{-1}(\widetilde{x}_n) \mathrel{\mathop{\longrightarrow}\limits^{d}} \mathcal{N}(0,\Sigma), \qquad\Sigma= A^{-1}SA^{-1}.

Here A=Hess⁡F(x⋆)A = \operatorname{Hess} F(x_\star) is the Riemannian Hessian and SS is the covariance of grad⁡f(x⋆,ξ)\operatorname{grad} f(x_\star,\xi); both act on Tx⋆MT_{x_\star}\mathcal{M}. This asymptotic behavior of RSGD provides a basis for statistical inference on Riemannian manifolds. Motivated by the design of batch-means covariance estimator in Zhu et al. [46], we raise the following question:

Can the batch-means covariance estimator be adapted to the averaged RSGD, and can the resulting estimator retain the same convergence rate as in the Euclidean setting?

In this paper, we provide an affirmative answer to the above question. In particular, we use retraction maps and vector transports to extend the online OL and NOL batch-means constructions of Zhu et al. [46] to averaged RSGD. To this end, we compute for each batch BjB_j its iterate average cjc_j using the retraction-based averaging rule in (5), and construct the covariance estimator from the vectors bj,n=Rx~n−1(cj)b_{j,n} = R_{\widetilde{x}_n}^{-1}(c_j), which represent the batch averages in the tangent space at the overall average x~n\widetilde{x}_n. This extension presents two challenges. (i) As the overall average is updated, the tangent space containing the vectors {bj,n}j\{b_{j,n}\}_j changes from Tx~nMT_{\widetilde{x}_n}\mathcal{M} to Tx~n+1MT_{\widetilde{x}_{n+1}}\mathcal{M}. Thus, computing each bj,n+1=Rx~n+1−1(cj)b_{j,n+1} = R_{\widetilde{x}_{n+1}}^{-1}(c_j) directly would require revisiting all previous batch averages and contradict the online spirit. To obtain an online update, we approximate bj,nb_{j,n} by b~j,n\widetilde{b}_{j,n} (see (13)) and update these approximations recursively by accounting for the change in the overall average and applying vector transport to move the resulting vectors to the new tangent space. This avoids repeatedly recomputing the inverse retractions of previous batch averages. (ii) These approximate updates introduce errors that may accumulate over time. To control them, we separate the Euclidean batch-means error from the additional errors induced by the manifold geometry. Under standard conditions (cf. Theorem 3.1), we show that these geometric errors are of higher order than the leading Euclidean error and therefore do not affect the overall convergence rate. Altogether, we establish that the convergence rate of covariance estimation on manifolds matches that in Euclidean space.

Main contributions. The main contributions of the paper are threefold. First, we construct an online batch-means covariance estimator Σ^n\widehat{\Sigma}_n for averaged RSGD, with OL and NOL versions. To our knowledge, this is the first estimator of the limiting covariance of averaged RSGD. Our estimator can be updated online and requires neither Riemannian Hessian computations nor a prespecified terminal sample size. Second, we establish the convergence rate for our estimator. Under the conditions of Theorem 3.1, choosing the batch exponent β=2/(1−α)\beta= 2/(1-\alpha) yields the bound

E[∥(Γx⋆x~n)−1∘Σ^n∘Γx⋆x~n−Σ∥]≲n−(1−α)/4.\mathbb{E}\left[\left\|(\Gamma_{x_\star}^{\widetilde{x}_n})^{-1} \circ\widehat{\Sigma}_n \circ\Gamma_{x_\star}^{\widetilde{x}_n} - \Sigma\right\|\right] \lesssim n^{-(1-\alpha)/4}.

Here, Γxx~n\Gamma_{x}^{\widetilde{x}_n} denotes the parallel transport from TxMT_x\mathcal{M} to Tx~nMT_{\widetilde{x}_n}\mathcal{M}. This rate matches the corresponding rate of Zhu et al. [46] in the Euclidean setting and approaches n−1/8n^{-1/8} as α→1/2\alpha\to1/2. Finally, we combine covariance consistency with asymptotic normality of averaged RSGD to develop online statistical inference on manifolds. In particular, we construct asymptotically valid confidence intervals for smooth scalar functions, as well as joint confidence regions.

Related work

References

  1. [1]P.-A. Absil and J. Malick. Projection-like retractions on matrix manifolds. SIAM Journal on Optimization, 22(1):135–158, 2012.DOI
  2. [2]P.-A. Absil, C. G. Baker, and K. A. Gallivan. Trust-region methods on Riemannian manifolds. Foundations of Computational Mathematics, 7(3):303–330, 2007.DOI
  3. [3]P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, 2008.DOI
  4. [4]Z. Allen-Zhu and Y. Li. First efficient convergence for streaming k-PCA: A global, gap-free, and near-optimal rate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487–492. IEEE, 2017.
  5. [5]M. Arnaudon, C. Dombry, A. Phan, and L. Yang. Stochastic algorithms for computing means of probability measures. Stochastic Processes and their Applications, 122(4):1437–1455, 2012.arxiv.org/abs/1106.5106
  6. [6]A. Benveniste, M. Métivier, and P. Priouret. Adaptive Algorithms and Stochastic Approximations, volume 22 of Applications of Mathematics. Springer-Verlag, Berlin, 1990.
  7. [7]S. Bonnabel. Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217–2229, 2013.DOI
  8. [8]L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018.arxiv.org/abs/1606.04838
  9. [9]N. Boumal. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge, 2023.DOI
  10. [10]N. Boumal and P.-A. Absil. RTRMC: A Riemannian trust-region method for low-rank matrix completion. In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. C. N. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, pages 406–414, 2011.
  11. [11]X. Chen, J. D. Lee, X. T. Tong, and Y. Zhang. Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48(1):251–273, 2020.arxiv.org/abs/1610.08637
  12. [12]D. Davis, D. Drusvyatskiy, and L. Jiang. Asymptotic normality and optimality in nonsmooth stochastic approximation. The Annals of Statistics, 52(4):1485–1508, 2024.arxiv.org/abs/2301.06632
  13. [14]J. C. Duchi and F. Ruan. Asymptotic optimality in stochastic optimization. The Annals of Statistics, 49(1):21–48, 2021.arxiv.org/abs/1612.05612
  14. [15]A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20(2):303–353, 1998.arxiv.org/abs/physics/9806030
  15. [16]V. Fabian. On asymptotic normality in stochastic approximation. The Annals of Mathematical Statistics, 39(4):1327–1332, 1968.DOI
  16. [17]Y. Fang, J. Xu, and L. Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research, 19(78):1–21, 2018.DOI
  17. [19]Y. Gao, M. K. Ng, M. W. Mahoney, and S. Na. Online inference of constrained optimization: Primal-Dual optimality and sequential quadratic programming. arXiv preprint arXiv:2512.08948, 2025.arxiv.org/abs/2512.08948
  18. [20]J. Hájek. Local asymptotic minimax and admissibility in estimation. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 175–194, Berkeley, 1972. University of California Press.DOI
  19. [21]W. Huang, K. A. Gallivan, and P.-A. Absil. A Broyden class of quasi-Newton methods for Riemannian optimization. SIAM Journal on Optimization, 25(3):1660–1685, 2015.DOI
  20. [22]M. Ishteva, P.-A. Absil, S. Van Huffel, and L. De Lathauwer. Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme. SIAM Journal on Matrix Analysis and Applications, 32(1):115–135, 2011.DOI
  21. [23]P. Jain, C. Jin, S. M. Kakade, P. Netrapalli, and A. Sidford. Streaming PCA: Matching matrix Bernstein and near-optimal finite sample guarantees for Oja’s algorithm. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1147–1164. PMLR, 2016.arxiv.org/abs/1602.06929
  22. [24]L. Jiang, A. Roy, K. Balasubramanian, D. Davis, D. Drusvyatskiy, and S. Na. Online covariance estimation in nonsmooth stochastic approximation. In N. Haghtalab and A. Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 3079–3123. PMLR, 2025.arxiv.org/abs/2502.05305
  23. [25]W. Kuang, M. Anitescu, and S. Na. Online covariance matrix estimation in sketched Newton methods. Information and Inference: A Journal of the IMA, 15(2):iaag012, 2026.arxiv.org/abs/2502.07114
  24. [26]H. Lam and Z. Wang. Cheap bootstrap for fast uncertainty quantification of stochastic gradient descent. Journal of Machine Learning Research, 27(93):1–42, 2026.
  25. [27]L. Le Cam. Limits of experiments. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 245–261, Berkeley and Los Angeles, 1972. University of California Press.DOI
  26. [28]S. Lee, Y. Liao, M. H. Seo, and Y. Shin. Fast and robust online inference with stochastic gradient descent via random scaling. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):7381–7389, 2022.
  27. [29]S. Na. Derivative-free sequential quadratic programming for equality-constrained stochastic optimization. In Refereed Proceedings of the 2026 INFORMS Optimization Society Conference. Zenodo, 2026.
  28. [30]S. Na and M. W. Mahoney. Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming. Journal of Machine Learning Research, 26(33):1–75, 2025.
  29. [33]B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992.DOI
  30. [34]W. Ring and B. Wirth. Optimization methods on Riemannian manifolds and their application to shape space. SIAM Journal on Optimization, 22(2):596–627, 2012.DOI
  31. [35]D. Ruppert. Efficient estimations from a slowly convergent Robbins–Monro process. Technical Report 781, Cornell University, Operations Research and Industrial Engineering, 1988.
  32. [36]H. Sato, H. Kasai, and B. Mishra. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. SIAM Journal on Optimization, 29(2):1444–1472, 2019.DOI
  33. [37]J. Sun, Q. Qu, and J. Wright. Complete dictionary recovery over the sphere II: Recovery by Riemannian trust-region method. IEEE Transactions on Information Theory, 63(2):885–914, 2017.DOI
  34. [38]N. Tripuraneni, N. Flammarion, F. Bach, and M. I. Jordan. Averaging stochastic gradient descent on Riemannian manifolds. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 650–687. PMLR, 2018.arxiv.org/abs/1802.09128
  35. [39]C. Udrişte. Convex Functions and Optimization Methods on Riemannian Manifolds, volume 297 of Mathematics and Its Applications. Kluwer Academic Publishers, Dordrecht, 1994.DOI
  36. [40]Z. Wei, W. Zhu, J. Lyu, and W. B. Wu. Refining covariance matrix estimation in stochastic gradient descent through bias reduction. In Proceedings of the 29th International Conference on Artificial Intelligence and Statistics, volume 300 of Proceedings of Machine Learning Research, pages 3565–3573. PMLR, 2026a.arxiv.org/abs/2604.21203
  37. [41]Z. Wei, W. Zhu, and W. B. Wu. General weighted averaging in stochastic gradient descent: CLT and adaptive optimality. In Proceedings of the 29th International Conference on Artificial Intelligence and Statistics, volume 300 of Proceedings of Machine Learning Research, pages 1198–1206. PMLR, 2026b.
  38. [42]X. Wen, W. W. Sun, and Y. Zhang. Online tensor inference. Operations Research, 74(3):1339–1353, 2026.arxiv.org/abs/2312.17111
  39. [44]H. Zhang, S. J. Reddi, and S. Sra. Riemannian SVRG: Fast stochastic optimization on Riemannian manifolds. In Advances in Neural Information Processing Systems, volume 29, pages 4592–4600. Curran Associates, Inc., 2016.arxiv.org/abs/1605.07147
  40. [45]J. Zhou and S. Said. Fast, asymptotically efficient, recursive estimation in a Riemannian manifold. Entropy, 21(10):1021, 2019.DOI
  41. [46]W. Zhu, X. Chen, and W. B. Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 118(541):393–404, 2023.

Paper details

vlnc:W_j56gpaeq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents