2
$\begingroup$

In a computational statistics book, I found an optimization method to find local minimum of a function.

Let's assume that we have a differentiable function $f: \mathbb{R}^2 \longrightarrow \mathbb{R}$. We want to find a local minimum $f(\theta)$ of the function. Starting with initialization $\theta^{*}_i$, instead of using gradient descent, a slightly different method is used.

Given a decreasing sequence of positive real numbers $\alpha_i$ (i = 1,2,3,...)

Set i = 1

  1. Sample $\omega_i$ from a uniform unit sphere
  2. Estimate the directional derivative of $f$ at $\theta = \theta^{*}_i$ along the direction $\omega_i$, denoting the result as $f_{\omega_i}^{'}( \theta^{*}_i)$
  3. Update $\theta^{*}_{i+1}$:= $\theta^{*}_{i} - \alpha_if_{\omega_i}^{'}( \theta^{*}_i)\omega_i$
  4. Stop and return $\theta^{*}_{i+1}$if(convergent). Otherwise increase i by 1 and go back to (1)

This question is mainly because of confusing terminology in different books. I think this algorithm is not the traditional "stochastic gradient descent" algorithm that machine learning scientists often refer to.

Is this true? And if it is, how do statisticians/machine learning scientists often call it?

$\endgroup$
2
  • $\begingroup$ Hi! Care to share the book? Anyways, the difference between this algo and stochastic gradient descent is that this chooses a direction completely at random and then goes either in that direction or in the opposite direction according to whichever decreases the cost, whereas stochastic gradient descent goes in a direction which is also sampled at random but crucially is not uniform, and in fact has expectation given by the "true" gradient (i.e. in finite sum applications, the gradient of the entire sum). $\endgroup$ Commented Dec 4, 2022 at 0:25
  • 1
    $\begingroup$ @JohnMadden I will (I forgot the name of that book. The question just popped up today in my mind) $\endgroup$
    – Neuchâtel
    Commented Dec 4, 2022 at 0:59

1 Answer 1

4
$\begingroup$

I don't know the name for the algorithm that you mention. It seems like stochastic hill climbing which selects random directions or (random) coordinate descent, which uses steps based on the derivative/gradient, but only along the direction of a single (randomly picked) coordinate.

I imagine that the advantage of changing the angle would be to avoid zigzag patterns that may occur in gradient descent.

zigzag


Stochastic gradient descent refers to the use of randomly optimizing the cost function where the randomness is created by randomly selecting only a part of the data for each step.

'regular' gradient descent

Descent in small steps along a complex surface. The cost function is computed for all the data together.

non convex

stochastic gradient descent

Descent in small steps along a simple surface, but each time based on a different (random) set of data points.

In the image below you see the paths of descent for six different starting values. The four images relate to four different data points in the (synthetic) data, which creatie different functions to optimise. The steps in the six paths are each time along one of those four surfaces (which of the four is randomly selected each step).

stochastic gradient descent

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed answer! That is so helpful! $\endgroup$
    – Neuchâtel
    Commented Dec 4, 2022 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.