Abstract
Adversarial training (AT) is a robust alternative to standard regularization techniques like Lasso, yet it remains computationally prohibitive for high-dimensional linear models. This paper introduces tailored optimization algorithms that reformulate the non-smooth adversarial min-max problem into smooth optimization tasks. By utilizing augmented variables for classification and an iteratively reweighted least squares approach for regression, our methods achieve high-precision solutions at scales where traditional solvers fail.
Introduction
Adversarial training is typically associated with deep learning defenses against adversarial examples. However, in the context of linear models, AT serves as a sophisticated form of regularization that offers unique benefits, such as producing sparse solutions and performing well without expensive cross-validation.
The primary challenge is mathematical: the standard formulation of AT is a non-smooth min-max problem. Existing solvers are either scalable but inaccurate (like PGD) or accurate but unscalable (like generic convex solvers). This work bridges the gap by creating tailored solvers that are both mathematically precise and computationally efficient.
Methodology
The paper proposes two distinct families of algorithms based on the loss function:
1. Classification (Logistic Loss)
The authors introduce an augmented variable formulation. By adding a single scalar variable, they transform the non-smooth min-max problem into a smooth constrained optimization problem. This allows the application of advanced first-order methods such as Accelerated Projected Gradient Descent (AGD) and SAGA (a stochastic method with variance reduction). These methods achieve high precision much faster than standard subgradient approaches, with SAGA demonstrating linear convergence.
2. Regression (Squared Error Loss)
For regression, the authors employ the "η-trick" (iteratively reweighted least squares), breaking the problem into a sequence of weighted ridge regression sub-problems. To maintain scalability on massive datasets, these sub-problems are solved approximately using Preconditioned Conjugate Gradient (CG), avoiding expensive matrix inversions.
Key Insights
- Smoothness as a Catalyst: The realization that adding one variable can smooth the objective function unlocks the $O(1/k^2)$ convergence rate of accelerated methods, a significant improvement over the $O(1/\sqrt{k})$ rate of standard adversarial methods.
- The "Default δ" Advantage: Unlike Lasso, which requires expensive 10-fold cross-validation to tune the penalty parameter, AT with a default adversarial radius (δ) performs nearly as well as a perfectly tuned Lasso "out of the box."
- Exploiting Geometry: By utilizing the specific geometry of $\ell_2$ and $\ell_\infty$ perturbations, the authors reduced complex projections to simple $O(p \log p)$ operations.
Experimental Results
The proposed solvers were evaluated against industry standards like CVXPY and standard deep learning methods (FGSM/PGD) across various real-world and synthetic datasets.
- Massive Speedups: On the MAGIC wheat dataset (55,000+ features), the tailored solver converged in under 5 minutes, while CVXPY failed to converge within a day.
- High Precision: The methods reached a sub-optimality of $10^{-8}$ rapidly, whereas standard deep learning approaches often plateaued at much lower accuracy levels.
- Competitive Performance: In regression tasks, the "default" AT performed on par with cross-validated Lasso while providing inherent protection against test-time perturbations.
Conclusion and Future Work
While these algorithms provide a significant leap in efficiency for linear models, future work includes extending these approaches to multiclass classification and optimizing implementations for GPU hardware. The "augmented variable" approach also holds promise for inspiring more efficient training methods for the final layers of deep neural networks.
Summary updated