Source-linked AI summary
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
Andrew An Bian, Joachim M. Buhmann, Andreas Krause, Sebastian Tschiatschek
TL;DR
The paper addresses the limited theoretical guarantees for Greedy on non-submodular nondecreasing set functions. It combines curvature and submodularity ratio to derive tight guarantees, bounds these parameters for applications, and validates the theory experimentally.
Problem
Greedy has strong guarantees for submodular maximization but few guarantees for important non-submodular objectives, despite strong empirical performance in applications such as experimental design.
Method
The paper combines generalized curvature α and submodularity ratio γ, derives approximation guarantees, and bounds these parameters for several real-world objectives.
Results
Greedy achieves the tight approximation guarantee 1/α(1- e^-γα) for cardinality-constrained maximization, while Bayesian A-optimality solutions are comparable to SDP solutions and usually two orders of magnitude faster.
Takeaways & Limitations
The bounds enlarge the domain where Greedy has guarantees and support its principled use for several non-submodular applications.
Takeaways & Limitations
The framework assumes normalized set functions, with F(∅) = 0, and some application objectives are generally non-submodular.
Abstract
from arXiv · showhide
We investigate the performance of the standard Greedy algorithm for cardinality constrained maximization of non-submodular nondecreasing set functions. While there are strong theoretical guarantees on the performance of Greedy for maximizing submodular functions, there are few guarantees for non-submodular ones. However, Greedy enjoys strong empirical performance for many important non-submodular functions, e.g., the Bayesian A-optimality objective in experimental design. We prove theoretical guarantees supporting the empirical performance. Our guarantees are characterized by a combination of the (generalized) curvature $α$ and the submodularity ratio $γ$. In particular, we prove that Greedy enjoys a tight approximation guarantee of $\frac{1}α(1- e^{-γα})$ for cardinality constrained maximization. In addition, we bound the submodularity ratio and curvature for several important real-world objectives, including the Bayesian A-optimality objective, the determinantal function of a square submatrix and certain linear programs with combinatorial constraints. We experimentally validate our theoretical findings for both synthetic and real-world applications.
1. Introduction
The paper studies why GREEDY performs well for important non-submodular subset-selection problems despite lacking classical submodular guarantees. It combines curvature and submodularity ratio to provide guarantees and validates them across applications.
- Motivation: Experimental design and sparse modeling can be formulated as cardinality-constrained subset selection problems over set functions.These problems arise when experiments are costly or sparse representations are sought for interpretability and robustness.
- Motivation: GREEDY has a (1 − 1/e) guarantee for monotone nondecreasing submodular functions, but this guarantee generally fails when the objective is non-submodular.Experimental design and sparse Gaussian-process applications can have non-submodular objectives despite good empirical GREEDY performance.
- Contributions: The paper derives improved constant-factor GREEDY guarantees for non-submodular nondecreasing functions by combining generalized submodularity ratio γ and curvature α.The resulting characterization is intended to explain empirical success over a broader class of objectives.
- Contributions: The theory provides first guarantees for Bayesian A-optimality, determinantal square-submatrix objectives, and linear programs with combinatorial constraints.These applications include auxiliary set functions arising from continuous optimization with support constraints.
- Experimental validation: For Bayesian A-optimality, GREEDY produces comparable solutions to a semidefinite-programming method while usually running two orders of magnitude faster.The paper also experimentally validates its theory on synthetic and real-world applications.
2. Submodularity Ratio and Curvature
This section extends submodularity ratio and curvature to general nondecreasing set functions, including versions measured along GREEDY's successive selections. These parameters characterize how closely objectives exhibit submodular or supermodular behavior and support the paper's approximation analysis.
- Submodularity ratio: The greedy submodularity ratio γG is defined along the successive sets selected by GREEDY and satisfies γG ≥ γ.The marginal gain at GREEDY step t is denoted ρt := ρjt(St−1).
- Submodularity ratio: The submodularity ratio measures the extent to which a set function has submodular properties; γ = 1 exactly characterizes submodularity for nondecreasing functions.Both γ and γG lie in [0, 1].
- Curvature: Generalized curvature α and greedy curvature αG extend curvature notions to non-submodular functions, with αG ≤ α.For nondecreasing functions, both parameters lie in [0, 1].
- Curvature: For submodular functions, the greedy curvature satisfies αG ≤ α = αtotal, while α = 0 characterizes supermodularity.The paper notes that αG often characterizes the problem more closely than αtotal.
3. Approximation Guarantee
The paper gives Greedy a tight approximation guarantee for nonnegative, nondecreasing set functions under a cardinality constraint, combining submodularity ratio γ and curvature α. The guarantee recovers several classical special cases and is tight for every admissible parameter pair.
- Theorem 1: 1/α(1 − e^−γα) is Greedy’s approximation guarantee for nonnegative, nondecreasing functions with submodularity ratio γ and curvature α.The guarantee applies to cardinality-constrained maximization and uses either of the paper’s versions of these generalized quantities.
- Interpreting Theorem 1: When γ = 1, the guarantee becomes α^−1(1 − e^−α), recovering the bounded-curvature submodular result.When α = 1, it becomes 1 − e^−γ; when α = 1 and γ = 1, it recovers 1 − 1/e.
- Proof Strategy: The proof framework extends the bounded-curvature submodular analysis of Conforti and Cornuéjols to non-submodular functions.Adapting that framework requires several changes, detailed in the paper’s later proof section.
- Proof Strategy: The proof analyzes groups of instances by Ω* ∩ S_K, constructs linear programs from their properties, and shows the worst case occurs when Ω* ∩ S_K = ∅.The resulting worst-case ratio is the stated theorem bound.
- Tightness Result: The guarantee is tight: for every submodularity ratio γ and curvature α, a set function achieves the bound exactly.The paper constructs objective functions whose submodularity ratio and curvature equal the prescribed parameters and for which Greedy attains the bound.
- Tightness Result: The tightness construction makes Greedy select S because corresponding elements have equal marginal gains, while the optimal solution is the disjoint set Ω.The constructed objective has F(Ω) = 1, and the resulting approximation ratio matches Theorem 1.
4. Applications
The paper applies its curvature–submodularity-ratio framework to Bayesian A-optimality, determinantal objectives, and LPs with combinatorial constraints, establishing parameter bounds that make Greedy guarantees applicable.
- Applications: Bounds on curvature and submodularity ratio make the theoretical Greedy guarantees applicable to Bayesian A-optimality, determinantal functions, and LPs with combinatorial constraints.The paper presents these as important applications where such guarantees were previously unavailable.
- Bayesian A-optimality: Bayesian A-optimality selects experiments to reduce posterior parameter variance, but its objective is generally non-submodular.The formulation uses a linear-Gaussian model with normalized stimuli and an isotropic Gaussian prior.
- Determinantal functions: The determinantal objective is generally non-submodular even though its logarithm is submodular; its curvature is 0 because the objective is supermodular.For eigenvalues λ1 ≥ ··· ≥ λn > 1, the greedy submodularity ratio has a lower bound depending on K and λn.
- Applications: The applications include production planning with budget and K-production-line constraints, alongside subset selection and sparse modeling.These examples motivate using auxiliary set functions for continuous optimization under combinatorial support constraints.
- LPs with combinatorial constraints: For LPs with combinatorial constraints, the induced set function is normalized and nondecreasing, with submodularity ratio bounded below by γ0 > 0.The curvature can be 1 in the worst case, while the submodularity ratio remains bounded away from zero under regular non-degeneracy assumptions.
5. Experimental Results
Experiments evaluate Greedy through objective quality, greedy curvature, and greedy submodularity ratio across Bayesian A-optimality, constrained LPs, and determinantal objectives.
- Experimental protocol: 20 repeated experiments were averaged, using greedy versions αG and γG because exhaustive calculation of full α and γ was too time consuming.The experiments cover synthetic and real-world applications.
- Bayesian Experimental Design: Greedy solutions are near-optimal on synthetic and Boston Housing Bayesian A-optimality experiments and are roughly comparable with SDP solutions.The Boston Housing results also report γG close to 1 and αG less than 1.
- Bayesian Experimental Design: Two orders of magnitude faster: Greedy usually outpaces SDP on medium-scale Bayesian A-optimality problems.The comparison varies feature and sample counts and uses runtime ratios summarized in Table 1.
- LPs with Combinatorial Constraints: For constrained synthetic LPs, γG ranges from approximately 0.15 to 1 while curvature is close to its worst-case value of 1.The observed parameter behavior is consistent with the theory for these LP objectives.
- Determinantal Functions: For synthetic determinantal objectives, γG reasonably predicts Greedy performance against the optimal objective value.The experiments use random covariance matrices with uniformly distributed eigenvalues in [0, 1].
- Determinantal Functions: CIFAR-10 active-set selection shows results similar to the synthetic determinantal experiments.The covariance matrix is computed from the first 12 test images using a squared exponential kernel.
6. Related Work
The paper situates its curvature and submodularity-ratio analysis among related notions of approximate, weak, and other forms of non-submodularity and their optimization methods.
- Approximation guarantees: The approximation-proof framework resembles prior curvature-based submodular analyses, but the LP construction and structural arguments require different techniques for non-submodular functions.The paper identifies three proof components that differ from the earlier framework.
- Approximate submodularity: Approximate submodularity uses an additive diminishing-returns error ε, yielding Greedy guarantees with an additive Kε loss.This differs from the paper’s curvature and submodularity-ratio characterization.
- Weak submodularity: Weak submodularity does not imply, and is not implied by, having positive submodularity ratio and curvature below 1.The paper explicitly states that these two properties need not entail one another.
- Other notions: Other related measures include supermodular degree and submodularity index, which characterize guarantees for different greedy or randomized procedures.These measures arise in welfare maximization and non-monotone maximization settings.
- Optimization methods: The submodular-supermodular procedure and cooperative-cut methods address optimization problems involving non-submodular functions, often through minimization formulations.The cited work covers difference-of-submodular minimization and unconstrained cooperative cuts.
7. Conclusion
The paper proves tight Greedy guarantees for non-submodular nondecreasing set functions by combining generalized curvature and submodularity ratio, then validates the framework across applications.
- Conclusion: The paper’s central result is the first tight approximation bounds for Greedy expressed through generalized curvature α and submodularity ratio γ.These bounds enlarge the class of non-submodular maximization problems with guarantees.
- Conclusion: The paper validates its theory experimentally and derives parameter bounds for Bayesian A-optimality, determinantal functions, and LPs with combinatorial constraints.Additional application results and proofs are provided in the appendices.
- Curvature and submodularity: Curvature α = 0 is equivalent to supermodularity for nondecreasing functions, while γ = 1 characterizes submodularity.These relationships connect the generalized quantities to classical structural properties.
- Curvature relations: For nondecreasing submodular functions, the greedy curvature is no larger than the generalized and total curvature.The paper proves αG ≤ α = αtotal in this special case.
- Proof strategy: The proof combines definitions of curvature, submodularity ratio, and Greedy’s selection rule within a linear-programming worst-case analysis.The framework adapts prior curvature-based proof ideas to non-submodular functions.
B.5. Proof of Lemma 3
The proof transforms the LP constraint structure in two stages while preserving a nonincreasing objective, establishing the required comparison with the empty set. It then uses convexity and monotonicity to derive the submodularity ratio and curvature.
- Proof strategy: The proof first makes joint elements adjacent, then removes joint columns from left to right while the LP objective value never increases.These two structural operations establish R({l1, ..., ls}) ≥ R(∅).
- Proof strategy: The construction distinguishes joint elements in Ω∗∩SK from disjoint elements and tracks adjacency through neighboring indices.This classification determines which constraint-matrix columns are exchanged during Step 1.
- Parameter bounds: The submodularity ratio reaches its lower bound when B = ∅ and B′ = Ω, using convexity and monotonicity of f on [0, K].The proof explicitly identifies this configuration as attaining the minimum.
- Parameter bounds: The curvature bound is obtained by lower-bounding the relevant marginal-gain ratio in two cases; together, they prove curvature α.The argument again relies on convexity and monotonicity of f.
- Relation to classical notions: The generalized parameters extend classical notions defined for submodular functions, whose curvature quantifies distance from modularity and whose ratio characterizes submodularity.For nondecreasing functions, γ = 1 is equivalent to submodularity.
C.2. Curvature of Non-submodular Functions and Relation to Our Results
This section relates the paper’s curvature to prior curvature notions and explains why combining generalized curvature with submodularity ratio gives more expressive Greedy guarantees. It also outlines parameter-bounding techniques for application objectives.
- Curvature relations: The prior curvature c satisfies c ≥ α, so its guarantee 1 − c is no better than 1 − α for the compared function class.The relation follows directly from the definitions and the tightness construction.
- Curvature relations: When α = 1, the prior guarantee becomes 0, whereas the paper’s guarantee remains γ for γ ∈ (0, 1].The comparison is stated for the tightness-result class.
- Curvature relations: The paper’s curvature α is a natural extension of classical curvature for monotone submodular functions and measures closeness to supermodularity.Classical curvature instead measures closeness to modularity.
- Curvature relations: The combined curvature–submodularity-ratio characterization is described as tight for Greedy and more expressive than curvature c alone.The paper also notes that the two parameter combinations do not imply weak submodularity in either direction.
- Application bounds: For Bayesian A-optimality, the analysis bounds parameters using spectral properties of XSX⊤, including eigenvalue and singular-value relations.The data-point normalization assumption yields ∥X∥ ≤ √n.
D.2. Proofs for Determinantal Functions of Square Submatrix
The determinantal-function proofs establish supermodularity and derive parameter bounds through matrix and LP arguments. Two LP examples demonstrate non-submodularity, while the Bayesian A-optimality formulation is reduced to an SDP for selection.
- Determinantal functions: The proof establishes that the determinantal objective F(·) is supermodular.This follows from comparing marginal gains for nested sets.
- Determinantal functions: The determinantal parameter analysis combines numerator and denominator bounds, with |Ω\S| ≤ K supplying the final inequality.The proof organizes these bounds through equations (28) and (29).
- LP objectives: F({1, 2}) − F({2}) < F({1, 2, 3}) − F({2, 3}) demonstrates non-submodularity in the first LP example.The example gives F({1, 2}) = 4, F({2}) = 2, F({1, 2, 3}) = 8, and F({2, 3}) = 4.
- LP objectives: The second LP example exhibits the same strict marginal-gain inequality but has degenerate basic feasible solutions.Its listed objective values are 120, 120, 136, and 120 for the corresponding sets.
- Bayesian A-optimality: For Bayesian A-optimality, binary selection is relaxed and converted through the Schur complement lemma into an SDP.The largest K coordinates of the relaxed λ solution are selected after sorting them in descending order.
F. Proofs and Details in Related Work (Section 6)
The related-work section contrasts the paper’s parameters with weak submodularity and connects its framework to subset selection, sparse modeling, and budget allocation. These applications use auxiliary set functions that Greedy can optimize under their constraints.
- Parameter relations: Bounds on γ away from 0 and α away from 1 do not imply weak submodularity, and weak submodularity does not imply those bounds.The paper gives separate counterexamples for both directions.
- Parameter relations: For F(S) = |S|^4, the function is supermodular with curvature 0 and submodularity ratio lower-bounded by n^-3, yet it is not weakly submodular.This supplies the counterexample for one implication.
- Parameter relations: For the minimum-cardinality function with k = 2, weak submodularity holds while the submodularity ratio is 0.This supplies the counterexample for the reverse implication.
- Applications: In subset selection, the R2 objective measures the fraction of variance in Z explained by variables in S, and prior work lower-bounds its submodularity ratio by λmin(C).The paper suggests curvature analysis could further improve Greedy guarantees for this objective.
- Applications: Sparse modeling minimizes loss subject to |supp(x)| ≤ K, and Greedy maximizes the corresponding auxiliary set function.Strong convexity and Lipschitz-gradient assumptions support prior submodularity-ratio bounds, while curvature analysis may improve them.
- Applications: In optimal budget allocation, Greedy maximizes an auxiliary function for a DR-submodular influence objective under continuous and combinatorial constraints.Studying its submodularity ratio and curvature can yield theoretical guarantees.
H.1. Bayesian A-optimality Experiments
Synthetic experiments use a randomly generated multivariate Gaussian dataset to compare approximation bounds with GREEDY’s performance. The reported results cover experimental-design function values, parameters, bounds, and an R2 objective.
- The synthetic data come from a multivariate Gaussian distribution with correlation 0.5.The experiment uses one randomly generated dataset.
- Figure 8 reports function values, parameters, and approximation bounds for the experimental-design objective.
- The experimental-design dataset contains d = 6 features and n = 12 observations.
- Theorem 1 and Lemma 3 provide two plotted bounds: the constant-factor bound α^-1(1 −e^-αγ) and a K-dependent bound.
- Both bounds give reasonable predictions of GREEDY’s performance.
- Figure 9 reports results for the R2 objective on synthetic data.