Bounds on Query Convergence
| dc.creator | Pearlmutter, Barak A. | |
| dc.date | 2005-11-25 | |
| dc.date.accessioned | 2026-07-07T06:49:38Z | |
| dc.date.available | 2026-07-07T06:49:38Z | |
| dc.description | 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. | |
| dc.description | 6 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0511088 | |
| dc.identifier | http://arxiv.org/abs/cs/0511088 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/104422 | |
| dc.subject | Machine Learning | |
| dc.subject | G.1.6 | |
| dc.title | Bounds on Query Convergence | |
| dc.type | text |