论文标题
私人分类和在线预测的关闭属性
Closure Properties for Private Classification and Online Prediction
论文作者
论文摘要
让〜$ \ ch $是一类布尔函数，并考虑使用某些任意聚合规则从〜$ \ ch $派生的{\ IT组成的class} $ \ ch' $（例如，$ \ ch' $可能是$ \ ch $中的所有3-Wise多数函数函数的类别）。我们在〜$ \ ch $方面绑定了〜$ \ ch' $的littlestone尺寸。作为推论，我们得出了在线学习和私人PAC学习的关闭属性。 小点上的衍生边界表现出不良指数依赖性。对于私人学习，我们证明了几乎可以避开这种次优依赖性的最佳界限。私人学习样本复杂性的改进界限是通过将原始类$ \ ch $的私人学习者转换为私人学习者的私人学习者的算法。使用相同的想法，我们表明的是，任何（{\ em正确或不当}）私人算法在可实现的情况下学习一类函数$ \ ch $（即，当示例在课堂中被某些函数标记时）可以将其转换为私人算法，以了解private算法，以了解类$ \ ch $ chnostic nes agnostic nes f. chnostic nes cannostic案例。
Let~$\cH$ be a class of boolean functions and consider a {\it composed class} $\cH'$ that is derived from~$\cH$ using some arbitrary aggregation rule (for example, $\cH'$ may be the class of all 3-wise majority-votes of functions in $\cH$). We upper bound the Littlestone dimension of~$\cH'$ in terms of that of~$\cH$. As a corollary, we derive closure properties for online learning and private PAC learning. The derived bounds on the Littlestone dimension exhibit an undesirable exponential dependence. For private learning, we prove close to optimal bounds that circumvents this suboptimal dependency. The improved bounds on the sample complexity of private learning are derived algorithmically via transforming a private learner for the original class $\cH$ to a private learner for the composed class~$\cH'$. Using the same ideas we show that any ({\em proper or improper}) private algorithm that learns a class of functions $\cH$ in the realizable case (i.e., when the examples are labeled by some function in the class) can be transformed to a private algorithm that learns the class $\cH$ in the agnostic case.
