# Approximation Analysis of the Entropic Penalty in Quadratic Programming

arXiv: https://arxiv.org/abs/2509.20031 · HTML: https://mlsanity.com/paper/2509.20031/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2025.

## Built on by (most cited first, 3 of 3)

- [Sliced Inner Product Gromov-Wasserstein Distances](https://mlsanity.com/paper/2605.08546/) (2026)
- [Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing](https://mlsanity.com/paper/2609.03094/) (2026)
- [Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems](https://mlsanity.com/paper/2609.31848/) (2026)

## Abstract (arXiv)

Quadratic assignment problems are a fundamental class of combinatorial optimization problems which are ubiquitous in applications, yet their exact resolution is NP-hard. To circumvent this impasse, it was proposed to regularize such problems via an entropic penalty, leading to computationally tractable proxies. Indeed, this enabled efficient algorithms, notably in the context of Gromov-Wasserstein (GW) problems, but it is unknown how well solutions of the regularized problem approximate those of the original one for small regularization parameters. Treating the broader framework of general quadratic programs (QPs), we establish that the approximation gap decays exponentially quickly for concave QPs, while the rate for general indefinite or convex QPs can be as slow as linear. Our analysis builds on the study of the entropic penalty in linear programming by leveraging a new representation for concave QPs, which connects them to a family of linear programs with varying costs. Building on these results, we design an algorithm which, given a local solution of the entropic QP, returns a candidate minimizer of the original QP and certifies it. We apply these findings to a general class of discrete GW problems, yielding new variational forms and the first exponentially vanishing entropic approximation bound in the GW literature.