論文の概要: Fast LapSum: Exact Differentiable Top-k at Million Scale
- arxiv url: http://arxiv.org/abs/2608.06912v1
- Date: Fri, 07 Aug 2026 07:44:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-10 16:21:25.400928
- Title: Fast LapSum: Exact Differentiable Top-k at Million Scale
- Title（参考訳）: Fast LapSum: 数百万のスケールで差別化可能なトップk
- Abstract要約: Fast LapSumは、GPUソルバがソート後に線形時間で実行される、正確な予算のソフトトップ$k$プリミティブである。
我々はFast LapSumを、トレーニングループ内で数百万の座標を操作する要求のある2つのアプリケーション上でデモした。
- 参考スコア（独自算出の注目度）: 10.106073328854459
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The top-$k$ operation is a fundamental building block of modern sparse computation, enabling token routing, expert activation, memory selection, and attention pruning. Yet standard hard top-$k$ blocks gradients, while existing continuous (soft) relaxations remain too costly for large-scale models. We introduce Fast LapSum, an exact-budget soft top-$k$ primitive whose GPU solver runs in linear time after sorting. Unlike prior linear-time methods such as DFTopK, which relax the normalization constraint, Fast LapSum is, to our knowledge, the first method to preserve an exact selection mass of $k$ while remaining fully differentiable end-to-end. Our solver combines a linear-time threshold computation with an analytical vector--Jacobian product, and for extreme scales employs probabilistic bracketing to sort only the uncertain middle band of kernel-noised scores. The resulting overhead is almost negligible: the solver processes $10^6$, $10^7$, and $10^8$ scores in $0.41$, $1.15$, and $5.23$\,ms, respectively. This makes exact soft top-$k$ practical for sparse routing, retrieval, and large-scale optimization. We demonstrate Fast LapSum on two demanding applications operating over millions of coordinates inside the training loop: generating megapixel sparse adversarial examples with an exact soft budget of ${\sim}0.02\%$ of an image's pixels, achieving an order-of-magnitude speedup over state-of-the-art methods, and training a fully differentiable sparse image coder from scratch.
- Abstract（参考訳）: トップ$の操作は、トークンルーティング、エキスパートアクティベーション、メモリ選択、アテンションプルーニングを可能にする、現代的なスパース計算の基本的なビルディングブロックである。
しかし、標準的なハードトップ$kのブロック勾配は、既存の(ソフトな)緩和は、大規模モデルではコストがかかりすぎている。
我々はFast LapSumを紹介した。これは、GPUソルバがソート後に線形時間で実行される、正確な予算のソフトトップ-$k$プリミティブである。
正規化制約を緩和するDFTopKのような従来の線形時間法とは異なり、Fast LapSumは我々の知識では、完全微分可能なエンドツーエンドを維持しながら、正確な選択質量を$k$で保存する最初の方法である。
我々の解法は線形時間しきい値計算と解析ベクトル-ヤコビアン積を結合し、極端スケールでは確率的ブラケットを用いてカーネルノイズの未確定な中間帯域のみをソートする。
10^6$, 10^7$, 10^8$をそれぞれ0.41$, $1.15$, 5.23$\,msで処理する。
これにより、スパースルーティング、検索、大規模最適化のためのソフトなトップ$kが実用的になる。
我々はFast LapSumを、トレーニングループ内で数百万の座標を操作する要求のある2つのアプリケーションでデモする:${\sim}0.02\%の正確なソフトな予算でメガピクセルスパースを逆向きに生成し、最先端の手法よりも高次の精度を実現し、完全に微分可能なスパースイメージコーダをスクラッチからトレーニングする。
関連論文リスト
- Accelerated Relax-and-Round for Concave Coverage Problems [7.984421247931201]
コンケーブ被覆問題に対する高速化された緩和・円周アルゴリズムを提案する。
我々のアルゴリズムは、最先端のLPソルバを使用するアプローチよりも優れています。
論文 参考訳（メタデータ） (2026-05-07T20:00:40Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
有界ノルムを持つ埋め込みベクトルに対して$rm SoftMax(XYT)$の正規化定数を計算する線形時間近似を提案する。
本稿では,提案手法が競合手法よりも高い精度あるいは同等の精度を達成できるような事前学習した埋め込みデータセットについて述べる。
提案アルゴリズムは解釈可能で,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Sparse Regression at Scale: Branch-and-Bound rooted in First-Order
Optimization [6.037383467521294]
我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。
私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。
実装をツールキットL0BnBでオープンソースにしています。
論文 参考訳（メタデータ） (2020-04-13T18:45:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。