Stochastic Gradient Descent

Summary

This is an optimization method, used in many algorithms such as Support Vector Machines or Conditional Random Fields to efficiently optimize the objective function, especially in the online setting. Stochastic optimizations like this method are known to be faster when trained with large, redundant data sets.

Gradient Descent

Given a function to be minimized $F(\mathbf {x} )$ and a point $\mathbf {x} =\mathbf {a}$, let $\mathbf {b} =\gamma \nabla F(\mathbf {a} )$ then we can say

$F(\mathbf {b} )\leq F(\mathbf {a} )$

for some small enough $\gamma$. Using this inequality, we can get a (local) minimum of the objective function using the following steps:

• Initialize $\mathbf {x}$
• Repeat the step above until the objective function converges to a local minimum
  • $\mathbf {x} _{new}=\mathbf {x} -\nabla F(\mathbf {a} )$
  • $\mathbf {x} =\mathbf {x} _{new}$

Stochastic Gradient Descent

One of the problems of the gradient descent method above is that calculating the gradient could be an expensive computation depending on the objective function or the size of the data set. Suppose your objective function is ${\mathcal {L}}({\mathcal {D}},\mathbf {\theta } )$. If the objective function can be decomposed as the following,

${\mathcal {L}}(\mathbf {\theta } ;{\mathcal {D}})=\sum _{i=1}^{\vert {\mathcal {D}}\vert }{{\mathcal {L}}(\mathbf {\theta } ;{\mathcal {D}}_{i})}$

where ${\mathcal {D}}_{i}$ indicates the $i\quad$-th example(sometimes ${\mathcal {D}}_{i}$ is a batch instead of one example), we can make the process stochastic. To make each step computationally efficient, a subset of the summand function is sampled. The procedure can be described as the following pseudocode:

• Initialize $\mathbf {\theta }$
• Repeat until convergence
  • Sample $n\quad$ examples
  • For each example sampled ${\mathcal {D}}_{i}$
    • $\mathbf {\theta } _{new}=\mathbf {\theta } -\alpha \nabla {\mathcal {L}}(\mathbf {\theta } ;{\mathcal {D}}_{i})$
    • $\mathbf {\theta } =\mathbf {\theta } _{new}$

where $\alpha \quad$ is the learning rate. Note that this method is no different from the plain gradient descent method when the batch size becomes the number of examples. For computational efficiency, small batch size around 5~20 turn out to be most efficient.

Pros

When this method is used for very large data sets that has redundant information among examples, it is much faster than the plain gradient descent because it requires less computation each iteration. Also, it is known to be better with noisy data since it samples example to compute gradient.

Cons

The convergence rate is slower than second-order gradient methods. However the speedup coming from computationally efficient iterations are usually greater and the method can converge faster if learning rate is adjusted as the procedure goes on. Also it tends to keep bouncing around the minimum unless the learning rate is reduced in the later iterations.

Related Papers

• Accelerated Training of Conditional Random Fields with Stochastic Gradient Methods, Vishwanathan et al, ICML 2006
• Practical very large CRFs