# Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 26 Jan 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Decision Trees for Decision-Making under the Predict-then-Optimize Framework](https://mlsanity.com/paper/2003.00360/) (2020)
- [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)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Structured Prediction with Projection Oracles](https://mlsanity.com/paper/1910.11369/) (2019)
- [Risk Guarantees for End-to-End Prediction and Optimization Processes](https://mlsanity.com/paper/2012.15046/) (2020)
- [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)
- [Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences](https://mlsanity.com/paper/2008.10460/) (2020)

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

- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis](https://mlsanity.com/paper/2501.13648/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods](https://mlsanity.com/paper/2405.14273/) (2024)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs](https://mlsanity.com/paper/2607.22263/) (2026)
- [A Fenchel-Young Loss Approach to Data-Driven Inverse Optimization](https://mlsanity.com/paper/2502.16120/) (2025)
- [Contextual Preference Distribution Learning](https://mlsanity.com/paper/2603.17139/) (2026)
- [OTSS: Output-Targeted Soft Segmentation for Contextual Decision-Weight Learning](https://mlsanity.com/paper/2605.00193/) (2026)
- [Decision-Driven Regularization: A Blended Model for Learning and Optimization](https://mlsanity.com/paper/2608.15124/) (2026)
- [Geometric Identification in Predict-Then-Optimize Learning](https://mlsanity.com/paper/2609.33472/) (2026)

## Abstract (arXiv)

In this paper, we study the predict-then-optimize problem where the output of a machine learning prediction task is used as the input of some downstream optimization problem, say, the objective coefficient vector of a linear program. The problem is also known as predictive analytics or contextual linear programming. The existing approaches largely suffer from either (i) optimization intractability (a non-convex objective function)/statistical inefficiency (a suboptimal generalization bound) or (ii) requiring strong condition(s) such as no constraint or loss calibration. We develop a new approach to the problem called textitmaximum optimality margin which designs the machine learning loss function by the optimality condition of the downstream optimization. The max-margin formulation enjoys both computational efficiency and good theoretical properties for the learning procedure. More importantly, our new approach only needs the observations of the optimal solution in the training data rather than the objective function, which makes it a new and natural approach to the inverse linear programming problem under both contextual and context-free settings; we also analyze the proposed method under both offline and online settings, and demonstrate its performance using numerical experiments.