Research map / Bandits and online learning / Online convex optimization and games

Tight Generalization Bounds for Noiseless Inverse Optimization

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes noiseless inverse optimization as a scenario program, proving O(d/T) set-level and action-level generalization bounds for consistent estimators, matching lower bounds, and O(d log T) cumulative regret with a Polyak-subgradient solver.

Problem

Generalization guarantees for inverse optimization: inferring a linear objective parameter from context-action demonstrations so that the learned greedy actions match the expert on unseen contexts, with tight rates in dimension d and sample size T.

Approach

Views the consistency constraints of noiseless IO as a random scenario program (each demonstration gives a random convex feasibility constraint), so scenario-optimization tail bounds give O(d/T) mismatch bounds; an incenter estimator with a strict margin yields unique actions and action-level guarantees, and a matching lower-bound instance shows tightness.

Key results

• Set-level mismatch bound: with T >= 2(d+log(1/beta)), P(mismatch) <= 2(d+log(1/beta))/T with probability 1-beta.
• Lower bound: sup over instances of inf over objectives gives violation probability at least beta = sum_{i<d} C(T,i) eps^i (1-eps)^(T-i), so O(d/T) is tight for the considered estimator class.
• Regret lower bound d log((T+1)/(d+1)) for cumulative regret, matching the known adversarial O(d log T) upper bounds.
• Empirically, mismatch decays roughly as O(1/T) for d in {5,10,20}; the incenter estimator performs best and the Polyak method tracks the sub-optimality estimator.

Surprising findings

• The stochastic IO setting is effectively as hard as the adversarial one for the considered estimator class, since the Omega(d log T) regret lower bound matches adversarial upper bounds.
• Set-level guarantees can be vacuous: a feasible estimator can yield full-line argmax sets with zero set-level mismatch but no action-level identifiability.

Limitations

• Lower bounds hold only for the considered class of consistent estimators with monotone transforms of linear objectives.
• Polyak-method iterates are not guaranteed to lie in the consistency set after finite iterations, so the theory does not directly cover them.
• Analysis assumes i.i.d. contexts, noiseless demonstrations, and bounded features with covariance diversity.

Experimental setup

Datasets: synthetic contextual linear decision data

Benchmarks: synthetic contextual linear decision model (K=15 actions, d in {5,10,20})

Metrics: generalization mismatch probability (GE_T) instantaneous regret cumulative regret

Baselines: theta_sub (sub-optimality consistency estimator) Polyak subgradient estimator

Builds on: scenario optimization best-arm identification Freedman inequality online inverse optimization

Closest papers by meaning

• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.87)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.86)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · similarity 0.86)
• Conformal Inverse Optimization (NeurIPS 2024 · similarity 0.86)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.86)
• Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces (NeurIPS 2024 · similarity 0.85)