Gradient Descent

Definition

An iterative optimization algorithm for finding a local minimum of a differentiable function

${\mathbf{x}}_{n+1}=x_n-\gamma \nabla f(x_n)$ where $\gamma$ is a learning rate

Examples

Solution of a linear system

Solve $A\mathbf{x}=\mathbf{b}$ with an MSE loss

The cost function is $f(\mathbf{x})=(A\mathbf{x}-\mathbf{b}{)}^{⊺}(A\mathbf{x}-\mathbf{b})$ and its gradient is $\nabla f(x)=-2(\mathbf{b}-A\mathbf{x}{)}^{⊺}$

Then, solution is ${\mathbf{x}}_{n+1}={\mathbf{x}}_n+2\gamma A^{⊺}(\mathbf{b}-A{\mathbf{x}}_n)$