Scaling Decision-Focused Learning to Large Problems with Lagrangian Decomposition

2026-06-07 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, quick

Summary

A new framework integrates Lagrangian decomposition (LD) into decision-focused learning (DFL) to overcome its scalability limitations in predict-then-optimize problems. Traditional DFL faces high computational costs, requiring a constrained optimization problem solution for each training instance per iteration. This novel approach introduces a surrogate objective and two loss functions, offering two variants with different trade-offs between computational efficiency and solution quality. The framework is compatible with standard DFL methods like Smart Predict-then-Optimize (SPO+) and Implicit Maximum Likelihood Estimation (IMLE). Experiments on multi-dimensional knapsack and quadratic portfolio optimization benchmarks demonstrate competitive performance, consistently outperforming traditional DFL on large-scale instances, handling up to eight times more variables than typically considered. An implementation is available at https://github.com/corail-research/DFL-LD.

Key takeaway

For Machine Learning Engineers building predict-then-optimize systems, if you face scalability issues with traditional decision-focused learning, consider integrating Lagrangian decomposition. This approach allows your models to handle up to eight times more variables efficiently, especially for large-scale problems like knapsack or portfolio optimization. Explore the provided implementation to enhance computational performance without sacrificing competitive solution quality.

Key insights

Lagrangian decomposition scales decision-focused learning, enabling efficient predict-then-optimize solutions for large, complex problems.

Principles

• DFL's scalability is limited by per-iteration optimization.
• Lagrangian decomposition improves DFL computational efficiency.
• Framework variants offer efficiency-quality trade-offs.

Method

The framework introduces a surrogate objective and two loss functions for prediction model training. It offers two variants balancing efficiency and solution quality, integrating with SPO+ and IMLE.

In practice

• Apply to multi-dimensional knapsack problems.
• Utilize for quadratic portfolio optimization.
• Integrate with existing SPO+ or IMLE methods.

Topics

• Decision-Focused Learning
• Lagrangian Decomposition
• Predict-then-Optimize
• Scalability
• Constrained Optimization
• Portfolio Optimization

Code references

• corail-research/DFL-LD

Best for: Research Scientist, AI Scientist, Machine Learning Engineer, AI Architect

Related on AIssential

• Score Function Gradient Estimation to Widen the Applicability of Decision-Focused Learning — Combining stochastic smoothing and score function gradient estimation extends decision-focused learning to complex optimization problems.
• Pareto-Optimal Offline Reinforcement Learning via Smooth Tchebysheff Scalarization — Smooth Tchebysheff scalarization enables multi-objective offline RL to recover non-convex Pareto fronts.
• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces — OPT★ provides scalable, auto-verifiable optimization tasks to train LLMs for complex step-by-step reasoning.
• Decoupling Numerical and Structural Parameters: An Empirical Study on Adaptive Genetic Algorithms via Deep Reinforcement Learning for the Large-Scale TSP — Dynamic structural adaptation is more critical than numerical fine-tuning for scalable evolutionary algorithms.
• A Gentle Introduction to Nonlinear Constrained Optimization with Piecewise Linear Approximations — Linearizing separable nonlinear programs via PWL approximations and SOS type 2 constraints enables efficient solution with LP/MIP solvers.
• RL Scaling Laws for LLMs — Scaling laws, while precise for LLM pretraining, are more complex and context-dependent in reinforcement learning.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.