Abstract
We present a minimax framework for classification that considers stochastic adversarial perturbations to the training data. We show that for binary classification it is equivalent to SVM, but with a fresh geometric perspective. By framing regularization as robustness against a stochastic adversary, we derive a novel multiclass regularization scheme ($L_{2,\infty}$ norm) that proves more resilient to noise than standard methods.
Introduction
In the classic linearly separable case, Support Vector Machines (SVMs) offer a compelling geometric interpretation: they maximize the margin between classes. However, when data is not perfectly separable and regularized hinge loss is employed, this clear geometric intuition is often lost. Previous attempts to restore this intuition via Robust Optimization—where a deterministic adversary moves training points within a ball to maximize loss—often result in overly pessimistic models or complex formulations. This paper explores an alternative: what if the adversary is stochastic? Instead of a single worst-case point, the adversary must choose a probability distribution of perturbations.
Methodology: Stochastic Adversaries
The proposed minimax framework involves a learner choosing a classifier $w$ and a stochastic adversary choosing a distribution $p(\bar{x}|x)$ for each training point. The game is governed by three rules:
- Centeredness: The average perturbed point must be the original point ($E[\bar{x}] = x$).
- Budgeted Spread: The expected distance (or squared distance) of the perturbation is limited by a parameter $\sigma$.
- Objective: The learner minimizes the maximum expected hinge loss.
Through convex duality, this infinite-dimensional problem is transformed into a tractable, finite-dimensional optimization. For the binary case, robustness to a stochastic adversary with an $L_2$ budget is mathematically identical to standard $L_2$-regularized SVM. For multiclass settings, this framework yields the $L_{2,\infty}$ norm regularization, which penalizes the maximum Euclidean norm among class weight vectors rather than the sum of squares (Frobenius norm).
Experimental Evaluation
The authors evaluated the Robust SVM (RSVM) across three domains: toy datasets with varying noise, standard UCI benchmarks, and large-scale text datasets.
Performance on Benchmark Datasets
On standard UCI datasets, RSVM variants demonstrated performance comparable to or exceeding standard SVMs. The results across various datasets like usps, glass, and segment highlight the stability of the stochastic adversarial approach.
Large-Scale Text Classification
The advantages of RSVM were particularly evident in high-dimensional text classification tasks. In datasets such as 20News and NY Times subsets, the $L_{2,\infty}$ regularization frequently outperformed the standard Frobenius-regularized SVM. For instance, on the 20News dataset, RSVM reduced the error rate from 14.76% to 12.74%.
Key Insights
- Regularization as a Noise Budget: The hyperparameter $\sigma$ represents a physical "expected distance" for noise, allowing for a heuristic setting based on the average distance to a point's nearest neighbor.
- Multiclass Robustness: The $L_{2,\infty}$ norm suggests that in multiclass settings, we should worry most about the "strongest" class classifier rather than the average of all of them.
- Noise Resilience: In toy experiments, as the number of noisy dimensions increased, RSVM significantly outperformed standard multiclass SVMs.
Conclusion and Future Work
This work provides a new lens through which to view SVM regularization. By replacing deterministic worst-case scenarios with stochastic ones, we recover geometric intuition and derive superior multiclass regularization. Future research will address the computational costs of squared $L_2$ constraints, which currently require expensive Semidefinite Programming, and extend these concepts to structured prediction tasks.
Summary updated