Convergence of batch gradient descent in logistic regression

Regularization is designed to combat overfitting, but not aid in gradient descent convergence.

If you are minimizing a function JJ parameterized by vector θθ and where each element of θθ is identified by θjθj, (i.e. minimize J(θ)J(θ)).

Then the basic idea in batch gradient descent is to iterate until convergence by computing a new value of θθ from the previous one in the following way. Updated each θjθj simultaneously with the formula.

θj:=θj−α∂∂θjJ(θ)θj:=θj−α∂∂θjJ(θ)

That αα term is called the learning rate. It's arbitrary and if it's very small then the algorithm will converge slowly which will make the algorithm take a long time, but if it's too large, then what can happen is exactly what you are experiencing. In this case θθ will be updated in the right direction, but will go too far and jump past the minimum or it can even climb out and increase.

The remedy is to simply decrease αα until it doesn't happen. A sufficiently small learning rate guarantees that J(θ)J(θ) will decrease on every iteration. The trick is to determine what value of αα is a good one that allows fast convergence but avoids non-convergence.

A useful approach is to plot J(θ)J(θ) while the algorithm is running to observe how it decreases. Start with a small value (e.g. 0.01) increase it if it appears to result in slow convergence or decrease it still further in the case of non-convergence.