Abstract
We present the first mini-batch algorithm for maximizing a non-negative monotone decomposable submodular function, $F=\sum_{i=1}^N f^i$, under a set of constraints. We improve over the sparsifier based approach both in theory and in practice. We experimentally observe that our algorithm generates solutions that are far superior to those generated by the sparsifier based approach.
The Challenge of Scale in Submodular Optimization
Submodular functions are fundamental in machine learning and data science, capturing the principle of "diminishing returns." They are widely used for tasks like selecting representative image sets, optimizing sensor placements, or choosing thumbnails for video platforms. In many modern applications, the objective function $F$ is decomposable: it is the sum of $N$ smaller functions $f^i$, representing individual user preferences or data points.
While the standard Greedy Algorithm provides strong approximation guarantees, its computational cost is prohibitive for massive datasets. With $N$ functions and $n$ possible items to select, the complexity is $O(Nnk)$. When $N$ reaches millions, the algorithm becomes a bottleneck. Previous solutions relied on "sparsifiers"—sampling a subset of functions once at the start. However, these often require expensive $O(Nn)$ preprocessing to calculate importance weights, which still scales with the full dataset size $N$.
The Mini-batch Greedy Algorithm
To address these limitations, we propose the Mini-batch Greedy Algorithm. Unlike one-time sparsification, our approach samples a fresh "mini-batch" of functions at every step of the greedy selection process. This iterative sampling allows the algorithm to "correct" itself over time, leading to more robust performance and better theoretical guarantees.
As shown in Algorithm 3, at each iteration $j$, the algorithm calls a sampling procedure (Algorithm 2) to create a temporary, smaller estimate of the objective function $\hat{F}^j$. The next element $e_j$ is then chosen based on this estimate. This process repeats until $k$ elements are selected.
Theoretical and Practical Advantages
A key contribution of this work is the analysis of uniform sampling. While weighted sampling is often preferred in theory to handle "worst-case" scenarios, we demonstrate that uniform sampling—which requires zero preprocessing—is highly effective in practice. We bridge this gap using smoothed analysis, assuming that real-world data is not adversarial but possesses some natural underlying structure.
The table above highlights the theoretical improvements. Notably, for uniform sampling, our method eliminates the $O(Nn)$ preprocessing step entirely, making the complexity independent of the total number of functions $N$. This is the "holy grail" for big data optimization, as it allows for near-optimal results without ever needing to process the entire dataset at once.
Key Results and Insights
- Efficiency: By bypassing $O(Nn)$ preprocessing, uniform mini-batching provides a massive speedup over traditional sparsifiers.
- Stability: Sampling a new batch at every step is more stable than one-time sampling. Our algorithm achieves near-optimal approximation ratios, specifically $(1 - 1/e - \epsilon)$ for cardinality constraints.
- Empirical Success: Evaluated on diverse datasets including Uber pickups, Discogs style coverage, and image clustering (CIFAR100, FashionMNIST), the mini-batch approach consistently outperformed state-of-the-art sparsifiers in solution quality for small sample sizes.
Future Directions
While the mini-batch approach is powerful for monotone functions under cardinality constraints, extending these guarantees to more complex constraints (like knapsack or general matroids) or non-monotone functions remains an active area of research. Additionally, exploring how the "curvature" of the submodular function impacts these mini-batch bounds could lead to even tighter theoretical guarantees.
Summary updated