AI Insight
This paper addresses inverse optimization problems for integer linear programs, where the goal is to estimate objective function parameters from observed optimal solutions. The researchers provide the first explicit bound on the number of iterations needed for projected subgradient descent to achieve exact consistency with observed data, expressing this bound as a polynomial function of problem size parameters including sample count, feature dimension, feature ranges, and constraint matrix structure.
Why it matters
This work advances the theoretical understanding of data-driven inverse optimization, which has applications in machine learning, preference learning, and system identification. By providing explicit iteration complexity bounds, the results enable practitioners to better estimate computational requirements when applying these methods to real-world integer programming problems.
Understand the Science
arXiv:2607.22263v1 Announce Type: cross
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/gamma(ell_{mathrm{sub}})^2)$ in terms of a problem-dependent geometric constant $gamma(ell_{mathrm{sub}})$. However, no means of bounding $gamma(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).
Source: Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs