# Tight Generalization Bounds for Noiseless Inverse Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 9 May 2026.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [Inverse Optimization with Noisy Data](https://mlsanity.com/paper/1507.03266/) (2015)
- [Data-driven Inverse Optimization with Imperfect Information](https://mlsanity.com/paper/1512.05489/) (2015)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms](https://mlsanity.com/paper/2305.07730/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Inverse Optimization via Learning Feasible Regions](https://mlsanity.com/paper/2505.15025/) (2025)
- [Inverse Optimization of Convex Risk Functions](https://mlsanity.com/paper/1607.07099/) (2016)
- [Inverse Optimization for Routing Problems](https://mlsanity.com/paper/2307.07357/) (2023)
- [Offline Reinforcement Learning via Inverse Optimization](https://mlsanity.com/paper/2502.20030/) (2025)

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

- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (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)
- [Optimal and Efficient Online Inverse Optimization](https://mlsanity.com/paper/2610.08735/) (2026)
- [Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisions](https://mlsanity.com/paper/2610.09890/) (2026)

## Abstract (arXiv)

Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context--action data. We study noiseless IO, where demonstrations are generated by a ground-truth objective. We provide a high-probability O(fracdT) generalization bound for the induced action set, where d is the number of unknown parameters and T is the size of the training dataset. We strengthen these guarantees under additional conditions that ensure uniqueness of the chosen action, bringing our IO guarantees in line with best-arm identification results in the bandit literature. We further show that the O(fracdT) rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret. Notably, the resulting regret lower bound matches the corresponding upper bounds in the adversarial setting, indicating that the stochastic IO setting is effectively adversarial for the class of estimators studied here. Finally, we propose a parameter-free algorithm with lower per-iteration complexity than generic solvers. Experiments validate the predicted rates and illustrate the tightness of our bounds.