Abstract
This paper presents a novel robust zero-sum game (RZSG) framework for pool-based active learning (PAL), grounded in advanced statistical learning theory. Traditional active learning often relies on disconnected two-step cycles of training and heuristic-based selection, which can lead to sub-optimality, sampling bias, and sensitivity to data imbalances or noise. We formulate PAL as a single minimax optimization problem where a classifier and a data selector compete. Our framework naturally incorporates distributionally robust optimization (DRO), providing a unified objective that balances average and maximal risk. Empirical results across synthetic, linear, and deep learning benchmarks demonstrate that RZSG consistently outperforms state-of-the-art methods, particularly in noisy and imbalanced scenarios.
Introduction
Passive learning requires massive labeled datasets, which are often expensive or difficult to obtain. Active learning (AL) addresses this by strategically querying labels for the most informative unlabeled examples. However, standard pool-based active learning (PAL) suffers from several critical flaws. First, the disconnect between the training objective and the selection heuristic can result in sub-optimal performance. Second, heuristics like margin-based selection often introduce sampling bias, causing the training set to diverge from the true data distribution. Finally, many AL methods are highly sensitive to outliers and class imbalance.
To overcome these challenges, we propose the Robust Zero-Sum Game (RZSG) framework. By treating AL as a unified optimization task, we ensure that data selection directly contributes to minimizing the final classification error while maintaining robustness to distribution shifts and noise.
The RZSG Framework
We formulate active learning as a single minimax optimization problem between a model $w$ and a selector $p$:
$$\min_{w} \max_{p \in \Delta_n} \sum_{i=1}^n p_i \mathbb{E}_{Y|x_i} [\ell(w; x_i, Y)]$$
In this game, the model $w$ seeks to minimize the weighted expected loss, while the selector $p$ (constrained within a probability simplex $\Delta_n$) attempts to maximize it by assigning higher weights to "hard" or informative examples. Since labels for the unlabeled pool are unknown, the framework estimates the expected loss using the model's current prediction confidence via sigmoid or softmax functions.
This formulation is essentially a form of Distributionally Robust Optimization (DRO). By controlling the distance between the selection weights and a uniform distribution through a regularization parameter $\lambda$, the model balances between minimizing "average loss" (robust to outliers) and "maximal loss" (effective for imbalanced data). This mathematical structure reveals that the algorithm naturally favors examples with small margins—those the model is most uncertain about—placing traditional heuristics within a rigorous theoretical framework.
Experimental Evaluation
We evaluated RZSG on a variety of datasets, ranging from synthetic 2D distributions to complex deep learning benchmarks like MNIST and CIFAR-10.
Synthetic Data and Robustness
To test robustness, we designed a 2D Gaussian dataset with extreme class imbalance (5 positive vs. 100 negative samples) and a single label-flipped outlier.
As shown in Figure 3, traditional approaches fail in this scenario. Maximal risk minimization ($\lambda=0$) is pulled toward the outlier, while average risk minimization ($\lambda=\infty$) is dominated by the majority class. RZSG, with an appropriately tuned $\lambda=1$, successfully ignores the outlier while maintaining a correct decision boundary for the imbalanced classes.
Benchmarks and Deep Learning
On 10 binary classification benchmarks from UCI and LIBSVM, RZSG consistently outperformed Random Sampling (RS) and other state-of-the-art methods like MADI and BMDR. In deep learning experiments on MNIST and CIFAR-10, RZSG demonstrated superior sample efficiency. For instance, on CIFAR-10, RZSG achieved higher accuracy with only 600 labels than competing methods did with 1000 labels, showing a significant lead in the early stages of learning.
Discussion and Conclusion
The RZSG framework provides a rigorous theoretical foundation for active learning. It offers a tighter upper bound on true risk than standard empirical risk minimization, especially when prediction variance is high. Furthermore, the method is computationally efficient, with $O(n)$ or even $O(\log n)$ complexity per iteration, making it suitable for large-scale applications.
While RZSG shows significant promise, its performance depends on the model's internal probability estimates for unlabeled data. Future work will explore improving these estimates through better calibration and extending the framework to more complex tasks such as structured prediction and reinforcement learning.
Summary updated