通用特征的通信复杂度研究

研究人员探讨了面向函数族评估的数据表示复杂度，构建出仅需 $O(d^{*}\log(1/\varepsilon))$ 比特编码长度的确定性编码器，其中 $d^*$ 为函数族的对偶 VC 维，误差至多为 $\varepsilon$。该编码长度在最坏情况下达到最优，且研究给出了两种基于无标签样本学习该表示的方法。实验验证了贪心构建方法的精度与大小权衡，并探索了其与神经稀疏自编码器的联系。