論文の概要: One-Shot Strategic Classification Under Unknown Costs
- arxiv url: http://arxiv.org/abs/2311.02761v1
- Date: Sun, 5 Nov 2023 20:43:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 16:03:48.614959
- Title: One-Shot Strategic Classification Under Unknown Costs
- Title(参考訳): 未知のコストによるワンショット戦略分類
- Authors: Elan Rosenfeld, Nir Rosenfeld
- Abstract要約: 分類の第一の目的は、戦略的入力に対して堅牢な決定ルールを学ぶことである。
不確実性の原因として,ユーザのコスト関数に注目した。
分析の結果,戦略的ユーザの反応から生じる重要な構造が明らかになった。
- 参考スコア(独自算出の注目度): 22.907341026741026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A primary goal in strategic classification is to learn decision rules which
are robust to strategic input manipulation. Earlier works assume that strategic
responses are known; while some recent works address the important challenge of
unknown responses, they exclusively study sequential settings which allow
multiple model deployments over time. But there are many
domains$\unicode{x2014}$particularly in public policy, a common motivating
use-case$\unicode{x2014}$where multiple deployments are unrealistic, or where
even a single bad round is undesirable. To address this gap, we initiate the
study of strategic classification under unknown responses in the one-shot
setting, which requires committing to a single classifier once. Focusing on the
users' cost function as the source of uncertainty, we begin by proving that for
a broad class of costs, even a small mis-estimation of the true cost can entail
arbitrarily low accuracy in the worst case. In light of this, we frame the
one-shot 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.
Our main contribution is efficient algorithms for both the full-batch and
stochastic settings, which we prove converge (offline) to the minimax optimal
solution at the dimension-independent rate of
$\tilde{\mathcal{O}}(T^{-\frac{1}{2}})$. Our analysis reveals important
structure stemming from the strategic nature of user responses, particularly
the importance of dual norm regularization with respect to the cost function.
- Abstract(参考訳): 戦略的分類の主要な目標は、戦略的な入力操作にロバストな決定ルールを学ぶことである。
いくつかの最近の研究は未知の応答の重要な課題に対処しているが、彼らは時間とともに複数のモデル展開を可能にするシーケンシャルな設定のみを研究している。
しかし、パブリックポリシーでは、多くのドメインがある:$\unicode{x2014}$ 特に、共通のモチベーションのユースケース$\unicode{x2014}$複数のデプロイメントが非現実的である、あるいは単一の悪いラウンドでさえ望ましくない。
このギャップに対処するため,我々は,単一分類子に一度コミットする必要がある一発設定において,未知の応答下での戦略的分類の研究を開始する。
不確実性の発生源としてのユーザのコスト関数に着目して、幅広いコストクラスにおいて、たとえ真コストの小さな誤評価であっても、最悪の場合、任意に低い精度が伴うことを証明し始める。
これを踏まえて、一発タスクを最小限の問題とみなし、可能なコストの不確実性セットに対して最小の最悪のリスクを持つ分類器を特定することを目的としている。
我々の主な貢献は、全バッチおよび確率的設定の両方に対する効率的なアルゴリズムであり、これは、$\tilde{\mathcal{O}}(T^{-\frac{1}{2}})$の次元非依存速度でミニマックス最適解に収束する(オフライン)ことを証明している。
分析の結果,ユーザ応答の戦略的性質,特にコスト関数に対する二重規範正規化の重要性に起因する重要な構造が明らかになった。
関連論文リスト
- Settling the Sample Complexity of Online Reinforcement Learning [100.52613756483589]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳(メタデータ) (2023-07-25T15:42:11Z) - Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning
with Linear Function Approximation [16.871660060209674]
本研究では, 線形関数近似を用いた展開効率向上強化学習(RL)の課題を, 遠近自由探索条件下で検討する。
我々は,最大$widetildeO(fracd2H5epsilon2)$ trajectoriesを$H$デプロイメント内で収集し,$epsilon$-Optimal Policyを任意の(おそらくはデータに依存した)報酬関数の選択に対して識別するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-03T03:48:26Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳(メタデータ) (2022-09-16T09:38:38Z) - Budgeted Classification with Rejection: An Evolutionary Method with
Multiple Objectives [0.0]
予算付きシーケンシャル分類器(BSC)プロセスは、部分的特徴取得と評価ステップのシーケンスを通じて入力を行う。
これにより、不要な特徴取得を防止するための入力の効率的な評価が可能になる。
本稿では,信頼度に基づく拒否オプション付き逐次分類器を構築するための問題固有遺伝的アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-05-01T22:05:16Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳(メタデータ) (2021-06-28T00:38:54Z) - 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) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z) - 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) - Estimating Principal Components under Adversarial Perturbations [25.778123431786653]
本研究では,高次元統計的推定問題に対するロバストネスの自然なモデルについて検討する。
我々のモデルは、低精度機械学習や対人訓練といった新しいパラダイムによって動機付けられている。
論文 参考訳(メタデータ) (2020-05-31T20:27:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。