Back to Search
Start Over
Lower Bounds for Hit-and-Run Direct Search.
- Source :
- Stochastic Algorithms: Foundations & Applications (9783540748700); 2007, p118-129, 12p
- Publication Year :
- 2007
-
Abstract
- "Hit-and-run is fast and fun" to generate a random point in a high dimensional convex set K (Lovász/Vempala, MSR-TR-2003-05). More precisely, the hit-and-run random walk mixes fast independently of where it is started inside the convex set. To hit-and-run from a point , a line L through is randomly chosen (uniformly over all directions). Subsequently, the walk's next point is sampled from L ∩ K using a membership oracle which tells us whether a point is in K or not. Here the focus is on black-box optimization, however, where the function to be minimized is given as an oracle, namely a black box for f-evaluations. We obtain in an obvious way a direct-search method when we substitute the f-oracle for the K-membership oracle to do a line search over L, and, naturally, we are interested in how fast such a hit-and-run direct-search heuristic converges to the optimum point in the search space . We prove that, even under the assumption of perfect line search, the search converges (at best) linearly at an expected rate larger (worse) than 1 − 1/n. This implies a lower bound of 0.5 n on the expected number of line searches necessary to halve the approximation error. Moreover, we show that 0.4 n line searches suffice to halve the approximation error only with an exponentially small probability of $\exp(-\Omega(n^{1/3}))$. Since each line search requires at least one query to the f-oracle, the lower bounds obtained hold also for the number of f-evaluations. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540748700
- Database :
- Complementary Index
- Journal :
- Stochastic Algorithms: Foundations & Applications (9783540748700)
- Publication Type :
- Book
- Accession number :
- 33176153
- Full Text :
- https://doi.org/10.1007/978-3-540-74871-7_11