Quantum Machine Learning is an exciting new area that was brought forward by the breakthrough quantum algorithm of Harrow, Hassidim, Lloyd for solving systems of linear equations. A classical linear system solver is a powerful tool, since it can be leveraged to solve optimization problems using iterative methods like gradient descent. Here, we provide the first quantum method for performing gradient descent when the gradient is an affine function. Performing t steps of the gradient descent requires time O(t C_S), where C_S is the cost of performing quantumly one step of the gradient descent, which at times can be exponentially smaller than the classical cost. We provide two applications of our method: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least squares problem with much reduced quantum memory requirements. We also provide an improved quantum linear system solver that provides exponential savings for large families of matrices.