Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution

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