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

• URL: http://arxiv.org/abs/2605.12693v1
• Date: Tue, 12 May 2026 19:43:49 GMT
• Title: IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback
• Abstract summary: Decision-focused learning trains models end-to-end against downstream decision loss, but online settings suffer delayed feedback.<n>We identify emphstaleness amplification, a failure mode unique to bilevel optimization under delay.<n>We prove that any black-box delayed gradient incurs an irreducible regret cost from inner-solver approximation error.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decision-focused learning trains predictive models end-to-end against downstream decision loss, but online settings suffer delayed feedback: outcomes may not arrive for many environment interactions. We identify \emph{staleness amplification}, a failure mode unique to bilevel optimization under delay, in which gradient staleness couples with inner-solver sensitivity to inflate regret beyond single-level delay theory. We prove that any black-box delayed optimizer incurs an irreducible regret cost from inner-solver approximation error, and that gradient staleness contributes a quadratically growing transport error without bilevel-aware correction. Our algorithm, \textbf{IGT-OMD}, applies Implicit Gradient Transport to hypergradients within Online Mirror Descent, re-evaluating stale gradients at the current parameters using stored inner solutions. This method reduces transport error from a quadratic to a linear dependence on delay and achieves the first sublinear regret bound for delayed bilevel optimization with queue-length-adaptive step sizes. Controlled experiments provide a \emph{mechanistic fingerprint}: transport benefit is exactly $0.0\%$ ($p=1.00$) at unit delay and grows monotonically to $9.5\%$ at fifty rounds ($p<0.001$), isolating the correction's effect. On Linear Quadratic Regulator, Warcraft shortest-path, and Sinkhorn optimal transport, IGT-OMD reduces decision loss by $17$--$55\%$ relative to single-level baselines, with phase transitions matching the theory.

Related papers

• Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
  We study delayed online convex optimization (OCO) under a hard capacity constraint.<n>We find that for first-order feedback, capacity $C = (log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors.<n>For bandit feedback, the regret rates are modulated by powers of $(1 + _textmax/C)$, where $_textmax$ is the maximum number of pending observations at any time.
  arXiv  Detail & Related papers  (2026-06-10T06:37:06Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Decision-Focused Learning via Tangent-Space Projection of Prediction Error [32.655683009031804]
  Decision-Focused Learning (DFL) trains predictors to improve downstream decision quality.<n>We show that, under standard regularity with locally stable active constraints, the regret gradient admits a closed-form geometric characterization.<n>We propose PEAR, which computes regret gradients via a reduced linear system over active constraints.
  arXiv  Detail & Related papers  (2026-05-02T10:10:16Z)
• CurvZO: Adaptive Curvature-Guided Sparse Zeroth-Order Optimization for Efficient LLM Fine-Tuning [15.930478833291827]
  Fine-tuning large language models (LLMs) with backpropagation achieves high performance but incurs substantial memory overhead.<n>We propose CurvZO, which tracks curvature signals online from scalar ZO feedback.<n>We show that CurvZO consistently improves fine-tuning performance and reduces training time over ZO baselines.
  arXiv  Detail & Related papers  (2026-03-23T09:13:45Z)
• $\ abla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• Minimizing Surrogate Losses for Decision-Focused Learning using Differentiable Optimization [7.597423277859608]
  Decision-focused learning (DFL) trains a machine learning (ML) model to predict parameters of an optimization problem.<n> Gradient-based DFL requires computing the derivative of the solution to the optimization problem with respect to the predicted parameters.<n>For many optimization problems, such as linear programs (LPs), the gradient of the regret with respect to the predicted parameters is zero almost everywhere.
  arXiv  Detail & Related papers  (2025-08-15T09:59:56Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  We investigate the problem of online convex optimization with unknown delays. We first extend the delayed variant of OGD for strongly convex functions. We establish a better regret bound of $O(dlog T)$, where $d$ is the maximum delay.
  arXiv  Detail & Related papers  (2021-03-21T10:16:15Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.