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

• arxiv url: http://arxiv.org/abs/2402.16442v1
• Date: Mon, 26 Feb 2024 09:38:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-27 13:55:34.030886
• Title: On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions
• Title（参考訳）: ペアワイズ部分モジュラ関数を用いた分散大規模タンメモリサブセット選択について
• Authors: Maximilian B\"other, Abraham Sebastian, Pranjal Awasthi, Ana Klimovic, Srikumar Ramalingam
• Abstract要約: 凸性の離散的な類似である部分モジュラリティは、一般に部分集合選択問題を解くために用いられる。 本稿では,証明可能な近似保証付き分散境界アルゴリズムを提案する。 これらのアルゴリズムは,CIFAR-100 と ImageNet の高品質なサブセットを,集中型手法と比較すると,品質が損なわれ,あるいは損なわれていないことを示す。
• 参考スコア（独自算出の注目度）: 32.09166873008287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many learning problems hinge on the fundamental problem of subset selection, i.e., identifying a subset of important and representative points. For example, selecting the most significant samples in ML training cannot only reduce training costs but also enhance model quality. Submodularity, a discrete analogue of convexity, is commonly used for solving 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 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 show that these algorithms 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（参考訳）: 多くの学習問題は、部分集合選択の基本的な問題、すなわち重要点と代表点のサブセットを特定することにひっかかる。 例えば、mlトレーニングで最も重要なサンプルを選択することで、トレーニングコストを削減できるだけでなく、モデルの品質も向上できる。 部分モジュラリティ(submodularity)は凸性の離散類推であり、集合選択問題を解くためによく用いられる。 しかしながら、サブモジュール関数を最適化するための既存のアルゴリズムは逐次的であり、以前の分散手法ではターゲットサブセットに適合するために少なくとも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)

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

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