Abstract
Adversarial training can be used to learn models that are robust against perturbations. For linear models, it can be formulated as a convex optimization problem. Compared to methods proposed in the context of deep learning, leveraging the optimization structure allows significantly faster convergence rates. Still, the use of generic convex solvers can be inefficient for large-scale problems. Here, we propose tailored optimization algorithms for the adversarial training of linear models, which render large-scale regression and classification problems more tractable. For regression problems, we propose a family of solvers based on iterative ridge regression and, for classification, a family of solvers based on projected gradient descent. The methods are based on extended variable reformulations of the original problem. We illustrate their efficiency in numerical examples.
Introduction
Adversarial training (AT) is a cornerstone of robust machine learning, involving training on "worst-case" perturbed versions of data. For linear models, this process is a convex optimization problem that acts as a powerful regularizer, similar to Lasso or Ridge regression. However, practitioners often face a trade-off: deep learning heuristics are fast but converge slowly, while generic convex solvers like CVXPY are accurate but prohibitively slow for high-dimensional datasets. This paper introduces tailored, high-performance optimization algorithms that allow linear adversarial training to scale to high-dimensional datasets where generic solvers fail.
Tailored Optimization Methods
The proposed algorithms are categorized by task type, leveraging smooth reformulations and specific structural properties of linear models.
Classification (Logistic Loss)
The original min-max problem is reformulated into a smooth constrained optimization problem. This allows the use of standard first-order methods like Projected Gradient Descent (PGD). The authors derive closed-form solutions for the projection step, particularly for $\ell_\infty$ attacks, using a sorting-based algorithm with $O(p \log p)$ complexity. Furthermore, they implement SAGA, a variance-reduction method that provides linear convergence rates, significantly outperforming standard Stochastic Gradient Descent (SGD) on large datasets.
Regression (Squared Error Loss)
For regression, an "extended variable" reformulation known as the $\eta$-trick is used. The authors demonstrate that the robust regression problem can be solved by repeatedly solving weighted ridge regression sub-problems. To handle high dimensions efficiently, they employ Preconditioned Conjugate Gradient (CG) descent to solve these sub-problems approximately, avoiding the $O(p^3)$ cost of full matrix inversions.
Experimental Results
The algorithms were evaluated on 13 real-world datasets, including high-dimensional genomics data (e.g., MAGIC wheat with $p=55,067$).
Performance and Scalability
A key finding is that adversarial training with a "rule-of-thumb" radius $\delta$ performs nearly as well as Lasso models that require extensive cross-validation. More importantly, the tailored solvers offer massive speedups. On the MAGIC wheat dataset, the proposed solver converged in under 5 minutes, while CVXPY failed to converge within 24 hours.
Robustness
While AT and Lasso perform similarly on clean data, AT significantly outperforms Lasso under adversarial attack. For example, on the Abalone dataset, AT maintained an $R^2$ of 0.18 under attack, whereas Lasso's performance dropped to -0.37.
Conclusion
By exploiting the specific convex structure of linear adversarial training, the proposed tailored solvers bridge the gap between fast heuristics and slow generic solvers. Future work includes addressing memory constraints for even larger datasets, implementing GPU acceleration, and extending these methods to multiclass classification and non-linear kernel regression.
Summary updated