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

• arxiv url: http://arxiv.org/abs/2406.17188v2
• Date: Fri, 17 Jan 2025 08:38:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-20 13:58:11.532847
• Title: Geometric Median (GM) Matching for Robust Data Pruning
• Title（参考訳）: ロバストデータ抽出のための幾何媒介(GM)マッチング
• Authors: Anish Acharya, Inderjit S Dhillon, Sujay Sanghavi,
• Abstract要約: 本稿では,雑音のあるデータセットの幾何的中央値に近似した$k$-subsetを求める群れ型グリードアルゴリズムを提案する。 いくつかの人気のあるディープラーニングベンチマークに対する実験は、$gm$ Matchingが従来よりも一貫して改善されていることを示している。
• 参考スコア（独自算出の注目度）: 29.458270105150564
• License:
• Abstract: Large-scale data collections in the wild, are invariably noisy. Thus developing data pruning strategies that remain robust even in the presence of corruption is critical in practice. In this work, we propose Geometric Median ($\gm$) Matching -- a herding 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 {\bf optimal breakdown point} of {\bf 1/2} even under {\bf arbitrary} corruption. Extensive experiments across several popular deep learning benchmarks indicate that $\gm$ Matching consistently improves over 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（参考訳）: 大規模なデータ収集は、もちろんノイズが多い。 したがって、汚職があっても堅牢なデータプルーニング戦略の開発は、実際は極めて重要である。 そこで本研究では,^k^,,<sup>,^,,^,,^,,^,,^,,^,,<sup>,^,,<sup>,<sup>,^,,<sup>,^,,<sup>,<sup>,^,,<sup>,^,,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,<sup>,^,,<sup>,<sup>,<sup>,<sup,<sup,<sup,<sup,<sup>,<sup,<sup,< 理論的には、$\gm$ Matchingは$\gO(1/k)$のスケールを$\gO(1/\sqrt{k})$の一様サンプリングのスケーリングよりも改善した$\gO(1/\sqrt{k})$のスケールを楽しむ。 いくつかの人気のあるディープラーニングベンチマークによる大規模な実験によると、$\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)

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

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