# Noise misleads rotation invariant algorithms on sparse targets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 5 Mar 2024.

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

- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Low-rank extended Kalman filtering for online learning of neural networks from streaming data](https://mlsanity.com/paper/2305.19535/) (2023)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Depth Without the Magic: Inductive Bias of Natural Gradient Descent](https://mlsanity.com/paper/2111.11542/) (2021)

## Abstract (arXiv)

It is well known that the class of rotation invariant algorithms are suboptimal even for learning sparse linear problems when the number of examples is below the "dimension" of the problem. This class includes any gradient descent trained neural net with a fully-connected input layer (initialized with a rotationally symmetric distribution). The simplest sparse problem is learning a single feature out of d features. In that case the classification error or regression loss grows with 1-k/n where k is the number of examples seen. These lower bounds become vacuous when the number of examples k reaches the dimension d. We show that when noise is added to this sparse linear problem, rotation invariant algorithms are still suboptimal after seeing d or more examples. We prove this via a lower bound for the Bayes optimal algorithm on a rotationally symmetrized problem. We then prove much lower upper bounds on the same problem for simple non-rotation invariant algorithms. Finally we analyze the gradient flow trajectories of many standard optimization algorithms in some simple cases and show how they veer toward or away from the sparse targets. We believe that our trajectory categorization will be useful in designing algorithms that can exploit sparse targets and our method for proving lower bounds will be crucial for analyzing other families of algorithms that admit different classes of invariances.