5
$\begingroup$

At 8:30 of this video Andrew Ng mentions that the cost function for stochastic gradient descent (for a single observation) for logistic regression is

$-y_i \log h_w(x_i) - (1 - y_i) \log h_w(1 - x_i) + \frac{\lambda}{2} ||w||^2$

My question (a rather technical one) is about the regularization term. If the cost function for all observations is

$\sum_{i=1}^n \{-y_i \log h_w(x_i) - (1 - y_i) \log h_w(1 - x_i)\} + \frac{\lambda}{2} ||w||^2$

should the cost function for a single observation be

$-y_i \log h_w(x_i) - (1 - y_i) \log h_w(1 - x_i) + \frac{\lambda}{2n} ||w||^2$

? In other words, the regularization term is divided by $n$; it is "spread out" across all observations. I know its rather technical as $\lambda$ can easily be changed, but I want to make sure I get the concept right.

$\endgroup$
4
$\begingroup$

First I would recommend you to check my answer in this post first.

How could stochastic gradient descent save time comparing to standard gradient descent?

Andrew Ng.'s formula is correct. We should not use $\frac \lambda {2n}$ on regularization term.

Here is the reason:

As I discussed in my answer, the idea of SGD is use a subset of data to approximate the gradient of objective function to optimize. Here objective function has two terms, cost value and regularization.

Cost value has the sum, but regularization term does not. This is why regularization term does not need to divide by $n$ by SGD.


EDIT:

After review another answer. I may need to retract what I said. Now I think both answers are right: we can use $\frac \lambda {2n}$ or $\frac \lambda {2}$, each has pros and cons. But it depends on how do we define our objective function. Let me use regression (squared loss) as an example.

If we define objective function as $\frac {\|Ax-b\|^2+\lambda\|x\|^2} N$ then, we should divide regularization by $N$ in SGD.

If we define objective function as $\frac {\|Ax-b\|^2} N+\lambda\|x\|^2$ (as shown in the code demo). Then, we should NOT divide regularization by $N$ in SGD.

Here is some code demo, we are using all data in SGD, so it should be the exact gradient.:

# ------------------------------------------------------
# data, and loss function, and gradient
# ------------------------------------------------------
set.seed(0)
par(mfrow=c(2,1))
n_data=1e3
n_feature=2
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)

sq_loss<-function(A,b,x,lambda){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1]/(2*n_data)+lambda*crossprod(x))
}
sq_loss_gr<-function(A,b,x,lambda){
  e=A %*% x -b
  v=t(A) %*% e
  return(v/n_data+2*lambda*x)
}

# ------------------------------------------------------
# sgd: approximate gradient using subset of data
# ------------------------------------------------------

sq_loss_gr_approx_1<-function(A,b,x,nsample,lambda){
  # sample data and calculate gradient
  i=sample(n_data,nsample)
  gr=t(A[i,] %*% x-b[i]) %*% A[i,]
  v=matrix(gr/nsample,ncol=1)
  return(v+2*lambda*x)
}

sq_loss_gr_approx_2<-function(A,b,x,nsample,lambda){
  # sample data and calculate gradient
  i=sample(n_data,nsample)
  gr=t(A[i,] %*% x-b[i]) %*% A[i,]
  v=matrix(gr/nsample,ncol=1)
  return(v+2*lambda*x/nsample)
}

x=matrix(runif(2),ncol=1)
sq_loss_gr(A,b,x,lambda=3)
sq_loss_gr_approx_1(A,b,x,nsample=n_data,lambda=3)
sq_loss_gr_approx_2(A,b,x,nsample=n_data,lambda=3)

The function sq_loss_gr_approx_1 is right. Because loss function is v[1]/(2*n_data)+lambda*crossprod(x) but not (v[1]+lambda*crossprod(x))/(2*n_data)

> sq_loss_gr(A,b,x,lambda=3)
         [,1]
[1,] 3.317703
[2,] 4.969016

> sq_loss_gr_approx_1(A,b,x,nsample=n_data,lambda=3)
         [,1]
[1,] 3.317703
[2,] 4.969016

> sq_loss_gr_approx_2(A,b,x,nsample=n_data,lambda=3)
          [,1]
[1,] 0.1325575
[2,] 0.1597326
$\endgroup$
  • 2
    $\begingroup$ ... then the gradient becomes dominated by the regularization term for a fixed value of $\lambda$, and the answer winds up much closer to $0$ than it would if you used all the data. $\endgroup$ – jbowman Dec 16 '16 at 20:34
  • 2
    $\begingroup$ To add to my comment above with a simple example not specific to logistic regression. Assume we have 1 million arbitrary functions $f_i(x)$. The derivative of the sum is $\sum_{i=1}^{1e6}df_i(x)/dx$. We'll add a regularization of $||x||$ with derivative $x$. $(\sum_{i=1}^{1e6}df_i(x)/dx) + x$ is not likely to be well approximated by $df_1(x)/dx + x$. $\endgroup$ – jbowman Dec 16 '16 at 20:52
  • 1
    $\begingroup$ @hxd1011 the meaning of $\lambda$ will not be standard in the second case ( where you do not divide by N). If one implementation divides by $N$ uses a $\lambda$ of 0.1, what is the equivalent $\lambda$ for the non-divided case? Its clear that $\frac{\lambda}{N}$ or just $\lambda$ is just a constant and any appropriate value will work, but that's not the full picture. Do you keep adjusting the $\lambda$ (for the non-divided case) for every new data set? $\endgroup$ – A.D Dec 16 '16 at 21:57
  • 2
    $\begingroup$ I think that mathematically you need to divide by $N$ to make the OP's two expressions equal. For a convex problem where SGD converges to the global minimum (w/annealing, etc.), then the $N$ factor would be required to converge to the optimum of the stated objective function as well. I will say that in practice when I do this sort of problem (for things like this) I tend to scale the regularization parameter by $N$ anyway, after determining an appropriate magnitude in the "single sample case", essentially to make the "units line up". $\endgroup$ – GeoMatt22 Dec 16 '16 at 22:11
  • 1
    $\begingroup$ I think you've got it now, with your two variants of the objective function leading to different conclusions about the $\lambda /N$. $\endgroup$ – jbowman Dec 17 '16 at 1:13
2
$\begingroup$

It looks like you are asking about how regularization might be applied in the case of stochastic gradient updates i.e. updating for one training example at a time.

Your idea to divide the regularization term by number of data points $N$ (you use $n$) is correct. I also checked this paper, and it appears to say the same. The loss or cost is defined by $Eq. 2$ and in section 3 (see the first equation in sec. 3) they show an update of the weights $w$ for a single training example, they have clearly divided the regularization term by $N$. Thus the loss for a single example is also divided by $N$.

$\endgroup$
  • $\begingroup$ Given the other answers, I don't think it is correct $\endgroup$ – wwl Dec 16 '16 at 20:33
  • 1
    $\begingroup$ @wwd - did you look at the paper? It's quite clearly correct. $\endgroup$ – jbowman Dec 16 '16 at 20:47
  • 1
    $\begingroup$ when you report $\lambda$ for sgd you should divide by $n$ IMO. If you have a million samples examples, and claim to use a $\lambda = 0.1$ you should be regularizing each update with $1.0e-7$. Of course, you can change $\lambda$ to be very small but this is incorrect or at least not the standard. there are fairly standard ranges of $\lambda$ that is used 0.1 0.01 etc. Based on the answer you accepted $\lambda$ will depend on $N$ which seems wrong. $\endgroup$ – A.D Dec 16 '16 at 20:49
  • 1
    $\begingroup$ @wwl you may want to review what you accept as correct, based on new discussions. $\endgroup$ – A.D Dec 16 '16 at 22:20
1
$\begingroup$

I always viewed the regularizer separately from the loss. Most machine learning problems come in the form of "Regularizer + Empirical Risk", where Empirical Risk means the arithmetic mean of the sum of the loss of every training sample.

What you mean by "spread out across all observations" probably is that when you take the stochastic gradient of a single sample with respect to the weights, then you have to also consider the regularizer which does not get "spread out"/averaged.

Compare gradient of regularized GD:

$\nabla_w~\lambda~Regularizer(w) + \nabla_w n^{-1}\sum_{i=1}^{n}loss_i (w) $

to regularized SGD (only one element of the sum is considered):

$\nabla_w~\lambda~Regularizer(w) + \nabla_w loss_i (w) $

Short: In my opinion it makes sense to separate the terms "regularization" and "cost" (which I named "Empirical Risk" for the full data and "loss" for one sample)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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