betaFeedback

WorksMathematics

Convergence Guarantees for the Broximal Point Method under Perturbations

Abstract

The Broximal Point Method (BPM) of Gruntkowska et al. (2025) comes with strong guarantees for convex optimization: under convexity alone, it terminates after finitely many steps and converges linearly in function value, with bounds that do not depend on the condition number or on any other regularity property of the objective. Each iteration, however, requires the exact minimization of the objective over a ball, which is generally intractable. As a first step toward implementable variants, we study the method when these subproblems are solved only approximately. We introduce and analyze Inexact BPM, which replaces the exact broximal point by an approximation and makes no assumption on how this approximation is obtained. Under summable or sufficiently small errors, we bound the number of iterations needed to reach a neighborhood of the set of minimizers, and these bounds remain independent of the regularity of the objective. Under the weaker requirement that the errors stay below the ball radius, we prove sublinear convergence in function value for the exact broximal points underlying the perturbed iterates, valid until the target neighborhood is reached, and we recover linear rates under bounded sublevel sets or strong convexity.

Introduction

We consider the problem

min⁡x∈Rdϕ(x),(1)\min_{x\in\mathbb{R}^{d}} \phi(x), \tag*{(1)}

where ϕ:Rd→R∪{+∞}\phi:\mathbb{R}^{d}\to\mathbb{R}\cup\{+\infty\} is proper, closed, and convex. We assume that ϕ\phi has a nonempty set of minimizers, that is,

X⋆:=arg min⁡x∈Rd ϕ(x)≠∅.(2)\mathcal{X}_{\star}:=\underset{x\in\mathbb{R}^{d}}{\operatorname{arg\,min}}\ \phi(x)\ne\varnothing. \tag*{(2)}

Since X⋆\mathcal{X}_{\star} is nonempty, the minimum is attained. We denote the corresponding optimal value by

ϕ⋆:=min⁡x∈Rdϕ(x).(3)\phi_{\star}:=\min_{x\in\mathbb{R}^{d}}\phi(x). \tag*{(3)}

Minimizing a convex function is a fundamental problem in optimization, with applications spanning signal processing, operations research, and the training of large-scale machine learning models.

A classical algorithmic framework for solving (1) is the Proximal Point Method (PPM), originally introduced by Martinet [1970] and later studied by Rockafellar [1976]. PPM is an iterative scheme in which a quadratic penalty term is added to the convex objective function. Starting from a point xkx_k, the next iterate xk+1x_{k+1} is the solution of the following minimization problem,

xk+1=arg min⁡x∈Rd{ϕ(x)+12γk∥x−xk∥2},(4)x_{k+1}=\underset{x\in\mathbb{R}^{d}}{\operatorname{arg\,min}}\left\{\phi(x)+\frac{1}{2\gamma_k}\lVert x-x_k\rVert^{2}\right\}, \tag*{(4)}

where γk>0\gamma_k>0 acts as a stepsize parameter that controls the trade-off between minimizing the objective function and remaining close to the current iterate. By adding the quadratic penalty term to the objective, PPM requires a strongly convex minimization subproblem to be solved at every iteration. For nonsmooth convex functions, PPM is known to converge sublinearly [9], whereas linear convergence is achieved under the additional assumption of strong convexity [21].

While PPM relies on a soft quadratic regularization, the Broximal Point Method (BPM), recently introduced by Gruntkowska et al. [2025], utilizes a hard ball constraint. The next iterate of the Exact BPM algorithm (cf. Algorithm 1) is the exact minimizer of the objective function over the ball Bt(xk)B_t(x_k) of radius tt centered at the current iterate xkx_k,

xk+1∈arg min⁡x∈Bt(xk)ϕ(x).(5)x_{k+1} \in\operatorname*{arg\,min}_{x \in B_t(x_k)} \phi(x). \tag*{(5)}

Under additional differentiability and smoothness assumptions, this update can be viewed as normalized gradient descent on the ball envelope [8]. The hard constraint yields stronger guarantees than those available for PPM. Under convexity alone, Exact BPM reaches a minimizer after finitely many steps, and its iteration bound depends only on the initial distance to the set of minimizers, not on the condition number or any other regularity property of the objective. Its function values also converge linearly, and the contraction factor improves as the iterates approach the set of minimizers [19] (Gruntkowska et al. 2025).

The broximal framework connects to trust-region methods [5], normalized gradient descent [14], and ball-oracle complexity [3, 4]. In particular, Carmon et al. [2020, Appendix A] analyze the iteration of an exact ball-optimization oracle, which is Exact BPM in our notation, for strictly convex objectives. Gruntkowska and Richtárik [2025] extend the convergence results to non-Euclidean geometries. This makes the framework relevant to recent deep learning optimizers with a similar non-Euclidean structure, such as Muon [11], Scion [17], and Gluon [18], all of which can be interpreted as approximate broximal updates applied to surrogate subproblems [Gruntkowska and Richtárik, 2025].

Neither BPM nor PPM is directly implementable because the proximal and ball-constrained subproblems (4) and (5) rarely admit a closed-form solution. In the case of PPM, this has not hindered the development of implementable algorithms that substitute the exact proximal step with an approximation, such as proximal-gradient methods [16] and operator splitting techniques [6, 2].

These implementable methods rely on the underlying framework’s robustness to computational errors. Early work by Rockafellar [1976] showed that global convergence of PPM is preserved when the approximation errors form a summable sequence. This was extended to more general error models [10, 25] and stochastic settings [22, 1, 20] (Tanyassov et al. 2026). For implementable algorithms, Schmidt et al. [2011] established that the convergence rates of proximal-gradient methods are preserved under controlled deterministic errors in the gradient or proximal evaluations.

Motivated by these extensions of PPM, we study how BPM behaves under similar perturbations. We introduce Inexact BPM (cf. Algorithm 2), in which each subproblem is solved approximately, so that the iterates deviate from the exact broximal points. We impose no structure on how the approximation is obtained, so our guarantees hold for any inner solver that returns a point within the prescribed distance of the exact broximal point. We leave the design of solver-specific implementations to future work.

Our main question is which guarantees of Exact BPM survive such perturbations, in particular finite termination and complexity bounds that do not depend on the regularity of the objective. Such guarantees are not available for classical PPM under convexity alone. We show that finite, regularity-independent hitting-time bounds persist under summable or sufficiently small errors. Under persistent errors bounded by a fraction of the ball radius (ϵˉ<t\bar{\epsilon} < t), we obtain a sublinear function-value bound along the sequence of exact broximal points, valid until the iterates enter the target neighborhood, with an exponent that depends only on the ratio ϵˉ/t\bar{\epsilon}/t. This regime is covered neither by classical summable-error analyses of PPM nor by the high-accuracy accelerated guarantee of Carmon et al. [2020].

In § 3, we show that Inexact BPM enters the tt-tube around the set of minimizers after a bounded number of iterations when the errors are summable or uniformly bounded by a constant that depends on the initial distance to the set of minimizers. In § 4, we consider a relaxed uniform bound on the errors and establish sublinear convergence in function value, at a rate that improves as the error bound tightens. In the limit of vanishing errors, we recover a linear rate for Exact BPM. We also show that linear convergence is recovered under bounded sublevel sets or strong convexity. § 5 illustrates the results on a simple example. Proofs not given in the main text are deferred to Section A.

Preliminaries

We work under the following assumption on the objective function ϕ\phi.

Algorithm 1 Exact BPM: The exact broximal point method.

  1. Input: Starting point x0∈dom⁡ϕx_0 \in\operatorname{dom}\phi, radius t>0t > 0

  2. for k=0,1,2,…k = 0, 1, 2, \ldots do

  3. &nbsp;&nbsp;&nbsp;&nbsp;if dist⁡(xk,X⋆)>0\operatorname{dist}(x_k, \mathcal{X}_\star) > 0 then

  4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;xk+1∈brox⁡ϕt(xk)x_{k+1} \in\operatorname{brox}_{\phi}^{t}(x_k)

  5. &nbsp;&nbsp;&nbsp;&nbsp;else

  6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;xk+1=xkx_{k+1} = x_k

  7. &nbsp;&nbsp;&nbsp;&nbsp;end if

  8. end for

Assumption 2.1. The function ϕ:Rd→R∪{+∞}\phi: \mathbb{R}^{d} \to\mathbb{R} \cup\{+\infty\} is proper, closed, and convex, and its set of minimizers,

X⋆=arg min⁡x∈Rd ϕ(x),(6)\mathcal{X}_\star= \underset{x \in\mathbb{R}^{d}}{\operatorname{arg\,min}}\ \phi(x), \tag*{(6)}

is nonempty.

Closedness and convexity of the objective function ϕ\phi imply closedness and convexity of its set of minimizers X⋆\mathcal{X}_\star, ensuring uniqueness of projections onto it. We denote the Euclidean distance of an iterate xk∈Rdx_k \in\mathbb{R}^{d} to this set by

Dk:=dist⁡(xk,X⋆).(7)D_k := \operatorname{dist}(x_k,\mathcal{X}_\star). \tag*{(7)}

Exact broximal point method

The broximal operator of Gruntkowska et al. [2025] returns the solutions of the subproblem (5).

Definition 2.2 (Broximal operator). For a radius t>0t > 0 and a function ϕ\phi satisfying Assumption 2.1, the broximal operator is the set-valued mapping

brox⁡ϕt(x):=arg min⁡y∈Bt(x) ϕ(y),(8)\operatorname{brox}_{\phi}^{t}(x) := \underset{y \in B_t(x)}{\operatorname{arg\,min}}\ \phi(y), \tag*{(8)}

where Bt(x):={y∈Rd:∥y−x∥≤t}B_t(x) := \{y \in\mathbb{R}^{d} : \lVert y - x \rVert\le t\} is the closed Euclidean ball of radius tt centered at $x.

Evaluating the broximal operator thus requires solving a constrained optimization problem. While this operator is set-valued, the resulting set is typically a singleton.

Remark 2.3 (Properties of the broximal operator). Under Assumption 2.1, if Bt(x)∩dom⁡ϕ≠∅B_t(x) \cap\operatorname{dom}\phi\ne\varnothing, then brox⁡ϕt(x)\operatorname{brox}_{\phi}^{t}(x) is nonempty and the subproblem has a finite minimum. Moreover, if Bt(x)∩X⋆=∅B_t(x) \cap\mathcal{X}_\star= \varnothing, that is, if dist⁡(x,X⋆)>t\operatorname{dist}(x,\mathcal{X}_\star) > t, then brox⁡ϕt(x)\operatorname{brox}_{\phi}^{t}(x) is a singleton {y}\{y\} lying on the boundary of the ball:

∥y−x∥=t.(9)\lVert y - x \rVert= t. \tag*{(9)}

In such cases, we write y=brox⁡ϕt(x)y = \operatorname{brox}_{\phi}^{t}(x) for this unique point. These properties are shown in the proof of Lemma 2.4; see also Gruntkowska et al. [2025, Theorem D.1].

The following lemma establishes that the broximal operator decreases the distance to the set of minimizers.

Lemma 2.4 (One-step contraction [Gruntkowska et al., 2025, Theorem 8.1(ii)]). Let Assumption 2.1 hold. For any x∈Rdx \in\mathbb{R}^{d} satisfying Bt(x)∩dom⁡ϕ≠∅B_t(x) \cap\operatorname{dom}\phi\ne\varnothing and dist⁡(x,X⋆)>t\operatorname{dist}(x,\mathcal{X}_\star) > t, let y=brox⁡ϕt(x)y = \operatorname{brox}_{\phi}^{t}(x) be the unique broximal point (cf. Remark 2.3). Then, for every minimizer x⋆∈X⋆x_\star\in\mathcal{X}_\star, we have:

∥y−x⋆∥2≤∥x−x⋆∥2−t2.(10)\lVert y - x_\star\rVert^{2} \le\lVert x - x_\star\rVert^{2} - t^{2}. \tag*{(10)}

By Lemma 2.4, as long as Dk>tD_k > t, each exact broximal step reduces the squared distance to X⋆\mathcal{X}_\star by at least t2t^{2}; once a minimizer lies within distance tt of xkx_k, the next step reaches it. This argument uses only Assumption 2.1 and requires no differentiability, smoothness, finite-valuedness, or strong convexity. Consequently, starting from x0∈dom⁡ϕx_0 \in\operatorname{dom}\phi, Exact BPM reaches a minimizer in at most

⌈D02t2⌉(11)\left\lceil\frac{D_0^{2}}{t^{2}} \right\rceil \tag*{(11)}

iterations [Gruntkowska et al., 2025, Theorem 8.1(iii)], where D0=dist⁡(x0,X⋆)D_0 = \operatorname{dist}(x_0,\mathcal{X}_\star) is the distance of the initial point to the set of minimizers. Classical methods for general convex optimization, such as PPM [9], subgradient methods [24, 15], and proximal-gradient methods [16], come with convergence rates but do not in general terminate after finitely many steps; the bound (11) is finite and depends only on D0D_0 and tt, not on smoothness, the condition number, or any other structural parameter of the objective. As the dimension grows, this dimension-independent bound is asymptotically attained by a family of polyhedral functions [19 Theorem 4.11]; in fixed dimension, the worst-case iteration count grows only linearly in D0/tD_0/t [19 Theorem 4.5].

Inexact broximal point method

Each iteration of Exact BPM (Algorithm 1) requires minimizing the objective function over a ball, which is generally intractable in practice. We therefore consider an inexact variant where the exact broximal point is replaced by an approximation. Specifically, we assume that the next iterate xk+1x_{k+1} produced by Inexact BPM (Algorithm 2) lies no more than some distance εk≥0\varepsilon_k \ge0 from the exact broximal step evaluated at the current iterate xkx_k, that is,

∥xk+1−brox⁡ϕt(xk)∥≤εk,whenever Dk>t.(12)\left\|x_{k+1}-\operatorname{brox}_{\phi}^{t}(x_k)\right\| \le\varepsilon_k, \qquad\text{whenever } D_k>t. \tag*{(12)}

We impose no structural assumptions on how this approximation is obtained, and our framework thus accommodates deterministic, randomized, and even adversarial perturbations. We consider a variety of settings for the error tolerances {εk}\{\varepsilon_k\} below.

Relation to inexact ball oracles. The error model (12) measures inexactness by the distance from the produced iterate to the exact ball-constrained minimizer. Carmon et al. [ [3] use the same notion in their (δ,r)(\delta,r)-ball optimization oracle, which, when queried at xˉ\bar{x}, returns a point y∈Br(xˉ)y \in B_r(\bar{x}) with ∥y−xr,xˉ∥≤δ\|y-x_{r,\bar{x}}\| \le\delta for some xr,xˉ∈arg⁡min⁡x∈Br(xˉ)ϕ(x)x_{r,\bar{x}} \in\arg\min_{x\in B_r(\bar{x})}\phi(x). Their setting differs from ours in several ways. Their accelerated guarantee assumes real-valued, strictly convex, smooth objectives and uses the oracle inside Monteiro–Svaiter acceleration, with an accuracy δ\delta that must be a small fraction of rr, depending on the smoothness constant, the initial distance to the optimum, and the target accuracy. We require only that ϕ\phi be proper, closed, and convex, we analyze the broximal iteration itself, and we allow persistent errors as large as a constant fraction of the radius (ε<t\varepsilon< t; cf. Assumption 4.1). Moreover, their oracle output lies in Br(xˉ)B_r(\bar{x}), whereas our iterate xk+1x_{k+1} need not lie in Bt(xk)B_t(x_k).

With approximation errors, the iterates can in general only be guaranteed to reach a neighborhood of X⋆\mathcal{X}_\star, not X⋆\mathcal{X}_\star itself. We use the following neighborhood as the target.

Definition 2.5 (Tube). Given ρ≥0\rho\ge0, the closed ρ\rho-tube around a set X⊆Rd\mathcal{X} \subseteq\mathbb{R}^d is

Tρ(X):={x∈Rd:dist⁡(x,X)≤ρ}.(13)\mathcal{T}_{\rho}(\mathcal{X}) := \{x \in\mathbb{R}^d : \operatorname{dist}(x,\mathcal{X}) \le\rho\}. \tag*{(13)}

Since X⋆\mathcal{X}_\star is closed, T0(X⋆)=X⋆\mathcal{T}_0(\mathcal{X}_\star)=\mathcal{X}_\star, so the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) generalizes the target set of the exact method. The radius tt thus plays two roles: it is the radius of the ball constraint and the target accuracy.

Algorithm 2 generalizes Algorithm 1 to inexact steps. It includes a truncation step that freezes the sequence once the iterates enter Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star). This truncation is an analytical device, not an implementable stopping rule: the test dist⁡(xk,X⋆)≤t\operatorname{dist}(x_k,\mathcal{X}_\star)\le t cannot be evaluated in general, since X⋆\mathcal{X}_\star is unknown. The updates themselves do not require the test.

Algorithm 2 Inexact BPM: The truncated inexact broximal point method.

1: Input: Starting point x0∈dom⁡ϕx_0 \in\operatorname{dom}\phi, radius t>0t>0 2: for k=0,1,2,…k=0,1,2,\ldots do 3: &nbsp;&nbsp;if dist⁡(xk,X⋆)>t\operatorname{dist}(x_k,\mathcal{X}_\star)>t then 4: &nbsp;&nbsp;&nbsp;&nbsp;xk+1≈brox⁡ϕt(xk)x_{k+1}\approx\operatorname{brox}_{\phi}^{t}(x_k) ▷ The approximation satisfies (12). 5: &nbsp;&nbsp;else 6: &nbsp;&nbsp;&nbsp;&nbsp;xk+1=xkx_{k+1}=x_k ▷ Truncation step. 7: &nbsp;&nbsp;end if 8: end for

Compared with Algorithm 1, Algorithm 2 makes two changes. First, xk+1x_{k+1} only approximates brox⁡ϕt(xk)\operatorname{brox}_{\phi}^{t}(x_k), with error at most εk≥0\varepsilon_k\ge0 as in (12); the tolerances need not be known to run the method. Second, the method stops when it enters Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) rather than when it reaches X⋆\mathcal{X}_\star.

To quantify the convergence properties of Inexact BPM, we analyze the number of iterations required for the sequence to enter the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star). We formalize this through the notion of a hitting time.

Definition 2.6 (Hitting time). The hitting time KtK_t of Algorithm 2 to the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) is defined as:

Kt:=inf⁡{k≥0:xk∈Tt(X⋆)}=inf⁡{k≥0:dist⁡(xk,X⋆)≤t},(14)K_t := \inf\{k\ge0:x_k\in\mathcal{T}_t(\mathcal{X}_\star)\} =\inf\{k\ge0:\operatorname{dist}(x_k,\mathcal{X}_\star)\le t\}, \tag*{(14)}

where we adopt the standard convention that inf⁡∅=+∞\inf\varnothing=+\infty.

Without errors, KtK_t is bounded by the iteration count (11) of the exact method. In the next section, we derive analogous bounds under perturbations. When the approximations are randomized, KtK_t is a random variable; all our bounds are worst-case and hold pathwise, for every sequence of approximations that satisfies the stated error conditions.

Distance contraction guarantees

In this section, we establish the iteration complexity of Inexact BPM under well-controlled error regimes. To that end, we first derive a one-step distance recursion generalizing Lemma 2.4 for the inexact setting.

Lemma 3.1. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2. Suppose Assumption 2.1 holds and Bt(xk)∩dom⁡ϕ≠∅B_t(x_k) \cap\operatorname{dom}\phi\ne\varnothing for every k<Ktk < K_t. The distances Dk=dist⁡(xk,X⋆)D_k = \operatorname{dist}(x_k, \mathcal{X}_{\star}) to the set of minimizers satisfy the following relations:

(i) If Dk>tD_k > t, we have the recursive upper bound:

Dk+1≤Dk2−t2+εk.(15)D_{k+1} \leq\sqrt{D_k^2-t^2}+\varepsilon_k. \tag*{(15)}

(ii) If Dk≤tD_k \leq t, the algorithm truncates the update step (xk+1=xkx_{k+1}=x_k), and thus:

Dk+1=Dk≤t.(16)D_{k+1}=D_k\leq t. \tag*{(16)}

Thus the contraction of the exact step in Lemma 2.4 survives, up to an additive error εk\varepsilon_k in the distance to the set of minimizers. We now consider two classical error regimes in which this recursion yields finite hitting times.

Summable errors

We first allow individual errors to be large, provided their sum is finite. This is the error model of the classical inexact proximal point analysis of Rockafellar [ [21].

Theorem 3.2. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 with radius t>0t>0, and suppose Assumption 2.1 holds. Assume further that every active subproblem is well-defined, in the sense that Bt(xk)∩dom⁡ϕ≠∅B_t(x_k) \cap\operatorname{dom}\phi\ne\varnothing for all k<Ktk<K_t. If the error sequence is summable, meaning

Σ:=∑k=0∞εk<∞,(17)\Sigma:= \sum_{k=0}^{\infty}\varepsilon_k < \infty, \tag*{(17)}

then the hitting time KtK_t to the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_{\star}) satisfies:

Kt≤⌈(D0+Σ)2t2⌉.(18)K_t \leq\left\lceil\frac{(D_0+\Sigma)^2}{t^2}\right\rceil. \tag*{(18)}

When Σ=0\Sigma=0, the bound reduces to ⌈D02/t2⌉\lceil D_0^2/t^2\rceil, the same expression as the Exact BPM baseline (11), although KtK_t measures tube entry rather than arrival at a minimizer. The term (D0+Σ)2(D_0+\Sigma)^2 accounts for the worst-case accumulation of approximation errors, which may increase the distance to the set of minimizers by up to Σ\Sigma relative to its initial value D0D_0. Thus finite tube entry is preserved under summable errors, with the worst-case hitting-time bound growing quadratically in the total error budget Σ\Sigma.

If, for example, Σ≤cD0\Sigma\leq cD_0 for some c≥0c\geq0, then (18) gives Kt≤⌈(1+c)2D02/t2⌉K_t\leq\lceil(1+c)^2D_0^2/t^2\rceil.

The condition Bt(xk)∩dom⁡ϕ≠∅B_t(x_k) \cap\operatorname{dom}\phi\ne\varnothing in Theorem 3.2 is needed because the summable regime places no bound on any individual error, so a single large perturbation may move xkx_k to a point whose ball misses dom⁡ϕ\operatorname{dom}\phi; the condition holds automatically when εk<t\varepsilon_k<t for all kk (see the proof of Theorem 3.4).

Uniformly small errors

We next consider errors that are uniformly bounded across all iterations. To quantify the progress made at each step, we use the following quantity.

Definition 3.3 (Progress guarantee). Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 with radius tt, and let {εk}k≥0\{\varepsilon_k\}_{k\geq0} denote a sequence of nonnegative error bounds for the approximations as described in (12). For each iteration kk satisfying Dk>tD_k>t, the progress guarantee pkp_k is defined as:

pk:=t2−εk2−2εkDk2−t2.(19)p_k := t^2-\varepsilon_k^2-2\varepsilon_k\sqrt{D_k^2-t^2}. \tag*{(19)}

Table 1: Hitting time bounds. The hitting time KtK_t to the tt-tube is defined in (14). Here D0=dist⁡(x0,X⋆)D_0 = \operatorname{dist}(x_0, \mathcal{X}_\star) is the initial distance to the set of minimizers, and pˉ=t2−εˉ2−2εˉD02−t2≤t2\bar{p} = t^2 - \bar{\varepsilon}^2 - 2\bar{\varepsilon}\sqrt{D_0^2-t^2} \le t^2 is the initial worst-case progress guarantee (22) under a uniform error bound εˉ\bar{\varepsilon}. All bounds are independent of the condition number and of any other regularity parameter of the objective.

ResultError regimeBound on KtK_t
Theorem 8.1(iii) [8]No errors: εk=0\varepsilon_k = 0⌈D02t2⌉\left\lceil\frac{D_0^2}{t^2}\right\rceil
Theorem 3.2Summable errors: Σ=∑k=0∞εk<∞\Sigma= \sum_{k=0}^{\infty}\varepsilon_k < \infty⌈(D0+Σ)2t2⌉\left\lceil\frac{(D_0+\Sigma)^2}{t^2}\right\rceil
Theorem 3.4Uniformly small errors: εk≤εˉ<D0−D02−t2\varepsilon_k \le\bar{\varepsilon} < D_0-\sqrt{D_0^2-t^2}⌈D02pˉ⌉\left\lceil\frac{D_0^2}{\bar{p}}\right\rceil

Table 1.

Since εk≥0\varepsilon_k \ge0, we have pk≤t2p_k \le t^2. Squaring both sides of the distance recursion in Lemma 3.1(i) yields

Dk+12≤Dk2−pk,(20)D_{k+1}^2 \le D_k^2-p_k, \tag*{(20)}

so the progress guarantee pkp_k quantifies the minimum guaranteed reduction in the squared distance to the set of minimizers X⋆\mathcal{X}_\star at step kk. For εk=0\varepsilon_k = 0, we recover pk=t2p_k = t^2, the exact per-step reduction of Exact BPM.

The progress guarantee pkp_k depends on the radius tt, the error bound εk\varepsilon_k, and the current distance DkD_k. It is positive only if the error bound is small enough. Specifically, we have pk>0p_k > 0 if and only if

εk<Dk−Dk2−t2.(21)\varepsilon_k < D_k-\sqrt{D_k^2-t^2}. \tag*{(21)}

If this condition is violated (pk≤0p_k \le0), the approximation error may exceed the broximal contraction, potentially pushing the iterate further away from the set of minimizers. Under a uniform bound on the errors that prevents the iterates from moving away from the set of minimizers, we obtain the following guarantee for the hitting time.

Theorem 3.4. Let {xk}k≥0\{x_k\}_{k\ge0} be the sequence generated by Algorithm 2 with radius t<D0t < D_0, and suppose Assumption 2.1 holds. Suppose the error sequence is uniformly bounded such that εk≤εˉ\varepsilon_k \le\bar{\varepsilon} for all k≥0k \ge0, and let

pˉ:=t2−εˉ2−2εˉD02−t2(22)\bar{p} := t^2-\bar{\varepsilon}^2-2\bar{\varepsilon}\sqrt{D_0^2-t^2} \tag*{(22)}

denote the initial worst-case progress guarantee. If the uniform error bound ensures that pˉ>0\bar{p} > 0, that is, if εˉ<D0−D02−t2\bar{\varepsilon} < D_0-\sqrt{D_0^2-t^2}, then the hitting time KtK_t to the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) satisfies:

Kt≤⌈D02pˉ⌉.(23)K_t \le\left\lceil\frac{D_0^2}{\bar{p}}\right\rceil. \tag*{(23)}

The bound (23) has the same form as the exact baseline (11), with the per-step progress t2t^2 replaced by pˉ\bar{p}. The proof shows that pk≥pˉp_k \ge\bar{p} for all k<Ktk < K_t, however the approximation errors evolve, so the squared distance to X⋆\mathcal{X}_\star decreases by at least pˉ\bar{p} in every iteration before tube entry. Like (11), the bound does not depend on any property of the objective. Table 1 summarizes the results of this section.

The threshold in (21) decreases in DkD_k, and for any fixed radius tt,

lim⁡D0→+∞(D0−D02−t2)=0.(24)\lim_{D_0\to+\infty}\left(D_0-\sqrt{D_0^2-t^2}\right)=0. \tag*{(24)}

That is, for any fixed εˉ>0\bar{\varepsilon}>0, a sufficiently distant starting point gives pˉ<0\bar{p}<0, and no single uniform tolerance guarantees positive progress from every starting point. This limitation motivates the next section.

Suboptimality bounds under relaxed tolerances

We now only require the errors to stay strictly below the ball radius.

Assumption 4.1 (Radius-bounded uniform error). The error bounds {εk}k≥0\{\varepsilon_k\}_{k\ge0} in (12) are uniformly bounded by a constant εˉ\bar{\varepsilon} smaller than the radius tt:

εk≤εˉ<t,∀k≥0.(25)\varepsilon_k \le\bar{\varepsilon}<t,\quad\forall k\ge0. \tag*{(25)}

The error bound εˉ\bar{\varepsilon} may be arbitrarily close to tt. This condition is weaker than the one in Theorem 3.4 and does not involve the distance to the set of minimizers. Unlike the summable model, which forces the errors to vanish, Assumption 4.1 allows a persistent error at every iteration.

The strict inequality εˉ<t\bar{\varepsilon}<t cannot be dropped. Since ∥brox⁡ϕt(xk)−xk∥≤t\lVert\operatorname{brox}_{\phi}^{t}(x_k)-x_k\rVert\le t, an adversary with εˉ≥t\bar{\varepsilon}\ge t can choose xk+1=xkx_{k+1}=x_k at every step, so the method stalls at x0x_0.

Throughout this section, tt and εˉ\bar{\varepsilon} are fixed constants satisfying Assumption 4.1. We define the inner radius rr,

r:=t−εˉ,(26)r:=t-\bar{\varepsilon}, \tag*{(26)}

and the auxiliary sequence {yk}\{y_k\},

y0:=x0,yk+1:=brox⁡ϕt(xk),0≤k<Kt.(27)\begin{aligned} y_0&:=x_0,\\ y_{k+1}&:=\operatorname{brox}_{\phi}^{t}(x_k),\qquad0\le k<K_t. \tag*{(27)} \end{aligned}

The point yk+1y_{k+1} is the point that Inexact BPM would compute in iteration kk without approximation error. With this notation, the approximation error bound (12) may equivalently be expressed as

∥xk+1−yk+1∥≤εk,0≤k<Kt.(28)\lVert x_{k+1}-y_{k+1}\rVert\le\varepsilon_k,\qquad0\le k<K_t. \tag*{(28)}

Equivalently, for every finite 1≤k≤Kt1\le k\le K_t,

∥xk−yk∥≤εk−1≤εˉ.(29)\lVert x_k-y_k\rVert\le\varepsilon_{k-1}\le\bar{\varepsilon}. \tag*{(29)}

Since y0=x0y_0=x_0, the bound ∥xk−yk∥≤εˉ\lVert x_k-y_k\rVert\le\bar{\varepsilon} holds for every finite 0≤k≤Kt0\le k\le K_t.

For general convex objectives, we have no bound on KtK_t under Assumption 4.1 alone, but it is finite under bounded sublevel sets (see the discussion after Theorem 4.5). Moreover, the distance-based condition (28) does not control the objective value ϕ(xk)\phi(x_k) under Assumption 2.1 alone. We therefore analyze the decrease of the objective along the sequence {yk}\{y_k\} of exact broximal points. The key observation, illustrated in Figure 1, is that ∥xk−yk∥≤εˉ\lVert x_k-y_k\rVert\le\bar{\varepsilon} implies Br(yk)⊆Bt(xk)B_r(y_k)\subseteq B_t(x_k): any point within distance rr of yky_k lies within distance tt of xkx_k and is therefore feasible for the subproblem that defines yk+1=brox⁡ϕt(xk)y_{k+1}=\operatorname{brox}_{\phi}^{t}(x_k).

Geometry of Assumption 4.1

Figure 1. Geometry of Assumption 4.1. The approximation error bound ∥xk−yk∥≤εˉ\lVert x_k-y_k\rVert\le\bar{\varepsilon} guarantees the inclusion Br(yk)⊆Bt(xk)B_r(y_k)\subseteq B_t(x_k) for r=t−εˉr=t-\bar{\varepsilon}. Thus, a reference point zkz_k on the segment [yk,yk⋆][y_k,y_k^\star], where yk⋆y_k^\star is the projection of yky_k onto X⋆\mathcal{X}_\star, lies in Bt(xk)B_t(x_k) if ∥yk−zk∥≤r\lVert y_k-z_k\rVert\le r. Since yk+1y_{k+1} minimizes ϕ\phi over Bt(xk)B_t(x_k), we get ϕ(yk+1)≤ϕ(zk)\phi(y_{k+1})\le\phi(z_k), which yields a decrease in function value.

General convex objectives

Our first result requires no assumption on ϕ\phi beyond Assumption 2.1. It shows that the suboptimality gap decays at a sublinear rate governed by the ratio εˉ/t\bar{\varepsilon}/t.

Theorem 4.2. Let {xk}k≥0\{x_k\}_{k\ge0} be the sequence generated by Algorithm 2 and {yk}k≥0\{y_k\}_{k\ge0} the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume D0>tD_0>t and that the uniform error bound of Assumption 4.1 is positive, εˉ>0\bar{\varepsilon}>0. For any iteration N≤KtN\le K_t, the suboptimality gap satisfies:

ϕ(yN)−ϕ⋆≤(1+NεˉD0)−εˉ/t(ϕ(y0)−ϕ⋆).(30)\phi(y_N)-\phi_\star\le\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\bar{\varepsilon}/t}\bigl(\phi(y_0)-\phi_\star\bigr). \tag*{(30)}

where rr is the inner radius defined in (26).

Proof. The following proof adapts the auxiliary point construction of Carmon et al. [ [3]. Fix an iteration k<Ktk < K_t. Since k<Ktk < K_t, we have dist⁡(xk,X⋆)>t\operatorname{dist}(x_k,\mathcal{X}_\star) > t. Therefore,

dist⁡(yk,X⋆)≥dist⁡(xk,X⋆)−∥xk−yk∥>t−εˉ=r.\operatorname{dist}(y_k,\mathcal{X}_\star) \ge\operatorname{dist}(x_k,\mathcal{X}_\star) - \lVert x_k-y_k\rVert> t-\bar{\varepsilon}=r.

Let yk⋆y_k^\star be the unique projection of yky_k onto X⋆\mathcal{X}_\star. Then

∥yk⋆−yk∥=dist⁡(yk,X⋆)>r,\lVert y_k^\star-y_k\rVert=\operatorname{dist}(y_k,\mathcal{X}_\star)>r,

and hence

α:=r∥yk⋆−yk∥∈(0,1).\alpha:= \frac{r}{\lVert y_k^\star-y_k\rVert}\in(0,1).

Define the reference point

zk:=yk+r∥yk⋆−yk∥(yk⋆−yk).(31)z_k := y_k+\frac{r}{\lVert y_k^\star-y_k\rVert}(y_k^\star-y_k). \tag*{(31)}

Then zk=(1−α)yk+αyk⋆z_k=(1-\alpha)y_k+\alpha y_k^\star lies at distance rr from yky_k on the line segment connecting yky_k and yk⋆y_k^\star. Because ϕ(yk⋆)=ϕ⋆\phi(y_k^\star)=\phi_\star, convexity of ϕ\phi yields

ϕ(zk)−ϕ⋆≤(1−α)(ϕ(yk)−ϕ⋆).(32)\phi(z_k)-\phi_\star\le(1-\alpha)(\phi(y_k)-\phi_\star). \tag*{(32)}

By the triangle inequality and Assumption 4.1, the distance from the reference point to the current approximate iterate xkx_k satisfies:

∥zk−xk∥≤∥zk−yk∥+∥yk−xk∥≤r+εˉ=t.(33)\lVert z_k-x_k\rVert\le\lVert z_k-y_k\rVert+\lVert y_k-x_k\rVert\le r+\bar{\varepsilon}=t. \tag*{(33)}

Thus, zk∈Bt(xk)z_k\in B_t(x_k), meaning zkz_k is a feasible point for the broximal subproblem solved at iteration kk. Because yk+1y_{k+1} is defined as the exact minimizer of ϕ\phi over this ball, we have:

ϕ(yk+1)≤ϕ(zk).(34)\phi(y_{k+1})\le\phi(z_k). \tag*{(34)}

Plugging (34) into (32) provides a one-step contraction bound for the sequence {yk}\{y_k\}:

ϕ(yk+1)−ϕ⋆≤(1−r∥yk⋆−yk∥)(ϕ(yk)−ϕ⋆).(35)\phi(y_{k+1})-\phi_\star\le\left(1-\frac{r}{\lVert y_k^\star-y_k\rVert}\right)(\phi(y_k)-\phi_\star). \tag*{(35)}

To bound the denominator, we recall that, for every finite 1≤k≤Kt1\le k\le K_t, the point yky_k is generated by an exact broximal step from xk−1x_{k-1}. By Lemma 2.4, the distance to the set of minimizers satisfies

dist⁡(yk,X⋆)≤Dk−12−t2≤Dk−1.(36)\operatorname{dist}(y_k,\mathcal{X}_\star)\le\sqrt{D_{k-1}^2-t^2}\le D_{k-1}. \tag*{(36)}

Furthermore, from the distance recursion in Lemma 3.1(i), we know

Di≤Di−1+εi−1≤Di−1+εˉ.(37)D_i\le D_{i-1}+\varepsilon_{i-1}\le D_{i-1}+\bar{\varepsilon}. \tag*{(37)}

By induction, it follows that Dk−1≤D0+(k−1)εˉD_{k-1}\le D_0+(k-1)\bar{\varepsilon} for every finite 1≤k≤Kt1\le k\le K_t. Since y0=x0y_0=x_0 yields ∥y0⋆−y0∥=D0\lVert y_0^\star-y_0\rVert=D_0, it follows that for every finite 0≤k≤Kt0\le k\le K_t, the distance to the set of minimizers is bounded by:

∥yk⋆−yk∥=dist⁡(yk,X⋆)≤D0+kεˉ.(38)\lVert y_k^\star-y_k\rVert=\operatorname{dist}(y_k,\mathcal{X}_\star)\le D_0+k\bar{\varepsilon}. \tag*{(38)}

Let Vk:=ϕ(yk)−ϕ⋆V_k:=\phi(y_k)-\phi_\star denote the suboptimality gap. Chaining the one-step contractions from (35) for k=0,…,N−1k=0,\ldots,N-1 with N≤KtN\le K_t, and applying the distance bound (38) gives:

VN≤V0∏k=0N−1(1−rD0+kεˉ).(39)V_N\le V_0\prod_{k=0}^{N-1}\left(1-\frac{r}{D_0+k\bar{\varepsilon}}\right). \tag*{(39)}

Applying the standard inequality 1−x≤exp⁡(−x)1-x\le\exp(-x) for x∈(0,1)x\in(0,1) yields:

VN≤V0exp⁡(−∑k=0N−1rD0+kεˉ).(40)V_N\le V_0\exp\left(-\sum_{k=0}^{N-1}\frac{r}{D_0+k\bar{\varepsilon}}\right). \tag*{(40)}

Bounding the sum from below with its corresponding integral gives:

∑k=0N−1rD0+kεˉ≥∫0NrD0+xεˉ dx=rεˉln⁡(1+NεˉD0).(41)\sum_{k=0}^{N-1}\frac{r}{D_0+k\bar{\varepsilon}}\ge\int_0^N\frac{r}{D_0+x\bar{\varepsilon}}\,dx=\frac{r}{\bar{\varepsilon}}\ln\left(1+\frac{N\bar{\varepsilon}}{D_0}\right). \tag*{(41)}

Substituting this into the exponential bound establishes the claim:

VN≤V0(1+NεˉD0)−rεˉ.(42)V_N \le V_0\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\frac{r}{\bar{\varepsilon}}}. \tag*{(42)}

Remark 4.3 (Convergence limit in the exact case). Taking the limit of (30) as εˉ→0\bar{\varepsilon}\to0 yields the bound ϕ(yN)−ϕ⋆≤exp⁡(−tN/D0)(ϕ(y0)−ϕ⋆)\phi(y_N)-\phi_\star\le\exp(-tN/D_0)(\phi(y_0)-\phi_\star). For exact steps, setting εˉ=0\bar{\varepsilon}=0 and r=tr=t in (39) gives the sharper bound

ϕ(yN)−ϕ⋆≤(1−tD0)N(ϕ(y0)−ϕ⋆).\phi(y_N)-\phi_\star\le\left(1-\frac{t}{D_0}\right)^N(\phi(y_0)-\phi_\star).

This is the geometric decrease established in the proof of Carmon et al. [ [3] for the exact ball-oracle iteration with strictly convex objectives. Richtárik and Li [ [19] prove the same bound for Exact BPM under Assumption 2.1, which improves on the bound (1+t/D0)−N(1+t/D_0)^{-N} of Gruntkowska et al. [ [8].

Writing εˉ=qt\bar{\varepsilon}=qt with q∈(0,1)q\in(0,1), so that r/εˉ=(1−q)/qr/\bar{\varepsilon}=(1-q)/q, Theorem 4.2 gives the rate O(N−(1−q)/q)O(N^{-(1-q)/q}); for example, q=1/4q=1/4, 1/21/2, and 3/43/4 give O(N−3)O(N^{-3}), O(N−1)O(N^{-1}), and O(N−1/3)O(N^{-1/3}). The exponent depends only on the relative error, and since (1+Nεˉ/D0)−r/εˉ≤(D0/(Nεˉ))r/εˉ(1+N\bar{\varepsilon}/D_0)^{-r/\bar{\varepsilon}}\le(D_0/(N\bar{\varepsilon}))^{r/\bar{\varepsilon}}, the constant hidden in O(⋅)O(\cdot) is (D0/εˉ)(1−q)/q(ϕ(y0)−ϕ⋆)(D_0/\bar{\varepsilon})^{(1-q)/q}(\phi(y_0)-\phi_\star). By contrast, the bounds of standard first-order methods scale with function-specific constants: subgradient methods for GG-Lipschitz functions achieve O(GD0/N)O(GD_0/\sqrt{N}) [24, 15], gradient descent for LL-smooth functions achieves O(LD02/N)O(LD_0^2/N) [15], and accelerated methods improve this to O(LD02/N2)O(LD_0^2/N^2) [13]. Our bound requires no such regularity. This feature is inherited from Exact BPM [8 Corollary 8.2] and survives persistent approximation errors.

Bounded sublevel sets

The sublinear rate of Theorem 4.2 can be sharpened to a linear rate if the sublevel sets of ϕ\phi are bounded, which confines the reference points yky_k to a bounded region.

Definition 4.4 (Bounded sublevel sets). The function ϕ\phi has bounded sublevel sets if for every α∈R\alpha\in\mathbb{R}, the corresponding sublevel set {y∈Rd:ϕ(y)≤α}\{y\in\mathbb{R}^d:\phi(y)\le\alpha\} is bounded. We denote the sublevel set of the initial point x0x_0 by Lx0L_{x_0} and its largest distance to the set of minimizers by Dmax⁡D_{\max}:

Lx0:={y∈Rd:ϕ(y)≤ϕ(x0)},(43)L_{x_0}:=\{y\in\mathbb{R}^d:\phi(y)\le\phi(x_0)\}, \tag*{(43)}
Dmax⁡:=sup⁡y∈Lx0dist⁡(y,X⋆).(44)D_{\max}:=\sup_{y\in L_{x_0}}\operatorname{dist}(y,\mathcal{X}_\star). \tag*{(44)}

Theorem 4.5. Let {xk}k≥0\{x_k\}_{k\ge0} be the sequence generated by Algorithm 2 and {yk}k≥0\{y_k\}_{k\ge0} the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume D0>tD_0>t and εˉ>0\bar{\varepsilon}>0. If ϕ\phi has bounded sublevel sets (Definition 4.4), then for any iteration N≤KtN\le K_t, the suboptimality gap satisfies:

ϕ(yN)−ϕ⋆≤min⁡{(1+NεˉD0)−rεˉ,(1−rDmax⁡)N}(ϕ(y0)−ϕ⋆).(45)\phi(y_N)-\phi_\star\le\min\left\{\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\frac{r}{\bar{\varepsilon}}},\left(1-\frac{r}{D_{\max}}\right)^N\right\}(\phi(y_0)-\phi_\star). \tag*{(45)}

where rr is the inner radius defined in (26), and Dmax⁡D_{\max} is given by (44).

When D0≪Dmax⁡D_0\ll D_{\max}, the first bound in (45) can be much smaller in early iterations. For large NN, the second bound gives linear convergence with factor 1−r/Dmax⁡1-r/D_{\max}. This rate is no longer independent of the objective, since Dmax⁡D_{\max} depends on the sublevel set Lx0L_{x_0} (cf. Table 2). The theorem also shows that Kt<∞K_t<\infty, although it gives no bound on KtK_t. Indeed, if Kt=∞K_t=\infty, then ϕ(yN)→ϕ⋆\phi(y_N)\to\phi_\star; since Lx0L_{x_0} is compact and ϕ\phi is lower semicontinuous, this forces dist⁡(yN,X⋆)→0\operatorname{dist}(y_N,\mathcal{X}_\star)\to0, contradicting dist⁡(yN,X⋆)>r\operatorname{dist}(y_N,\mathcal{X}_\star)>r for all N<KtN<K_t (see the proof of Theorem 4.2).

Table | Suboptimality bounds. Here D0=dist⁡(x0,X⋆)D_0 = \operatorname{dist}(x_0, X_\star) is the initial distance to the set of minimizers, V0=ϕ(y0)−ϕ⋆=ϕ(x0)−ϕ⋆V_0 = \phi(y_0) - \phi_\star= \phi(x_0) - \phi_\star is the initial suboptimality gap, and r=t−εˉr = t - \bar{\varepsilon} is the inner radius (26). The results of this section hold under the relaxed error regime of Assumption 4.1 for all iterations before entering the tt-tube, N≤KtN \le K_t. For Theorems 4.5 and 4.7, the table shows only the bound that uses the additional assumption; the bound of Theorem 4.2 holds as well. |

ResultAssumptionsBound on Suboptimality GapIndependent of Regularity
Theorem 3.1 [19]Convexity, exact steps(1−tD0)NV0\left(1-\frac{t}{D_0}\right)^N V_0✔
Theorem 4.2Convexity(1+NεˉD0)−N2V0\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\frac{N}{2}} V_0✔
Theorem 4.5Convexity, bounded sublevel sets(1−rDmax⁡)NV0\left(1-\frac{r}{D_{\max}}\right)^N V_0✘
Theorem 4.7μ\mu-strong convexityV0−Nμr22V_0-N\frac{\mu r^2}{2}✘

Table 2.

Strongly convex objectives

Under strong convexity, the reference values ϕ(yk)\phi(y_k) decrease by at least a fixed amount in every step before tube entry, which yields finite termination. Our next result expresses the linear bound of Theorem 4.5 in terms of the strong-convexity parameter and adds this absolute-decrease estimate.

Definition 4.6 (Strong convexity). Under Assumption 2.1, the function ϕ\phi is μ\mu-strongly convex with parameter μ>0\mu>0 if for all x,y∈dom⁡ϕx,y\in\operatorname{dom}\phi and α∈[0,1]\alpha\in[0,1], the following holds:

ϕ(αx+(1−α)y)≤αϕ(x)+(1−α)ϕ(y)−μ2α(1−α)∥x−y∥2.(46)\phi(\alpha x+(1-\alpha)y)\le\alpha\phi(x)+(1-\alpha)\phi(y)-\frac{\mu}{2}\alpha(1-\alpha)\lVert x-y\rVert^2. \tag*{(46)}

Theorem 4.7. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 and {yk}k≥0\{y_k\}_{k\geq0} the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume D0>tD_0>t and εˉ>0\bar{\varepsilon}>0. If ϕ\phi is μ\mu-strongly convex, then for any iteration N≤KtN\leq K_t, the suboptimality gap satisfies:

ϕ(yN)−ϕ⋆≤min⁡{(1+NεˉD0)−N2V0,(1−rμ2V0)NV0,V0−Nμr22},(47)\phi(y_N)-\phi_\star\leq\min\left\{\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\frac{N}{2}}V_0,\left(1-r\sqrt{\frac{\mu}{2V_0}}\right)^N V_0,V_0-N\frac{\mu r^2}{2}\right\}, \tag*{(47)}

where V0=ϕ(y0)−ϕ⋆V_0=\phi(y_0)-\phi_\star, and rr is the inner radius defined in (26).

Which of the three bounds is smallest depends on the parameters and on NN. Since the gap ϕ(yN)−ϕ⋆\phi(y_N)-\phi_\star is nonnegative, the constant decrease μr2/2\mu r^2/2 cannot continue indefinitely, which gives the following bound on the hitting time.

Corollary 4.8 (Finite hitting time). Under the conditions of Theorem 4.7, the hitting time KtK_t to the tt-tube Tt(X⋆)\mathcal{T}_t(X_\star) is bounded by:

Kt≤⌈2(ϕ(y0)−ϕ⋆)μr2⌉.(48)K_t \leq\left\lceil\frac{2(\phi(y_0)-\phi_\star)}{\mu r^2}\right\rceil. \tag*{(48)}

Thus, under strong convexity, the method still reaches the target neighborhood in finitely many steps when each subproblem is solved only up to an error below the ball radius.

Discussion

We summarize the guarantees of this section in Table 2. Under convexity alone, Theorem 4.2 gives a sublinear bound for the reference function values, valid up to tube entry and independent of the regularity of the objective. In comparison, Exact BPM admits a linear bound under convexity alone [19] (Gruntkowska et al. 2025). With the additional assumption of bounded sublevel sets, we obtain a linear bound involving Dmax⁡D_{\max}. Under strong convexity, Corollary 4.8 additionally supplies an explicit finite bound on KtK_t and thus a complexity guarantee for reaching the tt-tube. This bound depends explicitly on the strong-convexity parameter μ\mu.

The guarantees of this section have two limitations. First, they bound the suboptimality ϕ(yN)−ϕ⋆\phi(y_N)-\phi_\star along the auxiliary sequence {yk}\{y_k\} of exact proximal points, rather than along the iterates {xk}\{x_k\} actually produced by Algorithm 2. This distinction is unavoidable under our assumptions: the bound ∥xk−yk∥≤εˉ\lVert x_k-y_k\rVert\leq\bar{\varepsilon} does not control ϕ(xk)−ϕ(yk)\phi(x_k)-\phi(y_k) for a general proper, closed, extended-valued convex ϕ\phi. Indeed, xkx_k may lie arbitrarily close to yky_k while satisfy ϕ(xk)=+∞\phi(x_k)=+\infty, so a suboptimality guarantee for the produced iterate would be false without additional regularity such as Lipschitz continuity or smoothness. The point yk+1y_{k+1} is the exact target of the approximate subproblem solved at iteration kk, and the two sequences remain linked by ∥xk+1−yk+1∥≤εˉ\lVert x_{k+1}-y_{k+1}\rVert\leq\bar{\varepsilon}.

Second, these bounds hold only for N≤KtN\leq K_t, so they describe progress until the trajectory enters the tt-tube. Except under strong convexity (Corollary 4.8), we have no a priori bound on KtK_t, so the rates cannot in general be converted into the number of iterations needed to reach ϕ(yN)−ϕ⋆≤ε\phi(y_N)-\phi_\star\leq\varepsilon.

We next bound the suboptimality of the computed iterates after they enter the target neighborhood, in terms of the behavior of ϕ\phi near the set of minimizers. For ρ≥0\rho\geq0, define the tube gap

ω(ρ):=sup⁡{ϕ(x):x∈Tρ(X⋆)}−ϕ⋆,(49)\omega(\rho):=\sup\{\phi(x):x\in\mathcal{T}_\rho(X_\star)\}-\phi_\star, \tag*{(49)}

the worst-case suboptimality of ϕ\phi over the closed ρ\rho-tube Tρ(X⋆)T_{\rho}(\mathcal{X}_{\star}). It is nondecreasing, with ω(0)=0\omega(0)=0. The value ω(ρ)\omega(\rho) may be +∞+\infty, in which case the bounds below are vacuous.

Proposition 4.9 (Accuracy at tube entry). Let Assumptions 2.1 and 4.1 hold and suppose the hitting time is finite, Kt<∞K_t < \infty.

(i) The terminal iterate of Algorithm 2 satisfies ϕ(xKt)−ϕ⋆≤ω(t)\phi(x_{K_t})-\phi_{\star} \le\omega(t).

(ii) Consider the untruncated iteration, and assume that, for every k≥0k \ge0, there exists yk+1∈brox⁡ϕt(xk)y_{k+1} \in\operatorname{brox}_{\phi}^{t}(x_k) such that ∥xk+1−yk+1∥≤ϵk\lVert x_{k+1}-y_{k+1}\rVert\le\epsilon_k. Then dist⁡(xm,X⋆)≤ϵˉ\operatorname{dist}(x_m,\mathcal{X}_{\star}) \le\bar{\epsilon}, and hence ϕ(xm)−ϕ⋆≤ω(ϵˉ)\phi(x_m)-\phi_{\star} \le\omega(\bar{\epsilon}), for every m>Ktm > K_t.

Proof. (i) By definition of KtK_t, the iterate satisfies dist⁡(xKt,X⋆)≤t\operatorname{dist}(x_{K_t},\mathcal{X}_{\star}) \le t, so xKt∈Tt(X⋆)x_{K_t} \in T_t(\mathcal{X}_{\star}) and ϕ(xKt)−ϕ⋆≤ω(t)\phi(x_{K_t})-\phi_{\star} \le\omega(t) by (49). Truncation freezes the sequence, so the same bound holds for every xmx_m with m≥Ktm \ge K_t. (ii) Suppose dist⁡(xk,X⋆)≤t\operatorname{dist}(x_k,\mathcal{X}_{\star}) \le t. Then Bt(xk)B_t(x_k) contains a minimizer, so min⁡y∈Bt(xk)ϕ(y)=ϕ⋆\min_{y \in B_t(x_k)} \phi(y)=\phi_{\star}, and the exact broximal point yk+1∈brox⁡ϕt(xk)y_{k+1} \in\operatorname{brox}_{\phi}^{t}(x_k) lies in X⋆\mathcal{X}_{\star}. Hence dist⁡(xk+1,X⋆)≤∥xk+1−yk+1∥≤ϵk≤ϵˉ<t\operatorname{dist}(x_{k+1},\mathcal{X}_{\star}) \le\lVert x_{k+1}-y_{k+1}\rVert\le\epsilon_k \le\bar{\epsilon} < t, and the hypothesis holds again at k+1k+1. By induction, dist⁡(xm,X⋆)≤ϵˉ\operatorname{dist}(x_m,\mathcal{X}_{\star}) \le\bar{\epsilon} for all m>Ktm > K_t, and ϕ(xm)−ϕ⋆≤ω(ϵˉ)\phi(x_m)-\phi_{\star} \le\omega(\bar{\epsilon}) by (49).

Numerical illustration

We illustrate the convergence behavior of Algorithm 2 on a simple quadratic objective in R2\mathbb{R}^{2},

ϕ(x)=x12+3x22,x⋆=(0,0)⊤,\phi(x)=x_1^2+3x_2^2,\qquad x_{\star}=(0,0)^{\top},

starting from x0=(10,10)⊤x_0=(10,10)^{\top} with radius t=1t=1.

To evaluate the theoretical guarantees, we consider an adversarial approximation operator that, within the ϵˉ\bar{\epsilon}-ball centered at yk+1y_{k+1}, selects the point maximizing the distance to the optimum:

xk+1=yk+1+ϵˉyk+1∥yk+1∥.x_{k+1}=y_{k+1}+\bar{\epsilon}\frac{y_{k+1}}{\lVert y_{k+1}\rVert}.

The adversary thus pushes the iterates as far away from the optimum as possible at each step.

Figure 2 shows the trajectories of Exact BPM and Inexact BPM for ϵˉ∈{0.03,0.50,0.99,1.00,1.01}\bar{\epsilon}\in\{0.03,0.50,0.99,1.00,1.01\}, together with the distance to the optimum at each iteration. Exact BPM reaches x⋆x_{\star} after 16 steps. For ϵˉ<t=1\bar{\epsilon}<t=1, Inexact BPM reaches the tt-tube, as guaranteed by Corollary 4.8, since the quadratic objective is strongly convex with μ=2\mu=2. The hitting times are Kt=15K_t=15, 3030, and 15441544 for ϵˉ=0.03\bar{\epsilon}=0.03, 0.500.50, and 0.990.99, well below the corresponding bounds 426426, 16001600, and 4⋅1064\cdot10^{6} of Corollary 4.8. For ϵˉ=0.03\bar{\epsilon}=0.03, the condition pˉ>0\bar{p}>0 of Theorem 3.4 also holds, since D0−D02−t2≈0.035D_0-\sqrt{D_0^2-t^2}\approx0.035 for D0=102D_0=10\sqrt{2}, and that theorem gives Kt≤1310K_t\le1310. Convergence slows as ϵˉ\bar{\epsilon} approaches tt, in line with the bounds, which degrade as the inner radius r=t−ϵˉr=t-\bar{\epsilon} tends to zero. For ϵˉ≥t\bar{\epsilon}\ge t, Assumption 4.1 fails. With ϵˉ=t\bar{\epsilon}=t, the trajectory is first pushed outward and then stalls; with ϵˉ>t\bar{\epsilon}>t, the adversary pushes it outward indefinitely.

Figure 2. Robustness of Inexact BPM under adversarial perturbations. Exact BPM and Inexact BPM with radius t=1t=1 on ϕ(x)=x12+3x22\phi(x)=x_1^2+3x_2^2 from x0=(10,10)⊤x_0=(10,10)^\top, using an adversarial operator that maximizes the distance to the optimum within εˉ∈{0.03,0.50,0.99,1.00,1.01}\bar{\varepsilon}\in\{0.03,0.50,0.99,1.00,1.01\}. (a) Trajectories. (b) Distance to the optimum against the iteration count (log scale); black-edged markers indicate the hitting time KtK_t. For every tested εˉ<t\bar{\varepsilon}<t, the iterates reach the tt-tube although the adversary pushes them outward. The runs with εˉ≥t\bar{\varepsilon}\ge t never enter the tube and are stopped after 300 iterations.

Conclusion

We introduced Inexact BPM and gave, to our knowledge, the first convergence analysis of the Broximal Point Method with inexact broximal steps. We measure inexactness by the distance to the exact broximal point and make no assumption on how the approximation is obtained. Under summable or uniformly small errors, we bounded the hitting time of the tt-tube (Theorems 3.2 and 3.4). Under the weaker assumption that the errors are uniformly bounded by a constant below the ball radius (ϵˉ<t\bar{\epsilon}<t), we proved sublinear convergence in function value for general convex objectives (Theorem 4.2), which sharpens to a linear rate under bounded sublevel sets (Theorem 4.5) and yields an explicit bound on the hitting time under strong convexity (Corollary 4.8). In the general convex setting, as for Exact BPM, these bounds do not depend on the condition number or on any other regularity property of the objective. In the general convex and bounded-sublevel settings, however, they are function-value guarantees for the exact broximal points that hold until the tt-tube is reached, not complexity bounds for reaching ϵ\epsilon-optimality with the computed iterates.

Since our analysis imposes no structure on how the approximations are computed, it applies to any inner solver whose output satisfies the error conditions. Designing such solvers, and certifying their accuracy in practice, is left to future work.

Acknowledgments

The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) CRG Grant ORFS-CRG12-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.

Proofs

Proof of Lemma 2.4

Lemma 2.4 (One-step contraction [Gruntkowska et al., 2025, Theorem 8.1(ii)]). Let Assumption 2.1 hold. For any x∈Rdx \in\mathbb{R}^{d} satisfying Bt(x)∩dom⁡ϕ≠∅B_t(x) \cap\operatorname{dom}\phi\ne\varnothing and dist⁡(x,X⋆)>t\operatorname{dist}(x,\mathcal{X}_{\star}) > t, let y=brox⁡ϕt(x)y = \operatorname{brox}_{\phi}^{t}(x) be the unique broximal point (cf. Remark 2.3). Then, for every minimizer x⋆∈X⋆x_{\star} \in\mathcal{X}_{\star}, we have:

∥y−x⋆∥2≤∥x−x⋆∥2−t2.(50)\lVert y-x_{\star}\rVert^{2} \le\lVert x-x_{\star}\rVert^{2}-t^{2}. \tag*{(50)}

Proof. We adapt the argument of Gruntkowska et al. [2025, Theorem D.1]. Since ϕ\phi is lower semicontinuous and Bt(x)B_t(x) is compact, the minimum is attained; it is finite because Bt(x)∩dom⁡ϕ≠∅B_t(x) \cap\operatorname{dom}\phi\ne\varnothing and ϕ≥ϕ⋆\phi\ge\phi_{\star}. An interior solution would be a local minimizer of ϕ\phi and, by convexity, a global minimizer, contradicting Bt(x)∩X⋆=∅B_t(x) \cap\mathcal{X}_{\star} = \varnothing. Hence every solution lies on the boundary of the ball. If two distinct solutions existed, their midpoint would also be a solution by convexity, but would lie in the interior of the Euclidean ball. Thus the solution yy is unique and satisfies ∥y−x∥=t\lVert y-x\rVert= t.

Fix x⋆∈X⋆x_{\star} \in\mathcal{X}_{\star}. Since ϕ(y)>ϕ⋆\phi(y) > \phi_{\star}, convexity implies

ϕ(y+λ(x⋆−y))<ϕ(y),0<λ≤1.\phi\left(y+\lambda(x_{\star}-y)\right) < \phi(y), \qquad0 < \lambda\le1.

Optimality of yy therefore gives ∥y+λ(x⋆−y)−x∥2>t2\lVert y+\lambda(x_{\star}-y)-x\rVert^{2} > t^{2}. Expanding, dividing by λ\lambda, and letting λ↓0\lambda\downarrow0 yields ⟨x−y,y−x⋆⟩≥0\langle x-y,y-x_{\star}\rangle\ge0. Hence

∥x−x⋆∥2=t2+∥y−x⋆∥2+2⟨x−y,y−x⋆⟩≥t2+∥y−x⋆∥2.\lVert x-x_{\star}\rVert^{2} = t^{2}+\lVert y-x_{\star}\rVert^{2}+2\langle x-y,y-x_{\star}\rangle\ge t^{2}+\lVert y-x_{\star}\rVert^{2}.

Proof of Lemma 3.1

Lemma 3.1. Let {xk}k≥0\{x_k\}_{k\ge0} be the sequence generated by Algorithm 2. Suppose Assumption 2.1 holds and Bt(xk)∩dom⁡ϕ≠∅B_t(x_k) \cap\operatorname{dom}\phi\ne\varnothing for every k<Ktk < K_t. The distances Dk=dist⁡(xk,X⋆)D_k = \operatorname{dist}(x_k,\mathcal{X}_{\star}) to the set of minimizers satisfy the following relations:

  1. If Dk>tD_k > t, we have the recursive upper bound:

Dk+1≤Dk2−t2+εk.(51)D_{k+1} \le\sqrt{D_k^2-t^2}+\varepsilon_k. \tag*{(51)}
  1. If Dk≤tD_k \le t, the algorithm truncates the update step (xk+1=xk)(x_{k+1}=x_k), and thus:

Dk+1=Dk≤t.(52)D_{k+1}=D_k\le t. \tag*{(52)}

Proof. Assume first that Dk>tD_k > t, and let

yk+1=brox⁡ϕt(xk).y_{k+1}=\operatorname{brox}_{\phi}^{t}(x_k).

By the one-step contraction property (Lemma 2.4), we have

∥yk+1−z∥2≤∥xk−z∥2−t2\lVert y_{k+1}-z\rVert^{2}\le\lVert x_k-z\rVert^{2}-t^{2}

for every minimizer z∈X⋆z \in\mathcal{X}_{\star}. Let xk⋆∈X⋆x_k^{\star} \in\mathcal{X}_{\star} be the projection of xkx_k onto X⋆\mathcal{X}_{\star}, so that ∥xk−xk⋆∥=dist⁡(xk,X⋆)\lVert x_k-x_k^{\star}\rVert=\operatorname{dist}(x_k,\mathcal{X}_{\star}). Substituting z=xk⋆z=x_k^{\star} yields:

dist⁡(yk+1,X⋆)2≤∥yk+1−xk⋆∥2≤∥xk−xk⋆∥2−t2=Dk2−t2,\operatorname{dist}(y_{k+1},\mathcal{X}_{\star})^{2}\le\lVert y_{k+1}-x_k^{\star}\rVert^{2}\le\lVert x_k-x_k^{\star}\rVert^{2}-t^{2}=D_k^{2}-t^{2},

and therefore,

dist⁡(yk+1,X⋆)≤Dk2−t2.(53)\operatorname{dist}(y_{k+1},\mathcal{X}_{\star})\le\sqrt{D_k^{2}-t^{2}}. \tag*{(53)}

By (12), the approximate iterate satisfies ∥xk+1−yk+1∥≤εk\lVert x_{k+1}-y_{k+1}\rVert\le\varepsilon_k. The triangle inequality now yields

Dk+1=dist⁡(xk+1,X⋆)≤dist⁡(yk+1,X⋆)+∥xk+1−yk+1∥.D_{k+1}=\operatorname{dist}(x_{k+1},\mathcal{X}_{\star})\le\operatorname{dist}(y_{k+1},\mathcal{X}_{\star})+\lVert x_{k+1}-y_{k+1}\rVert.

Applying (53) and (12) to the right-hand side gives:

Dk+1≤Dk2−t2+εk,D_{k+1}\le\sqrt{D_k^{2}-t^{2}}+\varepsilon_k,

which proves part (i).

If Dk≤tD_k\le t, the algorithm sets xk+1=xkx_{k+1}=x_k. Thus, Dk+1=Dk≤tD_{k+1}=D_k\le t, establishing part (ii).

Proof of Theorem 3.2

Theorem 3.2. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 with radius t>0t>0, and suppose Assumption 2.1 holds. Assume further that every active subproblem is well-defined, in the sense that Bt(xk)∩dom⁡ϕ≠∅B_t(x_k)\cap\operatorname{dom}\phi\ne\varnothing for all k<Ktk<K_t. If the error sequence is summable, meaning

Σ:=∑k=0∞εk<∞,(54)\Sigma:= \sum_{k=0}^{\infty}\varepsilon_k < \infty, \tag*{(54)}

then the hitting time KtK_t to the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) satisfies:

Kt≤⌈(D0+Σ)2t2⌉.(55)K_t\leq\left\lceil\frac{(D_0+\Sigma)^2}{t^2}\right\rceil. \tag*{(55)}

Proof. If D0≤tD_0\leq t, then Kt=0K_t=0 and the claimed bound holds trivially.

Assume henceforth that D0>tD_0>t. By definition, Dk>tD_k>t for all k<Ktk<K_t, so Lemma 3.1(i) applies at every such step:

Dk+12≤Dk2−t2+εk2+2εkDk2−t2,∀k<Kt.(56)D_{k+1}^2\leq D_k^2-t^2+\varepsilon_k^2+2\varepsilon_k\sqrt{D_k^2-t^2},\qquad\forall k<K_t. \tag*{(56)}

We upper bound the square root term by DkD_k, so

Dk+12≤Dk2−t2+εk2+2εkDk,∀k<Kt.(57)D_{k+1}^2\leq D_k^2-t^2+\varepsilon_k^2+2\varepsilon_kD_k,\qquad\forall k<K_t. \tag*{(57)}

By Lemma 3.1(i), Di+1≤Di+εiD_{i+1}\leq D_i+\varepsilon_i for every i<Kti<K_t. Hence Dk≤D0+∑i=0k−1εiD_k\leq D_0+\sum_{i=0}^{k-1}\varepsilon_i for every finite k≤Ktk\leq K_t. Substituting this bound into (52) yields

Dk+12≤Dk2−t2+εk2+2εk(D0+∑i=0k−1εi).D_{k+1}^2\leq D_k^2-t^2+\varepsilon_k^2+2\varepsilon_k\left(D_0+\sum_{i=0}^{k-1}\varepsilon_i\right).

For any finite integer N≤KtN\leq K_t, summing over k=0,…,N−1k=0,\ldots,N-1 and using

∑k=0N−1εk2+2∑k=0N−1εk∑i=0k−1εi=(∑k=0N−1εk)2\sum_{k=0}^{N-1}\varepsilon_k^2+2\sum_{k=0}^{N-1}\varepsilon_k\sum_{i=0}^{k-1}\varepsilon_i=\left(\sum_{k=0}^{N-1}\varepsilon_k\right)^2

gives

DN2≤(D0+∑k=0N−1εk)2−Nt2≤(D0+Σ)2−Nt2.D_N^2\leq\left(D_0+\sum_{k=0}^{N-1}\varepsilon_k\right)^2-Nt^2\leq(D_0+\Sigma)^2-Nt^2.

Since DN2≥0D_N^2\geq0, we obtain Nt2≤(D0+Σ)2Nt^2\leq(D_0+\Sigma)^2. If Kt=∞K_t=\infty, choosing a finite integer N>(D0+Σ)2/t2N>(D_0+\Sigma)^2/t^2 gives a contradiction. Therefore, Kt<∞K_t<\infty, and taking N=KtN=K_t establishes the claimed bound. □\square

Proof of Theorem 3.4

Theorem 3.4. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 with radius t<D0t<D_0, and suppose Assumption 2.1 holds. Suppose the error sequence is uniformly bounded such that εk≤εˉ\varepsilon_k\leq\bar{\varepsilon} for all k≥0k\geq0, and let

pˉ:=t2−εˉ2−2εˉD02−t2(58)\bar{p}:=t^2-\bar{\varepsilon}^2-2\bar{\varepsilon}\sqrt{D_0^2-t^2} \tag*{(58)}

denote the initial worst-case progress guarantee. If the uniform error bound ensures that pˉ>0\bar{p}>0, that is, if εˉ<D0−D02−t2\bar{\varepsilon}<D_0-\sqrt{D_0^2-t^2}, then the hitting time KtK_t to the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) satisfies:

Kt≤⌈D02pˉ⌉.(59)K_t\leq\left\lceil\frac{D_0^2}{\bar{p}}\right\rceil. \tag*{(59)}

Proof. We first verify that every active subproblem is well-defined. The condition pˉ>0\bar{p}>0 implies εˉ<D0−D02−t2<t\bar{\varepsilon}<D_0-\sqrt{D_0^2-t^2}<t. The initial ball intersects dom⁡ϕ\operatorname{dom}\phi because x0∈dom⁡ϕx_0\in\operatorname{dom}\phi. Suppose that the subproblem at iteration k<Ktk<K_t is well-defined, and let yk+1y_{k+1} denote its exact solution. Then yk+1∈dom⁡ϕy_{k+1}\in\operatorname{dom}\phi and ∥xk+1−yk+1∥≤εk≤εˉ<t\lVert x_{k+1}-y_{k+1}\rVert\leq\varepsilon_k\leq\bar{\varepsilon}<t, so Bt(xk+1)∩dom⁡ϕ≠∅B_t(x_{k+1})\cap\operatorname{dom}\phi\ne\varnothing. Thus every active subproblem is well-defined by induction. Since Dk>tD_k>t for all k<Ktk<K_t, Lemma 3.1(i) yields:

Dk+12≤Dk2−t2+εk2+2εkDk2−t2,∀k<Kt.(60)D_{k+1}^2\leq D_k^2-t^2+\varepsilon_k^2+2\varepsilon_k\sqrt{D_k^2-t^2},\qquad\forall k<K_t. \tag*{(60)}

Since εk≤εˉ\varepsilon_k \le\bar{\varepsilon} and the right-hand side of (60) is monotonically increasing with respect to εk≥0\varepsilon_k \ge0, we can substitute the uniform error bound:

Dk+12≤Dk2−t2+εˉ2+2εˉDk2−t2,∀k<Kt.(61)D_{k+1}^{2} \le D_k^{2} - t^{2} + \bar{\varepsilon}^{2} + 2\bar{\varepsilon}\sqrt{D_k^{2}-t^{2}}, \qquad\forall k < K_t. \tag*{(61)}

Evaluating (61) at k=0k=0 under the assumption that pˉ>0\bar{p}>0 yields D12≤D02−pˉ<D02D_1^{2}\le D_0^{2}-\bar{p}<D_0^{2}. If Dk≤D0D_k\le D_0 and k<Ktk<K_t, then (61) gives Dk+12≤Dk2−pˉ<Dk2D_{k+1}^{2}\le D_k^{2}-\bar{p}<D_k^{2}. Induction therefore shows that the sequence {Dk}k=0Kt\{D_k\}_{k=0}^{K_t} is decreasing and that Dk≤D0D_k\le D_0.

Substituting the upper bound Dk≤D0D_k\le D_0 into the positive square root term of (61) yields a constant minimum progress per step:

Dk+12≤Dk2−(t2−εˉ2−2εˉD02−t2)=Dk2−pˉ.D_{k+1}^{2} \le D_k^{2} - \left(t^{2}-\bar{\varepsilon}^{2}-2\bar{\varepsilon}\sqrt{D_0^{2}-t^{2}}\right)=D_k^{2}-\bar{p}.

Fix any finite integer N≤KtN\le K_t. Summing the preceding inequality from k=0k=0 to N−1N-1 gives

Npˉ≤D02.N\bar{p}\le D_0^{2}.

If Kt=+∞K_t=+\infty, we could choose a finite integer N>D02/pˉN>D_0^{2}/\bar{p}, obtaining a contradiction. Hence Kt<+∞K_t<+\infty, and taking N=KtN=K_t gives the claimed bound.

Proof of Theorem 4.5

Theorem 4.5. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 and {yk}k≥0\{y_k\}_{k\geq0} the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume D0>tD_0>t and εˉ>0\bar{\varepsilon}>0. If ϕ\phi has bounded sublevel sets (Definition 4.4), then for any iteration N≤KtN\le K_t, the suboptimality gap satisfies:

ϕ(yN)−ϕ⋆≤min⁡{(1+NεˉD0)−rεˉ,(1−rDmax⁡)N}(ϕ(y0)−ϕ⋆),(62)\phi(y_N)-\phi_\star\le\min\left\{\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\frac{r}{\bar{\varepsilon}}},\left(1-\frac{r}{D_{\max}}\right)^N\right\}\left(\phi(y_0)-\phi_\star\right), \tag*{(62)}

where rr is the inner radius defined in (26), and Dmax⁡D_{\max} is given by (44).

Proof. Since Lx0L_{x_0} is bounded, Dmax⁡=sup⁡y∈Lx0dist⁡(y,X⋆)<∞D_{\max}=\sup_{y\in L_{x_0}}\operatorname{dist}(y,\mathcal{X}_\star)<\infty. For every active iteration k<Ktk<K_t, combining (34) and (32) gives

ϕ(yk+1)≤ϕ(zk)≤ϕ(yk).\phi(y_{k+1})\le\phi(z_k)\le\phi(y_k).

Hence, by induction, ϕ(yk)≤ϕ(y0)=ϕ(x0)\phi(y_k)\le\phi(y_0)=\phi(x_0) for every k≤Ktk\le K_t. Therefore, yk∈Lx0y_k\in L_{x_0} for every k≤Ktk\le K_t, and consequently

∥yk−yk⋆∥=dist⁡(yk,X⋆)≤Dmax⁡.\lVert y_k-y_k^\star\rVert=\operatorname{dist}(y_k,\mathcal{X}_\star)\le D_{\max}.

We now have two independent upper bounds on the distance to the set of minimizers for all k≤Ktk\le K_t: the global bound ∥yk−yk⋆∥≤Dmax⁡\lVert y_k-y_k^\star\rVert\le D_{\max}, and the accumulated error bound ∥yk−yk⋆∥≤D0+kεˉ\lVert y_k-y_k^\star\rVert\le D_0+k\bar{\varepsilon} derived in the proof of Theorem 4.2. Substituting the accumulated error bound into the one-step contraction (35) and chaining over NN steps recovers the sublinear rate from Theorem 4.2:

VN≤V0∏k=0N−1(1−rD0+kεˉ)≤V0(1+NεˉD0)−rεˉ.V_N\le V_0\prod_{k=0}^{N-1}\left(1-\frac{r}{D_0+k\bar{\varepsilon}}\right)\le V_0\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-\frac{r}{\bar{\varepsilon}}}.

Alternatively, substituting the global bound ∥yk−yk⋆∥≤Dmax⁡\lVert y_k-y_k^\star\rVert\le D_{\max} into (35) and chaining over NN steps yields the linear rate:

VN≤V0∏k=0N−1(1−rDmax⁡)=V0(1−rDmax⁡)N.V_N\le V_0\prod_{k=0}^{N-1}\left(1-\frac{r}{D_{\max}}\right)=V_0\left(1-\frac{r}{D_{\max}}\right)^N.

Since both upper bounds hold, the suboptimality gap VNV_N is bounded by their minimum, completing the proof.

Proof of Theorem 4.7

Theorem 4.7. Let {xk}k≥0\{x_k\}_{k\geq0} be the sequence generated by Algorithm 2 and {yk}k≥0\{y_k\}_{k\geq0} the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume D0>tD_0>t and εˉ>0\bar{\varepsilon}>0. If ϕ\phi is μ\mu-strongly convex, then for any iteration N≤KtN\leq K_t, the suboptimality gap satisfies:

ϕ(yN)−ϕ⋆≤min⁡{(1+NεˉD0)−r/εˉV0,(1−rμ2V0)NV0,V0−Nμr22}.(63)\phi(y_N)-\phi_\star\leq\min\left\{\left(1+\frac{N\bar{\varepsilon}}{D_0}\right)^{-r/\bar{\varepsilon}}V_0,\left(1-r\sqrt{\frac{\mu}{2V_0}}\right)^N V_0,V_0-N\frac{\mu r^2}{2}\right\}. \tag*{(63)}

where V0=ϕ(y0)−ϕ⋆V_0=\phi(y_0)-\phi_\star, and rr is the inner radius defined in (26).

Proof. Because ϕ\phi is μ\mu-strongly convex, its set of minimizers is a singleton, X⋆={x⋆}\mathcal{X}_\star=\{x_\star\}, and its sublevel sets are bounded. Specifically, for any y∈Lx0y\in L_{x_0}, strong convexity implies:

μ2∥y−x⋆∥2≤ϕ(y)−ϕ⋆≤ϕ(y0)−ϕ⋆=V0.\frac{\mu}{2}\lVert y-x_\star\rVert^2\leq\phi(y)-\phi_\star\leq\phi(y_0)-\phi_\star=V_0.

Thus, the largest distance to x⋆x_\star within the initial sublevel set is bounded by Dmax⁡≤2V0/μD_{\max}\leq\sqrt{2V_0/\mu}. Substituting this Dmax⁡D_{\max} into the linear bound from Theorem 4.5 yields the second term in the minimum. The first term follows directly from Theorem 4.2.

As shown in the proof of Theorem 4.2, ∥xk−yk∥≤εˉ\lVert x_k-y_k\rVert\leq\bar{\varepsilon} implies Br(yk)⊆Bt(xk)B_r(y_k)\subseteq B_t(x_k), and hence:

ϕ(yk+1)≤ϕ(wk):=min⁡z∈Br(yk)ϕ(z),\phi(y_{k+1})\leq\phi(w_k):=\min_{z\in B_r(y_k)}\phi(z),

where wkw_k is a minimizer of ϕ\phi over Br(yk)B_r(y_k). Since yk∈dom⁡ϕy_k\in\operatorname{dom}\phi, r>0r>0, and wk∈brox⁡rr(yk)w_k\in\operatorname{brox}_r^r(y_k), all hypotheses of Gruntkowska et al. [2025] Theorem D.2 are satisfied. Consequently, there exists cr(yk)≥0c_r(y_k)\geq0 such that

cr(yk)(yk−wk)∈∂ϕ(wk).c_r(y_k)(y_k-w_k)\in\partial\phi(w_k).

Applying μ\mu-strong convexity with this subgradient yields

ϕ(yk)≥ϕ(wk)+⟨cr(yk)(yk−wk),yk−wk⟩+μ2∥yk−wk∥2=ϕ(wk)+cr(yk)∥yk−wk∥2+μ2∥yk−wk∥2≥ϕ(wk)+μ2∥yk−wk∥2.\begin{aligned} \phi(y_k)&\geq\phi(w_k)+\langle c_r(y_k)(y_k-w_k),y_k-w_k\rangle+\frac{\mu}{2}\lVert y_k-w_k\rVert^2\\ &=\phi(w_k)+c_r(y_k)\lVert y_k-w_k\rVert^2+\frac{\mu}{2}\lVert y_k-w_k\rVert^2\\ &\geq\phi(w_k)+\frac{\mu}{2}\lVert y_k-w_k\rVert^2. \end{aligned}

For every active iteration k<Ktk<K_t,

dist⁡(yk,X⋆)≥dist⁡(xk,X⋆)−∥xk−yk∥>t−εˉ=r.\operatorname{dist}(y_k,\mathcal{X}_\star)\geq\operatorname{dist}(x_k,\mathcal{X}_\star)-\lVert x_k-y_k\rVert>t-\bar{\varepsilon}=r.

Hence, X⋆∩Br(yk)=∅\mathcal{X}_\star\cap B_r(y_k)=\varnothing. By Gruntkowska et al. [ [8] Theorem D.1(ii), this boundary condition forces ∥yk−wk∥=t−εˉ=r\lVert y_k-w_k\rVert=t-\bar{\varepsilon}=r. Combining these inequalities, we obtain a guaranteed absolute function value decrease of:

ϕ(yk+1)≤ϕ(wk)≤ϕ(yk)−μ2r2.\phi(y_{k+1})\leq\phi(w_k)\leq\phi(y_k)-\frac{\mu}{2}r^2.

Applying this recursively over NN steps gives ϕ(yN)−ϕ⋆≤V0−Nμr22\phi(y_N)-\phi_\star\leq V_0-N\frac{\mu r^2}{2}. Since all three bounds hold, the suboptimality gap is bounded by their minimum.

Proof of Corollary 4.8

Corollary 4.8 (Finite hitting time). Under the conditions of Theorem 4.7, the hitting time KtK_t to the tt-tube Tt(X⋆)\mathcal{T}_t(\mathcal{X}_\star) is bounded by:

Kt≤⌈2(ϕ(y0)−ϕ⋆)μr2⌉.(64)K_t\leq\left\lceil\frac{2(\phi(y_0)-\phi_\star)}{\mu r^2}\right\rceil. \tag*{(64)}

Proof. By Theorem 4.7, for every finite integer N≤KtN\leq K_t,

0≤ϕ(yN)−ϕ⋆≤V0−Nμr22.0\leq\phi(y_N)-\phi_\star\leq V_0-N\frac{\mu r^2}{2}.

Consequently,

N≤2V0μr2N \le\frac{2V_0}{\mu r^2}

for every finite N≤KtN \le K_t.

If Kt=+∞K_t = +\infty, we could choose a finite integer N>2V0/(μr2)N > 2V_0/(\mu r^2), which would contradict the preceding inequality. Hence, Kt<+∞K_t < +\infty. Taking N=KtN = K_t now gives

Kt≤2V0μr2≤⌊2V0μr2⌋,K_t \le\frac{2V_0}{\mu r^2} \le\left\lfloor\frac{2V_0}{\mu r^2} \right\rfloor,

which proves the claim. □\square

References

  1. [1]P. Bianchi. Ergodic convergence of a stochastic proximal point algorithm. SIAM Journal on Optimization, 26(4): 2235–2260, 2016.arxiv.org/abs/1504.05400
  2. [2]S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1–122, 2011.
  3. [3]Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. T. Lee, A. Sidford, and K. Tian. Acceleration with a ball optimization oracle. Advances in Neural Information Processing Systems, 33:19052–19063, 2020.arxiv.org/abs/2003.08078
  4. [4]Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 866–882. PMLR, 2021.arxiv.org/abs/2105.01778
  5. [5]A. R. Conn, N. I. M. Gould, and P. L. Toint. Trust Region Methods, volume 1 of MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000.DOI
  6. [6]J. Eckstein and D. P. Bertsekas. On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293–318, 1992.DOI
  7. [8]K. Gruntkowska, H. Li, A. Rane, and P. Richtárik. The Ball-Proximal (=“Broximal”) Point Method: a new algorithm, convergence theory, and applications. arXiv preprint arXiv:2502.02002, 2025.arxiv.org/abs/2502.02002
  8. [9]O. Güler. On the convergence of the proximal point algorithm for convex minimization. SIAM Journal on Control and Optimization, 29(2):403–419, 1991.DOI
  9. [10]O. Güler. New proximal point algorithms for convex minimization. SIAM Journal on Optimization, 2(4):649–664, 1992.DOI
  10. [11]K. Jordan, Y. Jin, V. Boza, J. You, F. Cesista, L. Newhouse, and J. Bernstein. Muon: An optimizer for hidden layers in neural networks. https://kellerjordan.github.io/posts/muon/, 2024.
  11. [13]Y. Nesterov. A method for solving the convex programming problem with convergence rate O(1/k²). Doklady Akademii Nauk SSSR, 269(3):543–547, 1983.
  12. [14]Y. Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29:519–531, 1984.
  13. [15]Y. Nesterov. Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer, Cham, 2nd edition, 2018.DOI
  14. [16]N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127–239, 2014.DOI
  15. [17]T. Pethick, W. Xie, K. Antonakopoulos, Z. Zhu, A. Silveti-Falls, and V. Cevher. Training deep learning models with norm-constrained LMOs. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 49069–49104. PMLR, 2025.arxiv.org/abs/2502.07529
  16. [18]A. Riabinin, E. Shulgin, K. Gruntkowska, and P. Richtárik. From Muon to Gluon: Bridging theory and practice of LMO-based optimizers for LLMs. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 105039–105082. PMLR, 2026.arxiv.org/abs/2505.13416
  17. [19]P. Richtárik and H. Li. A sharper theory of ball-proximal optimization: Convergence and radius selection. arXiv preprint arXiv:2609.35147, 2026.arxiv.org/abs/2609.35147
  18. [20]P. Richtárik, A. Sadiev, and Y. Demidovich. A unified theory of stochastic proximal point methods without smoothness. arXiv preprint arXiv:2405.15941, 2024.arxiv.org/abs/2405.15941
  19. [21]R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877–898, 1976.DOI
  20. [22]E. Ryu and S. Boyd. Stochastic proximal iteration: a non-asymptotic improvement upon stochastic gradient descent. Manuscript, https://stanford.edu/~boyd/papers/pdf/spi.pdf, 2017.
  21. [24]N. Z. Shor. Minimization Methods for Non-Differentiable Functions, volume 3 of Springer Series in Computational Mathematics. Springer, Berlin, Heidelberg, 1985.DOI
  22. [25]M. V. Solodov and B. F. Svaiter. A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis, 7(4):323–345, 1999.DOI

Paper details

vlnc:W_yjnp8tap
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents