Differentiable Knapsack and Top-k Operators via Dynamic Programming
Organizations: Google DeepMind, Paris, France · CERMICS, ENPC, Institut Polytechnique de Paris, CNRS, Marne-la-Vallée, France
Abstract
Knapsack and Top-k operators are useful for selecting discrete subsets of variables. However, their integration into neural networks is challenging as they are piecewise constant, yielding gradients that are zero almost everywhere. In this paper, we propose a unified framework casting these operators as dynamic programs, and derive differentiable relaxations by smoothing the underlying recursions. On the algorithmic side, we develop efficient parallel algorithms supporting both deterministic and stochastic forward passes, and vector-Jacobian products for the backward pass. On the theoretical side, we prove that Shannon's negative entropy is the unique separable regularization choice that yields permutation-equivariant operators, and characterize regularizers inducing sparse selections. On the experimental side, we demonstrate our framework on a benchmark on learning to predict Knapsack solutions, an extension of discrete VAEs, and a constrained dynamic assortment RL problem.
Figures & tables
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | Test Reconstruction Error | KL Divergence |
| Stochastic Tsallis | ||
| Deterministic Gini | ||
| LapSum | ||
| Stochastic Gini | ||
| Deterministic Tsallis | ||
| FDS |
| Test Reconstruction Error | Fenchel-Young Loss | Average | |
| (Ablated) | |||
| (Ours) | |||
| Shannon ( ) | Gini ( ) | 1.5-Tsallis ( ) | |
Differentiable Optimization
Differentiable optimization makes solvers and constrained decisions trainable with gradients for learning, control, design, and inverse problems.
See all 91 papers