Abstract: We investigate penalized maximum log-likelihood estimation for exponential family distributions whose natural parameter resides in a reproducing kernel Hilbert space. Key to our approach is a novel "doubly dual embedding" technique that reformulates the problem as a saddle-point optimization, bypassing the intractable partition function and providing an efficient sampler for the learned distribution.
Introduction
Exponential families are fundamental to statistical modeling, but their application in infinite-dimensional Reproducing Kernel Hilbert Spaces (RKHS) presents significant computational challenges. The primary obstacle is the partition function, a normalization constant that requires computing an integral over the entire domain. In high-dimensional or infinite-dimensional spaces, this integral is typically intractable.
Traditional Maximum Likelihood Estimation (MLE) requires evaluating this integral repeatedly. While alternative methods like "score matching" avoid the partition function by focusing on the derivatives of the log-density, they suffer from poor scalability. Score matching typically requires $O(n^3d^3)$ time and $O(n^2d^2)$ memory, where $n$ is the number of samples and $d$ is the feature dimension, making it impractical for large-scale datasets.
The Doubly Dual Embedding (DDE) Approach
This paper introduces a Doubly Dual Embedding strategy to transform the penalized MLE problem into a manageable stochastic optimization task:
- Fenchel Duality of the Log-Partition: By applying Fenchel duality, the log-partition function is rewritten as a maximization over a space of distributions. This converts the MLE objective into a saddle-point (min-max) problem.
- Fenchel Duality of KL Divergence: To handle the inner maximization, the authors apply duality again to the Kullback-Leibler (KL) divergence term. This introduces an auxiliary function and eliminates the need for an explicit density representation of the dual distribution.
- Transport Mapping: Instead of an explicit density, the method utilizes a "transport mapping" (similar to a generator network) to represent the dual distribution. This allows for efficient sampling from the model once trained.
- Stochastic Functional Gradients: The resulting optimization is solved via stochastic gradient descent, reducing complexity to scale linearly with iterations rather than cubically with sample size.
Experimental Evaluation
The DDE method was evaluated against state-of-the-art kernel exponential family (KEF) estimators using synthetic datasets—ring, grid, and two moons—and 16 UCI benchmark datasets for conditional density estimation.
Key Results
- Efficiency: Memory requirements were reduced from $O(n^2d^2)$ to $O(K^2)$ (where $K$ is the number of iterations).
- Accuracy: On the
griddataset, DDE achieved a Maximum Mean Discrepancy (MMD) of 1.32, significantly outperforming KEF's 40.39. - Inference Speed: The amortized inference provided by the transport map allowed DDE to generate samples orders of magnitude faster than KEF paired with Hamiltonian Monte Carlo (e.g., 0.07s vs 14.12s for the
ringdataset). - Conditional Estimation: DDE outperformed or matched competitors on 14 out of 16 UCI benchmark datasets.
Theoretical Insights and Connections
A significant theoretical contribution of this work is the discovery of a link between penalized MLE and Generative Adversarial Networks (GANs). The authors demonstrate that the dual problem of penalized MLE is equivalent to a KL-regularized MMD-GAN. This provides a formal framework for understanding GANs as a form of infinite-dimensional exponential family estimation.
Furthermore, the DDE estimator better captures the smoothness of the underlying distribution. Unlike score matching, where convergence rates often saturate, DDE's convergence rate continues to improve as the target density becomes smoother.
Conclusion and Future Work
Doubly Dual Embedding provides a scalable and flexible framework for kernel exponential family estimation. By bypassing the partition function and simultaneously learning a sampler, it addresses the primary bottlenecks of previous methods. While the introduction of transport mappings makes the optimization non-convex—requiring careful tuning—the gains in efficiency and inference speed represent a significant step forward. Future research may explore dynamic-based sampling to further refine the balance between model flexibility and density tractability.
Summary updated