論文の概要: Online Influence Maximization: Concept and Algorithm
- arxiv url: http://arxiv.org/abs/2312.00099v1
- Date: Thu, 30 Nov 2023 15:24:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-04 17:02:10.113398
- Title: Online Influence Maximization: Concept and Algorithm
- Title（参考訳）: オンライン影響最大化:概念とアルゴリズム
- Authors: Jianxiong Guo
- Abstract要約: まず、オフラインIM問題を明確に定義する。
次に、オンラインIM問題と基本的なコンビニアル・マルチアーメッド・バンディット・フレームワークCMAB-Tの標準定義について述べる。
これはオンライン学習手法を用いてオンラインIM問題を解決する方法である。
- 参考スコア（独自算出の注目度）: 0.5801621787540268
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this survey, we offer an extensive overview of the Online Influence
Maximization (IM) problem by covering both theoretical aspects and practical
applications. For the integrity of the article and because the online algorithm
takes an offline oracle as a subroutine, we first make a clear definition of
the Offline IM problem and summarize those commonly used Offline IM algorithms,
which include traditional approximation or heuristic algorithms and ML-based
algorithms. Then, we give a standard definition of the Online IM problem and a
basic Combinatorial Multi-Armed Bandit (CMAB) framework, CMAB-T. Here, we
summarize three types of feedback in the CMAB model and discuss in detail how
to study the Online IM problem based on the CMAB-T model. This paves the way
for solving the Online IM problem by using online learning methods.
Furthermore, we have covered almost all Online IM algorithms up to now,
focusing on characteristics and theoretical guarantees of online algorithms for
different feedback types. Here, we elaborately explain their working principle
and how to obtain regret bounds. Besides, we also collect plenty of innovative
ideas about problem definition and algorithm designs and pioneering works for
variants of the Online IM problem and their corresponding algorithms. Finally,
we encapsulate current challenges and outline prospective research directions
from four distinct perspectives.
- Abstract（参考訳）: 本稿では,オンライン影響最大化(IM)問題について,理論的側面と実用性の両方を網羅して概観する。
記事の完全性とオンラインアルゴリズムは、オフラインのオラクルをサブルーチンとするため、まずオフラインIM問題を明確に定義し、従来の近似アルゴリズムやヒューリスティックアルゴリズム、MLベースのアルゴリズムを含む一般的なオフラインIMアルゴリズムを要約する。
次に、オンラインim問題に関する標準的な定義と、cmab(basic combinatorial multi-armed bandit)フレームワークcmab-tについて述べる。
本稿では,CMABモデルにおける3種類のフィードバックを要約し,CMAB-Tモデルに基づくオンラインIM問題の研究方法について詳細に考察する。
これはオンライン学習手法を用いてオンラインim問題を解決する方法だ。
さらに、オンラインimアルゴリズムのほとんどすべてをカバーし、様々なフィードバックタイプに対するオンラインアルゴリズムの特徴と理論的保証に焦点を当てている。
ここでは,その作業原理と後悔の限界の獲得方法について詳しく説明する。
さらに,問題定義やアルゴリズム設計に関するイノベーティブなアイデアや,オンラインim問題とその対応アルゴリズムの変種に対する先駆的な取り組みも数多く集めています。
最後に、現状の課題をカプセル化し、4つの異なる視点から研究の方向性を概説する。
関連論文リスト
- A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。
さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
論文 参考訳（メタデータ） (2024-06-05T18:39:28Z) - Understanding the performance gap between online and offline alignment algorithms [63.137832242488926]
オフラインのアルゴリズムは、ペアの分類が得意になるようにポリシーを訓練し、オンラインのアルゴリズムは世代ごとに良いことを示しています。
このことは、識別能力と生成能力の間のユニークな相互作用を示唆しており、これはサンプリングプロセスに大きく影響している。
我々の研究は、AIアライメントにおけるオンラインサンプリングの重要な役割に光を当て、オフラインアライメントアルゴリズムのある種の根本的な課題を示唆している。
論文 参考訳（メタデータ） (2024-05-14T09:12:30Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Online Multi-Task Learning with Recursive Least Squares and Recursive Kernel Methods [50.67996219968513]
本稿では,オンラインマルチタスク学習(MTL)回帰問題に対する2つの新しいアプローチを紹介する。
入力空間の次元の2次パースタンスコストで精度よく近似的な再帰を実現する。
我々は,実世界の風速予測ケーススタディにおいて,オンラインMTL法と他の競技者との比較を行った。
論文 参考訳（メタデータ） (2023-08-03T01:41:34Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - A Survey on Influence Maximization: From an ML-Based Combinatorial
Optimization [2.9882027965916413]
影響最大化(IM)は、モバイルネットワーク、ソーシャルコンピューティング、レコメンデーションシステムで広く用いられる古典的な最適化問題である。
主な課題は、IM問題のNP硬度と、影響力の広がりを推定する#P硬度である。
我々は,関連する背景知識,基本原則,共通手法,応用研究の要約に重点を置いている。
論文 参考訳（メタデータ） (2022-11-06T10:13:42Z) - Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。
本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。
いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-07-14T18:18:02Z) - Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。
私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
論文 参考訳（メタデータ） (2021-11-19T15:48:43Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳（メタデータ） (2021-07-15T02:13:03Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
論文 参考訳（メタデータ） (2021-04-04T17:12:24Z) - Online Learning via Offline Greedy Algorithms: Applications in Market
Design and Optimization [0.0]
我々は局所的エラーに頑健な欲望アルゴリズムを用いて,定数係数近似に適応可能なオフライン問題に焦点を当てた。
このような問題に対して,オフラインロバストなアルゴリズムをオンラインに効率的に変換する汎用フレームワークを提供する。
得られたオンラインアルゴリズムは、完全な情報設定の下で、$O(sqrtT)$ (approximate) の後悔を持つことを示す。
論文 参考訳（メタデータ） (2021-02-18T19:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。