Divergence-based characterization of fundamental limitations of adaptive
dynamical systems
(2010)cite arxiv:1010.2286Comment: 8 pages, uses ieeeconf.cls; to appear in Proc. 48th Annual Allerton Conf. on Communication, Control and Computing (2010).Abstract
Adaptive dynamical systems arise in a multitude of contexts, e.g.,
optimization, control, communications, signal processing, and machine learning.
A precise characterization of their fundamental limitations is therefore of
paramount importance. In this paper, we consider the general problem of
adaptively controlling and/or identifying a stochastic dynamical system, where
our a priori knowledge allows us to place the system in a subset of a
metric space (the uncertainty set). We present an information-theoretic
meta-theorem that captures the trade-off between the metric complexity (or
richness) of the uncertainty set, the amount of information acquired online in
the process of controlling and observing the system, and the residual
uncertainty remaining after the observations have been collected. Following the
approach of Zames, we quantify a priori information by the Kolmogorov
(metric) entropy of the uncertainty set, while the information acquired online
is expressed as a sum of information divergences. The general theory is used to
derive new minimax lower bounds on the metric identification error, as well as
to give a simple derivation of the minimum time needed to stabilize an
uncertain stochastic linear system.
Description
Divergence-based characterization of fundamental limitations of adaptive
dynamical systems
