Manurangsi

新理论收紧了PAC学习中列表可复现性的界限

研究人员在PAC学习框架中为列表可复现性建立了一个新的上限，显著改进了先前的结果。研究表明，对于具有Littlestone维度为'd'和对偶VC维度为'v*'的概念类，列表可复现性由$2^{O(d \min\{\log d, v^*\})}$界定。这个新界限接近最优，紧密匹配已知的下界$2^{\Omega(d)}$，并将先前最佳上限$2^{2^{O(d)}}$指数级地改进。这些发现源于一种新颖的归纳框架，并利用了差分隐私学习和稳定正则化的工具。