The Price of Implicit Bias in Adversarially Robust Generalization

Summary

This paper studies the generalization gap of robust empirical risk minimization for linear regression. The paper shows that the choice optimization algorithm or architecture affects the generalization gap of the trained linear model. In particular, a steepest descent algorithm w.r.t. $l_p$ norm finds the minimum $l_p$ norm interpolating solution on linearly separable data; a reparametrization of the linear model into a two-layer diagonal linear network has a bias toward minimum $l_1$ norm solution.

Strengths

1. Connections between implicit bias (of optimization algorithm and of architecture) and adversarial robustness. 2. Interesting discussion on the optimal regularization for robust ERM w.r.t. $l_\infty$. 3. Experiments are through and well presented.

Weaknesses

1. The message in this paper is delivered but the supporting argument is rather incomplete: * Section 2.1 highlights the need for an optimal regularization given specific data assumption and threat model, but the discussion is primarily for $l_\infty$ threat model. * Section 3.2 discusses how a diagonal linear network has a bias toward minimum $l_1$ solution, but the connection is not formal (the author acknowledges it in Remark 3.9). 2. The technical contribution is minor in my opinion. The ERM counterparts of the results in Section 3 are well-known and extensively studied, and extending them to robust ERM is more or less straightforward. Minor comments: 1. Corollary 3.5 refers to equation (8), which has $p^*$ as the conjugate of $p$, yet the corollary itself contains another $p^*$, it is confusing whether they are the same $p^*$. 2. Referring steepest descent w.r.t. $l_1$ as "coordinate descent" is confusing. Generally, coordinate descent chooses the coordinate to be updated in a cyclic or random order. I understand there is a variation of CD that picks the coordinate with the largest gradient component, but plainly using CD may let the reader think of the more standard CD algorithm.

Questions

See Weakness

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

See Weakness

Summary

The paper studies the implicit bias of robust Empirical Risk Minimization (ERM) and its connection with robust generalization. In regularized classification, the authors discuss the choice of regularization for a given perturbation set to improve robust generalization. In the unregularized setting, they study the implicit bias of steepest descent when applying it to the worst-case exponential loss in scenarios where the data is separable. They investigate two architectures: linear models and diagonal neural networks.

Strengths

1. The paper is well-written, and its contributions are well-explained. 2. The difference between the convergence of Gradient Descent in linear models and diagonal neural networks with $\ell_{\infty}$ perturbations is a very interesting result.

Weaknesses

In my opinion, a weakness of the paper is that while the authors engage in an interesting discussion in the technical sections, the results presented in the paper are not very insightful on their own: 1. The result presented in Section 2 is directly derived from Theorem 2.1, which is borrowed from prior works, and Rademacher Complexity. 2. As the authors mention, the result of implicit bias in linear models is not surprising, and its proof is based on techniques from prior works. 3. The result of implicit bias in diagonal neural networks can be seen as a paraphrased theorem from prior work.

Questions

Could the authors elaborate on the technical challenges they faced in proving their results, especially the result of implicit bias in linear models?

Rating

5

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

Yes

Summary

In this paper, the authors study the issue of large generalization gap with Robust ERM objective, they connect this with the implicit bias of optimization (including architecture and the optimization algorithm). The findings suggest that optimizing models for robust generalization is challenging since it is hard to do the right capacity control for robust machine learning.

Strengths

- The paper has in-depth investigations into how does the choice of regularization norm affect the generalization ability of the model w.r.t. sparsity of data, optimization algorithm and choice of architecture - The authors validate their findings in both linear models and NN

Weaknesses

- The theory studies might be still too limited

Questions

See weakness

Rating

7

Confidence

2

Soundness

4

Presentation

3

Contribution

3

Limitations

See weakness

Summary

This paper explores a linear classification scenario, investigating the factors that contribute to the gap between empirical adversarial risk and expected adversarial risk. Furthermore, they discuss which type of regularization should be applied in different cases. There are also simulations results to support their points.

Strengths

1.The paper is well-written with a clear structure. Motivations are well-explained on why the authors study the problem and the contributions of this study are well discussed. The analysis for the theoretical results are helpful in understanding. Overall, it is easy to follow the logic and flow of the paper. 2.Theoretical results are solid and well-organized. The authors made the theoretical settings clear. 3.Empirical results support the theoretical findings.

Weaknesses

1.In Theorem 2.1, it is not clear whether the constant $\rho$ has influences on other constants shown in the theorem. 2.While these results mainly focus on the gap between empirical adversarial risk and expected adversarial risk, maybe the discussions about their influences on expected risk and empirical adversarial risk are lacked. 3.As Theorem 3.3 focuses on steepest gradient dynamics on linear model, and Theorem 3.6 is about gradient flow on diagonal model, from my side, it is better to add a result about steepest gradient dynamics on diagonal model to make the analysis more sufficient.

Questions

See weakness.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No negative social impact.