Approximating the Permanent with Deep Rejection Sampling
Authors: Juha Harviainen, Antti Röyskö, Mikko Koivisto
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate empirically that deep bounds , with d around 20, are computationally feasible and can yield orders-of-magnitude savings in running time as compared to the basic depth-zero bounds. We report on an empirical performance study of Deep AR for exact sampling of weighted permutations and for approximating the permanent. |
| Researcher Affiliation | Academia | Juha Harviainen University of Helsinki juha.harviainen@helsinki.fi Antti Röyskö ETH Zürich aroeyskoe@ethz.ch Mikko Koivisto University of Helsinki mikko.koivisto@helsinki.fi |
| Pseudocode | Yes | Function ESTIMATE(Ω, u, ϵ, δ) E1 k ψ(ϵ, δ) , t 0, s 0 E2 Repeat t t + 1, s s + SAMPLE(Ω, u) until s = k E2 Return u(Ω) k/t |
| Open Source Code | Yes | We include our C++ code and other materials in a supplement. |
| Open Datasets | Yes | We considered three classes of random matrices: in Uniform the entries are independent and distributed uniformly in [0, 1]; Block Diagonal consists of block diagonal matrices whose diagonal elements are independent 5 5 matrices from Uniform (the last element may be smaller); in Bernoulli(p), the entries are independent taking value 1 with probability p, and 0 otherwise. In Figure 2, with HL-d on the upper row and ADAPART-d on the bottom row, we observe that on Uniform, deep bounds do not pay off and that the Huber Law scheme is an order-of-magnitude faster than Ada Part. On Block Diagonal, deep bounds bring a significant, two-orders-of-magnitude boost and Ada Part is slightly faster than Huber Law; furthermore, DS brings a substantial additional advantage for larger instances (visible as a smaller slope of the log-time plot). Bernoulli(p) again shows the superiority of deep bounds, but also a case where DS is harmful. We also considered (non-random) benchmark instances. Five of these are from the Network Repository [28] (http://networkrepository.com, licensed under CC BY-SA), the same as included by Kuck et al. [23]. |
| Dataset Splits | No | The paper uses random matrices and benchmark instances to evaluate an approximation scheme but does not define training, validation, or test dataset splits for model training or evaluation in the traditional sense. |
| Hardware Specification | No | No specific hardware details (GPU/CPU models, processor types, memory amounts, or detailed computer specifications) used for running experiments were mentioned in the paper. |
| Software Dependencies | No | The paper mentions 'C++ code' but does not specify particular software dependencies with version numbers (e.g., specific compilers, libraries, or solvers with their versions). |
| Experiment Setup | Yes | We estimated the expected running time (ERT) of the schemes for producing a (0.1, 0.05)-approximation of the permanent. Using GBAS [18], this yields a requirement of 388 accepted samples. To save the total computing time of the study, we estimate the ERT based on 65 accepted samples. ... We ran the schemes with depths d {0, 20} and with and without preprocessing of the input matrix. |