The connection between optimization and generalization

Question

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).

Answer 1

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.