Introduction
In modern machine learning, data is often not static but reactive. When models are deployed in real-world scenarios—such as credit scoring or insurance risk assessment—agents (users) may adapt their behavior to achieve better outcomes. This phenomenon, known as performative prediction or strategic classification, creates a moving target for optimization. To maintain accuracy and robustness in these environments, researchers frequently employ min-max optimization.
However, two significant hurdles remain for practitioners: the lack of explicit gradient information in many strategic settings and the discrepancy between theoretical sampling assumptions and the practical use of "Random Reshuffling" (RR). This paper introduces a new zeroth-order algorithm designed to bridge these gaps, providing a theoretically grounded and practically efficient solution for decision-dependent risk minimization.
The Challenges of Strategic Environments
1. The Gradient Gap
Most optimization algorithms assume access to gradients (the direction of steepest ascent or descent). In strategic settings, we often do not know the internal utility functions of the agents reacting to our model. Consequently, we can only observe the final outcome—the loss—rather than the gradient. This necessitates "zeroth-order" methods that can optimize functions using only point evaluations.
2. The Theory-Practice Gap
While most mathematical proofs for stochastic optimization assume data is sampled "with replacement," practitioners almost exclusively use Random Reshuffling—shuffling the dataset and cycling through it in epochs—due to its superior empirical performance. Until now, there has been a lack of non-asymptotic analysis for optimistic min-max algorithms using this technique.
Proposed Methodology: OGDA-RR
The authors propose the Optimistic Gradient Descent-Ascent with Random Reshuffling (OGDA-RR) algorithm. This approach integrates several key components to handle the complexities of strategic data:
- Zeroth-Order Estimation: The algorithm estimates gradients by "probing" the objective function. It adds small random perturbations to the parameters and measures the resulting change in loss to determine the update direction.
- Random Reshuffling (RR): By processing data in shuffled epochs, the algorithm aligns with practical engineering standards. The paper provides the first non-asymptotic analysis for this approach in an optimistic min-max context.
- Optimism: The "Optimistic" component of the update uses information from the previous iteration to anticipate the next move in the min-max game. This helps stabilize training dynamics, which are often volatile in adversarial settings.
- Distributionally Robust Optimization (DRO): The authors reformulate strategic classification using a Wasserstein DRO framework. This essentially builds a "safety buffer" around the model, ensuring it remains performant even if the underlying data generation model is slightly misspecified.
Experimental Evaluation
The authors evaluated OGDA-RR across three distinct environments: synthetic datasets (ranging from 500 to 4,000 data points), the GiveMeSomeCredit (GMSC) dataset, and the Porto Bank marketing dataset.
Key Findings
- Superior Convergence: In simulations, OGDA-RR consistently outperformed standard stochastic gradient descent-ascent (SGDA) methods that do not utilize random reshuffling.
- Graceful Degradation: When subjected to large adversarial perturbations, the proposed model maintained its accuracy far better than standard strategic classification models (like LogReg SC), which saw rapid performance collapses.
- Computational Efficiency: The algorithm is more efficient than previous methods that required complex inner loops to approximate updates, making it a viable candidate for larger-scale machine learning tasks.
Conclusion and Future Work
This research successfully bridges the gap between strategic classification and distributionally robust optimization. It proves that one does not need to know the exact "best response" function of a strategic agent to find a robust model; simply querying the loss is sufficient to achieve competitive convergence rates.
While the results are promising, the authors note that the current theory relies on the objective function being convex-concave. Future work remains to extend these zeroth-order reshuffling methods to non-convex landscapes, such as deep neural networks, and to further investigate the sensitivity of the "query radius" hyperparameter used in gradient estimation.
Summary updated