MURAL - Maynooth University Research Archive Library



    Bounds on Query Convergence


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

    [img]
    Preview
    Download (399kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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)
    URI:
    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

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads