Implicit Bias Of Logistic Gradient Descent

Why Logistic Loss Can Keep Improving Without a Finite Solution

In separable classification, there is a parameter vector that assigns every training example the correct sign. But logistic loss does not ask only for correct signs: it continues to decrease as the signed predictions grow. Consequently, its infimum can be zero even when no finite parameter vector attains it. Gradient descent may therefore keep moving after the training classifications are already correct. The direction of that movement can matter as much as the predictions.

We will first show that, for any finite linearly separable dataset, stable full-batch gradient descent cannot converge to a finite parameter vector. We will then prove a precise maximum-margin direction result for an orthogonal-design setting. The distinction is important: divergence of the norm alone does not establish which direction the parameters select.

Setup and Definitions

Let the training data be $(x_i,y_i)$, $i=1,\ldots,n$, with $x_i\in\mathbb{R}^d$ and $y_i\in\{-1,+1\}$. Write $z_i=y_i x_i$ for the signed feature vector. A dataset is linearly separable if there is a vector $v\in\mathbb{R}^d$ such that $z_i^\top v>0$ for every $i$. For such a finite dataset, the vector can be rescaled so that the minimum of these finitely many positive inner products is positive.

Definition: The empirical logistic loss of a parameter vector $w$ is $$ \mathcal{L}(w)=\frac{1}{n}\sum_{i=1}^n \log\!\left(1+\exp(-z_i^\top w)\right). $$ Full-batch gradient descent with step size $\eta>0$ follows $$ w_{t+1}=w_t-\eta\nabla\mathcal{L}(w_t) =w_t+\frac{\eta}{n}\sum_{i=1}^n\frac{z_i}{1+\exp(z_i^\top w_t)}. $$ The hard-margin direction is the direction of the minimum-Euclidean-norm vector satisfying $z_i^\top w\geq 1$ for every training example, when that minimizer is unique.

The logistic loss is strictly positive at every finite $w$. On separable data, however, taking $w=cv$ for a separating vector $v$ and letting $c$ increase makes every term in the loss tend to zero. Thus the infimum is zero, but it is not attained at any finite vector. This observation suggests continued movement, but a separate argument is needed to prove what gradient descent does.

Worked Example: One Separable Observation

Take one observation with signed feature $z=2$ in one dimension. Its loss is $\mathcal{L}(w)=\log(1+\exp(-2w))$. The gradient-descent update is $$ w_{t+1}=w_t+\frac{2\eta}{1+\exp(2w_t)}. $$

For any finite $w_t$, the added quantity is strictly positive, so the iterates increase. To see their scale, set $q_t=\exp(2w_t)>0$. Then $$ q_{t+1}=q_t\exp\!\left(\frac{4\eta}{1+q_t}\right). $$ The increment $q_{t+1}-q_t$ is positive. If $q_t$ were bounded, the exponent would be bounded below by a positive constant, making the increments grow at least proportionally to $q_t$; in particular $q_t$ could not remain bounded. Hence $q_t\to\infty$, and $w_t=\tfrac12\log q_t\to\infty$. The only possible unit direction in one dimension is positive, which is also the hard-margin direction.

Norm Divergence on Any Finite Separable Dataset

The next result does not require orthogonal features. It requires a finite dataset that is strictly separable and a step size small enough for the usual smooth-gradient descent argument. Define $$ L=\frac{1}{4n}\left\|\sum_{i=1}^n z_i z_i^\top\right\|_{\mathrm{op}}, $$ where $\|\cdot\|_{\mathrm{op}}$ is the Euclidean operator norm. If all $z_i$ are zero, strict separability is impossible, so $L>0$ in the setting considered here.

Theorem: Suppose the dataset is finite and linearly separable, and $0<\eta<2/L$. For full-batch gradient descent on empirical logistic loss, $\|w_t\|_2\to\infty$.

Proof. For $r(s)=\log(1+\exp(-s))$, we have $r''(s)=\exp(s)/(1+\exp(s))^2\leq 1/4$. Therefore the Hessian of the empirical loss satisfies $$ \nabla^2\mathcal{L}(w) =\frac{1}{n}\sum_{i=1}^n r''(z_i^\top w)z_i z_i^\top \preceq \frac{1}{4n}\sum_{i=1}^n z_i z_i^\top, $$ so its operator norm is at most $L$. The descent lemma for an $L$-smooth function gives $$ \mathcal{L}(w_{t+1}) \leq \mathcal{L}(w_t) -\eta\left(1-\frac{\eta L}{2}\right)\|\nabla\mathcal{L}(w_t)\|_2^2. $$ Since the loss is nonnegative and $\eta<2/L$, summing this inequality over $t$ shows that $$ \sum_{t=0}^{\infty}\|\nabla\mathcal{L}(w_t)\|_2^2<\infty. $$ In particular, $\|\nabla\mathcal{L}(w_t)\|_2\to0$.

Let $v$ be a separating vector, so $z_i^\top v>0$ for every $i$. Direct differentiation yields $$ v^\top\nabla\mathcal{L}(w) =-\frac{1}{n}\sum_{i=1}^n \frac{z_i^\top v}{1+\exp(z_i^\top w)}<0 $$ for every finite $w$. Thus the gradient is nonzero at every finite point. If the sequence $w_t$ did not satisfy $\|w_t\|_2\to\infty$, it would have a bounded subsequence. That subsequence lies in a compact ball, on which the continuous function $\|\nabla\mathcal{L}(w)\|_2$ has a strictly positive minimum: it has no zero there. This contradicts $\|\nabla\mathcal{L}(w_t)\|_2\to0$. Hence $\|w_t\|_2\to\infty$. $\square$

This proves that the parameters escape every bounded region, not that they escape along a particular ray. To prove a direction result without assuming extra behavior of the trajectory, we now impose an explicit structure on the data and solve the resulting coordinate updates.

An Orthogonal-Design Maximum-Margin Result

Suppose the signed feature vectors are coordinate-aligned: for each coordinate $j=1,\ldots,d$, the dataset contains $m_j\geq1$ copies of $a_j e_j$, where $a_j>0$ and $e_j$ is the $j$th standard basis vector. The total sample size is $n=\sum_j m_j$. The hard-margin constraints are $a_j w_j\geq1$, one for each coordinate. The minimum-norm feasible vector is therefore $b$, where $b_j=1/a_j$.

Theorem: For this coordinate-aligned dataset, full-batch logistic gradient descent with any fixed $\eta>0$ and any finite initialization satisfies $$ \frac{w_t}{\|w_t\|_2}\longrightarrow \frac{b}{\|b\|_2}, \qquad b_j=\frac{1}{a_j}. $$ Thus the normalized parameters approach the hard-margin direction. The coordinate-wise conclusion below is proved directly; it does not require a general-data direction theorem.

Proof. The loss separates across coordinates, and the update for coordinate $j$ is $$ w_{j,t+1}=w_{j,t}+ \frac{\eta m_j a_j}{n(1+\exp(a_j w_{j,t}))}. $$ Let $q_{j,t}=\exp(a_j w_{j,t})$, which is positive for every finite initialization. Setting $c_j=\eta m_j a_j^2/n>0$, exponentiation gives $$ q_{j,t+1}=q_{j,t}\exp\!\left(\frac{c_j}{1+q_{j,t}}\right). $$ The sequence $q_{j,t}$ increases. It cannot be bounded: if it were, the increments $q_{j,t+1}-q_{j,t}$ would be bounded below by a positive constant, contradicting boundedness. Hence $q_{j,t}\to\infty$. Moreover, $$ q_{j,t+1}-q_{j,t} =q_{j,t}\left[\exp\!\left(\frac{c_j}{1+q_{j,t}}\right)-1\right] \longrightarrow c_j, $$ using $(\exp(u)-1)/u\to1$ as $u\to0$. The average of a convergent sequence has the same limit, so $q_{j,t}/t\to c_j$. Taking logarithms, $$ w_{j,t}=\frac{\log q_{j,t}}{a_j} =\frac{\log t}{a_j}+\frac{\log c_j}{a_j}+o(1). $$ There are finitely many coordinates, so in vector form $w_t=(\log t)b+O(1)$. Dividing by $\log t$ gives $w_t/\log t\to b$. Since $b\ne0$, continuity of normalization away from zero implies $w_t/\|w_t\|_2\to b/\|b\|_2$. Finally, minimizing $\|w\|_2$ subject to $a_jw_j\geq1$ requires $w_j\geq1/a_j$ for every $j$; the smallest squared norm is attained uniquely at $w_j=1/a_j$. This verifies that $b/\|b\|_2$ is the hard-margin direction. $\square$

Worked Example: Two Orthogonal Features

Take one signed feature $z_1=(2,0)$ and one $z_2=(0,1)$. Here $a_1=2$, $a_2=1$, and $m_1=m_2=1$. The hard-margin constraints are $2w_1\geq1$ and $w_2\geq1$, so the minimum-norm feasible vector is $b=(1/2,1)$. Its norm is $\sqrt{1/4+1}=\sqrt5/2$, and its unit direction is $$ \frac{b}{\|b\|_2}=\left(\frac{1}{\sqrt5},\frac{2}{\sqrt5}\right). $$ For any fixed positive step size, the update calculation gives $w_{1,t}=\tfrac12\log t+O(1)$ and $w_{2,t}=\log t+O(1)$. Thus the ratio of the coordinates tends to $1:2$, matching the displayed direction.

Worked Example: Repeated Orthogonal Observations

Suppose the signed feature $(1,0)$ occurs twice and $(0,2)$ occurs once. Then $n=3$, $a_1=1,m_1=2$, and $a_2=2,m_2=1$. The hard-margin constraints give $w_1\geq1$ and $w_2\geq1/2$. The minimum-norm vector is $b=(1,1/2)$, with unit direction $(2/\sqrt5,1/\sqrt5)$.

The coordinate update constants in the proof are $c_1=2\eta/3$ and $c_2=4\eta/3$. Thus $q_{1,t}/t\to2\eta/3$ and $q_{2,t}/t\to4\eta/3$. Taking logarithms and converting back to the parameters gives $w_{1,t}=\log t+O(1)$ and $w_{2,t}=\tfrac12\log t+O(1)$. The multiplicities alter the bounded terms through $c_1,c_2$, but not the leading coefficients or the limiting direction.

Worked Example: Checking the Maximum-Margin Optimization

For signed features $(3,0)$ and $(0,2)$, the constraints are $3w_1\geq1$ and $2w_2\geq1$. They require $w_1\geq1/3$ and $w_2\geq1/2$. Since $\|w\|_2^2=w_1^2+w_2^2$, its minimum over these constraints occurs at $b=(1/3,1/2)$. Its norm is $\sqrt{1/9+1/4}=\sqrt{13}/6$, so the unit direction is $(2/\sqrt{13},3/\sqrt{13})$. The update asymptotics give $w_{1,t}=\tfrac13\log t+O(1)$ and $w_{2,t}=\tfrac12\log t+O(1)$, yielding that same direction after normalization.

What the Result Does—and Does Not—Say

The coordinate-aligned theorem illustrates implicit bias: although the logistic objective has no finite minimizer on these data, gradient descent selects a particular limiting direction, namely the minimum-norm vector satisfying unit signed margins, after normalization. The optimization procedure and loss together determine this direction; it is not obtained by minimizing the logistic loss at a finite parameter value.

The general norm-divergence theorem applies to all finite strictly separable datasets under its step-size condition. The direction proof given here has a narrower hypothesis. For non-orthogonal data, coordinates interact in the gradient update, and the coordinate-wise recurrence used above no longer applies. In particular, divergence of $\|w_t\|_2$ by itself is not evidence that $w_t/\|w_t\|_2$ converges, or that any limit is maximum-margin.

Common Pitfall

Incorrect reasoning: “The loss tends to zero and the norm tends to infinity, so the normalized parameters must be maximum-margin.” Neither fact identifies the direction. A sequence can have diverging norm while its direction changes or approaches a non-optimal ray.
Correction: Prove direction selection separately. Here, the orthogonal structure yields scalar recurrences, from which each coordinate's leading $\log t$ term is derived and then compared with the hard-margin solution.
Another error: Treating the logistic objective as if it attained its infimum at a finite optimizer. On separable data every finite parameter has strictly positive loss, even though the infimum is zero.

Key takeaway: For stable full-batch gradient descent, strict separability forces the parameter norm to diverge. Under the stated coordinate-aligned condition, the normalized iterates converge to the unique hard-margin direction. These are distinct claims, and the second requires its own argument.

Check Your Understanding

Use the assumptions and derivations in this tutorial to answer the following.

Why can empirical logistic loss have infimum zero on separable data without having a finite minimizer?
Which step-size condition is used in the norm-divergence proof, and where does it enter?
For coordinate-aligned signed features $a_j e_j$, why is the minimum-norm vector satisfying unit margins $b_j=1/a_j$?
In the orthogonal recurrence, what limit does $q_{j,t+1}-q_{j,t}$ approach, and how does it imply logarithmic growth of $w_{j,t}$?
Why does norm divergence alone fail to establish convergence to the hard-margin direction?