Why does L2 regularization smooth the loss surface? Fitting neural nets with L2 penalization, I've noticed that I often attain lower in-sample mean-squared errors with higher rates of L2 "weight decay", then I do with lower rates of L2 weight decay.  
Say I train a network to convergence using a small $\lambda$ -- say $2^{-8}$ --  save the weights and then use them to initialize a network with $\lambda = 2^{-7}$, moving upwards until $\lambda$ gets so big that all the weights go to zero.
One would expect in-sample MSE to increase monotonically.  But it doesn't.  
I guess this reflects the algorithm being more prone to local minima defined by "crevasses" in a few dimensions.  Is that the case?  
Is this phenomenon general, and therefor able to be formalized?
 A: You have to be careful here. By re-initializing the network using your current weights you are essentially starting at what was the minimizer of your training error from the previous initialization, and moving downhill from there. By incrementally increasing your $\lambda$ you are making your error surface slightly smoother (ie less informed by the noisy data) and so we would expect random initializations to have higher in-sample MSE, but you are not randomly initializing. 
As @Sid pointed out, the loss functions of neural networks are nonconvex, and our intuition is worse than useless as a basis for understanding how gradient-based algorithms will work in these high dimensional non-convex systems. Recent papers, (ex. Dauphin et al., Kawaguchi, among others) address this issue and use theory developed in the Physics community back in the 1950s to show that in high dimensional problems like neural networks the error surface is typically rife with saddle points rather than local minima. 
Using that understanding as a basis for answering your problem, I suggest that at each initialization you are stopping at a saddle point. You then make your loss surface slightly smoother and begin moving downhill again before ending at another saddle point (or, perhaps, the global minima). At some point, of course, the smoothness (regularization) penalty outweighs the gains in performance and your in-sample MSE begins to go up as the penalty of the weights begins to outweigh the actual noise in your data, ultimately ending with weights that are a vector of zeros. 
Edit:
Incidentally, I recently came across a recent paper by Hazan, Levy, and Shalev-Schwartz that describes the opposite of what you are doing -- beginning with high regularization and gradually lowering it with restarts at the solution from the previous stage. They are proving results from a method outlined in 1987, called graduated optimization. Here is an excerpt from the introduction:

Initially, a simpler
  coarse-grained version of the objective is generated and
  minimized. Then, the method progresses in stages, gradually
  refining the versions of the objective, and using the
  solution of the previous stage as an initial point for the optimization
  in the next stage.

As mentioned above, it is plausible to expect that regularization in your direction would have the behavior you observed due to the fact that you land on a saddle-point at the end of each stage and move off of it. Though the analysis of this paper confirms the natural intuition that Sid has pointed out, that it is preferable to work in the other direction.
A: Slight addendum to my previous answer: The more I think about what you have written, the more I get the feeling you have made a mistake somewhere.  Let $L(x,W)$ be the loss function and $R(W,\lambda)$ be the regularization. For $\lambda_{1} < \lambda_{2}$, for the 2-norm, if $W$ is the optimal weight with regularization $\lambda_{2}$ we have
$R(W,\lambda_{2}) \geq  R(W,\lambda_{1})$
Therefore, given a ${\it{fixed}}$ input, $x$, 
$L(x,W) + R(W,\lambda_{2}) \geq L(x,W) + R(W,\lambda_{1})$.
Therefore 
$L(x,W) + R(W,\lambda_{2}) \geq inf_{w} \mbox{  } L(x,W) + R(W,\lambda_{1})$
Therefore the loss absolutely has to be a monotone function of $\lambda$. Please check your code; either there is a mistake or you have not chosen the starting points properly
A: The truth is that the loss function in neural nets is highly non-convex, and no one has a real intuitive sense for what the "optimal point" really means. There is a recent paper (https://openreview.net/forum?id=ryQu7f-RZ) which shows that ADAM need not converge. 
To see how researchers think of the contour see http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf. 
