Algorithmic statistics
Date Issued
20010901Publisher Version
10.1109/18.945257Author(s)
Gacs, Peter
Tromp, J.T.
Vitanyi, P.M.B.
Metadata
Show full item recordPermanent Link
https://hdl.handle.net/2144/29381Citation (published version)
P Gacs, JT Tromp, PMB Vitanyi. 2001. "Algorithmic statistics." IEEE Transactions On Information Theory, Volume 47, Issue 6, pp. 2443  2463 (21).Abstract
While Kolmogorov (1965, 1983) complexity is the accepted absolute measure of information content of an individual finite object, a similarly absolute notion is needed for the relation between an individual data sample and an individual model summarizing the information in the data, for example, a finite set (or probability distribution) where the data sample typically came from. The statistical theory based on such relations between individual objects can be called algorithmic statistics, in contrast to classical statistical theory that deals with relations between probabilistic ensembles. We develop the algorithmic theory of statistic, sufficient statistic, and minimal sufficient statistic. This theory is based on twopart codes consisting of the code for the statistic (the model summarizing the regularity, the meaningful information, in the data) and the modeltodata code. In contrast to the situation in probabilistic statistical theory, the algorithmic relation of (minimal) sufficiency is an absolute relation between the individual model and the individual data sample. We distinguish implicit and explicit descriptions of the models. We give characterizations of algorithmic (Kolmogorov) minimal sufficient statistic for all data samples for both description modesin the explicit mode under some constraints. We also strengthen and elaborate on earlier results for the "Kolmogorov structure function" and "absolutely nonstochastic objects"those objects for which the simplest models that summarize their relevant information (minimal sufficient statistics) are at least as complex as the objects themselves. We demonstrate a close relation between the probabilistic notions and the algorithmic ones: (i) in both cases there is an "information nonincrease" law; (ii) it is shown that a function is a probabilistic sufficient statistic iff it is with high probability (in an appropriate sense) an algorithmic sufficient statistic.
Collections
Related items
Showing items related by title, author, creator and subject.

On distributed virtual network embedding with guarantees
Esposito, Flavio; Di Paola, Donato; Matta, Ibrahim (Computer Science Department, Boston University, 20140110)To provide widearea network services, resources from different infrastructure providers are needed. Leveraging the consensusbased resource allocation literature, we propose a general distributed auction mechanism for the ... 
Uniform test of algorithmic randomness over a general space
Gacs, Peter (Elsevier Science BV, 20050905)The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. ... 
Accelerated extragradient descent: a novel accelerated firstorder method
Orecchia, Lorenzo; Diakonikolas, Jelena (2018)We provide a novel accelerated firstorder method that achieves the asymptotically optimal convergence rate for smooth functions in the firstorder oracle model. To this day, Nesterov’s Accelerated Gradient Descent (agd) ...