High-dimensional estimation with missing data: Statistical and computational limits
高维缺失数据估计：统计与计算极限AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
本页为预印本版本；arXiv 收录、作者填写的期刊信息以及作者既有发表经历，都不单独证明本篇已接收。作者发表记录按 OpenAlex 身份与完整姓名、本站覆盖期刊 ISSN 及正式卷期核对，只展示已核实例，档案仍可能误合并。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要讨论高维缺失数据下的估计极限与算法，属于统计与计算理论方向，未涉及所给微观、宏观或金融计量细分领域的主题。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
高维缺失数据估计：统计与计算极限
- 研究问题
- 研究在观测存在缺失、且缺失机制为可实现污染模型（任意未知的 MNAR）时，如何对总体参数进行计算可行估计，并刻画统计极限与计算极限之间的差距。
- 方法与思路
- 摘要称在真实数据为高斯、ε 比例观测受任意未知 MNAR 机制影响的设定下，分别考察均值估计（ℓ2 范数）、协方差估计（相对算子范数）与线性回归，比较信息论下界与多项式时间算法的样本复杂度。
- 材料陈述的贡献
- 作者提出均值与协方差估计中存在统计—计算差距：信息论最优需约 n≳de^{1/ρ²} 样本但算法计算不可行，而高效算法需约 n≳d^{1/ρ²}，并给出基于平方和的多项式时间算法近乎达到该下界；线性回归中该差距不持续，最小化简单强凸经验风险即可多项式时间近乎达到信息论下界。
- 阅读关注点
- 应核对缺失污染模型与 MNAR 的具体假设、下界所针对的算法族范围、平方和算法的阶数与运行时间、以及线性回归结论成立的条件与常数依赖。
- 阅读边界
- 摘要未说明具体定理形式、证明技术细节与数值实验；且本文为 arXiv 预印本，未经同行评审，不能据此声称已被期刊接收或结论已被验证。
原文摘要
We consider computationally-efficient estimation of population parameters when observations are subject to missing data. In particular, we consider estimation under the realizable contamination model of missing data in which an $ε$ fraction of the observations are subject to an arbitrary (and unknown) missing not at random (MNAR) mechanism. When the true data is Gaussian, we provide evidence towards statistical-computational gaps in several problems. For mean estimation in $\ell_2$ norm, we show that in order to obtain error at most $ρ$, for any constant contamination $ε\in (0, 1)$, (roughly) $n \gtrsim d e^{1/ρ^2}$ samples are necessary and that there is a computationally-inefficient algorithm which achieves this error. On the other hand, we show that any computationally-efficient method within certain popular families of algorithms requires a much larger sample complexity of (roughly) $n \gtrsim d^{1/ρ^2}$ and that there exists a polynomial time algorithm based on sum-of-squares which (nearly) achieves this lower bound. For covariance estimation in relative operator norm, we show that a parallel development holds. Finally, we turn to linear regression with missing observations and show that such a gap does not persist. Indeed, in this setting we show that minimizing a simple, strongly convex empirical risk nearly achieves the information-theoretic lower bound in polynomial time.