Understanding Machine Learning: From Theory to Algorithms

14.1 Gradient Descent 185

the Stochastic Gradient Descent algorithm, along with several useful variants.

We show that SGD enjoys an expected convergence rate similar to the rate

of gradient descent. Finally, we turn to the applicability of SGD to learning

problems.

14.1 Gradient Descent

Before we describe the stochastic gradient descent method, we would like to

describe the standard gradient descent approach for minimizing a differentiable

convex functionf(w).

The gradient of a differentiable functionf:Rd→Ratw, denoted∇f(w),

is the vector of partial derivatives off, namely,∇f(w) =

(

∂f(w)

∂w[1],...,

∂f(w)

∂w[d]

)

.

Gradient descent is an iterative algorithm. We start with an initial value ofw

(say,w(1)= 0 ). Then, at each iteration, we take a step in the direction of the

negative of the gradient at the current point. That is, the update step is

w(t+1)=w(t)−η∇f(w(t)), (14.1)

whereη >0 is a parameter to be discussed later. Intuitively, since the gradi-

ent points in the direction of the greatest rate of increase offaround w(t),

the algorithm makes a small step in the opposite direction, thus decreasing the

value of the function. Eventually, afterTiterations, the algorithm outputs the

averaged vector,w ̄ = T^1

∑T

t=1w(t). The output could also be the last vector,

w(T), or the best performing vector, argmint∈[T]f(w(t)), but taking the average

turns out to be rather useful, especially when we generalize gradient descent to

nondifferentiable functions and to the stochastic case.

Another way to motivate gradient descent is by relying on Taylor approxima-

tion. The gradient offatwyields the first order Taylor approximation off

aroundwbyf(u)≈f(w) +〈u−w,∇f(w)〉. Whenfis convex, this approxi-

mation lower boundsf, that is,

f(u)≥f(w) +〈u−w,∇f(w)〉.

Therefore, forwclose tow(t)we have thatf(w)≈f(w(t))+〈w−w(t),∇f(w(t))〉.

Hence we can minimize the approximation off(w). However, the approximation

might become loose forw, which is far away fromw(t). Therefore, we would like

to minimize jointly the distance betweenwandw(t)and the approximation of

faroundw(t). If the parameterηcontrols the tradeoff between the two terms,

we obtain the update rule

w(t+1)= argmin

w

1

2 ‖w−w

(t)‖ (^2) +η(f(w(t)) +〈w−w(t),∇f(w(t))〉).
Solving the preceding by taking the derivative with respect towand comparing
it to zero yields the same update rule as in Equation (14.1).