対敵ロバスト性は単純さと相反する可能性がある

現在の機械学習の手法は、対敵の摂動に対してロバストな分類器を学習することができません。しかし、ランダムな摂動があっても非常に高い精度の非ロバストな分類器を学習することができます。このギャップを説明するために、ロバストな分類には標準的な分類よりもより複雑な分類器（すなわち、より多くの能力）が必要であるという仮説を強調します。このメモでは、以下のような「単純な」分類器の分類タスクとセットのいくつかの理論的な例を挙げることで、この仮説が実際に可能であることを示します。(1) 高い標準の精度を持ち、ランダムなノイズ下でも高い精度を持つ単純な分類器が存在します。(2) どんな単純な分類器もロバストではありません：それは摂動に対して高い対敵損失を持たなければなりません。(3) ロバストな分類は可能ですが、より複雑な分類器が必要です（いくつかの例では指数関数的に複雑です）。さらに、単純な分類器の間にはロバスト性と標準精度の間に定量的なトレードオフがあります。これは、現在の分類器の構造がそのようなトレードオフを課しているため、この現象の別の説明を示唆しています。