跳转至

Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data

讲者: Yang Ning
会场: Advancements in Statistical Learning for Precision Medicine
报告题目: Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

本文研究的子方向是测量约束下的高维M估计，具体聚焦于最优个性化阈值估计。根本的统计问题是：在只能标记少量样本（标签预算N远小于总样本量n）的情况下，如何主动选择哪些样本去标记，以最快速度估计一个高维稀疏参数θ ∈ ℝ^d，该参数定义了一个线性阈值θ^T Z，使得连续变量X是否超过该阈值与二元结果Y的“不一致”最小化。该问题是非正则的（收敛率慢于√N），且在高维下需要正则化。当前成熟度：已有i.i.d.设定下的minimax最优率（Feng et al., 2022），但主动采样能否突破该率、达到参数速率，是本文要回答的核心问题。

发展脉络（history）

  • 奠基工作：Jaeschke et al. (1989) 提出最小临床重要差异（MCID）的概念，定义了一个全局阈值。Hedayat et al. (2015); Zhou et al. (2020) 将其推广为个性化阈值（iMCID），形式化为(1.1)的优化问题，并引入线性结构c(Z)=θ^T Z。
  • 主要进展：Manski (1975) 的最大得分估计量（maximum score estimator）本质上求解同一优化问题，但计算困难且收敛率为n^{-1/3}（Kim and Pollard, 1990）。Feng et al. (2022) 提出用光滑替代损失（smoothed surrogate loss）和Lasso正则化，在高维下得到收敛率(slogd/N)^{β/(2β+1)}，并证明该率是minimax最优的（i.i.d.设定）。该工作解决了计算和理论问题，但假设数据是i.i.d.且标签可全部获得。
  • 当前frontier：测量约束问题（Wang et al., 2017; Zhang et al., 2021）和主动学习（Balcan et al., 2007; Castro and Nowak, 2008）分别从不同角度处理标签稀缺。但前者主要针对正则模型（线性回归、GLM），后者主要针对分类问题的0-1损失，且理论依赖于Tsybakov噪声条件。
  • 本文位置：本文首次将主动子采样引入非正则的高维阈值估计问题，证明通过迭代缩小采样区域，可以突破i.i.d.下的minimax率，达到参数速率(slogd/N)^{1/2}（当β足够大时），并建立了N-预算minimax框架证明其最优性。

子线索聚类

  1. 子采样/测量约束回归：Wang et al. (2017); Zhang et al. (2021); Zrnic and Candès (2024) 等，针对线性或广义线性模型，通过最小化渐近方差设计最优采样权重。本文与之不同：目标是非正则问题，且采样策略基于“近阈值点最信息”的直觉。
  2. 主动学习：Balcan et al. (2007); Koltchinskii (2010); Castro and Nowak (2008); Wang and Singh (2016) 等，主要针对分类问题，理论依赖Tsybakov噪声条件，算法通常需要多次迭代（logN次）。本文算法只需K=2（β>1.37时），且理论基于条件密度光滑性而非噪声条件。
  3. 半监督学习：Cai and Guo (2020); Zhang and Bradic (2022); Deng et al. (2024) 等，利用未标记数据提升效率，但采样方案固定（均匀）。本文主动设计采样方案。
  4. 非正则M估计：Kim and Pollard (1990); Feng et al. (2022, 2024) 研究阈值估计的渐近理论。本文在此基础上引入主动采样。

核心问题与已知瓶颈

  • 核心问题：给定标签预算N，如何选择样本以最小化θ的估计误差？主动采样能否比均匀采样获得更快的收敛率？最优率是多少？
  • 已知瓶颈：i.i.d.设定下，minimax最优率为(slogd/N)^{β/(2β+1)}（Feng et al., 2022），慢于参数速率。主动学习文献中，对于分类问题，在Tsybakov噪声条件下可达到指数加速，但本文问题不同（连续X，0-1损失，高维稀疏参数）。

⚠️ 作者的framing

作者将缺口frame为：“在测量约束下，主动采样可以加速非正则估计的收敛率，甚至达到参数速率”。具体地： - 他们强调与主动学习文献的区别：本文依赖条件密度光滑性β而非Tsybakov噪声条件，算法更简洁（K=2即可），且理论揭示了β的相变现象。 - 他们淡化/回避了：主动学习文献中margin-based方法（如Balcan et al., 2007）也能达到指数加速，但那些方法通常需要求解0-1损失（计算困难），且理论依赖于噪声条件。本文通过光滑替代损失和梯度方法避免了计算困难。 - 什么明显该被引/该存在、却没出现在intro里？ 论文未引用Mallik et al. (2020)（多阶段采样M估计），该文研究了类似的两阶段采样问题（β=1情形），但未涉及高维和相变。此外，关于“信息论下界”的经典工作（如Castro and Nowak, 2008的minimax下界）未被引用，但本文在定理5中独立建立了N-预算minimax下界。值得研究者去查：Mallik et al. (2020) 是否与本文β=1的结果有更直接的联系？本文Remark 2中提到了该文，但未在intro中引用。

张力

未见明显对立引用。各子线索之间没有直接矛盾，但主动学习文献与本文在假设和算法上存在差异，作者已明确区分。

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

第一步：符号、模型、可观测数据交代清楚

  • 符号：
  • \(X \in \mathbb{R}\)：连续测量变量（如HbA1c值）。
  • \(Y \in \{-1, +1\}\)：二元结果（如是否30天内再入院）。
  • \(Z \in \mathbb{R}^d\)：d维协变量（如人口统计、临床指标）。
  • \(\theta^* \in \mathbb{R}^d\)：待估的高维稀疏参数，定义阈值\(\theta^{*T}Z\)。
  • \(s = \|\theta^*\|_0\)：真实稀疏度。
  • \(n\)：未标记数据集大小（非常大）。
  • \(N\)：标签预算（可标记的期望样本数），\(N \ll n\)。
  • \(K\)：算法迭代次数。
  • \(N_k\)：第k次迭代的期望采样数，\(\sum_{k=1}^K N_k = N\)。
  • \(R_i \in \{0,1\}\)：采样指示变量，\(R_i=1\)表示第i个样本被选中并标记。
  • \(c_{n,k}\)：第k次迭代的采样概率（条件于活动集）。
  • \(b_{k-1}\)：第k次迭代活动集的半宽度。
  • \(\delta_k\)：第k次迭代的核平滑带宽。
  • \(\lambda_k\)：第k次迭代的Lasso正则化参数。
  • \(L_\delta(u) = \int_{u/\delta}^\infty K(t) dt\)：光滑替代损失，\(K(t)\)为核函数。
  • \(R(\theta) = \mathbb{E}[\gamma(Y) L_{01}(Y(X - \theta^T Z))]\)：总体风险，其中\(L_{01}(u) = \frac{1}{2}(1 - \text{sign}(u))\)为0-1损失，\(\gamma(y) = 1/P(Y=y)\)为权重。

  • \(\beta\)：条件密度\(f(x|y,z)\)在\(x = \theta^{*T}z\)处的Hölder光滑度。

  • 模型：

  • 数据生成：\((X_i, Z_i, Y_i) \overset{i.i.d.}{\sim} P\)，但\(Y_i\)不可观测（除非被采样）。
  • 目标参数：\(\theta^* = \arg\min_\theta R(\theta)\)，即最小化加权0-1风险。

  • 假设：\(\theta^*\)是s-稀疏的，\(\|\theta^*\|_2 \leq C\)；条件密度\(f(x|y,z)\)在\(x = \theta^{*T}z\)附近属于Hölder类\(\mathcal{P}(\beta, L)\)；协变量Z满足稀疏特征值条件等。

  • 可观测数据：

  • 未标记数据：\(\mathcal{D} = \{(X_i, Z_i)\}_{i=1}^n\)，所有样本的X和Z均可观测。
  • 标记数据：只有被选中的样本（\(R_i=1\)）才能观测到\(Y_i\)。因此，实际观测为\(\{(X_i, Z_i, Y_i) : R_i=1\} \cup \{(X_i, Z_i) : R_i=0\}\)。
  • 潜在不可观测：所有未选中样本的\(Y_i\)永远不可知。识别依赖于条件独立性假设\(R_i \perp Y_i \mid X_i, Z_i, \bar{H}_{i-1}\)（即采样决策不依赖于Y）。

第二步：最小内核

最简特例：假设\(\beta > (1+\sqrt{3})/2 \approx 1.37\)（例如\(\beta=2\)，即密度一次可微且导数Lipschitz），且\(K=2\)（两步算法）。此时，论文的核心思路可以简化为：

  1. 第一步（均匀采样）：从\(\mathcal{D}\)中均匀随机采样\(N_1 = N/2\)个样本，标记其Y，求解正则化光滑M估计得到初始估计\(\hat{\theta}_1\)。由Feng et al. (2022)知，\(\|\hat{\theta}_1 - \theta^*\|_2 = O_p((s\log d / N)^{\beta/(2\beta+1)}) = O_p((s\log d / N)^{2/5})\)（当\(\beta=2\)时）。

  2. 构造活动集：基于\(\hat{\theta}_1\)，定义活动集

    \[S_2 = \left\{ (X,Z) : -b_1 \leq \frac{X - \hat{\theta}_1^T Z}{\sqrt{1+\|\hat{\theta}_1\|_2^2}} \leq b_1 \right\},\]
    其中\(b_1\)取为\(c (s\log d / N)^{1/(2\beta)} = c (s\log d / N)^{1/4}\)。该活动集大致对应于真实阈值\(\theta^{*T}Z\)附近宽度为\(O(b_1)\)的窄带。

  3. 第二步（主动采样）：仅在活动集\(S_2\)内采样\(N_2 = N/2\)个样本（即只选那些X接近当前估计阈值的点），标记其Y，求解新的正则化光滑M估计得到\(\hat{\theta}_2\)。

为什么这能加速？ 关键观察：梯度\(\nabla R_{D_2}^{\delta_2}(\theta^*)\)中，每个样本的贡献正比于核函数\(K((X - \theta^{*T}Z)/\delta_2)\)，该核函数在\(X \approx \theta^{*T}Z\)时取大值。因此，靠近阈值的样本对估计最“信息”。通过主动采样集中在这些点，相当于有效样本量增大（因为每个样本的方差贡献被压缩）。数学上，定理1表明第二步的收敛率为

\[\|\hat{\theta}_2 - \theta^*\|_2 = O_p\left( \left( \frac{P((X,Z)\in S_2) s\log d}{N_2} \right)^{\beta/(2\beta+1)} \right).\]
由于\(P((X,Z)\in S_2) \asymp b_1 \asymp (s\log d / N)^{1/(2\beta)}\)，代入得
\[\|\hat{\theta}_2 - \theta^*\|_2 = O_p\left( \left( \frac{(s\log d / N)^{1/(2\beta)} s\log d}{N} \right)^{\beta/(2\beta+1)} \right) = O_p\left( \left( \frac{s\log d}{N} \right)^{1/2} \right),\]
即参数速率。这里的关键是：活动集宽度\(b_1\)与第一步的估计误差\(\|\hat{\theta}_1 - \theta^*\|_2\)匹配（条件(3.11)），使得活动集足够窄以压缩概率质量，但又足够宽以保证包含真实阈值附近的点。

核心数学困难：当\(\beta\)较小时（如\(\beta=1\)），第一步估计误差太大，导致必须选择更大的\(b_1\)才能满足稳定性条件，从而活动集不够窄，无法一步达到参数速率，需要更多迭代（K随N缓慢增长）。这就是相变的来源。

三、这篇论文做了什么

三句话

  1. 研究问题：在测量约束（只能标记少量样本）下，估计高维稀疏个性化阈值\(\theta^*\)，设计主动子采样算法以加速收敛。
  2. 核心方法：提出K步主动子采样算法，迭代地根据当前估计缩小采样区域（活动集），并在每个阶段求解正则化光滑M估计。
  3. 主要结论：算法在条件密度光滑度\(\beta\)上呈现相变：当\(\beta > (1+\sqrt{3})/2\)时，两步算法（K=2）达到参数速率\(O_p((s\log d/N)^{1/2})\)，快于i.i.d.下的minimax最优率；当\(1<\beta\leq (1+\sqrt{3})/2\)时，需要更多固定步数；当\(\beta\leq 1\)时，步数需随N缓慢增长，速率降为\(O_p((s\log d/N)^{1/(2\beta)})\)。此外，建立了N-预算minimax下界，证明算法率最优（至多对数因子），并发展了Lepski自适应方法。

关键设定与假设

  • 设定：未标记数据集\(\mathcal{D}=\{(X_i,Z_i)\}_{i=1}^n\)，标签预算N，目标估计\(\theta^*\)。算法将\(\mathcal{D}\)随机分为K批，每批大小n/K。第1批均匀采样；第k批（k≥2）仅在活动集\(S_k\)内采样，活动集由上一轮估计\(\hat{\theta}_{k-1}\)定义。
  • 假设：
  • Assumption 3.1：\(\theta^*\) s-稀疏，\(\|\theta^*\|_2 \leq C\)。
  • Assumption 3.2：Y的类概率有界；协变量Z的分量有界（允许随n增长），且满足稀疏特征值条件；Z|Y是次高斯向量。
  • Assumption 3.3：条件密度\(f(x|y,z)\)在\(x=\theta^{*T}z\)附近属于Hölder类\(\mathcal{P}(\beta, L)\)，且密度有上下界。
  • Assumption 3.4：核函数\(K(t)\)为l=⌊β⌋阶核，有界支撑。
  • Assumption 3.5：光滑经验风险\(R_{D_k}^{\delta_k}(\theta)\)在稀疏向量上满足限制强凸性（RSC）和限制光滑性（RSM），曲率参数依赖于\(\beta\)和采样概率\(c_{n,k}\)。
  • 相比已有文献：Feng et al. (2022) 假设i.i.d.数据，本文放宽到测量约束；主动学习文献假设Tsybakov噪声条件，本文假设密度光滑性。

主要结果

  • Theorem 1（Master定理）：给出每步估计的收敛率。第一步：\(\|\hat{\theta}_1 - \theta^*\|_2 = O_p((s\log d / N_1)^{(\beta \vee 1)/(2\beta+1)})\)。第k步（k≥2）：\(\|\hat{\theta}_k - \theta^*\|_2 = O_p((P((X,Z)\in S_k) s\log d / N_k)^{(\beta \vee 1)/(2\beta+1)})\)，其中\(P((X,Z)\in S_k) \asymp b_{k-1}\)。
  • Theorem 2（β > (1+√3)/2）：取K=2，适当选择参数，得\(\|\hat{\theta}_2 - \theta^*\|_2 = O_p((s\log d/N)^{1/2})\)。条件：\(N \lesssim (s\log d)^{1/(2\beta+1)} n^{2\beta/(2\beta+1)}\)。
  • Theorem 3（1<β≤(1+√3)/2）：需要K = ⌈log_{β/(2β+1)}(1 - (β+1)/(2β^2))⌉ + 1步，最终达到参数速率。中间步的率如(3.17)所示。
  • Theorem 4（0<β≤1）：K = ⌈log_{2β+1}(\log N)⌉步，最终率\(O_p((\log(N/(Ks\log d)))^{1/(4\beta)} (Ks\log d/N)^{1/(2\beta)})\)。
  • Theorem 5（Minimax下界）：N-预算minimax风险下界为\(s^{1/q - 1/2} (s\log(d/s)/N)^{1/(2(\beta \wedge 1))}\)，匹配上界（至多对数因子）。

证明路线与技术技巧

整体路线（以Theorem 2为例）： 1. 第一步：应用Theorem 1，得\(\|\hat{\theta}_1 - \theta^*\|_2 = O_p((s\log d/N)^{\beta/(2\beta+1)})\)。 2. 活动集概率质量：证明\(P((X,Z)\in S_2) \asymp b_1\)。利用次高斯性控制\(\hat{\theta}_1\)的估计误差，以及密度下界保证活动集有足够质量。 3. 验证条件(3.11)：选择\(b_1 = c (s\log d/N)^{1/(2\beta)}\)，验证\(b_1 \geq C\delta_2\)和\(b_1 \geq C\|\hat{\theta}_1 - \theta^*\|_2 \sqrt{\log(N/(s\log d))}\)。当\(\beta > (1+\sqrt{3})/2\)时，\(\beta/(2\beta+1) > 1/(2\beta)\)，故第二步成立。 4. 第二步：再次应用Theorem 1，代入\(P((X,Z)\in S_2) \asymp b_1\)，得\(\|\hat{\theta}_2 - \theta^*\|_2 = O_p((b_1 s\log d/N)^{\beta/(2\beta+1)}) = O_p((s\log d/N)^{1/2})\)。

关键跳跃点： - Proposition A.1：控制随机梯度误差\(\|\nabla R_{D_k}^{\delta_k}(\theta^*) - \mathbb{E}[\nabla R_{D_k}^{\delta_k}(\theta^*)|\hat{\theta}_{k-1}]\|_\infty\)，用Bernstein不等式，得到\(O_p(\sqrt{c_{n,k}K\log d/(n\delta_k)})\)。 - Proposition A.2：控制偏差\(\mathbb{E}[\nabla R_{D_k}^{\delta_k}(\theta^*)|\hat{\theta}_{k-1}] - \nabla R(\theta^*)\)，利用核的阶和Hölder光滑性，得到\(O(c_{n,k}\delta_k^\beta)\)。这里需要条件(3.11)保证积分截断误差可忽略。 - 活动集概率质量估计：Lemma A.1和后续推导，证明\(P((X,Z)\in S_k) \asymp b_{k-1}\)，依赖于密度上下界和\(\hat{\theta}_{k-1}\)的收敛率。

技术技巧点名： - 核平滑：用光滑替代损失\(L_\delta\)逼近0-1损失，使风险函数可微，便于梯度分析和优化。 - 经验过程/Bernstein不等式：用于控制梯度随机误差（Proposition A.1）。 - 泰勒展开与核的阶：用于控制偏差（Proposition A.2），利用核的矩条件消除低阶项。 - 次高斯尾界：用于控制\(\hat{\theta}_{k-1}\)的估计误差对活动集的影响（Lemma A.1及后续）。 - 限制强凸性（RSC）：用于建立估计误差与梯度范数之间的关系（Lemma A.7）。 - 路径跟踪算法：用于求解非凸优化问题（Algorithm 4），保证稀疏性和收敛性。 - Lepski方法：用于自适应未知光滑度β和稀疏度s（Section A.8）。 - Fano不等式/构造假设检验：用于minimax下界（Theorem 5），构造两类分布使得参数分离但似然不可区分。

真实例子与应用

  • 糖尿病数据集（UCI）：101,766条住院记录，预处理后n=12,586，d=60。目标：估计个性化HbA1c阈值，预测30天内再入院。方法：数据驱动两步主动子采样（Algorithm 3），与被动路径跟随比较。结果：在N=3000,4000,5000下，主动方法在ℓ1, ℓ2, ℓ∞误差上均优于被动（Table 2）。例如N=5000时，主动ℓ2误差0.269 vs 被动0.543。识别的重要协变量（住院时间、药物变化）与先前研究一致。
  • MNIST手写数字（附录A.12）：二分类（3 vs 5），引入类不平衡。主动方法在F1分数和测试误差上一致优于被动，尤其在更困难的10%采样率下提升更显著（Table 3-4）。

🔎 结论是否比证明窄

  • 论文在Theorem 2-4中给出了精确的收敛率，但实际算法推荐K=2（Section 4），理由是即使β较小，两步的改进已很显著，且更易实现。这暗示了理论上的最优K可能在实际中并非必要，但论文未严格证明K=2在β≤1.37时是否仍能获得某种次优但可接受的率。作者在Remark 2中提到了Mallik et al. (2020)的两阶段结果，但未将其纳入主要理论。
  • 自适应部分（Section A.8）的定理12需要额外条件如信号强度条件(A.124)和\(\|\nabla_S \bar{R}_\delta(\theta^*)\|_2 \geq C\delta^\beta\)，这些条件在正文中未充分讨论其合理性，仅在附录A.8.3中举例说明。因此，自适应方法的实际适用性可能比理论声称的窄。
  • 论文假设核函数有界支撑（Assumption 3.4），但附录A.6.1讨论了无界核（如高斯核）的扩展，需要额外尾条件(A.60)。这暗示主要结果对常用高斯核也成立，但证明更复杂。

四、开放问题

  1. 非线性阈值：论文假设线性阈值\(\theta^T Z\)。扩展到非线性（如加性模型、神经网络）是否仍能设计主动采样策略？理论上的相变现象是否保留？扎根于论文的线性假设和“线性结构因其透明性和可解释性而被青睐”的陈述（Introduction第2段）。

  2. 更一般的损失函数：本文针对0-1损失。对于其他非光滑损失（如hinge loss、check loss），主动采样能否获得类似加速？扎根于论文的M估计框架（1.2）和光滑替代损失技巧。

  3. K=2的实际最优性：论文推荐K=2，但理论表明当β≤1.37时，两步算法是次优的。是否存在一个实际可行的准则（如基于交叉验证）来自动选择K，而不需要知道β？扎根于Section 4的讨论和Theorem 3-4的理论结果。

  4. 自适应方法的常数选择：Lepski自适应方法（Section A.8）中的常数\(\bar{c}\)如何选择？理论要求足够大，但实际中可能影响有限样本表现。扎根于定理12的证明和附录A.8.1中常数\(\bar{c}\)的引入。

  5. 与主动学习文献的更深层联系：本文的相变现象是否对应于Tsybakov噪声条件下的某种“有效噪声”参数？能否建立两者之间的精确对应？扎根于Introduction中作者对主动学习文献的区分（“our analysis relies on the smoothness of the conditional density... rather than such noise conditions”）。这是一个值得研究者去查的张力点：是否存在统一框架？

Maintained by 陈星宇 · Homepage · Source on GitHub

评论