# Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 15 Sep 2026.

## Builds on (most cited first, 13 of 13)

- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Learning with Fenchel-Young Losses](https://mlsanity.com/paper/1901.02324/) (2019)
- [The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm](https://mlsanity.com/paper/2505.16932/) (2025)
- [Lion Secretly Solves Constrained Optimization: As Lyapunov Predicts](https://mlsanity.com/paper/2310.05898/) (2023)
- [Sparse Optimization on Measures with Over-parameterized Gradient Descent](https://mlsanity.com/paper/1907.10300/) (2019)
- [On Representer Theorems and Convex Regularization](https://mlsanity.com/paper/1806.09810/) (2018)
- [Exact Support Recovery for Sparse Spikes Deconvolution](https://mlsanity.com/paper/1306.6909/) (2013)
- [The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy](https://mlsanity.com/paper/1811.06416/) (2018)
- [The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems](https://mlsanity.com/paper/1507.01562/) (2015)
- [FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures](https://mlsanity.com/paper/2312.05993/) (2023)
- [Learning from samples: inverse problems over measures](https://mlsanity.com/paper/2505.07124/) (2025)
- [Towards Off-the-grid Algorithms for Total Variation Regularized Inverse Problems](https://mlsanity.com/paper/2104.06706/) (2021)
- [The Smoothed Duality Gap as a Stopping Criterion](https://mlsanity.com/paper/2403.12579/) (2024)

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

- [Riemannian Gradient Descent for Gaussian Mixture Models with unknown diagonal covariances](https://mlsanity.com/paper/2609.30220/) (2026)

## Abstract (arXiv)

We study computable error bounds and certified early stopping for regularized inverse problems, where a data-fidelity term is traded against a regularizer. The analysis relies on an exact duality-gap identity that splits the total gap of F(Phiμ)+λ R(μ) into a data-fidelity Fenchel--Young loss and a regularizer Fenchel--Young loss,  Delta(μ,h)=LF(Phiμparallel h)+λ LR(μparallelη),qquad η=-Phi^star h/λ,  valid for any primal point μ and any dual point h. The data-fidelity term F is strictly convex, so wherever F^star is differentiable the loss LF(Phiμparallel h) is the Bregman divergence of~F between the prediction Phiμ and nabla F^star(h), and it vanishes exactly at Mirror Alignment h=nabla F(Phiμ). Evaluated at a dual-feasible point tilde h, the gap~Delta(μ,tilde h) is computable and oracle-free, meaning that it uses no knowledge of the solution, and it bounds the suboptimality of μ. Under the source condition, the same Fenchel--Young losses give a priori bounds on the estimation and prediction errors. Their scale is the irreducible model and noise error LF(Phiμ^starparallel h^star), which vanishes exactly when Mirror Alignment holds at the certificate. This gives an early-stopping rule: run the algorithm until the regularizer Fenchel--Young loss falls below a tolerance ε. A constructive version of the Bro ndsted--Rockafellar theorem then turns the current pair into an exact dual-feasible one, and this proxy lifts to an exact primal certificate. We build the proxy by a proximal step in the geometry of the fidelity, with Bregman kernel F^star and tilted by the prediction Phiμ: it recovers the Euclidean step of Carlier when F is the squared error, and it reduces the duality gap by the regularizer Fenchel--Young loss, up to a second-order remainder that vanishes in the quadratic case. Our running example is the Generalized Beurling--Lasso (GBL), where R is the total-variation norm on signed measures. It contains the classical Beurling--Lasso, obtained with the squared error, and also covers robust, logistic, entropic and inverse-optimal-transport losses. The same duality gap certifies deep-learning optimizers such as Lion-K and Muon, in their proximal form, as solvers of the regularized program. A companion paper by the same authors builds on these error bounds to establish exact support recovery for the GBL under a non-degenerate source condition.