論文の概要: Online Learning with Cumulative Oversampling: Application to Budgeted
Influence Maximization
- arxiv url: http://arxiv.org/abs/2004.11963v3
- Date: Wed, 16 Sep 2020 01:51:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-10 03:17:32.697155
- Title: Online Learning with Cumulative Oversampling: Application to Budgeted
Influence Maximization
- Title(参考訳): 累積オーバーサンプリングによるオンライン学習:予算効果最大化への応用
- Authors: Shatian Wang, Shuoguang Yang, Zhen Xu, Van-Anh Truong
- Abstract要約: オンライン学習のための累積オーバー(CO)手法を提案する。
私たちのキーとなるアイデアは、各ラウンドで一度更新された信念空間からパラメータ推定をサンプリングすることです。
IMの半帯域に対して,我々のCOベースのアルゴリズムは,理論上はUPBベースのアルゴリズムに匹敵する規模の後悔を達成できることを示す。
- 参考スコア(独自算出の注目度): 7.893654261799925
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a cumulative oversampling (CO) method for online learning. Our key
idea is to sample parameter estimations from the updated belief space once in
each round (similar to Thompson Sampling), and utilize the cumulative samples
up to the current round to construct optimistic parameter estimations that
asymptotically concentrate around the true parameters as tighter upper
confidence bounds compared to the ones constructed with standard UCB methods.
We apply CO to a novel budgeted variant of the Influence Maximization (IM)
semi-bandits with linear generalization of edge weights, whose offline problem
is NP-hard. Combining CO with the oracle we design for the offline problem, our
online learning algorithm simultaneously tackles budget allocation, parameter
learning, and reward maximization. We show that for IM semi-bandits, our
CO-based algorithm achieves a scaled regret comparable to that of the UCB-based
algorithms in theory, and performs on par with Thompson Sampling in numerical
experiments.
- Abstract(参考訳): オンライン学習のための累積オーバーサンプリング(CO)手法を提案する。
我々のキーとなる考え方は、各ラウンドで一度更新された信念空間からパラメータ推定をサンプリングし(トンプソンサンプリングと同様)、現在のラウンドまで累積サンプルを用いて、標準 UCB 法で構築されたものと比較して、真のパラメータの周りに漸近的に集中する楽観的なパラメータ推定を構築することである。
我々は, エッジウェイトを線形に一般化した影響最大化(IM)半帯域の新たな予算付き変種にCOを適用し, オフライン問題はNPハードである。
オフライン問題のために設計したオラクルとCOを組み合わせることで、オンライン学習アルゴリズムは予算配分、パラメータ学習、報酬の最大化に同時に取り組みます。
IMの半帯域に対して,我々のCOベースのアルゴリズムは理論上のUTBベースのアルゴリズムに匹敵する規模の後悔を達成し,数値実験でトンプソンサンプリングと同等に動作することを示す。
関連論文リスト
- Minimizing the Thompson Sampling Regret-to-Sigma Ratio (TS-RSR): a
provably efficient algorithm for batch Bayesian Optimization [5.461310760509014]
我々の目標は、不確実点間の冗長性を最小化する方法で、各バッチで選択されたアクションを調整できることです。
予測バッチアルゴリズムにおいて、最先端の理論的保証を提供する。
論文 参考訳(メタデータ) (2024-03-07T18:58:26Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳(メタデータ) (2023-05-29T17:25:26Z) - Multivariate Probabilistic CRPS Learning with an Application to
Day-Ahead Electricity Prices [0.0]
本稿では,多変量確率予測を結合(あるいは集約)する新しい手法を提案する。
オンライン学習を可能にするスムーズな手続きを通じて、量子と限界の間の依存関係を考察する。
提案アルゴリズムの高速なC++実装は、CRAN上のオープンソースのR-Package profocで提供される。
論文 参考訳(メタデータ) (2023-03-17T14:47:55Z) - Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
Annealed Importance Smpling (AIS) は、深層生成モデルの難易度を推定するために使われる一般的なアルゴリズムである。
本稿では、フレキシブルな中間分布を持つパラメータAISプロセスを提案し、サンプリングに少ないステップを使用するようにブリッジング分布を最適化する。
我々は, 最適化AISの性能評価を行い, 深部生成モデルの限界推定を行い, 他の推定値と比較した。
論文 参考訳(メタデータ) (2022-09-27T07:58:25Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳(メタデータ) (2022-09-16T19:15:50Z) - A Stochastic Bundle Method for Interpolating Networks [18.313879914379008]
本稿では,実験的な損失をゼロにすることができるディープニューラルネットワークのトレーニング手法を提案する。
各イテレーションにおいて,本手法は目的学習近似のバンドルとして知られる最大線形近似を構成する。
論文 参考訳(メタデータ) (2022-01-29T23:02:30Z) - Adaptive Client Sampling in Federated Learning via Online Learning with
Bandit Feedback [36.05851452151107]
統合学習(FL)システムは、トレーニングの各ラウンドに関与するクライアントのサブセットをサンプリングする必要があります。
その重要性にもかかわらず、クライアントを効果的にサンプリングする方法には制限がある。
提案手法は,最適化アルゴリズムの収束速度をいかに向上させるかを示す。
論文 参考訳(メタデータ) (2021-12-28T23:50:52Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳(メタデータ) (2021-04-09T14:50:59Z) - Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes [4.355567556995855]
ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。
標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
論文 参考訳(メタデータ) (2021-03-23T00:28:15Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。