跳转至

Generalized Tensor Completion with Non-Random Missingness

讲者: Biao Cai
会场: Statistics for Business
报告题目: Generalized Tensor Completion with Non-Random Missingness
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向是张量补全（Tensor Completion），其根本的统计问题是：如何从一个仅有部分条目被观测到的、带有噪声的高维张量中，恢复出完整的底层张量。该问题通常假设底层张量具有低秩结构（如CP分解或Tucker分解）。当前，该领域正从“完全随机缺失（MCAR）”的主流设定，向更现实的“非随机缺失（MNAR）”设定演进，即缺失概率依赖于张量条目本身的值。本文正是这一演进中的关键一步。

发展脉络（history）

  1. 奠基工作与均匀缺失设定：早期工作奠定了张量分解与补全的基础。Kolda and Bader (2009) 系统性地介绍了张量分解（CP、Tucker）及其应用。Yuan and Zhang (2016) 提出了基于核范数最小化的凸优化方法，并证明了其样本复杂度优于矩阵化方法。这些工作均假设条目以等概率独立缺失（MCAR）。
  2. 非均匀缺失（MAR）的探索：研究者开始放松均匀缺失假设，但仍假设缺失概率与底层值无关（即随机缺失，MAR）。Mao et al. (2019, 2021, 2024) 发展了一系列协变量辅助和逆倾向得分（IPS）框架，假设数据MAR。Lee and Wang (2020) 研究了在非均匀采样下的序数张量补全。这些工作允许缺失概率不同，但核心假设是缺失机制不依赖于未观测到的张量值。
  3. 非随机缺失（MNAR）的挑战：这是当前的前沿，也是本文的定位。Ma and Chen (2019) 和 Bhattacharya and Chatterjee (2022) 提出了矩阵补全下的两步法：先估计缺失概率（假设其具有低秩结构），再进行IPS加权补全。Yang et al. (2021) 将两步法推广到张量（TenIPS）。这些工作有一个共同的关键假设：缺失概率必须被一个常数均匀地远离0和1。Agarwal et al. (2023) 提出了一个因果矩阵补全框架，允许缺失依赖于底层值和其他缺失条目，但对观测条目的数量和位置有强假设。Choi and Yuan (2024) 则利用“缺失条目数量相对较少”这一事实进行推断。
  4. 本文的位置：本文直接挑战了上述两步法对缺失概率的均匀有界假设。它提出一个联合建模框架，同时估计底层张量和缺失机制参数，从而允许缺失概率可以任意接近0或1，只要其切片平均不极端。这显著放宽了现有MNAR张量补全工作的理论条件。

子线索聚类

  • 线索一：低秩张量分解与均匀缺失补全。核心是假设数据MCAR，利用CP或Tucker低秩结构进行恢复。代表工作：Kolda and Bader (2009), Yuan and Zhang (2016), Cai et al. (2022), Xia et al. (2021)。这些工作提供了最优的统计率和计算效率，但无法处理MNAR偏差。
  • 线索二：非均匀缺失（MAR）下的矩阵/张量补全。核心是允许缺失概率不同，但假设其与底层值无关。代表工作：Mao et al. (2019, 2021, 2024), Lee and Wang (2020)。这些工作通常使用协变量或加权策略，但无法纠正由MNAR引起的偏差。
  • 线索三：非随机缺失（MNAR）下的矩阵/张量补全。核心是建模缺失概率与底层值之间的依赖关系。代表工作：Ma and Chen (2019), Yang et al. (2021), Bhattacharya and Chatterjee (2022), Agarwal et al. (2023), Choi and Yuan (2024)。本文属于此线索，其独特贡献在于：1）采用联合估计而非两步法；2）理论条件大幅放宽，允许缺失概率极端；3）提供了检验MCAR vs MNAR的推断程序。

这个方向在追问的核心问题

  1. 识别性：在MNAR下，如何从观测数据中唯一地识别出底层张量和缺失机制？需要什么样的假设（如参数形式、低秩结构）？
  2. 估计的鲁棒性：当缺失概率非常小或非常大时（即倾向得分极端），如何避免IPS加权带来的巨大方差或偏差？联合建模是否比两步法更鲁棒？
  3. 推断：在非凸优化和MNAR的复杂设定下，如何对缺失机制参数（如b1）或张量条目本身进行有效的统计推断（如假设检验、置信区间）？
  4. 计算与统计的权衡：在MNAR设定下，是否存在类似均匀缺失下的统计-计算权衡？本文的交替最大化算法是否达到了某种最优性？

⚠️ 作者的 framing

  • 作者的缺口描述：作者将缺口frame为“现有MNAR方法（如Ma and Chen, 2019; Yang et al., 2021）要求缺失概率均匀有界，这在现实中不成立”。他们将自己的工作定位为“放宽这一条件，允许概率任意接近0或1，只需切片平均有界”。
  • 被淡化/回避的竞争路线：
    • 两步法（IPS）：作者明确指出了两步法的弱点：当倾向得分接近0时，IPS估计误差大。他们通过联合建模来回避这个问题。但联合建模引入了更复杂的非凸优化问题，其计算代价和收敛性保证是否优于两步法，作者没有直接比较。
    • 因果框架：Agarwal et al. (2023) 的因果矩阵补全框架被提及，但作者仅指出其“对观测条目的数量和位置有强假设”，并未深入讨论其与本文参数化建模在假设强度上的优劣。
  • 什么明显该被引/该存在、却没出现在intro里？
    • 统计-计算权衡文献：本文的交替最大化算法是一个非凸优化方法，其理论分析（几何收敛到统计误差邻域）与Cai et al. (2022) 等均匀缺失下的非凸张量补全工作一脉相承。但本文没有讨论是否存在更难的统计-计算权衡问题。例如，是否存在一个信号强度阈值，低于该阈值时，即使统计上可识别，也没有多项式时间算法能一致估计？这与研究者（陈星宇）感兴趣的“统计-计算权衡”高度相关。本文的设定（MNAR + 广义线性模型）可能为探索此类权衡提供了一个新平台。
    • 半参数效率理论：本文的推断部分（Theorem 3）是基于一个样本分割后的逻辑回归。这是否是半参数有效的？是否存在一个更高效的、基于整个样本的推断方法（如去偏机器学习）？作者没有讨论其推断的效率。

张力

未见明显对立引用。所有被引工作都在逐步放松缺失机制假设，本文是这一趋势下的一个自然进展。

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

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

  • 符号：

    • X ∈ R^{d1×d2×d3}: 我们感兴趣的未知底层张量。这是我们要估计的目标。
    • Y ∈ R^{d1×d2×d3}: 数据张量。其条目 Y_ijk 是在给定 X_ijk 下，从指数族分布中生成的观测值。
    • D ∈ {0,1}^{d1×d2×d3}: 缺失掩码张量。D_ijk = 1 表示 Y_ijk 被观测到，否则为0。
    • P_ijk = P(D_ijk = 1 | X_ijk): 观测概率。它是 X_ijk 的一个函数，由参数 θ 控制。
    • Θ: 所有未知参数的集合，包括CP分解的因子和缺失模型的参数。
    • R: CP分解的秩。
    • u_r ∈ R^{d1}, v_r ∈ R^{d2}, w_r ∈ R^{d3}: CP分解的因子向量，具有单位范数。
    • λ_r ∈ R^+: CP分解的权重。
    • θ = (b_0, b_1): 缺失模型的参数，例如 logit(P_ijk) = b_0 + b_1 * X_ijk。
    • Ω = {(i,j,k): D_ijk = 1}: 观测到的条目索引集合。
    • Y_obs = {Y_ijk: (i,j,k) ∈ Ω}: 观测到的数据。

  • 模型：

    1. 数据生成模型：给定 X_ijk，Y_ijk 独立地服从指数族分布，其密度为 f(Y_ijk | X_ijk) = c(Y_ijk) exp( (Y_ijk X_ijk - ψ(X_ijk)) / φ_0 )。这意味着 E[Y_ijk | X_ijk] = ψ'(X_ijk) = h^{-1}(X_ijk)，其中 h 是链接函数。
    2. 缺失机制模型：给定 X_ijk，D_ijk 独立地服从伯努利分布，其成功概率为 P_ijk = g_θ(X_ijk)。本文主要考虑 g_θ(x) = logit^{-1}(b_0 + b_1 x)。
    3. 低秩结构模型：底层张量 X 具有秩为 R 的CP分解：X = Σ_{r=1}^R λ_r u_r ◦ v_r ◦ w_r。

  • 可观测数据：

    • 研究者能观测到的是数据张量的部分条目 Y_obs 和完整的缺失掩码张量 D。
    • 想要但观测不到的量是：1）完整的底层张量 X；2）缺失机制参数 θ；3）未观测到的数据 {Y_ijk: (i,j,k) ∉ Ω}。识别 X 和 θ 依赖于上述模型假设。

第二步：讲最小内核

本文的核心数学困难在于：在缺失概率 P_ijk 可以任意接近0或1（即高度异质）的情况下，如何从联合似然中一致地估计出低秩张量 X 和缺失参数 θ？

最简特例：秩1 (R=1)，且张量维度相等 (d1=d2=d3=d)。

在这个特例下，模型简化为： - X_ijk = λ * u_i * v_j * w_k，其中 ||u||_2 = ||v||_2 = ||w||_2 = 1。 - 观测概率 P_ijk = logit^{-1}(b_0 + b_1 * X_ijk)。 - 数据 Y_ijk 服从一个简单的指数族分布，例如高斯分布 N(X_ijk, 1)。

核心思路：算法1通过交替最大化联合对数似然 ℓ_d(Θ) 来估计 Θ = {u, v, w, λ, b_0, b_1}。在每一步，它固定其他参数，只优化一个分量（如 u_i 的第 i 个坐标）。

在这个特例下，要证的命题（Theorem 1的核心）退化成什么？ Theorem 1声称，经过 t 次迭代后，估计误差 D(Θ^{(t)}, Θ^*) 可以被一个几何衰减的计算误差项和一个统计误差项之和所控制。统计误差项的形式为 O( (ψ'_max + 1) √(log(d)d) / ( (ψ''_min √p̄ + √q̄) λ^* ) )。

证明怎么走（核心跳跃点）？ 证明的关键在于分析单个坐标 u_i 的更新。对于固定的 u_i，其目标函数是 ℓ_d(u_i, 其他参数)。证明需要： 1. 建立强凹性（Strong Concavity）：证明 -∇²_{u_i} ℓ_d(u_i, ...) 有一个正的下界。这个下界依赖于 λ² * Σ_{j,k} v_j² w_k² * [D_ijk ψ''(X_ijk) + b_1² * P_ijk(1-P_ijk)]。难点：当 P_ijk 可以接近0或1时，P_ijk(1-P_ijk) 可能非常小，导致下界很弱。作者通过分析切片平均 p̄ 和 q̄ 而非单个 P_ijk 来绕过这个困难。他们证明，只要切片平均 p̄ 和 q̄ 满足条件，整个求和项的下界仍然足够大。 2. 控制梯度：证明 |∇_{u_i} ℓ_d(u_i^*, ...)| 有一个小的上界。这个梯度包含随机噪声项。难点：当 P_ijk 极端时，D_ijk 的方差很大，导致梯度波动大。作者通过坐标级分析，利用 u_i^* 的稀疏性（µ-mass 假设）和精细的浓度不等式，将梯度的上界控制为 O( √(log(d)d) )。 3. 迭代收缩：结合强凹性和梯度界，可以证明每次更新后，|u_i^{(t+1)} - u_i^*| 都会收缩，直到达到由梯度界决定的统计误差邻域。

为什么成立？ 这个特例成立的核心原因是：联合似然函数在单个坐标上具有足够的曲率（由切片平均保证），而噪声的波动可以通过坐标级的浓度不等式被有效控制。这使得即使缺失概率极端，算法仍然能收敛到真实值附近。

三、这篇论文做了什么

  • 三句话：

    1. 研究了在数据非随机缺失（MNAR）下，从噪声观测中恢复低秩张量的问题。
    2. 提出了一个联合建模框架，同时估计底层张量（通过CP分解）和缺失机制参数（通过一个参数化函数，如logistic回归），并开发了一个交替最大化算法进行求解。
    3. 主要结论包括：1）为算法每一步的估计量建立了非渐近误差界，该误差界在缺失概率可以任意接近0或1的条件下成立；2）提出了一个基于样本分割的假设检验程序，用于检验缺失机制是否为MCAR。

  • 关键设定与假设：

    • 设定：Y_ijk 服从指数族分布，D_ijk 服从伯努利分布，P(D_ijk=1) = logit^{-1}(b_0 + b_1 X_ijk)。底层张量 X 具有秩为 R 的CP分解。
    • 假设：
      • Condition 1 (数据与模型)：Y_ijk 是次高斯的；CP分解唯一；因子向量是 µ-mass的（即不集中）。
      • Condition 2 (缺失概率)：这是本文最关键的放松。它不要求所有 P_ijk 被常数均匀有界，而是要求切片平均 p̄ 和 q̄ 满足条件。p̄ 是每个切片上 P_ijk 的最小平均值，q̄ 是每个切片上 P_ijk(1-P_ijk) 的最小平均值。这允许单个 P_ijk 接近0或1，只要整体平均不极端。
      • Condition 3 (信噪比)：要求 λ_min √p̄ 足够大，这类似于均匀缺失下的条件，但用平均概率 p̄ 替代了均匀概率 p。
      • Condition 4 (非相干性，用于R>1)：要求不同秩的因子向量之间的内积足够小，以确保它们可以被区分。

  • 主要结果：

    • Theorem 1 (秩1情况)：给出了算法第 t 步估计误差 D(Θ^{(t)}, Θ^*) 的上界。该上界由两部分组成：一个以速率 ρ^t 几何衰减的计算误差，和一个与 t 无关的统计误差。统计误差的量级为 O( (ψ'_max + 1) √(log(d)d) / ( (ψ''_min √p̄ + √q̄) λ^*) )。当 t 足够大时，计算误差被统计误差主导。
    • Theorem 2 (一般秩R情况)：将Theorem 1推广到一般秩。误差上界形式类似，但统计误差项中出现了 λ_max / λ²_min 因子，反映了多秩估计的额外难度。
    • Theorem 3 (假设检验)：建立了在样本分割后，从测试集 A_2 上拟合的逻辑回归得到的参数 b̂θ_{A_2} 的渐近正态性。这为检验 H_0: b_1^* = 0 提供了理论基础。该定理成立需要一个更强的条件，即张量估计误差必须足够小。

  • 证明路线与技术技巧（理论型）：

    • 整体路线：
      1. 初始化：假设初始点在真实值的一个小邻域内（B_{1/2}(Θ^*)）。
      2. 单步收缩：证明算法中的每一步更新（如更新 u_r）都会使该分量的估计误差以某个因子 ρ < 1 收缩，直到达到一个由统计误差决定的“停滞”区域。
      3. 迭代归纳：通过归纳，证明所有分量的误差在每一步都收缩，最终达到Theorem 1和2中的误差界。
    • 关键跳跃点：
      • 从向量级到坐标级的强凹性分析：这是本文最核心的技术创新。标准方法是对整个向量 u 建立强凹性，但这需要 P_ijk 的均匀下界。作者转而分析单个坐标 u_i 的强凹性，利用切片平均 p̄ 和 q̄ 来保证 -∇²_{u_i} ℓ_d 的下界。这需要证明 Σ_{j,k} v_j² w_k² D_ijk ψ''(X_ijk) 等项的下界可以用 p̄ 和 q̄ 来控制，而不是单个 P_ijk。
      • 处理非线性缺失模型的梯度：由于缺失模型是logistic回归，其梯度项 ∇_{u_i} ℓ_d 包含 D_ijk 和 P_ijk 的复杂组合。当 P_ijk 极端时，D_ijk 的方差很大。作者通过将梯度分解为“期望项”和“波动项”，并利用覆盖数（covering number）论证和浓度不等式来统一控制波动项，从而得到梯度的上界。
    • 技术技巧点名：
      • 坐标级分析（Coordinate-wise analysis）：用于建立强凹性，避免了对单个 P_ijk 的均匀有界假设。
      • 切片平均（Slice-wise average）：用 p̄ 和 q̄ 替代 P_ijk 的逐点界，是放宽条件的关键。
      • 覆盖数论证（Covering number argument）：用于在参数空间的一个邻域内，对梯度差 ∇ℓ_d(u_i^*, Θ̄_{-u_i}) - ∇ℓ_d(u_i^*, Θ^*_{-u_i}) 建立一致的上界。
      • 样本分割（Sample splitting）：用于推断，确保估计张量 X̂ 与测试集上的 D 独立，从而将问题简化为标准逻辑回归推断。

  • 真实例子与应用：

    • InCarMusic数据：一个42用户×139歌曲×26上下文的音乐推荐张量，观测率仅2%。作者将评分二值化（≥4为1）。应用：1）用本文的检验程序，以p-value ≈ 10^{-43} 拒绝了 H_0: b_1=0，表明存在MNAR机制，且 b̂_1 为负，说明高评分更可能缺失。2）进行边预测（80%训练，20%测试），本文方法（GTC-MNAR）的AUC ROC（0.702）优于GCP、Ordinal、NonparaT、ENTED等方法。这个例子想说明：本文方法在真实的高稀疏、MNAR数据上，不仅能有效检测到MNAR，还能在预测任务中取得更好性能。
    • ADS数据：一个120参与者×20产品类别×3广告格式的完全观测张量。作者人为引入三种缺失机制（无依赖、正依赖、负依赖），然后随机掩码20%作为测试集。应用：在三种机制下，本文方法的AUC ROC均优于其他方法。这个例子想说明：在可控的模拟环境下，本文方法对各种MNAR模式都具有鲁棒性。

  • 🔎 结论是否比证明窄：

    • 检验部分的条件更强：Theorem 3的成立条件 (ψ'_max+1)λ²_max √(|A_2|log(d)) / ((ψ''_min √p̄ + √q̄)d λ²_min) = o(1) 比Theorem 1和2的估计一致性条件更强。这意味着，虽然估计可以在更宽松的条件下成立，但为了进行有效的推断，需要更强的信号或更大的样本量。作者在文中明确指出了这一点。
    • 参数化缺失模型：全文的证明和推断都依赖于 g_θ 是参数化函数（如logistic）这一假设。作者在讨论部分提到可以扩展到非参数模型，但这只是一个conjecture，没有理论证明。
    • CP分解的唯一性：证明依赖于CP分解的唯一性（Condition 1(b)）。这是一个很强的假设，在实际中可能不成立（如存在置换和缩放模糊性）。作者没有讨论当唯一性不严格成立时，误差界会如何变化。

四、开放问题

  1. 扩展到协变量：作者在讨论中提到可以将用户/物品属性等协变量纳入模型。一个具体的问题是：如何将协变量同时整合到张量分解模型（如 X = Xβ + low-rank）和缺失机制模型（如 logit(P) = b_0 + b_1 X + b_2^T covariates）中，并给出相应的理论保证？这扎根于论文Section 6的第一点。
  2. 非参数缺失模型：将 g_θ 从参数化的logistic函数推广到非参数形式（如核平滑、样条）。这需要发展新的识别条件和估计方法，并可能面临维度灾难。这扎根于论文Section 6的第二点。
  3. 张量条目的推断：本文只对缺失参数 θ 做了推断。一个更直接的应用是推断张量条目本身（如 X_ijk 的置信区间）。作者提到可以使用Xia et al. (2022) 和 Ma and Xia (2024) 的技术。一个具体的问题是：在MNAR设定下，如何为张量条目构建有效的置信区间？是否需要去偏？这扎根于论文Section 6的第三点。
  4. 计算效率与统计最优性：本文的交替最大化算法是计算高效的，但其统计误差是否达到了某种最优（如minimax最优）？在MNAR设定下，是否存在一个统计-计算权衡？例如，是否存在一个信号强度阈值，低于该阈值时，任何多项式时间算法都无法达到最优统计率？这个问题与研究者（陈星宇）的兴趣高度相关，但本文完全没有涉及。这扎根于论文没有讨论的领域，但可以从Cai et al. (2022) 和 Xia et al. (2021) 在均匀缺失下的最优性结果自然延伸出来。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论