How can I fix this "convex" problem ? Is it just a matter of overfitting?
Yes, what you are seeing is a classic case of overfitting. 

You stated that you use a linear model such as logistic regression. To regularize these types of models, usually L1 and/or L2 regularization is applied. L1 regularization is simply $||W||_1$ and L2 is $||W||_2^2$ usually.

Another method is to alter the labels of the model in a specific way, which is a method of regularization I created (shameless plug). Here is the link to the paper: https://arxiv.org/abs/1609.06693

Hope this helps.