Pith. sign in

REVIEW 3 major objections 5 minor 26 references

Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Gradient descent's multiclass generalization is governed by the norm in which the loss template is smooth, with p=∞ giving near-binary rates and p=2 paying linear k.

desk verdict Real contribution on exponential-tail multiclass GD, but the polynomial-tail corollary is outside the paper's own framework and needs reworking. read the letter →

arxiv 2505.22359 v1 pith:TDQ2DZIP submitted 2025-05-28 cs.LG

Matan Schliserman , Tomer Koren This is my paper
classification cs.LG MSC 68Q3268T05
keywords multiclassclassificationgradientdescentgeneralizationboundsseparabledatalosstemplateRademachercomplexitylow-noiseregimeimplicitbias
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies unregularized gradient descent on linearly separable multiclass problems and tries to establish finite-time population risk bounds that depend on the geometry of the loss template—the function that expresses a multiclass loss through differences of class scores—rather than only on the loss's tail decay. The main upper bound shows that for a template that is β-smooth with respect to the ℓ_p norm (p ≥ 2) and decays at rate ρ, the risk after T gradient steps on n samples is at most a polylogarithmic factor times β $k^{{2/p}}$ $ρ^{{-1}}$(ε/k)^2 / ($γ^{2}$ min{T,n}). For exponentially decaying losses this yields logarithmic dependence on the number of classes k when p=∞ (the cross-entropy case) and linear dependence when p=2, and a matching lower bound shows the linear dependence is not an artifact of the analysis. The results matter because they identify a property of the loss that a practitioner can choose—smoothness geometry—as a driver of generalization in the many-class regime.

What carries the argument

The central object is the loss template, the function ℓ̃ : $ℝ^{{k−1}}$ → ℝ such that ℓ(y, z) = ℓ̃(M_y z), where M_y records the differences between the score of class y and every other class score. Around this object the argument runs on three pieces: a worst-case Rademacher complexity bound for the class of loss-composed vector-valued predictors, which under the low-noise assumption scales as √(β F $k^{{1/p}}$) (R+1)/√n and is proved by transferring smoothness from the template to an ℓ_p covering of the predictor class; a smoothness lemma showing that the empirical risk is β $k^{{2/p}}$-smooth in the Frobenius norm, which sets the gradient descent step size η = 1/(6β $k^{{2/p}}$); and a low-risk reference point built from the margin assumption, whose norm is $ρ^{{-1}}$(ε/k)/γ. The lower bound uses a hard instance built from k parallel binary problems, whose template is a sum of univariate β-smooth decreasing functions, so it lies inside $C^{{β,2}}$_ρ and forces the linear-in-k risk.

What would settle it

Run gradient descent on a separable k-class problem with a sum-of-univariate exponential loss, whose template is β-smooth in ℓ2, and measure population risk at fixed margin, iterations, and sample size as k grows; Theorem 3 predicts an Ω(k/($γ^{2}$ min{T,n})) lower bound, so observing risk that grows sublinearly in k, for example O(log k), would refute the claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that in separable multiclass classification, finite-time generalization of gradient descent is characterized by the smoothness geometry of the loss template. Formally, for any loss in the class $C^{{β,p}}$_ρ (nonnegative convex template, β-smooth w.r.t. ℓ_p, decaying to zero, and pointwise bounded by a tail function ρ), Theorem 1 gives R(A_T) = O~(β $k^{{2/p}}$ $ρ^{{-1}}$(ε/k)^2 / ($γ^{2}$ min{T,n})), with the p=∞ case dropping the $k^{{2/p}}$ factor. For exponential tails this means the cross-entropy loss, whose template is ℓ∞-smooth, has risk O~(1/($γ^{2}$ min{T,n})) up to logarithmic factors, while there exists a loss with an ℓ2-smooth template whose risk must grow linearly with k; Theorem 3 constructs a hard distribution inside the class showing that Ω(k) is unavoidable for p=2. The separation is driven by two mechanisms: a Rademacher complexity bound for low-noise vector-valued predictors that scales as $k^{{1/p}}$, and a smoothness lemma showing that the loss as a function of the weight matrix is β $k^{{2/p}}$-smooth, so the allowable step size improves as p grows.

Load-bearing premise

Everything rests on the requirement that the loss has a template that is nonnegative, convex, β-smooth with respect to some ℓ_p norm with a constant β that does not grow with k, and that is pointwise bounded by a decaying tail function; a loss whose template is not smooth in any such norm, such as a multiclass hinge loss, is outside the analysis, and for it the stated logarithmic-versus-linear separation is not claimed.

Editorial extensions

If this is right

  • For exponentially decaying losses, gradient descent with a template smooth in ℓ∞, including cross-entropy, attains population risk O~(1/(γ^2 min{T,n})), matching the binary classification rate up to logarithmic factors.
  • For any decay rate, the risk bound degrades by a factor k^{2/p}; larger p, meaning a flatter template geometry, allows larger gradient descent step sizes and better generalization.
  • In the Euclidean p=2 case, the linear dependence on the number of classes is unavoidable: no analysis can remove it for the class C^{β,2}_ρ.
  • The bounds hold for unregularized gradient descent with a constant step size and extend to any gradient method that produces low-norm iterates with low optimization error.
  • The template's decay rate enters through ρ^{-1}(ε/k)^2, so slower-decaying tails pay more in both optimization error and sample complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: choosing a multiclass loss with an ℓ∞-smooth template, such as a softmax-type loss, over an ℓ2-smooth one could reduce the required number of samples or iterations by a factor of k when the number of classes is large.
  • Editorial extension: the Rademacher complexity bound is stated for bounded-norm predictor classes in the low-noise regime, so it likely yields fast rates for other optimization oracles besides gradient descent whenever the low-norm and low-optimization-error conditions hold.
  • Editorial extension: the sharp p=2 lower bound suggests that multiclass losses built as sums of independent univariate losses inherit a linear penalty in k; escaping that penalty may require templates that couple the score differences across coordinates.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the finite-time generalization of unregularized gradient descent in separable multiclass linear classification, for losses whose Wang--Scott template is nonnegative, convex, and β-smooth with respect to an ℓ_p norm and is pointwise bounded by a sum of a tail function ρ. The main upper bound, Theorem 1, gives population risk of order O~(β k^{2/p} ρ^{-1}(ε/k)^2 / (γ^2 min{T,n})) under a suitable step size, which for exponentially decaying losses becomes O~(k^{2/p}/(γ^2 min{T,n})) up to log factors. Theorem 3 provides a matching lower bound for p=2 showing that the linear dependence on k is unavoidable. The analysis combines a new Rademacher complexity bound for low-noise vector-valued predictors with template smoothness, a geometry-dependent descent lemma, and a hard-instance construction for the lower bound. Applications to cross-entropy (p=∞, logarithmic in k) and to an exponential-tail ℓ_2-smooth loss (linear in k) are given, together with a claimed polynomial-tail corollary.

Significance. If the main results are correct, they constitute a substantial step in the finite-time analysis of unregularized GD for multiclass classification: the paper identifies the norm geometry of the loss template, rather than the loss itself, as the quantity governing the k-dependence, and it proves that the logarithmic-versus-linear separation between ℓ∞ and ℓ2 smooth templates is real. The Rademacher complexity lemma extends prior vector-valued complexity bounds to general ℓ_p smooth templates and is a useful technical contribution. The lower-bound construction via sums of binary hard instances is explicit and convincing. However, the polynomial-tail application in Section 5.2 is not supported by the stated Definition 3, so the advertised scope 'any decay rate of the loss' is currently overclaimed and needs repair.

major comments (3)
  1. [§5.2, Corollary 7 and Definition 3] The polynomial-tail application is not valid under the paper's own definitions. Definition 3 requires a tail function ρ to be defined on [0,∞), nonnegative, 1-Lipschitz, β-smooth convex, strictly decreasing to 0, with ρ(0)≥1 and |ρ'(0)|≥1/2. The function ρ(x)=x^{-α} used in Section 5.2 is undefined at 0, has unbounded derivative near 0, and is not 1-Lipschitz or β-smooth with any finite β on [0,∞). Therefore the class C^{β,p}_ρ is not defined for this ρ, Theorem 1 cannot be invoked, and Corollary 7 does not follow from the stated results. The statement of Corollary 7 also says 'ρ(x)=e^{-x}', contradicting the polynomial-tail heading, and the displayed bound is garbled. This is a load-bearing gap in the claimed generality and in the polynomial example; it should be fixed by introducing an admissible regularized tail such as (1+x)^{-α} with a restricted α range and re-deriving the rates.
  2. [Appendix A, proof of Lemma 1] The proof of the Rademacher complexity bound applies Lemma 9(2), whose hypothesis is γ>2ℜ̂_{nk}(H_B), but the integral in the displayed chain is taken over γ ≥ √(24βF) k^{1/p} ℜ̂_{nk}(H_B). Unless √(24βF) k^{1/p} ≥ 2, the integration range includes values where the fat-shattering bound used for the covering number is not justified. Since Theorem 1 and Theorem 2 both rely on Lemma 1, this needs to be clarified or repaired; if a different version of the fat-shattering bound is intended, it should be stated and proved.
  3. [§4 and Appendix B, lower-bound construction] The lower-bound construction is stated for 'any tail function ρ', and the wrapper functions φ in Lemmas 18 and 20 are built from ρ and its derivative at 0. This is legitimate for admissible tail functions, but it means the lower bound inherits all restrictions of Definition 3. In particular, no lower bound is currently available for the polynomial ρ(x)=x^{-α} used in Section 5.2. The manuscript should either restrict its polynomial claims consistently or extend the definition of admissible tails.
minor comments (5)
  1. [§5.2] The section heading promises 'polynomially-tailed losses', but the statement of Corollary 7 says 'ρ(x)=e^{-x}'; this is almost certainly a typo and should be corrected, and the displayed rate should be typeset so that the powers of k, T, and n can be read unambiguously.
  2. [Appendix A, Lemma 7] Lemma 7 states a bound for a univariate function f but writes 'f(x,y)' in the conclusion; this should be f(x) and the proof should be aligned with the statement.
  3. [§3.1, proof of Lemma 1] The proof refers to the functions φ_j as 'defined in Theorem 1'; they are defined in Section 3.1, not in Theorem 1. The cross-reference should be corrected.
  4. [Abstract and Section 1] There are several grammatical slips ('previous work mostly deal', 'our results indicates') that should be cleaned up in a revision.
  5. [§C, Lemma 21] The convexity proof of the softmax template uses Hölder's inequality but the displayed line has a missing logarithm on the second factor; this is a presentation issue, not a mathematical one, but it should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation chain is self-contained, with a non-circular correctness gap in the polynomial-tail application.

full rationale

The paper's core derivation is self-contained. Theorem 1 is proved from ingredients developed in the paper: Lemma 1 (Rademacher complexity of the loss class, proved in Appendix A), Lemma 2 (Lipschitz smoothness of the loss induced by template smoothness, proved), Lemma 3 (optimization error of GD, proved), Lemma 12 (existence of a low-loss model with norm scaled by rho^{-1}(eps/k)/gamma, proved using only the separability assumption and the tail bound in Definition 4c), and Lemma 14 (iterate norm bound, proved). No step is defined in terms of the claimed conclusion. The lower bound (Theorem 3) constructs explicit distributions and loss functions and verifies membership in C^{beta,2}_rho via Lemmas 6, 18 and 20; it does not assume the lower bound. Self-citations to Schliserman and Koren [2024b] are used for motivation and as a 'similar construction', but the probabilistic claims (Lemmas 15-17) are proved in the paper, so the cited binary result is not load-bearing. No uniqueness theorem is imported from the authors' prior work, and no fitted parameter is later renamed as a prediction; the step size is set from the known class parameters beta,k,p. One non-circular correctness concern: Corollary 7 applies Theorem 1 to a polynomial tail rho(x)=x^{-alpha}, but such rho violates Definition 3 (it is not 1-Lipschitz, not beta-smooth on [0,infty), and is not finite at 0), so the polynomial-tail application is not justified by the stated results. This is a gap in the claimed generality, not a circularity, and does not affect the exponential-tail separation in Corollaries 4-6.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's theorems rest on the stated separability assumption, the definition of the ρ-tailed template class, and standard tools from Rademacher complexity and convex optimization. No parameters are fitted to data, and no new entities are postulated.

assumptions (4)
  • domain assumption Assumption 1 (Separability): there exists A* with ||A*||_F ≤ 1 such that (A*_y - A*_j)^T x ≥ γ for all j≠y with probability 1.
    This defines the separable margin setting; the risk bounds scale as 1/γ^2. It is a standard assumption in the implicit-bias literature.
  • domain assumption Definition 4 (ρ-tailed class): template is nonnegative, convex, β-smooth w.r.t ℓ_p, decays to zero, and satisfies \tilde{ℓ}(z) ≤ Σ ρ(z_j).
    This is the key geometric assumption on the loss; the results apply only to losses in this class.
  • standard math Lemma 9 and Bousquet's concentration inequality used without proof (covering number bounds and fixed-point sub-root function arguments).
    These are cited from Srebro et al. (2010), Rakhlin et al. (2015), Lei et al. (2019), and Bousquet (2002); they are standard tools in local Rademacher complexity analysis.
  • domain assumption Tail function normalization: ρ(0) ≥ 1 and |ρ'(0)| ≥ 1/2 (Definition 3).
    These conditions ensure the lower-bound construction of the hard-instance loss has the needed constants; any smooth decaying loss can be rescaled to satisfy them, so they are without essential loss of generality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification." pith.science (2026). https://pith.science/paper/TDQ2DZIP

@misc{pith2026250522359,
  author       = {Pith},
  title        = {Pith review of: Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TDQ2DZIP}},
  note         = {Machine review of arXiv:2505.22359}
}
abstract

We study the generalization performance of unregularized gradient methods for separable linear classification. While previous work mostly deal with the binary case, we focus on the multiclass setting with $k$ classes and establish novel population risk bounds for Gradient Descent for loss functions that decay to zero. In this setting, we show risk bounds that reveal that convergence rates are crucially influenced by the geometry of the loss template, as formalized by Wang and Scott (2024), rather than of the loss function itself. Particularly, we establish risk upper bounds that holds for any decay rate of the loss whose template is smooth with respect to the $p$-norm. In the case of exponentially decaying losses, our results indicates a contrast between the $p=\infty$ case, where the risk exhibits a logarithmic dependence on $k$, and $p=2$ where the risk scales linearly with $k$. To establish this separation formally, we also prove a lower bound in the latter scenario, demonstrating that the polynomial dependence on $k$ is unavoidable. Central to our analysis is a novel bound on the Rademacher complexity of low-noise vector-valued linear predictors with a loss template smooth w.r.t.~general $p$-norms.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

26 extracted references · 21 canonical work pages

  1. [1]

    P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3 0 (Nov): 0 463--482, 2002

    2002

  2. [2]

    Bousquet

    O. Bousquet. Concentration inequalities and empirical processes theory applied to the analysis of learning algorithms. Journal of Machine Learning Research, 01 2002

    work page 2002

  3. [3]

    Ji and M

    Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300, 2018

    arXiv 2018

  4. [4]

    Ji and M

    Z. Ji and M. Telgarsky. A refined primal-dual analysis of the implicit bias. Journal of Environmental Sciences (China) English Ed, 2019

    work page 2019

  5. [5]

    Z. Ji, M. Dud \'i k, R. E. Schapire, and M. Telgarsky. Gradient descent follows the regularization path for general losses. In J. Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2109--2136. PMLR, 09--12 Jul 2020

    work page 2020

  6. [6]

    Lei, \"U

    Y. Lei, \"U . Dogan, D.-X. Zhou, and M. Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65 0 (5): 0 2995--3021, 2019

    work page 2019

  7. [7]

    J. Li, Y. Liu, R. Yin, H. Zhang, L. Ding, and W. Wang. Multi-class learning: From theory to algorithm. Advances in Neural Information Processing Systems, 31, 2018

    work page 2018

  8. [8]

    Lyu and J

    K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv:1906.05890, 2019

    arXiv 1906

Show all 26 references
  1. [9]

    K. Lyu, Z. Li, R. Wang, and S. Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34: 0 12978--12991, 2021

    2021

  2. [10]

    Magen and O

    R. Magen and O. Shamir. Initialization-dependent sample complexity of linear predictors and neural networks. Advances in Neural Information Processing Systems, 36, 2024

    2024

  3. [11]

    A. Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 3--17. Springer, 2016

    2016

  4. [12]

    M. S. Nacson, J. Lee, S. Gunasekar, P. H. P. Savarese, N. Srebro, and D. Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420--3428. PMLR, 2019 a

    2019

  5. [13]

    M. S. Nacson, N. Srebro, and D. Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051--3059. PMLR, 2019 b

    2019

  6. [14]

    Rakhlin, K

    A. Rakhlin, K. Sridharan, and A. Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161 0 (1): 0 111--153, 2015. doi:10.1007/s00440-013-0545-5. URL https://doi.org/10.1007/s00440-013-0545-5

    2015 doi

  7. [15]

    H. Ravi, C. Scott, D. Soudry, and Y. Wang. The implicit bias of gradient descent on separable multiclass data. arXiv preprint arXiv:2411.01350, 2024

    2024 arXiv

  8. [16]

    Reeve and A

    H. Reeve and A. Kaban. Optimistic bounds for multi-output learning. In International Conference on Machine Learning, pages 8030--8040. PMLR, 2020

    2020

  9. [17]

    Schliserman and T

    M. Schliserman and T. Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In P.-L. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3380--3394....

    2022

  10. [18]

    Schliserman and T

    M. Schliserman and T. Koren. Complexity of vector-valued prediction: From linear models to stochastic convex optimization. arXiv preprint arXiv:2412.04274, 2024 a

    2024 arXiv

  11. [19]

    Schliserman and T

    M. Schliserman and T. Koren. Tight risk bounds for gradient descent on separable data. Advances in Neural Information Processing Systems, 36, 2024 b

    2024

  12. [20]

    O. Shamir. Gradient methods never overfit on separable data. The Journal of Machine Learning Research, 22 0 (1): 0 3847--3866, 2021

    2021

  13. [21]

    Soudry, E

    D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 0 (1): 0 2822--2878, 2018

    2018

  14. [22]

    Srebro, K

    N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010

    2010

  15. [23]

    Telgarsky

    M. Telgarsky. Stochastic linear optimization never overfits with quadratically-bounded losses on general data. In P.-L. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 5453--...

    2022

  16. [24]

    Wang and C

    Y. Wang and C. Scott. Unified binary and multiclass margin-based classification. Journal of Machine Learning Research, 25 0 (143): 0 1--51, 2024

    2024

  17. [25]

    L. Wu, A. Ledent, Y. Lei, and M. Kloft. Fine-grained generalization analysis of vector-valued learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, no. 12, pages 10338--10346, 2021

    2021

  18. [26]

    Zhang and M.-L

    Y. Zhang and M.-L. Zhang. Generalization analysis for multi-label learning. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings...

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.