DMS-EPSRC: Fast martingales, large deviations and randomised gradients for heavy-tailed target distributions

马尔可夫链（Markov chain）是一个数学对象，它代表随机演化，具有以下性质：如果我们知道链的现在状态，它的过去和未来是独立的（即关于过去的信息不会改变其未来状态的分布）。马尔可夫链模型是科学和工程领域的基础。这个项目的核心是多维状态空间上的马尔可夫链，它出现在统计学和机器学习中使用的随机算法中。本文主要对应用中链的极限分布有重尾情况下产生的链进行理论分析。对重尾现象的分析对于随机化算法的未来成功至关重要，原因有两个：(a)它们在许多应用问题中自然出现；(b)由于违反现有理论中的标准假设（例如，极限分布在无穷远处的势的渐近线性），因此很难被很好地理解。(a)在许多应用中自然出现重尾极限分布。例如，如果回归模型中的误差按照柯西分布分布，则后验密度具有多项式尾部。也许一个更令人吃惊的事实是，即使重尾分布没有出现在模型的定义中，重尾也可能出现在后验。如果数据集中的误差是异方差的，这意味着误差项的方差随每次观测值而变化，则有必要使用所谓的稳健回归（基于例如Lasso-type惩罚）来减少异常值的影响。同样，后侧有很重的尾巴。(b)已知谱隙的存在等价于马尔可夫链的几何收敛。然而，正如最近在排队文献中指出的那样，在几何收敛下，遍历估计仍然可能表现出重尾型的大偏差行为。相反，具有重尾平稳测度的马尔可夫链通常没有谱间隙，但可能仍然表现出良好的收敛性。EPSRC-NSF领导机构协议提供了一个独特的机会，将美国在理论运筹学方面的专业知识与英国在计算统计学方面的能力相结合，从而产生新的方法来分析具有重尾目标的马尔可夫链的收敛性，这是该项目的主要焦点。我们的主要目标是填补文献中的空白，下面的应用基线算法最好地说明了这一点：一个随机扫描的Metropolis-within- gibbs链随机选择目标分布的一个坐标，并根据目标的条件通过一维Metropolis步移动它。可以证明，如果目标的任意一维边缘具有重尾，则随机扫描链不是几何遍历的。本提案的主要目标是为分析具有重尾目标的马尔可夫链的稳定性奠定理论基础，重点关注实践中使用的许多随机算法的基础过程。随着时间的推移，这项工作的影响预计将远远超出应用概率，在计算统计学和机器学习的许多子领域，这些领域出现了重尾目标。

Markov chain is a mathematical object representing a random evolution with the following property: if we know the present state of the chain, its past and future are independent (i.e. information about the past does not alter the distribution of its future states). Markov chain models are fundamental across sciences and engineering. At the centre of this project are Markov chains on multi-dimensional state spaces that arise in randomised algorithms used in statistics and machine learning. This proposal is focused on the theoretical analysis of chains arising in applications in the case when their limiting distribution has heavy tails. The analysis of the heavy-tailed phenomena is crucial for the future success of randomised algorithms for two reasons: (a) they arise naturally in many applied problems and (b) are least well understood as they violate standard assumptions made in the existing theory (e.g. asymptotic linearity of the potential of the limit distribution at infinity).(a) Heavy-tailed limiting distributions arise naturally in many applications. For example, if the errors in a regression model are distributed according to a Cauchy distribution, the posterior density has polynomial tails. Perhaps a more startling fact is that heavy tails can arise in the posterior even though a heavy-tailed distribution does not appear in the definition of a model. If the errors in a data set are heteroscedastic, meaning that the variance of the error term varies with each observation, it is necessary to use the so-called robust regression (based on e.g. Lasso-type penalisation) in order to reduce the effect of the outliers. Again the posterior has heavy tails. (b) The presence of a spectral gap is known to be equivalent to geometric convergence of a Markov chain. However, as pointed out recently in the queueing literature, under geometric convergence ergodic estimators may still exhibit large deviation behaviour of the heavy-tailed type. Conversely, Markov chains with heavy tailed stationary measures typically do not have a spectral gap but might nevertheless exhibit good convergence properties. The EPSRC-NSF Lead Agency agreement presents a unique opportunity to combine the US expertise in theoretical Operations Research with the UK's capability in Computational Statistics, resulting in novel methodology for the analysis of the convergence of Markov chains with heavy-tailed targets, the main focus for this project.Our main goal is to fill the gap in the literature, best illustrated by the following baseline algorithm from applications: a random-scan Metropolis-within-Gibbs chain picks randomly a coordinate of a target distribution and moves it by a one-dimensional Metropolis step based on the conditional of the target. It is possible to prove that if ANY one-dimensional marginal of the target has heavy tails, the random-scan chain is NOT geometrically ergodic. The main goal of this proposal is to lay the theoretical foundations for the analysis of the stability of Markov chains with heavy-tailed targets, focusing on the processes that underpin many randomised algorithms used in practice. In time, this work is expected to have impact far beyond applied probability in a number of sub-areas of computational statistics and machine learning where heavy-tailed targets arise.