# Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis

arXiv: https://arxiv.org/abs/2501.13648 · HTML: https://mlsanity.com/paper/2501.13648/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 36 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Builds on (most cited first, 20 of 20)

- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [Data-driven Inverse Optimization with Imperfect Information](https://mlsanity.com/paper/1512.05489/) (2015)
- [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [An Online-Learning Approach to Inverse Optimization](https://mlsanity.com/paper/1810.12997/) (2018)
- [Learning Linear Programs from Optimal Decisions](https://mlsanity.com/paper/2006.08923/) (2020)
- [Inverse Optimization: Closed-form Solutions, Geometry and Goodness of fit](https://mlsanity.com/paper/1511.04650/) (2015)
- [Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming](https://mlsanity.com/paper/2301.11260/) (2023)
- [Generalized Inverse Optimization through Online Learning](https://mlsanity.com/paper/1810.01920/) (2018)
- [Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences](https://mlsanity.com/paper/2008.10460/) (2020)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Learning with Fitzpatrick Losses](https://mlsanity.com/paper/2405.14574/) (2024)

## Built on by (most cited first, 8 of 8)

- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes](https://mlsanity.com/paper/2609.09809/) (2026)
- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses](https://mlsanity.com/paper/2502.04889/) (2025)
- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)

## Abstract (arXiv)

This paper revisits the online learning approach to inverse linear optimization studied by B"armann et al. (2017), where the goal is to infer an unknown linear objective function of an agent from sequential observations of the agent's input-output pairs. First, we provide a simple understanding of the online learning approach through its connection to online convex optimization of Fenchel--Young losses. As a byproduct, we present an offline guarantee on the suboptimality loss, which measures how well predicted objectives explain the agent's choices, without assuming the optimality of the agent's choices. Second, assuming that there is a gap between optimal and suboptimal objective values in the agent's decision problems, we obtain an upper bound independent of the time horizon T on the sum of suboptimality and estimate losses, where the latter measures the quality of solutions recommended by predicted objectives. Interestingly, our gap-dependent analysis achieves a faster rate than the standard O(√T) regret bound by exploiting structures specific to inverse linear optimization, even though neither the loss functions nor their domains enjoy desirable properties, such as strong convexity.