論文の概要: 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})を達成できることが示されている。
最善の知識は,不等式制約下における実効予測問題の最適性に関する最初の研究と解析である。
最後に,数値シミュレーションによりアルゴリズムの有効性と理論的結果を検証する。
関連論文リスト
- 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) - Lazy Lagrangians with Predictions for Online Learning [24.18464455081512]
オンライン凸最適化における時間的差分制約による一般的な問題について考察する。
Follow-The-Regularized-Leaderイテレーションと予測適応動的ステップを組み合わせることで、新しい原始双対アルゴリズムを設計する。
我々の研究は、この制約されたOCO設定のためのFTRLフレームワークを拡張し、各最先端のグレディベースのソリューションより優れています。
論文 参考訳(メタデータ) (2022-01-08T21:49:10Z) - 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) - All of the Fairness for Edge Prediction with Optimal Transport [11.51786288978429]
グラフにおけるエッジ予測の課題に対する公平性の問題について検討する。
本稿では,任意のグラフの隣接行列に対して,グループと個々の公正性のトレードオフを伴う埋め込み非依存の補修手順を提案する。
論文 参考訳(メタデータ) (2020-10-30T15:33:13Z) - Scalable Approximate Inference and Some Applications [2.6541211006790983]
本稿では,近似推論のための新しいフレームワークを提案する。
提案する4つのアルゴリズムは,Steinの手法の最近の計算進歩に動機付けられている。
シミュレーションおよび実データを用いた結果から,アルゴリズムの統計的効率と適用性を示す。
論文 参考訳(メタデータ) (2020-03-07T04:33:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。