Fairly comparing algorithms that require early stopping with others that don't

I am currently comparing many learning algorithms on a specific dataset. My methodology is:

• Split the dataset into a test set of size N/3 and a design set of size 2N/3
• Use k-fold cross validation on the design set to select the best parameters for each algorithm
• This gives you one "best" set of parameters for each algorithm, which you can then evaluate on the test set either by retraining on the full design set or by bagging all k models
• Ideally repeat with a new test/design split, but this is so expensive that I doubt I'll have the time to do it

This works fine for, say, SVM and GMM, but breaks down with algorithms trained by gradient descent such as neural networks. The usual way of training those is to do early stopping with a validation set. However, using the "real" validation set for early stopping would risk overfitting and give overly optimistic results. I can see a few alternatives to this:

• Do nested cross validation on the training set (too expensive; the particular type of neural network I am using already has twice as many hyperparameters as the other algorithms...)
• Set the number of iterations as a hyperparameter and try a few different values
• Add regularization like weight decay (yet another hyperparameter, and has never worked very well for me in terms of avoiding overfitting)

Another concern is with the initialization of the weights. I am currently initializing them by picking random values in the range +/- 1/sqrt(#inputs to layer) (as described here http://www.willamette.edu/~gorr/classes/cs449/precond.html). I tried varying the random number generator's seed and noticed that the range of final errors is quite large. How, then, am I to fairly compare this algorithm to the other ones that don't depend on a random seed? Try many seeds and average the final test error? Train with many different seeds and bag the models?

Any suggestions would be appreciated.