論文の概要: Fundamental Bounds on Online Strategic Classification
- arxiv url: http://arxiv.org/abs/2302.12355v2
- Date: Tue, 25 Jun 2024 15:06:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-26 23:19:26.881681
- Title: Fundamental Bounds on Online Strategic Classification
- Title（参考訳）: オンライン戦略分類の基礎的境界
- Authors: Saba Ahmadi, Avrim Blum, Kunhe Yang,
- Abstract要約: 戦略設定において,決定論的アルゴリズムが$o(Delta)$の誤りを達成できないことを示す。
また、これを非依存の設定に拡張し、$Delta$乗法後悔のアルゴリズムを得る。
我々は,不愉快な,適応的な両敵に対して,サブ線形後悔境界を実現するランダム化アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 13.442155854812528
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。