Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
Authors: Shinsaku Sakaue
Taira Tsuchiya
Han Bao
Taihei Oki
Venue: NeurIPS 2025 poster ()
Keywords: inverse optimization
online learning
Primary area: theory
TL;DR: We present an efficient $O(n \ln T)$-regret method for online inverse linear optimization, extend it to suboptimal feedback, and provide an $\Omega(n)$-regret lower bound.

Abstract: In online inverse linear optimization, a learner observes time-varying sets of feasible actions and an agent's optimal actions, selected by solving linear optimization over the feasible actions. The learner sequentially makes predictions of the agent's true linear objective function, and their quality is measured by the *regret*, the cumulative gap between optimal objective values and those achieved by following the learner's predictions. A seminal work by Bärmann et al. (2017) obtained a regret bound of $O(\sqrt{T})$, where $T$ is the time horizon. Subsequently, the regret bound has been improved to $O(n^4 \ln T)$ by Besbes et al. (2021, 2025) and to $O(n \ln T)$ by Gollapudi et al. (2021), where $n$ is the dimension of the ambient space of objective vectors. However, these logarithmic-regret methods are highly inefficient when $T$ is large, as they need to maintain regions specified by $O(T)$ constraints, which represent possible locations of the true objective vector. In this paper, we present the first logarithmic-regret method whose per-round complexity is independent of $T$; indeed, it achieves the best-known bound of $O(n \ln T)$. Our method is strikingly simple: it applies the online Newton step (ONS) to appropriate exp-concave loss functions. Moreover, for the case where the agent's actions are possibly suboptimal, we establish a regret bound of $O(n\ln T + \sqrt{\Delta_T n\ln T})$, where $\Delta_T$ is the cumulative suboptimality of the agent's actions. This bound is achieved by using MetaGrad, which runs ONS with $\Theta(\ln T)$ different learning rates in parallel. We also present a lower bound of $\Omega(n)$, showing that the $O(n\ln T)$ bound is tight up to an $O(\ln T)$ factor.

Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
Shinsaku Sakaue" CyberAgent Tokyo, Japan shinsaku. www.ueemmaaaaaa....mamaa com
Taira Tsuchiya
The University of Tokyo and RIKEN AIP
Tokyo, Japan
tsuchiya@mist. w.w.okyo.......ccc...ooooo
Han Bao'
Taihei Oki
The Institute of Statistical Mathematics Tokyo, Japan bao. han& imm...imm..... ac. jp
Hokkaido University
Hokkaido, Japan
oki oki@icredd.
www.icrred..ouuaa..... hok.hai.aaccooooo acc
Abstract
In online inverse linear optimization, a learner observes time-varying sets of feasi- ble actions and agent's optimal actions, selected by solving linear optimization over the feasible actions. The learner sequentially makes predictions of the agent's s true linear objective function, and their quality measured by the regret, the cumu- lative gap between optimal objective values and those achieved by following the learner's predictions. seminal work by Bärmann al. (2017) obtained a regret bound of O(VT), where T the time horizon. Subsequently, the regret bound has been improved to On T)) by Besbes et al. (2021, 2025) and to O(n In T') by Gollapudi al. (2021), where n the dimension of the ambient space objective vectors. However, these logarithmic-regret methods are highly inefficient when T is large, as they need maintain regions specified by O(T) constraints, which repre- sent possible locations of the truc objective vector. In this paper, we present the first logarithmie-regee method whose per-round complexity is independent of indeed, it achieves the best-known bound of (n In 7"). Our method is strikingly simple: it applies the online Newton step (ONS) to appropriate exp-concave loss functions. Moreover, for the case where the agent's actions lish a regret bound On In T + A In T), where Ar is the cumulative subop- timality of the agent's actions. This bound is achieved by using MetaGrad, which runs ONS with (In T') different learning rates in parallel. We also present a lower bound of (()), showing that the O(n In bound is tight up to OIn 7) factor.
possibly suboptimal, we estab-
Introduction
Optimization problems serve as forward models of various processes and systems, ranging from human decision makiing to natural phenomena. In real-world applications, the true objective function of such models is rarely known a priori. This motivates the problem of inferring the objective function from observed optimal solutions, or inverse optimization. Early work in this area emerged from geo- physics, aiming estimating subsurface structure from seismic wave data [11, 53). Subsequently, in- verse optimization has been extensively studied [2, 13, 14, 28), applied across various domains, such as
'This work was primarily conducted during the period when SS was affiliated with the University of Tokyo RIKEN AIP, and HB with Kyoto University and OIST.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

transportation [6], power systems [9], and healthcare [12], and have laid the foundation for various ma- chine learning methods, including inverse reinforcement learning [44] and contrastive learning [50].
This study focuses on an elementary yet fundamental case where the objective function of forward optimization is linear. We consider an agent who repeatedly selects an action from set of feasible actions by solving forward linear optimization. Let n be a positive integer and R" the ambient space where forward optimization is defined. For 1,..., T, given set X; S IR" of feasible actions, the agent selects an action Ia E X, that maximizes x + {c", x) over Xx, where c* E IR" is the agent's internal objective vector and (:--) denotes the standard inner product on R" We want to infer e* from observations consisting of the feasible sets and the agent's 's optimal actions, i.e., { )
For this problem. Bärmann al. [4, 5] have shown that online learning methods effective for inferring the agent's s underlying objective vector c*. Consider a learner who aims to infer c². For t t= ........ T, the learner makes a prediction & of c* based on the past observations xx), and receives (Xe, 2x) feedback. Let 2, E arg m (C,, represent an optimal action induced by the learner's 's tth prediction. The regret of choosing 2, instead of x is defined as Σi=(("' 24 - 2,).² Their idea is regard RR" -> {c, f2 Fit) cost function and apply online learning methods, such as the online gradient descent (OGD). Then, Σi 2i - .t) S Σ (ô+ - c² dr - rz) = O(VT) follows from the standard guarantee of online learning methods. As such, online learning methods with sublinear regret bounds can make the average regret converge to zero as T + 00.
While the regret bound of O(vT) is optimal in general online linear optimization (e.g.. Hazan [26, Section 3.2]), the above online inverse linear optimization has special problem structures that could allow for better regret bounds; intuitively, feedback xx) is more informative about c², which defines the regret, due to the optimality of 2g E X, for c². Besbes et al. [7, 8] indeed showed that log- arithmic regret bound of ( In I') is possible, and Gollapudi et al. [25] further improved the bound to O(n In 7). 3 While these methods significantly improve the dependence on T in the regret bounds, their per-round computation cost is prohibitively high when T is large. Specifically, these methods iteratively update (appropriately inflated) regions that indicate possible locations of the true objective vector c* and set prediction & the "center" of the regions (the circumcenter in Besbes et al. [7, 8] and the centroid in Gollapudi et al. (25)). Since those regions are represented by OTT) constraints, their per-round complexity grows polynomially in T, least in a straightforward implementation. Indeed, Besbes et al. [7, 8] and Gollapudi et al. [25] only claim that their methods run in poly T") time. This in stark contrast to the earlier learning approach of Bärmann et al. [4, 5], whose per-round complexity independent of T; however, its O O(VT)-regree bound is much worse in terms of T. Is then possible to design logarithmic-regret method whose per-round complexity is independent of T
1.1 Our contributions
In this paper, we first present an (n In -regret method whose per-round complexity is independent T (Theorem 3.1). answering the above question affirmatively. Table summarizes the comparisons of our result with prior work. Our method is very simple: we apply the online Newton step (ONS) [27] to appropriately designed exp-concave loss functions. We believe this simplicity is a strength of our method, which makes it accessible to a wider audience and easier to implement.
We then address more realistic situations where the agent's 's actions can be suboptimal. We establish a regret bound of O(n In T + An In T), where Ar denotes the cumulative suboptimality of the agent's s actions over T rounds (Theorem 4).. We also apply this result to the offline setting via the online-to-batch conversion (Corollary 4.2). This bound is achieved by applying MetaGrra [55, 56), a universal online learning method that runs ONS with OIn 7) different learning rates in parallel, to the suboptimality loss [43], a loss function commonly used in inverse optimization. While universal online learning is originally intended to adapt to unknown types of loss functions, our result shows that it is useful for adapting to unknown suboptimality levels in online inverse linear optimization. At
An "agent" sometimes called an "expert." which we do not use to avoid confusion with the expert in universal online learning (see Section 2.3). Additionally, our results could potentially be extended to nonlinear settings based on kernel inverse optimization [6, 39], although we focus on the linear setting for simplicity. IIn online setting, the learner's 's goal subtly deviates from inferring directly. Instead, the learner aims to make predictions & such that the induced actions &, are good for the true objective c*.
Goolapudi et al. [25] studied the same problem under the name of contextual recommendation.

---

Table 1: Comparisons of the regret bound under optimal feedback and per-round/total complexity.
Here, Tualve is the time for computing ã, E arg x (cc, 2) and Te.pooj/TG.pu proj is the time for the Fucliddann/eeneralized projection; typically, poj = ((n) and pGppo =Onn²) (see Section 3 and Appendix A for details). Regarding the regret bound of Bärmann et al. [4. 5], the dependence on varies depending on the problem setting, which we discuss in Appendix A (here, set sizes are regarded as constants). Besbes et al. [7. 8] and Gollapudi et al. [25] only claim that the total complexity is poly(n, T). Our inspection in Appendix A estimates the per-round complexity of Gollapudi et al. [25] as (F + n n² or higher.
Regret bound
Per-round complexity
Total complexity
Bärmann al. [4, 5]
((vT)
(T + T..pmoj + n)
Per-round T
Besbes et al. [7, 8]
O(n In T)
Not claimed
poly(n, T)
Gollapudi et al. [25]
O(nIn T)
Not claimed
poly (n, T)
This work (Section 3)
O(nIn T)
O Tsalve + pruj + n²)
Per-round T
high level, our important contribution lies in uncovering the deeper connection between inverse opti- mization and online learning, thereby enabling the former to leverage the powerful toolkit of the latter.
Finally, we present regret lower bound of (()) (Theorem 5.1). Thus, the upper bound of O(n In T) achieved by the method of Gollapudi et al. [25] and ours is tight up to an O(In 7) factor. While the proof idea is somewhat straightforward, this lower bound clarifies the optimal dependence on n in the regret bound, thereby resolving a question raised in Besbes et al. [8, Section 7].
1.2 Related work
Classic studies on inverse optimization explored formulations for identifying parameters of forward optimization from a single observation [2, 29). Recently, data-driven inverse optimization, which is intended to infer parameters of forward optimization from multiple noisy (possibly suboptimal) observations, has drawn significant interest [3, 6, 10, 35, 39, 42. 43, 52, 63]. This body of work has addressed offline settings with other criteria than the regret, which we formally define in (2). The suboptimality loss was introduced by Mohajerin Esfahani et al. [43] in this context.
The line of work by Bärmann et al. [4, 5], Besbes et al. 17, 8], and Gollapudi et al. [25], mentioned in Section 1, is the most relevant to our work; we present the detailed comparisons with them in Appendix A. It is worth mentioning here that Gollapudi et al. [25] obtained an exp(O (On In -rreegrttt bound, in addition to the O(n In T') bound in Table 1; therefore, it is possible to achieve a finite regret bound, although the dependence on is exponential. Recently, Sakaue et al. [49] obtained finite regret bound by assuming a gap between the optimal and suboptimal objective values. Unlike their work, we do not require such gap assumptions. Online inverse linear optimization can also be viewed as a variant of stochastic linear bandits [1, 18), where noisy objective values are given as feedback, instead of optimal actions. Intuitively, the optimal-actio action feedback is more informative and allows for the (n In T) regret upper bound, while there is lower bound of Q(nvT) in stochastic linear bandits [18, Theorem 3]. Online-learning approaches to other related settings have also been studied [20, 30, 591; see Besbes et al. [8, Section 1.2] for extensive discussion on the relation to these studies. Additionally, Chen and Bilinç-Karzal [15] and Sun et al. [51] studied online-learning methods for related settings with different criteria.
ONS [27] is a well-known online convex optimization (OCO) method that achieves a logarithmic regret bound for exp-concave loss functions. While ONS requires the prior knowledge of the exp- concavity, universal online learning methods, including MetaGrad, can automatically adapt to the unknown curvatures of loss functions, such as the strong convexity and exp-concavity [55, 56, 58, 64). Our strategy for achieving robustness to suboptimal feedback is to combine the regret bound of MetaGrad (Proposition 2.6) with the self-bounding technique (see Section 4 for details), which is widely adopted in the online learning literature [23, 60, 66].
Contextual search [38, 48] is a related problem of inferring the value of (c", for an underlying vec- tor e given context vectors Iy. The method of Gollapudi et al. [25] based on techniques developed in this context. Robustness to corrupted feedback is also studied in contextual search [36, 46, 47].
3

---

However, note that the problem setting is different from ours, Also, the regret in contextual search is defined with optimal choices even under corrupted feedback, and the regret bounds scale linearly with the cumulative corruption level. By contrast, our regret is defined with the agent's 's possibly suboptimal actions and our regret bound grows only at the rate of vDr for the cumulative suboptimality År.
Improving the per-round complexity is crucial. This topic has gathered particular attention in online portfolio selection [17, 34, 57J. There exists a trade-off between the per-round complexity and regret bounds among known methods for this problem, and advancing this frontier is recognized as important research [32, 54, 65]. When it comes online inverse linear optimization, logarithmic regret bounds had only been achieved by the somewhat inefficient methods of Besbes et al. [7. 8] and Gollapudi et al. [25], while the efficient online-learning approach of Bärmann et al. [4. 5] only enjoys the O(vT)- regret bound. This background highlights the significance of our efficient OO In r-rgrett method, which realizes the benefits of both approaches that previously existed in trade-off relationship.
2 Preliminaries
2.1 Problem setting
We consider an online learning setting with two players, a learner and an agent. The agent sequentially solves linear optimization problems of the following form for f I..
maximize (c", x)
subject to x E Xt,
where ct is the agent's objective vector, which is unknown to the learner. Every feasible set X, S IR" non-empty and compact, and the agent's action H; always belongs X,, We assume that the agent's action is optimal for (1), i.c. Ty E arg m (c", z),, except in Section 4, where we discuss the case where 24 can be suboptimal. The set, X₁, not necessarily convex; we only assume access an oracle that returns an optimal solution I E arg x (c, x', for any E R" If X, is a polyhedron,
any solver for linear programs (LPs) of the form (1) can serve as the oracle. Even if (1) is, for example, an integer LP, we may use empirically efficient solvers, such as Gurobi, to obtain an optimal solution.
The learner sequentially makes a prediction of C* for t= 1,... ... T. Let θ C RR" denote objective vectors, from which the learner picks predictions. We assume that is a closed convex set and that the true objective vector c* is contained in θ. For prediction é of ot based on past observations {(X., az) )== and then receives (Xe, 21)) as feedback from the agent. Let & E arg maxzex. (c,, x) denote an optimal action induced by the learner's 's tth prediction." We consider the following two measures of the quality of predictions (i,.... êr E O:
of linear
1, ... T, the learner outputs
R Σ (c", xe .n) and Te = -RT
Σ
(2, Rt xz) Σ (6 C xz).
(2)
Following prior work [7, 8, 25], call R the regret, which is the cumulative gap between the optimal objective values and the objective values achieved by following the learner's predictions. Note that we have (c", .x) 2 0 as long as 2, is optimal for ct. While the regret is natural performance measure, the second one, Rt. in (2) is convenient when considering the online-learning approach [4, 5]. We always have Re. < ieg since the additional term consisting of (2,, & - xx) is non-negative due to the optimality of 2. for éq intuitively, this term quantifies how well é explains the agent's choice Zt. Our upper bounds in Theorems 3.1 and 4.1 apply to Rtç and our lower bound in Theorem 5.1 applies to Ry
Remark 2.1. The problem setting of Besbes al. [7, 8] involves context functions and initial knowledge sets, which might make their setting appear more general than ours. However, it is not difficult to confirm that methods are applicable to their setting. See Appendix A for details.
2.2 Boundedness assumptions and suboptimality loss
We introduce the following bounds on the sizes of X, and θ
We may break ties, if any, arbitrarily. Our results remain true as long as de is optimal for é

---

Assumption 2.2. The b2 di-mmeee of is bounded by > 0. i.e. max [|c cll2cc. E { D. Similarly. the 2-- di-mmeeeter of X, is bounded by K 0 = 1...., ., Furthermore, there exists B > 0 satisfying the following condition:
max (c x=)=xx) ,,c X.) SB for t I.
Assuming bounds on the diameters common in the previous studies [4, 5, 25]. We additionally introduce B >> 0 to measure the sizes of X, and θ taking their mutual relationship into account. Note that the choice of B DK is always valid due to the Cauchy- inspired by semi-norm of gradients used in Van Erven et al. [56] and enables sharper analysis than that conducted by simply setting = DK.
inequality. This quantity is
We also define the suboptimality loss for later use.
Definition 2.3. For = 1..... T, for any action set X and the agent's possibly suboptimal action Vys the suboptimality loss is defined by (c) maxxexx, (c, - (c, (c, for all e E θ
That is, (e(c) is the suboptimality of æt Xx for Mohajerin Esfahani et al. [43] introduced this as loss function that enjoys desirable computational properties in the context of inverse optimization. Specifically, the suboptimality loss is convex, and there a convenient expression of a subgradient.
Proposition 2.4 (cf. Bärmann et al. [4, Proposition 3.1]). The suboptinality loss. f θ R, is convex. Moreover, for any & E and 34 E arg max (Ct, x),, it holds that i, - It E (2))
Confirming these properties is not difficult: the convexity is due to the fact that & is the pointwise max- imum of linear functions c + (c, z) - (c, zt), and the subgradient expression is a consequence of Dan- skin's theorem [19] (or one can directly prove this in Bärmann et al. [4, Proposition 3.1J). It is worth mentioning that, as pointed out by Sakaue et al. [49], Ry appears the linearized upper bound on the regret with respect to the suboptimality loss, i.e., Ei=(( (G)) 2 (c")) S Ei= (c -0",""" ."))) ) = Rey", where i 34 E (l,().) This enables the online-to-batch conversion for the suboptimality loss, discussed in Section 4.1. Additionally, we have Pey Re Σ ((()) in (2).
2.3 ONS and MetaGrad
We briefly describe ONS and MetaGrad, based on Hazan [26, Section 4.4] and Van Erven et al. [56], to aid understanding of our methods. Appendix B shows the details for completeness. Readers who wish to proceed directly to our results may skip this subsection, taking Propositions 2.5 and 2.6 as given.
For convenience, we first state a specific form of ONS's O(n In T') regret bound, which is later used MetaGrad and in our analysis. See Algorithm in Appendix B.1 for the pseudocode of ONS.
Proposition 2.5. Let W C R be closed convex set whose fz-diameter is at most W > Let W1...., WT and 91.... be vectors in Rn satisfying the following conditions for some G, > Wt E W, 11ge|12 S G, and maxt (w' - -w,9t)
w' E EWW H for 1,..., T.
(3)
Take any E (0, 5H. 11 and define loss functions ff: : W fort- 1..... T as follows:
(w) == -n/ww, w. ge) + +12 (w: w. ) for any W.
(4)
Let wI...., w/ W be the outputs of ONS applied f7 f Then, for any u W, holds that
WGT
Σ (()(m -f fl(4) 0 nnn
Hn
Next, we describe MetaGrad (see Algorithm 2 in Appendix B.3), which we apply to the following general OCO problem closed convex set, W R For = 1...., .,. T, select wy E W based on information obtained up to the end of round - 1; then, we incur f((w)) and observe a subgradient, Øi (w:),, where fe: W R denotes the fth convex loss function. We assume that W and ge fort=1,.... T satisfy the conditions in (3). Our goal is to make the regret with respect to ft, i.e., (f(()( - fu)), as small as possible for any comparator E W.
MetaGrad maintains expeesss, each of whom is associated with of OIn T') different learning rates 7) E (0, 5Ø. Each -xeepett applies ONS to loss functions fo of the form (4), where w, E W
5

---

is the fth output of MetaGrad and E (w)(w) outputs w/ of 1--experts (which are computed based on information up to round 1), MetaGrad computes W, E W by aggregating them via the exponentially weighted average (EWA).
) is given feedback. In each round t. given the
For any comparator E W, define Ri = Ei=((u all functions ft are convex, the regret with respect to ft. or Σ ( fi()),, is bounded by RG from above. Furthermore, from the definition of ft', we can decompose R% as follows:
u, 9t) and V = Ei=((ue (wr u, ge)² Since
Zero by (4)
Ry El (((() + 1
" Σ (f(w))-((())
EVr(NN)- S( + nVT.
t=1
which simultancously holds for all 1 > The first summation on the right-hand side, i.c., the regret of EWA compared to wp, is indeed as small as OI IT),, while Proposition 2.5 ensures that the second summation is O(n In 7). Thus, the right-hand side is O nnnTT + v/7)) If we knew the
true V value, we could choose 7) In impossible as we do not know any of and wi beforehand. However, we can show that at least one of OIn I') values of 7) leads to almost the same regret, eschewing the need for knowing Vi. Formally, MetaGrad achieves the following regret bound (ef. Van Erven et al. [56, Corollary 8)).
achieve O D(vnn V7). This might seem
Proposition 2.6. Let W S IR' be given as in Proposition 2.5. Let Wi...., WT E W be the outputs of MetaGrad applied to convex loss functions fi..... fr: W - R. Assume that for every t = 1.... T, subgradient 9t E 0f{(w, (we) satisfies the conditions (3) in Proposition 2.5. Then, it holds that
R7 = 0 =
WGT
W WGT
V7 + Hn In
Hn
Hn
We outline how this result applies to exp-concave losses. Taking W, G, and H to be constants and
ignoring the additive term of On In(T/n)) for simplicity, have Rt. = O / T' V7). afl fr a-exp-concave for some 1/W),,, then f((w)) fa(u) (w, u. u.) a (w: u, 9t) holds (e.g., Hazan [26, Lemma 4.3]). Summing this over t and using Proposition 2.6 yield
-(M(wa)) fe()) s itz
a Vr = -OVTnnn V VV?) S
n a
2
where the last inequality due /ar br S a for any a 2 0, b 0, and x 2 Remarkably, MetaGrad achieves the ( In T) regret bound without prior knowledge of a, whereas ONS achieves this regret bound by using the value. Furthermore, even when some fi are not exp-concave, MetaGrad still enjoys regret bound of O(VTIn In In T) [56, Corollary 8]. As such, MetaGrad can automatically adapt to the unknown curvature of loss functions (at the cost of the negligible In In T factor), which is the key feature of universal online learning methods.
ab
3 An efficient O In T) rregret method based on ONS
This section presents an efficient logarithmic-regee method for online inverse linear optimization. Our method is remarkably simple: we apply ONS to exp-concave loss functions defined similarly to the neeeperrs'' losses (4) used in MetaGrad. The proof very short given the ONS's 's regret bound in Proposition 2.5. Despite this simplicity, we can achieve the regret bound of On In T), which matches the best-known regret upper bound of Gollapudi al. [25], with far lower per-round complexity.
Theorem 3.1. Assume that for every
.......22. T, action Ht E Xe is optimal for e* E O. Let CI...., eT E θ be the outputs of ONS applied to loss functions defined as follows for = 1,......
(c(c) = (n - c, c, σz) + 172 (Ce c, it =2,² for all E O
(5)
where 9t E arg max, x, (Ce, and we set = 5B.
1 Then, for R and R in (2), it holds that
(DKT)
RG R = o Bn In
Bn
'In Van Erven al. [56. Corollary 8J, the multiplicative factor of the second term and denominators Hn In are replaced with WG and n, respectively. We modify it to obtain the above bound; see Appendix B. This is equivalent to MetaGrad with single 5 expert applied to the suboptimality losses. Ei,..., Sr.

---

Proof. Consider using Proposition 2.5 in the current setting with W = θ w = w = ct 91 = & PT-J,, u c¹, W = D. D. tively, ensures (0r -0- 24 x4. 2 0, we have (êt (ôt-c", 24 -xx) < ((; c" _t vx) due to Assump- tion 2.2. Therefore, 129 > (Cr c Gt xx)) and Vf = E (c: (0-cc" & xz)² satisfy Vf" S
K, and H B. Since the optimality of Iy and é, for c* and é, respec-
BRG By using this and Proposition 2.5 with v = 5B" for some constant CoNs > 0, it holds that
7em (5)
T ( Pe = Σ -
(6)) (((c))
DKTT Bn
RG.
+
BBi S 5BCoNsh In
and rearranging the terms yields Re = ( In(
DKT Bu
))? This also applies to R& S RGy
Time complexity. We discuss the time complexity of the method. Let Tsolve be the time for solving linear optimization to find & and TG-proj the time for the generalized projection onto θ used in ONS (see Appendix B. In each round t, we compute ig E arg max (C,, x) in Twolve time; after that, the ONS update takes ( + TG-proj) time. Therefore, it runs in O( Tanlve + n² + TG.paa) time per round, which is independent of T. If problem (1) is an LP. Tsolve equals the time for solving the LP (ef. Cohen et al. [16] and Jiang et al. [33]). Also, TG-proj is often affordable as + is usually specified by the learner and hence has simple structure. For example, if θ the unit Euclidean ball, the gener- alized projection can be computed in (nn²) time by singular value decomposition (e.g., Mhammedi al. [41, Section J.. We may also use the muasi-Newton-type method for further efficiency [40].
Robustness to suboptimal feedback with MetaGrad
In practice, assuming that the agent's actions are always optimal is unrealistic. This section discusses how to handle suboptimal feedback effectively. Here, we let H, E X, denote arbitrary action taken by the agent, which the learner observes. Now that may have nothing to do with c*, we can longer ensure meaningful bounds on the regret that compares â. with optimal actions. For example, if revealed actions I, remain all zeros for / = 1,..., T, we can learn nothing about ct, and hence the regret that compares é, with optimal actions grows linearly in T in the worst case. Considering this issue, we highlight that the regret, R. = Ei'(ee" (c", Iz - &t), used here is defined with the agent's 's possibly suboptimal actions 24, not with those optimal for c². Small upper bounds on this regret ensure that, if the agent's ' actions He are nearly optimal for c", so are &t. This regret still satisfies Re: < Pey = Ei= (ce- c², It xie) since â is optimal for à. Additionally, recall that the suboptimality loss, 4, in Definition 2.3 can be defined for any action 2; X, and that le(c*) = maxxex, x) (c", xτ) 2 O indicates the suboptimality of I; for c*. Below, we use AT = = (((c)) to denote the cumulative suboptimality of the agent's actions x4.
In this setting, it is not difficult to show that ONS used in Theorem 3.1 enjoys regret bound that scales linearly with Ar. However, the linear dependence on AT is not satisfactory, as it results in a regret bound of OTT even for small suboptimality that persists across all rounds. The following theorem ensures that by applying MetaGrad to the suboptimality losses, we can obtain a regret bound that scales with VAT.
Theorem 4.1. Let êi,...,,y êr E θ be the outputs of MetaGrad applied to the suboptimality losses, Ei...., lT, given in Definition 2.3. Let iz arg max.ex. (be, for I,...,? T. Then, it holds that
R < Re = o (B
DKT Bn
DKT
+
Bn
Bn
Proof. Similar to the proof of Theorem 3.1, we apply Proposition 2.6 with W = θ wt = ct. St -t Tz, u c², W D. G K, and H B; in addition, 9t = 2, E 06, holds due
We may use any 17 long as 1/B3 holds; n 5B is for consistency with MetaGrad in Appendix B.
7

---

to Proposition 2.4. Thus, Proposition 2.6 ensures the following bound for some constant CMG > 0:
PG S CMG (Vmlm) DKT
DKT
Vf" + BB In
(6)
Bn
Bn
where Rij = - c*, rz)) and Vi = =i== (0) - c². -,- xx)2. In contrast to the case of Theorem 3.1, c", . - zz)² < B(e - -,, - 2z) is not ensured since (c, - c", &t - xx) can be negative due to the suboptimality of 2₁. Instead, we will show that the following inequality holds:
(or c² -h- 211² & B(e - c² -t - vz) + (Be((c).
(7)
If (ē. c² - 2 (7) immediate from (cg - ft - xx)² 2² < B(c; 100---00 c² - and le(c*) 2 0. If (c - c², 31 - 21) < 0. (a c² 8t- z1)² I B B(-(c: (c: - c² 21 - 21)) holds. In addition, we have
fe(c") max (c" x) (c", mz) 2 (c" 2. - 01) 2 (c 21 mz) (c, ft 1---------- xz) (c ((a-c",, c², xt),
=eX;
where the second inequality follows from (è,, dt xτ) 2 0. Multiplying both sides by 2 yields
-2(2 - c², कt zz) & (c) = -(es - c² ft xx) I (ce c², & - 21) - 26 (c')
Thus, (7) holds in any case, and hence Vi S Big + 2BAT. Substituting this into (6), we obtain
(1 Bn In
(KKT)
(in + +2Ar) + BB In ( (DKT)
Ro S CmG
Bn
Bn
Bn
We assume Po5 > O; otherwise, the trivial bound of itş" S 0 holds. By the subadditivity of x + vv for r 2 0, we have Ro $ VaRi + b, where a = C Bn In DKT) and b /2aaz + a OMG" x S 3(var+b) 3 = (v/z- +3 S (a+b)
Since x I vax+ implies x = 3 3
for any a, b. 0, obtain Rg (a b) O Bn Bnln( DKT) V A Bn In DKT
If every Fe is optimal, i.c., AT = O, the bound recovers that in Theorem 3.1. Note that MetaGrad requires prior knowledge of Ar; it automatically achieves the bound that scales with VAr. analogous to the original bound in Proposition 2.6 that scales with /VF. Moreover, refined version of MetaGrad [56] enables us to achieve a similar bound without prior knowledge of K, B, or T (see Appendix B.4). Universal online learning methods shine in such scenarios where adaptivity to unknown quantities is desired. Another noteworthy point is that the last part of the proof uses the
self-bounding technique [23, 60, 66). Specifically, we derived iGy Sa + b from iGG S / + b. where the latter means that itg is upper bounded by a term of lower order in P&. itself, hence the name boundioun...g. We expect that the combination of universal online learning methods and self-bounding, through relations like V < RG + AT used above, will be useful technique for deriving meaningful guarantees in online inverse linear optimization.
Time complexity. The use of MetaGrad comes with slight increase in time complexity. First, as with the case of ONS, i E arg max_ex, (ct, is computed in each round, taking Tsolve time. Then, each 1-expert performs the ONS update, taking O(n² + To praj) time. Since MetaGrad main- tains (In T) distinct values, the total per-round time complexity is 0 + (n² + TG-mij) In T).. If the OTTG-poo In T) factor is a bottleneck, we can use more efficient universal algorithms [41, 61] to reduce the number of projections from (In 7) to Moreover, the O(n)) factor can also be reduced by sketching techniques (see Van Erven al. [56, Section 5]).
4.1 Online-to-batch conversion
We briefly discuss the implication of Theorem 4.1 in the offline setting, where feedback follows some underlying distribution. As noted in Section 2.2, the bound in Theorem 4. 1 applies to the regret with respect to the suboptimality loss, Σiz (4)(2) - (c))),, since it is bounded by Reç from above. Therefore, the standard maline-to-bated conversion (e.g., Orabona [45, Theorem 3.1]) implies the following convergence of the average prediction in terms of the suboptimality loss.
'Here, we can simultaneously achieve FG" O(DK In thanks to MetaGrad's guarantee [56.
Corollary 8J, which can yield stronger bound when is huge.
8

---

Corollary 4.2. For any non-empry and compact X C R", 2 E X. and E O define the correspond- ing suboptimality loss as (c)=(c)= == m x (c, x²) (c, 2). Let A 0 and define X as the set of observations (X,4) with bounded suboptimality, xx I A. Assume that {( drawn i..d. from some distribution on Xs (hence DT I AT). Let cI,..., Cer E Q be the outputs of MetaGrad applied to the suboptimality losses & Ex.,,, fort I...., T. Then, it holds that
ot= are
E
Σ t=1
)
T
-
-xx((o)
-0
Bn T
In
DKT
+
ABn
In
DKT
T
Bn
T
Bn
Bärmann al. [4, Theorem 3.14] also obtained similar offline guarantee via the online-to-batch conversion. Their convergence rate is O (T) even when A = 0, whereas our Corollary 4.2 offers the
faster rate of (('12) if A = O. also applics to the case of A > O, which is important in practice because stochastic feedback is rarely optimal at all times. We emphasize that if regret bounds scale linearly with Ay, the above online-to-bate batch conversion cannot ensure that the excess suboptimality loss (the left-hand side) converge zero as T - O. This observation lends support the importance of the v Ad-dependent regret bound we established in Theorem 4.1.
(n)) lower bound
We construct an instance where any online learner incurs an 22(n) regret, implying that the O(n In T)
upper bound tight up an (In T) factor. More strongly, the following Theorem 5. shows that, for any B > 0 that gives the tight upper bound in Assumption 2.2, no learner can achieve regret smaller than 1 which means that the Bn factor in our Theorem 3.1 inevitable.
Theorem 5.1. Let n be a positive integer and θ = +
For any 2 n, B > 0, and
the learner's 's outputs 61,..., êr O there exist c² E and XI,...; XT C R such that
Bn
max max (c - -,, - x²) c, E 0, E x,} = B and E R c.I....? T
2 4
hold, where R9. = -Th -t=i (ct 2z ii), E angmax,e. (ct 2)), St arg max X, (Ce, 2). and the expectation is taken over the learner's 's possible randomness.
Proof. We focus on the first rounds and show that any learner must incur Bn in these rounds; in the I
remaining rounds, we may use any instance since the optimality of x4 for e* ensures (c" 34 i,) 2 0.
for & t). where sii) B denotes the ith element of x. That is, X, is the line segment on the /th axis from I v to 7 Vn. Then, max (c- x -a)) : c, c' E 0,,, x' E X, = B holds for each f t L..... n. Let e" E θ be a random vector such that each entry is /n Vn with probability 1. which is drawn indepen- dently of any other randomness. Then, the optimal action, Te E X₁, which zero everywhere except c'(t) that its ith coordinate equals (e)( 4 Vn. achieves (c", = 4-
For t ......,,, n, let X, = { {x E TR. : -n S x(t) S 4 Vn, xx1)
B
B Note that the learner's 's tth predic- tion é independent of c² (t) since it depends only on past observations, {(X,, [ which have no information about c* (t). Thus, Lt E arg x, (c,, x) is also independent of c* (t), and hence
B
1
1
B 4
El(c", 22 f.)l El(c", mx)1 Ellc", 2,)
(t
4
2
vn
Vn
where the expectation is taken over the randomness of c" This implies that any deterministic learner incurs En in the first rounds in expectation. Thanks Yao's minimax principle [62], we can 4
conclude that for any randomized learner, there exists e" E θ such that E R Bx holds. O
N
In the above proof, we restricted X1,... XT to line segments so that each I, E arg max, (c", reveals nothing about e* (t (1, "h....,,"((n) (n.) Whether a similar lower bound holds when all X, are full- dimensional remains an open question. Another side note is that the 2(n) lower bound does not contra- dict the (vT)) upper bound of Bärmann et al. [4]. Their OGD-based method indeed achieves a regret bound of tively. In the above proof, T 2 n, D 2 1, and K 2 2
where D and K are upper bounds on the fz-diameters of θ and X,, respec- B /n hold, implying that their regret upper bound
is DK VTVT& 2 Bn. Hence, the ?(n)) bound and their O(DK (DDKVT)-un upper bound are compatible.

---

6 Conclusion and discussion
We have presented an efficient ONS-based method that achieves an O In -rregrtt bound for online inverse linear optimization. Then, we have extended the method to deal with suboptimal feedback based on MetaGrad, achieving an On In T V In -regret bound, where Ây is the cumulative suboptimality of the agent's actions. Finally, we have presented a lower bound of ((n). which shows that the (n In T) upper bound is tight up to an O(n factor. Regarding limitations, our work is restricted to the case where the agent's s optimization problem is linear, mentioned in Footnote I; how to deal with non-linearity an important direction for future work. In online portfolio selection, ONS is efficient but inferior to the universal portfolio algorithm regarding the dependence the gradient norm [57]. Exploring possible similar relationships in online inverse linear optimization is left for future work. Last but not least, closing the ( 7) gap between the upper and lower bounds is an important open problem. Interestingly, if all X, are line segments as in Section 5 and the learner can observe X, in the beginning of round t, the algorithm of Gollapudi et al. [25, Theorem 5.2] offers regret upper bound of O( log" n),, which is finite and polynomial in n. We also provide an additional discussion on a finite regret bound for the case of n = 2 in Appendix C.
Acknowledgments and Disclosure of Funding
SS was supported by JST ERATO Grant Number JPMJER NMMJER1933.. TT was supported by JST ACT-X Grant Number JPMJAX210E and ISPS KAKENHI Grant Number 2325K23852. HB was supported by IST PRESTO Grant Number JPMJPR24K6. TO was supported by JST FOREST Grant Number JPMJFR232L and JSPS KAKENHI Grant Number JP22K17853.
References
[1] Y. Abbasi-Yadkorf D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312-2300. Curran Associates, Inc., 2011 (cited on page 3).
[2] R. K. Ahuja and J. B. Orlin. Inverse optimization. Operations Research, 49(5):771-783 2001
(cited pages 3).
[3] A. Aswani, Z.-J. (Max) Shen, and A. Siddiq. Inverse optimization with noisy data. Operations Research, 66(3):870-88) 892, 2018 (cited on page 3).
[4] A. Bärmann, A. Martin, S. Pokutta, and O. Schneider. An online-learning approach to inverse 11f0: 2020 (cited on pages 2-5, 9, 21, 28).
optimization.
[5] A. Bärmann, S. Pokutta, and O. Schneider. Emulating the expert: Inverse optimization through online learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 400-410. PMLR, 2017 (cited on pages 2-5, 21).
[6] D. Bertsimas, V. Gupta, and I. C. Paschalidis. Data-driven estimation in equilibrium using inverse optimization. Mathematical Programminng 153()):595 633, 2015 (cited on pages
3).
[7] O. Besbes, Y. Fonseca, and Lobel. Online learning from optimal actions. In Proceedings of the 34th Conference on Learning Theory, volume 134, pages 586-586. PMLR, 2021 (cited on pages 2-5, 21, 26).
[8] O. Besbes, Y. Fonseca, and I. Lobel. Contextual inverse optimization: Offline and online learning. Operations Research,
443, 2025 (cited on pages 2-5, 21, 26-28).
[9] J. R. Birge, A. Hortaçsu, and J. M. Pavlin. Inverse optimization for the recovery of market structure from market outcomes: An application to the MISO electricity market. Operations Research, 65(4):837 885,, 2017 (cited on page 2).
[10] J. R. Birge, X. Li, and C. Sun. Learning from stochastically revealed preference. In Advances in Neural Information P Processing Systems, volume 35, pages 35061-35071. Curran Associates, Inc., 2022 (cited on page 3).
[11] Burton and P. L. Toint. On an instance of the inverse shortest paths problem. Mathematical Programming, 53(1):45-65) (:45661, 1992 (cited on page 1).
10

---

[12] T. C. Y. Chan, M. Eberg. K. Forster, C. Holloway, L. Ieraci, Y. Shalaby, and N. Yousefi. An inverse optimization approach to measuring clinical pathway concordance. Management Science,
(000):882211900
2022 (cited on page 2).
[13] T. C. Y. Chan, T. Lee, and D. Terekhov. Inverse optimization: Closed-form solutions, geometry, and goodness of fit. Management Science, 65(3):1115-1135,, 2019 (cited on page 1).
[14] T. C. Y. Chan, R. Mahmood, and I. Y. Zhu. Inverse optimization: Theory and applications.
Operations Research, 73(2):1046-1074, 2025 (cited on page 1).
[15] V. X. Chen and F. Karzan. Online convex optimization perspective for learning from dynamically revealed preferences. arXiv:2008. 1008.10440 10460, 2020 (cited on page 3).
[16] M. B. Cohen, Y. T. Lee, and Z. Song. Solving linear programs in the current matrix multiplica- tion time. Journal of the ACM, 68(1):1-39, 2021 (cited on page 7).
[17] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions Information Theory, 42(2))348-366 1996 (cited on page 4).
[18] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Conference on Learning Theory, pages 355-366. PMLR, 2008 (cited on page 3).
[19] J. M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathe- matics, 1644,,441664, 1966 (cited on page 5).
[20] C. Dong, Y. Chen, and B. Zeng. Generalized inverse optimization through online learning. In Advances in Neural Information Processing Systems, volume 31, pages 86-95, Curran Associates, Inc., 2018 (cited on page 3).
[21] V. Feldman, C. Guzman, and S. Vempala. Statistical query algorithms for mean vector estima- tion and stochastic convex optimization. arXiv: /5/2.09// /70 2015 (cited on page 22). [22] M. Frank and P. Wolfe, An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1 3(1-2)995-110, 1956 (cited on page 22).
[23] P. Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In Proceed- ings of the 27th Conference on Learning Theeory volume 35, pages 176-196. PMLR, 2014 (cited pages 3, 8).
[24] D. Garber and N. Wolf. Frank-Wolfe with nearest extreme point oracle. In Proceedings of the 34th Conference on Learning Theory, volume 134, pages 2103-2132 PMLR, 2021 (cited on page 22).
[25] S. Gollapudi, G. Guruganesh, K. Kollias, P. Manurangsi, R. Paes Leme, and J. Schneider. Contextual recommendations and low-regret cutting-plane plane algorithms. In Advances in Neural Information Processing Systems, volume 34, pages 12498-22508. Curran Associates, Inc.,
2021 (cited on pages 2-6, 10, 21, 22, 26, 28).
[26] E. Hazan. Introduction to online convex optimization. arXiv:1909.05207..0 2023. https://arxiv. org/abs/1 (01.999990202. v05207233 (cited on pages 2, 5, 6. 22-24).
[27] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimiza- tion. Machine Learning, 69(2):169-192 69-1699 2007 (cited on pages 2, 3).
[28] C. Heuberger. Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization, 8(3):329-361, 2004 (cited on page 1).
[29] G. Iyengar and W. Kang. Inverse conic programming with applications. Operations Research Letters, 33(3):3193333
2005 (cited on page 3).
[30] S. Jabbari, R. M. Rogers, A. Roth, and S. Z. Wu, Learning from rational behavior: Predicting solutions to unknown linear programs. In Advances in Neural Information Processing Systems, volume 29, pages 1570-1578, Curran Associates, Inc., 2016 (cited on page 3).
[31] M. Jaggi. Revisiting Frank-Wolfe. Projection-free free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 427-435. PMLR, 2013 (cited on page 22).
[32] R. Jézéquel, D. M. Ostrovskii, and P. Gaillard. Efficient and near-optimal online portfolio 2022 (cited on page 4).
selection. arXiv:2209.1339
[33] S. Jiang, Z. Song, O. Weinstein, and H. Zhang. A faster algorithm for solving general LPs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 823 832. ACM, 2021 (cited on page 7).
[34] A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research, 3(Nov):423 440, 2002 (cited on page 4).
11

---

[35] A. Keshavarz, Y. Wang, and S. Boyd. Imputing convex objective function. In Proceedings of the 2011 IEEE International Symposium on Intelligent Control, pages 613-619. IEEE, 2011 (cited on page 3).
[36] A. Krishnamurthy, T. Lykouris, C. Podimata, and R. Schapire. Contextual search in the presence of irrational agents. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 910-918. ACM, 2021 (cited on page 3).
[37] S. Lacoste-Julien and M. Jaggi. On the global linear convergence of Frank-Woll optimization variants. In Advances in Neural Information Processing Systems, volume 28, pages 496-504. Curran Associates, Inc., 2015 (cited on page 22).
[38] A. Liu, R. Paes Leme, and J. Schneider. Optimal contextual pricing and extensions. Proceed- ings of the 2021 ACM-SIAM Symposium Discrete Algorithmss pages 1059-1078. SIAM, 2021 (cited on page 3).
[39] Y. Long. T. Ok, P. Zattoni Scroccaro, and P. Mohajerin Esfahani. Scalable kernel inverse optimization. In Advances in Neural Information Processing Systems, volume 37, pages 99464- 99487. Curran Associates, Inc., 2024 (cited on pages 2, 3).
[40] Z. Mhammedi and K. Gatmiry. Quasi- steps for efficient online exp-concave optimiza- tion. In Proceedings of the 36th Conference on Learning Theory, volume 195, pages 4473-
4503. PMLR, 2023 (cited on page 7).
[41] 7. Mhammedi, W. M. Koolen, and 'T Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Conference on Learning Theory, volume 99, pages 2490-2511, 1. PMLR, 2019 (cited pages 7, 26).
[42] S. K. Mishra, A. Raj, and S. Vaswani. From inverse optimization feasibility to ERM. In Proceedings of the 41 International Conference pages 35805-35825 PMIRR, 2024 (cited on page 3).
Machine Learning, volume 235,
[43] P. Mohajerin Esfahani, S. Chafieezadeh-Abadel G. A. Hanasusanto, and D. Kuhn. Data-driven inverse optimization with imperfect information. Mathematical Programming, 167:191-234,
2018 (cited on pages 2, 3, 5).
[44] A. Y. Ng and S. J. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning, pages 663-670. Morgan Kaufmann Publishers Inc., 2000 (cited on page 2).
[45] F. Orabona. A modern introduction online learning, arXiv: 2023. https://arxiv. org/abs/19 12.11113v6 (cited on page 8).
[46] R. Paes Leme, C. Podimata, and J. Schneider. Corruttion-obuust contextual search through density updates. In Proceedings of the 35th Conference on Learning Theory, volume 178, pages 3504-3505. PMLR, 2022 (cited on page 3).
[47] R. Paes Leme, C. Podimata, and J. Schneider. Density-based algorithms for corruption-robust contextual search and convex optimization. arXiv:2206. 075228 2025 (cited on page 3).
[48] R. Paes Leme and J. Schneider. Contextual search via intrinsic volumes. SIAM Journal on Computing, 51)) 1096-1 125, 2022 (cited on page 3).
[49] S. Sakaue, H. Bao, and T. Tsuchiya. Revisiting online learning approach to inverse linear opti- mization: A Fenchel- of the 28th International Conference on Artificial Intelligence and Staristics, volume 258, pages 46 54, PMLR, 2025 (cited on pages 3, 5).
loss perspective and gap-dependent regret analysis. In Proceedings
[50] L. Shi, G. Zhang. H. Zhen, J. Fan, and J. Yan. Understanding and generalizing contrastive learning from the inverse optimal transport perspective. In Proceedings of the 40th International Conference Machine Learning, volume 202, pages 31408 1140003-2221 31421. PMLR, 2023 (cited on
page 2).
[51] C. Sun, S. Liu, and X. Li. Maximum optimality margin: A unified approach for contextual linear programming and inverse linear programming. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages
PMLR, 2023 (cited on
page 3).
[52] Y. Tan, D. Terekhov, and A. Delong. Learning linear programs from optimal decisions. In Advances in Neural Information Processing Systems, volume 33, pages 19738-19749. Curran Associates, Inc., 2020 (cited on page 3).
[53] A. Tarantola. Inverse problem theory: Methods for data fitting and model parameter estimation. Geophysical Journal International, 9471):167-167, 1988 (cited on page l).
12

---

[54] C.-E. Tsai, H.-C. Cheng, and Y.-H. Li. Online ceff-concordant and relatively smooth mini- mization, with applications to online portfolio selection and learning quantum states. In Pro- ceedings of the 34th International Conference on Algorithmic Learning Theory, volume 201, pages 1481-1483, PMIR, 2023 (cited on page 4).
[55] T. van Erven and W. M. Koolen. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems, volume 29, pages 3666-3674. Curran Associates, Inc., 2016 (cited on pages 2, 3, 25).
[56] T. van Erven, W. M. Koolen, and D. van der Hoeven. MetaGrad: Adaptation using multiple learning rates in online learning. Journal of Machine Learning Research, 22(161): 2021 (cited on pages 2, 3, 5, 6, 8, 22, 26).
[57] T. van Erven, D. van der Hoeven, W. Kotlowski, and W. M. Koolen. Open problem: Fast and optimal online portfolio selection. In Proceedings of the 33rd Conference on Learning Theory, volume 125, pages 3864-3869. PMLR, 2020 (cited pages 4, 10).
[58] G. Wang. S. Lu, and Zhang. Adaptivity and optimality: A universal algorithm for online con- vex optimization. In Proceedings of the 35th Uncertainty in Artificial Intelligence Conference, volume 115, pages 559-668. PMLR, 2020 (cited on pages 3, 25).
[59] A. Ward, N. Master, and N. Bambos. Learning to emulate an expert projective cone scheduler. In Proceedings of the 2019 American Control Conference, pages 292-297. IEEE, 2019 (cited
on page 3).
[60] C.-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the s1 Conference On Learning Theory, volume 75, pages 1263-1291. PMLR, 2018 (cited pages 3, 8).
[61] W. Yang, Y. Wang, P. Zhao, and L. Zhang. Universal online convex optimization with 1 projection per round. Advances in Neural Information Processing Systems, volume 37, pages 31438-31472. Curran Associates, Inc., 2024 (cited on page 8).
[62] A. C.-C. Yao. Probabilistic computations: Toward unified measure of complexity. In Pro- ceedings of the 18th Annual Symposium on Foundations of Computer Science, pages 222-227.
IEEE, 1977 (cited page 9).
[63] P. Zattoni Scroccaro, B. Atasoy, and Mohajerin Esfahani. Learning in inverse optimization: Incenter cost, augmented suboptimality loss, and algorithms. Operations Research, 100):1119, 2024 (cited on page 3).
[64] L. Zhang, G. Wang, J. Yi, and T. Yang. A simple yet universal strategy for online convex optimization. In Proceedings of the 39th International Conference Machine Learning, volume 162, pages 26605-26623. PMLR, 2022 (cited on page 3).
[65] J. Zimmert, N. Agarwal, and S. Kale. Pushing the efficiency-regret Pareto frontier for online learning of portfolios and quantum states. In Proceedings of the 35th Conference on Learning Theory, volume 178, pages 182-226. PMLR, 2022 (cited on page 4).
[66] J. Zimmert and Y. Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22((8): 1499, 2021 (cited on pages 3, 8).
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Abstract, Section 1, and Section 1.1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 2.2 for assumptions, Sections 3 and for the computational complexity, Section for limitations regarding the lower bound, and Section 6 for additional discussions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
See Section 2.2 for assumptions. All theorems are followed by proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix D provides detailed description of our preliminary experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The source code and its readme file are available at https://githab..om//sssk.e online-inverss leaeeelinnar--eee cetaaroopimizztionn code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines htttpss/niis..c//ublic
Shiddss/oodeeubmissioonooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (hitps: www.bbiicggiiee/oeeeSuuuueee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Table 2 reports the results with the mean and standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is advance the field of Machine Learning, There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assetts are released, the license, copyright information, and terms of use package should be provided. For popular datasets, paperswithcode. wtt.://cooeeoooo/ttteeeeeeeeeeee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy Ottp:://eeeii.ccccccocceeeeessss for what should or should not be described.
20

---

A Detailed comparisons with previous results
Below we compare our results with Bärmann et al. [4, 51, Besbes et al. [7, 8], and Gollapudi et al. [25].
Bärmann et al. [4, 5] used " as the performance measure, as with our Theorems 3.1 and 4.1, and provided two specific methods. The first one, based on the multiplicative weights update (MWU), is tailored for the case where O is the probability simplex, i.e., Q = { E IR" c 2 0, ||c|]] = 1}. The authors assumed a bound of Ko > on the -ia-mmees of X, and obtained regret bound of O T n). The second one is based the online gradient descent (OGD) and applies to general convex sets θ The authors assumed that the fz-diameters of è and X, are bounded by D > 0 and K > 0, respectively, and obtained a regret bound of O(DK vT). In the first case, our Theorem 3.1 with B = Kx. D = 22, and K <. 2/nK offers a bound of O(K In(T/ in the second case, we obtain a bound of O(DKn (n(T /n)) by setting B DK. In both cases, our bounds improve the dependence on T from VT to In T, while scaled up by a factor of n, up to logarithmic terms. Regarding the computation time, their MWU and OGD methods run in ( + TFp + n) time per round, where pnoj is the time for the Fuclidean projection onto θ, hence faster than our method. Also, suboptimal feedback is discussed in Bärmann et al. [4, Sections 3.1]. However, their bound does not achieve the logarithmic dependence on T even when AT = O, unlike our Theorem 4.1.
Besbes et al. [7, 8] used Re as the performance measure, which is upper bounded by ftz They assumed that c" lies in the unit Euclidean sphere and that the bg fy-diameters of X, are at most one. Under these conditions, they obtained the first logarithmic regret bound of O(n" In T). By applying Theorem 3.1 to this case, we obtain bound of On In (T[//n)), which is better than their bound by a factor of n As discussed in Section I, their method relies on the idea of narrowing down regions represented with (T) constraints, and hence it seems inefficient for large T; indeed Besbes et al. [8, Theorem 4] only claims that the total time complexity is polynomial in n and T. Considering this, our ONS-OoN based method is arguably much faster while achieving the better regret bound.
On the problem setting of Besbes et al. 17, 8). As mentioned in Remark 2.1, the problem setting of Besbes et al. [7. 8] is seemingly different from ours. In their setting, in each round 4, the learner first observes (Xt: ft), where fe= X, + RR' is called context function. Then, the learner chooses & E X,, and receives an optimal action 2e E arg max f((z)) as feedback. It is assumed that the learner can solve x (c, fe(z)) for any c E Rn and that all ft are 1-Lipschitz, i.c.. [lff(()) - ft (z') 2| S || - =x'll2 for all x I' E X,, We note that our methods work in this setting, while the presence of ft might make their setting appear more general. Specifically, we redefine X, as the image of ft, i.e., { f((r)) x E X2 }. Then, their assumption ensures that we can find f( E X; that maximizes X, 3 E (Ć,, (), and the lz fz-diameter of the newly defined X, is bounded by due to the 1-Lipschitzness of ft. Therefore, by defining 9r- = fe(@.) ( (x())) and applying it in Theorems 3.1 and 4.1, we recover the bounds therein on Σ (0g - c², f fe fe(2r)), with D, K, and B being constants. The bounds also apply to the regret, Di=1("', (c - fe((:)). used in Besbes et al. [7, 8). Additionally, Besbes et al. [7, 8] consider (possibly non-convex) initial knowledge set Co C T that contains c². We note, however, that they do not care about whether predictions é lie in Co or not since the regret, their performance measure, does not explicitly involve é. Indeed, predictions é that appear in their method are chosen from ellipsoidal cones that properly contain Co in general. Therefore, our methods carried out on a convex set θ 2 Co work similarly in their setting.
Gollapudi et al. [25] studied essentially the same problem as online inverse linear optimization under the name of contextual recommendation (where they and Besbes et al. [7, 8] appear to have been unaware of each other's 's work). As with Besbes et al. [7, 8]. Gollapudi et al. [25] assumed that c* and Xı,..., Tr. lie in the unit Euclidean ball, denoted by B Similar to Besbes al. [7, 8), their method maintains the region K,, which is the intersection of hyperplanes { {c E Rdd (c- 2 I. - t.) 2 }} for s = 1,..., t - 1, and sets é to the centroid of K, + 1 BB", where + is the Minkowski sum. As regards the regret analysis, their key idea is to use the approximate Grünbaum theorem: whenever the learner incurs (c", .z - )2) 2 1 Vol K, + BB)) decreases by constant factor, where Vol denotes 7. the volume. Consequently, Vol(K1 + ABT) /Vo(/VV + AB") X T implies the regret bound of
Ry = E, xt - ..)) O(n 7). As such, the per-round complexity of their method also inherently depends on T, and Gollapudi et al. [25, Section 1.2] only claims the total time complexity of poly(n, T). In this setting, our ONS- method achieves regret bound of O( (T//n)) and is arguably more efficient since the por-round complexity is independent of T.
21

---

Algorithm Online Newton Step
Set y 7= min a.. E włyz Ao Ein, and w1 W.
2: for 1,..., T
3:
Play we and observe qt.
4: A <- A + (((w))qq((p))
W++1 arg min min Wr - Vv(())) w wll w neww EW]. Generalized projection.
5:
Estimating the per-round complexity of Gollapudi al. [25]. As described above, the method of Gollapudi et al. [25] requires ê, for each f, and hence the per-round complexity involves Tsolve. the time to solve maXxeX, ()).).. Aside from this, its per-round complexity is dominated by the cost for computing the centroid of K2 + JB", where K₁ is represented by O(T) hyperplanes. It is known that the problem of exactly computing the centroid #P-hard in general, but we can approximate it via sampling with a membership oracle of K2 + LB".. To the best of our knowledge, computing point that is s-close to the centroid takes 0(n²/e" membership queries, up to logarithmic factors [21, The- orem 5.7], and it natural to set E = 1/7 to make the approximation error negligible. Thus, it takes O membership queries. Regarding the complexity of the membership oracle, naively checking whether a given point satisfies all the O(T) linear constraints of K₁ takes O(Ti')) time. Handling the Minkowski sum with 1B would complicates the procedure, though it can be done in poly(n, T) time by using, for example, Frank- moonk--ooleetppp algorithms [22, 24, 31, 37J. For now, O(n'') would be reasonable (optimistic) estimate of the complexity of the membership oracle. Consequently, the total per-round complexity of their method is estimated to be (Tsalve + n T²) (or higher).
B Details of ONS and MetaGrad
We present the details of ONS and MetaGrad. The main purpose of this section is to provide simple descriptions and analyses of those algorithms, thereby assisting readers who are not familiar with them. As in Appendix B.4, we can also derive regret bound of MetaGrad that yields similar result to Theorem 4.1 directly from the results of Van Erven al. [56].
First, we discuss the regret bound of ONS used by r7-experts in MetaGrad, proving Proposition 2.5. Then, establish the regret bound of MetaGrad in Proposition 2.6.
B.1 Regret bound of ONS
Let In E _ax= denote the identity matrix. For any A, B E R"X*, A B means that A B is positive semidefinite. For positive semidefinite A E RRan let ||0|| = VxT Ax for x E IR².
Let W C R" be a closed convex set. A function q W + R is a-exp-coneave for some a
if W э w + e eaq((w) is concave. For twice differentiable a Vq()))V( The following regret bound of ONS mostly comes from the standard analysis [26, Section 4.4), and hence readers familiar with it can skip the subsequent proof. The only modification lies in the use of 3 instead of W X (defined below), where 3 < W X always holds and hence slightly tighter. This leads to the multiplicative factor of B, rather than DK, in Theorems 3.1 and 4.1.
this is equivalent to V²g(w) >
Proposition B.1. Let W C RT be closed convex set with the lg di-dimeet of at most W > O. Assume that Qt.... :T: W + I are twice differentiable and a-exp-concave for some a > O. Additionally, assume that there exist B, X > 0 such that max (g((w)) (w w.)] S 3 and || (g)(w)))2 < X hold. Let Wi,..., WT E W be the outputs of ONS (Algorithm 1). Then, for any u E W, it holds that
Σ
T (a((w)) - qe())) < 24
In
2X2T
+1 +1).
n
where 7 = min ( , a) is the parameter used in ONS.
22

---

Proof. We first give useful inequality that follows from the a-exp-coneavityy By the same analysis as the proof of Hazan [26, Lemma 4.3], for y S 2. we have
(e(w)) ge (u) - 27
In(1 - 27 (>)):(m) ( (u-n))))
Note that we also have V (ws) (u wi)
- 2y/3 - 1. Since In(1 - 5- x²/4 holds
for x 2 11 applying this with x = (
(u - wx) yields
(wa)) (w) S Vqe(w;) (wh - u)
? (we u) Vgi(w))V(((u)))
uu.
(8)
2
We turn to the iterates of ONS. Since w4+1 is the projection of we A, VVg onto W with
respect to the norm Il- we have [|00411 - u13 I | 2.4 (g((e)) u for urru E W due to the Pythagorean theorem, hence
(wi+1 w) T Ae(wu=1 - 11)
A, 1 1 (gr(wr) -
T
A Wt A, V (wx) - u)
< Wt
7
1 Vui(us) (w)))
= =ww - u) A.(ur - u) (w(( (wi - uu) + 72
Rearranging the terms, obtain
(uc( (w: uu)
(u((w)) T (w:) + 7 (w: -u) AA - u) - 7 (wi+1 uu) Ar(wo+1 u). 2
2y
From A,- = A--1 (e) summing over and ignoring (WTT1 - u) AA(WT++1 - u)
2 0, we obtain
(w: (wu u)
(er( (To,W,)A,T (V))) + $ [[(0 T) Ai (w, u)
27
T
+
7
Σ
(wr- - u) (A: - Ac-1)( u)
2
1=2
Vge(wx) AA- + 2 [w1 -u) T(A Van (wn u)
27
7
Σ (wi - u) T (w: (we u).
Since we have A (wn (e) = Ao =T and = = Wh the above inequality implies
T
[ge(wr) (w: -2)
7
Σ
(we - u) (vr T(wr u)
2
t=1
Vac(wr) (vx(w)) + 2 (w) T. Ao(w1 u)
27
(9)
1
Vac(wr) T "A," Vg((wr) + yE [ml 2112
27
2
T
1
Vgc(wr) Av
+ n
27
27
23

---

The first term in the right-hand side is bounded as follows due to the celebrated elliptical potential lemma (e.g., Hazan [26, proof Theorem 4.5]):
T
Vge(wn) A, Vgc(ur & In det Ar
TX2 + +sln) (uc
E +1) nln
W22 1 (TX² + +6)"
+1). (10)
det Ao S In
n
where we used det Ag = E" and det Ar - det Et (wr(w,)
which follows from the fact that eigenvalues of Σ Ei=1 Vq((wr) Vg((wr)) T are at most TX2. Combining (8), (9), and (10), we obtain
T
T
T
(w)) - (e(u)) -
Vg((wi) (wr - u) -u) 7
Σ
we
u) VV)(())) VQ( (we - u)
2
t=1
1=1
W22222T
n
In
+1) +
2y
as desired.
B.2 Regret bound of 17-expert
We now establish the regret bound of ONS in Proposition 2.5, which is used by 17-exeers in MetaGrad.
Let v) E (0, 577 and consider applying ONS to the following loss functions, which are defined in (4):
(w)) (w: w.gt) + n7² (w> w, 9)) for t = 1....,
As in Proposition 2.5, the lg- di-diemet of W is at most W > 0, and the following conditions hold:
W. E W. 11 S G, and max (w w/ gt) S H for 1....,, T.
w.w EE
From Vf, (w) 11(1 2ng. (we - w)) ge and V2 (w)) = 2n g.9. we have
(f' = =7² 2ng. (wr - w)) 9:9r
112 + HnH 9:0. (1+ + 2nH (w) for all w E W,
2
max (w)) (w w/'l max 79: T (w w/') 201² (gT (w? - wi)) 2
- h + 2
[V) = -1|7(11 - 2ng, (wr - w)) gr |l2 I 17(1 + 2nH
Therefore, f2 satisfies the conditions in Proposition B.1 with a (1+2n 3 =nH + 2nj² H² and
À 7/(1 + 2nHH). Since 1/2 + 2 2nj H 2 holds, we have 7 min a -
Thus, for any 7 (0, ]. we have E
25
1) C
n S G [ 1] and 7d I=2HH
TH Consequently,
19
Proposition B.1 implies that for any u E W, the regret of the neexpert's 's ONS is bounded as follows:
T (V)( -f( S sn(
G2T 49nH²
+ +1) +1) -0(mm) nlm
WGT
Hn ))
In
(11)
B.3 Regret bound of MetaGrad
We turn to MetaGrad applied to convex loss functions fi,..., Fr: W- We here use w, E W and Sr (w:) to denote the ith output of MetaGrad and subgradient of f, at w., respectively, for L = I,...,T. T.. We assume that these satisfy the conditions in (3), as stated in Proposition 2.6.
2 5I for i = 0, L.... _ log, T7. called grid points, and let G C (0, 5 denote the set of all grid points. For each E G. exxpert runs ONS with loss functions f" ...., f to compute w w....., w.. In each round t, we obtain w; by
Algorithm 2 describes the procedure of MetaGrad. Define
24

---

Algorithm 2 MetaGrad
2- i 0, ..... log2 T 1: Pi [+1)(++2] for all T7 E G
2: for = I,..,,
3: Fetch wy from n-exxerts for all r) E g.
4: Play we -neo np? "2
Eneg np?
5: Observe 9r E (m,, and send (w,, 9e) n--experts for all g.
6:
Pi+1 - Pi exp(-f( (w])) (/)) for all E G, where Ze = Eneg Pi exp(-f" (w))).
aggregating the 77-experts" outputs w based on the exponentially weighted average method (EWA). We set the prior as pf (++1)(+22 for all f/i E 9, where = 1+| To
Then, it known
that for every E G, the regret of EWA relative to the n7-expert's choice w. is bounded as follows:
1 Pl
((z log, T
+ ++) log, T +2) +2)
Σ (o) ((())))((ww))) & In S in
(12)
s In
log T ++
where we used C 2 1 in the second inequality. We here omit the proof as is completely the same as that of Van Erven and Koolen [55, Lemma 4] (see also Wang et al. [58, Lemma IJ).
We are ready to prove Proposition 2.6. Let V = Et= (10 u. v. ? By using (we) = 0. (11), and (12), it holds that
Σt
E (u
we u, gt)
+ V1
"
T 7
Σ
(w)) Si +
- + +
Regret WEL. vo?
Regret of quexpent
1
G²T
+1 + +1)) + +
21n
logz T T
In
77
2
49nH²
for all 1) G. For brevity, let
W2CTT
A 21n
log,
+ n T +3
In
+1)+1) 21.
+1
2
49nH²
If we knew Vi, we could set to
A
5HVT to minimize the above regret bound, 7) +ny.
VS
Actually, we can do almost the same without knowing V7 thanks to the fact that the regret bound holds for 1j E G. If 17" < 5H. by construction we have a grid point E such that 17* E [ v). hence
A
A < AAVAV.
Σ m 9. S V
2n
17"
Otherwise, 1)*
holds, which implies V < 25 A. Thus, for no
5H E G, we have
V
5H
T (w) - u, u. S 10V + < 10HA.
1=1
Therefore, in any case, we have
(w. u, 9t) < 3 AV 10H 10HA= = ( obtaining the regret bound in Proposition 2.6.
WGT
WGT Hn
Vi + Hn In
Hn
25

---

Algorithm 3 ((1)0(((e))))) Algorithm for = 2.
Ne.
I: Set C to S².
C
2:
for =.,...,,7??
C++1
3:
Draw é uniformly at random from C,
4: Observe (z).
5: C++1 + C₁ N, N₁ is the normal cone.
Figure Illustration of c², Ct Ne, and C++1-
B.4 Lipschitz adaptivity and anytime guarantee
Recent studies [41, 56] have shown that MetaGrad can be further made Lipschitz adaptive and agnostic to the number of rounds. Specifically, MetaGrad given in Van Erven et [56, Algorithms and 2] works without knowing G. H, or T in advance, while using (a guess of) W. By expanding the proofs of Van Erven al. [56, Theorem and Corollary 8], we can confirm that the refined version of MetaGrad enjoys the following regret bound:
Σ w u, gi) = -
WGT
WGT 11
Vi + Hnln
By using this the proof Theorem 4.1, we obtain
rz) = Bn In
DKT
DKT
(
- 21)
(c c' c',
+
Ar Bu
t=1
1=1
and the algorithm does not require knowing K, B, T, Ar in advance.
C On removing the In T factor: the case of n 2
This section provides additional discussion closing the In T gap in the upper and lower bounds on the regret. Specifically, focusing on the case of n = 2, we provide a simple algorithm that achieves regret bound of (1)) in expectation, removing the 2' factor. We also observe that extending the algorithm to general n 2 2 might be challenging. Note that Gollapudi et al. [25, Theorem 4.1] has already established regret bound of exp(O(n In n2) mentioned in Section 1.2, which implies an rregrrt bound for n 2. The purpose of this section is simply to stimulate discussions on closing the In T' gap by presenting another simple analysis. Below, let E" and S denote the unit Euclidean ball and sphere in I2"" respectively, for any integer n >> 1.
C.1 An O(I)-regret method for n 2
We focus on the case of n and present an algorithm that achieves a regret bound of O(1) in expectation. We assume that all xz E X2 are optimal for c* for t 1, ..... T. For simplicity, additionally assume that all X, are contained in ! and that c* lies S For any non-zero vectors T let (c, c') denote the angle between the two vectors. The following lemma from Besbes et al. [8], which holds for general n 2, is useful in the subsequent analysis.
Lemma C.1 (Besbes et al. [8, Lemma 1]). Let e", c. E S=-1, X, S 1 Bh, E arg max (c", .x), and & E arg maxxxxx (Ce, 2). (fc (4) n/2, holds that (c" It 2.) sinf(cc, C.).
Our algorithm, given in Algorithm 3, is randomized variant of the one investigated by Besbes et al. [7, 8). The procedure is intuitive: we maintain a set C, S Sl that contains c*. from which we draw è uniformly at random, and update C, by excluding the
that is ensured not to contain c* based on the tth feedback (Xe, 2.). Formally, the last step takes the intersection C, and the normal cone Nr, {c R" (c, x) 2 0, Vor X, of X, Tt, which is convex Therefore, every C, is a connected are on T1 and is non-empty due to c* E C, (see Figure 1).
containing et.
Theorem C.2. For the above setting of n 2, Algorithm 3 achieves E [R]]]] 2n.
26

---

C.
C7
Figure 2: An example of C. on S The darker area, A(C,), becomes arbitrarily small as e + O, while
O(c", 2)) does not.
Proof. For any connected are C' C let A(C) E [0, 2n] denote its central angle, which equals its length. Fix C.. If & E C2 n (n(, where int(-) denotes the interior, 2, 2₁ is the unique optimal solution for ét hence (c" 2t _1) = Taking the expectation about the randomness of éc, we have
[E((", 2r da)ه Pr(c, E (nt((N))) (c" x. - 5x) & E C. (in((N))
A(C, \Wi)
EE| (c", -0)) 1 C int([N))]
A(C,)
where we used Pr[e, E C. int( = Pr(e, E C. \M] = A(C, \ \NG)/A(C.) (since the boundary
of NG has zero measure). If A(C,) 2 7/2, from (c* ,t- - S ||ce 122111 - - 1, we have
2 Bliee 3t xx) S
A(C, \M) $ A(c \N)-
π
If ACC.) < T/2, Lemma C.I and é, c* E C. imply (c",x, - #1) s sin (c',,) S sin A(G.). Thus, by using sin (x E R), we obtain
A(C, \M)
El(c", 2 2.11 5
sin A(C,) S A(G, (N)..
A(C,)
Therefore, have El(ce .4 - -.1)l s A(C \M) in any case. Consequently, obtain
T
T
Σ
Elie x x.)1 S Σ A(C, \&) S 2T,,
E
where the last inequality is due to C++1 C, n&G which implies C, C C. and C, (C. \M) for any $ > t, and hence no double counting occurs in the above summation.
C.2 Discussion on higher-dimensional cases
Algorithm 3 might appear applicable to general n 2 2 by replacing S with S and defining A(C,) as the area of C. C S"-1 However, this idea faces challenge in bounding the regret when extending the above proof to general n 2 2.9
As suggested in the proof of Theorem C.2, bounding [[(c", [z,"""",=__""" -x,3 is trickier when A(C,) is small (cf. the case of A(C,) < x/2). Luckily, when n 2, we can bound it thanks to Lemma C.1 and sin O(c", 2.) < sin A(C,), where the latter roughly means the angle, 0(c", ē,), is bounded by the area, A(C,), from above. Importantly, when n = 2, both the central angle and the area of an are are identified with the length of the arc, which is the key to establishing sin 0(c", &.) S sin A(C,). This no longer true for 3. As in Figure 2, the area, A(C,), can be arbitrarily small even if the angle
We note that a hardness result given in Besbes et al. [8. Theorem 2] is different from what we encounter here They showed that their greedy circumcenter policy fails to achieve sublinear regret, which stems from the shape of the initial knowledge set and the behavior of the greedy rule for selecting é. this differs from the issue discussed above.
27

---

within there, or the maximum 8(c", ē)) for c², é E Ce, is large. This is why the proof for the case of 2 does not directly extend to higher dimensions. We leave closing the O I") gap for as an important open problem for future research.
D Numerical experiments
We conducted numerical experiments to complement our theoretical results. Experiments were conducted on Google Colab equipped with an Intel Xeon t CPU @ 2.20GHz, 12 GB RAM, running Ubuntu 22.04.4 LTS with Python 3.12.11. The code is available at https//gittub..oo//saaccc online-inverse linear- www.---iimmiiiiinnodddeooe
We use a setup based on the hard instance considered in our lower bound analysis (Section 5). Let c* be a random vector with ||c* 2l2 1. The learner's prediction set θ is the n-dimensional Euclidean unit ball. At each round we sample an endpoint uniformly random from the unit sphere in R and set X, = {-v, to). We report results for T 10,000 rounds in dimensions = 2, 20, and 200. To mitigate randomness, we repeat each experiment times independently and report mean and standard deviation.
Compared methods.
We compare the following three methods:
ONS: our proposed method based on ONS,
OGD: the OGD-bbaeed method of Bärmann et al. [4],
CP: a cutting-plane style method inspired by Gollapudi al. [25].
For CP, computing the centroid of the feasible region is #P-hard. Therefore, adopt randomized heuristic: we pre-sample n x 10 candidate points from the unit ball, climinate those violating accumulated cuts, and approximate the centroid by averaging the remaining points.
Results. Table 2 summarizes the cumulative regret and runtime over T 10,000 rounds (mean + standard deviation across 10 trials).
Table 2: Experimental results over T 10,000 rounds (mean + standard deviation across 10 independent runs).
(a) Cumulative Regret
Method
= 2
71 20
n 200
ONS
7.81 +: 2.52
31.55 + 0.43
46.19 + 0.88
OGD
8.46 4.07
33.80 + 0.50
67.41 1.36
CP
2.77 + 0.68
829.91 + 287.00
515.50 + 43.75
(b) Cumulative Runtime (s)
Method
n=
n 20
n 200
ONS
0.648 0.115
0.705 + 0.086
9.073 + 0.727
OGD
0.150 = 0.024
0.150 : 0.017
0.233 = 0.019
CP
4.670 = 3.205
5.700 = 1.748
71.252 = 12.152
When the dimension is small (n 2). CP achieves the lowest cumulative regret. However, its cumulative regret deteriorates significantly for n 20 and n = 200. This degradation stems from the limited number pre-sampled candidate points: in principle, about 7 samples would be required for an accurate approximation, which is infeasible even for moderate n. Moreover, although the above randomized centroid approximation substantially reduces computation by averaging over the
A similar issue, though leading to different challenges. noted Besbes al. [8, Section 4.4), where their method encounters ill ill-conditioned (or elongated) ellipsoids. They addressed this by appropriately determining when to update the ellipsoidal cone. The In 7 factor arises as result of balancing being ill ill-conditioned with the instantaneous regret.
28

---

surviving candidates, it remains less scalable than OGD and ONS. These results highlight practical limitations of CP moderate high nigh-dimensional settings.
In contrast, ONS consistently achieves low regret values across all dimensions while remaining computationally feasible. It outperforms OGD in terms of the regret and scales reasonably well with increasing n. Note that our ONS implementation uses straightforward projection subroutine that repeatedly solves similar linear systems-an overhead that could be reduced by more sophisticated implementation techniques. Further speedups could also be achieved via quasi-Newton-type updates or sketching- -asee techniques, as discussed in Sections 3 and
Taken together, these findings affirm that ONS provides a strong and scalable alternative to existing methods in online inverse linear optimization, especially when CP is computationally infeasible and OGD's 's regret performance is unsatisfactory.
29


Reviews:
[{"review_id": "fRe2vlwAwd", "reviewer": "Reviewer_5DsP", "summary": "This paper addresses the problem of online inverse linear optimization, where the learner is given a sequence of feasible sets $X_t \\subseteq \\mathbb{R}^n$ and corresponding optimal decisions $x_t$, and seeks to recover the unknown linear cost vector $c^*$. The authors propose a learning algorithm based on the Online Newton Step (ONS) method applied to a specially constructed loss function. Assuming this loss is exp-concave, the algorithm achieves a regret bound of $O(n \\log T)$, with per-round computational complexity independent of the time horizon $T$. The algorithm is also extended to handle suboptimal actions using a MetaGrad-style ensemble. A lower bound of $\\Omega(n)$ is provided, establishing the optimality of the regret's dimensional dependence up to logarithmic factors.", "questions": "1. Can you provide a formal proof or structural conditions under which the proposed loss function is exp-concave? Without this, the regret bound in Theorem 3.1 is not well grounded.\n2. Have you considered implementing your algorithm and comparing its runtime and regret behavior to prior methods (e.g., Besbes et al., which accumulate constraints over time)? Even synthetic experiments could strengthen the paper.\n3. The regret bounds include constants tied to parameters like $B, D, K$. Can you give concrete estimates or examples that help interpret these constants in typical inverse optimization settings?\n4. This work is clearly focused on linear objectives. Section 6 mentions the potential for kernelization. Can your self-bounding analysis extend to non-linear objectives or convex settings? Is exp-concavity still plausible in those cases?\n5. The $\\log T$ gap between upper and lower bounds remains open. Is this tight, or can the upper bound be improved with further algorithmic refinements?", "limitations": "While the paper discusses the restriction to linear objectives and the unresolved $\\log T$ gap, it does not sufficiently highlight the reliance on the unproven exp-concavity assumption, which is critical to the validity of the main result. This should be addressed explicitly.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\n\n1. The paper studies a well-motivated and practically relevant problem in online learning and inverse optimization.\n2. The paper includes a matching lower bound, which strengthens the theoretical framing.\n\n### Weaknesses\n\n1. The central theoretical guarantee relies entirely on the assumption that the proposed loss function is exp-concave. However, the paper does not prove this property or provide sufficient conditions under which it holds. Since exp-concavity is a strong assumption that does not hold generically, the regret bound is not fully justified.\n2. Once exp-concavity is assumed, the regret analysis is a standard application of the ONS algorithm. The work does not introduce new techniques or insights beyond this reuse.\n3. The paper includes no experiments to demonstrate the method’s practical efficiency or its advantage over existing baselines such as constraint-accumulation methods. This significantly limits its potential impact.\n4. The regret bound hides constants involving quantities such as $B, D, K$, which are not analyzed or estimated. This limits the practical interpretability of the results.\n5. Although the paper focuses on linear objectives, the framing and claims suggest broader applicability. In reality, the approach is tailored to a narrow setting, and the key assumptions do not generalize easily.", "was_revised": true, "final_justification": "I thank the authors for the detailed responses that addressed my concerns/problems. The exp-concavity of the surrogate loss function is clearly proved and the simplified analysis technique can be seen as a strength. Upon reading through other reviewers' comments, I decided to increase my score while decrease the confidence.", "rebuttal": "We sincerely thank the reviewer for their time and effort. Feedback that articulates specific points, like yours, is especially helpful in refining the manuscript. Below, we address the questions and concerns.\n\n## **Q1. Proof of exp-concavity**\n\nThe loss function used in Theorem 3.1 is exp-concave under Assumption 2.2. The proof is given in Appendix B.2 (as part of the general proof of Proposition 2.5), and we reproduce it below for clarity.\n\nSpecifically, for the $t$-th feedback $x_t \\in X_t$, prediction $\\hat c_t \\in \\Theta$, and $\\hat x_t \\in \\mathrm{argmax}_{x \\in X_t} \\langle \\hat c_t, x \\rangle$, the loss function is defined as\n$$\n\\ell_t^\\eta(c) = -\\eta \\langle \\hat{c}_t - c, \\hat{x}_t - x_t \\rangle + \\eta^2 \\langle \\hat{c}_t - c, \\hat{x}_t - x_t \\rangle^2 \\quad \\forall c \\in \\Theta,\n$$\nwhere $\\eta = \\frac{1}{5B}$. Its gradient and Hessian are\n$$\n\\nabla \\ell_t^\\eta(c) = \\eta\\left(1 - 2\\eta \\langle \\hat{c}_t - c, \\hat{x}_t - x_t \\rangle \\right)(\\hat{x}_t - x_t), \\quad\n\\nabla^2 \\ell_t^\\eta(c) = 2\\eta^2 (\\hat{x}_t - x_t)(\\hat{x}_t - x_t)^\\top.\n$$\n\nTherefore, we have\n$$\n\\nabla \\ell_t^\\eta(c) \\nabla \\ell_t^\\eta(c)^\\top = \\eta^2\\left(1 - 2\\eta \\langle \\hat{c}_t - c, \\hat{x}_t - x_t \\rangle \\right)^2(\\hat{x}_t - x_t)(\\hat{x}_t - x_t)^\\top \n\\preceq \\eta^2\\left(1 + 2\\eta B\\right)^2(\\hat{x}_t - x_t)(\\hat{x}_t - x_t)^\\top \n= \\frac{\\left(1 + 2\\eta B\\right)^2}{2}\\nabla^2\\ell_t^\\eta(c),\n$$\nwhere the inequality uses Assumption 2.2, which ensures $|\\langle \\hat{c}_t - c, \\hat{x}_t - x_t \\rangle| \\le B$. Thus, $\\ell_t^\\eta$ satisfies $\\nabla^2\\ell_t^\\eta(c) \\succeq \\alpha \\nabla \\ell_t^\\eta(c) \\nabla \\ell_t^\\eta(c)^\\top$ for $\\alpha = \\frac{2}{\\left(1 + 2\\eta B\\right)^2} = \\frac{50}{49} > 1$.\n\nThis condition is equivalent to $\\alpha$-exp-concavity for the twice-differentiable function $\\ell_t^\\eta$ (e.g., Hazan [26, Lemma 4.2]). Specifically, the Hessian of the function $\\phi\\colon c \\mapsto \\exp(-\\alpha\\ell^\\eta_t(c))$ satisfies\n$$\n\\nabla^2 \\phi(c) = \\alpha \\exp(-\\alpha \\ell^\\eta_t(c)) \\left(\\alpha\\nabla \\ell^\\eta_t(c) \\nabla \\ell^\\eta_t(c)^\\top - \\nabla^2 \\ell^\\eta_t(c)\\right) \\preceq 0,\n$$\nwhich implies that $\\phi$ is concave. Therefore, $\\ell_t^\\eta$ is $\\alpha$-exp-concave for $\\alpha > 1$.\n\n**Novelty given the exp-concavity.** While our methods build on ONS and MetaGrad, the way we leverage these tools in the context of online inverse linear optimization is novel and nontrivial. A key technical contribution is the identification of the exp-concave surrogate loss that enables the simple yet effective use of ONS in this setting. Notably, commonly used losses in inverse optimization—such as the suboptimality loss—are convex but not exp-concave, and thus do not support logarithmic regret bounds via ONS. Regarding this point, Reviewer 1Hto noted that “... it applies the Online Newton Step (ONS) to appropriate exp-concave loss functions. This simplicity is considered a strength, ...” More importantly, this viewpoint leads to our second main result: robustness to suboptimal feedback via MetaGrad. Reviewer kNBn remarked this application was “not obvious at all in hindsight,” highlighting the conceptual and technical novelty of our approach.\n\nWe hope this clarification resolves the reviewer’s concerns regarding the exp-concavity and the technical novelty of our contributions.\n\n## **Q2. Experiments**\nThank you for raising this point. Encouraged by your question, we conducted numerical experiments to evaluate our approach empirically. In summary, we found that our ONS-based method consistently outperforms OGD (Bärmann et al., 2020) in terms of the regret, while remaining significantly more efficient than cutting-plane-style methods, akin to those proposed by Besbes et al. (2021, 2025) and Gollapudi et al. (2021). These findings suggest that our ONS-based method is a highly effective approach, particularly when the problem dimension is too high for cutting-plane methods to be feasible and when OGD’s regret performance is unsatisfactory. Due to space limitations, we present the details of the experimental setup and results in our response to Reviewer xL4W.\n\n## **Q3. Regarding constants depending on $D$, $K$, and $B$**\n\nOur regret upper bound of $O\\left( Bn \\log \\frac{DKT}{Bn} \\right)$ depends only mildly on the parameters $B$, $D$, and $K$. The constant factor is interpretable and can be estimated based on the agent’s forward problem specifications. Let us first clarify their definitions:\n- $D$ is the $\\ell_2$-diameter of $\\Theta$, the learner’s set of predictions.\n- $K$ is the maximum $\\ell_2$-diameter of $X_t$, the agent’s feasible action set.\n- $B$ is an upper bound on the inner product $\\langle \\hat{c} - c, \\hat{x} - x \\rangle$ for any $c, \\hat{c} \\in \\Theta$ and $x, \\hat{x} \\in X_t$.\n\nIn many cases, the learner is interested only in predicting the direction of the agent’s objective vector $c^\\ast$, since the observed feedback $x_t \\in \\mathrm{argmax}_{x \\in X_t} \\langle c^\\ast, x \\rangle$ reveals no information about the scale of $c^\\ast$. Therefore, we can usually assume that $\\Theta$ is the unit Euclidean ball, yielding $D = 2$. If $c^\\ast$ is known to be non-negative, we may alternatively assume that $\\Theta$ is, for example, the probability simplex, as in Bärmann et al. (2017).\n\nThe value of $K$ depends on the agent’s forward problem. For instance, in the customer preference estimation problem studied by Bärmann et al. (2017, Section 4.1), the action set is defined by a knapsack constraint: $p^\\top x \\le b$ and $x \\ge 0$, for some price vector $p \\in \\mathbb{R}^n_{>0}$ and budget $b > 0$. If $l > 0$ is a lower bound on the price vector entries, then the $\\ell_2$-diameter is at most $K = O(b\\sqrt{n}/l)$. In the literature (e.g., Gollapudi et al., 2021; Besbes et al., 2021, 2025), this is often simplified to $K = O(1)$ by normalizing the action sets.\n\nFinally, the constant $B$ is upper bounded by $DK$ by the Cauchy–Schwarz inequality. We introduce $B$ to express the regret bounds with sharper dependence on the problem geometry. In practice, $B$ can also be interpreted as prior knowledge about the agent’s maximum attainable objective value (up to a constant factor).\n\nReturning to the $O\\left( Bn \\log \\frac{DKT}{Bn} \\right)$ regret upper bound, given a specification of the agent’s forward problem as discussed above, the constants in the bound can be computed straightforwardly. Roughly speaking, the logarithmic term can be estimated as at most $\\log T$ since we typically have $DK \\approx B$. Thus, the dominant contribution from the constant factor is $Bn$, which can be interpreted as the agent’s maximum attainable objective value multiplied by the dimensionality. Note that this is the optimal dependence on $Bn$ since there is a regret lower bound of $\\Omega(Bn)$, as shown in Theorem 5.1.\n\nAppendix A provides a more detailed discussion on how these parameters influence the regret bounds, including comparisons with prior work.\n\n## **Q4. Extension to non-linear objectives**\nThank you for the question. While our paper focuses on linear objectives, the techniques extend to a broad class of forward problems.\n\nIf the agent's objective function is nonlinear—for example, quadratic of the form $x^\\top Q x + q^\\top x$—we can still apply our framework by defining a suitable feature map. Specifically, we may define \n\n$$\\phi(x) = (x_1^2, \\ldots, x_n^2, x_1 x_2, \\ldots, x_{n-1}x_n, x_1, \\ldots, x_n) \\in \\mathbb{R}^{\\binom{n}{2} + 2n}$$ \n\nso that the agent’s objective becomes linear in the feature space: $\\langle c, \\phi(x) \\rangle$ with $c \\in \\mathbb{R}^{\\binom{n}{2} + 2n}$ encoding $Q$ and $q$. As long as the objective is expressed in this linear form in $c$, our surrogate loss, $\\ell^\\eta_t(c)$, remains exp-concave, and our approach can be applied; we have discussed a similar extension to the contextual setting of Besbes et al. (2021, 2025) in 562–578 in Appendix A. In this sense, our approach is compatible with a wide class of non-linear objectives. The main limitation of this extension is the increased dimensionality. Designing scalable algorithms that mitigate this issue is an important direction for future work.\n\nFinally, note that although the linear setting may appear restrictive, it captures many practical applications and provides a theoretical foundation for understanding the regret guarantees achievable in inverse optimization. This is why a foundational body of prior work—including Bärmann et al. (2017, 2020), Gollapudi et al. (2021), and Besbes et al. (2021, 2025)—has also focused on linear objectives. \n\n## **Q5. Regarding the $\\log T$-gap**\n\nWhether the $\\log T$ factor is avoidable in online inverse optimization is a fundamental open question, as also noted in prior work (e.g., Gollapudi et al., 2021, Section 4.1). Although no existing work has formally resolved this question, we believe that further progress could lead to removing the $\\log T$ factor from the regret upper bound. Our work contributes to this broader effort by offering a novel perspective: whereas previous approaches achieving logarithmic regret bounds (Gollapudi et al., 2021; Besbes et al., 2021, 2025) are based on cutting-plane methods, our approach is the first to leverage ONS in this context. We hope that this alternative methodology sheds new light on the structure of the problem and offers a fresh angle from which to approach this important open direction.\n\nWe hope that the above responses effectively address your concerns. Please do not hesitate to let us know if any questions remain or if further clarification would be helpful."}, {"review_id": "Q6dGtNCQTi", "reviewer": "Reviewer_kNBn", "summary": "This papers studies the problem online inverse linear optimization, proposing an algorithm with an improved regret bound of $O(n \\ln T)$  with a simple and relatively efficient algorithm. The main idea is the use of the Online Newton Step with a surrogate function proposed by the authors of the algorithm MetaGrad. Furthermore, the authors show that when the learner observes a suboptimal action instead of an optimal one as in the case of the original problem, using MetaGrad with $\\Theta(\\log T)$ experts leads to a similar regret bound with an extra penalty of $O(\\sqrt{\\Delta_T n \\ln T})$, where $\\Delta_T$ is the culmulative gap of the optimal payoffs and the payoffs of the observed actions. Finally, the authors also show a $\\Theta(n)$ lower bound on the regret of any (possibly randomized) algorithm for the problem, and show how one can get $O(1)$ regret for $n = 2$.", "questions": "Here are a few parts where notation is heavy and maybe a bit confusing:\n-  In Prop 2.5, do we need $w_i \\in \\mathcal{W}$? Or is it ok for them to be arbitrary vectors? Also, having $w_t$ as arbitrary vectors while $w_t^{\\eta}$ are iterates was quite confusing. It makes sense for MetaGrad, but at this point it was quite confusing;\n- For Theorem 4.1 we need the subgradients used by MetaGrad to be the specific gradients given by Prop 2.4, right? I don't think this is specified anywhere\nOther minor comments:\n- lines 49-50: \"(...) about $c^*$ defining the regret.\" not clear what you meant here\n- line 138: \"Alternately\" here is to mean that first the player places the prediction and only afterwards receives feedback, if I understood it correctly, but I don't think this is the correct way to say that.\n- Assumption 2.2: \"$\\ell_2$-diameter\" is slightly ambiguous since we don't know if you mean squared norm or not. If you have the space, I would add the mathematical formula to clear any possible confusions;", "limitations": "The author's do a good job on placing their contributions in the literature and discussing limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The algorithm proposed to the problem is surprisingly simple and yields strong results for the problem. It is quite interesting to see such a simple algorithm given that the previous algorithms for the same (or similar problem) use more intricate algorithms based on cutting plane methods. Ultimately the regret bounds follow from results from MetaGrad (as the authors note, even Thm 3.1 is MetaGrad with only one expert), but this should not be seen as a negative point for this paper, since this application was not obvious at all in hindsight and the authors do shave off some constants in their analysis. The lower bound is also simple, so I feel the results overall are quite elegant.\n\nOne problem (although relatively minor) the paper has is with notation. It is quite heavy at some moments, and it can get quite confusing at some points. I know the MetaGrad paper and know that a lot of this notation is from the original MetaGrad paper, but this is not a good excuse to use the same notation in the main paper. \n\nAnother minor problem with presentation is that it was not clear to me when first reading the paper whether the constants the big-Oh notation was hiding in sec 1 could be hiding a dependency on $n$ (such as the B or D constants later on). Appendix A (which is quite well-written) clarifies this a lot, but it would be nice to say, for example, that the rates in the table in Sec 1 are for all sets being constrained to the unit ball for the sake of uniformity.", "was_revised": true, "final_justification": "I went throught the other reviews, and I still believe this is a strong submission. I don't agree with the most negative review, and the other slightly negative reviewer had some good points that I felt were properly addressed in the rebuttal. I'll engage in the discussion with reviewers and AC to try to reach consensus.", "rebuttal": "We sincerely thank the reviewer for the careful and constructive feedback, as well as for your strong support of our work. We are grateful for the detailed reading and thoughtful suggestions rooted in deep expertise. Below, we respond to the questions:\n\n1. Regarding the domain of $w_t$ in Proposition 2.5, the vector (as well as $w_t^\\eta$) is assumed to belong to $\\mathcal{W}$. In the main text, $w_t \\in \\mathcal{W}$ is stated in eq. (3).\n\n2. In Theorem 4.1, subgradient $g_t$ corresponds to $\\hat{x}_t - x_t$, consistent with Proposition 2.4. We will clarify this in the revised version.\n\nWe also appreciate the minor comments and will incorporate the suggested improvements in the revised version.\n\nRegarding the remark on lines 49–50: we intended to convey that online inverse linear optimization can, in principle, benefit from richer feedback than standard online linear optimization (OLO). In OLO, the cost vectors provide little information about the best action in hindsight, which is the comparator in the regret, restricting the attainable regret rate to $\\sqrt{T}$. In contrast, in online inverse linear optimization, the observed feedback $x_t \\in X_t$ is optimal for the agent’s true objective vector $c^\\ast$, which defines the regret in this setting as $\\sum_{t=1}^T \\langle c^\\ast, x_t - \\hat x_t \\rangle$. Intuitively, this richer information about $c^\\ast$ enables us to achieve logarithmic regret bounds, surpassing the $\\sqrt{T}$ barrier of general OLO."}, {"review_id": "zPrWZhmWkz", "reviewer": "Reviewer_1Hto", "summary": "This paper aims to solve the problem of online inverse linear optimization, where a learner tries to deduce a hidden linear objective function of an agent by observing the agent's chosen optimal actions over time.\nThe quality of the learner's predictions is measured by regret, which is the cumulative gap between optimal objective values and those achieved by following the learner's predictions.\nIn the literature, Besbes et al. 2021 and 2025 propose an algorithm that achieves a logarithmic regret bound, while it is not computationally efficient since the number of constraints grows as fast as a polynomial of time length $T$. The authors propose an efficient algorithm that achieves logarithmic regret $O(n \\ln(T)$ and has a per-round complexity independent of $T$.", "questions": "1. Line 290 - 296, you state that MetaGrad's per-round complexity is $O(\\tau_{\\text{solve}} + (n^2 + \\tau_{G-\\text{proj}}) \\ln(T)$ and that \"If the $\\tau_{G-\\text{proj}} \\ln(T)$ factor is a bottleneck, we can use more efficient universal algorithms [Mhammedi et al., 2019, Yang et al., 2024] to reduce the number of projections from $\\Theta(lnT)$ to $1$.\"  Could you briefly explain how these more efficient universal algorithms (e.g., [Mhammedi et al., 2019, Yang et al., 2024]) reduce the number of projections to 1 in the context of MetaGrad? And what is the factor or concern that prevents you from choosing those more advanced algorithms in the first place?\n\n2. Line 338 - 339, you mention, \"Whether a similar lower bound holds when all $X_t$ are full-dimensional remains an open question.\" Can you briefly speculate on what specific challenges arise in constructing a similar lower bound proof for the full-dimensional case compared to the line segments used in Theorem 5.1?\n\n3. Line 715 - 727, in Section C.2, you discuss the challenge of extending the $O(1)$ regret bound for $n=2$ to $n \\geq 3$ due to the area $A(C_t)$ becoming arbitrarily small while $\\theta(c^\\star, \\hat{c})$ does not. Could you elaborate more on the most promising direction you believe to close the gap for $n \\geq 3$?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper presents the first logarithmic-regret method whose per-round computational complexity is independent of the time horizon $T$. This is a significant advancement, as previous logarithmic-regret methods were highly inefficient for large time steps.\nAlso, the proposed method achieves the best-known logarithmic regret bound of $O(n\\ln (T))$\n\n2. The method is described as \"strikingly simple\" as it applies the Online Newton Step (ONS) to appropriate exp-concave loss functions. This simplicity is considered a strength, making it more accessible and easier to implement.\n\n3. Corollary 4.2 provides an online-to-batch conversion for offline settings. The comparison with [Bärmann et al., 2020] on offline guarantees notes that their prior work is $O(1/T)$ even when $\\Delta=0$, whereas this paper offers a faster $O(\\ln(T)/T)$ rate, highlighting an improvement.\n\nWeakness:\n\n1. The primary limitation explicitly stated by the authors is that their work is restricted to the case where the agent's underlying optimization problem is linear. Extending this to nonlinear settings is identified as an important direction for future work.\n\n2. While the lower bound of $\\Omega(n)$ and upper bound of $O(n\\ln(T))$ are established, there remains an $O(\\ln(T))$ gap between them that the authors identify as an important open problem.", "was_revised": true, "final_justification": "The author has resolved my questions. I have also reviewed the discussions of the author with other reviewers, and I believe this paper is acceptable so I will keep my score and support for this paper.", "rebuttal": "We sincerely thank the reviewer for the insightful comments and questions. Below, we address each point raised.\n\n## **Q1. Reducing the number of projections in MetaGrad**\nThe reason we used the standard version of MetaGrad in the complexity discussion is that it is both intuitive and widely known. More efficient implementations in Mhammedi et al. (2019, Section 4) can indeed reduce the computation cost of projections from that of $O(\\log T)$ to 1 per round without any sacrifice, which we explain below.\n\nIn MetaGrad, each of the $O(\\log T)$ $\\eta$-experts performs a generalized projection of the following form, as in Algorithm 1 in Appendix B:\n\n$$\nw_{t+1} \\leftarrow \\arg\\min_{w \\in \\mathcal{W}} \\left\\\\| w_t - \\frac{1}{\\gamma} A_t^{-1} \\nabla q_t(w_t) - w \\right\\\\|_{A_t}^2,\n$$\n\nwhere $A_t = \\varepsilon I_n + S_t$ and $S_t = \\sum_{s=1}^t \\nabla q_s(w_s) \\nabla q_s(w_s)^\\top$.\nLet $\\mathcal{W}$ be a Euclidean ball for simplicity. Then, the projection can be computed via singular value decomposition (SVD) of $A_t$. Naively doing this for each expert would require $O(\\log T)$ SVD computations. However, as observed in Mhammedi et al. (2019, Section 4.1), $S_t$ is the sum of outer products of the same vectors across all $\\eta$-experts, and the only difference among the experts lies in the scalar weighting applied to $S_t$. This enables us to compute the SVD of $S_t$ once and reuse it across all experts, thereby reducing the projection cost to that of a single projection. Even when $\\mathcal{W}$ is not a Euclidean ball, the approach can be extended by reducing the projection to the Euclidean case based on a technique developed by Cutkosky and Orabona (2018, \"Black-box reductions for parameter-free online learning in Banach spaces\"), as discussed in Mhammedi et al. (2019, Section 4.2).\n\n## **Q2. On extending the lower bound to full-dimensional $X_t$**\nThank you for highlighting this subtle and important point. Our current lower bound construction relies on using line segment domains $X_t$ that are axis-aligned. Intuitively, this structure ensures that the observed feedback $x_t \\in \\mathrm{argmax}_{x \\in X_t} \\langle c^\\ast, x \\rangle$ reveals only a single coordinate of the agent’s true objective vector $c^\\ast$. For example, if $X_t$ is aligned with the $t$-th coordinate axis, then $x_t$ provides information only about $c^*(t)$ and nothing about the other coordinates. This readily implies that $\\Omega(n)$ observations are required to infer the full vector $c^\\ast$, which forms the basis of our lower bound.\n\nIn contrast, if $X_t$ is full-dimensional—say, $X_t = [-1, 1]^2$ for $n = 2$—the maximizer $x_t$ lies at one of the box’s corners. Observing the sign pattern of $x_t$ in such cases allows the learner to infer the sign of every coordinate of $c^*$, thereby revealing more information per round than in the line segment case.\n\nEstablishing lower bounds under full-dimensional $X_t$ thus involves additional challenges in limiting per-round information gain. For the purposes of this work, using line segment domains is sufficient to derive the $\\Omega(n)$ lower bound, while keeping the proof technically simple and transparent.\n\n## **Q3. On the discussion in Appendix C**\nWe are glad that the reviewer found the discussion in Appendix C of interest. This part of our analysis is inspired by cutting-plane-type ideas (Besbes et al., 2021, 2025; Gollapudi et al., 2021), where the learner iteratively eliminates inconsistent regions of the objective vector space. However, as noted, this approach faces technical barriers—such as the gap between angular and area—that make it challenging to extend the analysis to general $n$.\n\nIn contrast, our main approach builds on online Newton step (ONS) with tailored exp-concave surrogate losses. While this incurs a $\\log T$ factor, the online convex optimization (OCO) literature provides data-dependent refinements for exp-concave losses. For example, Orabona et al. (AISTATS 2012, \"Beyond Logarithmic Bounds in Online Learning\") introduce the so-called small-loss-dependent analysis, which tightens the regret bound based on the comparator's cumulative loss. Adapting such advanced OCO techniques to online inverse optimization could be a promising future direction. More broadly, we believe that the cutting-plane and ONS-based viewpoints highlight complementary aspects of the problem, and integrating insights from both may ultimately help close the $\\log T$ gap.\n\nWe hope the above responses effectively address your questions. Please do not hesitate to let us know if any questions remain or if further clarification would be helpful."}, {"review_id": "K6ErVJ9zoL", "reviewer": "Reviewer_xL4W", "summary": "This paper studies the problem of online inverse linear optimization. By applying the Online Newton Step (ONS) algorithm, the authors achieve logarithmic regret in time ($\\log T$) with time independent per round complexity. The setting is further extended to account for suboptimal actions, and corresponding lower bounds are established.", "questions": "Is the suboptimal feedback setting considered in the paper related in any way to the framework of online optimization with hints? If so, it would be helpful to clarify the connection and highlight any similarities or differences.", "limitations": "Adequately discussed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:  \n\n- Per round complexity of different algorithms are compared and time independent per round complexity has been achieved. \n\n- Lower bound of regret in terms of dimensional dependence has been proved. \n\nWeaknesses: \n\n- It seems that there is a tradeoff between per round complexity and regret bound in Table 1. In the case of high dimensions ONS can be costly which can also be observed in $n^2$ term in per round complexity. \n\n- The reported overall complexity can be somewhat misleading. For example, $\\tau_{proj}$ itself can depend on $n$, in which case the overall complexity may be well more expensive that just $n^2$.  \n\n- While the paper motivates the results from a practical perspective, there is no numerical experiment to demonstrate the effectiveness of the proposed methods over state-of-the-art.", "was_revised": true, "final_justification": "The authors adequately addressed my questions and I increased the initial score.", "rebuttal": "We sincerely thank the reviewer for their time and effort in reviewing our work. Below, we address each point raised.\n\n## **W1 & W2. Regarding complexity**\n\nWe appreciate your comments on the description of complexity. We will revise it accordingly to avoid any confusion.\n\nAs discussed in Section 3, the generalized projection step has a typical computational cost of $\\tau_{\\text{G-proj}} = O(n^3)$, and we agree that this should have been explicitly stated in Table 1. We will revise the table caption to include this remark.\n\nWhile ONS’s per-round complexity is indeed higher than that of OGD, it is important to note that existing logarithmic regret methods by Besbes et al. (2021, 2025) and Gollapudi et al. (2021) incur even greater per-round costs that depend on both $n$ and $T$—e.g., $O(n^5T^3)$, as noted in the caption of Table 1. In contrast, our approach eliminates any dependence on $T$ and typically keeps the per-round cost at $O(\\tau_{\\text{solve}} + n^3)$ when $\\tau_{\\text{G-proj}} = O(n^3)$, where $\\tau_{\\text{solve}}$ denotes the cost of solving linear optimization over $X_t$, which is also required by OGD. We thus believe that this complexity should be regarded as a strength of our approach rather than a weakness. In fact, Reviewer 1Hto noted that “This is a significant advancement, as previous logarithmic-regret methods were highly inefficient for large time steps.”\n\n## **W3. Numerical experiments**\nWe appreciate the reviewer's feedback regarding numerical experiments. In light of your and other reviewers’ comments, we have conducted experiments to complement our theoretical results.\n\n### **Setup**\nWe use synthetic datasets inspired by the hard instance used in our lower bound analysis (Section 5). Let $c^\\ast$ be a random vector with $\\\\| c^\\ast \\\\| = 1$. The learner’s prediction set $\\Theta$ is the $n$-dimensional Euclidean unit ball. For each $t$, we sample an endpoint $v$ uniformly at random from the unit sphere in $\\mathbb{R}^n$ and set $X_t$ to the line segment $[-v, +v]$. We generate $T = 10,000$ instances for $n = 2$, $20$, and $200$.\n\n### **Methods**\nWe compare the following three methods:\n- ONS: our online-Newton-step-based method,\n- OGD: the online gradient descent method based on Bärmann et al. (2020),\n- CP: a cutting-plane-style method inspired by Gollapudi et al. (2021).\n\nFor CP, we must compute the centroid of $\\bigcap_{s=1}^t \\\\{c \\in \\Theta : \\langle c - \\hat c_s, x_s - \\hat{x}_s \\rangle \\ge 0\\\\}$ at each round $t$. Since exact centroid computation is #P-hard, and even polynomial-time approximations like hit-and-run sampling are often impractical, we adopt a randomized heuristic: we pre-sample $n \\times 10^4$ candidate points from the unit ball $\\Theta$, eliminate those violating accumulated cuts, and approximate the centroid as the average of the remaining points. Though not theoretically grounded, this method serves as a tractable approximation of the original CP approach.\n\n### **Results**\nBelow are tables showing the cumulative regret and runtime over $T$ rounds.\n\n#### **Cumulative regret**\n\n| Method         | $n = 2$   | $n = 20$   | $n = 200$  |\n|----------------|---------|----------|----------|\n| ONS            | $4.93$    | $31.69$    | $46.85$    |\n| OGD            | $7.33$    | $33.20$    | $69.43$    |\n| CP             | $3.81$ | $564.49$   | $481.45$   |\n\n#### **Cumulative runtime (s)**\n\n| Method         | $n = 2$   | $n = 20$   | $n = 200$  |\n|----------------|---------|----------|----------|\n| ONS            | $0.137$   | $1.53$     | $17.26$    |\n| OGD            | $0.046$| $0.076$| $0.134$|\n| CP             | $1.64$    | $2.01$     | $41.31$    |\n\nWhen the dimension is small ($n = 2$), CP achieves the lowest cumulative regret. However, its cumulative regret deteriorates significantly for $n = 20$ and $n = 200$. This degradation stems from the limited number of pre-sampled candidate points: in principle, about $T^n$ samples would be required for an accurate approximation, which is infeasible even for moderate $n$. Moreover, although the above randomized centroid approximation substantially reduces computation by averaging over the surviving candidates, it remains less scalable than OGD or ONS. These results highlight practical limitations of CP in moderate to high-dimensional settings.\n\nIn contrast, ONS consistently achieves low regret values across all dimensions while remaining computationally feasible. It outperforms OGD in terms of the regret and scales reasonably well with increasing $n$. Note that our ONS implementation uses a straightforward projection routine that repeatedly solves similar linear systems—an overhead that could be reduced by more sophisticated implementation techniques. Further speedups could also be achieved via quasi-Newton-type updates or sketching-based techniques, as discussed in Sections 3 and 4.\n\nTaken together, these findings affirm that ONS provides a strong and scalable alternative to existing methods in online inverse linear optimization, especially when CP is computationally infeasible and OGD's regret performance is unsatisfactory. \n\n## **Q. Relation to online learning with hints**\nThank you for the interesting question. We considered your suggestion in light of the literature on *online learning with hints*, such as Dekel et al. (NeurIPS 2017, \"Online Learning with a Hint\") and Bhaskara et al. (ICML 2020, \"Online Learning with Imperfect Hints\"). Below, we clarify the similarities and differences.\n\nThe \"online learning with hints\" framework pertains to standard online linear optimization (OLO), where the learner selects an action $x_t$ and then observes a cost vector $c_t$. Before making a decision, the learner receives a hint vector $h_t$, which is expected to correlate with $c_t$. The goal is to minimize the regret $\\sum_{t=1}^T \\langle c_t, x_t - u \\rangle$ with respect to the best fixed action $u$ in hindsight.\n\nIn contrast, our setting arises from inverse optimization. The learner predicts an objective vector $\\hat{c}\\_t$, which induces an action $\\hat{x}\\_t \\in \\mathrm{argmax}\\_{x \\in X_t} \\langle \\hat{c}_t, x \\rangle$, and then observes the agent’s actual choice $x\\_t \\in X\\_t$. The regret is defined as $\\sum\\_{t=1}^T \\langle c^{\\ast}, x_t - \\hat{x}\\_t \\rangle$, where $c^{\\ast}$ is the agent's true objective vector. Thus, the learner selects $\\hat{c}_t$, and the feedback is observed *after* decision-making, in the form of the agent’s action $x_t$.\n\nAlthough the two frameworks might appear similar, they differ in fundamental ways. In the hint setting, the learner receives explicit side information *before* making a decision. In our setting, the feedback $x_t$ arrives *after* the learner’s prediction, and it only indirectly reflects the unknown objective vector $c^\\ast$.\n\nThat said, one could envision a hybrid setup where the learner receives both the agent's feedback and external side information about $c^{\\ast}$. Developing algorithms that leverage such additional information—perhaps to remove the $\\log T$ factor in the regret bound—would be an exciting direction for future research. We thank the reviewer for raising this intriguing connection and will include it in the revised version.\n\nWe hope the above clarifications help resolve your concerns. Please do not hesitate to let us know if any questions remain or if further clarification would be helpful."}, {"review_id": "X2oFKSMxTt", "reviewer": "Reviewer_Td8g", "summary": "This paper addresses the problem of online inverse linear optimization. In this framework, at each round, the learner receives a feasible optimization set along with the optimal result of an oracle call (referred to as the agent). The learner aims to recover the underlying linear parameter from these observations by minimizing cumulative regret.\n\nPrevious work has shown that a black-box reduction to online convex optimization can be applied, yielding regret upper bounds of order $O(\\sqrt{T})$ or $O(n \\log T)$. However, the logarithmic regret rate was only achieved by methods with a per-round time complexity of $\\Omega(T^3)$, which is polynomial and thus impractical for large $T$.\n\nIn this work, the authors present a simple reduction that allows the use of Online Newton Step (ONS) with a loss function inspired by that of MetaGrad. This approach achieves a regret of order $O(n \\log T)$ while retaining the per-round computational complexity of ONS---i.e., constant per round, with the main computational bottleneck being the generalized projection step.\n\nMoreover, by applying MetaGrad instead of ONS---which automatically tunes the parameters of ONS---they show that their method remains robust even when the agent is suboptimal. Specifically, their regret scales as $O(\\sqrt{\\Delta_T})$ rather than linearly, where $\\Delta_T$ denotes the cumulative suboptimality of the agent.\n\nFinally, the authors provide an $\\Omega(n)$ lower bound (on a specific instance), demonstrating the optimality of their method up to a logarithmic factor in $T$.", "questions": "1) For the online-to-batch conversion, is it possible to obtain the result with high probability?\n\n2) Since MetaGrad simultaneously achieves both $DK\\sqrt{T}$ and $n \\log T$ regret bounds, it would be valuable to state this explicitly in your results. The $DK\\sqrt{T}$ bound may be preferable in regimes where $n$ is large.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written, and the analysis is, as the authors claim, relatively simple. It mainly involves defining an appropriate loss function and applying existing results from ONS and MetaGrad. This simplicity can be viewed as a strength (a straightforward method with easy implementation that significantly improves upon existing results) or as a weakness (the lack of novel technical contributions).\n\n\nWeaknesses:\n\nThe paper lacks numerical experiments. It would have been valuable to demonstrate, in practice, the benefits in terms of regret or computational cost using synthetic experiments. In particular, what is the effective cost of the generalized projection step in ONS when solving the optimization problem to sufficient accuracy for the regret guarantees? (It would be helpful to recall this in the paper.) If both algorithms are given similar time budgets (e.g., by controlling the precision with which the optimization problems are solved), would it be possible to compare with the regret bound of [25]?\n\nThere remains a gap between the upper and lower bounds: $\\Omega(n)$ versus $O(n \\log T)$. Moreover, constant regret might be achievable in general, although it is likely to be challenging. It would also be worthwhile to include in the comparison table the constant regret bound (albeit exponential in $n$) from [25]. Is it possible that an exponential dependence on $n$ is unavoidable for achieving constant regret?", "was_revised": true, "final_justification": "I went through the reviews and rebuttal and support acceptance. In my view, the central question is whether the limited novelty of the analysis (being a straightforward application of ONS and MetaGrad) should be seen as a strength or a weakness. I believe it is a strength, as it improves previous approaches, that were significantly more complex. I think the authors address well other concerns in their rebuttal.", "rebuttal": "We sincerely thank the reviewer for the positive feedback and insightful questions. Below, we address each point raised.\n\n## **W1. Numerical experiments**\nThank you for the constructive suggestion regarding numerical experiments. Encouraged by your and other reviewers' comments, we conducted preliminary experiments to assess the practical performance of our approach.\n\nIn short, we found that cutting-plane-style methods (CP; e.g., Besbes et al. 2021, 2025; Gollapudi et al. 2021) quickly become computationally impractical, even in moderate dimensions. In contrast, our ONS-based method remains tractable and consistently outperforms OGD (Bärmann et al., 2020) in terms of the regret. The results provide empirical evidence that ONS can serve as a strong practical alternative to both CP and OGD. Please see our response to Reviewer xL4W for the details of the experimental setup and results.\n\nRegarding the effective cost of the generalized projection in ONS, as discussed by Mhammedi et al. (2019), the projection can be implemented via singular value decomposition (SVD), which achieves machine epsilon precision in $O(n^3)$ time. On the other hand, cutting-plane-based methods such as that of Gollapudi et al. [25] require an impractically large number of samples to reach comparable approximation accuracy. Thus, under any realistic time budget, ONS would perform significantly better than CP in terms of the regret—an observation supported by our experiments for $n = 20$ and $n = 200$.\n\n## **W2. On the dependence on $n$ in the constant regret bound**\nWhether it is possible to avoid the exponential dependence on $n$ in the constant regret bound remains an important open question. This is highlighted in Section 6 of our paper and in Gollapudi et al. [25, Section 4.1]. While prior approaches that achieve logarithmic and $\\exp(O(n \\log n))$ regret bounds (Gollapudi et al. 2021; Besbes et al. 2021, 2025) rely on cutting-plane methods, our work introduces a new approach based on Online Newton Step (ONS). The insights from these distinct methodologies would be complementary, and we hope that combining them will lead to progress on this open problem. In this respect, we believe that our ONS-based approach provides a meaningful contribution.\n\n\n## **Q1. High-probability online-to-batch conversion**\nYes, since it is the application of the standard online-to-batch conversion to the convex suboptimality loss, it can be extended to a high-probability guarantee via a commonly used concentration argument (e.g., Orabona \"A Modern Introduction to Online Learning,\" Section 3.1.2). A caveat is that, as is usual, obtaining a guarantee that holds with probability at least $1 - \\delta$ comes with an additive $O(\\sqrt{\\log(1/\\delta)/T})$ term. This additive factor makes the overall convergence rate $O(\\log T / T + \\sqrt{\\log(1/\\delta)/T})$, which is a fundamental limitation of the online-to-batch conversion approach to obtaining high-probability guarantees.\n\n## **Q2. Making both regret bounds explicit**\nWe appreciate the suggestion. We agree that explicitly stating the $O(DK\\sqrt{T})$ regret bound alongside the logarithmic one would be helpful. We will incorporate it into the revised version.\n\nWe hope that the above responses effectively address the points raised. Please do not hesitate to let us know if any questions remain or if further clarification would be helpful."}]

Author rebuttal:

Meta-review: This paper studies the online inverse linear optimization problem, and shows that ONS and MetaGrad with suitable surrogate loss functions can achieve the logarithmic regret bounds for this problem. The authors also establish an $\Omega(n)$ lower bound to demonstrate the near optimality of their algorithms, where $n$ is the dimensionality.

Note that previous studies have already proposed an algorithm to achieve the logarithmic regret bound for this problem. However, this algorithm is a cutting-plane-style method, which is more complex and requires much higher time complexity. Therefore, the main strengths of this paper are the efficient logarithmic-regret algorithms (i.e., ONS and MetaGrad with suitable surrogate loss functions) and the $\Omega(n)$ lower bound. 

Nonetheless, there are also some weaknesses (or concerns initially raised by some reviewers). First, the applications of ONS and MetaGrad are very standard, as MetaGrad was originally proposed with surrogate loss functions [55, 56], which implies that the technical novelty of this paper may be limited. Second, there still exists a time-dependent gap between the $\Omega(n)$ lower bound and the $O(n\log T)$ upper bound. Third, the authors do not provide experiments to verify the advantage of the proposed algorithms.

Due to these strengths and weaknesses, this paper initially got scores of 2, 4, 4, 3, and 5 from five reviewers. But after the rebuttal, most concerns of the reviewers have been addressed: i) they reach a consensus that the simplicity of applying ONS and MetaGrad should be regarded as a strength, rather than a weakness; ii) the authors provide some experiments to demonstrate the advantage of the proposed algorithms. Accordingly, their scores became 3, 4, 5, 4, and 5. 

I also like the simplicity (and efficiency) of applying ONS and MetaGrad to the online inverse linear optimization problem. Thus, I recommend accepting this paper, and hope that the authors could also revise this paper according to the reviewers' comments, e.g., the concerns about the experiments.
Decision: Accept (poster)