Tight Generalization Bounds for Noiseless Inverse Optimization
Authors: Pouria Fatemi, Hoomaan Maskan, Suvrit Sra et al.
Summary
The authors study inverse optimization (IO), where you observe someone's actions and try to figure out what objective function they were optimizing. They focus on the noiseless case—when demonstrations perfectly reflect some ground-truth objective—and prove tight statistical bounds showing you need roughly d/T samples (d parameters, T training examples) to generalize well. They also show this rate can't be beaten and propose a faster algorithm.
Main takeaways:
- Inverse optimization infers the parameters of someone's objective by watching context-action pairs (like watching a chess player and reverse-engineering their evaluation function)
- The generalization error is O(d/T) and this rate is tight—you can't do fundamentally better with any consistent estimator
- When actions are uniquely determined, the guarantees match bandit-style "best arm identification" results
- Surprisingly, the stochastic setting is effectively as hard as the adversarial one for these estimators
- They provide a parameter-free algorithm that's computationally cheaper than generic solvers
Relevance
Not directly related to my persona/midtraining work—this is about inferring objective functions from observed behavior, not about conditioning LM behavior on markers or prompts.
Abstract
arXiv:2605.08866v1 Announce Type: new 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}(\frac{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 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}(\frac{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.