An Online Algorithm for Maximizing Submodular Functions

Matthew J. Streeter, Daniel GolovinNeurIPS 2008

This paper, presented by Matthew Streeter and Daniel Golovin, tackles the challenge of making optimal decisions in real-time when faced with tasks that exhibit "diminishing returns." By combining submodular optimization with online learning, the authors provide a robust framework for problems ranging from database query optimization to managing portfolios of SAT solvers.

TL;DR

The authors present an online algorithm that learns to schedule resources (like CPU time) to maximize task completion when the reward function is submodular. Their approach achieves near-optimal performance compared to the best possible schedule in hindsight and outperforms top-tier solvers in practical SAT competition benchmarks.

The Challenge: Online Resource Allocation

Imagine you have a sequence of jobs arriving one by one. To finish a job, you can spend time on various "activities" (e.g., different search algorithms). You don't know how long a specific job will take or which activity is best until you try it.

The authors model this as an online resource allocation problem. The core challenge is that the utility of these activities is submodular. In plain English, this means "diminishing returns": the more time you've already invested in a task, the less a single extra second of work is likely to help.

The goal is to find a schedule (a sequence of actions) that performs well across two metrics:

  1. Benefit Maximization: Completing as many jobs as possible within a fixed time budget $T$.
  2. Cost Minimization: Minimizing the average time required to complete each job.

Methods: The Online Greedy (OG) Algorithm

The paper builds on the well-known Greedy Algorithm for submodular maximization. In an offline setting (where all job difficulties are known), the greedy approach—picking the action that provides the most "bang for your buck" at each step—is known to be a powerful approximation.

To move this into the Online realm (where jobs arrive one at a time), the authors introduce the OG (Online Greedy) algorithm:

  • Action Selection: The algorithm maintains a sequence of "experts" (using a no-regret algorithm like Randomized Weighted Majority). Each expert is responsible for choosing the action at a specific time step in the schedule.
  • Probabilistic Scheduling: To handle actions with different durations ($\tau$), the algorithm uses a clever trick: it appends a chosen action to the schedule with a probability of $1/\tau$. This ensures that, in expectation, the time spent matches the intended budget.
  • Feedback Loops: After a job is processed, the algorithm observes the "payoff" (how much closer the job got to completion) and updates its internal experts to perform better on future jobs.

Key Insights

  • Submodularity as a Universal Language: Many classic problems, like "Pipelined Set Cover" or "Budgeted Maximum Coverage," are actually special cases of this submodular framework. This makes the OG algorithm widely applicable.
  • Online-to-Offline Bridge: The paper proves that if you have a good online "expert" learner, you can combine multiple instances of it to approximate a complex, non-linear greedy schedule with provable regret bounds.
  • The Power of Portfolios: The algorithm doesn't just pick the "best" solver. It learns a portfolio—a sequence of different solvers—which is much more robust because one solver might be fast on easy problems while another excels at "heavy-tailed" difficult ones.

Empirical Results: SAT Solver Competition

The authors evaluated their algorithm using data from the 2007 SAT Solver Competition. The dataset consisted of a matrix of solve times for various SAT solvers (activities) across hundreds of benchmark instances (jobs), divided into "Industrial," "Random," and "Hand-crafted" categories. The goal was to learn a schedule that interleaves different SAT solvers to solve the maximum number of instances within the competition's time limit.

Theoretical Guarantees: The authors prove that their algorithm is asymptotically 4-competitive for cost minimization and achieves a $(1 - 1/e)$ approximation for benefit maximization, matching the best possible theoretical bounds for these types of problems.

Empirical Success: On the SAT 2007 data, the Online Greedy (OG) algorithm consistently outperformed the single best solver in the competition and a "naïve parallel" strategy (running all solvers at equal strength).

SAT 2007 Competition Results

As shown in the results, in the "Industrial" category, the OG algorithm solved 149 instances, whereas the top-performing individual solver only solved 139.

Limitations and Future Work

  • Feedback Requirements: The most effective version of the algorithm requires "full information" feedback (knowing how every solver would have performed on a job after it's finished). In "opaque" settings where you only see the final result, the algorithm requires many more samples to converge.
  • Discrete Time Steps: The online model currently assumes actions have integer durations, which might require discretization for continuous-time problems.
  • Sample Complexity: The authors noted that for some categories, the number of available benchmark instances was almost too small for the online learner to reach its full potential, suggesting that the algorithm is best suited for long-running systems with a high volume of tasks.

Summary updated

BibTeX
@inproceedings{streeter2008online,
  author = {Matthew J. Streeter and Daniel Golovin},
  title = {{An Online Algorithm for Maximizing Submodular Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
}
Figure