My ReLU network fails to launch So I have a problem.  Simple situation: Fully-connected Multi-Layer Perceptron with Rectified Linear (ReLU) units (both hidden and output layers), 1 hidden layer of 100 hidden units, trained with backprop on MNIST with minibatch_size = 1 and MSE loss (to 1-hot target vector), initial weights drawn from $\mathcal{N}(0, 0.01)$.  I'm doing this because I'm experimenting with variations on this type of network.
Now, if I set the learning rate above some threshold (in my case around 0.06), I get a very strange learning curve (see pictures).  Basically, my network starts off ok, then kind of just ... gives up.

x-axis: Epoch of training
y-axis: Score on test (solid) and training (dotted) sets at various points through training.  Each colour represents a network trained from the same initial weights, but with a different learning rate.
The weights are not exploding to infinity or anything, as the plots below show.

Weights from two of the above networks after training.
Top row: weights of failed network with eta=0.07
Bottom row: weights of successful network with eta=0.05
Left column: Weights from input to hidden (reshaped to dimensions of input images)
Right column: Weights from hidden to output.
So it seems that there's some invisible threshold where if you cross it, everything goes to hell.  The trouble is I don't understand how to determine the threshold, or what the real cause of failure is.  Even changing the random seed can cause the network to train successfully or fail.  Does anyone have experience with this phenomenon or know of a paper that examines/explains/proposes a solution for this problem?
EDIT
So, I've identified the problem, but have not yet found the solution.  The problem is that output units will sometimes get pushed into a regime where they are "dead" - that is, not responsive to any input.  Once they're dead, they're dead - all gradients from that unit become zero, and therefore they can not learn to be useful again.  They can more easily be pushed into this regime when the learning rate is higher.  An obvious solution is to use a softmax output layer, but that isn't applicable to my particular problem.    
 A: 
The problem is that output units will sometimes get pushed into a regime where they are "dead" - that is, not responsive to any input. Once they're dead, they're dead - all gradients from that unit become zero, and therefore they can not learn to be useful again.

This is a well-known problem with ReLU units. As work-arounds, some folks have designed alternative activation functions which are largely similar, but do not have a flat gradient. The Leaky ReLU function $L$ is probably the simplest
$$
L(x) = 
\begin{cases}
x &\text{if}~x > 0\\
\alpha x &\text{otherwise}
\end{cases}
$$
where $0 < \alpha< 1$ is some constant chosen by the user, usually something like $\alpha=0.2$. This always has positive gradient, so the weights can always update.

They can more easily be pushed into this regime when the learning rate is higher.

This thread addresses your observation about larger learning rates.


*

*the reason that the larger gradient flowing through an ReLU neuron can cause it to die
A: Lately there has been some work on why deep learning is successful.


*

*Loss Surfaces of Multilayer Networks

*Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
are some good references, and of course the references therein. 
Roughly it seems that high dimensional optimization problems, which frequently occur in deep learning, are hypothesized to have better optimization landscapes. 
For example, consult Figure 3 in the first link. Notice that the local minima obtained by wider MLPs (more parameters, higher dimensional optimization problem) have their local minimas banded much closely together than with the thinner nets. 
Further note that they did an experiment similar to yours, i.e. n = 100 hidden units and they have quite a wide band in local minima values. 
That's from a theory perspective. From a computational perspective, can you try bumping up the number of hidden units, and perhaps even the number of hidden layers? You might start to see that training the network is less and less sensitive to your step size (within reason of course, choosing step size 1e+10 is probably a bad idea). 
Geometrically, perhaps shallower/thinner networks have much more "treacherous" optimization landscapes and can get caught in these sorts of local minima. 
