# Does binary search converge faster than gradient descent on 2 convex functions?

Here is the thing, I have two functions, lets call them $E_0$ and $E_1$. The functions are both convex, and they essentially look something like this:

Now I am looking to get an $\epsilon$ close to their intersection $C^*$ i.e. converge in the fastest amount of time.

There are two ways here.

1) Binary search: Let's say I know $C^*$ lies in $[0,M]$ for a constant $M$, then I can start with $mid=\frac{M}{2}$, and see if $E_0(mid)>E_1(mid)$, if thats the case then I know that $C^*$ is to my left and I update the region to $[0,mid]$, and I do the opposite if $E_0(mid)<E_1(mid)$. This would take $O(\log(\frac{M}{\epsilon}))$ to converge to $\epsilon$ away from $C^*$.

2) Gradient Descent. I can start with any initial guess $x_0$. I take the tangent lines $y_0, y_1$ which are tangents to $E_0, E_1$ respectively at $x_0$. I then see where they intersect, say $(x_1, y_1)$ and update my guess to now by at $x=x_1$. This would clearly converge since the intersection of the tangent lines would always be pointing towards $C^*$. However, how fast would this be?

Would the binary search be faster in this case, or the gradient descent?

• Your 'intersect the tangent lines' is an interesting algorithm, but it is not the same as the standard gradient descent algorithm. – D.W. Jan 29 '18 at 1:59
• (1) You've drawn two concave functions. (2) are you formally assuming that $E_0$ is monotonically increasing while $E_1$ is monotonically decreasing? (3) If so, note your question is equivalent to: (a) finding the minimum of the convex function $E = \max\{E_0,E_1\}$; and also (b) finding the zero of the monotonic (but not necessarily convex) function $E_1 - E_0$. In the second case you use binary search; in the first, you use a special-case kind of gradient descent that takes advantage of the structure of $E$. Don't know but I'd guess that which alg is faster depends on $E_1,E_2$. – usul Jan 30 '18 at 1:35