# Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces

arXiv: https://arxiv.org/abs/2210.02604 · HTML: https://mlsanity.com/paper/2210.02604/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 51 references that are in the map.
- First posted on arXiv 5 Oct 2022.

## Builds on (most cited first, 21 of 21)

- [Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains](https://mlsanity.com/paper/2006.10739/) (2020)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks](https://mlsanity.com/paper/1901.06523/) (2019)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Spectral Norm Regularization for Improving the Generalizability of Deep Learning](https://mlsanity.com/paper/1705.10941/) (2017)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [A Fine-Grained Spectral Perspective on Neural Networks](https://mlsanity.com/paper/1907.10599/) (2019)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [Adaptive wavelet distillation from neural networks through interpretations](https://mlsanity.com/paper/2107.09145/) (2021)
- [Gradient methods for convex minimization: better rates under weaker conditions](https://mlsanity.com/paper/1303.4645/) (2013)
- [Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks](https://mlsanity.com/paper/1905.10264/) (2019)
- [Fast Haar Transforms for Graph Neural Networks](https://mlsanity.com/paper/1907.04786/) (2019)
- [The Spectral Bias of Polynomial Neural Networks](https://mlsanity.com/paper/2202.13473/) (2022)
- [On the Local Minima of the Empirical Risk](https://mlsanity.com/paper/1803.09357/) (2018)
- [Optimizing Star-Convex Functions](https://mlsanity.com/paper/1511.04466/) (2015)
- [SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform](https://mlsanity.com/paper/1508.06336/) (2015)

## Built on by (most cited first, 1 of 1)

- [Contrastive losses as generalized models of global epistasis](https://mlsanity.com/paper/2305.03136/) (2023)

## Abstract (arXiv)

Data-driven machine learning models are being increasingly employed in several important inference problems in biology, chemistry, and physics which require learning over combinatorial spaces. Recent empirical evidence (see, e.g., [1], [2], [3]) suggests that regularizing the spectral representation of such models improves their generalization power when labeled data is scarce. However, despite these empirical studies, the theoretical underpinning of when and how spectral regularization enables improved generalization is poorly understood. In this paper, we focus on learning pseudo-Boolean functions and demonstrate that regularizing the empirical mean squared error by the L_1 norm of the spectral transform of the learned function reshapes the loss landscape and allows for data-frugal learning, under a restricted secant condition on the learner's empirical error measured against the ground truth function. Under a weaker quadratic growth condition, we show that stationary points which also approximately interpolate the training data points achieve statistically optimal generalization performance. Complementing our theory, we empirically demonstrate that running gradient descent on the regularized loss results in a better generalization performance compared to baseline algorithms in several data-scarce real-world problems.