Inference of Online Newton Methods with Nesterov's Accelerated Sketching

Reliable decision-making with streaming data requires principled uncertainty quantification of online methods. While first-order methods enable efficient iterate updates, their inference procedures still require updating proper (covariance) matrices, incurring $O(d^2)$ time and memory complexity, and are sensitive to ill-conditioning and noise heterogeneity of the problem. This costly inference task offers an opportunity for more robust second-order methods, which are, however, bottlenecked by solving Newton systems with $O(d^3)$ complexity. In this paper, we address this gap by studying an online Newton method with Hessian averaging, where the Newton direction at each step is approximately computed using a *sketch-and-project solver with Nesterov's acceleration*, matching $O(d^2)$ complexity of first-order methods. For the proposed method, we quantify its uncertainty arising from both random data and randomized computation. Under standard smoothness and moment conditions, we establish global almost-sure convergence, prove asymptotic normality of the last iterate with a limiting covariance characterized by a Lyapunov equation, and develop a fully online covariance estimator with non-asymptotic convergence guarantees. We also connect the resulting uncertainty quantification to that of exact and sketched Newton methods without Nesterov's acceleration. Extensive experiments on regression models demonstrate the superiority of the proposed method for online inference.

Many machine-learning systems update their models as new data arrive, such as in recommendation systems, medicine, or finance. In these settings, a single best estimate is often not enough. Users also need to know how uncertain that estimate is. Many online methods are computationally inexpensive, but their uncertainty estimates can be unreliable when the problem is numerically unstable or when the data noise varies across directions. More advanced methods, called online Newton methods, use curvature information, but solving the required linear systems can be too expensive. This paper makes online Newton methods more practical by replacing each expensive Newton solve with a smaller randomized approximation and accelerating that approximation. The authors show how the method behaves over time and how its uncertainty is affected by two sources of randomness: the incoming data and the randomized computation. They also provide an online way to estimate this uncertainty, allowing confidence intervals to be constructed without storing all past data or repeatedly solving large systems. Experiments on linear and logistic regression show that the method produces confidence intervals close to the intended coverage level while using only a small number of randomized approximation steps.