3 ms·

Quite smart. No perpetual motion machine here. This forward differentiation method is not as powerful as the backward one, it does not give you the gradient of

Quite smart. No perpetual motion machine here. This forward differentiation method is not as powerful as the backward one, it does not give you the gradient of a function. Instead, you choose a direction, and it gives you the derivative along that direction. You could essentially get that by “bump and recalc”, at the cost of an additional function evaluation. I even doubt this comes at a cheaper compute cost than the brute force bump and recalculate. How about the stochastic gradient descent, if you don’t know the gradient? Well, you know the sign of the directional derivative, so you know which way is up and which is down. At each step you pick a random direction, and you move down along it. That’s it. Edit: I just implemented this descent algorithm, let’s call it Random Direction Descent. I was sure that the gradient descent outperforms it more and more for higher and higher dimensions. The exact oposite happens: this one outperforms the gradient descent, and the higher dimension, the more. This is a huge surprise for me. This descent algorithm might revolutionize ML.

deleted 5y ago
[deleted]
mjburgess 5y ago
The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. I'd expect "random direction" grad desc to improve the more dimensionality the data has, as in that space, the data surface itself is simple.
- cracker_jacks 5y ago
  > The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. Even assuming this statement were true (which is a big if). That does not explain how it would outperform gradient descent.
  - mjburgess 5y ago
    As dimensionality grows, data is more linearly sperable, so fewer dimensions are signficant in distinguishing the data (though for any pair of points, those dimensions will be different). Grad desc, as an exhaustive search over all those dimensions "maybe" less performant in very high dimensions, where we have enough data to be "right some of the time" when randomly choosing which dim to discriminate on. If we force zero loss, ie., an interpolation regime, then we're getting interpolation as usual. Can we get there faster when dimensionality increases? It's plausible if count(relevant dimensions) << count(dimensions), and if they discriminating dimensions for any two random points is itself random.
    - cracker_jacks 5y ago
      I believe what you are describing is grid search, not gradient descent. Gradient descent is not an exhaustive search.
      - mjburgess 5y ago
        It is if you see vec_a . vec_b, as a traversal over the dimensions of both vectors.
cracker_jacks 5y ago
That does not make sense, can you expand? The steepest descent direction is far more useful than a random direction in high dimensions because that random direction has a greater chance of being nearly orthogonal to the steepest descent direction.
- credit_guy 5y ago
  The random directions don’t have unit length. They are drawn from a multivariate normal. They have equal variance along all directions, including the direction of the gradient. The descent along the orthogonal directions somehow cancels out. The descent along the gradient direction somehow becomes more efficient, I don’t know why yet.
  - cracker_jacks 5y ago
    I agree, in expectation, the orthogonal directions cancel out. But the variance does not cancel out. Are you using some sort of momentum-like optimizer?
    - credit_guy 5y ago
      > But the variance does not cancel out. They are multiplied with the derivative in that direction, which is zero.
      - cracker_jacks 5y ago
        Oh, you're talking about using the forward gradient method. This still does not make much sense because if the projection of the gradient in that direction is zero or near zero, that is a very weak step in reducing the loss.
        credit_guy 5y ago
        Ok, to recap: this whole article that we are discussing here is about the forward "gradient" method. Which, despite the name, only calculates a single directional derivative. If this were all, that would be a bit interesting, but not much else. The article goes on to show how to make use of this in optimization. I called their descent algorithm the "random direction descent", because that's what it is. You chose a random direction, from a multivariate normal distribution with zero mean and identity covariance matrix (section 3.4). You chose a "step size" eta. Then you go along the chosen direction by eta times the directional derivative (times -1, so you go "downhill"). That is all explained at the top of page 4, Algorithm 1. Why does this work, if, as you correctly noticed, the chosen direction is almost perpendicular to the gradient (one of the "features" of high dimensional spaces -> most of the volume of a unit sphere is close to the equator). The answer is this: if you split the chosen random direction into the component along the gradient and the orthogonal component, then the first one has variance 1, and the second variance (N-1), since the overall variance is N, where N is the number of dimensions. The orthogonal component makes you move downhill, while the orthogonal component makes you move level-wise. The orthogonal component doesn't make things any better or worse. Another commenter in this thread claims that this method adds noise, and the noise is sometimes so high that the method is useless. Well, that's not what I observed. Why did I observe that the random direction descent outperforms the gradient descent. With the argument so far, you'd expect to do no worse, but why does it do better? This I don't have an explanation for, but maybe it's the fact that you don't have a constant step-size, but rather a stepsize that has variance 1. With the classical gradient descent, as you approach the minimum, the step becomes smaller and smaller. With this one, it still becomes smaller and smaller, but sometimes it's bigger, and sometimes even smaller. It appears there's some gain from the extra-stochasticity, so you end up getting faster at the minimum. I'm not sure why, but that's what I observed.

deleted 5y ago

[deleted]

mjburgess 5y ago

The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. I'd expect "random direction" grad desc to improve the more dimensionality the data has, as in that space, the data surface itself is simple.

cracker_jacks 5y ago
> The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. Even assuming this statement were true (which is a big if). That does not explain how it would outperform gradient descent.
- mjburgess 5y ago
  As dimensionality grows, data is more linearly sperable, so fewer dimensions are signficant in distinguishing the data (though for any pair of points, those dimensions will be different). Grad desc, as an exhaustive search over all those dimensions "maybe" less performant in very high dimensions, where we have enough data to be "right some of the time" when randomly choosing which dim to discriminate on. If we force zero loss, ie., an interpolation regime, then we're getting interpolation as usual. Can we get there faster when dimensionality increases? It's plausible if count(relevant dimensions) << count(dimensions), and if they discriminating dimensions for any two random points is itself random.
  - cracker_jacks 5y ago
    I believe what you are describing is grid search, not gradient descent. Gradient descent is not an exhaustive search.
    - mjburgess 5y ago
      It is if you see vec_a . vec_b, as a traversal over the dimensions of both vectors.

cracker_jacks 5y ago

That does not make sense, can you expand? The steepest descent direction is far more useful than a random direction in high dimensions because that random direction has a greater chance of being nearly orthogonal to the steepest descent direction.

credit_guy 5y ago
The random directions don’t have unit length. They are drawn from a multivariate normal. They have equal variance along all directions, including the direction of the gradient. The descent along the orthogonal directions somehow cancels out. The descent along the gradient direction somehow becomes more efficient, I don’t know why yet.
- cracker_jacks 5y ago
  I agree, in expectation, the orthogonal directions cancel out. But the variance does not cancel out. Are you using some sort of momentum-like optimizer?
  - credit_guy 5y ago
    > But the variance does not cancel out. They are multiplied with the derivative in that direction, which is zero.
    - cracker_jacks 5y ago
      Oh, you're talking about using the forward gradient method. This still does not make much sense because if the projection of the gradient in that direction is zero or near zero, that is a very weak step in reducing the loss.
      - credit_guy 5y ago
        Ok, to recap: this whole article that we are discussing here is about the forward "gradient" method. Which, despite the name, only calculates a single directional derivative. If this were all, that would be a bit interesting, but not much else. The article goes on to show how to make use of this in optimization. I called their descent algorithm the "random direction descent", because that's what it is. You chose a random direction, from a multivariate normal distribution with zero mean and identity covariance matrix (section 3.4). You chose a "step size" eta. Then you go along the chosen direction by eta times the directional derivative (times -1, so you go "downhill"). That is all explained at the top of page 4, Algorithm 1. Why does this work, if, as you correctly noticed, the chosen direction is almost perpendicular to the gradient (one of the "features" of high dimensional spaces -> most of the volume of a unit sphere is close to the equator). The answer is this: if you split the chosen random direction into the component along the gradient and the orthogonal component, then the first one has variance 1, and the second variance (N-1), since the overall variance is N, where N is the number of dimensions. The orthogonal component makes you move downhill, while the orthogonal component makes you move level-wise. The orthogonal component doesn't make things any better or worse. Another commenter in this thread claims that this method adds noise, and the noise is sometimes so high that the method is useless. Well, that's not what I observed. Why did I observe that the random direction descent outperforms the gradient descent. With the argument so far, you'd expect to do no worse, but why does it do better? This I don't have an explanation for, but maybe it's the fact that you don't have a constant step-size, but rather a stepsize that has variance 1. With the classical gradient descent, as you approach the minimum, the step becomes smaller and smaller. With this one, it still becomes smaller and smaller, but sometimes it's bigger, and sometimes even smaller. It appears there's some gain from the extra-stochasticity, so you end up getting faster at the minimum. I'm not sure why, but that's what I observed.