Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis

• URL: http://arxiv.org/abs/2501.13648v3
• Date: Fri, 07 Feb 2025 23:35:18 GMT
• Title: Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis
• Authors: Shinsaku Sakaue, Han Bao, Taira Tsuchiya,
• Abstract summary: This paper revisits the online learning approach to inverse linear optimization studied by B"armann et al. The goal is to infer an unknown linear objective function of an agent from sequential observations of the agent's input-output pairs. We present an offline guarantee on the emphsuboptimality loss, which measures how well predicted objectives explain the agent's choices.
• Score: 22.123582043898647
• License:
• Abstract: This paper revisits the online learning approach to inverse linear optimization studied by B\"armann et al. (2017), where the goal is to infer an unknown linear objective function of an agent from sequential observations of the agent's input-output pairs. First, we provide a simple understanding of the online learning approach through its connection to online convex optimization of \emph{Fenchel--Young losses}. As a byproduct, we present an offline guarantee on the \emph{suboptimality loss}, which measures how well predicted objectives explain the agent's choices, without assuming the optimality of the agent's choices. Second, assuming that there is a gap between optimal and suboptimal objective values in the agent's decision problems, we obtain an upper bound independent of the time horizon $T$ on the sum of suboptimality and \emph{estimate losses}, where the latter measures the quality of solutions recommended by predicted objectives. Interestingly, our gap-dependent analysis achieves a faster rate than the standard $O(\sqrt{T})$ regret bound by exploiting structures specific to inverse linear optimization, even though neither the loss functions nor their domains enjoy desirable properties, such as strong convexity.

Related papers

• Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization [78.82586283794886]
  $chi2$-Preference Optimization ($chi$PO) is an efficient offline alignment algorithm provably robust to overoptimization. $chi$PO implements the principle of pessimism in the face of uncertainty via regularization. $chi$PO's simplicity and strong guarantees make it the first practical and general-purpose offline alignment algorithm provably robust to overoptimization.
  arXiv  Detail & Related papers  (2024-07-18T11:08:40Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  We find that regret grows sub-linearly at a rate $Thetaleft(mfrac12cdotfrac11-2-Tright)$, thus converging exponentially fast to $Theta(sqrtm)$. These findings underscore the benefits of limited online learning and optimization, in that even a few rounds can provide significant benefits as compared to a no-learning baseline.
  arXiv  Detail & Related papers  (2024-06-20T23:00:25Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  offline preference optimization is a key method for enhancing and controlling the quality of Large Language Model (LLM) outputs. We perform objective discovery to automatically discover new state-of-the-art preference optimization algorithms without (expert) human intervention. Experiments demonstrate the state-of-the-art performance of DiscoPOP, a novel algorithm that adaptively blends logistic and exponential losses.
  arXiv  Detail & Related papers  (2024-06-12T16:58:41Z)
• Offline Model-Based Optimization via Policy-Guided Gradient Search [30.87992788876113]
  We introduce a new learning-to-search- gradient perspective for offline optimization by reformulating it as an offline reinforcement learning problem. Our proposed policy-guided search approach explicitly learns the best policy for a given surrogate model created from the offline data.
  arXiv  Detail & Related papers  (2024-05-08T18:27:37Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  We study unconstrained Online Linear Optimization with Lipschitz losses. Motivated by the pursuit of instance optimality, we propose a new algorithm. Central to these results is a continuous time approach to online learning.
  arXiv  Detail & Related papers  (2023-09-27T21:54:52Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Proximal Point Imitation Learning [48.50107891696562]
  We develop new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning. We leverage classical tools from optimization, in particular, the proximal-point method (PPM) and dual smoothing. We achieve convincing empirical performance for both linear and neural network function approximation.
  arXiv  Detail & Related papers  (2022-09-22T12:40:21Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• Contextual Inverse Optimization: Offline and Online Learning [3.6739949215165164]
  We study the problems of offline and online contextual optimization with feedback information. We aim to minimize regret, which is defined as the difference between our losses and the ones incurred by an all-knowing oracle.
  arXiv  Detail & Related papers  (2021-06-26T13:09:52Z)

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.