Abstract
Subset selection—the task of identifying a subset of $k$ items from a larger collection—is a fundamental discrete operation in machine learning. However, its non-differentiable nature poses challenges for end-to-end training via backpropagation. This paper provides a unified mathematical perspective on the two primary relaxation techniques: regularization and perturbation. We demonstrate that these approaches are dual to each other and evaluate their performance on complex tasks such as feature selection and environmental monitoring.
Introduction
In many machine learning domains, such as information retrieval and feature selection, we must select a discrete subset of data. For instance, we might want to identify the most informative pixels in an image or the best features for a predictive model. The standard "top-$k$" operator is a step function with zero gradients almost everywhere, making it incompatible with gradient-based optimization.
To bridge this gap, researchers employ relaxations to make the selection process differentiable. These typically fall into two categories:
- Regularization: Adding a smooth penalty (e.g., entropy) to the selection objective.
- Perturbation: Injecting noise into the scores and computing the expected selection.
This work establishes that these two paradigms are deeply connected, offering a unified framework for differentiable subset selection.
Methodology: A Unified Framework
The core contribution of this research is the proof that regularization and perturbation are mathematically equivalent under specific conditions. Specifically, the regularizer in the first approach is shown to be the Fenchel conjugate of the expected maximum in the second.
For example, using Gumbel noise in a perturbation scheme is equivalent to applying Negative Shannon Entropy as a regularizer. Similarly, Logistic noise corresponds to Binary Entropy. This unification allows practitioners to choose the method that best fits their computational constraints:
- Regularized Approach: Uses the Implicit Function Theorem to compute exact gradients through optimality conditions (KKT conditions).
- Perturbed Approach: Employs Monte Carlo estimation to approximate gradients by sampling noise.
Key Insights: The Role of Temperature
A critical component of both methods is the "temperature" parameter ($\tau$). This parameter controls the smoothness of the relaxation. As $\tau \to 0$, the selection becomes "hard" and discrete; as $\tau \to \infty$, it becomes uniform, picking everything equally.
Finding an appropriate annealing schedule for $\tau$ is essential for balancing the differentiability needed during training with the discreteness required at inference.
Experiments and Results
The framework was evaluated on the Maximum Entropy Sampling Problem (MESP) using environmental datasets and on feature selection using the MNIST dataset.
Feature Selection on MNIST
The authors introduced Perturbed and Regularized Autoencoders (PAE/RAE) to identify the most critical pixels for digit reconstruction. The results showed that these unified methods outperformed existing benchmarks like the Concrete Autoencoder (CAE).
In classification tasks using selected features, the PAE achieved an accuracy of 0.535, surpassing the CAE's 0.523. Visually, the selectors learned to prioritize pixels that define the unique geometry of each digit, whereas older methods often selected redundant or noisy pixels.
Conclusion
This work provides a theoretical bridge between regularization and perturbation in differentiable subset selection. By showing their equivalence, it simplifies the landscape of differentiable relaxations. While these methods are powerful, they remain approximations for NP-hard problems. Future work may extend this unified perspective to more complex discrete structures like rankings, matchings, or graph topologies.
Summary updated