A Computationally Efficient Method for Learning Exponential Family Distributions
This addresses a computational bottleneck in statistical estimation for exponential families, offering an incremental improvement over traditional maximum likelihood methods.
The paper tackles the problem of learning natural parameters of exponential family distributions from samples, proposing a computationally efficient estimator that achieves consistent and asymptotically normal estimation with sample and computational complexity polynomial in parameters and error.
We consider the question of learning the natural parameters of a $k$ parameter minimal exponential family from i.i.d. samples in a computationally and statistically efficient manner. We focus on the setting where the support as well as the natural parameters are appropriately bounded. While the traditional maximum likelihood estimator for this class of exponential family is consistent, asymptotically normal, and asymptotically efficient, evaluating it is computationally hard. In this work, we propose a computationally efficient estimator that is consistent as well as asymptotically normal under mild conditions. We provide finite sample guarantees to achieve an ($\ell_2$) error of $α$ in the parameter estimation with sample complexity $O(\mathrm{poly}(k/α))$ and computational complexity ${O}(\mathrm{poly}(k/α))$. To establish these results, we show that, at the population level, our method can be viewed as the maximum likelihood estimation of a re-parameterized distribution belonging to the same class of exponential family.