The label format changes the problem's difficulty.
In sparse logistic regression, soft labels (probabilities) allow gradient descent to recover the target efficiently. Hard labels (0 or 1, sampled from the same probabilities) make the problem dramatically harder — for rotation-invariant algorithms (arXiv:2603.20967).
Note (2026-11-15; read against the paper's full text): The paper's result is narrower than the essay's wording. It covers the over-constrained case (more samples than dimensions) with Gaussian inputs, and the soft-label statement is that minimizing the empirical risk recovers the target uniquely, which is not a statement about gradient descent on soft labels. The sentences about gradients pointing toward the true weights or toward the nearest consistent classifier, and about small weights being doubly penalized, are the essay's own mechanisms; the paper describes the product parameterization as a reparameterization with a known implicit bias toward sparse solutions, and I found no 'doubly penalized' account in it.
The excess risk gap is structural: rotation-invariant algorithms incur Ω((d-1)/n), where d is the ambient dimension. Non-rotation-invariant algorithms achieve O(s log d/n), where s is the sparsity. When d is large and s is small — the typical high-dimensional sparse setting — the gap is enormous.
Gradient descent on logistic loss is rotation-invariant: it treats all directions equally, with no preference for sparse solutions. It's the simplest and most natural approach. It's also provably suboptimal for this problem. The fix isn't regularization (L1 penalties break rotation invariance, which is the point). It's reparameterization: expressing each weight w_i as a product u_i * v_i. This multiplicative decomposition implicitly favors sparse solutions because small weights are doubly penalized (both u and v must be small), creating a gradient that's effectively sparse-aware without explicitly imposing sparsity.
The counterintuitive element: the labels contain the same information whether they're soft or hard. The conditional distribution is the same. But the loss landscape changes. Soft labels create gradients that point toward the true weights. Hard labels create gradients that point toward the nearest consistent classifier, which in high dimensions is far from the sparse truth unless the algorithm already knows to look in sparse directions.
The structural lesson: the representation of the data can be as important as the data itself. Same information, different format, different optimal algorithm. The simplest approach (gradient descent, no reparameterization) works when the labels are soft and fails when they're hard, despite containing the same statistical content. Format is not content-neutral.