論文の概要: On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions

• arxiv url: http://arxiv.org/abs/2402.16442v2
• Date: Wed, 12 Mar 2025 13:02:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-13 15:37:47.564214
• Title: On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions
• Title（参考訳）: ペアワイズ部分モジュラ関数を用いた分散大規模タンメモリサブセット選択について
• Authors: Maximilian Böther, Abraham Sebastian, Pranjal Awasthi, Ana Klimovic, Srikumar Ramalingam,
• Abstract要約: 証明可能な近似保証付き分散バウンディングアルゴリズムを提案する。 CIFAR-100 と ImageNet の高品質なサブセットは,集中型手法と比較して,品質が損なわれるか,あるいは損なわれない。
• 参考スコア（独自算出の注目度）: 31.334053253182795
• License:
• Abstract: Modern datasets span billions of samples, making training on all available data infeasible. Selecting a high quality subset helps in reducing training costs and enhancing model quality. Submodularity, a discrete analogue of convexity, is commonly used for solving such subset selection problems. However, existing algorithms for optimizing submodular functions are sequential, and the prior distributed methods require at least one central machine to fit the target subset in DRAM. At billion datapoint scale, even the subset may not fit a single machine, and the sequential algorithms are prohibitively slow. In this paper, we relax the requirement of having a central machine for the target subset by proposing a novel distributed bounding algorithm with provable approximation guarantees. The algorithm iteratively bounds the minimum and maximum utility values to select high quality points and discard the unimportant ones. When bounding does not find the complete subset, we use a multi-round, partition-based distributed greedy algorithm to identify the remaining subset. We discuss how to implement these algorithms in a distributed data processing framework and empirically analyze different configurations. We find high quality subsets on CIFAR-100 and ImageNet with marginal or no loss in quality compared to centralized methods, and scale to a dataset with 13 billion points.
• Abstract（参考訳）: 現代のデータセットは数十億のサンプルにまたがっており、利用可能なすべてのデータをトレーニングすることは不可能である。 高品質なサブセットの選択は、トレーニングコストの削減とモデル品質の向上に役立つ。 凸性の離散的な類似である部分モジュラリティは、そのような部分集合選択問題を解くために一般的に用いられる。 しかしながら、サブモジュール関数を最適化するための既存のアルゴリズムは逐次的であり、以前の分散手法ではDRAMのターゲットサブセットに適合するために少なくとも1つの中央マシンを必要とする。 数十億のデータポイントスケールでは、サブセットでさえ単一のマシンに収まらない可能性があり、シーケンシャルアルゴリズムは違法に遅い。 本稿では,証明可能な近似保証付き分散バウンディングアルゴリズムを提案することにより,対象サブセットの中央マシンを持つ必要を緩和する。 アルゴリズムは最小限と最大限のユーティリティ値を反復的にバインドして高品質のポイントを選択し、重要でないものを捨てる。 バウンディングが完全なサブセットを見つけられなかった場合、残りのサブセットを特定するために、複数ラウンドのパーティションベースの分散グリードアルゴリズムを使用する。 分散データ処理フレームワークでこれらのアルゴリズムをどのように実装するかを議論し、異なる構成を経験的に分析する。 CIFAR-100 と ImageNet の高品質なサブセットは,集中型手法に比べて品質が損なわれ,13億点のデータセットにスケールする。

関連論文リスト

• Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
  サブセット選択は最適化の基本的な問題であり、影響やスパース回帰といった幅広い応用がある。 欲求アルゴリズムや進化進化的POSSを含む従来のアルゴリズムは、ノイズの多い環境で苦労するか、過剰な計算資源を消費する。 本稿では,頑健な評価関数を最大化し,同時にサブセットサイズを最小化する,雑音性サブセット選択(PORE)のためのロバスト評価を用いたパレート最適化に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2025-01-12T14:04:20Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Determinantal consensus clustering [77.34726150561087]
  本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。 DPPは部分集合内の中心点の多様性を好んでいる。 DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
  論文  参考訳（メタデータ） (2021-02-07T23:48:24Z)
• Fast Greedy Subset Selection from Large Candidate Solution Sets in Evolutionary Multi-objective Optimization [11.110675371854988]
  本稿では,超体積,IGD,IGD+インジケータのグリーディ部分選択の効率について論じる。 我々の考えは、超体積インジケータで知られている部分モジュラー特性を用いて、それらの効率を改善することである。
  論文  参考訳（メタデータ） (2021-02-01T16:14:15Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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