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:
- 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.
- 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.
- 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.
- 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.
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