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/e 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 likeliidi 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:) + Σ (1))
(8)
RE(P]
J#1
They proposed an 22,1 regularized joint likelihood and an f2.1 regularized cone-condiiional 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 wpses-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: statiiiserricsstiittiesss 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 wrole- 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.1 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 vec (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 k2 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

---

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 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-sparsity 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 [.].booww) 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::9900002880 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.
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--116, 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- normalomdlz 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- dineeniinnii 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": "eUeN0HlJRf1", "reviewer": "Reviewer_nf2S", "summary": "This paper studies learning the natural parameter of a $k$-parameter minimal exponential family in the classical setting where the algorithm receives i.i.d. samples from the underlying distribution.\n\nThe author provides a computationally and statistically learning algorithm that outputs an estimate of the parameter of a $k$-parameter minimal exponential family within error $\\alpha$ in $\\ell_2$ norm with sample complexity $O(\\mathrm{poly}(k/\\alpha))$ and computationally complexity $O(\\mathrm{poly}(k/\\alpha))$ under some additional assumptions.", "questions": "", "limitations": "", "rating": 5, "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 innovative part of the proof is that instead directly analyzing the log-likelihood function of the minimal exponential family (which is NP-hard to compute in general), the author applies the projected gradient descent framework for smooth functions to a new loss function $L_n(\\Theta)$ (which is described in Definition 3.1). In addition, the author establishes some connections between their methods and the MLE of a re-parameterized distribution.\n\nIt seems that the author assumes that the dimension $p$ of the vector $x$ is a constant and it takes $O(k_1k_2n)$ time to compute the gradient of the loss function $L_n(\\Theta)$. Perhaps one thing I would like to see accounted for is the dependence of the bounds on $p$. Is the algorithm (specifically the running time for computing the gradient of $L_n(\\Theta)$) still computationally efficient on the dimension $p$? This gets quite hard to track through the proofs.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors adequately addressed the limitations and potential negative societal impact of their work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cdOXqAjWtVT", "reviewer": "Reviewer_xSou", "summary": "The paper studies the problem of learning truncated minimal exponential families. Here truncated refers to bounding the distribution in a certain domain which is equivalent to a re-normalization, and minimal refers to to a non-reducible representation of the exponential family. Towards this goal, the paper proposes a computationally tractable estimator which satisfies consistency, normality and gets finite sample guarantees. They further show that the proposed estimator is closely related to the MLE of a shifted distribution.\n\nThe paper provides guarantees which cover general norms and continuous/bounded features. The proposed estimator is closely related to prior estimators (see 2 below) and has nice connections to the MLE and satisfies most desirable properties. The techniques are standard, where the loss is proven to be smooth and strongly convex (restricted) to guarantee recovery of the parameters. ", "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": "Overall, the paper is well-written and covers various settings of parameter sparsity and low-rank. However, the bounds presented currently have sample complexity dependent polynomially in the parameter dimension. In most works in the field, sparsity and other assumptions allow to get away with logarithmic dependence on the parameter dimension and this is a major challenge that these works address. The same trade-off is not present here despite assuming norm-bounds on the parameters. This makes me less excited about the result. There are also a few other questions/comments I have below, addressing which would increase my confidence in the paper.\n\nComments/Suggestions:\n1. There has been a lot of work relaxing the assumptions of node conditional learning. With only assumptions on sparsity and a lower bound on minimum weight of the underlying graph, Klivans and Meka [1] gave a computationally efficient algorithm achieving optimal rates for Ising Models/MRFs. \n2. Vuffray et. al. [2] have previously proposed an estimator ISO which is similar to the proposed objective albeit the node-wise structure. Please compare with that as well.\n3. As far as I understand, in prior work on Ising models, Assumption 4.1 is in fact proven and $\\lambda_{min}$ depends on minimum edge weight and $\\ell_1$ norm. Since it depends on the parameter $\\theta^*$ it is important to discuss why it is reasonable to make this assumption and what it entails.\n4. Sparsity and low-rank structure is based on this 3-way tensor formulation. One could take alternate formulations. I believe the results shouldn't substantially change based on this. Why is the preference for such a decomposition?\n5. Computing the centering of the features would require some sampling which is not described. Would be good to include.\n\nTypos:\n1. Line 266 $\\phi_{max} = 2b^l$ instead of $2b^k$\n2. Equation (5) and (6) should have inner products since $\\phi$ aren't scalars.\n\n[1] Klivans, Adam, and Raghu Meka. \"Learning graphical models using multiplicative weights.\" In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 343-354. IEEE, 2017.\n\n[2] Vuffray, Marc, Sidhant Misra, Andrey Lokhov, and Michael Chertkov. \"Interaction screening: Efficient and sample-optimal learning of Ising models.\" Advances in Neural Information Processing Systems 29 (2016): 2595-2603.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors could add more discussion about the practicality of their algorithm and assumptions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "UOqLXmrs4CX", "reviewer": "Reviewer_VbcL", "summary": "In this paper, the authors look at the general problem of learning an exponential family of distributions from samples. They propose a new estimator which is computationally tractable. They show that the usual MLE estimator for this problem is not tractable. Finally, they show that their estimator can be seen as the $\\Theta$ minimizing the KL divergence from the uniform distribution to the MLE estimator corresponding to the difference $\\Theta*-\\Theta$, where $\\Theta*$ is the true parameter value. They show that their estimator is consistent and asymptotically normal. Unlike the MLE estimator, their estimator is not asymptotically efficient. Designing an estimator with both computational and asymptotic efficiency is left as an open problem. They also show finite sample bounds for their estimator, making certain technical assumptions that make things work. The finite bounds rely on strong convexity so that the gradient descent algorithm gets close to the true parameters.", "questions": "", "limitations": "", "rating": 7, "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 recent work by Dagan et al [STOC 21] for ising models, has a similar story, where the authors use a pseudo-likelihood as opposed to the MLE for reasons of computational efficiency, and show finite sample bounds using strong convexity. I think this paper is highly relevant to the current work and worth citing. \n\nI think an empirical study would have made the paper much stronger. I think this is a good paper and vote for 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": "10"}, "extra_text": {}}, {"review_id": "I1BHvPsg63U", "reviewer": "Reviewer_xzAW", "summary": "The authors consider the problem of learning exponential families with truncated support under low rank  ($O(\\log n)$ rank) assumptions on the parameters. They develop a loss function following related results on structured learning. They utilize a projected gradient descent algorithm to optimize this loss function in polynomial time. They establish sample complexity for parameter recovery by optimizing this loss function.", "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": "Overall I found the paper theoretically interesting and easy to read.\n\nThe authors develop a seemingly practical algorithm under reasonable assumptions for learning exponential families. The authors clearly explain their algorithm and results and how they compare theoretically to related works. Additionally they explain the intuition of the approach well in Theorem 4.1 and its proof.\n\nThe authors extent what I believe is being called the interactive screening objective. The authors cite [51] as inspiration for the loss function, however I believe the initial work on this loss function began in Vuffrey et al., \"Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models\", NeurIPS 2016, which is not cited.\n\nI believe that it is possible to perform experiments for the method proposed. These experiments can be used to show how practical the method is and how it compares to related approaches.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning the natural parameters of a k-parameter (minimal) exponential family, given i.i.d. samples from the underlying distribution. The main result is a computationally and statistically efficient (polynomial in k/eps) 
learning algorithm that outputs an estimate of the parameters within error eps under some additional assumptions. Instead of directly analyzing the log-likelihood of the minimal exponential family (which is computationally hard in general), this work uses projected gradient descent applied to a new loss function. A  caveat pointed out by the reviewers (and acknowledged by the authors) is that computing the gradient of the objective is not necessarily in polynomial-time, unless additional assumptions are made on the distribution. Efficient computability might be true for specific cases, but it is not true in the full generality stated in the paper. While the reviewers leaned towards accepting the paper, they believe that this point needs to be addressed in the final version.
Decision: Accept (Poster)