# Gradient descent vs ternary search

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?

-

There is no "$n$-dimensional ternary search or golden section search". These methods only work in one dimension.
"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? – Arthur Khashaev 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