Multilinear extension of k-submodular functions

Baoxiang Wang, Huanjian Zhou

Abstract

A $k$-submodular function is a pairwise monotone function that given $k$ disjoint subsets outputs a value that is submodular in every orthant. In this paper, we provide a new framework for $k$-submodular maximization problems, by relaxing the optimization to the continuous space with the multilinear extension of $k$-submodular functions and rounding the fractional solution to recover the discrete solution. The multilinear extension introduces new techniques to analyze and optimize $k$-submodular functions. When the variables are unconstrained, we propose simple algorithms that achieve almost $\frac{1}{2}$-approximation, which is asymptotically optimal. For finite $k$, the factors could be improved to almost as good as any combinatorial algorithm based on Iwata, Tanigawa, and Yoshida's meta-framework ($\frac{k}{2k-1}$-approximation for the monotone case and $\frac{k^2+1}{2k^2+1}$-approximation for the non-monotone case). For monotone functions, almost $\frac{1}{2}$-approximation are obtained under total size and knapsack constraints.

Introduction

Submodular maximization is a cornerstone of machine learning, used for applications ranging from sensor placement to dataset summarization. However, many real-world problems require more than a binary "yes/no" choice. This leads to the concept of $k$-submodularity: a generalization where each element can be assigned to one of $k$ different classes or left out entirely.

Consider a social media influencer campaign with $k$ different topics. The goal is not just to select influencers, but to assign each to the specific topic where they are most effective. While near-perfect algorithms exist for the $k=1$ case, the $k > 1$ scenario is significantly harder to optimize, particularly under real-world constraints like budgets (knapsack constraints) or structural requirements (matroid constraints). Previous approaches relied primarily on "greedy" combinatorial methods that often converged to sub-optimal solutions.

Methodology: A Continuous Optimization Framework

This research departs from traditional discrete greedy algorithms, adopting a continuous optimization approach through a three-stage "Relax-then-Round" pipeline:

  1. Multilinear Extension: The authors define a method to "smooth" the discrete $k$-submodular function into a continuous one. This allows optimization within a continuous space (the "corner of the cube" domain $\Delta_k^n$) using calculus-based tools.
  2. Frank-Wolfe Framework: Two unified Frank-Wolfe-type algorithms are proposed—one for monotone and one for non-monotone functions. These algorithms iteratively approach an optimal fractional solution by following the gradient of the multilinear extension.
  3. Rounding (KSUBROUND): A novel rounding scheme converts fractional solutions back into valid discrete assignments (integral solutions) without losing significant value.

A key technical contribution is the identification of new properties of this extension, such as approximate linearity and pairwise monotonicity, which are essential for proving that continuous optimization steps yield high-quality discrete results.

Key Insights and Results

The power of continuity is a central theme; the "multilinear extension" approach, which revolutionized standard submodular maximization, is shown to be the key to unlocking optimal bounds for $k$-submodularity. By treating assignment probabilities as a scaled simplex, the authors successfully navigate the "orthant" problem inherent in $k$-submodular functions.

The paper provides a significant jump in theoretical performance over previous state-of-the-art combinatorial methods. Notably, for monotone functions with knapsack constraints, the approximation ratio improves from $1/3$ to $1/2$, which is proven to be asymptotically optimal.

Comparison of approximation ratios for various constraint types and function types.

For non-monotone functions, the authors utilize "pairwise monotonicity" to reduce complexity, achieving a $1/3$ approximation ratio. For several common constraints, these $1/2$ ratios are asymptotically optimal, meaning no polynomial-time algorithm can significantly exceed them unless $P=NP$.

Limitations and Future Directions

While powerful, the continuous approach has a higher query complexity than simple greedy algorithms. Although it remains polynomial-time, the high exponents may limit its speed on massive datasets. Additionally, the current rounding schemes are randomized; future work could explore derandomization for applications requiring deterministic results. Finally, the property of pairwise monotonicity warrants further exploration to potentially unlock even better bounds for complex non-monotone optimization problems.

Summary updated

Abstract

A $k$-submodular function is a pairwise monotone function that given $k$ disjoint subsets outputs a value that is submodular in every orthant. In this paper, we provide a new framework for $k$-submodular maximization problems, by relaxing the optimization to the continuous space with the multilinear extension of $k$-submodular functions and rounding the fractional solution to recover the discrete solution. The multilinear extension introduces new techniques to analyze and optimize $k$-submodular functions. When the variables are unconstrained, we propose simple algorithms that achieve almost $\frac{1}{2}$-approximation, which is asymptotically optimal. For finite $k$, the factors could be improved to almost as good as any combinatorial algorithm based on Iwata, Tanigawa, and Yoshida's meta-framework ($\frac{k}{2k-1}$-approximation for the monotone case and $\frac{k^2+1}{2k^2+1}$-approximation for the non-monotone case). For monotone functions, almost $\frac{1}{2}$-approximation are obtained under total size and knapsack constraints.
BibTeX
@misc{wang2021multilinear,
  author = {Baoxiang Wang and Huanjian Zhou},
  title = {{Multilinear extension of k-submodular functions}},
  year = {2021},
  eprint = {2107.07103},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.07103},
}
Figure