Summary
This paper provides an in-depth analysis of adversarial training with linear models and its relationship to regularized regression methods under the overparametrized regime.
Depending on the value of the perturbation radius, it is revealed that there exist three modes.
When the radius is small, solutions to adversarial training behave as minimum-norm interpolators (Theorem 1).
When the radius is medium, the solutions behave as solutions to the parameter shrinkage regression (Proposition 4).
When the radius is large, the zero solution is necessary and sufficient (Proposition 3).
In addition to these theoretical results, the authors observe the mode change experimentally and discuss how adversarial training is advantageous over parameter shrinkage regression.
Strengths
- A modern extension of theory on robust optimization and regularization: The relationship between robust optimization (somewhat encompassing adversarial training in this work) and regularization has been known in the literature, including Xu et al. (2009). This work contributes to studying what happens when it comes to overparametrization and nicely characterizes the relationship between the perturbation radius and the corresponding modes (as I summarized above).
- Demonstration of the benefit of overparametrization: In the numerical simulation of Figure 2, the authors demonstrate that the robustness radius increases as the model becomes more overparametrized, namely, $p/n$ increases. This clearly indicates the benefits of overparametrization (though the analysis hinges on norm matching, as mentioned in Remark 2).
- Clarity: Despite the thorough theory, the paper is written clearly and easy to follow.
Xu et al. (2009). "Robustness and Regularization of Support Vector Machines." (JMLR)
Weaknesses
One of the main weaknesses would be the restriction to linear models, which is crucial for the current analysis yet needed for further understanding adversarial training.
You may refer to Xu et al. (2009) when you show Theorem 4. Indeed, the equation right after l.322 can be regarded as a generalization of Theorem 3 in Xu et al. (2009) because $\\ell(y(\\boldsymbol{x}^\\top\\boldsymbol{\\beta}) - \\delta\\|\\beta\_\*\\|) \\le \\ell(y(\\boldsymbol{x}^\\top\\boldsymbol{\\beta})) + \\delta\\|\\boldsymbol{\\beta}\\|\_\*$ when $\\ell$ is the hinge loss.
Below, I have other minor comments.
- In Figure 1, can you specify what $\\lambda$ and $\\delta$ are used for each line?
- In the proof of Theorem 1, you may need $-$ (negative) sign in front of either $\\epsilon\_i\boldsymbol{x}\_i$ in Eq. (6) or $n\\delta\boldsymbol{\\alpha}$ in l.132. Otherwise, "the subderivative contains zero" (l.132) does not seem to be correct.
- In l.150, the reason of $\\delta\_{\\text{test}} \\propto \mathbb{E}[\\|\\boldsymbol{x}\\|]$ is unclear to me. Can you elaborate on it?
- In Figure 4, can you specify what $n$ and $p$ are used?
- In Eq. (8), do you miss the exponent $2$ for the norm?
- In Eq. (9), it might be better to change the notation $\\epsilon$ for the noise because $\\epsilon$ has already been used in the proof of Theorem 1.
- In the equations after l.319 and l.322, should we need $+ \\Delta x$ on the left-hand sides?
- In the appendix, what is referred to as Theorem 3 seems to be Proposition 3.
Questions
See the weaknesses.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
Obviously, the analysis is entirely limited to the linear model case. Nonetheless, the analysis provides a fair amount of insights to readers, so I don't think this is a big limitation.