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

Abstract

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).

Disclosure

“LPs, and the exponential dependence of the iteration bound on d is genuine. Sharpening the general ILP lower bound and improving its N d dependence are left for future work. Acknowledgement We also thank GPT-5.2, GPT-5.4, Opus 4.7, and Opus 4.8, Fable 5 for their assistance with proofreading the manuscript.”

PDF page 29

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T19:04:45.486881Z

Structural counts