Research map / Learning theory and algorithms / Prediction and decision losses
Leaving the Nest: Going beyond Local Loss Functions for Predict-Then-Optimize
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Efficient Global Losses (EGLs), which combine feature-based parameterization of convex loss families with model-based sampling of candidate predictions, to learn decision-focused losses for predict-then-optimize more sample-efficiently and without the localness assumption.
Problem
Learning task-specific loss functions for predict-then-optimize (decision-focused learning) is sample-inefficient and relies on a localness assumption that fails when predictions are far from true labels, leading to poor decision quality.
Approach
Replace per-instance local loss functions with a neural mapping from features to parameters of convex-by-construction LODL loss families (feature-based parameterization), and generate candidate predictions from intermediate outputs of predictive models trained with MSE (model-based sampling) instead of Gaussian noise around true labels.
Key results
- On (Hard) Cubic Top-K, EGL achieves normalized DQ 0.69 versus 0.24 for the best baseline (Entropy-Regularized Top-K), a gain of nearly 200%.
- EGL with 32 samples matches LODL with 2048 samples on Cubic Top-K (0.96) and Web Advertising (0.95 vs 0.93), reaching state-of-the-art in the literature domains.
- EGLs take about 6% of LODL's total time (646.58s vs 10430.50s) on Web Advertising, an order-of-magnitude speedup.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace local Gaussian perturbation sampling with model-based sampling | EGL / learned losses · (Hard) Cubic Top-K | Mean Normalized Test DQ: -0.68 -> 0.69 | Helped |
| Use EGL with 32 samples rather than LODL with 2048 samples | learned losses · Web Advertising | Mean Normalized Test DQ: 0.93 -> 0.95 | Helped |
| Use EGL with 32 samples rather than LODL with 2048 samples | learned losses · Portfolio Optimization | Mean Normalized Test DQ: 0.154 $\pm$ 0.005 -> 0.153 $\pm$ 0.004 | No clear effect |
| Use EGL rather than LODL with 2048 samples | learned losses · Web Advertising | Total runtime: 10430.50 $\pm$ 131.66 -> 646.58 $\pm$ 66.70 | Helped |
| Add feature-based parameterization (FBP) to LODL (ablation) | Cubic Top-K, Directed Quadratic loss · Cubic Top-K | Normalized Test Decision Quality: -0.38 $\pm$ 0.29 -> 0.58 $\pm$ 0.26 | Helped |
| Add model-based sampling (MBS) to LODL (ablation) | Cubic Top-K, Directed Quadratic loss · Cubic Top-K | Normalized Test Decision Quality: -0.38 $\pm$ 0.29 -> 0.96 $\pm$ 0.00 | Helped |
| Add both MBS and FBP to LODL (ablation) | Web Advertising, Quadratic loss · Web Advertising | Normalized Test Decision Quality: 0.84 $\pm$ 0.04 -> 0.92 $\pm$ 0.02 | Helped |
| Use 4 rather than 1 layer in the FBP mapping network (ablation) | EGL · Web Advertising | Normalized Test DQ: 0.91 $\pm$ 0.04 -> 0.93 $\pm$ 0.01 | Helped |
| Use 5 rather than 1 layer in the FBP mapping network (ablation) | EGL · Portfolio Optimization | Normalized Test DQ: 0.13 $\pm$ 0.02 -> 0.1 $\pm$ 0.02 | Hurt |
| Increase the number of sampling models from 1 to 8 (ablation) | EGL · Web Advertising | Normalized Test DQ: 0.88 $\pm$ 0.04 -> 0.93 $\pm$ 0.01 | Helped |
Surprising findings
- Gaussian-noise localness sampling causes learned losses to fail on Hard Cubic Top-K, and even directed LODLs fail catastrophically there.
- Model-based sampling also improves performance in domains where the localness assumption holds, not only where it breaks.
Limitations
- Speed-ups are smaller for simple optimization problems where the solver is fast, such as Cubic Top-K, so FBP helps less there.
- The mechanism by which model-based sampling helps is only hypothesized; EGLs work in some domains where the necessary conditions do not hold.
- Portfolio Optimization results are confounded by a temporal distribution shift between validation and test sets.
Experimental setup
Datasets: Yahoo! Webscope Dataset QuandlWIKI dataset Cubic Top-K (synthetic) (Hard) Cubic Top-K (synthetic, introduced here)
Benchmarks: Cubic Top-K (Hard) Cubic Top-K Web Advertising Portfolio Optimization
Metrics: normalized test decision quality validation decision quality time taken to run meta-algorithm validation MSE
Baselines: MSE SPO+ Entropy-Regularized Top-K Multilinear Relaxation Differentiable QP L&Z LODL
Builds on: LODL Locally Optimized Decision Losses Learning-to-Rank/L&Z reweighted MSE SPO+ Gaussian sampling localness assumption
Closest papers by meaning
- A Survey of Learning Criteria Going beyond the Usual Risk (Abstract Reprint) (AAAI 2024 · similarity 0.89)
- Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML 2025 · similarity 0.87)
- Decision-Focused Learning with Directional Gradients (NeurIPS 2024 · similarity 0.86)
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.86)
- Locally Convex Global Loss Network for Decision-Focused Learning (AAAI 2025 · similarity 0.85)
- MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.