論文の概要: Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization

• arxiv url: http://arxiv.org/abs/2004.05549v1
• Date: Sun, 12 Apr 2020 05:35:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-14 05:41:53.210971
• Title: Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization
• Title（参考訳）: 連続的利益最大化:制約のないDr-submodular Maximizationの研究
• Authors: Jianxiong Guo, Weili Wu
• Abstract要約: 我々は、整数格子上の領域である連続利益(CPM-MS)問題を形成する。 格子に基づく二重グリードアルゴリズムを導入し, 定数近似を求める。 本稿では,格子型反復プルーニング手法を提案し,探索空間を効果的に縮小することができる。
• 参考スコア（独自算出の注目度）: 4.649999862713523
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Profit maximization (PM) is to select a subset of users as seeds for viral marketing in online social networks, which balances between the cost and the profit from influence spread. We extend PM to that under the general marketing strategy, and form continuous profit maximization (CPM-MS) problem, whose domain is on integer lattices. The objective function of our CPM-MS is dr-submodular, but non-monotone. It is a typical case of unconstrained dr-submodular maximization (UDSM) problem, and take it as a starting point, we study UDSM systematically in this paper, which is very different from those existing researcher. First, we introduce the lattice-based double greedy algorithm, which can obtain a constant approximation guarantee. However, there is a strict and unrealistic condition that requiring the objective value is non-negative on the whole domain, or else no theoretical bounds. Thus, we propose a technique, called lattice-based iterative pruning. It can shrink the search space effectively, thereby greatly increasing the possibility of satisfying the non-negative objective function on this smaller domain without losing approximation ratio. Then, to overcome the difficulty to estimate the objective value of CPM-MS, we adopt reverse sampling strategies, and combine it with lattice-based double greedy, including pruning, without losing its performance but reducing its running time. The entire process can be considered as a general framework to solve the UDSM problem, especially for applying to social networks. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed algorithms.
• Abstract（参考訳）: 利益の最大化(pm)は、オンラインソーシャルネットワークにおけるバイラルマーケティングの種としてユーザーのサブセットを選択することであり、コストと影響拡大による利益のバランスをとる。 我々はPMを一般的なマーケティング戦略の下で拡張し、整数格子上の領域である連続利益最大化(CPM-MS)問題を形成する。 CPM-MSの目的機能はDr-submodularであるが,非モノトンである。 本論文は,制約のないUDSM(Dr-submodular maximization)問題の典型例であり,その出発点として,既存の研究者とは大きく異なるUDSMを系統的に研究する。 まず, 定数近似保証が得られる格子型二重グリーディアルゴリズムを提案する。 しかし、厳密で非現実的な条件として、目的値の要求は全領域において非負であり、そうでなければ理論的な境界は存在しない。 そこで我々は格子型反復刈り法という手法を提案する。 探索空間を効果的に縮小することができ、近似比を損なうことなく、この小さい領域で非負の目的関数を満たす可能性を大きく高めることができる。 そこで我々は,CPM-MSの目的値の推定の難しさを克服するために,逆サンプリング戦略を採用し,その性能を損なうことなく,ランニングを含む格子ベースの二重グリージーと組み合わせる。 プロセス全体はUDSM問題を解決するための一般的なフレームワーク、特にソーシャルネットワークに適用するためのフレームワークとみなすことができる。 最後に,提案するアルゴリズムの有効性と効率を評価するために,実データを用いた実験を行った。

関連論文リスト

• Anti-Exploration by Random Network Distillation [63.04360288089277]
  ランダムネットワーク蒸留 (RND) の条件付けは, 不確実性推定器として用いるのに十分な識別性がないことを示す。 この制限は、FiLM(Feature-wise Linear Modulation)に基づく条件付けによって回避できることを示す。 D4RLベンチマークで評価したところ、アンサンブルベースの手法に匹敵する性能を達成でき、アンサンブルのない手法よりも広いマージンで性能を向上できることがわかった。
  論文  参考訳（メタデータ） (2023-01-31T13:18:33Z)
• Weighted Sum-Rate Maximization With Causal Inference for Latent Interference Estimation [9.569049935824227]
  本論文は、遅延干渉下でWSRMに対処するための因果的枠組みの下で、有名な代替最適化最小二乗誤差(WMMSE)を拡張した。 数値計算の結果, SC-WMMSEは, コンバージェンスと目的の両方において, オリジナルよりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2022-11-15T17:27:45Z)
• Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions [14.959412298776199]
  我々は、従来のネットワーク収益管理(NRM)問題について、意思決定を受理/退避し、IIDの到着を$T$で検討する。 本モデルでは,O(log2 T)$ regret を実現するオンラインアルゴリズムを開発した。 2階成長の仮定を追加して、$O(log T)$ regretを達成する2番目の結果を得る。
  論文  参考訳（メタデータ） (2022-10-14T17:52:19Z)
• Designing Biological Sequences via Meta-Reinforcement Learning and Bayesian Optimization [68.28697120944116]
  メタ強化学習を用いて自己回帰生成モデルを訓練し、選択のための有望なシーケンスを提案する。 我々は,データのサブセットのサンプリングによって誘導されるMDPの分布に対する最適ポリシーを求める問題として,この問題を提起する。 このようなアンサンブルに対するメタラーニングは,報酬の過小評価に対して頑健であり,競争的な結果が得られることを示す。
  論文  参考訳（メタデータ） (2022-09-13T18:37:27Z)
• Domain-Specific Risk Minimization for Out-of-Distribution Generalization [104.17683265084757]
  まず、適応性ギャップを明示的に考慮した一般化境界を確立する。 本稿では,目標に対するより良い仮説の選択を導くための効果的なギャップ推定法を提案する。 もう1つの方法は、オンラインターゲットサンプルを用いてモデルパラメータを適応させることにより、ギャップを最小化することである。
  論文  参考訳（メタデータ） (2022-08-18T06:42:49Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  サブグラディエント法(Sub-gradient method, SubGM)は, 限られた測定値から低ランク行列を復元するために用いられる。 我々は、SubGMが任意の大きさの高密度ノイズ値の下でも、真の解に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-17T17:50:04Z)
• KL Guided Domain Adaptation [88.19298405363452]
  ドメイン適応は重要な問題であり、現実世界のアプリケーションにしばしば必要である。 ドメイン適応文学における一般的なアプローチは、ソースとターゲットドメインに同じ分布を持つ入力の表現を学ぶことである。 確率的表現ネットワークにより、KL項はミニバッチサンプルにより効率的に推定できることを示す。
  論文  参考訳（メタデータ） (2021-06-14T22:24:23Z)
• Contingency-Aware Influence Maximization: A Reinforcement Learning Approach [52.109536198330126]
  インフルエンス(IM)問題は、インフルエンスの普及を最大化する、ソーシャルネットワーク内のシードノードのサブセットを見つけることを目的としている。 本研究では、招待されたノードがシードであるかどうかが不確実なIM問題(contingency-aware IM)に焦点をあてる。 最初の成功にもかかわらず、より多くのコミュニティへのソリューションの推進における大きな実践上の障害は、欲張りのアルゴリズムの巨大な実行時である。
  論文  参考訳（メタデータ） (2021-06-13T16:42:22Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• The Power of Sampling: Dimension-free Risk Bounds in Private ERM [25.676350220943274]
  本アルゴリズムは,ゼロ次オラクルのみを用いて,非平滑凸対象に対するランク依存的リスクバウンダリを実現することができることを示す。 これは、差分プライバシーにおけるサンプリングのパワーを強調します。
  論文  参考訳（メタデータ） (2021-05-28T07:28:24Z)
• Improving the filtering of Branch-And-Bound MDD solver (extended) [11.728147523456702]
  本稿では,多値決定図(MDD)に基づく制約最適化解法の効率向上のための2つのプルーニング手法を提案し,評価する。 Bergmanらによって提案されたブランチ・アンド・バウンド・フレームワークを採用している。 2016年、動的プログラムを最適に解く。
  論文  参考訳（メタデータ） (2021-04-24T13:42:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。