Multivariate Submodular Optimization

Richard Santiago, F. Bruce ShepherdICML 2019

Overview

This paper introduces a generalized framework for Multivariate Submodular Optimization (MVSO), where a set of resources must be selected and then partitioned among $k$ different agents to optimize a joint objective. The authors establish the "Multivariate Gap"—the performance loss incurred when moving from single-agent to multi-agent settings—and provide near-optimal approximation algorithms for both maximization and minimization.

Introduction & Problem Statement

Submodular functions are the "convex functions" of the discrete world, capturing the intuitive property of diminishing returns: adding an element to a small set helps more than adding it to a large one. While single-agent submodular optimization (finding one set $S$ to maximize $f(S)$) is well-studied, many real-world problems are inherently collaborative or competitive.

Imagine a sensor placement problem: you have a budget of sensors, but you need to deploy them across $k$ different locations (agents). The total "informativeness" depends not just on which sensors you pick, but how you distribute them. If two agents place sensors too close to each other, their utility might overlap, creating redundancy.

Previous work often assumed "separable" objectives—where each agent has their own independent submodular function. This paper tackles the much harder non-separable case, where a single "joint" function $f(S_1, S_2, \dots, S_k)$ accounts for complex interactions between agents.

Methodology

The authors bridge the gap between single-agent and multivariate optimization using three primary techniques:

  1. The Lifting Reduction: They show that an MVSO problem can be transformed into a standard single-agent problem by "lifting" the ground set. Essentially, they create $k$ disjoint copies of the original items (one for each agent). This allows them to use existing single-agent machinery, though it comes with a potential loss in approximation quality. The structural mapping of constraints from the multivariate space to the reduced single-agent space is a key enabler of this technique.
Constraint mapping between multivariate and single-agent reduced problems.
  1. Multilinear Relaxation: For maximization, the authors use a continuous extension of the submodular function. By solving the problem in continuous space and then rounding the result back to a discrete partition, they can handle very general constraints (like matroids or $p$-systems).
  2. Curvature Analysis: For minimization, the authors utilize the concept of curvature ($c$), which measures how far a submodular function is from being "modular" (linear). This allows them to provide much tighter bounds than would be possible for general submodular functions.

Evaluation & Theoretical Bounds

As a theoretical contribution to algorithmic game theory and combinatorial optimization, this paper does not evaluate against standard empirical datasets (like MNIST or ImageNet). Instead, it provides:

  • Mathematical Examples: Specific constructions of $k$-multi-submodular functions using multilinear and quadratic forms.
  • Information-Theoretic Lower Bounds: Proofs showing the fundamental limits of how well any algorithm can perform in the "value oracle model" (where the algorithm can only learn about the function by querying specific sets).

Key Insights

  • The Multivariate (MV) Gap: The authors define this as the approximation factor loss incurred by moving to the multivariate setting. For maximization, they prove this gap is a constant $(1-1/e)$, meaning we don't lose much. For minimization, however, the gap can be as large as $O(n/\log n)$.
  • Maximization is Robust: A surprising insight is that if you have a good algorithm for a single-agent problem, you can almost always turn it into a good algorithm for the multi-agent version with only a small, constant-factor penalty.
  • Minimization is Brittle: Unlike maximization, multivariate minimization is significantly harder than its single-agent counterpart. The authors show that even if the single-agent version is easy, the multi-agent version can be "hard" unless the function has specific curvature properties.
  • Invariance: For certain structures like matroids and spanning trees, the MV gap is exactly 1. This means the multi-agent problem is essentially no harder to approximate than the single-agent one.

Main Results

  • Monotone Maximization: The authors achieve a $(1 - 1/e) \cdot \alpha$ approximation, where $\alpha$ is the best possible for the single-agent case.
  • Non-monotone Maximization: They achieve a $0.385 \cdot \alpha$ approximation.
  • Minimization Hardness: They prove that monotone MVSO minimization cannot be approximated better than $o(n/\log n)$ in general, but provide a curvature-dependent approximation that scales with $1/(1-c)$.
  • Capacitated Models: They extend these results to "Capacitated MVSO," allowing for individual constraints on each agent (e.g., Agent 1 can only take 5 items, while Agent 2 can take 10).

Limitations & Future Directions

The primary limitation is the Value Oracle Model. The bounds provided are information-theoretic; in practice, evaluating the multilinear relaxation can be computationally expensive for very large ground sets.

The authors suggest that future work could explore more specific "structured" multivariate functions that appear in machine learning, such as those used in diverse data summarization or fair allocation, to see if the general bounds can be further improved for those specific niches. Additionally, implementing these "accelerated greedy" variants on large-scale distributed systems remains an engineering challenge.

Summary updated

BibTeX
@inproceedings{santiago2019multivariate,
  author = {Richard Santiago and F. Bruce Shepherd},
  title = {{Multivariate Submodular Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
}
Figure