論文の概要: Adversarial Robustness of Streaming Algorithms through Importance Sampling

• arxiv url: http://arxiv.org/abs/2106.14952v1
• Date: Mon, 28 Jun 2021 19:24:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-01 08:35:17.759193
• Title: Adversarial Robustness of Streaming Algorithms through Importance Sampling
• Title（参考訳）: 重要サンプリングによるストリーミングアルゴリズムの逆ロバスト性
• Authors: Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, Samson Zhou
• Abstract要約: 我々は、中央の機械学習とアルゴリズムタスクに逆向きに頑健なストリーミングアルゴリズムを導入する。 我々の結果は、多くの重要なサンプリングベースのアルゴリズムが敵の堅牢性をもたらすという、単純だが強力で観察に基づいている。 我々は、様々な敵攻撃に対するアルゴリズムの堅牢性を実証的に確認し、対照的に、いくつかの一般的なアルゴリズムは堅牢ではないことを示す。
• 参考スコア（独自算出の注目度）: 29.957317489789745
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we introduce adversarially robust streaming algorithms for central machine learning and algorithmic tasks, such as regression and clustering, as well as their more general counterparts, subspace embedding, low-rank approximation, and coreset construction. For regression and other numerical linear algebra related tasks, we consider the row arrival streaming model. Our results are based on a simple, but powerful, observation that many importance sampling-based algorithms give rise to adversarial robustness which is in contrast to sketching based algorithms, which are very prevalent in the streaming literature but suffer from adversarial attacks. In addition, we show that the well-known merge and reduce paradigm in streaming is adversarially robust. Since the merge and reduce paradigm allows coreset constructions in the streaming setting, we thus obtain robust algorithms for $k$-means, $k$-median, $k$-center, Bregman clustering, projective clustering, principal component analysis (PCA) and non-negative matrix factorization. To the best of our knowledge, these are the first adversarially robust results for these problems yet require no new algorithmic implementations. Finally, we empirically confirm the robustness of our algorithms on various adversarial attacks and demonstrate that by contrast, some common existing algorithms are not robust. (Abstract shortened to meet arXiv limits)
• Abstract（参考訳）: 本稿では,重回帰やクラスタリングといった中央的機械学習やアルゴリズム的タスクに対して,より汎用的な部分空間埋め込み,低ランク近似,コアセット構築などに対して,逆ロバストなストリーミングアルゴリズムを導入する。 回帰やその他の数値線形代数関連タスクに対しては,行到着ストリーミングモデルを検討する。 本研究の結果は,多くの重要なサンプリングベースアルゴリズムが,ストリーミング文学において非常に多いが,敵対的攻撃に悩まされているスケッチベースアルゴリズムとは対照的に,敵対的堅牢性をもたらすという,単純かつ強力で強力な観察に基づいている。 さらに、ストリーミングにおけるよく知られたマージと削減パラダイムが逆向きに堅牢であることを示す。 マージと削減のパラダイムはストリーミング環境でコアセットの構成を可能にするので、$k$-means, $k$-median, $k$-center, Bregmanクラスタリング、射影クラスタリング、主成分分析(PCA)、非負行列分解のための堅牢なアルゴリズムが得られる。 我々の知る限りでは、これらの問題は最初の逆向きに堅牢な結果であり、新しいアルゴリズムの実装を必要としない。 最後に,様々な敵攻撃におけるアルゴリズムのロバスト性を確認するとともに,既存のアルゴリズムがロバストでないことを示す。 (抽象的短縮によりarXiv制限を満たす)

関連論文リスト

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  我々はロバスト成分分析のためのアルゴリズムを設計する(A) 行列を低主行列とスパース主行列の和に分解する。
  論文  参考訳（メタデータ） (2023-07-12T03:48:26Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。 このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。 このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
  論文  参考訳（メタデータ） (2022-09-27T19:04:36Z)
• Fairness Degrading Adversarial Attacks Against Clustering Algorithms [35.40427659749882]
  そこで本研究では,k-medianクラスタリングのためのフェアネス劣化攻撃アルゴリズムを提案する。 生成した対数サンプルの追加により、フェアネス値が大幅に低下することが判明した。
  論文  参考訳（メタデータ） (2021-10-22T19:10:27Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  少数の敵対的攻撃は、数ピクセルを摂動するだけでディープ・ネットワーク(DNN)を騙すことができる。 近年の取り組みは、他の等級のl_infty摂動と組み合わせている。 本稿では,空間的・神経的摂動に対処するホモトピーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-10T20:11:36Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。 私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
  論文  参考訳（メタデータ） (2020-11-12T18:58:51Z)
• A black-box adversarial attack for poisoning clustering [78.19784577498031]
  本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。 我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
  論文  参考訳（メタデータ） (2020-09-09T18:19:31Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• How to Solve Fair $k$-Center in Massive Data Models [5.3283669037198615]
  我々は、$k$-center問題に対して、新しいストリーミングおよび分散アルゴリズムを設計する。 主な貢献は、(a)最初の分散アルゴリズム、(b)証明可能な近似保証付き2パスストリーミングアルゴリズムである。
  論文  参考訳（メタデータ） (2020-02-18T16:11:40Z)

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

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