我们证明了顺序蒙特卡洛(SMC)算法的有限样品复杂性,该算法仅需要相关的马尔可夫核的局部混合时间。当目标分布是多模式的,而马尔可夫内核的全局混合速度很慢时,我们的边界特别有用。在这种情况下,我们的方法确定了SMC比相应的Markov链蒙特卡洛(MCMC)估计量的好处。通过依次控制SMC重采样程序引入的偏差来解决全局混合。我们将这些结果应用于对数凸出分布的混合物下的近似期望获得复杂性界限,并表明SMC为某些困难的多模式问题提供了完全多项式时间随机近似方案,而相应的Markov链采样器的指数呈呈呈速度速度。最后,我们比较了通过我们在相同问题上使用钢结战的马尔可夫链的现有界限获得的界限。
translated by 谷歌翻译
Non-linear state-space models, also known as general hidden Markov models, are ubiquitous in statistical machine learning, being the most classical generative models for serial data and sequences in general. The particle-based, rapid incremental smoother PaRIS is a sequential Monte Carlo (SMC) technique allowing for efficient online approximation of expectations of additive functionals under the smoothing distribution in these models. Such expectations appear naturally in several learning contexts, such as likelihood estimation (MLE) and Markov score climbing (MSC). PARIS has linear computational complexity, limited memory requirements and comes with non-asymptotic bounds, convergence results and stability guarantees. Still, being based on self-normalised importance sampling, the PaRIS estimator is biased. Our first contribution is to design a novel additive smoothing algorithm, the Parisian particle Gibbs PPG sampler, which can be viewed as a PaRIS algorithm driven by conditional SMC moves, resulting in bias-reduced estimates of the targeted quantities. We substantiate the PPG algorithm with theoretical results, including new bounds on bias and variance as well as deviation inequalities. Our second contribution is to apply PPG in a learning framework, covering MLE and MSC as special examples. In this context, we establish, under standard assumptions, non-asymptotic bounds highlighting the value of bias reduction and the implicit Rao--Blackwellization of PPG. These are the first non-asymptotic results of this kind in this setting. We illustrate our theoretical results with numerical experiments supporting our claims.
translated by 谷歌翻译
Hamiltonian Monte Carlo(HMC)是Markov链算法,用于从具有密度$ e^{ - f(x)} $的高维分布中进行采样,可访问$ f $的梯度。一种特殊的感兴趣的情况是带有协方差矩阵$ \ sigma $的$ d $二维高斯分布,在这种情况下$ f(x)= x^\ top \ top \ sigma^{ - 1} x $。我们表明,HMC可以使用$ \ wideTilde {o}(\ sqrt {\ kappa} d^{1/4} \ log(1/\ varepsilon),使用$ \ varepsilon $ -close在总变化距离中取样。)$渐变查询,其中$ \ kappa $是$ \ sigma $的条件号。我们的算法对哈密顿动力学使用了长时间和随机的整合时间。这与最近的结果(并受到了)的形成对比,该结果给出了$ \ widetilde \ omega(\ kappa d^{1/2})$查询的HMC较低限制,即使是高斯案例,也有固定的集成时间。
translated by 谷歌翻译
重要性采样(IS)是一种使用来自建议分布和相关重要性权重的独立样本在目标分布下近似期望的方法。在许多应用中,只有直到归一化常数才知道目标分布,在这种情况下,可以使用自称为(SNIS)。虽然自我正态化的使用可能会对估计量的分散产生积极影响,但它引入了偏见。在这项工作中,我们提出了一种新方法BR-SNIS,其复杂性与SNI的复杂性基本相同,并且显着降低了偏见而不增加差异。这种方法是一种包装器,从某种意义上说,它使用了与SNIS相同的建议样本和重要性权重,但巧妙地使用了迭代采样(ISIR)重新采样(ISIR)来形成估算器的偏置版本。我们为提出的算法提供了严格的理论结果,包括新的偏见,方差和高概率界限,这些算法由数值示例进行了说明。
translated by 谷歌翻译
我们展示了具有高斯流程先验的非线性回归模型中产生的高维单模式后分布的示例后措施浓缩。基于梯度或随机步行步骤,对一般MCMC方案的反示例持有,该理论用于大都市 - 危机调整后的方法,例如PCN和MALA。
translated by 谷歌翻译
我们设计了快速算法,以反复从强烈的雷利分布中采样,其中包括随机跨越树分布和确定点过程。对于图$ g =(v,e)$,我们展示了如何大致统一的随机样本从$ g $ in $ \ wideTilde {o}(\ lvert v \ rvert)$ plime plimation $ \ in tampl of $ \ wideTilde {o}(\ lvert v \ rvert)$ time。 widetilde {o}(\ lvert e \ rvert)$时间预处理。对于$ n $元素的地面集的尺寸$ k $子集的确定点过程,我们将显示如何在$ \ widetilde {o}(k^\ omega)$ time of timit $ \ wideTilde { o}(nk^{\ omega-1})$时间预处理,其中$ \ omega <2.372864 $是矩阵乘法指数。我们甚至改进了从确定点过程中获取单个样本的最新技术,从$ \ widetilde {o}的先前运行时(\ min \ {nk^2,n^\ omega \})$到$ \ widetilde {o}(nk^{\ omega-1})$。在我们的主要技术结果中,我们达到了强烈的雷利分布的最佳范围稀疏限制。在域稀疏中,从$ \ binom {[n]} {k} $上的分配$ \ mu $取样减少为$ \ binom {[t]} {k} $ for $ t \ ll的相关发行量的采样n $。我们表明,对于强烈的瑞利分布,我们可以实现最佳$ t = \ widetilde {o}(k)$。我们的还原涉及从$ \ widetilde {o}(1)$ domain-sparsparsified发行版进行采样,所有这些分布都可以有效地产生,假设$ \ mu $的边际上的近似近距离访问方便的访问。可以访问边际类似于访问连续分布的平均值和协方差,或者知道分布的“各向同性”,这是Kannan-lov \'asz-simonovits(KLS)的关键假设(KLS)的猜想,并基于基于最佳采样器它。我们认为我们的结果是KLS猜想的道德类似物及其对采样的后果,以实现强烈的瑞利度量。
translated by 谷歌翻译
在本文中,我们考虑从一类具有薄尾部的分布式采样,支持$ \ mathbb {r} ^ d $,并制作两个主要贡献。首先,我们提出了一种具有优化步骤(MAO)的新的大都市算法,其非常适合这种目标。我们的算法能够从分布中采样,其中Metropolic调整的Langevin算法(MALA)不收敛或缺乏理论保证。其次,我们在毛泽东混合时间上获得上限。我们的结果是通过模拟多目标分布的支持。
translated by 谷歌翻译
我们调查了一定类别的功能不等式,称为弱Poincar的不等式,以使Markov链的收敛性与均衡相结合。我们表明,这使得SubGoom测量收敛界的直接和透明的推导出用于独立的Metropolis - Hastings采样器和用于棘手似然性的伪边缘方法,后者在许多实际设置中是子表芯。这些结果依赖于马尔可夫链之间的新量化比较定理。相关证据比依赖于漂移/较小化条件的证据更简单,并且所开发的工具允许我们恢复并进一步延长特定情况的已知结果。我们能够为伪边缘算法的实际使用提供新的见解,分析平均近似贝叶斯计算(ABC)的效果以及独立平均值的产品,以及研究与之相关的逻辑重量的情况粒子边缘大都市 - 黑斯廷斯(PMMH)。
translated by 谷歌翻译
我们解决了从单个观测轨迹估算马尔可夫链的混合时间的基本问题。与以前考虑了希尔伯特空间方法来估计光谱差距的作品相反,我们选择了基于收缩的总变异的方法。具体而言,我们根据Dobrushin定义并估算了广义收缩系数。我们表明,与光谱差距不同,该数量可以控制到强烈通用常数的混合时间,并且对于非可逆链仍然有效。我们在系数周围设计了完全依赖数据的置信区间,该系数既比其光谱对应物更易于计算和更薄。此外,我们通过展示如何利用有关过渡矩阵的其他信息来启动超越最坏情况的分析,以便获得有关其相对于诱导统一规范的实例依赖性速率以及其某些混合属性。
translated by 谷歌翻译
我们研究了随机近似程序,以便基于观察来自ergodic Markov链的长度$ n $的轨迹来求近求解$ d -dimension的线性固定点方程。我们首先表现出$ t _ {\ mathrm {mix}} \ tfrac {n}} \ tfrac {n}} \ tfrac {d}} \ tfrac {d} {n} $的非渐近性界限。$ t _ {\ mathrm {mix $是混合时间。然后,我们证明了一种在适当平均迭代序列上的非渐近实例依赖性,具有匹配局部渐近最小的限制的领先术语,包括对参数$的敏锐依赖(d,t _ {\ mathrm {mix}}) $以高阶术语。我们将这些上限与非渐近Minimax的下限补充,该下限是建立平均SA估计器的实例 - 最优性。我们通过Markov噪声的政策评估导出了这些结果的推导 - 覆盖了所有$ \ lambda \中的TD($ \ lambda $)算法,以便[0,1)$ - 和线性自回归模型。我们的实例依赖性表征为HyperParameter调整的细粒度模型选择程序的设计开放了门(例如,在运行TD($ \ Lambda $)算法时选择$ \ lambda $的值)。
translated by 谷歌翻译
高维统计数据的一个基本目标是检测或恢复嘈杂数据中隐藏的种植结构(例如低级别矩阵)。越来越多的工作研究低级多项式作为此类问题的计算模型的限制模型:在各种情况下,数据的低级多项式可以与最知名的多项式时间算法的统计性能相匹配。先前的工作已经研究了低度多项式的力量,以检测隐藏结构的存在。在这项工作中,我们将这些方法扩展到解决估计和恢复问题(而不是检测)。对于大量的“信号加噪声”问题,我们给出了一个用户友好的下限,以获得最佳的均衡误差。据我们所知,这些是建立相关检测问题的恢复问题低度硬度的第一个结果。作为应用,我们对种植的子静脉和种植的密集子图问题的低度最小平方误差进行了严格的特征,在两种情况下都解决了有关恢复的计算复杂性的开放问题(在低度框架中)。
translated by 谷歌翻译
对复杂模型执行精确的贝叶斯推理是计算的难治性的。马尔可夫链蒙特卡罗(MCMC)算法可以提供后部分布的可靠近似,但对于大型数据集和高维模型昂贵。减轻这种复杂性的标准方法包括使用子采样技术或在群集中分发数据。然而,这些方法通常在高维方案中不可靠。我们在此处专注于最近的替代类别的MCMC方案,利用类似于乘客(ADMM)优化算法的庆祝交替方向使用的分裂策略。这些方法似乎提供了凭经验最先进的性能,但其高维层的理论行为目前未知。在本文中,我们提出了一个详细的理论研究,该算法之一称为分裂Gibbs采样器。在规律条件下,我们使用RICCI曲率和耦合思路为此方案建立了明确的收敛速率。我们以数字插图支持我们的理论。
translated by 谷歌翻译
在本文中,我们在使用离散的Langevin扩散的三个方案中从目标密度采样的误差提供非渐近上限。第一个方案是Langevin Monte Carlo(LMC)算法,歌曲的欧拉分散化的歌曲扩散。第二个和第三种方案分别是用于可微分电位和动力学Langevin Monte Carlo的动力学Langevin Monte Carlo(KLMC),用于两次可分视电位(KLMC2)。主要焦点是在$ \ mathbb r ^ p $的目标密度上,但不一定强烈地抖动。在两种类型的平滑假设下获得计算复杂度的界限:电位具有嘴唇连续梯度,并且电位具有嘴角连续的Hessian基质。采样误差由Wassersein-$ Q $距离测量。我们倡导在计算复杂性定义中使用新的维度适应缩放,当考虑Wasserstein-$ Q $距离时。所获得的结果表明,实现小于规定值的缩放误差的迭代次数仅取决于多项尺寸。
translated by 谷歌翻译
我们证明了连续和离散时间添加功能的浓度不平等和相关的PAC界限,用于可能是多元,不可逆扩散过程的无界函数。我们的分析依赖于通过泊松方程的方法,使我们能够考虑一系列非常广泛的指数性千古过程。这些结果增加了现有的浓度不平等,用于扩散过程的加性功能,这些功能仅适用于有界函数或从明显较小的类别中的过程的无限函数。我们通过两个截然不同的区域的例子来证明这些指数不平等的力量。考虑到在稀疏性约束下可能具有高维参数非线性漂移模型,我们应用连续的时间浓度结果来验证套索估计的受限特征值条件,这对于甲骨文不平等的推导至关重要。离散添加功能的结果用于研究未经调整的Langevin MCMC算法,用于采样中等重尾密度$ \ pi $。特别是,我们为多项式增长功能$ f $的样品蒙特卡洛估计量$ \ pi(f)提供PAC边界,以量化足够的样本和阶梯尺寸,以在规定的边距内近似具有很高的可能性。
translated by 谷歌翻译
我们提出了改进的算法,并为身份测试$ n $维分布的问题提供了统计和计算下限。在身份测试问题中,我们将作为输入作为显式分发$ \ mu $,$ \ varepsilon> 0 $,并访问对隐藏分布$ \ pi $的采样甲骨文。目标是区分两个分布$ \ mu $和$ \ pi $是相同的还是至少$ \ varepsilon $ -far分开。当仅从隐藏分布$ \ pi $中访问完整样本时,众所周知,可能需要许多样本,因此以前的作品已经研究了身份测试,并额外访问了各种有条件采样牙齿。我们在这里考虑一个明显弱的条件采样甲骨文,称为坐标Oracle,并在此新模型中提供了身份测试问题的相当完整的计算和统计表征。我们证明,如果一个称为熵的分析属性为可见分布$ \ mu $保留,那么对于任何使用$ \ tilde {o}(n/\ tilde {o}),有一个有效的身份测试算法Varepsilon)$查询坐标Oracle。熵的近似张力是一种经典的工具,用于证明马尔可夫链的最佳混合时间边界用于高维分布,并且最近通过光谱独立性为许多分布族建立了最佳的混合时间。我们将算法结果与匹配的$ \ omega(n/\ varepsilon)$统计下键进行匹配的算法结果补充,以供坐标Oracle下的查询数量。我们还证明了一个计算相变:对于$ \ {+1,-1,-1 \}^n $以上的稀疏抗抗铁磁性模型,在熵失败的近似张力失败的状态下,除非RP = np,否则没有有效的身份测试算法。
translated by 谷歌翻译
We study non-parametric estimation of the value function of an infinite-horizon $\gamma$-discounted Markov reward process (MRP) using observations from a single trajectory. We provide non-asymptotic guarantees for a general family of kernel-based multi-step temporal difference (TD) estimates, including canonical $K$-step look-ahead TD for $K = 1, 2, \ldots$ and the TD$(\lambda)$ family for $\lambda \in [0,1)$ as special cases. Our bounds capture its dependence on Bellman fluctuations, mixing time of the Markov chain, any mis-specification in the model, as well as the choice of weight function defining the estimator itself, and reveal some delicate interactions between mixing time and model mis-specification. For a given TD method applied to a well-specified model, its statistical error under trajectory data is similar to that of i.i.d. sample transition pairs, whereas under mis-specification, temporal dependence in data inflates the statistical error. However, any such deterioration can be mitigated by increased look-ahead. We complement our upper bounds by proving minimax lower bounds that establish optimality of TD-based methods with appropriately chosen look-ahead and weighting, and reveal some fundamental differences between value function estimation and ordinary non-parametric regression.
translated by 谷歌翻译
马尔可夫链Monte Carlo(MCMC)为难以相干后望的渐近一致的估计提供,因为迭代的数量趋于无穷大。但是,在大数据应用中,MCMC可计算地计算地昂贵。这催化了对诸如MCMC等近似MCMC的采样方法的兴趣,这对渐近一致性进行了改善的计算速度。在本文中,我们提出了基于马尔可夫链耦合的估计,以评估这种渐近偏置的采样方法的质量。估计器给出了渐近偏置抽样方法的限制分布与利息的原始目标分布之间的韦斯特·距离的经验上限。我们为我们的上限建立了理论担保,并表明我们的估算变量能够在高维度方面保持有效。我们将质量措施应用于随机梯度MCMC,变分贝叶斯和LAPPAlt近似为高数据,并在50000维度中以4500维度和贝叶斯线性回归近似MCMC。
translated by 谷歌翻译
我们介绍内核变薄,更有效地压缩了一个新的程序,而不是i.i.d. \采样或标准变薄。给定合适的再现内核$ \ mathbf {k} $和$ \ mathcal {o}(n ^ 2)$ time,内核变薄将$ n $ thepoint近似压缩为$ \ mathbb {p} $ to to $ \ sqrt {n} $ - 点近似与相关的再现内核希尔伯特空间相比的可比最坏情况集成错误。具有高概率,集成错误中的最大差异是$ \ mathcal {o} _d(n ^ { - 1/2} \ sqrt {\ log n})$,用于紧凑地支持$ \ mathbb {p} $和$ \ mathcal {o} _d(n ^ { - \ frac {1} {2}}(\ log n)^ {(d + 1)/ 2} \ sqrt {\ log \ log n})$ for子指数$ \ $ \ mathbb {r} ^ d $上的mathbb {p} $。相反,来自$ \ mathbb {p} $ \ oomega(n ^ { - 1/4})$ Integration错误的平等大小。我们的子指数保证类似于统一$ \ mathbb {p} $ on $ [0,1] ^ d $的典型准蒙特卡洛错误速率,但适用于$ \ mathbb {r} ^ d $和a的常规发行版广泛的常见内核。我们使用我们的结果推导出Gaussian,Mat \'ern和B样曲线内部的显式非渐近最大平均差异界限,并提出了两个渐晕,说明了内核变薄的实际益处,而\采样和标准马尔可夫链蒙特卡罗稀疏,尺寸$ d = 2美元到100美元。
translated by 谷歌翻译
我们研究了情节块MDP中模型估计和无奖励学习的问题。在这些MDP中,决策者可以访问少数潜在状态产生的丰富观察或上下文。我们首先对基于固定行为策略生成的数据估算潜在状态解码功能(从观测到潜在状态的映射)感兴趣。我们在估计此功能的错误率上得出了信息理论的下限,并提出了接近此基本限制的算法。反过来,我们的算法还提供了MDP的所有组件的估计值。然后,我们研究在无奖励框架中学习近乎最佳政策的问题。根据我们有效的模型估计算法,我们表明我们可以以最佳的速度推断出策略(随着收集样品的数量增长大)的最佳策略。有趣的是,我们的分析提供了必要和充分的条件,在这些条件下,利用块结构可以改善样本复杂性,以识别近乎最佳的策略。当满足这些条件时,Minimax无奖励设置中的样本复杂性将通过乘法因子$ n $提高,其中$ n $是可能的上下文数量。
translated by 谷歌翻译
我们在具有Martingale差异噪声的可实现的时间序列框架中学习正方形损失。我们的主要结果是一个快速率的多余风险结合,这表明每当轨迹超收缩条件成立时,依赖数据的最小二乘估计器的风险与燃烧时间后的IID速率订单匹配。相比之下,从依赖数据中学习的许多现有结果都具有有效的样本量,即使在燃烧时间之后,有效的样本量也被基础过程的混合时间降低。此外,我们的结果允许协变量过程表现出远距离相关性,这些相关性大大弱于几何牙齿。我们将这种现象学习称为几乎没有混合的方式,并为其示出了几个示例:$ l^2 $和$ l^{2+\ epsilon} $ norms的有界函数类是等效的,有限的有限态Markov链,各种参数模型,以及一个无限尺寸$ \ ell^2(\ mathbb {n})$椭圆形的广阔家族。通过将我们的主要结果实例化,以使用广义线性模型过渡对非线性动力学的系统识别,我们仅在多项式燃烧时间后获得了几乎最小的最佳超量风险。
translated by 谷歌翻译