acceptodds
Under review as a conference paper at ICLR 2027

IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback

Abstract

Decision-focused learning (DFL) trains prediction models for better decisions, rather than prediction accuracy alone. In the online setting, predictions can guide successive decisions; a learning algorithm (the learner) updates a model as decision outcomes arrive. When those outcomes arrive late, both the model and the decisions it would produce have changed, making old learning gradients stale. How can the learner make better use of this feedback? We introduce implicit gradient transport for online mirror descent (IGT-OMD) to answer this question and combine gradients from new feedback with changes in past gradients caused by model updates. One version of this algorithm reuses stored decisions and gradient information (frozen transport); another recomputes them at the current model (full re-evaluation). For stationary problems, we bound the frozen gradient-descent variant's excess cumulative loss over the best fixed model chosen in hindsight (i.e., regret), and derive a sufficient number of iterations to solve the decision problem. For a shared strongly convex quadratic model, continuous and discrete stability analyses give an explicit learning-rate rule. Experiments cover linear–quadratic regulator (LQR) stability, Warcraft paths, and Sinkhorn transport. At delay 50 on Sinkhorn, full re-evaluation with Adam reduces loss by 10.81% versus learning from newly arrived feedback alone and by 26.6% versus the best tested delayed optimistic mirror descent (DOOMD) baseline. The transport gain costs the arrival-only control's training-update time. Independent random realizations confirm the transport benefit; frozen transport offers a lower-cost option in the tradeoff between decision quality and computation.

Primary area:
optimization
Keywords:
decision-focused learning, predict-then-optimize, online learning, delayed feedback, bilevel optimization, hypergradient, implicit differentiation, gradient transport, online mirror descent, regret analysis, learning-rate stability, delay differential equations.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ECdiOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies online decision-focused learning (DFL) with delayed feedback. In this setting, model parameters and their associated decisions may have changed by the time feedback arrives, making historical gradients outdated. To address this issue, the authors propose Implicit Gradient Transport Online Mirror Descent (IGT-OMD). The method combines gradients from newly arrived feedback with correction terms that account for changes in historical gradients as model parameters evolve. This improves the use of delayed feedback. The authors develop two implementations. Frozen Transport reduces computational costs by caching historical decisions and gradient-related information. Full Re-evaluation recomputes decisions and their gradients using the current model. On the theoretical side, the authors establish a regret upper bound for Frozen Euclidean IGT-OMD under assumptions of stationarity, convexity, and boundedness. They analyze how delays, inner optimization accuracy, and historical gradient corrections affect gradient estimation errors. They also derive a sufficient iteration complexity for the inner solver and learning rate stability conditions for a specific quadratic model. In the experiments, the authors evaluate the algorithm on LQR, Warcraft shortest path, and Sinkhorn optimal transport tasks, focusing on stability, decision quality, and computational cost. In the Sinkhorn experiments with independent random seeds, Full Re-evaluation + Adam + IGT reduces cumulative decision loss by 10.81% compared with a matched baseline that uses only newly arrived feedback at a delay of 50. However, its training update time increases to approximately 40.28 times that of the baseline. The results show that the benefits of gradient transport depend on the optimizer, gradient computation method, and learning rate. They also reveal a clear trade-off between decision quality and computational cost.

Critical strengths

S1. The method offers some novelty. To address the issue of outdated gradients in bilevel optimization with delayed feedback, the authors propose IGT-OMD based on historical gradient differences. They also develop two implementations, Frozen Transport and Full Re-evaluation, offering different trade-offs between computational efficiency and gradient accuracy.

S2. The theoretical analysis is relatively comprehensive. Under clearly stated assumptions, the paper provides regret bounds, hypergradient error bounds, and learning rate stability conditions. It also analyzes inner optimization accuracy and iteration complexity, providing theoretical support for the proposed algorithm.

S3. The experimental evaluation is reasonably thorough. The authors evaluate the method on three tasks: LQR, Warcraft, and Sinkhorn. They use independent random seeds and paired experiments to validate the main performance improvements. They also report computational costs, which strengthens the credibility of the experimental findings.

Critical weaknesses

W1. There is a gap between the theoretical analysis and the main experimental results. The regret and stability analyses mainly focus on Frozen Euclidean IGT-OMD under strong assumptions, while the most significant experimental gains come from Full Re-evaluation + Adam. Therefore, the current theory does not fully explain or guarantee the performance improvements observed in practice.

W2. The fairness of baseline comparisons remains a concern. Comparisons with methods such as DOOMD involve different optimizers and learning rate settings. Moreover, the best baseline learning rate lies at the boundary of the search range, suggesting that the baseline may not have been fully tuned. This raises questions about the claimed performance advantages over existing methods.

W3. The high computational cost raises concerns about practical applicability. Although Full Re-evaluation reduces decision loss by 10.81% at a delay of 50, its training update time increases by a factor of 40.28. In addition, the effectiveness of gradient transport is sensitive to the optimizer and learning rate. The lack of comparisons under equal computational budgets further limits the assessment of its practical value.

Questions for authors

1. Regarding the consistency between theory and experiments. The theoretical guarantees mainly focus on Frozen Euclidean IGT-OMD, while the most significant experimental gains come from Full Re-evaluation + Adam. Could the authors further explain how the current theory supports these experimental results and whether a verifiable theoretical connection exists between the two methods?

2. DOOMD still achieves its best performance at the upper boundary of the learning rate search range, even after the range is expanded. Could the authors clarify whether the baseline has been sufficiently tuned and whether further learning rate tuning could significantly narrow the performance gap?

3. Full Re-evaluation requires approximately 40 times the training update cost at a delay of 50. Could the authors provide performance comparisons under equal computational budgets to demonstrate whether the advantages of IGT still hold?

5 comments
AuthorsOpenReview ↗

Weakness and Questions 1-2 answered here.

Thank you for the precise summary and questions. "IGT" below is full re-evaluation with Adam, the configuration of our main transport results. We answer each weakness together with its matching question, in order.

W1 / Q1. Connection between the theory and the experiments.

The analyzed and the empirical methods use the same gradient estimate: each stored example contributes its gradient at arrival and afterwards only the changes, so its total contribution always equals its most recently computed gradient. They differ in two respects, the decision computation (frozen versus full) and the optimizer that turns this estimate into a parameter step (plain gradient steps versus Adam). The theory connects to the experiments at three levels.

  1. The gradient-error bound does not depend on the optimizer. Theorem 2 bounds the error of the gradient estimate along any sequence of parameter updates. Its statement and proof use only the size of each parameter change, not the rule that produced it, so the bound holds unchanged along the trajectory Adam produces. For full re-evaluation, the term that comes from outdated decisions (κ∑k∥Δk∥\kappa\sum_k\|\Delta_k\|) is replaced by the accuracy of the finite solver's derivative, because the decision is recomputed at the current parameters. What requires plain gradient steps is Theorem 1's conversion of gradient error into regret, so the regret bound itself is stated for the Euclidean update.
  2. The analyzed algorithm itself confirms the theory's prediction. On the quadratic-control problem we run exactly the analyzed algorithm. Its largest stable learning rate shrinks with delay at a log–log slope of −0.962, against Proposition 2's prediction of −1.
  3. The empirical gain is not a learning-rate artifact. With arrival re-evaluation and Adam held fixed, and the learning rate selected separately for each method on calibration seeds before evaluation, IGT lowers cumulative loss on ten fresh seeds by 6.44% [5.78, 7.10], 11.31% [10.22, 12.40] and 17.99% [17.26, 18.71] at delays 5, 10 and 50 (95% intervals; all three survive Holm correction). Arrival-only selects 0.001, the rate used in the paper. IGT selects 0.003, 0.003 and 0.01.

W2 / Q2. Baseline fairness: optimizers, learning rates and tuning.

We extended DOOMD's search to rates {0.003, 0.01, 0.03, 0.1, 0.3, 1} for both hint choices, on five calibration seeds per delay. The selected rates are 0.1, 0.03 and 0.03 at delays 5, 10 and 50, all without the hint, and each is now worse at both neighbouring rates, so the best tested rate lies inside the grid. We froze these choices and then evaluated on five new seeds with common inputs:

DelayIGT loss reduction relative to tuned DOOMD95% interval
517.23%[15.17, 19.29]
1024.12%[22.62, 25.61]
5032.90%[31.60, 34.21]

Each percentage is the average over seeds of the per-seed reduction; all three survive Holm correction.

Two comparisons separate the optimizer from the method. First, with Adam held fixed and each method's learning rate tuned separately, IGT still lowers loss by 6.44–17.99% (W1 / Q1, point 3). Second, on five untouched seeds our arrival-only Adam control is within 1.6% of DF-OGD, a plain-gradient method whose four settings were tuned until all were bracketed, while IGT is 7–19% better than both (response to Reviewer YPWM, Q3). The advantage therefore comes from refreshing stored examples, not from the choice of optimizer.

AuthorsOpenReview ↗

Weakness 3/ Question 3 answered

W3 / Q3. Computational cost, sensitivity to the optimizer and learning rate, and equal budgets.

The 40.28× factor. It came from our original implementation, which recomputed stored examples one at a time. Computing them in one batched call, IGT's training time is 3.2×, 3.5× and 5.4× that of arrival-only learning at delays 5, 10 and 50 (median paired ratios; at delay 50, 19.8 s versus 3.6 s for 1,000 decisions).

Sensitivity to the learning rate. Mean cumulative loss on the calibration seeds, for each method at each tested rate:

Delay, methodRate 0.0003Rate 0.001Rate 0.003Rate 0.01
Delay 5, arrival-only676.1576.9671.7913.7
Delay 5, IGT665.8546.4531.5657.0
Delay 50, arrival-only708.2616.7702.7921.7
Delay 50, IGT689.6554.6510.7503.9

IGT has lower loss than arrival-only at every tested rate and delay, and it tolerates large rates far better: at rate 0.01, IGT's loss is 657.0 versus 913.7 at delay 5 and 503.9 versus 921.7 at delay 50. Tuning each method's rate therefore preserves IGT's advantage, as the held-out comparison in W1 / Q1 confirms (6.44–17.99%).

Sensitivity to the optimizer. With plain gradient steps at the same rate as the arrival-only learner, transport can hurt, as in our Warcraft runs with plain SGD. Proposition 2 predicts this: with plain gradient steps, the buffered changes enlarge the step along high-curvature directions, so the largest stable rate shrinks from 2/λmax⁡2/\lambda_{\max} without transport to 2/(λmax⁡(1+2B))2/\bigl(\lambda_{\max}(1+2B)\bigr) with it. Our plain-gradient comparisons used one shared rate for both arms, so they did not give transport the smaller rate this condition requires. With Adam and separately tuned rates, the gain holds at every delay (W1 / Q1).

Equal computational budgets.

On five untouched seeds, with 1,000 decisions on 10×10 transport problems, the same feedback and inputs for every method, and each seed's methods sharing the same two-CPU allocation (mean cumulative loss · median training time; DF-OGD tuned until all four of its settings were bracketed, see our response to Reviewer YPWM, Q3):

MethodDelay 5Delay 10Delay 50
Arrival-only Adam583.1 · 3.4 s588.8 · 4.0 s626.9 · 3.6 s
IGT (batched)544.0 · 10.7 s528.3 · 14.1 s513.9 · 19.8 s
DF-OGD (fully tuned)590.6 · 31.9 s597.9 · 36.1 s632.4 · 34.2 s
FTL, 2 steps454.5 · 54.2 s460.0 · 62.0 s493.3 · 57.2 s
IGT's share of FTL's improvement over arrival-only30%47%85%
IGT's training time relative to FTL's0.200.230.35

Follow-the-leader (FTL), the unperturbed form of DF-FTPL (Capitaine et al., 2026), re-optimizes the predictor over all revealed examples every round. Its cost per round grows with the number of revealed examples, while IGT's stays fixed at the buffer size. Between the arrival-only control and FTL, IGT's improvement grows with delay. At delay 50 it achieves 85% of FTL's improvement over arrival-only in about a third of FTL's training time. IGT is also better and faster than the fully tuned DF-OGD at every delay. The batched implementation computes the same per-example gradients as the original one (relative difference about 10−610^{-6}) and is 1.4×, 2.1× and 6.6× faster at delays 5, 10 and 50.

Thanks for the response and the additional experiments. They address some of my concerns, but there is still no theoretical guarantee for Full Re-evaluation + Adam, or proof that gradient transport performs better than arrival-only learning. So I'll keep my rating unchanged for now.

Reviewer_YPWMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies decision-focused learning (DFL) in online scenario with delayed feedback, where model updates can make previously computed decision gradients stale. It proposes Implicit Gradient Transport for Online Mirror Descent (IGT-OMD), which reuses past feedback by incorporating changes in previously computed gradients rather than repeatedly adding stale gradients; its two variants, frozen transport and full re-evaluation, trade computational cost against gradient freshness. Theoretically, under stationary-loss and regularity assumptions, the paper establishes a regret bound for the frozen variant’s exact-inner-solution regret, characterizes hypergradient errors, and derives inner-solver iteration and learning-rate stability guarantees. Experiments on LQR, Warcraft path planning, and Sinkhorn optimal transport demonstrate improved stability and decision quality in several settings.

Critical strengths
  1. The paper addresses an important practical challenge: tackles stale gradients in delayed-feedback decision-focused learning and proposes Implicit Gradient Transport to reuse historical feedback while accounting for changes in gradients.
  2. The paper provides regret bounds, hypergradient-error analysis, and solver stability guarantees.
Critical weaknesses
  1. The full re-evaluation variant can be substantially more expensive than arrival-only learning (e.g., 40.28× training-update time in one experiment), which may limit its practicality in large-scale or latency-sensitive settings.
  2. The theoretical guarantees rely on specific assumptions, while the experiments cover a relatively narrow set of tasks. Further evaluation across more problem classes and delayed-feedback regimes would strengthen the claims of generality.
Questions for authors
  1. The regret analysis relies on stationary losses and specific regularity assumptions. How would the theoretical guarantees extend to nonstationary environments, where the underlying decision costs change over time?

  2. Full re-evaluation achieves better decision quality in some experiments but incurs substantially higher computational costs. Can the authors develop an adaptive strategy that selectively re-evaluates buffered examples to balance performance and efficiency?

  3. The paper discusses window-averaged hypergradient methods for online bilevel optimization, such as SOBOW (Lin et al., 2023), but does not compare against them experimentally/. How does IGT-OMD compare with other existing online bilevel optimization methods, e.g. windowed hypergradient methods, under the same delayed-feedback setting?

2 comments
AuthorsOpenReview ↗

Weakness 1/Question 2 addressed.

Thank you for the constructive questions. We ran new experiments for each one. "IGT" below is full re-evaluation with Adam, the configuration of our main transport results. New results:

  • With learning rates selected separately for each method before evaluation, IGT lowers cumulative decision loss relative to arrival-only Adam by 6.44%, 11.31% and 17.99% at delays 5, 10 and 50, on ten fresh seeds. All three survive Holm correction.
  • A batched implementation makes IGT 6.6× faster at delay 50: 19.8 seconds of training for 1,000 decisions.
  • Refreshing only a quarter of the stored examples, chosen by how much their forecast changed, keeps 84% of IGT's improvement.
  • SOBOW, even when given exact inner solutions, does not improve on arrival-only learning; IGT is 6.8–18.5% better.
  • With DF-OGD (Capitaine et al., 2026) tuned until all four of its settings were bracketed, IGT lowers loss by 7–19%, winning on every seed at every delay, and the batched IGT also trains faster. Against DOOMD tuned to a bracketed best rate, IGT lowers loss by 17–33%.

W1 / Q2. Computational cost and selective re-evaluation.

Our original implementation recomputed each stored example's gradient one at a time. These computations are independent, so we now compute them together in a single batched call. The batched version computes the same per-example gradients (relative difference about 10−610^{-6}); the small difference in final loss below comes from floating-point rounding accumulated over 1,000 rounds of training. On five untouched seeds at delay 50 (1,000 decisions, 10×10 transport problems, two CPU cores, the same inputs and allocation for every method):

MethodMean cumulative lossMedian training time
Arrival-only Adam626.93.6 s
IGT, original509.1127.8 s
IGT, batched513.919.8 s

The median paired speedup is 6.6×.

Selective re-evaluation fits directly into the update. If only some stored examples are refreshed in a round, each refreshed example contributes the difference between its new gradient and the last value we computed for it, and the others contribute nothing until their next refresh. Each example's total contribution still equals its most recently computed gradient, so the update remains consistent under any refresh schedule. A budget of kk refreshes per round can then go to the examples whose forecast has changed most since their last refresh. That change is measured with a forward pass of the predictor alone, with no decision problem solved.

We tested this on a separate set of five fresh seeds at delay 50, with 50 stored examples and the learning rate selected on calibration seeds:

Examples refreshed per roundDecision solves for refreshShare of full refresh's improvement over arrival-only
all 50 (full refresh)100%100%
25, largest forecast change51%92%
12, largest forecast change24%84%
25, in rotation51%89%
12, in rotation24%80%
none (arrival-only)0%0%

Refreshing the 12 examples whose forecast changed most keeps 84% of the improvement with a quarter of the decision solves, and choosing by forecast change beats refreshing in rotation at both budgets.

AuthorsOpenReview ↗

Weakness 2/Question 1 and Question 3 addressed

W2 / Q1. Nonstationary environments.

Our main experiments are nonstationary, and the analysis extends to round-dependent problems.

BenchmarkWhat changes over timeDelays tested
Optimal transport (Sinkhorn)True costs drift (Ornstein–Uhlenbeck process)0–50 rounds
Shortest path (Warcraft)Tile costs drift0–50 rounds
Quadratic controlTrue system fixed (a learning-rate stability test)1–500 rounds

Every IGT gain cited in this response, including the tuned results above, is measured under this drift.

On the theory, the extension changes two steps of the proof and keeps the rest:

Step of the proofIn the extension to round-dependent losses
Error of each arriving gradientCompared with the gradient of the loss of its own round instead of a common objective, so the bound of Theorem 2 applies example by example
How delay entersLosses are summed by the round in which each decision was made, so delay enters only through how far the parameters move while that round's feedback is pending
Bound on parameter movement; memory termUnchanged
ComparatorBest fixed predictor (static regret) for convex per-round losses; tracking a best predictor that moves over time (dynamic regret) adds a term for how far it moves (Zinkevich, 2003)

The revision adds this extension route to the discussion of Theorem 1.

Q3. Comparison with online bilevel methods, including SOBOW.

IGT's loss reduction relative to each comparator, on five fresh seeds held out from that method's tuning (average over seeds of the per-seed reduction; 95% intervals; all Holm-corrected; SOBOW was evaluated at delays 5 and 50):

Comparator (how it was tuned)Delay 5Delay 10Delay 50
DF-OGD (Capitaine et al., 2026), all settings bracketed7.16% [5.44, 8.87]11.63% [9.69, 13.58]19.48% [18.79, 20.18]
DOOMD, learning rate bracketed17.23% [15.17, 19.29]24.12% [22.62, 25.61]32.90% [31.60, 34.21]
SOBOW, faithful adaptation26.93% [24.90, 28.95]—33.41% [32.93, 33.89]
SOBOW, exact inner solutions, plain step14.17% [10.94, 17.40]—23.90% [21.49, 26.32]
SOBOW, exact inner solutions, Adam (strongest)6.77% [4.62, 8.92]—18.52% [17.89, 19.15]

SOBOW (Lin et al., 2023) combines a single-loop inner update, which keeps one inner variable and moves it one step per round, with an outer update that averages the hypergradients of the last WW rounds. The single-loop update assumes consecutive rounds share nearly the same inner problem. In decision-focused learning every round is a new problem with its own forecast costs, so in our faithful delayed implementation (Algorithm 2, with float64 linear solves checked against exact hypergradients) the inner plan's row sums stay off by about as much as their target values. We therefore also gave SOBOW exact inner solutions, computed with the same 10-iteration solver every other method uses, so that only its window averaging remains. We calibrated the window (WW = 1, 5, 10) and the learning rate on separate seeds; every window's best rate lies inside the tested range. No window larger than 1 improved on W=1W=1, and with W=1W=1 the update is exactly our arrival-only control (identical losses on every seed). Because SOBOW averages stored, past hypergradients and never recomputes them, the last row isolates what IGT adds: refreshing stored examples at the current predictor.

DF-OGD is the algorithm Capitaine et al. (2026) design for changing environments. Its four settings (step-size coefficient, radius of the parameter region, and the number and step size of its inner optimization steps) were tuned jointly over 1,485 calibration runs, extending the search wherever the best value lay at the edge until every selected value was worse at both of its neighbouring values. For example, the radius search went out to 500; the selected radius is 50 at delay 5 and 150 at delays 10 and 50. IGT wins on all 15 seed–delay pairs, and the batched implementation trains 1.8–3.0× faster than DF-OGD. The quality–time comparison with the follow-the-leader learner from the same paper is in our response to Reviewer ECdi, Q3.

Reviewer_dbjsOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a new algorithm, implicit gradient transport for online mirror descent (IGT-OMD), for decision-focused learning under delayed feedback.

Critical strengths

I think the main strength of the paper is identifying this interesting problem setting where feedback (i.e., decision costs) are not available to a model until later time steps. This has not been a well-studied problem in the decision-focused learning literature.

Critical weaknesses
  1. The paper is very clearly AI-written. While AI-writing along is not disqualifying, I find it incredibly challenging to understand the paper. In particular, I struggle to understand how the paper proposes to “reuse” feedback, and what the paper even defines as “feedback.” Furthermore, many terms are undefined (e.g., hypergradient), and many statements are not explained (see questions section below).

  2. In my opinion, the paper does not adequately distinguish between its own contributions / terminology and those borrowed from the literature. For example, the paper calls Hs−1∇wℓsH_s^{-1} \nabla_w \ell_s the “adjoint” - is this commonly used terminology, or is this paper the first to use this term? This should be clarified.

  3. The paper seems to only consider smooth, unconstrained inner problems (Line 133). If so, this seems to severely limits the types of problems that this algorithm can apply to. At a minimum, the authors should explain how restrictive this assumption is.

Questions for authors
  1. Line 89: What does this mean: “Our continuous/discrete results share one restricted recurrence.”

  2. Line 105: Why might the solver return wt≠wt⋆(θt)w_t \neq w_t^\star(\theta_t)? Why is this a setting we care about?

  3. Line 122: RTenvR_T^\mathrm{env} does not seem to be defined.

  4. Line 131: What are the “stationary outcomes” referring to?

  5. Line 162: Why does the inner problem need to be repeatedly solved to begin with?

  6. Line 339: Why use an LQR proxy? Why a proxy?

3 comments
AuthorsOpenReview ↗

Weaknesses addressed.

W1. What "feedback" is and how it is "reused."

Take the transport experiment. In each round, the predictor sees the features of that round's problem and forecasts its 10×10 cost matrix. The solver turns the forecast into a transport plan, and the plan is executed. The true cost matrix of that round is revealed dd rounds later. This true cost matrix is the feedback. Every method we compare receives the same feedback at the same time.

Once an example's true costs are known, we keep the example (its features and true costs). Reuse means that we keep computing this example's learning gradient in later rounds at the predictor's current parameters, instead of using it once and discarding it. The plan that was executed is never changed; only the learning signal is updated.

The learning gradient is a hypergradient: the derivative of the decision's true cost with respect to the predictor's parameters, including the effect that flows through the decision (changing the parameters changes the forecast, which changes the plan, which changes the cost).

IGT adds a stored example's gradient once, when its feedback arrives, and afterwards adds only the change in that gradient since the previous round. If an example's gradient is 2.0 at arrival, then 2.3, then 2.4, IGT adds 2.0, then 0.3, then 0.1. The running total, 2.4, always equals the example's gradient at the current parameters. Re-adding the full gradient every round would give 2.0 + 2.3 + 2.4 = 6.7, so an example's influence would grow with the number of times it was revisited.

The two versions differ only in how the current gradient is obtained. Full re-evaluation solves the example's decision problem again with the current forecast and differentiates it. Frozen transport skips that solve: it keeps the decision and adjoint computed at arrival and updates only the parts of the gradient that depend directly on the parameters.

W2. Standard tools versus our contribution.

Standard tools we use: the implicit-differentiation formula for the hypergradient (Eq. 4); the adjoint, i.e. the vector vv that solves Hv=∇wℓHv=\nabla_w \ell so that the inverse Hessian never has to be formed (the term is standard, e.g. Giles and Pierce, 2000, and the same linear solve is used for bilevel learning in Pedregosa, 2016, Eq. 2); and the idea of transporting past gradients to the current parameters (Arnold et al., 2019).

Our contribution: (i) the observation that, under delayed feedback in decision-focused learning, a stored example's gradient becomes outdated both because the parameters moved and because the decision those parameters imply moved; (ii) the arrival-plus-change update described above, in a frozen and a full version; (iii) the analysis of this update (Theorems 1–3, Propositions 1–2); and (iv) the experiments. The revised introduction states this division explicitly.

W3. How restrictive is the smooth inner-problem assumption?

Much less than it first appears, because it describes the decision layer that every gradient-based decision-focused method trains through. A raw linear or combinatorial problem has a piecewise-constant solution, so its derivative with respect to the forecast is zero or undefined. Every gradient-based method (SPO+, blackbox differentiation, perturbed optimizers, regularized LP/QP layers) therefore trains through a smoothed or surrogate version of the decision problem, and the smoothed versions in common use are smooth, strongly convex problems of the kind our assumption describes. Our three benchmarks illustrate the range:

  • Quadratic control. The decision problem is a strongly convex quadratic whose curvature is at least 2R=0.2 I2R = 0.2\,I for every forecast, so the assumption holds exactly and uniformly.
  • Optimal transport. The transport plan must satisfy marginal constraints, but the entropy-regularized problem that Sinkhorn solves can be written over its dual potentials, where it is unconstrained and smooth, and strongly convex on any bounded set of potentials once the one free constant shift (which leaves the plan unchanged) is fixed. That is the form our assumption requires.
  • Shortest path (Warcraft). This is a discrete problem, trained through the blackbox-differentiation surrogate of Vlastelica et al. (2020). Here our update goes beyond the theorem's setting, and it still reduces the decision-cost gap by 10.7%, 10.0% and 5.5% at delays 5, 10 and 50 with the optimizer held fixed (Table 2).

So the assumption leaves out only decision layers with no usable gradient, which no gradient-based method can train through, and the update itself remains effective on a discrete surrogate. The revision places this discussion next to the assumption.

AuthorsOpenReview ↗

Questions 1-4 addressed

Answers to the six questions

Q1. "Our continuous/discrete results share one restricted recurrence" (line 89). Proposition 1 (stability of a continuous-time model) and Proposition 2 (the learning-rate condition for the actual discrete algorithm) analyze the same simplified version of Algorithm 1. In that version:

  • every stored example's gradient is the same linear function g(θ)=C(θ−θ⋆)g(\theta)=C(\theta-\theta^\star), with the same curvature matrix CC and the same minimizer θ⋆\theta^\star, the point where every gradient is zero;
  • one example's feedback arrives per round;
  • the buffer always holds BB examples;
  • the step size η\eta is constant.

Let xnx_n be the distance from θ⋆\theta^\star after nn updates, measured along one direction in which CC stretches by a factor λ\lambda (an eigenvector of CC). Algorithm 1's update then becomes

xn+1=[1−ηλ(1+B)] xn+ηλB xn−1.(Eq. 10)x_{n+1}=\bigl[1-\eta\lambda(1+B)\bigr]\,x_n+\eta\lambda B\,x_{n-1}. \qquad \text{(Eq. 10)}

The xn−1x_{n-1} term is the memory: the BB buffered examples contribute the change in their gradients since the previous update.

Proposition 1 studies the continuous-time model x′(u)=−λ(1+B) x(u)+λB x(u−h)x'(u)=-\lambda(1+B)\,x(u)+\lambda B\,x(u-h), in which the past state enters with lag hh, and shows that it is stable for every lag. Proposition 2 studies Eq. 10 itself and gives the exact learning-rate condition η<2/(λmax⁡(C)(1+2B))\eta<2/\bigl(\lambda_{\max}(C)(1+2B)\bigr). The two are linked because stepping the continuous model forward with step size η\eta and lag h=ηh=\eta (forward Euler) reproduces Eq. 10 exactly. Together they show that the continuous model never limits the learning rate, so the limit comes entirely from taking finite steps. That limit is what our LQR experiment measures (Q6). The revision replaces the sentence at line 89 with this explanation.

Q2. Why might the solver return wt≠wt⋆(θt)w_t\ne w_t^\star(\theta_t) (line 105)? Here wt⋆(θt)w_t^\star(\theta_t) is the exact best decision for the costs the predictor forecasts, and wtw_t is the decision we actually execute. They differ whenever the decision is computed by an iterative solver that is stopped after a fixed number of iterations, as practical systems do to meet a time limit. For example, our transport plans use 10 Sinkhorn iterations. Sinkhorn reaches the exact optimal plan only in the limit, so the plan after 10 iterations is close to the optimum but not equal to it.

This matters because the cost we actually pay is the cost of wtw_t. Eq. 3 therefore splits regret into two parts: RTenvR_T^{\mathrm{env}}, the regret we would have if every decision were solved exactly (how well the predictor learns), and ETE_T, the extra loss from executing the solver's approximate decisions (how well each decision problem is solved). Theorem 3 bounds ETE_T and shows that O(log⁡T)O(\log T) solver iterations per round keep the total regret at the O(T(1+d))O(\sqrt{T(1+d)}) rate. The revision introduces both decisions in words before the inequality.

Q3. Definition of RTenvR_T^{\mathrm{env}} (line 122). RTenvR_T^{\mathrm{env}} is the regret of our predictor sequence when every decision is solved exactly. It is the extra total loss compared with the single best fixed predictor chosen in hindsight. Write Ft(θ)=ℓt(wt⋆(θ),θ)F_t(\theta)=\ell_t(w_t^\star(\theta),\theta) for round tt's true loss when the predictor uses parameters θ\theta and the decision is solved exactly. Then

RTenv=∑t=1TFt(θt)−min⁡θ∈Ω∑t=1TFt(θ),R_T^{\mathrm{env}}=\sum_{t=1}^{T}F_t(\theta_t)-\min_{\theta\in\Omega}\sum_{t=1}^{T}F_t(\theta),

where Ω\Omega is the fixed set of parameter values over which the best predictor is chosen; it contains every parameter value the learner visits. Eq. 3 then reads: actual regret =RTenv+ET=R_T^{\mathrm{env}}+E_T, the learning part plus the execution gap from Q2. The revision displays this definition before Eq. 3.

Q4. "Stationary outcomes" (line 131). We meant that even when nothing in the world changes, so that a stored example's true costs stay exactly the same, that example's gradient still changes, because the predictor that determines its decision has changed. Staleness therefore arises from learning itself, not only from a changing environment. In Theorem 1, "stationary" has a precise meaning: every round has the same decision problem (ft=ff_t=f, ℓt=ℓ\ell_t=\ell). The revision replaces the phrase with these two sentences. Our response to Reviewer YPWM (Q1) describes how the analysis extends to changing problems.

AuthorsOpenReview ↗

Questions 5-6 addressed

Q5. Why solve the decision problem again (line 162)? Take one past example, say round ss's transport problem, whose true costs are now known. Its learning gradient follows the chain rule through the decision: (how the true cost changes with the plan) × (how the plan changes with the forecast) × (how the forecast changes with the parameters). The middle factor is evaluated at the plan the current predictor would choose for this example. When the predictor is updated, its forecast for the example changes, so that plan changes, and with it the gradient. Computing the exact current gradient therefore requires solving the example's decision problem again with the new forecast; this is full re-evaluation. Frozen transport avoids the extra solve by keeping the plan and adjoint from the arrival round and updating only the parts that depend directly on the parameters. The plan that was executed in round ss is never changed.

Q6. Why an LQR proxy (line 339)? The experiment's purpose is to test Proposition 2: how the largest stable learning rate of the analyzed algorithm (frozen IGT with plain gradient steps) shrinks as delay grows. That test is meaningful only if (a) every forecast leads to a well-defined decision, (b) the decision problem satisfies the theorem's assumptions, and (c) any instability we observe comes from the learning update and not from the system being controlled.

Our problem keeps LQR's structure. The predictor learns the system matrices (A^,B^)(\hat A,\hat B) of a 10-state, 3-input linear system (130 parameters). The decision is a linear feedback gain KK, chosen to minimize a quadratic cost in the state and the control. The cost is scored with the true matrices. It differs from full LQR in one respect: the gain minimizes the one-step cost tr⁡[(A^−B^K)⊤Q(A^−B^K)+K⊤RK]\operatorname{tr}\bigl[(\hat A-\hat BK)^\top Q(\hat A-\hat BK)+K^\top RK\bigr] instead of the infinite-horizon cost. That is what makes it a proxy, and that choice is what satisfies (a)–(c).

The one-step problem has curvature at least 2R=0.2 I2R=0.2\,I for every forecast, so the optimal gain always exists, is unique, and has an exact adjoint. The infinite-horizon problem satisfies none of (a)–(c):

  • its optimal gain exists only when the forecast (A^,B^)(\hat A,\hat B) is stabilizable;
  • its cost is nonconvex in the gain (Fazel et al., 2018), so the strongly convex decision problem the theorem assumes cannot hold;
  • the decision would require an iterative Riccati solve;
  • a blow-up could come from an unstable closed loop rather than from the learning rate, so the two kinds of instability would be confounded.

With the infinite-horizon problem, the experiment would therefore no longer test the theorem. With the one-step problem it does: the measured stable-rate boundary shrinks with delay at a log–log slope of −0.962, against Proposition 2's prediction of −1. The revision renames the experiment "delayed quadratic-control learning" and states this rationale before the results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.