Finding degree of polynomial in regression analysis I am working on a machine learning project where I am trying to fit a curve on data. Unfortunately the date has somewhat high feature vector. So, I can't really plot them on a 2D or 3D space to guess how the shape of the data looks like. 
So, other than hit and trial, does there exist a mathematical way to find degree of polynomial that might best fit my data. 
I mean I do know that I can look into a least square error for each degree and then choose the one with the minimum error, but then it will be a double optimization problem as the first optimization loop would consist in finding a set of weights for the curve that fits the data, while the second loop would be used to check the degree. Any suggestions?
 A: Sorry if this is too elementary, I just wanted to make this answer as self-contained as possible. In fact, you can't do what you're describing: the best polynomial of degree $k+1$ will always fit at least as well as the best polynomial of degree $k$, since the set of $k+1$ degree polynomials includes all $k$ degree polynomials (just set $a_{k+1} = 0$). As you continue to increase $k$, at a certain point you will be able to find a polynomial that fits the data perfectly (i.e. with zero error).
This usually isn't a very attractive solution because it's hard to imagine a process that ought to be described by e.g. a million-degree polynomial, and it's almost certain that this kind of model will be more complex than is necessary to adequately describe the data. This phenomenon is called overfitting, and a good example is this Wikipedia image. The data is clearly close to linear, but it's possible (but not desirable) to get a lower error with a more complex model.

In general, the goal is to minimize the error that would occur on new data from the same underlying model, rather than on the current set of data. Often it isn't possible or practical to just get more data, so usually one would employ some form of cross-validation to find the model that generalizes the best to unseen data. There are lots of forms of cross-validation, and you can read about them in the Wikipedia article or in numerous answers on CrossValidated (ha!). But in effect they all can be reduced to: fit a model on some of your data and use this to predict the values for the remainder of your data. Do this repeatedly and choose the model (in this case, the degree of polynomial) that gives you the best performance on average.
A: One of the ways to solve this "search" problem is to first start with some meta-heuristic algorithm like Genetic Programming and once the program is able to create a "near" function (of decent fitness), start with traditional machine learning regression algorithms of degree identified by GP. You will still need to perform cross validations for fitting your n-degree polynomial model.
Few things you need to make sure while running GP is that not to provide functions which should not be used else GP has the tendency to create complex models mimicking decision tree + linear + quadratic etc.
