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

DMS-EPSRC：重尾目标分布的快速鞅、大偏差和随机梯度

基本信息

批准号：
EP/V009478/1
负责人：
Aleksandar Mijatovic
金额：
$ 84.43万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2021
资助国家：
英国
起止时间：
2021 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV009478%2F1
关键词：
DMS EPSRC Fast martingales large

项目摘要

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.

马尔可夫链是代表具有以下属性的随机演变的数学对象：如果我们知道链的当前状态，那么它的过去和未来是独立的（即有关过去的信息不会改变其未来状态的分布）。马尔可夫链模型是科学和工程的基本。该项目的中心是在统计和机器学习中使用的随机算法中出现的多维状态空间上的马尔可夫链。该提案的重点是在其限制分布较重的情况下，在应用中产生的链条的理论分析。对重尾现象的分析对于随机算法的未来成功至关重要。例如，如果回归模型中的误差是根据cauchy分布分布的，则后密度具有多项式尾巴。也许更令人震惊的事实是，即使模型的定义没有出现重尾分布，但后部可能会出现重尾巴。如果数据集中的误差是异质的，这意味着误差项的差异随每个观察结果而变化，则有必要使用所谓的鲁棒回归（基于例如套索型罚款），以减少异差的效果。同样，后部有沉重的尾巴。（b）已知光谱间隙的存在等效于马尔可夫链的几何融合。然而，正如最近在排队文献中指出的那样，在几何收敛下，厄尔贡估计量仍可能表现出重尾类型的较大偏差行为。相反，马尔可夫链条具有重型尾部固定措施通常没有频谱差距，但可能表现出良好的收敛性。 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大都会 - 吉布斯链链随机选择目标分布的坐标，并根据目标的条件将其移动一维大都市步骤。有可能证明，如果任何目标边缘的边际有重尾，那么随机扫描链不会在几何上具有痕迹。该提案的主要目的是奠定理论基础，以分析马尔可夫链的稳定性具有重尾目标，重点是基于实践中许多随机算法的过程。随着时间的流逝，这项工作有望在许多计算统计和机器学习的子方面的概率远远超出了重型目标的概率。