Hard labels sampled from sparse targets mislead rotation invariant algorithms

• URL: http://arxiv.org/abs/2603.20967v1
• Date: Sat, 21 Mar 2026 22:38:24 GMT
• Title: Hard labels sampled from sparse targets mislead rotation invariant algorithms
• Abstract summary: In binary logistic regression, the feedback can be either soft labels, corresponding to the true conditional probability of the data, or sampled hard labels.<n>We show that when the examples are labeled by hard labels $y_i$ sampled from the same conditional distribution $(mathbfx_itopmathbfwstar)$ and $mathbfwstar$ is $s$-sparse, then rotation-invariant algorithms are provably suboptimal.
• Score: 6.565070116874382
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\pm 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 $σ(\mathbf{x}^{\top}\mathbf{w}^{\star})$. In the over-constrained case (i.e. the number of samples $n$ exceeds the input dimension $d$) with examples $(\mathbf{x}_i,σ(\mathbf{x}_i^{\top}\mathbf{w}^{\star}))$, it is sufficient to recover $\mathbf{w}^{\star}$ and hence achieve the Bayes risk. However, we prove that when the examples are labeled by hard labels $y_i$ sampled from the same conditional distribution $σ(\mathbf{x}_i^{\top}\mathbf{w}^{\star})$ and $\mathbf{w}^{\star}$ is $s$-sparse, then rotation-invariant algorithms are provably suboptimal: they incur an excess risk $Ω\!\left(\frac{d-1}{n}\right)$, while there are simple non-rotation invariant algorithms with excess risk $O(\frac{s\log d}{n})$. 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 $u_i,v_i$, where now the linear weight $w_i$ is reparameterized as $u_iv_i$.

Related papers

• Algorithms for adaptive and heteroskedastic linear regression at the computational threshold [2.2359088001899736]
  We study finite-sample linear regression in the presence of varied and unknown label noise.<n>In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution.<n>We introduce a (computationally inefficient) adaptive estimator that achieves so long as $p$ is a mixture of $k symmetric log-concave.
  arXiv  Detail & Related papers  (2026-08-19T00:17:22Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  We derive approximation bounds for learning single neuron models using thresholded descent. We also study the linear regression problem, where $sigma(mathbfx) = mathbfx$.
  arXiv  Detail & Related papers  (2024-09-05T16:59:56Z)
• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  This paper aims to recover the intrinsic model parameters given the leverage scores gradient. We specifically scrutinize the inversion of the leverage score gradient, denoted as $g(x)$.
  arXiv  Detail & Related papers  (2024-08-21T01:39:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted $n$-sized label-feature sample of at most $epsilon n$ arbitrary outliers. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on $(Sigma,Xi) nor the operator norm of $Xi$.
  arXiv  Detail & Related papers  (2022-09-06T23:37:31Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
  We show that a preconditioned Lasso can solve a large class of sparse linear regression problems nearly optimally. For the first time, we construct random-design instances which are provably hard for an optimally preconditioned Lasso.
  arXiv  Detail & Related papers  (2021-06-17T02:12:01Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.