Convexity and Lagrange Multipliers: Optimization With Rules (ML Lesson 37)

Imagine a hiker who wants the lowest point in a valley, but a fence blocks the lowest spot. Gradient descent alone cannot handle that. Today we learn two big ideas: convexity, which tells us when a minimum can be trusted, and Lagrange multipliers, which let us optimize while obeying rules.

• Unconstrained vs constrained
• Lesson 37

In lesson 36 we mastered the chain rule and computational graphs, which tell us how to compute gradients. Today we ask a different question: once we have a gradient, when can we trust where it leads? This idea powers linear regression, logistic regression, and the support vector machine.

• Lesson 36: chain rule
• Today: convexity and constraints
• Next: covariance

Here is the picture. Take a curve and pick any two points on it. Draw the straight line segment between them, called a chord. If the chord never dips below the curve, for every pair of points, the function is convex. Think of a bowl: a string stretched across the bowl always hangs above the surface.

• Chord stays above the curve
• f(tx+(1-t)y) ≤ t f(x)+(1-t) f(y)

As a formula: f of t times x plus one minus t times y is less than or equal to t times f of x plus one minus t times f of y, for every t between zero and one. The left side is the curve at a blend of the inputs. The right side is the same blend of the outputs, which is the height of the chord.

• t between 0 and 1
• Point on chord = weighted average

Let us check with numbers. Let f of x equal x squared, with x equal to zero, y equal to four, and t equal to one half. The blended input is two, and f of two is four. The blend of outputs is half of zero plus half of sixteen, which is eight. Four is at most eight, so the chord is above the curve.

• f(x)=x² , x=0, y=4, t=0.5
• Curve 4 ≤ chord 8

Now a function that fails. Take a curve with two valleys and a hill between them. Choose one point in each valley and draw the chord. Over the hill, the chord passes below the curve. One violation is enough, so the function is not convex. Those two valleys are exactly the trouble we will worry about next.

• Wavy curve breaks the rule
• Chord dips below the curve

Here is the payoff. In a convex function, every local minimum is a global minimum. Why? Suppose a point a is a local minimum but a lower point b exists. The chord from a to b stays above the curve, yet near a it would point downhill below f of a. That contradicts a being a local minimum. So no lower point can exist.

• Every local minimum is global
• No bad valleys

A small caution. Convex does not mean there is exactly one minimizer. A function with a flat bottom has many minimizers, but they all share the same value and form one connected set. If the chord is strictly above the curve, we call it strictly convex, and then the minimizer is unique. Either way, gradient descent cannot get trapped.

• Convex: minima form a connected set
• Strictly convex: unique minimum

Drawing chords for every pair is impractical, so we use calculus. In one dimension, a twice differentiable function is convex exactly when its second derivative is never negative. The second derivative measures how fast the slope changes. Convex means the slope only ever increases, so the curve bends upward like a smile.

• f''(x) ≥ 0 everywhere
• Slope keeps increasing

Examples. For x squared the second derivative is two, always positive, so convex. For x to the fourth, it is twelve x squared, never negative, so convex. For x cubed it is six x, which is negative when x is negative, so x cubed is not convex. Also e to the x has second derivative e to the x, always positive.

• x²: f''=2 convex
• x⁴: f''=12x² convex
• x³: f''=6x not convex

With many parameters, the second derivative becomes the Hessian matrix from lesson 7, holding all second partial derivatives. The rule becomes: the function is convex when the Hessian is positive semidefinite at every point. Recall from lesson 5 that this means all eigenvalues are zero or larger. Positive definite means strictly larger than zero.

• Hessian = matrix of second derivatives
• Convex iff Hessian is PSD

Let us do one. Take f of x and y equal to x squared plus three y squared. The second derivative with respect to x is two, with respect to y is six, and the mixed terms are zero. So the Hessian is a diagonal matrix with two and six. Both eigenvalues are positive, so f is strictly convex, a bowl with a single bottom.

• f = x² + 3y²
• H = diag(2, 6)
• Eigenvalues 2 and 6

Now change one sign: f equals x squared minus y squared. The Hessian is diagonal with two and minus two. One eigenvalue is negative, so the test fails. Geometrically this is a saddle, curving up along x and down along y. The gradient is zero at the origin, yet it is not a minimum. Zero gradient alone proves nothing without convexity.

• f = x² − y²
• H = diag(2, −2)
• One negative eigenvalue

Two handy facts. A sum of convex functions is convex, and multiplying a convex function by a positive number keeps it convex. That means a convex loss plus an L2 penalty, as in lesson 17, is still convex, and the penalty even makes it strictly convex. A negative multiplier, however, flips the bowl upside down.

• Sum of convex is convex
• Positive scaling keeps convexity
• Convex loss + L2 penalty is convex

Now ML losses. For linear regression the mean squared error is one over n times the squared length of X w minus y. Its Hessian is two over n times X transpose X. For any vector v, v transpose X transpose X v equals the squared length of X v, which is never negative. So the Hessian is positive semidefinite and MSE is convex. This is why gradient descent and the normal equation agree.

• L(w) = (1/n)‖Xw − y‖²
• H = (2/n) XᵀX
• XᵀX is PSD

If two features are perfectly collinear, X transpose X has a zero eigenvalue. The bowl then has a flat trough instead of one point. There are infinitely many best weights, but all of them are global minima with the same loss. Adding an L2 penalty makes the Hessian strictly positive definite and restores a unique answer.

• Collinear features
• XᵀX singular
• Flat valley, still all global

Logistic regression uses the log loss. For a positive example with score z, the loss is log of one plus e to the minus z. Its second derivative is sigma of z times one minus sigma of z. At z equal to zero that is one half times one half, which is zero point two five. It is always positive, so the loss is convex in the score, and therefore convex in the weights.

• ℓ(z) = log(1 + e^(−z))
• ℓ''(z) = σ(z)(1 − σ(z))
• Between 0 and 0.25

Neural networks break the rule. Swap two hidden neurons and their weights, and the network computes exactly the same function, so the loss is identical. We get many separate minima with equal loss. If the loss were convex, the average of two such solutions would be no worse, but in general it is worse. So deep loss surfaces are non-convex, with saddles and many valleys.

• Hidden-unit symmetry
• Many equal minima
• Local minima and saddles

Yet deep learning trains well in practice. Many minima found by good optimizers perform similarly, and noisy mini-batch updates help escape poor spots. We lose guarantees, not usefulness. Convex theory still guides us, because every local piece of a smooth loss looks like a bowl or a saddle, and the Hessian test tells us which.

• Good minima are often similar
• Optimizers and noise help
• Convex theory is still the guide

Now constraints. A constrained problem says: minimize f of x and y, subject to g of x and y equals zero. Example: minimize x squared plus y squared, the squared distance from the origin, while staying on the line x plus y equals two. We want the point on the line closest to the origin.

• Minimize f(x, y)
• Subject to g(x, y) = 0

Picture walking along the line. Far away, you cross large circles, so f is big. As you approach the middle, you cross smaller circles. Past the middle, they grow again. The best spot is where the line just touches a circle without crossing it. At that point the line and the circle are tangent.

• Walk along the line
• Value of f goes down then up
• Stop where contour just touches

Tangent curves share a tangent direction, so their normal directions are parallel. The gradient of f is perpendicular to its contour, and the gradient of g is perpendicular to the constraint. At the best point these two arrows point along the same line. We write that as gradient of f equals lambda times gradient of g, where lambda is just a scaling number.

• ∇f ⟂ contour
• ∇g ⟂ constraint
• At optimum: ∇f = λ ∇g

Why must they align? If gradient of f has any component along the constraint, we can slide in the opposite direction and lower f while still obeying the rule. Only when gradient of f points entirely along the normal is there no useful sliding direction left. That is a stationary point for the constrained problem.

• Component along the line
• Slide to reduce f
• Zero component means stuck

Joseph-Louis Lagrange packaged this into one function. Define the Lagrangian L of x, y, lambda as f minus lambda times g. Now set every partial derivative to zero. The derivatives with respect to x and y give gradient of f equals lambda gradient of g. The derivative with respect to lambda gives g equals zero, which is the constraint itself.

• L(x, y, λ) = f − λ g
• Set all partial derivatives to zero

Let us solve our example fully. The objective is x squared plus y squared, and g is x plus y minus two. The Lagrangian is x squared plus y squared minus lambda times the quantity x plus y minus two. Now take three partial derivatives and set them equal to zero.

• f = x² + y²
• g = x + y − 2
• L = x² + y² − λ(x + y − 2)

With respect to x: two x minus lambda equals zero. With respect to y: two y minus lambda equals zero. With respect to lambda: x plus y equals two. The first two give x equals y equals lambda over two. Substituting into the third gives lambda equals two. So x equals one, y equals one, and the minimum value is one squared plus one squared, which is two.

• 2x − λ = 0
• 2y − λ = 0
• x + y = 2
• Solution: x = y = 1, λ = 2

Lambda has a meaning: it measures how the optimal value changes if we shift the constraint. Replace two with a number c. The optimum is x equals y equals c over two, giving f star equal to c squared over two. The derivative with respect to c is c, which is two when c is two. That matches lambda. Moving c from 2 to 2.1 raises the best value by about 0.2.

• Sensitivity of optimum to the constraint
• Change 2 → 2.1
• f* = c²/2, so df*/dc = c = 2

Three common mistakes. First, forgetting the equation from differentiating with respect to lambda, which leaves the system underdetermined. Second, worrying about the sign of lambda; plus or minus conventions flip the sign but give the same x and y. Third, assuming every solution is a minimum. Lagrange gives candidates; you must check, for example with convexity, or compare values.

• Forgetting the constraint equation
• Sign of λ is a convention
• Stationary ≠ minimum without checks

Many ML problems use inequalities: stay inside a region rather than exactly on a boundary. Write the rule as g of x less than or equal to zero. The solution is now one of two cases. Either the unconstrained best point already lies inside the region, so the constraint is inactive, or the best point is pushed onto the boundary, so the constraint is active.

• g(x) ≤ 0
• Feasible region instead of a curve
• Constraint active or inactive

The Karush-Kuhn-Tucker, or KKT, conditions handle both cases. Stationarity: gradient of f plus mu times gradient of g equals zero. Feasibility: g is at most zero, and the multiplier mu is at least zero. Complementary slackness: mu times g equals zero. So either the constraint is tight, or its multiplier is zero. A constraint that is not touching exerts no force.

• Stationarity: ∇f + μ∇g = 0
• Feasibility: g ≤ 0, μ ≥ 0
• Complementary slackness: μ g = 0

Minimize x squared plus y squared subject to two minus x minus y at most zero. Try the unconstrained minimum at the origin: g there is two, which is positive, so infeasible. So the constraint is active. Stationarity gives two x minus mu equals zero, and the same for y, with x plus y equal to two. That gives x equals y equals one and mu equals two, which is positive. All KKT conditions hold. If instead the rule were x plus y at least minus two, the origin is feasible and mu is zero.

• Minimize x² + y² s.t. 2 − x − y ≤ 0
• Active: x = y = 1, μ = 2
• Inactive version: μ = 0

This is exactly what the support vector machine from lesson 21 needs. We minimize half the squared length of w, which maximizes the margin, subject to one inequality per training point: y i times w dot x i plus b is at least one. The objective is convex and the constraints are linear, so KKT conditions are both necessary and sufficient here.

• Minimize ½‖w‖²
• Subject to yᵢ(w·xᵢ + b) ≥ 1
• One constraint per training point

Now complementary slackness becomes a picture. A point far from the margin has a slack constraint, so its multiplier is zero, and it has no influence on the boundary. Only points sitting exactly on the margin have active constraints and positive multipliers. Those are the support vectors. You could delete every other point and get the same classifier.

• Far points: constraint slack, μᵢ = 0
• Points on margin: active, μᵢ > 0
• Only support vectors shape the boundary

One last idea, at intuition level. For any fixed nonnegative multipliers, the minimum of the Lagrangian over x is a lower bound on the true constrained minimum. The dual problem searches for the multipliers that make this bound as high as possible. It turns a problem about weights into a problem about multipliers.

• Primal: minimize over x
• Dual: maximize over multipliers
• Dual gives a lower bound

Weak duality always holds: the dual value never exceeds the primal value. For convex problems with a mild condition, such as a strictly feasible point, strong duality holds and the gap closes to zero. The SVM satisfies this. In lesson 43 we will use it to derive the SVM dual and see how kernels appear. Today we only need the idea.

• Weak: dual ≤ primal always
• Strong: equality for convex problems with a feasible interior
• Gap closes at the KKT point

Let us recap. Convex functions have chords above the curve, a positive semidefinite Hessian, and every local minimum is global. MSE and logistic loss are convex; neural network losses are not. With equality constraints, the gradients align and Lagrange multipliers give us equations to solve. With inequalities, KKT adds feasibility, nonnegative multipliers, and complementary slackness. Duality gives lower bounds.

• Convex: chord above curve, Hessian PSD
• MSE and logistic loss convex, deep nets not
• Lagrange: ∇f = λ∇g; KKT adds μ ≥ 0, μg = 0

Next time, in lesson 38, we turn to covariance, correlation, and the multivariate Gaussian, which will connect ellipses and eigenvectors to data.

• Next: covariance and the multivariate Gaussian
• Subscribe for the full course