In the world of machine learning, we often want our models to do more than just minimize error. We want them to be fair, robust, and satisfy specific rules. Usually, we handle this using constrained optimization, where we add a "penalty" (a Lagrange multiplier) for every rule the model breaks.
But what happens when you have thousands of rules? Or an infinite number of them? This paper from Google Research and UC Berkeley, presented at NeurIPS 2020, offers a clever solution: instead of keeping track of every single penalty manually, let’s train a second machine learning model to predict them.
TL;DR
This paper introduces Lagrange Multiplier Models to solve optimization problems with a massive or even infinite number of constraints. By replacing individual Lagrange multipliers with a model that predicts them based on constraint features, the authors enable fine-grained requirements like per-query fairness in ranking and intersectional fairness across hundreds of groups.
What Problem Does This Paper Address?
Standard constrained optimization works well when you have a few dozen constraints (e.g., "don't discriminate against these five racial groups"). However, modern ML demands much higher resolution:
- Intersectional Fairness: Ensuring fairness not just for "Race" and "Gender" separately, but for every possible combination (e.g., Black women over 50 in a specific zip code). The number of groups grows exponentially.
- Per-Query Fairness: In search engines or recommendation systems, we might want every single search query to be fair, not just the "average" query. Since there are infinite possible queries, we can't possibly assign a fixed penalty to each one.
The "standard" approach requires storing and updating one Lagrange multiplier ($\lambda$) for every constraint. When the number of constraints ($m$) is huge, this becomes computationally impossible and fails to generalize to new, unseen constraints.
Methods
The authors propose a fundamental shift in how we define the Lagrangian.
In a typical setup, the Lagrangian is: $$\mathcal{L}(\theta, \lambda) = \text{Loss}(\theta) + \sum_{i=1}^{m} \lambda_i \cdot \text{Constraint}_i(\theta)$$
The authors replace the vector of multipliers $\lambda$ with a multiplier model $\vec{\lambda}(\gamma)$. This model takes a "feature vector" describing the constraint as input and outputs the appropriate multiplier.
- The Multiplier Model: This can be a simple linear model or a deep neural network. It learns the relationships and redundancies between different constraints.
- The Optimization: They treat the problem as a two-player game (a Nash equilibrium). One player (the main model) tries to minimize the loss, while the other player (the multiplier model) tries to find and penalize the most violated constraints.
- Graceful Failure: If the multiplier model is too simple (under-parameterized), the system "fails gracefully" by defaulting to satisfying the average of the constraints rather than failing entirely.
Key Insights and Ideas
- Redundancy is a Feature: Constraints in ML are rarely independent. If a model is unfair to one intersectional group, it’s likely unfair to a similar one. By using a model for multipliers, the system learns these patterns, allowing it to handle millions of constraints with a relatively small number of parameters.
- Generalization to the Unseen: Because the multipliers are generated by a model based on features, the system can estimate a penalty for a constraint it has never seen before (like a brand-new search query).
- Capacity Controls Strictness: The complexity of the multiplier model acts as a dial for how strictly the constraints are enforced. A high-capacity neural network can "hunt down" every small violation, while a simpler model focuses on the big picture.
Key Results
The authors evaluated their approach on three distinct tasks, including intersectional fairness (Communities and Crime dataset), fairness under noisy group memberships (UCI Adult), and per-query fairness (MSLR-WEB10K).
- Intersectional Fairness: On the Communities & Crime dataset, defining 535 different groups based on racial demographics, a 3-layer neural network multiplier model was able to satisfy almost all constraints. It significantly outperformed unconstrained models and simple linear multiplier models, driving the 95th percentile violation down effectively.
- Ranking Fairness: In the MSLR-WEB10K experiments, the proposed method achieved much better "90th percentile" fairness. While previous state-of-the-art methods only ensured fairness on average across all queries, this method significantly reduced the unfairness of the "worst-off" queries.
- Efficiency: The method avoids the need for a "brute-force" search for the most violated constraint, making it practical for real-world training pipelines.
Limitations and Future Work
- Approximate Feasibility: The authors prove that the constraints are satisfied approximately. If the multiplier model isn't flexible enough, some constraints will still be violated.
- Stochasticity: The theoretical guarantees rely on "mixed Nash equilibria," which technically results in a stochastic model (one that makes slightly different predictions each time). While the authors found that deterministic versions work well in practice, bridging this gap more formally is an area for future research.
- Choosing Constraint Features: The success of the model depends on having good features to describe the constraints. In some applications, it might not be obvious what those features should be.
Summary updated