Bounds on Query Convergence

Details Bounds on Query Convergence Bounds on Query Convergence

2005-11-25

arxiv.org/abs/cs/0511088v1

Computer Science

Learning

6 pages, 2 figures

Scientific paper

The problem of finding an optimum using noisy evaluations of a smooth cost function arises in many contexts, including economics, business, medicine, experiment design, and foraging theory. We derive an asymptotic bound E[ (x_t - x*)^2 ] >= O(1/sqrt(t)) on the rate of convergence of a sequence (x_0, x_1, >...) generated by an unbiased feedback process observing noisy evaluations of an unknown quadratic function maximised at x*. The bound is tight, as the proof leads to a simple algorithm which meets it. We further establish a bound on the total regret, E[ sum_{i=1..t} (x_i - x*)^2 ] >= O(sqrt(t)) These bounds may impose practical limitations on an agent's performance, as O(eps^-4) queries are made before the queries converge to x* with eps accuracy.

Affiliated with

Also associated with

No associations

Rating

Bounds on Query Convergence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds on Query Convergence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on Query Convergence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-435436