Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications to Parallel Machine Learning and Multi-Label Image Segmentation

Kai Wei, Rishabh Iyer, Shengjie Wang, Wenruo Bai, Jeff Bilmes

TL;DR

This paper introduces scalable algorithms for "Submodular Partitioning," a framework that balances robust (worst-case) and average-case performance when dividing data or tasks. By bridging the gap between high-level theoretical guarantees and real-world scalability, the authors demonstrate significant improvements in distributed machine learning convergence and unsupervised image segmentation.

What Problem Does This Paper Address?

In many fields—from parallel computing to computer vision—we need to partition a set of items into groups. Traditionally, researchers have optimized for one of two extremes:

  1. Average-case (Welfare): Maximize the total utility across all groups (e.g., maximizing total throughput in a cluster).
  2. Robust-case (Fairness/Load Balancing): Maximize the utility of the worst-off group to ensure no single node becomes a bottleneck.

While average-case algorithms are often fast and scalable, robust-case algorithms (like Submodular Fair Allocation) have historically relied on complex, non-scalable theoretical constructions. Furthermore, real-world applications rarely fall perfectly into one bucket; a system designer might want a "mixed" objective that ensures decent performance for everyone while still pushing for high overall efficiency.

The authors address this by providing a unified framework for mixed robust/average submodular partitioning, offering new algorithms that are both theoretically sound and fast enough for "big data" applications.

A taxonomy of the partitioning problems addressed in this work, showing how they generalize existing robust and average-case problems.

Methods

The paper introduces several algorithmic frameworks tailored for submodular functions (functions that exhibit a "diminishing returns" property):

  • Greedy Strategies: The authors propose GreedMax and GreedSat. GreedMax is a simple, scalable approach for the homogeneous case (where all groups use the same utility function), while GreedSat uses a "saturate" approach to handle heterogeneous settings.
  • Majorization-Minimization (MMin) & Minorization-Maximization (MMax): These iterative algorithms use modular bounds (linear approximations) of submodular functions to solve complex partitioning problems through a sequence of simpler ones.
  • Lovász Extension Relaxation: For load balancing problems, the authors use the Lovász extension to relax discrete partitioning into a continuous convex optimization problem, which is then rounded back to a discrete solution.
  • Extremal Combination Schemes: To handle the "mixed" objective (controlled by a parameter $\lambda$), they propose schemes like CombSfaSwp that intelligently combine solutions from the pure robust and pure average-case algorithms.

Datasets

The efficacy of these algorithms was tested across diverse domains:

  • Synthetic Data: Facility location and set cover functions used to verify theoretical approximation bounds on small-scale controlled instances.
  • Distributed Convex Optimization: The 20Newsgroups text dataset, using ADMM (Alternating Direction Method of Multipliers) to train logistic regression models.
  • Distributed Deep Learning: The MNIST (handwritten digits) and TIMIT (speech recognition) datasets, used to evaluate how data partitioning affects the convergence of distributed Neural Networks.
  • Image Segmentation: The Grab-Cut dataset (30 color images), treated as an unsupervised pixel-partitioning task.

Key Insights and Ideas

  • The Power of Submodularity: Submodular functions are naturally suited for these tasks because they can model "diversity" (in maximization) or "redundancy" (in minimization). For example, in distributed learning, you want each data partition to be as "diverse" as the whole set so that local models don't diverge too far from the global truth.
  • Scalability vs. Theory: The authors show that simple greedy heuristics, which are often overlooked in pure theory papers, can actually achieve tighter approximation bounds in specific settings (like the $1/m$ factor for GreedMax) than much more complex existing algorithms.
  • The "Mixed" Sweet Spot: In image segmentation, the authors found that neither the pure robust nor the pure average objective was optimal. Instead, a mix ($\lambda \approx 0.2$) yielded the best F-measure, suggesting that balancing these two perspectives is key to capturing natural image structures.

Key Results

The paper provides a comprehensive suite of new approximation factors, summarized in the table below:

Summary of the approximation guarantees for Problem 1 (Maximization). Note the new bounds achieved by the authors' proposed algorithms (marked with asterisks).
  • Distributed Training: Submodular partitioning significantly outperformed random partitioning. On the 20Newsgroups task with 5 partitions, the submodular approach reached higher test accuracy in fewer iterations, effectively dampening the "oscillations" common in distributed optimization.
  • Neural Networks: For TIMIT speech data, submodular partitioning provided a more balanced computational load and faster convergence compared to random or adversarial partitioning.
  • Image Segmentation: The proposed method achieved an F-measure of 0.870 on the Grab-Cut dataset, outperforming standard baselines like k-means (0.810), k-medoids (0.823), and even specialized Graph Cut methods (0.853).

Limitations and Future Work

While the greedy and MMax/MMin algorithms are highly scalable, the Lovász Rounding approach involves solving a convex program that can become computationally expensive for very large ground sets. The authors suggest using greedy heuristics (like GeneralGreedMin) as a practical alternative for these cases.

Future research could explore more complex classes of submodular functions or extend these partitioning techniques to dynamic settings where data arrives in a stream, further pushing the boundaries of parallel machine learning efficiency.

Summary updated

Abstract

We study two mixed robust/average-case submodular partitioning problems that we collectively call Submodular Partitioning. These problems generalize both purely robust instances of the problem (namely max-min submodular fair allocation (SFA) and min-max submodular load balancing (SLB) and also generalize average-case instances (that is the submodular welfare problem (SWP) and submodular multiway partition (SMP). While the robust versions have been studied in the theory community, existing work has focused on tight approximation guarantees, and the resultant algorithms are not, in general, scalable to very large real-world applications. This is in contrast to the average case, where most of the algorithms are scalable. In the present paper, we bridge this gap, by proposing several new algorithms (including those based on greedy, majorization-minimization, minorization-maximization, and relaxation algorithms) that not only scale to large sizes but that also achieve theoretical approximation guarantees close to the state-of-the-art, and in some cases achieve new tight bounds. We also provide new scalable algorithms that apply to additive combinations of the robust and average-case extreme objectives. We show that these problems have many applications in machine learning (ML). This includes: 1) data partitioning and load balancing for distributed machine algorithms on parallel machines; 2) data clustering; and 3) multi-label image segmentation with (only) Boolean submodular functions via pixel partitioning. We empirically demonstrate the efficacy of our algorithms on real-world problems involving data partitioning for distributed optimization of standard machine learning objectives (including both convex and deep neural network objectives), and also on purely unsupervised (i.e., no supervised or semi-supervised learning, and no interactive segmentation) image segmentation.
BibTeX
@inproceedings{wei2015mixed,
  author = {Kai Wei and Rishabh Iyer and Shengjie Wang and Wenruo Bai and Jeff Bilmes},
  title = {{Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications to Parallel Machine Learning and Multi-Label Image Segmentation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=H1-VRObd-S},
}
Figure