I have a difficulty where to start the implementation of incremental stochastic gradient descent algorithm and its respective implementation in logistic regression. I don't quite understand this algorithm and there are few sources to explain it with crystal-clear interpretation and possible demo code. I am quite new with ML algorithm and I have no idea which would be efficient workaround to solve this problem.

In particular, the problem I am studying is to implement hogWild! algorithm for logistic regression, which asks me to program incremental SGD algorithm with a sequential order. Can anyone give me a general idea or possible pipeline to make this happen in python?

logistic loss function and gradient

enter image description here

Here is my implementation:

import numpy as np
import scipy as sp
import sklearn as sl
from scipy import special as ss
from  sklearn import datasets

X_train, y_train=datasets.load_svmlight_file('/path/to/train_dataset')

class ISGD:
def lossFunc(X,y,w):

    lossFnc=ss.log1p(1+np.nan_to_num(ss.expm1(-y* np.dot(X,w,))))
    return rslt

def gradFnc(X,y,w):

    return gradF3

def _init_(self, learnRate=0.0001, num_iter=100, verbose=False):

def fitt(self, X,y):

    for i in range(self.num_iter):
        print ("\n:", "Iteration:", i)

        grd=gradFnc(self.w, X,y)
        print "Loss:", lossFunc(self.w,X,y)

    return self

Seems my above implementation has some problems. Can anyone help me how to correct that? Plus, I don't have a solid idea how to implement incremental SGD sequentially. How can I make this happen? Any idea?

  • $\begingroup$ Please post the entirety of your code for us to be able to look at it. It seems you have an init function outside a class. That function header is also missing a d, for "def". $\endgroup$
    – JahKnows
    Commented Jan 25, 2018 at 10:39
  • $\begingroup$ @JahKnows Thank you. How can I deal with the implementation of sequential incremental stochastic gradient descent algorithm? How to get started with that? Any idea? $\endgroup$
    – Andy.Jian
    Commented Jan 26, 2018 at 16:11
  • $\begingroup$ Jian I edited my answer to add the corresponding code. $\endgroup$
    – JahKnows
    Commented Jan 26, 2018 at 19:09

2 Answers 2


Gradient Descent

The idea of gradient descent is to traverse a function $f_{LR}(\textbf{w})$ and find a local maximum or minimum for a set a values $\textbf{w}$. Gradient descent is an iterative process. At each iteration you will evaluate the function given your current set of values. Then you will take the derivative of that function with respect to those values to see how much each value contributes to the slope of the function. We can then change the values in a proportionate way to move towards this optimal point.

The gradient descent equation is described as

$\textbf{w}^{(k+1)} = \textbf{w}^{(k)} - \rho \frac{\partial f_{LR}(\textbf{w})}{\partial \textbf{w}^{(k)}}$

where $\rho$ is the learning rate, usually small number. A constant which determines the speed at which we want to change the values we are optimizing.

Initializing the values

There's many ways to initialize these values. We can either set them all to zero, or set them randomly.

Then you can take a random instance in your dataset $x_i$ and $y_i$ and compute the derivative

$\frac{\partial f_{LR}(\textbf{w})}{\partial \textbf{w}^{(k)}} = \textbf{x}_i (-y_i \frac{e^{-y_i \textbf{x}_i \textbf{w}}}{1 + e^{-y_i \textbf{x}_i \textbf{w}}})$.

Once the compute this you can put the result into the gradient descent equation and update all your weights.

You then continue to go through this process until your weights $\textbf{w}$ converge to a value, or some other condition is met. You might want to limit your algorithm with some iteration counter to avoid infinite loops caused by weights that do not converge.

Gradient Descent Code

Here is an example using gradient descent to train weights along the logistic regression loss function.

import numpy as np

def update_weights(x_i, y_i, w):
   p = 0.8                  # The learning rate
   yhat = predict(x_i, w)   # The predicted target
   error = y_i - yhat       
   return w + p * (y_i - yhat) * x_i  # Update the weights

def predict(x_i, w):
   return 1/(1+np.exp(-1 * np.dot(w.T, x_i)))

def train_weights(x, y, verbose = 0):
   w = np.zeros((x.shape[1],))
   w_temp = np.zeros((x.shape[1],)) 

   epoch = 0
   while epoch <= 1000:
      for i, x_i in enumerate(x):
         w = update_weights(x_i, y[i], w)

      pred = 1/(1+np.exp(-1 * np.dot(x, w)))
      error = np.sum(pred - y)

      pred[pred < 0.5] = 0
      pred[pred >= 0.5] = 1
      epoch += 1

      if verbose == 1:
         print('Targets: ', y)
         print('Predictions: ', pred)
         print('Predictions: ', pred)

      # Check if we have reach convergence
      if np.sum(np.abs(w_temp - w)) < 0.001:
         return w
         w_temp = w
  return w

# Create some artificial database
x = np.zeros((4,3))
y = np.zeros((4,)) 
x[0] = [1, 1, 1]
x[1] = [1, 2, 2]
x[2] = [1, 10, 10]
x[3] = [1, 11, 11]
y[0] = 0
y[1] = 0
y[2] = 1
y[3] = 1


# Train the weights
w = train_weights(x, y, 0)
print('Trained weights: ', w)

# Get predicitons
pred = 1/(1+np.exp(-1 * np.dot(x, w)))
error = np.sum(pred - y)   
pred[pred < 0.5] = 0
pred[pred >= 0.5] = 1
print('Predictions: ', pred)
  • 1
    $\begingroup$ Any possible update on my implementation respect to the problem that I stated above? Plus how can I implement incremental SGD sequentially? Would it possible for you to update your motivated answer with the possible code? Thanks for your help. $\endgroup$
    – Andy.Jian
    Commented Jan 25, 2018 at 10:55
  • $\begingroup$ Yah I'll append some code, one sec. $\endgroup$
    – JahKnows
    Commented Jan 26, 2018 at 2:03

I don't quite understand this algorithm

Actually, before 2020 nobody (in this world) understood it. But from June 2020 there is a paper from our Lab (https://richtarik.org/) that describes this method: https://arxiv.org/abs/2006.05988

Of course, it's for you if you want to understand why this method actually works and in what sense it works... (published in NeurIPS 2020)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.