Online Decision-Focused Learning
Authors: Aymeric Capitaine
Maxime Haddouche
Eric Moulines
Michael I. Jordan
Etienne Boursier
Alain Oliviero Durmus
Venue: ICLR 2026 Poster (2026)
Keywords: decision-focused learning
integrated estimaton optimization
predict-then-optimize
online learning
Primary area: optimization

Abstract: Decision-focused learning (DFL) is an increasingly popular paradigm for training predictive models whose outputs are used in decision-making tasks. Instead of merely optimizing for predictive accuracy, DFL trains models to directly minimize the loss associated with downstream decisions. However, existing studies focus solely on scenarios where a fixed batch of data is available and the objective function does not change over time. We instead investigate DFL in dynamic environments where the objective function and data distribution evolve over time. This setting is challenging for online learning because the objective function  has zero or undefined gradients, which prevents the use of standard first-order optimization methods, and is generally non-convex. To address these difficulties, we (i) regularize the objective to make it differentiable and (ii) use perturbation techniques along with a near-optimal oracle to overcome non-convexity. Combining those techniques yields two original online algorithms tailored for DFL, for which we establish respectively static and dynamic regret bounds. These are the first provable guarantees for the online decision-focused problem. Finally, we showcase the effectiveness of our algorithms on a knapsack experiment, where they outperform two standard benchmarks.

Published as a conference paper at ICLR 2026
ONLINE DECISION-FOCUSE LEARNING
Aymeric Capitaine*
Maxime Haddouche
Eric Moulines 1
Michael I. Jordan S
Etienne Boursier 1
Alain Durmus'
ABSTRACT
Decision-focused learning (DFL) is an increasingly popular paradigm for train- ing predictive models whose outputs are used in decision-making tasks. Instead of merely optimizing for predictive accuracy, DFL trains models to directly min- imize the loss associated with downstream decisions. However, existing studies focus solely on scenarios where a fixed batch of data is available and the objective function does not change over time. We instead investigate DFL in dynamic envi- ronments where the objective function and data distribution evolve over time. This setting challenging for online learning because the objective function has zero undefined gradients, which prevents the use of standard first-order optimization methods, and is generally non-convex. To address these difficulties, we (i) regu- larize the objective to make it differentiable and (ii) use perturbation techniques along with a near-optimal oracle to overcome non-convexity. Combining those techniques yields two original online algorithms tailored for DFL., for which we establish respectively static and dynamic regret bounds. These are the first prov- able guarantees for the online decision-focused problem. Finally, showease the effectiveness of our algorithms on a knapsack experiment, where they outperform two standard benchmarks.
INTRODUCTION.
Many real-world decision problems involve uncertainty, which is commonly handled through the pedict-then-optimiie framework (Bertsimas and Kallus, 2020). First, a prediction model trained on historical data; then, its output is fed into an optimization problem to guide decision-making This natural strategy has been successfully applied in many operation research (OR) problems, ranging from supply chain management (Acimovic and Graves, 2015; Fisher al., 2016; Ban and Rudin, 2019; Bertsimas and Kallus, 2020), revenue management (Farias et al., 2013; Ferreira et al., 2016; Cohen et al., 2017: Chen al., 2022) to healthcare operation (Bertsimas et al., 2013; Aswani al., 2019; Gupta et al., 2020; Rath et al., 2017), see Mivsić and Perakis (2020) for an extensive review. It clear that this approach would yield optimal decisions the predictions were perfectly accurate. However, in practice, prediction errors are inevitable, and even small inaccuracies can propagate through the optimization process, potentially leading to poor decisions.
To address this limitation, approach known as decisson--ocusee learning (Mandi et al., 2024), also referred to as smart predict-then-opimiic (Elmachtoub and Grigas, 2022) or integrated learning- optimization (Sadana et al., 2025), has emerged. Instead of optimizing for prediction accuracy alone, this method trains the predictive model to directly minimize the downstream decision loss. By aligning the learning objective with the decision-making goal, it produces models that are more robust to prediction errors in practical applications. While decision-focusee learning yields strong empirical performance (Donti et al., 2017: Verma al., 2022: 2023; Wang et al., 2023), theoretical development has so far been limited to the batch setting, where models are trained on pre-collected,
"Centre de Mathématiques Appliquées CNRS, École Polytechnique, Paris, France I INRIA CNRS, Ecole Normale Supérieure, PSL Research University, France *PPITA. Laboratoire de Recherche de EPEPITA Mohamed Bin Zayed University of AI, Paris, France 6 Inria Paris, Ecole Normale Superieure PSL, UC Berkeley, Paris, France
Inria Saclay, Université Paris Saclay, LMO, Orsay, France

---

Published as a conference paper at ICLR 2026
independently and identically distributed (i.idd)) data (Wilder et al., 2019; Mandi et al., 2022; Shah et al., 2022: Schutte et al., 2024). This assumption breaks down in many real-world scenarios in- volving dynamic environments (Cheung et al., 2019; Padakandla et al., 2020) and shifting data distributions (Lu et al., 2018; Quinonero-Candela et al., 2022).
Online learning Dess-BBincchi and Lugosi, 2006; Hazan, 2023) provides a general way to cope with such non-stationarity of data-generating processes. This framework considers a learner who makes decisions sequentially, at each round leveraging data collected from previous rounds inform its next decision. Crucially, the objective function is allowed to vary over time, either in a stochastic or adversarial way. This provides a natural framework for the work that we present here, which extends decision-focusee learning beyond the i.i.d., batch setting.
Contributions. We develop theoretical foundation for online decision-focused learning, en- abling its application in non-stationary settings. This presents a significant technical challenge, as the inherent difficulties of decision-focused learning, such the non-differentiabiiiiy of the ob- jective function or the lack of convexity of the losses due to the bi-level nature of the problem, compound those already present in online learning. Our contributions are as follows:
(i) We formalize the online decision-focusee learning problem by assuming that at each round, decision-maker seeks to solve a linear optimization problem over a polytope but does not have access to the true cost function. Thus the decision-maker has to predict the cost using whatever partial information that it has at hand. The cost function is then revealed, and the decision-maker updates its model in a recision-focusee fashion. This results in a bi-level optimization problem, where the inner problem consists in making a decision and the outer problem involves optimizing the resulting decision cost.
(ii) We present two algorithms tackle this problem, Decision-Focused Seflow-thh-Perturbeer Leader (DF-FTPL) and Decision-Focused Online Gradient Descent (DF-OGD). While both rely on regularizing the inner problem to make the resulting decision differentiable, they differ on the way they update the parameters of the prediction model. DF-FTPL uses the FTPL approach (Hutter and Poland, 2005), and DF- leverages a variant of Online Gradient Descent (Zinkevich, 2003). We establish sublinear convergence guarantees for both procedures, in the form of a static regret bound for the former and a dynamic regret bound for the latter. To our knowledge, these are the first provable guarantees for the online decision-focused learning problem.
(ii) Finally, we assess the performance of our algorithms on a knapsack experiment inspired by Mandi et al. (2024). Our simulations demonstrate that our approach outperforms the online version of two popular baselines, namely prediction-fouueed learning and -reeict-then--Optiiee in both static and dynamic environments.
Additional related work. Several decision-focused approaches have been proposed in the batch setting, among which differentiating the associated KKT conditions Gould et al. (2016); Amos and Kolter (2017); Donti et al. (2017); Wilder et al. (2019); Mandi and Guns (2020), smoothing via ran- dom perturbation Berthet et al. (2020), building surrogate losses via duality Elmachtoub and Grigas (2022) or directional gradients Huang and Gupta (2024) and relying on pairwise ranking techniques Mandi et al. (2022), see Mandi et al. (2024); Sadana et al. (2025) for additional references. However, the extension of fecision-focused learning the online setting remains unexplored. While several recent studies address online bi-le optimization Shen et al. (2023); Tarzanagh et al. (2024); Lin al. (2023), none of them are applicable to decision-focused learning as they rely on restrictive smoothness assumptions, that are incompatible with the structure of decision-focure In particular, the fecision-focusee objective is typically non-convex and features gradients that are either zero or undefined, owing to its underlying linear structure.
problems.
This motivates the use of different online methods, specifically tailored to address these problems. On the one hand, lack of differentiability is usually tackled through zero-th order methods Héliou et al. (2020); Frezat et al. (2023), sub-gradient Duchi et al. (2011), proximal Dixit et al. (2019) or smoothing approaches Abernethy et al. (2014). On the other hand, methods to address non- convexity in online learning often rely on the existence of a near optimal oracle Kalai and Vempala (2005); Agarwal et al. (2019); Suggala and Netrapalli (2020); Xu and Zhang (2024) or additional smoothness conditions Lesage-Landry et al. (2020); Ghai et al. (2022). All those results are derived for static regret (Zinkevich, 2003) which compares the learned predictors the best static strategy
2

---

Published as a conference paper at ICLR 2026
and is defined in Section 2. A more challenging criterion, also described in Section is dynamic regret, introduced Zinkevich (2003) and later developed in Hall and Willett (2013); Besbes et al. (2015); Zhao et al.; Zhao and Zhang (2021) among others, which takes into account the evolution of the environment. An alternative approach to obtain guarantees in the online non-convex setting is to weaken static regret local regret Hazan al. (2017); Aydore al. (2019); Zhuang et al. (2020); Hallak et al. (2021), which is the sum of the objective gradient norms evaluated in the iterates over time. Minimizing local regret corresponds encouraging convergence toward stationary points. However as we shall see, this approach is not sensible in our framework, as objective gradients are either zero or undefined.
Outline. In Section 2, we introduce the online decision-focused problem, our notions of regret and our assumptions. In Section we present the DF-FTPL and DF-OGD algorithms, before deriving bounds on the static regret of the former and the dynamic regret of the latter. Finally, we present our experiment in Section
Notation. For differentiable map y RR + Y such that Y C R. Vy((x) denotes the gradient of o at E TR. and (2)(() denotes the Hessian yo. In the case where y C Rd V denotes the Jacobian of p.. For two vectors (v, w) Ed Rd V i means that 2 w; for any i E [d]. and (u, w) v'u refers to the standard Euclidian inner product. Also, ||||| (v, is the standard euclidian norm. Given compact convex set θ Rdd IT denotes the orthogonal projection O. For a matrix M E Rmxd -|IM llop refers to its -'-oopertoor norm. In the case d = m, Amia (M) refers to its lowest real eigenvalue and Amax (M) it largest real eigenvalue. For (I. E RR, means that there exists E I= such that x = Ag.
FRAMEWORK
Sequential decision-making. ods, defined for any E [T] as
We consider an online decision-making problem over T peri-
min (X,,, w) WEW
(1)
where W = (en (K) ) is a bounded convex polytope of Rd with non-empty interior and vertices {r: 1=1- This feasible set appears naturally in many problems such shortest-path (Gallo and Pallottino, 1988), portfolio selection (Li and Hoi, 2014) or mixed strategy design in games (Syrgkanis al., 2015). In (I), Xx are random covariates and Ø. X' + 12d is a deterministic cost function, which satisfies for instance ge (X,) = BiZ, Xx]] for some hidden state Z, E Rd At each period f, nature picks both a distribution for X, and a cost function gt. This situation corresponds to the stochastic adversary setting (Rakhlin et al., 201 I). Importantly, X, is revealed at the beginning of the round, but not (X,)) which only available at the end of the round. While ge (X,) unknown to the decision-maker at the decision time, they have access to family of models θ x X - Rd, parameterized by è C Rm to predict it. The general form of the decision- decision-making dynamics we consider can be described as follows: at each round E [T], for a horizon T N, given the current parameter 0,,
1. Nature picks a distribution for X, E X' and a cost function Dt X + Z.
2. The decision maker observes X, and compute its prediction as g(0, X)).
3. Then, they take an action minimizing the resulting predicted cost
Wt w (0s) argmin (9t,, w)
wEW
4. Finally, the decision-maker observes ğr (X,) and update 0 for the next round.
Formally, the decision-maker considers a joint process (0,, we we)ter starting from 02 E O and history Ho 0, and defined by the following recursion. At round E [T], the decision-maker takes the best action given the current estimate 8, and a new feature X, as in (2). Then, they observe Gr (X.) and update their history H, H,-1 ((Xe,,((Xe)) 0r, w (0.)).. Finally, they update their prediction parameter 0c+1 based on H, through an algorithm Alg, A central question for the decision-maker is then the choice of algorithms heelyy to fit their regression model, that is how to pick 02 θ for each /. [T].
3

---

Published as a conference paper at ICLR 2026
Online decision-focused learning. From online perspective, prediction:focused learning con- sists in selecting at each t E [T] an algorithm Alg, to estimate argmingee Re()), where R, is statistical risk based on the historical observations H4, typically chosen as the empirical risk Re(0) E (():(X)) (0, X))), for some loss function (e.g., cross-entropy or squared error).
Alternatively, we consider in this paper, the decision-focused tearning approach, which selects pa- rameters 0 E θ by directly minimizing the downstream objective instead of risk function. Specif- ically, the decision-maker chooses Alg, to solve argmingge (Gr ()), w (0)) where wi is defined in (2). From the previous formulation, we see that the decision-focused learning formulation corre- sponds to a bilevel optimization problem (Colson et al., 2007: Sinha et al., 2017: Ji et al., 2021).
We emphasize that no stationary assumptions are made on the process {- Go (x.)))))eee)))))))) (er)) In other words, the adversary may select any distribution for X₁ and any function gr (as long as H2 below satisfied). To fully accommodate this flexibility, we assess the optimality of (0r (8() with two notions of regret. Let
:::0 θ ~ (Xt,, wy (0))
denotes the loss incurred when taking an action based on the prediction parameter O, E O. Following Zinkevich (2003), we consider the notions of static and dynamic regret to measure the effectiveness of learning strategy {0r (et)r) which are respectively:
RG
Σ (c)),) inf Σ B() and 94 Σ F.(O.) TE[T]
inf Fe(O), Σ tE(T)
(4)
BEB (E(T]
BEE
EE[T]
where F A H (l) | 14-1). In our dynamic regret, the sequence of actions is compared against sequence of oracles, each minimizing the instantancous loss. Without taking the condi- tional expectation over H4-1, each comparator could overfit to the specific realization of X, result- ing in unrealistically strong benchmark. By considering the conditional expectation of the loss, we effectively regularize the dynamic comparators, making them meaningful competitors. Note that our static regret compare to the best fixed strategy, with respect to the averaged losses. This no- tion makes sense here as we aim to control those regrets in expectation over the randomness of the process.
We make the following mild regularity assumptions for the rest of the analysis.
HI. (i) θ C Rmm is a compact and convex set with diameter De < oc. ((i) for any E [T]. 0 ( X,) E RRmd is continuously differentiable almost surely and (Veg(B,X))ll < G < do
for any 0 E θ almost-surely. (ii) For any E [T]. (X.)l & Dz < co almost-surely.
It is common in online learning to assume boundedness of the parameter space, model gradient and prediction space (Boyd, 2004; Bishop and Nasrabadi, 2006). Note that in the well-specified setting, i.e., T: g(f,.-) -) for some 6;, these two former conditions automatically imply the latter. We emphasize however that we do not assume this realizability condition, contrast to most of the literature decision-focused learning (Bennouna et al., 2024).
Without further assumptions on the sequence of costs gr and models y, the problem can still be made arbitrarily hard. Therefore, we make an assumption coming from the classification (Mammen and Tsybakov, 1999; Tsybakov, 2004) and bandit literature (Zeevi and Goldenshluger, 2009; Perchet and Rigollet, 2013) about the margins of the cost function. Recall that we denote by { the vertices of W. We define for any x E X and i [K], u,(0, x) = (g(0, x), v.).
H2. There exist Co > 0 and 3 E (0, 1). such that almost surely for any E [T], 0 E O and E [0, 1).
P
inf (+1(0)
(0, (0, > (H6-1)
> 1 - 1-C0
where (,))) E argmin u. (0, Xt).
H2 controls how difficult it is to solve problem (2) since it determines the objective gap between the optimal vertex (1,(0) E W and the other vertices. In other words, it quantifies how identifiable is the optimal vertex, 5 = 0 meaning it is not distinguishable from the others. If it is satisfied for 8 > 1, then it is automatically satisfied for / 1 thus we do not loose any generality restraining 3 to [0, 1]. This assumption is critical in our analysis, as it allows bounding the expected distance between the actual optimal decision u (0) and the regularized approximation (0) introduced in (5) below.
4

---

Published as a conference paper at ICLR 2026
We expect H2 to hold in wide variety of classical statistical settings. For example, in Appendix A we show that it is satisfied when : (6, X) + X where X has i.id standard Gaussian columns.
ONLINE ALGORITHMS FOR DECISION-FOCUSER LEARNING.
On the need of regularization to get differentiation. From an online learning perspective, a nat- ural approach to minimize the two regrets defined in (4) would be to update 8,+1 at each round t through an algorithm Alg, being either a variant of either the Follow-The-Leadee algorithm (FTI,, Kalai and Vempala, 2005) or Online Gradient Descent (OGD, Zinkevich, 2003), applied to the objec- tive function ft defined in (3). However, these algorithms are designed for single-level optimization problems and require access to (sub-)gradients of the objective. In our setting, this requirement is problematic because the function ft does not admit an informative gradient: by construction, computing the gradient of fi involves differentiating the mapping 9 + W (0), which is generally not buub-)differentiabl.. Indeed, Wi minimizes a linear function over the convex polytope W, thus 0 w (0) ranges in the finite set of vertices (uI,..., UK).
To address this issue, following Wilder et al. (2019), we propose to add a regularizer R to the objective function in (2). Accordingly, we define for any 0 @ and some ar > 0
w (0) E argmin (g(0, Xt). w) + a;R(w))
(5)
wEW
which is regularized approximation of wi- When this surrogate is continuously differentiable, which is the case for our choices of in Section 3, we can use (0) in our algorithmic routine. This approach amounts to minimizing the surrogate
f (x,( (0))
instead of Jt, which admits gradients of the form v.: = (0) Note that there is natural trade-off in the choice of the regularization parameter ox On the one hand, choosing a large ar makes the function (0) smoother. On the other hand, the larger a is. the more w; deviates from the true function wo that we aim to approximate. As we will see later, it is possible to balance these two extremes by carefully tuning the parameter Ozz.
On the choice of regularization on a general polytope. In what follows, we write W as the intersection of n spaces, that W == (w E Rd A-w- 0} where n >> is the number of faces, A E Rdxn and E TR... We assume that W is not degenerated, i.e. AAT E Idddd is full-rank.
remains to determine what regularizer to choose in (6). We recall that our aim is to obtain a w; (0) in (5) which is differentiable for any 0 E O. A possible strategy is to choose R so w, remains in the strict interior of W. In this case, (0) is differentiable a neighborhood of any E and admits close-form Jacobian V (f) by the implicit function theorem. A natural choice force
i to remains in the interior of W is the corresponding log- barrier function
R : w.wn H Σ In(b; - A]w),
where A, E IRd is the i-th column of A. With this choice of regularization, we show in Lemma that VW, has explicit formulation, allowing its use in practice.
Remark 1. We remark that in the special case where W = {w E Rdd : simplex TR', an alternative choice for R in (5) is the negative entropy Ro w w w, In(w:). In this case, w)) in (5) reduces to the softmax mapping, which is differentiable and admits a close- form Jacobian. In Appendix C, we theoretically study the performances of our algorithms in this special case.
w 1' 13 is the
Approximate oracles to handle non-convexity. The bi-level structure of the problem yields un- expected properties. particular, even when the regularizer R strongly-conve in (26), which the case with both log- barriers and negative entropy, and the model g is simple (such g(, X) = XO), fe 0 + (wx, (xx.) is lipschitz (see Lemmas and 5) but not convex in general. This pre- vents us from directly using known online convex optimization algorithms (Hazan, 2023). How- ever, recent line of research (Agarwal et al., 2019; Suggala and Netrapalli, 2020; Xu and Zhang.
5

---

Published as a conference paper at ICLR 2026
2024) has developed online algorithms in the non-convex case, provided the losses Lipschitz- continuous. These studies combine near-optimal oracles with perturbation techniques to establish sublinear bounds on the expected regret. In line with this literature, also assume to have access to an approximate offline optimization oracle, a notion that appeared a slightly modified form in Suggala and Netrapalli (2020).
Definition 1. An E-approximate offline optimization oracle (or approximate oracle), adapted to class is a mapping Oş taking a function such that f + E. and outputiing Oç(f) e è satisfying:
f(0)
< inf f(0) +
(8)
BEB
This notion of an approximate oracle reflects the fact that, in non-convex settings, we cannot rely on subroutines that provably find global minimizer of ft time (as is possible in convex problems with offline gradient descent). Instead, we must be content with local minimizers. Their quality is measured by a parameter Ç. which becomes small in favorable loss landscapes. When contains differentiable and Lipschitz functions, the stochastic gradient descent (SGD) algorithm can be used for the oracle Og. Indeed, a large body work has shown that, even with models as complicated as deep neural networks, SGD converge to local minimizers (Ghadimi and Lan, 2013; Mertikopou- los et al., 2020; Patel and Zhang, 2021; Cutkosky et al., 2023), justifying its use as an approximate oracle. A more detailed discussion is provided in Appendix B.
We conclude this remark by mentioning that is possible to conduct a non-convex analy- sis without an approximate oracle by considering the weaker notion of local regret defined as Exerry [ see (Hazan et al., 2017; Aydore et al., 2019; Zhuang et al., 2020; Hallak et al., 2021). However, such a definition is not meaningful in the DFL. framework, where gradients are zero undefined due the structure of the problem.
The combined use of approximate oracles and regularization allows us to derive original online algorithms. In Section 3.1, focus on a variant of the FTL algorithm, enjoying a static regret bound, while in Section 3.2 we propose a version of OGD enjoying a dynamic regret bound, both results holding the non-convex case.
3.1 STATIC REGRET: DECISION- FOLLOW THE PERTURBED LEADER
Our first algorithm is displayed in Algorithm 1, where Exp(n) refers to exponential distribution with parameter 7/ > 0. is inspired from the classic Follow-the-Leadee approach (Kalai and Vem- pala, 2005), which consists in making decision minimizing the sum of objective functions observed so far. When losses are non-convex, it is common to inject random noise at each step to regularize (Hutter and
the total cost function, resulting in an approach known as Follow-the- Lane--ertureed-Leaaa Poland, 2005; Suggala and Netrapalli, 2020). We employ this strategy as Alg, to update 0,+1 in Algorithm 1. Note that the oracle in line 6 of Algorithm crucially works with the regularized losses fi...., fr. This allows to use in practice gradient- bassed methods to obtain approximate minimizer as per our discussion in Section 3, since these surrogate losses are differentiable and Lipschitz.
Algorithm Decision-Focusee Follow The Perturbed Leader DF-FTPL
1: Input: horizon 7' > 0, initialization 0 E O, E-pprrxximate oracle Og and history Ho 0.
2: for each č {l, .., 2' do
3: Observe X, E X' and play wi (0:) = argmmn,wew (o Xi), w)
4: Observe (x, Z and update the history H4-
5: Draw E Rd such that for all j E [d]. the j-th component Jj. Exp(n).
6: Update
4 Og
Σ (o):))
7: end for
Note that in line 3, the algorithm takes the best action wi (0.) given the predicted cost g(0,, X,) (the regularized action ūy only needed to compute Ī.). In most practical settings, wr can be computed

---

Published as a conference paper at ICLR 2026
efficiently with standard numerical solvers. However, show in Appendix F that only being able to determine w, (0,) E W such that (g( w, ((t)) (g) wt (0:) < k for some k >> only shifts the regret bounds of the next section by
We provide a theoretical guarantce on the convergence of Algorithm 1 with the following static regret bound.
Theorem Assume H1, H2 and having access to an É-approximate oracle Og adapted to EE fs (or, 4) HE(T. Let {6s hEET) be the output of DF-FTPL (Algorithm 1) instantiated with learning step rj > O and regularization coefficients at a > 0oror any Then:
m.D + +
TERR mm
a nf
where E denotes the expectation both data and the intrinsic randomness of DF-FTPL and Ö contains polynomial dependency in In(1/a) (InLa) In(In(d))
Furthermore, taking y ix i m///17-3/44 -1 11/2 and a xx ,1//-,1//27-11/ yields:
T E mm33/1 3/22 ,,7
The proof of Theorem 1 can be found in Appendix G.2. In particular, Theorem 1 shows that DF-FTPL enjoys an average regret bound decaying in T-1/4 long as O(T-1/44. While it features a polynomial dependency m²/2 on the dimension of O, it only depends the dimension of the decision space W through a In In(d) term. This makes Algorithm a particularly competitive approach when the decision space is of high dimension.
It is informative to compare our guarantee to existing bounds in the literature. Suggala and Ne- trapalli (2020), who also study non-convex online learning, achieves a rate of O(T-1/2) as long as their offline oracle satisfies & = O/3") at the cost degraded m/ dependency on the dimension. Their faster rate in T comes from the fact that they tackle simpler, single-level prob- lem as compared to our bi-level, non differentiable setting. Indeed, we need to regularize the inner problem overcome non-differentiabiliyy as discussed in Section 3. This introduces an additional trade-off on the regularization strength on top of the usual trade-off in the learning rate 7), which reflected our rate.
3.2 DECISION-FOCUSED ONLINE GRADIENT DESCENT
While DF-FTPL (Algorithm 1) benefits from a converging static regret bound, the techniques in- volved in Suggala and Netrapalli (2020) are not enough to reach dynamic regret guarantees, which is particularly relevant in highly non-stationary environments where the optimal decisions may change significantly from one round to another. To this end, we go beyond the sellowtthe-Ladees approach and propose an original algorithm based on the celebrated Online Gradient Descent (Zinkevich, 2003). This procedure, which we call DF-OGD, is presented Algorithm 2.
In Algorithm 2, at each time & E [T], decision wi (0t) W is made based on the current parameter 0, O The feedback g. (X.) E Z is then observed and used define the surrogate objective ft- Then, near-minimizer of this objective is computed using the offline oracle from Definition 1. To address non-convexity, the gradient V Vwl(u.) is evaluated at point u, drawn uniformly random from [0,, 0.). Finally, the parameter is updated to ôt + 1 using the standard gradient step of OGD.
The main difference with Algorithm the update of 0c+1 through Alg, On the one hand, DF-FTPL invokes Og to minimize the cumulative loss observed so far and perturbs the entire objective func- tion. On the other hand, DF-OGD relies only on a mear-optimizer of the most recent regularized cost, 0, Og(f)) and perturbs the point at which the descent direction (gradient) evaluated.
Moreover, note that Algorithm 1 is instanciated with a single pair of parameters (a, 7) whereas Algorithm uses on sequence (ar. Ti [T()- This additional flexibility is crucial for the algorithm to adapt to the variation of the problem so as to maintain a low dynamic regret.
We provide a convergence guarantee for Algorithm 2 with the following dynamic regret bound. Theorem 2. Assume H1, H2, access to a ε-approximate oracle adapted (fibeetr) Let (0the(m) be the output of DF-OGD (Algorithm 2) instantiated with the non-increasing sequence (me))rry and
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 Decision-Focused Online Gradient Descent (DF-OGD)
1: Input: horizon T 0, initialization 01 e and history Hu 0.
2: for each t E fl..... } do
3: Observe X, X' and play wi (0:) argmin ((0,,, Xx), w))
4: Observe (x( E 2 and update the history Hi-
5: Get t) = Of(ft)
6: Draw 6, ~ Uni 1J). compute u, 02 6e(0: U1) and Ve(u)) "
7: Update 0.+1 ll nh v(()))
8: end for
regularization coefficients (ot) (ET)) Then:
T T D = δ
E
1+ Pr
1 T
Σ [E[T]
2 + naa
+
Tif
where Pr 1 - dell. E denotes the expectation on both data and the intrinsic random- ness of DF-OGD and O contains polynomial dependency in In(1/a), In(((d)).
Furthermore, assume
(1 + Pt))c21 is non-increasing almost surely with Pt.
Ez 1el11l Dzll. Then, using at 1/2- (1) and Nu x n 111122-3/411++ 3/+ P1)3//4 for
any t E [T] leads to:
T B = ( Pr) 1// 1/4 + +5)
Our dynamic regret bound naturally depends on Pr. which captures the problem's variability by measuring the cumulative distance between approximate minimizers over time. When & = O((1 + Pr))/4T-1/44 the average dynamic regret decreases at the rate O + Pr)1/AT-1//4) Notably, the bound is independent of the dimension of θ, and depends only mildly on the dimension of
W through a In (dd) factor. This constitutes a key strength of the optimistic strategy underlying DF-DGD, making particularly well-suited for high-dimensional settings.
is instructive compare our guarantee with those established in recent studies on dynamic regret. For instance, Zhang et al. (2018) derive O(T-1/2 /T(T- + 1)) bound. However, their setting is not directly comparable to ours, as they consider a simpler single-level problem with differentiable and convex objectives. In contrast,
framework involves non-convex, non-differentiable losses due the bi-level nature decision-focusee learning. More recently, Huang and Wang (2025) obtained a ((11 + p bound, where P : Ei= [|5e+1 felloo. Yet, this rate is achieved under substantially more favorable conditions: single-level problem with losses that are strongly convex or Lipschitz, an additional assumption of path involving the full landscapes of the fts. By comparison, our losses are neither Lipschitz (indeed, they may even be discontinuous due to the linearity of the lower-level problem) nor required to be stationary over time- the only restriction being H2 to hold. We view the ability of our algorithm to achieve efficient convergence despite these demanding conditions as core contribution of our work.
and more challenging
EXPERIMENTS
In this section, we compare the performances our algorithms DF-FTPL and DF-OGD to two impor- tant benchmarks, namely prediction-focused learning and SPO (Elmachtoub and Grigas, 2022).
Setting. Our experimental setup is inspired by the knapsack example from Mandi et al. (2024). More precisely, we consider decision maker who must pick each E [T' object 12 E V among K items denoted V {1, 21,,..... K} with respective costs (X) = (ūr, (X),... (X)) e [0, 1] depending on some covariates X E X. At the beginning of each period, the decision- maker only observe covariates X, X RRP and have their disposal parametric model g
8

---

Published as a conference paper at ICLR 2026
Ox [0. 1| to predict Gt- Given their current parameter 8, E θ they predict item costs as g(0;, (t)) Xe)..... 9K (fr, Xt)) and pick an item (0,) = argmin;e(1* Xx). This setting depicted in Figure for K' in Appendix After having made their decision, the decision-maker observes the true item costs Pr (Xx),, and update 0c+1 for the next round based this feedback. Note that this setting can directly be mapped in the simplex example of Remark I, since of (8&) argmin (w, g(8, Xe)). Wo being the simplex of R For this reason, instantiate our algorithms DF-OGD and DF-FTPL with the negative entropy regularizer, following Remark 1.
Synthetic data. We instantiate the previous problem with the following symthetic data. For any t E [T], we draw X, E TK KXP with correlated rows, and generate cost vector o (X,) E R as:
C. (x.)) = A sin ((2x,0)))
Ex
where A > 0, Et N(O, [x) is Gaussian noise and 07 E Rº is parameter which satisfies 07 1/20* + 1/2 where 4 ~ N(0, Ip) for some H E RP. This is a challenging data generating process, since (x,), = sin sin' ((2x;8;) -)) is non-stationary and highly non- non-linear, and features are correlated. Equation (9) is discussed more in detail in Appendix E. To predict e, from Xt, assume that the decision-maker has access to a class of linear predictors of the form (0, X) + XO.
Benchmarks. In this setting, we compare the performances of DF-FTPL (Algorithm 1) and DF-OGD (Algorithm 2) to two benchmarks. First, we implement Prediction-Focused Online Gra- dient Descent (PF-OGD). This strategy consists in training in an online manner the model at each timestep it minimizes the statistical loss fu (v, X() || x0I? irrespective of the down- stream decision problem. Then, decisions are greedily made based on the predictions of the model. This approach is formally described in Algorithm 3 in Appendix E. Second, compare gorithms to an online version of the Smart Pecdict-then-Opiimee approach from Elmachtoub and Grigas (2022). This algorithm introduces differentiable and con- vex loss which upper-bounds the actual decision-focuse loss. Given its effectiveness and versatility, it is considered as a very important benchmark the literature.
al- (online SPO, see Algorithm 4)
Results. In Figure 1, we plot on the left-hand panel the average cumulated cost + t- "E Ds.v. (X.) incurred by DF-OGD, DF-FTPL, PF-OGD and online SPO over runs of T = 5000 timesteps, well the associated 95% confidence intervals. On the right-hand panel, we plot the average Mean Square Error (MSE) resulting from the sequence of prediction parame- ters (0)) It appears that both DF-FTPL and DF-OGD outperform PF-OGD and online SPO from a decision point of view, while incurring a higher MSE. This is line with decision-focusee ap- proach, which cares about decision cost rather than statistical loss. This experiment shows that (i) DFL outperforms PFL when models are clearly mispecified and (ii) our algorithms also outperforms the celebrated online SPO. We also mention the presence of additional numerical experiments in
Average Cumulative Cost
Prediction Error (Smoothed)
DFDDGD Avy Cusl
DF-OGD Preciition
PR. Avg Cost
FFI, Prodiction Frii
Avg Cost (x110)
SPO fvgg Cost
Prediction Error
Avg Cost
MSE LODS
Prediction
2000
200
2003
400
2000
300
2004
200
Timestep
Timestep
Figure 1: Average cumulated cost (left) and prediction errors (right) of DF-OCD, PF-OCD, DF-FTPL and online SPO.
Appendix E, to study how model misspecification affects the relative performances of DFL and PFL.

---

Published as a conference paper at ICLR 2026
5 CONCLUSION.
Decision-focusele learning offers a promising way to integrate prediction into decision making. We extend its analysis from the batch the online setting, enabling non-stationary data and varying objectives. Our algorithms DF-FTPL and DF-OGD comes with provable guarantees, and empirically outperform prediction- focused learning and online SPO in our experiment.
We believe that this work can be extended in several ways. First, it is plausible that faster rates (c.g., T-1/2) could be obtained using more traditional online-learning techniques that bypass the bilevel framework, such as discretizing the parameter space and applying expert aggregation over the result- ing bins. However, such approaches would likely incur a prohibitive dependence on the parameter dimension m (e.g., exponential in m). Exploring this direction remains however an interesting av- enue in future work. Second, we believe that alternative smoothing techniques could be successfully employed, such Moreau- Yosida transform and proximal operators, adress the more challenging of general convex set W. Third, it would be valuable to investigate less adversarial environments, such as those involving i.i.d. data, to explore whether stronger theoretical guarantees could be ob- tained and whether novel algorithmic designs might emerge. Finally, implementing our method in more ambitious experimental settings would be of great interest from a practical perspective.
ACKNOWLEDGMENT
Funded by the European Union (ERC, Ocean, 101071601). M.H. is partially supported by the European Research Council Starting Grant DYNASTY 101039676. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency, Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
J. Abernethy, C. Lee, A. Sinha, and A. Tewari. Online linear optimization via smoothing, In Conference on learning theory, pages 807-823, PMLR, 2014.
Acimovic and Graves. Making better fulfillment decisions on the fly in an online retail environment. Manufacturing & Service Operations Management, 17(1):34-51, 2015.
N. Agarwal, A. Gonen, and E. Hazan. Learning in non-convex games with optimization oracle. In Conference on Learning Theory, pages 18-29, PMLR, 2019.
B. Amos and J. Z. Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International conference on machine learning, pages 135.145. PMLR, 2017.
A. Aswani, Z.J. M. Shen, and A. Siddiq. Data-driven incentive design in the medicare shared savings program. Operations Research, 67(4):1002-1026, 2019.
S. Aydore, T. Zhu, and D. P. Foster. Dynamic local regret for non-convex online forecasting. Ad- vances in neural information processing systems, 32, 2019.
G.-Y. Ban and C. Rudin. The big data newsvendor: Practical insights from machine learning. Op- erations Reseurch, 67(1):90-108, 2019.
O. Bennouna, J. Zhang. S. Amin, and A. Ozdaglar. Addressing misspecification in contextual opti- mization. arXiv preprint arXiv:2409 10479 2024.
Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach. Learning with differentiable pertubed optimizers. Advances in neural information processing systems, 33:9508-9519, 2020.
D. Bertsimas and N. Kallus. From predictive to prescriptive analytics. Management Science, 66(3): 1025-1044, 2020.
D. Bertsimas, V. F. Farias, and N. Trichakis. Fairness, efficiency, and flexibility in organ allocation for kidney transplantation. Operations Research, 61(1):73-87, 2013.
10

---

Published as a conference paper at ICLR 2026
O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations research, 63 (5):1277-124,, 2015.
C. M. Bishop and N. M. Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006.
S. Boyd. Convex optimization. Cambridge 2004.
N.
and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
X. Chen, Z. Owen, C. Pixton, and D. Simchi-Levi. A statistical learning approach to personalization in revenue management. Management Science, 68(3):1923-193)) 2022.
W. C. Cheung, D. Simchi-Levi, and R. Zhu. Learning to optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1087 PMLR, 2019.
M. C. Cohen, N.-H. Z. Leung, K. Panchamgam, G. Perakis, and A. Smith. The impact of linear optimization on promotion planning. Operations Research, 65(2):4464468, 2017.
B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of operations research, 153:235-256, 2007.
A. Cutkosky, H. Mehta, and F. Orabona. Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-conves Conversion. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, 2023.
O. de Oliveira. The implicit and the inverse function theorems: Easy proofs. Real Analysis Exchange, 39(1):207, 2014, ISSN 0147-1937. doi: 10. 1ee113//caalaaaeexc.......000 http: //tp://dx..r doi. orgoorg//// /0.1442////eaaaaaaeeccc 39. 1.007..
URL
R. Dixit, Bedi, Tripathi, and K. Rajawat. Online learning with inexact proximal online gradient descent algorithms. IEEE Transactions on Signal Processing, 67(55:1338-133 1352, 2019.
P. Donti, B. Amos, and Z. Kolter. Task-based end-to-end model learning in stochastic optimiza- tion. Advances in neural information processing systems, 30, 2017.
J. Duchi, F. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
A. N. Elmachtoub and P. Grigas. Smart "predict, then optimize". Management Science, 68(1):9-26. 2022.
V. F. Farias, S. Jagabathula, and D. Shah. A nonparametric approach to modeling choice with limited data. Management science, 59(2)3305-322, 2013.
K. Ferreira, B. H. A. Lee, and D. Simchi-Levi. Analytics for an online retailer: Demand fore- casting and price optimization. Manufacturing & service operations management, 18(1):69-88, 2016.
M. Fisher, C. K. Glaeser, and X. Su. Optimal retail location: Empirical methodology and application to practice. Available SSRN, 2016.
H. Frezat, R. Fablet, G. Balarac, and J. Sommer. Gradient-free online learning of subgrid-scabe dynamics with neural emulators. arXiv preprint arXiv:2310.1938 2023.
G. Gallo and S. Pallottino. Shortest path algorithms. Annals of operations research, 13(1):1-79, 1988.
S. Ghadimi and G. Lan. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. SIAM Optim., 2013.
U. Ghai, Z. Lu, and E. Hazan. Non- con-convex online learning via algorithmic equivalence. Advances in Neural Information Processing Systems, 35:22161-22172. 2022.

---

Published as a conference paper at ICLR 2026
S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differentiating param- eterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv:1607.05447, 2016.
V. Gupta, B. R. Han, S.-H. Kim, and H. Pack. Maximizing intervention effectiveness. Management Science, 66(12):5576-5598 2020.
E. Hall and R. Willett. Dynamical models and tracking regret in online convex programming. In International Conference Machine Learning. PMLR, 2013.
N. Hallak, P. Mertikopoulos, and V. Cevher. Regret minimization in stochastic non-convex learn- ing via mroximal-gradien approach. In International Conference on Machine Learning, pages 4008-4017. PMLR, 2021.
E. Hazan. Introduction to online convex optimization, 2023. URL https://arxiv.ot org //bs// 1909. 1909.05200 05207.
E. Hazan, K. Singh, and C. Zhang. Efficient regret minimization in non-convex games, In Interna- tional Conference on Machine Learning, pages 4433-1441. PMLR, 2017.
A. Héliou, P. Mertikopoulos, and Zhou. Gradient-fres online learning continuous games with delayed rewards. In International conference on machine learning, pages 1172-4181 PMLR, 2020.
Y. Hsieh, M. R. Jaghargh, K. se, and P. Mertikopoulos. Riemannian stochastic optimiza- tion methods avoid strict saddle points. In Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
C. Huang and K. Wang. A stability principle for learning under nonstationarity. Operations Re- search, 2025.
M. Huang and V. Gupta. Decision- learning with directional gradients. Advances in Neural Information Processing Systems, 37:79194-79220. 2024.
M. Hutter and J. Poland. Adaptive online prediction by following the perturbed leader. 2005.
K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882-4892. PMLR, 2021.
A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 7103) 2005.
A. Lesage-Landry, J. Taylor, and I. Shames. Second-order online nonconvex optimization. IEEE Transactions on Automatic Control, 66(10): 4872, 2020.
B. Li and S. C. Hoi. Online portfolio selection: A survey, ACM Computing Surveys (CSUR), 46(3): 1-36, 2014.
H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the Loss Landscape of Neural Nets. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, 2018.
S. Lin, D. Sow, K. Ji, Y. Liang, and N. Shroff. Non-convex bilevel optimization with time-varying objective functions. Advances in Neural Information Processing Systems, 11-29692-297119 2023.
Lu, A. Liu, F. Dong, F. Gu, Gama, and G. Zhang. Learning under concept drift: review. IEEE transactions on knowledge and data engineering, (1(12))2346-29 2363, 2018.
E. Mammen and A. B. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6): 1808-1829, 1999.
Mandi and T. Guns. Interior point solving for Ip-based prediction+ optimisation. Advances in Newral Information Processing Systems, 33:7272-7282, 2020.
12

---

Published as a conference paper at ICLR 2026
J. Mandi, V. Bucarey, M. M. K. Tchomba, and T. Guns. Decision-focused learning: Through the lens of learning to rank. In International conference on machine learning, pages 14935-14947. PMLR, 2022.
Mandi, J. Kotary, S. Berden, M. Mulamba, V. Bucarey, T. Guns, and F. Fioretto. Decision-focused learning: Foundations, state of the art, benchmark and future opportunities. Journal of Artificial Intelligence Research, 80:1623-1701, 1701, 2024.
Mertikopoulos, N. Hallak, A. Kavis, and Cevher. On the Almost Sure Convergence of Stochas- tic Gradient Descent in Non-Convex Problems. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
V. V. Mivsić and G. Perakis. Data analyties in operations management: review. Manufacturing & Service Operations Management, 22(1):158-169, 2020.
S. Padakandla, P. KJ, and S. Bhatnagar. Reinforcement learning algorithm for non-stationary envi- ronments. Applied Intelligence, 50(11):3500-366, 2020.
V. Patel and S. Zhang. Stochastic Gradient Descent on Nonconvex Functions with General Noise Models, 2021.
V. Perchet and P. Rigollet. The multi-armed bandit problem with covariates. 2013.
Quininero-Candell, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset shift in ma-
chine learning. Mit Press, 2022.
A. Rakhlin, K. Sridharan, and A. Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
S. Rath, K. Rajaram, and A. Mahajan. Integrated anesthesiologist and room scheduling for surgeries: Methodology and application. Operations Research, (5(6):1460-144 2017.
U. Sadana, A. Chenreddy, E. Delage, A. Forel, E. Frejinger, and T. Vidal. survey of contextual optimization methods for decision-making under uncertainty. European Journal of Operational Research, 320(2))271-288) 2025.
N. Schutte, K. Postek, and N. Yorke-Smith. Robust losses for decision-focused learning. In Pro- ceedings the Thirty-Third International Joint Conference Artificial Intelligence, pages 4868- 4875, 2024.
S. Shah, K. Wang, B. Wilder, A. Perrault, and M. Tambe. Decision-focused learning without decision-making: Learning locally optimized decision losses. Advances Neural Information Processing Systems, 35:1320-1333 1332, 2022.
L. Shen, N. Ho-Nguyen, and F. Kılmee-Karr Karzan. An online convex optimization-based framework for convex bilevel optimization. Mathematical Programming, 198())1519-11582 2023.
A. Sinha, P. Malo, and K. Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. JEEE transactions on evolutionary computation, 22(2):276-295, 2017.
A. S. Suggala and P. Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pages 845-861. PMLR, 2020.
V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015,
D. A. Tarzanagh, Nazari, Hou, I.. Shen, and Balzano. Online bilevel optimization: Re- gret analysis of online alternating gradient methods. In International Conference on Artificial Intelligence and Statistics, pages 2854-2862. PMLR, 2024.
A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
13

---

Published as a conference paper at ICLR 2026
S. Verma, A. Mate, K. Wang, A. Taneja, and M. Tambe. Case study: Applying decision focused learning in the real world. In Workshop on Trustworthy and Socially Responsible Machine Learn- ing, NeurlPS 2022, 2022.
S. Verma, A. Mate, K. Wang, N. Madhiwalla, A. Hegde, A. Taneja, and M. Tambe. Restless multi- armed bandits for maternal and child health: Results from decision-focused learning. In AAMAS, pages 1312-1320, 2023.
K. Wang, S. Verma, A. Mate, S. Shah, A. Taneja, N. Madhiwalla, A. Hegde, and M. Tambe. Scal- able decision-focused learning in restless multi-armed bandits with application to maternal and child health. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 12138 12146, 2023.
B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learn- ing for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 33, pages 1658-1665, 2019.
Z. Xu and L. Zhang. Online non-convex learning in dynamic environments. Advances in Neural Information Processing Systems, 177551930-51963 2024.
revisited. A. Zeevi and A. Goldenshluger. Woodroofe's ' one-armed bandit reviteee Annals of Applied Probability, 1964):1603-1633, 2009.
L. Zhang, S. Lu, and Z.-H. Zhou. Adaptive online learning in dynamic environments. Advances in neural information processing systems, 31, 2018
Zhao and L. Zhang. Improved analysis for dynamic regret of strongly convex and smooth func- tions. In Learning for Dynamics and Control, pages 48-59. PMLR, 2021.
P. Zhao, Y.-. Zhang, L. Zhang, and Z.-H. Zhou. Dynamic Regret of Convex and Smooth Functions. In Advances Neural Information Processing Systems. Curran Associates, Inc.
Z. Zhuang, Wang, K. Yu, and S. Lu. No-regret non-convex online meta-learning. In ICASSP 2020- 2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 3942-3946. IEEE, 2020.
M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, 2003.
14

---

Published as a conference paper at ICLR 2026
A
H2 IS SATISHIED IN THE GAUSSIAN LINEAR CASE.
In this section, we prove that H2 holds true when W is the simplex of R is a linear model and X has columns distributed according to a Gaussian distribution. In what follows, we denote by
X₁ Rd the j-th column of X.
Proposition 1. Assume that g (0, E O x & H X0 where θ = {0 E R. : ||0122 = 1} and
X (X1 Xm) E RRdx where Xj itd. N( 1). Then, H2 is true for any A E θ with
Co d(d 1) 2/T
and 3 =-1.
Proof. Let 0 E O In what follows, we denote = T(0) where T(0) is defined as in H2. Since W is the simplex Rd, My is the j-th vector of the canonical basis of Rd. For any & > 0 we have:
P inf (X0, 0z) - (x0,e)) & {
PP
(1) (X0, & o}
P(1(0,X - -v)) <
jfi
Σ
P(KO, - Xxy1 <))
(10)
Since for any j i., X;) N0(00 with density fj. we have:
P(K(,, x & <) = [ (x) dz = (2V5(10112) [ exp
x22
dx
4|101|
and since the integrand reaches its maximum in x O,
< <<(]T(012)
(11)
Then, plugging (11) in (10) and summing over all pairs (i,j) such that j * yields the desired result.
Note that the d2 factor in Co comes from the use of an union bound, and could be reduced with refined analysis.
B EXTENDED DISCUSSION ON THE RELEVANCE OF APPROXIMATE ORACLES.
The notion of approximate oracle reflects the fact that, in non-convex settings, cannot rely on subroutines that provably reach global minimizer of fc time (as offline gradient descent would in convex problems). Instead, we must settle for local minimizers, whose quality is governed by parameter Ç which vanishes in favorable loss landscapes.
As concrete example, consider O as the stochastic gradient descent (SGD) algorithm. Even in the context of deep networks, it is plausible that O converges to a local minimizer. Indeed, large body of work has analyzed SGD in non-convex settings, establishing convergence to stationary points either in expectation (Ghadimi and Lan, 2013) or almost surely (Mertikopoulos al., 2020; Patel and Zhang, 2021; Cutkosky et al., 2023). Such stationary points may correspond to local/global minima or saddle points.
Recent studies further show that SGD avoids saddle points. For instance, Mertikopoulos et al. (2020) proved that the trajectories of SGD almost surely avoid all strict saddle manifolds -ie., sets of critical points where the Hessian has at least negative eigenvalue. These manifolds include connected families of non-isolated saddle points, phenomenon common in the loss landscapes of overparametrized neural networks (Li et al., 2018).
15

---

Published as a conference paper at ICLR 2026
Beyond SGD, similar guarantees extend more general methods. In particular, the stochastic Rie- mannian Robbins-Monn method (a broad template encompassing various algorithms) has been shown to converge almost surely local or global minima (Hsich et al., 2023).
Finally, we highlight that, most practical industrial settings, solving the downstream optimization problem is typically far more computationally demanding than updating the prediction model. It therefore reasonable to assume that the oracle call represents only small fraction the overall computational cost.
C SUPPLEMENTARY RESULTS ON THE SIMPLEX.
We now provide convergence guarantees for Algorithms 1 and 2 when W is the simplex. To do so we choose another regularizer than done the main document.
C.1 ADDITIONAL FRAMEWORK
We focus on the case where W is the simplex of Rd. that is
Wo ww E Rd x O, 1
This setting encompasses various docision-making scenarios such as portfolio selection Li and Hoi (2014) or mixed strategy design in multiplayer games Syrgkanis al. (2015). In this case, we choose the negative entropy
Ru W +
wy In(w:),
1E[d
as the regularizer (5). The minimizer (0) Wo in (5) with R. Ro can easily shown be the softmax mapping, that is it satisfies for any i [d]:
exp(-a Xx))
(0) = Enelo exp(-a 9b (0, X,))
is clear from this expression that w. is differentiable, and that for any 0 e θ:
(w) = [diag] (0) (0000,
(12)
C.2 RESULTS
DF-FTPL
Proposition 2. Assume HI, H2 and having access to an ε-approximate optimization oracle Og adapted f (o..)) serri Fix W Wo. R Ro- Let (0threm be the output of
DF-FTPL (Algorithm 1) instantiated with learning step r and regularization coefficients a4, >>> for any I, Then:
T EERI < <Ō mmm²²
1 mD
+5+aan(d)
a² np
where denotes the expectation on both data and the intrinsic randomness of DF-FTPL and Ö contains polynomial dependency in In(1/a), (a1//),,nnnn(((()) (In(d))).
The proof of this result is postponed to Appendix G.4.
DF-OGD
Proposition 3. Assume HI, H2, and having access E-approximate optimization oracle Og
adapted to (e(r)
Fix W Wo. R Ro. Let (0, terme be the output of DF-OGD (Algorithm 2)
16

---

Published as a conference paper at ICLR 2026
instantiated with the non non-increasing sequence (ne)ett) and regularization coefficients (AI)
Then:
Da + DeL[[P]
25D=Grt
E p
Σ
1T
32T
1E(7]
+ 2Dz
Σ
aill+ + +
(1- (11-3) 3) (n In d))] +
te[2]
where Py = 11++1 -
The proof this result is postponed to Appendix G.5,
Note that the principal gain, compared to the general polytope case, is to avoid the dependency in the number of faces and enjoys a nice In(d) dependency in the dimension of the decision space.
D BACKGROUND ON THE FTPL ALGORITHM
Approximate Optimization Oracle. The recent work of Suggala and Netrapalli (2020) proposed an online algorithm for nonconvex losses (4))er/1 with static regret guarantees. They rely an approximate optimization oracle O which takes as input any function f, a d-dimensional vector and returns approximate minimizer of f (a..). An optimization oracle is called "(E.x ) approximate optimization oracle" it returns 4 E IC such that
((u") - (a, 1*) < inf [e(p) - (a, 14) + (E xllarl1) WEK.
(13)
We denote the output of such an optimization oracle by , 5x (). Note the notion
of oracle described in (13) is very close from the Definition 1 we made in Section on the expert sequence (DT) (in this case X as no a is involved).
Remark 2. Note that, in our work, made the choice fo x O. This stronger assumption is due to the will of having a unifying framework encompassing both the setup for DF-FIPL and DF-OGD.
Follow The Perturbed Leader. Given access to an (E, x >-approximate optimization oracle, Sug- gala and Netrapalli (2020) study the FTPL algorithm which is described by the following recursion. Starting from fi, at each time steps t, Pe E K is updated as follows:
1-1
A41 = Os,x
Σ
4 - (0..)
(14)
where 0, E R is random perturbation such that dzjj the j-th coordinate of o, is sampled from Exp(r), the exponential distribution with parameter r).
Following this update route, the addition of an exponential noise allowing to handle the non- convexity of the losses, they reach the following static regret bound.
Proposition 4 (Theorem of Suggala and Netrapalli (2020)). Let D be the diameter of K. Suppose that &, is L-Lipschitz w.r.t LI norm, for all E [T). For any fixed n, FTPL (Equation (14)) with access to a (E, x) -approxxmmate" optimization oracle satisfies the following static regret bound:
Σ 1=1
T
((a))) - inf Σ Eelm)) < <0
T
m(XT + D)
+ XmL).
T
1/T
where E denotes the expectation over T1 Or.
E ADDITIONAL EXPERIMENTAL MATERIAL
The motivating example from Mandi et al. (2024), In this paragraph, we recall the example that motivates our experiment. Mandi al. (2024) illustrates the interest of focused learning
17

---

Published as a conference paper at ICLR 2026
with simple problem where decision maker seeks to pick, between two objects, the with the lowest cost. Before picking an object, they do not know costs but have at their disposal a model to predict it. This situation is depicted in Figure 2. For instance, if the true cost Pr 1 Jt.k) is (+), any prediction ft = ( ft. x.) lying in the blue-shaded area, such as (+), induces the optimal decision et 1. As observed in Mandi et al. (2024), prediction-focuser approach one in this setting. This is because generating
may underperform compared to decision-focusee a prediction & that closely approximates the true value ui-in the sense of minimizing statistical loss does not necessarily ensure that 0e falls on the same side of the 45 line as For example, the prediction (x) is satisfactory from predictive point of view, but induces a sub-optimal action. On the contrary, one would expect the decision-focused approach to produce predictions that lie further away from (*) since does not minimize prediction error, but on the right side the 45 line; see for instance
(V) on Figure 2.
Value Item
%
Value Ttmm
Figure Figure from Mandi al. (2024).
Details the experimental setup. In this paragraph, provide detail about the exper- imental setup in Section 4 and perform additional numerical simulations. We start by explaining more precisely how the data used in our experiment are drawn. First, for any E [T]. X, e RK*p constructed as follows: (i) we generate Toeplitz covariance matrix
(pl (L.EEK for it: Σ LL". and (iii) generate matrix X, with standard Gaussian entries. Then, X, is defined as X, = LX,, This introduces correlation between features, which makes convergence harder for an online linear model. Second, we generate 0t e IRK as follows:
some p (0,1), 1), (ii) apply Cholesky decomposition to
G min(max((,, 0), 1) with & = Asn ((2x0)))
In the above equation, A is constant, or satisfies:
1 o
1 Se, where Se NoO, TR) and 0" PERK
07
and & ~ N(O, [x) is Gaussian noise. The fact that 0g varies throughout time and that the relation- ship between 8, and X, is highly linear makes learning hard for a linear model.
We now present the values used for the different parameters in our experiment. We consider K = items and p = 10 features. The horizon is DF-OGD and PF-OGD. The reported error bars are 95% Gaussian confidence intervals (from the CLT). In (9), A 45 and the correlation coefficient for X, p = 0.8. Our algorithms are instantiated with the following parameters. First, DF-OGD runs with (ax) and (mx) suggested by our theoretical analysis. The oracle from H2 is obtained through a SGD algorithm performing la = 10 steps at each iteration with learning rate set to no 0.01, while being initialized at 8,-1- On the other hand, PF-OGD runs with a learning rate = 10 determined by grid search. Our code is implemented with pytorch.
T' 5000. For each plot, run N 10 times
Benchmark algorithms.
18

---

Published as a conference paper at ICLR 2026
Algorithm 3 Prediction-Foousee Online Gradient Descent (PF-OGD).
1: Input: horizon T > 0. initialization 01 E e.
2: for each / E (I,..., , T do
3: Observe Xr, predict 6 g0,, X₂)
4: Play o7 (0t) = [[[] Ca,s observe (X,).
5: Update P = (fe - emso ( xx),, X,0,))
6: end for
Deviation from realizability. As argued in Section I, prediction-focused learning would be opti- mal the prediction model made no mistake, since in this case problem (2) would perfectly align would expect prediction-focuse
learning perform very well in the realizable setting, that is when for any t [7], there exists 9, E e such that (x())) = = X)). On the flip side, it is likely struggle in mispecified setting. This is in contrast with DF-OGD, whose theoretical performance analysis does not highlight any peculiar dependence on realizabil- ity. We therefore hypothetize that PFL should outperform DFL in the realizable case, and DFL should take the upper hand when the prediction model is highly mispecified. To test this hypothesis, run an alternative experiment where interpolate between the well-specified, linear case, and ill-specified, non-linear one. More precisely, for 7 E [0, 1]. we generate (X₂, o (7)) "eeTT as follows:
with (I). As a consequence,
(7) = =1 X), + sin ((2X;07)=)) +
In Figure 3, we make vary from 0 to 1. At each value, plot the average cumulated cost gap between DF-OGD and PF-OGD, averaged over runs with horizon T = 1000. This experiment provides empirical support to the previous conjecture, namely, DFL becomes competitive option when the prediction model is ill-specified.
0.00
Average Cost Gap
-0.02
-0.02
-013
Non linearity
Figure 3: Average cumulated cost gap PFL DFL function of 7.
Algorithm Online Smart Seafict-then-Optimmze Online Gradient Descent (Online SPO).
1: Input: horizon 0, initialization 01 E O.
2: for each t {1, ,1,,..,77 7'} do
3: Observe X₁, predict & = ((t,XX)).
4: Play of (0)) argmin, Eu, observe Ct.
5: Compute u² (&t) = argmin, eev ofv and ve()) argmin cv.
6: Define SPO+ surrogate: SSPO+ (SPO+ = 2cfu" (ot)
(2).
7: Update 0z-1 1Tg 02 VoESPO+ (+)): where the gradient is computed via chain rule
through é = (l,, Xt). 8: end for
19

---

Published as a conference paper at ICLR 2026
Average Cumulative Cost
Prediction on Froor (Smoothee)
(x100)
DF-OED 4og Gisd
CF-OGD Heddtor Enior
PTS Aug Text
Preducton Expr end
Mediciin
Timestep
Timesttep
Figure 4: Experiment results with 80 items.
Higher dimension problem. Finally, the following figure shows the performance of our algo- rithms in a higher dimension problem, with K 80 items. We that our algorithms still sig- nificantly beat the baselines, suggesting that they remain effective in moderately high dimension problems.
F REGRET BOUND WITH AN APPROXIMATE OPTIMAL SOLUTION.
In this section, show that when cannot access wi (0.) W but only w, (0.) E W such that (g(0, X2), w, (0,) (0)) & k for >> O, our regret bounds are only shifted by k. The following proof is for the general convex polytope case. The simplex case is established in the exact same way.
Proposition Assume the assumptions from Theorem and that each step, w (0,) E W is
replaced by (0.) E W which satisfies
(g(0, X,), w/ (0.)) < k
where K. > O. Then,
E E
D3g D&L Pr]
Σ tE(T]
1h
GDz sup weW 16 - Aw
+
2/fr
2
a,Amin (AA7)
+ 2Dz
Σ
2n max kE[K]
||
Co(I(aa, + (1 -1) In) (nr + k.
(E[T]
The proof Proposition 5 is deferred to Appendix G.6.
G PROOFS
G.1 PROOFS OF PRELIMINARY LEMMAS.
G.1.1 SIMPLEX
Lemma 1. Assume HI, W = Wo and R Ro- Then for any [T], ft is K,-Lipchitz almost surely, with K, = =DDzG(4o))
Proof. Let (0,0") 0¹) E 0 We have:
[((00) F((07 = (oc(X))) (() (()))
< (X.)) (
= =19x(X.)1 || (0 + 1(0' - 0))(( 0')ll
Dz /' 1| + t(0 00))l 110 0' (by HI-(i)
(15)
20

---

Published as a conference paper at ICLR 2026
Now, denoting ( = 0 + t(0' - 8), we have:
[Vūn(())lop = a, [I(diag[f (C) ui (() Xx)lllp
< a, ||diag| (() (i.( Mp Vog(S. Xa)llop
< "aa,"lldig (()( ((,()) 1l.p (by HI-(ii))
(16)
Since diag[ (ix (C) Th (()))(())))))))))))))))) (C) is symmetric, its operator norm equals its largest eigenvalue, denoted Amax It then follows that:
||diag |[diag((r(()) - wi ( Ammax(diagg Lo, (() (,(O),((()))
max KE
diag (1+ (C)) - (C))
jE
ih (1) wc(().))) (0)) Σ wr(S).
max KE[d]
5
4
where the two last inequalities hold because di E [0. 1].. Therefore, we obtain from (16) that
[[Vil(())lop < 5G(4a.) and plugging this in (15) yields:
5GD2 S
110 dt = 5GDz 2 110 - 0'|l
f ((0))-F100 F.(00) <
4at
4az
Lemma 2. Assume H2, W Wo and R Ro. Then for any 0 Q and t for for any 0 E 0
[l] ,0, (0)]l Hh-1] < or 2(0 Indd) Co min {In
( 0+ - ()) 3))
Proof. Let 0 O and [T]. Since W Wo. denoting for any E [d] ej the j-th element of
the canonical basis, we have (0, X2) = (0( Xz), We recall that we denote (1,(0) (0, X.) =
minsel4 u, (0,,.,),. We first prove the following lemma.
Lemma 3. Assume that there exists > such that (1, X.) + & (1) for any j
{1. K} \ (0)). Then,
20z In(d)
|| (8) (0) <
E
Proof. In this proof, (00) from H2 is denoted I, lighten notation. We have by assumption:
(0(0, Xi), (0)) = g(0, Xt).
wi (0)
ur. (0, Xc X.) (0) + Σ (0,
j+l.
us, (0. X₂ X (0) + (uz, (0, +E) Σ (0)
j+1,
= =w, (0, X, )r, (0) + (us, X,) + +1 T..,,
(17)
The last equality holds because [| (0)1l = 1. On the other hand, using the facts that Ro > 0,
ne (0) argm Xz), w) Ro and ur, X,) (0, X.), w (0)) yields:
(0 X,), (x(())
< (g), ū. + a, Ro (0) < (9(0, w/ (0)) Ra (w) (0)) u1, (1) + (o)(((
un, (0, + a, ln
(18)
21

---

Published as a conference paper at ICLR 2026
The last line holds because Ro(w) & In(e) for any Wo- Combining (17) and (18) gives:
"r, (0, 1,,, + (uz, + +) (iI,,,()) & ws, (0, + ar In(d).
Re-organizing the terms then yields Tr, (0) > or Infd) and again, as || = 1, we have: Ejar, (0) In(d)
Combining those inequalities yields:
2a, In(d)
(0) (0)l |ler, ū. (0)]1 1 - (0) + Σ
(0)
jFl
To conclude the proof, we first write the expected distance as follows:
B|llwř (0) wx (0)ll H4-1] P[[[w] (0) (0)l H
Since both w (0) and ky (0) belong to the simplex, we can restrict the integral to:
P([lw; (0) (.) y He-1) dy
(19)
P(Ilw) (0) - wi (0) > 174-1) dy
(20)
P([lw) (6) (1)112 > y 14-11 dy
2
< a+ +
(0) P([lw, - (0)1 > H4-1)
(21)
a
We now apply the change of variable y 20, In(d)=- to obtain: B[]lw; (0) (1))l H4-1
(2 In(d))
P [1) (.)( 2 a gllm(d)
de
oz + 20, (nd
HHe-
(22)
22
(a, In(d))
e
Moreover, for any & > 0 we have by H2 and Lemma that:
1 C x P
inf (0, - un, X.)) 2 H4-1
ltl
< P([lww ( & 20, In(d)= H1-1),
so it follows that:
[lw] (0) (0))l > 20 In(d)
H(-1) = 1 - Pe (1)) :.(()]l < 20 In(d)
Pr
He-1
< Co
(23)
Hence, plugging (23) in (22) gives:
E|]lwt (0) क; (f)ll1 He-1l aa + 2an In(d)Co (
e 3-2 de.
In(d)
We now proceed to bound v(3) = L 2l In(d)
3- 2 for 3 (0,1). With a = ar In(d) and b
2 In(d,, we have
((3) (1 3) 1aa 1 (1) (00--3(-(13)10 (1-3) (11-))
22

---

Published as a conference paper at ICLR 2026
Factoring out e () a²-1 yields
((3) = a (1 (1-) (1--)))) (1-5))
Since for any x E one has c & min(r, 1,, we obtain
= & 8 (1 3) min 3) In(b/a), 1] a= a min((m((/a)) 83) 3)
Substituting the values of a and finally gives
[ 04 (1 B)-1
(()) < (a, in (nd) min In
which concludes the proof.
G.1.2 GENERAL POLYTOPE
In this section, denote by W1 the general polytope described in ?? and R. the log-barrier regu- larization described in Equation (7).
Lemma 4. Assume HI, W = Wi and R = RR. Then for any t E (Th is differentiable and for any 0 O, (() = (o)((()..(.)) where:
Vo) = -a
Σ (be -10,((0))- Vog(O,
Proof. Let E R and t E [T]. With
he (w, (9(0, (i), w) R.Ri(w)
we have (w) + to0 as w + bdry(Wi)). Since /1 (0). that (0) E int(W,). It follows from the first order condition and the implicit function theorem (de Oliveira, 2014, Theorem 2) that W + we (0) is differentiable, and
(0),0) = ww, hy (w, 0), we deduce
Vw, (0) - (V he ④ (0), 0)) (e
V RR ( (0)) Vog
(24)
Since (w)
In(b, -in A,w), simple computations give:
R (0)) = Σ (b. 2 -4,47
(25)
Moreover, since rank(AA") = d by assumption, RR (w, is invertible. Plugging (25) in (24) gives the result.
Lemma 5. Assume HI and R = R2. For any t E [T], fi is Ky-Lipschitz almost-surely, with
GD2 sup sup 1 Awl.s
K,
ag
Amin (AA*)
Proof.
Let (0,0") @?. We proved in (15) that:
[.((0) f.(00) Dz
||Vw, -
- 0)) 1p0 1p) 0 dt.
1=0
Denoting Ç = 0 t(0' 0), by (24), since ||. ol is sub-multiplicative:
[[)o)(()) -a; (
-
( G (by HI-(ii))
23

---

Published as a conference paper at ICLR 2026
Moreover, have:
|
n Σ (be ATuoa(()) -2A)) 2A.A.
[[]
1lop
op
sup ||b Au |2 (AA')-1
weWi
Since AA" is symmetric. [|(AA)) of M. We therefore obtain by (15) and the previous inequalities that almost-surely:
II min (AA)) -1 where Amin ( is the lowest eigenvalue
< GDz suP |bb Awl
110-0111
Amin (AAT)
1=0
2D2 weP |bb Awll
10 0'l
a2
Amin (AA')
Lemma 6. Assume H2, W Wi and R R1. Then any E [T) and E O
2 (1 (1- (1-
(0) w/ (0)l, Hi-1] < az
2n max kE
|ull| anlar, In d) min In
Proof. Let 0 E θ and t [T]. (1).,.))).,, (0)) E [0, 1] such that
Since
Wi
(Kk) there exists
K (0) (0)e and Σ (0)
We recall that u, X() (g(0, 12) denotes the value of the objective function on the vertex
Vy E W. and ur, (0, X²) = minje[[] (0 X,) so U1, = wī((), (0). We start by proving the following lemma:
Lemma 7, If there exists > such that u1, + & Uj for any j E (1....,KK) K} \ {4., then,
2nay
||w| (0) 2z (0) <
max
le
kE[K]
Proof. On the one hand, wh (0) is by definition the solution to the problem:
T (0) argmin Xi),, w) - at Σ In(b, - A(w).
(26)
wEW
which is uniquely determined by strong convexity of the objective. We know by (Boyd, 2004, page 566) that:
(.),,
inf (g(0, X.), w) na,, weW;
that is
X.), wr (0) & 4I, + na:
(27)
On the other hand, by assumption we know that for any F L. us > us, 5
(0, (()))
9(0, X.), Σ
(0)
(28)
1=1
-e.,, (0)ur, +
Σ (0)s
1+1
> (0,1, + Σ \t, +
j$1
(0),,,0)u1, + (u,, + E1 Xt,,, (0))
(29)
24

---

Published as a conference paper at ICLR 2026
Combining (27) and (29) yields: and it follows from (30) that:
Ae.1, (0) 3 1 noc
(30)
K
|| 20x(0) 1| = =1121, - (x(()]1== =
Σ (1 (j=))) {e)(0))
5=1
No., (0)) + Σ (e)
max | lla
sth kE[K]
2no:
max ||xkl12
kE|K]
The result follows from combining H2 and Lemma 7 according to the same lines of computation as in the proof of Lemma 2.
G.1.3 OTHER LEMMAS
Lemma 8. Assume that for any t E [T], fe is K2 Lipschitz almost-surety and that the sequence of
steps (ne)aa is am--increasnn. Denote Hd Every f(())) - f(()). Then it holds almost surely that:
T
E
Ri
<
D + 2D
Σ 10+11-1 - rell +
Σ
K?
2Tyr
2
t=1
[=
where the expectation is taken over the sequence (u4....,,ry in Algorithu 2.
Proof. In what follows, we write En, the expectation under the distribution Unif([O, 1]) of ur and Em the expectation under the joint distribution Unif((0, 1))@T of (wi,..., Wr). For any E (T),
we have:
Σ f.(0.) - f.(0,) Σ
Σ a=0
Vi((e + u(O; - 0.)), U, )
T
V.r(O, + ur(0 - 0.11) 0. - ..))
Emy
t=1
T
[t([u)] 01.)
Eug
(31)
t=1
where vuu) f((00 + (0, - U.) as in Algorithm 2. To control (31) note that by definition
of 0,41 in Algorithm 2,
Eyg
|10241
001171
Eng
I no (u,)) - - 1r 0.11"]
100 21 m v.(ue)) 112
< Emg
< 11. 0.12 211 Bun (Ve(ue)) 0, 0.) + ni K? (32)
where we have used that (V((u>) ||
< K? because Je is K,-Lipschitz. Re-arranging (32) and
taking the expectation over (ui...., .a......,uy Ur) yields:
Bui. (Vr(ue), 0.)l Boir
1 (10,- 2-112-10 -110+1 -2.13) + n:K3
1
21pe
2
(33)
25

---

Published as a conference paper at ICLR 2026
Now notice that, for any t {l..... 1}.
|00+1 Det1ll
10++1 0ell² + |10 0ct1ll2 -110+11 - -dell
= 10++1 - 0zl12
+ (110+1 let1ll 110 0e11)(100+41 1e+1ll 1| -bell)
< |0++ 0.11² 2Del 00+1 - 0:1l
(34)
where we have used HI (i) and the reversed triangular incquality in the last line. It follows that:
-110c+1 - 0 < - 110++1 0+t1 +DDelll111 -9el
(35)
Plugging (35) into (33) then gives:
EMLT
(Ve(ue), 0r b.)l & Euyr
(100, -0,11= -110+1 - 0c+1l1²)
217
K?
- Dol 01+1 0.1l +
2
Thus, summing over T and plugging the resulting sum in (31) gives:
Σ f(0) - f((0s)
T
100
0el1
1
1
Euyr
&
B
2
71
T7--1
K?
Dol || 1 02+1
- 0ell
Σ
TJt
2
t=1
D
1
De
- |||1 + Σ ne
+
11+1
2
M--1
TT
where we used that for all t, ||0, 0.ll & De by HI-(i) and that for all t [T], 76-1 m mr. Then, we have by telescoping the first sum:
T Eur Σ
f.(0.)) - F((0.) <
D8 2D
2
T
1041
Hell
T Σ
K?
27T
2
G.2 PROOF OF THEBREM
Theorem Assume H1, and having access to an E-approximate oracle Og adapted to (Ein Jr - () DE(T.- Let (0:he(T) be the output of DF-FTPL (Algorithm 1) instantiated with learning step n > 0 and regularization coefficients ar a > 0fr any Then:
T T'M Ö mmm
+ mD
+ +5+aam) an
az
where E. denotes the expectation both data and the intrinsic randomness of DF-FTPL and Ô contains polynomial dependency
In((())))))))
Furthermore, taking 1j x m. 3/44-3//4p -1/2211/22 and a 3/ 1/2T yields:
T E p Ö mmmm)
3/4 3/27, 1/4 +5)
Proof. For the sake of conciseness we use the notation Eg to denote E[- H4-11 In what follows, we consider, for any the intermediary regret: R2)(0) Σx F.(O.) F.(0), where F, 0
26

---

Published as a conference paper at ICLR 2026
B[f((0) M4-1). We have, for any 8, the following decomposition of the static regret
(0)(
Σ
E. ( w/ (0.) (x:)0))]]
(36)
TE(T]
+
Σ
Eg (g w,())))
Σ
Eg
(37)
tE[T]
+E[
+ Σ
(X,,
Σ
E. Egl (X,) w7)))
(38)
EE(T]
NE(T)
Then, taking the sup over ④ in Equations (36) and (38), and defining
Reg =
(x)
Σ
<E|2]
LE|T]
in Equation (37) yields for any 0:
(0) < Regī +
Σ
sup E. (Xx,),,, w7 (x))
rE(T]
ace
Using the fact that || ol is dual -1:
(0) < Regg + 2
Σ sup E. (X:) i. (0)ll)
rE(T]
Since for any & [T]. (X, $ (x < Dz by Hi-(ii,
(0) < Regì + 2Dz
Σ
E 1 (0) we (0)l
8E8
[E[T]
First, notice that, by Lemma 6, and because for any t, at = a we have for all t:
2
ūr (0) w (0)l H.-1] & a + 2n max
U and
min Iu
(1-8)
(1 - 8)-
ke
(39)
Second, taking the expectation (denoted by EE) over (ot)re(T) and X1, ... Xy on both sides gives:
([R](00) < E [eg + 2D2T a 2n max
kE[K] | an min II 2
(1-3)
B) 3)-))
(40)
We now bound the first term in the right-hand haadh-hhnn-side of Equation (40). By the definition of conditional expectation, we have:
E
Regs] Ex. Eor.
Σ (X,,)),, (0))) ( (Xt), (0))
[E|T]
and then,
E [egg
< Xx, Eo....
f((())
inf #EB
Σ f((
LEMT
One recognises (up to a factor T') the left-hand side of Proposition 4 on the loss sequence (fi)ee(T) Furthermore, we use this proposition as, given our choice of R, for any E [7]. fo is L-Lisschitz with = 5D2G(4a) almost surely by Lemma (with x = 0). We then have:
E or
1 Σ f((O.)
inf Σ f((0) dee
< <0(m²
mmm
1
+
mD
rT +5)
(41)
T
T
a²
[E
[E[T]
27

---

Published as a conference paper at ICLR 2026
Dividing Equation (40) by T, and plugging Equation (41) gives: for all A E O:
T-ER(((()) < O mm D 1 a²
mD
+
+E)
n/t
(in((n) In (2) |1 a(a 1
a (2). , (1-33-1))
+ +2DzT
a
2n
max kE|K]
min
=0(m²²) a
1
mD
+ E + om
n/
Finally remark that, by the definition of the conditional expectation (thus of Fr), and because 0, is Ft-1 me---measurbble have for any A:
E [ = E
f((O,) fi(0)
E
f(()
-[]((())
Then taking the infimum over yields:
1 mD a²
TEM <
mmm mmm²D
+
+
+ an
Tf
This concludes the proof. The second equation consists in simply plugging the proposed value of 7): in this bound.
G.3 PROOF OF THEOREM 2
Theorem 2. Assume HI, H2, access to a É-approximate oracle adapted to (fihetT Let (Othe be the output of DF-OGD (Algorithm 2) instantiated with the non-increasing sequence (Nt)ee and regularization coefficients (at)tE(T). Then:
T- [p = δ
E
+
PT
Σ
T/t +
n04
+5]
+
Tmr
T
tE|T]
where Pr = -T=111110++ - Dell. E. denotes the expectation on both data and the intrinsic random- ness of DF-OGD and Ô contains polynomial dependency in In(1/o),, In(In(d)).
Furthermore, assume (1-1(1 + P:)) is non-increasing almost surely with Pt = E1= ||0+11 Pall. Then, using n 2// (1) and Th xn" 1 P,33/4 for any E [T] leads to:
TEE = - (B( PT) 1/4
- + +E)
Proof. In this proof, for the sake of conciseness, Observe that the dynamic regret can be decomposed as follows:
the notation E2 denote E(. H4-1)-
Σ TE(T]
E (Xt), wi (0.) w. (0.))) +
Σ
E. [. w. w..
(42)
TE(T]
(X)e)(())) T7 (0.))) inf E, E. (X.), (0)) BEB
(43)
EE[T]
inf EE, (g. to (0)) dee
inf Er (g. (())
(44)
dee
rE(T]
28

---

Published as a conference paper at ICLR 2026
First, remark that for any t, given dh O(fi). control (43) by Jensen:
(X) inf E, (ú) (0)) & E, F((O))) inf f((0)
#iee
aee
<
Then, taking the sup over @ for each summand of the first sum of (42) (which is valid as 0g is F measurable), defining by Regr = Exetry (X) dy (0,) /; (1x)). and noticing for (44) that
infage [S()) inf [.) inffage [[ff((00--ineee) E, [fx( & supace [+)
fc(0)]] & supace (ellf((0) (0)]] leads to:
R4 < Regr +
Σ
sup E, (X), क., (0))1 + ET
*E[T] OEN
Using the fact that || al is dual ||
R
< Regz
+ 2
Σ sup E, (xx (.(()))))+))
EE[T] BEB
Since for any / [T]. (X.) |(
Da almost surely by HI-(ii.
R < Regr + 2Dz
Σ
sup E,llvo (.(()ll +7
(45)
tE|T) AEN
First, by Lemma 6, we know have for any t:
2 at ) (1 })
sup Be[ll(7()) (0)l < aa + 2n max |eull (r Ind) min { In 156
kE[K]
Thus combining the two last equations and taking the expectation (denoted by E) over (ux) and "I,... XT both sides gives:
E [
[[Regr]
ar 2n max aelll In d min In (2) (2) (1 (1- (1-))-1)) + + (46) at
+ 2Dz
kE[K]
LE[T]
Now, bound the first term in Equation (46) note that the definition of conditional expectation implies:
E. Regrl = Ex,--x Xy E Bug Mer
Σ J.(O.) J.(O.)
aer
FE|T
One recognizes the definition of Rt of Lemma 8. Since fo K, Lipsshtt with K, =
GDz suPwew, [[b-Aw] almost surely for any t by Lemma 5, we deduce from Lemma 8 that: Amain (11')
D% De
Th (G2 supwew. 16 - Awll ardmiu (Dmii(AA7 (AAT)
E Eug Marr
Σ f(00) - f((1))
<
Σ
2TT
2
tE|2
1E[2]
(47)
Plugging Equation (47) into Equation (46) and then dividing by 7' on both sides gives:
29

---

Published as a conference paper at ICLR 2026
GDz sup weW 116 Awl 2
T
D3 + D&E[PT]
"t
atAmiu(An) (AA)
2Dz 2
Σ
O2 + 2n max | o Ind) min In 2
(1 11-)))-))
+
kE(K]
04
NE(T]
(48)
Rewriting Equation (48) using O concludes the proof.
Concerning the second bound, We know by Equation (48) that the regret of Algorithm 2 satisfies the following bound:
)
E RV
E
PT
Tl
Σ
ar ET
1/T
LE|T]
BE[2
With og n nn11/2--1441 + // and me e/t-1/2(1 + 1/2 n 1/1 + P.) the sequence (er) is non-increasing because so is (t- (1+))eemT by assumption. Moreover, the first term satisfies:
1 Pr
O
1/2
T3/4
P/.33/1 3// (1+ (1+
1+ Pr Tnp
O n2
14 Pr 1/1
so
Wr
(1 + Pr.
For the second term,
T
T
I+P.
T
1+ P.
1/4
O
1/2
vtas
Moreover, since
P. &
Pr for any & [7], we have:
1 )))²))
1/4
Th at n 21 Pr) 1/1
O
- -1 Pr) P2)+)/223//)
where we used the last line that Ei, t = (T for E (0, 1). Dividing by T again gives
a rate of (( ((=tp))) 1/4) for the second term. Finally, we obtain by the same reasoning that
m Σ a. < n 1/2 (1 P/1
Σ 2-1111 000=0(n22) (n pr)1/173/11
[E[T
LE|T]
and dividing by > 0 yields the desired rate.
G.4 PROOF OF PROPOSITION 2
Proposition Assume HI, H2 and having access to an É-approximate optimization oracle Og adapted f. Jeer Fix W Wo. R Rg. Let (0ehter be the output of DF-FTPL (Algorithm 1) instantiated with learning step r > and regularization coefficients 04 = f.ror Joy I. Then:
TERR <Ō rmm²
1 mD a
+5+aan(d))
+
n/p'
where denotes the expectation on both data and the intrinsic randomness of DF-FTPL and Ô contains polynomial dependency in In(1/o), (n(//),,I((I(())) In(((d)).
30

---

Published as a conference paper at ICLR 2026
Proof. For the sake of conciseness
the notation E, to denote E[- H4-1 In what follows,
consider, for any 0, the intermediary regret: R2-(0) Σ (.(O.) (O),, where [f) H4-1]- We have, for any 0, the following decomposition of the static regret
F,
(0) = Σ
E. (o (Xe), w (0.) - wxx(+))]]
(49)
TE
Σ
Ee((oe
(x)),x())))))))) wo(0.)) Σ
(x, 8y (OM)
(50)
+E(TT
+ Σ
E. (.
Σ
Be (X,), wi (0))
(51)
6E[T]
DE[T]
Then, taking absolute values, using the triangular inequality and taking the sup over θ in Equa- tions (49) and (51), well as defining
Reg = Σ (X,)), C. (0.))
Σ
(X,,,,
tE|M
LE|T]
in Equation (50) yields for any A:
(+) < Regr + 2 Σ
sup (X,),, wx()) (.())
rE|T]
Aee
Using the fact that || al is dual to 11:
(0) < Regd + 2
Σ sup E, (X.)ll i (6)1la)
1E/U o
Since for any & [T]. 10. (X,) 0o < (X,() < Dz by HI-(ii),
(+) < Reg 2Dz
Σ
Eysup| w (0) ii, (
Ag
(E(T]
First, notice that, by Lemma 2, and because for any t,
have for all t:
E[| (0) w7 (0)11 H4-1] & a la min In 2
(1 (1-
(52)
Second, taking the expectation (denoted by IE) over (o.)e and X1, Xy on both sides gives:
(0) < E Regē] + +DDT a 2( ln()) mine In 2
(1 (1 - ()-))
(53)
To bound the first term in the right-hand-sine of Equation (53). by the definition of conditional expectation, we have:
E Regsl = Ex.... Xy Ear... or
Σ (E|T]
(0.)) (o.((),, (G, (Xt), w. (0))
(X,(),),
Then,
E RRgg & Ex Xy Eagi oa
Σ
(((0.)
inf Σ F.(0)) BEe 1E|2T
[E(TT
One recognises (up to a factor 7') the left-hand side of Proposition 4 on the loss sequence (fe)ee Furthermore, we can use this proposition as, given our choice of R, for any L-Lipschitz with L = 5DzG(44) almost surely by Lemma (with x = 0). We then have:
[7]. f. is
E
1 Σ fe(O.)
inf dee
Σ f((00) [E[T]
< <
mm
1
+
mD
nf +5)
(54)
or
T
T
a²
[E
31

---

Published as a conference paper at ICLR 2026
Dividing Equation (53) by T, and plugging Equation (54) gives: for all A E O:
T ERR; & O mmm fmm²D==
mD
a² +
+E)
n/T
( In (2) + + +11-3) (n
+ 2Dza
|1
= = mmm =0(m²²
1 a²
mD
nf + +laal)))).
Finally remark that, by the definition of the conditional expectation (thus of Fi), and because 0, is Fe---meauurable, we have for any A:
T E EIR (0)
Se(O.) 12(0))
E
fe(0.))
B[f((0))
Then taking the infimum over yields:
T EE Ö
1mmm
mD np
+ a In(d))
a²
This concludes the proof. The second equation consists in simply plugging the proposed value of in this bound.
G.5 PROOF OF PROPOSITION 3
Proposition 3. Assume H1, H2, and having access to an É-upproximate optimization oracle Og adapted to { { rE|r]" Wi = Wo. R = RRo Let {0r) be the oulput of DF-OGD (Algorithm 2) instantiated with the non-increasing sequence (nt) (Me)ee(T) and regularization coefficients (at))t(T) Then:
D& + De
25DzGm
7- E [M4]]
2TTT
32T
+ +DDz Σ
on + 2l (1- In &
*E[T]
where Pr = ET-1 11001 - 0zll
Proof. In this proof, for the sake of conciseness, we denote by E, the conditional expectation B|. Hc-1]-
Observe that the dynamic regret can be decomposed as follows:
R
Σ
E. (G (Xt), wi (0.) (0.))) + Σ
E. [x (..)) w. (o.)))
(55)
TE(T]
TE(T]
Kig (Xt), T7 (0.)) inf E. (g. (X.), (0)) BEB
(56)
EE[T]
Σ
inf EE, (X)) to (0)) dee
inf Er (g. wt
(57)
dee
rE(T]
32

---

Published as a conference paper at ICLR 2026
First, remark that for any t, given dh O(fi). control (56) by Jensen:
(x(()((X)) inf (xl, 8y (0) & Er [((O)) inf fi())
DE6
E
Then, taking the sup over for each summand of the first sum of (55) (which is valid as is -e---uuaurrblle) defining by Regr Everr E, lig (X,). (0,) ú; (0,)), and noticing for (57) that infage [e(]((0)] inface [e)) & supace (e) [o) leads to:
Ry < Regr 2
Σ
sup (g. (0) (()) ET
aEe
1E[T]
Using the fact that || al is dual to 11:
n4 & Regr + 2
Σ
sup Er, (x (0(1)))1)+77
xE[T] AE
Since for any & [2]. (X, (X))(X)))l2 Da almost surely by HI-(i).
R4 < Regr + 2Dz
sup (,)l (.(()l +T
(58)
tE|T) AEe
First, notice that, by Lemma 2, for all
sup (0) n. (0) < au (1+ [1+2In(d]Ca 8c
In ( 04
+ (1 (a) In(d))
(59)
Second, taking the expectation (denoted by E)) over (u))eTT) and X,, .. Xy on both sides gives:
E [ < E[Rgr]]
+ +2Dz
Σ tE[T]
[1 In ox
2
+ In) In) (n(a)))))))))))()))) + ET. (60)
To bound the first term in the right-hand side of Equation (60). Remark that, by the definition of conditional expectation:
f((()) F((Oo)
E Regrl = Ex, Eu,... ur
1E
One recognises the definition of oं of Lemma 8. Thus, by this lemma, know that for any
i E [T], because Se is K,- -ipLchhhittz with K. 5D2G(44r)) almost surely by Lemma 1,
have:
25D3Gam
Eug en Marg
Σ [E[T]
f(()))
<
(D3 DePr)
Σ
(61)
2nr
32a
:E(T]
Plugging Equation (61) into Equation (60) and then dividing by T > on both sides gives the desired result.
33

---

Published as a conference paper at ICLR 2026
G.6 PROOFS OF APPENDIX F
Proof of Proposition 5. The regret simply decomposes as follows:
Ry
Σ
Exl(o,(X,), w,((1))]- Σ
inf E. (X,) (0))
1E BEB
EE[T]
Σ Exl(oe( (.( w/ (0:))]
AE[2]
+
Σ
R (1,)((X)) wz (0.)))
Σ
inf E2 (X,), un (0))
BEO
1E(T]
1E|T]
< +
Bx (g, w[ (0.)))
Σ
in E, ( (Xe), w/ (0))
AEB
(E(T]
<E(T]
and the proof continues as in Theorem 2.
34


Reviews:
[{"review_id": "v4eAIx1auG", "reviewer": "Reviewer_JCMo", "summary": "This paper tackles the problem of training predictive models that are used not downstream decision-making tasks. The authors frame this as a bi-level online optimization problem. They overcome challenges of non-differentiability and non-convexity by using regularization and perturbation, and develop variants of follow the perturbed leader and online gradient descent that get sublinear static and dynamic regret.", "questions": "* The oracle assumption is understandable but it seems quite expensive to invoke the oracle in each round, especially for large non-convex problems. I understand that there are a lot of analyses on favorable loss landscapes for neural networks and how gradient descent-based methods can find \"good optima\". However, running such methods to convergence in each round seems quite slow in practice. Did you measure this in your experiments / are your experiments large-scale enough for this to be a problem? Do you have thoughts on how you could use lazy updating to only invoke the oracle once every few rounds while maintaining or suffering from a tolerable degradation in the regret bound?\n\n* Is my understanding correct that the choice of the regularizer does not affect the final regret bound as long as the hyperparameter $\\alpha_t$ is chosen correctly? This hyperparameter is chosen a function of $T, m$ and $n$. I understand that the time horizon is sometimes unknown. Are there cases where $m$ and $n$ might be unknown? In case of mis-specified $T, m$ or $n$, how does the regret bound degrade with the degree of mis-specification?\n\n* The paper assumes that the set $\\mathcal{W}$ is a convex polytope. How restrictive is the polytope assumption? If we had general convex sets, how would that impact your analyses and where would the problems arise?\n\n* The (average) regret bound of $ T^{-\\frac14} $ is quite slow compared to the usual $ T^{-\\frac12} $ regret bounds. I understand that the problem in this paper is harder (bi-level optimization, non-differentiable, non-convex). Do you have thoughts on whether this is tight and a lower bound? If not, what do you think could lead to improved regret bounds? For example, using an alternative to perturbation, an alternative to offline optimization oracles, etc.?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is an excellent paper!\n\n* The paper is very well written and includes intuitive explanations along with precise mathematical statements.\n\n* The paper tackles a fundamental problem: online decision-focused learning, where the goal is to train predictive models not just for prediction but for using those predictions in a downstream decision-making task. While prior work looked at this problem in the offline setting, this paper studies this problem in the online setting, provides provable regret guarantees - static and dynamic - and shows strong experimental results, where the proposed algorithms have a worse prediction accuracy than baselines but superior downstream performance.\n\n* The formulated problem is challenging: bi-level optimization, non-differentiable, and non-convex. The authors overcome these challenges using a combination of smoothing/regularization, perturbation and offline optimization oracles - all somewhat standard tools. Then, they develop variants of standard online learning algorithms, follow the perturbed leader and online gradient descent, for the online decision-focused setting. However, the overall problem formulation and solution methodology is very elegant and this is a plus in my opinion, especially when combined with the theoretical and empirical results and the importance of the problem.", "weaknesses": "Please see the questions section some weaknesses/questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eA8aRTWf25", "reviewer": "Reviewer_X6pL", "summary": "This paper studies decision-focused online learning and utilize regularization for differentiability and perturbation for non-convexity. They succeed in generating static and dynamic regret results with respect to loss predictor parameters.", "questions": "Questions:\n\nPage 2 Line 93: how does the linear structure cause zero or undefined gradient?\n\nPage 4 Line 195: should it be $i\\in[K]$?\n\nPage 4 Line 204: why does $\\epsilon=0$ imply anything? Doesn't the inequality hold for all $\\epsilon$?\n\nPage 6 Algorithm 1 Line 3: shouldn't the objective for $w$ be regularized?\n\n\nSuggestions:\n\nPage 2 Line 85: correct grammar.\n\nPage 3 Line 117: there seems to be a typo between $g$ and $\\phi$.\n\nPage 5 Line 275: $\\Theta$ was the parameter space in (8). Please correct.\n\nPage 7 Line 352: check grammar.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality:\nThe originality arises from a proper problem formulation for the regret analysis of decision-focused online optimization, incorporating static and dynamic regret analysis into the said problem and removing limitations of non-differentiability and non-convexity.\n\nQuality:\nThe submission seems technically correct, experimentally rigorous and reproducible (except minor caveats in the algorithms).\n\nClarity:\nThe submission is mostly clear.\n\nSignificance:\nThe submission presents theoretical (and possibly algorithmic) novel findings to achieve the static and dynamic regret results for online decision-focused learning.", "weaknesses": "I did not notice any substantial weakness, so I am leaning towards acceptance.\n\nOne thing to note is that the exact challenge in achieving the said results could be emphasized. Possibly, after proper formulation, everything follows from the existing regret analysis techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oe4WKS3LcK", "reviewer": "Reviewer_FEZs", "summary": "The paper studies an online version of decision-focused learning, where the learner is evaluated not by the accuracy of the predictions but by the quality of the decisions made. Unlike in the batch case, in the online version, the problem may evolve over time in a fully non-stationary way. As the problem is non-differentiable and non-convex, the authors leverage a regularized version of the bi-level optimization problem and rely on near-optimal oracles to derive regret guarantees by instantiating follow-the-leader and online gradient descent algorithmic schemes. Finally a synthetic experiment illustrates the effectiveness of the proposed algorithms in minimizing the average cost.", "questions": "* Please refer to weaknesses.\n* Please clarify if any technical contribution in the paper is novel or it required specific treatment due to the nature of the problem.\n* In Fig.1 the average cost of PFL, SPO, and FTPL see to converge towards the same value. Is this the case? If the overall process is stationary and ergodic, maybe we should indeed expect all methods to coverage to the same performance. If not, what is the explanation behind the difference in performance?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper extends the decision-focused framework to online learning, whereas most of the existing literature on the topic is limited to the batch case, where iid samples and a fixed estimation/optimization problem is available.\n* The authors provide a complete analysis of the problem leveraging state-of-the-art technical algorithms and tools from online learning literature.", "weaknesses": "* The technical novelty of the paper is limited. While the authors stress the challenges posed by the online decision-focused learning setting (non-differentiable and non-convex functions), once formulated as in eq.(3) the problem is amenable to any \"standard\" online learning treatment. Indeed most of the results in the paper are obtained by carefully instantiating known assumptions, algorithms, and theoretical results, such as assumptions H1/H2, FTL and OGD, regularization and approximate oracle for non-convex objectives. As such, the results in the paper should be mostly assessed based on the interest of the setting.\n* While I'm not very familiar with the decision-focused learning paradigm, I can see a strong resemblance with other decision-making settings in machine learning, where accuracy in prediction problems do not directly translate into performance wrt to a target objective function. These includes reinforcement learning (e.g., accurately estimating an MDP does not translate into computing an optimal policy for a given reward) or bandit (e.g., accurately estimating the mean of each arm does not translate into accurately returning a high-reward arm). While the decision-focused learning paradigm may have emerged in a different literature, it would be helpful to have a more extensive justification of how the proposed online version differs from adversarial bandit/RL settings and provide more practical examples supporting its relevance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EMs8gqSscn", "reviewer": "Reviewer_riB6", "summary": "This paper studies the predict-then-optimize framework in the online setting. To handle the non-stationarity of online data streams, the authors regularize the objective and present two new algorithms, based on FTPL and OGD, to handle the non-convexity of the overall objective function. The authors prove both static and dynamic regret bounds, complementing their theoretical results with strong empirical evidence.", "questions": "See Weaknesses. Also, can the authors comment on practical settings where having access to an offline optimization oracle is reasonable?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is well-written and easy to follow\n- The problem is well-motivated and of general interest to the ML community\n- In my opinion, the contributions by the authors are substantial as they provide both strong theoretical and empirical results", "weaknesses": "My biggest gripe with this paper is its lack of clarity in the problem setup. Below, I summarize a few points of confusion for me. \n\n-  In line 136, the authors write $\\bar{g}_t(X_t) = E[Z_t|X_t]$ for some hidden state $Z_t \\n R^d$. What does this mean? Does $X_t$ index a hidden distribution $D_t$ and $\\bar{g}_t(X_t)$ is the expected value of this distribution? \n\n- In line 176, $F_t$ is defined in terms of an expectation. What is the expectation taken with respect to? Just the learner's randomness?\n\n- In Equation 4, why is there an expectation over the player's actions in dynamic regret but not static regret? \n\n- In Line 196, what is the probability taken with respect to? Line 164-165 claims that you place no assumption on $(X_t \\bar{g}_t(X_t)), so I'm not sure where the randomness is coming from...\n\n-  Likewise, why is there an expectation on the data in Theorem 1 if, according to Lines 164-165 you place no assumptions on the data-generating process?  \n\nOverall, I think the authors need to clarify how the adversary is selecting the data stream. This lack of clarity is the main reason for my rating. I am happy to increase my score, given that the authors address this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)