Convex vs Non-Convex Optimization: What Changes for Gradient Descent

Last updated 8 October 2026

In convex optimization, every local minimum is a global minimum, so gradient descent with a small enough step size cannot settle in a worse valley. In non-convex optimization, the surface can contain several minima, saddle points and plateaus, so where you start can change where training ends. Linear and logistic regression are classic examples of convex problems, whereas training a neural network is a non-convex problem.

Formally, a convex optimization problem minimizes a convex function over a convex set, meaning a set where the straight line between any two of its points stays inside it. Most of this lesson is about unconstrained training losses, where the set is the whole parameter space and only the function matters.

Convex vs non-convex: what is the difference?

The practical difference lies in what it means when training converges. On a convex loss, a point where the gradient is zero is a global minimum, so convergence means the problem is solved. On a non-convex loss, a zero-gradient point could be a minimum, a maximum or a saddle, and even a genuine minimum may not be the best one available.

Two rows of this table are easy to misread, so each gets its own section below: convex does not mean there is only one answer (it means there is one minimum value), and non-convex does not mean gradient descent gets stuck (it means the guarantee is weaker). It also helps to remember that convexity is a property of the loss viewed as a function of the parameters, which is why the model, the loss and the optimizer are best treated as three separate choices.

What does gradient descent do on each kind of surface?

Before getting to the formal definition, it helps to watch what gradient descent actually does. The visualization below has two one-dimensional losses: a convex bowl, and a non-convex curve with two valleys of different depths and a hilltop between them. Click anywhere on a curve to choose a starting point, then run gradient descent and see where it ends up.

Here is the same experiment in code, using the convex loss $f(x) = (x - 3)^2$ and the non-convex loss $g(x) = x^4 - 3x^2 + x$, whose derivative $g'(x) = 4x^3 - 6x + 1$ has three roots at $x \approx -1.3008$, $0.1699$ and $1.1309$. The second derivative $g''(x) = 12x^2 - 6$ is positive at the outer two roots, which makes each of them a minimum, and negative at the middle one, which is the hilltop. The whole algorithm is the single line x = x - lr * grad(x), which is the update $x \leftarrow x - \eta f'(x)$.

def gradient_descent(grad, x0, lr, steps):
    x = float(x0)
    for _ in range(steps):
        x = x - lr * grad(x)
    return x


# Convex bowl: f(x) = (x - 3)^2
def convex_grad(x):
    return 2 * (x - 3)


# Double well: g(x) = x^4 - 3x^2 + x
def g(x):
    return x**4 - 3 * x**2 + x

def nonconvex_grad(x):
    return 4 * x**3 - 6 * x + 1


for start in (-10, 0, 10):
    end = gradient_descent(convex_grad, start, lr=0.1, steps=200)
    print(f"convex      start {start:>3}  ->  x = {end:.4f}")

for start in (-2, 2):
    end = gradient_descent(nonconvex_grad, start, lr=0.01, steps=2000)
    print(f"non-convex  start {start:>3}  ->  x = {end:.4f}   g(x) = {g(end):.4f}")

convex      start -10  ->  x = 3.0000
convex      start   0  ->  x = 3.0000
convex      start  10  ->  x = 3.0000
non-convex  start  -2  ->  x = -1.3008   g(x) = -3.5139
non-convex  start   2  ->  x = 1.1309   g(x) = -1.0702

On the convex bowl, all three starting points end at exactly the same place. On the non-convex curve, the two runs end at different points with different losses: the run from −2 finds the deeper valley at −3.51, while the run from 2 settles in the shallower one at −1.07. The algorithm was identical in both cases and did nothing wrong either time, so the difference comes entirely from the shape of the surface.

The hilltop at $x \approx 0.17$ is what separates the two outcomes. With a small step size, the iterate keeps sliding downhill and can never climb over a hill that is higher than where it currently stands, so the hilltop divides the starting positions into two basins. You can find the dividing line directly by trying many starting points:

import numpy as np

# spacing 0.05
starts = np.linspace(-2, 2, 81)
ends = np.array([gradient_descent(nonconvex_grad, s, 0.01, 3000) for s in starts])
print("largest start that ends in the left valley:  ", round(float(starts[ends < 0].max()), 2))
print("smallest start that ends in the right valley:", round(float(starts[ends > 0].min()), 2))

largest start that ends in the left valley:   0.15
smallest start that ends in the right valley: 0.2

The boundary falls between 0.15 and 0.20, right where the hilltop is. The practical lesson is that on a non-convex loss a single training run is only one sample, so you should compare the final loss across several random initializations before drawing conclusions about a model or a hyperparameter.

What do convex and non-convex functions mean?

Informally, a convex function is bowl-shaped, with no bump between two valleys of the kind $g$ has above. The precise definition uses a chord: pick any two points $x$ and $y$, draw the straight line between $(x, f(x))$ and $(y, f(y))$, and the function is convex if its graph never rises above that line, whichever two points you choose. A non-convex function is one that breaks this rule somewhere, meaning there are two points whose chord passes below the graph, which is exactly what happens across the hilltop between the two valleys of $g$.

As $\lambda$ moves from 1 to 0, the point $\lambda x + (1-\lambda)y$ slides along the segment from $x$ to $y$. The left side of the inequality is the height of the curve at that point and the right side is the height of the chord, so the inequality simply says the curve never sits above the chord. A bump between two valleys would poke above the chord, which is why a convex function cannot have one.

The same inequality explains why a convex function cannot have a worse local minimum. Suppose $x$ is a local minimum and some other point $y$ has a lower value. If you move a small fraction $t$ of the way from $x$ toward $y$, the inequality gives $f(x + t(y - x)) \le (1-t) f(x) + t f(y)$, which is below $f(x)$. That means there are lower points arbitrarily close to $x$, contradicting the assumption that $x$ was a local minimum.

The Hessian test

For a twice-differentiable function there is also a test you can actually compute. The Hessian $H$ is the matrix of second derivatives, and the function is convex exactly when $H$ is positive semi-definite everywhere, meaning the curvature is non-negative in every direction (all eigenvalues are at least 0). In one dimension this reduces to $f''(x) \ge 0$. The bowl $(x-3)^2$ passes easily because its second derivative is 2 everywhere, while $g$ fails because $g''(0) = -6$.

Three related terms are often mixed up, so it is worth stating them precisely:

• Convex: the chord inequality holds, and there may be many minimizers (together they form a convex set).
• Strictly convex: the inequality is strict whenever $x \ne y$ and $0 < \lambda < 1$, which allows at most one minimizer ($e^x$ is strictly convex and has none at all).
• $\mu$-strongly convex: the Hessian is at least $\mu I$ for some $\mu > 0$, so the curvature is at least $\mu$ in every direction, which guarantees a unique minimizer and lets gradient descent converge faster.

The same inequality with averages: Jensen's inequality

If you replace the weights $\lambda$ and $1-\lambda$ with probabilities, the chord inequality turns into Jensen's inequality: for a convex $f$ and a random variable $X$, $f(\mathbb{E}[X]) \le \mathbb{E}[f(X)]$. For example, if $X$ is −2 or 2 with equal probability and $f(x) = x^2$, the left side is $f(0) = 0$ while the right side is 4. This is the step behind the evidence lower bound in VAEs, and it is also how you prove that KL divergence is never negative.

Why does convexity make gradient descent reliable?

On a convex loss there is nothing for gradient descent to get trapped by. Every point where the gradient of a differentiable convex function is zero is a global minimum, so following the gradient downhill can only end at the best value.

You can see how quickly it gets there by working through one update on the bowl $f(x) = (x-3)^2$ with step size $\eta$:

With $\eta = 0.1$, the distance to 3 shrinks by a factor of 0.8 at every step, no matter where you start. With $\eta = 0.5$ the factor is 0, so the very first step lands exactly on 3, but with $\eta = 1.1$ the factor becomes −1.2 and the iterates oscillate with growing amplitude. Convexity guarantees that there is only one valley, but it does not protect you from a step size that is too large.

Many classical models are convex in their parameters. Linear regression with squared error has Hessian $\tfrac{2}{n} X^\top X$, which is always positive semi-definite, and logistic regression with cross-entropy and SVMs with hinge loss are convex as well, as are their L1 and L2 regularized versions. For these models the optimizer's job is mostly a numerical one, since every run is heading for the same minimum value. Constrained convex problems also enjoy strong duality under mild conditions, which is what SVM solvers take advantage of.

Does “convex” mean there is only one answer?

Not necessarily. Convexity guarantees a single minimum value, but that value can be reached at many different points, and only strict convexity rules this out. When the minimizers form a flat region, where gradient descent ends up inside it depends on where it started.

A common way this happens in ML is a duplicated feature. If a regression has two identical columns, the prediction is $(w_1 + w_2)x$ and the loss depends only on the sum $w_1 + w_2$. Squared error is still convex, but the Hessian has a zero eigenvalue along the direction $w_1 - w_2$, so the minimum is a whole line rather than a single point. Since the gradient of the mean squared error, $\tfrac{2}{n} X^\top (Xw - y)$, is the same for both weights, their difference never changes during training.

import numpy as np

# two identical feature columns
X = np.array([[1., 1.], [2., 2.], [3., 3.]])
y = np.array([2., 4., 6.])

def fit(w0, lr=0.05, steps=2000):
    w = np.array(w0, dtype=float)
    for _ in range(steps):
        # gradient of the mean squared error
        grad = (2 / len(y)) * X.T @ (X @ w - y)
        w = w - lr * grad
    return w

for w0 in ([0, 0], [4, 0], [10, -3]):
    w = fit(w0)
    mse = np.mean((X @ w - y) ** 2)
    print(f"start {w0!s:>8}  ->  w = {np.round(w, 4)}   mse = {mse:.6f}")

start   [0, 0]  ->  w = [1. 1.]   mse = 0.000000
start   [4, 0]  ->  w = [ 3. -1.]   mse = 0.000000
start [10, -3]  ->  w = [ 7.5 -5.5]   mse = 0.000000

All three runs reach zero loss, yet they end with three different weight vectors: each one keeps its starting difference (0, 4 and 13) and moves until the sum reaches 2. This is why the coefficients from a convex fit can still be arbitrary when features are redundant, and why adding an L2 penalty, which makes the loss strongly convex, settles on a single answer.

Why are neural network losses non-convex?

The root cause is that a network's output multiplies parameters from different layers, and a product of parameters is not convex in those parameters. You can see this with a network that has only two weights.

Take a network with one input, one hidden unit and no activation, so the prediction is $a \cdot b \cdot x$. With a single training example $x = 1$ and target 1, the loss is $L(a, b) = (ab - 1)^2$, and it fails the chord test straight away: the points $(1, 1)$ and $(-1, -1)$ both have loss 0, so a convex function would need a loss of at most 0 at their midpoint $(0, 0)$, but the actual loss there is 1.

The Hessian tells the same story. The second derivatives are $L_{aa} = 2b^2$, $L_{bb} = 2a^2$ and $L_{ab} = 4ab - 2$, so at the origin the Hessian is $\begin{bmatrix} 0 & -2 \\ -2 & 0 \end{bmatrix}$, whose eigenvalues are −2 and 2, meaning there is negative curvature along the direction $(1, 1)$.

Real networks add nonlinear activations and many more layers, but they keep this product structure. They also have symmetries: permuting the hidden units in a layer, together with their weights, leaves the function unchanged, so a minimizer rarely stands alone. You can explore the loss surface of a small network below.

The loss matters, not only the model

Whether a problem is convex depends on the loss as well as the model. Take a single example with target 1 and $p = \sigma(w)$: the cross-entropy loss $-\log \sigma(w)$ has second derivative $p(1-p)$, which is positive everywhere, so logistic regression with cross-entropy is convex in its weights. The squared-error loss $(\sigma(w) - 1)^2$ has second derivative $-2p(1-p)^2(1-3p)$, which is negative whenever $w < -\ln 2$, so the same model trained with squared error is not convex. This is one of the reasons cross-entropy is the standard choice for classifiers.

Does a non-convex loss mean gradient descent gets stuck?

Usually not, but you do lose the convex guarantee, and what remains is much weaker. For a smooth loss that is bounded below, gradient descent with step $1/L$ only guarantees that the smallest gradient norm seen so far shrinks, at a rate like $\sqrt{2L(f(x_0) - f_{\inf})/k}$. In other words, the iterates approach a point where the gradient is small, and the theory says nothing about whether that point is a good one.

Three different kinds of trouble can show up on a non-convex surface:

• Local minimum: the gradient is zero and the loss rises in every direction, but the value may be worse than the global minimum.
• Saddle point: the gradient is zero, but the Hessian has eigenvalues of both signs, so the loss rises in some directions and falls in others (a saddle is not just a flat region).
• Plateau: the gradient is small over a wide area, so progress is slow even though no zero-gradient point has been reached.

The two-weight loss $(ab - 1)^2$ makes the difference between minima and saddles very concrete. Its gradients are $\partial L / \partial a = 2(ab-1)b$ and $\partial L / \partial b = 2(ab-1)a$, and the key line in the listing updates both weights using the old values of $a$ and $b$.

def loss(a, b):
    # one example: x = 1, target = 1, prediction = a * b
    return (a * b - 1) ** 2

def descend(a, b, lr=0.05, steps=3000):
    for _ in range(steps):
        # residual
        r = a * b - 1
        # both updates use the old a and b
        a, b = a - lr * 2 * r * b, b - lr * 2 * r * a
    return a, b

print("loss at (1, 1), (-1, -1), (0, 0):", loss(1, 1), loss(-1, -1), loss(0, 0))

for start in [(0.1, 0.1), (2.0, 0.1), (-1.5, 0.5), (0.5, -0.5)]:
    a, b = descend(*start)
    print(f"start {start!s:>12}  ->  a = {a:7.4f}, b = {b:7.4f}, loss = {loss(a, b):.4f}")

loss at (1, 1), (-1, -1), (0, 0): 0 0 1
start   (0.1, 0.1)  ->  a =  1.0000, b =  1.0000, loss = 0.0000
start   (2.0, 0.1)  ->  a =  2.0468, b =  0.4886, loss = 0.0000
start  (-1.5, 0.5)  ->  a = -1.5108, b = -0.6619, loss = 0.0000
start  (0.5, -0.5)  ->  a =  0.0000, b = -0.0000, loss = 1.0000

Three of the runs end at different weights but all reach a loss of 0, because every minimum of this loss lies on the curve $ab = 1$ and all of them are global. So even though the loss is non-convex, it has no bad local minimum.

The fourth run ends at the saddle $(0, 0)$ with a loss of 1. It started exactly on the line $a = -b$, which is the direction of positive curvature (eigenvalue +2) at the saddle, and along that line the loss is $(a^2 + 1)^2$, which is smallest at $a = 0$. Gradient descent therefore slides straight into the saddle and stays there.

In practice it rarely ends up there, because starting exactly on that line is a measure-zero event. If you move the start even slightly off the line, the unstable component grows by a factor of about 1.1 per step:

def steps_to_leave(delta, lr=0.05, limit=5000):
    # almost on the line a = -b that leads into the saddle
    a, b = 0.5, -0.5 + delta
    for k in range(limit):
        # clearly on the way to the valley ab = 1
        if a * b > 0.5:
            return k
        r = a * b - 1
        a, b = a - lr * 2 * r * b, b - lr * 2 * r * a
    # never left within the limit
    return None

for delta in (1e-2, 1e-4, 1e-6, 1e-8, 0.0):
    print(f"offset {delta:.0e}  ->  steps to leave: {steps_to_leave(delta)}")

offset 1e-02  ->  steps to leave: 55
offset 1e-04  ->  steps to leave: 103
offset 1e-06  ->  steps to leave: 151
offset 1e-08  ->  steps to leave: 199
offset 0e+00  ->  steps to leave: None

Making the offset 100 times smaller costs only about 48 extra steps, since $\ln(100) / \ln(1.1) \approx 48$, so a saddle mostly delays gradient descent rather than trapping it, and only an exact hit stays forever. In the toy model, starting at $(0, 0)$ means being stuck for good because the gradient there is exactly zero. Real networks face the same hazard with all-zero or perfectly symmetric initializations, which is one of the reasons weights are initialized randomly.

This agrees with the theory. Lee et al. (2016) proved that for smooth functions whose saddle points all have a direction of negative curvature, gradient descent with a small enough step size converges to a saddle only from a set of starting points of measure zero, and the saddle in our toy model is exactly this kind of strict saddle.

For large networks, two results are worth knowing, and they make different kinds of claim. Kawaguchi (2016) proved that for deep linear networks with squared loss, the loss is non-convex but every local minimum is global and every other critical point is a saddle; his extension to nonlinear networks relies on an independence assumption. Dauphin et al. (2014) argued, using statistical physics, random matrix theory and experiments, that in high dimensions the main obstacle is saddle points and the plateaus around them rather than poor local minima, which is a well-supported argument rather than a theorem that holds for every model and dataset.

Together, these results explain why “stuck in a bad local minimum” is rarely the right first diagnosis when a run fails; the step size, the initialization and the gradient computation are better places to start looking. The lessons on local minima vs saddle points and loss landscapes go into more depth.

Do momentum and Adam make the problem convex?

No. An optimizer changes the path taken across the loss surface, but it has no effect on whether the objective itself is convex.

Momentum keeps a running average of past gradients, which carries the iterate across flat regions and smooths out oscillation in narrow valleys. RMSProp and Adam rescale each parameter's step using running gradient magnitudes, which helps when curvature differs a lot across parameters. Mini-batch noise in SGD plays a role similar to the small offset in the last listing, since it can push an iterate off a saddle's stable direction, although this is an intuition for why noise helps rather than a proof.

None of these methods gives a global-optimality guarantee on a non-convex loss. When two optimizers end at different losses on the same network, the difference comes from the paths they took across one fixed surface. Adaptive methods often train faster in practice, but that is an empirical observation on particular problems rather than a theorem.

What mistakes do people make when reasoning about convexity?

Each of the beliefs below is almost right, which is exactly why it keeps coming up, so the more precise version follows each one.

• “Convex means there is only one minimum.” Convexity means there is one minimum value, but the minimizers can form a line or a plane, as the duplicated-feature example showed.
• “Non-convex means gradient descent gets stuck.” It means the only guarantee is that the gradient gets small. Landing exactly on a saddle is rare, and the bigger risks are usually the step size, the initialization and plateaus.
• “A zero gradient means I found the answer.” That is true for a differentiable convex loss, but otherwise you need to check the Hessian eigenvalues to tell whether the point is a minimum, a maximum or a saddle.
• “My model is convex because it is simple.” Convexity is a property of the loss as a function of the parameters, which is why logistic regression is convex with cross-entropy but not with squared error.
• “A larger learning rate just trains faster.” On the bowl above the shrink factor is $1 - 2\eta$, so once $\eta$ goes past 1 the iterates grow with every step.
• “My gradient is probably right.” A wrong gradient on a convex bowl will converge calmly to the wrong place, so compare it against a finite-difference estimate before debugging anything else.

Practice this

You have now seen the update rule on a bowl, a double well and a two-weight network, and the problems below let you implement each of these pieces yourself.

• Implement Gradient Descent for a 1D Quadratic: write the update $x \leftarrow x - \eta(2ax + b)$ and confirm the $1 - 2a\eta$ shrink factor yourself.
• Finite Difference Gradient Checking: compare an analytic gradient against a numerical estimate, which is the check that catches a wrong derivative on any surface.
• Implement Adam Optimizer Step: code one Adam update with moment estimates and bias correction, then compare its path with plain gradient descent.
• Train a Tiny Micrograd MLP: train a small network with an autograd engine on a real non-convex loss, where it is worth comparing several initializations.

For more in the same area, see the optimization problem list and the full problem catalogue.

Sources

• Boyd and Vandenberghe, Convex Optimization (Cambridge University Press, 2004), for the definitions and the first-order and Hessian conditions.
• Bubeck, Convex Optimization: Algorithms and Complexity (2015), for convergence of gradient descent on smooth and strongly convex functions.
• Nesterov, Introductory Lectures on Convex Optimization (2004), for gradient descent rates, including the non-convex gradient-norm bound.
• Lee, Simchowitz, Jordan and Recht, “Gradient Descent Only Converges to Minimizers”, COLT 2016.
• Dauphin et al., “Identifying and attacking the saddle point problem in high-dimensional non-convex optimization”, NeurIPS 2014.
• Kawaguchi, “Deep Learning without Poor Local Minima”, NeurIPS 2016.