Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
"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? –  Inviz May 3 '12 at 10:03
    
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. –  Rahul May 3 '12 at 10:25
    
By «unimodal» I mean «strictly convex». Yes, that's the real disadvantages, thanks for your response. –  Inviz May 3 '12 at 11:00
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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