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
where is proper, closed, and convex. We assume that has a nonempty set of minimizers, that is,
Since is nonempty, the minimum is attained. We denote the corresponding optimal value by
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 , the next iterate is the solution of the following minimization problem,
where 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 of radius centered at the current iterate ,
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 (), 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 . 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 -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 .
Algorithm 1 Exact BPM: The exact broximal point method.
Input: Starting point , radius
for do
if then
else
end if
end for
Assumption 2.1. The function is proper, closed, and convex, and its set of minimizers,
is nonempty.
Closedness and convexity of the objective function imply closedness and convexity of its set of minimizers , ensuring uniqueness of projections onto it. We denote the Euclidean distance of an iterate to this set by
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 and a function satisfying Assumption 2.1, the broximal operator is the set-valued mapping
where is the closed Euclidean ball of radius 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 , then is nonempty and the subproblem has a finite minimum. Moreover, if , that is, if , then is a singleton lying on the boundary of the ball:
In such cases, we write 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 satisfying and , let be the unique broximal point (cf. Remark 2.3). Then, for every minimizer , we have:
By Lemma 2.4, as long as , each exact broximal step reduces the squared distance to by at least ; once a minimizer lies within distance of , 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 , Exact BPM reaches a minimizer in at most
iterations [Gruntkowska et al., 2025, Theorem 8.1(iii)], where 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 and , 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 [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 produced by Inexact BPM (Algorithm 2) lies no more than some distance from the exact broximal step evaluated at the current iterate , that is,
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 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 -ball optimization oracle, which, when queried at , returns a point with for some . 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 that must be a small fraction of , depending on the smoothness constant, the initial distance to the optimum, and the target accuracy. We require only that 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 (; cf. Assumption 4.1). Moreover, their oracle output lies in , whereas our iterate need not lie in .
With approximation errors, the iterates can in general only be guaranteed to reach a neighborhood of , not itself. We use the following neighborhood as the target.
Definition 2.5 (Tube). Given , the closed -tube around a set is
Since is closed, , so the -tube generalizes the target set of the exact method. The radius 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 . This truncation is an analytical device, not an implementable stopping rule: the test cannot be evaluated in general, since is unknown. The updates themselves do not require the test.
Algorithm 2 Inexact BPM: The truncated inexact broximal point method.
1: Input: Starting point , radius 2: for do 3: if then 4: ▷ The approximation satisfies (12). 5: else 6: ▷ Truncation step. 7: end if 8: end for
Compared with Algorithm 1, Algorithm 2 makes two changes. First, only approximates , with error at most as in (12); the tolerances need not be known to run the method. Second, the method stops when it enters rather than when it reaches .
To quantify the convergence properties of Inexact BPM, we analyze the number of iterations required for the sequence to enter the -tube . We formalize this through the notion of a hitting time.
Definition 2.6 (Hitting time). The hitting time of Algorithm 2 to the -tube is defined as:
where we adopt the standard convention that .
Without errors, 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, 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 be the sequence generated by Algorithm 2. Suppose Assumption 2.1 holds and for every . The distances to the set of minimizers satisfy the following relations:
(i) If , we have the recursive upper bound:
(ii) If , the algorithm truncates the update step (), and thus:
Thus the contraction of the exact step in Lemma 2.4 survives, up to an additive error 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 be the sequence generated by Algorithm 2 with radius , and suppose Assumption 2.1 holds. Assume further that every active subproblem is well-defined, in the sense that for all . If the error sequence is summable, meaning
then the hitting time to the -tube satisfies:
When , the bound reduces to , the same expression as the Exact BPM baseline (11), although measures tube entry rather than arrival at a minimizer. The term accounts for the worst-case accumulation of approximation errors, which may increase the distance to the set of minimizers by up to relative to its initial value . Thus finite tube entry is preserved under summable errors, with the worst-case hitting-time bound growing quadratically in the total error budget .
If, for example, for some , then (18) gives .
The condition in Theorem 3.2 is needed because the summable regime places no bound on any individual error, so a single large perturbation may move to a point whose ball misses ; the condition holds automatically when for all (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 be the sequence generated by Algorithm 2 with radius , and let denote a sequence of nonnegative error bounds for the approximations as described in (12). For each iteration satisfying , the progress guarantee is defined as:
Table 1: Hitting time bounds. The hitting time to the -tube is defined in (14). Here is the initial distance to the set of minimizers, and is the initial worst-case progress guarantee (22) under a uniform error bound . All bounds are independent of the condition number and of any other regularity parameter of the objective.
| Result | Error regime | Bound on |
| Theorem 8.1(iii) [8] | No errors: | |
| Theorem 3.2 | Summable errors: | |
| Theorem 3.4 | Uniformly small errors: |
Table 1.
Since , we have . Squaring both sides of the distance recursion in Lemma 3.1(i) yields
so the progress guarantee quantifies the minimum guaranteed reduction in the squared distance to the set of minimizers at step . For , we recover , the exact per-step reduction of Exact BPM.
The progress guarantee depends on the radius , the error bound , and the current distance . It is positive only if the error bound is small enough. Specifically, we have if and only if
If this condition is violated (), 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 be the sequence generated by Algorithm 2 with radius , and suppose Assumption 2.1 holds. Suppose the error sequence is uniformly bounded such that for all , and let
denote the initial worst-case progress guarantee. If the uniform error bound ensures that , that is, if , then the hitting time to the -tube satisfies:
The bound (23) has the same form as the exact baseline (11), with the per-step progress replaced by . The proof shows that for all , however the approximation errors evolve, so the squared distance to decreases by at least 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 , and for any fixed radius ,
That is, for any fixed , a sufficiently distant starting point gives , 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 in (12) are uniformly bounded by a constant smaller than the radius :
The error bound may be arbitrarily close to . 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 cannot be dropped. Since , an adversary with can choose at every step, so the method stalls at .
Throughout this section, and are fixed constants satisfying Assumption 4.1. We define the inner radius ,
and the auxiliary sequence ,
The point is the point that Inexact BPM would compute in iteration without approximation error. With this notation, the approximation error bound (12) may equivalently be expressed as
Equivalently, for every finite ,
Since , the bound holds for every finite .
For general convex objectives, we have no bound on 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 under Assumption 2.1 alone. We therefore analyze the decrease of the objective along the sequence of exact broximal points. The key observation, illustrated in Figure 1, is that implies : any point within distance of lies within distance of and is therefore feasible for the subproblem that defines .

Figure 1. Geometry of Assumption 4.1. The approximation error bound guarantees the inclusion for . Thus, a reference point on the segment , where is the projection of onto , lies in if . Since minimizes over , we get , which yields a decrease in function value.
General convex objectives
Our first result requires no assumption on beyond Assumption 2.1. It shows that the suboptimality gap decays at a sublinear rate governed by the ratio .
Theorem 4.2. Let be the sequence generated by Algorithm 2 and the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume and that the uniform error bound of Assumption 4.1 is positive, . For any iteration , the suboptimality gap satisfies:
where is the inner radius defined in (26).
Proof. The following proof adapts the auxiliary point construction of Carmon et al. [ [3]. Fix an iteration . Since , we have . Therefore,
Let be the unique projection of onto . Then
and hence
Define the reference point
Then lies at distance from on the line segment connecting and . Because , convexity of yields
By the triangle inequality and Assumption 4.1, the distance from the reference point to the current approximate iterate satisfies:
Thus, , meaning is a feasible point for the broximal subproblem solved at iteration . Because is defined as the exact minimizer of over this ball, we have:
Plugging (34) into (32) provides a one-step contraction bound for the sequence :
To bound the denominator, we recall that, for every finite , the point is generated by an exact broximal step from . By Lemma 2.4, the distance to the set of minimizers satisfies
Furthermore, from the distance recursion in Lemma 3.1(i), we know
By induction, it follows that for every finite . Since yields , it follows that for every finite , the distance to the set of minimizers is bounded by:
Let denote the suboptimality gap. Chaining the one-step contractions from (35) for with , and applying the distance bound (38) gives:
Applying the standard inequality for yields:
Bounding the sum from below with its corresponding integral gives:
Substituting this into the exponential bound establishes the claim:
Remark 4.3 (Convergence limit in the exact case). Taking the limit of (30) as yields the bound . For exact steps, setting and in (39) gives the sharper bound
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 of Gruntkowska et al. [ [8].
Writing with , so that , Theorem 4.2 gives the rate ; for example, , , and give , , and . The exponent depends only on the relative error, and since , the constant hidden in is . By contrast, the bounds of standard first-order methods scale with function-specific constants: subgradient methods for -Lipschitz functions achieve [24, 15], gradient descent for -smooth functions achieves [15], and accelerated methods improve this to [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 are bounded, which confines the reference points to a bounded region.
Definition 4.4 (Bounded sublevel sets). The function has bounded sublevel sets if for every , the corresponding sublevel set is bounded. We denote the sublevel set of the initial point by and its largest distance to the set of minimizers by :
Theorem 4.5. Let be the sequence generated by Algorithm 2 and the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume and . If has bounded sublevel sets (Definition 4.4), then for any iteration , the suboptimality gap satisfies:
where is the inner radius defined in (26), and is given by (44).
When , the first bound in (45) can be much smaller in early iterations. For large , the second bound gives linear convergence with factor . This rate is no longer independent of the objective, since depends on the sublevel set (cf. Table 2). The theorem also shows that , although it gives no bound on . Indeed, if , then ; since is compact and is lower semicontinuous, this forces , contradicting for all (see the proof of Theorem 4.2).
Table | Suboptimality bounds. Here is the initial distance to the set of minimizers, is the initial suboptimality gap, and 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 -tube, . 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. |
| Result | Assumptions | Bound on Suboptimality Gap | Independent of Regularity |
| Theorem 3.1 [19] | Convexity, exact steps | ✔ | |
| Theorem 4.2 | Convexity | ✔ | |
| Theorem 4.5 | Convexity, bounded sublevel sets | ✘ | |
| Theorem 4.7 | -strong convexity | ✘ |
Table 2.
Strongly convex objectives
Under strong convexity, the reference values 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 is -strongly convex with parameter if for all and , the following holds:
Theorem 4.7. Let be the sequence generated by Algorithm 2 and the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume and . If is -strongly convex, then for any iteration , the suboptimality gap satisfies:
where , and is the inner radius defined in (26).
Which of the three bounds is smallest depends on the parameters and on . Since the gap is nonnegative, the constant decrease 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 to the -tube is bounded by:
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 . Under strong convexity, Corollary 4.8 additionally supplies an explicit finite bound on and thus a complexity guarantee for reaching the -tube. This bound depends explicitly on the strong-convexity parameter .
The guarantees of this section have two limitations. First, they bound the suboptimality along the auxiliary sequence of exact proximal points, rather than along the iterates actually produced by Algorithm 2. This distinction is unavoidable under our assumptions: the bound does not control for a general proper, closed, extended-valued convex . Indeed, may lie arbitrarily close to while satisfy , so a suboptimality guarantee for the produced iterate would be false without additional regularity such as Lipschitz continuity or smoothness. The point is the exact target of the approximate subproblem solved at iteration , and the two sequences remain linked by .
Second, these bounds hold only for , so they describe progress until the trajectory enters the -tube. Except under strong convexity (Corollary 4.8), we have no a priori bound on , so the rates cannot in general be converted into the number of iterations needed to reach .
We next bound the suboptimality of the computed iterates after they enter the target neighborhood, in terms of the behavior of near the set of minimizers. For , define the tube gap
the worst-case suboptimality of over the closed -tube . It is nondecreasing, with . The value may be , 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, .
(i) The terminal iterate of Algorithm 2 satisfies .
(ii) Consider the untruncated iteration, and assume that, for every , there exists such that . Then , and hence , for every .
Proof. (i) By definition of , the iterate satisfies , so and by (49). Truncation freezes the sequence, so the same bound holds for every with . (ii) Suppose . Then contains a minimizer, so , and the exact broximal point lies in . Hence , and the hypothesis holds again at . By induction, for all , and by (49).
Numerical illustration
We illustrate the convergence behavior of Algorithm 2 on a simple quadratic objective in ,
starting from with radius .
To evaluate the theoretical guarantees, we consider an adversarial approximation operator that, within the -ball centered at , selects the point maximizing the distance to the optimum:
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 , together with the distance to the optimum at each iteration. Exact BPM reaches after 16 steps. For , Inexact BPM reaches the -tube, as guaranteed by Corollary 4.8, since the quadratic objective is strongly convex with . The hitting times are , , and for , , and , well below the corresponding bounds , , and of Corollary 4.8. For , the condition of Theorem 3.4 also holds, since for , and that theorem gives . Convergence slows as approaches , in line with the bounds, which degrade as the inner radius tends to zero. For , Assumption 4.1 fails. With , the trajectory is first pushed outward and then stalls; with , the adversary pushes it outward indefinitely.
Figure 2. Robustness of Inexact BPM under adversarial perturbations. Exact BPM and Inexact BPM with radius on from , using an adversarial operator that maximizes the distance to the optimum within . (a) Trajectories. (b) Distance to the optimum against the iteration count (log scale); black-edged markers indicate the hitting time . For every tested , the iterates reach the -tube although the adversary pushes them outward. The runs with 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 -tube (Theorems 3.2 and 3.4). Under the weaker assumption that the errors are uniformly bounded by a constant below the ball radius (), 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 -tube is reached, not complexity bounds for reaching -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 satisfying and , let be the unique broximal point (cf. Remark 2.3). Then, for every minimizer , we have:
Proof. We adapt the argument of Gruntkowska et al. [2025, Theorem D.1]. Since is lower semicontinuous and is compact, the minimum is attained; it is finite because and . An interior solution would be a local minimizer of and, by convexity, a global minimizer, contradicting . 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 is unique and satisfies .
Fix . Since , convexity implies
Optimality of therefore gives . Expanding, dividing by , and letting yields . Hence
Proof of Lemma 3.1
Lemma 3.1. Let be the sequence generated by Algorithm 2. Suppose Assumption 2.1 holds and for every . The distances to the set of minimizers satisfy the following relations:
If , we have the recursive upper bound:
If , the algorithm truncates the update step , and thus:
Proof. Assume first that , and let
By the one-step contraction property (Lemma 2.4), we have
for every minimizer . Let be the projection of onto , so that . Substituting yields:
and therefore,
By (12), the approximate iterate satisfies . The triangle inequality now yields
Applying (53) and (12) to the right-hand side gives:
which proves part (i).
If , the algorithm sets . Thus, , establishing part (ii).
Proof of Theorem 3.2
Theorem 3.2. Let be the sequence generated by Algorithm 2 with radius , and suppose Assumption 2.1 holds. Assume further that every active subproblem is well-defined, in the sense that for all . If the error sequence is summable, meaning
then the hitting time to the -tube satisfies:
Proof. If , then and the claimed bound holds trivially.
Assume henceforth that . By definition, for all , so Lemma 3.1(i) applies at every such step:
We upper bound the square root term by , so
By Lemma 3.1(i), for every . Hence for every finite . Substituting this bound into (52) yields
For any finite integer , summing over and using
gives
Since , we obtain . If , choosing a finite integer gives a contradiction. Therefore, , and taking establishes the claimed bound.
Proof of Theorem 3.4
Theorem 3.4. Let be the sequence generated by Algorithm 2 with radius , and suppose Assumption 2.1 holds. Suppose the error sequence is uniformly bounded such that for all , and let
denote the initial worst-case progress guarantee. If the uniform error bound ensures that , that is, if , then the hitting time to the -tube satisfies:
Proof. We first verify that every active subproblem is well-defined. The condition implies . The initial ball intersects because . Suppose that the subproblem at iteration is well-defined, and let denote its exact solution. Then and , so . Thus every active subproblem is well-defined by induction. Since for all , Lemma 3.1(i) yields:
Since and the right-hand side of (60) is monotonically increasing with respect to , we can substitute the uniform error bound:
Evaluating (61) at under the assumption that yields . If and , then (61) gives . Induction therefore shows that the sequence is decreasing and that .
Substituting the upper bound into the positive square root term of (61) yields a constant minimum progress per step:
Fix any finite integer . Summing the preceding inequality from to gives
If , we could choose a finite integer , obtaining a contradiction. Hence , and taking gives the claimed bound.
Proof of Theorem 4.5
Theorem 4.5. Let be the sequence generated by Algorithm 2 and the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume and . If has bounded sublevel sets (Definition 4.4), then for any iteration , the suboptimality gap satisfies:
where is the inner radius defined in (26), and is given by (44).
Proof. Since is bounded, . For every active iteration , combining (34) and (32) gives
Hence, by induction, for every . Therefore, for every , and consequently
We now have two independent upper bounds on the distance to the set of minimizers for all : the global bound , and the accumulated error bound derived in the proof of Theorem 4.2. Substituting the accumulated error bound into the one-step contraction (35) and chaining over steps recovers the sublinear rate from Theorem 4.2:
Alternatively, substituting the global bound into (35) and chaining over steps yields the linear rate:
Since both upper bounds hold, the suboptimality gap is bounded by their minimum, completing the proof.
Proof of Theorem 4.7
Theorem 4.7. Let be the sequence generated by Algorithm 2 and the auxiliary sequence defined in (27), and suppose Assumptions 2.1 and 4.1 hold. Assume and . If is -strongly convex, then for any iteration , the suboptimality gap satisfies:
where , and is the inner radius defined in (26).
Proof. Because is -strongly convex, its set of minimizers is a singleton, , and its sublevel sets are bounded. Specifically, for any , strong convexity implies:
Thus, the largest distance to within the initial sublevel set is bounded by . Substituting this 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, implies , and hence:
where is a minimizer of over . Since , , and , all hypotheses of Gruntkowska et al. [2025] Theorem D.2 are satisfied. Consequently, there exists such that
Applying -strong convexity with this subgradient yields
For every active iteration ,
Hence, . By Gruntkowska et al. [ [8] Theorem D.1(ii), this boundary condition forces . Combining these inequalities, we obtain a guaranteed absolute function value decrease of:
Applying this recursively over steps gives . 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 to the -tube is bounded by:
Proof. By Theorem 4.7, for every finite integer ,
Consequently,
for every finite .
If , we could choose a finite integer , which would contradict the preceding inequality. Hence, . Taking now gives
which proves the claim.
References
- [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]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]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]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]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]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
- [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
- [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
- [10]O. Güler. New proximal point algorithms for convex minimization. SIAM Journal on Optimization, 2(4):649–664, 1992.DOI
- [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.
- [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.
- [14]Y. Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29:519–531, 1984.
- [15]Y. Nesterov. Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer, Cham, 2nd edition, 2018.DOI
- [16]N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127–239, 2014.DOI
- [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
- [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
- [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
- [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
- [21]R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877–898, 1976.DOI
- [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.
- [24]N. Z. Shor. Minimization Methods for Non-Differentiable Functions, volume 3 of Springer Series in Computational Mathematics. Springer, Berlin, Heidelberg, 1985.DOI
- [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
