1) You don't evaluate the performance of the classifier at parameters outside of the chosen grid.  Essentially this relies on a continuity assumption, that the performance of a classifier at points "between" two grid points is comparable to the performance at the bounding grid points.  This seems reasonable as long as the grid is chosen finely enough.  If you want to get crazy it can probably be proven with the [inverse function theorem][1].

2) You seem to have a misconception about cross validation:

> If θ is given, then CV(θ) is actually the average error of $f_θ(x)$ on the whole 10 fold, i.e. the whole training data.

that last stretch of logic is not correct.  Here are two situations:

  - You train a model on the full training data.  Then you split your data into 10 folds, calculate the average error of the model predictions on the folds, then average the results.

  - You split the data into 10 folds, then *train the model 10 times*, each time leaving out one fold of the data.  For each of the 10 resulting models, you score the model on the data it was not trained on, calculate the average error for each, and then average the results.

The fist is the situation you can draw your conclusion from, the second is what cross validation actually does.  Cross validation calculates the expected out of sample error averaging over *training and testing* sets, not just testing sets.

3) You have your quantifiers reversed.  It is not:

> For each fold, calculate the optimal theta $\theta$.

It is:

> For each $\theta$, calculate the cross validation estimate of the out of sample error (average the out of fold errors).  Then choose that $\theta$ with lowest estimate.

Often once $\theta$ is determined, it is fixed, and the model is retrained on the entire training set.


  [1]: http://en.wikipedia.org/wiki/Inverse_function_theorem