論文の概要: Zero-Regret Performative Prediction Under Inequality Constraints
- arxiv url: http://arxiv.org/abs/2309.12618v1
- Date: Fri, 22 Sep 2023 04:54:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-25 16:01:40.058930
- Title: Zero-Regret Performative Prediction Under Inequality Constraints
- Title（参考訳）: 不等式制約下におけるゼロレグレット実効予測
- Authors: Wenjing Yan and Xuanyu Cao
- Abstract要約: 本稿では不等式制約下での性能予測について検討する。
我々は,ある程度の精度しか必要としない頑健な原始双対フレームワークを開発する。
次に、位置ファミリに対する適応的原始双対アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 5.513958040574729
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Performative prediction is a recently proposed framework where predictions
guide decision-making and hence influence future data distributions. Such
performative phenomena are ubiquitous in various areas, such as transportation,
finance, public policy, and recommendation systems. To date, work on
performative prediction has only focused on unconstrained scenarios, neglecting
the fact that many real-world learning problems are subject to constraints.
This paper bridges this gap by studying performative prediction under
inequality constraints. Unlike most existing work that provides only
performative stable points, we aim to find the optimal solutions. Anticipating
performative gradients is a challenging task, due to the agnostic performative
effect on data distributions. To address this issue, we first develop a robust
primal-dual framework that requires only approximate gradients up to a certain
accuracy, yet delivers the same order of performance as the stochastic
primal-dual algorithm without performativity. Based on this framework, we then
propose an adaptive primal-dual algorithm for location families. Our analysis
demonstrates that the proposed adaptive primal-dual algorithm attains
$\ca{O}(\sqrt{T})$ regret and constraint violations, using only $\sqrt{T} + 2T$
samples, where $T$ is the time horizon. To our best knowledge, this is the
first study and analysis on the optimality of the performative prediction
problem under inequality constraints. Finally, we validate the effectiveness of
our algorithm and theoretical results through numerical simulations.
- Abstract（参考訳）: performanceative predictionは、最近提案されたフレームワークで、予測は意思決定を導き、将来のデータ分布に影響を与える。
このような行動現象は、交通、金融、公共政策、レコメンデーションシステムなど、様々な分野で広く見られる。
現在まで、パフォーマンス予測の研究は制約のないシナリオにのみ焦点を合わせており、現実の学習問題の多くが制約の対象となっているという事実を無視している。
本稿では,不等式制約下での性能予測を研究することにより,このギャップを埋める。
性能安定点のみを提供する既存の作業とは異なり、最適解を見つけることを目指している。
パフォーマンス勾配の予測は、データ分布に対する非依存なパフォーマンス効果のため、難しい課題である。
この問題に対処するために,我々はまず,一定の精度まで近似勾配しか必要とせず,かつ,確率的プライマル・デュアルアルゴリズムと同等の性能を提供するロバストなプリマル・デュアル・フレームワークを開発した。
この枠組みに基づき,位置族に対する適応的原始双対アルゴリズムを提案する。
解析により,提案アルゴリズムは,時間的地平線が$T$である場合,$\sqrt{T} + 2T$サンプルのみを用いて,後悔と制約違反に対して$\ca{O}(\sqrt{T})を達成できることが示されている。
最善の知識は,不等式制約下における実効予測問題の最適性に関する最初の研究と解析である。
最後に,数値シミュレーションによりアルゴリズムの有効性と理論的結果を検証する。
関連論文リスト
- Fair Secretaries with Unfair Predictions [12.756552522270198]
予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。
私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
論文 参考訳（メタデータ） (2024-11-15T00:23:59Z) - Online Fair Allocation of Perishable Resources [1.4952056744888913]
我々は、標準オンラインフェアアロケーション問題の事実上の動機付け型を考察する。
意思決定者は、一定回数のラウンドを割り当てるために、パーシシブルなリソースの予算を持っている。
目標は、うらやましいほど効率的で効率的なアロケーションのシーケンスを構築することです。
論文 参考訳（メタデータ） (2024-06-04T15:14:10Z) - Non-clairvoyant Scheduling with Partial Predictions [17.387787159892287]
本稿では, 頑健性, 一貫性, 滑らかさの基準を満たす学習補助アルゴリズムを提案する。
また,予測数を制限するシナリオに固有の一貫性と滑らかさの新たなトレードオフも提示する。
論文 参考訳（メタデータ） (2024-05-02T05:29:22Z) - Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model [16.466711636334587]
オンライン意思決定者は、到着や要求など、将来の変数に関する予測を得ることが多い。
意思決定者にとって予測精度は未知であるため、予測に盲目的に追従することは有害である。
我々は未知の予測精度に頑健な方法で予測を利用するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-21T04:57:32Z) - Source-Free Unsupervised Domain Adaptation with Hypothesis Consolidation
of Prediction Rationale [53.152460508207184]
Source-Free Unsupervised Domain Adaptation (SFUDA)は、モデルがターゲットのドメインラベルやソースドメインデータにアクセスせずに新しいドメインに適応する必要がある、という課題である。
本稿では,各サンプルについて複数の予測仮説を考察し,各仮説の背景にある理論的根拠について考察する。
最適性能を達成するために,モデル事前適応,仮説統合,半教師付き学習という3段階の適応プロセスを提案する。
論文 参考訳（メタデータ） (2024-02-02T05:53:22Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳（メタデータ） (2022-02-22T18:37:23Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Bayes DistNet -- A Robust Neural Network for Algorithm Runtime
Distribution Predictions [1.8275108630751844]
ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。
従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。
この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
論文 参考訳（メタデータ） (2020-12-14T01:15:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。