論文の概要: The Pseudo-Dimension of Contracts
- arxiv url: http://arxiv.org/abs/2501.14474v1
- Date: Fri, 24 Jan 2025 13:13:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-27 14:57:29.461850
- Title: The Pseudo-Dimension of Contracts
- Title（参考訳）: 契約の擬似次元
- Authors: Paul Duetting, Michal Feldman, Tomasz Ponitka, Ermis Soumalias,
- Abstract要約: アルゴリズム契約設計は、主任がエージェントに彼女の代理として努力するよう動機付けるシナリオを研究する。
本研究では,エージェントの型が未知の分布から引き出される設定と,サンプルエージェントの型から最適に近いコントラクトを学習するためのオフライン学習フレームワークに焦点を当てる。
我々の分析における中心的なツールは、統計学習理論からの擬似次元の概念である。
- 参考スコア（独自算出の注目度）: 8.710927418537908
- License:
- Abstract: Algorithmic contract design studies scenarios where a principal incentivizes an agent to exert effort on her behalf. In this work, we focus on settings where the agent's type is drawn from an unknown distribution, and formalize an offline learning framework for learning near-optimal contracts from sample agent types. A central tool in our analysis is the notion of pseudo-dimension from statistical learning theory. Beyond its role in establishing upper bounds on the sample complexity, pseudo-dimension measures the intrinsic complexity of a class of contracts, offering a new perspective on the tradeoffs between simplicity and optimality in contract design. Our main results provide essentially optimal tradeoffs between pseudo-dimension and representation error (defined as the loss in principal's utility) with respect to linear and bounded contracts. Using these tradeoffs, we derive sample- and time-efficient learning algorithms, and demonstrate their near-optimality by providing almost matching lower bounds on the sample complexity. Conversely, for unbounded contracts, we prove an impossibility result showing that no learning algorithm exists. Finally, we extend our techniques in three important ways. First, we provide refined pseudo-dimension and sample complexity guarantees for the combinatorial actions model, revealing a novel connection between the number of critical values and sample complexity. Second, we extend our results to menus of contracts, showing that their pseudo-dimension scales linearly with the menu size. Third, we adapt our algorithms to the online learning setting, where we show that, a polynomial number of type samples suffice to learn near-optimal bounded contracts. Combined with prior work, this establishes a formal separation between expert advice and bandit feedback for this setting.
- Abstract（参考訳）: アルゴリズム契約設計は、主任がエージェントに彼女の代理として努力するよう動機付けるシナリオを研究する。
本研究では,エージェントの型が未知の分布から引き出されるような設定に着目し,サンプルエージェントの型から最適に近いコントラクトを学習するためのオフライン学習フレームワークを定式化する。
我々の分析における中心的なツールは、統計学習理論からの擬似次元の概念である。
サンプルの複雑さに関する上限を確立する上での役割に加えて、擬似次元は、一連の契約の固有の複雑さを測定し、契約設計における単純さと最適性の間のトレードオフに関する新たな視点を提供する。
我々の主な成果は、線形および有界な契約に対する擬次元と表現誤差(プリンシパルの効用における損失として定義される)の間の本質的に最適なトレードオフを提供する。
これらのトレードオフを利用して、サンプルと時間効率の学習アルゴリズムを導出し、サンプルの複雑さにほぼ一致する下限を提供することで、そのほぼ最適性を実証する。
逆に、非有界契約に対しては、学習アルゴリズムが存在しないことを示す不可能な結果が証明される。
最後に、我々のテクニックを3つの重要な方法で拡張する。
まず, 組み合わせ動作モデルに対して, 擬似次元と標本複雑性の保証を改良し, 臨界値の数とサンプル複雑性との新たな関係を明らかにする。
第2に,契約書のメニューに結果を拡張し,その擬似次元がメニューサイズと線形にスケールしていることを示す。
第三に、我々のアルゴリズムをオンライン学習環境に適応させ、そこでは、多項式数の型サンプルが最適に近い有界契約を学習するのに十分であることを示す。
以前の作業と組み合わせることで、専門家のアドバイスと、この設定に対する包括的フィードバックの正式な分離を確立します。
関連論文リスト
- Contractual Reinforcement Learning: Pulling Arms with Invisible Hands [68.77645200579181]
本稿では,契約設計によるオンライン学習問題において,利害関係者の経済的利益を整合させる理論的枠組みを提案する。
計画問題に対して、遠目エージェントに対する最適契約を決定するための効率的な動的プログラミングアルゴリズムを設計する。
学習問題に対して,契約の堅牢な設計から探索と搾取のバランスに至るまでの課題を解き放つために,非回帰学習アルゴリズムの汎用設計を導入する。
論文 参考訳（メタデータ） (2024-07-01T16:53:00Z) - New Perspectives in Online Contract Design [2.296475290901356]
本研究は, オンライン学習の観点から, 繰り返し主エージェント問題について考察する。
プリンシパルの目標は、反復的な相互作用を通じて彼女の効用を最大化する最適な契約を学ぶことである。
論文 参考訳（メタデータ） (2024-03-11T20:28:23Z) - Are Bounded Contracts Learnable and Approximately Optimal? [8.121834515103243]
本稿では,主エージェントが契約を用いてプロジェクトに取り組む動機付けを行う,主エージェント問題の隠れアクションモデルについて考察する。
本研究では,有界決済契約が学習可能か,ほぼ最適かを検討する。
論文 参考訳（メタデータ） (2024-02-22T12:19:19Z) - RGM: A Robust Generalizable Matching Model [49.60975442871967]
RGM(Robust Generalist Matching)と呼ばれる疎密マッチングのための深部モデルを提案する。
合成トレーニングサンプルと実世界のシナリオのギャップを狭めるために、我々は、疎対応基盤真理を持つ新しい大規模データセットを構築した。
さまざまな密集したスパースなデータセットを混ぜ合わせることができ、トレーニングの多様性を大幅に改善しています。
論文 参考訳（メタデータ） (2023-10-18T07:30:08Z) - Delegating Data Collection in Decentralized Machine Learning [67.0537668772372]
分散機械学習(ML)エコシステムの出現に動機付けられ,データ収集のデリゲートについて検討する。
我々は、2つの基本的な情報非対称性を扱う最適でほぼ最適な契約を設計する。
最適効用の1-1/e分を達成できるような単純な線形契約により、主成分がそのような非対称性に対処できることが示される。
論文 参考訳（メタデータ） (2023-09-04T22:16:35Z) - Faster Adaptive Federated Learning [84.38913517122619]
フェデレートラーニングは分散データの出現に伴って注目を集めている。
本稿では,クロスサイロFLにおけるモーメントに基づく分散低減手法に基づく適応アルゴリズム(FAFED)を提案する。
論文 参考訳（メタデータ） (2022-12-02T05:07:50Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Improved Robust Algorithms for Learning with Discriminative Feature
Feedback [21.58493386054356]
識別的特徴フィードバック(英: Discriminative Feature Feedback)は、人間の教師によって提供される特徴説明に基づく対話型学習のためのプロトコルである。
我々は、識別的特徴フィードバックモデルのための、新しい堅牢な対話型学習アルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-09-08T12:11:12Z) - Byzantine Resilient Distributed Multi-Task Learning [6.850757447639822]
タスク間の関連性を学習するための分散アルゴリズムは、ビザンティンエージェントの存在下では回復力がないことを示す。
ビザンチンレジリエントな分散マルチタスク学習のためのアプローチを提案する。
論文 参考訳（メタデータ） (2020-10-25T04:32:52Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。