Discrepancy Based Early Stopping in Iterative Solvers

127 concepts69 papers

When recovering a hidden signal or image from noisy measurements—a classic challenge known as an inverse problem—we often rely on iterative optimization algorithms. Intuitively, it seems that running an optimizer longer should always yield a better, more accurate solution.

However, for ill-posed problems, the exact opposite happens. The reconstruction improves at first, reaches a peak of high fidelity, and then rapidly degrades as the algorithm continues to run. To get the best result, we must stop the algorithm early.

The Paradox of Semi-Convergence

This counterintuitive behavior is known as semi-convergence. To understand why it happens, we have to look at how iterative solvers treat different components of data.

In an ill-posed inverse problem, the mapping from the underlying signal to the observed data is unstable; small variations in the data (like measurement noise) correspond to massive oscillations in the reconstructed solution. As Yuling Jiao et al. explain in Alternating Direction Method of Multipliers for Linear Inverse Problems, iterative optimization algorithms act as implicit regularizers. In the early iterations, the solver captures the large-scale, structurally stable components of the signal—the low-frequency information.

Once the true signal is mostly recovered, subsequent iterations begin to invert the unstable components of the system, fitting the high-frequency noise present in the data. Without a principled way to halt the algorithm, the solver overfits the noise, introducing severe artifacts and causing the solution to diverge from the ground truth. This behavior has been documented across a wide variety of optimization frameworks, from primal-dual methods for convex regularizers (Cesare Molinari et al.) to stochastic mirror descent (Jing Huang et al.).

The Discrepancy Principle

How do we know when to stop if we do not have access to the clean ground-truth signal? The answer lies in monitoring the residual—the difference between our model's current forward prediction and the observed noisy data.

While the error relative to the true signal follows a U-shaped curve (decreasing and then increasing), the residual relative to the noisy data decreases monotonically. If we let the algorithm run indefinitely, the residual will eventually hit zero, meaning we have perfectly fit a noisy dataset.

The Morozov discrepancy principle provides a mathematically rigorous threshold: terminate the iteration the exact moment the norm of the residual drops below the expected noise level of the data. As Otmar Scherzer demonstrated in A multi-level algorithm for the solution of moment problems, this data-driven stopping criterion balances measurement noise against missing high-frequency components without requiring prior knowledge of the signal's exact bandwidth.

By stopping when the residual variance matches the noise variance, the algorithm effectively freezes the optimization before noise amplification can occur. In inverse scale space flows, Guy Gilboa et al. showed that this property guarantees a monotonic decrease in true error up until the stopping threshold is met, providing a reliable point of termination.

Universality Across Solvers

The beauty of discrepancy-based stopping is its versatility; it transforms standard optimization routines into stable regularization tools across diverse mathematical domains:

  • Ensemble Methods: In derivative-free optimization like Ensemble Kalman Inversion (EKI), the ensemble members naturally collapse toward a solution but are highly prone to overfitting noise. Andrew M. Stuart et al. showed in Convergence Analysis of Ensemble Kalman Inversion: The Linear, Noisy Case that deterministic discrepancy-based stopping rules are significantly more robust than fixed-time Bayesian stopping rules. Similarly, Marco Iglesias et al. utilized this principle to maintain parameter stability in complex physical systems.
  • Stochastic Optimization: For large-scale problems where computing full gradients is computationally impossible, Qinian Jin et al. integrated the discrepancy principle directly into a step-size adaptation strategy for Stochastic Mirror Descent. By setting the step-size to zero when the mini-batch error falls below the noise threshold, the algorithm dynamically manages semi-convergence on the fly.
  • Untrained Neural Networks: The principle even extends to deep learning. When using untrained convolutional neural networks as implicit priors (such as Deep Image Prior), Tim Jahn et al. proved that stopping gradient descent via the discrepancy principle achieves minimax optimal convergence rates, turning network architecture into a formal regularizer.

Alternative Data-Driven Stopping Metrics

When the exact noise level is unknown, researchers rely on alternative statistical or structural indicators to guide termination:

  • Stein's Unbiased Risk Estimator (SURE): SURE allows algorithms to estimate the true reconstruction error using only the noisy observations. Yiqing Wang implemented SURE-guided termination to prevent artifact introduction in piecewise linear image denoising. More recently, Batu Ozturkler et al. used SURE for real-time hyperparameter tuning and early stopping in diffusion-based MRI reconstruction, preventing hallucinations without ground-truth data.
  • Duality Gaps: For non-smooth convex regularizers (like the $\ell_1$ norm), Cesare Molinari et al. proposed monitoring the difference between primal and dual objectives. This duality gap provides a clean signal to stop the solver when it reaches the minimum-norm interpolator manifold but before noise fitting begins.
  • Residual Ratios: In greedy signal pursuit algorithms, San-Jun He et al. demonstrated that tracking the ratio of residuals between consecutive iterations can serve as an adaptive stopping criterion, halting the pursuit when relative improvements flatten out.

Key Foundational Work

Signal reconstruction using sparse tree representations (2005) — contributed 2 concept elements to this direction.
A multi-level algorithm for the solution of moment problems (1999) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 69 papers
  2. Version 1 · 2026-10-04 · 46 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_discrepancy_based_stopping_bee534ca,
  title = {discrepancy-based stopping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrepancy-based-stopping/rdr_bee534ca45ac4d94a26f9c9cba1457a6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_discrepancy_based_stopping_bee534ca_v2,
  title = {discrepancy-based stopping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrepancy-based-stopping/rdr_bee534ca45ac4d94a26f9c9cba1457a6/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}

See something wrong? Report a mistake