{
  "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(\\Phi\\mu)+\\lambda R(\\mu)$ into a data-fidelity Fenchel--Young loss and a regularizer Fenchel--Young loss, \\[ \\Delta(\\mu,h)=L_F(\\Phi\\mu\\parallel h)+\\lambda L_R(\\mu\\parallel\\eta),\\qquad \\eta=-\\Phi^\\star h/\\lambda, \\] valid for any primal point $\\mu$ and any dual point $h$. The data-fidelity term $F$ is strictly convex, so wherever $F^\\star$ is differentiable the loss $L_F(\\Phi\\mu\\parallel h)$ is the Bregman divergence of~$F$ between the prediction $\\Phi\\mu$ and $\\nabla F^\\star(h)$, and it vanishes exactly at \\emph{Mirror Alignment} $h=\\nabla F(\\Phi\\mu)$. Evaluated at a dual-feasible point $\\tilde h$, the gap~$\\Delta(\\mu,\\tilde h)$ is computable and \\emph{oracle-free}, meaning that it uses no knowledge of the solution, and it bounds the suboptimality of $\\mu$. 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(\\Phi\\mu^\\star\\parallel 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 $\\epsilon$. 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^\\star$ and tilted by the prediction $\\Phi\\mu$: 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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.17629",
  "author_total": 2,
  "authors": [
    {
      "name": "Pierre-Cyril Aubin-Frankowski"
    },
    {
      "name": "Yohann de Castro"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/caehndctaw5h7.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.17629",
  "fulltext_url": null,
  "id": "caehndctaw5h7",
  "issns": [],
  "landing_url": "https://hal.science/hal-05736861v1",
  "language": "en",
  "licence": "CC-BY-SA-4.0",
  "licence_label": "CC BY-SA 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by-sa/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.OC"
    ],
    [
      "arxiv",
      "math.ST"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "arxiv",
      "stat.TH"
    ],
    [
      "hal",
      "0.math"
    ],
    [
      "hal",
      "0.stat"
    ],
    [
      "hal",
      "1.math.math-oc"
    ],
    [
      "hal",
      "1.math.math-st"
    ],
    [
      "hal",
      "1.stat.ml"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://hal.science/hal-05736861/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-03",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/caehndctaw5h7.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:27Z",
      "native_id": "hal-05736861",
      "source": "hal",
      "url": "https://hal.science/hal-05736861v1"
    },
    {
      "first_seen": "2026-10-30T12:22:04Z",
      "native_id": "2609.17629",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.17629"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.ST",
      "subfield": "statistics"
    }
  ],
  "title": "Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems",
  "title_text": "Fenchel-Young Duality Gaps: Certified Early Stopping for Regularized Inverse Problems",
  "type": "preprint",
  "updated_at": "2026-10-30T12:22:10Z",
  "url": "https://research.draconitic.com/paper/caehndctaw5h7",
  "venue": "HAL",
  "versions": []
}