The Implicit Bias of Steepest Descent on Multiclass Nonseparable Data

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.