内存与N无关！DeepMVSA搞定1亿点单纯形估计，精度不输多项式基准
Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis
📖 AI 总结
本文研究从单纯形内部均匀采样的独立同分布数据点中估计K维单纯形的问题，观测值为K+1个未知原型的凸组合。现有多项式时间估计方法每样本计算量达三次方级别，或需O(NK)存储，在N达百万至亿级时难以实用。作者提出DeepMVSA方法，将最小体积原则改写为神经隐式形式：由轻量坐标网络生成混合权重，并用三角LU型参数化对偶单纯形矩阵，使可训练状态内存降至O(K²)、与N无关，每次数据遍历代价为O(NK²)。理论方面，作者证明了局部化代理估计量的非渐近样本复杂度界达到多项式时间基准阶，给出了神经目标任意全局极小值的oracle不等式（含体积膨胀控制与显式收缩偏差），并在显式包络事件上建立了分离统计、逼近、优化与包围残差项的端到端误差预算，同时给出两点下界：在任意与N无关的固定噪声水平下，N的负二分之一幂次标度不可改进。实验在高达一亿个合成观测上验证了预测精度与标度规律，并在约千万像素的真实场景中展示了可行性。
🔑 关键词速览
| 最小体积单纯形估计 | 从凸组合数据中恢复未知单纯形顶点的方法，通过最小化单纯形体积来求解。 |
| DeepMVSA | 本文提出的神经隐式方法，用轻量网络参数化混合权重和对偶单纯形矩阵，实现可扩展估计。 |
| 非渐近分析 | 在有限样本下给出误差界和收敛速率，不依赖于样本量趋于无穷的假设。 |
| 样本复杂度 | 达到给定精度所需的最少样本数量，衡量估计器的数据效率。 |
| oracle 不等式 | 一种理论工具，将估计误差与最优可能误差（oracle）进行比较，用于分析全局极小值的性能。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅