Three pillars on which Machine Learning stands on: Linear Algebra, Optimization, and Probablity & Statistics.
An optimization problem can be either
an unconstrained optimization, or
a constrained optimization problem.
The general form of a constrained optimization problem is to minimize an objective function \(f(x)\) subject to some inequality constraints \(g_i(x)\le 0\) (for \(i=1, 2, \ldots, k\)) and some equality constraints \(h_j(x) = 0\) (for \(j=1, 2, \ldots, \ell\)): \[\begin{array}{lrl} & {\displaystyle \min_{x}} & f(x) \\ \text{subject to} && g_i(x) \le 0 , \quad i = 1,2\ldots, k \\ & \text{and} & h_j(x) = 0 , \quad j = 1,2\ldots, \ell \end{array}\] Here, \(x\) is a \(d\)-dimensional vector whose components are real numbers: \(x\in \mathbb{R}^d\) and \(f\) is a real valued function so that \(f(x)\in \mathbb{R}\).
The general form of an unconstrained optimization is to minimize an objective function where \(x\) is free to vary over the entire \(\mathbb{R}^d\).
Maximizing \(f(x)\) is equivalent to minimizing \(-f(x)\).
A point/vector \(x^*\) is said to be a local minimizer of \(f(x)\) if \(f(x^*)\le f(x)\) for all \(x\) is a neighbourhood of \(x^*\).
A point \(x^*\) is said to be a global minimizer of \(f(x)\) if \(f(x^*)\le f(x)\) for all \(x \in \text{dom }( f)\).
Given a real-valued function \(f\), the notation \(\mathop{\mathrm{arg\,min}}f(x)\) denotes the argument (a point in the domain of \(f\)) that minimizes the function \(f\), assuming such a point is unique.
If for a point \(x^*\) in the domain of \(f\), it is found that
\(\nabla f(x^*)=0\), and
the \( H(x^*) \) is a positive definite matrix, where \(H(x)\) is the Hessian matrix evaluated at \(x\),
then \(x^*\) is a local minimizer of \(f\).
The direction of \(\nabla f(x)\) is the direction of the steepest ascent, while the direction of \(-\nabla f(x)\) is the direction of the steepest descent at some point \(x\) in the domain of \(f\).
Gradient Descent: For unconstained optimization, an important method to find a local minimizer is the gradient descent method (also referred as the steepest descent method) which, starting from an initial point \(x_0\), iteratively moves through a sequence of points \(x_0\), \(x_1\), \(x_2\), \(\ldots\) in such a way that finally a local minimizer is found as the limit of the sequence \(\{x_0, x_1, x_2, \ldots\}\).
The point \(x_k\) obtained after the \(k\)-th iteration is obtained as \[x_k = x_{k-1} -\eta_k \nabla f(x_{k-1})\] where \(\eta_k\) is the step size chosen during the \(k\)-th iteration.
A suitable choice of \(\eta_k\) is important for the method of gradient descent to converge. If \(\eta_k\) is too large, the algorithm might end up oscillating about the local minimizer; if \(\eta_k\) is too small, the process might become too slow.
A suitable choice for the step size during the \(k\)-th step can be found as \[\eta_k = \mathop{\mathrm{arg\,min}}_{\eta \ge 0} f\left(x_{k-1} -\eta \nabla f(x_{k-1})\right)\]
In practice, we can work with a constant step size chosen suitably.