<a href="https://colab.research.google.com/github/balamurugan-palaniappan-CEP/AIML_CEP_2021/blob/main/Optimization_SVM_TA_Session_2021Dec18.ipynb" target="_parent"></a>


```python
import numpy as np
#for the following statement to compile successfully, you need the scikit-learn package. 

from sklearn.datasets import load_iris #for loading iris dataset
from sklearn.svm import LinearSVC #linear svm from scikit learn 

np.random.seed(1000) #for reproducibility
iris = load_iris()
#check the shape of iris data features
print('iris data shape:', iris.data.shape)
A = iris.data
#check the shape of iris target labels
print('iris target shape:', iris.target.shape)
#We can print first 5 samples of iris data and check 
print('Features of first five samples of iris data:')
print(A[0:5])
```

    iris data shape: (150, 4)
    iris target shape: (150,)
    Features of first five samples of iris data:
    [[5.1 3.5 1.4 0.2]
     [4.9 3.  1.4 0.2]
     [4.7 3.2 1.3 0.2]
     [4.6 3.1 1.5 0.2]
     [5.  3.6 1.4 0.2]]



```python
#How many labels does iris data have? 
#print the unique classes
print('unique classes: ',np.unique(iris.target))
n = iris.data.shape[0] #Number of data points or samples 
d = iris.data.shape[1] #Dimension of data points
```

    unique classes:  [0 1 2]



```python
#In the following code, we create a nx1 vector of target labels 
y = 1.0*np.ones([A.shape[0],1])
for i in range(iris.target.shape[0]):
    if iris.target[i] == 1:
        y[i] = 1
    else:
        y[i] = -1
```


```python
#Create an index array 
indexarr = np.arange(n) #index array
np.random.shuffle(indexarr) #shuffle the indices 
#print('shuffled indices of samples:')
#print(indexarr)
```


```python
#Use the samples corresponding to first 80% of indexarr for training 
num_train = int(0.8*n)
#Use the remaining 20% samples for testing 
num_test = n-num_train
print('num_train: ',num_train, 'num_test: ', num_test)
```

    num_train:  120 num_test:  30



```python
#Use the first 80% of indexarr to create the train data features and train labels 
train_features = A[indexarr[0:num_train]]
train_label = y[indexarr[0:num_train]]
print('shape of train data features:')
print(train_features.shape)
print('shape of train data labels')
print(train_label.shape)
```

    shape of train data features:
    (120, 4)
    shape of train data labels
    (120, 1)



```python
#Use remaining 20% of indexarr to create the test data and test labels  
test_features = A[indexarr[num_train:n]]
test_label = y[indexarr[num_train:n]]
print('shape of test data features:')
print(test_features.shape)
print('shape of test data labels')
print(test_label.shape)
```

    shape of test data features:
    (30, 4)
    shape of test data labels
    (30, 1)


#SVM Optimization Problem

Given a training data set $D=\{(\mathbf{x}^i,y^i)\}_{i=1}^{n}$ of $n$ training samples where ${\mathbf{x}}^i \in \mathcal{X} \subset {\mathbb{R}}^d$ and $y^i \in \mathcal{Y}=\{+1,-1\}$, we solve the following optimization problem: 

$
\begin{align}
\min_{\mathbf{w}, b, \xi_i} & \ \frac{1}{2} \|\mathbf{w}\|_2^2 + C \sum_{i=1}^{n} \xi_i^2 \\ 
\text{s.t.}  & \ y^i (\mathbf{w}^\top {\mathbf{x}}^i + b) \geq 1 - \xi_i, \ \forall i \in \{1,2,\ldots,n\} \\   
& \ \xi_i \geq 0 \ \forall i \in \{1,2,\ldots,n\}. 
\end{align}
$

This problem can be equivalently written as:

$
\begin{align}
\min_{\mathbf{w}, b} & \ \frac{1}{2} \|\mathbf{w}\|_2^2 + C \sum_{i=1}^{n} (\max\{0,  1 - y^i (\mathbf{w}^\top {\mathbf{x}}^i + b)\})^2.\\ 
\end{align}
$



For simplicity we shall consider only the first two dimensions of the IRIS data and will not consider the bias term. Without the bias term the optimization problem would look as follows:

$
\begin{align}
\min_{\mathbf{w}} F(\mathbf{w}) = & \ \frac{1}{2} \|\mathbf{w}\|_2^2 + C \sum_{i=1}^{n} (\max\{0,  1 - y^i (\mathbf{w}^\top {\mathbf{x}}^i)\})^2.\\ 
\end{align}
$

The gradient with respect to $\mathbf{w}$ is given as: 

$
\begin{align}
\nabla_{\mathbf{w}} F(\mathbf{w}) = \mathbf{w} + C \sum_{i=1}^{n} 2(\max\{0,  1 - y^i (\mathbf{w}^\top {\mathbf{x}}^i)\})(-y^i {\mathbf{x}}^i)  
\end{align}
$


```python
train_features_new = train_features[:,0:2]
print(train_features_new.shape)
test_features_new = test_features[:,0:2]
print(test_features_new.shape)
```

    (120, 2)
    (30, 2)



```python
import math 

def obj_fn_SVM(X,y,C,w,b=0):
  num_train = X.shape[0]
  w_norm = np.linalg.norm(w)
  obj_fn_val = 0.5*w_norm**2
  loss = 0
  for i in range(num_train):
    loss_i = max(1-y[i]*(np.dot(w,X[i])+b),0)
    loss += loss_i**2
  obj_fn_val += C*loss
  return obj_fn_val

def backtracking_line_search_gd(X, y, C, w, grad_w, b=0, grad_b = 0, is_bias_used = False):
    max_backtrack = 100
    alpha = 1.
    rho = 0.5
    obj_fn_start = obj_fn_SVM(X,y,C,w,b) #compute objective function value at the starting point
    temp_w = np.subtract(w, alpha*grad_w) 
    if is_bias_used:
      temp_b = b -  alpha*grad_b 
    else: 
      temp_b = 0
    obj_fn_temp_w = obj_fn_SVM(X,y,C,temp_w,temp_b)
    num_backtrack = 0
    while (obj_fn_temp_w >= obj_fn_start):
      num_backtrack += 1
      alpha = rho*alpha  
      temp_w = np.subtract(w, alpha*grad_w) 
      if is_bias_used:
        temp_b = b -  alpha*grad_b 
      obj_fn_temp_w = obj_fn_SVM(X,y,C,temp_w,temp_b)
      #print ('withing backtrackls: old obj fn:', obj_fn_start, 'new obj fn:', obj_fn_temp_w)    
      if (num_backtrack > max_backtrack):
        break
    #print ('alpha:',alpha, 'old obj fn:', obj_fn_start, 'new obj fn:', obj_fn_temp_w)
    return alpha


def grad_descent_SVM(X, y, C=1, is_bias_used = False, tol=1e-3, verbose = True):
  num_train = X.shape[0]
  dim = X.shape[1]
  #Initialize weights 
  w = np.zeros(dim)
  b = 0

  grad_tol = tol
  step_length = 0.

  gd_iter = 0
  max_gd_iter = 100000 
  
  obj_fn_val_list = [] 
  
  while 1!=0:
    gd_iter += 1
    grad_w = np.copy(w)
    grad_b = 0
    for i in range(num_train):
      #compute gradient component for each example
      loss_i = max(1-y[i]*(np.dot(w,X[i])+b),0)
      grad_w_i = -2*C*loss_i*y[i]*X[i]
      grad_w = np.add(grad_w,grad_w_i)
      if is_bias_used:
        grad_b += -2*C*loss_i*y[i]

    
    grad_norm = np.sqrt(np.dot(grad_w,grad_w) + grad_b**2)
    obj_fn_val = obj_fn_SVM(X,y,C,w,b)
    obj_fn_val_list.append(obj_fn_val)
    if (verbose == True or  gd_iter%100 == 0):
      print('GD iter:', gd_iter, 'step length:', step_length, 'obj fn val:', obj_fn_val, 'grad norm:', grad_norm)
    
    if grad_norm < grad_tol:
      print('Gradient norm:', grad_norm, ' less than tol:', grad_tol, ' Exiting...!')
      break

    #compute step length
    step_length = backtracking_line_search_gd(X, y, C, w, grad_w, b, grad_b, is_bias_used)
    #update weights 
    w = np.subtract(w, np.multiply(step_length, grad_w))
    if is_bias_used:
      b = b - step_length*grad_b

    if gd_iter > max_gd_iter:
      print('MAX ITERATIONS ',max_gd_iter, ' REACHED.. EXITING..!')
      break
  return obj_fn_val_list  


def mini_batch_SGD_SVM(X, y, C=1, batch_size=32,  is_bias_used = False, max_epochs = 70, verbose=True):
  num_train = X.shape[0]
  dim = X.shape[1]
  #Initialize weights 
  w = np.zeros(dim)
  b = 0

  
  step_length = 0.

  msgd_epoch = 0
  max_msgd_epochs = max_epochs 
  msgd_batches = 0

  obj_fn_val_list = [] 
  idx_arr = np.array(range(num_train))
  num_batches = math.ceil(num_train/batch_size)

  while msgd_epoch < max_msgd_epochs:
    msgd_epoch += 1

    #shuffle
    np.random.shuffle(idx_arr)
        
    for batch in range(num_batches):
      msgd_batches += 1
      grad_w = np.copy(w)
      grad_b = 0
      #extract batch 
      start_idx = batch*batch_size
      end_idx = min(num_train,(batch+1)*batch_size)
      for i in np.arange(start_idx, end_idx):
        #compute gradient component for each example
        loss_i = max(1-y[idx_arr[i]]*(np.dot(w,X[idx_arr[i]])+b),0)
        grad_w_i = -2*C*loss_i*y[idx_arr[i]]*X[idx_arr[i]]
        grad_w = np.add(grad_w,grad_w_i)
        if is_bias_used:
          grad_b += -2*C*loss_i*y[idx_arr[i]]
      obj_fn_val = obj_fn_SVM(X,y,C,w,b)
      obj_fn_val_list.append(obj_fn_val)
      if (verbose == True or  msgd_epoch%10 == 0):
        print('Epoch:', msgd_epoch, 'batch:', batch, 'step length:', step_length, 'obj fn val:', obj_fn_val)

      #update weights 
      step_length = 0.01/(msgd_epoch+1)
      
      w = np.subtract(w, np.multiply(step_length, grad_w))
      if is_bias_used:
        b = b - step_length*grad_b
  
  return obj_fn_val_list  

```


```python
C = 0.1
obj_fn_vals = grad_descent_SVM(train_features_new, train_label,C)
```

    GD iter: 1 step length: 0.0 obj fn val: [12.] grad norm: 60.30928618380425
    GD iter: 2 step length: 0.0009765625 obj fn val: [10.28723879] grad norm: 4.793016599057074
    GD iter: 3 step length: 0.00390625 obj fn val: [10.24690255] grad norm: 8.678703062254225
    GD iter: 4 step length: 0.001953125 obj fn val: [10.22077271] grad norm: 9.209276639950504
    GD iter: 5 step length: 0.001953125 obj fn val: [10.19645263] grad norm: 9.798359222468179
    GD iter: 6 step length: 0.001953125 obj fn val: [10.17404237] grad norm: 10.449654543727437
    GD iter: 7 step length: 0.001953125 obj fn val: [10.15366565] grad norm: 11.167153244852216
    GD iter: 8 step length: 0.001953125 obj fn val: [10.13547356] grad norm: 11.955178489874646
    GD iter: 9 step length: 0.001953125 obj fn val: [10.11964903] grad norm: 12.818430792295292
    GD iter: 10 step length: 0.001953125 obj fn val: [10.10641193] grad norm: 13.762032095457952
    GD iter: 11 step length: 0.001953125 obj fn val: [10.09602513] grad norm: 14.791569444538098
    GD iter: 12 step length: 0.001953125 obj fn val: [10.08880155] grad norm: 15.913138773032784
    GD iter: 13 step length: 0.001953125 obj fn val: [10.08511238] grad norm: 17.133389423992696
    GD iter: 14 step length: 0.0009765625 obj fn val: [9.94184704] grad norm: 3.4139507803706906
    GD iter: 15 step length: 0.03125 obj fn val: [9.86511019] grad norm: 22.11514887811656
    GD iter: 16 step length: 0.0009765625 obj fn val: [9.63293878] grad norm: 2.5922710211328277
    GD iter: 17 step length: 0.0078125 obj fn val: [9.60775932] grad norm: 6.905975270398414
    GD iter: 18 step length: 0.001953125 obj fn val: [9.60112135] grad norm: 7.395464858694616
    GD iter: 19 step length: 0.001953125 obj fn val: [9.59538082] grad norm: 7.931457999479524
    GD iter: 20 step length: 0.001953125 obj fn val: [9.59062251] grad norm: 8.517133083980134
    GD iter: 21 step length: 0.001953125 obj fn val: [9.5869477] grad norm: 9.15595745209314
    GD iter: 22 step length: 0.001953125 obj fn val: [9.58447684] grad norm: 9.85171419660381
    GD iter: 23 step length: 0.001953125 obj fn val: [9.58335278] grad norm: 10.608529487394946
    GD iter: 24 step length: 0.0009765625 obj fn val: [9.52849908] grad norm: 2.081015893994244
    GD iter: 25 step length: 0.03125 obj fn val: [9.50292742] grad norm: 13.69915038584884
    GD iter: 26 step length: 0.0009765625 obj fn val: [9.41387847] grad norm: 1.582281443948314
    GD iter: 27 step length: 0.0078125 obj fn val: [9.40478643] grad norm: 4.271021272552616
    GD iter: 28 step length: 0.001953125 obj fn val: [9.40236648] grad norm: 4.575048079871247
    GD iter: 29 step length: 0.001953125 obj fn val: [9.40028681] grad norm: 4.907823517524709
    GD iter: 30 step length: 0.001953125 obj fn val: [9.3985801] grad norm: 5.271319971838432
    GD iter: 31 step length: 0.001953125 obj fn val: [9.39728535] grad norm: 5.667689294505007
    GD iter: 32 step length: 0.001953125 obj fn val: [9.39644895] grad norm: 6.099279218541716
    GD iter: 33 step length: 0.001953125 obj fn val: [9.39612584] grad norm: 6.568650135676044
    GD iter: 34 step length: 0.0009765625 obj fn val: [9.37512168] grad norm: 1.2685377443381904
    GD iter: 35 step length: 0.03125 obj fn val: [9.36674716] grad norm: 8.485947623295207
    GD iter: 36 step length: 0.0009765625 obj fn val: [9.33259165] grad norm: 0.9658591450402739
    GD iter: 37 step length: 0.0078125 obj fn val: [9.32931433] grad norm: 2.6415691613404744
    GD iter: 38 step length: 0.001953125 obj fn val: [9.32843295] grad norm: 2.830388482213351
    GD iter: 39 step length: 0.001953125 obj fn val: [9.32768061] grad norm: 3.036981067836213
    GD iter: 40 step length: 0.001953125 obj fn val: [9.32706993] grad norm: 3.2625709325223293
    GD iter: 41 step length: 0.001953125 obj fn val: [9.32661592] grad norm: 3.5084935289126133
    GD iter: 42 step length: 0.001953125 obj fn val: [9.32633644] grad norm: 3.7762058064102377
    GD iter: 43 step length: 0.001953125 obj fn val: [9.32625263] grad norm: 4.067296517281051
    GD iter: 44 step length: 0.0009765625 obj fn val: [9.31820925] grad norm: 0.7732885095028605
    GD iter: 45 step length: 0.03125 obj fn val: [9.31552947] grad norm: 5.256660293918836
    GD iter: 46 step length: 0.0009765625 obj fn val: [9.30242848] grad norm: 0.5896187436045645
    GD iter: 47 step length: 0.0078125 obj fn val: [9.30124938] grad norm: 1.6338611550644402
    GD iter: 48 step length: 0.001953125 obj fn val: [9.3009287] grad norm: 1.7511206792614047
    GD iter: 49 step length: 0.001953125 obj fn val: [9.30065696] grad norm: 1.8793686502152998
    GD iter: 50 step length: 0.001953125 obj fn val: [9.30043904] grad norm: 2.0193646747717193
    GD iter: 51 step length: 0.001953125 obj fn val: [9.30028072] grad norm: 2.1719375411016664
    GD iter: 52 step length: 0.001953125 obj fn val: [9.30018887] grad norm: 2.337991384594346
    GD iter: 53 step length: 0.001953125 obj fn val: [9.30017162] grad norm: 2.518512021512211
    GD iter: 54 step length: 0.0009765625 obj fn val: [9.29709124] grad norm: 0.47140068235064486
    GD iter: 55 step length: 0.03125 obj fn val: [9.29626105] grad norm: 3.2562837040924473
    GD iter: 56 step length: 0.0009765625 obj fn val: [9.29123578] grad norm: 0.35996219602230306
    GD iter: 57 step length: 0.0078125 obj fn val: [9.29081247] grad norm: 1.0106263244262992
    GD iter: 58 step length: 0.001953125 obj fn val: [9.29069463] grad norm: 1.078842433993645
    GD iter: 59 step length: 0.001953125 obj fn val: [9.29058629] grad norm: 1.1528430798339597
    GD iter: 60 step length: 0.001953125 obj fn val: [9.290503] grad norm: 1.2306372091306652
    GD iter: 61 step length: 0.001953125 obj fn val: [9.29042664] grad norm: 1.3145557809986637
    GD iter: 62 step length: 0.001953125 obj fn val: [9.29038276] grad norm: 1.4030123910751224
    GD iter: 63 step length: 0.001953125 obj fn val: [9.29034421] grad norm: 1.4981425244912907
    GD iter: 64 step length: 0.0009765625 obj fn val: [9.28925221] grad norm: 0.2867201889988049
    GD iter: 65 step length: 0.03125 obj fn val: [9.2887474] grad norm: 1.8754074983562372
    GD iter: 66 step length: 0.0009765625 obj fn val: [9.28706097] grad norm: 0.21518881805353965
    GD iter: 67 step length: 0.015625 obj fn val: [9.2868029] grad norm: 0.905461074950273
    GD iter: 68 step length: 0.001953125 obj fn val: [9.28678669] grad norm: 0.9584067632715114
    GD iter: 69 step length: 0.001953125 obj fn val: [9.28677847] grad norm: 1.0148367855283598
    GD iter: 70 step length: 0.0009765625 obj fn val: [9.28627571] grad norm: 0.17653058196786
    GD iter: 71 step length: 0.03125 obj fn val: [9.28590859] grad norm: 0.9908943963240177
    GD iter: 72 step length: 0.0009765625 obj fn val: [9.28543552] grad norm: 0.1319436302305005
    GD iter: 73 step length: 0.03125 obj fn val: [9.28542692] grad norm: 0.970228425804473
    GD iter: 74 step length: 0.0009765625 obj fn val: [9.28497683] grad norm: 0.09943290278665261
    GD iter: 75 step length: 0.015625 obj fn val: [9.28494473] grad norm: 0.46700991181950285
    GD iter: 76 step length: 0.001953125 obj fn val: [9.28494413] grad norm: 0.4946149520408106
    GD iter: 77 step length: 0.0009765625 obj fn val: [9.28482503] grad norm: 0.08220271380595869
    GD iter: 78 step length: 0.03125 obj fn val: [9.28475573] grad norm: 0.48323109918377005
    GD iter: 79 step length: 0.0009765625 obj fn val: [9.28464341] grad norm: 0.06150933034953352
    GD iter: 80 step length: 0.015625 obj fn val: [9.28461581] grad norm: 0.23411363122300974
    GD iter: 81 step length: 0.001953125 obj fn val: [9.28461368] grad norm: 0.24763531544717104
    GD iter: 82 step length: 0.001953125 obj fn val: [9.28461211] grad norm: 0.2620614014374807
    GD iter: 83 step length: 0.001953125 obj fn val: [9.28461115] grad norm: 0.2774415710979818
    GD iter: 84 step length: 0.001953125 obj fn val: [9.28461084] grad norm: 0.29382896680259574
    GD iter: 85 step length: 0.0009765625 obj fn val: [9.28456879] grad norm: 0.0492753053337694
    GD iter: 86 step length: 0.03125 obj fn val: [9.28454313] grad norm: 0.28703403545849643
    GD iter: 87 step length: 0.0009765625 obj fn val: [9.28450349] grad norm: 0.03686247930804316
    GD iter: 88 step length: 0.015625 obj fn val: [9.2844934] grad norm: 0.13910674931167016
    GD iter: 89 step length: 0.001953125 obj fn val: [9.28449261] grad norm: 0.14713164099428896
    GD iter: 90 step length: 0.001953125 obj fn val: [9.28449202] grad norm: 0.1556941063032601
    GD iter: 91 step length: 0.001953125 obj fn val: [9.28449165] grad norm: 0.16482362101322842
    GD iter: 92 step length: 0.001953125 obj fn val: [9.28449151] grad norm: 0.17455171692337493
    GD iter: 93 step length: 0.0009765625 obj fn val: [9.28447666] grad norm: 0.029537587312737156
    GD iter: 94 step length: 0.03125 obj fn val: [9.28446717] grad norm: 0.17049559475818568
    GD iter: 95 step length: 0.0009765625 obj fn val: [9.28445318] grad norm: 0.022091862777549466
    GD iter: 96 step length: 0.015625 obj fn val: [9.2844495] grad norm: 0.08265583792409734
    GD iter: 97 step length: 0.001953125 obj fn val: [9.2844492] grad norm: 0.08741841274217328
    GD iter: 98 step length: 0.001953125 obj fn val: [9.28444898] grad norm: 0.0925005237952456
    GD iter: 99 step length: 0.001953125 obj fn val: [9.28444884] grad norm: 0.0979196585589292
    GD iter: 100 step length: 0.001953125 obj fn val: [9.28444878] grad norm: 0.10369452606725749
    GD iter: 101 step length: 0.0009765625 obj fn val: [9.28444354] grad norm: 0.017706111449449526
    GD iter: 102 step length: 0.03125 obj fn val: [9.28444003] grad norm: 0.10127312138233391
    GD iter: 103 step length: 0.0009765625 obj fn val: [9.28443509] grad norm: 0.01323988803887946
    GD iter: 104 step length: 0.015625 obj fn val: [9.28443375] grad norm: 0.04911371213666974
    GD iter: 105 step length: 0.001953125 obj fn val: [9.28443364] grad norm: 0.051940144387576534
    GD iter: 106 step length: 0.001953125 obj fn val: [9.28443356] grad norm: 0.05495651292450144
    GD iter: 107 step length: 0.001953125 obj fn val: [9.2844335] grad norm: 0.058173192647929646
    GD iter: 108 step length: 0.001953125 obj fn val: [9.28443348] grad norm: 0.0616012842175615
    GD iter: 109 step length: 0.0009765625 obj fn val: [9.28443163] grad norm: 0.0106138710059198
    GD iter: 110 step length: 0.03125 obj fn val: [9.28443033] grad norm: 0.06015566348752611
    GD iter: 111 step length: 0.0009765625 obj fn val: [9.28442859] grad norm: 0.00793488063085727
    GD iter: 112 step length: 0.015625 obj fn val: [9.2844281] grad norm: 0.029183404326071638
    GD iter: 113 step length: 0.001953125 obj fn val: [9.28442806] grad norm: 0.030860776279561915
    GD iter: 114 step length: 0.001953125 obj fn val: [9.28442803] grad norm: 0.03265105019711209
    GD iter: 115 step length: 0.001953125 obj fn val: [9.28442801] grad norm: 0.034560381187376
    GD iter: 116 step length: 0.001953125 obj fn val: [9.284428] grad norm: 0.036595355542996325
    GD iter: 117 step length: 0.0009765625 obj fn val: [9.28442734] grad norm: 0.006362485564280812
    GD iter: 118 step length: 0.03125 obj fn val: [9.28442687] grad norm: 0.03573223345581391
    GD iter: 119 step length: 0.0009765625 obj fn val: [9.28442625] grad norm: 0.004755547488258407
    GD iter: 120 step length: 0.03125 obj fn val: [9.28442624] grad norm: 0.03498714681136956
    GD iter: 121 step length: 0.0009765625 obj fn val: [9.28442566] grad norm: 0.0035838590090570897
    GD iter: 122 step length: 0.015625 obj fn val: [9.28442562] grad norm: 0.016840519530352573
    GD iter: 123 step length: 0.001953125 obj fn val: [9.28442561] grad norm: 0.01783600751351173
    GD iter: 124 step length: 0.0009765625 obj fn val: [9.28442546] grad norm: 0.002962741222894546
    GD iter: 125 step length: 0.03125 obj fn val: [9.28442537] grad norm: 0.01742561181507219
    GD iter: 126 step length: 0.0009765625 obj fn val: [9.28442522] grad norm: 0.0022169417696141294
    GD iter: 127 step length: 0.015625 obj fn val: [9.28442519] grad norm: 0.008442125414691573
    GD iter: 128 step length: 0.001953125 obj fn val: [9.28442519] grad norm: 0.008929749114244611
    GD iter: 129 step length: 0.001953125 obj fn val: [9.28442518] grad norm: 0.009449984836055416
    GD iter: 130 step length: 0.001953125 obj fn val: [9.28442518] grad norm: 0.010004624259531063
    GD iter: 131 step length: 0.001953125 obj fn val: [9.28442518] grad norm: 0.010595583848848284
    GD iter: 132 step length: 0.0009765625 obj fn val: [9.28442513] grad norm: 0.0017759745736594297
    GD iter: 133 step length: 0.03125 obj fn val: [9.28442509] grad norm: 0.010350622880760439
    GD iter: 134 step length: 0.0009765625 obj fn val: [9.28442504] grad norm: 0.0013286102075197623
    GD iter: 135 step length: 0.015625 obj fn val: [9.28442503] grad norm: 0.005016179679864748
    GD iter: 136 step length: 0.001953125 obj fn val: [9.28442503] grad norm: 0.0053055763430487875
    GD iter: 137 step length: 0.001953125 obj fn val: [9.28442503] grad norm: 0.005614357477716437
    GD iter: 138 step length: 0.001953125 obj fn val: [9.28442503] grad norm: 0.005943586070011222
    GD iter: 139 step length: 0.001953125 obj fn val: [9.28442503] grad norm: 0.006294399246480458
    GD iter: 140 step length: 0.0009765625 obj fn val: [9.28442501] grad norm: 0.0010645897871843755
    GD iter: 141 step length: 0.03125 obj fn val: [9.28442499] grad norm: 0.006148174417039519
    GD iter: 142 step length: 0.0009765625 obj fn val: [9.28442498] grad norm: 0.0007962421062177696
    Gradient norm: 0.0007962421062177696  less than tol: 0.001  Exiting...!



```python
msgd_obj_fn_vals = mini_batch_SGD_SVM(train_features_new, train_label,C)
```

    Epoch: 1 batch: 0 step length: 0.0 obj fn val: [12.]
    Epoch: 1 batch: 1 step length: 0.005 obj fn val: [12.49681168]
    Epoch: 1 batch: 2 step length: 0.005 obj fn val: [22.35726404]
    Epoch: 1 batch: 3 step length: 0.005 obj fn val: [14.58091666]
    Epoch: 2 batch: 0 step length: 0.005 obj fn val: [12.03070995]
    Epoch: 2 batch: 1 step length: 0.0033333333333333335 obj fn val: [10.64068855]
    Epoch: 2 batch: 2 step length: 0.0033333333333333335 obj fn val: [10.28746777]
    Epoch: 2 batch: 3 step length: 0.0033333333333333335 obj fn val: [10.56313433]
    Epoch: 3 batch: 0 step length: 0.0033333333333333335 obj fn val: [10.17432847]
    Epoch: 3 batch: 1 step length: 0.0025 obj fn val: [10.50380154]
    Epoch: 3 batch: 2 step length: 0.0025 obj fn val: [10.15559671]
    Epoch: 3 batch: 3 step length: 0.0025 obj fn val: [10.23931302]
    Epoch: 4 batch: 0 step length: 0.0025 obj fn val: [10.17571621]
    Epoch: 4 batch: 1 step length: 0.002 obj fn val: [10.14777831]
    Epoch: 4 batch: 2 step length: 0.002 obj fn val: [10.13122644]
    Epoch: 4 batch: 3 step length: 0.002 obj fn val: [10.10731207]
    Epoch: 5 batch: 0 step length: 0.002 obj fn val: [10.10954325]
    Epoch: 5 batch: 1 step length: 0.0016666666666666668 obj fn val: [10.15438234]
    Epoch: 5 batch: 2 step length: 0.0016666666666666668 obj fn val: [10.10436065]
    Epoch: 5 batch: 3 step length: 0.0016666666666666668 obj fn val: [10.16035706]
    Epoch: 6 batch: 0 step length: 0.0016666666666666668 obj fn val: [10.08760458]
    Epoch: 6 batch: 1 step length: 0.0014285714285714286 obj fn val: [10.06648177]
    Epoch: 6 batch: 2 step length: 0.0014285714285714286 obj fn val: [10.0631579]
    Epoch: 6 batch: 3 step length: 0.0014285714285714286 obj fn val: [10.06319171]
    Epoch: 7 batch: 0 step length: 0.0014285714285714286 obj fn val: [10.05312154]
    Epoch: 7 batch: 1 step length: 0.00125 obj fn val: [10.07765226]
    Epoch: 7 batch: 2 step length: 0.00125 obj fn val: [10.04829992]
    Epoch: 7 batch: 3 step length: 0.00125 obj fn val: [10.06474212]
    Epoch: 8 batch: 0 step length: 0.00125 obj fn val: [10.03984718]
    Epoch: 8 batch: 1 step length: 0.0011111111111111111 obj fn val: [10.0873305]
    Epoch: 8 batch: 2 step length: 0.0011111111111111111 obj fn val: [10.04244435]
    Epoch: 8 batch: 3 step length: 0.0011111111111111111 obj fn val: [10.02414207]
    Epoch: 9 batch: 0 step length: 0.0011111111111111111 obj fn val: [10.02338811]
    Epoch: 9 batch: 1 step length: 0.001 obj fn val: [10.03459083]
    Epoch: 9 batch: 2 step length: 0.001 obj fn val: [10.02808725]
    Epoch: 9 batch: 3 step length: 0.001 obj fn val: [10.01591314]
    Epoch: 10 batch: 0 step length: 0.001 obj fn val: [10.01649573]
    Epoch: 10 batch: 1 step length: 0.0009090909090909091 obj fn val: [10.00874567]
    Epoch: 10 batch: 2 step length: 0.0009090909090909091 obj fn val: [10.00847673]
    Epoch: 10 batch: 3 step length: 0.0009090909090909091 obj fn val: [10.00481631]
    Epoch: 11 batch: 0 step length: 0.0009090909090909091 obj fn val: [10.0051]
    Epoch: 11 batch: 1 step length: 0.0008333333333333334 obj fn val: [9.99765968]
    Epoch: 11 batch: 2 step length: 0.0008333333333333334 obj fn val: [10.03361204]
    Epoch: 11 batch: 3 step length: 0.0008333333333333334 obj fn val: [10.01108039]
    Epoch: 12 batch: 0 step length: 0.0008333333333333334 obj fn val: [9.99210269]
    Epoch: 12 batch: 1 step length: 0.0007692307692307692 obj fn val: [9.99371556]
    Epoch: 12 batch: 2 step length: 0.0007692307692307692 obj fn val: [9.99352549]
    Epoch: 12 batch: 3 step length: 0.0007692307692307692 obj fn val: [9.99017963]
    Epoch: 13 batch: 0 step length: 0.0007692307692307692 obj fn val: [9.98308251]
    Epoch: 13 batch: 1 step length: 0.0007142857142857143 obj fn val: [9.9814995]
    Epoch: 13 batch: 2 step length: 0.0007142857142857143 obj fn val: [9.97799722]
    Epoch: 13 batch: 3 step length: 0.0007142857142857143 obj fn val: [9.98101259]
    Epoch: 14 batch: 0 step length: 0.0007142857142857143 obj fn val: [9.97536181]
    Epoch: 14 batch: 1 step length: 0.0006666666666666666 obj fn val: [9.97543268]
    Epoch: 14 batch: 2 step length: 0.0006666666666666666 obj fn val: [9.98138833]
    Epoch: 14 batch: 3 step length: 0.0006666666666666666 obj fn val: [9.98987628]
    Epoch: 15 batch: 0 step length: 0.0006666666666666666 obj fn val: [9.968621]
    Epoch: 15 batch: 1 step length: 0.000625 obj fn val: [9.96670789]
    Epoch: 15 batch: 2 step length: 0.000625 obj fn val: [9.99145676]
    Epoch: 15 batch: 3 step length: 0.000625 obj fn val: [9.96520794]
    Epoch: 16 batch: 0 step length: 0.000625 obj fn val: [9.96163031]
    Epoch: 16 batch: 1 step length: 0.0005882352941176471 obj fn val: [9.95967138]
    Epoch: 16 batch: 2 step length: 0.0005882352941176471 obj fn val: [9.98353391]
    Epoch: 16 batch: 3 step length: 0.0005882352941176471 obj fn val: [9.96938977]
    Epoch: 17 batch: 0 step length: 0.0005882352941176471 obj fn val: [9.95862522]
    Epoch: 17 batch: 1 step length: 0.0005555555555555556 obj fn val: [9.95278399]
    Epoch: 17 batch: 2 step length: 0.0005555555555555556 obj fn val: [9.95421879]
    Epoch: 17 batch: 3 step length: 0.0005555555555555556 obj fn val: [9.95158083]
    Epoch: 18 batch: 0 step length: 0.0005555555555555556 obj fn val: [9.95070025]
    Epoch: 18 batch: 1 step length: 0.0005263157894736842 obj fn val: [9.95052733]
    Epoch: 18 batch: 2 step length: 0.0005263157894736842 obj fn val: [9.95199846]
    Epoch: 18 batch: 3 step length: 0.0005263157894736842 obj fn val: [9.94560951]
    Epoch: 19 batch: 0 step length: 0.0005263157894736842 obj fn val: [9.94511932]
    Epoch: 19 batch: 1 step length: 0.0005 obj fn val: [9.94512325]
    Epoch: 19 batch: 2 step length: 0.0005 obj fn val: [9.94754398]
    Epoch: 19 batch: 3 step length: 0.0005 obj fn val: [9.94078582]
    Epoch: 20 batch: 0 step length: 0.0005 obj fn val: [9.93895029]
    Epoch: 20 batch: 1 step length: 0.0004761904761904762 obj fn val: [9.96217291]
    Epoch: 20 batch: 2 step length: 0.0004761904761904762 obj fn val: [9.94774517]
    Epoch: 20 batch: 3 step length: 0.0004761904761904762 obj fn val: [9.93553465]
    Epoch: 21 batch: 0 step length: 0.0004761904761904762 obj fn val: [9.93537771]
    Epoch: 21 batch: 1 step length: 0.00045454545454545455 obj fn val: [9.93231306]
    Epoch: 21 batch: 2 step length: 0.00045454545454545455 obj fn val: [9.93192867]
    Epoch: 21 batch: 3 step length: 0.00045454545454545455 obj fn val: [9.93500389]
    Epoch: 22 batch: 0 step length: 0.00045454545454545455 obj fn val: [9.93018829]
    Epoch: 22 batch: 1 step length: 0.0004347826086956522 obj fn val: [9.94076282]
    Epoch: 22 batch: 2 step length: 0.0004347826086956522 obj fn val: [9.92922557]
    Epoch: 22 batch: 3 step length: 0.0004347826086956522 obj fn val: [9.92991151]
    Epoch: 23 batch: 0 step length: 0.0004347826086956522 obj fn val: [9.92520074]
    Epoch: 23 batch: 1 step length: 0.0004166666666666667 obj fn val: [9.93066282]
    Epoch: 23 batch: 2 step length: 0.0004166666666666667 obj fn val: [9.92543903]
    Epoch: 23 batch: 3 step length: 0.0004166666666666667 obj fn val: [9.9224131]
    Epoch: 24 batch: 0 step length: 0.0004166666666666667 obj fn val: [9.92141792]
    Epoch: 24 batch: 1 step length: 0.0004 obj fn val: [9.92368856]
    Epoch: 24 batch: 2 step length: 0.0004 obj fn val: [9.91902206]
    Epoch: 24 batch: 3 step length: 0.0004 obj fn val: [9.9188209]
    Epoch: 25 batch: 0 step length: 0.0004 obj fn val: [9.91715236]
    Epoch: 25 batch: 1 step length: 0.0003846153846153846 obj fn val: [9.9170497]
    Epoch: 25 batch: 2 step length: 0.0003846153846153846 obj fn val: [9.922822]
    Epoch: 25 batch: 3 step length: 0.0003846153846153846 obj fn val: [9.91378141]
    Epoch: 26 batch: 0 step length: 0.0003846153846153846 obj fn val: [9.91377091]
    Epoch: 26 batch: 1 step length: 0.00037037037037037035 obj fn val: [9.91305481]
    Epoch: 26 batch: 2 step length: 0.00037037037037037035 obj fn val: [9.91137638]
    Epoch: 26 batch: 3 step length: 0.00037037037037037035 obj fn val: [9.9109172]
    Epoch: 27 batch: 0 step length: 0.00037037037037037035 obj fn val: [9.91001083]
    Epoch: 27 batch: 1 step length: 0.00035714285714285714 obj fn val: [9.91628424]
    Epoch: 27 batch: 2 step length: 0.00035714285714285714 obj fn val: [9.91355852]
    Epoch: 27 batch: 3 step length: 0.00035714285714285714 obj fn val: [9.90988491]
    Epoch: 28 batch: 0 step length: 0.00035714285714285714 obj fn val: [9.90641234]
    Epoch: 28 batch: 1 step length: 0.0003448275862068966 obj fn val: [9.90623491]
    Epoch: 28 batch: 2 step length: 0.0003448275862068966 obj fn val: [9.90458061]
    Epoch: 28 batch: 3 step length: 0.0003448275862068966 obj fn val: [9.90516281]
    Epoch: 29 batch: 0 step length: 0.0003448275862068966 obj fn val: [9.90310852]
    Epoch: 29 batch: 1 step length: 0.0003333333333333333 obj fn val: [9.9032721]
    Epoch: 29 batch: 2 step length: 0.0003333333333333333 obj fn val: [9.90103188]
    Epoch: 29 batch: 3 step length: 0.0003333333333333333 obj fn val: [9.9002052]
    Epoch: 30 batch: 0 step length: 0.0003333333333333333 obj fn val: [9.8999133]
    Epoch: 30 batch: 1 step length: 0.0003225806451612903 obj fn val: [9.89877006]
    Epoch: 30 batch: 2 step length: 0.0003225806451612903 obj fn val: [9.89837755]
    Epoch: 30 batch: 3 step length: 0.0003225806451612903 obj fn val: [9.8967778]
    Epoch: 31 batch: 0 step length: 0.0003225806451612903 obj fn val: [9.89687819]
    Epoch: 31 batch: 1 step length: 0.0003125 obj fn val: [9.8962014]
    Epoch: 31 batch: 2 step length: 0.0003125 obj fn val: [9.89520701]
    Epoch: 31 batch: 3 step length: 0.0003125 obj fn val: [9.89451039]
    Epoch: 32 batch: 0 step length: 0.0003125 obj fn val: [9.89395764]
    Epoch: 32 batch: 1 step length: 0.00030303030303030303 obj fn val: [9.89648417]
    Epoch: 32 batch: 2 step length: 0.00030303030303030303 obj fn val: [9.8926464]
    Epoch: 32 batch: 3 step length: 0.00030303030303030303 obj fn val: [9.89174903]
    Epoch: 33 batch: 0 step length: 0.00030303030303030303 obj fn val: [9.89120029]
    Epoch: 33 batch: 1 step length: 0.00029411764705882356 obj fn val: [9.89167022]
    Epoch: 33 batch: 2 step length: 0.00029411764705882356 obj fn val: [9.89180616]
    Epoch: 33 batch: 3 step length: 0.00029411764705882356 obj fn val: [9.89018735]
    Epoch: 34 batch: 0 step length: 0.00029411764705882356 obj fn val: [9.88870529]
    Epoch: 34 batch: 1 step length: 0.00028571428571428574 obj fn val: [9.89031113]
    Epoch: 34 batch: 2 step length: 0.00028571428571428574 obj fn val: [9.88791042]
    Epoch: 34 batch: 3 step length: 0.00028571428571428574 obj fn val: [9.88674817]
    Epoch: 35 batch: 0 step length: 0.00028571428571428574 obj fn val: [9.88599724]
    Epoch: 35 batch: 1 step length: 0.0002777777777777778 obj fn val: [9.88594518]
    Epoch: 35 batch: 2 step length: 0.0002777777777777778 obj fn val: [9.8844302]
    Epoch: 35 batch: 3 step length: 0.0002777777777777778 obj fn val: [9.88363758]
    Epoch: 36 batch: 0 step length: 0.0002777777777777778 obj fn val: [9.88343231]
    Epoch: 36 batch: 1 step length: 0.0002702702702702703 obj fn val: [9.88311864]
    Epoch: 36 batch: 2 step length: 0.0002702702702702703 obj fn val: [9.88263248]
    Epoch: 36 batch: 3 step length: 0.0002702702702702703 obj fn val: [9.88127808]
    Epoch: 37 batch: 0 step length: 0.0002702702702702703 obj fn val: [9.88087204]
    Epoch: 37 batch: 1 step length: 0.0002631578947368421 obj fn val: [9.88115563]
    Epoch: 37 batch: 2 step length: 0.0002631578947368421 obj fn val: [9.8798555]
    Epoch: 37 batch: 3 step length: 0.0002631578947368421 obj fn val: [9.87972925]
    Epoch: 38 batch: 0 step length: 0.0002631578947368421 obj fn val: [9.87848297]
    Epoch: 38 batch: 1 step length: 0.0002564102564102564 obj fn val: [9.88033198]
    Epoch: 38 batch: 2 step length: 0.0002564102564102564 obj fn val: [9.87770538]
    Epoch: 38 batch: 3 step length: 0.0002564102564102564 obj fn val: [9.88122987]
    Epoch: 39 batch: 0 step length: 0.0002564102564102564 obj fn val: [9.87619478]
    Epoch: 39 batch: 1 step length: 0.00025 obj fn val: [9.87678191]
    Epoch: 39 batch: 2 step length: 0.00025 obj fn val: [9.87531326]
    Epoch: 39 batch: 3 step length: 0.00025 obj fn val: [9.87975276]
    Epoch: 40 batch: 0 step length: 0.00025 obj fn val: [9.87386017]
    Epoch: 40 batch: 1 step length: 0.00024390243902439024 obj fn val: [9.87326286]
    Epoch: 40 batch: 2 step length: 0.00024390243902439024 obj fn val: [9.87291983]
    Epoch: 40 batch: 3 step length: 0.00024390243902439024 obj fn val: [9.87264731]
    Epoch: 41 batch: 0 step length: 0.00024390243902439024 obj fn val: [9.8717368]
    Epoch: 41 batch: 1 step length: 0.0002380952380952381 obj fn val: [9.873421]
    Epoch: 41 batch: 2 step length: 0.0002380952380952381 obj fn val: [9.87249052]
    Epoch: 41 batch: 3 step length: 0.0002380952380952381 obj fn val: [9.87107836]
    Epoch: 42 batch: 0 step length: 0.0002380952380952381 obj fn val: [9.86956737]
    Epoch: 42 batch: 1 step length: 0.00023255813953488373 obj fn val: [9.86941773]
    Epoch: 42 batch: 2 step length: 0.00023255813953488373 obj fn val: [9.87074249]
    Epoch: 42 batch: 3 step length: 0.00023255813953488373 obj fn val: [9.86916249]
    Epoch: 43 batch: 0 step length: 0.00023255813953488373 obj fn val: [9.86751684]
    Epoch: 43 batch: 1 step length: 0.00022727272727272727 obj fn val: [9.86705506]
    Epoch: 43 batch: 2 step length: 0.00022727272727272727 obj fn val: [9.86634399]
    Epoch: 43 batch: 3 step length: 0.00022727272727272727 obj fn val: [9.86568023]
    Epoch: 44 batch: 0 step length: 0.00022727272727272727 obj fn val: [9.86551834]
    Epoch: 44 batch: 1 step length: 0.00022222222222222223 obj fn val: [9.86537836]
    Epoch: 44 batch: 2 step length: 0.00022222222222222223 obj fn val: [9.86960697]
    Epoch: 44 batch: 3 step length: 0.00022222222222222223 obj fn val: [9.86415197]
    Epoch: 45 batch: 0 step length: 0.00022222222222222223 obj fn val: [9.86360058]
    Epoch: 45 batch: 1 step length: 0.0002173913043478261 obj fn val: [9.86312332]
    Epoch: 45 batch: 2 step length: 0.0002173913043478261 obj fn val: [9.86344844]
    Epoch: 45 batch: 3 step length: 0.0002173913043478261 obj fn val: [9.86240971]
    Epoch: 46 batch: 0 step length: 0.0002173913043478261 obj fn val: [9.86168224]
    Epoch: 46 batch: 1 step length: 0.0002127659574468085 obj fn val: [9.86159439]
    Epoch: 46 batch: 2 step length: 0.0002127659574468085 obj fn val: [9.86061009]
    Epoch: 46 batch: 3 step length: 0.0002127659574468085 obj fn val: [9.860752]
    Epoch: 47 batch: 0 step length: 0.0002127659574468085 obj fn val: [9.8598346]
    Epoch: 47 batch: 1 step length: 0.00020833333333333335 obj fn val: [9.86092762]
    Epoch: 47 batch: 2 step length: 0.00020833333333333335 obj fn val: [9.86108291]
    Epoch: 47 batch: 3 step length: 0.00020833333333333335 obj fn val: [9.86201287]
    Epoch: 48 batch: 0 step length: 0.00020833333333333335 obj fn val: [9.85815542]
    Epoch: 48 batch: 1 step length: 0.00020408163265306123 obj fn val: [9.85823091]
    Epoch: 48 batch: 2 step length: 0.00020408163265306123 obj fn val: [9.86009573]
    Epoch: 48 batch: 3 step length: 0.00020408163265306123 obj fn val: [9.85697134]
    Epoch: 49 batch: 0 step length: 0.00020408163265306123 obj fn val: [9.85630628]
    Epoch: 49 batch: 1 step length: 0.0002 obj fn val: [9.85568172]
    Epoch: 49 batch: 2 step length: 0.0002 obj fn val: [9.85536387]
    Epoch: 49 batch: 3 step length: 0.0002 obj fn val: [9.85496616]
    Epoch: 50 batch: 0 step length: 0.0002 obj fn val: [9.85459914]
    Epoch: 50 batch: 1 step length: 0.000196078431372549 obj fn val: [9.85439056]
    Epoch: 50 batch: 2 step length: 0.000196078431372549 obj fn val: [9.85402995]
    Epoch: 50 batch: 3 step length: 0.000196078431372549 obj fn val: [9.85356662]
    Epoch: 51 batch: 0 step length: 0.000196078431372549 obj fn val: [9.85294146]
    Epoch: 51 batch: 1 step length: 0.0001923076923076923 obj fn val: [9.85242666]
    Epoch: 51 batch: 2 step length: 0.0001923076923076923 obj fn val: [9.85164998]
    Epoch: 51 batch: 3 step length: 0.0001923076923076923 obj fn val: [9.85184003]
    Epoch: 52 batch: 0 step length: 0.0001923076923076923 obj fn val: [9.85130392]
    Epoch: 52 batch: 1 step length: 0.00018867924528301886 obj fn val: [9.85077032]
    Epoch: 52 batch: 2 step length: 0.00018867924528301886 obj fn val: [9.85361223]
    Epoch: 52 batch: 3 step length: 0.00018867924528301886 obj fn val: [9.85006853]
    Epoch: 53 batch: 0 step length: 0.00018867924528301886 obj fn val: [9.8497601]
    Epoch: 53 batch: 1 step length: 0.00018518518518518518 obj fn val: [9.84979022]
    Epoch: 53 batch: 2 step length: 0.00018518518518518518 obj fn val: [9.84896201]
    Epoch: 53 batch: 3 step length: 0.00018518518518518518 obj fn val: [9.85074745]
    Epoch: 54 batch: 0 step length: 0.00018518518518518518 obj fn val: [9.8482978]
    Epoch: 54 batch: 1 step length: 0.00018181818181818183 obj fn val: [9.84800213]
    Epoch: 54 batch: 2 step length: 0.00018181818181818183 obj fn val: [9.84766019]
    Epoch: 54 batch: 3 step length: 0.00018181818181818183 obj fn val: [9.84688105]
    Epoch: 55 batch: 0 step length: 0.00018181818181818183 obj fn val: [9.84669681]
    Epoch: 55 batch: 1 step length: 0.00017857142857142857 obj fn val: [9.84634009]
    Epoch: 55 batch: 2 step length: 0.00017857142857142857 obj fn val: [9.84616409]
    Epoch: 55 batch: 3 step length: 0.00017857142857142857 obj fn val: [9.84524692]
    Epoch: 56 batch: 0 step length: 0.00017857142857142857 obj fn val: [9.84523572]
    Epoch: 56 batch: 1 step length: 0.00017543859649122808 obj fn val: [9.84588629]
    Epoch: 56 batch: 2 step length: 0.00017543859649122808 obj fn val: [9.8484411]
    Epoch: 56 batch: 3 step length: 0.00017543859649122808 obj fn val: [9.8476407]
    Epoch: 57 batch: 0 step length: 0.00017543859649122808 obj fn val: [9.84400328]
    Epoch: 57 batch: 1 step length: 0.0001724137931034483 obj fn val: [9.84385821]
    Epoch: 57 batch: 2 step length: 0.0001724137931034483 obj fn val: [9.84487367]
    Epoch: 57 batch: 3 step length: 0.0001724137931034483 obj fn val: [9.84308342]
    Epoch: 58 batch: 0 step length: 0.0001724137931034483 obj fn val: [9.84237849]
    Epoch: 58 batch: 1 step length: 0.00016949152542372882 obj fn val: [9.84495272]
    Epoch: 58 batch: 2 step length: 0.00016949152542372882 obj fn val: [9.84198671]
    Epoch: 58 batch: 3 step length: 0.00016949152542372882 obj fn val: [9.84102917]
    Epoch: 59 batch: 0 step length: 0.00016949152542372882 obj fn val: [9.84085298]
    Epoch: 59 batch: 1 step length: 0.00016666666666666666 obj fn val: [9.84044008]
    Epoch: 59 batch: 2 step length: 0.00016666666666666666 obj fn val: [9.84005725]
    Epoch: 59 batch: 3 step length: 0.00016666666666666666 obj fn val: [9.84095854]
    Epoch: 60 batch: 0 step length: 0.00016666666666666666 obj fn val: [9.83944696]
    Epoch: 60 batch: 1 step length: 0.0001639344262295082 obj fn val: [9.83935844]
    Epoch: 60 batch: 2 step length: 0.0001639344262295082 obj fn val: [9.83890428]
    Epoch: 60 batch: 3 step length: 0.0001639344262295082 obj fn val: [9.83838239]
    Epoch: 61 batch: 0 step length: 0.0001639344262295082 obj fn val: [9.83808287]
    Epoch: 61 batch: 1 step length: 0.00016129032258064516 obj fn val: [9.83948225]
    Epoch: 61 batch: 2 step length: 0.00016129032258064516 obj fn val: [9.84224936]
    Epoch: 61 batch: 3 step length: 0.00016129032258064516 obj fn val: [9.8391401]
    Epoch: 62 batch: 0 step length: 0.00016129032258064516 obj fn val: [9.83666032]
    Epoch: 62 batch: 1 step length: 0.00015873015873015873 obj fn val: [9.83672483]
    Epoch: 62 batch: 2 step length: 0.00015873015873015873 obj fn val: [9.83731055]
    Epoch: 62 batch: 3 step length: 0.00015873015873015873 obj fn val: [9.83566611]
    Epoch: 63 batch: 0 step length: 0.00015873015873015873 obj fn val: [9.83537656]
    Epoch: 63 batch: 1 step length: 0.00015625 obj fn val: [9.83474773]
    Epoch: 63 batch: 2 step length: 0.00015625 obj fn val: [9.8349385]
    Epoch: 63 batch: 3 step length: 0.00015625 obj fn val: [9.83440589]
    Epoch: 64 batch: 0 step length: 0.00015625 obj fn val: [9.83409226]
    Epoch: 64 batch: 1 step length: 0.00015384615384615385 obj fn val: [9.83389699]
    Epoch: 64 batch: 2 step length: 0.00015384615384615385 obj fn val: [9.83330922]
    Epoch: 64 batch: 3 step length: 0.00015384615384615385 obj fn val: [9.83376171]
    Epoch: 65 batch: 0 step length: 0.00015384615384615385 obj fn val: [9.83285149]
    Epoch: 65 batch: 1 step length: 0.00015151515151515152 obj fn val: [9.8325746]
    Epoch: 65 batch: 2 step length: 0.00015151515151515152 obj fn val: [9.83220369]
    Epoch: 65 batch: 3 step length: 0.00015151515151515152 obj fn val: [9.83193206]
    Epoch: 66 batch: 0 step length: 0.00015151515151515152 obj fn val: [9.83160897]
    Epoch: 66 batch: 1 step length: 0.00014925373134328358 obj fn val: [9.83115175]
    Epoch: 66 batch: 2 step length: 0.00014925373134328358 obj fn val: [9.83075463]
    Epoch: 66 batch: 3 step length: 0.00014925373134328358 obj fn val: [9.83067542]
    Epoch: 67 batch: 0 step length: 0.00014925373134328358 obj fn val: [9.83039307]
    Epoch: 67 batch: 1 step length: 0.00014705882352941178 obj fn val: [9.83025363]
    Epoch: 67 batch: 2 step length: 0.00014705882352941178 obj fn val: [9.8301323]
    Epoch: 67 batch: 3 step length: 0.00014705882352941178 obj fn val: [9.82968653]
    Epoch: 68 batch: 0 step length: 0.00014705882352941178 obj fn val: [9.82920108]
    Epoch: 68 batch: 1 step length: 0.00014492753623188405 obj fn val: [9.82914804]
    Epoch: 68 batch: 2 step length: 0.00014492753623188405 obj fn val: [9.82922498]
    Epoch: 68 batch: 3 step length: 0.00014492753623188405 obj fn val: [9.82896448]
    Epoch: 69 batch: 0 step length: 0.00014492753623188405 obj fn val: [9.82801448]
    Epoch: 69 batch: 1 step length: 0.00014285714285714287 obj fn val: [9.8283218]
    Epoch: 69 batch: 2 step length: 0.00014285714285714287 obj fn val: [9.82776879]
    Epoch: 69 batch: 3 step length: 0.00014285714285714287 obj fn val: [9.82709187]
    Epoch: 70 batch: 0 step length: 0.00014285714285714287 obj fn val: [9.82687817]
    Epoch: 70 batch: 1 step length: 0.00014084507042253522 obj fn val: [9.82647826]
    Epoch: 70 batch: 2 step length: 0.00014084507042253522 obj fn val: [9.82633168]
    Epoch: 70 batch: 3 step length: 0.00014084507042253522 obj fn val: [9.82602149]



```python
import matplotlib.pyplot as plt 
fig,ax = plt.subplots(1,1)
ax.plot(np.arange(1,len(obj_fn_vals)+1),obj_fn_vals)
ax.plot(np.arange(1,len(msgd_obj_fn_vals)+1),msgd_obj_fn_vals)
ax.set_xlabel('Iterations')
ax.set_ylabel('Obj fn val')
ax.legend(['Full GD','Mini-batch SGD (B=32)'])
ax.set_title('SVM with squared loss (No bias)')
plt.show()

```

#Now let us consider the bias term 

Here the objective function would be as follows:

$
\begin{align}
\min_{\mathbf{w},b} F(\mathbf{w},b) = & \ \frac{1}{2} \|\mathbf{w}\|_2^2 + C \sum_{i=1}^{n} (\max\{0,  1 - y^i (\mathbf{w}^\top {\mathbf{x}}^i+b)\})^2.\\ 
\end{align}
$

The gradient with respect to $\mathbf{w}$ is given as: 

$
\begin{align}
\nabla_{\mathbf{w}} F(\mathbf{w},b) = \mathbf{w} + C \sum_{i=1}^{n} 2(\max\{0,  1 - y^i (\mathbf{w}^\top {\mathbf{x}}^i+b)\})(-y^i {\mathbf{x}}^i)  
\end{align}
$

and the gradient with respect to bias $b$ is given as:

$
\begin{align}
\nabla_{b} F(\mathbf{w},b) =  C \sum_{i=1}^{n} 2(\max\{0,  1 - y^i (\mathbf{w}^\top {\mathbf{x}}^i+b)\})(-y^i).  
\end{align}
$



```python
C = 0.1
obj_fn_vals = grad_descent_SVM(train_features_new, train_label,C, is_bias_used=True, tol=1e-2, verbose=False)
```

    GD iter: 100 step length: 0.0009765625 obj fn val: [9.15986031] grad norm: [0.51513327]
    GD iter: 200 step length: 0.03125 obj fn val: [8.94958943] grad norm: [3.03830709]
    GD iter: 300 step length: 0.0009765625 obj fn val: [8.81840835] grad norm: [0.30139316]
    GD iter: 400 step length: 0.0009765625 obj fn val: [8.74060431] grad norm: [0.22832463]
    GD iter: 500 step length: 0.015625 obj fn val: [8.69970892] grad norm: [0.75172647]
    GD iter: 600 step length: 0.0009765625 obj fn val: [8.67766528] grad norm: [0.14631548]
    GD iter: 700 step length: 0.03125 obj fn val: [8.66338213] grad norm: [0.8215416]
    GD iter: 800 step length: 0.03125 obj fn val: [8.65391598] grad norm: [0.60416546]
    GD iter: 900 step length: 0.0009765625 obj fn val: [8.64755055] grad norm: [0.07772012]
    GD iter: 1000 step length: 0.001953125 obj fn val: [8.6433562] grad norm: [0.32755621]
    GD iter: 1100 step length: 0.001953125 obj fn val: [8.64055166] grad norm: [0.24151774]
    GD iter: 1200 step length: 0.001953125 obj fn val: [8.63872196] grad norm: [0.24748242]
    GD iter: 1300 step length: 0.001953125 obj fn val: [8.63763504] grad norm: [0.3209006]
    GD iter: 1400 step length: 0.001953125 obj fn val: [8.63679751] grad norm: [0.32812286]
    GD iter: 1500 step length: 0.0009765625 obj fn val: [8.63599904] grad norm: [0.02369261]
    GD iter: 1600 step length: 0.001953125 obj fn val: [8.63560724] grad norm: [0.19224522]
    GD iter: 1700 step length: 0.001953125 obj fn val: [8.63533955] grad norm: [0.19661215]
    GD iter: 1800 step length: 0.001953125 obj fn val: [8.63504914] grad norm: [0.13382234]
    GD iter: 1900 step length: 0.001953125 obj fn val: [8.63500575] grad norm: [0.16345468]
    GD iter: 2000 step length: 0.001953125 obj fn val: [8.63498531] grad norm: [0.19669648]
    GD iter: 2100 step length: 0.001953125 obj fn val: [8.63496189] grad norm: [0.20125331]
    GD iter: 2200 step length: 0.001953125 obj fn val: [8.63493376] grad norm: [0.16997497]
    GD iter: 2300 step length: 0.001953125 obj fn val: [8.63490384] grad norm: [0.10069379]
    GD iter: 2400 step length: 0.001953125 obj fn val: [8.63488111] grad norm: [0.05325729]
    GD iter: 2500 step length: 0.001953125 obj fn val: [8.63486244] grad norm: [0.02891677]
    GD iter: 2600 step length: 0.001953125 obj fn val: [8.63484583] grad norm: [0.01688442]
    GD iter: 2700 step length: 0.001953125 obj fn val: [8.63483072] grad norm: [0.02407568]
    GD iter: 2800 step length: 0.001953125 obj fn val: [8.6348166] grad norm: [0.014376]
    GD iter: 2900 step length: 0.001953125 obj fn val: [8.63480369] grad norm: [0.02010683]
    GD iter: 3000 step length: 0.001953125 obj fn val: [8.63479167] grad norm: [0.01231501]
    GD iter: 3100 step length: 0.001953125 obj fn val: [8.63478064] grad norm: [0.01685342]
    GD iter: 3200 step length: 0.001953125 obj fn val: [8.63477042] grad norm: [0.01061835]
    Gradient norm: [0.00998214]  less than tol: 0.01  Exiting...!



```python
msgd_obj_fn_vals = mini_batch_SGD_SVM(train_features_new, train_label,C, batch_size = 48, is_bias_used=True, max_epochs =300, verbose=False)
```

    Epoch: 10 batch: 0 step length: 0.001 obj fn val: [10.01917827]
    Epoch: 10 batch: 1 step length: 0.0009090909090909091 obj fn val: [10.03977223]
    Epoch: 10 batch: 2 step length: 0.0009090909090909091 obj fn val: [10.01083742]
    Epoch: 20 batch: 0 step length: 0.0005 obj fn val: [9.93956568]
    Epoch: 20 batch: 1 step length: 0.0004761904761904762 obj fn val: [9.93669934]
    Epoch: 20 batch: 2 step length: 0.0004761904761904762 obj fn val: [9.9384139]
    Epoch: 30 batch: 0 step length: 0.0003333333333333333 obj fn val: [9.89928276]
    Epoch: 30 batch: 1 step length: 0.0003225806451612903 obj fn val: [9.90008361]
    Epoch: 30 batch: 2 step length: 0.0003225806451612903 obj fn val: [9.89669433]
    Epoch: 40 batch: 0 step length: 0.00025 obj fn val: [9.87204523]
    Epoch: 40 batch: 1 step length: 0.00024390243902439024 obj fn val: [9.87186815]
    Epoch: 40 batch: 2 step length: 0.00024390243902439024 obj fn val: [9.87068553]
    Epoch: 50 batch: 0 step length: 0.0002 obj fn val: [9.85183658]
    Epoch: 50 batch: 1 step length: 0.000196078431372549 obj fn val: [9.85096193]
    Epoch: 50 batch: 2 step length: 0.000196078431372549 obj fn val: [9.85080497]
    Epoch: 60 batch: 0 step length: 0.00016666666666666666 obj fn val: [9.83593325]
    Epoch: 60 batch: 1 step length: 0.0001639344262295082 obj fn val: [9.83567284]
    Epoch: 60 batch: 2 step length: 0.0001639344262295082 obj fn val: [9.83533159]
    Epoch: 70 batch: 0 step length: 0.00014285714285714287 obj fn val: [9.8228828]
    Epoch: 70 batch: 1 step length: 0.00014084507042253522 obj fn val: [9.82276392]
    Epoch: 70 batch: 2 step length: 0.00014084507042253522 obj fn val: [9.82196899]
    Epoch: 80 batch: 0 step length: 0.000125 obj fn val: [9.81181193]
    Epoch: 80 batch: 1 step length: 0.0001234567901234568 obj fn val: [9.81164346]
    Epoch: 80 batch: 2 step length: 0.0001234567901234568 obj fn val: [9.81147523]
    Epoch: 90 batch: 0 step length: 0.00011111111111111112 obj fn val: [9.80226913]
    Epoch: 90 batch: 1 step length: 0.00010989010989010989 obj fn val: [9.80243859]
    Epoch: 90 batch: 2 step length: 0.00010989010989010989 obj fn val: [9.80187434]
    Epoch: 100 batch: 0 step length: 0.0001 obj fn val: [9.79390013]
    Epoch: 100 batch: 1 step length: 9.900990099009902e-05 obj fn val: [9.79389875]
    Epoch: 100 batch: 2 step length: 9.900990099009902e-05 obj fn val: [9.79324789]
    Epoch: 110 batch: 0 step length: 9.090909090909092e-05 obj fn val: [9.7864714]
    Epoch: 110 batch: 1 step length: 9.009009009009009e-05 obj fn val: [9.78639771]
    Epoch: 110 batch: 2 step length: 9.009009009009009e-05 obj fn val: [9.78599972]
    Epoch: 120 batch: 0 step length: 8.333333333333333e-05 obj fn val: [9.77978734]
    Epoch: 120 batch: 1 step length: 8.264462809917356e-05 obj fn val: [9.77945169]
    Epoch: 120 batch: 2 step length: 8.264462809917356e-05 obj fn val: [9.77923795]
    Epoch: 130 batch: 0 step length: 7.692307692307693e-05 obj fn val: [9.7737328]
    Epoch: 130 batch: 1 step length: 7.633587786259542e-05 obj fn val: [9.77373886]
    Epoch: 130 batch: 2 step length: 7.633587786259542e-05 obj fn val: [9.77330809]
    Epoch: 140 batch: 0 step length: 7.142857142857143e-05 obj fn val: [9.76820358]
    Epoch: 140 batch: 1 step length: 7.092198581560284e-05 obj fn val: [9.76816586]
    Epoch: 140 batch: 2 step length: 7.092198581560284e-05 obj fn val: [9.76773977]
    Epoch: 150 batch: 0 step length: 6.666666666666667e-05 obj fn val: [9.76309746]
    Epoch: 150 batch: 1 step length: 6.622516556291391e-05 obj fn val: [9.76318898]
    Epoch: 150 batch: 2 step length: 6.622516556291391e-05 obj fn val: [9.76270877]
    Epoch: 160 batch: 0 step length: 6.25e-05 obj fn val: [9.75838388]
    Epoch: 160 batch: 1 step length: 6.211180124223603e-05 obj fn val: [9.75833554]
    Epoch: 160 batch: 2 step length: 6.211180124223603e-05 obj fn val: [9.75808904]
    Epoch: 170 batch: 0 step length: 5.882352941176471e-05 obj fn val: [9.75400792]
    Epoch: 170 batch: 1 step length: 5.847953216374269e-05 obj fn val: [9.75381673]
    Epoch: 170 batch: 2 step length: 5.847953216374269e-05 obj fn val: [9.75364805]
    Epoch: 180 batch: 0 step length: 5.555555555555556e-05 obj fn val: [9.74992325]
    Epoch: 180 batch: 1 step length: 5.524861878453039e-05 obj fn val: [9.74974447]
    Epoch: 180 batch: 2 step length: 5.524861878453039e-05 obj fn val: [9.74965442]
    Epoch: 190 batch: 0 step length: 5.2631578947368424e-05 obj fn val: [9.74609381]
    Epoch: 190 batch: 1 step length: 5.2356020942408376e-05 obj fn val: [9.74586214]
    Epoch: 190 batch: 2 step length: 5.2356020942408376e-05 obj fn val: [9.74574859]
    Epoch: 200 batch: 0 step length: 5e-05 obj fn val: [9.74249958]
    Epoch: 200 batch: 1 step length: 4.9751243781094526e-05 obj fn val: [9.74235276]
    Epoch: 200 batch: 2 step length: 4.9751243781094526e-05 obj fn val: [9.7422449]
    Epoch: 210 batch: 0 step length: 4.761904761904762e-05 obj fn val: [9.7391082]
    Epoch: 210 batch: 1 step length: 4.739336492890995e-05 obj fn val: [9.73900678]
    Epoch: 210 batch: 2 step length: 4.739336492890995e-05 obj fn val: [9.73882269]
    Epoch: 220 batch: 0 step length: 4.545454545454546e-05 obj fn val: [9.73589688]
    Epoch: 220 batch: 1 step length: 4.524886877828054e-05 obj fn val: [9.73582849]
    Epoch: 220 batch: 2 step length: 4.524886877828054e-05 obj fn val: [9.73567976]
    Epoch: 230 batch: 0 step length: 4.347826086956522e-05 obj fn val: [9.73285511]
    Epoch: 230 batch: 1 step length: 4.329004329004329e-05 obj fn val: [9.73274384]
    Epoch: 230 batch: 2 step length: 4.329004329004329e-05 obj fn val: [9.73260653]
    Epoch: 240 batch: 0 step length: 4.1666666666666665e-05 obj fn val: [9.72996642]
    Epoch: 240 batch: 1 step length: 4.149377593360996e-05 obj fn val: [9.72982431]
    Epoch: 240 batch: 2 step length: 4.149377593360996e-05 obj fn val: [9.72972779]
    Epoch: 250 batch: 0 step length: 4e-05 obj fn val: [9.72721592]
    Epoch: 250 batch: 1 step length: 3.9840637450199205e-05 obj fn val: [9.72706538]
    Epoch: 250 batch: 2 step length: 3.9840637450199205e-05 obj fn val: [9.72700407]
    Epoch: 260 batch: 0 step length: 3.846153846153846e-05 obj fn val: [9.72458988]
    Epoch: 260 batch: 1 step length: 3.8314176245210727e-05 obj fn val: [9.7246388]
    Epoch: 260 batch: 2 step length: 3.8314176245210727e-05 obj fn val: [9.72449224]
    Epoch: 270 batch: 0 step length: 3.7037037037037037e-05 obj fn val: [9.72208158]
    Epoch: 270 batch: 1 step length: 3.690036900369004e-05 obj fn val: [9.72208516]
    Epoch: 270 batch: 2 step length: 3.690036900369004e-05 obj fn val: [9.7219698]
    Epoch: 280 batch: 0 step length: 3.571428571428572e-05 obj fn val: [9.71967781]
    Epoch: 280 batch: 1 step length: 3.558718861209964e-05 obj fn val: [9.71960411]
    Epoch: 280 batch: 2 step length: 3.558718861209964e-05 obj fn val: [9.71948781]
    Epoch: 290 batch: 0 step length: 3.4482758620689657e-05 obj fn val: [9.71737349]
    Epoch: 290 batch: 1 step length: 3.4364261168384884e-05 obj fn val: [9.71729683]
    Epoch: 290 batch: 2 step length: 3.4364261168384884e-05 obj fn val: [9.71717791]
    Epoch: 300 batch: 0 step length: 3.3333333333333335e-05 obj fn val: [9.71515969]
    Epoch: 300 batch: 1 step length: 3.322259136212625e-05 obj fn val: [9.71507889]
    Epoch: 300 batch: 2 step length: 3.322259136212625e-05 obj fn val: [9.71503123]



```python
import matplotlib.pyplot as plt 
fig,ax = plt.subplots(1,1)
ax.plot(np.arange(1,len(obj_fn_vals)+1),obj_fn_vals)
ax.plot(np.arange(1,len(msgd_obj_fn_vals)+1),msgd_obj_fn_vals)
ax.set_xlabel('Iterations')
ax.set_ylabel('Obj fn val')
ax.legend(['Full GD','Mini-batch SGD (B=48)'])
ax.set_title('SVM with squared loss (With bias)')
plt.show()

```


```python

```

032512e4c121ebec235b886b3b6773ab6f5b8049
ipynb
Jupyter Notebook
Optimization/Optimization_SVM_TA_Session_2021Dec18.ipynb
arvind-maurya/AIML_CEP_2021
eb09ccb812b1b3fb5761d45423a08289923c8da9
CC0-1.0
Optimization/Optimization_SVM_TA_Session_2021Dec18.ipynb
arvind-maurya/AIML_CEP_2021
eb09ccb812b1b3fb5761d45423a08289923c8da9
CC0-1.0
Optimization/Optimization_SVM_TA_Session_2021Dec18.ipynb
arvind-maurya/AIML_CEP_2021
eb09ccb812b1b3fb5761d45423a08289923c8da9
CC0-1.0
2021-10-17T10:16:01.000Z
2022-01-29T13:43:25.000Z
Qwen/Qwen-72B
1. YES
2. YES