Why do I get different results each time I run my algorithm? I'm doing machine learning with a training set, validation set and test set.
I train with the L_BFGS algorithm. The training converges all the time. I have the default accuracy from scipy, which is quite high.
Then I have a regularization parameter that I optimize on the validation set. I do this with grid search. For efficiency reasons, the way I implemented is that after each iteration during validation, I start from the weights used for the previous training. 
Therefore, I don't start each training with zero or random weights. I do this because I think the training algorithm finds the minimum faster this way, because it has a good guess.
Now I have this result which I don't understand. 
Doing grid search [0, 40] 
set param to 0 
training, converged! 
measure validation error 
set param 40 
training, converged! 
measure validation error 
Best param is 40, lowest valid err: -8916, training error:-35274

Now I do the same thing but only with param 40
Doing grid search [40] 
set param 40 
training, converged! 
measure validation error 
Best param is 40, lowest valid err: -5214, training error:-41428   

So in the second case, I started training with param 40 with weights all zero. In the first case, I started training with weights that came from training with param 0.
If I used LBFGS with high accuracy, shouldn't it give me the same result with param 40 in both cases? How come the training and validation errors are so different? If I don't get the same result, is it likely that I have a bug in my code?
As an explanation, I was thinking that LBFGS gets stuck in a local minimum based on the starting weights, but I'm not sure. If that's the case, how do I prevent this? Am I supposed to start from some random weights every time? When can I be relatively sure that LBFGS has indeed found a global minimum?
 A: The current practice is to start with random weights and re-run it some number of times, then select the result that has both minimum error and minimum number of parameters.  If your parameter count is constant then you just go for low error.
If you are splitting your training versus test samples randomly then you will also get some noise in the final result.  Don't let it stress you.
If you look at the distribution (think histogram or eCDF) of your errors from your tests and the lowest value is an outlier then you may have too few tests, or you may have other convergence issues.  There are usually multiple stopping criteria including iteration count, time, and change in result (error rate).  Make sure that you at least wiggle those other controls a little to verify you are doing things properly.
I was reading about convolutional networks for image processing and they recommend elastically deforming the training set to make a synthetic but larger training set.  If you know enough about your data then you might be able to blur, stretch, or otherwise extend it similarly to get better convergence and more robust performance from your network.  Mileage may vary.
Keep in mind that the real world is messy.  There is noise everywhere.  Perfect solutions are rare, but "Good enough" solutions are plentiful.  Think about what you are trying to do with the network and what makes a "good enough" solution and aim for that.
