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