Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Computing the matrix permanent is known as a #P-complete problem and no exact polynomial-time algorithm is known. Several works developed a randomized algorithm for approximating the permanent of a non-negative matrix based on recursive acceptance-rejection (AR) sampling and various upper bounds of permanent. This paper adopts a deep AR sampling scheme that skips some recursive steps. Then, the authors additionally propose an efficient way for computing skipped steps based on dynamic programming of permanent. Empirical results demonstrate order-of-magnitude savings of computational time under random synthetic and real-world datasets.
main_review: The main contribution of this work is boosting recursive sampling by skipping intermediate steps. Although the method is simple, the authors additionally propose an efficient way of computing the upper bound at depth d. This is a novel approach that utilizes the key properties of permanent. Furthermore, experimental results show a huge gap of computational savings under real-world datasets. 
Some questions are the following:
- In Theorem 1, it is clear that the running time depends on the depth d, but unclear how the depth affects an approximation quality. It would be great if the approximation quality is provided in terms of the choice of depth.
- The depth can be specified by the user, but the algorithm varies on the choice of the depth. Is it possible to theoretically/empirically predict the optimal value of depth? Simply, does the optimal depth that minimizes the running time of the algorithm provided in Theorem 1?
- In section 5, what is the approximation quality (or accuracy) of each benchmark algorithm?  It would be great to provide accuracy comparison.
- Additionally, it would be much better if the paper is polished more so that it can be much easier to understand the proposed algorithm and related works.

Minor questions:
- In equation (2), does the summation over all permutations \sigma of S drop?
- Is the \gamma (in line 114-115) well-defined for k=0?
- The toy example provided in section 4 seems to be related to an adjacency matrix of Erdos-Renyi graph. If so, the proposed algorithm can estimate the number of perfect matchings of a given graph. Some readers may welcome it if the paper provides a corollary of perfect matching counting algorithm.

limitations_and_societal_impact: Described above
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a randomized method for estimating the permanent positive matrix. It uses a recursive rejection sampling method but with a more fine-grained upper bound and provides an efficient way to compute it. They provide theoretical analysis on expected running time for random matrices, where the bound is superior for certain regimes of p, and provide compelling empirical experiments to show practical improvement over prior methods.
main_review: I think the paper is well-structured, has nice theoretical results with competitive practical performance. It is a good step toward understanding  efficient permanent approximation algorithms. I only have three small concerns regarding the work:

1) I am not sure NeurIPS is the best venue for this work, as it is quite theoretical, and I am unsure about how significant it is a problem of estimating permanent for the general machine learning community.

2) The framework seems to rely heavily on the recursive rejection sampling method in prior work, and the main novelty in idea is the deep bound depending on depth instead of a uniform bound to increase acceptance probability for better efficiency. 

3) Also, the runtime has an infavorable 2^d factors, which doesn't seem very scalable.

I would be happy to increase my score if authors offer compelling arguments against my concerns.
limitations_and_societal_impact: Yes, in sections 4 and 5.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The authors addressed the efficient approximation of permanent of a matrix with nonnegative entries. The proposed scheme is based on the recursive rejection sampling method by Huber 2008, but the upper bound on the permanent is based on the linear combination of the subproblems with the deep recursion tree. The expected running time is both theoretically and experimentally analyzed. 
main_review: I think the research is quite interesting overall. The algorithmic idea (previous rejection sampling-based method with deep bounds), related work, algorithm, results, proof sketch are quite well presented. Both theoretical and numerical performance improvement is quite significant. Due to the importance of the problem of permanent computation, I believe that this result will be very valuable. 

The only comment I can make is that Theorem 2 is not directly compared with the complexity result in [23]. I think it is fair to make an accurate comparison including both improvements and limitations. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper gives a new algorithm to approximate permanents of non-negative matrices. The method builds upon the well-known rejection sampling method by Huber-Law (SODA'08). The algorithm is experimentally shown to perform well, and in particular better than the related result by Kuck et al. (NeurIPS'19). Finally, a mathematical analysis of the performance of the algorithm on a family of random matrices is given, where it is shown to run in polynomial time to yield arbitrarily good precision.
main_review: The paper studies approximating weighted counting problems such as the permanent using an idea based on self-reducible rejection sampling by Huber-Law. This is a well-studied heuristic for approximating permanents. Roughly speaking, in this method we have a certain upper bound on the permanent per(A)<=U(A) and we keep sampling permutations (according to a specially crafted distribution resulting from self-reducibility) until we have seen at least K "yes" samples. Finally the estimate is given by U(M)*K/T, where T is the total number of samples drawn. It is not hard to see that the running time of this method depends on the quality of the upper bound U(M) and what this paper achieves is replacing this bound by a tighter one. The new bound U_d(M) obtained in this paper is a generalization of the Huber-Law bound, based on a kind of d-level deep look-ahead in the tree that is used in the sampling process. The regular Huber-Law bound U(M) is U_1(M).

The presentation of the paper's results is clear and the paper is generally easy to read. The basic idea of self-reducible rejection sampling is explained with enough details before moving on with the presentation of this paper's contribution: deep rejection sampling.

The first result in the paper (Theorem 1) asserts that in time roughly O(2^d*dn + U_d(A)/per(A)*poly(n, 1/eps)) one can compute an eps-approximation of the permanent per(A) of an nxn matrix with >=0 entries (with logarithmic dependency on the error probability). In general, it is not simple to give reasonable bounds on U_d(A), hence the authors provide an analysis of U_d(A) for random Bernoulli matrices. They show (Theorem 2) that in this case the algorithm runs in polynomial time, and beats known results in the regime where p (the probability of an entry being 1) is <1/5.

Most of the proofs are delegated to the supplementary materials, yet the provided overviews are valuable and allow to shape some intuitions.

Authors provide an empirical evaluation of their results comparing their algorithm with the one by Kuck et al. When presenting the results it would be much cleaner if both methods were plotted on a single diagram instead of having separate diagrams per method -- this way it is not clear how do they compare (which seems to be the main point of this experiment).

When assessing the paper I had the following doubt: shall I consider it as A) a theoretical paper with the main contribution being the mathematical theorems, or B) an applications-focused paper, giving a practical heuristic for counting problems. When treated as A) I have concerns that the contribution of this paper over previous work (Huber-Law and then Kuck et al.) is not that significant and hence I would not place it among top papers. When treated as B), I felt that this paper does not provide enough discussion on *concrete* possible applications in learning and what the concrete impact of this new method could be.
limitations_and_societal_impact: -
review_title: null

Meta-review: This paper gives a generalization of an algorithm of Huber and Law for approximating the permanent of a non-negative matrix (an important and basic counting/sampling problem). The idea is to combine the rejection sampling method of Huber and Law with a deep (parameterized by some depth parameter d) "look-ahead" that uses a linear combination of sub-problems at depths <= d in the recursion tree as an upper bound on the permanent. This theoretically strengthens the guarantees of Huber and Law (and beats them on the "toy" example of random Bernoulli matrices. In experiments it beats the guarantees of a recent work of Kuck et. al. in approximating the permanent. 

There were concerns that the theoretical contributions of the paper are not strong enough on top of prior work. However, the relatively clean and simple look-ahead method (deep AR) developed in this paper does give a significant advantage in terms of practical speed-ups. The deep AR heuristic, as a result, appears an appealing avenue to explore further. We recommend acceptance. 
Decision: Accept (Poster)