Does a targets-permutation test prove that regression find a real pattern? I need to solve a standard ("vanilla") regression problem meaning that I have a 2D array of real-valued features (X) and 1D array of real-valued targets (Y). I use this data to train a simple regression model (let say a linear model or a simple decision tree).
Since my data are very noisy, I am not sure that there is any pattern in the data at all. In other words, it might be the case, that what I have is only noise and there is absolutely no dependency of my targets on my features. To exclude this possibility, I came up with the idea of the following test:

*

*I randomly permute all my targets so that, per construction, I destroy any possible relation between features and targets. For example, the first features-vector gets 137-th target, the second features-vector gets 34-th target and so on.

*I use these (fake, synthetic) data to fit my model again and I record its accuracy (for example squared deviation).

*Then I permute my targets again and run a fit again. I do it 10 000 times and check how often my accuracy on "fake" (synthetic) data is as good as, or even better, than accuracy achieved on real (original) data.

I was happy with this test. I said that, if accuracies obtained on the "fake" data is almost never better than accuracy achieved on the "real" data, then we can say that there is some dependency of targets on features in my data set. So, my model does something meaningful and not just overfitting by finding some "fake" patterns in pure noise.
However, I am not sure anymore about my interpretation. I guess that the only thing that I prove, is that the distribution of targets depends on features and it does not necessarily mean that the mean of this features-dependent distribution depends on features!
By minimising squared deviation I search dependency of mean on targets but my test probably does not guaranty that the found dependency of mean on features makes any sense. Maybe mean is not features dependent but standard deviation (or kurtosis, or skewness or other property of distribution) is and, this is why accuracy achieved on the real data is almost always better than accuracy achieved on the fake data.
Are my concerns valid?

Your idea does work.
This can be viewed as a type of Monte Carlo simulation where you randomly pick a set of points from the target distribution and regress to them, and you get a distribution of MSE. you can then check if the MSE you get for the real target distribution is significantly lower than from a randomly assigned distribution.
The common way of doing it is called "permutation feature importance" where you shuffle a feature instead of the target, and it's used mainly for nonlinear estimators like trees, random forests, etc.
It would be better though to actually randomly assign targets from the distribution of targets and not just permuting them.
But I'm not sure why you would do this instead of just checking that the regression coefficients you get are significantly greater than zero for linear regression.
