Differentiable Knapsack and Top-k Operators via Dynamic Programming

• URL: http://arxiv.org/abs/2601.21775v1
• Date: Thu, 29 Jan 2026 14:25:35 GMT
• Title: Differentiable Knapsack and Top-k Operators via Dynamic Programming
• Authors: Germain Vivier-Ardisson, Michaël E. Sander, Axel Parmentier, Mathieu Blondel,
• Abstract summary: Knapsack and Top-k operators are useful for selecting discrete subsets of variables.<n>We propose a unified framework casting these operators as dynamic programs, and derive differentiable relaxations.<n>On the algorithmic side, we develop efficient algorithms supporting both deterministic and forward passes.<n>On the theoretical side, we prove that Shannon entropy is the unique regularization choice yielding permutation-equivariant operators.
• Score: 10.762219154434709
• License: http://creativecommons.org/licenses/by/4.0/
• 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 entropy is the unique regularization choice yielding permutation-equivariant operators, and characterize regularizers inducing sparse selections. Finally, on the experimental side, we demonstrate our framework on a decision-focused learning benchmark, a constrained dynamic assortment RL problem, and an extension of discrete VAEs.

Related papers

• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  randomized quantum algorithms have been proposed in the context of quantum simulation and quantum linear algebra.<n>We provide explicit bounds on all relevant parameters that control the total error for a randomized quantum linear systems solver.<n>Our work serves as a bridge between theoretical algorithmic proposals and efficient hardware implementations.
  arXiv  Detail & Related papers  (2025-10-15T17:12:55Z)
• Recursive Reward Aggregation [60.51668865089082]
  We propose an alternative approach for flexible behavior alignment that eliminates the need to modify the reward function.<n>By introducing an algebraic perspective on Markov decision processes (MDPs), we show that the Bellman equations naturally emerge from the generation and aggregation of rewards.<n>Our approach applies to both deterministic and deterministic settings and seamlessly integrates with value-based and actor-critic algorithms.
  arXiv  Detail & Related papers  (2025-07-11T12:37:20Z)
• Efficient Differentiable Approximation of Generalized Low-rank Regularization [64.73416824444328]
  Low-rank regularization (LRR) has been widely applied in various machine learning tasks.<n>In this paper, we propose an efficient differentiable approximation of LRR.
  arXiv  Detail & Related papers  (2025-05-21T11:49:17Z)
• Parseval Convolution Operators and Neural Networks [16.78532039510369]
  We first identify the Parseval convolution operators as the class of energy-preserving filterbanks. We then present a constructive approach for the design/specification of such filterbanks via the chaining of elementary Parseval modules. We demonstrate the usage of those tools with the design of a CNN-based algorithm for the iterative reconstruction of biomedical images.
  arXiv  Detail & Related papers  (2024-08-19T13:31:16Z)
• Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks [1.3654846342364308]
  We show that a first-scalable optimisation algorithm can efficiently use the exact inverse Hessian with absolute-value eigenvalues. A t-run of this series provides a new optimisation which is comparable to other first- and second-order optimisation methods.
  arXiv  Detail & Related papers  (2023-10-23T13:11:30Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Latency considerations for stochastic optimizers in variational quantum algorithms [0.02294014185517203]
  Variational quantum algorithms, which have risen to prominence in the noisy intermediate noisy quantum-scale setting, require the implementation of hardware. To date, most research has employed algorithms based on the gradient iteration as the classical iteration. In this work we propose instead using optimization algorithms that yield processes emulating the dynamics of classical deterministic algorithms.
  arXiv  Detail & Related papers  (2022-01-31T18:51:24Z)
• A research framework for writing differentiable PDE discretizations in JAX [3.4389358108344257]
  Differentiable simulators are an emerging concept with applications in several fields, from reinforcement learning to optimal control. We propose a library of differentiable operators and discretizations, by representing operators as mappings between families of continuous functions, parametrized by finite vectors. We demonstrate the approach on an acoustic optimization problem, where the Helmholtz equation is discretized using Fourier spectral methods, and differentiability is demonstrated using gradient descent to optimize the speed of sound of an acoustic lens.
  arXiv  Detail & Related papers  (2021-11-09T15:58:44Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks [0.0]
  We present a new class of Langevin based algorithms, which overcomes many of the known shortcomings of popular adaptive vanishing algorithms. In particular, we provide a nonasymptotic analysis and full theoretical guarantees for the convergence properties of an algorithm of this novel class, which we named TH$varepsilon$O POULA (or, simply, TheoPouLa)
  arXiv  Detail & Related papers  (2021-05-28T15:58:48Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.