Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions
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 …