Continuous Submodular Function Maximization

• URL: http://arxiv.org/abs/2006.13474v1
• Date: Wed, 24 Jun 2020 04:37:31 GMT
• Title: Continuous Submodular Function Maximization
• Authors: Yatao Bian, Joachim M. Buhmann, Andreas Krause
• Abstract summary: Continuous submodularity is a class of functions with a wide spectrum of applications. We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
• Score: 91.17492610120324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Continuous submodular functions are a category of generally non-convex/non-concave functions with a wide spectrum of applications. The celebrated property of this class of functions - continuous submodularity - enables both exact minimization and approximate maximization in poly. time. Continuous submodularity is obtained by generalizing the notion of submodularity from discrete domains to continuous domains. It intuitively captures a repulsive effect amongst different dimensions of the defined multivariate function. In this paper, we systematically study continuous submodularity and a class of non-convex optimization problems: continuous submodular function maximization. We start by a thorough characterization of the class of continuous submodular functions, and show that continuous submodularity is equivalent to a weak version of the diminishing returns (DR) property. Thus we also derive a subclass of continuous submodular functions, termed continuous DR-submodular functions, which enjoys the full DR property. Then we present operations that preserve continuous (DR-)submodularity, thus yielding general rules for composing new submodular functions. We establish intriguing properties for the problem of constrained DR-submodular maximization, such as the local-global relation. We identify several applications of continuous submodular optimization, ranging from influence maximization, MAP inference for DPPs to provable mean field inference. For these applications, continuous submodularity formalizes valuable domain knowledge relevant for optimizing this class of objectives. We present inapproximability results and provable algorithms for two problem settings: constrained monotone DR-submodular maximization and constrained non-monotone DR-submodular maximization. Finally, we extensively evaluate the effectiveness of the proposed algorithms.

Related papers

• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  We aim to select and rank a group of $k$ items from a ground set $V$ such that the weighted assortment of $k$ is maximized. The results of this research have implications in various fields, including recommendation systems and optimization.
  arXiv  Detail & Related papers  (2023-08-16T19:32:29Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization. We propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions.
  arXiv  Detail & Related papers  (2022-10-20T06:00:45Z)
• Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
  We show that for many standard submodular algorithms one can prove new approximation guarantees that depend on the monotonicity ratio. This leads to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming and image summarization.
  arXiv  Detail & Related papers  (2022-02-07T10:35:40Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences [44.11102526976392]
  This paper studies the problem class of maximizing monotone submodular functions over sequences. EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.
  arXiv  Detail & Related papers  (2021-04-20T10:36:10Z)
• Planning with Submodular Objective Functions [118.0376288522372]
  We study planning with submodular objective functions, where instead of maximizing cumulative reward, the goal is to maximize the value induced by a submodular function. Our framework subsumes standard planning and submodular objective with cardinality constraints as special cases.
  arXiv  Detail & Related papers  (2020-10-22T16:55:12Z)
• Concave Aspects of Submodular Functions [0.0]
  Submodular functions generalize several information-theoretic quantities such as entropy and mutual information. Submodular functions also show signs of concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular using the differentials.
  arXiv  Detail & Related papers  (2020-06-27T17:06:24Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)

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.