論文の概要: Adversarially Robust Learning with Tolerance

• arxiv url: http://arxiv.org/abs/2203.00849v1
• Date: Wed, 2 Mar 2022 03:50:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-03 13:48:19.149805
• Title: Adversarially Robust Learning with Tolerance
• Title（参考訳）: 忍耐力を持つ対向的ロバストな学習
• Authors: Hassan Ashtiani, Vinayak Pathak, Ruth Urner
• Abstract要約: 本稿では,距離摂動集合に対する寛容逆PAC学習の問題点について考察する。 自然摂動・平滑アルゴリズムの変種であるPACは、$gamma$-tolerant adversarial setにおいて、VC次元が$v$の任意の仮説クラス$mathcalH$を学習する。 また,2次元に線形依存したサンプル境界を求める学習手法を提案する。
• 参考スコア（独自算出の注目度）: 8.658596218544774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of tolerant adversarial PAC learning with respect to metric perturbation sets. In adversarial PAC learning, an adversary is allowed to replace a test point $x$ with an arbitrary point in a closed ball of radius $r$ centered at $x$. In the tolerant version, the error of the learner is compared with the best achievable error with respect to a slightly larger perturbation radius $(1+\gamma)r$. For perturbation sets with doubling dimension $d$, we show that a variant of the natural ``perturb-and-smooth'' algorithm PAC learns any hypothesis class $\mathcal{H}$ with VC dimension $v$ in the $\gamma$-tolerant adversarial setting with $O\left(\frac{v(1+1/\gamma)^{O(d)}}{\varepsilon}\right)$ samples. This is the first such general guarantee with linear dependence on $v$ even for the special case where the domain is the real line and the perturbation sets are closed balls (intervals) of radius $r$. However, the proposed guarantees for the perturb-and-smooth algorithm currently only hold in the tolerant robust realizable setting and exhibit exponential dependence on $d$. We additionally propose an alternative learning method which yields sample complexity bounds with only linear dependence on the doubling dimension even in the more general agnostic case. This approach is based on sample compression.
• Abstract（参考訳）: 距離摂動集合に対する寛容逆PAC学習の問題について検討する。 敵対的pac学習では、敵はテストポイント $x$ を、半径 $r$ を中心とする閉じたボール内の任意の点に置き換えることができる。 耐性のあるバージョンでは、学習者の誤差はわずかに大きい摂動半径$(1+\gamma)r$に対して達成可能な最良の誤差と比較される。 二重次元 $d$ を持つ摂動集合に対して、自然の ``perturb-and-smooth'' アルゴリズムの変種 PAC が任意の仮説クラス $\mathcal{H}$ と VC 次元 $v$ と $\gamma$-tolerant の逆数集合 $O\left(\frac{v(1+1/\gamma)^{O(d)}}{\varepsilon}\right)$サンプルを学ぶことを示す。 これは、領域が実数直線であり摂動集合が半径 $r$ の閉球(内部)である特別な場合であっても、v$ に対する線形依存を持つ最初の一般保証である。 しかし、現在提案されているパーターブ・アンド・スムースアルゴリズムの保証は頑健な実現可能な設定を保ち、$d$に指数関数的依存を示すのみである。 さらに,より一般的な非依存の場合であっても2倍次元に線形依存したサンプル複雑性境界を生成する代替学習法を提案する。 このアプローチはサンプル圧縮に基づいている。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Interplay between depth and width for interpolation in neural ODEs [0.0]
  それらの幅$p$と層遷移数$L$の相互作用について検討する。 高次元設定では、$p=O(N)$ニューロンが正確な制御を達成するのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-01-18T11:32:50Z)
• Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error [8.615625517708324]
  サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。 本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
  論文  参考訳（メタデータ） (2023-02-23T19:13:30Z)
• The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning [29.44582058149344]
  n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。 次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
  論文  参考訳（メタデータ） (2023-02-09T14:20:14Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Learning the optimal regularizer for inverse problems [1.763934678295407]
  線形逆問題 $y=Ax+epsilon$ を考えると、$Acolon Xto Y$ は分離可能なヒルベルト空間 $X$ と $Y$ の間の既知の線型作用素である。 この設定は、デノイング、デブロアリング、X線トモグラフィーなど、画像のいくつかの逆問題を含んでいる。 古典的な正規化の枠組みの中では、正規化関数が優先順位を与えられず、データから学習される場合に焦点を当てる。
  論文  参考訳（メタデータ） (2021-06-11T17:14:27Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Toward Adversarial Robustness via Semi-supervised Robust Training [93.36310070269643]
  アドリラルな例は、ディープニューラルネットワーク(DNN)に対する深刻な脅威であることが示されている。 R_stand$ と $R_rob$ の2つの異なるリスクを共同で最小化することで、新しい防御手法であるロバストトレーニング(RT)を提案する。
  論文  参考訳（メタデータ） (2020-03-16T02:14:08Z)
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning [7.6146285961466]
  我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。 最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
  論文  参考訳（メタデータ） (2020-02-24T15:12:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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