effective in the case of large-scale machine learning problems. Iterative method In stochastic (or "on-line") gradient descent, the true gradient of is approximated by a gradient at a single sample: As the algorithm sweeps through the training set, it performs the above update for each training sample. Several passes can be made over the training set until the algorithm converges. If this is done, the data can be shuffled for each pass to prevent cycles. Typical implementations may use an adaptive learning rate so that the algorithm converges. In pseudocode, stochastic gradient descent can be presented as : Choose an initial vector of parameters and learning rate . Repeat until an approximate minimum is obtained: Randomly shuffle samples in the training set. For , do: A compromise between computing the true gradient and the gradient at a single sample is to compute the gradient against more than one training sample (called a "mini-batch") at each step. This can perform significantly better than "true" stochastic gradient descent described, because the code can make use of vectorization libraries rather than computing each step separately as was first shown in where it was called "the bunch-mode back-propagation algorithm". It may also result in smoother convergence, as the gradient computed at each step is averaged over more training sample. The convergence of stochastic gradient descent has been analyzed using the theories of convex minimization and of stochastic approximation. Briefly, when the learning rates decrease with an appropriate rate, and subject to relatively mild assumptions, stochastic gradient descent converges almost surely to a global minimum when the objective function is convex or pseudoconvex, and otherwise converges almost surely to a local minimum. This is in fact a consequence of the Robbins–Siegmund theorem. Example Let's suppose we want to fit a straight line to a training set with observations and corresponding estimated responses using least squares. The objective function to be minimized is: The last line in the above pseudocode for this specific problem will become: Note that in each iteration (also called update), the gradient is only evaluated at a single point instead of at the set of all samples. The key difference compared to standard (Batch) Gradient Descent is that only one piece of data from the dataset is used to calculate the step, and the piece of data is picked randomly at each step. Notable applications Stochastic gradient descent is a popular algorithm