Stochastic gradient descent updates parameters using an unbiased or approximate gradient computed from one observation or a mini-batch rather than the complete data set.
Projected stochastic gradient descent takes a stochastic-gradient step and then projects the result onto a closed feasible set. For a convex set it has the form .
A differentiable function with an -Lipschitz gradient obeys . Integrate the gradient along the line segment and bound the deviation from its initial value. The lemma does not require convexity.
For with positive definite and residual , exact line search along usesThe objective error contracts by
For a positive-definite matrix , the conjugate gradient method chooses mutually -conjugate search directions. Starting with and , it usesand with
.
.
The residual of an approximate solution of is . It is the unbalanced right-hand side, while the solution error is . The Conjugate gradient method makes residuals orthogonal to successive Krylov subspaces.
At iteration of the conjugate gradient method,and itself lies in . These Galerkin conditions imply finite termination once the Krylov subspace becomes invariant under .
A symmetric preconditioner transforms intoThe aim is to make the transformed positive-definite matrix have clustered eigenvalues while keeping application of inexpensive.
For a positive-definite matrix , choosing gives , so conjugate gradients terminates in one step. Constructing or applying the exact inverse square root is generally as expensive as solving the original system.
In exact arithmetic, conjugate gradients reaches the exact solution in at most the number of distinct eigenvalues of , and therefore in at most steps for an -dimensional system.
For and ,Thus is a polynomial in applied to the initial residual and lies in the corresponding Krylov subspace.
Articles by others on the same topic
Gradient descent is an optimization algorithm used to minimize a function by iteratively moving towards the steepest descent direction, which is indicated by the negative gradient of the function. It is widely used in machine learning and deep learning to minimize loss functions during the training of models.