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

Akira Kitaoka

math.OCJul 24, 2026

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

Authors: Akira Kitaoka

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

Explore similar work

Sep 9, 2026cs.LG

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of

\log T

between the regret upper bound

O(d \log T)

and the lower bound

Ω(d)

is unresolved (here

T

is the total number of rounds and

d

is the dimension). When the action set is M-convex, the regret is known to be bounded by

O(d \log d)

, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake in the case where the correct action is uniformly separated from the other candidates, and applies it to online gradient descent, the online Newton step, and MetaGrad. The number of mistakes is then bounded, for all three, by a quantity independent of

T

; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes

O(d^2)

when the forward problem is an integer linear program, that is, the factor

\log T

is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

Akira Kitaoka

Sublinear Regret Convex Optimization Mixed-Integer Linear Programming Convex Sets Newton

Ask PDF

May 8, 2026cs.LG

Sample Complexity of Stochastic Optimization with Integer Variables

We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuous optimization problem. We show that integer optimization can sometimes require strictly more samples and sometimes strictly smaller number of samples, depending on the structure of the objective and constraints. 1. For Lipschitz objectives over subsets of the

\ell_\infty

ball, the statistical complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization is exactly the same as stochastic linear optimization with just bound constraints. 2. For Lipschitz objectives over subsets of the

\ell_2

ball, we show that integer optimization can require strictly smaller sample size compared to the continuous setting in a certain regime. To get to this result, we also establish tight sample complexity results for nonconvex continuous stochastic optimization which, to the best of our knowledge, do not appear in prior work. 3. For strongly convex, smooth objectives, integer optimization has high statistical complexity compared to the continuous setting. In particular, we show that integer optimization requires

Ω(1/ε^2)

samples to report an

ε

-approximate solution, compared to the well-known

O(1/ε)

sample complexity from the continuous optimization literature.

Hongyu Cheng, Yinghao Zheng, Marco Molinaro +1

Stochastic Optimization Mixed-Integer Linear Programming Sample Complexity Optimal Sample Complexity Spectral Norm

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

Generalization Bounds Adversaries

Ask PDF