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

arXiv:2607.22263 · math.OC, cs.AI, cs.LG, stat.ML · Submitted 2026-07-24 · Read on arXiv

Akira Kitaoka

math.OC, cs.AI, cs.LG, stat.ML

Submitted: 2026-07-24

Comments: 34 page. This paper was splited from arXiv:2405.14273v7

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 18× in this paper · explained in 3 episodes
• Consistency — 15× in this paper · explained in 3 episodes
• Combinatorial Optimization — 3× in this paper · explained in 2 episodes
• Objective Function — 3× in this paper · explained in 2 episodes
• Reinforcement Learning — 3× in this paper · explained in 4 episodes
• Loss Function — 2× in this paper · explained in 2 episodes
• Multi-objective Optimization — 2× in this paper · explained in 4 episodes
• Adaptation — 1× in this paper · explained in 1 episode
• Degeneracy — 1× in this paper · explained in 3 episodes
• Ensemble Learning — 1× in this paper · explained in 2 episodes
• Regularization — 1× in this paper · explained in 3 episodes
• Robustness — 1× in this paper · explained in 5 episodes

Sources

• An Online-Learning Approach to Inverse Optimization
• Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences
• Handbook of Convergence Theorems for (Stochastic) Gradient Methods
• Introduction to Online Convex Optimization
• Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods
• A proof of convergence of inverse reinforcement learning for multi-objective optimization
• A proof of imitation of Wasserstein inverse reinforcement learning for multi-objective optimization
• Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
• Petrov-Galerkin operator inference with application to stability-encouraging identification