Abstract
Most existing submodular maximization algorithms provide theoretical guarantees with approximation bounds. However, in many cases, users may be interested in an anytime algorithm that can offer a flexible trade-off between computation time and solution quality. This paper introduces Filtered Search (FS), a framework that provides a "tunable knob" ($\alpha$) to balance these factors, offering guaranteed approximation bounds for a wide variety of constraints and function types.
Introduction
Submodular functions, characterized by the property of "diminishing returns," are fundamental in machine learning applications such as image segmentation, sensor placement, and data summarization. While maximizing these functions is generally NP-hard, practitioners typically rely on greedy algorithms. Although efficient, greedy methods offer fixed theoretical guarantees (e.g., the $1 - 1/e$ bound for monotone functions under cardinality constraints).
There is a significant gap for researchers who require better-than-greedy solutions and are willing to invest more computation time, or conversely, need faster solutions for complex non-monotone functions. Existing "anytime" algorithms are often restricted to specific constraints. Filtered Search (FS) addresses this by providing a unified, flexible framework applicable to various constraints—including cardinality, partition, and knapsack—and both monotone and non-monotone functions.
The Filtered Search Framework
The authors frame submodular maximization as a state-space search problem, where each state represents a subset of elements. By adapting the classic A* search algorithm, they introduce several key innovations to make it practical for submodular optimization:
1. The Tunable Evaluation Function
The search is guided by a priority function: $$f(S) = g(S) + \alpha h(S)$$ where $g(S)$ is the current subset value, $h(S)$ is a heuristic estimating future potential gains, and $\alpha \in [0, 1]$ is the user-controlled parameter.
- When $\alpha = 0$, the algorithm behaves like a standard greedy search.
- When $\alpha = 1$, the search finds the global optimum.
2. Critical Admissibility (CA)
In standard A search, the heuristic $h(S)$ must be "admissible" (never underestimating the remaining gain). However, finding tight admissible bounds for submodular functions is computationally expensive. The authors prove that a weaker condition, Critical Admissibility*, is sufficient. CA only requires the heuristic to be accurate along the optimal path, significantly simplifying the implementation.
3. Modular Approximation
To compute $h(S)$ efficiently, the authors leverage the fact that submodular functions are bounded above by their modular approximations. For matroid and partition constraints, a simple greedy sub-routine is used; for knapsack constraints, a fractional relaxation is employed.
Experimental Evaluation
The framework was evaluated on a speech recognition task using the TIMIT Corpus. The goal was to select a subset of un-transcribed speech utterances to maximize a "cut function," which measures both similarity and diversity. To allow for comparison against the true global optimum, ground set sizes were kept between 20 and 30.
Results and Discussion
The experimental results demonstrate the effectiveness of the "tunable knob" across different constraint types.
As shown in Figure 1, increasing $\alpha$ consistently improves the solution quality ($g(S)$), eventually reaching the global optimum (indicated by the black horizontal line) at $\alpha = 1$. Notably, at $\alpha = 0.5$, Filtered Search already outperforms standard baselines like the Greedy algorithm and Lee’s algorithm across cardinality, partition, and knapsack constraints.
While the computation time increases with $\alpha$ (as seen in the bottom row of Figure 1), the CA heuristic allows for effective pruning of the search space. In practice, the algorithm examines only a small fraction of the possible $2^{|U|}$ states. Furthermore, the framework successfully handles non-monotone cut functions, which are traditionally more challenging to optimize than monotone ones.
Conclusion
Filtered Search provides a theoretical bridge between greedy heuristics and exact combinatorial optimization. While computation time can spike as $\alpha$ approaches 1—making the optimal setting impractical for very large datasets—the framework's flexibility is a major step forward. Future work may involve integrating AI techniques such as partial-order reduction and symmetry detection to further prune the search space, potentially enabling high-$\alpha$ searches on much larger ground sets.
Summary updated