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

Summary

This paper develops computable error bounds and certified early-stopping rules for regularized inverse problems of the form min F(Φμ) + λR(μ), with F a strictly convex fidelity on a Hilbert space and R a weak-* lower semicontinuous regularizer on a dual Banach space (e.g., the total-variation norm on measures). Its core result is an exact algebraic decomposition of the duality gap into a data-fidelity and a regularizer Fenchel–Young loss (Theorem 1); at a dual-feasible certificate the gap is computable, oracle-free, and bounds objective suboptimality. Under the source condition, the same losses yield a priori estimation and prediction bounds whose scale is the irreducible fidelity loss L_F(Φμ*∥h*) (Theorem 3). A constructive Brøndsted–Rockafellar argument (Theorem 4), refined by a mirror proximal step with kernel F* (Propositions 4–5, Corollary 6), upgrades approximate primal–dual pairs to exact dual-feasible proxies, recovering Carlier's Euclidean step when F is quadratic. The framework is instantiated on the Generalized Beurling–Lasso with least-squares, logistic, Poisson, KL, Huber and inverse-optimal-transport fidelities, and several regularizers (TV, group TV, analysis sparsity, nuclear norm). Experiments (public notebook) show the gap upper-bounds the true optimality gap along CPGD on synthetic 1D super-resolution, and certifies proximal-form Lion-K/ISTA and Muon/SVT on ℓ1 and nuclear-norm instances. Limitations: no algorithm-specific stopping-time rates, small synthetic-only experiments, and the deep-learning-optimizer certification applies only to proximal surrogates.