Given a dataset \[\mathcal{D} = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), \ldots, (x_n, y_n)\}\] of data points \(x_i \in \mathbb{R}^d\) and the corresponding labels \(y_i \in \mathbb{R}\), a common Machine Learning problem is to find a model function \(h:\mathbb{R}^d \to \mathbb{R}\) that can predict the label of a test data point as \[\hat{y} = h(x_\text{test})\]
In linear regression, we look for a linear function \[h_w(x) = w^Tx\] for some \(w\in \mathbb{R}^d\).
The weight \(w\) corresponding to the “best” model is determined from the given data \(\mathcal{D}\).
A suitable performance measure is the sum of squares error: \[f(w) = \dfrac{1}{2} \sum_{i=1}^n \left( w^Tx_i - y_i\right)^2\]
The specific goal of linear regression is to select a \(w\) so that \(f(w)\) is minimized: \[\mathop{\mathrm{arg\,min}}_{w\in \mathbb{R}^d} f(w) = \mathop{\mathrm{arg\,min}}_{w\in \mathbb{R}^d} \ \dfrac{1}{2} \sum_{i=1}^n \left( w^Tx_i - y_i\right)^2\]
The loss function \(f(w)\) is a convex function since it is the sum of convex functions. Hence, the global minimum is obtained by setting \(\nabla_w f(w)=0\)
Define the matrices: \[X = \begin{bmatrix} \text{---} & x_1^T & \text{---} \\ \text{---} & x_2^T & \text{---} \\ & \vdots & \\ \text{---} & x_n^T & \text{---} \end{bmatrix}, \quad y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}\] The loss function can then be written in the matrix form as \[f(w) = \dfrac{1}{2} \Vert Xw - y \Vert ^2 = \dfrac{1}{2} (Xw - y)^T (Xw-y)\] which can further be transformed as \[f(w) = \dfrac{1}{2} w^T (X^TX) w - w^T(X^Ty) + \dfrac{1}{2}y^Ty\]
The gradient of the loss function equated to zero: \[\nabla f(w) = 2((X^TX)w - X^Ty) = 0\]
The optimal weight \(w^*\) is the solution of the normal equation: \[(X^TX)w^* = X^T y\] which gives \[w^* = (X^TX)^\dagger X^Ty\]
For \(x_i \in \mathbb{R}^d\), the “inverse” computation requires \(O(d^3)\) number of operations, which may be computationally expensive for large \(d\).
The gradient descent method can be used as it doesn’t involve inverse calculation: Starting from an initial guess \(w_0\), iteratively compute the weight in the \(k\)-th iteration, using the step size \(\eta_k\), as \[w_{k} = w_{k-1} - \eta_k \nabla f(w_{k-1})\] which, upon plugging the gradient, becomes \[w_{k} = w_{k-1} - \eta_k \left((X^TX)w_{k-1}-X^Ty \right)\]
In case, the number of points \(n\) is also very large, we can use the stochastic gradient descent (SGD) in which, at each iteration, the exact gradient \(\nabla f\) is replaced by a cheap, unbiased estimator of the gradient.
In a particular instantiation of the SGD, called the mini-batch SGD, at each iteration, the exact gradient is replaced by the average gradient of a uniformly sampled subset of the training data.
The SGD has a slower convergence rate compared to the actual gradient descent.
Both the gradient descent and the stochastic gradient descent can be also applied efficiently to non-convex optimization problems as well.
If \(f\) is convex, the global minimum can be obtained by solving \(\nabla f(x) = 0\).
The problem: \[\begin{array}{lrl} & {\displaystyle \min_{x}} & f(x) \\ \text{subject to} && g(x) \le 0 \end{array}\] where \(f, g : \mathbb{R}^d \to \mathbb{R}\).
Define the Lagrangian: \[\mathcal{L}(x, \lambda) = f(x) + \lambda g(x)\] where \(x\in \mathbb{R}^d\) and \(\lambda \in \mathbb{R}\).
Viewed as a function of \(\lambda\), this is a linear function with slope \( g(x) \).
If \( x \) is a feasilble point, then \(g(x)\le 0\), so the graph of \( \mathcal{L} (x, \lambda) \) versus \( \lambda \) is downward slanting line with maximum value \( f(x) \) for \( \lambda \ge 0 \) .
If \( x \) is a not a feasible point, then \(g(x)>0\), so the graph of \( \mathcal{L} (x, \lambda) \) versus \( \lambda \) is an upward slanting line with maximum value \( \to \infty \) for \( \lambda \ge 0 \) .
As a result, in the feasible region: \[f(x) = {\displaystyle\max_{\lambda \ge 0}} \ \mathcal{L}(x, \lambda)\]
Hence, the original problem is equivalent to finding the minimum value of \(\mathcal{L}(x,\lambda )\) for \(\lambda \ge 0\): \[\begin{array}{rcl} \begin{array}{rl} & {\displaystyle \min_{x}}\ f(x) \\[2ex] \text{subject to} & g(x) \le 0 \end{array} & \equiv & {\displaystyle \min_x} \left( {\displaystyle \max_{\lambda \ge 0 }} \ \mathcal{L}(x, \lambda) \right) \end{array}\]
\({\displaystyle \min_x} \left( {\displaystyle \max_{\lambda \ge 0 }} \ \mathcal{L}(x, \lambda) \right)\) is known as the primal form of the optimization problem.
This \(\min \max\) problem is usually hard to solve.
The corresponding dual form of the optimization problem is the \(\max \min\) form: \[{\displaystyle \max_{\lambda \ge 0}} \left( {\displaystyle \min_x} \ \mathcal{L}(x, \lambda) \right)\]
Thus \[\begin{aligned} \boxed{{\displaystyle \min_x} \left( {\displaystyle \max_{\lambda \ge 0 }} \ \mathcal{L}(x, \lambda) \right)} & \longleftrightarrow \boxed{{\displaystyle \max_{\lambda \ge 0}} \left( {\displaystyle \min_x} \ \mathcal{L}(x, \lambda) \right)} \\[2ex] \mathrm{Primal }\quad &\qquad\quad \mathrm{Dual} \end{aligned}\]
The primal optimum \(x^*\) is the point at which the primal form attains the minimum \(f(x^*)\).
Let \(\ell(\lambda) = {\displaystyle \min_x} \ \mathcal{L}(x, \lambda)\). The dual optimum \(\lambda^*\) is the value at which the dual form attains its maximum \(\ell(\lambda^*)\).
In general, the value at the primal optimum may not be equal to the value at the dual optimum.
The principle of weak duality says that the value at the dual optimum is less than or equal to the value at the primal optimum: \[\ell(\lambda^*) \le f(x^*)\]
In case, the objective function \(f\) and the inequality constraints are convex functions, the value at the dual optimum is equal to the value at the primal optimum. This is referred to as strong duality.
Let the objective function \(f\) and the inequality constraint function \(g\) be convex functions. Then strong duality holds with some regularizing conditions. Let the primal optimum be \(x^*\) and the dual optimum be \(\lambda^*\). Then the following conditions hold true:
Stationarity condition: \[\nabla f(x^*) + \lambda^* \nabla g(x^*) = 0\]
Complimentary slackness condition: \[\lambda^*\ g(x^*) = 0\]
Primal feasibility condition: \[g(x^*) \le 0\]
Dual feasibility condition: \[\lambda^* \ge 0\]
These are referred to as the KKT conditions.
The generalized form of the constrained optimization problem: \[\begin{matrix} & {\displaystyle \min_x}\ f(x) & \\[2ex] \text{subject to } & g_i(x) \le 0, & i=1,2, \ldots, n \\[2ex] & h_j(x) = 0, & j=1, 2, \ldots, m \end{matrix}\] where \(f\), \(g_i\), \(h_j : \mathbb{R}^d\to \mathbb{R}\) for \(i=1,2, \ldots, n\), \(j=1,2, \ldots, m\).
The generalized Lagrangian: \[\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^n \lambda_i g_i(x) + \sum_{j=1}^m \mu_j h_j(x)\] where \(x\in \mathbb{R}^d\), \(\lambda = \begin{bmatrix} \lambda_1 & \lambda_2 & \ldots & \lambda_n \end{bmatrix}^T\), \(\mu = \begin{bmatrix} \mu_1 & \mu_2 & \ldots & \mu_m \end{bmatrix}^T\).
The scalars \(\lambda_i\)s are called KKT multipliers while the scalars \(\mu_j\)s are called the Lagrange multipliers.
If \(x^*\) be a local minimizer of \(f\), there exist \(\lambda_i^*\) and \(\mu_j^*\) satisfying the following conditions referred to as the KKT conditions:
Stationarity condition: \[\nabla f(x^*) + \sum_{i=1}^n \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^m \mu_j^* \nabla h_j(x^*) = 0\]
Complimentary slackness condition: \[\lambda_i^*\ g_i(x^*) = 0,\quad i=1, 2, \ldots, n\]
Primal feasibility condition: \[\begin{matrix} g_i(x^*) \le 0 & i = 1, 2, \ldots, n \\[2ex] h_j(x^*) = 0 & j =1, 2, \ldots, m \end{matrix}\]
Dual feasibility condition: \[\lambda_i^* \ge 0, \quad i = 1, 2, \ldots, n\]
If \(f\) and the inequality constraint functions \(g_i\) are convex, then the local minimizer \(x^*\) is also a global minimizer.
An important ML task is to find a linear classifier that has a large geometric margin, i.e., whose decision boundary is well separated from all the training data points.
Such a classifier is known as the Support Vector Machine or SVM for short.
Given a dataset \[\mathcal{D} = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), \ldots, (x_n, y_n)\}\] of data points \(x_i \in \mathbb{R}^d\) and the corresponding labels \(y_i \in \{-1, +1\}\).
The SVM is a linear model that predicts a label for a input \(x\) as \[h_w(x) = \mathrm{sign} ( w^Tx )\] with as large geometric margin (distance between the decision boundary and the nearest data point) as possible.
The problem of finding the optimum weight \(w\) reduces to a quadratic optimization problem: \[\begin{matrix} & {\displaystyle \min_w}\ \dfrac{1}{2} \Vert w \Vert^2 & \\[3ex] \text{subject to } & 1-y_i w^T x_i \le 0, & i = 1, 2, \ldots , n \end{matrix}\]
Since the objective function is quadratic, it is a convex function. In addition, the inequality constraint function is linear and hence also convex. As a result, any local optimum will be global minimum.