We study adversarial perturbations when the instances are uniformly
distributed over $\{0,1\}^n$. We study both "inherent" bounds that apply to any
problem and any classifier for such a problem as well as bounds that apply to
specific problems and specific hypothesis classes.
As the current literature contains multiple definitions of adversarial risk
and robustness, we start by giving a taxonomy for these definitions based on
their goals, we identify one of them as the one guaranteeing misclassification
by pushing the instances to the error region. We then study some classic
algorithms for learning monotone conjunctions and compare their adversarial
risk and robustness under different definitions by attacking the hypotheses
using instances drawn from the uniform distribution. We observe that sometimes
these definitions lead to significantly different bounds. Thus, this study
advocates for the use of the error-region definition, even though other
definitions, in other contexts, may coincide with the error-region definition.
Using the error-region definition of adversarial perturbations, we then study
inherent bounds on risk and robustness of any classifier for any classification
problem whose instances are uniformly distributed over $\{0,1\}^n$. Using the
isoperimetric inequality for the Boolean hypercube, we show that for initial
error $0.01$, there always exists an adversarial perturbation that changes
$O(\sqrt{n})$ bits of the instances to increase the risk to $0.5$, making
classifier's decisions meaningless. Furthermore, by also using the central
limit theorem we show that when $n\to \infty$, at most $c \cdot \sqrt{n}$ bits
of perturbations, for a universal constant $c< 1.17$, suffice for increasing
the risk to $0.5$, and the same $c \cdot \sqrt{n} $ bits of perturbations on
average suffice to increase the risk to $1$, hence bounding the robustness by
$c \cdot \sqrt{n}$.

研究了均匀分布在 {0,1}^n 上的实例中的敌对扰动，提出了不同于通常定义的错误区域的保真度定义，并根据该定义研究了任何分类问题的任何分类器的风险和稳健性的内在限制。使用布尔超立方体的等周不等式和中心极限定理，对单个和大规模的问题提出了与数学相关的结果。