Logistic Regression

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. The Classification Problem
6. The Logistic Function and Link
7. Bernoulli Likelihood and Cross-Entropy
8. Gradient Derivation
9. The Hessian and Convexity
10. Decision Boundaries and Geometry
11. Multiclass Extension: Softmax Regression
12. Regularized Logistic Regression
13. Connection to Generalized Linear Models
14. Worked Examples
15. Connection to the Broader Curriculum
16. Common Pitfalls and Misconceptions
17. Research Perspective
18. Summary of Takeaways
19. Exercises

---

Learning Objectives

After reading this chapter, you should be able to:

1. Formulate binary classification as estimating $P(y=1 \mid \mathbf{x})$ via a linear predictor composed with the logistic sigmoid.
2. Derive the cross-entropy (logistic) loss from the Bernoulli negative log-likelihood.
3. Compute the gradient $\nabla_{\boldsymbol{\theta}} J$ and explain its resemblance to the linear regression gradient.
4. Prove that the logistic loss is strictly convex in $\boldsymbol{\theta}$, guaranteeing a unique global minimum.
5. Characterize the decision boundary as a hyperplane in feature space.
6. Extend the framework to $K$-class classification via the softmax function.
7. Explain why linear classification remains linear in feature space even though the link function is nonlinear.

---

Prerequisites

This chapter builds on:

• Linear Regression — design matrix, parameter vector, loss minimization
• Gradient Descent — iterative optimization, convexity
• Bayes' Theorem — conditional probability, odds

---

Notation

• $y_i \in \lbrace 0, 1 \rbrace$ or $\lbrace 1, \ldots, K \rbrace$ — Binary or multiclass labels
• $\sigma(z) = 1/(1+e^{-z})$ — Logistic sigmoid
• $\mathbf{W} \in \mathbb{R}^{K \times d}$ — Multiclass weight matrix
• $p(y \mid \mathbf{x}; \boldsymbol{\theta})$ — Predicted class probability
• $\mathcal{L}(\boldsymbol{\theta})$ — Cross-entropy loss

---

Core Intuition

Linear regression predicts continuous values; logistic regression predicts probabilities for binary (and, by extension, categorical) outcomes. The key insight is separation of concerns:

1. A linear score $z = \boldsymbol{\theta}^T \tilde{\mathbf{x}}$ captures how strongly the features favor class 1.
2. A link function $\sigma(z)$ maps the score to a valid probability in $(0, 1)$.

This template — linear predictor plus link function — defines the class of Generalized Linear Models (GLMs). Logistic regression is the GLM for Bernoulli-distributed responses. Every binary classifier in deep learning (the final sigmoid or softmax layer) is a direct descendant.

The loss function changes from squared error to cross-entropy, which penalizes confident wrong predictions harshly. The gradient takes a remarkably clean form — structurally identical to linear regression but with "residuals" replaced by prediction errors in probability space.

Series context. This is Part II of Chapter 4 (Supervised Learning) in Volume II. It follows Linear Regression and precedes Bayesian Linear Regression.

---

The Classification Problem

Definition 1 (Binary Classification). Given training data $\{(\mathbf{x}_i, y_i)\}_{i=1}^{N}$ with $\mathbf{x}_i \in \mathbb{R}^d$ and $y_i \in \{0, 1\}$, learn a function that predicts the label of unseen examples.

We model the conditional probability:

$$P(y = 1 \mid \mathbf{x}; \boldsymbol{\theta}) = h_{\boldsymbol{\theta}}(\mathbf{x}), \quad P(y = 0 \mid \mathbf{x}; \boldsymbol{\theta}) = 1 - h_{\boldsymbol{\theta}}(\mathbf{x}). \tag{1}$$

The prediction task reduces to estimating $h_{\boldsymbol{\theta}}(\mathbf{x})$ and thresholding (typically at $\frac{1}{2}$).

Definition 2 (Linear Score). The logit input (linear predictor) is

$$z = \boldsymbol{\theta}^T \tilde{\mathbf{x}} = \theta_0 + \sum_{j=1}^{d} \theta_j x_j. \tag{2}$$

We require a function $h: \mathbb{R} \to (0,1)$ such that $h_{\boldsymbol{\theta}}(\mathbf{x}) = h(z)$.

---

The Logistic Function and Link

Definition 3 (Logistic Sigmoid). The logistic function (sigmoid) is

$$\sigma(z) = \frac{1}{1 + e^{-z}} = \frac{e^z}{1 + e^z}. \tag{3}$$

Proposition 1 (Properties of $\sigma$). The logistic function satisfies:

1. $\sigma(z) \in (0, 1)$ for all $z \in \mathbb{R}$
2. $\sigma(-z) = 1 - \sigma(z)$ (symmetry)
3. $\sigma'(z) = \sigma(z)(1 - \sigma(z))$ (derivative in terms of itself)
4. $\lim_{z \to \infty} \sigma(z) = 1$, $\lim_{z \to -\infty} \sigma(z) = 0$

Proof of (3). By the quotient rule:

$$\sigma'(z) = \frac{e^z(1+e^z) - e^z \cdot e^z}{(1+e^z)^2} = \frac{e^z}{(1+e^z)^2} = \sigma(z) \cdot \frac{1}{1+e^z} = \sigma(z)(1-\sigma(z)). \quad \blacksquare$$

Definition 4 (Log-Odds / Logit). The logit is the inverse of the logistic function:

$$\text{logit}(p) = \log\frac{p}{1-p} = z. \tag{4}$$

Logistic regression models log-odds as linear in features:

$$\log\frac{P(y=1 \mid \mathbf{x})}{P(y=0 \mid \mathbf{x})} = \boldsymbol{\theta}^T \tilde{\mathbf{x}}. \tag{5}$$

Important equation. Equation (5) is the defining property of logistic regression: the log-odds are an affine function of features. This is why the model is "linear" despite predicting nonlinear probabilities.

---

Bernoulli Likelihood and Cross-Entropy

Definition 5 (Bernoulli Distribution). For $y \in \{0, 1\}$, the Bernoulli PMF can be written compactly as

$$P(y \mid \mathbf{x}; \boldsymbol{\theta}) = h_{\boldsymbol{\theta}}(\mathbf{x})^y \cdot (1 - h_{\boldsymbol{\theta}}(\mathbf{x}))^{1-y}. \tag{6}$$

Proposition 2 (Negative Log-Likelihood). The negative log-likelihood for a single observation is

$$-\log P(y \mid \mathbf{x}; \boldsymbol{\theta}) = -y \log h_{\boldsymbol{\theta}}(\mathbf{x}) - (1-y)\log(1 - h_{\boldsymbol{\theta}}(\mathbf{x})). \tag{7}$$

Substituting $h_{\boldsymbol{\theta}}(\mathbf{x}) = \sigma(\boldsymbol{\theta}^T \tilde{\mathbf{x}})$, this is the binary cross-entropy between the true label $y$ and predicted probability $\hat{p} = \sigma(\boldsymbol{\theta}^T \tilde{\mathbf{x}})$.

Definition 6 (Empirical Cross-Entropy Loss). Over $N$ i.i.d. observations:

$$J(\boldsymbol{\theta}) = -\frac{1}{N}\sum_{i=1}^{N}\left[y_i \log \hat{p}_i + (1 - y_i)\log(1 - \hat{p}_i)\right], \tag{8}$$

where $\hat{p}_i = \sigma(\boldsymbol{\theta}^T \tilde{\mathbf{x}}_i)$.

Theorem 1 (Cross-Entropy vs. Squared Error). For probability estimation, cross-entropy is the proper scoring rule derived from maximum likelihood. Using squared error $(y - \hat{p})^2$ on binary labels yields a non-convex loss in $\boldsymbol{\theta}$ and is theoretically unjustified.

Proof sketch. Squared error on $\hat{p} = \sigma(z)$ gives $\frac{d^2}{dz^2}(y - \sigma(z))^2$ which can be negative for certain $(y, z)$ pairs, violating convexity. Cross-entropy's Hessian is positive semidefinite (Theorem 3 below). $\blacksquare$

---

Gradient Derivation

We derive the gradient of (8) in complete detail.

Theorem 2 (Logistic Regression Gradient). The gradient of the average cross-entropy loss is

$$\nabla_{\boldsymbol{\theta}} J = \frac{1}{N}\mathbf{X}^T(\hat{\mathbf{p}} - \mathbf{y}), \tag{9}$$

where $\hat{\mathbf{p}} = (\hat{p}_1, \ldots, \hat{p}_N)^T$ with $\hat{p}_i = \sigma(\boldsymbol{\theta}^T \tilde{\mathbf{x}}_i)$, and $\mathbf{X}$ is the design matrix.

Proof. For a single sample, the loss is $\ell_i = -y_i \log \hat{p}_i - (1-y_i)\log(1-\hat{p}_i)$. By the chain rule:

$$\frac{\partial \ell_i}{\partial \theta_j} = \frac{\partial \ell_i}{\partial \hat{p}_i} \cdot \frac{\partial \hat{p}_i}{\partial z_i} \cdot \frac{\partial z_i}{\partial \theta_j}, \tag{10}$$

where $z_i = \boldsymbol{\theta}^T \tilde{\mathbf{x}}_i$.

Step 1: $\frac{\partial \ell_i}{\partial \hat{p}_i} = -\frac{y_i}{\hat{p}_i} + \frac{1-y_i}{1-\hat{p}_i}$.

Step 2: $\frac{\partial \hat{p}_i}{\partial z_i} = \hat{p}_i(1-\hat{p}_i)$ by Proposition 1.

Step 3: $\frac{\partial z_i}{\partial \theta_j} = \tilde{x}_{ij}$.

Combining:

$$\frac{\partial \ell_i}{\partial \theta_j} = \left(-\frac{y_i}{\hat{p}_i} + \frac{1-y_i}{1-\hat{p}_i}\right)\hat{p}_i(1-\hat{p}_i) = -y_i(1-\hat{p}_i) + (1-y_i)\hat{p}_i = \hat{p}_i - y_i. \tag{11}$$

The simplification in (11) is the hallmark of exponential-family GLMs: the gradient equals the prediction error. Averaging over $N$ samples and stacking into matrix form gives (9). $\blacksquare$

Important equation. Equation (9) mirrors linear regression's gradient $\frac{1}{N}\mathbf{X}^T(\mathbf{X}\boldsymbol{\theta} - \mathbf{y})$, with predictions $\hat{p}_i$ replacing linear predictions. This structural unity is why both models are solved by the same gradient descent machinery.

Corollary 1 (Gradient Descent Update).

$$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \alpha \cdot \frac{1}{N}\mathbf{X}^T(\hat{\mathbf{p}}_t - \mathbf{y}). \tag{12}$$

Unlike linear regression, no closed-form solution exists — $\boldsymbol{\theta}$ appears nonlinearly inside $\sigma$.

---

The Hessian and Convexity

Theorem 3 (Strict Convexity). The logistic loss $J(\boldsymbol{\theta})$ is strictly convex in $\boldsymbol{\theta}$ when $\mathbf{X}$ has full column rank. The Hessian is

$$\mathbf{H} = \nabla^2_{\boldsymbol{\theta}} J = \frac{1}{N}\mathbf{X}^T \mathbf{W} \mathbf{X}, \tag{13}$$

where $\mathbf{W} = \text{diag}(\hat{p}_1(1-\hat{p}_1), \ldots, \hat{p}_N(1-\hat{p}_N))$ is a positive diagonal matrix.

Proof. From (11), $\nabla_{\boldsymbol{\theta}} \ell_i = (\hat{p}_i - y_i)\tilde{\mathbf{x}}_i$. Differentiating with respect to $\boldsymbol{\theta}$:

$$\nabla^2_{\boldsymbol{\theta}} \ell_i = \frac{\partial \hat{p}_i}{\partial z_i}\tilde{\mathbf{x}}_i \tilde{\mathbf{x}}_i^T = \hat{p}_i(1-\hat{p}_i)\tilde{\mathbf{x}}_i \tilde{\mathbf{x}}_i^T. \tag{14}$$

Since $\hat{p}_i(1-\hat{p}_i) > 0$ for $\hat{p}_i \in (0,1)$, each $\nabla^2 \ell_i$ is positive semidefinite. Summing: $\mathbf{H} = \frac{1}{N}\mathbf{X}^T \mathbf{W} \mathbf{X} \succcurlyeq \mathbf{0}$. Strict positive definiteness holds when $\mathbf{X}$ has full column rank and at least one $\hat{p}_i \notin \{0, 1\}$. $\blacksquare$

Consequence. Gradient descent (with appropriate step size) converges to the unique global minimum. Newton's method, using $\mathbf{H}^{-1}$, converges quadratically near the optimum — the basis of Iteratively Reweighted Least Squares (IRLS).

Proposition 3 (IRLS). Newton's update for logistic regression is equivalent to solving a weighted least-squares problem at each iteration:

$$\boldsymbol{\theta}_{t+1} = \left(\mathbf{X}^T \mathbf{W}_t \mathbf{X}\right)^{-1}\mathbf{X}^T \mathbf{W}_t \tilde{\mathbf{z}}_t, \tag{15}$$

where $\mathbf{W}_t$ depends on current predictions and $\tilde{\mathbf{z}}_t$ is a "working response."

---

Decision Boundaries and Geometry

Definition 7 (Decision Boundary). The decision boundary is the set of points where $P(y=1 \mid \mathbf{x}) = \frac{1}{2}$, equivalently where $\boldsymbol{\theta}^T \tilde{\mathbf{x}} = 0$ (since $\sigma(0) = \frac{1}{2}$).

Proposition 4. The decision boundary of logistic regression is a hyperplane in $\mathbb{R}^d$ (or an affine hyperplane if the bias is included in $\tilde{\mathbf{x}}$).

Proof. $\boldsymbol{\theta}^T \tilde{\mathbf{x}} = 0$ defines a hyperplane with normal vector $\boldsymbol{\theta}$. $\blacksquare$

Interpretation. Logistic regression is a linear classifier — it can only separate classes with a linear boundary in the original feature space. Nonlinear boundaries require feature transformations (polynomial features, kernels) or deeper models.

Definition 8 (Margin and Confidence). The magnitude $|\boldsymbol{\theta}^T \tilde{\mathbf{x}}|$ measures distance from the boundary in log-odds space. Large positive $z$ implies high confidence in class 1; large negative $z$ implies high confidence in class 0.

---

Multiclass Extension: Softmax Regression

Definition 9 (Multinomial Logistic / Softmax Regression). For $K$ classes, assign a parameter vector $\boldsymbol{\theta}_k \in \mathbb{R}^{d+1}$ to each class. The softmax function gives class probabilities:

$$P(y = k \mid \mathbf{x}; \boldsymbol{\Theta}) = \frac{\exp(\boldsymbol{\theta}_k^T \tilde{\mathbf{x}})}{\sum_{j=1}^{K}\exp(\boldsymbol{\theta}_j^T \tilde{\mathbf{x}})} = \text{softmax}(\boldsymbol{\Theta}^T \tilde{\mathbf{x}})_k, \tag{16}$$

where $\boldsymbol{\Theta} = [\boldsymbol{\theta}_1 | \cdots | \boldsymbol{\theta}_K] \in \mathbb{R}^{(d+1) \times K}$.

Proposition 5 (Softmax Properties). (i) $P(y=k) \in (0,1)$ and $\sum_k P(y=k) = 1$; (ii) Softmax is invariant to adding a constant to all logits; (iii) Binary logistic regression is softmax with $K=2$.

Definition 10 (Categorical Cross-Entropy). With one-hot labels $\mathbf{y}_i \in \{0,1\}^K$:

$$J(\boldsymbol{\Theta}) = -\frac{1}{N}\sum_{i=1}^{N}\sum_{k=1}^{K} y_{ik} \log \hat{p}_{ik}. \tag{17}$$

Theorem 4 (Softmax Gradient). The gradient with respect to class-$k$ parameters is

$$\nabla_{\boldsymbol{\theta}_k} J = \frac{1}{N}\sum_{i=1}^{N}(\hat{p}_{ik} - y_{ik})\tilde{\mathbf{x}}_i. \tag{18}$$

The same "prediction minus target" structure persists. This is the loss function used in the output layer of every multi-class neural network.

---

Regularized Logistic Regression

Definition 11 (L2-Regularized Logistic Regression).

$$J_{\text{reg}}(\boldsymbol{\theta}) = -\frac{1}{N}\sum_{i=1}^{N}\left[y_i \log \hat{p}_i + (1-y_i)\log(1-\hat{p}_i)\right] + \lambda \|\boldsymbol{\theta}_{1:d}\|_2^2. \tag{19}$$

The regularized problem remains convex. The gradient becomes:

$$\nabla_{\boldsymbol{\theta}} J_{\text{reg}} = \frac{1}{N}\mathbf{X}^T(\hat{\mathbf{p}} - \mathbf{y}) + 2\lambda \mathbf{D}\boldsymbol{\theta}, \tag{20}$$

where $\mathbf{D} = \text{diag}(0, 1, \ldots, 1)$ excludes the bias.

Proposition 6 (L1 Regularization). L1 penalty $\lambda\|\boldsymbol{\theta}_{1:d}\|_1$ produces sparse models — some feature coefficients are exactly zero, performing feature selection. The loss remains convex but is non-differentiable at zero.

---

Connection to Generalized Linear Models

Definition 12 (GLM). A Generalized Linear Model specifies:

1. Linear predictor: $\eta = \boldsymbol{\theta}^T \tilde{\mathbf{x}}$
2. Link function: $g(\mu) = \eta$, where $\mu = \mathbb{E}[y \mid \mathbf{x}]$
3. Exponential family distribution for $y$

For logistic regression: $g = \text{logit}$, $\mu = P(y=1)$, $y \sim \text{Bernoulli}(\mu)$.

For linear regression: $g = \text{identity}$, $\mu = \boldsymbol{\theta}^T \tilde{\mathbf{x}}$, $y \sim \mathcal{N}(\mu, \sigma^2)$.

The GLM framework unifies the gradient structure: $\nabla \ell_i = (y_i - \mu_i)\tilde{\mathbf{x}}_i$ for all exponential-family GLMs with canonical link.

---

Worked Examples

Example 1: Single-Feature Classification

Suppose $\mathbf{x}_i \in \mathbb{R}$ (one feature) and we fit $\hat{p} = \sigma(\theta_0 + \theta_1 x)$. The decision boundary is at $x^* = -\theta_0/\theta_1$. If $\theta_1 > 0$, larger $x$ increases $P(y=1)$.

Example 2: Gradient at Perfect Separation

When data are linearly separable, the MLE $\hat{\boldsymbol{\theta}}$ does not exist — $\|\boldsymbol{\theta}\| \to \infty$ drives $\hat{p}_i \to 0$ or $1$ for all $i$. Regularization is essential to obtain finite parameter estimates.

Example 3: Softmax with Three Classes

For $K=3$, logits $z_1 = 2$, $z_2 = 1$, $z_3 = 0$:

$$\hat{p}_1 = \frac{e^2}{e^2+e^1+e^0} \approx 0.665, \quad \hat{p}_2 \approx 0.245, \quad \hat{p}_3 \approx 0.090. \tag{21}$$

The softmax amplifies differences — class 1 dominates despite modest logit separation.

---

Connection to the Broader Curriculum

• Sigmoid link — Output activation of binary classifiers
• Cross-entropy loss — Standard classification loss
• Softmax — Multi-class output layer
• Linear decision boundary — Last layer before activation; deeper layers learn features
• IRLS / Newton — Second-order optimization methods
• Regularization — Weight decay in all neural networks

Backpropagation extends the gradient computation in (18) through hidden layers. Self-Attention uses softmax over a different axis — attention weights over tokens rather than class probabilities.

---

Common Pitfalls and Misconceptions

Pitfall 1: Using squared error for classification. MSE on binary labels is theoretically improper and practically non-convex in $\boldsymbol{\theta}$. Always use cross-entropy for probabilistic classification.

Pitfall 2: Interpreting coefficients as causal effects. $\theta_j$ is the change in log-odds per unit change in $x_j$, holding other features fixed. This is an associational, not causal, statement unless additional assumptions hold.

Pitfall 3: Ignoring class imbalance. When $P(y=1) \ll 0.5$, the classifier can achieve high accuracy by always predicting 0. Use balanced metrics (F1, AUC-ROC) and consider class-weighted loss.

Pitfall 4: Assuming nonlinear boundaries. Logistic regression with raw features produces only linear boundaries. Nonlinear problems require feature engineering or deeper architectures.

Pitfall 5: Perfect separation without regularization. Linearly separable data causes the MLE to diverge. Always apply regularization or use a Bayesian treatment (Bayesian Linear Regression extends naturally to classification).

Pitfall 6: Confusing $\sigma'(z)$ with the gradient. The derivative of the sigmoid appears in backpropagation through hidden layers, but the gradient of the loss with respect to $\boldsymbol{\theta}$ simplifies to $\hat{\mathbf{p}} - \mathbf{y}$ at the output layer.

---

Research Perspective

Logistic regression originated with the work of Barnard (1949) and Cox (1958) on binary response models. The GLM framework (Nelder & Wedderburn, 1972) placed logistic regression within a unified statistical theory.

In machine learning, logistic regression remains the baseline for:

• Calibration studies: assessing whether predicted probabilities match observed frequencies
• Interpretable models in medicine, finance, and policy
• Neural network output layers: the final softmax-with-cross-entropy layer is softmax regression over learned features

Modern research on calibration in deep learning (Guo et al., 2017) shows that large neural networks are often miscalibrated despite high accuracy — temperature scaling, a single-parameter adjustment of the softmax logits, connects directly to the logistic framework.

The logistic loss also appears in contrastive learning and recommendation systems as a pairwise ranking objective, demonstrating the breadth of this simple model.

---

Summary of Takeaways

• Logistic sigmoid — $\sigma(z) = 1/(1+e^{-z})$ — Maps scores to probabilities
• Log-odds linearity — $\text{logit}(p) = \boldsymbol{\theta}^T\tilde{\mathbf{x}}$ — Defining GLM property
• Cross-entropy — $-y\log\hat{p} - (1-y)\log(1-\hat{p})$ — Proper Bernoulli loss
• Gradient — $\frac{1}{N}\mathbf{X}^T(\hat{\mathbf{p}} - \mathbf{y})$ — Same structure as linear regression
• Hessian — $\frac{1}{N}\mathbf{X}^T\mathbf{W}\mathbf{X}$ — Strict convexity
• Decision boundary — $\boldsymbol{\theta}^T\tilde{\mathbf{x}} = 0$ — Linear hyperplane
• Softmax — $e^{z_k}/\sum_j e^{z_j}$ — Multiclass extension

Next article: Bayesian Linear Regression → — where we place a prior on $\boldsymbol{\theta}$ and derive the posterior predictive distribution.

---

Exercises

Exercise 1 (Sigmoid properties). Prove all four properties in Proposition 1. In particular, verify $\sigma'(z) = \sigma(z)(1-\sigma(z))$ by direct differentiation.

Exercise 2 (Gradient). Derive (11) step by step without skipping algebraic simplification. Show each intermediate expression.

Exercise 3 (Hessian). Verify (14) by differentiating (11). Confirm that $\mathbf{H}$ is positive semidefinite for any $\boldsymbol{\theta}$.

Exercise 4 (Decision boundary). For $\boldsymbol{\theta} = (1, -2, 3)^T$ and features $(1, x_1, x_2)$, find the equation of the decision boundary in the $(x_1, x_2)$ plane. Sketch the regions where $P(y=1) > \frac{1}{2}$.

Exercise 5 (Softmax). Prove that $\text{softmax}(\mathbf{z}) = \text{softmax}(\mathbf{z} + c\mathbf{1})$ for any scalar $c$. Why does this imply identifiability issues for $\boldsymbol{\Theta}$?

Exercise 6 (Separation). Construct a 2D dataset with two points labeled 0 and two labeled 1 that is linearly separable. Show that the cross-entropy loss can be driven arbitrarily close to zero by scaling $\boldsymbol{\theta}$.

Exercise 7 (Multiclass gradient). Derive (18) by applying the chain rule to (17). Show that the gradient for each class has the same "prediction minus target" form.

Exercise 8 (Connection). Show that binary logistic regression with $K=2$ and constraint $\boldsymbol{\theta}_1 = \mathbf{0}$ reduces to standard binary logistic regression. Explain the redundancy in the $K$-class parameterization.