Randomly sampling parameters for model selection Suppose I'm fitting a complicated (e.g. neural network) model's parameters $\theta$ to some data $D$, and I'm trying to tune hyperparameters (e.g. number of layers, size of layers) $\eta$.
Normally I would solve $\max_\theta p(D|\theta,\eta)$, at least approximately, for a fixed $\eta$ and then do a grid search or ad-hoc search by re-fitting for different values of $\eta$.
\begin{align*}
\hat{\theta}(D, \eta) &= \mathrm{argmax}_\theta p(D|\theta, \eta) \\
\hat{\eta} &= \mathrm{argmax}_\eta p(D'|\hat{\theta}(D,\eta),\eta)
\end{align*}
Couldn't I instead just try out random parameters $\theta$ for each $\eta$ and see how they do on average?
$$ \int p(D | \theta, \eta) p (\theta| \eta) \mathrm{d}\theta
= \int p(D, \theta | \eta) \mathrm{d}\theta = p(D|\eta)$$
I could pick some priors $p(\theta|\eta)$ and then draw a bunch of random samples $\{\theta_1(\eta), \theta_2(\eta), \dots \theta_n(\eta) \}$ and solve
$$ \hat{\eta} = \mathrm{argmax}_\eta \frac{1}{n} \sum_i p(D|\theta_i(\eta), \eta)$$
I guess it's a type of Monte Carlo Empirical Bayes.
What gave me the idea is the following quote for Goodfellow, Bengio and Courville's "Deep Learning":

Saxe et al. (2011) showed that layers consisting of convolution
  followed by pooling naturally become frequency selective and
  translation invariant when assigned random weights. They argue that
  this provides an inexpensive way to choose the architecture of a
  convolutional network: first, evaluate the performance of several
  convolutional network architectures by training only the last layer;
  then take the best of these architectures and train the entire
  architecture using a more expensive approach.

I guess they fit some of the paramaters here, but I think it's related?
My questions are:
Is this a legitimate way of doing model selection/hyperparameter tuning


*

*In theory?

*In practice?

 A: First of all, this is not empirical Bayes. In empirical Bayes you estimate the priors from the data and then apply Bayes theorem (see nice example with further references). Unless I'm missing something, here you are not doing anything to estimate the prior distribution from the data, but rather assume some prior distribution.

Couldn't I instead just try out random parameters $\theta$ for each
  $\eta$ and see how they do on average?

What do you mean by "trying" different parameters in here? "Trying" sounds like you would like to take some random values for $\theta$ and evaluate the model on them. In such case, what would you be doing is taking samples from the prior predictive distribution of your model

In Bayesian data analysis (Gelman et al. 2013) the marginal likelihood
  is called a prior predictive distribution. This is because it presents
  our beliefs about the probabilities of the data before any
  observations are made. It is a distribution of the data computed as a
  weighted average over all the possible parameter values, and the
  weights are determined by the prior distribution.

This averages over possible results from your model, but tells you nothing about the optimal parameter values. There's also practical concern: in neural network you would usually have hundreds, thousands, or even hundreds of thousands, of the real-valued parameters, so the parameter space is very infinite. If you draw few hundred, or several thousand of the possible parameter values, this would be just a negligible fraction of all the possible parameter values and their combinations. Such Monte Carlo simulation wouldn't tell you much. Also, why looking at average performance in here? Why average over all the crappy results given the random parameters? Why not look at the best performance (i.e max, rather then average)? If you looked at best performance on the randomized parameters, this would basically be a random search.
What your procedure is lacking, is either maximizing the posterior probability (maximum a posteriori estimation), or sampling from the posterior (full Bayesian estimation), otherwise you are doing pure exploration. You may also be interested in reading about Bayesian optimization, just few days ago there was nice Distill tutorial by Agnihotri and Batara on it. In Bayesian optimization you also evaluate model on random parameters, but the parameters are carefully picked so to speed up exploration and finding the optimal ones.
There is also a related concept of neural networks with random weights. There are some results showing, that it is possible to find neural network architectures that perform well without training, using random parameters. In such case, comparing different neural networks with random parameters would make sense. This doesn't have to work in all cases, and is considerably harder problem, then "just" training the network, but it is at least theoretically possible. Even though, finding such architecture would need much more sophisticated algorithm then the kind of random search that you propose.
A: Interestingly, here is a Wikipedia commentary on Least-Absolute Regression, to quote:

Checking all combinations of lines traversing any two (x,y) data points is another method of finding the least absolute deviations line. Since it is known that at least one least absolute deviations line traverses at least two data points, this method will find a line by comparing the SAE (Smallest Absolute Error over data points) of each line, and choosing the line with the smallest SAE. In addition, if multiple lines have the same, smallest SAE, then the lines outline the region of multiple solutions. Though simple, this final method is inefficient for large sets of data, passes through at least k+1 points for regression involving k median-centered explanatory variables. 

Also, LAD is robust, and apparently the points producing the 'best line' are not impacted by outliers (think of the univariate case where LAD reduces to the data median and symmetric trimming of outliers is of no consequence), which implies the 'outer region' may be systemically ignored or minimized in the random sampling process. 
As such, guided (or censored, see this work) random sampling around a centroid region of two (x,y) data points, may actually be a strategy that returns a robust LAD estimate, or a result that may converge to it with increased sampling. In other words, there are paths to avoid sampling of extreme number of points.
So massive random sampling of points is inefficient, but one may be able to do better, and, in practice, the application of LAD itself does suggest bootstrap sampling to construct precision intervals on regression parameters.
