Optimal Statistical Guarantees for
Adversarially Robust Gaussian Classification

Chen Dan, Yuting Wei, Pradeep Ravikumar
ICML 2020
Computer Science Department, Statistics Department, Machine Learning Department
Carnegie Mellon University

Adversarial Example

Deep Neural Networks are vulnerable to adversarial attacks.

1

Statistical Challenges(Schmidt et al. NeurIPS’18) The generalization gap in Adv-RobustClassification is significantly larger than Standard Classification.
2

Conditional Gaussian Model(Mixture of two gaussians picture here)
Binary Classification with Conditional Gaussian Model Pµ,Σ :1p(y = 1) = p(y = −1) = ,2x|y = +1 ∼ N(+µ, Σ),x|y = −1 ∼ N(−µ, Σ).
Minimize Robust Classification Error:
Rrobust (f ) = Pr[∃kx 0 − xkB ≤ ε, f (x 0 ) 6= y ]where k · kB is a norm, e.g. `p norm.
3Sample Complexity”Adversarially Robust Generalization Requires More Data”:
Theorem ((Schmidt et al. NeurIPS’18))√1 1/4
When Σ = σ 2 I , kµk2 = d, σ ≤ 32
d ,adversarial perturbation kx 0 − xk∞ ≤ 14 .
• O(1) samples sufficient for 99% standard accuracy.
√• Ω̃( d) samples necessary for 51% robust accuracy.
• Why do we need more data?
• What happens in other regimes?

4

Contributions• Understanding the sample complexity through the lens ofStatistical Minimax Theory.
• Introducing ”Adversarial Signal-to-Noise Ratio”, which explains
why robust classification requires more data.
• Near-optimal upper and lower bounds on minimax risk.
• ** Computationally efficient minimax-optimal estimator.
• ** Minimal assumptions.

5Minimax Theory

Our goal is to characterize the Statistical Minimax Error of robust
Gaussian classification:∗min max [Rrobust (fb) − Rrobust]
fb Pµ,Σ ∈D

where:• D is a class of distributions.
• fˆ is any estimator based on n i.i.d samples {xi , yi }ni=1 ∼ Pµ,Σ .

∗• Rrobust
is the smallest classification error of any classifier.

6

Fisher’s LDA: Bayes Risk

When ε = 0, the problem reduces to Fisher’s LDA.
The smallest possible classification error R ∗ is Φ̄( 12 SNR), where:• SNR is the Signal-to-Noise Ratio of the model:pSNR(Pµ,Σ ) = 2 µT Σ−1 µ.
• Φ̄ : Gaussian tail probability Φ̄(c) = PrX ∼N(0,1) [X > c].
SNR characterizes the hardness of classification problem.

7

Minimax Rate of Fisher LDA

Consider the family of distributions with a fixed SNR:
Dstd (r ) := {Pµ,Σ |SNR(Pµ,Σ ) = r }.
The following minimax rate is proved by prior works:
Theorem (Li et al. AISTATS’17)
∗−( 18 +o(1))r 2 dbmin max [R(f ) − R ] ≥ Ω e·.
nfb P∈Dstd (r )with a nearly-matching upper bound.

8Signal-to-Noise Ratio

Signal-to-Noise Ratio exactly characterizes the hardness of standard
Gaussian classification problem.
Can we find a similar quantity for the robust setting?
• SNR is not the correct answer!
• Two distributions with same SNR can have very different
optimal robust classification error (e.g. 0.1% vs 50%)!

9Adversarial Signal-to-Noise Ratio

We define Adversarial Signal-to-Noise Ratio(AdvSNR) as:
AdvSNR(Pµ,Σ ) = min SNR(Pµ−z,Σ ).
kzkB ≤εUsing AdvSNR, we can re-formulate one of the main theorems in(Bhagoji et al. ,NeurIPS 2019) as:1
∗Rrobust= Φ̄( AdvSNR).
2
which recovers the results in Fisher LDA when ε = 0!

10

Main ResultConsider the family of distributions with a fixed AdvSNR:
Drobust (r ) := {Pµ,Σ |AdvSNR(Pµ,Σ ) = r }.
Our Main Theorem:
Theorem (Dan, Wei, Ravikumar, ICML’20)
∗−( 18 +o(1))r 2 dbmin max [Rrobust (f ) − Rrobust ] ≥ Ω e·.
nfb P∈Drobust (r )and there is a computationally efficient estimator which achieves
this minimax rate!
Generalization of (Li et al. 2017) in adversarially robust setting!
11

Why does Adv-Robust Classification Require More Data?

The minimax rates for Standard vs. Adv-Robust classification:
1dexp{− SNR 2 }8nvs.

1dexp{− AdvSNR 2 }8n• AdvSNR ≤ SNR, so Adv-Robust Risk always converges slower.
• Sometimes AdvSNR = Θ(1) and SNR = Θ(1), theconvergence is only a constant factor slower.
• Sometimes AdvSNR = Θ(1) and SNR = Θ(d), theconvergence is exp(Ω(d)) times slower!

12Upper Bound & Algorithm• (Bhagoji et al. ,NeurIPS 2019) showed that a linear classifierf (x) = sign(w0T x) has the minimal robust classification error,
wherew0 = Σ−1 (µ − z0 ),z0 = argmin(µ − z)T Σ−1 (µ − z).
kzkB ≤εb• Replace (µ, Σ) by their empirical counterpart (bµ, Σ).
• Now you have an efficient algorithm that achieves the minimax
rate!

13

Lower Bound• Main idea: Black-Box Reduction• Robust Classification is ”harder” than Standard Classification.
• For any distribution P with Signal-to-Noise Ratio r ,• We can find a P 0 with AdvSNR r , such that for any classifier f ,RobustExcessRiskP 0 (f ) ≥ StdExcessRiskP (f )• Take minf maxP∈Dstd (r ) ,MinimaxRobustExcessRisk(Drobust (r ))≥MinimaxStdExcessRisk(Dstd (r )).
• Apply (Li et al. 2017) and we get the minimax lower bound.

14

Summary• In this paper, we provide the first statistical minimax optimality
result for Adversarially Robust Classification.
• We introduced AdvSNR, which characterizes the hardness ofAdv-Robust Gaussian Classification.
• We proved matching upper and lower bounds for minimax
excess risk, and an efficient, minimax-optimal algorithm.
• Adversarially Robust Classification requires More Data, because
adversarial perturbation decreases the Signal-to-Noise Ratio!

15