目录

• 概
• 主要内容
  • 高斯模型
    • upper bound
  • lower bound
  • 伯努利模型
    • upper bound
    • lower bound

Schmidt L, Santurkar S, Tsipras D, et al. Adversarially Robust Generalization Requires More Data[C]. neural information processing systems, 2018: 5014-5026.

@article{schmidt2018adversarially,

title={Adversarially Robust Generalization Requires More Data},

author={Schmidt, Ludwig and Santurkar, Shibani and Tsipras, Dimitris and Talwar, Kunal and Madry, Aleksander},

pages={5014--5026},

year={2018}}

本文在二分类高斯模型和伯努利模型上分析adversarial, 指出对抗稳定的模型需要更多的数据支撑.

高斯模型定义: 令\(\theta^* \in \mathbb{R}^n\)为均值向量, \(\sigma >0\), 则\((\theta^*, \sigma)\)-高斯模型按照如下方式定义: 首先从等概率采样标签\(y \in \{\pm 1\}\), 再从\(\mathcal{N}(y \cdot \theta^*, \sigma^2I)\)中采样\(x \in \mathbb{R}^d\).

伯努利模型定义: 令\(\theta^* \in \{\pm1\}^d\)为均值向量, \(\tau >0\), 则\((\theta^*, \tau)\)-伯努利模型按照如下方式定义: 首先等概率采样标签\(y \in \{\pm 1\}\), 在从如下分布中采样\(x \in \{\pm 1\}^d\):

\[x_i =
\left \{
\begin{array}{rl}
y \cdot \theta_i^* & \mathrm{with} \: \mathrm{probability} \: 1/2+\tau \\
-y \cdot \theta_i^* & \mathrm{with} \: \mathrm{probability} \: 1/2-\tau
\end{array} \right.
\]

分类错误定义: 令\(\mathcal{P}: \mathbb{R}^d \times \{\pm 1\} \rightarrow \mathbb{R}\)为一分布, 则分类器\(f:\mathbb{R}^d \rightarrow \{\pm1\}\)的分类错误\(\beta\)定义为\(\beta=\mathbb{P}_{(x, y) \sim \mathcal{P}} [f(x) \not =y]\).

Robust分类错误定义: 令\(\mathcal{P}: \mathbb{R}^d \times \{\pm 1\} \rightarrow \mathbb{R}\)为一分布, \(\mathcal{B}: \mathbb{R}^d \rightarrow \mathscr{P}(\mathbb{R}^d)\)为一摄动集合. 则分类器\(f:\mathbb{R}^d \rightarrow \{\pm1\}\)的\(\mathcal{B}\)-robust 分类错误率\(\beta\)定义为\(\beta=\mathbb{P}_{(x, y) \sim \mathcal{P}} [\exist x' \in \mathcal{B}(x): f(x') \not = y]\).

注: 以\(\mathcal{B}_p^{\epsilon}(x)\)表示\(\{x' \in \mathbb{R}^d|\|x'-x\|_p \le \epsilon\}\).

高斯模型

upper bound

定理18: 令\((x_1,y_1),\ldots, (x_n,y_n) \in \mathbb{R}^d \times \{\pm 1\}\) 独立采样于同分布\((\theta^*, \sigma)\)-高斯模型, 且\(\|\theta^*\|_2=\sqrt{d}\). 令\(\hat{w}:=\bar{z}/\|\bar{z}\| \in \mathbb{R}^d\), 其中\(\bar{z}=\frac{1}{n} \sum_{i=1}^n y_ix_i\). 则至少有\(1-2\exp(-\frac{d}{8(\sigma^2+1)})\)的概率, 线性分类器\(f_{\hat{w}}\)的分类错误率至多为:

\[\exp (-\frac{(2\sqrt{n}-1)^2d}{2(2\sqrt{n}+4\sigma)^2\sigma^2}).
\]

定理21: 令\((x_1,y_1),\ldots, (x_n,y_n) \in \mathbb{R}^d \times \{\pm 1\}\) 独立采样于同分布\((\theta^*, \sigma)\)-高斯模型, 且\(\|\theta^*\|_2=\sqrt{d}\). 令\(\hat{w}:=\bar{z}/\|\bar{z}\| \in \mathbb{R}^d\), 其中\(\bar{z}=\frac{1}{n} \sum_{i=1}^n y_ix_i\). 如果

\[\epsilon \le \frac{2\sqrt{n}-1}{2\sqrt{n}+4\sigma} - \frac{\sigma\sqrt{2\log 1/\beta}}{\sqrt{d}},
\]

则至少有\(1-2\exp(-\frac{d}{8(\sigma^2+1)})\)的概率, 线性分类器\(f_{\hat{w}}\)的\(\ell_{\infty}^{\epsilon}\)-robust 分类错误率至多为\(\beta\).

lower bound

定理11: 令\(g_n\)为任意的学习算法, 并且, \(\sigma > 0, \epsilon \ge 0\), 设\(\theta \in \mathbb{R}^d\)从\(\mathcal{N}(0,I)\)中采样. 并从\((\theta,\sigma)\)-高斯模型中采样\(n\)个样本, 由此可得到分类器\(f_n: \mathbb{R}^d \rightarrow \{\pm 1\}\). 则分类器关于\(\theta, (y_1,\ldots, y_n), (x_1,\ldots, x_n)\)的\(\ell_{\infty}^{\epsilon}\)-robust 分类错误率至少为

\[\frac{1}{2} \mathbb{P}_{v\sim \mathcal{N}(0, I)} [\sqrt{\frac{n}{\sigma^2+n}} \|v\|_{\infty} \le \epsilon ].
\]

伯努利模型

upper bound

令\((x, y) \in \mathbb{R}^d \times \{\pm1\}\)从一\((\theta^*, \tau)\)-伯努利模型中采样得到. 令\(\hat{w}=z / \|z\|_2\), 其中\(z=yx\). 则至少有\(1- \exp (-\frac{\tau^2d}{2})\)的概率, 线性分类器\(f_{\hat{w}}\)的分类错误率至多为\(\exp (-2\tau^4d)\).

lower bound

引理30： 令\(\theta^* \in \{\pm1\}^d\) 并且关于\((\theta^*, \tau)-伯努利模型\)考虑线性分类器\(f_{\theta^*}\),

\(\ell_{\infty}^{\tau}\)-robustness: \(f_{\theta^*}\)的\(\ell_{\infty}^{\tau}\)-robust分类误差率至多为\(2\exp (-\tau^2d/2)\).

\(\ell_{\infty}^{3\tau}\)-nonrobustness: \(f_{\theta^*}\)的\(\ell_{\infty}^{3\tau}\)-robust分类误差率至少为\(1-2\exp (-\tau^2d/2)\).

Near-optimality of \(\theta^*\): 对于任意的线性分类器, \(\ell_{\infty}^{3\tau}\)-robust 分类误差率至少为\(\frac{1}{6}\).

定理31: 令\(g_n\)为任一线性分类器学习算法. 假设\(\theta^*\)均匀采样自\(\{\pm1\}^d\), 并从\((\theta^*, \tau)\)-伯努利分布(\(\tau \le 1/4\))中采样\(n\)个样本, 并借由\(g_n\)得到线性分类器\(f_{w}\).同时\(\epsilon < 3\tau\)且\(0 < \gamma < 1/2\), 则当

\[n \le \frac{\epsilon^2\gamma^2}{5000 \cdot \tau^4 \log (4d/\gamma)},
\]

\(f_w\)关于\(\theta^*, (y_1,\ldots, y_n), (x_1,\ldots, x_n)\)的期望\(\ell_{\infty}^{\epsilon}\)-robust 分类误差至少为\(\frac{1}{2}-\gamma\).