Datasets that "simple" models fail but more complex models work Notes:

*

*The term "simple" in this context is defined at the end of the question;

*I believe this question is somehow not about dataset request even if its title is named this way...

Main body:
Datasets I have seen usually fall within one of the following three categories:

*

*"simple" models work (i.e., prediction consistently better than random guess, even by a tiny margin such as 1%), machine learning/deep learning models work
better

*"simple" models work, machine learning/deep learning models
are more or less the same

*"simple" models don't work (i.e., prediction not better than random guess), machine learning/deep learning models don't work either.

This rule does not only apply to tabular data but also apply to some simple image classification tasks as well (but yes, you may argue that underlyingly images are tabular data as well since we flatten the high-dimensional data to 1-D array anyway). I tried cats and dogs classification--logistic regression can do better than random guess although it is much worse than CNN (so it falls to category I). Since I work mostly with tabular data, I did not try some even more complicated image classification tasks.
Let's say we discuss only supervised classification using tabular datasets, that is, the datasets with a few (or a LOT if you wish...) columns as X and one categorical column as y. Under this constraint, do you know any publicly available or synthetically generated datasets with which a "simple" model does not work at all but a more complex model can do better (even just slightly) than random guess?
In the context of this question:

*

*"simple" means linear models (e.g., OLS, Ridge, Lasso, Logistic, etc) plus decision tree and k-NN. These models are considered "simple" mostly because they are computationally inexpensive;

*"linear" means linear with respect to X and no feature engineering, such as $x_2 = x_1^2$, is allowed. So that one can not add non-linearity to the model by manually creating new features from old olds--I believe this makes my question easier; otherwise feature engineering allows OLS to go much further;

*I confine the question to classification tasks only because the meaning of "random guess" is not very clear for a regression problem (we guess by mean? median? mode? frequency? how about continuity and differentiability?) Please let me know if I am wrong;

*Overfitting control techniques such as cross validation are allowed just in case the synthetic dataset tries to trick a simple model into severe overfitting, which is not the intent of this question;

*SVM, Gradient Boosting, etc are not considered "simple", but suppose you have a dataset or you can generate a synthetic dataset which fails these models but cannot fail a neural network, I will be even more interested to know what such dataset looks like.

Datasets tried:

*

*vanilla hand-written digit recognition: Category I

*obfuscated hand-written digit recognition: Category I

*obfuscated hand-written digit recognition with binary label: Category I

EDIT 1: The original term "linear" is changed to "simple", which reflects what I want to ask more accurately;
EDIT 2: k-NN is added to the list of "simple" models.


Let's say we discuss only supervised classification using tabular
datasets, that is, the datasets with a few columns as X and one
categorical column as y. Under this constraint, do you know any
publicly available or synthetically generated datasets with which a
"simple" model does not work at all but a more complex model can do
better (even just slightly) than random guess?

I believe that any such example would have to be so contrived that you are very unlikely to see it in real life.
If by "better" you mean in terms of classification error, you can actually get close to a proof of this fact by using the Cover-Hart inequality.
(The Cover-Hart inequality says that in a two-class classification problem, the error of a 1-nearest neighbour classifier is asymptotically not worse than twice the Bayes rate. Here the "Bayes rate" is the lowest possible error for any classifier, and "asymptotically" means as the number of rows of your data set gets larger and larger.)
I know that your list of simple classifiers doesn't include 1-nearest neighbour, but in practice it seems that the performance of a decision tree is likely to be quite close to 1-NN, because both algorithms partition the feature space into regions around known data points in which the predicted value for y is constant. (Certainly, I think quite some work would be required in order to get an example in which a decision tree doesn't work at all, but 1-NN has some predictive power.)
So, the only hope for finding a data set like this in the wild would be to have a situation in which you had a very large number of columns, which might be something like image classification, or even better maybe something like an algorithm which inputs a chess position and outputs the best move.
Actually, isn't this chess thing an example? It has about 64 features and you have to predict a categorical y. It's known that it can be done with a neural network, but certainly I don't think that any simple algorithm could work. Wouldn't other games like backgammon also provide examples? Now I have confused myself.
