Technical Summary: Higher-Order Equilibrium Tracking for EM-Compressible Online Estimation

Problem Formulation

The paper addresses the challenge of online statistical estimation in latent-variable models, specifically aiming to match the efficiency of batch estimators while operating under bounded memory and computational constraints. Unlike standard online stochastic approximation which targets a fixed population parameter, the authors observe that in latent-variable settings (e.g., covariance estimation), the "target" itself is dynamic.

After $t$ observations, the running sufficient statistic $S_t$ defines a frozen empirical objective $L_{S_t}$. The local minimizer of this objective, denoted $\Sigma^\circ(S_t)$, constitutes a frozen empirical equilibrium. As the data stream evolves, $S_t$ drifts, causing the equilibrium $\Sigma^\circ(S_t)$ to trace a slowly moving curve on a manifold. The online estimation problem is thus recast as tracking this moving equilibrium.

The core difficulty lies in separating the statistical fluctuation of the batch estimator from the algorithmic tracking error. Standard analyses often conflate these, failing to isolate the empirical batch optimum from the online tracking lag at finite horizons.

Methodology

The authors propose a framework that decomposes the online estimate $\vartheta_T$ (in local coordinates) into two components:
$$\vartheta_T = r(S_T) + e_T$$
where $r(S_T)$ is the equilibrium branch (the frozen batch target at the final statistic) and $e_T$ is the tracking lag.

1. Equilibrium-Jet Predictor-Corrector

The algorithm (Algorithm 1) employs a two-step mechanism to minimize the tracking lag $e_T$:

• Predictor: An $m$-th order equilibrium-jet predictor approximates the next displacement of the equilibrium branch $r(S)$ using a Taylor expansion (jet) of the response map $r(S)$. This predicts the drift of the target based on the statistic increment $\Delta S_t$.
• Corrector: An order-$\nu$ frozen corrector (implemented as a damped inexact Newton-Conjugate Gradient step) contracts the predicted state toward the new frozen target.

Theoretical analysis shows that combining an $m$-th order predictor with an order-$\nu$ corrector yields a localized tracking rate of $O(T^{-\nu(m+1)})$. For instance, a first-order predictor ($m=1$) with a Newton corrector ($\nu=2$) achieves a rate of $O(T^{-2})$.

2. EM-Compressibility and EM-jetR-Compressibility

A critical structural requirement for this method is that the predictor and corrector must be computable from a retained streaming statistic rather than the full history. The paper formalizes two conditions:

• EM-compressibility: The frozen score function closes on a compressed sufficient statistic $C_t$ via an EM-style identity.
• EM-jetR-compressibility: A stronger condition ensuring that not only the score, but also the statistic-directional derivatives of the score up to order $R+1$ (required for higher-order jets and Hessian-vector products), can be evaluated using only the compressed statistic.

3. Batch-to-Online Transfer Theorem

The paper establishes a transfer theorem: if the tracking lag satisfies $\|e_T\|_{L_2} = o(T^{-1/2})$, the online estimator inherits the batch Central Limit Theorem (CLT) and the sharp first-order risk constant ($T^{-1} \text{tr}(V^*)$). This implies that a sufficiently accurate tracker incurs no asymptotic penalty compared to the ideal batch estimator computed on the same data.

Key Contributions

1. Empirical-Equilibrium Formulation: The authors recast online estimation as tracking a statistic-indexed equilibrium branch, cleanly separating statistical fluctuation from algorithmic lag.
2. Higher-Order Tracking Rates: They demonstrate that an $m$-th order predictor combined with an order-$\nu$ corrector achieves localized tracking rates of $O(T^{-\nu(m+1)})$. Specifically, a first-order scheme achieves $O(T^{-2})$.
3. Structural Conditions (EM-Compressibility): They define EM-compressibility and EM-jetR-compressibility as the necessary structural conditions for evaluating equilibrium responses and Newton correctors from streaming statistics.
4. Transfer Theorem: They prove that any online tracker with a terminal lag of $o(T^{-1/2})$ inherits the batch CLT and the optimal risk constant.
5. Latent Linear Gaussian Instantiation: The theory is instantiated for latent linear Gaussian covariance estimation. Here, the first-order scheme operates on a compressed $d \times d$ statistic (where $d$ is the latent dimension), independent of the observation dimension $p$. The authors provide explicit finite-sample risk envelopes and a certified restart rule to ensure entry into the local tracking regime.

Results and Validation

The paper provides both theoretical guarantees and numerical diagnostics:

• Tracking Order Verification: Experiments on scalar and latent Gaussian models confirm the predicted log-log slopes. A first-order predictor with a Newton corrector yields a slope of $\approx -2.0$, matching the $O(T^{-2})$ theoretical rate. Higher orders ($m=2, \nu=3$) further improve rates as predicted.
• Damping Sensitivity: Results show that fixed damping ($\lambda > 0$) degrades the Newton corrector from order 2 to order 1, reducing the tracking rate from $T^{-2}$ to $T^{-1}$.
• Batch-to-Online Transfer: Numerical experiments verify that $\sqrt{T}\|e_T\|_{L_2} \to 0$, satisfying the transfer condition. Consequently, the online risk $T \cdot E[d_h^2(\Sigma_T, \Sigma^*)]$ converges to the sharp batch constant $\text{tr}(J_*^{-1})$, indistinguishable from the batch estimator's performance.
• Computational Efficiency: In the latent Gaussian case, the online step costs $O(pd + d^2 + (k_{pred} + k_{cor} + 1)d^3)$ with memory $O(pd + d^2)$, avoiding the storage of past samples.

Significance and Claims

The paper claims to provide a local tracking and transfer theory for the certified equilibrium regime. It does not assert global convergence from arbitrary initialization; rather, it relies on a restart rule (e.g., linear inverse initialization) to enter the local neighborhood where the equilibrium branch is smooth and the corrector is contractive.

The significance lies in:

• Theoretical Unification: Bridging the gap between batch asymptotics and online tracking by treating the batch target as a moving object.
• Structural Insight: Identifying that "EM-compressibility" is not just about the score, but about the compressibility of the derivatives (jets) required for higher-order tracking.
• Optimality: Demonstrating that online estimators can achieve the exact same asymptotic risk constants as batch estimators without requiring full data storage, provided the tracking lag is controlled via higher-order prediction and correction.

The authors position this work as foundational mathematical theory for online covariance estimation in latent variable models, offering certified contraction and sharp risk guarantees for streaming data under memory constraints.