Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

Vitaly Feldman, Jan Vondrák

Abstract

This paper establishes the first tight bounds on the low-degree spectral concentration of submodular and XOS (fractionally subadditive) functions. By analyzing second-order Fourier influences and introducing novel threshold norms, the authors demonstrate that these functions have their Fourier weight concentrated on degrees significantly lower than previously known: $O(1/\epsilon^{4/5})$ for submodular functions and $O(1/\epsilon)$ for XOS functions. These structural results lead to nearly optimal PAC learning algorithms, closing significant gaps in computational learning theory and revealing a nuanced hierarchy of complexity among discrete function classes.

Introduction

In discrete mathematics and machine learning, submodular functions serve as the discrete counterparts to convex functions, defined by the property of diminishing returns. XOS functions, a broader class representing the maximum of several linear functions, are equally critical in combinatorial optimization, algorithmic game theory, and economics. A fundamental question in computational learning theory is determining the sample complexity required to learn these functions.

A powerful approach to this problem involves Fourier analysis over the Boolean hypercube. If a function's spectral weight is concentrated on low-degree Fourier coefficients, it can be efficiently approximated by a low-degree polynomial. Prior to this work, the best-known upper bound for the degree required to approximate submodular and XOS functions within an error of $\epsilon$ was $O(1/\epsilon^2)$. This paper closes the gap between these upper bounds and known lower bounds, providing a precise characterization of their spectral concentration.

Methodology

The authors move beyond traditional first-order analysis—which examines how individual variable changes affect function value—to investigate second-degree influences. Their approach incorporates several key innovations:

  1. Second-Order Fourier Analysis: The study focuses on the quantity $\sum_{i,j} \|\partial_{ij} f\|_2^2$, where $\partial_{ij} f$ represents the second-degree discrete derivative. This metric captures how the marginal contribution of one element fluctuates in the presence of another, providing a more granular view of function structure.
  2. Threshold Norms: To manage submodular functions, the authors introduce "threshold norms" to isolate variables with high individual influence. They prove that only a limited number of variables can possess large influence; for the remainder, second-order influences are sufficiently small to bound the Fourier tail.
  3. The Boosting Lemma: Utilizing a boosting lemma from prior literature, the authors demonstrate that if a submodular function exhibited high influence across many variables, it would eventually exceed its bounded range $[0, 1]$. This contradiction effectively limits the number of "influential" variables.
  4. Lower Bound Constructions: To ensure the tightness of their bounds, the authors construct specific adversarial functions, such as the "hockey-stick" function for submodular classes and noise-sensitive Talagrand’s random DNF formulas for XOS classes.

Key Results and Complexity Hierarchy

The primary contribution of this research is the establishment of tight $(\ell_2, \epsilon)$-approximate degree bounds. The results reveal a clear hierarchy of complexity across different function classes, as summarized in the table below.

Summary of established $(\ell_2, \epsilon)$-approximate degree bounds across function classes.

By breaking the $1/\epsilon^2$ barrier, the authors show that the interactions between variables in submodular and XOS functions are more constrained than previously assumed. Specifically, XOS functions are shown to satisfy a "degree-two version of self-boundedness," which is the structural key to the $O(1/\epsilon)$ bound. These theoretical results translate directly into nearly optimal PAC learning algorithms. For instance, submodular functions can now be learned in $2^{\tilde{O}(1/\epsilon^{4/5})} \cdot n^2$ time, a significant improvement over the previous $2^{\tilde{O}(1/\epsilon^2)}$ complexity.

Conclusion and Future Work

This work provides a definitive answer to the spectral concentration of submodular and XOS functions under the uniform distribution. However, several avenues for future research remain. A small $O(\log(1/\epsilon))$ gap persists between the upper and lower bounds for submodular functions, and closing this polylogarithmic factor is a natural next step. Furthermore, while these results are robust for the uniform distribution, extending these tight bounds to general product distributions or achieving distribution-independent learning remains a major challenge in the field. Finally, while the techniques apply to agnostic learning, the optimality of these bounds in noisier settings warrants further exploration.

Summary updated

Abstract

Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning. Motivated by learnability of these classes of functions from random examples, we consider the question of how well such functions can be approximated by low-degree polynomials in ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> norm over the uniform distribution. This question is equivalent to understanding the concentration of Fourier weight on low-degree coefficients, a central concept in Fourier analysis. Denoting the smallest degree sufficient to approximate f in ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> norm within ∈ by deg <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∈</sub> (ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> )(f), we show that : For any submodular function f : {0, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> → [0, 1], deg <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∈</sub> (ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> )(f) = O(log(1/∈)/∈ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4/5</sup> ) and there is a submodular function that requires degree Ω(1/∈ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4/5</sup> ). : For any XOS function f : {0, 1} → [0, 1], deg <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∈</sub> (ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> ) (f) = O(1/∈) and there exists an XOS function that requires degree Ω(1/∈). This improves on previous approaches that all showed an upper bound of O(1/∈ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) for submodular [CKKL12], [FKV13], [FV13] and XOS [FV13] functions. The best previous lower bound was Ω(1/∈ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2/3</sup> ) for monotone submodular functions [FKV13]. Our techniques reveal new structural properties of submodular and XOS functions and the upper bounds lead to nearly optimal PAC learning algorithms for these classes of functions.
BibTeX
@inproceedings{feldman2015tight,
  author = {Vitaly Feldman and Jan Vondrák},
  title = {{Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions}},
  booktitle = {FOCS},
  year = {2015},
  url = {https://openreview.net/forum?id=pgVQjLPupcY},
}
Figure