Fenchel-Young Estimators of Perturbed Utility Models

Xi Lin, Yafeng Yin, Tianming LiuarXiv 2026 · arXiv

TL;DR

This paper introduces a unified, globally convex estimation framework for Perturbed Utility Models (PUMs) using the Fenchel-Young loss. By integrating Wasserstein Distributionally Robust Optimization (DRO), the authors provide a mathematically rigorous way to estimate choice models even with sparse data, revealing that standard $\ell_2$-regularization and Hinge loss are actually specific limiting cases of this robust framework.

What Problem Does This Paper Address?

Discrete choice modeling—predicting how people choose between alternatives like transportation modes or consumer products—has long relied on Maximum Likelihood Estimation (MLE). While MLE works beautifully for the classic Multinomial Logit (MNL) model, it breaks down when applied to more modern, flexible frameworks like Perturbed Utility Models (PUMs).

The authors identify two "pathologies" in MLE:

  1. The Zero-Probability Singularity: Modern models like Sparsemax can predict a 0% probability for some options. MLE involves taking the logarithm of these probabilities; since $\log(0)$ is undefined, the math literally explodes.
  2. Non-Convexity: For certain models (like those with heavy-tailed distributions), the MLE objective function isn't "bowl-shaped" (convex), meaning optimization algorithms can get stuck in local traps.

Furthermore, the "curse of limited data" often leads to overfitting and biased estimates when sample sizes are small—a common reality in high-cost survey research.

Methods

The researchers propose a two-step solution:

  1. The Fenchel-Young (FY) Loss: Instead of the logarithmic scoring of MLE, they use a loss function based on Fenchel-Legendre duality. This loss measures the "duality gap" between the predicted utility and the observed choice. Crucially, this objective is globally convex for any PUM and remains numerically stable even when probabilities are zero.
  2. Wasserstein DRO: To handle data scarcity, they wrap the FY loss in a Distributionally Robust Optimization framework. This creates an "ambiguity set" (a ball of possible data distributions) around the observed data using the Wasserstein metric. They then solve for the "worst-case" scenario within that ball to ensure the model is "immunized" against noise and small-sample bias.

To solve these complex minimax problems, they employ a Projected Extragradient algorithm, which handles the saddle-point optimization efficiently.

Datasets

  • Synthetic Datasets: Used to stress-test the model under controlled conditions of high variance, small sample sizes ($N=20$ to $200$), and varying degrees of sparsity.
  • Swissmetro Benchmark: A classic real-world dataset from a 1998 survey regarding a hypothetical mag-lev rail system in Switzerland. It involves choices between Train, Swissmetro, and Private Car.

Key Insights and Ideas

  • Geometric Unification: Perhaps the most elegant finding is that their robust estimator acts as a "bridge" between different fields. They prove that as you change the "budget" for uncertainty, the model mathematically transforms into either standard $\ell_2$-regularization (Ridge regression) or a multi-class Hinge loss (common in Support Vector Machines).
  • Endogenous Scoring: Unlike generic loss functions (like squared error) that are "bolted on," the Fenchel-Young loss is endogenous—it is generated by the same potential function that defines the choice model itself. This makes it the most "natural" way to estimate these models.
  • The Scaling Law: The authors derive a specific formula for how to tune the "uncertainty radius" ($\epsilon$) based on the number of samples ($N$) and the number of attributes ($d$). This provides a data-driven guideline for researchers to avoid expensive cross-validation.

Key Results

  • Stability in Sparse Regimes: While MLE failed catastrophically on Sparsemax models due to numerical instability, the FY estimator remained stable and recovered true parameters accurately.
  • Massive Error Reduction: In low-data scenarios ($N=20$) on the Swissmetro dataset, the proposed robust estimators reduced the estimation error gap by nearly two orders of magnitude compared to standard MLE.
  • Robustness to Clustering: When data was sampled by "individual" (where one person answers multiple questions, creating correlated noise), the DRO framework significantly outperformed standard methods by expanding the "uncertainty radius" to account for the lack of diversity in the sample.

Limitations and Future Work

  • Fixed Perturbations: Currently, the researcher must choose the "perturbation function" (like entropy or quadratic) beforehand. The authors suggest future work could involve learning the shape of this function directly from the data.
  • Structured Choice Sets: The current work focuses on explicit, finite sets of choices. Extending this to "combinatorial" choices—like picking a specific path through a massive road network (stochastic route choice)—presents a high-dimensional challenge for future investigation.
  • Computational Overhead: While the authors optimized the algorithm, PUM estimation with non-separable functions still requires an "embedded optimization layer" that is more computationally demanding than simple Logit models.

Summary updated

Abstract

The Perturbed Utility Model framework offers a powerful generalization of discrete choice analysis, unifying models like Multinomial Logit and Sparsemax through convex optimization. However, standard Maximum Likelihood Estimation (MLE) faces severe theoretical and numerical challenges when applied to this broader class, particularly regarding non-convexity and instability in sparse regimes. To resolve these issues, this paper introduces a unified estimation framework based on the Fenchel-Young loss. By leveraging the intrinsic convex conjugate structure of PUMs, we demonstrate that the Fenchel-Young estimator guarantees global convexity and bounded gradients, providing a mathematically natural alternative to MLE. Addressing the critical challenge of data scarcity, we further extend this framework via Wasserstein Distributionally Robust Optimization. We first derive an exact finite-dimensional reformulation of the infinite-dimensional primal problem, establishing its theoretical convexity. However, recognizing that the resulting worst-case constraints involve computationally intractable inner maximizations, we subsequently construct a tractable safe approximation by exploiting the global Lipschitz continuity of the Fenchel-Young loss. Through this tractable formulation, we uncover a rigorous geometric unification: two canonical regularization techniques, standard L2-regularization and the margin-enforcing Hinge loss, emerge mathematically as specific limiting cases of our distributionally robust estimator. Extensive experiments on synthetic data and the Swissmetro benchmark validate that the proposed framework significantly outperforms traditional methods, recovering stable preferences even under severe data limitations.
BibTeX
@misc{lin2026fenchel,
  author = {Xi Lin and Yafeng Yin and Tianming Liu},
  title = {{Fenchel-Young Estimators of Perturbed Utility Models}},
  year = {2026},
  eprint = {2602.21376},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.21376},
  howpublished = {arXiv},
}
Figure