We consider the classical problem of learning, with arbitrary accuracy, the natural parameters of a $k$-parameter truncated \textit{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 novel loss function and a computationally efficient estimator that is consistent as well as asymptotically normal under mild conditions. 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. Further, we show that our estimator can be interpreted as a solution to minimizing a particular Bregman score as well as an instance of minimizing the \textit{surrogate} likelihood. We also provide finite sample guarantees to achieve an error (in $\ell_2$-norm) of $\alpha$ in the parameter estimation with sample complexity $O({\sf poly}(k)/\alpha^2)$. Our method achives the order-optimal sample complexity of $O({\sf log}(k)/\alpha^2)$ when tailored for node-wise-sparse Markov random fields. Finally, we demonstrate the performance of our estimator via numerical experiments.

在本文中，我们提出了一种新的损失函数和一种计算高效的估计器，它在温和条件下是一致且渐近正态的。我们将我们的方法视为同一类指数族的重新参数化分布的最大似然估计，并证明我们的估计器可以解释为最小化特定的Bregman得分以及最小化代理似然的实例。同时，我们还提供了有限样本保证，以在参数估计中实现误差（在ℓ₂范数中）为α，样本复杂度为O(poly(k)/α²)。当定制为节点稀疏马尔可夫随机场时，我们的方法实现了O(log(k)/α²)的优化样本复杂度。最后，我们通过数值实验展示了我们估计器的性能。

关于计算高效学习指数族分布的研究