mlsanityData to 7 Oct 2026

Hard labels sampled from sparse targets mislead rotation invariant algorithms

arXiv 2603.20967 ↗First posted 21 Mar 2026stat.ML cs.LG math.STcited by 0

Not on the map. Why?

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 52 of its 73 references that are in the map. First posted on arXiv 21 Mar 2026.

Builds on

52 of 73 references.

References · 52

  1. 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 748
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2017Implicit Regularization in Matrix Factorizationcited by 318
  5. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  6. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  7. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  8. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  9. 2020Benign overfitting in ridge regressioncited by 152
  10. 2018Convergence of Gradient Descent on Separable Datacited by 108
  11. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  12. 2021Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsitycited by 83
38 more
  1. 2018Risk and parameter convergence of logistic regressioncited by 81
  2. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  3. 2019Implicit Regularization for Optimal Sparse Recoverycited by 78
  4. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 70
  5. 2018A Continuous-Time View of Early Stopping for Least Squarescited by 67
  6. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  7. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 54
  8. 2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
  9. 2022The Implicit Bias of Benign Overfittingcited by 38
  10. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  11. 2023(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stabilitycited by 35
  12. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  13. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
  14. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  15. 2018Finite-sample analysis of M-estimators using self-concordancecited by 30
  16. 2019Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordancecited by 28
  17. 2019The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regimecited by 27
  18. 2020Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularizationcited by 27
  19. 2025Learning quadratic neural networks in high dimensions: SGD dynamics and scaling lawscited by 23
  20. 2020The Statistical Complexity of Early-Stopped Mirror Descentcited by 19
  21. 2021Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measurescited by 19
  22. 2021Exponentiated Gradient Reweighting for Robust Training Under Label Noise and Beyondcited by 16
  23. 2021Smooth Bilevel Programming for Sparse Regularizationcited by 14
  24. 2023A Unified Approach to Controlling Implicit Regularization via Mirror Descentcited by 13
  25. 2023On the sample complexity of parameter estimation in logistic regression with normal designcited by 13
  26. 2024Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networkscited by 13
  27. 2024Grokking at the Edge of Linear Separabilitycited by 11
  28. 2020Logistic Regression Regret: What's the Catch?cited by 9
  29. 2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
  30. 2025Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networkscited by 9
  31. 2022Step-size Adaptation Using Exponentiated Gradient Updatescited by 7
  32. 2023Risk Bounds of Accelerated SGD for Overparameterized Linear Regressioncited by 7
  33. 2024Implicit Bias of Mirror Flow on Separable Datacited by 7
  34. 2025Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularizationcited by 7
  35. 2023Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regressioncited by 4
  36. 2024Finite-sample performance of the maximum likelihood estimator in logistic regressioncited by 4
  37. 2025Learning sparse generalized linear models with binary outcomes via iterative hard thresholdingcited by 4
  38. 2025Learning Dynamics of Deep Linear Networks Beyond the Edge of Stabilitycited by 4

50 most cited of 52 All 52 (JSON)

Built on by

Not cited yet.