Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisions

Akira Kitaoka

cs.AIOct 7, 2026

Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisions

Authors: Akira Kitaoka

Abstract

Inverse optimization estimates the weights of an objective function that explain observed decisions as optimal solutions, and is used in a variety of fields. For mixed-integer linear programs (MILPs), existing methods aim to reproduce the observations as optimal solutions, and thus learn compromise weights when the observations are suboptimal. We propose outperformance inverse optimization, which instead seeks weights that induce, at each state, an optimal solution outperforming the observed action in every component. We give a loss function that can be evaluated with forward-problem oracles alone and is thus applicable to MILPs, together with gradient-based and DC optimization algorithms for minimizing it. For weights inducing a unique outperforming optimal solution at all observations, we prove that the probability of failing to induce such a solution at a new state (the generalization error) is bounded by a quantity inversely proportional to the number of observations, and that this bound is tight in the number of observations up to logarithmic factors. In experiments on synthetic and real data, the proposed methods improve the prediction of solutions outperforming the actions over existing methods.

Figures & tables

Problem	PSG	ONS(FB)	MetaGrad(FB)	Episodes
Knapsack	241 /9/0	75/27/ 148	230 /4/16	250
Single machine	24 /51/0	30 /42/3	28 /47/0	75
Movie (MovieLens)	97 /2/1	45 /23/32	90 /9/1	100
Multi-cover (Cora)	92 /2/6	59 /19/22	72 /11/17	100
Multi-cover (ogbn-arxiv)	81 /15/4	74 /22/4	63 /30/7	100

Table 1. Comparison of the three pairs differing only in the loss function (OS-PSG vs. Sub-PSG, OS-ONS(FB) vs. Sub-ONS(FB), OS-MetaGrad(FB) vs. Sub-MetaGrad(FB)). The numbers of episodes on the same instances in which

\ell^{\mathrm{OP}}

at the point where the number of calls reaches

B

is smaller/equal/larger for the OS-loss variant (wins/ties/losses). The larger of wins and losses is shown in bold.

	PSG		ONS(FB)		MetaGrad(FB)		OS-DC
$d$	OS	Sub	OS	Sub	OS	Sub
20	98	16	34	0	86	6	90
40	96	0	2	0	52	0	88
60	92	0	0	0	46	0	86
80	90	0	0	0	8	0	82
100	76	0	0	0	12	0	84

Table 2. Knapsack problem: the fraction [%] of episodes that attained

\ell^{\mathrm{OP}}=0

at the point where the number of calls reaches

B=4000

. 50 episodes for each

d

. For each optimization method, the OS loss (OS) and the suboptimality loss (Sub) are shown side by side, and the higher one in each pair is shown in bold. The DC optimization uses only the OS loss. The median of

\ell^{\mathrm{OP}}

for each dimension is shown in Table 4 .

Figure 1. Relation between the worst 10% (the 90th percentile across episodes) of

\ell^{\mathrm{OP}}

(best-so-far) and the number of oracle calls. The vertical axis is

\ell^{\mathrm{OP}}+0.01

on a logarithmic scale, and

0.01

represents

\ell^{\mathrm{OP}}=0

. Since the actions are integer-valued,

\ell^{\mathrm{OP}}

takes discrete values in steps of

1/N

, and the percentiles are chosen from the observed values without interpolation. The colors indicate the optimization methods (PSG, MetaGrad(FB), ONS(FB), DC optimization); solid lines indicate the OS loss (proposed) and dashed lines the suboptimality loss (existing).

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Optimization method	Pseudocode	Remarks
Empirical mean of the suboptimality loss (existing)
Sub-PSG	PSG	Algorithm 8
Sub-ONS	ONS	Algorithm 9	state-by-state update, online-to-batch conversion ( Sakaue et al., 2025b )
Sub-MetaGrad	MetaGrad	Algorithm 9	state-by-state update, online-to-batch conversion ( Sakaue et al., 2025b )
Sub-ONS(FB)	ONS	Algorithm 10	FB
Sub-MetaGrad(FB)	MetaGrad	Algorithm 10	FB

Appendix

Table 3. The 13 compared methods. PSG is the projected subgradient method, ONS is the Online Newton Step ( Hazan et al., 2007 ) , and MetaGrad is van Erven and Koolen (2016) ; we also call these optimization methods learners. FB (full-batch) denotes the update that gives the learner the average of the subgradients over all states only once per iteration and does not use the averaged iterate (the average of the iterates so far). The online-to-batch conversion is the conversion that outputs the averaged iterate. The inner solvers CP, LV+CPF, and PB+CPF are the cutting-plane method, the level method with cutting-plane finishing, and the proximal bundle method with cutting-plane finishing, respectively ( Appendix D ). In the main text, OS-DC[PB+CPF]+SGF is simply written as OS-DC.

Figure 2. Relation between the worst 10% of

\ell^{\mathrm{OP}}

(best-so-far) and the number of oracle calls on the knapsack problem. The vertical axis and the lines are drawn as in Figure 1 .

Method	$d=20$	$d=40$	$d=60$	$d=80$	$d=100$
OS-PSG	0.00 (98)	0.00 (96)	0.00 (92)	0.00 (90)	0.00 (76)
Sub-PSG	0.15 (16)	0.20 (0)	0.23 (0)	0.28 (0)	0.35 (0)
OS-MetaGrad(FB)	0.00 (86)	0.00 (52)	0.08 (46)	0.35 (8)	0.38 (12)
Sub-MetaGrad(FB)	0.15 (6)	0.40 (0)	0.65 (0)	0.80 (0)	0.95 (0)
OS-ONS(FB)	0.10 (34)	0.40 (2)	0.70 (0)	0.95 (0)	1.15 (0)
Sub-ONS(FB)	0.15 (0)	0.40 (0)	0.62 (0)	0.70 (0)	0.88 (0)

Appendix

Table 4. Knapsack problem: median of

\ell^{\mathrm{OP}}

B=4000

oracle calls (the attainment rate [%] of

\ell^{\mathrm{OP}}=0

in parentheses). 50 episodes for each

d

. For each optimization method, the pair of the OS loss (proposed) and the suboptimality loss (existing) is shown, and the one with the smaller median in each pair (with the higher attainment rate in case of a tie) is shown in bold.

	Cora ( $d$ )					ogbn-arxiv ( $d$ )
Method	20	40	60	80	100	20	40	60	80	100
OS-PSG	0.78	2.58	4.40	5.72	6.82	0.57	2.40	4.30	6.50	9.30
Sub-PSG	1.25	3.00	4.95	6.25	7.47	1.12	2.95	4.85	7.22	9.40
OS-MetaGrad(FB)	0.97	2.92	5.25	6.75	7.80	0.78	2.73	4.65	7.18	9.55
Sub-MetaGrad(FB)	1.27	3.23	5.18	7.05	8.15	1.15	2.97	4.85	7.20	9.47
OS-ONS(FB)	1.00	3.05	5.22	6.88	8.00	0.82	2.67	4.68	6.92	9.43

Appendix

Table 5. Weighted multi-cover problem (left: Cora, right: ogbn-arxiv): median of

\ell^{\mathrm{OP}}

B=4000

oracle calls. 20 episodes for each

d

. For each optimization method, the pair of the OS loss (proposed) and the suboptimality loss (existing) is shown, and the one with the smaller median in each pair is shown in bold.

Method	$d=4$	$d=6$	$d=8$
OS-PSG	0.00 (100)	0.00 (100)	0.00 (96)
Sub-PSG	0.00 (88)	0.00 (72)	0.10 (44)
OS-MetaGrad(FB)	0.00 (100)	0.00 (100)	0.00 (96)
Sub-MetaGrad(FB)	0.00 (84)	0.00 (76)	0.30 (28)
OS-ONS(FB)	0.00 (100)	0.00 (100)	0.00 (84)
Sub-ONS(FB)	0.00 (84)	0.00 (52)	0.30 (40)

Appendix

Table 6. Single-machine scheduling problem: median of

\ell^{\mathrm{OP}}

B=2000

oracle calls (the attainment rate [%] of

\ell^{\mathrm{OP}}=0

in parentheses). 25 episodes for each

d

Method	$d=20$	$d=40$	$d=60$	$d=80$	$d=100$
OS-PSG	0.72 [0.59,1.01]	2.52 [2.02,2.90]	4.05 [3.65,4.22]	5.18 [4.57,5.71]	6.50 [5.65,7.09]
Sub-PSG	0.95 [0.70,1.11]	2.85 [2.44,3.17]	4.60 [4.40,5.11]	5.80 [5.39,6.53]	7.57 [6.84,7.98]
OS-MetaGrad(FB)	0.95 [0.79,1.10]	2.70 [2.60,3.10]	4.50 [4.09,4.79]	5.65 [5.42,6.19]	7.10 [6.50,7.75]
Sub-MetaGrad(FB)	1.30 [1.12,1.52]	3.25 [2.91,3.42]	4.88 [4.67,5.20]	6.18 [5.85,6.53]	7.90 [6.66,8.49]
OS-ONS(FB)	1.10 [0.85,1.30]	3.15 [2.91,3.31]	4.95 [4.49,5.16]	6.45 [6.01,6.76]	8.00 [7.08,8.49]
Sub-ONS(FB)	1.35 [1.19,1.51]	3.27 [2.95,3.40]	4.95 [4.67,5.15]	6.17 [5.85,6.65]	7.72 [6.96,8.26]

Appendix

Table 7. Movie selection problem with viewing costs: median of

\ell^{\mathrm{OP}}

B=4000

oracle calls. 20 episodes for each

d

. For each optimization method, the pair of the OS loss (proposed) and the suboptimality loss (existing) is shown, and the one with the smaller median in each pair is shown in bold.

Figure 3. Relation between the worst 10% of

\ell^{\mathrm{OP}}

(best-so-far) and the number of oracle calls on the single-machine scheduling problem and the movie selection problem with viewing costs. The vertical axis and the lines are drawn as in Figure 1 .

Method	$\ell^{\mathrm{OP}}$ median	interquartile range	attainment rate [%]	$\bar{\ell}^{\mathrm{OS}}$ median	time mean	time median
Sub-PSG	0.250	[0.150,0.300]	3	$4.9\times 10^{-4}$	1.3	1.3
Sub-ONS	0.150	[0.100,0.250]	9	$3.9\times 10^{-4}$	2.2	2.2
Sub-MetaGrad	0.350	[0.200,0.550]	3	$2.8\times 10^{-3}$	8.4	8.3
Sub-ONS(FB)	0.600	[0.300,0.800]	0	$6.2\times 10^{-3}$	1.4	1.4
Sub-MetaGrad(FB)	0.550	[0.300,0.850]	1	$5.5\times 10^{-3}$	2.4	2.4
OS-PSG	0.000	[0.000,0.000]	90	$0$	0.3	0.2

Appendix

Table 8. Knapsack problem (oracle-call budget

B=4000

). Each value is the median, over the 250 runs (

d\in\{20,40,60,80,100\}

, 50 episodes for each

d

), of the value at

B

oracle calls, and the attainment rate is the fraction of these 250 runs that attained

\ell^{\mathrm{OP}}=0

. For the time (in seconds), the mean is also shown.

Method	$\ell^{\mathrm{OP}}$ median	interquartile range	attainment rate [%]	$\bar{\ell}^{\mathrm{OS}}$ median	time mean	time median
Sub-PSG	0.000	[0.000,0.150]	68	$0$	17.7	2.8
Sub-ONS	0.500	[0.100,1.350]	23	$1.5\times 10^{-2}$	32.6	17.3
Sub-MetaGrad	0.000	[0.000,0.300]	52	$0$	24.9	11.8
Sub-ONS(FB)	0.000	[0.000,0.300]	59	$0$	24.6	13.7
Sub-MetaGrad(FB)	0.000	[0.000,0.200]	63	$0$	19.7	1.2
OS-PSG	0.000	[0.000,0.000]	99	$0$	6.3	1.1

Appendix

Table 9. Single-machine scheduling problem (oracle-call budget

B=2000

). Each value is the median, over the 75 runs (

d\in\{4,6,8\}

, 25 episodes for each

d

), of the value at

B

oracle calls, and the attainment rate is the fraction of these 75 runs that attained

\ell^{\mathrm{OP}}=0

. For the time (in seconds), the mean is also shown.

Method	$\ell^{\mathrm{OP}}$ median	interquartile range	attainment rate [%]	$\bar{\ell}^{\mathrm{OS}}$ median	time mean	time median
Sub-PSG	4.600	[2.438,6.000]	0	$3.1\times 10^{-2}$	106.7	95.3
Sub-ONS	3.550	[1.950,4.612]	0	$2.0\times 10^{-2}$	98.9	91.2
Sub-MetaGrad	3.425	[1.900,4.600]	0	$2.4\times 10^{-2}$	107.4	97.5
Sub-ONS(FB)	4.950	[2.950,6.312]	0	$5.0\times 10^{-2}$	39.6	40.4
Sub-MetaGrad(FB)	4.875	[2.913,6.300]	0	$5.4\times 10^{-2}$	76.1	62.5
OS-PSG	3.975	[2.025,5.362]	0	$1.2\times 10^{-2}$	75.7	81.1

Appendix

Table 10. Movie selection problem with viewing costs (oracle-call budget

B=4000

). Each value is the median, over the 100 runs (

d\in\{20,40,60,80,100\}

, 20 episodes for each

d

), of the value at

B

oracle calls, and the attainment rate is the fraction of these 100 runs that attained

\ell^{\mathrm{OP}}=0

. For the time (in seconds), the mean is also shown.

Method	$\ell^{\mathrm{OP}}$ median	interquartile range	attainment rate [%]	$\bar{\ell}^{\mathrm{OS}}$ median	time mean	time median
Sub-PSG	4.800	[2.787,6.338]	0	$7.0\times 10^{-2}$	18.9	16.9
Sub-ONS	4.500	[2.688,6.100]	0	$7.9\times 10^{-2}$	17.9	16.9
Sub-MetaGrad	4.600	[2.537,6.075]	0	$9.1\times 10^{-2}$	40.8	35.4
Sub-ONS(FB)	5.150	[2.888,6.812]	0	$1.1\times 10^{-1}$	17.7	16.2
Sub-MetaGrad(FB)	5.150	[2.975,7.075]	0	$1.1\times 10^{-1}$	21.8	20.3
OS-PSG	4.375	[2.362,5.900]	0	$6.3\times 10^{-2}$	8.9	8.7

Appendix

Table 11. Weighted multi-cover problem (Cora) (oracle-call budget

B=4000

). Each value is the median, over the 100 runs (

d\in\{20,40,60,80,100\}

, 20 episodes for each

d

), of the value at

B

oracle calls, and the attainment rate is the fraction of these 100 runs that attained

\ell^{\mathrm{OP}}=0

. For the time (in seconds), the mean is also shown.

Method	$\ell^{\mathrm{OP}}$ median	interquartile range	attainment rate [%]	$\bar{\ell}^{\mathrm{OS}}$ median	time mean	time median
Sub-PSG	4.650	[2.612,7.375]	0	$8.4\times 10^{-2}$	17.2	14.2
Sub-ONS	4.475	[2.663,6.650]	0	$3.4\times 10^{-2}$	16.3	14.6
Sub-MetaGrad	3.950	[2.012,6.013]	0	$7.2\times 10^{-2}$	36.5	31.1
Sub-ONS(FB)	4.650	[2.650,7.312]	0	$1.1\times 10^{-1}$	18.0	14.1
Sub-MetaGrad(FB)	4.650	[2.650,7.537]	0	$1.1\times 10^{-1}$	21.4	17.3
OS-PSG	4.200	[1.738,7.088]	0	$4.7\times 10^{-2}$	8.5	7.4

Appendix

Table 12. Weighted multi-cover problem (ogbn-arxiv) (oracle-call budget

B=4000

). Each value is the median, over the 100 runs (

d\in\{20,40,60,80,100\}

, 20 episodes for each

d

), of the value at

B

oracle calls, and the attainment rate is the fraction of these 100 runs that attained

\ell^{\mathrm{OP}}=0

. For the time (in seconds), the mean is also shown.

Explore similar work

Oct 6, 2025math.OC

Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions

Data-driven inverse optimization for mixed-integer linear programs (MILPs), which seeks to learn an objective function and constraints consistent with observed decisions, is important for building accurate mathematical models in a variety of domains, including power systems and scheduling. However, to the best of our knowledge, existing data-driven inverse optimization methods primarily focus on learning objective functions under known constraints, and learning both objective functions and constraints from data for MILPs remains largely unexplored. In this paper, we propose a two-stage approach for a class of inverse optimization problems in which the objective is a linear combination of given feature functions and the constraints are parameterized by unknown functions and thresholds. Our method first learns the constraints and then, conditioned on the learned constraints, estimates the objective-function weights. On the theoretical side, we provide finite-sample guarantees for solving the proposed inverse optimization problem. To this end, we develop statistical learning tools for pseudo-metric spaces under sub-Gaussian assumptions and use them to derive a learning-theoretic framework for inverse optimization with both unknown objectives and constraints. On the experimental side, we demonstrate that our method successfully solves inverse optimization problems on scheduling instances formulated as ILPs with up to 100 decision variables.

Akira Kitaoka

Mixed-Integer Programming Optimal Learner

Ask PDF

Jul 24, 2026math.OC

Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs

A data-driven inverse optimization problem (DDIOP) is the problem of estimating the objective-function parameters (weights) that explain observed optimal-solution data, and it arises in many applications, including integer linear programming (ILP). It is known that, by applying gradient-based optimization methods to the suboptimality loss, the inverse optimization of ILPs can be solved exactly within finitely many oracle iterations, and that the required number of iterations is bounded as

T=O(1/γ(\ell_{\mathrm{sub}})^2)

in terms of a problem-dependent geometric constant

γ(\ell_{\mathrm{sub}})

. However, no means of bounding

γ(\ell_{\mathrm{sub}})

from below as a function of the problem size has been available, and hence the number of iterations could not be given as an explicit function of the problem size. We therefore give, when the forward problem is an integer linear program (ILP), the number of iterations sufficient for projected subgradient descent applied to the suboptimality loss to achieve exact consistency with the observed data, as a fully explicit function of the number of samples, the dimension of the features, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set, the step-size parameter, and the Lipschitz constant of the suboptimality loss).

Akira Kitaoka

Linear Programming Optimal Sample Complexity Objective Functions

Ask PDF

May 9, 2026stat.ML

Tight Generalization Bounds for Noiseless Inverse Optimization

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.

Pouria Fatemi, Hoomaan Maskan, Suvrit Sra +1

Technical University of Munich, Germany · Uppsala University, Sweden · University of Toronto, Canada

Generalization Bounds Adversarial Robustness

Ask PDF

	PSG		ONS(FB)		MetaGrad(FB)		OS-DC
$d$	OS	Sub	OS	Sub	OS	Sub
20	98	16	34	0	86	6	90
40	96	0	2	0	52	0	88
60	92	0	0	0	46	0	86
80	90	0	0	0	8	0	82
100	76	0	0	0	12	0	84

	PSG		ONS(FB)		MetaGrad(FB)		OS-DC
$d$	OS	Sub	OS	Sub	OS	Sub
20	98	16	34	0	86	6	90
40	96	0	2	0	52	0	88
60	92	0	0	0	46	0	86
80	90	0	0	0	8	0	82
100	76	0	0	0	12	0	84

	PSG		ONS(FB)		MetaGrad(FB)		OS-DC
$d$	OS	Sub	OS	Sub	OS	Sub
20	98	16	34	0	86	6	90
40	96	0	2	0	52	0	88
60	92	0	0	0	46	0	86
80	90	0	0	0	8	0	82
100	76	0	0	0	12	0	84