acceptodds
Under review as a conference paper at ICLR 2027

Riemannian Newton Methods with Statistical Inference

Abstract

We develop online statistical inference for Polyak-Ruppert averages of inexact Newton iterates on Riemannian manifolds. A local asymptotic representation separates observation noise, solver randomization, and accumulated implementation bias, and yields one-pass covariance estimators and asymptotically valid Wald regions under local regularity and centering conditions. Independent fresh solves add a positive semidefinite term to the score-sandwich covariance; averaging solver replicas reduces this term in inverse proportion to their number. Slowly varying predictable gains instead cancel from the first order law. Product torus simulations show how Newton scaling shortens an ill-conditioned transient and how retaining solver variation restores coverage. Intrinsic means and principal subspaces provide geometric applications, with a streaming data illustration.

Primary area:
optimization
Keywords:
Manifolds data, Newton Methods, Online inference, Riemannian optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_iyNJOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the statistical inference of randomized newton iterates for estimating parameters which exist on a Reimanian manifold. In particular, the algorithm in question is Polyak-Rupert averaging of the following sequence: The sequence of randomized Newton iterates (Hessian-conditioned SGD on the manifold). The randomization comes from solving a random projection of the linear system required to estimate the inverse of the Hessian. The main results of this work is not just establishing the asymptotic variance for the CLT of the estimator, but demonstrating that when the estimate of the random solve inverted Hessian is a fresh random estimate at each iteration that this introduces a lasting term on the asymptotic variance and if the random solve inverted Hessian is replaced with a running average of all the past estimates at each step that the estimator remains asymptotically unbiased and the additional term in the CLT variance arising from the random solve disappears. The paper demonstrates the proposed algorithm on a few numerical examples, one toy and one real world dataset without an existing ground truth (the ladder is only in the appendix).

It is my understanding that the contribution of demonstrating how the Hessian averaging step can remove the additional term from the asymptotic variance in contrast to the 'fresh random estimate' version of the algorithm is not new and is part of a recent line of work. The novelty here is adapting the same idea to the Riemannian Manifold setting.

I emphasize here that I do not have the sufficient background to understand any of the low level details of this paper and certainly not to check for correctness. That said my overall impressions (which were in general positive) are based entirely on my (hopefully correct) high level understanding of what this paper accomplished and where it stands relative to existing work.

Critical strengths

The paper provides a CLT for Polyak Rupert averaged Randomized Newton Iterates for estimating parameters existing on Riemannian manifolds. Further they demonstrate a scheme for the randomized solve step that does not leave lasting variation in the CLT, in contrast to the default randomized solve at each iterate which they also demonstrate leaves an additional covariance term in the corresponding CLT. While the idea for the randomization mechanism which does not leave a lasting effect is not new, demonstrating the results on Reimannian Manifolds in contrast to euclidean space seems to be a solid contribution.

Critical weaknesses

The experimental section is perhaps a bit weak. The examples are limited and it seems the authors admit that the Taurus example is perhaps somewhat simple and not substantially differentiated from the Euclidean case.

Questions for authors

Could you provide some more examples of applications where one might use this algorithm?

Does the Taurus example differentiate the manifold version of the algorithm from the euclidean version?

5 comments

Thank you for your time and valuable comments.

Note: Because of the 5000-character limit, we divided our response into two comments.

The distinction between predictable gains and fresh randomization is established in stochastic approximation. A fresh solver can retain random variation after the Hessian estimate has stabilized.

Under Theorem 3.4's independence, finite second moment and invertibility conditions, write ΔP=P~−Pˉ\Delta P=\widetilde P-\bar P and

\qquad V-V_{\mathrm{sand}} =H^{-1}\bar P^{-1}R(\bar P^{\ast})^{-1}(H^{\ast})^{-1}.$$ The extra covariance is positive semidefinite. Moreover, $$\operatorname{tr}(R) =\mathbb E\\|\Delta P S^{1/2}\\|_F^2,$$ so it vanishes exactly when $\Delta P S^{1/2}=0$ almost surely. It is nonzero when the solver fluctuates on the score covariance support, although individual contrasts can still have zero inflation. In particular, positive-definite $S$ and a nonconstant solver imply a nonzero extra covariance. Theorem 3.6 instead treats predictable gains under its inverse gain Abel-summation and weighted remainder conditions. Its centered conclusion is first-order asymptotic and uses the stated accumulated-bias conditions. **W1.** We have clarified the local CLT, bias-correction scope, and covariance tracking, and added the curved-sphere comparison below. This experiment measures how including solver variation changes coverage under non-zero curvature. The product torus was chosen as a controlled benchmark to isolate transient conditioning and solver noise studentization within a chart linear coordinate system, deliberately decoupling these effects from non-zero curvature. To directly investigate the combined interaction of nonlinear manifold curvature, learned curvature, and randomized solves, we conducted a dedicated benchmark on the two dimensional unit sphere $\mathbb S^2$. Observations were generated via the exponential map from clipped anisotropic tangent Gaussian draws (coordinate standard deviations $0.30$ and $0.18$, radius cap $0.85$). From a fixed non-zero initial offset, we compared RSGD, Predictable Newton (sample-Hessian Newton), and Proposed ($m=4$, fresh coordinate sketch-and-project with learned Hessian). Each configuration used $n=1024$ observations and a 128-step burn-in ($c=0.4$). Observation streams were paired and solver seeds generated independently. | Method | Reported coverage (%) | Score-only coverage (%) | Geodesic RMSE | |---|---:|---:|---:| | RSGD | 96.2 | 96.2 | 0.01171 | | Predictable Newton | 96.2 | 96.2 | 0.01171 | | Proposed ($m=4$) | **93.6** | **90.6** | 0.01350 | The 95% Wald regions are joint in two dimensions. In a low dimensional setting ($d=2$), sketching introduces solver variance without offering the high dimensional $O(md^2)$ versus $O(d^3)$ computational advantage, leading to a mild finite-sample variance penalty (RMSE $0.01350$ vs. $0.01171$). Crucially, this benchmark serves as a diagnostic for covariance estimation under non-zero curvature: 1. Under fresh solver randomization, standard score-only studentization underestimates variance, resulting in under coverage ($90.6\\%$). 2. Direction-based studentization increases coverage from 90.6% to 93.6%, a gain of 3.0 percentage points, by including solver variation in the Wald region. The two predictable methods exhibit nearly identical aggregate errors, with negligible paired mean squared-error difference, though their pathwise trajectories and Wald statistics differ. The sphere experiment shows the coverage gain from direction-based covariance correction alongside the larger RMSE caused by solver randomization. *Continued in Part 2/2 with Q1–Q2 and the references.*

Part 2/2 of our response to Reviewer iyNJ, continued from Part 1/2. We address Q1–Q2 below, followed by the references.

Q1. To demonstrate broader geometric applicability, Corollaries B.21–B.24 provide explicit specializations for intrinsic Fréchet means, directional sphere means, affine-invariant covariance centers on the SPD manifold, and Grassmann principal subspaces for streaming dimension reduction (illustrated via the WDBC data). Furthermore, the two-dimensional sphere benchmark in W1 of Part 1/2 evaluates the algorithm on a curved Riemannian state space: direction-based studentization raises coverage from 90.6% to 93.6% for nominal 95% regions.

Q2. The product torus was chosen as a controlled benchmark to isolate transient conditioning and solver-noise studentization within a chart-linear coordinate system, deliberately decoupling these effects from non-zero curvature.

To demonstrate broader geometric applicability, Corollaries B.21–B.24 provide explicit specializations for intrinsic Fréchet means, directional sphere means, affine-invariant covariance centers on the SPD manifold, and Grassmann principal subspaces for streaming dimension reduction (illustrated via the WDBC data). Furthermore, the two-dimensional sphere benchmark in W1 of Part 1/2 evaluates the algorithm on a curved Riemannian state space: direction-based studentization raises coverage from 90.6% to 93.6% for nominal 95% regions.

References.

  • X. Du, W. Zhu, W. B. Wu, and S. Na (2025), Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling, arXiv:2505.18327.
  • X. Du, E. Rebrova, M. Dereziński, and S. Na (2026), Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling, arXiv:2609.12421.
  • H. Wang, X. Du, and S. Na (2026), Inference of Online Newton Methods with Nesterov's Accelerated Sketching, ICML 2026.
  • N. Tripuraneni, N. Flammarion, F. Bach, and M. I. Jordan (2018), Averaging Stochastic Gradient Descent on Riemannian Manifolds, COLT 2018.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Thank you again for your careful review and constructive feedback. We hope that our responses and revisions have addressed your concerns and questions. If you find that they resolve your main concerns, we would be grateful if you would reconsider your assessment and score in light of these changes. We would be happy to clarify any outstanding points.

Reviewer_QBvwOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper examines online inference for Polyak-Ruppert averages of inexact Newton iterations on finite-dimensional Riemannian manifolds. A local tangent-space representation is employed to address observation noise. A randomized-solver variation is also considered, along with accumulated implementation bias. The approach yields covariance estimators and Wald regions under explicitly stated local conditions. Introducing independent solver randomness results in a positive semidefinite covariance term that decreases inversely with the number of independent replicas. The resulting gains are gradual and predictable. Action is canceled under a condition involving inverse gain. Simulations on a chart-linear product-torus are used to elucidate the main mechanisms, and an application is demonstrated through a Grassmann streaming example.

Critical strengths
  1. The paper identifies the appropriate inferential object and establishes its estimability. Implemented-direction covariance preserves solver variation, and explicit bias analysis clarifies why a covariance correction cannot repair noncentering. This materially connects the asymptotic law to a usable uncertainty estimator.
  2. The mathematical treatment addresses implementation details that often remain implicit. Retraction averaging, accumulated errors, covariance consistency under limited moments, and fixed-budget sketch The specified conditions give the framework greater substantive depth than the covariance identity alone.
Critical weaknesses

The argument regarding applicability is still incomplete when it comes to the more difficult aspects of stochastic geometry. Assumptions B.1 through B.7 involve almost-sure confinement to a sufficiently small neighbourhood, a mean-square state rate, negligible accumulated remainders, and averaging equivalence (pages 19 to 21). Even the fixed-budget solver construction mentioned in Proposition B.20 includes the invariant-basin assumption. The authors themselves admit that a step cap does not guarantee this assumption. The fully verified construction in Example B.28 is a bounded Euclidean diagonal quadratic whose Hessian is known. Thus, the paper fails to address the assumptions in the combined case of nonlinear manifold geometry, learned curvature, randomized solves, and feasible inference.

These experiments do not greatly address this issue. On the product torus, transport, recursion, and averaging are exactly linear within the invariant chart (pp. 7–8 and 12). This allows the random-product variance mechanism to be tested while eliminating the geometric and Hessian-estimation difficulties which led to the development of the framework. The Grassmann application makes use of a fixed calibration preconditioner and provides illustrative intervals rather than carrying out repeated-sampling calibration. The headline covariance identity by itself is not enough to show the importance of the contribution. Equation (11) can be obtained directly by breaking down the solver into its mean and its centered fluctuation, and the inverse-replica-count law then results from the assumption of independence. The real contribution is therefore in verifying the manifold reduction and the feasibility of inference for a actual algorithm. In that case, however, it is still weaker than the presentation implies. Bias correction that is feasible is also more limited than the general decomposition. Although Equation (9) supposes the use of a consistent bias estimator, the computable approach in Section B.6.2 ignores the bias arising from the solver-score product. The paper fails to provide a general correction for the dependent or residual-adaptive solves which can cause exactly this problem.

Questions for authors

Clarification affecting novelty: Which precise theorem conclusions or assumptions extend beyond combining existing Euclidean averaged sketched-Newton inference with established Riemannian averaging? A direct It would materially affect the assessment of significance. Clarification affecting applicability: What arguments or recorded diagnostics support the local-basin, common-chart, and derivative-invertibility conditions in the WDBC implementation? How often does its step What is the activation capacity, and how sensitive are the intervals to initialization and burn-in? Evidence affecting practical significance: Do existing results include repeated-sampling coverage and region-size comparisons for learned curvature and fresh solver randomization on a curved manifold, or equal-computation comparisons when exact solves are expensive? If none do, that combined setting should remain an explicit validation limit. Adding such experiments is a recommendation, not a request to restate an existing theorem.

6 comments

Thank you for your time and valuable comments.

Note: Because of the 5000-character limit, we divided our response into three comments.

W1. We have clarified the local CLT, bias correction scope, and covariance tracking, and added the sphere comparison below. This experiment measures how including solver variation changes coverage under non-zero curvature.

The product torus benchmark was intentionally designed to isolate the solver variance mechanism within a linear coordinate chart. WDBC illustrates a Grassmann streaming setting with a fixed preconditioner and a learned reporting Hessian.

To directly investigate the combined interaction of nonlinear manifold curvature, learned curvature, and randomized solves, we conducted a dedicated benchmark on the two dimensional unit sphere S2\mathbb S^2. Observations were generated via the exponential map from clipped anisotropic tangent Gaussian draws (coordinate standard deviations 0.300.30 and 0.180.18, radius cap 0.850.85). From a fixed non-zero initial offset, we compared RSGD, Predictable Newton (sample-Hessian Newton), and Proposed (m=4m=4, fresh coordinate sketch-and-project with learned Hessian). Each configuration used n=1024n=1024 observations and a 128 step burn-in (c=0.4c=0.4). Observation streams were paired and solver seeds generated independently.

MethodReported coverage (%)Score-only coverage (%)Geodesic RMSE
RSGD96.296.20.01171
Predictable Newton96.296.20.01171
Proposed (m=4m=4)93.690.60.01350

The 95% Wald regions are joint in two dimensions. In a low dimensional setting (d=2d=2), sketching introduces solver variance without offering the high dimensional O(md2)O(md^2) versus O(d3)O(d^3) computational advantage, leading to a mild finite sample variance penalty (RMSE 0.013500.01350 vs. 0.011710.01171). Crucially, this benchmark serves as a diagnostic for covariance estimation under non-zero curvature:

  1. Under fresh solver randomization, standard score-only studentization underestimates variance, resulting in under-coverage (90.690.6\\%).
  2. Direction based studentization increases coverage from 90.6% to 93.6%, a gain of 3.0 percentage points, by including solver variation in the Wald region.

The two predictable methods exhibit nearly identical aggregate errors, with negligible paired mean squared error difference, though their pathwise trajectories and Wald statistics differ. The curved sphere experiment shows the coverage gain from direction based covariance correction alongside the larger RMSE caused by solver randomization.

W2. While the algebraic decomposition of independent solver fluctuations reflects general variance splitting principles, our primary contribution is establishing online inference for Polyak–Ruppert averaged iterates directly on Riemannian manifolds with complete geometric error accounting.

Theorem 3.1 establishes the joint local tangent space representation after transporting the score, solver product, and complete implementation discrepancy; Theorem 3.3 supplies one pass direction based studentization, and Theorem 3.6 isolates a distinct predictable gain cancellation regime. These statements account for generic C2C^2 retractions, explicit accumulated retraction errors, and the signed bias boundary. By comparison, earlier manifold averaging results (e.g., Tripuraneni et al., 2018, Assumption 2 for RSGD) require confinement and second order retractions at the target. Furthermore, while constrained Euclidean optimization, such as the primal–dual sketched SQP formulation of Du et al. (2025), uses extrinsic constraints, our framework operates intrinsically on Riemannian geometries and explicitly accounts for frame identification and retraction discrepancies in the asymptotic distribution and studentization.

The bias corrected portion of Theorem 3.3 assumes a consistent estimator of the signed accumulated bias; its correction applies the positive shift needed to remove the −A−1b-\mathrm{A}^{-1}b displacement. We give the implementation discrepancy construction explicitly. If the two conditional solver score product means satisfy bk+1ξ=bk+1q=0b_{k+1}^{\xi}=b_{k+1}^{q}=0, record the full discrepancy ek+1e_{k+1} and use

b^na=n−1/2∑k=0n−1Txk→aek+1.\widehat b_n^a=n^{-1/2}\sum_{k=0}^{n-1}\mathcal T_{x_k\to a}e_{k+1}.

Under the signed accumulated bias and vanishing centered discrepancy variance conditions, frame identification maps its predictable part to the signed bias sum, while the centered martingale part vanishes. Thus b^na→pba\widehat b_n^a\xrightarrow{p}b_a, using one additional running vector. Unknown solver score product biases induced by serial dependence or residual adaptive solves require an additional estimator. For centered settings where b=0b=0, the uncorrected estimator supplies the stated inference.

Continued in Part 2/3 with Q1–Q2. Q3 and references follow in Part 3/3.

Part 2/3 of our response to Reviewer QBvw, continued from Part 1/3. We address Q1–Q2 below.

Q1. While the algebraic decomposition of independent solver fluctuations reflects general variance splitting principles, our primary contribution is establishing online inference for Polyak–Ruppert averaged iterates directly on Riemannian manifolds with complete geometric error accounting.

Theorem 3.1 establishes the joint local tangent space representation after transporting the score, solver product, and complete implementation discrepancy; Theorem 3.3 supplies one-pass direction based studentization, and Theorem 3.6 isolates a distinct gain cancellation regime. These statements account for generic C2C^2 retractions, explicit accumulated retraction/frame errors, and the signed bias boundary. By comparison, earlier manifold averaging results (e.g., Tripuraneni et al., 2018, Assumption 2 for RSGD) require confinement and second order retractions at the target. Furthermore, while constrained Euclidean optimization, such as the primal–dual sketched SQP formulation of Du et al. (2025), uses extrinsic constraints, our framework operates intrinsically on Riemannian geometries and explicitly accounts for coherent-frame identification and retraction discrepancies in the asymptotic distribution and studentization.

Q2. In the WDBC analysis, a 169-record calibration set supplied feature scaling, initialization, and the update preconditioner; 400 streaming records formed the analysis stream (350 retained after burn-in). The covariance and second moment eigengaps were approximately 8.22 and 5.70, respectively. The 0.300.30-radian step cap activated only twice across 400 updates; the primary retained derivative maintained a minimum eigenvalue of 5.37.

In sensitivity checks crossing burn-ins 0,50,100\\{0, 50, 100\\} with initial-angle perturbations of 00 and 0.100.10 radians, the largest anchor angle remained below 0.4460.446 radians, and all retained derivative estimates remained strictly positive definite. Initialization sensitivity was minimal: changing the initial angle altered projector mass estimates by less than 0.00250.0025 and moved interval endpoints by less than 0.00290.0029. Increasing burn-in from 0 to 100 changed the size-group interval from [0.273,0.525][0.273,0.525] to [0.223,0.506][0.223,0.506]; its width increased from 0.2520.252 to 0.2830.283. These fixed stream changes quantify sensitivity to burn-in. The temporal independence assumption concerns successive records; within record feature correlation is part of the multivariate observation model. The intervals remain pointwise and conditional on calibration, where the target is the leading eigenspace of the second moment about the fixed calibration center.

Continued in Part 3/3 with Q3 and the references.

Part 3/3 of our response to Reviewer QBvw, continued from Part 2/3. We address Q3 below, followed by the references.

Q3. The sphere experiment reported under W1 (Part 1/3) directly examines the interaction of nonlinear manifold curvature, learned curvature, and randomized solves. In that design, including solver variation in the covariance estimate increases joint 95% Wald coverage from 90.6% to 93.6%, a gain of 3.0 percentage points. This improvement accompanies a higher geodesic RMSE of 0.01350 for Proposed, compared with 0.01171 for both RSGD and Predictable Newton. The full experimental setup and comparison table are given in W1 of Part 1/3.

The sphere comparison reports joint coverage and geodesic point-estimation RMSE; confidence region area or volume remains a separate unreported comparison.

The timings on the two dimensional torus illustrate the expected scaling trade-off: when the dimension is small (d=2d=2) and the Hessian is diagonal, exact inversion is computationally trivial, so randomized sketching introduces per-iteration sampling overhead without its asymptotic dimensional benefits (O(md2)O(md^2) vs. O(d3)O(d^3)).

The observation-budget advantage is governed by curvature conditioning: its gains are most pronounced in ill conditioned regimes (κ=300\kappa=300), where second order preconditioning eliminates RSGD's severe transient slowdown. The timing comparison concerns a low-dimensional problem with inexpensive exact solves. Randomized sketching targets high dimensional problems where solving the Newton system is costly; an equal computation comparison in that regime remains to be evaluated.

References.

  • X. Du, W. Zhu, W. B. Wu, and S. Na (2025), Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling, arXiv:2505.18327.
  • X. Du, E. Rebrova, M. Dereziński, and S. Na (2026), Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling, arXiv:2609.12421.
  • H. Wang, X. Du, and S. Na (2026), Inference of Online Newton Methods with Nesterov's Accelerated Sketching, ICML 2026.
  • N. Tripuraneni, N. Flammarion, F. Bach, and M. I. Jordan (2018), Averaging Stochastic Gradient Descent on Riemannian Manifolds, COLT 2018.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Reviewer_k6mcOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper develops local asymptotic inference for averaged randomized Newton methods on Riemannian manifolds. It represents iterates in a common tangent frame, decomposes solver and score errors, proves a root-n CLT for the averaged estimator, and derives one-pass covariance estimators. A key distinction is between fresh randomized solvers, which require direction covariance including solver variance, and slowly varying predictable preconditioners, which permit score-sandwich inference. It analyzes Newton preconditioning versus RSGD, specializes to Fréchet means, SPD covariance centers, and Grassmann PCA, and validates with a product-torus simulation and WDBC subspace example.

Critical strengths

The main strength is a coherent inferential theory that does not require solver randomness to vanish, with an explicit covariance decomposition and a clear separation between optimization conditioning and statistical efficiency. The fresh-solver direction-covariance construction and predictable-gain score-sandwich branch are consequential because they tell practitioners which covariance to report under fixed solver budgets. The local CLT and application-specific derivative/score calculations make the framework reusable beyond one model. The conditioning analysis also clarifies when Newton scaling improves transients but not the asymptotic sandwich covariance.

Critical weaknesses

The theory relies on strong, intertwined local assumptions: an invariant working basin, consistent mean solver/Jacobian, uniform moment and Lindeberg conditions, and root-n averaging equivalence. Sufficiency results are given, but there is limited empirical evidence that these are verifiable in realistic nonlinear, nonsymmetric, adaptive, or dependent-stream settings. Validation is narrow: a linearizable product torus and one WDBC application. Computational cost and comparison with concurrent sketched-Newton inference are not thoroughly benchmarked, limiting confidence in practical reach.

Questions for authors
  1. How do you recommend verifying the invariant-basin/localization condition and a consistent mean-solver estimator in generic nonlinear Riemannian problems, beyond the product-torus example?

  2. How does the proposed covariance inflation and fixed-budget guarantee compare theoretically and empirically with Du et al. (2025, 2026) and Wang et al. (2026) for sketched Newton inference?

  3. For nonsymmetric estimating fields, what concrete Jacobian estimator and invertibility safeguard do you recommend, and can you demonstrate it empirically?

  4. The paper leaves dependent streams and residual-adaptive solvers to future work; which theorem conditions fail first in those settings, and how material is that limitation?

4 comments

Thank you for your time and valuable comments.

Note: Because of the 5000-character limit, we divided our response into three comments.

W1. We have clarified the local CLT, bias correction scope, and covariance tracking, and added the sphere comparison below. This experiment measures how including solver variation changes coverage under non-zero curvature.

The product torus benchmark was intentionally designed to isolate the solver variance mechanism within a linear coordinate chart. WDBC illustrates a Grassmann streaming setting with a fixed preconditioner and a learned reporting Hessian.

To directly investigate the combined interaction of nonlinear manifold curvature, learned curvature, and randomized solves, we conducted a dedicated benchmark on the two dimensional unit sphere S2\mathbb S^2. Observations were generated via the exponential map from clipped anisotropic tangent Gaussian draws (coordinate standard deviations 0.300.30 and 0.180.18, radius cap 0.850.85). From a fixed non-zero initial offset, we compared RSGD, Predictable Newton (sample-Hessian Newton), and Proposed (m=4m=4, fresh coordinate with learned Hessian). Each configuration used n=1024n=1024 observations and a 128 step burn-in (c=0.4c=0.4). Observation streams were paired and solver seeds generated independently.

MethodReported coverage (%)Score-only coverage (%)Geodesic RMSE
RSGD96.296.20.01171
Predictable Newton96.296.20.01171
Proposed (m=4m=4)93.690.60.01350

The 95% Wald regions are joint in two dimensions. In a low dimensional setting (d=2d=2), sketching introduces solver variance without offering the high dimensional O(md2)O(md^2) versus O(d3)O(d^3) computational advantage, leading to a mild finite sample variance penalty (RMSE 0.013500.01350 vs. 0.011710.01171). Crucially, this benchmark serves as a diagnostic for covariance estimation under non-zero curvature:

  1. Under fresh solver randomization, standard score studentization underestimates variance, resulting in under coverage (90.690.6\\%).
  2. Direction based studentization increases coverage from 90.6% to 93.6%, a gain of 3.0 percentage points, by including solver variation in the Wald region.

The two predictable methods exhibit nearly identical aggregate errors, with negligible paired mean squared error difference, though their pathwise trajectories and Wald statistics differ. The sphere experiment shows the coverage gain from direction based covariance correction alongside the larger RMSE caused by solver randomization.

The timings on the two dimensional torus illustrate the expected scaling trade off: when the dimension is small (d=2d=2) and the Hessian is diagonal, exact inversion is computationally trivial, so randomized sketching introduces per-iteration sampling overhead without its asymptotic dimensional benefits (O(md2)O(md^2) vs. O(d3)O(d^3)).

The observation budget advantage is governed by curvature conditioning: its gains are most pronounced in ill conditioned regimes (κ=300\kappa=300), where second order preconditioning eliminates RSGD's severe transient slowdown. The timing comparison concerns a low dimensional problem with inexpensive exact solves. Randomized sketching targets high dimensional problems where solving the Newton system is costly; an equal computation comparison in that regime remains to be evaluated.

Continued in Part 2/3 with Q1–Q2. Q3–Q4 and references follow in Part 3/3.

Part 2/3 of our response to Reviewer k6mc, continued from Part 1/3. We address Q1–Q2 below.

Q1. The main CLT result is local in nature; its assumptions require confinement to a sufficiently small common chart. Proposition B.20 gives sufficient conditions for a fixed budget rank one sketch: a common positive spectral band controls the sketch operator and its perturbation, an independent spanning sketch law yields positive stable mean drift, and a predictable Hessian rate ∣Bk−H∣L2(op)=O(k−δ)\\|\mathrm{B}_k-\mathrm{H}\\|_{L^2(\mathrm{op})}=O(k^{-\delta}) with δ>(1−α)/2\delta > (1-\alpha)/2 ensures that the accumulated mean drift error is negligible.

The state rate and covariance requirements depend on localization and model specific score moments. Example B.28 illustrates the basin invariance mechanism constructively for a bounded Euclidean quadratic, while for generic nonlinear Riemannian geometries, Assumption B.1 and Proposition B.20 require the following model specific conditions: first identify a common chart and establish invariance for the actual update (or justify a modification with its associated discrepancy), and then verify the drift and moment conditions. In practice, monitoring angular deviations and clipping frequencies provides an effective empirical diagnostic for local confinement.

Algorithm 2 averages the realized solver operators after transport into a fixed anchor frame. The proof of Proposition B.20 establishes consistency through a bounded martingale average and a vanishing Cesàro error in the conditional solver mean. Online covariance estimation requires access to the realized solver operator, in addition to its directional action Pg\mathrm{P}g.

Q2. The primary distinction lies in the inferential target, non-Euclidean geometric accounting, and error propagation. Du, Zhu, Wu and Na (2025) prove an averaged primal–dual sketched-SQP CLT and random scaling inference for nonlinear equality constraints. Du, Rebrova, Dereziński and Na (2026) establish an averaged Euclidean sketched Newton CLT, covariance inflation, and random scaling. Wang, Du and Na (2026) study the last iterate of an accelerated sketched Newton method and estimate its Lyapunov covariance online.

Our framework addresses intrinsic Riemannian optimization: Theorem 3.1 transports the complete recursion into a common tangent space, explicitly accounting for generic C2C^2 retraction errors, frame transport discrepancies, and a signed root-nn bias; Theorem 3.3 establishes the covariance of the implemented directions for the Polyak–Ruppert averaged manifold estimator. Theorem 3.4 gives the covariance decomposition for independent solver randomization in the common tangent frame; Theorem 3.1 controls the retraction and frame discrepancies. Furthermore, our 1/m1/m replication law averages mm independent solver outputs at each step, whereas increasing the number of sequential steps refines each individual solve (e.g., Du et al., 2026, Proposition 4.3). These represent distinct computational interventions within asymptotic inference. The product torus experiment compares RSGD and Exact Newton to isolate conditioning and solver noise. The comparison with the three Euclidean/SQP algorithms is theoretical; direct empirical comparisons remain to be evaluated.

Continued in Part 3/3 with Q3–Q4 and the references.

Part 3/3 of our response to Reviewer k6mc, continued from Part 2/3. We address Q3–Q4 below, followed by the references.

Q3. For a differentiable sample field G^(x,Z)\widehat G(x,Z), a concrete reporting derivative is the average of transported covariant Jacobians Txk→a∇G^(xk,Zk+1)Ta→xk\mathcal T_{x_k\to a}\nabla\widehat G(x_k,Z_{k+1})\mathcal T_{a\to x_k}. Sufficient conditions are uniformly bounded second moments of the centered matrix contributions and a vanishing Cesàro average of their conditional mean errors relative to the target Jacobian. Martingale orthogonality bounds the centered average's squared L2L^2 norm by O(n−1)O(n^{-1}), while the mean error vanishes in L1L^1. This gives the consistency justification directly.

For the current optimization gain, only past contributions are used. If H^=Udiag⁡(σi)V∗\widehat{\mathrm{H}}=U\operatorname{diag}(\sigma_i)V^{\ast}, clipping its singular values into a positive band [h−,h+][h_-,h_+] (h−>0h_- > 0) bounds the inverse operator and preserves consistency whenever the true singular values lie within that band. This yields the safeguarded inverse Vdiag⁡(σ~i−1)U∗V\operatorname{diag}(\widetilde\sigma_i^{-1})U^{\ast}. Singular value control guarantees invertibility. Positive stability of the mean drift and the inverse gain variation bound are additional conditions on the specific estimating field. We give this Jacobian estimator and safeguard for nonsymmetric fields; their empirical performance on non gradient dynamics remains to be evaluated.

Q4. For serially dependent data, Assumption B.2 requires conditional score centering E(ξk+1∣Fk)=0\mathbb{E}(\xi_{k+1}\mid\mathcal F_k)=0, which is stronger than marginal centering. Inference also requires a long-run covariance estimator that includes serial cross-covariances. Applying the predictable gain theorem requires its raw score CLT, inverse gain Abel summation and weighted remainder conditions under that dependence structure.

Residual adaptive stopping rules can make the effective solver depend on the current score. Conditional product centering, E(P~k+1ξk+1∣Fk)=0\mathbb E(\widetilde P_{k+1}\xi_{k+1}\mid\mathcal F_k)=0, is a sufficient route to eliminating this product bias component. The joint solver score law determines this product mean.

More generally, Theorem 3.1 requires the total signed accumulated bias to satisfy n−1/2∑k<nβk+1→pbn^{-1/2}\sum_{k < n}\beta_{k+1}\xrightarrow{p}b, where βk+1\beta_{k+1} includes the conditional solver score and implementation biases. Centered uncorrected inference uses b=0b=0. Under its remaining assumptions, Theorem 3.3 also allows b≠0b\ne0 when a consistent estimator of the signed accumulated bias is available.

For instance, consider ξ=±1\xi=\pm1 equiprobably, independent of the past, and set P=1+εξ\mathrm{P}=1+\varepsilon\xi with 0<∣ε∣<10 < |\varepsilon| < 1. Then EP=1\mathbb{E}\mathrm{P}=1, Eξ=0\mathbb{E}\xi=0, but E(Pξ)=ε\mathbb{E}(\mathrm{P}\xi)=\varepsilon; a persistent bias of this form directly violates the root-nn accumulated bias condition. Moreover, centered implementation errors with persistent variance must be incorporated into the innovation covariance. Dependent or adaptive procedures therefore require control of product centering, accumulated bias and innovation covariance.

References.

  • X. Du, W. Zhu, W. B. Wu, and S. Na (2025), Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling, arXiv:2505.18327.
  • X. Du, E. Rebrova, M. Dereziński, and S. Na (2026), Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling, arXiv:2609.12421.
  • H. Wang, X. Du, and S. Na (2026), Inference of Online Newton Methods with Nesterov's Accelerated Sketching, ICML 2026.
  • N. Tripuraneni, N. Flammarion, F. Bach, and M. I. Jordan (2018), Averaging Stochastic Gradient Descent on Riemannian Manifolds, COLT 2018.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Thank you again for your careful review and constructive feedback. We hope that our responses and revisions have addressed your concerns and questions. If you find that they resolve your main concerns, we would be grateful if you would reconsider your assessment and score in light of these changes. We would be happy to clarify any outstanding points.

Comments on the paper

1 comment

Thank you for your time and valuable comments. We have clarified the local confinement and signed-bias conditions, the role of implemented-direction covariance, and the distinction between predictable gains and fresh solver randomization. We have supplied the reporting-Jacobian construction, safeguards, and model specializations, and added a curved-sphere comparison with learned curvature and fresh randomized solves. The sphere results show how direction-based studentization improves coverage while retaining the associated estimation cost; the WDBC sensitivity results describe initialization and burn-in effects. These results and explanations are incorporated into the paper and marked in blue. We hope the detailed responses below address your concerns. Thank you again for your valuable feedback; we welcome further questions and discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.