論文の概要: Regret Bounds for Competitive Resource Allocation with Endogenous Costs
- arxiv url: http://arxiv.org/abs/2603.18999v1
- Date: Thu, 19 Mar 2026 15:04:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-20 17:19:06.216108
- Title: Regret Bounds for Competitive Resource Allocation with Endogenous Costs
- Title（参考訳）: 内因性コストを考慮した競争資源配分のためのレグレトバウンド
- Authors: Rui Chai,
- Abstract要約: 我々は,Tラウンド上での相互作用モジュール間のオンラインリソース割り当てについて検討した。
通常のオンライン最適化とは異なり、コストは内在的であり、それらはペアの協調と競合を符号化する相互作用行列Wを介して完全な割り当てベクトルに依存する。
- 参考スコア（独自算出の注目度）: 2.182298024908194
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study online resource allocation among N interacting modules over T rounds. Unlike standard online optimization, costs are endogenous: they depend on the full allocation vector through an interaction matrix W encoding pairwise cooperation and competition. We analyze three paradigms: (I) uniform allocation (cost-ignorant), (II) gated allocation (cost-estimating), and (III) competitive allocation via multiplicative weights update with interaction feedback (cost-revealing). Our main results establish a strict separation under adversarial sequences with bounded variation: uniform incurs Omega(T) regret, gated achieves O(T^{2/3}), and competitive achieves O(sqrt(T log N)). The performance gap stems from competitive allocation's ability to exploit endogenous cost information revealed through interactions. We further show that W's topology governs a computation-regret tradeoff. Full interaction (|E|=O(N^2)) yields the tightest bound but highest per-step cost, while sparse topologies (|E|=O(N)) increase regret by at most O(sqrt(log N)) while reducing per-step cost from O(N^2) to O(N). Ring-structured topologies with both cooperative and competitive links - of which the five-element Wuxing topology is canonical - minimize the computation x regret product. These results provide the first formal regret-theoretic justification for decentralized competitive allocation in modular architectures and establish cost endogeneity as a fundamental challenge distinct from partial observability. Keywords: online learning, regret bounds, resource allocation, endogenous costs, interaction topology, multiplicative weights, modular systems, Wuxing topology
- Abstract（参考訳）: 我々は,Tラウンド上での相互作用モジュール間のオンラインリソース割り当てについて検討した。
通常のオンライン最適化とは異なり、コストは内在的であり、それらはペアの協調と競合を符号化する相互作用行列Wを介して完全な割り当てベクトルに依存する。
我々は, (I) 均一割当(コスト非依存), (II) ゲート割当(コスト推定), (III) 相互作用フィードバック(コスト回収)による乗算重み更新による競合割当の3つのパラダイムを解析した。
本研究の主な成果は,Omega(T) が一様で,O(T^{2/3}) が成立し,競合が O(sqrt(T log N)) となるような,有界な変動を持つ逆列の下で厳密な分離を確立することである。
パフォーマンスギャップは、競合アロケーションが、相互作用を通じて明らかになった内因性コスト情報を利用する能力に起因している。
さらに、W の位相が計算-回帰トレードオフを支配していることを示す。
完全な相互作用 (|E|=O(N^2)) は最も厳密な境界を持つが、最も高いステップ毎のコストをもたらすが、スパース位相 (|E|=O(N)) は、O(sqrt(log N)) が最大で、O(N^2) から O(N) へのステップ毎のコストを減少させる。
5要素のWuxingトポロジが正準であるような、協調的および競合的なリンクを持つリング構造化トポロジは、計算 x の後悔積を最小化する。
これらの結果は、モジュラーアーキテクチャにおける分散的な競合アロケーションに対する最初の公式な後悔-理論の正当性を提供し、部分的可観測性とは異なる根本的な課題としてコスト内在性を確立する。
キーワード:オンライン学習、後悔境界、資源配分、内因性コスト、相互作用トポロジ、乗法重み、モジュラーシステム、ワックストポロジ
関連論文リスト
- SeqTG: Scalable Combinatorial Test Generation via Sequential Integer Linear Programming [9.092621106269503]
複雑な制約下での最小限のカバレッジ配列は、未解決のNPハードチャレンジのままである。
現在の強欲なアルゴリズムは、非常に欲求的だが、深刻なリターンの低下に苦しむ。それらは、初期相互作用を効率的にカバーするが、最後のいくつかの困難なペアをまとめるのに苦労するときに、肥大した冗長なテストスイートを生成する。
シークエンシャル線形プログラミング(ILP)に基づくスケーラブルなフレームワークであるSeqTGを紹介する。
本稿では,SeqTGが最新の肥大を効果的に根絶し,最先端のテストスイートのコンパクト性と厳密な制約順守を実現していることを示す。
論文 参考訳（メタデータ） (2026-03-14T14:18:43Z) - Online Linear Programming with Replenishment [9.214452378957697]
オンライン線形プログラミング(OLP)モデルについて検討し、在庫を事前に提供せず、補充プロセスを通じて徐々に到着する。
分散された不確実な補充の導入は、古典的なALPの構造を根本的に変える。
我々は,ALP文献で研究されている3つの主要な分布系について,新しいアルゴリズムと後悔の分析法を開発した。
論文 参考訳（メタデータ） (2026-01-21T04:09:29Z) - Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency [15.330129666665927]
接続性を考慮したスペーシフィケーションフレームワークである textbfCo-Sparsify を提案する。
私たちのキーとなる洞察は、3ノードの相互作用は、エンファンビコネクテッドなコンポーネントの中でのみ、表現的に必要であるということです。
Co-Sparsify は 2-FWL テストと同じくらい表現力があることを示す。
論文 参考訳（メタデータ） (2025-11-16T23:46:54Z) - Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
ハーフスペースの交叉学習は計算学習理論における中心的な問題である。
たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。
本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-11-13T00:28:24Z) - Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks [19.642496463491053]
我々は、オンラインバイナリ分類を再考し、最良クラスのバイナリ損失との競合から、緩やかなベンチマークとの競合へと焦点を移した。
我々は、小さな入力摂動に対して頑健な予測器の比較、ガウス平滑化下での良好な性能、あるいは所定の出力マージンを維持することを検討する。
我々のアルゴリズムは、VC次元とインスタンス空間の複雑さにのみ依存する後悔の保証を達成する。
論文 参考訳（メタデータ） (2025-04-14T18:00:23Z) - Localized Physics-informed Gaussian Processes with Curriculum Training for Topology Optimization [3.6352820455705372]
物理インフォームドガウス過程(GP)に基づく同時かつメッシュフリーなトポロジー最適化(TO)フレームワークを提案する。
我々のフレームワークは、カスタマイズされたディープニューラルネットワーク(DNN)を介してパラメータ化される共有のマルチアウトプット平均関数を持つGPプリエントを介して、すべての設計と状態変数を提供する。
我々のTOアプローチは、適切に定義された材料インターフェースを生成し、グローバルな最適性を促進するための継続特性を内蔵している。
論文 参考訳（メタデータ） (2025-03-18T22:59:16Z) - On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
我々は,100万ドル以上の分散データを用いたオンラインモデル選択について検討し,クライアント間のコラボレーションの必要性について検討する。
i) クライアント上の計算コストが$o(K)$に制限された場合, (ii) クライアント上での計算制約がない場合, (i) 協調は不要であり, (ii) クライアント上での計算コストは$o(K)$に制限される。
論文 参考訳（メタデータ） (2024-04-15T06:32:28Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳（メタデータ） (2021-11-11T01:19:53Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。