Tight Generalization Bounds for Noiseless Inverse Optimization
Abstract
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(d/T) 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 this guarantee 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(d/T) 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.
Related
- Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
- Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space
- Characterizing Identifiability and Generalization for Inverse Receding-Horizon Linear-Quadratic Regulator Problems
BibTeX
@misc{fatemi2026tight,
title = {{Tight Generalization Bounds for Noiseless Inverse Optimization}},
author = {Pouria Fatemi and Hoomaan Maskan and Suvrit Sra and Peyman Mohajerin Esfahani},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.08866},
eprint = {2605.08866},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.08866},
}
RIS
TY - UNPB
TI - Tight Generalization Bounds for Noiseless Inverse Optimization
AU - Pouria Fatemi
AU - Hoomaan Maskan
AU - Suvrit Sra
AU - Peyman Mohajerin Esfahani
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2605.08866
UR - https://arxiv.org/abs/2605.08866
AB - 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(d/T) 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 this guarantee 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(d/T) 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.
ER -