Why does gradient descent fail training a network for predicting times table?

Question

I am training a feedforwardnet with gradient descent traingd as backpropagation algorithm to predict times table.

X = [repmat([1:10]', 10, 1) repelem([1:10]', 10)];
y = X(:, 1) .* X(:, 2);

net = feedforwardnet(8);                % Create a neural network with 8 neurons in the hidden layer
net.layers{1}.transferFcn = 'logsig';   % Hidden layer activation function set to logsig
net.trainFcn = 'traingd';               % Set backpropagation algorithm to gradient descent
net.divideParam.trainRatio = 0.6;
net.divideParam.testRatio = 0.2;
net.divideParam.valRatio = 0.2;
[net, TR] = train(net, X', y');         % Train the network

But when I try to train my network it directly fails, I mean validation error keeps increasing from the start as you can see below.

I couldn't figure out the reason so I wanted to ask it here.

When I train my network using Levenberg-Marquardt trainlm as backpropagation algorithm then everything works fine.

Answer 1

Some hypotheses:

1. Scaling the data could improve the conditioning of the problem. See: In Machine learning, how does normalization help in convergence of gradient descent?

2. Training a neural network is hard in general; maybe a different configuration of hyperparameters (especially learning rate) would allow gradient descent to succeed. See: What should I do when my neural network doesn't learn?

3. Gradient descent isn't a very good optimizer; LM is way better. And we should hope that LM is better, because it's doing more work to find a good direction! So in this sense, it's not surprising that gradient descent doesn't do a great job compared to LM.

   Here's a fun comparison of SGD and LM on a very simple problem:

   I bet a lot of you have tried training a deep net of your own from scratch and walked away feeling bad about yourself because you couldn’t get it to perform.

   I don’t think it’s your fault. I think it’s gradient descent’s fault. I’m going to run gradient descent on the simplest deep net you can imagine, a two layer deep net with linear activations and where the labels are a badly-conditioned linear function of the input. $$ \min_{W_1,W_2} \mathbb{E}_x \left\|W_1 W_2 x - Ax \right\|^2 $$

   

   Here, the condition number of $A$ is 1020. Gradient descent makes great progress early on, then spends the rest of the time making almost no progress at all. You might think this it’s hit a local minimum. It hasn’t. The gradients aren’t decaying to 0. You might say it’s hitting a statistical noise floor of the dataset. That’s not it either. I can compute the expectation of the loss and minimize it directly with gradient descent. Same thing happens. Gradient descent just slows down the closer it gets to a good answer. If you’ve ever trained Inception on ImageNet, you’ll know that gradient descent gets through this regime in a few hours, and takes days to crawl through this regime.

   The black line is what a better descent direction would do. This is Levenberg-Marquardt.

   If you haven’t tried optimizing this problem with gradient descent, please spend 10 minutes coding this up or try out this Jupyter notebook. This is the algorithm we use as our workhorse, and it fails on a completely benign non-contrived problem. You might say “this is a toy problem, gradient descent fits large models well.” First, everyone who raised their hands a minute ago would say otherwise. Secondly, this is how we build knowledge, we apply our tools to simple problems we can analyze, and work our way up in complexity. We seem to have just jumped our way up.

From Ali Rahimi and Ben Recht. "Reflections on Random Kitchen Sinks." argmin.net blog. Dec. 5, 2017.