A Computationally Efficient Method for Learning Exponential Family Distributions
Authors: Abhin Shah
Devavrat Shah
Gregory Wornell
Venue: NeurIPS 2021 Poster (2021)
Keywords: Exponential Family
M-estimation
Maximum Likelihood Estimation
Consistency
Normality
Efficiency

Abstract: We consider the question of learning the natural parameters of a $k$ parameter \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 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 $\alpha$ in the parameter estimation  with sample complexity $O(\mathrm{poly}(k/\alpha))$ and computational complexity ${O}(\mathrm{poly}(k/\alpha))$. 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. 

A Computationally Efficient Method for Learning Exponential Family Distributions
Abhin Shah
Devavrat Shah
Gregory W. Wornell MIT gww@mit. edu
MIT abhin@mit.edu
MIT devavrat@mit.edu
Abstract
We consider the question of learning the natural parameters of k- k-parameter mini- mal 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 consistent as well as asymp- totically normal under mild conditions. We provide finite sample guarantees to achieve an (fz) error of in the parameter estimation with sample complexity (poly (k/a)) and computational complexity O(poly(k/a)). To establish these results, we show that, at the population level, our method can be viewed as the maximum likelihood estimation of re- re-paramcterized distribution belonging to the same class of exponential family.
Introduction
We are interested in the problem of learning the natural parameters of minimal exponential family with bounded support. Consider p-dimensional random vector (xi.-.. Xp) with support X' C IRP. An exponential family is a set of parametric probability distributions with probability densities of the following canonical form
(x 0) exp (0 (xxx) + (x)).
where x E A' is a realization of the underlying random variable x, 0 E R& the natural parameter, Φ X + R is the natural statistic, & denotes the number of parameters, and 5 is the log base function. For representational convenience, we shall utilize the following equivalent representation of
fx(x: Q) exp ((0, exp (Eeetiisetteaeellela Ozg (x)(())
(2)
where θ [0yr] E R x is the natural parameter, 4 [ X Rk x is the natural statistic, x 12 hi
k and ((0, (xx))) denotes the tensor inner product, i.c. the sum of product of entries of θ and ((x). An exponential family is minimal if there does not exist nonzero tensor U E RA x ky such that (UU (xx)) is equal to constant for all x E X.
The notion of exponential family was first introduced by Fisher [17] and was later generalized by Darmois [12]. Koopman [30], and Pitman 40). Exponential families play an important role in statistical inference and arise many diverse applications for a variety of reasons: (a) they are analytically tractable, (b) they arise as the solutions to several natural optimization problems on the
space of probability distributions, (c) they have robust generalization property (see [5] 2 for details).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Truncated (or bounded) exponential family, first introduced by Hogg and Craig 20), is a set of parametric probability distributions resulting from truncating the support of an exponential family. Truncated exponential families share the same parametric form with their non-truncated counterparts up to normalizing constant. These distributions arise in many applications where we can observe only a truncated dataset (truncation is often imposed by during data acquisition) e.g., geolocation tracking data can only be observed up to the coverage mobile signal, police department can often monitor crimes only within their city's boundary.
The natural parameter specifies particular distribution in the exponential family. the natural statistic & and the support of x (i.e., X') are known, then learning distribution in the exponential family equivalent learning the corresponding natural parameter Ô Despite having long history. there has been limited progress on learning natural parameter è of minimal truncated exponential family. More precisely, there is no known method (without any abstract condition) that both computationally and statistically efficient for learning natural parameter of the minimal truncated exponential family considered in this work.
1.1 Contributions
As the primary contribution of this work, we provide a computationally tractable method with statistical guarantees for learning distributions in truncated minimal exponential families. Formally, the learning task of interest is estimating the true natural parameter O' from i.i.d. samples of x obtained from [x(:; O*). We focus on the setting where O" and & are appropriately bounded (see Section 2 We summarize our contributions in the following two categories.
1. Computationally Tractable Estimator:
Consistency, Normality, Finite Sample Guarantees. Given n samples x() ... xx()) of x, we propose the following novel loss function to learn a distribu- tion belonging to the exponential family in 2
22
(0)
Σ = n
exp (- (=((0,((x)))))
where (--) = (--) -eux [.)] with Ux being the uniform distribution over X' We establish that the estimator θ,, obtained by minimizing (9) over all θ in the constraint set A, i...
Ô E arg min C, (9),
(4)
9EA
is consistent and (under mild further restrictions) asymptotically normal (see Theorem
4.2).
We obtain
an c-optimal solution θ.,, of the convex minimization problem in (4) (i.e., ( < L, (ên) + e)
by implementing a projected gradient descent algorithm with (2g k2//) Lemma 3.1.. Finally, we provide rigorous finite sample guarantees for 6... (with e O(a²))
iterations (see
achieve an error of a (in the tensor E2 norm) with respect to the true natural parameter θ* with (pooy(kky kz/a)) samples and (pooly (k₃ kz/aa) computations (see Theorem 4.3). By letting certain additional structure on the natural parameter, we allow our framework to capture various constraints on the natural parameter including sparse, low-rank, sparse-plus-low-.. (see Section 1.II.
2. Connections to maximum likelihood estimation (MLE) of a re-parameterized distribution. We establish connections between method and the MLE of the distribution fx(:: O* O). We show that the estimator that minimizes the population version of the loss function in (3) i.e.,
(())=
E exp (()))))))))
equivalent to the estimator that minimizes the Kullback-Leible (KL) divergence between Ux (the
uniform distribution on X') and f=(:; O θ) (see Theorem 4.1 Therefore, at the population level, our method can be viewed as the MLE of the parametric family [x(5 O O). We show that the KL divergence (and therefore ((O)) minimized if and only if θ O", and this connection provides an intuitively pleasing justification of the estimator in
We let A3 O(1). See Section

---

1.2 Related Works
In this section, we look at the related works on learning exponential family. Broadly speaking, there are two line of approaches to overcome the computational hardness of the MLE : (a) approximating the MLE and (b) selecting a surrogate objective. Given the richness of both of approaches, we cannot do justice in providing a full overview. Instead, we look at few examples from both. Next, we look at some of the related works that focus on learning class of exponential family. More specifically, we look at works on (a) learning the Gaussian distribution and (b) learning exponential family Markov random fields (MRFs). Finally, we explore some works on the powerful technique of score matching. [ we further review works on learning exponential family MRFs, score-based methods
In Appendix (including the related literature on Stein discrepancy) and latent variable graphical models (since these capture paarse-luus-low-ee
constraints the parameters similar to our framework).
Approximating the MLE. Most of the techniques falling in this category approximate the MLE by approximating the log partition function. A few examples include : (a) approximating the gradient of log- legliikllihod with a stochastic estimator by minimizing the contrastive divergence [9]: (b) upper
bounding the log-pan oog-parition function by an iterative tree-reweighted belief propagation algorithm [57]
(c) using Monte Carlo methods like importance sampling for estimating the partition function 43
Since these methods approximate the partition function, they come at the cost of an approximation error or result in a biased estimator.
Selecting surrogate objective. This line of approach selects an easier-to-compute surrogate objective that completely avoids the partition function. A few examples are as follows: (a) sseudo-likelihodd estimators [4] approximate the joint distribution with the product of conditional distributions, each of which only represents the distribution of a single variable conditioned on the remaining variables;
(b) score matching [22) [21] minimizes the Fisher divergence between the true log density and the model log density. Even though score matching does not require evaluating the partition function, is computationally expensive as it requires computing third order derivatives for optimization; (c) kernel Stein discrepancy [32 g measures the kernel mean discrepancy between a data distribution and model density using the Stein's 's identity. This measure is directly characterized by the choice of the kernel and there is no clear objective for choosing the right kernel [61].
Learning the Gaussian distribution. Learning the Gaussian distribution is a special case of learning exponential family distributions. There has been a long history of learning Gaussian distributions in the form of learning Gaussian graphical models e.g. the neighborhood selection scheme [36]. the graphical lasso [18. the CLIME 66. etc. However, finite sample analysis of these methods require various bard-to-verify conditions e.g. the restricted eigenvalue condition, the incoherence
assumption (159 24). bounded eigenvalues of the precision matrix, etc. recent work (28 provided an algorithm whose sample complexity, for specific subclass of Gaussian graphical models, match the information- -hhooretccc lower bound of (60) without the aforementioned hard-to-verify conditions.
Learning Exponential Family Markov Random Fields (MRFs). MRFs can be naturally repre- sented exponential family distributions via the principle of maximum entropy (see (58)) A popular method for learning MRFs is estimating node-neighborhoods (fitting conditional distributions of each node conditioned on the rest of the nodes) because the natural parameter is assumed to be node-wise- sparse. A recent line of work has considered a subclass of node-wise-ste wade--asesperrse pairwise continuous MRFs where the node-conditional distribution of x; X; for every arise from an exponential family as follows:
fxix (0,|x_ x-:) x exp (10, +
Σ (1)((z;))((z)))
(5)
where ((x;)) is the natural statistics and 0: + Ejen) (z)((2)) is the natural parameter Yang al. (62] showed that only the following joint distribution is consistent with the node-conditional distributions in (5)
[x() x exp
Σ Ozb(xz) + [ono(a)d(a;))) KE(P
(6)
To learn the node-conditional distribution in 5 for linear o(-) (i.e., o(x) = x), Yang et al. 162 proposed an l regularized node-conditional likeliodi However, their finite sample analysis
Under oade-wise-sparsity Eyepo.. |0,] is bounded by a constant for every E [p].
3

---

required the following conditions: incoherence, dependency (see [59] 24 bounded moments of the variables, and local smoothness of the log-partition function. Tansey et [1]] extended the approach in [2] to vector-space MRFs (i.e., vector natural parameters and natural statistics) and non-linear (()). They proposed a sparse group lasso (see [45) regularized node-conditional log-likelihood and an afternating direction method of multipliers based approach to solving the resulting optimization problem. However, their analysis required same conditions as [62]
While node-conditional log-likelihode has been a natural choice for learning exponential family and maximum pseudo-likelihood estimator [39 63 have
MRFs, M-estimation [56
55 4
recently gained popularity. The objective function in M-estimation is sample average and the estimator is generally consistent and asymptotically normal. Shah et al. [44] proposed the following M-estimation (inspired from [56] (55)) for vector- space MRFs and non-linear α(-): with Ux, being
the uniform distribution on X; and @(x,) = <(x,) Say (xx))xxx (xt))xz)
1 "
arg min
Σ 72
exp [0,6(z,) JElP
E (1)()))(11)1)
They provided an entropic descent algorithm (borrowing from [55] to solve the optimization in 7 and their finite-sample bounds rely on bounded domain of the variables and a condition (naturally satisfied by linear <(-)) that lower bounds the variance of a non-constant random variable.
Yuan et al. 64 considered broader class of sparse pairwise exponential family MRFs compared to They studied the following joint distribution with natural statistics (6.)) and (b())
62
fx(x) X exp Σ 01b(1:) + Σ (15)
(8)
RE(P]
J#1
They proposed an 22,1 regularized joint likelihood and an f2.1 regularized coneicondiiional likelihood. They also presented Monte-Carlo approximation to these estimators via proximal gradient descent. Their finite-sample analysis required restricted strong convexity (of the Hessian of the negative log-likelihood of the joint density) and bounded moment-generating function of the variables.
Building upon [55] and 44). Ren et al. [4]] addressed learning continuous exponential family distributions through a series of numerical experiments. They considered unbounded distributions and allowed for terms corresponding to multi-wise interactions in the joint density. However, they considered only monomial natural statistics. Further, they assume node-wise-spane wise-sparsity of the parameters in MRFs and their estimator is defined as a series of node-wise optimization problems.
In summary, tremendous progress has been made on learning the sub-classes of exponential family in (6) and (8) However, this sub-classes are restricted by the assumption that the natural parameters are wises-sese- For example, none of the existing methods for exponential family MRFs work in the setting where the natural parameters have low-rank constraint.
Score-based method. A scoring rule S(x, Q) is a numerical score assigned to a realization x of a random variable and it measures the quality of predictive distribution Q (with probability density g()). If is the true distribution of x, the divergence D(P, Q) associated with a scoring rule is defined as Ex(S((x Q) S(x P).. The MLE is an example of scoring rule with S(, = -- log q(-) and the resulting divergence is the KL-divergence.
To bypass the intractability of MLE, [22] proposed an alternative scoring rule with S(, Q) logg(-) + 2 | (b)]( where A the Laplacian operator, V is the gradient and || ||2 is the & norm. This method is called score matching and the resulting divergence is the Fisher divergence. Score matching is widely used for estimating unnormalizable probability distributions because computing the scoring rule S(,, Q) does not require knowing the partition function. Despite the flexibility of this approach, it is computationally expensive in high dimensions since it requires computing the trace of the unnormalized density's Hessian (and its derivatives for optimization). Additionally, it breaks down for models in which the second derivative grows very rapidly.
In 33], the authors considered estimating truncated exponential family using the principle of score matching. They build on the framework of generalized score matching [21] and proposed a novel estimator that minimizes weighted Fisher divergence. They showed that their estimator is a special case of minimizing a Stein Discrepancy. However, their finite sample analysis relies on certain hard-to-verify assumptions, for example, the assumption that the optimal parameter is well-separated

---

from other neighboring parameters in terms of their population objective. Further, their estimator lacks the useful properties of asymptotic normality and asymptotic efficiency.
1.3 Useful notations and outline
Notations. For any positive integer t, let [t] == (1....,t) .t). For deterministic sequence For a random sequence vi.". V2, we let v == (v v)). For a matrix M E _ we denote the element in ith row and jth column by My. the singular values of the matrix by (M) for E [min(u, v},, the matrix maximum norm by ||M] = [a [Myl the entry-wise L1.1 norm by [|]][, = Eie(u].it(u) |Mall the nuclear norm by ||M]]+ == Exelmintu.o) (M)) We denote the Frobenius or Trace in- ner product of matrices M, N E Roxe by (M, = Eie()),Ejo) My,. For a matrix M E Rux0 we denote generic norm on R=x* by R ((M and denote the associated dual norm by R (M)- == sup NY (R(N) S t} where N Ruxx For tensor U E Raxexw we denote its (.) entry by Usjt, its 1thh slice (obtained by fixing the last index) by Un or U the tensor maximum norm (with a slight abuse of notation) by [|U] max = [e [Uez]], and the
"1.".... lt, we let v = (1,,-..,0) Ub).
tensor norm by |UIT = v /Evelw),J Ubj We denote the tensor inner product of tensors U. E RuxEx" by ((U, V)) = Eielu] wo] Vaj. We denote the vectorization of the tensor U E Ruxexx by Ve)(U) E Ravwxl (the ordering of the elements is not important as long as it is consistent). Let O E Rh x denote the tensor with every entry zero. We denote a p-dimensional ball of radius b centered at 0 by B(0, b).
Outline. In Section 2 examples. In Section we provide our loss function and algorithm. In Section we present our main results including the connections to the MLE of fx(:; θ), consistency, asymptotic normality, and finite sample guarantees. In Section 5 we conclude, provide some remarks, discuss limitations as well as some directions for future work. See supplementary for organization of the Appendix.
we formulate the problem of interest, state our assumptions, and provide
2 Problem Formulation
Let x (.., xp)) be a p dimensioonl vector of continuous random variables let the support of x; be X; C IR. Define X' == I X. Let x , E X be a realization of x. In this work, we assume that the random vector x belongs to exponential family with bounded support (i.e., length of X; is bounded) along with certain additional constraints. More specifically, we make certain assumptions on the natural parameter O E R Xka and on the natural statistic (x)) : X + te x as follows.
3 For any i E [p].
Natural parameter O We focus on natural parameters with bounded norms. However, instead of having such constraints on the natural parameter Ô as it is, we decompose θ into 13 slices (or matrices) and have slice specific constraints. The key motivation for this is to broaden the class of exponential family covered by our formulation. For example, this decomposabilityy allows our formulation to en-capture the sparse- sparse-plus- only low-rank decompositions of θ (see Section 2.J). This is precisely the reason for considering tensor natural parameters instead of matrix natural parameters. Further, we assume k3 0(1) i.e., it does not scale with p. We formally state this assumption below.
decomposition of θ in addition to only sparse or
Assumption 2.1. (Bounded norms of Q.) For every E [Rig], we let (,((()) I r; where @ Rkixkz xk2 is the ith slice of θ R; Rkk xk2 + R4 is norm and is known constant. This decomposition is represented compactly by R(O) S r where R(0) (R, and r (F1,".. (kkg)
RRg ( (ka)))
We define A to be the set of all natural parameters satisfying Assumption 2.1 i.c., A = (() S r}. For any Ô, e E A and t E [0. 1]. we have R(tê + (1 - t)θ) < (R) + (1 - R) ( S tr + (1 - f)r = r. Therefore, 1 + (1 - t) E A and the constraint set A is a convex set.
Even though we focus continuous variables, our framework applies equally discrete variables.
5

---

Natural Statistic o. For mathematical simplicity, we center the natural statistic Φ(-) such that their integral with respect to the uniform density on X' (i.e., Uxx is zero. Ux well-defined because the support X' is a strict subset of TRP i.e., X' C TRP.
Definition 2.1. (Centered natural statistics). The centered natural statistics are defined as follows:
(()) (.) Eexx (x())
In this work, we focus on bounded natural statistics which may enforce certain restrictions on the length of support X. See Section 2.1 for examples. We define two notions of boundedness. First, we make the following assumption to be able to bound the tensor inner product between the natural parameter θ and the centered natural statistic ((-) (see Appendix B.1)
Assumption 2.2. (Bounded dual norms of )). For every i E [ka] and norm R,, we assume that the dual norm R2 of the 8th slice of the centered natural statistic i.e., Φ(0) is bounded by constant d,. Formally, for any i E [Ka] and x E X. (2(0)) (x)) I di. This is represented compactly by R (Ø(x)) S d where R (#(x)) = (RT (x). ... Rks (g(ka) and d = (d1, dkg) )-
Next, we assume that the tensor maximum norm of the centered natural statistic o(.) is bounded by a constant 6max. This assumption stated formally below.
Assumption 2.3. (Bounded lensor maximum norm of Φ). For any x E X, [[[(x]]lma) S Omax.
The Exponential Family, Summarizing, x belongs to minimal truncated exponential family with probability density function as follows
() x exp (((00(()))
where the natural parameter θ E x is such that R()) S and the natural statistic ((x) X - xgiikkxkk, is such that for any x E X, R (f(x)) S d and [x S @max.
Let @r denote the true natural parameter of interest and fx(:; θ*) denote the true distribution of x. Naturally, we assume R(0*)= & r. Formally, the learning task of interest as follows:
Goal. (Natural Parameter Recovery). Given n independent samples of i.e., x(1) x( obtained
from fx(x; O*), compute an estimate Ô of @* in polynomial time such that ||O* Q|| is small.
2.1
Examples
We will first present examples of natural parameters that satisfy Assumption 2.1 Next, we will
present examples of natural statisties along with the corresponding support that satisfy Assumptions
2.2 and 2.3 See Appendix H and [ for more discussion on these examples.
Examples of natural parameter. We provide examples in Table to illustrate the decomposability of as in Assumption 2.1 We will revisit these examples briefly in Section 4 and in-depth in Appendix H Assumption 2.1 should be viewed as a potential flexibility in the problem specification i.., practitioner has the option to choose from a variety of constraints on the natural parameters (that could be handled by framework). For example, in sparse while in some other real-world applications the parameters have low-rank and a practitioner could choose either depending the application at hand. For the ppare-plus--ovve lous-low-rank decomposition,
real-world applications the parameters
Table 1: A few examples of natural parameter θ
Decomposition
h3 Convex Relaxation
Sparse decomposition (Q* (O)(1))
| |11 Sm
Low-rank decomposition (0- -0-=(00)) (0~(1))
|0001]]|_ 51
Sparse-plus-low-rankk decomposition
| I1, Sn and ||012)]| S r2
(0* (0))))))((2
more natural think about the minimality of the exponential family in terms of matrices as opposed to tensors. See Appendix for details.

---

Examples of natural statistic. The following are few example of natural statistics (along with the corresponding support) that fall in-line with Assumptions 2.2 and 2.3
1. Polynomial statistics: Suppose the natural statistics are polynomials of x with maximum degree 1,
i.e., [ee[s] " such that 4 2 0 vi E [p] and Eielp) 4 S l. If = [0, bj for b E IR, then @max
26'. If O* has sparse decomposition and X [0, for b R. then R (x)) 26 Further,
@ has low-rank decomposition, / = 2, and X' = (0, 6) for 6 E R. then R (x(x) decomposition,
x))== S. 2(1+6)).
Finally, if O' has sparse- pesss--puu--oww-re
and (00, b) for E R, then
R' (x(x)) & (2b², 2 2b").
2. Trigonometric statistics: statsiiserricsstiittiesss Suppose the natural statistics are sines and cosines of x with / different
frequencies, i.e., sin (ii 4x,)) U cos cos(Eiilp) [,a;)) such that E [7] U (0). For any X C RP,
Φmax 2. e has sparse decomposition, then R (P(x)) < 2 for any X C I.P.
Our framework also allows combinations of polynomial and trigonometric statistics (see Appendix
Algorithm
We propose a novel, computationally tractable loss function drawing inspiration from the recent
advancements in exponential family Markov Random Fields [56 55
The loss function and the estimator. The loss function, defined below, is an empirical average of the inverse of the function of x that the probability density fx(x; θ) is proportional to (see (9).
Definition 3.1 (The loss function). Given samples (1..... .x(") of x, the loss function maps IR x to (O) E R defined as
C, (0)
Σ exp (- (0,
(10)
The proposed estimator θ, produces an estimate of O by minimizing the loss function (O) over all natural parameters θ satisfying Assumption
2.1 i.e.
θ E arg min C. (9). BEA
(11)
For any 0, Ô.,,. is an c-optimal solution of Ô, if L, (O..) S (ê.) + The optimization in I a convex minimization problem (i.e., minimizing convex function E, over convex set A) and has efficient implementations for finding e-optimal solution. Although alternative algorithms (including Trank-Wolfe, can be used, we provide a projected gradient descent algorithm below.
Algorithm 1: Projected Gradient Descent
Input: 1). T,A
Output: θ..
Initialization: (0) for t 0, do
(c41) + arg minges [0(()) .)V O||
Ô + -((-1)
The following Lemma shows that running sufficient iterations of the projected gradient descent in Algorithm results in an c-optimal solution of é,,
Lemma 3.1. Let Assumptions 2 2.2 and 2.3 be satisfied. Let 1 1/ kokg exp(rTal d). Then,
Algorithm returns an c-optimal solution θ as long
2k: k2kg exp(r T d)
12.
(12)
Further, ignoring the dependence on k3, Qmax. r and d, T in 12) scales as (poly kikz
"We believe that for polynomial and/or trigonometric natural statistics, Assumptions 2.2 and 2.3 would hold whenever the domain of X' is appropriately bounded.
7

---

The proof of Lemma 3.1 can be found in Appendix B
The proof outline is as follows: (a) First, we prove the smoothness property of 2, (b) Next. we complete the proof using standard result from convex optimization for the projected gradient descent algorithm for smooth functions.
4 Analysis and Main results
In this section, we provide our analysis and main results. First, we focus on the connection between our method and the MLE of (x @r @). Then, we establish consistency and asymptotic normality of our estimator. Finally, we provide non-asymptotic finite sample guarantees to recover O*.
1. Connection with MLE of fx(:; -r )). First, we will establish a connection between the population version of the loss function in (T)) (denoted by ((O) and the KL-divergence of the uniform density on X' with respect to fx; O θ). Then, using minimality of the exponential family, we will show that this KL-divergence and (()) are minimized and only if O This provides justification for the estimator in [1] as well as helps us obtain consistency and asymptotic normality of Ô,.
For any θ A, (()) = TE exp (-((9,((x)) The following result shows that the population
version of the estimator in (TT is equivalent the maximum likelihood estimator of fx(x; 0 +).
Theorem 4.1. With ( representing the KL-divergence,
arg min ((O)
arg min (( II [x(:;"- -)).
GEA
Further, the true parameter @* is the unique minimizer ((0).
The proof of Theorem 4.] can be found in Appendix C The proof outline is as follows: : (a) First, we express fx +) in terms of ((O) (b) Next, complete the proof by simplifying the KL-divergence between (-)-)) and fx(:; O* -).
2. Consistency and Normality. We establish consistency and asymptotic normality of the proposed estimator ,, by invoking the asymptotic theory of M-estimation. We emphasize that, from Theorem 4.1 the population version of Ô, is equivalent to the maximum likelihood estimate of fx(: O θ) and not f=(:; +). Moreover, there no clear connection between é,, and the finite sample maximum likelihood estimate of fx(:; Q) or fx(:; O - θ). Therefore, we cannot invoke the asymptotic theory of MLE to show consistency and asymptotic normality of Ô,.
Let A(O*) denote the covariance matrix of vee (xx(xx exp (- ((0 ((0*'((()))))))))) .(x))))) Let B(0*) denote the cross-covariance matrix vec(&(x)) and vec($(x) exp (-< (x)))) Let (N, , Σ) represent the multi variate Gaussian distribution with mean vector μs and covariance matrix E.
Theorem 4.2. Let Assumptions 2. 2.2 and 2.3 be satisfied. Let Ôn be solution of 1II Then, as n xc, 6, 3 O-, Further, assuming O E interior(A) and B(0*) is invertible, we have ((O))
V x vec(@,, (,, )*) $
The proof of Theorem 4.2 can be found in Appendix D The proof is based on two key observations (a) Ô,, is an M esstmmator and (b) (()) is uniquely minimized at θ*.
3. Finite Sample Guarantees. To provide the non-asymptotic guarantees for recovering O*, re- quire the following assumption on the smallest eigenvalue of the autocorrelation matrix of vec()(x)).
Assumption 4.1. (Positive eigenvalue of the autocorrelation matrix of Φ.) Let Amin denote the minimum eigenvalue of [x(vec( (x))ee(((()))e((((x))) We assume Amiu strictly positive i.e., Amia
We also make use of the following property of the matrix norms.
Property 4.1. For any norm R. IR - R.,, and matrix M E BR Ri there exists g such that
R(M) < gki kg M]] m|xx-
For most matrix norms of interest including entry-wise Tup. norm (p.g 2 1), (p 2 1), and operator p-norm (p 2 1). we have g = 1 as shown in Appendix ]
Schatten p-norm
8

---

Let = (g1.-.. 9Kg) where Vi E [ka]: 9: is such that R S g:kgky [ max with R being the dual norms from Assumption 2.2
Theorem 4.3 below shows that, with enough samples, the e-optimal solution of Ó, close to the true natural parameter in the tensor norm with high probability.
Theorem 4.3. Let Ö.,n be an e-optimal solution of O, obtained from Algorithm 1 for of the order (a Amin). Let Assumptions 2.7
2.2 2.3 and 4.1
(.11b be satisfied. Recall Property 4.1 Then, for any
ô E (0, 1), we have ||0,,n 1T with probability at least 1 - 8 as long
hi ki1k2
)
2 O
log (~))
(13)
The computational cost scales as 0 ki max (ka c(A)) where c(A) is the cost of projection
onto A. Further, ignoring the dependence on 6, Amin. and c(A), n. in (13) (as well as the associated computational cost) scales as Opooly (y
The proof of Theorem 4.3 can be found in Appendix G The proof is based two key properties
of the loss function L. (+)= (a) with enough samples, the loss function C., (e) naturally obeys the restricted strong convexity with high probability and (b) with enough samples, V (O") max is bounded with high probability. See the proof for the dependence of the sample complexity and the computational complexity on k3, r, d. g and @max-
The computational cost of projection onto i.c., c(A) is typically polynomial in k2 In Appendix H we provide the computational cost for the example constraints on the natural parameter O from Section 2.1 i.e. sparse decomposition, low-rank decomposition, and sparse sparse-plus- plus-low-rand decomposition.
4. Comparison with the traditional MLE. To contextualize our method, we compare it with the MLE of the parametric family fx(:; θ). The MLE of [x(:; O) minimizes the following loss function
min Σ ((0, ((x()))) + log /
exp (((e,
(14)
XEX
The maximum likelihood estimator has many attractive asymptotic properties : (a) consistency (see 16 Theorem 17J). i.e., as the sample size goes to infinity, the bias in the estimated parameters goes to zero, (b) asymptotic normality (see [16] Theorem 18]), i.e., the sample size goes infinity, normalized estimation eгror coverges to a Gaussian distribution and (c) asymptotic efficiency (see [66] Theorem 20]), i.e., as the sample size goes infinity, the variance in the estimation error attains the minimum possible value among all consistent estimators. Despite having these useful asymptotic properties of consistency, normality, and efficiency, computing the maximum likelihood estimator
computationally hard [22 26
Our method can be viewed as a computationally efficient proxy for the MLE. More precisely, method is computationally tractable as opposed to the MLE while retaining the useful properties of consistency and asymptotic normality. However, our method misses out asymptotic efficiency. This raises an important question for future work - can computational and asymptotic efficiency be achieved by single estimator for this class of exponential family?
can
5 Conclusion, Remarks, Limitations, Future Work
In this section, we conclude, provide a few remarks, discuss the limitations of our work as well as some interesting future directions.
Conclusion. In this work, we provide a computationally and statistically efficient method to learn distributions in a minimal truncated k-parameter exponential family from i.i.d. samples. We propose a novel estimator via minimizing a convex loss function and obtain consistency and asymptotic normality of the same. We provide rigorous finite sample analysis to achieve an a-approximation to the true natural parameters with (poly(k//a) samples and O O(poly(& (k/a)) computations. We also provide interpretation of our estimator in terms of a maximum likelihood estimation.
Wode-wise-sparse exponential family MRFs vs general exponential family. We highlight that the focus of our work is beyond the exponential families associated with node- sise- MRFs and

---

towards general exponential families. The former focuses on local assumptions on the parameters such as wodd-wise-sparsiyy and the sample complexity depends logarithmically on the parameter dimension i.e., ((log(k)) In contrast, our work can handle global structures on the parameters (e.g.. a low-rank constraint) and there are no prior work that can handle such global structures with sample complexity (llog())) [k)). Similarly, for see--wiisssssssss MRFs there has been a lot of work to relax the assumptions required for learning (see the discussion on Assumption [.].oooww) Since our work focuses on global structures associated with the parameters, we leave the question of relaxing the assumptions required for learning as an open question. Likewise, the interaction screening objective [56) and generalized interaction screening objective [55 44 were designed for node-wis wide-wiseepee parameter estimation i.e., they require the parameters to be wode-wise-sparce and are less useful when the parameters have global structure. On the contrary, our loss function is designed to accommodate global structures on the parameters.
For sisle--isssspssee pairwise exponential family MRFs (e.g., Ising models), which a special case of the setting considered in our work, Assumption i.T proven (e.g., Appendix T.1 of [44] provides one such analysis for a condition that is equivalent to Assumption [. for sparse continuous graphical model). However, such analysis typically requires (a) a bound on the infinity norm of the parameters and a bound on the degree of each node or (b) a bound on the e norm of the parameters associated with each node. Since the focus of our work is beyond the exponential families associated with node-wise-se wise-sparse MRFs, we view Assumption 4. as adequate condition to rule out certain singular distributions (as evident in the proof of Proposition E. where this condition is used to effectively lower bounds the variance of a non-constant random varialle) and expect it to hold for most real-world applications. Further, we highlight that the MLE in (14p remains computationally intractable even under Assumption 4.1 To see this, one could again focus on mode-wise-spane pairwise exponential family MRFs where Assumption 4.1 is proven and the MLE is still known to be computationally intractable.
Assumption 4.1
Sample Complexity, We do not assume p (the dimension of x) to be constant and think of kj and 2y as implicit functions of p. Typically, for an exponential family, the quantity of interest is the number of parameters i.e., k and this quantity scales polynomially in p e.g., k = Opp²) for Ising model, k = OOp') for t-wise MRFs over binary alphabets. Therefore, in this scenario, the dependence of the sample complexity on would also be Oppoly(p). Further, the 1/a+* dependence of the sample complexity seems fundamental our loss function. For learning node-wise-spee wise-sparse MRFs, this dependence is in-line with some prior works that use a similar loss function [44]55) as well as that do not use similar loss function [29]. While it is known that for learning pode-wise-sparss
MRFs (56) and truncated Gaussian [33 one could achieve a better dependence of 1/a², it is not yet clear how the lower bound on the sample complexity would depend on a for the general class of exponential families considered in this work (which may not be sparse or Gaussian).
Practicality of Algorithm I While the optimization associated with Algorithm I is convex minimization problem (i.c.. (TT) and the computational complexity of Algorithm i polynomial in the parameter dimension and the error tolerance, computing the gradient of the loss function requires centering of the natural statisties (see (26). If the natural statistics are polynomials or trigonometric, centering them should be relatively straightforward (since the integrals would have closed-fomm expressions). In other cases, centering them may not be polynomial-timg and one might require an assumption of computationally efficient sampling or that obtaining approximately random samples of x is computationally efficient [1].
Limitations and Future Work. First, in our current framework, we assume boundedness of the support. While, conceptually, most non-compact distributions could be truncated by introducing a controlled amount of error, we believe this assumption could be lifted for exponential families: P([x| Z loog)) S oy where c > 0 is a constant and y > O. Alternatively, the notion of multiplicative regularizing distribution from 41 could also be used. Second, while the population version of our estimator has a nice interpretation in terms of maximum likelihood estimation, the finite sample version of our estimator does not have similar interpretation. We believe there could be connections with the Bregman score and this is an important direction for immediate future work. Third, while our estimator is computationally efficient, consistent, and asymptotically normal, it not asymptotically efficient. Investigating the possibility of a single estimator that achieves computational and asymptotic efficiency for this class of exponential family could be an interesting future direction. Lastly, building on our framework, empirical study is an important direction for future work.
10

---

Acknowledgments and Disclosure of Funding
This work was supported, in part, by NSR under Grant No. CCF-1816209, ONR under Grant No. N00014-19-1-200 the NSF TRIPODS Phase II grant towards Foundations of Data Science Institute, the MIT-IBM project on time series anomaly detection, and the KACST project on Towards Foundations of Reinforcement Learning.
References
[1] T. Amemiya. Advanced econometrics. Harvard university press, 1985.
[2] O. Barndorff-Nielen. Information and exponential families: in statistical theory. John Wiley Sons, 2014.
[3] A. Barp, F-X. Briol, A. B. Duncan, M. Girolami, and L. Mackey. Minimum stein discrepancy estimators. arXiv preprint arXiv: (tte::990000288 08283, 2019.
[4] J. Besag. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society: Series D (The Statistician), (4(3):179-115, 1975.
L. Brown. Fundamentals of statistical exponential families: with applications in statistical decision theory. Ims, 1986.
[6] T. Cai, W. Liu, and X. Luo. A constrained & minimization approach to sparse precision matrix estimation. Journal of the American Statistical Association, 106(494):594-607, 2011.
[7] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1337 1-7,, 2011.
[8] V. Chandrasekaran, P. A. Parrilo, and A. S. Willsky. Latent variable graphical model selection via optimization. 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1610-1613. IEEE, 2010.
[9] K. Chwialkowski, H. Strathmann, and A. Gretton. A kernel test of goodness of fit. In International conference machine learning, pages 2606-2615. PMLR, 2016.
[10] Y. Dagan, C. Daskalakis, N. Dikkala, and A. V. Kandiros. Learning ising models from multiple samples. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 161-168,20 2021.
[11] B. Dai, Z. Liu, H. Dai, N. Hc, A. Gretton, L. Song, and D. Schuurmans, Exponential family estimation via adversarial dynamics embedding. arXiv preprint 1rXiv:1904. 12083, 2019.
[12] G. Darmois. Sur les lois de probabilitéa estimation exhaustive. CR Acad. Sci. Paris, 260(1265):88 1935.
[13] C. Daskalakis, T. Gouleakis, C. Tzamos, and M. Zampetakis. Efficient statistics, in high dimensions. from truncated samples. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 639-649. IEEE, 2018
[14] Diakonikolas, dobrushin's 's condition. arXiv preprint arXiv:2102.02.71, 2021.
Kane, A. Stewart, and Sun. Outlier-robust learning ising models under
[15] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the f for learning in high dimensions. In Proceedings of the 25th international conference Machine learning, pages 272-279, 2008
[16] T. Ferguson. A course large sample theory. Routledge, 2017.
[17] R. Fisher. Two new properties of mathematical likelihond. Proceedings of the Royal Society of London. Series A, Containing Papers of Mathematical and Physical Character, 144(852):2853377, 1934.
[18] Friedman, T. Hastic, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432 141 2008
[19] G. E. Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-1800 2002.

---

[20] R. V. Hogg and A. T. Craig. Sufficient statistics in elementary distribution theory. Sankhyā: The Indian Journal Statistics (1933-1960), 17(3):09--166 1956.
[21] A. Hyvärinen. Some extensions of score matching, Compitational statistics & data analysis, 51(5):2499- 2512, 2007.
[22] A. Hyvärinen and P. Dayan. Estimation of non- normalomalz statistical models by score matching, Journal of Machine Learning Research, 6(4), 2005.
[23] M. Jaggi. Revisiting frank-wolfc: Projection-free sparse convex optimization. In International Conference Machine Learning, pages 427-435. PMLR, 2013.
[24] A. Jalali, P. Ravikumar, V. Vasuki, and S. Sanghavi. On learning discrete graphical models using group- sparse regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA. April 11-13, 2011. pages 378-387, 2011.
[25] R. I. Jennrich. Asymptotic properties of non-linear least squares estimators. Ann. Math. Statist,, 40(2):633 643, 04 1969.
[26] M. Jerrum and A. Sinclair. Approximating the permanent. SIAM journal on computing, 18(6): 149-111799177 1989.
[27] S. Kakade, O. Shamir, K. Sindharan, and A. Tewari. Learning exponential families in high- digh-dimensions:: Strong convexity and sparsity. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 381-388. JMLR Workshop and Conference Proceedings. 2010.
[28] J. Kelner, F. Koehler, R. Mcka, and A. Moitra. Learning some popular gaussian graphical models without condition number bounds. 2019.
[29] A. R. Klivans and R. Mcka. Learning graphical models using multiplicative weights. In 58th IEEE Annual Sympusium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 343-354, 2017.
[30] B. O. Koopman. On distributions admitting a sufficient statistic. Transactions of the American Mathematical society, 39(3):399-400 409, 1936.
[31] L. Lin. M. Drton, and A. Shojaie. Estimation of high- dineenninnii graphical models using regularized score matching. Electronic journal of statistics, 10(1):806, 2016.
[32] Q Liu, J. Lec, and M. Jordan. A kemelized stein discrepancy for goodness-of- fit tests. In International conference machine learning, pages 276-284. PMLR, 2016.
[33] S. Liu, T. Kanamori, W. Jitkrittum, and Y. Chen. Fisher efficient inference of intractable models. Advances in Neural Information Processing Systems, 1188793-8803 2019.
[34] S. Liu, T. Kanamori, and D. J. Williams. Estimating density models with truncation boundaries. arXiv preprint arXiv:1910.0388 2019.
[35] B. Meghana and N. He. Lower bounds & projected gradient descent.
[36] N. Meinshausen, P. Bühlmann, al. High-dimensional graphs and variahle selection with the lasso. Annals of statistics, 436-1143, 2006.
[37] Z. Meng, B. Eriksson, and A. Hero. Learning latent variable gaussian graphical models. In International Conference on Machine Learning, pages 1269-1277. PMLR, 2014.
[38] S. Na, M. Kolar, and O. Koyejo. Estimating differential latent variable graphical models with applications to brain connectivity. arXiv preprint / http:://900000922, 2019.
[39] Y. Ning, T. 7hao, H. Liu, al. A likelihood ratio framework for high-dimensional semiparametric regression. Annals of Statistics, 45(6):2299-3377,20 2017.
[40] E. J. G. Pitman. Sufficient statistics and intrinsic accuracy. In Mathematical Proceedings of the cambridge Philosophical society, volume 32, pages 567-579. Cambridge University Press, 1936.
[41] C. X. Ren, S. Misra, M. Vuffray, and A. Y. Lokhov. Learning continuous exponential families beyond gaussian, 2021.
[42] B. Rhodes, K. Xu, and M. U. Gutmann. arXiv:2006.1222 12204, 2020.
Telescoping density-ratio estimation. arXiv preprint
12

---

[43] C. Robert and G. Casella. Monte Carlo statistical methods. Springer Science & Business Media, 2013.
[44] A. Shah, D. Shah, and G. Wornell. On learning continuous pairwise markov random fields. In International Conference on Artificial Intelligence and Statistics, pages 1153-1161. PMLR, 2021.
[45] N. Simon, J. Friedman, Hastie, and Tihshirani. A sparse-group lasso. Journal of computational and graphical statistics, 22(2)231-245, 2013.
[46] B. Sripcrumbudur, K. Fukumizu, A. Gretton, A. Hyvärinen, and R. Kumar. Density estimation in infinite dimensional exponential families. Journal of Machine Learning Research, 18, 2017.
[47] H. Strathmann, D. Sejdinovic, S. Livingstone, 7. Szabo, and A. Gretton. Gradient-free hamiltonian monte carlo with efficient kernel exponential families, arXiv preprint arXiv: 1506..04444 2015.
[48] A. S. Suggala, M. Kolar, and P. Ravikumar. The expxorcist: Nonparametric graphical models via conditional exponential densities. In Advances in Neural Information Processing Systems, pages 1446-4456 2017.
[49] S. Sun, M. Kolar, and J. Xu. Learning structured densities infinite dimensional exponential families. In Advances in Neural Information Processing Systems, pages 2287-2299 2015.
[50] D. Sutherland, H. Strathmann, M. Arbel, and A. Gretton. Efficient and principled score estimation with nyström kernel exponential familics, In International Conference on Artificial Intelligence and Statistics, pages 652-660. PMLR, 2018.
[51] W. Tansey, O. H. M. Padilla. A. Suggala, and Ravikumar. Vector-space markov random fields via exponential families. International Conference on Machine Learning. pages 684-692, 2015.
[52] L. G. Valiant. The complexity enumeration and reliability problems. SIAM Journal on Computing. 83)):400-21,, 1979.
[53] A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[54] G. Vinci, V. Ventura, M. A. Smith, and R. E. Kass, Adjusted regularization in latent graphical models: Application to multiple-neuron spike count data. The annals of upplied statistics, 12(2):1068. 2018.
[55] M. Vuffray, S. Misra, and A. Y. Lokhov. Efficient learning of discrete graphical models. CoRR, 1bs/09 2019.
[56] M. Vuffray, S. Misra, A. Y. Lokhov, and M. Chertkov. Interaction screening: Efficient and sample-optimal learning of ising models. Advances in Neural Information Processing Systems, pages 2595-2603, 2016.
[57] M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. Tree-reweighted belief propagation algorithms and approximate ml estimation by pseudo momentt matching. In AISTATS, volume 3, page 3, 2003.
[58] M. J. Wainwright and M. 1. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, (11-2):1-305, 2008.
[59] M. J. Wainwright, P. Ravikumar, and J. D. Lafferty. High nigh-dimensiooal graphical model selection using 41- regularized logistic regression. Advances in Neural Information Processing Systems, pages 2006.
[60] W. Wang. M. J. Wainwright, and K. Ramchandran. Information-theons bounds on model selection for gaussian markov random fields. In 2010 IEFE International Symposium on Information Theory, pages 1373-1377. IEEF, 2010.
[61] L. Wenliang, D. Sutherland, H. Strathmann, and A. Gretton. Learning deep kernets for exponential family densities. In International Conference on Machine Learning, pages 6737-6746. PMLR, 2019.
[62] E. Yang. Ravikumar, I. Allen, and Liu. Graphical models via univariate exponential family distributions. J. Mach. Learn. Res., 04:3813-3847, 2015.
[63] Z. Yang. Y. Ning, and H. Liu. On semiparametric exponential family graphical models. The Journal of Machine Learning Research, (9111 222314-23722 2018.
[64] X. Yuan, P. Li, T. Zhang, Q. Liu, and G. Liu. Learning additive exponential family graphical models via f2, 1 -norm regularized m-estimation. In Advances in Neural Information Processing Systems, pages 4367-4375 2016.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section S
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work theoretical in nature.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Each theoretical result accompanied with the assumptions required.
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are in the supplementary. Each theoretical result is followed by an appropriate reference to corresponding proof. Each theoretical result also followed by either the proof outline or the key ideas used in the proof.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "d5onn_G1_H", "reviewer": "Reviewer_sAxR", "summary": "The paper presents a new estimator of the natural parameters of an exponential family with bounded support. To derive the proposed estimator, the authors first present a new loss function which does not involve the normalizing constant. Then the proposed estimator is defined as the minimizer of the loss function. Consistency and asymptotic normality of the proposed estimator is shown. Also, the condition on the number of samples and that on the computational cost are given to achieve a certain approximation of the proposed estimator to the true parameter.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The presented estimator seems new. Theorem 4.1 implies that the population version of the proposed estimator is equivalent to the maximum likelihood estimator (MLE), but its sample version is different in general and is claimed to be calculated more efficiently than the MLE. Related works are well explained and the background of this work is clear.\n\nQuality: The submission seems technically sound. The claims are well supported theoretically. No experimental study is given in the paper.\n\nClarity: The paper is clearly written in general. Appendix is very helpful because it provides detailed proofs of the theoretical results given in the paper.\n\nSignificance: I reckon that the theoretical results of the paper are nice. The presented estimator has two desirable properties, namely, consistency and asymptotic normality. Also, the calculation of the loss function (10) is simpler than the likelihood function in the sense that the proposed loss function does not involve the calculation of the normalizing constant at each step of the algorithm.\n\nHowever the authors do not conduct any experiment to compare the proposed estimator with MLE and other existing estimators in terms of their performance and computational cost. Without the experiments, it is difficult to convince readers of the importance of the proposed estimator. Although Theorem 4.3 is helpful to evaluate the performance and computational cost of the proposed estimator, I think empirical results are necessary to verify the theoretical results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations of their work. As pointed out by the authors in the last section of the paper and by this reviewer in the last paragraph of \"Main Review\" Section, empirical study is an important direction. I suggest that the authors conduct (at least simple) experiments in this work rather than in future work.\n\nI do not find any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not find any ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "a04_O-1baRD", "reviewer": "Reviewer_SSuU", "summary": "   In this paper, the authors consider the problem of estimating the\n  natural parameters of an exponential family with bounded values from samples.\n  With bounded values we refer to the fact that both the norm of the sufficient\n  statistics and the norm of the parameters are bounded.\n\n  Their main result is an efficient estimation algorithm with sample\n  complexity that is roughly equal to d^2/a^4 where d is the number of\n  parameters of the exponential family and a is the estimation error.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "  Strengths\n  ====================\n\n  - The problem of learning exponential families is very relevant and has a\n  wide range of applications in many scientific areas.\n\n  - The proposed solution is elegant and can be applied to real world scenarios\n  where a theoretical guarantee is important.\n\n  - The authors do not only provide finite sample results but also asymptotic normality and asymptotic efficiency.\n\n\n  Weaknesses - Comments\n  ========================\n\n  1. The main drawback of the current finite sample result is that it seems\n  suboptimal. In particular, in many cases, e.g., Gaussian distributions,\n  exponential distributions, linear regression, Poisson distributions, etc., the\n  sample complexity for parameter estimation is of order d/a^2 instead of\n  d^2/a^4. Is their an example of an exponential family where d^2/a^4 are\n  necessary?\n\n  2. Example applications of Theorem 4.3 are missing. What is the result if we\n  apply this theorem to bounded value exponential families like Ising models or\n  Mallows distributions or truncated Gaussian distributions. For the latter,\n  how are the results compared to the recent work of [*].\n\n  3. There is one way to compute the maximum likelihood estimation via sampling.\n  In particular, it is not hard to see that if we can sample any given member\n  of the exponential family then we can compute an unbiased estimation of the\n  gradient of the log-likelihood function. Using this unbiased gradient we can\n  run the Stochastic Gradient Descent algorithm which will converge because the\n  log-likelihood function is convex. One particular property that is important\n  for this is Assumption 4.1 which states that the log-likelihood function is\n  not only convex but also strongly convex. Since Assumption 4.1 is necessary\n  for the main result of this paper it is important that the lower bounds for\n  computing MLE holds even under the Assumption 4.1. Is this true based on the\n  known lower bounds?\n\n  4. In a lot of places in the paper the use of the expectation operator is not\n  very clear. For example, in Assumption 4.1 it is not clear what is the\n  expectation over. My guess is that the expectation is over x ~ f_x(\\Theta)\n  and the assumption should hold for all \\Theta \\in \\Lambda.\n\n  5. The result cannot be applied to many natural exponential families, e.g.,\n  exponential families with unbounded support and sufficient statistics that\n  are polynomial functions.\n\n  [*] https://arxiv.org/abs/1809.03986\n\n\n  Summary of Recommendation\n  ======================================\n  The results provided in this paper seem to be important towards a better\n  understanding of the important problem estimating the parameters of\n  exponential families from samples. The solution provided is computationally\n  efficient and elegant and for this reason I recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "QqETiGWywmU", "reviewer": "Reviewer_kMiC", "summary": "This paper considers the parameter estimation of the minimal exponential family and proposed an estimator by minimizing a convex objective function. The resulting estimate is proved to be consistent, asymptotically normal, and has polynomial sample complexity. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem considered is of broad interest, and the overall analysis and presentation are clear. The main issue of this paper is the validity of assumptions. The key assumption 2.1 assuming constant r and d needs justification since the dependency on r and d is exponential. Currently, I don't see any other benefits of using the tensor formulation, and this assumption looks pretty restrictive. Also, the author comments on the restriction of boundedness assumption, so it'd be helpful to extract the explicit dependency on the bound. For the results on such a specific problem with a series of assumptions, the notion of poly is not sufficient (btw, it is inappropriate to use $\\approx$ in a theorem statement). For instance, the rate $1/\\alpha^4$ should be properly discussed. \n\n======\n\nElaborations on the review comments: \n- Tensor formulation: as the authors pointed out, the formulation in (1) and (2) are equivalent. Can you explain the necessity of using tensor formalism? From my understanding, Assumption 2.1 restricts the norm of each slice of the tensor, so it appears that a matrix formulation suffices for that purpose. \n- Notion of poly: as the problem is tailored to a parametric formulation, I'd expect some parametric rate. However, the current $1/\\alpha^4$ is far from the parametric rate. So please explain more about your result. For instance, can you discuss whether $1/\\alpha^4$ is tight or loose? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the paper. The potential negative societal impacts are not available as the paper is mostly on the theoretical aspects. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1zIgYNLKz8x", "reviewer": "Reviewer_kDGo", "summary": "The authors consider the problem of estimating parameters of an exponential family from i.i.d samples. Although MLE has all the nice statistical guarantees, it is open to efficiently compute it. In this work, the authors overcome the computational difficulty by proposing a new estimator. This new estimator can be computed efficiently and under certain conditions also has nice statistical guarantees except for the asymptotical efficiency.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The things that I like about the paper.\n1) The problem considered here is fundamental and the results presented are quite interesting. \n2) The authors provide the first efficient estimator with nice statistical guarantees. In particular, their estimator achieves polynomial sample complexity.\n3) The authors do a good job of discussing the limitation of their work.\n4) The paper is well structured and does a clear presentation of the results.\n\nFew concerns/suggestions:\n1) Notation was a little confusing at few places. For instance, using italic and bold characters to denote different quantities was difficult to notice. However, I don't have any better suggestions.\n2) Maybe include some experiments comparing the performance of the proposed algorithm with previous work on learning Gaussian distributions. I am curious to see the empirical performance of the proposed estimator if the underlying distribution is Gaussian. \n3) The proposed estimator doesn't achieve asymptotic efficiency and they pose this as an open problem. \n4) As this is the first paper to introduce the problem of estimating parameters of the exponential family. It would have been nice if the authors included some non-trivial information-theoretic lower bounds. Also in the related work, talk about the sample complexity for the Gaussian case and compare it with the more general exponential family.\n5) Provide an explanation on why various assumptions in the paper are reasonable/necessary and the difficulties in designing algorithms without these assumptions. In particular, try to provide real-world applications where the assumptions considered in this paper hold.  \n\nI would be happy if authors could handle a subset of these suggestions/concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do a good job of addressing the limitations of their work. Although the current work is theoretical in nature, I would urge authors to think about the potential societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a computationally efficient estimator for learning truncated exponential family distributions from i.i.d. samples. In addition, the proposed estimator is consistent and asymptotically normal.

This paper was viewed as a borderline paper.

There is a well-known tradeoff between computation and statistics. That is, something that is more computationally efficient might be less statistically efficient. In addition, the optimization problem does not use any sparsity-encouraging or low-rank prior. Thus, the polynomial sample complexity is somewhat expected (versus a logarithmic one.)

Unfortunately, it is unclear whether the same arguments would be possible for an optimal method for learning sparse models. (Perhaps from restricted strong convexity but it is ultimately the responsibility of the authors to provide a full proof.) Regarding presentation, I also concur that the tensor notation might be unnecessary. In addition, while not necessary, NeurIPS readers would appreciate synthetic experiments on simple examples, such as truncated Gaussian distributions or discrete pairwise MRF for a small number of nodes.

On the other hand, the paper proposes a new idea that can inspire other researchers in other problems/areas. Specially given that the focus is on such a fundamental problem as finding alternatives to MLE. In particular, the paper proposes a sum of factor potentials (corrected with a uniform distribution), instead of MLE which uses the sum of log factor potentials and the (NP-hard) log partition function.
Decision: Accept (Poster)