From a more practical point of view, several of the recent approaches for learning over combinatorial spaces (see, e.g.,  [1]}, [2]}, [3]}, [4]}) follow similar ideas for improving empirical generalization. Instead of directly learning the \(2^d\) -dimensional polynomial, they have converged on explicitly promoting sparsity in the spectral representation of the learned compactly-represented nonlinear function—also known as spectral regularization.
These empirical studies motivate several important theoretical questions regarding the underlying mechanism of spectral regularization in improving generalization in practice. In this paper, we focus on the question: When and how does spectral regularization improve generalization? The answer to this question is important from both theoretical and practical perspectives. Theoretically, it helps us understand how the loss landscape is reshaped as the result of spectral regularization in favor of data-frugal learning. Practically, it tells us when and how to use spectral regularization in learning real-world combinatorial functions.
