Fugu-MT 論文翻訳(概要): Geometric Median (GM) Matching for Robust Data Pruning

論文の概要: Geometric Median (GM) Matching for Robust Data Pruning

arxiv url: http://arxiv.org/abs/2406.17188v1
Date: Tue, 25 Jun 2024 00:02:01 GMT
ステータス: 処理完了
システム内更新日: 2024-06-26 16:11:02.005694
Title: Geometric Median (GM) Matching for Robust Data Pruning
Title（参考訳）: ロバストデータ抽出のための幾何媒介(GM)マッチング
Authors: Anish Acharya, Inderjit S Dhillon, Sujay Sanghavi,
Abstract要約: データプルーニングは、大規模なデータハングリーモデルのトレーニングに伴う膨大な計算コストを軽減するために不可欠である。本研究では,部分集合の平均値が(潜在的に)ノイズデータセットの中央値に近似するように,$k$-subsetを求めるGeometric ($gm$) Matchingを提案する。一般的なディープラーニングベンチマークによる実験によると、$gm$ Matchingは、従来よりも一貫してパフォーマンスが向上している。
参考スコア（独自算出の注目度）: 29.458270105150564
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Data pruning, the combinatorial task of selecting a small and informative subset from a large dataset, is crucial for mitigating the enormous computational costs associated with training data-hungry modern deep learning models at scale. Since large-scale data collections are invariably noisy, developing data pruning strategies that remain robust even in the presence of corruption is critical in practice. Unfortunately, the existing heuristics for (robust) data pruning lack theoretical coherence and rely on heroic assumptions, that are, often unattainable, by the very nature of the problem setting. Moreover, these strategies often yield sub-optimal neural scaling laws even compared to random sampling, especially in scenarios involving strong corruption and aggressive pruning rates -- making provably robust data pruning an open challenge. In response, in this work, we propose Geometric Median ($\gm$) Matching -- a herding~\citep{welling2009herding} style greedy algorithm -- that yields a $k$-subset such that the mean of the subset approximates the geometric median of the (potentially) noisy dataset. Theoretically, we show that $\gm$ Matching enjoys an improved $\gO(1/k)$ scaling over $\gO(1/\sqrt{k})$ scaling of uniform sampling; while achieving the optimal breakdown point of 1/2 even under arbitrary corruption. Extensive experiments across popular deep learning benchmarks indicate that $\gm$ Matching consistently outperforms prior state-of-the-art; the gains become more profound at high rates of corruption and aggressive pruning rates; making $\gm$ Matching a strong baseline for future research in robust data pruning.
Abstract（参考訳）: データプルーニング(Data pruning)は、大規模データセットから小さくて情報的なサブセットを選択するための組合せ的タスクであり、大規模にデータに飢えた現代のディープラーニングモデルをトレーニングする際の膨大な計算コストを軽減するために不可欠である。大規模なデータ収集はめったに騒がしいため、汚職があっても頑丈なデータ刈り取り戦略を開発することは、実際は極めて重要である。残念なことに、(ロバストな)データプルーニングの既存のヒューリスティックスは理論的なコヒーレンスを欠いており、問題設定の性質によってしばしば達成不可能な英雄的な仮定に依存している。さらに、これらの戦略は、特に強い汚職やアグレッシブプルーニング率を含むシナリオにおいて、ランダムサンプリングよりも、サブ最適のニューラルスケーリング法を生じることが多い。これは、証明可能なロバストなデータプルーニングをオープンな課題とする。これに対し、我々は、Geometric Median(\gm$) Matching -- a herding~\citep{welling2009herding}スタイルのgreedyアルゴリズムを提案する。これは、サブセットの平均が(潜在的に)ノイズデータセットの幾何学的中央値に近似するように、$k$-subsetを生成する。理論的には、$\gm$ Matchingは$\gO(1/k)$のスケールを$\gO(1/\sqrt{k})$のスケールで楽しむ。一般的なディープラーニングベンチマークの広範な実験によると、$\gm$ Matchingは、最先端の最先端を一貫して上回り、高い汚職率とアグレッシブプルーニングレートで上昇し、$\gm$ Matchingは、堅牢なデータプルーニングにおける将来の研究の強力なベースラインとなる。

関連論文リスト

Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文参考訳（メタデータ） (2024-06-01T07:33:41Z)
A Combinatorial Approach to Robust PCA [18.740048806623037]
敵の汚職下でのガウスデータの回復問題について検討する。ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
論文参考訳（メタデータ） (2023-11-28T01:49:51Z)
Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文参考訳（メタデータ） (2023-10-23T04:07:26Z)
Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。また、Acharyaなどのアルゴリズムの改良版も提供します。
論文参考訳（メタデータ） (2023-06-20T06:13:56Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文参考訳（メタデータ） (2022-10-31T03:00:11Z)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文参考訳（メタデータ） (2022-06-17T09:24:41Z)
Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
論文参考訳（メタデータ） (2022-02-16T16:24:31Z)
Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文参考訳（メタデータ） (2022-02-05T01:59:09Z)
Sample Complexity of Adversarially Robust Linear Classification on Separated Data [41.30425613353595]
対向的堅牢性を伴う学習の複雑さについて考察する。非常に分離されたデータの場合、$o(frac1n)$の収束率は達成可能である。
論文参考訳（メタデータ） (2020-12-19T22:04:59Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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