Here we study the comparative power of classical and quantum learners for
generative modelling within the Probably Approximately Correct (PAC) framework.
More specifically we consider the following task: Given samples from some
unknown discrete probability distribution, output with high probability an
efficient algorithm for generating new samples from a good approximation of the
original distribution. Our primary result is the explicit construction of a
class of discrete probability distributions which, under the decisional
Diffie-Hellman assumption, is provably not efficiently PAC learnable by a
classical generative modelling algorithm, but for which we construct an
efficient quantum learner. This class of distributions therefore provides a
concrete example of a generative modelling problem for which quantum learners
exhibit a provable advantage over classical learning algorithms. In addition,
we discuss techniques for proving classical generative modelling hardness
results, as well as the relationship between the PAC learnability of Boolean
functions and the PAC learnability of discrete probability distributions.

本文比较了传统和量子学习者在 Probably Approximately Correct (PAC) 框架下的生成模型能力，并构造了一类离散概率分布，通过决策 Diffie-Hellman 假设证明传统生成模型算法无法高效 PAC 学习，但我们构建了一个高效的量子学习器。同时，本文还讨论了证明经典生成建模难度结果的技术，以及布尔函数和离散概率分布的 PAC 学习性之间的关系。

关于离散分布的量子与经典可学习性

On the Quantum versus Classical Learnability of Discrete Distributions

It is becoming increasingly important to understand the vulnerability of
machine learning models to adversarial attacks. In this paper we study the
feasibility of robust learning from the perspective of computational learning
theory, considering both sample and computational complexity. In particular,
our definition of robust learnability requires polynomial sample complexity. We
start with two negative results. We show that no non-trivial concept class can
be robustly learned in the distribution-free setting against an adversary who
can perturb just a single input bit. We show moreover that the class of
monotone conjunctions cannot be robustly learned under the uniform distribution
against an adversary who can perturb $\omega(\log n)$ input bits. However if
the adversary is restricted to perturbing $O(\log n)$ bits, then the class of
monotone conjunctions can be robustly learned with respect to a general class
of distributions (that includes the uniform distribution). Finally, we provide
a simple proof of the computational hardness of robust learning on the boolean
hypercube. Unlike previous results of this nature, our result does not rely on
another computational model (e.g. the statistical query model) nor on any
hardness assumption other than the existence of a hard learning problem in the
PAC framework.

本文研究了机器学习模型对抗攻击的容易受攻击性问题，并从计算学习理论的角度探究了鲁棒学习的可行性和计算复杂度，并给出了相应的计算困难性证明。

关于强鲁棒分类的困难程度

On the Hardness of Robust Classification

We consider two multi-armed bandit problems with $n$ arms: (i) given an
$\epsilon > 0$, identify an arm with mean that is within $\epsilon$ of the
largest mean and (ii) given a threshold $\mu_0$ and integer $k$, identify $k$
arms with means larger than $\mu_0$. Existing lower bounds and algorithms for
the PAC framework suggest that both of these problems require $\Omega(n)$
samples. However, we argue that these definitions not only conflict with how
these algorithms are used in practice, but also that these results disagree
with intuition that says (i) requires only $\Theta(\frac{n}{m})$ samples where
$m = |\{ i : \mu_i > \max_{i \in [n]} \mu_i - \epsilon\}|$ and (ii) requires
$\Theta(\frac{n}{m}k)$ samples where $m = |\{ i : \mu_i > \mu_0 \}|$. We
provide definitions that formalize these intuitions, obtain lower bounds that
match the above sample complexities, and develop explicit, practical algorithms
that achieve nearly matching upper bounds.

提出多臂老虎机算法中两个问题：如何识别平均值与最大平均值相差小于给定阈值的武器和如何识别平均值大于给定阈值的 k 支武器。在此基础上，给出了形式化的定义，匹配了样本复杂度的下界，并提供了几乎匹配上界的具体实用算法。

鉴别好臂之真实样本复杂性

The True Sample Complexity of Identifying Good Arms

This paper establishes problem-specific sample complexity lower bounds for
linear system identification problems. The sample complexity is defined in the
PAC framework: it corresponds to the time it takes to identify the system
parameters with prescribed accuracy and confidence levels. By problem-specific,
we mean that the lower bound explicitly depends on the system to be identified
(which contrasts with minimax lower bounds), and hence really captures the
identification hardness specific to the system. We consider both uncontrolled
and controlled systems. For uncontrolled systems, the lower bounds are valid
for any linear system, stable or not, and only depend of the system finite-time
controllability gramian. A simplified lower bound depending on the spectrum of
the system only is also derived. In view of recent finitetime analysis of
classical estimation methods (e.g. ordinary least squares), our sample
complexity lower bounds are tight for many systems. For controlled systems, our
lower bounds are not as explicit as in the case of uncontrolled systems, but
could well provide interesting insights into the design of control policy with
minimal sample complexity.

该论文针对线性系统识别问题建立了特定于问题的样本复杂性下限，其能够精确地表示系统的主要特征，并考虑了受控系统和不受控制的系统的情况。