I am training a binary classifier (e.g. logistic regression) on some multidimensional problem. I have tried leave-one-out and k-fold cross-validation. I have tried L1 and L2 regularization, and I have produced plots sweeping the regularization parameter over multiple orders of magnitude.
The typical behaviour is that for some range of regularization parameters the testing error significantly improves. However, I have some datasets where the testing error stays below chance (e.g. below 40%) for all values of the regularization parameter, whereas training error transitions between 100% and chance.
What does that mean? Is this expected for datasets that are not predictive of the labels? Or is this an indication that there is overfitting happening and that L1/L2 regularizers are potentially suboptimal for those datasets?