Gradient Descent

Takes small steps using first derivative information to arrive at root, or minima of a function. Similar to Newton’s Method except it converges slower if using constant step sizes

${\theta }^{t+1}\leftarrow {\theta }^t-\eta \frac{\partial f}{\partial \theta }$

• The new parameters for our ML model
• $\eta$ is the step size
• $f$ is the error function (we want to minimize error)

Training

Gradient Descent

• GradientDescent()
  • $\theta :=0$
  • For epoch $=1\dots T$
    • ${\theta }^{t+1}\leftarrow {\theta }^t-\eta \frac{\partial f}{\partial \theta }$
  • return $\theta$

$O(nd)$

• Time complexity depends on the number of samples and dimensionality

Stochastic Gradient Descent

• StochasticGradientDescent()
  • $\theta :=0$
  • For epoch $=1\dots T$
    • For $(x,y)\in \mathcal{D}$
      • ${\theta }^{t+1}\leftarrow {\theta }^t-\eta \nabla J_{(x,y)}(\theta )$
        • The gradient is calculated on just one datapoint
  • return $\theta$