The Sample Complexity of Learning Lipschitz Operators with respect to Gaussian Measures
本文研究了针对高斯测度的利普希茨算子近似问题，证明了其具有更高的高斯索伯列夫正则性，并建立了赫米特多项式近似误差的下界与上界。研究进一步分析了从 $m$ 个任意（可能自适应）线性样本重构利普希茨算子的通用策略，核心发现是严格刻画了相应的样本复杂度，即所有采样与重构策略中可实现的极小最坏情况误差。该结果揭示了样本复杂度的固有灾难：基于 $m$ 个线性样本的利普希茨算子近似方法无法实现关于 $m$ 的代数收敛速率；但若能证明底层高斯测度协方差算子具有足够快的谱衰减，则可保证收敛速率任意接近任何代数速率。总体而言，该工作通过严格界定样本复杂度，证实了学习利普希茨算子的内在困难性，无论数据或学习技术如何变化。