To access the full text documents, please follow this link: http://hdl.handle.net/2117/87244

An optimal anytime estimation algorithm
Gavaldà Mestre, Ricard
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
In many applications a key step is estimating some unknown quantity ~$mu$ from a sequence of trials, each having expected value~$mu$. Optimal algorithms are known when the task is to estimate $mu$ within a multiplicative factor of $epsilon$, for an $epsilon$ given in advance. In this paper we consider {em anytime} approximation algorithms, i.e., algorithms that must give a reliable approximation after each trial, and whose approximations have to be increasingly accurate as the number of trials grows. We give an anytime algorithm for this task when the only a-priori known property of $mu$ is its range, and show that it is asymptotically optimal in some cases, in the sense that no correct anytime algorithm can give asymptotically better approximations. The key ingredient is a new large deviation bound for the supremum of the deviations in an infinite sequence of trials, which can be seen as a non-limit analog of the classical Law of the Iterated Logarithm.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Optimal algorithms
Approximation algorithms
info:eu-repo/semantics/publishedVersion
Report
         

Show full item record

Related documents

Other documents of the same author

Berral García, Josep Lluís; Gavaldà Mestre, Ricard; Torres Viñals, Jordi
Balle Pigem, Borja de; Castro Rabal, Jorge; Gavaldà Mestre, Ricard
Chattopadhyay, Arkadev; Gavaldà Mestre, Ricard; Arnsfelt Hansen, Kristoffer; Thérien, Denis
Berral García, Josep Lluís; Goiri, Iñigo; Nguyen, Thu D.; Gavaldà Mestre, Ricard; Torres Viñals, Jordi; Bianchini, Ricardo
Berral García, Josep Lluís; Gavaldà Mestre, Ricard; Torres Viñals, Jordi
 

Coordination

 

Supporters