Hacker News Reader

Comment by frankreyes | Hacker News Reader

Hobest question, why not just use a binary/ternary search? It's because there's no known a priori how many local maximum and/or minimums?

Because that's just an iterative/recursive version of binary/ternary search.

View on HN

How would you do a binary search on a continuous space without discretizing?

Replace A[x] with f(x) and done.

A modified binary search called ternary search is well known used to find when derivative = 0, numerically.

https://en.m.wikipedia.org/wiki/Ternary_search

Try doing binary search on a space of nontrivial dimensionality (ie, not 1, 2, or 3) and you will have your answer.

What would you search for, the zero/root in the derivative? Imagine the derivative is a function like y=x^2-eps with some small eps, say 0.000001. For binary search like that to work, you need to start with two values x1 and x2 such that sign(y1) != sign(y2). But with the derivative above those values are hard to find with random initialization.

More generally, for binary search to find a value x such that f(x)=0, we need to have f(any value less than x)<0 and f(any value greater than x)>0. We can't guarantee these properties for general derivatives.

> What would you search for

I imagine you could search until the incremental change between your current and last result is below some threshold epsilon, as a kind of stopping criterion.

IEEE 754 is by default limited by 64 bits, so yes.

We do, it’s called global optimization. It works for small problems with ~ 1000 variables or so. Check BARON and the branch & reduce algorithm

Thanks!

Binary search only works on sorted data.

This is probably what you're thinking of:

https://en.m.wikipedia.org/wiki/Bisection_method

Because of the dimensionality of the problem. Bracketing is easy to do in 1D space, not so in N-dimensional space, with large N.

Because the search space is tremendously huge.

Binary search only works in 1D parameter space

Reply on news.ycombinator.com