论文标题
度量熵二元性和结果不可区分的样本复杂性
Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability
论文作者
论文摘要
我们为结果提供了第一个样本复杂性特征，这是DWORK，KIM，REINGOLD，ROTHBLUM和YONA最近引入的机器学习的理论框架（Stoc 2021）。在结果的不可区分性中，学习者的目标是输出一个无法通过$ d $的差异级别的预测变量来分开的预测因子，这些差异级别的划分器检查了根据预测指标的预测来检查产生的结果。 在特定于分布特定且可实现的设置中，将学习者与包含目标预测变量的预测变量类别$ p $一起，我们显示结果不可区分的样本复杂性的特征是$ p $ w.r.t.的度量熵的特征。双$ D $定义的双Minkowski规范，并由$ d $ W.R.T.的度量熵等同于$ P $定义的双Minkowski规范。这种等效性使得与凸几何形状中长期的度量熵二元性双重性构想有着有趣的联系。我们的样本复杂性表征意味着公制熵二元性的变体，我们显示的几乎很紧。在无分配环境中，我们关注Dwork等人考虑的案例。 $ p $包含所有可能的预测指标，因此样本复杂性仅取决于$ d $。在这种情况下，我们表明结果不可区分的样本复杂性的特征是$ d $的脂肪震惊。 我们还显示了在无分布和特定于分布的特定设置中可实现的和不可分性结果之间不可区分的样本复杂性分离。这与无分布（分布特定分布）PAC学习相反，在这种学习中，可实现和不可知设置的样品复杂性都可以通过VC维度（分别度量熵）来表征。
We give the first sample complexity characterizations for outcome indistinguishability, a theoretical framework of machine learning recently introduced by Dwork, Kim, Reingold, Rothblum, and Yona (STOC 2021). In outcome indistinguishability, the goal of the learner is to output a predictor that cannot be distinguished from the target predictor by a class $D$ of distinguishers examining the outcomes generated according to the predictors' predictions. In the distribution-specific and realizable setting where the learner is given the data distribution together with a predictor class $P$ containing the target predictor, we show that the sample complexity of outcome indistinguishability is characterized by the metric entropy of $P$ w.r.t. the dual Minkowski norm defined by $D$, and equivalently by the metric entropy of $D$ w.r.t. the dual Minkowski norm defined by $P$. This equivalence makes an intriguing connection to the long-standing metric entropy duality conjecture in convex geometry. Our sample complexity characterization implies a variant of metric entropy duality, which we show is nearly tight. In the distribution-free setting, we focus on the case considered by Dwork et al. where $P$ contains all possible predictors, hence the sample complexity only depends on $D$. In this setting, we show that the sample complexity of outcome indistinguishability is characterized by the fat-shattering dimension of $D$. We also show a strong sample complexity separation between realizable and agnostic outcome indistinguishability in both the distribution-free and the distribution-specific settings. This is in contrast to distribution-free (resp. distribution-specific) PAC learning where the sample complexity in both the realizable and the agnostic settings can be characterized by the VC dimension (resp. metric entropy).
