Differentiable Knapsack and Top- k k Operators via Dynamic Programming

Germain Vivier-Ardisson, Michaël E. Sander, Axel Parmentier, Mathieu Blondel · 2026

Read Differentiable Knapsack and Top- k k Operators via Dynamic Programming by Germain Vivier-Ardisson, Michaël E. Sander, Axel Parmentier, Mathieu Blondel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21775.txt.

Description

Germain Vivier-Ardisson, Michaël Sander, Axel Parmentier, and Mathieu Blondel make two classic selection tools usable inside neural networks. The knapsack operator and the top-k operator pick discrete subsets of variables, which is useful for sparse decisions. But both are piecewise constant, so their gradients are zero almost everywhere.

Without gradients, standard training cannot learn through them. The team's 2026 preprint casts both operators as dynamic programs and derives smooth, differentiable versions by softening the underlying recursions. That gives networks a principled way to learn selections end to end. Applications range from selecting features and items to ranking, wherever a model must choose a few winners and still be trainable.

Catalog record

CREATORGermain Vivier-Ardisson, Michaël E. Sander, Axel Parmentier, Mathieu Blondel
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE160 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21775

Browse the full library · About the Tower of Babel