Abstract
Many optimization objectives in machine learning and data mining seek to minimize set functions under cardinality constraints. This paper introduces the concept of weak-$\alpha$-supermodularity, a theoretical framework that explains why simple greedy algorithms work surprisingly well for complex minimization problems. We prove that such problems benefit from a greedy extension phase. Specifically, let $S^*$ be the optimal set of cardinality $k$ that minimizes $f$ and let $S_0$ be an initial solution such that $f(S_0)/f(S^*) \le \rho$. We demonstrate that a greedy extension $S \supset S_0$ of size $|S| \le |S_0| + \lceil \alpha k \ln(\rho/\varepsilon) \rceil$ yields a solution where $f(S)/f(S^*) \le 1+\varepsilon$. This framework provides new bicriteria results for $k$-means clustering, sparse regression, and column subset selection.
Introduction
Subset selection is a fundamental task in machine learning: given a large collection of items (such as features, data points, or columns), how do we select a small subset of size $k$ that minimizes a specific cost function $f(S)$? While greedy algorithms—which iteratively pick the best available item—are the standard in practical implementations, they often lack rigorous theoretical guarantees for the non-convex, NP-hard problems encountered in the real world.
Traditionally, strong guarantees for greedy algorithms have been reserved for "supermodular" functions. However, many essential problems, including $k$-means clustering and sparse regression, do not satisfy strict supermodularity. This research bridges the gap by defining a broader class of functions—weakly supermodular functions—where greedy approaches are provably effective.
Defining Weak-$\alpha$-Supermodularity
The authors introduce weak-$\alpha$-supermodularity as a relaxation of standard supermodularity.
- The Intuition: In a perfectly supermodular function, the marginal gain from adding the single best element is at least the average gain of adding an entire set of optimal elements.
- The Relaxation: A function is defined as weakly-$\alpha$-supermodular if the best single element provides at least $1/\alpha$ times that average gain.
By introducing the parameter $\alpha$, the authors demonstrate that supermodularity is not a binary property but a spectrum. Many real-world problems are "mostly" supermodular, and their computational difficulty scales gracefully with the value of $\alpha$.
The Greedy Extension Algorithm
The core contribution of this work is the Greedy Extension Algorithm. Rather than attempting to find the optimal set of size $k$ from scratch, the algorithm utilizes a two-phase approach:
- Initialization: Start with an initial solution $S_0$ that provides a rough approximation (a constant factor $\rho$).
- Greedy Extension: Iteratively add elements to $S_0$ until the cost function drops below a target threshold.
This leads to a "bicriteria" guarantee: by allowing the set size to grow slightly larger than the target $k$ (specifically by a factor involving $\alpha$ and the logarithm of the desired error $\varepsilon$), one can achieve a $(1+\varepsilon)$ approximation of the optimal cost. This approach makes previously intractable problems theoretically manageable by trading a small amount of "budget" (set size) for high precision.
Framework Applications
The paper applies this unifying framework to three major problems in data science:
1. Sparse Multiple Linear Regression (SMLR)
The authors prove that SMLR is weakly-$\alpha$-supermodular. They improve upon classic results (e.g., Natarajan, 1995) by reducing the bound for the number of features needed to reach a target error by a factor of 2. Crucially, this theory extends to "under-constrained" cases where the number of features exceeds the number of observations.
2. $k$-means Clustering
The research provides new bicriteria results for both constrained and unconstrained $k$-means. By greedily extending an initial solution (such as one generated by $k$-means++), the algorithm achieves a $(1+\varepsilon)$ approximation with a set size of only $O(k \log(1/\varepsilon))$.
3. Column Subset Selection (CSSP)
As CSSP is a special case of sparse regression, the framework provides the first bicriteria results for CSSP that relate the size of the chosen column set to the condition number of the matrix, offering a new tool for numerical linear algebra.
Limitations and Future Directions
While the framework is powerful, its efficiency is tied to the value of $\alpha$. In sparse regression, $\alpha$ is related to the inverse of the smallest singular value; if this value is very small, $\alpha$ becomes large, weakening the guarantee on the final set size. Additionally, the algorithm requires a "good" initial solution $S_0$. While such solutions are readily available for $k$-means, they may be more difficult to identify for other weakly supermodular functions. Future work may focus on reducing the computational cost of the greedy steps or finding tighter bounds for $\alpha$ in specific domains.
Summary updated