On Additive Approximate Submodularity

• URL: http://arxiv.org/abs/2010.02912v2
• Date: Wed, 7 Oct 2020 16:59:21 GMT
• Title: On Additive Approximate Submodularity
• Authors: Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar
• Abstract summary: A real-valued set function is approximately submodular if it satisfies the submodularity conditions with an additive error. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n2)$ pointwise-close to a submodular function.
• Score: 30.831477850153224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n^2)$ pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an $\Omega(\sqrt{n})$ lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.

Related papers

• Supermodular Rank: Set Function Decomposition and Optimization [2.578242050187029]
  We define the supermodular rank of a function on a lattice. We analogously define the submodular rank. We use submodular decompositions to optimize set functions.
  arXiv  Detail & Related papers  (2023-05-24T02:09:28Z)
• 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)
• 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)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
  arXiv  Detail & Related papers  (2021-04-06T20:25:57Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  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.
  arXiv  Detail & Related papers  (2020-06-24T04:37:31Z)
• A Parameterized Family of Meta-Submodular Functions [3.233545237942899]
  We give a broad parameterized family of monotone functions which includes submodular functions and a class of supermodular functions containing diversity functions. We show that the $gamma$-submodular families include well-known classes of functions such as meta-submodular functions, metric diversity functions and submodular functions.
  arXiv  Detail & Related papers  (2020-06-23T16:45:12Z)
• 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)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  Submodularity is inherently related to the notions of diversity, coverage, and representativeness. We propose methods for maximizing a regularized submodular function $f = g ell$ expressed as the difference between a determinant submodular function $g$ and a modular function $ell$.
  arXiv  Detail & Related papers  (2020-02-10T02:37:18Z)

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.