論文の概要: Online Resource Allocation with Non-Stationary Customers
- arxiv url: http://arxiv.org/abs/2401.16945v1
- Date: Tue, 30 Jan 2024 12:19:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-31 15:22:33.106679
- Title: Online Resource Allocation with Non-Stationary Customers
- Title(参考訳): 非定常顧客によるオンラインリソース割り当て
- Authors: Xiaoyue Zhang, Hanzhang Qin, Mabel C. Chou
- Abstract要約: 非定常的な顧客到着率と未知のクリックスルー率を持つオンラインリソースアロケーションのための新しいアルゴリズムを提案する。
さまざまな顧客シナリオに対して,アプローチが最適に近い収益を生み出すことを示すため,広範な数値実験を実施している。
- 参考スコア(独自算出の注目度): 1.4886278504056065
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel algorithm for online resource allocation with
non-stationary customer arrivals and unknown click-through rates. We assume
multiple types of customers arrive in a nonstationary stochastic fashion, with
unknown arrival rates in each period, and that customers' click-through rates
are unknown and can only be learned online. By leveraging results from the
stochastic contextual bandit with knapsack and online matching with adversarial
arrivals, we develop an online scheme to allocate the resources to
nonstationary customers. We prove that under mild conditions, our scheme
achieves a ``best-of-both-world'' result: the scheme has a sublinear regret
when the customer arrivals are near-stationary, and enjoys an optimal
competitive ratio under general (non-stationary) customer arrival
distributions. Finally, we conduct extensive numerical experiments to show our
approach generates near-optimal revenues for all different customer scenarios.
- Abstract(参考訳): 非定常顧客到着率と未知クリックスルー率を持つオンラインリソース割り当てのための新しいアルゴリズムを提案する。
複数の顧客が非定常の確率的方法で到着し、各期間に未知の到着率を持ち、顧客のクリックスルー率は未知であり、オンラインでしか学べないと仮定する。
Knapsackによる確率的文脈的バンディットと、敵の到着とオンラインマッチングの結果を活用することで、非定常顧客に対してリソースを割り当てるオンラインスキームを開発する。
提案手法は, 利用者の到着がほぼ静止状態である場合に, サブリニアな後悔を伴い, 一般の(静止していない)顧客到着分布の下で最適な競争比率を享受する。
最後に,提案手法があらゆる顧客シナリオに最適に近い収益をもたらすことを示すために,広範な数値実験を行った。
関連論文リスト
- Greedy Shapley Client Selection for Communication-Efficient Federated
Learning [32.38170282930876]
フェデレートラーニング(FL)のための標準的なクライアント選択アルゴリズムは、しばしばバイアスがなく、クライアントのランダムサンプリングが一様である。
私たちは、各通信ラウンドで最も貢献するクライアントを特定し、優しく選択する、バイアスのあるクライアント選択戦略であるGreedyFedを開発します。
複数の実世界のデータセット上のさまざまなクライアント選択戦略と比較して、GreedyFedは、タイミング制約の下で高い精度で高速で安定した収束を示す。
論文 参考訳(メタデータ) (2023-12-14T16:44:38Z) - Multi-Criteria Client Selection and Scheduling with Fairness Guarantee
for Federated Learning Service [17.986744632466515]
フェデレートラーニング(FL)は、複数のクライアントが生のトレーニングデータを共有せずに、機械学習モデルを協調的にトレーニングすることを可能にする。
公平性を保証するマルチ基準クライアント選択とスケジューリング方式を提案する。
我々のスキームは、特にデータが非IDである場合、モデル品質を改善することができる。
論文 参考訳(メタデータ) (2023-12-05T16:56:24Z) - When to Trust Aggregated Gradients: Addressing Negative Client Sampling
in Federated Learning [41.51682329500003]
本稿では,各ラウンドにおける集約勾配に対するサーバ学習率を調整するための新しい学習率適応機構を提案する。
我々は、最適なサーバ学習率に肯定的な有意義で堅牢な指標を見つけるために、理論的な推論を行う。
論文 参考訳(メタデータ) (2023-01-25T03:52:45Z) - Federated Graph-based Sampling with Arbitrary Client Availability [34.95352685954059]
本稿では,FedGS(Federated Graph-based Smpling)というフレームワークを提案する。
実験結果から,FedGSが公正なクライアントサンプリング方式を実現し,任意のクライアントアベイラビリティの下でモデル性能を向上させるという利点が確認できた。
論文 参考訳(メタデータ) (2022-11-25T09:38:20Z) - Fed-CBS: A Heterogeneity-Aware Client Sampling Mechanism for Federated
Learning via Class-Imbalance Reduction [76.26710990597498]
本研究では,ランダムに選択したクライアントからのグループデータのクラス不均衡が,性能の大幅な低下につながることを示す。
我々のキーとなる観測に基づいて、我々は効率的なクライアントサンプリング機構、すなわちフェデレートクラスバランスサンプリング(Fed-CBS)を設計する。
特に、クラス不均衡の尺度を提案し、その後、同型暗号化を用いてプライバシー保護方式でこの尺度を導出する。
論文 参考訳(メタデータ) (2022-09-30T05:42:56Z) - Straggler-Resilient Personalized Federated Learning [55.54344312542944]
フェデレーション学習は、プライバシと通信の制限を尊重しながら、クライアントの大規模なネットワークに分散されたサンプルからのトレーニングモデルを可能にする。
これら2つのハードルを同時に処理する理論的なスピードアップを保証する新しいアルゴリズム手法を開発した。
提案手法は,すべてのクライアントのデータを用いてグローバルな共通表現を見つけ,各クライアントに対してパーソナライズされたソリューションにつながるパラメータの集合を学習するために,表現学習理論からのアイデアに依存している。
論文 参考訳(メタデータ) (2022-06-05T01:14:46Z) - Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。
エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。
我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
論文 参考訳(メタデータ) (2022-06-01T00:44:53Z) - Two-Stage Facility Location Games with Strategic Clients and Facilities [64.89284690002836]
施設と顧客の両方が戦略的かつ大きな影響を与える非協力的な施設配置ゲームについて考察する。
当社のモデルでは,各施設の場所は,顧客を引き寄せる集合体を持ち,各クライアントは,その消費能力に応じた一組のショッピングロケーションと重みを有する。
我々は,準ゲーム完全平衡が存在することを示し,無政府価格と安定価格にほぼ一定の定数を与える。
論文 参考訳(メタデータ) (2021-05-04T11:27:09Z) - Non-Stationary Latent Bandits [68.21614490603758]
非定常ユーザに対して高速なパーソナライズのための実践的アプローチを提案する。
鍵となる考え方は、この問題を潜在バンディットとみなすことであり、ユーザ行動のプロトタイプモデルがオフラインで学習され、ユーザの潜伏状態がオンラインで推論される。
我々は,非定常潜伏帯域における後悔最小化のためのトンプソンサンプリングアルゴリズムを提案し,それらを解析し,実世界のデータセット上で評価する。
論文 参考訳(メタデータ) (2020-12-01T10:31:57Z) - Client Selection in Federated Learning: Convergence Analysis and
Power-of-Choice Selection Strategies [29.127689561987964]
フェデレートラーニングにより、多数のリソース制限されたクライアントノードが、データ共有なしで協調的にモデルをトレーニングできる。
局所的損失の高いクライアントに対するクライアント選択の偏りは、より高速なエラー収束を実現することを示す。
通信および計算効率の高いクライアント選択フレームワークであるPower-of-Choiceを提案する。
論文 参考訳(メタデータ) (2020-10-03T01:04:17Z) - Distributed Non-Convex Optimization with Sublinear Speedup under
Intermittent Client Availability [46.85205907718874]
フェデレーション学習は新しい機械学習フレームワークで、多くのクライアントがトレーニングデータを共有することなく、協力的にモデルをトレーニングする。
本研究では,間欠的なモバイル環境におけるフェデレーション学習の実践と課題について考察する。
我々はFedLaAvg(略してFedLaAvg)と呼ばれる単純な分散非線形最適化アルゴリズムを提案する。
我々の理論的解析は、FedLaAvgが$(E1/2/(NT1/2)$の収束率に達し、クライアントの総数に対してサブ線形速度を達成することを示している。
論文 参考訳(メタデータ) (2020-02-18T06:32:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。