Research map / Learning theory and algorithms / Prediction and decision losses
Estimating the Permanent by Nesting Importance Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes nesting importance sampling (NIS), a sequential importance sampler that draws proportionally to nesting upper bounds, giving bounded importance weights and accuracy guarantees for permanent estimation.
Problem
Estimating the permanent of nonnegative matrices (#P-hard) with (epsilon, delta) accuracy guarantees; SIS is empirically fast but lacks variance bounds and stopping rules, while rejection sampling has guarantees but is slower.
Approach
Sample subproblems in SIS proportionally to a nesting upper bound on permanents, so importance weights are bounded by the upper bound U(Omega); this enables optimal stopping rules for [0,1] variables and yields provably fewer samples than self-reducible rejection sampling, especially at high accuracy.
Key results
- DEEPNIS obtains up to two orders-of-magnitude speedups over the state-of-the-art rejection sampler DEEPAR for computing (epsilon, delta)-approximations of permanents (delta=0.05).
- Speedup ratio grows as epsilon decreases; e.g., on cage5 the ratio is 36 at epsilon=0.02 and 115 at epsilon=0.005.
- Relative error exceeded epsilon in only 2.2% of runs on real-world matrices, below delta=0.05.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use nesting importance sampling instead of self-reducible rejection sampling with the same deep bound | Permanent estimation (DEEPNIS vs DEEPAR) · Real-world and synthetic matrices | running time: up to two orders-of-magnitude speedups | Helped |
| Decrease ϵ | DEEPNIS and DEEPAR · Permanent estimation | running time ratio (DEEPAR to DEEPNIS): the ratio increases as ϵ decreases | Helped |
| Use the naive nesting bound instead of the depth-16 extended Huber bound (ablation) | Nesting importance sampling for the permanent · Permanent estimation | convergence | Helped |
| Use the naive nesting bound for accuracy-guaranteed estimation (ablation) | Nesting importance sampling for the permanent · Permanent estimation | efficiency | Hurt |
Surprising findings
- The naive row-sum nesting bound SIS appears to converge rapidly in practice, but its bound is too loose to give provable guarantees.
Limitations
- Loses the ability to draw exact samples, unlike rejection sampling.
- Naive nesting bound has large critical ratio so no guarantees; tighter analysis needed.
- Running time depends on tightness of nesting bound; experiments limited to permanent problem.
Experimental setup
Datasets: ENZYMES graph adjacency matrices (Rossi & Ahmed 2015) synthetic Uniform, Block Diagonal, Bernoulli matrices Staircase cage5 bcspwr01 GD95-c CAG-mat72
Benchmarks: permanent approximation running time on real-world and synthetic matrices
Metrics: average running time speedup ratio relative error (epsilon, delta)-approximation
Baselines: DEEPAR (self-reducible rejection sampling with deep extended Huber bound) naive nesting bound SIS Godsil-Gutman estimators
Builds on: self-reducible rejection sampling (Huber 2006) extended Huber bound (Harviainen & Koivisto 2023) deep bounds (Harviainen et al. 2021) Dagum et al. 2000 stopping rule Huber & Jones 2019 stopping rule Chen & Liu 2007 SIS
Closest papers by meaning
- A Faster Practical Approximation Scheme for the Permanent (AAAI 2023 · similarity 0.91)
- Approximating the Permanent with Deep Rejection Sampling (NeurIPS 2021 · similarity 0.87)
- Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond (ICLR 2026 · similarity 0.86)
- Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond (NeurIPS 2023 · similarity 0.86)
- Differentiable Annealed Importance Sampling Minimizes The Jensen-Shannon Divergence Between Initial and Target Distribution (ICML 2024 · similarity 0.83)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.