論文の概要: Approximate Top-$k$ for Increased Parallelism

• arxiv url: http://arxiv.org/abs/2412.04358v1
• Date: Thu, 05 Dec 2024 17:17:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-06 14:39:56.242358
• Title: Approximate Top-$k$ for Increased Parallelism
• Title（参考訳）: 並列性向上のための近似Top-k$
• Authors: Oscar Key, Luka Ribar, Alberto Cattaneo, Luke Hudlass-Galley, Douglas Orr,
• Abstract要約: そこで本研究では,バケット付き近似式をk$のアルゴリズムで評価する。 上位$が正確であるという要件を緩和することで、バケット付きアルゴリズムは利用可能な並列性を劇的に向上させることができる。 PyTorch用の高速なバケット付きトップ$実装もリリースしています。
• 参考スコア（独自算出の注目度）: 1.2557921586915128
• License:
• Abstract: We present an evaluation of bucketed approximate top-$k$ algorithms. Computing top-$k$ exactly suffers from limited parallelism, because the $k$ largest values must be aggregated along the vector, thus is not well suited to computation on highly-parallel machine learning accelerators. By relaxing the requirement that the top-$k$ is exact, bucketed algorithms can dramatically increase the parallelism available by independently computing many smaller top-$k$ operations. We explore the design choices of this class of algorithms using both theoretical analysis and empirical evaluation on downstream tasks. Our motivating examples are sparsity algorithms for language models, which often use top-$k$ to select the most important parameters or activations. We also release a fast bucketed top-$k$ implementation for PyTorch.
• Abstract（参考訳）: そこで本研究では,バケット付き近似式をk$のアルゴリズムで評価する。 なぜなら、$k$の最大の値はベクトルに沿って集約されなければならないため、高並列機械学習アクセラレーターの計算には適していないからである。 上位k$が正確であるという要件を緩和することにより、バケット付きアルゴリズムは、多数の小さな上位k$演算を独立に計算することで、並列性を劇的に向上させることができる。 本稿では,下流タスクにおける理論的解析と経験的評価の両方を用いて,このアルゴリズムの設計選択について検討する。 私たちのモチベーションの例は、言語モデルのためのスパーシティアルゴリズムであり、しばしば最も重要なパラメータやアクティベーションを選択するために、トップ$k$を使用する。 PyTorch用の高速なバケット付きトップ$実装もリリースしています。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。 以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
  論文  参考訳（メタデータ） (2023-02-20T05:16:18Z)
• Robust Methods for High-Dimensional Linear Learning [0.0]
  統計的に頑健で計算効率の良い線形学習法を高次元バッチ設定で提案する。 バニラスパース、グループスパース、低ランク行列回復など、いくつかのアプリケーションでフレームワークをインスタンス化する。 バニラ $s$-sparsity の場合、重いテールと $eta$-corruption の下で $slog (d)/n$ レートに達することができます。
  論文  参考訳（メタデータ） (2022-08-10T17:00:41Z)
• A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
  最適な輸送を計算するための厳密なアルゴリズムは遅くなる。 我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。 我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
  論文  参考訳（メタデータ） (2022-03-07T21:40:14Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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