論文の概要: Differentiable Knapsack and Top-k Operators via Dynamic Programming

• arxiv url: http://arxiv.org/abs/2601.21775v1
• Date: Thu, 29 Jan 2026 14:25:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.89075
• Title: Differentiable Knapsack and Top-k Operators via Dynamic Programming
• Title（参考訳）: 動的プログラミングによるKnapsackとTop-K演算子
• Authors: Germain Vivier-Ardisson, Michaël E. Sander, Axel Parmentier, Mathieu Blondel,
• Abstract要約: Knapsack と Top-k 演算子は変数の離散部分集合を選択するのに有用である。 我々はこれらの演算子を動的プログラムとしてキャストする統一的なフレームワークを提案し、微分可能な緩和を導出する。 アルゴリズム面では、決定論的パスとフォワードパスの両方をサポートする効率的なアルゴリズムを開発する。 理論面では、シャノンエントロピーが置換同変作用素をもたらす唯一の正規化選択であることを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: Knapsack と Top-k 演算子は変数の離散部分集合を選択するのに有用である。 しかしながら、ニューラルネットワークへの統合は、断片的に一定であり、ほぼ至るところでゼロな勾配をもたらすため、難しい。 本稿では,これらの演算子を動的プログラムとしてキャストする統一的なフレームワークを提案する。 アルゴリズム面では,決定論的および確率的前方通過と,後方通過に対するベクトル-ヤコビアン積の両方をサポートする効率的な並列アルゴリズムを開発する。 理論面では、シャノンエントロピーが置換同変作用素を生じる唯一の正則化選択であることを示し、スパース選択を誘導する正則化を特徴付ける。 最後に、実験的な側面から、決定にフォーカスした学習ベンチマーク、制約付き動的分解RL問題、離散VAEの拡張に関するフレームワークを実演する。

関連論文リスト

• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  ランダム化量子アルゴリズムは、量子シミュレーションと量子線型代数の文脈で提案されている。 ランダム化量子線形系解法における全誤差を制御する全ての関連するパラメータに明示的な境界を与える。 私たちの研究は、理論的なアルゴリズムの提案と効率的なハードウェア実装の橋渡しとして役立ちます。
  論文  参考訳（メタデータ） (2025-10-15T17:12:55Z)
• Recursive Reward Aggregation [60.51668865089082]
  本稿では,報酬関数の変更を不要としたフレキシブルな行動アライメントのための代替手法を提案する。 マルコフ決定過程(MDP)の代数的視点を導入することにより、ベルマン方程式が報酬の生成と集約から自然に現れることを示す。 我々のアプローチは決定論的および決定論的設定の両方に適用され、価値に基づくアルゴリズムとアクター批判的アルゴリズムとシームレスに統合される。
  論文  参考訳（メタデータ） (2025-07-11T12:37:20Z)
• Efficient Differentiable Approximation of Generalized Low-rank Regularization [64.73416824444328]
  低ランク正規化(LRR)は様々な機械学習タスクに広く応用されている。 本稿では,LRRの効率的な微分可能近似を提案する。
  論文  参考訳（メタデータ） (2025-05-21T11:49:17Z)
• Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks [1.3654846342364308]
  絶対値固有値を持つ正逆 Hessian を,一階乗算可能な最適化アルゴリズムで効率的に利用できることを示す。 この級数のt-runは、他の1階と2階の最適化手法に匹敵する新しい最適化を提供する。
  論文  参考訳（メタデータ） (2023-10-23T13:11:30Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Latency considerations for stochastic optimizers in variational quantum algorithms [0.02294014185517203]
  ノイズの多い中間雑音の量子スケール設定で顕著になった変分量子アルゴリズムは、ハードウェアの実装を必要とする。 これまでのところ、ほとんどの研究では勾配反復を古典的な反復として用いたアルゴリズムが採用されている。 本研究では,古典的決定論的アルゴリズムの力学をエミュレートするプロセスを生成する最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-31T18:51:24Z)
• A research framework for writing differentiable PDE discretizations in JAX [3.4389358108344257]
  微分可能シミュレータは、強化学習から最適制御まで、いくつかの分野で応用される新しい概念である。 連続関数の族間の写像として作用素を表現し、有限ベクトルでパラメタ化することにより、微分可能作用素と離散化のライブラリを提案する。 本稿では、フーリエスペクトル法を用いてヘルムホルツ方程式を離散化し、勾配勾配を用いて微分可能性を示し、音響レンズの音速を最適化する音響最適化問題に対するアプローチを示す。
  論文  参考訳（メタデータ） (2021-11-09T15:58:44Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks [0.0]
  本稿では,Langevinベースのアルゴリズムを新たに導入し,一般的な適応的消滅アルゴリズムの欠点の多くを克服する。 特に、この新しいクラスのアルゴリズムの収束性についての漸近解析と完全な理論的保証を提供し、TH$varepsilon$O POULA(あるいは単にTheoPouLa)と名付けた。
  論文  参考訳（メタデータ） (2021-05-28T15:58:48Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。