Piyushi Manupriya, Tarun Ram Menta, Nath, J. Saketha et al. · arXiv (Cornell University) · 2021
This work explores the novel idea of learning a submodular scoring function to improve the specificity/selectivity of existing feature attribution methods. Submodular scores are natural for attribution as they are known to accurately model the principle of diminishing returns. A new formulation for learning a deep submodular set function that is consistent with the real-valued attribution maps obtained by existing attribution methods is proposed. The final attribution value of a feature is then defined as the marginal gain in the induced submodular score of the feature in the context of other highly attributed features, thus decreasing the attribution of redundant yet discriminatory features. Experiments on multiple datasets illustrate that the proposed attribution method achieves higher specificity along with good discriminative power. The implementation of our method is publicly available at https://github.com/Piyushi-0/SEA-NN.
Cited by 0Open access
Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi et al. · arXiv (Cornell University) · 2020
In this paper, we introduce a novel technique for constrained submodular maximization, inspired by barrier functions in continuous optimization. This connection not only improves the running time for constrained submodular maximization but also provides the state of the art guarantee. More precisely, for maximizing a monotone submodular function subject to the combination of a $k$-matchoid and $\ell$-knapsack constraint (for $\ell\leq k$), we propose a potential function that can be approximately minimized. Once we minimize the potential function up to an $ε$ error it is guaranteed that we have found a feasible set with a $2(k+1+ε)$-approximation factor which can indeed be further improved to $(k+1+ε)$ by an enumeration technique. We extensively evaluate the performance of our proposed algorithm over several real-world applications, including a movie recommendation system, summarization tasks for YouTube videos, Twitter feeds and Yelp business locations, and a set cover problem.
Cited by 3Open access
Yaoyao Zhang, Chaojie Zhu, Shaojie Tang et al. · arXiv (Cornell University) · 2022
Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.
Cited by 0Open access
Kshipra Bhawalkar, Yang Cai, Zhe Feng et al. · ArXiv.org · 2025
We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of an exact value oracle. Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a $(1-1/e)/2$-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a $(1-1/e)$-approximation (resp. $1/e$-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a $1/2$-approximation for unconstrained (non-monotone) submodular maximization under noise.
Cited by 0Open access
Shaojie Tang, Yuan Jing · arXiv (Cornell University) · 2023
In this paper, we study a fundamental problem in submodular optimization, which is called sequential submodular maximization. Specifically, we aim to select and rank a group of $k$ items from a ground set $V$ such that the weighted summation of $k$ (possibly non-monotone) submodular functions $f_1, \cdots ,f_k: 2^V \rightarrow \mathbb{R}^+$ is maximized, here each function $f_j$ takes the first $j$ items from this sequence as input. The existing research on sequential submodular maximization has predominantly concentrated on the monotone setting, assuming that the submodular functions are non-decreasing. However, in various real-world scenarios, like diversity-aware recommendation systems, adding items to an existing set might negatively impact the overall utility. In response, this paper pioneers the examination of the aforementioned problem with non-monotone submodular functions and offers effective solutions for both flexible and fixed length constraints, as well as a special case with identical utility functions. The empirical evaluations further validate the effectiveness of our proposed algorithms in the domain of video recommendations. The results of this research have implications in various fields, including recommendation systems and assortment optimization, where the ordering of items significantly impacts the overall value obtained.
Cited by 1Open access
Christopher Harshaw, Ehsan Kazemi, Moran Feldman et al. · Mathematics of Operations Research · 2021
We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SampleGreedy, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-extendible system using [Formula: see text] evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-Streaming, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and [Formula: see text] evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
Cited by 0Open access
Shahar Dobzinski, Jan Vondrák · 2013
We prove the first communication complexity lower bound for constant-factor approximation of the submodular welfare problem. More precisely, we show that a -approximation (≃ 0.816) for welfare maximization in combinatorial auctions with submodular valuations would require exponential communication. We also show NP-hardness of -approximation in a computational model where each valuation is given explicitly by a table of constant size. Both results rule out better than (1 − )-approximations in every oracle model with a separate oracle for each player, such as the demand oracle model. Our main tool is a new construction of monotone submodular functions that we call multi-peak submodular functions. Roughly speaking, given a family of sets , we construct a monotone submodular function f with a high value f(S) for every set S ∊ (a “peak”), and a low value on every set that does not intersect significantly any set in . We also study two other related problems: max-min allocation (for which we also get hardness of -approximation, in both models), and combinatorial public projects (for which we prove hardness of -approximation in the communication model, and hardness of -approximation in the computational model, using constant size valuations).
Cited by 17
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar et al. · Edinburgh Research Explorer (University of Edinburgh)
Many large-scale machine learning problems-clustering, non-parametric learning, kernel machines, etc.-require selecting a small yet representative subset from a large dataset.Such problems can often be reduced to maximizing a submodular set function subject to various constraints.Classical approaches to submodular optimization require centralized access to the full dataset, which is impractical for truly large-scale problems.In this paper, we consider the problem of submodular function maximization in a distributed fashion.We develop a simple, two-stage protocol GreeDi, that is easily implemented using MapReduce style computations.We theoretically analyze our approach, and show that under certain natural conditions, performance close to the centralized approach can be achieved.We begin with monotone submodular maximization subject to a cardinality constraint, and then extend this approach to obtain approximation guarantees for (not necessarily monotone) submodular maximization subject to more general constraints including matroid or knapsack constraints.In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar based clustering on tens of millions of examples using Hadoop.
Cited by 0Open access
Shuang Cui, Kai Han, Jing Tang et al. · ACM SIGMETRICS Performance Evaluation Review · 2023
Due to the pervasive "diminishing returns" property appeared in data-intensive applications, submodular maximization problems have aroused great attention from both the machine learning community and the computation theory community. During the last decades, a lot of algorithms have been proposed for submodular maximization subject to various constraints [4, 6, 8], and these algorithms can be used in numerous applications including sensor placement [9], clustering [5], network design [13], and so on. The existing algorithms for submodular maximization can be roughly classified into offline algorithms and streaming algorithms; the former assume full access to the whole dataset at any time (e.g.,[4, 10]), while the latter only require an amount of space which is nearly linear in the maximum size of a feasible solution (e.g., [1, 7]). Apparently, streaming algorithms are more useful in big data applications, as the whole data set is usually too large to be fit into memory in practice. However, compared to the offline algorithms, the existing streaming algorithms for submodular maximization generally have weaker capabilities in that they handle more limited problem constraints or achieve weaker performance bounds, due to the more stringent requirements under the streaming setting. Another classification of the existing algorithms is that they concentrate on either monotone or non-monotone submodular functions. As monotone submodular function is a special case of non-monotone submodular function, we will concentrate on non-monotone submodular maximization in this paper.
Cited by 2
Gunnar Fløystad, Dominique Manchon · arXiv (Cornell University) · 2024
Submodular functions $z$ defined on the power set of a finite set are in bijection with generalized permutahedra $\egp(z)$. To any such $z$ we define a class of preorders, {\it conforming} preorders. We show the faces of $\egp(z)$ and the conforming preorders are in bijection. We investigate in detail this interplay between submodular functions and generalized permutahedra on one side, and conforming preorders on the other side, with many examples. In particular, the face poset structure of $\egp(z)$ correspond to two order relations $\lhd$ and $\btl$ on preorders, and we investigate their properties. Ardila and Aguiar \cite{AA2017} introduced a Hopf monoid of submodular functions/generalized permutahedra. We show there is a bimonoid of modular functions cointeracting in a non-standard way. By recent theory of L.Foissy \cite{Fo2022}, on double bialgebras we get a canonical polynomial associated to any submodular function.
Cited by 0Open access
Kazutoshi Ando · 1999
We consider a class of lattice polyhedra introduced by Hoffman and Schwartz. The polyhedra are defined in terms of a kind of submodular function defined on the set of antichains of a poset. Recently, Krüger [U. Krüger: Structural aspects of ordered polymatroids. Discrete Applied Mathematics (to appear)] showed the validity of a greedy algorithm for this class of lattice polyhedra, which had been proved to be valid for less general class of polyhedra by Faigle and Kern. In this paper, we investigate submodular functions in Krüger's sense and the associated polyhedra. Namely, we see that Lovasz extension of a submodular function in the Krüger's sense is convex, and vice versa. Furthermore, we show an O(n²) time algorithm to test a vector for being an extreme point of the associated polyhedron, where n is the cardinality of the ground set.
Cited by 0
Hassan Jaleel, Jeff S. Shamma · arXiv (Cornell University) · 2017
We develop a framework for the distributed minimization of submodular\nfunctions. Submodular functions are a discrete analog of convex functions and\nare extensively used in large-scale combinatorial optimization problems. While\nthere has been significant interest in the distributed formulations of convex\noptimization problems, distributed minimization of submodular functions has\nreceived relatively little research attention. Our framework relies on an\nequivalent convex reformulation of a submodular minimization problem, which is\nefficiently computable. We then use this relaxation to exploit methods for the\ndistributed optimization of convex functions. The proposed framework is\napplicable to submodular set functions as well as to a wider class of\nsubmodular functions defined over certain lattices. We also propose an approach\nfor solving distributed motion coordination problems in discrete state space\nbased on submodular function minimization. We establish through a challenging\nsetup of capture the flag game that submodular functions over lattices can be\nused to design artificial potential fields over discrete state space in which\nthe agents are attracted towards their goals and are repulsed from obstacles\nand from each other for collision avoidance.\n
Cited by 3Open access
Elchanan Mossel, Sebastien Roch · ScholarlyCommons (University of Pennsylvania) · 2007
Social networks are often represented as directed graphs where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or “word-of-mouth” effects on such a graph is to consider an increasing process of “infected” (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. Such a model was introduced by Kempe, Kleinberg, and Tardos (KKT) in [KKT03, KKT05] where the authors also impose several natural assumptions: the threshold values are random and the activation functions are monotone and submodular. The monotonicity condition indicates that a node is more likely to become active if more of its neighbors are active, while the submodularity condition indicates that the marginal effect of each neighbor is decreasing when the set of active neighbors increases.\nFor an initial set of active nodes S, let σ(S) denote the expected number of active nodes at termination. Here we prove a conjecture of KKT: we show that the function σ(S) is submodular under the assumptions above. We prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination. Roughly, our results demonstrate that “local” submodularity is preserved “globally” under this diffusion process. This is of natural computational interest, as many optimization problems have good approximation algorithms for submodular functions.
Cited by 0Open access
Rishabh Iyer · arXiv (Cornell University) · 2026
Shannon entropy is a polymatroidal set function and lies at the foundation of information theory, yet the class of entropic polymatroids is strictly smaller than the class of all submodular functions. In parallel, submodular and combinatorial information measures (SIMs) have recently been proposed as a principled framework for extending entropy, mutual information, and conditional mutual information to general submodular functions, and have been used extensively in data subset selection, active learning, domain adaptation, and representation learning. This raises a natural and fundamental question: are the monotone submodular functions most commonly used in practice entropic? In this paper, we answer this question in the affirmative for a broad class of widely used polymatroid functions. We provide explicit entropic constructions for set cover and coverage functions, facility location, saturated coverage, concave-over-modular functions via truncations, and monotone graph-cut-type objectives. Our results show that these functions can be realized exactly as Shannon entropies of appropriately constructed random variables. As a consequence, for these functions, submodular mutual information coincides with classical mutual information, conditional gain specializes to conditional entropy, and submodular conditional mutual information reduces to standard conditional mutual information in the entropic sense. These results establish a direct bridge between combinatorial information measures and classical information theory for many of the most common submodular objectives used in applications.
Cited by 0Open access
Rishabh Iyer · ArXiv.org · 2026
Shannon entropy is a polymatroidal set function and lies at the foundation of information theory, yet the class of entropic polymatroids is strictly smaller than the class of all submodular functions. In parallel, submodular and combinatorial information measures (SIMs) have recently been proposed as a principled framework for extending entropy, mutual information, and conditional mutual information to general submodular functions, and have been used extensively in data subset selection, active learning, domain adaptation, and representation learning. This raises a natural and fundamental question: are the monotone submodular functions most commonly used in practice entropic? In this paper, we answer this question in the affirmative for a broad class of widely used polymatroid functions. We provide explicit entropic constructions for set cover and coverage functions, facility location, saturated coverage, concave-over-modular functions via truncations, and monotone graph-cut-type objectives. Our results show that these functions can be realized exactly as Shannon entropies of appropriately constructed random variables. As a consequence, for these functions, submodular mutual information coincides with classical mutual information, conditional gain specializes to conditional entropy, and submodular conditional mutual information reduces to standard conditional mutual information in the entropic sense. These results establish a direct bridge between combinatorial information measures and classical information theory for many of the most common submodular objectives used in applications.
Cited by 0Open access
Aryan Mokhtari, Hamed Hassani, Amin Karbasi · arXiv (Cornell University) · 2018
This paper considers stochastic optimization problems for a large class of\nobjective functions, including convex and continuous submodular. Stochastic\nproximal gradient methods have been widely used to solve such problems;\nhowever, their applicability remains limited when the problem dimension is\nlarge and the projection onto a convex set is costly. Instead, stochastic\nconditional gradient methods are proposed as an alternative solution relying on\n(i) Approximating gradients via a simple averaging technique requiring a single\nstochastic gradient evaluation per iteration; (ii) Solving a linear program to\ncompute the descent/ascent direction. The averaging technique reduces the noise\nof gradient approximations as time progresses, and replacing projection step in\nproximal methods by a linear program lowers the computational complexity of\neach iteration. We show that under convexity and smoothness assumptions, our\nproposed method converges to the optimal objective function value at a\nsublinear rate of $O(1/t^{1/3})$. Further, for a monotone and continuous\nDR-submodular function and subject to a general convex body constraint, we\nprove that our proposed method achieves a $((1-1/e)OPT-\\eps)$ guarantee with\n$O(1/\\eps^3)$ stochastic gradient computations. This guarantee matches the\nknown hardness results and closes the gap between deterministic and stochastic\ncontinuous submodular maximization. Additionally, we obtain $((1/e)OPT -\\eps)$\nguarantee after using $O(1/\\eps^3)$ stochastic gradients for the case that the\nobjective function is continuous DR-submodular but non-monotone and the\nconstraint set is down-closed. By using stochastic continuous optimization as\nan interface, we provide the first $(1-1/e)$ tight approximation guarantee for\nmaximizing a monotone but stochastic submodular set function subject to a\nmatroid constraint and $(1/e)$ approximation guarantee for the non-monotone\ncase.\n
Cited by 11Open access
Ehsan Kazemi, Shervin Minaee, Moran Feldman et al. · arXiv (Cornell University) · 2020
In this paper, we propose scalable methods for maximizing a regularized submodular function $f = g - \ell$ expressed as the difference between a monotone submodular function $g$ and a modular function $\ell$. Indeed, submodularity is inherently related to the notions of diversity, coverage, and representativeness. In particular, finding the mode of many popular probabilistic models of diversity, such as determinantal point processes, submodular probabilistic models, and strongly log-concave distributions, involves maximization of (regularized) submodular functions. Since a regularized function $f$ can potentially take on negative values, the classic theory of submodular maximization, which heavily relies on the non-negativity assumption of submodular functions, may not be applicable. To circumvent this challenge, we develop the first one-pass streaming algorithm for maximizing a regularized submodular function subject to a $k$-cardinality constraint. It returns a solution $S$ with the guarantee that $f(S)\geq(ϕ^{-2}-ε) \cdot g(OPT)-\ell (OPT)$, where $ϕ$ is the golden ratio. Furthermore, we develop the first distributed algorithm that returns a solution $S$ with the guarantee that $\mathbb{E}[f(S)] \geq (1-ε) [(1-e^{-1}) \cdot g(OPT)-\ell(OPT)]$ in $O(1/ ε)$ rounds of MapReduce computation, without keeping multiple copies of the entire dataset in each round (as it is usually done). We should highlight that our result, even for the unregularized case where the modular term $\ell$ is zero, improves the memory and communication complexity of the existing work by a factor of $O(1/ ε)$ while arguably provides a simpler distributed algorithm and a unifying analysis. We also empirically study the performance of our scalable methods on a set of real-life applications, including finding the mode of distributions, data summarization, and product recommendation.
Cited by 16Open access
Lin Chen, Moran Feldman, Amin Karbasi · arXiv (Cornell University) · 2017
Submodular functions are a broad class of set functions, which naturally arise in diverse areas. Many algorithms have been suggested for the maximization of these functions. Unfortunately, once the function deviates from submodularity, the known algorithms may perform arbitrarily poorly. Amending this issue, by obtaining approximation results for set functions generalizing submodular functions, has been the focus of recent works. One such class, known as weakly submodular functions, has received a lot of attention. A key result proved by Das and Kempe (2011) showed that the approximation ratio of the greedy algorithm for weakly submodular maximization subject to a cardinality constraint degrades smoothly with the distance from submodularity. However, no results have been obtained for maximization subject to constraints beyond cardinality. In particular, it is not known whether the greedy algorithm achieves any non-trivial approximation ratio for such constraints. In this paper, we prove that a randomized version of the greedy algorithm (previously used by Buchbinder et al. (2014) for a different problem) achieves an approximation ratio of $(1 + 1/γ)^{-2}$ for the maximization of a weakly submodular function subject to a general matroid constraint, where $γ$ is a parameter measuring the distance of the function from submodularity. Moreover, we also experimentally compare the performance of this version of the greedy algorithm on real world problems against natural benchmarks, and show that the algorithm we study performs well also in practice. To the best of our knowledge, this is the first algorithm with a non-trivial approximation guarantee for maximizing a weakly submodular function subject to a constraint other than the simple cardinality constraint. In particular, it is the first algorithm with such a guarantee for the important and broad class of matroid constraints.
Cited by 4Open access
Hui Lin, Jeff Bilmes · 2010
We address the problem of finding a subset of a large training data set (corpus) that is useful for accurately and rapidly prototyping novel and computationally expensive machine learning architectures. To solve this problem, we express it as an minimization problem over a weighted sum of modular functions and submodular functions. Quantities such as number of classes (or quality) in a set of samples, or quality of a bundle of classes are submodular functions which make finding the optimal solutions possible. We apply the principal partition to our problem such that solutions for all possible trade-offs between a modular function and a submodular function can be found efficiently. We show results for speech recognition on the Switchboard-I speech recognition corpus, demonstrating improved results over previous techniques for this purpose. We also demonstrate the variety of the resulting corpora that may be produced using our method. 1
Cited by 0
Brandon Van Over, Bowen Li, Edwin K. P. Chong et al. · IEEE Transactions on Automatic Control · 2025
We present a simple performance bound for the greedy scheme in string optimization problems. Our approach generalizes the family of greedy curvature bounds established by Conforti and Cornuejols (1984). Specifically, we examine three bounds they introduced for evaluating the performance of the greedy scheme in maximizing monotone submodular set functions. We first generalize two of these bounds to string optimization problems in a manner that includes maximizing monotone submodular set functions as a special case. Next, we derive a simpler and more computable bound that applies to a broader class of functions with string domains. We then prove that our bound is superior to two of their bounds and provide a counterexample to show that the third bound is incorrect under the assumptions in Conforti and Cornuejols (1984). We demonstrate our results through two applications. First, we apply our bound to sensor coverage problems with both monotone set and string submodular objective functions. The second application is a social welfare maximization problem involving a monotone non-submodular black-box utility function.
Cited by 0