Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary:    In this paper, the authors consider the problem of estimating the
  natural parameters of an exponential family with bounded values from samples.
  With bounded values we refer to the fact that both the norm of the sufficient
  statistics and the norm of the parameters are bounded.

  Their main result is an efficient estimation algorithm with sample
  complexity that is roughly equal to d^2/a^4 where d is the number of
  parameters of the exponential family and a is the estimation error.


main_review:   Strengths
  ====================

  - The problem of learning exponential families is very relevant and has a
  wide range of applications in many scientific areas.

  - The proposed solution is elegant and can be applied to real world scenarios
  where a theoretical guarantee is important.

  - The authors do not only provide finite sample results but also asymptotic normality and asymptotic efficiency.


  Weaknesses - Comments
  ========================

  1. The main drawback of the current finite sample result is that it seems
  suboptimal. In particular, in many cases, e.g., Gaussian distributions,
  exponential distributions, linear regression, Poisson distributions, etc., the
  sample complexity for parameter estimation is of order d/a^2 instead of
  d^2/a^4. Is their an example of an exponential family where d^2/a^4 are
  necessary?

  2. Example applications of Theorem 4.3 are missing. What is the result if we
  apply this theorem to bounded value exponential families like Ising models or
  Mallows distributions or truncated Gaussian distributions. For the latter,
  how are the results compared to the recent work of [*].

  3. There is one way to compute the maximum likelihood estimation via sampling.
  In particular, it is not hard to see that if we can sample any given member
  of the exponential family then we can compute an unbiased estimation of the
  gradient of the log-likelihood function. Using this unbiased gradient we can
  run the Stochastic Gradient Descent algorithm which will converge because the
  log-likelihood function is convex. One particular property that is important
  for this is Assumption 4.1 which states that the log-likelihood function is
  not only convex but also strongly convex. Since Assumption 4.1 is necessary
  for the main result of this paper it is important that the lower bounds for
  computing MLE holds even under the Assumption 4.1. Is this true based on the
  known lower bounds?

  4. In a lot of places in the paper the use of the expectation operator is not
  very clear. For example, in Assumption 4.1 it is not clear what is the
  expectation over. My guess is that the expectation is over x ~ f_x(\Theta)
  and the assumption should hold for all \Theta \in \Lambda.

  5. The result cannot be applied to many natural exponential families, e.g.,
  exponential families with unbounded support and sufficient statistics that
  are polynomial functions.

  [*] https://arxiv.org/abs/1809.03986


  Summary of Recommendation
  ======================================
  The results provided in this paper seem to be important towards a better
  understanding of the important problem estimating the parameters of
  exponential families from samples. The solution provided is computationally
  efficient and elegant and for this reason I recommend acceptance.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Quality: The submission seems technically sound. The claims are well supported theoretically. No experimental study is given in the paper.

Clarity: The paper is clearly written in general. Appendix is very helpful because it provides detailed proofs of the theoretical results given in the paper.

Significance: 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.

However 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.
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.

I do not find any potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: The things that I like about the paper.
1) The problem considered here is fundamental and the results presented are quite interesting. 
2) The authors provide the first efficient estimator with nice statistical guarantees. In particular, their estimator achieves polynomial sample complexity.
3) The authors do a good job of discussing the limitation of their work.
4) The paper is well structured and does a clear presentation of the results.

Few concerns/suggestions:
1) 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.
2) 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. 
3) The proposed estimator doesn't achieve asymptotic efficiency and they pose this as an open problem. 
4) 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.
5) 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.  

I would be happy if authors could handle a subset of these suggestions/concerns.
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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 
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. 

======

Elaborations on the review comments: 
- 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. 
- 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? 
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_title: null

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)