Random initialization/order in neural network — bias or variance? I'm puzzled about how to describe differences occurring between neural networks trained on the same data and with the same configuration. They differ only in the initial weights (different seeds used for random initialization) and in the random order in which they process the training data.
Are these two examples of bias or variance? I tend towards bias, as both effects have no connection to the data, yet only to the initial state of my model.
Thanks!
 A: In using a neural network model, you're solving a non-convex optimization problem by following the gradient down to a local minimum from a (random) starting point in the parameter space. Some solution might be different depending on the initial value of the weight matrices. But you don't know which local minimum would an initial value lead you to. So depending on the topology of the objective function, bias could result from these two sources of randomness. 
A: Imagine we want to fit a function by minimizing the squared error. The bias-variance decomposition (also see here) lets us write the total error as the sum of a squared bias term, a variance term, and an irreducible error term (the noise). Say we repeatedly sample training data from the true underlying distribution and fit a model using each training set. The bias measures the extent to which the learned function is systematically 'off' from the true function. It's given by the expected value (over possible training sets) of the difference between the learned function and the true function. The variance measures the extent to which the learned function varies across training sets. It's given by the expected value (over possible training sets) of the squared difference between the learned function and the true function.
Neural nets typically have nonconvex loss functions and are trained using local optimization routines. Parameters will therefore converge to different local minima, depending on how they were initialized. When using online learning methods like minibatch training or stochastic gradient descent, the order of the training data will also influence the local minimum that is ultimately obtained.
The question is whether random initialization and data order contribute to the bias or to the variance. Imagine the situation above, where we draw many training sets from the true underlying distribution. Randomizing the initial parameters or data order won't cause the learned function to be systematically different from the true function--if this were true, randomization would always cause the function to be 'off' in a similar direction, by a similar amount. Therefore, randomization doesn't contribute to bias. But, the learned function will certainly vary from run to run. Part of this variability will be due to fitting run-to-run fluctuations in the training data. But, another part will caused by the randomization. Therefore, randomization contributes to the variance.
These slides mention random weight initialization in neural nets as a source of variance. They mention that bias would be caused by things like using too few hidden units.
A: This is an interesting question.  I find it fascinating that there are already two answers that come to opposite conclusions that both are seemingly consistent.  Let me try to explain how that could be so.
When discussing these topics it's very important that we identify what is considered random and what is considered fixed in our situation.  Hastie, Tibshirani and Friedman put this very explicitly in their "Elements of Statistical Learning":

Discussions of error rate estimation can be confiusing, because we have to make clear what quantities are fixed and what are random (Indeed, in the first edition of this book, this section wasn't sufficiently clear).

For example, in the usual discussion of this sort we assume that the data $X$ are fixed (or at least conditioned upon), and the response given the predictors is random.  This assumption leads to the famous bias and variance decomposition of the least squared error, known to every serious student of statistical learning.
What about in your question?  I won't guess at your intenet, so there are two options:


*

*We consider the initial point to be random, that is, drawn from some distribution.

*We consider the initial point to be fixed, with the randomness coming only from the data we use to train.


Random Case: We are drawing our initial point at random from some distribution.  This distribution has some expectation, the expected initialization point.  We incur randomness in our process from the specific initialization point we choose, which varies around the model trained from the expected initialization point.  From this perspective, the choice of initialization point is model variance.
Fixed Case: We start the algorithm at the same point each time, and the randomness in our results is due to the data we use to train.   Each time, the ascent algorithm terminates at a local optima, which is more than likely not the global optima.  As we perturb the training data the local optima that is found varies continuously with the training data, so in this sense, for small perturbations of the training data, we end up at the same local optima every time(*).  This local optima is most likely not global, so we have consistently ended up at a sub optimal place, this is bias.
So, you see, it depends on your point of view.  It's very important we precisely set up our model of the situation if we would like to communicate these concepts clearly.
(*) This is the kind of thing you can prove with the inverse function or implicit function theorems from calculus.  There are assumptions involved, most likely that the second derivative of the loss function does not vanish at the local optima.  I spend a lot of time proving these things in my qualifying exams, but it has been a long time!
