FUNDAMENTAL PERFORMANCE LIMITS OF STATISTICAL PROBLEMS: FROM DETECTION THEORY TO SEMI-SUPERVISED LEARNING

Abstract

Designing and analyzing close-to-optimal mechanisms to infer or learn useful information from raw data is of tremendous significance in this digital and data-rich era. This thesis explores the fundamental performance limits of three classes of statistical problems—distributed detection, change-point detection and the generalization capabilities of semi-supervised learning (SSL). For the detection problems, in contrast to classical works assuming known underlying data distributions, we consider the practical scenario where training data samples are available instead. We derive the asymptotically optimal detector and error exponent for distributed detection (or detection confidence width for change-point detection). For the statistical learning problem, we are motivated to mitigate the high cost of acquiring labelled data. We analyze the fundamental limits of SSL which makes use of both labelled and unlabelled training data. Using information-theoretic principles, we investigate the generalization error, which quantifies the extent to which the algorithms overfit to the training data.