跳转至

On mixing rates for Bayesian CART

作者: Jungeum Kim, Veronika Ročková
来源: Electronic Journal of Statistics
主题: 非参数 / 半参数
相关性: 6/10
机构绿灯: University of Chicago（US News 前 50，免分进入精读）
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么 这个子方向要解决的根本问题是：在贝叶斯非参数回归（特别是基于树/森林的模型）中，后验分布的统计最优性（如收敛速率、覆盖率）与计算可达性（MCMC 算法的 mixing time）之间是否存在鸿沟。当前成熟度处于“统计理论已基本完备，但计算复杂度理论刚刚起步”的阶段——人们已经知道树后验能达到近 minimax 速率，但直到最近才开始严格证明用来逼近这些后验的 MCMC 链到底需要跑多久。

发展脉络 - 奠基工作（统计理论）：Castillo & Ročková (2019) [5] 将 Bayesian CART 重构为“结构化小波收缩”，证明其后验在 supremum norm 下达到近 minimax 收敛速率，并构造了自适应置信带。Ročková & Rousseau (2021) [4] 进一步证明 spike-and-slab 先验与 Bayesian CART 在局部 Hölder 函数下具有局部自适应速率。这两篇确立了后验作为统计对象是优良的，但未触及 MCMC 的计算复杂度。 - 主要进展（计算复杂度初探）：Yang, Wainwright & Jordan (2015) [7] 在高维贝叶斯变量选择中，通过 canonical path ensemble 证明 Metropolis-Hastings 算法在截断稀疏先验下可达到线性（对数因子内）的 mixing time，首次将后验集中与快速 mixing 显式挂钩。Belloni & Chernozhukov (2007) [15] 在大样本下对 Metropolis 随机游走给出了多项式复杂度界，但依赖于准后验的 Laplace-Bernstein-Von Mises 形状（局部正态），对树这种离散/非凸空间不适用。 - 当前 frontier（树模型的 mixing 下界与补救）：Ronen 等 (2022) [6] 对简化版 BART 给出了指数级 mixing time 下界，首次严格证实了树 MCMC 的慢 mixing 现象。Zhou 等 (2021) [3] 在变量选择中证明 informed proposal 可达到与维数无关的 mixing time，展示了“利用局部后验信息加速”的路线。Pratola (2013) [2] 提出树旋转等复杂 proposal 以改善 mixing，但无理论速率。 - 本文的位置：填补了 Bayesian CART（单树）mixing time 上界的空白，同时给出标准 grow-and-prune 的指数下界，并提出 Twiggy/informed 变体以多项式时间绕过障碍。

子线索聚类 1. 后验统计最优性：[5, 4, 16]——证明树后验/森林后验在统计上达到 minimax 或局部自适应速率，不涉及计算。 2. MCMC mixing time 理论（变量选择/连续空间）：[7, 3, 15]——在变量选择或准后验框架下给出多项式 mixing 界或 dimension-free 界，为树模型提供方法论参照（canonical path, informed proposal, drift condition）。 3. 树 MCMC 的实证慢 mixing 与工程补救：[2, 18, 20, 19, 12]——从工程角度提出旋转、SMC、Particle Gibbs、XBART warm start 等加速方案，缺乏严格 mixing rate 分析。 4. 树 MCMC 的严格下界：[6]——给出 BART（单树简化版）的指数 mixing 下界，揭示标准 proposal 的根本缺陷。

这个方向在追问的核心问题 1. Stat-Computing Gap 是否存在？ 后验集中速率快，是否意味着 MCMC 也能快速逼近它？[6] 给出了下界证据，本文补充上界与条件，显式刻画了 gap 的边界（信号结构假设）。 2. 信号结构如何决定 mixing rate？ 树后验的支撑集依赖于信号的树拓扑连通性；孤立信号 vs 连通信号是否导致 polynomial vs exponential 的分野？ 3. Proposal 设计能否消除 gap？ 局部 proposal（grow/prune）vs 全局 proposal（twig attach/detach）vs informed proposal，在何种假设下能将 exponential 降为 polynomial 甚至 dimension-free？

⚠️ 作者的 framing - 作者的说法：作者将缺口 frame 为“Bayesian CART 的 inferential theory 已有 [5, 4]，但 MCMC mixing time 的刻画除了下界 [6] 外几乎空白”，从而将自己的工作定位为“首次给出 mixing 上界、揭示信号连通性假设的关键角色、并提出 Twiggy/informed 变体实现多项式 mixing”。 - 被淡化的竞争路线：SMC/Particle Gibbs [18, 20] 与 XBART [19] 作为替代采样/初始化方案，作者仅在背景中提及，未在理论层面比较其 mixing rate；变量选择中的 dimension-free informed proposal [3] 被引用为方法论灵感，但作者未讨论 BART 森林（多树）的 mixing 是否也能 dimension-free。 - 缺失的引用：泛函空间上的 MCMC mixing 理论（如 Hamiltonian Monte Carlo 在连续非参数模型中的 spectral gap 分析）未出现；低维树结构上的 combinatorial mixing 分析（如 random walk on binary trees 的 hitting time 经典结果）也未引用。这可能是作者刻意聚焦于“统计信号结构驱动的 mixing”所致，但读者可去查：连续非参数 MCMC 的 mixing bound 是否与这里的 polynomial/exponential 分野有对应关系？

张力 未见明显对立引用。[6] 给出指数下界，本文给出指数下界（强化）与多项式上界（条件性），两者在“标准 proposal 下存在 exponential barrier”上是一致的；张力体现在“是否需要连通性假设才能多项式 mixing”——本文说“需要（对标准 proposal）”，但 Twiggy 变体说“不需要”，这是内部张力，而非文献间对立。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据

  • \(f_0\)：真实回归函数（未知，要估的对象），属于 \(L^2[0,1]\) 或局部 Hölder 类。
  • \(Y_i\)：可观测响应变量，\(Y_i = f_0(x_i) + \varepsilon_i\)，\(i=1,\dots,n\)。
  • \(x_i\)：可观测设计点，固定在 \([0,1]\) 上的等距网格 \(x_i = i/n\)（固定设计）。
  • \(\varepsilon_i\)：不可观测噪声，\(\varepsilon_i \sim \mathcal{N}(0, \sigma^2)\)，\(\sigma^2\) 已知（简化设定；论文也讨论 \(\sigma^2\) 未知但先验集中于真值的情况）。
  • \(T\)：二叉回归树（随机变量，MCMC 的状态），由内部节点集合 \(T_{\text{int}}\)（决定分割规则）和终端节点集合 \(T_{\text{term}}\)（叶子，决定局部常数拟合）构成。\(T\) 的深度/结构是随机的。
  • \((l,k)\)：树节点的坐标，\(l\) 为深度（level），\(k\) 为该深度下的位置索引，\(l=0\) 为根节点。
  • \(\Theta_T\)：树 \(T\) 下的参数向量（叶子均值），维度 \(= |T_{\text{term}}|\)。
  • \(\Pi(\cdot \mid Y_1,\dots,Y_n)\)：树后验分布（目标分布），由先验 \(\Pi(T)\)（节点分裂概率 \(p_{lk}\) 控制）与似然 \(L(Y \mid T, \Theta_T)\) 构成。
  • \(K\)：MCMC 转移核（proposal + accept/reject），\(T^{(i)} \sim K(T^{(i-1)}, \cdot)\)。
  • \(\tau_{\text{mix}}(\epsilon)\)：Mixing time，定义为达到总变差距离 \(\leq \epsilon\) 所需的最小迭代步数，\(\tau_{\text{mix}}(\epsilon) = \min\{t : \max_{T_0} \|K^t(T_0, \cdot) - \Pi(\cdot \mid Y)\|_{\text{TV}} \leq \epsilon\}\)。
  • \(\beta_{lk}\)：小波系数（wavelet representation），\(f_0\) 在树 \(T\) 下的投影系数，\(\beta_{lk} \approx \int f_0 \psi_{lk}\)。树后验可重构为对 \(\{\beta_{lk}\}\) 的结构化收缩。

第二步：最小内核——深层孤立信号下的 exponential barrier

剥掉所有一般性讨论，支撑本文核心论断的最小内核是：一个深层孤立的大信号系数，如何让标准 grow-and-prune MCMC 卡死。

  • 最简特例设定：假设 \(f_0\) 的小波表示中，只有一个系数 \(\beta_{L,k^*}\) 显著非零（\(L\) 较深，如 \(L \sim \log_2 n\)），其余所有系数近乎零。这对应一个极窄的尖峰信号。真实树 \(T^*\) 必须在深度 \(L\) 的位置 \(k^*\) 有一个内部节点（才能捕捉该系数），而从根到该节点的路径上所有祖先节点 \((l, k_l)\) 也必须存在（树的结构约束）。
  • 标准 proposal 的困境：标准 Bayesian CART 的 proposal 只有 grow（在某叶子节点分裂，增加一个内部节点）和 prune（删除一个内部节点，合并两个叶子）。要从空树（或浅树）到达 \(T^*\)，必须依次 grow 出从根到 \((L, k^*)\) 的整条路径。每一步 grow 的候选节点是当前树的所有叶子（数量随深度增长），而分裂位置 \(k_l\) 的选择是连续区间离散化后的众多候选。关键在于：在路径尚未完成时，中间步骤的树拟合极差（因为中间树只能用局部常数拟合一个尖峰，残差巨大），导致后验概率 \(\Pi(T_{\text{intermediate}} \mid Y)\) 极低；而 grow proposal 提议这些中间树的概率被分散到众多叶子与分割位置上。结果：从浅树向深树转移的接受率极低，链在浅树处停留极久。
  • 要证的命题（退化形式）：在上述孤立信号设定下，标准 grow-and-prune MCMC 的 mixing time 下界为 \(\tau_{\text{mix}} \geq C \cdot e^{c L}\)（\(L \sim \log_2 n\) 时即为 \(e^{c' n}\) 量级），即 exponential in \(n\)。
  • 证明直觉：构造一个瓶颈集 \(A\)（包含所有不包含节点 \((L, k^*)\) 的树），证明从 \(A\) 转移到补集 \(A^c\)（包含 \((L, k^*)\) 的树）的概率极小（因为需要连续多次“幸运”的 grow 提议且被接受），而 \(A^c\) 的后验质量不小（因为 \(T^*\) 拟合好）。由 Cheeger 不等式或直接 conductance 论证，spectral gap 极小，mixing time 极大。
  • Twiggy 变体如何破局：Twiggy Bayesian CART 的 proposal 不是 grow/prune 单个节点，而是 attach/detach 整条 twig（从某叶子到目标深度的一条完整路径）。在孤立信号例子中，一步 attach 就能从浅树直接跳到包含 \((L, k^*)\) 的深树，绕过了中间极低后验概率的瓶颈。因此 mixing time 从 exponential 降为 polynomial。

三、这篇论文做了什么

三句话 ①研究了 Bayesian CART MCMC 算法的 mixing time 上界与下界，刻画了信号结构假设与 proposal 设计对收敛速率的影响。 ②核心工具是树的小波表示（将树后验重构为结构化小波收缩）与 canonical path / drift condition / conductance 分析。 ③主要结论：标准 grow-and-prune 在信号满足 hierarchical connectivity 时多项式 mixing，但对深层孤立信号 exponential mixing；Twiggy Bayesian CART 无需 connectivity 假设即可多项式 mixing；informed 变体可达更快收敛。

关键设定与假设 - 模型：非参数回归 \(Y_i = f_0(x_i) + \varepsilon_i\)，固定等距设计，\(\varepsilon_i \sim \mathcal{N}(0, \sigma^2)\)，\(\sigma^2\) 可已知或未知（未知时配 Inverse-Gamma 先验，后验集中于真值）。 - 先验： - 树结构先验 \(\Pi(T)\)：节点 \((l,k)\) 分裂的概率 \(p_{lk} = \alpha (1 + l)^{-\beta}\)（\(\alpha, \beta\) 控制树的深度与大小），分裂位置均匀分布。 - 叶子参数先验 \(\Pi(\Theta_T \mid T)\)：独立 \(\mathcal{N}(0, \tau^2)\)，\(\tau^2\) 配 Inverse-Gamma 或固定为大值。 - 信号假设（关键）： 1. Hierarchical Connectivity：若深度 \(l\) 的系数 \(\beta_{lk}\) 显著（\(> \rho_n\)），则其所有祖先系数 \(\beta_{l',k'}\)（\(l' < l\)）也显著。这对应小波树上的连通信号（如连续函数的平滑区域或间断点）。这是标准 Bayesian CART 多项式 mixing 的充分条件。 2. Near-parametric Sparsity：显著系数数量 \(s_n = o(n / \log n)\)，保证后验集中在稀疏树上。 3. Signal Strength：显著系数 \(|\beta_{lk}| > \rho_n \asymp \sqrt{\log n / n}\)，保证检测性。 - 相比已有文献的放宽/强化： - 相比 [5, 4] 的后验集中理论，本文新增了 mixing time 分析，但统计假设基本沿用（connectivity 是 [5] 中树后验集中的自然条件，本文显式指出它也是 mixing 的关键）。 - 相比 [6] 的下界，本文给出匹配的下界（标准 proposal 下 exponential）并补充上界（connectivity 下 polynomial），刻画了完整边界。 - Twiggy 变体放宽了 connectivity 假设，在孤立信号下仍多项式 mixing，这是对 [5, 6] 假设的实质性放松。

主要结果

  1. Theorem 1（标准 Bayesian CART 的多项式 mixing 上界）：
  2. 陈述：在 hierarchical connectivity 与 near-parametric sparsity 假设下，标准 grow-and-prune Bayesian CART 的 mixing time \(\tau_{\text{mix}}(\epsilon) \leq C n^{c}\)（多项式级），其中常数依赖于 \(\alpha, \beta, \rho_n\)。
  3. 直觉：连通信号意味着真实树 \(T^*\) 的路径上每一步 grow 都能被后验支持（因为祖先系数也显著，中间树不会拟合极差），从而 canonical path 上的每步转移都有合理接受率，conductance 不太小。
  4. 必要条件：connectivity 假设是关键的；去掉它则退化为 exponential（见 Theorem 2）。

  5. 解决的技术难点：如何在离散树空间上构造 canonical path 并控制每步的接受率，同时处理树结构约束（分裂位置连续性离散化后的众多候选）与叶子参数的连续积分。

  6. Theorem 2（标准 Bayesian CART 的 exponential mixing 下界）：

  7. 陈述：存在信号配置（深层孤立大系数，不满足 connectivity），使得标准 grow-and-prune 的 mixing time \(\tau_{\text{mix}} \geq e^{c n}\)。
  8. 直觉：如最小内核所述，孤立信号导致中间树后验极低，conductance 极小。
  9. 必要条件：信号必须“深层且孤立”——浅层孤立信号仍可能被快速捕捉（因为 grow 步数少）。

  10. 解决的技术难点：构造具体的信号配置并严格计算 conductance 下界，需要精确控制 grow proposal 的分散性与中间树的后验质量。

  11. Theorem 3-4（Twiggy Bayesian CART 的多项式 mixing）：

  12. 陈述：Twiggy Bayesian CART（attach/detach 整条 twig）在无 connectivity 假设下，mixing time 仍为多项式级 \(\tau_{\text{mix}} \leq C n^{c'}\)；informed Twiggy 变体（利用局部后验信息加权提议 twig）可达更快速率（\(n\) 的更低阶多项式）。
  13. 直觉：twig attach 一步跳过瓶颈路径；informed proposal 进一步集中提议于高后验概率的 twig，减少无效探索。
  14. 解决的技术难点：twig attach 的候选空间更大（整条路径的分割位置组合），需证明提议概率的分散不会抵消一步跳跃的优势；informed proposal 需控制局部后验计算的额外成本并证明其不破坏 polynomial 界。

证明路线与技术技巧

  • 整体路线（Theorem 1 上界）：
  • 小波重构：将树后验 \(\Pi(T, \Theta_T \mid Y)\) 重构为对小波系数 \(\{\beta_{lk}\}\) 的结构化收缩后验，利用 [5] 的框架，将树结构约束转化为系数的连通性约束。
  • 后验集中：引用 [5] 的结果，证明后验集中在真实树 \(T^*\) 的邻域（\(T^*\) 包含所有显著系数的路径）。
  • Canonical Path 构造：在树空间上构造从任意树 \(T\) 到 \(T^*\) 的 canonical path，每步为单个 grow 或 prune（标准 proposal 支持的操作）。利用 connectivity 假设，保证路径上每步的中间树 \(T_i\) 都包含 \(T^*\) 的某个祖先子树，从而拟合不极差。

  • Conductance/Spectral Gap 界：通过 canonical path 的流量分析，控制每步转移的接受率下界，进而得到 conductance 下界 \(\Phi \geq \text{poly}(1/n)\)，由 Cheeger 不等式得 spectral gap \(\geq \text{poly}(1/n)\)，mixing time \(\leq \text{poly}(n)\)。

  • 整体路线（Theorem 2 下界）：

  • 构造孤立信号：设定 \(f_0\) 只有深层系数 \(\beta_{L,k^*}\) 显著。
  • 瓶颈集构造：定义 \(A\) 为所有不包含节点 \((L, k^*)\) 的树集合，证明 \(\Pi(A \mid Y)\) 不极小（因为浅树有先验支持）。
  • 转移概率界：计算从 \(A\) 到 \(A^c\) 的转移概率上界 \(K(A, A^c) \leq e^{-c n}\)，因为需要连续 \(L\) 次 grow 且每次分裂位置必须精确命中 \(k^*\) 的祖先路径，概率极小。

  • Conductance 下界：由 \(\Phi \leq K(A, A^c) / \Pi(A \mid Y) \leq e^{-c' n}\)，得 mixing time \(\geq 1 / \Phi \geq e^{c' n}\)。

  • 整体路线（Theorem 3-4 Twiggy 上界）：

  • Twig 操作定义：attach = 在某叶子下一次性生长出深度 \(d\) 的完整子树（twig）；detach = 删除某内部节点下的整棵子树。候选 twig 的分割位置组合是多项式级（\(O(n^d)\)）。
  • Canonical Path 修改：从 \(T\) 到 \(T^*\) 的路径不再逐步 grow，而是按 twig 逐步 attach；每步 attach 直接跳过瓶颈，因为整条 twig 的拟合改善是显著的（即使信号孤立，twig 包含目标节点后拟合立即改善）。
  • 接受率控制：twig attach 的提议概率虽分散（\(O(1/n^d)\)），但接受率因拟合改善而高（\(O(1)\) 或 \(\text{poly}(1)\)），且 detach 的反向转移概率也有合理控制（先验惩罚与拟合恶化的平衡），总体 conductance \(\geq \text{poly}(1/n)\)。

  • Informed 变体：利用局部后验信息（如残差下降量）加权提议 twig，将提议概率集中于高接受率 twig，进一步提升 conductance。

  • 关键跳跃点：

  • 从树空间到小波空间的映射：这是本文的理论基石，允许将树结构的组合复杂性转化为系数空间的代数结构，从而利用 [5] 的后验集中结果。难点在于树结构约束（分裂位置依赖）在小波空间中表现为系数的连通性，如何精确控制这一映射的误差。

  • Canonical Path 上的接受率精确计算：标准 proposal 的接受率涉及连续参数（叶子均值）的积分与离散结构（分裂位置）的组合数，需要同时控制两者；本文通过“条件先验”（给定树结构下参数的先验）与“似然比”的分解，将接受率简化为可计算的量。

  • 技术技巧点名：

  • Wavelet representation of trees（[5] 的框架）：将树后验重构为结构化小波收缩，利用树拓扑诱导的系数相关性，是后验集中与 mixing 分析的统一基础。
  • Canonical path ensemble（[7] 的方法）：在离散状态空间上构造从任意状态到目标状态的路径集合，通过流量分析控制 conductance，是 mixing 上界的标准工具。
  • Drift condition / Two-stage drift（[3] 的启发）：对 informed proposal 变体，使用 drift condition（向高后验区域漂移）替代纯 conductance 分析，以处理非均匀提议概率。
  • Cheeger's inequality：连接 conductance 与 spectral gap，是 mixing time 界的桥梁。
  • Tail bounds for \(\chi^2\)（[24]）：控制噪声项 \(\|\varepsilon\|_2^2\) 的尾部，用于证明后验集中在拟合好的树上（似然比检验的阈值化）。
  • Twig attach/detach proposal：本文新提出的组合操作，一步修改整条路径而非单节点，是绕过 exponential barrier 的关键设计。

真实例子与应用 - 仿真实验：论文包含 thorough simulation study，对比 spike-and-slab prior（连续小波空间）与 Bayesian CART（离散树空间）在多种 proposal（标准 grow/prune, Twiggy, informed Twiggy）下的 mixing 表现。 - 场景设计：构造满足 connectivity 的信号（如 Doppler, Blocks）与孤立信号（如单尖峰），观察不同 proposal 的收敛轨迹（trace plot of tree depth/fit）。 - 结果：标准 Bayesian CART 在连通信号下 mixing 可接受，在孤立信号下极慢；Twiggy 在孤立信号下显著加速；informed Twiggy 最快。Spike-and-slab prior（连续空间）在孤立信号下也慢，但比标准树 proposal 好（因为连续空间无树结构约束）。 - 说明什么：验证理论预测（connectivity 决定标准 proposal 的 mixing；twig 操作绕过瓶颈；informed 进一步加速），并展示树模型与连续小波模型在计算复杂度上的结构性差异。

🔎 结论是否比证明窄 - Theorem 1 的多项式上界在 connectivity 假设下严格证明，但作者在讨论中暗示“实际中许多信号近似满足 connectivity”，这是泛泛 claim，未严格量化“近似连通”的容忍度（多少孤立小系数可被容忍仍保持多项式 mixing）。 - Theorem 3-4 的 Twiggy 多项式界在无 connectivity 假设下证明，但依赖于 twig 深度 \(d\) 的选择（\(d\) 需足够大以覆盖孤立信号的深度），作者未显式讨论 \(d\) 的自适应选择如何影响 mixing rate（实际中 \(d\) 是固定的或随机选择的，理论界可能随 \(d\) 增大而变差）。 - Informed Twiggy 的更快速率在定理中陈述，但证明细节相对简略（依赖 drift condition 的泛界），具体的速率阶数（如 \(n^{c}\) vs \(n^{c'}\) 的 \(c, c'\) 差异）未完全显式化。

四、开放问题（点到为止，扎根具体语句）

  1. 多树森林（BART）的 mixing time 界：本文聚焦单树 Bayesian CART，而 BART 是多树叠加；作者在 intro 提到“BART 的 backfitting 可能缓解单树的慢 mixing”，但未给出理论界。要证什么：BART MCMC（多树交替更新）在孤立信号下的 mixing time 是 polynomial 还是 exponential？扎根于 intro 第 1 页“Another way to prevent single trees from getting stuck is by adding them up and by performing Bayesian back-fitting (see the BART method of [11])”——这是未严格验证的 claim。

  2. “近似连通”信号的 mixing rate 量化：Theorem 1 要求严格 hierarchical connectivity，实际信号常有少量孤立小系数；要估什么：容忍 \(k\) 个孤立系数时，标准 proposal 的 mixing time 从 polynomial 退化为何种 rate（如 \(n^{c} \cdot e^{c' k}\)）？扎根于 Section 6 讨论“connectivity restriction may be typically satisfied in practice”——这是泛泛断言，未给出量化容忍度。

  3. Twig 深度 \(d\) 的自适应选择与 mixing rate 的依赖关系：Theorem 3 的多项式界隐式依赖于 twig 深度 \(d\) 足够大以覆盖信号深度；要算什么：若 \(d\) 随机选择或随链迭代自适应调整，mixing rate 如何变化？扎根于 Section 4 Twiggy Bayesian CART 定义中 \(d\) 的固定设定——理论界未显式包含 \(d\) 的成本。

  4. 连续小波空间（spike-and-slab）与离散树空间的 stat-computing gap 精确比较：仿真显示 spike-and-slab 在孤立信号下也慢但比标准树好；要证什么：spike-and-slab MCMC 在孤立信号下的 mixing time 下界是何种阶数（exponential in \(n\) or in \(\log n\)）？扎根于 Section 5 仿真对比与 Section 6 讨论“discrepancies between spike-and-slab priors and Bayesian CART”——这是实证观察，未严格理论化。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论