0
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ Your 'intersect the tangent lines' is an interesting algorithm, but it is not the same as the standard gradient descent algorithm. $\endgroup$ – D.W. Jan 29 '18 at 1:59
  • $\begingroup$ (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$. $\endgroup$ – usul Jan 30 '18 at 1:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.