There are no hard-and-fast rules about what constitutes "over-fitting".
When using regression, heuristics are sometimes given in terms of the ratio of the sample size to the number of parameters, rather than the difference in predictive accuracy in-sample versus out-of-sample. E.g., in a regression context, I recall reading both 3 and 5 observations per observation being the minimum.
In predictive applications, the goal is to improve your out-of-sample prediction, so if you have a model that is 20% worse out of sample than in-sample, but still predicts better than a model that is only 1% better out-of-sample than in-sample, you should going to prefer the model that is over-fitted. Of course, in such a situation you will also want to find ways of reducing the over-fitting, while keeping the out-of-sample prediction constant.