arXiv:2605.19625cs.LG2026-05中稿 · COLT 2026被引 1

在高维空间中用线性查询最优重构点,揭示了误差下限与查询次数的深层关系。

Optimal Reconstruction from Linear Queries

论文配图:Optimal Reconstruction from Linear Queries
图 1 · 摘自论文原文
  • 通过推广朱恩定理,建立近似极值体的几何分析框架。
  • 无限查询时误差收敛至√(2d/(d+1))δ,且超出部分呈双指数衰减。
  • 适用于信号恢复、隐私推理等需精确重构的高维场景。

我们研究从近似线性查询中重构ℝ^d中未知点的问题。该问题广泛存在于低维遥感、信号恢复、高维数据分析及隐私敏感推断等应用中。核心目标是刻画重构误差关于查询次数T、环境维度d和噪声参数δ的最优关系。首先分析T→∞极限,证明最优误差收敛至显式值√(2d/(d+1))δ,其作用类比监督学习中的贝叶斯最优误差。当维度固定时,超过此极限的多余误差随T→∞以双指数速度衰减,远快于典型学习曲线。当维度增长时,实现可忽略多余误差所需的查询数约为exp(d),且此数量级为必要且充分。最后,引入并分析了重建问题的一种非正规变体。技术上,主要贡献是对朱恩定理(1901)的推广:经典定理界定直径为1的集合的最大可能半径并刻画极值体;新定理提供鲁棒版本,刻画近极值体,并通过利用对称性和李群作用的几何与动力学论证完成证明。

原文摘要 · Abstract (English)

We study the problem of reconstructing an unknown point in $\mathbb{R}^d$ from approximate linear queries. This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference. Our main goal is to characterize the optimal reconstruction error as a function of the number of queries $T$, the ambient dimension $d$, and the noise parameter $δ$. We first analyze the limit $T \to \infty$ and show that the optimal reconstruction error converges to the explicit value $\sqrt{2d/(d+1)} δ$, which plays a role analogous to the Bayes optimal error in supervised learning. When the dimension is fixed, we show that the excess error above this limit decays doubly exponentially fast as $T \to \infty$, a rate that is significantly faster than those typically encountered in learning curves. When the dimension grows, we show that a number of queries on the order of $\exp(d)$ is necessary and sufficient to achieve vanishing excess error. Finally, we introduce and analyze an improper variant of the reconstruction problem. From a technical perspective, our main contribution is a generalization of Jung's theorem (1901). The classical theorem bounds the maximum possible radius of a set of diameter 1 and characterizes extremal bodies. Our generalization provides a robust variant that characterizes near-extremal bodies and is proved via geometric and dynamical arguments exploiting symmetry and Lie group actions.

高维重构线性查询几何优化误差下界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。