論文の概要: One-Shot Strategic Classification Under Unknown Costs

• arxiv url: http://arxiv.org/abs/2311.02761v2
• Date: Tue, 19 Mar 2024 14:41:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 00:20:56.815436
• Title: One-Shot Strategic Classification Under Unknown Costs
• Title（参考訳）: 未知のコストによるワンショット戦略分類
• Authors: Elan Rosenfeld, Nir Rosenfeld,
• Abstract要約: 戦略的分類の目標は、戦略的入力に対して堅牢な決定ルールを学ぶことである。 広範囲のコストに対して、ユーザコスト関数の小さな誤推定でさえ、最悪の場合、自明な精度を伴う可能性があることを示す。 我々の理論応答は、戦略応答、特に双対ノルム正規化の値から生じる重要な構造を明らかにする。
• 参考スコア（独自算出の注目度）: 19.390528752448283
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The goal of strategic classification is to learn decision rules which are robust to strategic input manipulation. Earlier works assume that these responses are known; while some recent works handle unknown responses, they exclusively study online settings with repeated model deployments. But there are many domains$\unicode{x2014}$particularly in public policy, a common motivating use case$\unicode{x2014}$where multiple deployments are infeasible, or where even one bad round is unacceptable. To address this gap, we initiate the formal study of one-shot strategic classification under unknown responses, which requires committing to a single classifier once. Focusing on uncertainty in the users' cost function, we begin by proving that for a broad class of costs, even a small mis-estimation of the true cost can entail trivial accuracy in the worst case. In light of this, we frame the task as a minimax problem, with the goal of identifying the classifier with the smallest worst-case risk over an uncertainty set of possible costs. We design efficient algorithms for both the full-batch and stochastic settings, which we prove converge (offline) to the minimax solution at the dimension-independent rate of $\tilde{\mathcal{O}}(T^{-\frac{1}{2}})$. Our theoretical analysis reveals important structure stemming from strategic responses, particularly the value of dual norm regularization with respect to the cost function.
• Abstract（参考訳）: 戦略的分類の目標は、戦略的入力操作に堅牢な決定ルールを学習することである。 いくつかの最近の研究は未知のレスポンスを扱うが、彼らは反復的なモデル展開でオンライン設定を独占的に研究している。 しかし、パブリックポリシーでは、多くのドメインがある:$\unicode{x2014}$ 特に、共通のモチベーションのユースケース$\unicode{x2014}$複数のデプロイメントが実現不可能、あるいは、1つの悪いラウンドが受け入れられない。 このギャップに対処するために、未知の応答下でのワンショット戦略分類の正式な研究を開始し、1つの分類器に1回コミットする必要がある。 利用者のコスト関数の不確実性に着目して、広範囲のコストに対して、たとえ真のコストの小さな誤推定であっても、最悪の場合、自明な精度が伴うことを証明することから始める。 これを踏まえて,本課題を最小限の問題とみなし,可能なコストの不確実性に対して最小の最悪のリスクで分類器を識別することを目的とする。 我々は、全バッチおよび確率的設定の両方に対して効率的なアルゴリズムを設計し、$\tilde{\mathcal{O}}(T^{-\frac{1}{2}})$の次元非依存速度でミニマックス解に収束する(オフライン)ことを証明した。 我々の理論解析は、戦略的応答、特にコスト関数に対する双対ノルム正規化の値から生じる重要な構造を明らかにする。

関連論文リスト

• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• 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)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  我々は、敵対コストと既知の移行で最短経路問題を研究します。 ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T20:55:28Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Minimum discrepancy principle strategy for choosing $k$ in $k$-NN regression [2.0411082897313984]
  保持データを用いずに、$k$-NN回帰推定器でハイパーパラメータ$k$を選択するための新しいデータ駆動戦略を提案する。 本稿では,早期停止と最小一致原理に基づく実践的戦略を実践的に容易に導入することを提案する。
  論文  参考訳（メタデータ） (2020-08-20T00:13:19Z)
• Estimating Principal Components under Adversarial Perturbations [25.778123431786653]
  本研究では,高次元統計的推定問題に対するロバストネスの自然なモデルについて検討する。 我々のモデルは、低精度機械学習や対人訓練といった新しいパラダイムによって動機付けられている。
  論文  参考訳（メタデータ） (2020-05-31T20:27:19Z)

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

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