It's all In the (Exponential) Family: An Equivalence between Maximum Likelihood Estimation and Control Variates for Sketching Algorithms

Keegan Kang; Kerong Wang; Ding Zhang; Rameshwar Pratap; Bhisham Dev Verma; Benedict H. W. Wong

stat.MLJan 29, 2026

It's all In the (Exponential) Family: An Equivalence between Maximum Likelihood Estimation and Control Variates for Sketching Algorithms

Authors: Keegan Kang, Kerong Wang, Ding Zhang, Rameshwar Pratap, Bhisham Dev Verma, Benedict H. W. Wong

Abstract

Maximum likelihood estimators (MLE) and control variate estimators (CVE) have been used in conjunction with known information across sketching algorithms and applications in machine learning. We prove that under certain conditions in an exponential family, an optimal CVE will achieve the same asymptotic variance as the MLE, giving a fixed point algorithm for the MLE. Experiments show the fixed point algorithm is faster and numerically stable compared to other root finding algorithms for the MLE for the bivariate Normal distribution, and we expect this to hold across distributions satisfying these conditions. We show how this algorithm leads to reproducibility for algorithms using MLE / CVE, and demonstrate how the algorithm leads to finding the MLE when the CV weights are known.

Explore similar work

Inference of Online Newton Methods with Nesterov's Accelerated Sketching
Apr 25, 2026Haoxuan Wang, Xinchen Du, Sen NaNewton Learning-Augmented Algorithms
Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
Sep 14, 2026Xinchen Du, Elizaveta Rebrova, Micha\l Dereziński +1Newton Covariance Estimation
Improving TensorSketch Using Complex Random Variables
Aug 11, 2026Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap +1Optimal Sample Complexity Kernel Method

Apr 25, 2026 · stat.MLJ/K move · Enter open · S save

Inference of Online Newton Methods with Nesterov's Accelerated Sketching

Haoxuan Wang, Xinchen Du, Sen Na

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.

Newton Learning-Augmented Algorithms Online Inference Sketches

Open paper Ask about it PDF

Abstract

Explore similar work

Inference of Online Newton Methods with Nesterov's Accelerated Sketching

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

Improving TensorSketch Using Complex Random Variables