論文の概要: On Optimal Learning Under Targeted Data Poisoning
- arxiv url: http://arxiv.org/abs/2210.02713v1
- Date: Thu, 6 Oct 2022 06:49:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 17:58:12.189077
- Title: On Optimal Learning Under Targeted Data Poisoning
- Title（参考訳）: ターゲットデータによる最適学習について
- Authors: Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel and Shay
Moran
- Abstract要約: 本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
- 参考スコア（独自算出の注目度）: 48.907813854832206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the task of learning a hypothesis class $\mathcal{H}$ in the
presence of an adversary that can replace up to an $\eta$ fraction of the
examples in the training set with arbitrary adversarial examples. The adversary
aims to fail the learner on a particular target test point $x$ which is known
to the adversary but not to the learner. In this work we aim to characterize
the smallest achievable error $\epsilon=\epsilon(\eta)$ by the learner in the
presence of such an adversary in both realizable and agnostic settings. We
fully achieve this in the realizable setting, proving that
$\epsilon=\Theta(\mathtt{VC}(\mathcal{H})\cdot \eta)$, where
$\mathtt{VC}(\mathcal{H})$ is the VC dimension of $\mathcal{H}$. Remarkably, we
show that the upper bound can be attained by a deterministic learner. In the
agnostic setting we reveal a more elaborate landscape: we devise a
deterministic learner with a multiplicative regret guarantee of $\epsilon \leq
C\cdot\mathtt{OPT} + O(\mathtt{VC}(\mathcal{H})\cdot \eta)$, where $C > 1$ is a
universal numerical constant. We complement this by showing that for any
deterministic learner there is an attack which worsens its error to at least
$2\cdot \mathtt{OPT}$. This implies that a multiplicative deterioration in the
regret is unavoidable in this case. Finally, the algorithms we develop for
achieving the optimal rates are inherently improper. Nevertheless, we show that
for a variety of natural concept classes, such as linear classifiers, it is
possible to retain the dependence $\epsilon=\Theta_{\mathcal{H}}(\eta)$ by a
proper algorithm in the realizable setting. Here $\Theta_{\mathcal{H}}$
conceals a polynomial dependence on $\mathtt{VC}(\mathcal{H})$.
- Abstract（参考訳）: 仮説クラス $\mathcal{H}$ を、任意の逆例でトレーニングセットの例の最大$\eta$分を置き換えることができる敵の存在下で学習するタスクを考える。
相手は、特定の目標テストポイント$x$で学習者を失敗させることを目的としており、相手には知られ、学習者には知られない。
本研究の目的は,実現可能な最小のエラーである$\epsilon=\epsilon(\eta)$を,現実的かつ不可知的な設定の両方において,学習者によって特徴付けることである。
これを完全に実現し、$\epsilon=\Theta(\matht{VC}(\mathcal{H})\cdot \eta)$, ここで$\matht{VC}(\mathcal{H})$は$\mathcal{H}$のVC次元であることを示す。
注目すべきは,上界が決定論的学習者によって達成できることである。
我々は、決定論的学習者に、$\epsilon \leq c\cdot\mathtt{opt} + o(\mathtt{vc}(\mathcal{h})\cdot \eta)$ の乗法的後悔の保証を考案する。
我々は、決定論的学習者に対して、そのエラーを少なくとも2$\cdot \mathtt{OPT}$に悪化させる攻撃が存在することを示すことでこれを補完する。
これは、この場合、後悔の多元的劣化は避けられないことを意味する。
最後に、最適な速度を達成するために開発したアルゴリズムは本質的に不適切である。
それでも、線形分類器のような様々な自然概念クラスに対して、従属 $\epsilon=\Theta_{\mathcal{H}}(\eta)$ は実現可能な設定における適切なアルゴリズムによって維持可能であることを示す。
ここで、$\Theta_{\mathcal{H}}$は$\mathtt{VC}(\mathcal{H})$に対する多項式依存を隠蔽する。
関連論文リスト
- Deterministic Apple Tasting [2.4554686192257424]
我々は、初めて広く適用可能な決定論的リンゴテイスティング学習者を提供する。
すべてのクラス $mathcalH$ は簡単、困難、あるいは学習不能でなければならない、という三分法を証明します。
我々の上限は、リンゴの味付けフィードバックに関する専門家のアドバイスから学ぶための決定論的アルゴリズムに基づいている。
論文 参考訳（メタデータ） (2024-10-14T11:54:46Z) - Revisiting Agnostic PAC Learning [30.67561230812141]
PAC学習は、Valiant'84とVapnik and Chervonenkis'64,'74にさかのぼる、教師あり学習を研究するための古典的なモデルである。
経験的リスク最小化(英: Empirical Risk Minimization、ERM)は、訓練データに最も少ない誤りを犯すために$mathcalH$から仮説を出力する自然学習アルゴリズムである。
私たちはPAC学習を再考し、最良仮説の性能を$tau:=Pr_mathcalD[hstar_mathと表すと、ERMが実際は準最適であることを示す。
論文 参考訳（メタデータ） (2024-07-29T08:20:49Z) - Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-05-21T17:31:10Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳（メタデータ） (2021-04-17T08:22:04Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Phase Transitions in Rate Distortion Theory and Deep Learning [5.145741425164946]
もし$mathcalS$をエンコードするために$mathcalO(R-s)$のエラーを達成できれば、$mathcalS$は$s$で圧縮できると言う。
ある"ニッチ"信号クラスに対して、$mathcalS$が相転移を起こすことを示す。
論文 参考訳（メタデータ） (2020-08-03T16:48:49Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。