End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty

My H Dinh, James Kotary, Ferdinando Fioretto

Introduction

In many real-world decision-making scenarios, we must act based on parameters that are not known with certainty. Whether predicting traffic delays to optimize a route or forecasting stock returns to build a portfolio, the standard approach is the Predict-Then-Optimize (PtO) paradigm. However, modern applications often demand more than just maximizing a single expected value; they require fairness (e.g., balancing utility across demographic groups) or robustness (e.g., ensuring performance across various future scenarios).

A powerful mathematical tool for these requirements is Ordered Weighted Averaging (OWA). OWA aggregates multiple objectives by assigning weights to their sorted values, allowing decision-makers to prioritize the "worst-off" outcomes or balance competing interests. Despite its utility, OWA functions are inherently non-differentiable due to the sorting operation. This non-differentiability creates a "gradient wall" that prevents standard deep learning models from being trained end-to-end to produce predictions that lead to fair or robust optimal decisions.

Methodological Innovations

This paper introduces a framework to make OWA-based optimization problems differentiable, enabling the integration of complex fairness and robustness objectives directly into the neural network training loop. The authors propose several key techniques:

1. OWA-QP (Quadratic Smoothing)

By transforming the OWA problem into a Linear Program (LP) and adding a quadratic regularization term, the authors create a smooth Quadratic Program (QP). This version can be differentiated using Karush-Kuhn-Tucker (KKT) conditions. While mathematically sound, this approach faces scalability issues because the number of constraints grows factorially ($m!$) with the number of objectives.

2. OWA-Moreau (Moreau Envelope Smoothing)

To address the scalability bottleneck, the authors apply the Moreau envelope—a technique from convex analysis used to create a smooth approximation of a non-smooth function. This represents the first application of Moreau envelopes for objective smoothing in the PtO context. Crucially, this method allows the model to scale linearly with the number of objectives, making it feasible for complex, high-dimensional problems.

3. Surrogate Solvers for Discrete Problems

For problems involving discrete variables, such as Mixed-Integer Programs (MIPs), the authors utilize a differentiable linear surrogate model during training. This surrogate provides a continuous gradient signal that guides the neural network toward predictions that result in better discrete decisions.

Experimental Evaluation

The framework was evaluated across three distinct domains, each representing a different challenge in multiobjective optimization:

  • Robust Portfolio Optimization: Using Nasdaq stock data (2015-2019), the model predicted asset prices across multiple scenarios to minimize regret and maximize robust returns.
  • Multi-Species Warcraft Shortest Path (WSP): In this benchmark, three different "species" (Humans, Naga, and Dwarves) have different movement costs on a map. The goal is to find a single path that balances the costs for all three species fairly.
  • Fair Learning-to-Rank: Using the MSLR-Web10k dataset, the authors optimized search results to balance user relevance (DCG) with "exposure fairness" for different groups of items.

Key Insights and Results

The research demonstrates that embedding fairness and robustness directly into the training loop significantly outperforms traditional two-stage approaches (where a model is trained on Mean Squared Error and then used for optimization).

  • Scalability and Performance: The OWA-Moreau approach proved to be a game-changer. While OWA-QP failed due to memory limits when handling more than 5-7 objectives, OWA-Moreau maintained low runtimes and high performance even as the number of objectives increased.
  • Superior Fairness: In the ranking task, the proposed SoFaiR model achieved an order-of-magnitude reduction in fairness violations compared to existing penalty-based methods, all while maintaining high utility.
  • Improved Robustness: In the Warcraft pathfinding task, the OWA-trained surrogate model significantly reduced the path length for the "worst-off" species, effectively balancing the needs of all groups more effectively than standard baselines.

Conclusion

By bridging the gap between non-differentiable OWA functions and deep learning, this work enables a new class of "fair-aware" and "robust-aware" predictive models. The transition from factorial to linear scalability via the Moreau envelope is particularly significant for practical applications. Future work may extend these techniques to other complex engineering domains, such as urban planning and energy management, where balancing the competing interests of diverse stakeholders is a critical requirement.

Summary updated

Abstract

Many decision processes in artificial intelligence and operations research are modeled by parametric optimization problems whose defining parameters are unknown and must be inferred from observable data. The Predict-Then-Optimize (PtO) paradigm in machine learning aims to maximize downstream decision quality by training the parametric inference model end-to-end with the subsequent constrained optimization. This requires backpropagation through the optimization problem using approximation techniques specific to the problem's form, especially for nondifferentiable linear and mixed-integer programs. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives, known for their ability to ensure properties of fairness and robustness in decision models. Through a collection of training techniques and proposed application settings, it shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
BibTeX
@inproceedings{dinh2024end,
  author = {My H Dinh and James Kotary and Ferdinando Fioretto},
  title = {{End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=ptbCobFKtX},
}
Figure