Online Covariance Matrix Estimation in Sketched Newton Methods

This paper proposes a fully online, batch-free covariance matrix estimator constructed solely from Newton iterates for sketched Newton methods, enabling consistent online statistical inference for model parameters in streaming data scenarios without requiring matrix factorization.

The Gist

Imagine you are trying to find the perfect spot to set up a campfire in a vast, foggy forest. You can't see the whole forest at once; you only get to feel the ground and smell the air at your current location. Your goal is to find the absolute best spot (the "true parameter") where the fire burns hottest and safest.

This is the problem of Stochastic Optimization that this paper tackles. In the real world, this is like a doctor trying to find the perfect drug dosage for a patient based on streaming data, or a stock trader trying to find the best portfolio based on a constant flow of market news.

Here is the breakdown of the paper's solution, explained through a camping analogy.

1. The Problem: The Foggy Forest and the Slow Hiker

Most people use a method called Stochastic Gradient Descent (SGD). Imagine this as a hiker who takes small, cautious steps. Every time they take a step, they look at the ground, feel a slight slope, and move a tiny bit downhill.

• The Good: It's fast and doesn't need a map of the whole forest.
• The Bad: It's sensitive to the terrain. If the ground is bumpy or tilted (ill-conditioned), the hiker might zigzag wildly, taking forever to find the bottom.
• The Missing Piece: Once the hiker finds a spot, they need to know: "How sure are we that this is the best spot?" To answer this, they need to calculate a "Confidence Interval" (a circle around the spot saying, "The real best spot is probably inside here"). To draw this circle accurately, you need to know the Covariance Matrix (a fancy way of describing how the ground slopes and twists in all directions).

2. The Old Way: The Heavy Backpack (Second-Order Methods)

There is a smarter way to walk called Newton's Method. Instead of just feeling the slope, this hiker carries a heavy backpack with a full topographic map (the Hessian matrix). They can see the curvature of the land and take giant, perfect leaps straight to the bottom.

• The Problem: Carrying that map is heavy. In the digital world, calculating that map for huge datasets takes so much computer power that it's often impossible.
• The "Sketching" Fix: A previous study introduced Sketched Newton. Imagine the hiker doesn't carry the whole map, but instead takes a few quick, blurry snapshots (sketches) of the terrain to get a good enough idea of the curve. This makes the leaps fast and light.
• The New Problem: We know how to make the leaps fast, but we still don't know how to draw the Confidence Circle accurately. The old way to draw the circle required recalculating the heavy map (inverting a matrix), which defeats the purpose of being fast.

3. The Paper's Solution: The "Batch-Free" Compass

This paper introduces a new, clever way to draw that confidence circle without ever needing to carry the heavy map or stop to organize the data into groups.

The Analogy: The "Weighted Step" vs. The "Group Photo"

• The Old Way (Batch-Means): Imagine the hiker stops every 100 steps, takes a group photo of everyone in that group, and uses those photos to guess the terrain. This is slow because you have to wait to take the photo, and you have to decide how big the group should be.
• The New Way (Batch-Free): The authors propose a method where every single step counts immediately.
  • They realize that the hiker's steps get smaller and more precise as they get closer to the goal.
  • They assign a "weight" to every step based on how fast the hiker was moving at that moment.
  • They combine all these weighted steps on the fly to build the confidence circle.

Why is this cool?

1. No Heavy Backpack: It doesn't require complex math (matrix inversion) that slows down the computer. It just uses the steps the hiker already took.
2. No Waiting: You don't have to wait to take a "group photo" (batch). You update the confidence circle instantly with every new step.
3. Faster & Smarter: Because Newton's method (the smart hiker) is already better at finding the bottom, this new method proves that the confidence circle converges (settles down) much faster than the old "group photo" methods used for the slow hikers.

4. The Results: A Clearer View in the Fog

The authors tested this on:

• Regression Problems: Like predicting house prices based on streaming data.
• CUTEst Benchmarks: Standard, difficult math puzzles used to test optimization algorithms.

The Verdict:
Their new "Batch-Free" compass works better than the old methods.

• It gives more accurate confidence intervals (the circle is the right size, not too wide, not too narrow).
• It is computationally cheap (it doesn't crash the computer's memory).
• It works even when the data is messy or the "terrain" is tricky.

Summary

In simple terms, this paper solves a specific headache for data scientists: "How do we know how good our fast, approximate answers are, without doing expensive calculations?"

They built a tool that lets you calculate your "certainty" instantly, using only the data you've already processed, making high-speed, high-accuracy decision-making possible for streaming data in the real world. It's like giving a fast hiker a compass that updates itself with every step, so they never have to stop to check a heavy map.

Technical Summary

1. Problem Statement

The paper addresses the challenge of performing online statistical inference for model parameters in stochastic optimization problems, specifically:
$$\min_{x \in \mathbb{R}^d} F(x) = \mathbb{E}_P[f(x; \xi)]$$
where data arrives in a streaming fashion. While Stochastic Gradient Descent (SGD) is computationally efficient ($O(d)$ per iteration), it suffers from sensitivity to stepsize tuning, noise heterogeneity, and ill-conditioning. Newton methods offer superior robustness and convergence by utilizing second-order (Hessian) information, but they are computationally prohibitive ($O(d^3)$) for large-scale problems due to the need to invert the Hessian.

To bridge this gap, Online Sketched Newton Methods have been developed, using randomized sketching to approximate the Newton step with reduced complexity ($O(d^2)$ or better). However, a critical gap remains: while the asymptotic normality of these sketched Newton iterates has been established, there is no consistent, fully online estimator for the limiting covariance matrix ($\Xi_\star$) required to construct valid confidence intervals. Existing estimators either:

1. Plug-in estimators: Require Hessian inversion ($O(d^3)$) and are biased in the sketched setting because they ignore sketching-induced bias.
2. Batch-means estimators: Designed for first-order methods (SGD), require grouping data into batches (introducing tuning parameters), and have slower convergence rates.

2. Methodology

The authors propose a novel Fully Online, Batch-Free Weighted Sample Covariance Estimator ($\hat{\Xi}_t$) constructed entirely from the Newton iterates.

A. The Algorithm (Online Sketched Newton)

The method updates the iterate $x_t$ using a randomized sketching solver:

1. Gradient/Hessian Estimation: Compute $\bar{g}_t = \nabla f(x_t; \xi_t)$ and update the Hessian average $B_t$.
2. Sketching Solver: Instead of solving $B_t \Delta x_t = -\bar{g}_t$ exactly, an approximate solution $\bar{\Delta} x_t$ is found via $\tau$ inner iterations of a sketching projection (e.g., Randomized Kaczmarz or Gaussian sketching).
3. Update: $x_{t+1} = x_t + \bar{\alpha}_t \bar{\Delta} x_t$, where $\bar{\alpha}_t$ is an adaptive stepsize.

B. The Covariance Estimator

The proposed estimator $\hat{\Xi}_t$ is defined as a weighted sample covariance of the iterates:
$$\hat{\Xi}_t = \frac{1}{t} \sum_{i=1}^t \frac{1}{\phi_{i-1}} (x_i - \bar{x}_t)(x_i - \bar{x}_t)^\top$$
where:

• $\bar{x}_t = \frac{1}{t} \sum_{i=1}^t x_i$ is the averaged iterate (used as a proxy for the true parameter $x_\star$ due to its faster convergence rate).
• $\phi_{i-1} = \beta_{i-1} + \chi_{i-1}/2$ is a centered stepsize parameter derived from the algorithm's stepsize sequence.
• Key Feature: The estimator is matrix-free (no Hessian inversion) and recursive, allowing for $O(d^2)$ updates per iteration, matching the memory and computational cost of first-order methods.

3. Key Contributions

1. First Consistent Online Estimator for Second-Order Methods:
   The paper provides the first fully online construction of a consistent estimator for the limiting covariance matrix of sketched Newton methods. Unlike plug-in estimators, it does not require inverting the Hessian, avoiding $O(d^3)$ costs.

2. Batch-Free Design:
   Unlike batch-means estimators used for SGD (which require tuning batch sizes and grouping data), this estimator is batch-free. It utilizes every individual iterate with appropriate weighting, eliminating the need for extra hyperparameters and improving data efficiency.

3. Theoretical Guarantees:

   • Consistency: The authors prove that $\hat{\Xi}_t \to \Xi_\star$ almost surely.
   • Convergence Rate: The estimator achieves a convergence rate of $O(1/\sqrt{t\beta_t})$. This is provably faster than the $O(1/\sqrt[4]{t\beta_t})$ rate of batch-means estimators for SGD.
   • Asymptotic Normality: Coupled with the established asymptotic normality of the sketched Newton iterates, the estimator enables the construction of asymptotically valid confidence intervals and regions.

4. Generalization:
   The framework is extended to constrained stochastic optimization (via Sketched Sequential Quadratic Programming) and conditioned SGD (e.g., AdaGrad, RMSProp), demonstrating broad applicability beyond standard unconstrained Newton methods.

4. Experimental Results

The authors evaluated the estimator on linear/logistic regression and CUTEst benchmark problems.

• Coverage Rates: In regression tasks, the confidence intervals constructed using $\hat{\Xi}_t$ achieved empirical coverage rates close to the nominal 95% level across various dimensions ($d=20$ to $100$) and covariance structures (Identity, Toeplitz, Equi-correlation).
• Comparison with Plug-in: The plug-in estimator (Na and Mahoney, 2025) exhibited significant undercoverage in sketched settings due to bias from ignoring sketching errors. The proposed estimator corrected this bias.
• Comparison with Batch-Means: The proposed estimator converged faster and provided more stable confidence intervals than the batch-means estimator for SGD, which suffered from oscillations due to batch grouping.
• Robustness: The method remained robust under varying noise levels and different sketching configurations (Gaussian vs. Kaczmarz, varying sketching dimensions $q$ and steps $\tau$).
• Constrained Problems: On CUTEst benchmark problems, the estimator maintained high coverage rates, validating its extension to constrained optimization.

5. Significance

This work resolves a fundamental bottleneck in online statistical inference for second-order methods.

• Statistical Efficiency: It leverages the superior convergence properties of Newton methods (better stationarity and robustness to ill-conditioning) while maintaining the computational efficiency of first-order methods ($O(d^2)$).
• Practical Utility: By providing a consistent, matrix-free covariance estimator, it enables practitioners to perform rigorous hypothesis testing and construct confidence regions for model parameters in streaming data environments without the computational overhead of Hessian inversion or the statistical inefficiency of batch grouping.
• Theoretical Advancement: It establishes that the benefits of second-order information extend to the statistical inference phase, offering faster convergence rates for covariance estimation compared to first-order counterparts.

In summary, the paper bridges the gap between high-performance optimization (Sketched Newton) and rigorous statistical inference, offering a computationally efficient and theoretically sound tool for modern streaming data applications.