4
$\begingroup$

Optimization algorithms such as gradient descent or particle swarm can find a minima in a function.

On the other hand, learning methods such as back-prop define learning as an optimization problem and are used to learn weights in deep neural networks and etc.

We know that DL models can learn/memorize basically anything in the training data [2], even random noise, which brings us to the question of then how we can achieve generalization (as defined in [5]) *.

In [7, 1, 3] authors tried to show the connection between generalization and the loss landscape (sharp minima/flat minima) plus its effect from the batchsize.

The effect of training data on generalization studied in [4] shows that models that have high influence from more data points generalize better than models that rely/influenced on less data points.

On the other hand [6] sheds some light on the role of the model's parameters from a neuroscience point of view in terms of effect of neurons in generalization (Networks that generalize better are harder to break with neuron deletion.).

Although all of these papers investigated generalization up to a certain point, the effect of optimization used in the learning algorithm on the generalization is not yet clear.

Is there any study done in this direction? What are the possible related work on this? Or do you have an answer to this question?

*: Let me point out that although many believe explicit regularization is crucial for generalization, [2] already explains explicit regularization (l1/l2/dropout) does not play a big role in generalization. Many tricks that were known as a generalizer, are shown to be a myth. They also show that interestingly, SGD works as an implicit regularizer which might be a connection to the effect of optimization alg. to generalization.

[1]: Li, Hao, et al. "Visualizing the Loss Landscape of Neural Nets." arXiv preprint arXiv:1712.09913 (2017).

[2]: Zhang, Chiyuan, et al. "Understanding deep learning requires rethinking generalization." arXiv preprint arXiv:1611.03530 (2016).

[3]: Keskar, Nitish Shirish, et al. "On large-batch training for deep learning: Generalization gap and sharp minima." arXiv preprint arXiv:1609.04836 (2016).

[4]: Koh, Pang Wei, and Percy Liang. "Understanding black-box predictions via influence functions." arXiv preprint arXiv:1703.04730 (2017).

[5]: Kawaguchi, Kenji, Leslie Pack Kaelbling, and Yoshua Bengio. "Generalization in deep learning." arXiv preprint arXiv:1710.05468 (2017).

[6]: Ari S. Morcos, David G.T. Barrett, Neil C. Rabinowitz, Matthew Botvinick, "On the importance of single directions for generalization." arXiv preprint arXiv:1803.06959 (2018). https://deepmind.com/blog/understanding-deep-learning-through-neuron-deletion/

[7]: Dinh, Laurent, et al. "Sharp minima can generalize for deep nets." arXiv preprint arXiv:1703.04933 (2017).

$\endgroup$
  • 1
    $\begingroup$ This is a good question. As you can see, by the date of the papers you cited, it's a current topic in research. One conjecture is that good generalization is associated with the optima in a flat region of the objective function (Chaudari et al 2016). But this was disproved in [2] who show sharp minima are better on test error. $\endgroup$ – horaceT Mar 26 '18 at 16:37
  • $\begingroup$ @horaceT exactly... each of the papers I cited, studied the generalization from one aspect. But investigating the generalization and its relation to the optimization is not studied yet. I remember a physicist once told me SGD won't work for them at all and will always stuck in a local minima in their problems as their search space is very large and very difficult to find a good minima. He was surprised that ML community now-a-days uses so much of GD. I think there's def. a connection to opt. in here... $\endgroup$ – PickleRick Mar 26 '18 at 16:46
  • 1
    $\begingroup$ I think (pure speculation with little theoretical base probably) the heart of the matter is not about optimization, but search technique used in optimization such as SGD. The fact that deep learning has achieved tremendous success has more to do with the bag of tricks (thanks to Hinton and others) to improve on SGD than adding more and more layers in a deep neural net. $\endgroup$ – horaceT Mar 26 '18 at 16:55
  • $\begingroup$ indeed that might be the cause. But one should investigate whether this comes from the optimization or the learning...Let's see if anyone can point out some related work in this direction... $\endgroup$ – PickleRick Mar 26 '18 at 17:02
3
$\begingroup$

What part the optimization alg. (Grad. Descent) plays in generalization of the learning algorithm?

Actually for generalizing you have to find a model that does not overfits the training data. For doing so, there are numerous approaches, like L1/L2 regularization which adds noise to the cost function and somehow weights to prohibit the network from having large weights which may lead to overfitting. Take a look at here. Other techniques are drop-out which adds noise to the activations to help the network not to depend on special nodes. These techniques add some noise to different parts of the network which lead to a cost function with a high error value. After finding the error back prop techniques try to set the parameters/weights to go downhill of the cost function. These techniques help the algorithm not to overfit which means the constructed model will be able to generalize, although you have to test it using cross-validation data and test data. Consequently, optimization techniques by themselves always try to reduce the amount of error and they somehow always lead to overfitting because they try to reduce the cost and this is regularization techniques and other variants that have to be used to construct a cost function which its optimum points do not lead to overfitting. This link also may help you.

Or the influence of the data [4] plays a more important role? Although [6] sheds the light on the role of the model parameters from a neuroscience point of view in terms of the effect of neurons in generalization, the question on how to learn such models remains unsolved.

Data is the most important part of the learning process. Your data have to be representative enough. Deep learning problems are considered those problems which may have better results if their training data increases. If the model should be able to generalize, it is vital to use data from the real distribution. This is just for training. You can use some techniques in order not to overfit the data using your training data-set. It is customary to add small noises to the input to let the model generalize well. Transforming data by translation, rotation and even distorting image inputs are examples of adding noise to the input to avoid overfitting. Although changing the data is dangerous because it may change the distribution of the real population. So, you can do something with your input data to avoid overfitting and let your model to generalize well.

So how can we really better understand the generalization considering different factors as mentioned above?

Generalization techniques are used to make the network generalize well. The customary approaches are:

  • Drop Out
  • L1/L2 Regularization
  • Early Stop
  • Adding Noise and data-augmentation

It should be considered that adding noise to the input should be without changing the distribution. The ratio of signal to noise also should not be small because the information may be lost compeletely. Depending on your problem each of them make work well but I guess there is no consensus which one is the best but in deep-learning the first one is so helpful.

What is the connection between optimization and generalization (as defined in [5])?

What I'm saying is based on my experience. Optimization itself always lead to overfitting. You have to use generalization techniques to avoid that. To help you figure out the problem, suppose that deep-learning algorithms are able to learn all functions. If you provide them with relatively small number of data, they will memorize a hypothesis, and they do not learn the problem.

$\endgroup$
  • 1
    $\begingroup$ thank you for your answer. Actually [2] already explains that explicit regularization (l1/l2/dropout) does not play a big role in generalization. Many tricks that were known as a generalizer, are shown to be a myth. They also show that interestingly, SGD works as an implicit regularizer which might be a connection to the effect of optimization alg to generalization. I pointed out the papers that studied generalization in recent years, but still nobody really focused on optimization. Because in the end, the way you learn the parameters of your models is via your learning alg. (via opt,) $\endgroup$ – PickleRick Mar 23 '18 at 15:27
  • $\begingroup$ @PickleRick Regularization is so much helpful in SVMs. In neural nets people usually use drop out which is better, but it does not mean regularzation techniques are useless. Moreover, optimization just tries to reduce the error function. The techniques used for avoiding overfitting try to add noise to ovoid overfitting. $\endgroup$ – Media Mar 23 '18 at 15:28
  • $\begingroup$ the regularization effect on generalization might be true for SVMs since [2] only studies DL. The regularization in DL models probably helps generalization up to a certain level, but I am not sure if I agree with you on the role of the optimizer in generalization. Perhaps this needs to be empirically and theoretically evaluated. $\endgroup$ – PickleRick Mar 23 '18 at 15:40
  • $\begingroup$ @PickleRick take this in mind, suppose that deep-learning algorithms are able to learn all functions. If you provide them with relatively small number of data, they will memorize a hypothesis, and they do not learn the problem. $\endgroup$ – Media Mar 23 '18 at 15:48
  • $\begingroup$ true if you use lots of parameters, yet having lots of data won't guarantee the generalization in DL too. $\endgroup$ – PickleRick Mar 23 '18 at 15:53

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.