On the Geometry of Regularization in Adversarial Training: High-Dimensional Asymptotics and Generalization Bounds

Thank you for the thoughtful and insightful review. Regarding all the typos and clarity suggestions, we will fix them in the camera-ready version.

[...] I think an experiment showing that the main conceptual result (i.e., regularizing with the dual norm improves performance) transfers to a real dataset would enhance the paper. [...]

We refer to the answer given to Reviewer BhWC, where we explain how a similar behavior is observed for a classification task on 0 vs. 1 MNIST.

I wish the authors were able to extract more insight directly from Theorem 3.15. I fully appreciate that these self-consistent equations are not easily analyzable, but Remark 3.17 doesn't really say anything specific to this result. It merely restates the standard idea that the order parameters are sufficient statistics, and mentions the proof strategy (which is re-stated again in lines 297-301). Are there any special cases (beyond isotropic data) for which you could make something more of this result?

The system of equations in the theorem could provide insights for specific questions. For instance, studying them perturbatively might help reveal how generalization error scales with model parameters. As an example, [Vilucchio et al. 2024] derived such scalings for a robust regression setting.

However, the analytical progress in that paper relies critically on their choice of loss functions ($\ell_2$, $\ell_1$, and Huber loss) which have closed-form proximal operators, and on the regression setting they consider. In our binary classification context, the proximal operator lacks an analytical form for all the commonly used classification losses, making similar closed-form derivations significantly more challenging to obtain.

[...] I acknowledge that a complete analysis of the transition to optimality of the dual norm with increasing perturbation scale is out of reach, but (in the same vein as my previous comment) I wish the authors showed how more can be done with access to the sharp asymptotic. At the very least, the authors should show how loose the Rademacher complexity bounds are.

Thank you for the suggestion. Indeed, it would be useful to show that the Rademacher complexity bounds are numerically loose. We will add in Appendix B the high-dimensional version of the Rademacher complexity bounds. For instance, see the attached anonymized plot (bound_comparison.pdf) that shows that the $\ell_2$ bound $\left(\frac{ \mathcal{W}_2}{ \sqrt{\alpha}} \left(1 + \sqrt{\frac{1}{\lambda_1 (\Sigma) }} \right),\right)$ where $\lambda_1(\Sigma)$ is the smallest eigenvalue of the perturbation matrix $\Sigma$, is numerically loose (and even increases with $\alpha$). It corresponds to the blue lines shown in the Figure.

Given the smooth transition between $r^\star = 2$ and $r^\star = 1$ with increasing $\epsilon$ that you observe in Figure 4, can you gain any insight by expanding around $\epsilon = 0$ and $\epsilon \to \infty$?

The primary challenge with formal expansions in this binary classification context is that the system of equations remains unsolvable and depends on integrals at any order in the expansion. As a result, the expansion would depend on a specific scaling ansatz in $\varepsilon$, where the coefficients at each order of the expansion are solutions of a similar system of equations as the original one. Thus, it appears to be not possible to obtain such an expansion without resorting to numerical solutions.

Thank you very much for your critical and thorough review of our work.

The evaluation methods used are generally appropriate for assessing the proposed method. However, it would also be interesting to test the robustness of the results by examining scenarios where the linear classifier assumption is violated. This would provide valuable insights into how the method performs under model misspecification.

We agree that this is a nice addition for our paper and are adding such an experiment. We consider the case of 0 vs 1 MNIST classification. We take 0 and 1 MNIST images, normalize their pixel values in $[0,1]$ and flatten them to have a $d=784$ dimensional $\bf{x}_i$. The labels are converted to be $-1$ and $+1$. We then train as per eqs. (6,7) with this dataset, using subsets of a suitable size to fix various $\alpha = n / d$ and then test robust and clean error as per eqs. (3,4) with $1000$ new samples. We attach the results of two experiments with $\varepsilon = 1.0, 2.0$ in an anonymized folder. We see that by reducing the number of training samples (lowering $\alpha$) the robust error differs based on the choice of the regularization. The optimal choice of regularization is $r=1$, which is constistent with our idealized theoretical model. In the camera ready version, we will include a discussion of these results.

[...] the algorithm used to solve the minimization problem (7) on page 3 is not clearly explained. [...]

Thank you for pointing this out. Equation (7) corresponds to a convex problem as explained in Appendix A (see eq (37)). Thus, it can be solved using a general purpose convex solver. We used the L-BFGS-B algorithm with random normal initialization and a stopping tolerance of 1e-5 for the gradient. We will include these experimental details in the revised version.

This paper focuses on binary classification models. I wonder if the results can be extended to linear regression models and generalized linear models?

The key step that allows the analytical description of the problem is going from eq. (36) to eq. (37). This step relies on the fact that we consider binary classification, as explained in Appendix A, and cannot easily be generalized to more complicated classification tasks.

Thank you very much for your thorough review of our work.

Could the authors provide a comparison and contrast of their results with those of Tanner et al., 2024, particularly in terms of the technical settings and innovations in their technical analysis? Additionally, what were the key technical challenges in extending the work of Tanner et al., 2024 to the proposed setting?

In a nutshell, Tanner et al. 2024 study Mahalanobis-norm perturbations and regularization with an $\ell_2$ penalty, while Section 3 in our paper presents results for (a) Mahalanobis-norm perturbations and general Mahalanobis-norm regularizations and (b) $\ell_p$ norms for both perturbation and regularization. On the technical side the proofs that appear in [Tanner et al. 2024] are based on a mapping to a Generalised Approximate Message Passing algorithm. Our results are proven via Gordon's Theorem (Theorem A.1) and allow for a broader range of loss and regularization functions.

Can Assumption 3.11 be extended to accommodate zero-mean sub-Gaussian covariates?

This is an excellent question about practical extensions. While our theoretical guarantees rely on Gaussian assumptions for applying Gordon's Theorem, recent work on universality [Montanari & Saeed (2022), and Dandi et al. (2023)] suggests these results often extend to more general distributions including sub-Gaussian covariates.

The key technical challenge for a formal extension would involve using more general concentration inequalities for sub-Gaussian random variables [Vershynin, "High-Dimensional Probability", 2018]. However, maintaining the freedom of chosing an arbitrary non-increasing convex loss function would require additional technical machinery beyond the scope of this initial work. We believe this is a promising direction for future research.

How restrictive is Assumption 3.13 in practice, and how often is it likely to hold in real-world scenarios?

Assumption 3.13 (simultaneous diagonalizability) is primarily a technical assumption that allows for a well specified setting. In practice, this assumption is less restrictive than it might appear. For example, this property holds when the matrices $\Sigma_w, \Sigma_\delta$ share principal components, which occurs naturally in many signal processing applications where the same underlying factors drive both input correlations and noise structure. The assumption tries to mimic PCA applied to data, which is common practice in many ML pipelines. In such cases, the perturbation and regularization matrices would indeed share eigenvectors with the transformed data covariance.

Nonetheless we agree that future work could relax this assumption to broaden applicability, and our Rademacher complexity analysis in Section 4 already takes a step in this direction by providing distribution-agnostic guarantees.