Research map / Learning theory and algorithms / Prediction and decision losses
Decision-Focused Learning with Directional Gradients
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 Perturbation Gradient (PG) surrogate losses for decision-aware predict-then-optimize, built from zeroth-order finite differences of the plug-in objective, with vanishing excess-regret guarantees even under misspecification.
Problem
Decision-aware learning for predict-then-optimize: the decision loss is piecewise constant and discontinuous in the prediction, so gradient methods cannot be applied directly, and existing surrogates lack regret guarantees when the hypothesis class is misspecified.
Approach
Connect the expected decision loss to the directional derivative of the concave plug-in objective V(t)=min_z t^T z (Danskin's theorem), then approximate that derivative with zeroth-order finite differences (backward PGB, central PGC). The resulting surrogates are Lipschitz, difference-of-concave, have informative gradients, and their approximation error vanishes as n grows.
Key results
- Under misspecification (m=0, alpha=1), only the PG losses show vanishing normalized excess regret as n grows, per the paper's convergence experiment over 100 trials.
- In the well-specified setting (m=-4), all methods including decision-blind ETO achieve relative regret below 0.6% even at n=20.
- The paper reports that PGB and PGC are notably stronger than other methods on the low signal-to-noise portfolio problem, and PG losses substantively outperform SPO+ and FYL on the planted-arc shortest path.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PGB or PGC instead of existing surrogates under model misspecification | Decision-focused learning · Simple misspecification experiment (m=0, α=1) | normalized excess regret | Helped |
| Use PGB or PGC instead of SPO+ as misspecification increases | Decision-focused learning · Simple misspecification experiment | normalized excess regret | Helped |
| Use PGB or PGC instead of SPO+ as noise becomes less symmetric | Decision-focused learning · Simple misspecification experiment | normalized excess regret | Helped |
| Use PGB or PGC instead of FYL or SPO+ | Decision-focused learning · Portfolio optimization | normalized excess regret | Helped |
| Use PG losses instead of FYL or SPO+ | Decision-focused learning · Harder shortest path with planted arcs | normalized excess regret | Helped |
| Use PGB or PGC instead of FYL or SPO+ | Decision-focused learning · Shortest path with random arc costs | normalized excess regret | No clear effect |
| Use PG losses instead of other methods in the well-specified setting | Decision-focused learning · Simple misspecification experiment (m=-4) | normalized excess regret: less than 0.6% | No clear effect |
| Replace backward differencing (PGB) with central differencing (PGC) (ablation) | Perturbation Gradient loss · Simple misspecification experiment | normalized excess regret | Helped |
| Replace backward differencing (PGB) with forward differencing (PGF) (ablation) | Perturbation Gradient loss · Misspecified synthetic setup (α=1, m=0) | decision quality | Hurt |
| Tune the finite-difference step size h (ablation) | Perturbation Gradient loss · Harder shortest path with planted arcs | normalized excess regret | No clear effect |
Surprising findings
- Forward differencing (PGF, the surrogate of a prior work) optimistically underestimates the loss for concave V and can select a policy with significant regret, while backward differencing is pessimistic and performs well.
- SPO+ is nearly as susceptible to misspecification as decision-blind ETO in the synthetic experiment.
Limitations
- PG losses are non-convex (difference of concave functions), so finding best-in-class policies is NP-hard in the worst case; convergence to global optima is not guaranteed.
- Theoretical guarantees rely on a Lipschitz log conditional density assumption (for the expected-error bound) and bounded VC or Rademacher complexity; the rate depends on the choice of h and the complexity of F.
- Fully characterizing how the choice of zeroth-order gradient scheme affects surrogate quality is left open; experiments use only a linear hypothesis class and small grids for h.
Experimental setup
Datasets: Synthetic misspecified data (uniform X, asymmetric noise) PyEPO shortest path grid data Fama-French 12 Industry Portfolios
Benchmarks: Synthetic misspecified experiment Shortest path (random arc costs) Shortest path with planted arcs Portfolio optimization (Fama-French)
Metrics: normalized excess regret expected regret
Baselines: ETO SPO+ DBB FYL LTR list loss PGF
Builds on: SPO+ Danskin's theorem Fenchel-Young loss PyEPO
Closest papers by meaning
- Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML 2025 · similarity 0.89)
- Locally Convex Global Loss Network for Decision-Focused Learning (AAAI 2025 · similarity 0.88)
- Gradient Descent as Loss Landscape Navigation: a Normative Framework for Deriving Learning Rules (NeurIPS 2025 · similarity 0.86)
- Leaving the Nest: Going beyond Local Loss Functions for Predict-Then-Optimize (AAAI 2024 · similarity 0.86)
- Realizable $H$-Consistent and Bayes-Consistent Loss Functions for Learning to Defer (NeurIPS 2024 · similarity 0.86)
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.86)
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.