Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

• Prior inference work used identity-metric sketching, while averaged GASN inference and covariance ordering remained open; Hessian inversion typically costs O(d3) per step.Source: §1 · p. 3
• GASN embeds GAS in online Newton updates; the paper proves almost-sure and L2 convergence and asymptotic normality for the averaged iterate.Source: §1 · p. 3
• Exact Newton yields Ω⋆, matching averaged SGD’s minimax efficiency, while the GASN covariance converges toward Ω⋆ exponentially in sketching steps.Source: §1 · p. 4
• For GAS with µtνt < 1, the averaged GASN covariance approaches Ω⋆ faster than the comparison covariance; when µtνt = 1, it recovers averaged USN efficiency.The paper characterizes these regimes as a computational-statistical trade-off analysis.Source: §1 · p. 4
• Averaging also stabilizes ASN: the averaged ASN covariance is smaller than that of its last iterate.Source: §1 · p. 4
• Random scaling studentizes averaged GASN iterates into a pivotal statistic, enabling online inference without covariance estimation and under weaker moment conditions.The limiting distribution is free of unknown parameters; experiments cover linear and logistic regression.Source: §1 · p. 4

2 Online Newton with Generalized Accelerated Sketch-and-Project

• GASN is presented as a direct extension of online Newton methods using the GAS solver.Source: §2 · pp. 5–6
• At each outer iteration, GASN forms stochastic gradient and Hessian estimates, averages the Hessian, and uses GAS to approximate the Newton direction in an update with a decreasing step size.The solver takes matrix and vector inputs, a projection metric, acceleration parameters, and a sketch-step count; it can be performed in O(d^2) time.Source: §2 · p. 5
• Provable acceleration disappears exactly when µν = 1, although momentum may still be used without improving the convergence rate.Source: §2 · p. 6
• Coordinate sketches yield a strictly smaller accelerated factor, with greater improvement when the minimum diagonal entry of B greatly exceeds its minimum eigenvalue, including ill-conditioned regimes.The method is a direct application of accelerated sketch-and-project to online Newton methods.Source: §2 · p. 6
• Choosing projection metric E = B can make the sketched direction substantially cheaper to compute than using E = I, especially for dense matrices.With E = B, the required matrix corresponds to a sampled entry or small submatrix; E = I requires accessing the full column BS_j.Source: §2 · p. 6
• GASN applies GAS to online Newton methods, extending prior inference analyses to averaged iterates and comparing covariance-based statistical efficiency without extra computation.The authors characterize this as a “free” gain in statistical efficiency.Source: §2 · p. 6

3 Assumptions and Convergence Guarantees

• The objective is twice continuously differentiable, has Hessian eigenvalues bounded between positive constants, and has a Lipschitz-continuous Hessian.Source: §3 · p. 7
• Gradient and Hessian estimates are conditionally unbiased and satisfy stated moment-growth conditions; the paper says these are weaker than conditions used by several covariance-estimation procedures.The comparison includes fourth-moment growth requirements and a bounded-moment condition in prior work.Source: §3 · p. 7
• Sketching must satisfy a lower-bound condition, while the projection metric must remain bounded and positive definite; the canonical choices E_t = I and E_t = B_t meet the metric condition automatically.The lower bound ensures sketch-solver convergence, and boundedness ensures invertibility of Z_t.Source: §3 · p. 7
• Under Assumptions 3.1–3.3 and the theorem’s sketch-step condition, GASN iterates converge almost surely to x⋆.The result also establishes L2 convergence.Source: §3 · p. 7
• The sketch-step condition can be satisfied uniformly, and it ensures that GAS returns an approximate Newton direction that remains close on average to the exact direction.Source: §3 · p. 8

4 Uncertainty Quantification and Online Inference for GASN

• The paper characterizes asymptotic uncertainty for averaged GASN iterates, compares their limiting covariance with USN and the minimax-optimal covariance, and proposes random-scaling inference.Source: §4 · p. 8

4.1 Asymptotic normality of averaged GASN

• Averaged GASN is asymptotically normal under the convergence conditions and projection-metric assumption, for step sizes φ_t = C_φ · (t + 1)^−φ with φ ∈ (0.5, 1).Source: §4.1 · pp. 8–9
• Exact Newton attains minimax-optimal statistical efficiency, whereas GAS reduces computational cost with a mild loss in statistical efficiency.Source: §4.1 · p. 9
• When E_t = I and µ_tν_t = 1, averaged GASN and averaged USN have the same limiting covariance; when µ_tν_t < 1, GASN approaches the optimal covariance strictly faster in sketch-step count.Source: §4.1 · p. 9
• Under the stated conditions, the averaged ASN iterate is more statistically efficient than the last ASN iterate, regardless of the sketching distribution.Source: §4.1 · p. 9

4.2 Online inference via random scaling

• The paper strengthens averaged-iterate asymptotic normality to a functional central limit theorem, which supports a studentized pivotal statistic with a limiting distribution free of unknown parameters.The limiting process uses standard d-dimensional Brownian motion.Source: §4.2 · p. 10
• Random scaling yields an asymptotically valid confidence interval whose test-statistic quantities can be updated online as Newton iterations collect data.Source: §4.2 · p. 10

5.1 Synthetic data experiments

• For linear-model covariance comparisons, ASN and GASN closely track USN’s quantiles and are sometimes smaller, while all sketched methods exceed Exact Newton’s quantiles.The comparison uses QQ plots for coordinate and Gaussian sketches; Exact Newton has the smallest limiting variance.Source: §5.1 · p. 11, Figure 1 · p. 11
• In the synthetic experiments, GASN’s confidence-interval coverage remains close to the nominal 95% level across settings.Table 1 reports empirical coverage rates for the inference procedures under different parameter settings with d = 40.Source: §5.1 · p. 11, Table 1 · p. 12
• Across synthetic settings, averaged iterates have substantially smaller MAEs than last iterates, often by 4× to an order of magnitude.EN, ASN, and GASN have similar MAEs when compared under the same model, covariance, and sketching distribution.Source: §5.1 · p. 12

5.2 Real-data experiment on UCI Covertype dataset

• The Covertype experiment uses binary logistic regression on 495,141 samples and 50 standardized cartographic features.The evaluation pairs EN, ASN, and GASN with coordinate and Gaussian sketches and compares LastBF with AveRS over 200 runs.Source: §5.2 · pp. 12–13
• On Covertype, AveRS achieves coverage at or above 95%, MAE 4× to an order of magnitude smaller, and intervals 2.5–6× shorter than LastBF.For the coordinate sketch, GASN and ASN both have MAE 1.28 and interval length 0.16, while GASN uses the cheaper metric E_t = B_t.Source: §5.2 · p. 13, Table 2 · p. 13
• On Covertype, AveRS retains at least nominal 95% coverage while reducing MAE and interval length relative to LastBF in every setting.The reported reductions are 4× to an order of magnitude in MAE and 2.5–6× in interval length.Source: §5.2 · p. 13

6 Conclusion

• GASN has global almost-sure and L2 convergence, and its averaged iterate is asymptotically normal with a characterized limiting covariance.The conclusion says GASN reduces computation relative to Exact Newton at a statistical-efficiency cost, but incurs no such trade-off relative to unaccelerated sketched Newton.Source: §6 · p. 13
• The paper’s random-scaling procedure uses a pivotal statistic to bypass covariance estimation altogether.The appendix provides an online update for the random scaling matrix V_t.Source: §6 · p. 13, B Online Update of Vt · p. 18

A Quantiles of the Limiting Distribution

• Table 3 gives quantiles for the limiting distribution in (19), adapted from Abadir and Paruolo (1997).These quantiles support the confidence-interval construction described for the pivotal statistic.Source: A Quantiles of the Limiting Distribution · p. 18, Table 3 · p. 18

B Online Update of Vt

• The appendix rewrites V_t so its four terms can be computed recursively and formalizes the online calculation in an algorithm.The update is presented as Algorithm 2.Source: B Online Update of Vt · p. 18

C Preparation Lemmas

• Appendix C lists preparation results including a sequence-decay lemma, Kronecker’s lemma, and the Stolz–Cesàro theorem.The supplied passages identify these auxiliary results but do not state all their conditions or applications.Source: C Preparation Lemmas · pp. 18–19

D Proofs in Section 3

• The Section 3 proof develops conditional-expectation matrices from the sketch updates, including C_t and K_t.The proof passage defines these quantities through conditional expectations of their corresponding tilde matrices.Source: D Proofs in Section 3 · p. 19

D.1 Proof of Lemma 3.4

• In the proof of Lemma 3.4, conditional expectation and Assumption 3.3 are used to obtain the concluding inequality.The passage then states that the lemma’s proof is complete.Source: §D.1 · p. 20

D.2 Proof of Theorem 3.5

• Lemma D.1 identifies the conditional expectation of z_t,τ as −(I − K_t)B_t^-1∇f_t and states that its deviation from (I − K_t)Δx_t is a martingale difference.The lemma is stated under Assumptions 3.1–3.3.Source: §D.2 · p. 20
• Under the stated assumptions, the proof first obtains a finite almost-sure limit for f_t − f⋆ and summability of φ_t∥∇f_t∥².It then uses these facts to establish convergence to the minimizer.Source: §D.2 · p. 22
• The proof concludes that x_t converges almost surely to x⋆ after establishing that f_t − f⋆ converges to zero almost surely.The argument uses the divergent sum of φ_t and the preceding bound on the weighted squared gradient norms.Source: §D.2 · p. 22

E Proofs in Section 4

• B_t converges almost surely to B⋆ = ∇²f⋆ under Theorem 3.5’s conditions, without requiring Assumption 4.1.The passage also states that the convergence rate does not require Assumption 4.1.Source: E Proofs in Section 4 · p. 22
• Under Theorem 3.5’s conditions and Assumption 4.1, ∥K_t − K⋆∥ is bounded by a constant-order sum of ∥B_t − B⋆∥ and ∥E_t − E⋆∥, and K_t converges almost surely to K⋆.Source: E Proofs in Section 4 · p. 23

E.1 Proof of Theorem 4.2

• The proof verifies a martingale-difference decomposition, convergence of conditional covariance, a Lindeberg condition, and vanishing error terms for Theorem 4.2.These steps yield the theorem’s central limit result.Source: §E.1 · pp. 23–25

E.2 Proof of Proposition 4.3

• The GAS linear-system argument applies a contraction result to the transformed system, with arbitrary deterministic initial co-state values permitted.The transformed system is nonsingular under the stated positive-definiteness conditions.Source: §E.2 · p. 27

E.3 Proof of Proposition 4.4

• The proof identifies a special acceleration setting in which the limiting covariance reduces to that of the averaged unaccelerated sketched Newton method.When the system is solved exactly, the proof sets the error matrices to zero and uses the covariance identity.Source: §E.2 · p. 26, §E.3 · p. 29

E.4 Proof of Proposition 4.5

• Under the stated parameter conditions, the Lyapunov equation simplifies and the Lyapunov theorem yields the limiting covariance.The proof notes that K⋆ is symmetric when E_t = I.Source: §E.4 · p. 30

E.5 Proof of Theorem 4.6

• The proof verifies convergence of the martingale conditional covariance and the Lindeberg condition, then applies a martingale functional central limit theorem.This establishes the partial-sum process limit used in Theorem 4.6.Source: §E.5 · pp. 30–31

E.6 Proof of Theorem 4.7

• The rescaled process converges to standard one-dimensional Brownian motion, supporting the path-based limit used in Theorem 4.7.The proof applies a continuous functional to the process to obtain the random-scaling limit.Source: §E.6 · p. 35

F.1 Proof of Lemma D.1

• The GAS recursion yields a closed form for the sketched solver and the conditional expectation identities used in the algorithm’s analysis.The proof also uses the independence of the sketches and sample noise.Source: §F.1 · p. 37

F.2 Proof of Lemma E.1

• The Hessian estimate B_t converges almost surely to B⋆, with mean-squared error bounded at order φ_t.The limit is the Hessian at the solution, B⋆ = ∇²f⋆.Source: §F.2 · pp. 38, 40

F.3 Proof of Lemma E.2

• The projection and acceleration quantities converge: the projection matrices are controlled under the metric bounds, and (α_t, β_t, γ_t) converge almost surely to their limits.The parameter deviation is bounded in terms of the expected projection discrepancy.Source: §F.3 · p. 40

F.4 Proof of Lemma E.3

• The iterate error is decomposed into a stable linear recursion, an approximation-error term, and a martingale-difference term.The decomposition separates solver and gradient noise from the remaining error.Source: §F.4 · p. 42

F.5 Proof of Lemma E.4

• The conditional covariance of the martingale increment converges to the sketched-noise covariance expression used in the limiting analysis.The increment combines gradient noise with inner-solver error.Source: §F.5 · pp. 42–44

F.6 Proof of Lemma E.5

• The lemma’s proof uses Jensen’s inequality, Assumption 3.1’s ΥH-Lipschitz continuity of ∇f(x), and Assumption 3.2’s moment bound (12a), and concludes a.s. convergence to x⋆ as i → ∞.Source: §F.6 · p. 45

F.9 Proof of Lemma F.3

• The conditional covariance contribution from the sketched solver converges to its limiting expression as t tends to infinity.The proof combines bounds on the projection and acceleration quantities with convergence of the covariance matrices.Source: §F.9 · p. 49

G Additional Experimental Details

• Section G provides experimental setup and additional results supplementing the experiments reported in Section 5.1.Source: G Additional Experimental Details · p. 49

G.1 Detailed experimental setup

• The experiments vary d over {20, 40} and use identity, Toeplitz, and equi-correlation covariate designs for linear and logistic regression.The Toeplitz and equi-correlation designs use r = 0.4.Source: §G.1 · p. 49
• Using Gaussian sketches with S ∼ N(0, I), the study runs each inference method for 10^5 iterations at 95% nominal coverage and reports coverage rates and interval lengths averaged over 200 independent runs per configuration.Inference targets the coordinate-wise average of the model parameter.Source: §G.1 · p. 49
• Figure 2 compares expected averaged-iterate error E∥x̄_t−x⋆∥ with expected last-iterate error E∥x_t−x⋆∥ for linear and logistic regression under three stochastic Newton methods; both sketched methods use τ = 5 sketching steps.Source: Figure 2 · p. 50

G.2 Additional results and discussions

• The averaged iterate achieves t-consistency, while the last iterate attains only O(t^1/4)-consistency; averaged-iterate curves are also smoother.The smoother curves suggest lower variability and greater statistical efficiency for averaging.Source: §G.2 · p. 50
• AveRS yields substantially smaller mean absolute errors and shorter confidence intervals than LastBF, while maintaining comparable empirical coverage across the reported settings.Table 4 covers dimensions d = 20 and d = 40 and sketching steps τ ∈ {5, 10}.Source: §G.2 · pp. 50–51, Table 4 · p. 52
• Increasing sketching steps from τ = 5 to τ = 10 generally reduces mean absolute error and shortens confidence intervals for sketched Newton methods.The passage attributes this trend to more accurate Newton-direction approximation and a limiting covariance closer to the minimax-optimal covariance.Source: §G.2 · p. 51
• In logistic regression, sketched Newton methods have larger limiting variances than Exact Newton, while USN, ASN, and GASN show closely aligned covariance patterns.Figure 3 reports a representative configuration with d = 20, equi-correlation r = 0.4, and τ = 5 for the sketched methods.Source: §G.2 · p. 51, Figure 3 · p. 51