Scalable Subset Sampling with Neural Conditional Poisson Networks

Adeel Pervez, Phillip Lippe, Efstratios GavvesICLR 2023 · OpenReview

Overview

Subset sampling—the process of picking $k$ items out of a universe of $n$ elements—is a fundamental operation in machine learning. However, it is notoriously difficult to integrate into differentiable neural networks. This paper introduces Neural Conditional Poisson Subset Sampling (NCPSS), a scalable, differentiable method that is faster and more memory-efficient than existing "Top-k" approximations, while uniquely allowing the subset size $k$ to be learned dynamically during training.

The Challenge of Differentiable Subset Sampling

In many machine learning tasks, models must select a discrete subset of data. For example, in "Learning to Explain" tasks, a model might need to pick the 10 most important words in a sentence to justify a classification. Because the operation of picking the "Top-k" elements is discrete and non-differentiable, standard backpropagation cannot pass gradients through it to train the rest of the network.

Existing solutions typically rely on "order sampling," which involves assigning a random rank to every element and picking the largest $k$. While differentiable relaxations of this process exist, they often involve internal loops or sorting operations that scale poorly as $k$ or the total universe $n$ grows. When attempting to select thousands of pixels from a high-resolution image, current methods often run out of GPU memory or become prohibitively slow.

Proposed Method: Neural Conditional Poisson Sampling

The authors pivot away from order-based sampling toward Poisson Sampling, introducing several key innovations to make it viable for deep learning.

1. Poisson Sampling

Instead of ranking elements globally, each element is treated as an independent Bernoulli trial (a coin flip) with a probability $p_i$. On average, this yields a subset of size $k$, but the actual size can vary wildly on a single pass.

2. The Iterative Fix

To reduce this variance, the authors propose an iterative procedure. If a sample has fewer than $k$ elements, the model performs another pass to add more. If it has too many, it performs a pass to remove some. By doing this for a fixed, small number of iterations (usually 5–8), the subset size converges very close to $k$ with exceptionally low variance.

Effect of iterative Poisson sampling on subset size variance.

3. Differentiability via Straight-Through Estimator

To make this iterative sampling work within a neural network, the authors utilize the Straight-Through (ST) estimator. This technique allows gradients to bypass the discrete sampling step during the backward pass, enabling end-to-end training.

Forward and backward passes using the Straight-Through estimator.

4. Differentiable $k$

Because $k$ acts as a simple scaling factor for the probabilities in the NCPSS framework, the model can actually learn the optimal subset size $k$ for a given task via backpropagation, rather than treating it as a rigid, fixed hyperparameter.

Key Insights and Scalability

  • Independence Scales: By treating element selection as independent trials rather than a global ranking problem, the computational complexity becomes independent of the subset size $k$. This is the primary driver of the method's scalability.
  • Expectation vs. Exactness: The authors realized that for most deep learning applications, sampling exactly $k$ elements every single time is unnecessary. Sampling $k$ elements in expectation with low variance is sufficient and computationally much cheaper.
  • Memory Efficiency: Unlike Gumbel-based Top-k methods that require storing large intermediate matrices (often leading to Out-Of-Memory errors on high-res images), NCPSS maintains a very light memory footprint.
  • The Power of a Learned $k$: Allowing $k$ to be differentiable means the model can dynamically adjust its subset size based on the input. For instance, it can decide that a short sentence only needs 5 words to be explained, while a complex one needs 20.

Experimental Results

The authors evaluated NCPSS across several domains, including text classification (IMDB, 20Newsgroups), image classification (CIFAR-10, STL-10), high-resolution subsampling (CelebA-HQ), and stochastic k-NN tasks (MNIST, CIFAR-10).

  • Accuracy: On the 20Newsgroups dataset, NCPSS outperformed the previous state-of-the-art (RelaxSubSample) by 7–10% in post-hoc accuracy.
  • Speed: NCPSS trained nearly twice as fast as competitors on CIFAR-10 tasks.
  • Scalability: NCPSS successfully handled 512x512 image subsampling. Previous methods were intractable for this task, requiring over 27GB of VRAM just to store the sampling matrix for a batch of 10 images.
  • Variance Reduction: With just 5–8 iterations, the variance in subset size dropped exponentially, consistently hitting the target $k$ within a tiny margin (e.g., $\pm 4$ elements for $k=300, n=3000$).

Limitations and Future Work

While highly scalable, the authors note that for very small subset sizes (where $k$ is tiny), traditional order-based sampling might still be preferable as the complexity gap narrows. Additionally, while the Straight-Through gradient works well empirically, the paper lacks a formal theoretical guarantee for its convergence in this specific iterative Poisson context. Finally, if an application strictly requires exactly $k$ elements (no more, no less), the "in expectation" nature of NCPSS might require a final non-differentiable correction step.

Summary updated

Abstract

A number of problems in learning can be formulated in terms of the basic primitive of sampling $k$ elements out of a universe of $n$ elements. This subset sampling operation cannot directly be included in differentiable models and approximations are essential. Current approaches take an \emph{order sampling} approach to sampling subsets and depend on differentiable approximations of the Top-$k$ operator for selecting the largest $k$ elements from a set. We present a simple alternative method for sampling subsets based on \emph{conditional Poisson sampling}. Unlike order sampling approaches, the parallel complexity of the proposed method is independent of the subset size which makes the method scalable to large subset sizes. We adapt the procedure to make it efficient and amenable to discrete gradient approximations for use in differentiable models. Furthermore, the method also allows the subset size parameter $k$ to be differentiable. We demonstrate our approach on model explanation, image sub-sampling and stochastic $k$-nearest neighbor tasks outperforming existing methods in accuracy, efficiency and scalability.
BibTeX
@inproceedings{pervez2023scalable,
  author = {Adeel Pervez and Phillip Lippe and Efstratios Gavves},
  title = {{Scalable Subset Sampling with Neural Conditional Poisson Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=p8hMBcPtvju},
}
Figure