Source-linked AI summary
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
Rishabh Iyer, Jeff A. Bilmes
TL;DR
The paper addresses minimization of differences between submodular functions, a formulation covering several machine-learning problems. It introduces monotone iterative algorithms with lower per-iteration cost and broader combinatorial-constraint support, while establishing hardness for multiplicative approximation and additive bounds for the optimum. Experiments on feature selection support the practical value of the procedures.
Problem
The paper studies how to minimize a difference between submodular functions across machine-learning applications and combinatorial constraints.
Method
The paper develops modular-bound-based iterative procedures, constructs submodular decompositions when possible, and analyzes their computational behavior and constraints.
Results
The algorithms monotonically reduce the objective, have lower per-iteration cost than prior methods, support several combinatorial constraints, and are empirically effective for feature selection.
Takeaways & Limitations
The procedures provide practical heuristics for difference-of-submodular optimization, including feature selection with submodular costs and problems involving complex combinatorial constraints.
Takeaways & Limitations
Multiplicative approximation is impossible in polynomial time unless P=NP, and general decomposition construction can be NP hard.
Abstract
from arXiv · showhide
We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a dierence between submodular functions. Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step. We empirically and theoretically show that the per-iteration cost of our algorithms is much less than [30], and our algorithms can be used to efficiently minimize a dierence between submodular functions under various combinatorial constraints, a problem not previously addressed. We provide computational bounds and a hardness result on the multiplicative inapproximability of minimizing the dierence between submodular functions. We show, however, that it is possible to give worst-case additive bounds by providing a polynomial time computable lower-bound on the minima. Finally we show how a number of machine learning problems can be modeled as minimizing the dierence between submodular functions. We experimentally show the validity of our algorithms by testing them on the problem of feature selection with submodular cost features.
1 Introduction
The paper develops algorithms for minimizing differences between submodular functions, motivated by machine-learning problems including feature selection, inference, sensor placement, and discriminative graphical models. Its procedures monotonically decrease the objective, reduce per-iteration cost, support combinatorial constraints, and offer theoretical and empirical guarantees.
- The paper studies minimizing v(X)=f(X)−g(X) for two submodular functions f and g.
- Applications: Feature selection can combine mutual-information objectives with submodular costs, yielding a difference between two submodular functions.Under naïve Bayes, mutual information is submodular; grouped feature-computation costs can exhibit diminishing returns.
- Contributions: The paper extends prior iterative methods with algorithms that monotonically reduce the objective and converge to a local minimum.The new procedures are designed to improve computational efficiency relative to the earlier approach.
- Contributions: The algorithms support cardinality, knapsack, matroid, and more complex constraints such as spanning trees, matchings, and cuts.
- Theory: No polynomial-time multiplicative approximation guarantee exists unless P=NP, even when the submodular decomposition is available.The paper instead provides polynomial-time computable additive bounds on the optimum.
- Experiments: Experiments on feature selection show better performance than greedy selection with lower cost.The comparison is made under feature-selection cost models, with greedy selection noted as near optimal under naïve Bayes assumptions.
2 Modular Upper and Lower bounds
This section develops tight modular lower and upper bounds for submodular functions. Lower bounds are parameterized through base-polytope or subgradient constructions, while upper bounds use conditional gains and are tight at a selected set.
- A convex function's first-order Taylor approximation provides a linear lower bound, motivating analogous modular bounds for submodular functions.
- Submodular functions admit both tight lower and upper bounds, unlike strictly convex functions, which have only a tight first-order lower bound.
- Modular Lower Bounds: Extreme subgradients of a submodular function correspond to chains whose successive increments equal function-value differences.The theorem characterizes extreme points of the subdifferential through a chain ending at the reference set.
- Modular Lower Bounds: The resulting modular lower bound is parameterized by a reference set Y and a permutation σ.
- Modular Upper Bounds: The conditional gain f(A|B)=f(A∪B)−f(B) measures the gain from adding A in the context of B.
- Modular Upper Bounds: Two tight modular upper bounds can be defined for any submodular function and are tight at the selected set X.
3 Submodular-Supermodular Procedure
The SubSup procedure minimizes a difference between submodular functions by replacing one component with a modular lower bound. It monotonically decreases the objective and converges to a local minimum, while any set function admits such a decomposition, though general construction can be computationally expensive.
- Procedure: The SubSup procedure replaces g with a modular lower bound and minimizes the resulting submodular function at each iteration.The procedure chooses a permutation whose chain contains the current set and minimizes the corresponding modularized objective.
- DS decomposition: Any set function v can be expressed as v(X)=f(X)−g(X) using suitable submodular functions f and g.The paper gives a combinatorial construction that avoids Hessians of polyhedral convex functions and produces a non-unique decomposition.
- DS decomposition: Constructing the decomposition generally requires exponentially complex computation of α and β.For certain set functions, β can be computed easily and a polynomial-time decomposition follows when a lower bound on α is available.
- DS decomposition: If α or a lower bound on α can be computed in polynomial time, the corresponding submodular functions f and g can also be obtained in polynomial time.This condition provides a tractable route to constructing decompositions for restricted classes of set functions.
- Guarantees: Algorithm 1 monotonically decreases the objective function and converges to a local minimum after checking at most O(n) permutations per iteration.Each iteration requires submodular function minimization, whose best stated complexity is O(n^5η+n^6), where η is the function-evaluation cost.
4 Alternate algorithms for minimizing DS functions
The paper introduces SupSub and ModMod as alternatives that preserve monotonic descent and local-minimum guarantees while reducing the cost of each iteration. These procedures also support constrained optimization and use permutation heuristics to improve practical performance.
- Overview: Both proposed algorithms monotonically reduce the objective at every iteration and converge to local minima.The guarantees apply to the alternate procedures for minimizing DS functions.
- SupSub: SupSub replaces f with a modular upper bound and performs submodular maximization instead of minimizing a submodular function.Approximate maximization does not generally preserve monotonic descent, so the algorithm compares or alternates between two modular upper bounds.
- SupSub: Under the stated local-maximization assumption, SupSub reaches a local optimum when neither modular upper bound improves the objective.The theorem covers both variants of Algorithm 2.
- ModMod: ModMod minimizes only a modular function at each iteration, which can be done in O(n) time.It retains monotonic decrease and reaches a local minimum after checking O(n) permutations with both modular upper bounds.
- Permutation choice: Permutation choice strongly affects solution quality, and gain-based heuristics perform better than random permutations in practice.For feature selection, the heuristic based on gains of v performs best among the discussed choices.
- Constraints: The algorithms can be extended to cardinality, knapsack, and matroid constraints, while one algorithm also handles spanning trees, matchings, and cuts.Constrained submodular minimization is difficult, whereas the proposed approach leverages submodular maximization procedures for constrained settings.
5 Theoretical results
Theoretical analysis shows that minimizing a difference of submodular functions is generally computationally difficult, with severe multiplicative inapproximability. Nevertheless, polynomial-time algorithms obtain additive guarantees and polynomial convergence bounds for approximate local optimization.
- 5 Theoretical results: The hardness results justify heuristic procedures that can scale to very large instances and remain practically useful.The paper specifically identifies the ModMod and SupSub procedures as scalable examples.
- 5.1 Hardness: Unless P = NP, no polynomial-time algorithm can achieve any positive polynomially computable multiplicative approximation for positive DS minimization.The hardness applies when f and g are given submodular functions and the objective is f(X) − g(X).
- 5.1 Hardness: Information-theoretic hardness shows that deterministic or randomized algorithms can perform arbitrarily poorly on general DS minimization.Consequently, finding a global optimum may require exponential time.
- 5.2 Polynomial time lower and upper bounds: Polynomial-time computable lower bounds on the objective minima yield worst-case additive approximation guarantees.These bounds estimate how far the algorithms are from the optimum.
- 5.3 Computational Bounds: The epsilon-approximate versions of Algorithms 1–3 converge to epsilon-approximate local optima in polynomial time.Each iteration proceeds only when the objective satisfies the specified multiplicative improvement condition.
- 5.3 Computational Bounds: The worst-case complexity is O(log(|M|/|m|) ...), with each iteration requiring submodular minimization, maximization, or modular minimization.The per-iteration cost is strongly polynomial in n, including O(n^5η + n^6) for the cited submodular minimization algorithm, O(n^2) for greedy maximization, and O(n) for modular minimization.
6 Experiments
The experiments evaluate feature-subset selection on Mushroom and Adult data using greedy, heuristic, and classifier-based comparisons. The proposed methods generally outperform greedy baselines, while ModMod and SupSub offer much lower runtime than SubSup.
- Experimental setup: Feature subset selection seeks smaller feature sets that retain nearly the same classification accuracy while reducing training and testing costs.The experiments select features under size or cost constraints because many features are correlated and redundant.
- Experimental setup: The study compares factored and non-factored mutual-information formulations, greedy methods, and the SupSub, SubSup, and ModMod procedures.Experiments use Mushroom and Adult datasets, with SVM and naïve Bayes classifiers.
- Runtime: SubSup is around 100 times slower than the greedy algorithm, whereas ModMod and SupSub are each only a few times slower.ModMod incurs additional cost from computing modular semigradients, while SubSup relies on general submodular function procedures.
- Classifier results: With all features, SVM reaches 99.6% accuracy on Mushroom and 83.9% on Adult, compared with 95.5% and 82.3% for naïve Bayes.These are the reported ten-fold cross-validation accuracies for the full feature sets.
- Classifier results: On Mushroom, SVM substantially outperforms naïve Bayes, and GrF performs much worse than the other algorithms.On Adult, SVM and naïve Bayes are more comparable, while the proposed algorithms generally outperform GrF and GrNF.
- Submodular cost selection: Under submodular feature costs, greedy methods perform much worse because the objective is no longer submodular even under the naïve Bayes assumption.This contrast is especially evident on the Mushroom dataset.
7 Discussion
The paper introduces algorithms and theory for minimizing differences between submodular functions, then evaluates them on feature selection with modular and submodular costs. ModMod is presented as a fast practical heuristic that performs comparably to competing procedures and supports combinatorial constraints.
- Contributions: The paper introduces new algorithms for optimizing the difference between two submodular functions and develops theoretical justification for related heuristics.The work also addresses applications and feature-selection experiments with modular and submodular costs.
- Practical implications: ModMod is fast at each iteration and performs about as well experimentally as SupSub and SubSup.This comparison is stated for the paper’s feature-selection experiments.
- Practical implications: ModMod can be used under various combinatorial constraints, making it the paper’s most promising practical heuristic.The paper presents this as a practical implication rather than a formal superiority claim.