Inexact Proximal Point and Tseng Algorithms with Nonsummable Errors to Solve Monotone Inclusions

This paper establishes, for the first time, the convergence of practical Inexact Proximal Point and Tseng Algorithms for solving monotone inclusions in Hilbert spaces under nonsummable errors by leveraging Tikhonov regularization, contraction properties, and R-continuity theory.

The Gist

Imagine you are trying to find the exact center of a dark, foggy room (the "solution"). You have a compass (an algorithm) that points you toward the center. In a perfect world, your compass would be flawless, and you would walk straight to the center.

However, in the real world, your compass is a bit shaky. Sometimes it points slightly left, sometimes slightly right. This "shakiness" is what mathematicians call error.

For a long time, mathematicians believed that for you to eventually reach the exact center, these shakiness errors had to get smaller and smaller until they disappeared completely. They thought the total amount of "wobble" in your entire journey had to add up to a tiny, finite number. If the wobble kept happening at a steady, noticeable level forever, they thought you would never stop wandering in circles and would never actually arrive at the center.

This paper says: "Not necessarily, but you won't get the exact center either."

The authors, Ba Khiet Le, Boris S. Mordukhovich, and Michel Théra, have discovered a new way to navigate that works even if your compass keeps shaking with a steady, non-vanishing amount of error. However, there is a crucial distinction: you do not reach the exact center. Instead, you settle into a stable, "good enough" spot that stays within a small, predictable distance of the center, wobbling slightly around that neighborhood forever.

Here is how they did it, using simple metaphors:

1. The Problem: The "Summable" Rule vs. Real-World Noise

Traditionally, to guarantee you find the exact center, the rule was: The errors must eventually vanish.
Think of this like walking toward a target while being pushed by the wind. If the wind gets weaker and weaker until it stops, you will eventually reach the target exactly. But if the wind keeps blowing at a steady, annoying speed (non-summable error), traditional math said you'd never get there.

In the real world, however, errors (like computer rounding noise) often never fully vanish. They stay at a small, fixed level. The old rules said this meant failure; this paper says it means "stable approximation."

2. The Solution: Adding a "Magnetic Pull" (Tikhonov Regularization)

The authors' secret weapon is Tikhonov regularization.
Imagine that instead of just walking on a flat floor, you are walking on a gentle, curved slope that leads directly to the center. Even if the wind (the error) keeps pushing you sideways, the slope (the mathematical "pull") constantly drags you back toward the path.

In their math, they add a small, artificial "force" (represented by $\epsilon$) to the problem. This force makes the landscape "steeper" and more defined. It turns the flat, slippery ground into a bowl shape. Even if you are pushed off course by a steady error, the bowl shape ensures you don't wander off forever. You won't stop exactly at the bottom (the exact center), but you will stay trapped in a small, safe circle right next to it.

3. The Two Algorithms: The Hiker and the Guide

The paper tests this idea on two specific types of "hikers" (algorithms):

• The Inexact Proximal Point Algorithm (IPPA): This is like a hiker who takes a step, checks the map, and corrects their path. The authors show that even if the map has a constant, small blur (error), the "magnetic slope" ensures the hiker ends up staying within a small, bounded distance of the target, never settling exactly on it but never wandering far away.
• The Inexact Tseng Algorithm (ITA): This is a more complex hiker who has to deal with two different types of terrain at once. The authors show that even with this extra complexity and constant errors, the "magnetic slope" still works to keep the hiker in a stable neighborhood of the goal.

4. The "R-Continuity" Safety Net

To prove this works, they use a concept called R-continuity.
Think of this as a safety net that says: "If you are close to the target, your steps will be predictable." It guarantees that the "magnetic pull" doesn't behave erratically. As long as the map doesn't suddenly twist in a crazy way near the center, the hiker will stay within a predictable distance of the goal, wobbling slightly but never escaping the neighborhood.

5. The Result: "Good Enough" is the New Goal

The paper proves that with this new method:

• You do not need the errors to disappear to get a result.
• You do not need the errors to add up to a tiny number (which is hard to check).
• You just need the errors to stay within a fixed, manageable limit (like a compass that is always off by no more than 2 degrees).

If you set your parameters correctly, the hiker will stop wandering off into the distance and settle into a stable, bounded orbit around the true center. You will never converge to the exact center with steady errors, but you will stay close enough to be useful.

Why This Matters (According to the Paper)

In real-world computer calculations, it is often impossible to make errors disappear completely. Computers always have a tiny bit of "noise" or "rounding error" that never goes away.

This paper claims that by using their "magnetic slope" technique, we can trust these algorithms to find stable, practical results even when the computer's errors are stubborn. It shifts the focus from "perfect precision" (which requires the old, strict rule that errors must vanish) to "stable approximation."

Crucially, the rule they use is very practical: "Keep every error below a fixed small limit." This is much easier to check and enforce in real life than the old rule, which required errors to shrink over time and sum up to a tiny number.

In summary: The paper teaches us that even if your tools are imperfect and the errors never stop, you can still find a stable, good-enough position near the solution by changing the shape of the problem. You won't reach the exact center, but you will stay safely within a small, predictable distance of it, which is often all we need in the real world.

Technical Summary

Technical Summary: Inexact Proximal Point and Tseng Algorithms with Nonsummable Errors

Problem Statement
The paper addresses the problem of solving monotone inclusions of the form $0 \in Ax$ in a real Hilbert space $H$, where $A: H \rightrightarrows H$ is a set-valued maximally monotone operator. The primary focus is on the convergence of practical, inexact versions of two classical algorithms: the Proximal Point Algorithm (PPA) and the Tseng Algorithm (for composite inclusions $0 \in Ax + Bx$).

A critical constraint of this work is the treatment of computational errors. Unlike most existing literature, which assumes that error sequences are summable (i.e., $\sum \|y_k\| < \infty$, implying errors vanish asymptotically), this paper investigates algorithms under bounded, nonsummable errors. Specifically, the error sequence $(y_k)$ satisfies $\|y_k\| \le \delta$ for a fixed tolerance $\delta > 0$. This condition is motivated by practical scenarios where computational errors never tend to zero; while relative-error criteria are theoretically possible, they are often difficult to verify in practice, whereas absolutely bounded errors are easy to verify and represent a realistic model for finite-precision computations where errors may persist.

Methodology
The authors propose a novel approach that avoids reliance on the summability of errors. Instead, the methodology relies on three core components:

1. Tikhonov Regularization: The original inclusion problem is regularized by adding a strongly monotone term $\epsilon I$ (where $\epsilon > 0$). For the PPA, the operator becomes $\tilde{A} = A + \epsilon I$. For the composite problem, the regularized inclusion is $0 \in \tilde{A}x + Bx$. This regularization ensures the associated resolvent operators possess strong contraction properties.
2. Contraction Properties: By utilizing the strong monotonicity induced by the regularization term, the authors demonstrate that the resolvent operators (and the associated Tseng mapping) become contractive. This allows for the control of error propagation without requiring the errors to decay to zero.
3. R-Continuity Theory: The convergence analysis leverages the recently developed theory of R-continuity for set-valued mappings. Specifically, the authors assume that the inverse operator (e.g., $A^{-1}$ or $(A+B)^{-1}$) is R-continuous at the origin. This property allows the authors to bound the distance between the solution of the regularized problem and the solution set of the original problem.

Key Contributions and Results

• Inexact Proximal Point Algorithm (IPPA):
  The paper analyzes the IPPA defined by $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$ under the bounded error assumption $\|y_{k+1}\| \le \delta$, where $y_{k+1}$ represents the per-iteration computational error in evaluating the resolvent operator.

  • Result: Under bounded, nonsummable errors, the iterates $x_k$ do not converge to an exact solution of the original inclusion. Instead, the sequence remains asymptotically within a stable, explicitly bounded neighborhood of the solution set $S = \text{zer}(A)$. The authors derive a constructive upper bound for the asymptotic distance:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    where $\rho$ is the modulus of R-continuity of $A^{-1}$ at 0, and $a$ is the norm of the minimal norm element in $S$.
  • Convergence Condition: It is crucial to note that obtaining true (weak) convergence of $x_k$ to an actual solution point requires the classical summable-error condition ($\sum \|y_k\| < \infty$); this stronger conclusion is not available under the bounded-error setting of this paper. However, by choosing $\delta = \epsilon^2$, the bound vanishes as $\epsilon \to 0$, ensuring the algorithm produces arbitrarily accurate approximate solutions (in the sense of a bounded neighborhood) as the regularization parameter approaches zero.

• Inexact Tseng Algorithm (ITA):
  The approach is extended to the composite problem $0 \in Ax + Bx$, where $B$ is single-valued, monotone, and Lipschitz continuous. The ITA is applied to the Tikhonov-regularized problem.

  • Result: Under the assumption that $(A+B)^{-1}$ is R-continuous at 0, the authors prove that the ITA sequence does not converge to a solution but remains within a bounded distance of the solution set $S$. The derived error bound is:
    $$d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • Similar to the IPPA, setting $\delta = \epsilon^2$ yields convergence to the solution set (in terms of distance) as the regularization parameter $\epsilon$ approaches zero, but not point-wise convergence of the iterates under nonsummable errors.

Significance and Claims
The paper claims to be the first in the literature to establish the stability and error bounds of practical inexact PPA and Tseng algorithms under the sole assumption of bounded, nonsummable errors.

The authors emphasize that their analysis reveals the strong monotonicity induced by the Tikhonov regularization term, rather than the classical summability of errors, is the essential mechanism ensuring the stability and well-posedness of these algorithms in the presence of persistent errors. They argue that the standard summability assumption is often difficult to guarantee in practice, whereas the bounded-error condition is computationally realistic.

The proposed techniques are presented as a flexible framework that can be extended to analyze other inexact algorithms for optimization-related problems involving nonsummable perturbations. The paper does not propose new applications or experimental validations but focuses strictly on the theoretical justification of these algorithms under relaxed error conditions, explicitly clarifying that they provide bounded approximate solutions rather than exact convergence.