論文の概要: 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})$に対する多項式依存を隠蔽する。
関連論文リスト
- Does Sparsity Help in Learning Misspecified Linear Bandits? [32.920577630673804]
アルゴリズムは$O(varepsilon-sds)$アクションをクエリすることで、$O(varepsilon)$-optimalアクションを得ることができることを示す。
また、サンプルの複雑さに対する上限は、エラーが$O(sdeltavarepsilon)$$$0delta1$を要求する場合、ほぼ厳密であることを示す。
論文 参考訳(メタデータ) (2023-03-29T19:58:39Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳(メタデータ) (2022-07-28T17:50:53Z) - Differentially Private Nonparametric Regression Under a Growth Condition [9.416757363901295]
実数値仮説クラス $mathcalH$ が与えられた場合、最適な仮説を学習する微分プライベートアルゴリズムが存在する場合の条件について検討する。
緩和条件である$lim inf_eta downarrow 0 eta cdot rm sfat_eta(mathcalH)$ = 0$, $mathcalH$はプライベートに学習可能であることを示す。
論文 参考訳(メタデータ) (2021-11-24T20:36:01Z) - Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。
学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文 参考訳(メタデータ) (2021-06-25T09:08:33Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-06-09T05:39:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。