acceptodds
Under review as a conference paper at ICLR 2027

The Implicit Bias of Steepest Descent on Multiclass Nonseparable Data

Abstract

We study steepest descent for linear multiclass classification with softmax cross-entropy on nonseparable data. Unlike binary nonseparable logistic regression, where the data split into separable and nonseparable examples, a multiclass example induces multiple pairwise margin constraints that may differ in separability. We therefore introduce a norm-dependent parameter-space decomposition: one component remains constant throughout the descent, an escaping component that maximizes the margin in the separable subspace, and a bounded component that converges to a finite optimum in the nonseparable subspace. We derive convergence rates of the risk to its infimum and of the normalized margin of the escaping component to the norm-dependent optimum. We also characterize *directional convergence*. When the norm is strictly convex, the max-margin direction is unique and the escaping component converges to it directionally. Without strict convexity, we find that this can *fail*: we construct a linear classification problem and an optimization norm for which the normalized escaping component has multiple distinct max-margin accumulation points, even with separable training data.

Primary area:
optimization
Keywords:
implicit bias, steepest descent, multiclass nonseparable data, directional convergence, tie-breaking rule

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_qTXVOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the implicit bias of steepest descent towards max-margin solutions. The paper first decomposes the parameter space into three components: An (update-irrelevant) invariant component, an escaping component, and a component associated with the real optimization variables. The paper then quotients out the symmetries and optimizes out the escape directions, yielding a coercive reduced objective that is strongly convex on compact convex subsets and admits a unique minimizer (Theorem 3.1). With these in place, the paper establishes risk convergence (Theorem 4.3) using an error bound for the risk objective (Lemma 4.2), and then derives results for margin convergence (Theorems 5.2 and 5.3). As an aside, the paper also presents interesting counterexamples showing that margin convergence doesn't necessarily guarantee directional convergence.

Critical strengths
  1. The paper introduces an insightful decomposition of the parameter space.
  2. I believe that the theoretical developments in this paper make a solid contribution to the field.
Critical weaknesses

None.

Questions for authors

I believe the analysis of directional convergence in this paper is closely connected to the theory of cosmic spaces in variational analysis; see "Rockafellar, R. T., & Wets, R. J. (1998). Variational analysis. Berlin, Heidelberg: Springer Berlin Heidelberg." In particular, I believe the notion of directional convergence considered here is equivalent to the cosmic convergence in variational analysis (given the norm divergence established Theorem 5.2); see Definition 3.1 of the monograph. Moreover, in this terminology, the accumulation set considered here can essentially be identified with the horizon outer limit of the unnormalized iterates; see Section 4.F of the same monograph. I think highlighting this connection would deepen the discussion and suggest new directions for future research. For example, even when directional convergence fails, it would be interesting to determine whether one can still establish rates at which the iterates approach their cosmic accumulation set, measured using the cosmic metric in Exercise 4.48 of the same monograph.

3 comments

Thank you for your insightful suggestions. We answered your question below.

Q. Connection between cosmic spaces in variational analysis.

Thank you for specifically pointing us to cosmic spaces in variational analysis. When the iterate norms diverge, directional convergence corresponds to cosmic convergence to a direction point, and the normalized accumulation set corresponds to the unit-norm directions in the horizon outer limit. We added this connection in Section 5, highlighted in blue. This perspective may provide useful tools for studying implicit bias.

Establishing rates of approach to the cosmic accumulation set in the metric of Exercise 4.48 of the monograph requires further analysis beyond the limited rebuttal period. We plan to investigate these rates in the next revision.

Thanks for your response, and all the best with your submission :)

Thank you for your response. We appreciate your continued positive assessment of our work.

Reviewer_RjQjOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the implicit bias of steepest descent for linear multiclass classification with softmax cross-entropy on nonseparable data. The authors introduce a norm-dependent decomposition of the parameter space into invariant, escaping, and bounded components. Based on this decomposition, they establish convergence rates for the empirical risk, the bounded component, and the normalized margin. They further show that strict convexity of the optimization norm guarantees directional convergence, while directional convergence can fail for non-strictly convex norms, even on separable data.

Critical strengths
  1. The paper focuses on a distinction between binary and multiclass classification: different class comparisons within the same example may exhibit different separability properties. The proposed pairwise decomposition addresses this issue and provides a foundation for analyzing steepest descent under general norms.

  2. The paper distinguishes convergence of the normalized margin from convergence of the parameter direction. The directional convergence guarantee under strict convexity is motivated, and the counterexamples showing that directional convergence can fail. These results provide useful insights.

Critical weaknesses
  1. Although the directional nonconvergence counterexample is interesting, it relies on a specially constructed optimization norm. It remains unclear whether similar behavior occurs under general norms, such as entrywise ℓ1\ell_1, ℓ∞\ell_\infty, or matrix norms. A detailed discussion of this distinction would help clarify.

  2. The margin convergence result requires a summability condition on the step sizes, excluding constant learning rates. The authors provide a counterexample showing that constant-step convergence can fail. Nevertheless, it remains unclear whether stronger guarantees are possible for standard optimization geometries. This limits the direct applicability of this paper's results to commonly used steepest descent procedures.

Questions for authors
  1. Can the authors discuss whether directional nonconvergence can occur under commonly used norms, particularly ℓ1\ell_1, ℓ∞\ell_\infty norms? Is the highly specialized norm construction essential to Theorem 6.3?

  2. Are there additional structural conditions on the optimization norm, weaker than strict convexity, that would guarantee directional convergence when the max-margin solution is not unique?

  3. Can the authors clarify whether the stronger step-size condition for margin convergence can be relaxed for commonly used norms, even though constant-step convergence fails in the general setting?

3 comments

Thank you for your interesting questions. We answered below and updated our manuscript; refer to our revisions written in olive.

W1, Q1. Limitation of norms in counterexamples.

We added two examples in Section H.3 showing directional nonconvergence under the entrywise ℓ1\ell_1 and ℓ∞\ell_\infty norms with deterministic tie-breaking rules. These examples exploit oscillation in the lineality space, similar to the idea of Proposition 6.2.

Whether directional nonconvergence can occur under every tie-breaking rule for these norms, as in Theorem 6.3, remains open. For ℓ1\ell_1, steepest directions depend on the indices and signs of gradient coordinates with the largest magnitude. For ℓ∞\ell_\infty, gradient coordinates of nonzero values fix the signs of corresponding coordinates of the steepest directions, while those of zero values allow them to vary in [−1,1][-1,1]. One possible way to obtain directional nonconvergence would be to construct a dataset that repeatedly changes these indices or signs, with successive phases of updates toward distinct limiting directions dominating earlier updates. The challenge is to enforce such behavior under every tie-breaking rule.

W2, Q3. Summability assumption for margin condition.

When J⋆≠∅\mathcal J_\star\ne\varnothing, Assumption 4.1 and ηt→0\eta_t\to0 suffice for attaining max margin γ⋆\gamma_\star. In particular, the polynomial step sizes ηt=η0/(t+1)a\eta_t=\eta_0/(t+1)^a now yield margin convergence for every 0<a≤10<a\le1 and 0<η0β≤10<\eta_0\beta \le 1. We outline the proof below.

Lemma F.1 holds under Assumption 4.1. The first inequality in Lemma F.4, −Δ(i,c)(Ut)≥−log⁡δt−c12-\Delta_{(i,c)}(U_t)\ge-\log\delta_t-c_{12}, holds without Assumption 5.1 for every (i,c)∈J⋆(i,c) \in \mathcal J_\star and sufficiently large tt. The inequality implies that the total length of update Lt:=∑j=0t−1ηj∣∇R(Wj)∣∗→∞L_t := \sum_{j=0}^{t-1}\eta_j\\|\nabla R(W_j)\\|_* \to\infty from Equation (38) and δt↓0\delta_t \downarrow 0.

Lemma F.1 and β\beta-smoothness of the risk also give

−log⁡δt≥γ⋆Lt−βγ⋆2∑j<tηj2∣∇R(Wj)∣∗−c7∑j<tηjδj∣∇R(Wj)∣∗−log⁡δ0=γ⋆Lt−o(Lt)−O(1),-\log\delta_t \ge \gamma_\star L_t -\frac{\beta\gamma_\star}{2} \sum_{j<t} \eta_j^2\\|\nabla R(W_j)\\|_{\ast} - c_7 \sum_{j<t} \eta_j\delta_j\\|\nabla R(W_j)\\|_{\ast} - \log\delta_0 = \gamma_\star L_t - o(L_t) - O(1),

where c7c_7 is the constant in Lemma F.1. Hence, we see that γ⋆≥min⁡(i,c)∈J⋆−Δ(i,c)(Ut)∣Ut∣≥γ⋆Lt−o(Lt)−O(1)Lt+c13→γ⋆\gamma_\star \ge \frac{\min_{(i,c)\in\mathcal J_\star}\\{-\Delta_{(i,c)}(U_t)\\}}{\\|U_t\\|} \ge \frac{\gamma_\star L_t-o(L_t)-O(1)}{L_t+c_{13}} \to\gamma_\star, where c13c_{13} appears in Equation (38).

Assumption 5.1 is used to derive an explicit convergence rate of the margin, especially controlling the o(Lt)o(L_t) terms. We added this distinction; refer to our revision in olive (page 6 footnote and Proposition F.5).

Q2. Beyond strict convexity of norms for directional convergence.

We do not currently know a structural condition on the norm, weaker than strict convexity, that guarantees directional convergence when the max-margin solution is nonunique. One possibility is that directional convergence depends on the interaction between the dataset, optimization norm, tie-breaking rule, and initialization. On the positive side, directional convergence can occur even when the norm is not strictly convex. For example, choose the dataset as ((1,0)⊤,1),((−1,−1)⊤,2)\\{((1,0)^\top,1),((-1,-1)^\top,2)\\}, the entrywise ℓ∞\ell_\infty norm, and W0=0W_0=0. The set of max-margin solutions is computed as \mathcal U=\left\\{\begin{pmatrix}1&a\\\\-1&b\end{pmatrix}:-1\le b\le a\le1\right\\},

with γ⋆=2\gamma_\star=2. We have ∇R(W)=−12(1+e−Δ(1,2)(W))(10−10)−12(1+e−Δ(2,1)(W))(11−1−1).\nabla R(W)=-\frac{1}{2(1+e^{-\Delta_{(1,2)}(W)})}\begin{pmatrix}1&0\\\\-1&0\end{pmatrix}-\frac{1}{2(1+e^{-\Delta_{(2,1)}(W)})} \begin{pmatrix}1&1\\\\-1&-1\end{pmatrix}.

Hence, for every finite WW, the set of steepest directions is

\mathcal F_{\\|\cdot\\|_{\max}}(\nabla R(W)) = \left\\{\begin{pmatrix}-1&-1\\\\1&1\end{pmatrix}\right\\}.

In this example, the steepest direction is unique and constant; thus, directional convergence follows despite the nonuniqueness of the max-margin solution. For other datasets and norms, different initializations and tie-breaking rules could lead to different limiting directions or affect whether directional convergence occurs. Therefore, a complete characterization may need to account for initialization, together with the dataset, norm, and tie-breaking rule.

Thank you for your response. I also reviewed the comments from the other reviewers and decided to raise my rating to 3. However, I would encourage you to improve the writing to make the paper easier to read, making that readers from other domains can also get the intuition.

Thank you for your response and for taking the time to reassess our work. We will improve the presentation of our paper to make it easier to follow.

Reviewer_QzuHOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers multiclass linear models with cross-entropy loss optimized by steepest descent in a general norm. It shows that a training set defines a direct sum decomposition of parameter space into three subspaces, directions that do not affect the loss and are not in any steepest descent direction, directions where parameters can go to infinity to drive the loss down, and directions where parameters have a finite minimum of the loss. It shows how the evolution of the third component evolves and how the risk converges to its optimal value for steepest descent with certain stepsize constraints. Finally, it shows how the second component evolves (and converges in direction) and how it maximizes the margin.

Critical strengths

These are interesting results and it's a worthwhile generalization of the corresponding results for gradient descent in logistic regression from gradient descent to steepest descent and from binary classification to multiclass.

Critical weaknesses

This is a nice, easy-to-state problem to present to a strong AI model (generalize these results in these two directions). The answers are interesting, and should be known. But there seems to be very little conceptual contribution, it seems likely that the problem-solving part of the contribution comes from an AI, and so we should expect the presentation to be a significant part of the contribution. This paper falls short there.

The paper describes the decomposition informally, and the formal results hint at the interpretations, but the intuition is stated formally (in Thm 3.1) only for the third part of the direct sum decomposition. It would be more digestible to actually state the properties of the other two parts of the decomposition as a theorem in Section 3.

There are several strange omissions and discontinuities that make the paper hard to follow:

p1: What does "Each training example contributes one loss term for each incorrect class." mean?

p2: "under the standard softmax cross-entropy loss" - the paper does not define this anywhere, nor give a reference.

p2: "For a linear subspace" -> "For a linear subspace of matrices"

p2: The notation Delta_{ic}(W) is terrible. i is an index into the data set, and c is a class label.

p2: "The risk is convex and globally smooth for some beta > 0" - what is beta? I can infer the definition from beta's appearance in (24) on p20. But I can't find a definition anywhere.

p3: Where does the terminology 'norming face' come from? It sounds like the authors are inventing it, but refer to it in the same way that they refer to a standard term like 'dual norm'.

p4: "For the Frobenius norm, Z = S^orthog and N = S (Corollary B.2)." is a parenthetical example, but it's followed by "We then split Z..." which suggests the focus is now on the Frobenius norm, but it's not.

p4: Another place where a parenthetical comment appears and make what follows confusing: "Thus, I* = \emptyset is equivalent to multiclass separability..." is a side comment, not the setting for the next sentence.

p5, Ass 4.1: eta_t\le 1/beta. Is this the same unspecified beta from p2?

p5: The sentence "The proof controls both R_0..." appears after a definition. Is it referring to the proof of the lemma that we're about to see? It's mysterious.

p6: The definition of the margin appears many times (in the max margin set definition, in equation 10, etc). Why not introduce some notation for it?

p17, section C: It would help to include a picture. Why is this 2-dimensional example described as an example in R^4?

The decomposition of W_t into the three pieces isn't stated explicitly in the main paper, but this notation (V_t, U_t) is used throughout. This seems careless.

Questions for authors

n/a

3 comments

Thank you for your considerate review and detailed guidelines. We reflected your guidelines in the manuscript; refer to our revisions written in purple.

W. Revisions for better presentation.

The paper describes the decomposition informally, and the formal results hint at the interpretations, but the intuition is stated formally (in Thm 3.1) only for the third part of the direct sum decomposition. It would be more digestible to actually state the properties of the other two parts of the decomposition as a theorem in Section 3.

We added a new theorem about the properties of each subspace at the beginning of Section 3.1. Specifically, 1) N\mathcal N contains directions along which the risk is constant and which are not steepest directions at nonzero gradients, 2) M\mathcal M contains directions that do not increase the risk, and 3) every nonzero element of E\mathcal E produces score gaps of both signs. The context that informally describes the decomposition is now a proof sketch of the new theorem.

p1: What does "Each training example contributes one loss term for each incorrect class." mean?

The sentence explains Equation (1) without using any terminologies to be introduced. The risk RR contains one logarithm per example, which has one exponential summand for each incorrect class. We modified the sentence and referred to Equation (1) so that the meaning becomes exact and clear.

p2: "under the standard softmax cross-entropy loss" - the paper does not define this anywhere, nor give a reference.

We added a reference to Equation (1).

p2: "For a linear subspace" -> "For a linear subspace of matrices"

We revised as you suggested.

p2: The notation Delta_{ic}(W) is terrible. i is an index into the data set, and c is a class label.

We revised the subscript to (i,c)(i,c) to properly distinguish two indices.

p2: "The risk is convex and globally smooth for some beta > 0" - what is beta? I can infer the definition from beta's appearance in (24) on p20. But I can't find a definition anywhere.

We added the definition of β\beta-smooth functions in Section 2.

p3: Where does the terminology 'norming face' come from? It sounds like the authors are inventing it, but refer to it in the same way that they refer to a standard term like 'dual norm'.

The term comes from the fact that F∣⋅∣(G)\mathcal F_{\\|\cdot\\|}(G) is an exposed "face" of the unit ball with respect to the "norm". We agree that the term is not standard, and thus we changed "norming face" to "the set of steepest directions (at GG)".

p4: "For the Frobenius norm, Z = S^orthog and N = S (Corollary B.2)." is a parenthetical example, but it's followed by "We then split Z..." which suggests the focus is now on the Frobenius norm, but it's not.

p4: Another place where a parenthetical comment appears and make what follows confusing: "Thus, I* = \emptyset is equivalent to multiclass separability..." is a side comment, not the setting for the next sentence.

We moved these parenthetical comments to footnotes to preserve the flow of the main text.

p5, Ass 4.1: eta_t\le 1/beta. Is this the same unspecified beta from p2?

Yes. We explicitly stated this fact in Assumption 4.1.

p5: The sentence "The proof controls both R_0..." appears after a definition. Is it referring to the proof of the lemma that we're about to see? It's mysterious.

Yes, it refers to Lemma 4.2 that we are about to see. We mentioned which result the sentence is referring to.

p6: The definition of the margin appears many times (in the max margin set definition, in equation 10, etc). Why not introduce some notation for it?

We introduced the margin notation γ(U)\gamma(U) in Section 2 and used it in the subsequent statements.

p17, section C: It would help to include a picture. Why is this 2-dimensional example described as an example in R^4?

We added a figure to describe the example. While it is true that D=2D=2 suffices in Section C, the same example is used for Proposition 6.2 (counterexample within lineality), where the additional two-dimensional subspace is used to easily choose the rotating directions in the lineality subspace.

The decomposition of W_t into the three pieces isn't stated explicitly in the main paper, but this notation (V_t, U_t) is used throughout. This seems careless.

We stated the decomposition of WtW_t and defined its components immediately after Equation (4).

We appreciate your careful review and detailed suggestions, which helped us substantially improve the presentation of our manuscript.

Thanks for the response.

Thank you for your response. We appreciate your continued positive assessment of our work.

Comments on the paper

1 comment

Dear Reviewers,

The rebuttal period ends in less than two days. If you have not already done so, I kindly ask you to acknowledge the authors’ responses, and indicate whether your main concerns have been adequately addressed or further clarification is needed.

Thank you.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.