Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization

• URL: http://arxiv.org/abs/2004.05549v1
• Date: Sun, 12 Apr 2020 05:35:19 GMT
• Title: Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization
• Authors: Jianxiong Guo, Weili Wu
• Abstract summary: We form continuous profit (CPM-MS) problem, whose domain is on integer lattices. We introduce lattice-based double greedy algorithm, which can obtain a constant approximation. We propose a technique, called lattice-based iterative pruning. It can shrink the search space effectively.
• Score: 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.

Related papers

• Anti-Exploration by Random Network Distillation [63.04360288089277]
  We show that a naive choice of conditioning for the Random Network Distillation (RND) is not discriminative enough to be used as an uncertainty estimator. We show that this limitation can be avoided with conditioning based on Feature-wise Linear Modulation (FiLM) We evaluate it on the D4RL benchmark, showing that it is capable of achieving performance comparable to ensemble-based methods and outperforming ensemble-free approaches by a wide margin.
  arXiv  Detail & Related papers  (2023-01-31T13:18:33Z)
• Weighted Sum-Rate Maximization With Causal Inference for Latent Interference Estimation [9.569049935824227]
  The paper extends the famous alternate optimization weighted minimum mean square error (WMMSE) under a causal framework to tackle with WSRM under latent interference. Numerical results suggest the superiority of the SC-WMMSE over the original in both convergence and objective.
  arXiv  Detail & Related papers  (2022-11-15T17:27:45Z)
• Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions [14.959412298776199]
  We study the classical Network Revenue Management (NRM) problem with accept/reject decisions and $T$ IID arrivals. We develop an online algorithm that achieves $O(log2 T)$ regret under this model. We derive a second result that achieves $O(log T)$ regret under an additional assumption of second-order growth.
  arXiv  Detail & Related papers  (2022-10-14T17:52:19Z)
• Designing Biological Sequences via Meta-Reinforcement Learning and Bayesian Optimization [68.28697120944116]
  We train an autoregressive generative model via Meta-Reinforcement Learning to propose promising sequences for selection. We pose this problem as that of finding an optimal policy over a distribution of MDPs induced by sampling subsets of the data. Our in-silico experiments show that meta-learning over such ensembles provides robustness against reward misspecification and achieves competitive results.
  arXiv  Detail & Related papers  (2022-09-13T18:37:27Z)
• Domain-Specific Risk Minimization for Out-of-Distribution Generalization [104.17683265084757]
  We first establish a generalization bound that explicitly considers the adaptivity gap. We propose effective gap estimation methods for guiding the selection of a better hypothesis for the target. The other method is minimizing the gap directly by adapting model parameters using online target samples.
  arXiv  Detail & Related papers  (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) is used to recover a low-rank matrix from a limited number of measurements. We show that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values.
  arXiv  Detail & Related papers  (2022-02-17T17:50:04Z)
• KL Guided Domain Adaptation [88.19298405363452]
  Domain adaptation is an important problem and often needed for real-world applications. A common approach in the domain adaptation literature is to learn a representation of the input that has the same distributions over the source and the target domain. We show that with a probabilistic representation network, the KL term can be estimated efficiently via minibatch samples.
  arXiv  Detail & Related papers  (2021-06-14T22:24:23Z)
• Contingency-Aware Influence Maximization: A Reinforcement Learning Approach [52.109536198330126]
  influence (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence. In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM. Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms.
  arXiv  Detail & Related papers  (2021-06-13T16:42:22Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• The Power of Sampling: Dimension-free Risk Bounds in Private ERM [25.676350220943274]
  We show that our algorithm can achieve rank-dependent risk bounds for non-smooth convex objectives using only zeroth order oracles. This highlights the power of sampling in differential privacy.
  arXiv  Detail & Related papers  (2021-05-28T07:28:24Z)
• Improving the filtering of Branch-And-Bound MDD solver (extended) [11.728147523456702]
  This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDDs) It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality.
  arXiv  Detail & Related papers  (2021-04-24T13:42:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.