Implement the function grid$\_$search, which takes in a training set xTr$,$ yTr$,$ a validation set xVal, yVal and a list of tree depth candidates depths. Your job here is to fit a regression tree for each depth candidate on the training set xTr$,$ yTr$,$ evaluate the fitted tree on the validation set xVal, yVal, and then pick the candidate that yields the lowest loss for the validation set.

Implementation Notes:

Use the square$\_$loss function to calculate the training and validation loss for corresponding predictions against true labels yTr and yVal respectively.

In the event of a tie, return the depth that appears first in depths list $($np$.$argmin on the list of validation losses will give you the first index in case of a tie$).$

def grid$\_$search$($xTr$,$ yTr$,$ xVal, yVal, depths$)$:

$"""$

Calculates the training and validation loss for trees trained on xTr and validated on yTr with a number of depths.

Input:

xTr: nxd training data matrix

yTr: n$-$dimensional vector of training labels

xVal: mxd validation data matrix

yVal: m$-$dimensional vector of validation labels

depths: a list of len k of depths

Output:

best$\_$depth, training$\_$losses, validation$\_$losses

best$\_$depth: the depth that yields that lowest validation loss

training$\_$losses: a list of len k$.$ the i$-$th entry corresponds to the the training loss of the tree of depth$=$depths$[$i$]$

validation$\_$losses: a list of len k$.$ the i$-$th entry corresponds to the the validation loss of the tree of depth$=$depths$[$i$]$

$"""$

training$\_$losses $=[]$

validation$\_$losses $=[]$

best$\_$depth $=$ None

# YOUR CODE HERE

raise NotImplementedError$()$

return best$\_$depth, training$\_$losses, validation$\_$losses

We need to replace # YOUR CODE HERE