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).
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.