Technical Summary: Decision-Focused Learning via Tangent-Space Projection of Prediction Error

1. Problem Statement

In "predict-then-optimize" pipelines, a predictive model estimates parameters (e.g., cost vectors) for a downstream optimization problem, which then computes a final decision. Traditional Decision-Focused Learning (DFL) aims to train predictors to minimize regret—the suboptimality incurred by acting on predicted parameters rather than true ones—rather than simply minimizing prediction error (e.g., Mean Squared Error, MSE).

However, computing the gradient of regret with respect to the predictor's parameters is challenging. Existing approaches face significant limitations:

• Differentiable Optimization Layers: Methods that differentiate through solver iterations (e.g., via KKT conditions) can be computationally expensive, numerically unstable (due to ill-conditioned linear systems), and solver-dependent.
• Surrogate Losses: Methods using convex surrogates (e.g., SPO+) or perturbed estimators often deviate from the true regret objective, may lack generality beyond linear costs, or require additional solver calls.

The paper addresses the need for a method that computes true regret gradients efficiently, without differentiating through solver iterations or relying on proxy objectives, while maintaining numerical stability.

2. Methodology: PEAR

The authors propose PEAR (Projected Error As Regret-gradient), a method grounded in the geometric characterization of regret gradients under standard regularity conditions.

Theoretical Foundation

Under assumptions of strict convexity, Linear Independence Constraint Qualification (LICQ), and Strict Complementary Slackness, the active set of constraints at the optimal solution remains locally stable under small perturbations. Within this region, the paper establishes that the regret gradient admits a closed-form geometric characterization:
$$\nabla_{\hat{c}} R(\hat{c}; c) = P_H (\hat{c} - c) = P_H e$$
where:

• $e = \hat{c} - c$ is the prediction error.
• $P_H$ is a sensitivity operator defined as $P_H = H^{-1} - H^{-1}J^\top(JH^{-1}J^\top)^{-1}JH^{-1}$.
• $H$ is the Hessian of the objective function (local curvature).
• $J$ is the Jacobian of the active constraints.

Geometric Interpretation: The regret gradient is equivalent to the prediction error projected onto the tangent space of the active constraints, scaled by the local curvature. This implies that the learning signal filters out "decision-irrelevant" components of the error (those orthogonal to the feasible region) and retains only the components that influence the decision.

Algorithmic Implementation

PEAR computes this gradient without forming the dense projection operator $P_H$ explicitly. Instead, it utilizes a reduced linear system derived from the active constraints:

1. Forward Pass: Solve the optimization problem to obtain the primal-dual solution and identify the active set $\mathcal{A}$ via complementary slackness.
2. Backward Pass:
   • Compute the prediction error $e$.
   • Solve a compact $k \times k$ linear system (where $k$ is the number of active constraints) using a Schur complement reduction: $(JH^{-1}J^\top)v = JH^{-1}e$.
   • Reconstruct the projected gradient: $g = H^{-1}e - H^{-1}J^\top v$.

Handling Linear Programs (LPs): Since LPs lack curvature ($H$ is singular) and have piecewise-constant solution maps, PEAR adds a small quadratic regularization term ($\phi(z) = \frac{\lambda}{2}\|z\|^2$) to ensure differentiability. To prevent the gradient from vanishing in flat regions, PEAR employs normal injection, selectively adding a controlled component of the normal space gradient to the tangent projection to stabilize learning.

3. Key Contributions

1. Geometric Characterization: The paper establishes an explicit geometric relationship between prediction error and regret gradients, showing that regret gradients are simply MSE gradients filtered to remove decision-irrelevant directions.
2. Efficient Computation (PEAR): The proposed method computes regret gradients via a reduced linear system over active constraints. This avoids differentiating through solver iterations, eliminates the need for surrogate losses, and improves numerical stability compared to existing differentiable layers.
3. Empirical Performance: PEAR demonstrates superior decision quality and training efficiency across synthetic Linear Programming (LP) benchmarks and a real-world Quadratic Programming (QP) portfolio optimization task.

4. Experimental Results

The authors evaluated PEAR against baselines including MSE (two-stage), SPO+, DBB, PFYL, and LAVA.

• Synthetic LP Benchmarks (Shortest Path & Knapsack):

  • Regret: PEAR achieved the lowest normalized regret across various polynomial degrees of cost generation, outperforming or matching all baselines.
  • Efficiency: PEAR was consistently the most computationally efficient, often training significantly faster than differentiable layers (e.g., 2x faster than SPO+ on Shortest Path) and avoiding timeouts that plagued other methods on complex Knapsack instances.
  • Robustness: Under multiplicative noise in cost generation, PEAR maintained the lowest regret, demonstrating robustness to model misspecification.

• Real-World QP (Mean-Variance Portfolio Optimization):

  • On S&P 100 data, PEAR achieved the lowest normalized regret and translated this into superior realized portfolio performance, including the highest cumulative/annualized returns, best Sharpe ratio, and lowest maximum drawdown.
  • PEAR was faster than differentiable QP layers (QPTH, CvxpyLayers) and exhibited more stable gradients, leading to better out-of-sample performance.

• Constraint Shifts:

  • The paper tested robustness when test-time constraints differed from training (e.g., changing origin-destination pairs in Shortest Path, tightening Knapsack capacity, or allowing short-selling in portfolios).
  • PEAR consistently degraded the least among DFL methods and maintained the lowest regret, suggesting it learns transferable cost structures rather than memorizing specific optimal paths.

5. Significance and Claims

The paper claims that PEAR provides a simpler and more direct alternative to existing DFL approaches by revealing that regret gradients are structurally related to prediction errors via tangent-space projection.

• Interpretability: The method clarifies why certain error components matter for decisions (those in the tangent space) and which do not (those in the normal space).
• Efficiency and Stability: By decoupling the forward solver from the backward computation via a reduced linear system, PEAR avoids the computational overhead and numerical instability associated with differentiating through complex solvers.
• Generality: The approach applies to optimization problems with linear or quadratic objectives, offering a deterministic regret gradient without requiring perturbation-based estimation or additional solver calls.

The authors conclude that PEAR achieves superior decision quality with reduced training time and improved robustness under constraint shifts, offering a principled and efficient framework for Decision-Focused Learning.