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

Thank you for the feedback! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period.

”The discussion regarding the stepsize in Line 233, which claims that $\eta = 1/\beta$ is "optimal," appears to overlook recent findings.”

This is a very good point. Our understanding is that the work [Wu, Bartlett, Telgarsky, Yu, 2024, Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency] discusses the specific case of the logistic loss, while our work give upper and lower bounds for general functions with $\beta$-smooth template. As a result, the word “optimal” in line 233 referred to the optimal choice for general smooth functions, which is $\Theta(1/\beta)$. For the latter, it is a folklore fact that even for $\eta=2/\beta$, GD might not converge to a local minimum. We will clarify this point in the final version of the paper.

”it would be highly beneficial to provide an example of a specific loss function that satisfies the conditions for the worse polynomial dependence on k”

Corollary 6 is a direct application of Lemmas 4 and 5. As a result, as detailed in the proof of Theorem 3 the function that achieves the lower bound is $\ell(Wx)=\frac12 \ell_4(Wx)+\frac12 \ell_5(Wx)$, where $\ell_4$ and $\ell_5$ are the functions from Lemmas 4 and 5 with $\rho(x)=e^{-x}$. We will add a proof for Corollary 6 in the next revision of the paper.

Thanks for the review! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period.

“From a theoretical standpoint, I view these results as a strong advancement; however, I would say there is a limitation from an applied standpoint, given that the setting assumes the model is a separable linear classifier.”-

We appreciate the fact that you see the results as a strong theoretical advancement. The scope of this work is indeed linear models parameterized by a matrix, where even in this relatively restricted setting, the analysis and results are already non-trivial. Focus on the linear case is rather common in theoretical work in learning theory, as it allows for derivation of rigorous conclusions and concrete insights. We conjecture that some of the results in the work, e.g., the separation between $\ell_\infty$ and $\ell_2$ can be generalized to more complex regimes, and that this is a good idea for future work. We will discuss future work in more detail in the final version of the paper.

Could you comment on these insights generalizing beyond multi-class learning such as structured prediction or other tasks?

This is a good point. Our current analysis focuses on multiclass prediction with a linear output layer, but we believe that some insights may extend to more general settings such as structured prediction tasks where the number of output classes is naturally very large. For example, the fact that the use of a loss function with $\ell_\infty$-smooth template like the cross entropy decreases the dependence on the number of classes, compared to other loss functions, is of particular importance in such scenarios. Extending the analysis to structured or sequence prediction is an interesting direction. We will add a brief discussion in the final version to clarify this.

Could you comment on settings where assuming the data is linear separable is valid?

The assumption of separability is originally motivated by overparameterized models, where the number of parameters far exceeds the number of training samples. This has led to a rich line of theoretical work analyzing the performance of various algorithms under such conditions. Our work continues this line by studying linear classification under the separability assumption as a theoretical model. We hope that some of the insights derived here will be transferable to more complex and practical settings.

Thank you for your reply, I find it helpful as a reviewer. As a final score, I will stay at 5~accept. I think this work is clearly presented and provides a thoughtful provoking new result meriting it as an accepted paper.

Thank you for the feedback! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period. We will of course fix all of the typos you mentioned.

“The assumptions are restricted. The work would be even more compelling if it goes beyond linear case.”

The scope of this work is linear models parameterized by a matrix, where even in this relatively restricted setting, the analysis and results are already non-trivial. Focus on the linear case is rather common in theoretical work in learning theory, as it allows for derivation of rigorous conclusions and concrete insights.

Investigating whether the geometry of the loss function influences the performance of gradient descent beyond the linear case is indeed an interesting direction for future work. We conjecture that the separation between different norms occurs also in more complex regimes, and therefore, some of the insights developed here may extend to broader settings. We will address these limitations and outline possible directions for future research in the next revision of the paper.

“It is mentioned that another line of work on implicit bias of GD focus on the asymptotic convergence of classifier to max-margin one. Is it possible to derive non-asymptotic estimate on that convergence?”

This is a very good question. It is indeed possible to derive non-asymptotic bounds for the convergence to max-margin. However, usually the generalization bounds that one can achieve will be much worse than the optimal rates. For example, for the binary case, the output of GD satisfies $|\|w_t/||w_t|| -w^*\||=O(1/\log{T})$. This implies a very weak upper bound of $\exp(1/\gamma)$ on the number of steps till the predictor achieves a positive margin $\gamma$ on all the data points. We refer the reviewer to a more extensive discussion in page 2 of [20].

Thanks for the review! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period.

“I would be interested to see if the results indicate any implications on choice of loss functions for extreme classification (large number of classes)? In the generative modeling setup, for example, do we gain some understanding when the vocabulary sizes are very large?”

This is an excellent point. While our classification result is formally established in the linear setting, we conjecture that some of its insights may extend to more general scenarios. For example, it may help explain the common use of cross-entropy loss in more complex models. According to our bounds, a loss function with $\ell_\infty$-smooth template like the cross-entropy reduces the dependence on the number of classes, which, in extreme classification tasks with a very large number of classes, can result in significant differences in performance compared to other loss functions.

” I would like to see a broader discussion of the applications of the results, given the assumptions of separable data, linear classification etc,... For example, do the results help understand properties of classifier-head fine-tuning in deep learning? A meaningful discussion along this direction would help contextualize the paper for a broader audience.”

Following up on our previous response, classifier-head fine-tuning (assuming you meant the last layer of a pretrained model) is yet another example of a multi-class prediction problem with a large number of classes, where our results give support for using a loss function $\ell_\infty$-smooth template such as the cross-entropy loss. We agree that a discussion about these implications and applications is warranted, and we will include one in the final version.

“the paper ends rather abruptly at an example application of one of the results... the results could benefit from a practical discussion. Further, what do the authors consider as problems that future work may address?”

We agree - we will discuss the implications and limitations of our work, as well as directions for future work, in the final version of the paper. Future research may study whether the geometry of the loss function influences the behavior of gradient descent beyond the linear setting. We conjecture that the separation between different norms occurs in more complex regimes.

“Typo in corollary 7:”

Thanks for pointing that out. We will fix this in the next revision.

“What does the result of Ravi et al, referenced here say and how is the current result not at odds with the same? Does the setup differ?”

Reference [15] analyzes a setup similar yet different from ours. They show that for any loss function that decays exponentially to zero, gradient descent exhibits similar asymptotic behavior and converges in direction to the max-margin solution. In contrast, our work deals with more general loss functions and reaches a different conclusion, demonstrating that finite-time generalization depends on the geometry of the loss function. Despite this difference, our results are not in conflict with [15], as we deal with a different setup and we further focus on different aspects: finite-time behavior versus asymptotic behavior.

” it would be helpful to see any insights on what conditions are needed for the data to be linearly separable in a multi-class sense… Is there an understanding for the separability criterion considered by the authors? Does data dimension play a role in the risk bounds?”

The separability criterion considered in this work is One-Vs-All linear separability. This assumption is originally motivated by overparameterized neural networks, where the number of parameters significantly exceeds the number of examples $n$. In our setting, the model has $kd$ parameters, where $d$ is the dimension of the data. Since our bounds depend on $k$ but not on $d$, this suggests that when $d$ is large, the data may become separable without negatively impacting the performance of gradient descent.

”The limitations from the perspective of assumptions is mentioned in the checklist. It might be a good idea to note this in the main body of the paper.”

Thanks for this advice. We will add a discussion about the limitations of our work in the next revision of the paper.