Train accuracy < Test accuracy with regularization

Question

With a friend we were playing with the notMNIST data, logistic regression and regularization.

Without regularization, we could achieve a training accuracy (10k samples) of 78%, and test accuracy (15k samples) of 82%.

With regularization, we achieve a training accuracy of 84% and a test accuracy of 88%.

I cannot understand these results: training accuracy is not higher than testing accuracy, so I think there is no overfitting. So, regularization shouldn't help much, but in our case we get a significant improvement.

Can you help me understand what is happening here? Thanks in advance

Answer 1

First, As I know, the training sample size is usually not less than the test sample size. However, it is not the case in your similation. Second, as comment as @gung - Reinstate Monica, how did you train the dataset, the cross-validaiton or other methods? Third, which kind of regularization you used, the LASSO, ridge or elastic net? The regularization is able to make a compromise between estmation variance and bias, thus usually obtain high testing accuracy.

Answer 2

This is only a guess, but I suspect the regularization is interacting with the logistic regression optimizer. In principle, if you can find optimal loss-minimizing parameters, regularization won't increase performance, and instead is likely to lower it (on the training set). However, for large data sets, there are typically stochastic or iterative solvers used to learn the regression parameters, and these will not generally find an optimal solution. For example, the sklearn default in python is LBFGS, a low-memory variant of a quasi-Newtonian iterative solver.

Intuitively, when you add regression, you may be restricting the optimization path to a smaller, "better behaved" region of the parameter space, making the optimizer work better in practice.

Answer 3

Did you look at the distribution of the classes... It may most likely be due imbalanced class distibutions. For example, if you sample contain two class labels 'A', 'B' and if 'A' occurs 80% of the times in your dataset. Assume that your classifier almost always classifies any test data as beloning to class 'A'. Then your training accuracy score is most likely to be around 0.8., However, since, you are chosing your test samples in random, if by some means, the number of samples belonging to Class 'A' is more than than the number of samples belonging to Class 'B', assuming a 90/10 ratio, then your test accuracy would be 0.9 i.e test accuracy > training accuracy.

Typically, you'd have a low cross validation score and if you are using python scikit-learn and use StratifiedKFold, for some values of K you would receive warning messages.