論文の概要: Data Sharing for Mean Estimation Among Heterogeneous Strategic Agents
- arxiv url: http://arxiv.org/abs/2407.15881v1
- Date: Sat, 20 Jul 2024 17:45:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 21:44:53.218633
- Title: Data Sharing for Mean Estimation Among Heterogeneous Strategic Agents
- Title（参考訳）: 不均一な戦略エージェント間の平均値推定のためのデータ共有
- Authors: Alex Clinton, Yiding Chen, Xiaojin Zhu, Kirthevasan Kandasamy,
- Abstract要約: 通常の分布からサンプルを収集することにより,$m$エージェントがベクトル$muinmathbbRd$を推定する協調学習問題について検討する。
独自の作業を行う代わりに、エージェントはコストの安いデータを収集し、それと引き換えに他のデータと共有することができる。
- 参考スコア（独自算出の注目度）: 11.371461065112422
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a collaborative learning problem where $m$ agents estimate a vector $\mu\in\mathbb{R}^d$ by collecting samples from normal distributions, with each agent $i$ incurring a cost $c_{i,k} \in (0, \infty]$ to sample from the $k^{\text{th}}$ distribution $\mathcal{N}(\mu_k, \sigma^2)$. Instead of working on their own, agents can collect data that is cheap to them, and share it with others in exchange for data that is expensive or even inaccessible to them, thereby simultaneously reducing data collection costs and estimation error. However, when agents have different collection costs, we need to first decide how to fairly divide the work of data collection so as to benefit all agents. Moreover, in naive sharing protocols, strategic agents may under-collect and/or fabricate data, leading to socially undesirable outcomes. Our mechanism addresses these challenges by combining ideas from cooperative and non-cooperative game theory. We use ideas from axiomatic bargaining to divide the cost of data collection. Given such a solution, we develop a Nash incentive-compatible (NIC) mechanism to enforce truthful reporting. We achieve a $\mathcal{O}(\sqrt{m})$ approximation to the minimum social penalty (sum of agent estimation errors and data collection costs) in the worst case, and a $\mathcal{O}(1)$ approximation under favorable conditions. We complement this with a hardness result, showing that $\Omega(\sqrt{m})$ is unavoidable in any NIC mechanism.
- Abstract（参考訳）: 通常の分布からサンプルを収集することにより,$m$エージェントがベクトル$\mu\in\mathbb{R}^d$を推定する協調学習問題を,$k^{\text{th}}$ distribution$\mathcal{N}(\mu_k, \sigma^2)$から,コスト$c_{i,k} \in (0, \infty]$からサンプルを得るために,各エージェント$i$を用いて検討する。
独自の作業を行う代わりに、エージェントはコストの安いデータを収集し、それと引き換えに他のデータと共有することができる。
しかしながら、エージェントが異なるコレクションコストを持つ場合には、まず、すべてのエージェントに利益をもたらすために、データコレクションの作業を適切に分割する方法を決定する必要があります。
さらに、ナイーブな共有プロトコルでは、戦略的エージェントはデータの収集や作成を過小評価し、社会的に望ましくない結果をもたらす可能性がある。
本機構は,協調ゲーム理論と非協調ゲーム理論のアイデアを組み合わせることで,これらの課題に対処する。
私たちは、データ収集のコストを分配するために、公理交渉のアイデアを使用します。
このようなソリューションを前提として、真に報告を強制するためのNashインセンティブ互換(NIC)メカニズムを開発する。
我々は、最悪の場合、最小限の社会的ペナルティ(エージェント推定エラーとデータ収集コストの仮定)に対する$\mathcal{O}(\sqrt{m})$近似と、好ましい条件下での$\mathcal{O}(1)$近似を達成する。
我々はこれをハードネスの結果で補完し、$\Omega(\sqrt{m})$が任意のNICメカニズムでは避けられないことを示す。
関連論文リスト
- Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。
我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。
我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
論文 参考訳（メタデータ） (2024-10-22T19:34:53Z) - Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Collaboratively Learning Linear Models with Structured Missing Data [3.4376560669160394]
我々は、$magentsの最小二乗推定問題について検討する。
我々のゴールは、各エージェントに最適な推定器を生成するために、学習中のエージェントを協調させる方法を決定することである。
論文 参考訳（メタデータ） (2023-07-22T00:07:10Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Impact of Redundancy on Resilience in Distributed Optimization and
Learning [4.664766612388049]
本稿では,サーバアーキテクチャにおける分散最適化と学習のレジリエンスの問題について考察する。
システムはサーバと複数のエージェントから構成され、各エージェントは独自のローカルコスト関数を持つ。
局所コスト関数が十分冗長であることを考えると、実際に$(f, r; epsilon)$-レジリエンスが達成できることが示される。
論文 参考訳（メタデータ） (2022-11-16T02:23:34Z) - Mechanisms that Incentivize Data Sharing in Federated Learning [90.74337749137432]
我々は、データ共有の利点が完全に損なわれているような、ナイーブなスキームが破滅的なフリーライディングのレベルにどのように結びつくかを示す。
次に,各エージェントが生成するデータ量を最大化する精度形成機構を導入する。
論文 参考訳（メタデータ） (2022-07-10T22:36:52Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - A Provably Efficient Sample Collection Strategy for Reinforcement
Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。
1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文 参考訳（メタデータ） (2020-07-13T15:17:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。