10:37arXiv cs.LG@Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel WiedmerLee、Mehrotra和Zampetakis(FOCS'24)首次提出多项式时间算法学习高维截断高斯,但样本与时间非最优。本研究针对非平凡截断,给出高效算法,使用n = Õ(d²/ε²)个样本在总变差距离上达到ε误差。算法时间复杂度主要由计算经验协方差矩阵主导。该样本与时间复杂度在d和ε上均为最优,即使无截断时亦如此。关键创新在于用相对截断参数重新解释截断高斯低阶矩,从而直接恢复参数,避开耗时投影随机梯度下降。论文Gaussianhalfspace truncation样本复杂度学习理论算法推荐理由:这篇论文给出了学习半空间截断高斯分布的最优算法,样本和时间复杂度都达到理论下界,而且避开了繁琐的随机梯度下降,值得了解。原文