Distributed Estimation, Information Loss and Exponential Families

Qiang Liu, Alexander T. IhlerNeurIPS 2014 · OpenReview

In the era of massive datasets and privacy concerns, moving all data to a centralized server is often impractical. Instead, distributed learning is employed: local models are trained on small chunks of data at different locations and then "fused" together. But how much information is lost in this process, and what is the mathematically optimal way to combine these local models?

In their paper, "Distributed Estimation, Information Loss and Exponential Families," Qiang Liu and Alexander Ihler explore the geometry of probability to answer these questions, revealing that while most practitioners simply average model parameters, a KL-divergence-based combination is theoretically optimal and far more robust.

The Challenge of Distributed Estimation

The standard "divide and conquer" strategy for distributed learning involves two steps:

  1. Local Learning: Each data repository calculates its own Maximum Likelihood Estimate (MLE) based on its local subset.
  2. Model Combination: A central "fusion center" combines these local MLEs into a single global model.

This two-step process is generally less efficient than a "global" MLE trained on all data simultaneously. The authors set out to quantify this information loss, seeking the fundamental statistical limits of this framework and a combination method that minimizes the gap between distributed and centralized learning.

Methods: Linear vs. KL-Averaging

The paper compares two primary methods for combining local models ($\hat{\theta}^k$):

  1. Linear Averaging: Taking the arithmetic mean of the parameters ($\frac{1}{d} \sum \hat{\theta}^k$). While computationally simple, it is highly sensitive to parameterization (e.g., averaging variances versus standard deviations yields different results).
  2. KL-Averaging: Finding a new model that minimizes the Kullback-Leibler (KL) divergence to all local models. This approach averages the distributions themselves rather than just their numerical parameters.

To analyze these methods, the authors utilize Efron’s Statistical Curvature. They conceptualize "Full Exponential Families" (like Gaussian or Poisson distributions) as "flat" spaces where distributed learning is straightforward. Conversely, "Curved Exponential Families" represent more complex models where simple linear averaging "falls off" the curve, introducing significant errors.

Key Insights: The Curvature Penalty

A central finding of the paper is that the information loss in distributed learning is directly proportional to the square of the distribution's statistical curvature.

The gap between combined local MLEs and the global MLE is proportional to the statistical curvature.
  • Zero Curvature: If the model belongs to a "Full Exponential Family," the curvature is zero. In this ideal scenario, distributed learning via KL-averaging is exactly as efficient as centralized learning.
  • Suboptimality of Linear Averaging: Even for relatively simple models, linear averaging can be biased depending on how parameters are defined. It consistently fails to reach the theoretical lower bound of error that KL-averaging can achieve.
  • Robustness to Local Optima: In complex, non-convex models like Gaussian Mixture Models (GMMs), local nodes might converge to different peaks (modes) in the likelihood surface. Linear averaging these disparate parameters often results in a "nonsense" model located in a low-probability region. KL-averaging, however, acts similarly to a "parametric bootstrap," effectively mimicking the global MLE even when local estimates diverge significantly.

Experimental Results

The authors validated their theoretical findings using both synthetic data (a Bivariate Normal on an Ellipse designed to exhibit high curvature) and real-world datasets (MNIST and YearPredictionMSD for GMM training).

Comparison of Global MLE, KL Average, and Linear Average parameter estimates across different sample sizes.
  • Theoretical Optimality: The study proves that KL-averaging achieves the minimum possible asymptotic error rate for any combination of local MLEs.
  • Handling Heterogeneous Data: In MNIST experiments where data was partitioned "label-wise" (e.g., one node only sees '1's, another only '2's), linear averaging failed completely. In contrast, KL-averaging remained stable and performed nearly as well as the global MLE.
  • Faster Bias Reduction: On the synthetic "Ellipse" model, the bias of the KL method decreased at a much faster rate ($1/n^2$) compared to the linear method ($1/n$) as the total sample size $n$ increased.

Limitations and Future Directions

While KL-averaging is theoretically superior and practically more robust, it comes with a computational cost. For many complex models, the KL divergence lacks a simple closed-form solution, necessitating approximations like Monte Carlo sampling.

The authors suggest several avenues for future research:

  • Applying these geometric insights to high-dimensional inference problems.
  • Developing more efficient KL approximations for highly complex models, such as Latent Dirichlet Allocation (LDA) and Deep Neural Networks.
  • Exploring distributed settings where data is partitioned by features (variables) rather than by samples (instances).

Summary updated

Abstract

Distributed learning of probabilistic models from multiple data repositories with minimum communication is increasingly important. We study a simple communication-efficient learning framework that first calculates the local maximum likelihood estimates (MLE) based on the data subsets, and then combines the local MLEs to achieve the best possible approximation to the global MLE, based on the whole dataset jointly. We study the statistical properties of this framework, showing that the loss of efficiency compared to the global setting relates to how much the underlying distribution families deviate from full exponential families, drawing connection to the theory of information loss by Fisher, Rao and Efron. We show that the full-exponential-family-ness" represents the lower bound of the error rate of arbitrary combinations of local MLEs, and is achieved by a KL-divergence-based combination method but not by a more common linear combination method. We also study the empirical properties of the KL and linear combination methods, showing that the KL method significantly outperforms linear combination in practical settings with issues such as model misspecification, non-convexity, and heterogeneous data partitions."
BibTeX
@inproceedings{liu2014distributed,
  author = {Qiang Liu and Alexander T. Ihler},
  title = {{Distributed Estimation, Information Loss and Exponential Families}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=SyNtW_ZdWB},
}
Figure