Minimum HGR correlation principle: From marginals to joint distribution

Farzan Farnia, Meisam Razaviyayn, Sreeram Kannan, David Tse

Abstract

Constructing a joint distribution from low-order information, such as marginals or moments, is a fundamental challenge in statistical modeling. While the Maximum Entropy Principle is the traditional approach, its computational complexity often limits its application in high-dimensional settings. This paper introduces the Minimum Hirschfeld-Gebelein-Rényi (HGR) Correlation Principle as a computationally efficient alternative. We demonstrate that in continuous settings with fixed first and second-order moments, the jointly Gaussian distribution is the unique minimizer of HGR correlation. In discrete settings, we show that the principle leads to additive models and that the optimization problem can be reduced to a convex least-squares regression. Our findings provide a new information-theoretic justification for the ubiquity of Gaussian and additive models.

Introduction

In machine learning and statistics, we frequently encounter scenarios where the full joint distribution $P(X, Y)$ is unknown. Instead, we are often limited to "low-order" snapshots of the data, such as the means and variances of individual features or pairwise marginals between features and a target. The problem of "filling in the gaps" to create a complete model is typically addressed via the Maximum Entropy Principle, which selects the distribution that is most random while remaining consistent with the observed constraints.

However, maximizing entropy or minimizing mutual information is often computationally intractable for high-dimensional problems. This paper explores an alternative metric of dependence: the Hirschfeld-Gebelein-Rényi (HGR) maximal correlation. By seeking a distribution that satisfies known marginals while minimizing HGR correlation, we propose a framework that is both theoretically grounded and computationally feasible.

The Minimum HGR Correlation Principle

The HGR correlation is a powerful metric capable of capturing non-linear dependencies between random variables. The core objective of this research is to identify distributions that assume the "least possible" dependence—as measured by HGR—given a set of observed low-order statistics.

Continuous Setting: The Optimality of Gaussianity

A significant contribution of this work is the characterization of the continuous setting. When the first and second-order moments (means and covariances) are fixed, the authors analytically prove that the jointly Gaussian distribution is the unique minimizer of the HGR correlation.

Theorem 1 formally establishes this result. While Gaussian models are often used for their mathematical convenience, this principle provides a deeper information-theoretic justification: the Gaussian model is the one that assumes the absolute minimum non-linear dependence between variables when only means and variances are known.

Discrete Setting: Additive Structures

In discrete scenarios, particularly those involving a binary target $Y$ and a vector of features $X$, the paper focuses on fixing the pairwise marginals between each feature $X_i$ and $Y$. The authors derive a lower bound for the HGR correlation and demonstrate that calculating this bound is equivalent to solving a convex optimization problem—specifically, a least-squares regression.

Crucially, the research identifies a specific "additive structure" where the conditional expectation takes the form: $$E[Y|X] = \sum f_i(X_i)$$

The authors prove that the minimum HGR correlation is achieved if and only if the distribution follows this additive decomposition. This bridges the gap between information theory and Generalized Additive Models (GAMs), suggesting that additive models are the natural consequence of minimizing HGR correlation.

Computational Feasibility and Genericity

Unlike Mutual Information, which is notoriously difficult to optimize, the Minimum HGR approach results in a simple least-squares problem. This suggests that the principle can scale to much larger datasets than traditional maximum entropy methods.

Furthermore, the authors address the prevalence of these structures. Through Theorem 5, they demonstrate that "additive structured" distributions are not merely mathematical curiosities; they occupy a significant portion of the probability space (a positive Lebesgue measure), indicating that this principle is widely applicable to real-world data distributions.

Discussion and Limitations

While the Minimum HGR Correlation Principle offers a robust framework for model construction, several areas remain for future exploration:

  1. Binary Constraints: Much of the current discrete analysis is restricted to binary targets. Extending these proofs to multi-class classification or general discrete variables is a necessary next step.
  2. Tightness Gaps: In certain cases, such as those involving parity-check style dependencies, the lower bound for HGR correlation is not tight because the underlying distribution lacks an additive structure.
  3. Empirical Validation: While the theoretical and computational advantages are clear, large-scale implementation on high-dimensional real-world data is required to compare its predictive performance against standard deep learning or maximum entropy models.

Conclusion

The Minimum HGR Correlation Principle provides a novel lens through which to view distribution fitting. By proving that Gaussian and additive models are the optimal "minimum dependence" solutions under specific constraints, this work offers both a theoretical foundation for common modeling choices and a computationally efficient path forward for high-dimensional statistical inference.

Summary updated

BibTeX
@inproceedings{farnia2015minimum,
  author = {Farzan Farnia and Meisam Razaviyayn and Sreeram Kannan and David Tse},
  title = {{Minimum HGR correlation principle: From marginals to joint distribution}},
  booktitle = {ISIT},
  year = {2015},
  doi = {10.1109/isit.2015.7282681},
}
Figure