5
$\begingroup$

I've come across the concept of fitness landscape before and, in my understanding, a smooth fitness landscape is one where the algorithm can converge on the global optimum through incremental movements or iterations across the landscape.

My question is: Does deep learning assume that the fitness landscape on which the gradient descent occurs is a smooth one? If so, is it a valid assumption?

Most of the graphical representations I have seen of gradient descent show a smooth landscape.

This Wikipedia page describes the fitness landscape.

$\endgroup$
10
  • $\begingroup$ What is the fitness landscape? Is it the surface where gradient descent occurs? To compute the derivatives we need a smooth manifold. So, I think the landscape is smooth. $\endgroup$ Apr 9 at 7:54
  • $\begingroup$ I am not sure about what fitness landscape mean but if it is the landscape where gradient descent occur. Then I think smooth means there is not discontinuty or sudden jump in the surface, so we can find out the derivatives. $\endgroup$ Apr 9 at 7:57
  • $\begingroup$ i dont believe it's smooth landscape theoretically, since gradient descent in neural net does partial derivation thus other weights may get to wrong values when a certain weight is optimised; this results oscillation sometimes $\endgroup$ Apr 9 at 9:42
  • $\begingroup$ You say "I've come across the concept of fitness landscape before". Can you please provide the link to the research papers or books that use this term "fitness landscape". I think this term occurs more in the context of evolutionary algorithms and not deep learning. $\endgroup$
    – nbro
    Apr 9 at 12:57
  • $\begingroup$ @nbro: You are right. It does occur mainly in the evolutionary context. I just thought the concept might still be applicable. $\endgroup$
    – Joebevo
    Apr 9 at 13:08
1
$\begingroup$

Main answer

To answer your question as directly as possible: No, deep learning does not make that "assumption".

But you're close. Just swap the word "assumption" with "imposition".

Deep learning sets things up such that the landscape is (mostly) smooth and always continuous*, and therefore it is possible to do some sort of optimization via gradient descent.

* quick footnotes on that bit:

  • Smoothness is a stronger condition than continuity, that's why I mention them both.
  • My statement is not authoritative, so take it with a grain of salt, especially the "always" bit. Maybe someone will debunk this in the comments.
  • The reason that I say "(mostly) smooth" is because I can think of a counter example to smoothness, which is the ReLU activation function. ReLU is still continuous though.

Further elaboration

In deep learning we have linear layers which we know are differentiable. We also have non-linear activations, and a loss function which for the intents of this discussion can be bundled with non-linear activations. If you look at papers which focus specifically on crafting new types of non-linear activations and loss functions you will usually find a discussion section that goes something like "and we designed it this way such that it's differentiable. Here's how you differentiate it. Here are the properties of the derivative". For instance, just check out this paper on ELU, a refinement on ReLU.

We don't need to "assume" anything really, as we are the ones who designate the building blocks of the deep learning network. And the building blocks are not all that complicated in themselves, so we can know that they are differentiable (or piecewise differentiable like ReLU). And for rigor, I should also remind you that the composition of multiple differentiable functions is also differentiable.

So hopefully that helps you see what I mean when I say deep learning architects "impose" differentiability, rather than "assume" it. After all, we are the architects!

$\endgroup$
1
$\begingroup$

I'm going to take the fitness landscape to be the graph of the loss function, $\mathcal{G} = \{\left(\theta, L(\theta)\right) : \theta \in \mathbb{R}^n\}$, where $\theta$ parameterises the network (i.e. it is the weights and biases) and $L$ is a given loss function; in other words, the surface you would get by plotting the loss function against its parameters.

We always assume the loss function is differentiable in order to do backpropagation, which means at the very least the loss function is smooth enough to be continuous, but in principle it may not be infinitely differentiable1.

You talk about using gradient descent to find the global minimiser. In general this is not possible: many functions have local minimisers which are not global minimisers. For an example, you could plot $y = x^2 \sin(1/x^2)$: of course the situation is similar, if harder to visualise, in higher dimensions. A certain class of functions known as convex functions satisfy the property that any local minimiser is a global minimiser. Unfortunately, the loss function of a neural network is rarely convex.

For some interesting pictures, see Visualizing the Loss Landscape of Neural Nets by Li et al.


1 For a more detailed discussion on continuity and differentiability, any good text on mathematical analysis will do, for example Rudin's Principles of Mathematical Analysis. In general, any function $f$ that is differentiable on some interval is also continuous, but it need not be twice differentiable, i.e. $f''$ need not exist.

$\endgroup$
2
  • $\begingroup$ This answer seems reasonable to me, i.e. you need differentiability to apply back-propagation, but note that not all neural networks are trained with back-prop (although this may be an assumption, when you use the term "deep learning"). But why do you say that $G$ is a graph? Maybe you mean a space (en.wikipedia.org/wiki/Space_(mathematics))? In any case, it seems that you're using the term "graph" not as defined in graph theory. $\endgroup$
    – nbro
    Apr 9 at 17:19
  • 1
    $\begingroup$ @nbro Thanks for the question, I mean graph as in the literal sense of plotting a graph of a function (you can see an example of this usage here, for example). My choice of notation has clearly added to the confusion as it is common to denote a graph (in the network sense) by $G$, but I don't mean to say $G$ is a network. Hopefully the latest revision clarifies this. $\endgroup$
    – htl
    Apr 9 at 18:15
-2
$\begingroup$

Does deep learning assume that the fitness landscape on which the gradient descent occurs is a smooth one?

One can interpret this question from a formal-mathematical standpoint and from a more "intuitively-practical" standpoint.

From the formal point of view, smoothness is the requirement that the function is continuous with continuous first derivatives. And this assumption is quite often not true in lots of applications - mostly because of the widespread use of ReLU activation function - it is not differentiable at zero.

From the practical point of view, though, by "smoothness" we mean that the function's "landscape" does not have a lot of sharp jumps and edges like that:

enter image description here

Practically, there's not much difference between having a discontinuous derivative and having derivatives making very sharp jumps.

And again, the answer is no - the loss function landscape is extremely spiky with lots of sharp edges - the picture above is an example of an actual loss function landscape.

But... why the gradient descent works then?

As far as I know, this is a subject of an ongoing discussion in the community. There are different takes and some conflicting viewpoints that are still subject of a debate.

My opinion is that, fundamentally, the idea that we need it to converge to the global optimum is a flawed one. Neural networks was shown to have enough capacity to completely remember the training dataset. A neural network, that completely remembered the training data. has reached the global optimization minimum (given only the training data). We are not interested in such overtrained models - we want models that generalize well.

As far as I know, there is no conclusive results on which properties of the minimum are linked to ability to generalize. People argued that these should be the "flat" minima, but then it was refuted. After that a "wide optimium" term was introduced and gave rise of an interesting technique of Stochastic Weight Averaging.

$\endgroup$
13
  • 1
    $\begingroup$ Why would we be looking for the "widest" minimum? Moreover, although I think what you mean, you should explain what you mean by "widest minimum" (maybe a more common term is "flat minimum"). I really don't understand why we would not be looking for the global minimum. The global minimum/maximum is the optimal solution. Not sure what you're talking about here and where your conclusions come from. $\endgroup$
    – nbro
    Apr 9 at 15:41
  • $\begingroup$ @nbro Would you agree that a neural network, that completely remembered the training data, has reached the global optimization minimum? $\endgroup$
    – Kostya
    Apr 9 at 16:53
  • 1
    $\begingroup$ Mathematics is not about agreeing on something or not. It's about making assumptions or starting from premises and follow the rules to reach some conclusions. In any case, that would be the global optimum but for the training dataset. In reality, as you know, we're not trying to overfit the training data but to find a function that generalizes well to unseen data too. The thing is: I don't know where your conclusion that we're trying to find the "widest minimum" comes from and why would that mean "better generalization", which is what you seem to mean/imply now. $\endgroup$
    – nbro
    Apr 9 at 17:01
  • 1
    $\begingroup$ To be honest, the question is not even clear. The author is talking about the "fitness landscape", but they didn't even clarify what that would mean in the context of deep learning. They are probably talking about "loss landscape", but it's also not clear. I'm not an expert on the topic, but I don't think that your conclusion (last part) is well motivated. The first paragraphs seem reasonable to me, though, although, again, I am not a mathematician and not an expert on this specific topic of "loss landscapes", whatever the definition is. $\endgroup$
    – nbro
    Apr 9 at 17:03
  • $\begingroup$ @nbro I thought that my three last sentences unambiguously stated that I'm talking about generalization... If you have a suggestion on how to rephrase that - I'd happily do that. I didn't want to go into formal details of it because it was my slightly opinionated aside on the subject. Also, I do agree that the question is not well-phrased, but demanding mathematically precise formulation from beginners is not very productive, wouldn't you say? $\endgroup$
    – Kostya
    Apr 9 at 17:09

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.