Ever since we’re tiny little optimization children, we’re told some nursery rhyme to the tune of “convex problems are easy, nonconvex problems are hard”. The reason is because convex problems can be solved in polynomial time (that is, under the assumption that the number of variables and constraints are also polynomial). On the other hand, exact solvers for nonconvex problems are tough, because they have to tryout almost all solutions, or do a local search in which they pray that whatever local optima they get in is just good enough.
But what if I told you that
- even convex problems can have multiple solutions, and
- the consequences will carry over to important nonconvex problems as well?
In fact, what if I told you that one of the most important problems in this category is simple logistic regression?
You might be really confused, because this is not an LLM, not even a CNN. So how can it be so complex and important? Well, the second part is easier to answer: most deep learning models use either logistic regression or multiclass logistic regression in their last layer (the decision layer). Therefore, the issues we bring up for a simple convex function here are the same issues that appear in these larger, more substantive models.
The implicit bias problem
Implicit bias arises when a problem has multiple solutions. Logistic regression, over separable data, has unattained, asymptotic solutions. Specifically, consider a dataset $\mathcal D = \{(x_i,y_i)\}_{i=1}^n$ with binary labels $y_i\in \{+1,-1\}$, which is separable, i.e. there exists at least one $\theta$ where
$$
\mathrm{sep}(\mathcal D) := \{\theta : \mathbf{sign}(\langle \theta, x_i\rangle) = \mathbf{sign}(y_i), \quad \forall i = 1,…,n \}\tag{Separable}
$$
Equivalently,
$$
\mathrm{sep}(\mathcal D) := \{\theta :\langle \theta, y_ix_i\rangle >0, \quad \forall i = 1,…,n.\} \tag{Separable}
$$
Clearly, of $\mathcal D$ is separable then the set $\mathrm{sep}(\mathcal D)$ must contain at least one ray; in general, it is a convex cone with nontrivial interior. That is to say, the solutions to logistic regression are not attained. Specifically, if some $\theta$ separates data, then for $f(\theta) = \frac{1}{n}\sum_{i=1}^n \log(1+\exp(-y_ix_i^T\theta))$,
$$
c_1 > c_2 \quad \Rightarrow \quad f(c_1\theta) < f(c_2\theta)
$$
So, the “solutions” to minimizing $f$ is the limit of $f(c_t \theta)$ for some increasing sequence $c_t$.
Figures 1 and 2 below show an example of the multiple solutions of logistic regression, separating two different datasets. It also shows the underlying problem of implicit bias:
- a separable dataset will likely have multiple separating hyperplanes (not just in magnitude, but in direction), and
- different solvers converge to different ones.
Now there have been many papers written about this [1-5]. In short, they show that SGD and Adam do not converge to the same implicit bias, and then gave some nonasymptotpic rates on the margin of which the method goes to. In this post I’m just going to present intuition, and do enough math to get a feel of this stuff, but not actually present any nonasymptotic rates.
Margin maximization w.r.t. p norm
“Wait,” the first year ML student pauses and asks. “I thought logistic regression solutions were margin maximizers. So it’s not like every separating hyperplane is a valid solution, only ones which maximize distance to all points! Doesn’t that enforce uniqueness?”
Yes, it does, to some extent. But… with respect to which distance?
Recall that for a set of parameters $\theta$, the minimum margin distance between the discriminator described by $y=\mathbf{sign}(\langle x,\theta\rangle)$ is exactly $\frac{\langle y_i x_i, \theta\rangle}{\|\theta\|}$. To jog your memeory, let’s stare at the figure below from my graduate ML class.
Here, the Euclidean distance between $x$ and $u$, the closest point on the discriminator to $x$, is the solution to the following minimization problem
$$
\underset{u: u^T\theta = 0}{\mathrm{minimize}} \, \|x-u\|_2
$$
We can solve this using Lagrangian duality but honestly I like to just use high school geometry instead. Here, we can see from the picture that $d(x,D) = \|x\|_2\,|\cos(\alpha)|$. Moreover, $\cos(\alpha) = \frac{\langle x_i,\theta\rangle }{\|x_i\|_2\|\theta\|_2}$.
Therefore, the distance from any datapoint $x_i$ to the discriminator is
\[
d(x,D)=\frac{|\langle x_i, \theta\rangle|}{\|\theta\|_2}
\]
Finally, we denote the normalized margin maximizer as
$$
\theta_p = \underset{\|\theta\|_p\leq 1}{\mathrm{argmax}}\, \min_{i\in [n]} \, \frac{\langle y_i x_i, \theta\rangle}{\|\theta\|_p}\tag{$*$}
$$
Note that I have removed the absolute values and inserted in $y_ix_i$, since $\langle y_i x_i, \theta\rangle \geq 0$ is the “good” scenario (datapoint classified correctly) and $\langle y_i x_i, \theta\rangle \leq 0$ is the “bad” scenario (datapoint misclassified), which we are trying to avoid.
Now, the implicit bias problem
The intuition we are trying to understand in this post is… drumroll…
Gradient descent minimizes ($*$) for $p = 2$ (standard Euclidean norm), but Adam minimizes ($*$) for $p = \infty$ (the worst coordinate distance)!
To try to understand this, let’s actually limit our attention to normalized gradient descent, and its steepest descent variants. Later, we will show that GD follows the pattern of normalized GD w.r.t. the 2 norm, and Adam follows the pattern of steepest descent, w.r.t. the 1,$\infty$ norm pair. Specifically, consider
\[\theta_{t+1} = \theta_t \,- \,\eta_t d_t, \qquad d_t = \arg\min_{\|d\|_p\leq 1}\langle d, \nabla f(\theta_t)\rangle \tag{Steepest Descent}\]
Then if $p = 2$, $d_t = \frac{\nabla f(\theta_t)}{\|\nabla f(\theta_t)\|_2}$ the normalized gradient (NGD), and if $p = 1$, this is normalized coordinate descent (CoordGD), where $d_t = \mathbf{sign}(g_k)e_k$ where $g_k$ is the $k$th coordinate of the negative gradient, and $k = \arg\max_{i} |g_i|$. And, if $p = \infty$, then $d_t = \mathbf{sign}(-\nabla f(\theta_t))$ where the sign is computed elementwise (SignGD).
Specifically, we know from optimality conditions that $d_t$ is exactly the vector that satisfies (for $\frac{1}{p} + \frac{1}{q} = 1$)
$$
\cos_p(d, -\nabla f(\theta_t)) := -\frac{\langle d, \nabla f(\theta_t)\rangle}{\|d\|_p\,\|\nabla f(\theta_t)\|_q}=1.
$$
Then, the final pieces of the puzzles fall from the simple observation (which can be quantified, but that’s a lot of work): that the gradient exactly approaches the support vectors. To see this, let’s do a staring exercise. Stare at the equation below.
$$
\nabla f(\theta) = -\frac{1}{n}\sum_{i=1}^n \sigma(-y_ix_i^T\theta) y_ix_i, \qquad \sigma(s) = \frac{e^s}{1+e^s}
$$
When a point $(x_i,y_i)$ is well-classified, e.g. with correct sign and large margin, then $w_i:=\sigma(-y_ix_i^T\theta)\approx 0$. Then, the datapoints with the largest $w_i$ are indeed the support vectors themselves, the points closest to the descriminator boundary and controlling the direction of the final solution $\theta$. Moreover, if the dataset is separable by $\theta$, $w_i > 0 $. So, as $t\to\infty$, $\nabla f(\theta_t) \to -\frac{1}{|S|}\sum_{i\in S} \sigma(-y_ix_i^T\theta) y_ix_i$ where $S$ is the set of support vectors themselves! Specifically, define the weighted mixture of support vectors as
$$
\bar z := \frac{1}{|S|}\sum_{i\in S} \sigma(-y_ix_i^T\theta_\infty) y_ix_i \quad \text{Then,} \quad \nabla f(\theta_t) \to -\bar z.
$$
After that happens, we can see that $d_t$ changes less w.r.t. $t$, and so the iterates $\frac{\theta_t}{\|\theta_t\|_p}$ start looking a lot like $d_t$ itself. That is to say,
$$
1 \overset{\text{opt. cond.}}{=} \cos_p(d_t, -\nabla f(\theta_t)) \approx \cos_p(\theta_t, -\bar z)
$$
Finally, noting that the specific $\theta$ which satisfies $\cos_p(\theta, -\bar z) = 1$ is exactly, as defined earlier, $\theta_p$, the $p$-norm margin maximizer.
Let’s do some case studies
Steepest descent: NGD, CoordGD , and SignGD
Let’s take a look at the special cases for $p = 2,1$, and $\infty$. In all three cases, the data is separable, and the objective value decreases log-linearly.
Additionally, when we compare $\cos_p(d_t,\nabla f(\theta_t))$ for different values of $p$, we indeed find the highest correlation for $p = 2$ with NGD, for $p = \infty$ with SignGD, and for $p = 1$ with CoordGD.
While the relationship with $\cos_p(\theta_t,\nabla f(\theta_t))$ is less clean, we see that once $\theta_t$ has been moving consistently in the direction $d_t$ for long enough, this accumulated alignment dominates, so the same $p$-hierarchy emerges here as well. (But, note that as $\|\nabla f(\theta_t)\|$ gets so small we’re in the realm of machine precision, this whole analysis become super noisy and not that reliable.)
Shifting our attention, we can also try to see the filtering effect of the support vectors themselves. Below, I have sorted at each iteration the data by $w_i = \sigma(-y_ix_i^T\theta_t)$, and then plotted $\frac{\|g_i\|_2}{\|\nabla f(\theta_t)\|_2}$ where $g_i$ is the projection of $\nabla f(\theta_t)$ to the dataset $\{x_1,…,x_i\}$, ordered by $w_i$. Indeed, we can see that the gradient falls into the span of the support vectors, and becomes well-modeled by some conic combination of them.
Finally, we show the cossine similarity between each $\theta_t$ and $\theta_p$ the known $p$-norm margin maximizer. Actually, the hierarchy of alignment is pretty narrow, but you can clearly see the NGD one aligning best with $w_2$, the SignGD one aligning best with $w_\infty$, and the CoordGD aligning best with $w_1$.
What about GD (unnormalized)?
GD actually behaves pretty similarly to NGD. The convergence of the loss and gradient is much slower (and the norm of the gradient does not grow linearly like steepest descent can). And, the projection of the gradient into the span of the support vector is more gradual with iteration.
Finally, what about Adam and RMSProp?
For these two methods, if there is no biasing and no $\epsilon$, then if $\beta = \beta_1=\beta_2 = 0$, the two methods reduce to SignGD. I think in general the biasing doesn’t really change anything, and the $\epsilon$ certainly has a smoothing effect but it is not that surprising, so I focused on the $\beta$ values, swept below. (For Adam, $\beta_1=\beta_2=\beta$.) I guess what I would say is… yes there is a correspondence with SignGD, but when $\nabla f(\theta_t)$ becomes very close to 0, and if the support vector contributions are not very stable, then it is not always clear the other terms are acting “in line”. Still, the SignGD way of thinking is valuable intuition to these coordinate-wise normalized methods.
But why should I care? An unanswered question…
An interesting followup question is, of course: which margin is better? We know that in general, the margin maximization property is what gives gradient-based methods their nice generalization properties — the bigger the margin, the less sensitive the model is to small perturbations in the data. But… small with respect to what distance? Why would stability w.r.t. the Euclidean distance necessarily be the right distance metric? Why not a different $p$-norm, or even not a norm for that matter? It’s not clear, and I really don’t have any answers… but I think if we really want to draw the line between implicit bias, margin maximization, and generalization, we should start thinking in that direction!
References
[1] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. 2018.
[2] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. 2019.
[3] Chen Fan, Mark Schmidt, and Christos Thrampoulidis. Implicit bias of spectral descent and Muon on multiclass separable data. 2025.
[4] Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. 2018.
[5] Chenyang Zhang, Difan Zou, and Yuan Cao. The implicit bias of Adam on separable data. 2024.
[6] Haoyuan Sun, Kwangjun Ahn, Christos Thrampoulidis, and Navid Azizan. Mirror descent maximizes generalized margin and can be implemented efficiently. 2022.
[7] Gal Vardi. On the implicit bias in deep-learning algorithms. 2023.