Artificial Intelligence Lab 6: Gradient Descent Solution

Description

Let L: R ! R be a function, and let:

1. L = min_w2R L(w) be its minimum value

2. w = arg min_w2R L(w) be the minimiser, i.e., the argument for which the minimum value is attained (note that L = L(w )).

The gradient descent algorithm to find w of a function L(w) is given as follows:

wt+1 = wt	dL(w)	jw=wt ;	(1)
	dw

where

1. > 0 is a step-size parameter

2. ^dL_dw^(w) j_w=wt is the derivative of L(w) with respect to w evaluated at w = w_t.

Let L(w) = ^a₂ w² + bw + c.

Q1) [20 Marks] Plot the function L(w) (in red) L = L(w ) (blue dot) and w (green star), for the following cases:

1. a = 1; b = 0; c = 0.

2. a = 0:1; b = 0; c = 0

3. a = 10; b = 0; c = 0

4. a = 1; b = 0; c = 10

5. a = 1; b = 1; c = 1

(6) a = 0:1; b = 1; c = 1

Calculate L and w with pen and paper. Choose appropriate axis range so that L and w can be displayed in a proper manner.

Q2) [30 Marks] Run the gradient descent algorithm for t = 1; : : : ; T iterations (try various values for

• such as 10; 100; 1000). For each iteration display

(1) The complete function L(w) (for w in an appropriate range used in [Q1] ), and L(w_t) in one plot

(2) w_t w in a different plot.

Run the gradient descent algorithm for various values of such that : (i) the iterates w_t are on the same side of w and converge to w , (ii) the iterates w_t oscillate on both sides of w and converge to w , (iii) the iterates w_t oscillate on both sides of w , but diverge to 1. Please derive these cases with pen and paper first and then proceed to code.

Q3) [25 Marks] Create your own function with multiple local minima, and compare (i) gradient descent versus (ii) gradient descent with momentum.

Q4) [25 Marks] Gradient Descent in 2D: Let w 2 R2. Consider the functions f1(w) =													1				w(1)2	+
													2
	1	w(2)2, f2(w) =	10	w(1)2 +	1	w(2)2, f3(w) =	1	w(1)2 +	10	w(2)2, f4(w) =	1	w(1)2 +		1		w(2)2		+
	2		2		2		2		2		2			2
5w(1) 3w(2) 2. For the functions fi; i = 1; : : : ; 4
a) Show the negative gradient directions and contour plots.

2. Perform gradient descent to find the minima and show the trajectories of the gradient descent algorithm. Use different step-sizes to demonstrate (i) no oscillation, (ii) oscillation in one coordinate (iii) one-sided, oscillatory and divergent modes of convergence behavior.

2