One Proposal for Every Margin: Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices

One Proposal for Every Margin. Zero-Shot Amortized Sequential Importance Sampling for Binary Matrices. By Ruishuo Chen and five others, from Tsinghua University. Published on the twenty-eighth of September. No code repository is linked to it.

In ecology, in psychometrics, and in the study of social and financial networks, binary matrices are often analysed conditional on their observed row and column sums. Fixing those margins restricts the problem to a finite space: every zero-one matrix with the same margins. Two basic questions follow. How many such matrices are there, and how can one be drawn uniformly at random? Sequential importance sampling, SIS, answers both, producing independent weighted samples and an unbiased estimate of the count. Its efficiency, though, hinges on the proposal distribution. Existing proposals are designed analytically, and how accurate they are can vary substantially from one set of margins to another. A proposal that suits one set of margins can serve another poorly, which is why the comparison later in the paper picks the best hand-designed option separately for every margin.

The paper's central observation is an exact equivalence. The ideal SIS proposal, the one under which every weight equals the count and the variance vanishes, is exactly the policy of a generative flow network, a GFlowNet, whose reward is one on every matrix with the given margins. Designing a proposal therefore becomes a learning problem. Instead of a person deriving a good proposal by analysis, a network can be trained toward the ideal one, and the closer it gets, the closer every importance weight comes to the true count.

MarginFlow is the framework built on that. It amortizes the learned proposal across margins by exploiting their self-similarity. Every partially filled matrix is itself an instance of the same problem, with reduced margins. So one set transformer, reading the margins that remain, can serve every margin rather than being retrained for each. Filling in the matrix piece by piece keeps producing smaller versions of the same question, and the same network answers each of them, which is what lets it handle margins it never saw in training.

MarginFlow is trained on a pool of one thousand nine hundred and four margins, then evaluated zero-shot on one thousand one hundred and ninety held-out margins, synthetic and real. Their sizes run from three by three up to eight hundred and seventy by six. On all but three of those held-out margins, it matches or beats the best of thirty-one analytically designed configurations, even though that best is chosen after the fact for each margin. Its median effective sample fraction is ninety-nine point eight percent.

The hard cases sharpen the picture. There are fifty-six margins where that post hoc best loses more than one nat of effective sample size. MarginFlow wins every one of them, and lifts the median effective sample fraction there from ten point three percent to ninety-four point one percent.

The comparison was built to favour the old approach: a fresh pick of the best hand-designed proposal for every margin, made with hindsight. Against that, a single learned proposal that never saw these margins came out level or ahead almost everywhere, and far ahead exactly where the hand-built options struggled.