# Hard labels sampled from sparse targets mislead rotation invariant algorithms

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

## Key facts

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

## Builds on (most cited first, 30 of 52)

- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Gradient descent aligns the layers of deep linear networks](https://mlsanity.com/paper/1810.02032/) (2018)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity](https://mlsanity.com/paper/2106.15933/) (2021)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy](https://mlsanity.com/paper/2007.06738/) (2020)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [The Implicit Bias of Depth: How Incremental Learning Drives Generalization](https://mlsanity.com/paper/1909.12051/) (2019)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime](https://mlsanity.com/paper/1911.01544/) (2019)
- [Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization](https://mlsanity.com/paper/2011.09148/) (2020)

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

- [Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates](https://mlsanity.com/paper/2608.17573/) (2026)

## Abstract (arXiv)

One of the most common machine learning setups is logistic regression. In many classification models, including neural networks, the final prediction is obtained by applying a logistic link function to a linear score. In binary logistic regression, the feedback can be either soft labels, corresponding to the true conditional probability of the data (as in distillation), or sampled hard labels (taking values ± 1). We point out a fundamental problem that arises even in a particularly favorable setting, where the goal is to learn a noise-free soft target of the form σ(xtopwstar). In the over-constrained case (i.e. the number of samples n exceeds the input dimension d) with examples (xi,σ(xitopwstar)), it is sufficient to recover wstar and hence achieve the Bayes risk. However, we prove that when the examples are labeled by hard labels yi sampled from the same conditional distribution σ(xitopwstar) and wstar is s-sparse, then rotation-invariant algorithms are provably suboptimal: they incur an excess risk Omega!left(fracd-1nright), while there are simple non-rotation invariant algorithms with excess risk O(fracslog dn). The simplest rotation invariant algorithm is gradient descent on the logistic loss (with early stopping). A simple non-rotation-invariant algorithm for sparse targets that achieves the above upper bounds uses gradient descent on the weights ui,vi, where now the linear weight wi is reparameterized as uivi.