Concave Aspects of Submodular Functions

• URL: http://arxiv.org/abs/2006.16784v1
• Date: Sat, 27 Jun 2020 17:06:24 GMT
• Title: Concave Aspects of Submodular Functions
• Authors: Rishabh Iyer and Jeff Bilmes
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular Functions are a special class of set functions, which generalize several information-theoretic quantities such as entropy and mutual information [1]. Submodular functions have subgradients and subdifferentials [2] and admit polynomial-time algorithms for minimization, both of which are fundamental characteristics of convex functions. Submodular functions also show signs similar to concavity. Submodular function maximization, though NP-hard, admits constant-factor approximation guarantees, and concave functions composed with modular functions are submodular. In this paper, we try to provide a more complete picture of the relationship between submodularity with concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular maximization using the-super differentials. This paper is a concise and shorter version of our longer preprint [3].

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)
• Sparsification of Decomposable Submodular Functions [27.070004659301162]
  Submodular functions are at the core of many machine learning and data mining tasks. The number of underlying submodular functions in the original function is so large that we need large amount of time to process it and/or it does not even fit in the main memory. We introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function is a (weighted) sum of only a few submodular functions.
  arXiv  Detail & Related papers  (2022-01-18T20:05:25Z)
• 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)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Submodular Combinatorial Information Measures with Applications in Machine Learning [2.5329739965085785]
  Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. We study information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of variables.
  arXiv  Detail & Related papers  (2020-06-27T17:45:32Z)
• 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)
• 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)
• Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
  We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier. A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
  arXiv  Detail & Related papers  (2019-06-05T07:15:17Z)

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.