Reduced Cost Influence Functions for Predict-then-Optimize under Noisy Data

AI summary

Overview

Research area: Machine learning for decision-making pipelines (predict-then-optimize / decision-focused learning), robust learning under corrupted labels, and linear optimization theory. Technical level: Advanced — the paper assumes familiarity with linear programming (bases, reduced costs, optimality cones), influence functions from robust statistics, and regret-based analyses of prediction. Scope: The paper introduces "Reduced Cost Influence Functions" (RCIFs) — a decision-aware signal that measures how upweighting each training point shifts the reduced costs of a downstream linear program — and uses them to reweight noisy training data so that downstream decision regret falls.

What This Paper Is About

In a predict-then-optimize pipeline, a model predicts the cost vector of a linear program, and the LP's optimal solution is the decision actually acted on. Small prediction errors that move the prediction across the boundary between two optimality cones can cause a discontinuous jump in decision quality, so training data corruption that would look mild under a standard squared-loss metric can be costly downstream. The paper asks how to make that downstream decision robust without changing either the predictor's architecture or the LP solver, using a large possibly corrupted training set plus a small clean validation set.

Key Contributions

1. A new decision-aware influence signal. The authors define the Reduced Cost Influence Function, RCIF_{k,θ̂}(z_v, w_j) = δ(B,k)^T ∇_θ f_θ̂(z_v) I_θ̂(w_j), which composes the standard influence function of a training point on the learned parameters with the LP's edge direction δ(B,k), yielding a first-order estimate of how upweighting that training point changes a reduced cost at a validation point.
2. Two scoring schemes and a reweighting algorithm. A "two-sided" score Ψ^TS that uses the smallest reduced-cost margin at each validation point, and a "directed" score Ψ^D that, for incorrect validation points, restricts attention to nonbasic directions where the true cost violates optimality (s_k(c_v, B_v) < 0). Scores are converted to weights by an exponential rule with temperature λ (set to 0.05 in experiments) and optionally accumulated over τ iterations (set to 5).
3. Theory characterizing the score and when the method wins. A factorization of the RCIF into a residual-interaction term and a Mahalanobis input-alignment term, a decomposition of the score into clean plus corruption components, a high-probability signed decrease for directionally corrupted points, and thresholds on validation-set size m separating regimes where the reweighted estimator beats unweighted ERM, validation-only ERM, or both.
4. Experiments on random LPs, shortest path, neural upstreams, and misspecified feature maps, benchmarking against ten methods including SPO+ variants and an SPO-based influence-function reweighting baseline.

Main Findings

• Lowest regret on random LPs among reweighting methods: Iterative Exp. Directed reaches 0.3451 ± 0.0133 test regret against 0.3564 ± 0.0130 for unweighted ERM, 0.4184 ± 0.0191 for validation-only, 0.3509 ± 0.0124 for SPO Influence Weight, and 0.2785 ± 0.0109 for the Clean ERM oracle (100 seeds; paired Wilcoxon signed-rank p = 0.007). Setup: upstream dimension 20, LP dimension 10, 20 constraints, 200 training points, 50 validation points, 150 test points, β = 0.3.
• Much larger gains on structured problems: On the 4×4 grid shortest-path benchmark (upstream input dimension 30, 400 training, 100 validation, 200 test points, β = 0.2), Iterative Exp. Directed attains 0.9437 ± 0.0172 versus 1.0029 ± 0.0169 unweighted and 0.9560 ± 0.0158 for SPO Influence Weight, with paired p < 0.048 for all methods. The paper reports this as recovering 39% of the noise-induced error (the gap of 0.152 between Clean ERM at 0.8513 ± 0.0171 and unweighted), versus 30% for the next-best method.
• The best variant depends on whether the upstream model is linear: With a two-layer Tanh network (hidden dimension 8; 5×4 grid, 200 training, 100 validation, 200 test points, β = 0.3), the additive Directed variant wins at 1.3958 ± 0.0217, ahead of Exp. Two-Sided at 1.4211 ± 0.0196, unweighted at 1.4317 ± 0.0198, Iterative Exp. Directed at 1.4511 ± 0.0187, and the Clean ERM reference at 1.3452 ± 0.0190. The authors conjecture that influence-function approximation error compounds across iterations in nonlinear settings.
• A validation-size "sweet spot" matches the theory: In a study varying the clean validation set over {5, 10, 20, 50, 100, 150} (4×4 grid, upstream input dimension 20, 500 training points, 200 test points, β = 0.3, 100 seeds), unweighted ERM wins at small m, the RCIF method wins at moderate m, and validation-only ERM wins at large m — the ordering predicted by Theorem 2.
• Gains persist under misspecification: Raising the polynomial degree of PyEPO's feature-to-cost map from 1 to 2 and 4 (4×4 grid, input dimension 30, 400/100/200 train/validation/test, β = 0.2, 50 seeds), Iterative Exp. Directed attains 0.4856 ± 0.0135 at degree 2 and 0.2899 ± 0.0115 at degree 4, versus 0.5715 ± 0.0145 and 0.3483 ± 0.0135 for unweighted ERM. The paper notes raw regrets are not comparable across degrees because PyEPO rescales costs.
• Signed score decrease for corrupted points: Under assumptions (D1)–(D5) with a linear upstream (f_θ(z) = θz) and squared loss, when the alignment parameter γ > 0, the corrupted point's score is shifted by -αγ in expectation and satisfies Ψ_j(c̃_j) - Ψ_j(c_j) ≤ -αγ/2 with probability at least 1 - exp(-mγ²/(8M_γ²)).
• Score decomposition: The RCIF factors as -δ(B_v,k)^T r_j · κ(z_v,z_j), where r_j = θ̂z_j - c̃_j is the residual and κ is the Mahalanobis inner product z_v^T Σ̂^{-1} z_j; the aggregate score decomposes as Ψ_j = Ψ_j^clean + u_j^T η_j, separating clean signal from corruption.
• A naive reduced-cost baseline does not help much: The "RC Weight" baseline using the raw reduced-cost margin scores 0.3549 ± 0.0131 on random LPs and 1.0035 ± 0.0169 on shortest path, close to unweighted ERM, whereas the influence-based propagation does.

Methodology in Plain English

The pipeline has two parts: a regression model that predicts costs from features, and a linear program that takes those predicted costs and returns a decision. Because the LP's answer only changes when the predicted cost vector crosses a boundary between regions ("optimality cones") where different bases are optimal, the natural quantity to track is the reduced cost — the slack measuring how far the prediction sits from each boundary.

The authors start from the classical influence function, which approximates how much the fitted model's parameters would move if one training point were upweighted slightly; that quantity has a closed form built from the gradient of the loss at that point and the inverse Hessian of the training objective. They then push that parameter shift through the predictor's gradient at a clean validation point and project it onto the LP's edge direction, giving one number per (training point, validation point, boundary direction) triple. Each training point is scored by averaging these numbers across the validation set, with a sign that asks correct validation points to be pushed deeper into their cone and incorrect ones to be pushed out of the wrong cone. The directed variant uses the true validation cost to pick which boundary to target.

Scores become weights through a softmax with temperature λ, the model is refit on the reweighted data, and the procedure can be repeated — recomputing scores at the new fit and summing them across rounds. Hyperparameters are λ = 0.05, τ = 5 iterations, and φ = 0.05 for the additive variant. Corruption is simulated by picking a fraction β of training points uniformly (default 0.3) and adding isotropic Gaussian noise to their cost labels, with validation and test sets kept clean; the metric is out-of-sample regret on a clean test set.

Why This Matters

The work reframes robustness in decision-focused learning as a data reweighting problem rather than a loss-design problem, so it composes with existing SPO+ style training instead of replacing it. It also makes a concrete theoretical statement about when a small clean validation set is worth more as a weighting signal than as a standalone training set — a practical question for anyone with limited labelling budget. The finding that iterative influence-based reweighting helps with linear upstreams but can hurt with neural ones is a caution for practitioners.

Real-world applications named or implied by the paper:

• Vehicle routing and shortest-path routing systems, where the downstream LP is the route-selection step.
• Dynamic pricing engines, where predicted costs feed a price-optimization program.
• Clinical decision support, where predictions feed a constrained allocation or treatment-planning problem.
• General LP-based operations pipelines where labels are logged from noisy sensors or historical records but a small audited clean set exists.

Industry relevance: the method requires no change to the deployed predictor or solver, only a reweighting pass and a refit, and its assumptions — a large noisy log plus a small clean audit sample — match common industrial data situations.

Future Directions

• Extending the theory and the algorithm beyond nondegenerate LPs and linear upstream models, since the formal guarantees assume f_θ(z) = θz, squared loss, nondegeneracy, and bounded LP geometry (assumption D5).
• Controlling the accumulation of influence-function approximation error across iterations, which the authors conjecture explains why iterative reweighting underperforms the single-round or additive variants with a neural upstream.
• Characterizing the thresholds m_*(λ) and m^*(λ) more concretely for real problem families, so practitioners can predict from data statistics whether their validation set sits in the favorable regime.
• Extending the corruption model: the theory's directional corruption assumption (D4, η_j = -α δ̂_j) is narrower than the isotropic Gaussian noise used in experiments, and the paper reports a separate zero-mean corruption analysis in its appendix.

Target Audience

Researchers and graduate students in operations research and machine learning who work on decision-focused or predict-then-optimize methods, robust learning with noisy labels, or influence-function-based data valuation. It is also relevant to practitioners building pricing, routing, or resource-allocation pipelines who have a large noisy log of cost labels and a small curated clean set, and who are comfortable with LP duality concepts such as reduced costs and optimality cones.

Authors’ abstract

Machine learning models deployed in decision-making pipelines, from vehicle routing to dynamic pricing to clinical decision support, must remain reliable in the face of low-quality training data. We study a predict-then-optimize setting in which an upstream model predicts the cost vector of a downstream linear program, with a large pool of noisy training data supplemented by a small curated set of clean data. We introduce Reduced Cost Influence Functions (RCIFs), which combine influence functions from robust statistics with the geometry of linear optimization to estimate how each training point shifts downstream decisions. Building on this, we propose a reweighting algorithm that uses RCIFs to downweight harmful training points and reduce downstream regret. Experiments on random linear programs and shortest-path problems show that our approach reduces regret, and accompanying theory characterizes properties of RCIFs and identifies regimes favorable to our method relative to baselines.