HOME            RESEARCH            PUBLICATIONS            ABOUT & CV

 

OVERVIEW

My research explores connections between information theory, probability and statistics, ranging from fundamental questions about compression and randomness to the development and analysis of methods for statistical inference, computation, information transmission, machine learning and artificial intelligence. A recurring interest is how mathematical structure can be used both to establish performance limits and to design algorithms. The themes below describe longstanding work with collaborators, as well as recent and ongoing projects. References are to my publications list.

 

SELECTED CURRENT WORK

●       Information-theoretic foundations of distributed AI: co-investigator, EPSRC’s INFORMED-AI Hub

●       Learned image compression, with Deniz Gündüz and Yassine Hamdi

●       Efficient non-convex optimisation, with Sean Meyn [U7]

●       The sample complexity of channel coding, with Terence Viaud

●       Entropy estimation from genetic data, with Ian Henderson [Pre1]

 

COMPRESSION & ENTROPY ESTIMATION

Data compression is a foundational area, connecting efficient data storage and communication with statistical inference and even with the broad philosophical basis of scientific discovery. My early work examined data compression algorithms based on string-matching, for both lossless and lossy data compression, using techniques from ergodic theory and large deviations [J4, J5, J12]. Their analysis led to the realization that Shannon’s classical source coding theorems could be refined to more precise second-order asymptotic results [J1]. This theory extends to lossy data compression, where a new critical phenomenon was discovered: The redundancy rate is either of order n1/2 or O(log n), depending on the source distribution [J7, J8, J13]. It also led me to introduce a lossy version of the celebrated Lempel-Ziv algorithm, and its natural extension to multidimensional data [J6, J16]. Further connections with statistics, implementation complexity and lattice quantization were explored in [J9, J15, J20, J33].

My interest in entropy estimation began through the family of Lempel-Ziv-based estimators, and their applications to English text and spike-train data in neuroscience [Ch1, U2, J3, J24, C43]. A complementary line of work examined fundamental limits on the estimation of entropy and other functionals of discrete distributions [J11], and results on estimating the rate-distortion function [J25]. Also, with collaborators, I established a formal connection between the problem of estimating the directed information and detecting temporal causality [J37, J55]. More recently, we have been exploring principled Bayesian approaches for estimating the entropy rate of time-series data using the Bayesian Context Trees (BCT) framework [C123].

 

FUNDAMENTAL LIMITS & SAMPLE COMPLEXITY

Understanding and analysing the fundamental performance limits of data compression, estimation and communication has been one of the constant threads in my work. In addition to my “compression central limit theorem” and the subsequent results described above, in collaboration with Sergio Verdú we established definitive asymptotic coding theorems as well as nonasymptotic bounds for lossless data compression [J35]. In collaboration with Gavalakis, we then extended this work to the case of compression with side information [J42, J46], revealing a new phenomenon: Optimal performance depends critically on whether a single side-information data set is used repeatedly, or a fresh, independent data set is employed whenever a new message is compressed.

When strict performance guarantees are required in data compression, the corresponding fundamental limits in the “large deviations regime” were established in terms of the optimal pragmatic rate of a source in [J66], with corresponding bounds for hypothesis testing in [C23, C131]. And in the “moderate deviations regime”, when the excess-rate probability is small but subexponentially so, corresponding bounds were derived in [C76].

Recently, my Ph.D. student Terence Viaud and I introduced a framework for examining and evaluating the fundamental limits of data compression. Instead of considering the traditional rate-error probability trade-off in the long-blocklength regime, we adopted a different and genuinely nonasymptotic point of view. Motivated by recent developments in nonparametric statistics, we defined a new fundamental limit for data compression, the sample complexity, and we were able to obtain explicit, finite-blocklength bounds for data compression and universal data compression [J68].

In a related but different vein, in joint work with several students and colleagues we were recently able to obtain fine expansions for the best achievable performance in the problem of approximate channel simulation [C149].

 

ENTROPY INEQUALITIES IN PROBABILITY & COMBINATORICS

Since the early days of information theory, there has been a fascinating line of research that re-examines core probabilistic results through an information-theoretic lens. With collaborators, we were able to develop strong nonasymptotic bounds for Poisson approximation and thinning [J17, J29], using information-theoretic tools. We then generalised this approach to compound Poisson approximation [J28, C47] and to concentration bounds for compound Poisson measures [J21], viewing the compound Poisson distribution as a maximum entropy law within an appropriate class [J34]. More recently, we were able to give an information-theoretic proof of the classical discrete central limit theorem [J56], and to establish several new nonasymptotic versions of the celebrated de Finetti representation theorem with significantly improved – and in some cases best possible – rates [J50, Ch6, Ch3, C130, J62].

Over the past 20 years or so, there have been exciting developments in the use of information-theoretic tools and ideas in combinatorics, and in the reverse direction we have witnessed combinatorial ideas and techniques leading to new inequalities for the entropy. Two of the early papers exploring this connection resulted from my joint work with Madiman on deriving entropy inequalities inspired by additive combinatorics [J36, J40]. In further joint work with Madiman and Gavalakis, we applied related tools in order to bound the capacity of additive-noise channels and to establish the robustness of Gaussian codebooks [J60]. Subsequent joint work with Gavalakis and others developed additional connections with Shannon’s and Tao’s entropy power inequalities [J64, Pre4, Pre5]. A central question is whether near-equality in these entropy inequalities forces the underlying distributions to be close to their corresponding equality cases. In the more general case of random variables taking values in compact groups, stability results of the relevant entropy power inequalities were derived in [Pre6]. These were recently employed in [C147] to establish polarization on bounded Euclidean spaces and in more general compact groups.

 

MARKOV PROCESSES & STOCHASTIC ALGORITHMS

In addition to their very rich mathematical structure, Markov processes are perhaps the most successful family of probabilistic models used in applications. In collaboration with Sean Meyn and others, over the past 25+ years I have studied the spectral theory, convergence and large-deviations behaviour of Markov processes, and their implications for statistical computation. First, Meyn and I established a general framework for analysing the spectral properties and large deviations behaviour of Markov chains [J14, J18, C21, J32], including the development of theory for a strong form of ergodicity in an appropriate Sobolev space [J41]. For Markov processes in continuous time, we examined conditions for ergodicity in [J38], and we developed elements of their spectral theory in [J39]. In a related direction, we derived concentration bounds for geometrically ergodic Markov chains and used them to design effective stopping criteria for Monte Carlo estimation and simulation [J26, C56, C37, C46].

Markov chains also are key ingredients in machine learning methods. In [J48] we developed new differential temporal-difference (TD) learning algorithms for smooth Markovian models, established their consistency under appropriate conditions, and demonstrated substantial variance reduction relative to standard methods. The ODE method was employed in [J61] to establish moment bounds, general central limit theorems and asymptotic covariance results for stochastic approximation with Markovian noise, with applications to reinforcement learning. More recent work examines the effects of fixed step sizes on convergence, bias and variability in stochastic approximation algorithms for optimisation and learning [Pre3].

 

STATISTICAL INFERENCE, TIME SERIES & CAUSALITY

Bayesian methods offer a wealth of methodological tools as well as effective links to theoretical techniques. One of the first Bayesian problems I worked on was variance reduction for Markov chain Monte Carlo (MCMC) samplers used for Bayesian computation. With Petros Dellaportas we developed a general methodology using control variates that is applicable to a broad range of reversible MCMC samplers and often reduces the resulting estimation error by several orders of magnitude [J30, U4].

Working with a group of my former students led by Ioannis Papageorgiou, we proposed a general framework for the analysis of discrete time series, called Bayesian Context Trees (BCT). Based in part on the context tree weighting (CTW) data compression algorithm, Bayesian Context Trees model discrete time series whose dependence on the past varies with the observed context. They facilitate the use of exact Bayesian inference for numerous statistical tasks [J53, J54, J57, S1]. In addition to the more common problems of estimation, forecasting and model selection, we proposed new methods for changepoint detection [Ch5, C121] as well as entropy estimation as described above. A particularly exciting and somewhat unexpected further development was the extension of BCT to a much richer state-space model for real-valued time series [J65].

In a different direction, in the spirit of modern nonparametric statistics, work with Berrett and Samworth established optimal rates for independence testing using U-statistic permutation tests [J49], with accompanying software [S2]. More recently, in collaboration with several students and colleagues, we explored new theory and tools for detecting temporal causality (in the sense of Granger) for discrete time series, including in cases when a potentially confounding third time series is present [J37, J55]. And in related but distinct work, with a group of students and colleagues we examined Bayesian methods and theory for causal structure identification, and for quantifying the relative value of observational versus interventional data [Pre2, C144].

 

FURTHER CONNECTIONS

●       A bit of fun: Entropy and prime numbers! [J23, Ch2]

●       Some more fun: A new look at the infinite monkey theorem through entropy [J67], video

●       Wireless communications, ad hoc networks and routing [J10, J19, J43, J45, C67]  

●       Satellite image storage and analysis [J2, C3, U1, Pat1, Pat2]

●       Signal processing for linear systems driven by Lévy processes [J44, J58, C89, C102]

●       Conformal prediction in neural databases [C145]