Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 38 · Applications in Machine Learning

Logistic Regression as a Convex Problem

Show that the logistic loss is convex, derive its gradient and Hessian, and train a classifier with gradient descent and Newton's method on a small two-class dataset.

Logistic regression is the standard model for two-class classification. Given features x, it predicts the probability of class +1 as σ(wᵀx), where the sigmoid is σ(z) = 1 / (1 + e^{−z}). Training means finding the weights w that fit labeled data best. The reason this is a good fit for a course on convex optimization: the training problem is convex, so any local minimum is global and the algorithms from this track apply directly.

The loss

Label each sample with y_i ∈ {−1, +1}. The probability the model assigns to the correct label is σ(y_i wᵀx_i). We minimize the average negative log-likelihood, the logistic loss:

Text
F(w) = (1/N) Σ log(1 + exp(−y_i wᵀx_i))

When y_i wᵀx_i is large and positive (a confident, correct prediction), the term is near 0. When it is large and negative (confident and wrong), the term grows linearly. So the loss is a smooth, convex stand-in for counting mistakes.

Why it is convex

Let ℓ(m) = log(1 + e^{−m}) with margin m = y wᵀx. Its derivatives are:

Text
ℓ'(m)  = −σ(−m)
ℓ''(m) =  σ(m) σ(−m)  =  σ(m)(1 − σ(m))  > 0

Since ℓ'' > 0, the one-variable function ℓ is convex. The margin m = y xᵀw is linear in w, and a convex function of a linear map is convex. A sum of convex functions is convex, so F is convex.

The gradient and Hessian of F follow from the chain rule (write s_i = σ(wᵀx_i); because y_i² = 1, the labels drop out of the Hessian):

Text
∇F(w) = −(1/N) Σ y_i x_i σ(−y_i wᵀx_i)
∇²F(w) = (1/N) Σ s_i (1 − s_i) x_i x_iᵀ,      where s_i = σ(wᵀx_i)

Each term x_i x_iᵀ is positive semidefinite and each weight s_i(1 − s_i) is positive, so the Hessian is positive semidefinite everywhere, a second confirmation of convexity.

If the two classes can be perfectly separated by a hyperplane, the loss keeps decreasing as ‖w‖ grows, and no finite minimizer exists. Adding a ridge penalty (λ/2)‖w‖² fixes this and makes the problem strongly convex. Real libraries use such a penalty by default.

Training with gradient descent and Newton's method

Gradient descent works but needs a step size. For this loss, the gradient is Lipschitz with constant at most λ_max(XᵀX) / (4N), because σ(1 − σ) ≤ 1/4. Newton's method uses the Hessian to take a much better step: w ← w − H⁻¹ g. For logistic regression this is also called IRLS (iteratively reweighted least squares). It needs a linear solve per iteration but converges in a handful of steps.

We generate two overlapping Gaussian clouds in 2D, add a bias column, and train with a small ridge penalty λ = 0.01 to keep the problem well posed.

Python Gradient descent versus Newton on logistic loss

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the gradient norms. Newton's method drives the gradient below 10⁻¹⁰ at iteration 6 (quadratic convergence near the solution: the number of correct digits roughly doubles each step), while gradient descent needs about 200 iterations to reach the same accuracy. Both end at the same weights, as convexity promises.

Checking convexity numerically

A convex function has a positive semidefinite Hessian everywhere. We cannot check every point, but evaluating the smallest Hessian eigenvalue at many random weight vectors is a useful sanity test: seeing a clearly negative value would prove a bug.

Python Smallest Hessian eigenvalue at random points

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading the model

  • The decision boundary is wᵀx = 0, a straight line in 2D (a hyperplane in general).
  • σ(wᵀx) is the predicted probability of class +1; a point on the boundary has probability 0.5.
  • Regularization (ridge or lasso, as in the previous lessons) trades a little training loss for stability and, with L1, for a sparse model. Logistic regression with an L1 penalty is solved by exactly the ISTA/FISTA method of the proximal lesson.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why is the logistic loss convex in w?

    A convex function composed with a linear map is convex, and sums of convex functions stay convex.
  2. 2. What is the main advantage of Newton's method over gradient descent here?

    Using curvature gives quadratic convergence near the solution; each iteration is more expensive.
  3. 3. What happens to unregularized logistic regression on perfectly separable data?

    Scaling w up makes every margin larger and the loss smaller, forever.
  4. 4. Which bound on σ(z)(1 − σ(z)) is used to set the gradient-descent step?

    The sigmoid's slope peaks at 1/4 (at z = 0), so the Hessian is bounded by XᵀX/(4N).

Summary

  • The logistic loss (1/N) Σ log(1 + exp(−y_i wᵀx_i)) is smooth and convex; adding a ridge term makes it strongly convex.
  • Gradient: −(1/N) Σ y_i x_i σ(−y_i wᵀx_i); Hessian: (1/N) Σ s_i(1 − s_i) x_i x_iᵀ.
  • Gradient descent with step 1/L is simple; Newton (IRLS) converges in a few iterations.
  • Perfectly separable data needs a penalty to have a finite solution.

Next: Support Vector Machines and Duality