TL;DR
This paper introduces ParetoSPO, a novel Decision-Focused Learning (DFL) framework that extends the popular "Smart Predict, then Optimize" (SPO+) approach to multi-objective problems. By leveraging the true Pareto Frontier during training, ParetoSPO overcomes the limitations of simple scalarization, allowing models to make high-quality decisions even in complex, non-convex trade-off spaces.
What Problem Does This Paper Address?
In many real-world scenarios—like routing a delivery truck or managing a power grid—we face two major hurdles:
- Uncertainty: We don't know the exact costs (e.g., traffic delays, fuel prices) and must predict them using machine learning.
- Conflicting Goals: We want to minimize time and cost and emissions simultaneously.
The traditional "Predict, then Optimize" approach treats these as separate steps: first, minimize prediction error (like Mean Squared Error), then feed those predictions into a solver. However, minimizing prediction error doesn't always lead to the best decisions—a small error in a critical cost can lead to a disastrously bad plan. This is the prediction-decision gap.
Decision-Focused Learning (DFL) closes this gap by training the ML model directly on the quality of the final decision. But for multi-objective problems, existing DFL methods rely on "scalarization"—turning multiple goals into one weighted sum. This fails for many combinatorial problems where the "Pareto Frontier" (the set of optimal trade-offs) is non-convex; scalarization simply cannot "see" solutions in those non-convex regions.
Methods
The authors propose ParetoSPO, which bridges the gap between efficient single-objective DFL and complex Pareto-based optimization.
- Model Committee: Instead of one giant model, they train a "committee" of expert models. Each expert is specialized for a specific user preference (e.g., one expert for "fastest delivery," another for "lowest fuel cost").
- Pareto-Informed Target Selection: This is the core innovation. During training, the system uses a multi-objective solver offline to find the true Pareto Frontier for the training data. For a given preference, it selects the "best" target solution from this true frontier using cosine similarity.
- Hybrid Loss Function: The model then calculates a loss based on the difference between the decision made using its current predictions and this high-quality, Pareto-optimal target. This provides a geometrically sound learning signal that guides the model toward the correct region of the solution space, regardless of non-convexity.
Datasets
The researchers evaluated their method using the PyEPO framework on two classic combinatorial problems:
- Multi-Objective Shortest Path Problem (MOSPP): Finding paths in grid graphs (4x4 and 5x5) with two conflicting costs per edge.
- Multi-Objective Multi-Dimensional Knapsack Problem (MOMDKP): Selecting items (32 items total) to maximize two value objectives while staying within multiple capacity constraints.
They generated synthetic datasets where features map to costs through non-linear functions, adding varying levels of noise ($\epsilon = 0, 0.25, 0.5$) to test robustness.
Key Insights and Ideas
- Geometry Matters: Standard SPO+ is "blind" to non-convex parts of the Pareto front because it always targets a vertex on the convex hull. By picking a target directly from the true Pareto set, ParetoSPO provides a much richer learning signal.
- Efficiency through Pre-computation: Multi-objective solvers are notoriously slow. By solving the optimization problems offline during data preparation, the authors keep the actual training loop fast, as it only requires a standard single-objective solver.
- The "Aha" Moment: Even in zero-noise settings, standard SPO+ struggles because of the non-convexity of combinatorial problems. ParetoSPO's ability to "see" the whole frontier gives it a fundamental advantage that isn't just about handling noise, but about understanding the problem's structure.
Key Results
The performance was measured using Hypervolume Regret—the percentage of the optimal trade-off space the model fails to capture. Lower is better.
- Consistent Superiority: ParetoSPO outperformed both standard MSE (two-stage) and scalarized SPO+ baselines across all noise levels.
- Shortest Path (MOSPP): At zero noise, ParetoSPO achieved a regret of 0.70%, compared to 0.98% for scalarized SPO+ and 1.15% for MSE.
- Knapsack (MOMDKP): The gap was even wider here. At zero noise, ParetoSPO had 8.36% regret, while scalarized SPO+ trailed at 10.96% and MSE at 12.65%.
- Robustness: As noise increased to $\epsilon=0.5$, ParetoSPO maintained its lead, showing it learns more robust cost representations.
Limitations and Future Work
- Scalability: The "model committee" approach requires training a separate model for every discrete preference. This doesn't scale well if there are thousands of different user preferences.
- Generalization: Currently, an expert model only knows about its specific preference. It cannot generalize to a new, unseen trade-off requested by a user at runtime.
- Future Directions: The authors suggest developing a single preference-conditioned model that takes both features and a preference vector as input. This would allow a single model to generalize across the entire Pareto Frontier, combining the accuracy of ParetoSPO with the flexibility of a unified architecture.
Summary updated