Class 7: Intrinsic Limits on Adversarial Robustness

Here are the PPT slides for the presentation. The slides were also made by Somrita.

We discussed the following two papers that demonstrates the limits to attaining adversarial robustness namely:

1. Theoretically Principled Trade-off between Robustness and Accuracy - Zhang et al.[ Links]
2. Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness - Mahloujifar et al, Zhang et al.[ Links]

Theoretically Principled Trade-off between Robustness and Accuracy #

- Main contributions of this paper: #

1. There exists an intrinsic tradeoff between robustness and accuracy.
2. It is possible to upper-bound both terms using a technique called classification-calibrated loss.
3. Development of a heuristic algorithm to minimise the empirical risk

The paper upperbounds the term \( R_{rob}(f) - R_{nat}^* \), so that we know \( R_{rob}(f) \) is more than \( R_{nat}^* \) by some maximum amount.

- Optimization #

The first term encourages the natural error to be optimized by minimizing the “difference” between \( f(X) \) and \( Y \). The second regularization term encourages the output to be smooth, that is, it pushes the decision boundary of classifier away from the sample instances via minimizing the “difference” between the prediction of natural example \( f(X) \) and that of adversarial example \( f(X’) \). The tuning parameter \( \lambda \) plays a critical role on balancing the importance of natural and robust errors.

Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness #

- Main Contributions: #

1. Bridging the gap: The research aims to narrow the gap between theoretical analyses of classification robustness for idealized data distributions and the intrinsic robustness of real-world datasets.

2. Method for evaluating concentration: The paper presents a general method to evaluate the concentration of a given input distribution \( \mu \) using a set of data samples. It demonstrates that by increasing both the sample size \( m \) and a complexity parameter \( T \), the concentration of the empirical measure converges to the actual concentration of \( \lambda \).

In the paper they work with the following definitions of adversarial risk:

The main aim is to estimate the minimum possible adversarial risk, which captures the intrinsic robustness for classification in terms of the underlying distribution \( \mu \), conditioned on the fact that the original risk is at least \( \alpha \).

- Few other definitions: #

The above theorem states that if the underlying collection of subsets \( \mathcal{G} \) is not too complex, then the empirical concentration, represented by \( \hat\mu_S \), is close to the true concentration, represented by \( \mu \), with high probability.

The above theorem implies that as the sample size m increases and the complexity penalties \( \phi \) and \( \phi_\epsilon \) decrease, the empirical concentration function becomes a reliable estimate of the true concentration function. In other words, the concentration behaviour observed in the empirical distribution based on a finite sample is likely to be close to the concentration behaviour of the true underlying distribution.

Finally, the following theorem states that the empirical concentration function will converge to the actual concentration function as the sample size increases.

The paper also provides heuristic methods to find the best possible error region, which covers atleast \( \alpha \) fraction of the samples and its expansion covers the least number of points, for both \( \ell_\infty \) and \( \ell_2 \) settings.

- Main Takeaways: #

1. We see an upper bound on the gap between robust error and optimal natural error from the first paper.
2. We see the development of a general framework to measure the concentration of an unknown distribution through samples from the distribution in the second paper.