3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think that your initial reaction was more correct... The non-convexity of the solution space means that @generic_user likely wasn't finding the optimal weight at each regularization step, but was probably getting closer at each initialization. This allows for the loss to decrease with each re-initialization. It would be less likely, though not impossible for the loss to decrease if the weights were randomly intitialized each step. In the case of a convex function where the optimization algorihtm is stopped at a (or $the$ in the case of strongly-convex) optima then your proof is correct. $\endgroup$ – David Kozak Feb 11 '18 at 2:04
  • $\begingroup$ If you follow a gradient descent, by definition you have to hit a local minimum/saddle point at the very least. If by "optimal" you mean global optimum then yes, he is probably not hitting that, but local optimum almost certainly. I agree with your point on a random initialization, hence I emphasize the fixed part in my definitions. The problems being seen seem to suggest that the input space has not been scanned properly..hence Check the starting points $\endgroup$ – Sid Feb 11 '18 at 2:39
  • $\begingroup$ The regularization experiment seems like one of the sanity checks I would perform to make sure my code has not bug, and non-monotonicity on the train set would definitely make me uneasy $\endgroup$ – Sid Feb 11 '18 at 2:40
  • $\begingroup$ Yes it will be a critical point (or at least a point where $\nabla f < \epsilon$ where $\epsilon$ is the tolerance), but it is highly unlikely to be a local or global optima (see the first of the two papers I reference). You emphasize the fix with respect to the x, but I am speaking about randomly initializing the W as without that it is starting at exactly the 'best' point of the last initialization. As the surface will change by adding to that regularization term, it may no longer be a saddle point so that the algorithm can continue moving downhill, hence the improvement. $\endgroup$ – David Kozak Feb 11 '18 at 2:57
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.