Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems
Abstract
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(Φμ)+λ R(μ) into a data-fidelity Fenchel--Young loss and a regularizer Fenchel--Young loss, Δ(μ,h)=LF(Φμ∥ h)+λ LR(μ∥η), η=−Φ⋆ h/λ, valid for any primal point μ and any dual point h. The data-fidelity term F is strictly convex, so wherever F⋆ is differentiable the loss LF(Φμ∥ h) is the Bregman divergence of~F between the prediction Φμ and ∇ F⋆(h), and it vanishes exactly at \emph{Mirror Alignment} h=∇ F(Φμ). Evaluated at a dual-feasible point h̃, the gap~Δ(μ,h̃) is computable and \emph{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 \emph{a priori} bounds on the estimation and prediction errors. Their scale is the irreducible model and noise error LF(Φμ⋆∥ h⋆), 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 Br\o ndsted--Rockafellar theorem then turns the current pair into an exact \emph{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⋆ and tilted by the prediction Φμ: 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.
Related
- On optimal stopping problems with full information and rank-dependent reward
- Early stopping of stochastic variance reduced gradient for linear inverse problems by the discrepancy principle
- Local W2,1p convergence of penalization for time-inconsistent stopping problems
- Monotone Multiple Stopping and Last-Success Problems
- Data-driven stochastic asymptotic regularization for ill-posed inverse problems with a posteriori and heuristic stopping
BibTeX
@misc{aubinfrankowski2026fenchelyoung,
title = {{Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems}},
author = {Pierre-Cyril Aubin-Frankowski and Yohann de Castro},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17629},
eprint = {2609.17629},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05736861v1},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems
AU - Pierre-Cyril Aubin-Frankowski
AU - Yohann de Castro
PY - 2026
DA - 2026/09/03
PB - HAL
DO - 10.48550/arxiv.2609.17629
UR - https://hal.science/hal-05736861v1
AB - 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(Φμ)+λ R(μ) into a data-fidelity Fenchel--Young loss and a regularizer Fenchel--Young loss, Δ(μ,h)=L_F(Φμ∥ h)+λ L_R(μ∥η), η=−Φ^⋆ h/λ, valid for any primal point μ and any dual point h. The data-fidelity term F is strictly convex, so wherever F^⋆ is differentiable the loss L_F(Φμ∥ h) is the Bregman divergence of~F between the prediction Φμ and ∇ F^⋆(h), and it vanishes exactly at \emph{Mirror Alignment} h=∇ F(Φμ). Evaluated at a dual-feasible point h̃, the gap~Δ(μ,h̃) is computable and \emph{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 \emph{a priori} bounds on the estimation and prediction errors. Their scale is the irreducible model and noise error L_F(Φμ^⋆∥ h^⋆), 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 Br\o ndsted--Rockafellar theorem then turns the current pair into an exact \emph{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^⋆ and tilted by the prediction Φμ: 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.
ER -