論文の概要: RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions

• arxiv url: http://arxiv.org/abs/2504.09648v1
• Date: Sun, 13 Apr 2025 16:47:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:53:31.023456
• Title: RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions
• Title（参考訳）: RANSACが再考: 対向的・雑音的破壊下でのロバスト部分空間回復のための改良アルゴリズム
• Authors: Guixian Chen, Jianhao Ma, Salar Fattahi,
• Abstract要約: 破損しないサンプルのかなりの部分を含む低次元部分空間を復元することを目的としている。 この問題に対する既存のアプローチは、しばしば高い計算コストに悩まされるか、制限的な分布仮定に依存する。 本稿では,標準的なRANSACの障害モードを正確に特定し,修正する2段階アルゴリズムであるRANSAC+を提案する。
• 参考スコア（独自算出の注目度）: 16.45408984254899
• License:
• Abstract: In this paper, we study the problem of robust subspace recovery (RSR) in the presence of both strong adversarial corruptions and Gaussian noise. Specifically, given a limited number of noisy samples -- some of which are tampered by an adaptive and strong adversary -- we aim to recover a low-dimensional subspace that approximately contains a significant fraction of the uncorrupted samples, up to an error that scales with the Gaussian noise. Existing approaches to this problem often suffer from high computational costs or rely on restrictive distributional assumptions, limiting their applicability in truly adversarial settings. To address these challenges, we revisit the classical random sample consensus (RANSAC) algorithm, which offers strong robustness to adversarial outliers, but sacrifices efficiency and robustness against Gaussian noise and model misspecification in the process. We propose a two-stage algorithm, RANSAC+, that precisely pinpoints and remedies the failure modes of standard RANSAC. Our method is provably robust to both Gaussian and adversarial corruptions, achieves near-optimal sample complexity without requiring prior knowledge of the subspace dimension, and is more efficient than existing RANSAC-type methods.
• Abstract（参考訳）: 本稿では,強敵対的汚職とガウス雑音の存在下でのロバスト・サブスペース・リカバリ(RSR)の問題について検討する。 具体的には、限られた数のノイズサンプル(そのうちのいくつかは適応的で強い敵によって妨げられている)が与えられた場合、我々はガウス雑音でスケールする誤差まで、ほとんど破壊されていないサンプルのかなりの部分を含む低次元の部分空間を復元することを目指している。 この問題に対する既存のアプローチは、しばしば高い計算コストに悩まされるか、あるいは制限的な分布仮定に依存し、真に敵対的な設定で適用性を制限する。 これらの課題に対処するために、古典的ランダムサンプルコンセンサス(RANSAC)アルゴリズムを再検討し、敵の外れ値に対して強い堅牢性を提供するが、ガウス雑音に対する効率性と堅牢性を犠牲にし、その過程におけるモデル不特定性を解消する。 本稿では,標準的なRANSACの障害モードを正確に特定し,修正する2段階アルゴリズムであるRANSAC+を提案する。 提案手法はガウス的, 対角的両汚職に対して確実に堅牢であり, 部分空間次元の事前知識を必要とせず, ほぼ最適サンプルの複雑さを実現し, 既存のRANSAC方式よりも効率的である。

関連論文リスト

• Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate [6.209600119671225]
  本研究では,悪質な雑音の存在下でのハーフスペースの計算効率の高いPAC学習の問題について検討する。 再重み付きヒンジ損失を最小化することにより、一定の耐雑音性を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-10-02T02:38:33Z)
• ROPO: Robust Preference Optimization for Large Language Models [59.10763211091664]
  外部モデルの助けを借りずにノイズ耐性とノイズサンプルのフィルタリングを統合する反復アライメント手法を提案する。 Mistral-7BとLlama-2-7Bで広く使われている3つのデータセットの実験では、ROPOが既存の嗜好アライメント法を大幅に上回っていることが示されている。
  論文  参考訳（メタデータ） (2024-04-05T13:58:51Z)
• STBA: Towards Evaluating the Robustness of DNNs for Query-Limited Black-box Scenario [50.37501379058119]
  本研究では,クエリ制限シナリオにおいて,悪意のある逆の例を作成するために,空間変換ブラックボックス攻撃(STBA)を提案する。 そこで本研究では,STBAが対向例の認識不能性を効果的に改善し,クエリ制限条件下での攻撃成功率を大幅に向上できることを示す。
  論文  参考訳（メタデータ） (2024-03-30T13:28:53Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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