Tight Generalization Bounds for Noiseless Inverse Optimization

• URL: http://arxiv.org/abs/2605.08866v1
• Date: Sat, 09 May 2026 10:33:38 GMT
• Title: Tight Generalization Bounds for Noiseless Inverse Optimization
• Abstract summary: Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context--action data.<n>We provide a high-probability $O(fracdT)$ bound for the induced action set, where $d$ is the number of unknown parameters and $T$ is the size of the training dataset.<n>We show that the $O(fracdT)$ rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret.
• Score: 20.72173263660803
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  Black-box optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations.<n>We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters.
  arXiv  Detail & Related papers  (2026-05-29T14:24:54Z)
• DARTS: Targeting Prognostic Covariates in Budget-Constrained Sequential Experiments [47.61857875238484]
  We introduce Dynamic Adaptive Rerandomization via Thompson Sampling (DARTS)<n>DARTS treats covariate acquisition as a sequential optimization problem embedded within a design-based causal inference task.<n>We derive a Bayes risk bound for the acquisition layer that matches the minimax lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2026-05-07T17:27:51Z)
• Estimation of Toeplitz Covariance Matrices using Overparameterized Gradient Descent [1.7188280334580195]
  We revisit Toeplitz covariance estimation through the lens of simple descent (GD)<n>We show that when $K = P$, GD may converge to suboptimal solutions.<n>We propose an accelerated GD variant with separate learning rates for amplitudes and frequencies.
  arXiv  Detail & Related papers  (2025-11-03T14:07:53Z)
• Constrained Linear Thompson Sampling [39.724313550777715]
  Constrained Linear Thompson Sampling (COLTS) is a sampling-based framework that selects actions by solving perturbed linear programs.<n>We develop two main variants: S-COLTS, which ensures zero risk and $widetildeO(sqrtd3 T)$ regret given a safe action, and R-COLTS, which achieves $widetildeO(sqrtd3 T)$ regret and risk with no instance information.
  arXiv  Detail & Related papers  (2025-03-03T20:44:58Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Adaptive importance sampling for heavy-tailed distributions via $\alpha$-divergence minimization [2.879807093604632]
  We propose an AIS algorithm that approximates the target by Student-t proposal distributions. We adapt location and scale parameters by matching the escort moments of the target and the proposal. These updates minimize the $alpha$-divergence between the target and the proposal, thereby connecting with variational inference.
  arXiv  Detail & Related papers  (2023-10-25T14:07:08Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  In contextual bandits, an agent sequentially makes actions from a time-dependent action set based on past experience. We propose the first online continuous hyperparameter tuning framework for contextual bandits. We show that it could achieve a sublinear regret in theory and performs consistently better than all existing methods on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2023-02-18T23:31:20Z)
• Adaptive Noisy Data Augmentation for Regularized Estimation and Inference in Generalized Linear Models [15.817569026827451]
  We propose the AdaPtive Noise Augmentation (PANDA) procedure to regularize the estimation and inference of generalized linear models (GLMs) We demonstrate the superior or similar performance of PANDA against the existing approaches of the same type of regularizers in simulated and real-life data.
  arXiv  Detail & Related papers  (2022-04-18T22:02:37Z)
• Partial Identification with Noisy Covariates: A Robust Optimization Approach [94.10051154390237]
  Causal inference from observational datasets often relies on measuring and adjusting for covariates. We show that this robust optimization approach can extend a wide range of causal adjustment methods to perform partial identification. Across synthetic and real datasets, we find that this approach provides ATE bounds with a higher coverage probability than existing methods.
  arXiv  Detail & Related papers  (2022-02-22T04:24:26Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Adversarial Robustness Guarantees for Gaussian Processes [22.403365399119107]
  Gaussian processes (GPs) enable principled computation of model uncertainty, making them attractive for safety-critical applications. We present a framework to analyse adversarial robustness of GPs, defined as invariance of the model's decision to bounded perturbations. We develop a branch-and-bound scheme to refine the bounds and show, for any $epsilon > 0$, that our algorithm is guaranteed to converge to values $epsilon$-close to the actual values in finitely many iterations.
  arXiv  Detail & Related papers  (2021-04-07T15:14:56Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDAT crafts perturbations in the low-dimensional subspace formed by the sparse component of the input sample and that of an adversarial sample. LSD works directly in the image pixel domain to guarantee that non-$ell$ constraints, such as sparsity, are satisfied.
  arXiv  Detail & Related papers  (2021-03-19T13:10:47Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  We consider multi-armed bandits with heavy-tailed rewards, whose $p$-th moment is bounded by a constant $nu_p$ for $1pleq2$. We propose a novel robust estimator which does not require $nu_p$ as prior information. We show that an error probability of the proposed estimator decays exponentially fast.
  arXiv  Detail & Related papers  (2020-10-24T10:44:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.