Abstract
Large-scale learning systems are often evaluated across multiple, sometimes conflicting, objectives. How can we effectively learn and optimize such complex systems with potentially incompatible goals? Moreover, how do we improve these systems when user feedback, potentially highlighting previously unaddressed issues, becomes available? We propose a novel theoretical model for learning and optimizing such systems. Instead of relying on a static or predefined trade-off among objectives, our model dynamically adapts based on received feedback, updating its internal state accordingly. This approach accommodates multiple objectives in a general form, accounting for their potential incompatibilities. We explore both stochastic and adversarial settings. In the stochastic setting, we demonstrate that our framework can be naturally formulated as a Markov Decision Process with stochastic losses, for which we provide efficient algorithms that achieve vanishing regret. In the adversarial setting, we design algorithms with competitive ratio guarantees. Finally, we report a series of experimental results validating the effectiveness of our stochastic algorithms.
Introduction
Modern AI systems, such as recommendation engines and advertising auctions, are tasked with satisfying hundreds of metrics simultaneously. However, these metrics are often fundamentally incompatible. For instance, in recidivism prediction tools like COMPAS, optimizing for overall predictive accuracy can directly conflict with achieving equal false positive rates across demographic groups.
Traditionally, system designers set static trade-offs between these goals before deployment. This approach suffers from two major flaws: it cannot adapt to "hidden" biases revealed by live user feedback, and it faces a "curse of dimensionality" — with $k$ criteria, there are $2^k$ possible configurations, making exhaustive search impossible. This paper introduces a framework to navigate this incompatibility space efficiently by using real-time feedback to minimize total loss, including the cost of system transitions.
The Incompatibility Model
The core of the proposed framework is the Incompatibility Graph. In this model, vertices represent individual criteria (e.g., accuracy, diversity, fairness for specific groups), and edges indicate that two criteria cannot be simultaneously satisfied.
To overcome the exponential complexity of the state space, the authors introduce Correlation Sets. By assuming that complaints for a specific metric only depend on a small subset of other metrics rather than the entire system, the problem becomes tractable. This local interaction model allows the system to reduce a potentially massive search problem into a series of manageable local optimizations.
Optimization Settings
The paper addresses two primary environments for user feedback:
1. The Stochastic Setting
When user complaints follow a stable probability distribution, the problem is modeled as a Markov Decision Process (MDP). The authors developed "Explore-Then-Commit" and UCB-style algorithms that allow the system to spend a limited phase testing configurations to estimate interaction effects. These algorithms achieve vanishing regret, meaning the system's performance converges to that of an optimal offline strategy over time.
2. The Adversarial Setting
In scenarios where complaints are unpredictable or potentially manipulated, the authors propose a Barrier Algorithm. To prevent the system from "jittering" — frequently switching states in response to every minor complaint — the algorithm implements a threshold. A neighboring configuration must accumulate a significant amount of loss before a switch is triggered. This ensures a constant competitive ratio, guaranteeing that the online performance remains within a fixed factor of an omniscient offline optimizer.
Experimental Validation
The effectiveness of these algorithms was validated using both synthetic and real-world data:
- Simulated Scalability: Using Erdős-Rényi models to generate synthetic incompatibility graphs, the researchers demonstrated that the "Correlation Set" approach allows the system to handle over 100 criteria effectively.
- UCI Adult Dataset: In a real-world application predicting income levels, the model successfully balanced overall accuracy with fairness metrics (True Positive Rate and AUC) across racial groups. The online algorithm converged to the optimal configuration rapidly following a brief exploration phase.
Conclusion
This research shifts the perspective on fairness from a static constraint to a dynamic, feedback-driven process. By explicitly accounting for the "fixing costs" of system changes and leveraging local interactions between metrics, the proposed framework provides a scalable and theoretically grounded path for managing the complex trade-offs inherent in modern large-scale learning systems.
Summary updated