Abstract
The standard greedy algorithm has been recently shown to enjoy approximation guarantees for constrained non-submodular nondecreasing set function maximization. While these recent results allow to better characterize the empirical success of the greedy algorithm, they are only applicable to simple cardinality constraints. In this paper, we study the problem of maximizing a non-submodular nondecreasing set function subject to a general matroid constraint. We first show that the standard greedy algorithm offers an approximation factor of $\frac{0.4 {\gamma}^{2}}{\sqrt{\gamma r} + 1}$, where $\gamma$ is the submodularity ratio of the function and $r$ is the rank of the matroid. Then, we show that the same greedy algorithm offers a constant approximation factor of $(1 + 1/(1-\alpha))^{-1}$, where $\alpha$ is the generalized curvature of the function. In addition, we demonstrate that these approximation guarantees are applicable to several real-world applications in which the submodularity ratio and the generalized curvature can be bounded. Finally, we show that our greedy algorithm does achieve a competitive performance in practice using a variety of experiments on synthetic and real-world data.
Introduction
In many domains of machine learning and data science—ranging from feature selection to social network analysis—the core challenge involves selecting an optimal subset of items to maximize a utility function. Traditionally, these problems are solved efficiently when the utility function exhibits submodularity, a property analogous to the law of diminishing returns. For submodular functions, a simple greedy algorithm is known to provide strong approximation guarantees.
However, many real-world applications involve non-submodular functions, where the marginal gain of an item may actually increase as the set grows. Furthermore, these problems are often subject to matroid constraints, which represent complex structural requirements (e.g., ensuring a selection does not exceed specific budgets across multiple categories). While the greedy algorithm has shown empirical success in these settings, its theoretical performance under general matroid constraints remained largely uncharacterized until now.
Theoretical Framework
To analyze the performance of the greedy algorithm in non-submodular settings, we utilize two key parameters that quantify the "distance" of a function from being submodular or modular:
- Submodularity Ratio ($\gamma$): A value in $[0, 1]$ that measures how much the submodularity property is violated. If $\gamma = 1$, the function is submodular.
- Generalized Curvature ($\alpha$): A metric that captures the degree of interaction between elements. It measures how far a function is from being modular (where items have no interaction).
This paper provides the first theoretical approximation guarantees for the standard greedy algorithm when maximizing non-submodular functions under general matroid constraints using these parameters.
The Greedy Guarantee
The standard greedy algorithm operates by iteratively selecting the element that provides the largest marginal increase in the objective function while remaining within the feasible set defined by the matroid constraint. We establish two primary bounds for this deterministic approach:
- Rank-Dependent Bound: For functions with a submodularity ratio $\gamma$, the greedy algorithm achieves an approximation factor of $\frac{0.4\gamma^2}{\sqrt{\gamma r + 1}}$, where $r$ is the rank of the matroid.
- Rank-Independent Bound: For functions with a generalized curvature $\alpha$, we prove a constant approximation factor of $(1 + 1/(1-\alpha))^{-1}$. This result is particularly significant as it provides a performance guarantee that does not degrade as the problem size increases.
These results demonstrate that the simplicity of the deterministic greedy algorithm does not preclude it from having robust theoretical foundations, even in the absence of diminishing returns.
Applications and Empirical Results
We validate our theoretical findings through two primary applications: Gaussian Graphical Model (GGM) estimation and Network Visibility optimization.
Gaussian Graphical Models
In the task of GGM estimation using tree-structured constraints, the goal is to identify the underlying dependency structure of a set of variables. Our experiments on synthetic data show that the greedy algorithm performs comparably to state-of-the-art methods based on Maximum Spanning Trees (MST). In several instances, the greedy approach slightly outperformed MST-based methods in terms of negative log-likelihood, confirming its utility in structural learning.
Network Visibility Optimization
A central application of this work is the Network Visibility Problem. Using a real-world Twitter dataset (comprising user profiles and tweet history), we modeled the problem of recommending links to broadcasters to maximize their reach. This problem is naturally non-submodular and subject to matroid constraints (e.g., limits on the number of recommendations per user).
Our results indicate that the greedy algorithm (referred to as GP) consistently outperforms common heuristics, such as Constant Probability (CP) or User Probability (UP) baselines. Across various link budgets, the greedy approach achieved significantly higher average visibility, demonstrating its effectiveness in navigating the complex interactions of social media networks.
Conclusion
This research bridges the gap between the empirical success and theoretical understanding of the greedy algorithm for non-submodular maximization. By establishing bounds based on the submodularity ratio and generalized curvature, we provide a rigorous justification for using simple greedy strategies under complex matroid constraints. Future work will focus on tightening these bounds and developing methods to estimate $\gamma$ and $\alpha$ directly from data to further refine algorithm selection in practice.
Summary updated