# How to find parameters for ridge and lasso regularization when cost minimization does not converge?

In the Stanford ML course, we were taught to find good values for the lambda parameters of ridge/lasso by iterating for various lambda values on several cross-validation sets and picking the values which correspond to the hypothesis with the minimum CV error.

The problem is, I am playing with a big data set (which might not even be well suited for logistic regression (??): Internet Ads set) and I can't use the method described above because, during optimization, the cost stays stable (changes only around the 8th decimal place between iterations) and doesn't seem to converge.

I need good values for the regularization in order to converge, but I can't converge without the aforementioned good values.

Any suggestions? Should I move on to using SVM, or is this data set solvable with logistic regression?

NB: I am doing this for learning purposes, so I'm much more interested in explanations why my approach is bad than I am in black-box libraries which will give me a solution.

EDIT: Some relevant code snippets (occasionally pseudocode-ish, for clarity). The usual notations apply.

The function used to compute the cost:

def computeCost(theta, X, y):
global iter
iter += 1
if iter > 10:
raise TooManyIterationsException(iter) # Because the cost doesn't converge, I force interruption in order to jump to another combination of lambda values
m = y.size
h = sigmoid(X.dot(theta.T))
J = y.T.dot(log(h)) + (1.0 - y.T).dot(numpy.log(1.0 - h))
J_reg2 = theta[1:]**2
J_reg1 = theta[1:]
cost = (-1.0 / m) * (J.sum()) + LAMBDA2 * J_reg2.sum() + LAMBDA1 * J_reg1.sum()
print "Cost: ", cost
return cost


Invoking scipy.optimize.fmin_bfgs:

initial_thetas = numpy.zeros((len(train_X[0]), 1))
myargs = (train_X, train_y)

for LAMBDA1 in [0.01, 0.02, 0.04, ..., 10]:
for LAMBDA2 in my_range[0.01, 0.02, 0.04, ..., 10]:
try:
iter = 0
theta = scipy.optimize.fmin_bfgs(computeCost, x0=initial_thetas, args=myargs)
except TooManyIterationsException as e:
print '\n'


A typical output looks like this:

EDITED AGAIN: Evolution of thetas!

-
How is it possible that your cost is not changing? The only thing I can think of is that your lambda values aren't actually different. Maybe posting code for what you have done will help to see if your situation can be re-created. –  idris Apr 25 '12 at 5:45
@idris I have tried manually various combinations of lambdas, but the cost is always the same. In the meantime, I have found a couple other secondary issues with my implementation; if after fixing them I'm still having problems, I'll post the relevant parts of my code here. –  Cristina Apr 25 '12 at 11:44
@idris Added source code, as well as an output example. Thanks! –  Cristina Apr 25 '12 at 12:39
@Denis I'm not sure what you meant by +/- 1-5%... shall I increase/reduce each of my thetas by those percents and use cost with them modified? By the way, updated my post -- there's an interesting trend in the thetas. The value in theta[0] is shifted in the next cost computation to theta[1], then to theta[2], and so on. I'm not sure whether this is relevant, since I don't know the details of fmin_bfgs implementation. –  Cristina Apr 26 '12 at 11:23
@Denis Aha, now I understand! Thank you, this kind of debugging suggestion is invaluable -- I'll check it out! –  Cristina Apr 26 '12 at 12:54
show 1 more comment

Is the question "why is cost() so flat near [0 0 0 0] ?",
or "why does fmin_xx not find a minimum on a flat surface ?"
A couple of suggestions anyway:

1) look at cost() near x0, with look( f, x0, h ) -> f() at all corners of a cube of side 2h around x0, or if that's too many at a random subset.
2) is [0 0 0 0] a reasonable start point for weights ?
3) what happened to the first 3, continuous, columns of X ?
4) start with fmin() a.k.a. Nelder-Mead (at the best dim + 1 points from look()) before running fmin_xx -- more powerful but harder to drive.
5) scikit-learn SGDClassifier got to

97.3 % correct  SGDClassifier  uciml/ad*
X (1572, 1558) Xtest (787, 1558)  -- 2/3, 1/3 split
centre 3  -- scale all feature columns to [-1, 1]
sgditer 100  loss log  penalty l2
11 sec
Confusion matrix: 97.3 % correct = 766 / 787
True classes down, estimated across  / true class sizes
0:  652    8  /  660  99 %
1:   13  114  /  127  90 %

-
Thank you for the extra suggestions and for all the effort you've put into my question! I feel smarter than I was a week ago :-) –  Cristina Apr 27 '12 at 13:51

I don't understand why you have two $\lambda$ values. In all the logistic regression I've encountered, there is only one $\lambda$ value, and you try different values of $\lambda$ to minimize the cost $J$. I also took the machine learning class you reference, and my Octave code looked like this.

J = 1/m * sum(-y' * log(sigmoid(X*theta)) - (1-y)'*log(1-sigmoid(X*theta)));
J += lambda/(2*m) * sum(theta(2:theta_len,:).^2);


Note that lambda should be a scalar value in this implementation.

This is the math equivalent of the above Octave statement.

$J(\theta) = \frac{1}{m}\sum\limits_{i=1}^m[y^{(i)}log(h_{\theta}(x^{(i)})) - (1-y^{(i)})log(1-h_{\theta}(x^{(i)}))] + \frac{\lambda}{2m}\sum\limits_{j=1}^n\theta^{2}_{j}$

-
What we did there was ridge regression. Based on previous suggestions in another post, I was trying to implement here elastic net regularization, which is a combination of ridge and lasso methods. Hence, I need lambda2 for ridge, and lambda1 for lasso. –  Cristina Apr 26 '12 at 7:24
Ok, this is out of my wheel house as I am not yet familiar with elastic net. I do notice your (\theta) look to be pretty much all zero. Might be something work looking at. –  idris Apr 26 '12 at 15:02
Yeah, I have a couple of directions I want to follow now, the thetas are only one of them. Thanks a lot for the idea-bouncing! :-) –  Cristina Apr 26 '12 at 15:18