Why normalizing the data gives worst cross validation error but better testing error? I have used cross validation on my training set to choose the parameters that gives the lowest error for different machine learning models. I then used these models to predict the target values of my testing set and then calculated the error.
I tried normalizing the data and went through the same process as above, but I was surprised to see that my normalized cross validation error was worst than my not normalized cross validation error. However, my normalized testing error was better than my not normalized testing error.
Should I go with the normalized or not-normalized data?
 A: Normalisation is mainly intended to create model stability by standardising value scales and to remove sources of absolute variability in favour of exploring relative variability.
Your results suggest that not normalising prior to training means that the model has to include adaptations to overcome the variation that otherwise would be controlled by normalisation. Because it is a training set it can find very powerful rules to minimise this unwanted variation in the training at so appears to perform well under cross validation. 
The fact it falls apart in independent validation shows that whatever rules it had learned to cope with unnormalised data are not generalising to the validation set, I. E. It has an overfitted adaption. 
Stability of models in validation sets is far more important than any cross validation performance, so having a standardised normalisation procedure appears to be making a more stable and reliable model for you. 
Of course I am assuming errors are rising significantly in the unnormalised data and relatively stable in the normalised
Go with more stable model, with more emphasis on test set performance. 
A: An example where this can occur is regularised linear regression.
Normalising the data (like converting each regressor in a standard score $X_i^\prime = (X_i-\mu_{X_i})/\sigma_{X_i}$) changes the scale of the parameters. This will have an effect on the coefficients which scale similarly with a same rate. For instance the OLS solution
$$\hat{y} = a + b_1 X_1 + b_2 X_2 + \dots b_n X_n$$ will change into
$$\hat{y} = a^\prime + b_1^\prime X_1^\prime + b_2^\prime X_2^\prime+ \dots + b_n^\prime X_n^\prime$$
with $b_i^\prime = \sigma_{X_i} b_i$.
And if you regularise based on the sizes of the coefficient, which now have changed, then you will get a different training (and testing) result. Effectively you are changing the regularisation term in the cost function

*

*A parameter with large $\sigma_{X_i}$ would before the normalisation have a large influence on the model for a small coefficient, and after normalisation this influence will be reduced.
If the relevant parameters in your model (the ones that are related to the true model or are good general predictors and not noise) are with large $\sigma_{X_i}$ then the normalisation will decrease the quality of the model.


*In addition the optimum/minimum error in the test data may be achieved with a lower degree of regularisation. (because the bias has become stronger)  And this you may observe as the training error improving at a given testing error.
