Consider a strictly convex function $f: [0; 1]^n \rightarrow \mathbb{R}$. The question is why people (especially experts in machine learning) use gradient descent in order to find a global minimum of this function instead of using n-dimensional ternary search or golden section search?

Here is a list of disadvantages:

  1. It is required for gradient descent to experimentally choose a value of step size $\alpha$.
  2. It is also required to calculate partial derivatives of $f$. Furthermore, it is not always possible, for example, the «black box» function.
  3. Ternary search guaranteed to converge in $\Theta(\lg^n \epsilon^{-1})$ iterations, where $\epsilon$ is our required absolute precision. However, for gradient descent we should choose number of iterations experimentally.

Maybe I misunderstand a bit?

Thanks in advance.


There is no "$n$-dimensional ternary search or golden section search". These methods only work in one dimension.

What you can do in principle is use the gradient to determine the direction in which to search, and then apply ternary search or golden section search along that direction. However, you don't want to find the exact minimum along the chosen search direction, because you'll recompute the gradient and minimize along a different line immediately after that anyway. So in practice, you only spend enough time to find a point that guarantees making progress, for example by using the Wolfe conditions.

  • 1
    $\begingroup$ "There is no n-dimensional ternary search" — Suppose that $n = 2$ and our unimodal function is $f(x, y)$. Then we can use 2 ternary searches: $solve_1 = \min_{x \in [0; 1]} solve_2(x)$, $solve_2(x) = \min_{y \in [0; 1]} f(x, y)$. It seems to be true. What's the problem? $\endgroup$ – Arthur Khashaev May 3 '12 at 10:03
  • $\begingroup$ By "unimodal" do you really mean "convex"? Your procedure has two problems: (a) You can only evaluate $\operatorname{solve}_2$ approximately, not exactly. If you get it wrong, you may choose the wrong branch in the ternary search of $\operatorname{solve}_1$ and end up far from the true optimum. (2) The running time goes up exponentially in the number of dimensions. I imagine most interesting problems in machine learning are high-dimensional, and this procedure would be unusable for them. $\endgroup$ – Rahul May 3 '12 at 10:25
  • $\begingroup$ By «unimodal» I mean «strictly convex». Yes, that's the real disadvantages, thanks for your response. $\endgroup$ – Arthur Khashaev May 3 '12 at 11:00

A quick look at the Wikipedia pages you linked to suggests that both of these techniques only work for unimodal functions, not general functions. Usually the error function that you want to minimise won't be unimodal, and so (presumably) these search techniques won't work.


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.