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?
 A: 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.
A: There are some issues with the type of used cost functions. For these issues see a previous second version of this answer. The current question is edited.
Your first fit already determined an effect that the mean is dependent on the features. Or at least expressing the mean as a linear function of the regressors gives a lower mean squared error than expressing the mean as a constant (and this indicates that a linear function is closer to the true mean of the population and a zero effect is not the true model).
The question that the permutations answer is not whether there is an effect and what the effect is (whether it is a difference in the mean or another difference in the distribution) but whether the observed effect is statistically significant. Statistically significant means that the observed effect in unlikely occuring in repeated experiments with different samples/data. These repeated experiments is what you simulated with the permutations.
If there is anything wrong with your method then it is not that the effect is not about the mean but that the significance might not be well approximated by permutations.

*

*For instance: is your data a collection of independent samples? If you have for example only two types of data points (say you measure a lot of people, but they are all from only two villages or other categories) and these are repeated many times, then your sample is effectively very small (it may not need to be about the number of observed people but instead about the number of observed villages). The same datapoints repeated many times in slightly different form makes you overestimate the sample size and you can easily get a false idea of a significant effect

