論文の概要: Fundamental Bounds on Online Strategic Classification
- arxiv url: http://arxiv.org/abs/2302.12355v1
- Date: Thu, 23 Feb 2023 22:39:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 15:10:17.516998
- Title: Fundamental Bounds on Online Strategic Classification
- Title（参考訳）: オンライン戦略分類の基礎的境界
- Authors: Saba Ahmadi, Avrim Blum, Kunhe Yang
- Abstract要約: 戦略設定において,決定論的アルゴリズムが$o(Delta)$の誤りを達成できないことを示す。
また、これを非依存の設定に拡張し、$Delta$乗法後悔のアルゴリズムを得る。
我々は,不愉快な,適応的な両敵に対して,サブ線形後悔境界を実現するランダム化アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 13.096037258255558
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online binary classification where strategic agents
can manipulate their observable features in predefined ways, modeled by a
manipulation graph, in order to receive a positive classification. We show this
setting differs in fundamental ways from non-strategic online classification.
For instance, whereas in the non-strategic case, a mistake bound of $\ln|H|$ is
achievable via the halving algorithm when the target function belongs to a
known class $H$, we show that no deterministic algorithm can achieve a mistake
bound $o(\Delta)$ in the strategic setting, where $\Delta$ is the maximum
degree of the manipulation graph (even when $|H|=O(\Delta)$). We obtain an
algorithm achieving mistake bound $O(\Delta\ln|H|)$. We also extend this to the
agnostic setting and obtain an algorithm with a $\Delta$ multiplicative regret,
and we show no deterministic algorithm can achieve $o(\Delta)$ multiplicative
regret.
Next, we study two randomized models based on whether the random choices are
made before or after agents respond, and show they exhibit fundamental
differences. In the first model, at each round the learner deterministically
chooses a probability distribution over classifiers inducing expected values on
each vertex (probabilities of being classified as positive), which the
strategic agents respond to. We show that any learner in this model has to
suffer linear regret. On the other hand, in the second model, while the
adversary who selects the next agent must respond to the learner's probability
distribution over classifiers, the agent then responds to the actual hypothesis
classifier drawn from this distribution. Surprisingly, we show this model is
more advantageous to the learner, and we design randomized algorithms that
achieve sublinear regret bounds against both oblivious and adaptive
adversaries.
- Abstract（参考訳）: 本研究では,戦略エージェントが事前定義された方法で観察可能な特徴を操作グラフでモデル化し,肯定的な分類を受けるためのオンラインバイナリ分類の問題点について検討する。
この設定は,非戦略的オンライン分類と根本的に異なる。
例えば、非ストラテジックの場合、ターゲット関数が既知のクラス$H$に属している場合、$\ln|H|$の誤り境界は半可算アルゴリズムによって達成可能であるが、戦略的な設定では$o(\Delta)$の誤りを決定論的アルゴリズムが達成できないことを示し、$\Delta$は演算グラフの最大次数である(|H|=O(\Delta)$のときでさえ)。
誤差付き$O(\Delta\ln|H|)$を得るアルゴリズムを得る。
また、これを非依存設定に拡張し、$\Delta$乗算後悔を持つアルゴリズムを得るとともに、決定論的アルゴリズムが$o(\Delta)$乗算後悔を達成できないことを示す。
次に,エージェントの反応前後にランダムな選択がなされているかどうかに基づいて2つのランダム化モデルについて検討し,基本的な違いを示す。
第1のモデルでは、学習者は各ラウンドにおいて、戦略エージェントが応答する各頂点(正に分類される確率)に期待値を誘導する分類器上の確率分布を決定論的に選択する。
このモデルの学習者は、線形後悔に苦しむ必要がある。
一方、第2のモデルでは、次のエージェントを選択する相手が学習者の確率分布に応答しなければならないが、エージェントはこの分布から引き出された実際の仮説分類器に応答する。
意外なことに、このモデルは学習者にとってより有利であることが示され、不愉快かつ適応的な双方の敵に対するサブ線形後悔境界を達成するランダム化アルゴリズムを設計した。
関連論文リスト
- Agnostic Smoothed Online Learning [5.167069404528051]
本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。
R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
論文 参考訳（メタデータ） (2024-10-07T15:25:21Z) - Rejection via Learning Density Ratios [50.91522897152437]
拒絶による分類は、モデルを予測しないことを許容する学習パラダイムとして現れます。
そこで我々は,事前学習したモデルの性能を最大化する理想的なデータ分布を求める。
私たちのフレームワークは、クリーンでノイズの多いデータセットで実証的にテストされます。
論文 参考訳（メタデータ） (2024-05-29T01:32:17Z) - Delta-AI: Local objectives for amortized inference in sparse graphical models [64.5938437823851]
スパース確率的グラフィカルモデル(PGM)における補正推論のための新しいアルゴリズムを提案する。
提案手法は, PGMにおける変数のサンプリングをエージェントが行う一連の行動とみなす場合, エージェントのポリシー学習目的において, PGMの疎結合が局所的な信用割当を可能にするという観察に基づいている。
合成PGMからサンプリングし、スパース因子構造を持つ潜在変数モデルを訓練するための$Delta$-AIの有効性について説明する。
論文 参考訳（メタデータ） (2023-10-03T20:37:03Z) - Value-Distributional Model-Based Reinforcement Learning [59.758009422067]
政策の長期的業績に関する不確実性の定量化は、シーケンシャルな意思決定タスクを解決するために重要である。
モデルに基づくベイズ強化学習の観点から問題を考察する。
本稿では,値分布関数を学習するモデルに基づくアルゴリズムであるEpicemic Quantile-Regression(EQR)を提案する。
論文 参考訳（メタデータ） (2023-08-12T14:59:19Z) - Risk Preferences of Learning Algorithms [0.0]
広く使われている学習アルゴリズムである$varepsilon$-Greedyは、突発的なリスク回避を示す。
このバイアスを修正する2つの方法について議論する。
論文 参考訳（メタデータ） (2022-05-10T01:30:24Z) - Universal and data-adaptive algorithms for model selection in linear
contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。
データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。
我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文 参考訳（メタデータ） (2021-11-08T18:05:35Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Thought Flow Nets: From Single Predictions to Trains of Model Thought [39.619001911390804]
人間が複雑な問題を解くと、すぐに決定が下されることはめったにない。
その代わり、彼らは直感的な決定から始まり、間違いを見つけ、矛盾を解決し、異なる仮説の間を飛び交う。
論文 参考訳（メタデータ） (2021-07-26T13:56:37Z) - Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
本研究では,学習者が最適仮説クラスの次元に適応しなければならない線形帯域設定におけるモデル選択問題について検討する。
本稿では,まず,固定アクション集合であっても,未知の内在次元$d_star$ への適応がコスト的に現れることを示す下限を定式化する。
論文 参考訳（メタデータ） (2021-02-12T16:02:06Z) - The Strategic Perceptron [11.078814063722803]
正であると分類されたい戦略エージェントが存在する場合、パーセプトロンアルゴリズムはエージェントの真の位置を観察できないかもしれない。
2つの解の間に永久に振動する予測器の例を示す。
私たちの主な貢献は、戦略エージェントの存在下で多くの誤りを犯すPerceptronスタイルのアルゴリズムの修正です。
論文 参考訳（メタデータ） (2020-08-04T17:20:24Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。