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.
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.
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