betaFeedback

WorksMathematics

Self-Normalized Inference from Riemannian Stochastic Gradient Paths

Abstract

Riemannian stochastic gradient paths estimate constrained parameters, but confidence regions usually require estimating the Hessian and gradient-noise covariance. We develop self-normalized inference from one path by expressing retained iterates in a common random tangent space. Their average and centered partial sums share an unknown covariance factor that cancels in a Brownian bridge pivot. Under suitable regularity conditions, a joint expansion of the averaged estimator and integrated path controls nonlinear coordinate errors using conditional second moments. The procedure uses fixed-dimensional memory and extends to nondegenerate smooth functionals and alternative local coordinates. Numerical studies show competitive coverage relative to plug-in Wald inference while avoiding Hessian and residual-density estimation.

Introduction

Many statistical and machine learning parameters have geometric constraints: directions lie on spheres, covariance matrices and diffusion tensors in the symmetric positive definite (SPD) matrix cone, and principal subspaces on a Grassmann manifold. These lead to population problems

x⋆∈arg⁡min⁡x∈MF(x),F(x)=E{ℓ(x;Z)},(1)x_{\star} \in\arg\min_{x \in\mathcal{M}} F(x), \qquad F(x) = \mathbb{E}\{\ell(x; Z)\}, \tag*{(1)}

where (M,g)(\mathcal{M}, g) is a finite-dimensional Riemannian manifold. With sequential observations or a single sample pass, Riemannian stochastic gradients naturally estimate (1) [5, 11, 31]. Their optimization and averaging theory is well developed [1, 6].

Inference is less direct. For an unbiased stochastic Riemannian gradient G(x,Z)G(x, Z), write in the tangent space at a regular minimizer, using ⊗\otimes for tangent outer products,

H=Hess⁡F(x⋆),Ω=H−1ΣH−1,H = \operatorname{Hess} F(x_{\star}), \qquad\Omega= H^{-1}\Sigma H^{-1},
Σ=E{G(x⋆,Z)⊗G(x⋆,Z)}.(2)\Sigma= \mathbb{E}\{G(x_{\star}, Z) \otimes G(x_{\star}, Z)\}. \tag*{(2)}

Averaged stochastic approximation has covariance (2) [27, 31]. Plug-in Wald inference estimates HH and Σ\Sigma in a common tangent space. This adds a second-order calculation to a first-order optimizer. For affine-invariant matrix means, it involves differentiating a matrix logarithm; for conditional-median sensing, the population Hessian contains an unknown residual density. Even an analytic observation Hessian can be difficult to average accurately: in multi-frequency circular estimation its magnitude grows with frequency while the stochastic gradient remains bounded. A path-based procedure avoids these additional Hessian calculations and their estimation variability.

Self-normalization uses the same partial sum process in numerator and denominator, cancelling the unknown linear covariance factor in Euclidean time series and stochastic approximation [21, 28, 29]. On a manifold, constructing such sums requires common coordinates and control of nonlinear coordinate errors accumulated along the gradient path.

Classical stochastic approximation and Polyak–Ruppert averaging provide the underlying estimation theory [19, 27]. Riemannian results establish convergence, averaging, streaming kk-PCA, and fixed-step approximation [5, 11, 31]. Euclidean online inference uses covariance estimates and batch means [7], perturbed trajectories [14], or HiGrad branching [30]. Random scaling instead uses a single path [21, 22], including stochastic subgradient quantile regression where it avoids residual-density estimation [20]. Our construction reduces exactly to Euclidean random scaling; the additional difficulty is preserving its common covariance factor through nonlinear coordinates and a random tangent anchor.

Inference from manifold observations includes intrinsic and extrinsic mean limits [4], distributions meeting the cut locus [17], and empirical likelihood for Fréchet means [18]. Here the inferential input is the dependent trajectory of an online optimizer, whose covariance is determined by stochastic gradients.

To construct inference from a single path, we express retained iterates in the tangent space at a burn-in iterate and accumulate their average and centered partial sums in one pass. The central difficulty is to show that nonlinear coordinates preserve the common covariance factor needed for self-normalization. We address this through a joint Polyak–Ruppert expansion of the averaged estimator and integrated path, controlling the nonlinear remainders with conditional second moments under the localization, stability, and martingale conditions in § 3.1. This expansion yields a Brownian bridge pivot depending only on dimension, and hence confidence regions without Hessian or gradient-noise covariance estimation. Because the same cancellation survives smooth projection and changes of local coordinates, the construction also provides inference for interpretable contrasts such as squared principal-component loadings.

The rest of the paper is organized as follows. Section 2 gives the methodology, Section 3 presents the theoretical results, Section 4 reports simulations and a data illustration, and Section 5 discusses implications. The appendices contain additional experiments, geometric specializations, technical lemmas, and proofs.

Methodology

Let (M,g)(\mathcal{M},g) be a connected dd-dimensional Riemannian manifold, with tangent inner product ⟨⋅,⋅⟩x\langle\cdot,\cdot\rangle_x and norm ∥⋅∥x\|\cdot\|_x. We write I\mathrm{I} for the identity operator, ∥⋅∥op\|\cdot\|_{\mathrm{op}} for the operator norm, and vec⁡\operatorname{vec} for column-stacking of a matrix. On a strongly convex normal neighborhood, Exp⁡x\operatorname{Exp}_x is the exponential map, Log⁡x\operatorname{Log}_x its local inverse, and Px→y\mathcal{P}_{x\to y} parallel transport along the minimizing geodesic.

Recursion and averaging in a fixed chart

Let Fk=σ(Z1,…,Zk,x0)\mathcal{F}_k=\sigma(Z_1,\ldots,Z_k,x_0) and let Gk+1G_{k+1} be an adapted unbiased gradient field: E[Gk+1(x)∣Fk]=grad⁡F(x)\mathbb{E}[G_{k+1}(x)\mid\mathcal{F}_k]=\operatorname{grad}F(x). For i.i.d. observations, Gk+1(x)=G(x,Zk+1)G_{k+1}(x)=G(x,Z_{k+1}). We use

xk+1=Rxk{−ηk+1Gk+1(xk)},ηk=η0k−β,(3)x_{k+1}=\mathcal{R}_{x_k}\{-\eta_{k+1}G_{k+1}(x_k)\},\qquad\eta_k=\eta_0 k^{-\beta}, \tag*{(3)}

where η0>0\eta_0>0 and Rx\mathcal{R}_x is a C2C^2 retraction, with Rx(0)=x\mathcal{R}_x(0)=x and DRx(0)=ID\mathcal{R}_x(0)=\mathrm{I}. The exponential map Rx=Exp⁡x\mathcal{R}_x=\operatorname{Exp}_x is one such choice. Discard the first bnb_n iterates, where the deterministic burn-in satisfies

bn→∞,bn/n→0,Nn=n−bn,(4)b_n\to\infty,\qquad b_n/n\to0,\qquad N_n=n-b_n, \tag*{(4)}

Thus the number of discarded iterates grows with nn, while their fraction vanishes and Nn/n→1N_n/n\to1. This is the diverging burn-in used below. Set an=xbna_n=x_{b_n} to fix the tangent space for averaging; if the recursion converges to x⋆x_\star, this anchor is consistent. Assumptions 3.1 and 3.4 specify the localization and stability needed for the retained path. On the common normal neighborhood define

vk,n=Log⁡an(xk)∈TanM,bn<k≤n,(5)v_{k,n}=\operatorname{Log}_{a_n}(x_k)\in T_{a_n}\mathcal{M},\qquad b_n<k\le n, \tag*{(5)}

and the fixed-chart Polyak–Ruppert estimate

vˉn=Nn−1∑k=bn+1nvk,n,x^n=Exp⁡an(vˉn).\bar{v}_n=N_n^{-1}\sum_{k=b_n+1}^{n}v_{k,n},\qquad\hat{x}_n=\operatorname{Exp}_{a_n}(\bar{v}_n).

Smooth inverse retractions provide alternative coordinates; Proposition B.4 establishes their first order equivalence.

Centered path and confidence region

For 0≤m≤Nn0\le m\le N_n, with S0,n=C0,n=0S_{0,n}=C_{0,n}=0, define

Sm,n=∑j=1mvbn+j,n,S_{m,n}=\sum_{j=1}^{m}v_{b_n+j,n},
Cm,n=Sm,n−mNnSNn,n.C_{m,n}=S_{m,n}-\frac{m}{N_n}S_{N_n,n}.

The centered sums give

V^n=Nn−2∑m=1NnCm,n⊗Cm,n,(6)\hat{V}_n=N_n^{-2}\sum_{m=1}^{N_n}C_{m,n}\otimes C_{m,n}, \tag*{(6)}

where (u⊗v)w=u⟨v,w⟩an(u\otimes v)w=u\langle v,w\rangle_{a_n}. Since the centered sums fluctuate on the Nn\sqrt{N_n} scale, this normalization gives a nondegenerate limit. For a candidate xx, define en(x)=vˉn−Log⁡an(x)e_n(x)=\bar{v}_n-\operatorname{Log}_{a_n}(x) in orthonormal tangent coordinates and put

Tn(x)=Nnen(x)TV^n−1en(x).(7)T_n(x)=N_n e_n(x)^{\mathsf{T}}\hat{V}_n^{-1}e_n(x). \tag*{(7)}

Let WdW_d be a standard dd-dimensional Brownian motion on [0,1][0,1] and define

Bd(r)=Wd(r)−rWd(1),B_d(r)=W_d(r)-rW_d(1),
Qd=∫01Bd(r)Bd(r)T dr,(8)Q_d=\int_0^1 B_d(r)B_d(r)^{\mathsf{T}}\,\mathrm{d}r, \tag*{(8)}
Td=Wd(1)TQd−1Wd(1).T_d=W_d(1)^{\mathsf{T}}Q_d^{-1}W_d(1).

For 0<α<10<\alpha<1, let cd,1−αc_{d,1-\alpha} be the (1−α)(1-\alpha) quantile of TdT_d and report

Cn,1−α={x:Tn(x)≤cd,1−α}(9)C_{n,1-\alpha}=\{x:T_n(x)\le c_{d,1-\alpha}\} \tag*{(9)}

within the chart domain. In tangent coordinates, (9) is an ellipsoid centered at vˉn\bar{v}_n. An eigenvalue λ^j\hat{\lambda}_j of V^n\hat{V}_n gives semiaxis cd,1−αλ^j/Nn\sqrt{c_{d,1-\alpha}\hat{\lambda}_j/N_n}; the exponential map sends this ellipsoid to the manifold.

Algorithm 1 Estimation and inference from a single path
Require: Initial point $x_0$, gradient stream, gains $\eta_k$, sample size $n$, burn-in $b_n$, and critical value $c_{d,1-\alpha}$.
Ensure: Estimate $\hat{x}_n$ and region $C_{n,1-\alpha}$.
1: Run (3) for $b_n$ steps.
2: Set $a_n \leftarrow x_{b_n}$ and $N \leftarrow n-b_n$.
3: Initialize $S=B=0\in T_{a_n}\mathcal{M}$ and $A=0$.
4: for $m=1,\ldots,N$ do
5: Continue (3) to obtain $x_{b_n+m}$.
6: $v_m\leftarrow\operatorname{Log}_{a_n}(x_{b_n+m})$.
7: $S\leftarrow S+v_m$.
8: $A\leftarrow A+S\otimes S$.
9: $B\leftarrow B+mS$.
10: end for
11: $\bar{v}_n\leftarrow S/N$ and $\hat{x}_n\leftarrow\operatorname{Exp}_{a_n}(\bar{v}_n)$.
12: Compute $\widehat{V}_n$ by (10).
13: return $\hat{x}_n$ and $C_{n,1-\alpha}$ from (9).

Computation in one pass

Write N=NnN=N_n, Sm=Sm,nS_m=S_{m,n}, and maintain AN=∑m=1NSm⊗SmA_N=\sum_{m=1}^{N}S_m\otimes S_m and BN=∑m=1NmSmB_N=\sum_{m=1}^{N}mS_m. Expanding the centered products gives

References

  1. [1]Absil, P.-A., Mahony, R., and Sepulchre, R. (2008). Optimization Algorithms on Matrix Manifolds. Princeton University Press.DOI
  2. [2]Afsari, B. (2011). Riemannian Lᵖ center of mass: existence, uniqueness, and convexity. Proceedings of the American Mathematical Society, 139, 655–673.DOI
  3. [3]Balzano, L., Nowak, R., and Recht, B. (2010). Online identification and tracking of subspaces from highly incomplete information. In Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, 704–711.arxiv.org/abs/1006.4046
  4. [4]Bhattacharya, R. and Patrangenaru, V. (2005). Large sample theory of intrinsic and extrinsic sample means on manifolds. II. The Annals of Statistics, 33, 1225–1259.DOI
  5. [5]Bonnabel, S. (2013). Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Automatic Control, 58, 2217–2229.DOI
  6. [6]Boumal, N. (2023). An Introduction to Optimization on Smooth Manifolds. Cambridge University Press.DOI
  7. [7]Chen, X., Lee, J. D., Tong, X. T., and Zhang, Y. (2020). Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48, 251–273.arxiv.org/abs/1610.08637
  8. [8]Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. (2009). Modeling wine preferences by data mining from physicochemical properties. Decision Support Systems, 47, 547–553.DOI
  9. [9]Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. (2009). Wine Quality [Dataset]. UCI Machine Learning Repository. https://doi.org/10.24432/C56S3T.
  10. [10]Dryden, I. L., Koloydenko, A., and Zhou, D. (2009). Non-Euclidean statistics for covariance matrices, with applications to diffusion tensor imaging. The Annals of Applied Statistics, 3, 1102–1123.DOI
  11. [11]Durmus, A., Jiménez, P., Moulines, E., and Said, S. (2021). On Riemannian stochastic approximation schemes with fixed step-size. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, PMLR 130, 1018–1026.arxiv.org/abs/2102.07586
  12. [12]Edelman, A., Arias, T. A., and Smith, S. T. (1998). The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20, 303–353.arxiv.org/abs/physics/9806030
  13. [13]Eltzner, B. and Huckemann, S. F. (2019). A smeary central limit theorem for manifolds with application to high-dimensional spheres. The Annals of Statistics, 47, 3360–3381.arxiv.org/abs/1801.06581
  14. [14]Fang, Y., Xu, J., and Yang, L. (2018). Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research, 19(78), 1–21.DOI
  15. [15]Fletcher, P. T. and Joshi, S. (2007). Riemannian geometry for the statistical analysis of diffusion tensor data. Signal Processing, 87, 250–262.DOI
  16. [16]Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application. Academic Press.
  17. [17]Hotz, T., Le, H., and Wood, A. T. A. (2024). Central limit theorem for intrinsic Fréchet means in smooth compact Riemannian manifolds. Probability Theory and Related Fields, 189, 1219–1246.arxiv.org/abs/2210.17191
  18. [18]Kurisu, D. and Otsu, T. (2026). Empirical likelihood for manifolds. Journal of the Royal Statistical Society, Series B, 88, 91–119.DOI
  19. [19]Kushner, H. J. and Yin, G. G. (2003). Stochastic Approximation and Recursive Algorithms and Applications, second edition. Springer.
  20. [20]Lee, S., Liao, Y., Seo, M. H., and Shin, Y. (2025). Fast inference for quantile regression with tens of millions of observations. Journal of Econometrics, 249, 105673.
  21. [21]Lee, S., Liao, Y., Seo, M. H., and Shin, Y. (2022). Fast and robust online inference with stochastic gradient descent via random scaling. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7), 7381–7389.
  22. [22]Li, X., Liang, J., Chang, X., and Zhang, Z. (2022). Statistical estimation and online inference via local SGD. In Proceedings of the 35th Conference on Learning Theory, PMLR 178, 1613–1661.arxiv.org/abs/2109.01326
  23. [23]Mardia, K. V. and Jupp, P. E. (2000). Directional Statistics. Wiley.DOI
  24. [24]Oja, E. (1982). Simplified neuron model as a principal component analyzer. Journal of Mathematical Biology, 15, 267–273.pubmed.ncbi.nlm.nih.gov/7153672
  25. [25]Pennec, X. (2006). Intrinsic statistics on Riemannian manifolds: basic tools for geometric measurements. Journal of Mathematical Imaging and Vision, 25, 127–154.DOI
  26. [26]Pennec, X., Fillard, P., and Ayache, N. (2006). A Riemannian framework for tensor computing. International Journal of Computer Vision, 66, 41–66.
  27. [27]Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30, 838–855.DOI
  28. [28]Shao, X. (2010a). A self-normalized approach to confidence interval construction in time series. Journal of the Royal Statistical Society, Series B, 72, 343–366.arxiv.org/abs/1005.2137
  29. [29]Shao, X. (2010b). Corrigendum: A self-normalized approach to confidence interval construction in time series. Journal of the Royal Statistical Society, Series B, 72, 695–696.DOI
  30. [30]Su, W. J. and Zhu, Y. (2023). HiGrad: uncertainty quantification for online learning and stochastic approximation. Journal of Machine Learning Research, 24(124), 1–53.
  31. [31]Tripuraneni, N., Flammarion, N., Bach, F., and Jordan, M. I. (2018). Averaging stochastic gradient descent on Riemannian manifolds. In Proceedings of the 31st Conference on Learning Theory, PMLR 75, 650–687.arxiv.org/abs/1802.09128

Paper details

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

views · 7

downloads · 0

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

  • Mathematics

Generative AI tools

View statement
Looking for related papers…
Contents