Regression

345. Regression

345.1. Linear Regression

345.1.1. Simple Linear Regression

345.1.1.1. Data and Model

We observe a dataset of $𝑛$ samples:

(𝑥_{𝑖}, 𝑦_{𝑖}) 𝑖 = 1, \dots, 𝑛

We assume a linear relationship between $𝑥$ and $𝑦$ :

𝑦 = 𝛼 + 𝛽 𝑥_{𝑖} + 𝜀_{𝑖}

Where:

$𝛼$ : intercept
$𝛽$ : slope
$𝜀_{𝑖}$ : error term (noise)

345.1.1.2. Optimization Problem

The parameters $𝛼$ and $𝛽$ are estimated by minimizing the sum of square errors (SSE)

min_{𝛼, 𝛽} 𝑓 (𝛼, 𝛽) = \sum_{𝑖 = 1}^{𝑛} {[𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{1})]}^{2}

This is an unconstrained convex optimization problem

345.1.1.3. Gradient and Hessian

Compute the partial derivatives:

\begin{matrix} \frac{𝜕 𝑓}{𝜕 𝛼} = - 2 \sum_{𝑖 = 1}^{𝑛} [𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{1})] \\ \frac{𝜕 𝑓}{𝜕 𝛽} = - 2 \sum_{𝑖 = 1}^{𝑛} [𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{1})] 𝑥_{𝑖} \end{matrix}

Thus, the gradient is:

\nabla 𝑓 (𝛼, 𝛽) = [\begin{matrix} - 2 \sum_{𝑖 = 1}^{𝑛} [𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{1})] \\ - 2 \sum_{𝑖 = 1}^{𝑛} [𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{1})] 𝑥_{𝑖} \end{matrix}]

and the Hessian matrix is:

\begin{aligned} \nabla^{2} 𝑓 (𝛼, 𝛽) & = [\begin{matrix} 2 𝑛 & 2 \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} \\ 2 \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} & 2 \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2} \end{matrix}] \\ = 2 [\begin{matrix} 𝑛 & \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} \\ \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} & \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2} \end{matrix}] \end{aligned}

345.1.1.4. Convexity

The Hessian is constant (does not depend on $𝛼$ , $𝛽$ ) and symmetric. We check positive semidefiniteness via the determinant:

det (\nabla^{2} 𝑓) = 4 (𝑛 \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2} - {(\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖})}^{2}) = 4 \sum_{𝑖 < 𝑗} {(𝑥_{𝑖} - 𝑥_{𝑗})}^{2} \geq 0

Sincle this expression is nonnegative for all $𝑥_{𝑖}$ , $𝑓$ is convex

345.1.1.5. Optimality Conditions

Setting the gradient equal to zero gives the normal equaltions:

{\begin{cases} 𝑛 𝛼 + (\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}) 𝛽 & = \sum_{𝑖 = 1}^{𝑛} 𝑦_{𝑖} \\ (\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}) 𝛼 + (\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2}) 𝛽 & = \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} 𝑦_{𝑖} \end{cases}

Solving this linear system yields the closed-form solution:

\begin{aligned} \hat{𝛽} & = \frac{\sum_{𝑖} (𝑥_{𝑖} - \bar{𝑥}) (𝑦_{𝑖} - \bar{𝑦})}{\sum_{𝑖} {(𝑥_{𝑖} - \bar{𝑥})}^{2}} \\ \hat{𝛼} & = \bar{𝑦} - \hat{𝛽} \bar{𝑥} \end{aligned}

where:

\bar{𝑥} = \frac{1}{𝑛} \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖} \bar{𝑦} = \frac{1}{𝑛} \sum_{𝑖 = 1}^{𝑛} 𝑦_{𝑖}

345.1.1.6. Convexity by Decomposition

Alternatively, decompose $𝑓 (𝛼, 𝛽)$ as:

𝑓 (𝛼, 𝛽) = \sum_{𝑖 = 1}^{𝑛} {[𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{𝑖})]}^{2} = \sum_{𝑖 = 1}^{𝑛} 𝑓_{𝑖} (𝛼, 𝛽)

𝑓_{𝑖} (𝛼, 𝛽) = {[𝑦_{𝑖} - (𝛼 + 𝛽 𝑥_{𝑖})]}^{2}

Expanding $𝑓_{𝑖}$ :

𝑓_{𝑖} (𝛼, 𝛽) = 𝑦_{𝑖}^{2} + 𝛼^{2} + 𝛽^{2} 𝑥_{𝑖}^{2} - 2 𝛼 𝑦_{𝑖} - 2 𝛽 𝑥_{𝑖} 𝑦_{𝑖} + 2 𝛼 𝛽 𝑥_{𝑖}

Each $𝑓_{𝑖}$ is a quadratic function in ( $𝛼$ , $𝛽$ )

Each $𝑓_{𝑖}$ has Hessian:

\nabla^{2} 𝑓_{𝑖} (𝛼, 𝛽) = [\begin{matrix} 2 & 2 𝑥_{𝑖} \\ 2 𝑥_{𝑖} & 2 𝑥_{𝑖}^{2} \end{matrix}] = 2 [\begin{matrix} 1 & 𝑥_{𝑖} \\ 𝑥_{𝑖} & 𝑥_{𝑖}^{2} \end{matrix}]

Since each $\nabla^{2} 𝑓_{𝑖}$ is positive semidefinite, and sums of convex functions are convex, $𝑓$ is convex

Example

345.1.2. Multiple Linear Regression

345.1.2.1. Data and Model

For $𝑛$ samples and $𝑝$ predictors:

(𝑥_{1}^{(𝑖)}, 𝑥_{2}^{(𝑖)}, \dots, 𝑥_{𝑝}^{(𝑖)}, 𝑦_{𝑖}) 𝑖 = 1, \dots, 𝑛

The model is:

\begin{aligned} 𝑦_{𝑖} & = 𝛼 + 𝛽_{1} 𝑥_{1}^{(𝑖)} + \dots + 𝛽_{𝑝} 𝑥_{𝑝}^{(𝑖)} + 𝜀_{𝑖} \\ = 𝛼 + 𝜷^{𝑇} 𝐱^{(𝑖)} + 𝜀_{𝑖} \end{aligned}

345.1.2.2. Optimization Problem

min_{𝛼, 𝛽} 𝑓 (𝛼, 𝛽)

where

\begin{aligned} 𝑓 (𝛼, 𝛽) & = \sum_{𝑖 = 1}^{𝑛} {[𝑦_{𝑖} - (𝛼 + \sum_{𝑗 = 1}^{𝑝} 𝛽_{𝑗} 𝑥_{𝑗}^{𝑖})]}^{2} \\ = \sum_{𝑖 = 1}^{𝑛} {[𝑦_{𝑖} - (𝛼 + 𝜷^{𝑇} 𝐱^{(𝑖)})]}^{2} \end{aligned}

In matrix form, letting $𝑋 \in ℝ^{𝑛 \times 𝑝}$ be the data matrix, $𝒚 \in ℝ^{𝑛}$ , and $𝟏$ the column of ones:

min_{𝛼, 𝛽} ‖ 𝒚 - 𝛼 𝟏 - 𝑋 𝛽 ‖_{2}^{2}

The closed-form solution is:

\begin{aligned} \hat{𝛽} & = {(𝑋^{𝑇} 𝑋)}^{- 1} 𝑋^{𝑇} (𝐲 - \bar{𝑦} 𝟏) \\ \hat{𝛼} & = \bar{𝑦} - {\hat{𝛽}}^{𝑇} \bar{𝐱} \end{aligned}

provided $𝑋^{𝑇} 𝑋$ is invertible

345.1.3. Regularization

Regularization penalizes large coefficients to prevent overfitting and improve numerical stability.

Let $𝜆 > 0$ be a regularization parameter.

345.1.3.1. Ridge Regression (L2 Regularization)

min_{𝛼, 𝛽} \sum_{𝑖 = 1}^{𝑛} {[𝑦_{𝑖} - (𝛼 + 𝜷^{𝑇} 𝐱^{𝑖})]}^{2} + 𝜆 \sum_{𝑗 = 1}^{𝑝} 𝛽_{𝑗}^{2}

In matrix form:

min_{𝛽} ‖ 𝐲 - 𝑋 𝜷 ‖_{2}^{2} + 𝜆 ‖ 𝜷 ‖_{2}^{2}

Closed-form solution (for centered data):

\hat{𝜷} = {(𝑋^{𝑇} 𝑋 + 𝜆 𝐼_{𝑝})}^{- 1} 𝑋^{𝑇} 𝐲

Ridge regression shrinks coefficients toward zero but does not set them exactly to zero.

345.1.3.2. LASSO Regression (L1 Regularization)

min_{𝛼, 𝛽} \sum_{𝑖 = 1}^{𝑛} {[𝑦_{𝑖} - (𝛼 + 𝛽^{𝑇} 𝑥^{𝑖})]}^{2} + 𝜆 \sum_{𝑗 = 1}^{𝑝} | 𝛽_{𝑗} |

LASSO performs feature selection because some coefficients can become exactly zero.

This problem is still convex but non-differentiable due to the absolute value term.

Example