MURAL - Maynooth University Research Archive Library



    Bounds on Query Convergence


    Pearlmutter, Barak A. (2005) Bounds on Query Convergence. Working Paper. arXiv.

    Abstract

    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.
    Item Type: Monograph (Working Paper)
    Additional Information: Cite as: arXiv:cs/0511088 [cs.LG]
    Keywords: Bounds; Query Convergence;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 8163
    Identification Number: arXiv:cs/0511088 [cs.LG]
    Depositing User: Barak Pearlmutter
    Date Deposited: 13 Apr 2017 14:21
    Publisher: arXiv
    Funders: Science Foundation Ireland (SFI)
    Related URLs:
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Downloads

    Downloads per month over past year

    Origin of downloads

    Altmetric Badge

    Repository Staff Only (login required)

    Item control page
    Item control page