A Fenchel-Young Loss Approach to Data-Driven Inverse Optimization

Zhehao Li, Yanchen Wu, Xiaojie Mao · 2025

Read A Fenchel-Young Loss Approach to Data-Driven Inverse Optimization by Zhehao Li, Yanchen Wu, Xiaojie Mao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16120.txt.

Introduction

Zhehao Li, Yanchen Wu, and co-authors reframe a classic estimation problem through a modern loss function, in a 2025 paper. Inverse optimization works backward: given the choices a decision maker made, infer the hidden costs or goals that explain them. Real observations are noisy and often less than perfect, which breaks older methods or slows them badly.

The team connect the problem to the Fenchel-Young loss, a tool built for predicting structured outputs. That link yields a method trainable by plain gradient steps, far faster than earlier solvers. Theory backs the estimates, and tests on simulated and real data show gains in accuracy of the recovered goals and in the quality of later decisions.

Catalog record

CREATORZhehao Li, Yanchen Wu, Xiaojie Mao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16120

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Fenchel-Young Loss Approach to Data-Driven Inverse Optimization Zhehao Li, Yanchen Wu, Xiaojie Mao Abstract Data-driven inverse optimization seeks to estimate unknown parameters in an optimization model from observations of optimization solutions. Many existing methods are ineffective in handling noisy and suboptimal solution observations and also suffer from computational challenges. In this paper, we build a connection between inverse optimization and the Fenchel-Young (FY) loss originally designed for structured prediction, proposing a FY loss approach to data-driven inverse optimization. This new approach is amenable to efficient gradient-based optimization, hence much more efficient than existing methods. We provide theoretical guarantees for the proposed method and use extensive simulation and real-data experiments to demonstrate its significant advantage in parameter estimation accuracy, decision error and computational speed. † † runningauthor: Li et al. † † runningtitle: A Fenchel-Young Loss Approach to Data-Driven Inverse Optimization † † authors: Tsinghua University, 100084 Beijing, China, [email protected] Tsinghua University, 100084 Beijing, China, [email protected] Tsinghua University, 100084 Beijing, China, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction Inverse optimization is a fundamental problem in operations research and machine learning, aiming to estimate unknown parameters in an optimization model from observations of solutions ( Ahuja and Orlin 2001 ) . Inverse optimization is important in many applications, such as consumer utility modeling ( Saez-Gallego et al. 2016 , Saez-Gallego and Morales 2017 ) , vehicle routing ( Chen et al. 2021 , Zattoni Scroccaro et al. 2024 ) , medical decision-making ( Chan et al. 2014 , Aswani et al. 2019 ) , and portfolio risk management ( Li 2021 , Yu et al. 2023 ) , etc. For example, in the consumer utility modeling problem, customers’ utility function may involve unknown parameters characterizing their preference for different products. These parameters may be estimated from observations of utility-maximizing customers’ purchase decisions. By recovering the unknown parameters in the optimization, analysts can better understand the underlying decision-making process and make better decisions of their interest. In data-driven inverse optimization, the observed decisions may be often noisy, suboptimal and even infeasible, which poses significant challenges for estimating the unknown parameters ( Chan et al. 2023 ) . Aswani et al. (2018) discovered that many existing approaches may not effectively recover the true parameter value, such as the Karush-Kuhn-Tucker approximation (KKA) approach ( Keshavarz et al. 2011 ) and the variational inequality approximation (VIA) approach ( Bertsimas et al. 2015 ) . Aswani et al. (2018) then proposed a parameter estimator such that the average squared distance between the decision induced by the estimated parameter and the observed decision is minimized and showed its effectiveness theoretically and numerically. However, this approach involves non-convex optimization solved by brute-force enumeration, restricted to only small-scale problems. For larger problems, Aswani et al. (2018) relied on a semiparametric approach that is more scalable than enumeration. However, this approach it is not amenable to first-order gradient-based optimization, hence still computationally challenging for large-scale problems. In this paper, we propose an alternative surrogate loss function approach to overcome the drawbacks of existing methods. Specifically, we consider a regularized version of the optimization problem of interest and adapt the suboptimality loss in Chan et al. (2014) , Chan and Lee (2018) to the regularized problem. We find that the resulting loss coincides with the Fenchel-Young (FY) loss originally designed for structured prediction tasks such as classification and ranking ( Blondel et al. 2020 , Blondel et al. 2022 ) . This builds a novel connection between FY loss and data-driven inverse optimization, providing new perspectives on both. Importantly, the FY loss is differentiable with a closed-form gradient and it is convex for linear problems. This allows for efficient first-order optimization like stochastic gradient descent (SGD), thereby achieving significant computational advantage over existing methods. By extending existing FY loss theory, we also provide some theoretical guarantees for the proposed method. We evaluate our method on synthetic and real-world datasets, demonstrating that our approach outperforms existing methods in terms of parameter estimation accuracy, generating high quality decisions, and computational efficiency. In particular, the proposed method can achieve robust performance even in settings where existing methods easily give degenerate solutions. 1.1 Related Work Inverse Optimization Early work on inverse optimization focused on parameter recovery from noiseless observations of decision solutions ( Ahuja and Orlin 2001 , Chan et al. 2014 , Chan and Lee 2018 ) . Bärmann et al. (2017) studied inverse optimization with noiseless solutions in the online setting, focusing on minimizing decision suboptimality, while Besbes et al. (2023) aimed to estimate parameters by minimizing worst-case regret. To handle noisy and suboptimal decisions in data-driven inverse-optimization, Aswani et al. (2018) proposed a squared distance loss approach and a semiparametric approach and compared their methods with methods in Keshavarz et al. (2011) , Bertsimas et al. (2015) . Their methods were also expanded to the online setting ( Dong et al. 2018 ) . Chan et al. (2019) proposed a goodness-of-fit measure for data-driven inverse-optimization. We refer to Chan et al. (2023) for a comprehensive survey of literature on classical inverse optimization and data-driven inverse optimization and, Mohajerin Esfahani et al. (2018) , Birge et al. (2022) , Lin et al. (2024) for some recent advances in enhancing the robustness of inverse optimization methods. Our paper considers the offline setting in Aswani et al. (2018) and proposes a Fenchel-Young loss approach to inverse optimization, addressing the computational challenges with existing methods while achieving rigorous theoretical guarantees. Structured Prediction with FY Loss The Fenchel-Young (FY) loss was originally introduced for structured prediction (SP) tasks such as multi-class classification and ranking ( Blondel et al. 2019 , Blondel et al. 2020 , Blondel et al. 2022 , e.g.,) . We refer to Blondel et al. (2020) for a systematic introduction to FY loss. In this paper, we build the connection between FY loss and data-driven inverse-optimization. Our methodology and theory build on and extend the FY loss literature, broadening the applicability of FY loss. In particular, the traditional structured prediction tasks for which FY loss is designed typically involve optimization or ranking over simple sets like simplex, while inverse optimization may often involve operations problems with more complex structure. 2 Problem Formulation 2.1 Forward and Inverse Optimization In this paper, we study the inverse linear optimization problem with noisy observed decisions. Let x\in\mathbb{R}^{d} be the decision vector, u\in\mathbb{R}^{m} the context variable, and \theta^{\star}\in\mathbb{R}^{p} the unknown parameter vector to be estimated. The forward optimization problem (FOP) is given by: \operatorname{FOP}(\theta^{\star},u):=\max_{x}\{h(\theta^{\star};u)^{\top}x\mid g(u,x)\preceq 0\}. (1) Here h:\mathbb{R}^{p}\times\mathbb{R}^{m}\to\mathbb{R}^{d} represents the cost function, and function g:\mathbb{R}^{m}\times\mathbb{R}^{d}\to\mathbb{R}^{q} defines the constraints. Both h and g are assumed known, leaving \theta^{\star} as the only unknown parameter. We define the feasible region of FOP as \mathcal{X}(u):=\{x\in\mathbb{R}^{d}\mid g(u,x)\preceq 0\} , and use x^{\star}(\theta^{\star};u)\in\mathcal{X}^{\star}(\theta^{\star};u) to denote a generic optimal solution of \operatorname{FOP}(\theta^{\star},u) , where \mathcal{X}^{\star}(\theta;u):=\argmax_{x}\{h(\theta;u)^{\top}x\mid g(u,x)\preceq 0\} is the optimal solution set. We assume that h(\theta;u) is continuous in \theta and u , while g(u,x) is continuous in both u and x and convex in x for each fixed u . These conditions mean that the FOP in Equation 1 has a linear objective with convex constraints 1 1 1 While

Read the complete text