論文の概要: Mistake, Manipulation and Margin Guarantees in Online Strategic Classification

• arxiv url: http://arxiv.org/abs/2403.18176v1
• Date: Wed, 27 Mar 2024 01:05:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-28 18:45:45.666076
• Title: Mistake, Manipulation and Margin Guarantees in Online Strategic Classification
• Title（参考訳）: オンライン戦略分類におけるミステイク・マニピュレーション・マージン保証
• Authors: Lingqing Shen, Nam Ho-Nguyen, Khanh-Hung Giang-Tran, Fatma Kılınç-Karzan,
• Abstract要約: 到着した各エージェントが真の特徴ベクトルを操作して正の予測ラベルを得るという,オンライン戦略分類問題を考える。 我々は、様々なエージェントコスト構造に対する収束、有限の誤り、有限の操作保証を証明した。 実データおよび合成データに関する数値的な研究により、新しいアルゴリズムは、マージン、操作数、誤り数において、以前のアルゴリズムよりも優れていることが示された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label, while incurring a cost that depends on the amount of manipulation. The learner seeks to predict the agent's true label given access to only the manipulated features. After the learner releases their prediction, the agent's true label is revealed. Previous algorithms such as the strategic perceptron guarantee finitely many mistakes under a margin assumption on agents' true feature vectors. However, these are not guaranteed to encourage agents to be truthful. Promoting truthfulness is intimately linked to obtaining adequate margin on the predictions, thus we provide two new algorithms aimed at recovering the maximum margin classifier in the presence of strategic agent behavior. We prove convergence, finite mistake and finite manipulation guarantees for a variety of agent cost structures. We also provide generalized versions of the strategic perceptron with mistake guarantees for different costs. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of margin, number of manipulation and number of mistakes.
• Abstract（参考訳）: 我々は,各エージェントが真の特徴ベクトルを操作して,操作量に依存するコストを発生させながら,正の予測ラベルを得るという,オンライン戦略分類問題を考える。 学習者は、操作された特徴のみへのアクセスを与えられたエージェントの真のラベルを予測する。 学習者が予測を公表した後、エージェントの真のラベルが明らかにされる。 戦略パーセプトロンのような以前のアルゴリズムは、エージェントの真の特徴ベクトルに対するマージン仮定の下で有限個の誤りを保証した。 しかし、これらはエージェントが真実であるように促すことを保証するものではない。 そこで我々は,戦略エージェントの存在下での最大マージン分類器の回復を目的とした2つの新しいアルゴリズムを提案する。 我々は、様々なエージェントコスト構造に対する収束、有限の誤り、有限の操作保証を証明した。 戦略パーセプトロンの一般化版も提供し、異なるコストの誤りを保証します。 実データおよび合成データに関する数値的な研究により、新しいアルゴリズムは、マージン、操作数、誤り数において、以前のアルゴリズムよりも優れていることが示された。

関連論文リスト

• Strategic Classification With Externalities [11.36782598786846]
  戦略分類問題の新しい変種を提案する。 実世界のアプリケーションによって動機づけられた我々のモデルは、あるエージェントの操作が他のエージェントに影響を与えることを決定的に許している。 特定の仮定の下では、このエージェント操作ゲームの純粋なナッシュ平衡はユニークであり、効率的に計算できることが示される。
  論文  参考訳（メタデータ） (2024-10-10T15:28:04Z)
• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  我々は,エージェント群を協調させようとする学習者の視点で,マルチエージェント模倣学習(MAIL)問題を研究する。 MAILの以前の作業のほとんどは、基本的には、デモのサポート内で専門家の振る舞いにマッチする問題を減らすものです。 エージェントが戦略的でないという仮定の下で、学習者と専門家の間の価値ギャップをゼロにするのに十分であるが、戦略的エージェントによる逸脱を保証するものではない。
  論文  参考訳（メタデータ） (2024-06-06T16:18:20Z)
• Learnability Gaps of Strategic Classification [68.726857356532]
  我々は,戦略的分類と標準学習の間にある学習可能性のギャップという,根本的な問題に対処することに注力する。 ほぼ厳密なサンプルの複雑さと後悔の限界を提供し、以前の結果よりも大幅に改善します。 この設定における我々のアルゴリズムは、独立して興味を持ち、マルチラベル学習のような他の問題にも適用できる。
  論文  参考訳（メタデータ） (2024-02-29T16:09:19Z)
• Fundamental Bounds on Online Strategic Classification [13.442155854812528]
  戦略設定において,決定論的アルゴリズムが$o(Delta)$の誤りを達成できないことを示す。 また、これを非依存の設定に拡張し、$Delta$乗法後悔のアルゴリズムを得る。 我々は,不愉快な,適応的な両敵に対して,サブ線形後悔境界を実現するランダム化アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-02-23T22:39:43Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。 エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。 我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
  論文  参考訳（メタデータ） (2022-06-01T00:44:53Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  実世界の機械学習デプロイメントは、ソース(トレーニング)とターゲット(テスト)ディストリビューションのミスマッチによって特徴づけられる。 本研究では,ラベル付きソースデータとラベルなしターゲットデータのみを用いて,対象領域の精度を予測する手法を検討する。 本稿では,モデルの信頼度をしきい値として学習し,精度をラベルなし例のごく一部として予測する実践的手法である平均閾値保持信頼度(ATC)を提案する。
  論文  参考訳（メタデータ） (2022-01-11T23:01:12Z)
• Distribution-free uncertainty quantification for classification under label shift [105.27463615756733]
  2つの経路による分類問題に対する不確実性定量化(UQ)に焦点を当てる。 まず、ラベルシフトはカバレッジとキャリブレーションの低下を示すことでuqを損なうと論じる。 これらの手法を, 理論上, 分散性のない枠組みで検討し, その優れた実用性を示す。
  論文  参考訳（メタデータ） (2021-03-04T20:51:03Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  エージェントの選好が不明な場合,共有資源の不足の設定における意思決定の問題について検討する。 我々のアプローチは、再生されたカーネルヒルベルト空間における好みの表現に基づいている。 エージェントの期待した利益を最大化する最適な戦略を導出する。
  論文  参考訳（メタデータ） (2020-10-29T03:08:22Z)
• The Strategic Perceptron [11.078814063722803]
  正であると分類されたい戦略エージェントが存在する場合、パーセプトロンアルゴリズムはエージェントの真の位置を観察できないかもしれない。 2つの解の間に永久に振動する予測器の例を示す。 私たちの主な貢献は、戦略エージェントの存在下で多くの誤りを犯すPerceptronスタイルのアルゴリズムの修正です。
  論文  参考訳（メタデータ） (2020-08-04T17:20:24Z)
• No-Regret and Incentive-Compatible Online Learning [29.267666165169324]
  本研究では,学習アルゴリズムの予測に対する影響を最大化するために,専門家が戦略的に行動するオンライン学習環境について検討する。 私たちは、学習アルゴリズムを、後見の最高の固定専門家に対して、不適切なものにしたいと考えています。 完全な情報設定と部分的な情報設定の両方について、専門家にとって後悔とインセンティブの相性のないアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-02-20T16:21:34Z)
• Bounded Incentives in Manipulating the Probabilistic Serial Rule [8.309903898123526]
  確率的シリアルはインセンティブ互換ではない。 戦略行動による実質的な実用性の向上は、自己関心のエージェントがメカニズムを操作するきっかけとなる。 このメカニズムのインセンティブ比が$frac32$であることを示す。
  論文  参考訳（メタデータ） (2020-01-28T23:53:37Z)

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

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