Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound

We sincerely thank the reviewer for the positive feedback and insightful questions. Below, we address each point raised.

W1. Numerical experiments

Thank 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.

In 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.

Regarding 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$.

W2. On the dependence on $n$ in the constant regret bound

Whether 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.

Q1. High-probability online-to-batch conversion

Yes, 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.

Q2. Making both regret bounds explicit

We 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.

We 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.

We sincerely thank the reviewer for their time and effort in reviewing our work. Below, we address each point raised.

W1 & W2. Regarding complexity

We appreciate your comments on the description of complexity. We will revise it accordingly to avoid any confusion.

As 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.

While 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.”

W3. Numerical experiments

We 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.

Setup

We 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$.

Methods

We compare the following three methods:

• ONS: our online-Newton-step-based method,
• OGD: the online gradient descent method based on Bärmann et al. (2020),
• CP: a cutting-plane-style method inspired by Gollapudi et al. (2021).

For 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.

Results

Below are tables showing the cumulative regret and runtime over $T$ rounds.

Cumulative regret

Cumulative runtime (s)

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 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.

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 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.

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 regret performance is unsatisfactory.

Q. Relation to online learning with hints

Thank 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.

The "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.

In 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$.

Although 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$.

That 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.

We 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.

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:

1. 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).

2. 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.

We also appreciate the minor comments and will incorporate the suggested improvements in the revised version.

Regarding 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.

We sincerely thank the reviewer for the insightful comments and questions. Below, we address each point raised.

Q1. Reducing the number of projections in MetaGrad

The 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.

In MetaGrad, each of the $O(\log T)$ $\eta$-experts performs a generalized projection of the following form, as in Algorithm 1 in Appendix B:

where $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$. Let $\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).

Q2. On extending the lower bound to full-dimensional $X_t$

Thank 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.

In 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.

Establishing 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.

Q3. On the discussion in Appendix C

We 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$.

In 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.

We 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.

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.

Q1. Proof of exp-concavity

The 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.

Specifically, 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

where $\eta = \frac{1}{5B}$. Its gradient and Hessian are

Therefore, we have

where 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$.

This 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

which implies that $\phi$ is concave. Therefore, $\ell_t^\eta$ is $\alpha$-exp-concave for $\alpha > 1$.

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.

We hope this clarification resolves the reviewer’s concerns regarding the exp-concavity and the technical novelty of our contributions.

Q2. Experiments

Thank 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.

Q3. Regarding constants depending on $D$, $K$, and $B$

Our 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:

• $D$ is the $\ell_2$-diameter of $\Theta$, the learner’s set of predictions.
• $K$ is the maximum $\ell_2$-diameter of $X_t$, the agent’s feasible action set.
• $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$.

In 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).

The 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.

Finally, 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).

Returning 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.

Appendix A provides a more detailed discussion on how these parameters influence the regret bounds, including comparisons with prior work.

Q4. Extension to non-linear objectives

Thank you for the question. While our paper focuses on linear objectives, the techniques extend to a broad class of forward problems.

If 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

$\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}$

so 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.

Finally, 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.

Q5. Regarding the $\log T$-gap

Whether 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.

We 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.