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

AI summary

Overview

Research area: Statistical machine learning / estimation theory, specifically sketching algorithms, maximum likelihood estimation (MLE), control variates (CVE), and exponential families.

Technical level: Advanced. The paper's core arguments rely on exponential family parameterizations, Fisher information, score functions, and asymptotic variance calculations. The introductory framing is accessible, and the authors include an appendix example on the zero-mean bivariate Normal specifically to give intuition to readers who find exponential families unfamiliar.

Scope in one sentence: The paper proves that, under stated conditions, the variance reduction achieved by an optimal control variate estimator equals that of the maximum likelihood estimator, and uses this equivalence to build a fixed point algorithm (CV-FP) for finding the MLE.

What This Paper Is About

Sketching algorithms estimate quantities such as inner products, angles, matrix traces, and frequencies by generating random variables from a chosen distribution rather than computing the quantity exactly, then applying either a maximum likelihood estimator or a control variate estimator that exploits parameters already known to the user. The paper's goal is to show that these two apparently different approaches — MLE and CVE — achieve identical asymptotic variance reduction under conditions on exponential family distributions, and to turn that equivalence into a practical iterative algorithm. In doing so it also explains why CVE implementations have produced inconsistent, hard-to-reproduce experimental results, and how CV weights can be used to recover the MLE.

Key Contributions

1. An equivalence theorem between MLE and CVE. The authors formally state conditions under which the asymptotic variance reduction of the MLE in estimating a set of parameters equals the variance reduction given by a CVE that uses the remaining (known) components as control variates. This is Theorem 1 (informal) and Theorem 4 (formal). The authors state that no formal proof of CVE being equivalent to MLE existed to their knowledge, and that the closest hints came from information geometry (Amari 1987; Amari and Nagaoka 2000), which mentions the equivalence condition but does not mention CVE.

2. A fixed point algorithm (CV-FP) for the MLE, plus reproducibility. Given the equivalence, the paper shows that the CVE can be written as a system of fixed point equations equivalent to the likelihood stationary equations (Theorem 6). Under uniqueness and local convergence conditions in Corollary 2 and Theorem 7, Algorithm 1 (CV-FP) converges to the MLE from sufficiently close initial values. The authors report that CV-FP is empirically faster and numerically stable relative to several root-finding methods for the MLE, and that this resolves the reproducibility issue of CVE.

3. Using known CV weights to find the MLE. The paper describes two heuristics in Section 6 and Appendix D for efficiently finding the MLE via CVE weights, giving expressions for MLEs that are tedious to compute, such as Hutchinson's Trace Estimator.

4. Experimental comparison on feature hashing and random projection. The paper runs simulations comparing CV-FP against a baseline sketch estimate, MLE via Newton Raphson, MLE via the Secant method, a control variate using the baseline estimate in the CV correction (CV-Init), and a control variate using empirical covariance and variance (CV-Emp).

An important caveat on scope: the results are proven under specific conditions on regular and minimal exponential families with a twice-continuously-differentiable scaling function and a positive-definite Hessian at the parameter value considered; the authors state they expect the findings to hold across distributions satisfying these conditions.

Main Findings

• Optimal CVE matches MLE variance. Theorem 4 states that the asymptotic variance reduction given by the MLE of a linear combination of the parameters to be estimated (denoted ν_E = {ν_i}, i = 1 to t) equals the variance reduction given by a CVE where components of the sufficient statistic vector y are used as control variates, provided every μ_i ≡ ∂ψ(η)/∂η_i = E(y_i) equals ν_i. The proof works by computing the Fisher Information with respect to ν_E, which involves the matrix [∂η_i/∂μ_j], computing the CVE variance, which involves [∂μ_i/∂η_j], and then linking the two matrices via Lemma 1.

• The result extends to linear transformations. Corollary 1 states Theorem 4 also holds when μ = Aν.

• Duality between MLE and CVE. The authors describe a duality: the MLE maximizes t terms in ∂η/∂μ using knowledge of the likelihood function, while the CVE minimizes (p − t) terms in ∂μ/∂η by computing relevant second moments. If fewer parameters are known (p − t small), CVE is desirable; otherwise MLE is desirable.

• CV weights depending on unknown terms invalidate theoretical CVE variance. Because the optimal CV corrections ĉ_i typically depend on covariances involving the very terms y_i that are being estimated, substituting estimates in place of y_i invalidates the theoretical variance calculation of the CVE. Algorithm 1 implies that the theoretical variance at convergence is the MLE theoretical variance.

• Experimental ranking on feature hashing. Across 10,000 iterations, the MSE of all five methods (baseline, MLE-NR, MLE-Secant, CV-Init, CV-Emp, CV-FP) was lower than the baseline feature hashing estimate. CV-FP and MLE-Secant showed similar best performance. Among control variate implementations, CV-Init was worst, followed by CV-Emp, with CV-FP best. At smaller values of k, MLE-NR had the worst performance; after a threshold of approximately k ≈ 70, its performance converged to that of MLE-Secant and CV-FP.

• Convergence speed. Boxplots of update steps until convergence at sketch sizes k = {20, 40, 60, 80, 100} indicate CV-FP generally takes fewer steps than MLE-NR and MLE-Secant.

• Newton Raphson's apparent failure is an outlier artifact. The authors report that the poor performance of MLE-NR at small k is mostly due to a higher number of outliers, since its interquartile range is comparable to other methods. They note this matters for reproducibility: using the median would ignore outliers and make MLE-NR look good, while using error bars based on standard deviations of estimates can be misleading because MLE-NR shows more outliers in one direction.

• Numerical MSE values. The paper does not report specific numeric MSE values in the provided content; it presents MSE plots and boxplots.

Methodology in Plain English

The authors set up a general framework in which data comes from an exponential family, written in terms of canonical parameters η, sufficient statistics y, and a scaling factor ψ. Some parameters (called ν_E) are unknown and must be estimated; the rest (called ν_K) are known.

To compare MLE and CVE, they compute the asymptotic variance of the MLE in two ways and show the answers coincide. The MLE's variance comes from the inverse Fisher information, involving derivatives of η with respect to the mean parameters μ. The CVE's variance comes from the optimal control-variate coefficients, involving derivatives of μ with respect to η. A lemma in the appendix relates these two matrices, completing the proof. The authors deliberately use exponential family results rather than information geometry so that more practitioners can follow the argument.

Recognizing that the likelihood score equations can be rewritten in the same form as the optimal CV coefficients, they obtain a fixed point equation for each parameter to be estimated, and package it as Algorithm 1 (CV-FP), a Gauss-Seidel-style sweep that updates each estimate in turn until successive updates differ by at most ε.

For experiments, they use feature hashing sketches of randomly generated vector pairs in R^10,000, with norms related by ratios r in {0.1, 0.5, 1, 2, 10} where ‖x_1‖² = r‖x_2‖², and angles θ in {π/12, π/4, π/2, 3π/4, 11π/12}. Sketch sizes k range from 1 to 100, and every experiment is repeated for 10,000 iterations. They compare the baseline sketch estimate, MLE via Newton Raphson, MLE via the Secant method, a CV using the baseline estimate in the correction (CV-Init), a CV using empirical covariance and variance (CV-Emp), and CV-FP. The experiments ran on a machine with an Intel Core i7-8750H CPU at 2.21 GHz × 6, 16 GB memory, Windows 10; each specific ratio-and-angle vector-pair run took approximately 2 hours, with generated data up to 150 MB.

Why This Matters

Impact on research. The paper gives a formal proof of an equivalence that the authors say was only hinted at in the information geometry literature and absent from reference books on exponential families (McLachlan and Krishnan 2007; Efron 2022) and from Glynn and Szechtman (2002), which examined an equivalence of CVE to non-parametric MLE. It also supplies an explanation for why CVE implementations report mixed results: different choices of root-finding method or CV weight construction produce different numerical error and convergence speed, and reporting choices such as medians versus error bars can flip the apparent conclusion. This has direct implications for how sketching experiments are designed and reported.

Real-world applications (all cited in the paper as sketching contexts):

• Feature hashing and similarity search, including duplicate detection, where inner products between high-dimensional vectors are estimated from compressed sketches.
• Estimating angles between vectors and random projection based inner-product estimation, used for tasks such as identifying highly similar vectors.
• Estimating spectral densities of large matrices.
• Matrix trace estimation via Hutchinson's estimator, and frequency estimation from large-scale data streams, plus sampling from sparse data.

Industry relevance. Sketching is a practical compression technique for large-scale data, and its value depends on squeezing lower error out of very few observations. The CV-FP algorithm offers a route to the theoretically correct estimator variance at a given sketch size k, fewer update steps in the reported experiments, and numerical stability — properties that matter when deploying similar-vector search or streaming frequency estimation at scale. The reproducibility discussion is also relevant to benchmarking claims made about sketch-based systems.

Future Directions

The following are open questions the work raises; the paper's conclusion section content was not included in the available excerpt, so these are inferred from the results and limitations rather than stated as the authors' own future work list.

• Validity beyond the proven conditions. The theorem requires a regular and minimal exponential family, a twice continuously differentiable ψ, and V = ∇²ψ(η) ≻ 0 at the parameter value considered. How CV-FP behaves when these conditions fail is not reported.
• Empirical coverage of other exponential families. The paper names the Normal distribution (feature hashing, inner products), the multinomial distribution (frequency estimation, angle estimation), and the χ² distribution (matrix trace estimation) as relevant families, and the abstract's speed and stability claim concerns the bivariate Normal distribution. Experiments for the multinomial and χ² cases, and for random projection, are deferred to appendices and are not reported in the available excerpt.
• Convergence guarantees. Corollary 2 and Theorem 7 give uniqueness and local convergence conditions, and Algorithm 1 converges from sufficiently close initial values. Whether global convergence can be guaranteed, or how sensitive the method is to initialization, is not established in the available content.
• The two heuristics for extracting the MLE from CV weights. The paper states these are given in Section 6 and Appendix D but the details are not in the available excerpt; how broadly they apply, and how they perform relative to direct optimization, remains to be evaluated.

Target Audience

This paper is most valuable to researchers and graduate students working on sketching algorithms, randomized numerical linear algebra, and streaming/compressed data estimation, as well as statisticians interested in exponential families and variance reduction. Practitioners who implement MLE or control variate based estimators in machine learning pipelines — particularly for similarity search, feature hashing, and trace estimation — will benefit from the practical guidance on how implementation choices affect reproducibility and reported error. Readers without a background in exponential family parameterization, Fisher information, or asymptotic variance will need the appendix's bivariate Normal example and some statistical maturity to follow the main proof.

Authors’ 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.