Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Metric Entropy Duality and the Sample Complexity of Outcome
  Indistinguishability   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).

13
The categories of this paper are: quant-ph
0
The categories of this paper are: hep-ph
3
The categories of this paper are: physics
31
The categories of this paper are: ao-sci
11
The categories of this paper are: hep-lat
20
The categories of this paper are: acc-phys
9
The categories of this paper are: nlin
33
The categories of this paper are: plasm-ph
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex
7
The categories of this paper are: hep-th
36
The categories of this paper are: cmp-lg
14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th