Noise misleads rotation invariant algorithms on sparse targets

arXiv:2403.02697v1 Announce Type: cross
Abstract: 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 …

abstract algorithms arxiv class cs.lg examples gradient layer linear neural net noise rotation stat.ml targets type