# HW1  Try out gradient descent

## Due Wed Oct 6th, 2021 at 11:59PM

You should submit this jupyter notebook with your solutions. The solutions should include the code and also the output of all the cells.

Note that for the problmes that require a cost function as input you should always use the most recent cost function that you have implemented (unless specified otherwise).

1) [5 points] Calculate the derivative of following cost function and write it down:

$g(w) = \frac{1}{50}\left(w^4 + w^2 + 10w - 50 \right)$

$\frac{\partial}{\partial w}g(w) = \frac{1}{50}(4w^3+2w+10) $

2) [25 points] Implement the gradient descent function as discussed in class using the gradient derived in the last problem. The function should return the cost history for each step. Use the code template below:



```python
#gradient descent function
#inputs: alpha (learning rate parameter), max_its (maximum number of iterations), w0 (initialization)
def gradient_descent(alpha,max_its,w0):
    gw = 1/50*(w0**4+w0**2+10*w0-50)
    dw = 1/50*(4*w0**3+2*w0+10)
    cost_history = [gw]
    for i in range(max_its):
        w0 = w0 - alpha*dw
        gw = 1/50*(w0**4+w0**2+10*w0-50)
        dw = 1/50*(4*w0**3+2*w0+10)
        cost_history.append(gw)
    ##Your code here
    return cost_history
```

3) [10 points] Run the gradient_descent function you implemented three times, with the following parameters. Generate a single plot showing the cost as a function of step number for all three runs (combine all three runs into a single plot). If you are not familiar with plotting in python, here is the docs for matplotlib:(https://matplotlib.org/3.2.1/api/_as_gen/matplotlib.pyplot.plot.html#matplotlib.pyplot.plot). 


$w^0$ = 2.0
max_its = 1000

# first run
alpha = 1
# second run
alpha = 0.1
# third run
alpha = 0.01



```python
import matplotlib.pyplot as plt
%matplotlib inline 
# To keep your plots embedded

first_run = gradient_descent(alpha = 1, max_its = 1000, w0 = 2.0 )
second_run = gradient_descent(alpha = 0.1, max_its = 1000, w0 = 2.0 )
third_run = gradient_descent(alpha = 0.01, max_its = 1000, w0 = 2.0 )
plt.plot(first_run,'g-',second_run,"b-",third_run,"r-")# red for alpha0.01, blue for 0.1, and green for 1

##Your code here
```

For the next few problems we will be comparing fixed and diminishing learning rates

Take the following cost function:
\begin{equation}
g(w) = \left \vert w \right \vert
\end{equation}

4) [5 points] Is this function convex? If no, why not? If yes, where is its global minimum?

 Yes, this function is convex. The global minimum is 0.

5) [5 points] What is the derivative of the cost function? 

This cost function is not differentiable at the point of zero, so the derivative of the cose function would be following:
$$\frac{\partial}{\partial w}g(w) = \begin{cases}
1 & w>0 \\
-1 & w<0 \\
\end{cases}
$$

6) [20 points] Rewrite the gradient descent function from question 2 such that it takes the cost funciton g as input and uses the autograd library to calculate the gradient. The function should return the weight and cost history for each step. Use the code template below.

autograd is a python package for automatic calculation of the gradient. Here is a tutorial on it: (http://www.cs.toronto.edu/~rgrosse/courses/csc321_2017/tutorials/tut4.pdf

Note that in Python you can pass functions around like any other variables. That is why you can pass the cost function g to the gradient_descent function. 

You should be able to install it by running "pip install autograd" in a cell in your Jupyter notebook.


```python
from autograd import grad 

#gradient descent function
#inputs: g (cost function), alpha (learning rate parameter), max_its (maximum number of iterations), w (initialization)
def gradient_descent(g,alpha,max_its,w0):
    gradient = grad(g)   ## This is how you use the autograd library to find the gradient of a function  
    ##Your code here
    weight_history = [w0]
    cost_history = [g(w0)]
    for i in range(max_its):
        w0 -= alpha*gradient(w0)
        cost_history.append(g(w0))
        weight_history.append(w0)
    return weight_history,cost_history
```

7) [10 points] Make a run of max_its=20 steps of gradient descent with initialization at the point $w^0 = 1.75$, and a fixed learning rate of $\alpha = 0.5$. Using the cost and weight history, plot the cost as a function of the weight for each step (cost on y-axis, weight on x-axis). Recall that the terms weight and parameter used interchangeably and both refer to w.


```python
import matplotlib.pyplot as plt
%matplotlib inline 
def g(x):
    return abs(x)
result07 = gradient_descent(g, alpha = 0.5,max_its=20, w0=1.75)
plt.plot(result07[0],result07[1])
```

8) [15 points] Make a run of max_its=20 steps of gradient descent with initialization at the point $w^0 = 1.75$, using the diminishing rule $\alpha = \frac{1}{k}$ (for this you have to modify the gradient_descent function slightly. Use the code template below. Using the cost and wiehgt history, plot the cost as a function of the weight for each step (cost on y-axis, weight on x-axis)


```python
#from autograd import grad 

#gradient descent function
#inputs: g (cost function), alpha (learning rate parameter), max_its (maximum number of iterations), w (initialization)
def gradient_descent(g,alpha,max_its,w0):
    gradient = grad(g)   ## This is how you use the autograd library to find the gradient of a function 
    ##Your code here
    weight_history = [w0]
    cost_history = [g(w0)]
    for k in range(max_its):
        if k > 1:
            alpha = 1/k
        w0 -= alpha*gradient(w0)
        cost_history.append(g(w0))
        weight_history.append(w0)
    return weight_history,cost_history
result08 = gradient_descent(g, alpha = 0.5,max_its=20, w0=1.75)
plt.plot(result08[0],result08[1])
```

9) [10 points]  Generate a single plot showing the cost as a function of step number for both runs (combine all  runs into a single plot). Which approach works better? Why ?


```python
plt.plot(result07[1],'b-',result08[1],"g-")#blue for the first one
```

The diminishing alpha approach works better, because it ultimately descend to the value that near to the minimun of the cost function, while the first approach didn't.

We will now look at the oscilating behavior of gradient descent. 

Take the following cost function:
$g(w) = w_0^2 + w_1^2 + 2\sin(1.5 (w_0 + w_1)) +2$

Note that this cost function has two parameters.


```python
import autograd.numpy as np
def g(w):
    w0 = w[0]
    w1 = w[1]
    result = w0**2 + w1**2+ 2*np.sin(1.5*(w0+w1))+2
    return result
    
```

10) [5 points] Make sure your gradient descent function from problem 6 can handle cost functions with more than one parameter. You may need to rewrite it if you were not careful. Use the code template below (if your function from problem 6 is good, you can just copy and paste it here)


```python
from autograd import grad 


#gradient descent function
#inputs: g (cost function), alpha (learning rate parameter), max_its (maximum number of iterations), w (initialization)
def gradient_descent(g,alpha,max_its,w0):
    gradient = grad(g)   ## This is how you use the autograd library to find the gradient of a function  
    ##Your code here
    weight_history = [w0]
    cost_history = [g(w0)]
    for i in range(max_its):
        for j in range(0,len(w0)):
            w0[j] -=  alpha * gradient(w0)[j]
        cost_history.append(g(w0))
        weight_history.append(w0)
    return weight_history,cost_history
```

11) [10 points] Run the gradient_descent function with the cost function above three times with the following parameters. Generate a single plot showing the cost as a function of step number for all three runs (combine all three runs into a single plot). Use the code template below. Which alpha leads to an oscillating behavior?

$w^0$ = [3.0,3.0]
max_its = 10

# first run
alpha = 0.01
# second run
alpha = 0.1
# third run
alpha = 1




```python
import autograd.numpy as np
import matplotlib.pyplot as plt
%matplotlib inline 

w = [3.0,3.0]
gd = grad(g)
gd(w)
#q11first = gradient_descent(g,alpha = 0.01 ,max_its = 10,w0 = w)
#q11second = gradient_descent(g,alpha = 0.1 ,max_its = 10,w0 = w)
#q11third = gradient_descent(g,alpha = 1 ,max_its = 10,w0 = w)
#plt.plot(q11first[1],'b-',q11second[1],"r-",q11third[1],"g-")#green(third one lead to oscillating behavior)
#Your code here
```




    [array(3.26660921), array(3.26660921)]



The third alpha($\alpha = 1$) leads to oscillating behavor.

### 12) [15 points] This problem is about learning to tune fixed step length for gradient descent. Here, you are given a cost function:
$g(w) = 2w_0^2 + w_1^2 +4w_2^2$ 

Assume your $w^0$= [5,5,5] and your max_iter = 100

Use your latest gradient descent function with a fixed learning rate. Play around with at least 5 different values of alpha (using your intuition). Generate a single plot of the cost as a function of the number of iterations. Which value of alpha seems to converge the fastest?

Not that your grade will not depend on how well you do, as long as you try at least 5 different values for alpha and plot them.


```python
def g(w):
    #w0 = w[0]
    #w1 = w[1]
    #w2 = w[2]
    square = np.square(w)
    result = 2 * square[0] + square[1] + 4 * square[2]
    return result 
```


```python
%matplotlib inline 
w =[5.0,5.0,5.0]

q12first = gradient_descent(g,alpha = 0.01 ,max_its = 100,w0 = w)
q12second = gradient_descent(g,alpha = 0.1 ,max_its = 100,w0 = w)
q12third = gradient_descent(g,alpha = 0.15 ,max_its = 100,w0 = w)
q12forth = gradient_descent(g,alpha = 0.20 ,max_its = 100,w0 = w)
q12fifth = gradient_descent(g,alpha = 0.9 ,max_its = 100,w0 = w)
plt.plot(q12first[1],'b:',q12second[1],'r-',q12third[1],'y-',q12forth[1],'g-',q12fifth[1],'k-')
#Since the larger learing rate converge so fast, it almost like a straight line and covers all other lines of the plot

```


```python
plt.plot(q12fifth[1],'k-')
```

From result above, the 0.9 of alpha seems have the fastest speed to converge.

6e1e62e94f3f0ae30e49b50515107d16acf3732c
ipynb
Jupyter Notebook
HW1_cosc74_FA2021.ipynb
chenhz1223/ML-dartmouth-cs274
e096547b5c084b924522d168435ff979357f2c92
MIT
HW1_cosc74_FA2021.ipynb
chenhz1223/ML-dartmouth-cs274
e096547b5c084b924522d168435ff979357f2c92
MIT
HW1_cosc74_FA2021.ipynb
chenhz1223/ML-dartmouth-cs274
e096547b5c084b924522d168435ff979357f2c92
MIT
Qwen/Qwen-72B
1. YES
2. YES