acceptodds
Under review as a conference paper at ICLR 2027

An Implementable Halpern-Accelerated Proximal Point Method with Sharp Residual Rates

Abstract

Halpern-accelerated proximal point methods (HPPMs) improve the fixed-point residual rate from to under exact resolvent evaluations. In practice, however, exact resolvent evaluations can be computationally expensive. To address this issue, we study an implementable HPPM with a relaxation parameter and resolvent errors satisfying , aiming to determine the error decay required to preserve the accelerated residual rate. Specifically, for every fixed , we establish the sharp worst-case residual rate for and for . Thus, is the exact threshold for preserving the accelerated residual rate, removing the extraneous \(\log k\) factor in existing upper bounds. By contrast, at the boundary , we obtain the sharp rates for , for , and for . Matching lower-bound constructions establish the sharpness of all these rates. These results precisely characterize the resolvent accuracy required to retain Halpern acceleration under approximate resolvent evaluations.

Primary area:
optimization
Keywords:
Halpern iteration, proximal point method, fixed-point residual, sharp convergence rate

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_AXtiOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies Halpern-accelerated proximal point iterations when each resolvent evaluation has an error that decreases over time. It gives worst-case residual rates for different error decay speeds and relaxation parameters, with matching lower bounds. For a fixed relaxation parameter below 2, the paper shows that errors of order k^(-3/2) are enough to retain the O(1/k) residual rate. At the boundary value 2, a faster error decrease is needed. It also applies these results to three existing optimization settings.

Critical strengths
  1. The paper gives a precise answer to a clear theoretical question. The difference between relaxation parameters below 2 and at 2 is especially useful.
  2. The matching lower bounds support the claimed thresholds. The applications show where the new bounds improve earlier results.
Critical weaknesses
  1. The claim of being “implementable” needs more support. The error assumption measures distance from the exact resolvent, which an inner solver generally cannot compute directly. The paper does not give a concrete stopping test or show the total inner work needed to achieve the sharper outer rate.
Questions for authors
  1. What computable stopping test for an inner solver would guarantee the required resolvent error in the three applications? How much inner work would it require?
  2. The constants in the bound grow as the relaxation parameter approaches 2. How would you choose this parameter in practice?
  3. In Proposition 4.1, the operator may depend on the target iteration. Can one fixed problem and error sequence attain the lower-bound order for all sufficiently large iterations?
4 comments
AuthorsOpenReview ↗

Response to Reviewer AXti Point by Point - Part 1

Response to the Critical Weakness.

We thank the reviewer for highlighting the importance of implementable stopping criteria and the associated inner computational costs. Our inexactness model follows Rockafellar's classical framework for inexact proximal-point methods [1]. Following the reviewer's suggestion, we have added computable stopping criteria and inner-complexity estimates for the three applications in Appendices A.6–A.8.

We have also added a basis-pursuit experiment in Section 6, comparing PPM, HPPM, iPPM, and iHPPM using the same accelerated proximal-gradient (APG) inner solver. Figure 1 reports the absolute KKT residual against outer iterations and CPU time. The results show that iHPPM requires nearly the same number of outer iterations as HPPM while achieving an approximately 5.3×5.3\times speedup in total CPU time to reach a KKT residual of 10−410^{-4}.

AuthorsOpenReview ↗

Response to Reviewer AXti Point by Point - Part 2

Response to Question 1.

We thank the reviewer for this question. Below, we explain how the prescribed inexactness conditions can be enforced through computable stopping criteria or explicit inner-iteration budgets, and quantify the corresponding computational costs for the three applications in Section 5.

ALM. Computable stopping criteria for ALM subproblems are available for various structured optimization problems. As an illustration, consider the Lasso problem

\frac12\\|Bx-b\\|^2+\lambda\\|x\\|_1,$$ where $B\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, and $\lambda>0$. Following [2, Section 3.2], the dual ALM subproblem reduces to minimizing a $1$-strongly convex function $\psi_k$ with computable gradient $$\nabla\psi_k(y) =y+b-BS_{\sigma\lambda}(x^k-\sigma B^\top y),$$ where $\sigma>0$ is the penalty parameter, $x^k$ is the current ALM multiplier, and $S_{\sigma\lambda}$ denotes componentwise soft-thresholding. By strong convexity, $$\psi_k(y)-\inf\psi_k \le\frac12\\|\nabla\psi_k(y)\\|^2.$$ Consequently, the computable stopping criterion $$\\|\nabla\psi_k(\widetilde y)\\| \le\frac{c}{\sqrt{\sigma}(k+1)^{3/2}}$$ ensures the required ALM objective-gap accuracy, provided the eliminated variable is recovered exactly. Moreover, $\nabla\psi_k$ is Lipschitz continuous with $L_\psi=1+\sigma\\|B\\|^2$. Under uniformly bounded initial subproblem errors, accelerated gradient requires $\mathcal O(\sqrt{L_\psi}\log(k+2))$ inner iterations at outer iteration $k$. Related computable stopping criteria are available for convex composite conic programming [3, Proposition 7] and convex quadratic semidefinite programming [4, Section 2.2]. Further details are provided in Appendix A.6. **DRO.** The projected-gradient mapping in our DRO application requires evaluating $\Pi_C(v^k)$, where $v^k=w^k-\alpha F(w^k)$, $\alpha>0$, $F$ is the saddle-point operator, and $C$ is the feasible set. For any feasible approximation $\widetilde z^k\in C$ and $n^k\in N_C(\widetilde z^k)$, the computable optimality-residual condition $$\\|\widetilde z^k-v^k+n^k\\| \le\frac{\alpha c}{(k+1)^{3/2}}$$ guarantees the prescribed projection accuracy. For a concrete example, consider $C=X\times Q$, where $$X=\\{x\in\mathbb R^n: \mathbf1^\top x=1,\\ l\le x\le u\\}, \qquad Q=\\{q\in\mathbb R^m: \\|q-\widehat q\\|\le R_Q\\},$$ with nonempty $X$, finite bounds $l,u$, and $R_Q>0$, as in [5]. Writing $v^k=(v_x^k,v_q^k)$, define $$[x_k(t)]_i =\min\\{u_i,\max\\{l_i,(v_x^k)_i-t\\}\\}, \qquad h_k(t)=\mathbf1^\top x_k(t)-1.$$ By the projection characterization in [6], the optimal multiplier is a root of $h_k$. Given a bisection bracket $[a,b]$ satisfying $h_k(a)>0>h_k(b)$, set $$\theta=\frac{-h_k(b)}{h_k(a)-h_k(b)}, \qquad \widetilde x^k=\theta x_k(a)+(1-\theta)x_k(b).$$ Then $\widetilde x^k\in X$, and componentwise monotonicity of $x_k(t)$ gives the certified projection-error bound $$\\|\widetilde x^k-\Pi_X(v_x^k)\\| \le\\|x_k(a)-x_k(b)\\|.$$ If a root of $h_k$ is encountered, we return the corresponding exact projection instead. Since $\Pi_Q$ is explicit, the computable criterion $$\\|x_k(a)-x_k(b)\\| \le\frac{\alpha c}{(k+1)^{3/2}}$$ guarantees the required approximation accuracy. For uniformly bounded initial bracket widths, this requires $\mathcal O(\log(k+2))$ bisection iterations and $\mathcal O(n\log(k+2)+m)$ arithmetic operations per outer iteration, excluding evaluations of $F$. Further details are provided in Appendix A.7.
AuthorsOpenReview ↗

Response to Reviewer AXti Point by Point - Part 3

Finite-sum monotone inclusions. Consider F=1n∑i=1nFiF=\frac1n\sum_{i=1}^n F_i and A=η(F+G)A=\eta(F+G), where η>0\eta>0 and GG is maximally monotone. Under the assumptions of [7], including monotonicity of FF, n≥2n\ge2, and the mean-square Lipschitz condition

\\|F_i(u)-F_i(v)\\|^2 \le L^2\\|u-v\\|^2,$$ we use VR-FoRB [7, Algorithm 3] to approximate $J_A(w^k)$, initializing all inner states at $w^k$ and using the prescribed algorithmic parameters and uniform component sampling, with fresh randomness conditional on the outer iteration history. We assume access to exact resolvent evaluations for $\eta G$ at the prescribed inner stepsize. By [7, Theorem 4.6], the explicit inner-iteration budget $$M_k=\left\lceil 14\max\\{n,\sqrt n(\eta L+1)\\} \log\bigl(\sqrt6(k+2)\bigr) \right\rceil$$ guarantees $$\mathbb E_k\\|e_{k+1}\\|^2 \le\frac{\\|R(w^k)\\|^2}{(k+2)^2},$$ where $\mathbb E_k$ denotes conditional expectation, $e_{k+1}$ is the resolvent approximation error, and $R=I-J_A$. Thus, an explicit budget of $$\mathcal O\\!\left( \max\\{n,\sqrt n(\eta L+1)\\}\log(k+2) \right)$$ inner iterations yields a certified conditional mean-square error bound without evaluating the full resolvent $J_A(w^k)$ or its residual. For the outer Halpern iteration with $\rho=1$, Corollary 5.3 shows that this criterion guarantees $$\mathbb E\\|R(w^k)\\|=\mathcal O((k+1)^{-1}).$$ Further details are provided in Appendix A.8. **Response to Question 2.** For $p=3/2$, Theorem 3.5 establishes $$\\|R(w^k)\\| \le \frac{2\\|w^0-w^\star\\|}{\rho k+2} + \frac{6c}{k+1} \left(1+\sqrt{\frac{2\rho}{2-\rho}}\right), \quad 0<\rho<2.$$ Increasing $\rho$ reduces the exact-iteration contribution but amplifies the worst-case effect of computational errors, with the corresponding coefficient diverging as $\rho\uparrow2$. This reveals a trade-off between the benefit of larger relaxation and sensitivity to inner inaccuracies. Our numerical results in Table 2 illustrate this trade-off. For $c=10$, increasing $\rho$ from $1$ to $1.9$ reduces the median CPU time from $6.109$ to $2.844$ seconds, whereas for $c=1000$, the same change increases it from $2.250$ to $10.641$ seconds. These observations suggest that larger relaxation parameters can be beneficial when the inner subproblems are solved accurately, while more moderate relaxation may be preferable when larger errors are allowed. We therefore recommend selecting $\rho$ jointly with the inner accuracy parameter $c$, based on the total computational cost required to reach the desired accuracy. For the reported instance, the ranges $c\in[10,1000]$ and $\rho\in[1,1.9]$ provide useful starting points for parameter tuning, although suitable ranges may vary with problem scaling and inner-solver costs. Among the tested combinations, the lowest median CPU time is attained at $(\rho,c)=(1,1000)$, highlighting the potential computational benefit of allowing relatively inaccurate inner solves.
AuthorsOpenReview ↗

Response to Reviewer AXti Point by Point - Part 4

Response to Question 3.

Yes. Following the reviewer's suggestion, we have strengthened the lower-bound result by establishing a fixed-instance construction in Proposition A.1 (Appendix A.4).

For any fixed 0<ρ<20<\rho<2, 0<p<3/20<p<3/2, and c>0c>0, there exist a maximally monotone operator AA on an infinite-dimensional real Hilbert space, an initial point w0w^0, and an error sequence ejj≥1\\{e_j\\}_{j\ge1} satisfying ∣ej∣≤cj−p\\|e_j\\|\le cj^{-p} such that

\ge \xi_{\rho,p}cK^{1/2-p}$$ for every sufficiently large $K$, where $\xi_{\rho,p}>0$ depends only on $\rho$ and $p$. Unlike the two-dimensional construction in Proposition 4.1, which allows the instance to depend on the target iteration $K$, the new construction attains the matching lower-bound order on a single instance independent of $K$. **References.** [1] R. T. Rockafellar. Monotone operators and the proximal point algorithm. *SIAM Journal on Control and Optimization*, 14(5):877–898, 1976. doi:10.1137/0314056. [2] X. Li, D. Sun, and K.-C. Toh. A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. *SIAM Journal on Optimization*, 28(1):433–458, 2018. doi:10.1137/16M1097572. [3] Y. Cui, D. Sun, and K.-C. Toh. On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming. *Mathematical Programming*, 178:381–415, 2019. doi:10.1007/s10107-018-1300-6. [4] X. Li, D. Sun, and K.-C. Toh. QSDPNAL: A two-phase augmented Lagrangian method for convex quadratic semidefinite programming. *Mathematical Programming Computation*, 10(4):703–743, 2018. doi:10.1007/s12532-018-0137-6. [5] L. Liang, Z. Xu, K.-C. Toh, and J.-J. Zhu. An inexact Halpern iteration with application to distributionally robust optimization. *Journal of Optimization Theory and Applications*, 206, Article 58, 2025. doi:10.1007/s10957-025-02744-y. [6] R. Cominetti, W. F. Mascarenhas, and P. J. S. Silva. A Newton's method for the continuous quadratic knapsack problem. *Mathematical Programming Computation*, 6:151–169, 2014. doi:10.1007/s12532-014-0066-y. [7] X. Cai, A. Alacaoglu, and J. Diakonikolas. Variance reduced Halpern iteration for finite-sum monotone inclusions. In *Proceedings of the Twelfth International Conference on Learning Representations (ICLR)*, 2024.
Reviewer_gP75OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies a Halpern-accelerated proximal point method with inexact resolvent evaluations. Assuming that the resolvent errors decay as ∥ek∥=O(k−p)\|e^k\| = O(k^{-p}), the authors establish sharp worst-case residual rates for a fixed relaxation parameter ρ∈(0,2]\rho \in (0,2]. For 0<ρ<20 < \rho < 2, the accelerated O(1/k)O(1/k) rate is preserved when p≥3/2p \ge 3/2, including the critical case p=3/2p=3/2 where previous analyses incurred a logarithmic factor. For ρ=2\rho=2, preserving the O(1/k)O(1/k) rate requires p>2p>2, with a logarithmic loss at p=2p=2. The authors also provide matching lower-bound constructions and discuss applications to augmented Lagrangian methods, distributionally robust optimization, and finite-sum monotone inclusions.

Critical strengths
  • This reviewer finds the paper clear and well organized.
  • The motivation is reasonable, and the main convergence results appear to be sound.
  • The matching lower-bound constructions make the characterization of the residual rates more complete.
Critical weaknesses

This reviewer did not identify any critical weaknesses in the paper. However, this reviewer has some concerns about whether the contributions are sufficiently substantial, as discussed in the Questions section.

Questions for authors

To the best of this reviewer's understanding, while the framing of this paper is interesting, the core analysis comes from the Lyapunov function defined in (11), which seems to have a somewhat standard form used to analyze Halpern methods. Could the authors clarify what the main technical bottlenecks were and what novel strategies were required to overcome them compared to previous work?

While Lemma 3.3 and Proposition 3.4 seem new, to the best of this reviewer's understanding, their main role is to handle the critical case p=3/2p=3/2, rather than to overcome a broader challenge arising from the framework considered in this paper. This reviewer would be happy to be corrected if this interpretation overlooks an important aspect of the contribution.

6 comments
AuthorsOpenReview ↗

Response to Reviewer gP75 Point by Point - Part 1

Response to the Critical Weakness.

We thank the reviewer for recognizing the clarity and soundness of our results. We emphasize that our contributions go beyond improving existing residual upper bounds. Our main contributions are summarized as follows.

  • Sharp residual-rate characterization. We establish worst-case sharp residual rates for every p>0p>0 and fixed ρ∈(0,2]\rho\in(0,2], identifying the exact accuracy thresholds for preserving the accelerated O(1/k)\mathcal O(1/k) rate: p≥3/2p\ge 3/2 for 0<ρ<20<\rho<2 and p>2p>2 for ρ=2\rho=2. This reveals a fundamental distinction between the two relaxation regimes.

  • New analytical techniques. We develop a square-tail residual discrepancy estimate (Lemma 3.3) and a refined Lyapunov comparison starting from an intermediate iterate (Proposition 3.4). These techniques not only eliminate the logarithmic loss in standard Lyapunov analysis at the critical exponent p=3/2p=3/2, establishing the sharp O(1/k)\mathcal O(1/k) rate, but also remove the diverging factor (3−2p)−1/2(3-2p)^{-1/2} in Proposition 3.2 as p↑3/2p\uparrow 3/2. Consequently, for each fixed ρ∈(0,2)\rho\in(0,2), our analysis yields a unified residual bound for all p>0p>0, with an error coefficient independent of pp.

  • Matching lower bounds. We establish matching lower bounds proving the worst-case sharpness of our residual rates. In particular, Proposition A.1 constructs a fixed infinite-dimensional instance attaining the lower bound for all sufficiently large kk, while Proposition 4.2 establishes sharpness at ρ=2\rho=2. These results show that the accuracy thresholds are intrinsic rather than artifacts of the analysis.

  • Extension to degenerate preconditioning. We extend our analysis to iHPPMs with possibly singular positive-semidefinite preconditioners M\mathcal M, providing a theoretical framework for implementable Halpern-accelerated operator-splitting methods. Under the assumptions of the preconditioned ADMM framework in Appendix A.9, our results establish an O(1/k)\mathcal O(1/k) KKT residual rate for implementable Halpern-accelerated preconditioned ADMM [1] under errors ∣ej∣≤cj−3/2\\|e_j\\|\le cj^{-3/2} for fixed 0<ρ<20<\rho<2. This extension is particularly relevant to recent GPU-accelerated solvers incorporating Halpern acceleration, including HPR-LP [2] for linear programming and HPR-QP [3] and PDHCG-II [4] for convex quadratic programming. Our analysis provides a theoretical basis for studying inexact variants of their underlying Halpern iterations under suitable preconditioning and error assumptions. Theorem A.2 establishes residual rates in the M\mathcal M-seminorm, Proposition A.4 proves their worst-case sharpness for preconditioners of rank at least two, and Corollary A.5 provides ambient-norm guarantees under an additional Lipschitz assumption (Section 5.4 and Appendix A.9).

AuthorsOpenReview ↗

Response to Reviewer gP75 Point by Point - Part 2

Response to Question 1.

We agree that the Lyapunov function follows an established structure in Halpern analyses. Our main technical contribution lies in developing refined estimates that overcome the limitations of standard Lyapunov analysis. In particular, directly telescoping the Lyapunov inequality from the initial iterate introduces the term QK=∑j=1Kj(j+1)∣ej∣2Q_K=\sum_{j=1}^K j(j+1)\\|e_j\\|^2 in Proposition 3.2. Under ∣ej∣≤cj−3/2\\|e_j\\|\le cj^{-3/2}, we have

\left(\frac1j+\frac1{j^2}\right) =\mathcal O\bigl(c^2\log(K+1)\bigr).$$ Substituting this estimate into Proposition 3.2 yields only an $\mathcal O(\sqrt{\log K}/K)$ residual bound. A similar logarithmic loss occurs in Liang et al. [5, Theorem 3.1] under errors of order $k^{-3/2}$, while the stronger condition $\mathcal O(k^{-3/2}/\log k)$ suffices to recover the $\mathcal O(1/K)$ rate. The key challenge is therefore to eliminate this loss without imposing stronger error-decay requirements. For $0<\rho<2$, we overcome this difficulty by combining a new square-tail residual discrepancy estimate with a localized Lyapunov argument. Exploiting the strict averagedness of the relaxed resolvent, Lemma 3.3 establishes $$\sum_{j=m}^{\infty} \\|R(w^j)-R(u^j)\\|^2 \leq \frac{9\rho c^2}{2(2-\rho)(m+1)},$$ where $w^j$ and $u^j$ denote the inexact and exact Halpern iterates starting from the same initial point, respectively. Taking $m=\lfloor K/2\rfloor$, we obtain an index $s\in\\{m,\ldots,K-1\\}$ such that $$\\|R(w^s)-R(u^s)\\|^2 \leq \frac{9\rho c^2} {2(2-\rho)(m+1)(K-m)} =\mathcal O(K^{-2}).$$ Proposition 3.4 then compares the inexact Lyapunov function with that of the exact trajectory at $s$. This comparison gives an upper bound on the inexact Lyapunov function $\Phi_s$ that is independent of the terminal iteration $K$. We then telescope the Lyapunov inequality only from $s$ to $K$. Crucially, $$\sum_{j=s+1}^{K}\frac1j \leq \frac{K-s}{s+1}\leq 1,$$ while the mixed error terms are controlled using the square-tail estimate and the Cauchy–Schwarz inequality. This eliminates the logarithmic loss and establishes the sharp $\mathcal O(1/K)$ residual rate at $p=3/2$ (Appendix A.2). The intermediate index $s$ is used only in the analysis and does not require modifying the algorithm. Moreover, the resulting estimate extends to all $p>0$, eliminating the diverging factor $(3-2p)^{-1/2}$ in Proposition 3.2 as $p\uparrow 3/2$. Thus, our techniques yield a unified residual bound across polynomial error-decay schedules, rather than addressing only the critical case. **A different approach for $\rho=2$.** At the boundary $\rho=2$, the strict averagedness descent term vanishes, so the square-tail argument is no longer applicable. Instead, direct comparison with the exact Halpern trajectory using nonexpansiveness yields $$\\|R(w^K)\\| \leq \frac{\\|w^0-w^\star\\| +2\sum_{j=1}^K j\\|e_j\\|}{K+1}$$ in Theorem 3.6. Proposition 4.2 constructs a fixed one-dimensional instance attaining this bound with equality at every even iteration. Consequently, among polynomial error-decay schedules, preserving the worst-case $\mathcal O(1/K)$ residual rate requires $p>2$, and the logarithmic factor at $p=2$ is unavoidable. This establishes an intrinsic distinction between the regimes $0<\rho<2$ and $\rho=2$.
AuthorsOpenReview ↗

Response to Reviewer gP75 Point by Point - Part 3

Response to Question 2.

We agree that resolving the critical case p=3/2p=3/2 is a key motivation for Lemma 3.3 and Proposition 3.4. However, the significance of these results extends beyond removing the logarithmic factor at this particular exponent, as explained below.

Identifying the sharp accuracy threshold. For each fixed 0<ρ<20<\rho<2, Proposition 3.4 establishes that ∣ej∣≤cj−3/2\\|e_j\\|\le cj^{-3/2} suffices to preserve the accelerated O(1/K)\mathcal O(1/K) residual rate. Conversely, for every 0<p<3/20<p<3/2, Proposition 4.1 establishes a matching Ω(K1/2−p)\Omega(K^{1/2-p}) lower bound, ruling out a uniform O(1/K)\mathcal O(1/K) guarantee. Thus, p=3/2p=3/2 is the exact polynomial error-decay threshold for preserving the accelerated rate in the worst case. Resolving the critical case is therefore essential for establishing the optimal accuracy requirement, rather than merely improving an existing upper bound. Proposition A.1 further strengthens this conclusion by constructing a fixed infinite-dimensional instance attaining the lower-bound order for all sufficiently large KK.

A unified residual estimate for all p>0p>0. More importantly, the refined analysis in Proposition 3.4 also yields a unified residual estimate across all polynomial error-decay schedules, rather than being restricted to p=3/2p=3/2. To see this, for 0<p<3/20<p<3/2 and any fixed KK, define cK:=c(K+1)3/2−pc_K:=c(K+1)^{3/2-p}. Since wKw^K depends only on the first KK errors, we may set ej=0e_j=0 for j>Kj>K without changing wKw^K. The resulting error sequence satisfies

\qquad 1\le j\le K,$$ and the same bound holds trivially for $j>K$. Applying Proposition 3.4 with $c_K$ gives $$\\|R(w^K)\\| \le \frac{2\\|w^0-w^\star\\|}{\rho K+2} + 6\left(1+\sqrt{\frac{2\rho}{2-\rho}}\right) c(K+1)^{1/2-p}.$$ For $p\ge3/2$, Proposition 3.4 applies directly. Together, these arguments yield Theorem 3.5, which provides a unified residual bound for every $p>0$, with an error coefficient independent of $p$ for each fixed $0<\rho<2$. In particular, this removes the diverging factor $(3-2p)^{-1/2}$ in Proposition 3.2 as $p\uparrow3/2$, demonstrating that the refined analysis also improves the estimates away from the critical exponent. Thus, Lemma 3.3 and Proposition 3.4 not only resolve the critical case needed to identify the sharp accuracy threshold, but also provide the analytical foundation for a unified characterization of residual convergence under general polynomially decaying computational errors. **References.** [1] D. Sun, Y. Yuan, G. Zhang, and X. Zhao. Accelerating preconditioned ADMM via degenerate proximal point mappings. *SIAM Journal on Optimization*, 35(2):1165–1193, 2025. doi:10.1137/24M1650053. [2] K. Chen, D. Sun, Y. Yuan, G. Zhang, and X. Zhao. HPR-LP: An implementation of an HPR method for solving linear programming. *Mathematical Programming Computation*, 18:183–210, 2026. doi:10.1007/s12532-025-00292-0. [3] K. Chen, D. Sun, Y. Yuan, G. Zhang, and X. Zhao. HPR-QP: A dual Halpern Peaceman–Rachford method for solving large-scale convex composite quadratic programming. arXiv preprint arXiv:2507.02470, 2025. [4] H. Li, Y. Huang, H. Liu, D. Ge, and Y. Ye. PDHCG-II: An enhanced version of PDHCG for large-scale convex QP. arXiv preprint arXiv:2602.23967, 2026. [5] L. Liang, Z. Xu, K.-C. Toh, and J.-J. Zhu. An inexact Halpern iteration with application to distributionally robust optimization. *Journal of Optimization Theory and Applications*, 206, Article 58, 2025. doi:10.1007/s10957-025-02744-y.
Reviewer_RBTaOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Halpern-accelerated proximal-point methods can require an iterative inner solve at each outer iteration. This paper studies how accurately those inner problems must be solved to retain the acceleration. It gives sharper worst-case guarantees showing when approximate inner solves preserve the same rate of fixed-point residual reduction as exact solves, measured over outer iterations. It also constructs examples showing that the guarantees are sharp and presents theoretical applications. From my perspective, the possibility of avoiding unnecessarily accurate inner solves is compelling for practical inverse problems, where these subproblems can be expensive.

My background is primarily in practical uses of gradient proximal optimization. I have limited experience with this specific theory and its literature.

Critical strengths
  1. Solving proximal subproblems accurately can be expensive. The paper shows when less accurate inner solves can preserve the accelerated convergence rate over outer iterations. This is compelling to me because it could help avoid unnecessary work in practical inverse problems.

  2. The paper gives accuracy requirements that preserve acceleration, along with worst-case examples showing why weaker requirements cannot guarantee the same rate for this algorithm. This helps clarify how much approximation the method can tolerate.

I lean toward weak acceptance because the stated contribution addresses a practical concern I find important: allowing less accurate inner solves while retaining accelerated outer convergence to potentially reduce computational work. My confidence is limited by my familiarity with this specific theory. A worked example (eg: basis pursuit) explaining the implementation choices and their practical tradeoffs would help me better assess its practical value.

Critical weaknesses

The main limitation for me is the gap between the abstract inner-error schedule and a worked implementation. It is difficult to judge the practical benefit without seeing how the tolerance scale cc is chosen, how the required accuracy is certified, and how tightening inner tolerances changes total work and achieved accuracy. From a practical standpoint, I would also like to understand how reducing the fixed-point residual relates to improving the objective value or the estimated solution. To the best of my understanding, a smaller residual does not necessarily mean a smaller objective error or a solution closer to an optimizer. A worked example showing these quantities together, and explaining how to choose a residual tolerance that delivers useful application accuracy, would make the practical implications clearer. A concrete example building on these results would make the contribution substantially easier to evaluate from an applied perspective.

Questions for authors

Two questions would help me understand the practical value of the results:

  1. How would you choose the error constant cc in equation (4) for a practical application? It would help to see how to decide when each inner solve is accurate enough without knowing its exact answer, and what changes if cc is made larger or smaller. How would you handle tolerances that become too small to achieve reliably in floating-point arithmetic? In other words, on a high level, if someone were to implement this algorithm, what defaults would you choose for their implementation and why?

  2. How can a user tell whether a small fixed-point residual means the answer is accurate enough? For one example, could you show the residual together with objective error and, if a unique solution is known, distance to that solution? I would also appreciate guidance on how conditioning affects this connection.

Suggestion for practical validation:

A small experiment measuring these quantities against runtime or total computation, including the inner solves, would be helpful. If possible, could you compare with ordinary proximal-point iteration without acceleration and show the behavior under different schedules for inner-solve accuracy? This would help visualize how the accuracy schedule affects convergence and whether less accurate inner solves save work overall.

4 comments
AuthorsOpenReview ↗

Response to Reviewer RBTa Point by Point - Part 1

Response to the Critical Weakness.

We thank the reviewer for emphasizing the importance of connecting the theoretical error requirements with practical implementation and solution accuracy. Our inexactness model follows Rockafellar's classical framework for inexact proximal-point methods [1]. Following the reviewer's suggestion, we have added a basis-pursuit experiment in Section 6 of the revised paper, comparing PPM, HPPM, iPPM, and iHPPM using the same accelerated proximal-gradient (APG) inner solver. Figure 1 reports the absolute KKT residual against outer iterations and CPU time. The results show that iHPPM closely tracks HPPM in outer-iteration convergence while achieving an approximately 5.3×5.3\times speedup in total CPU time over HPPM in reaching a KKT residual of 10−410^{-4}.

Appendix A.10 provides implementation details and a computable subgradient-based stopping criterion that guarantees the prescribed resolvent accuracy without evaluating the exact resolvent. Furthermore, Table 2 investigates how the error constant cc and relaxation parameter ρ\rho jointly affect computational efficiency. Our response to Question 1 discusses practical parameter selection and floating-point limitations. Regarding solution accuracy, we clarify in our response to Question 2 how additional error-bound and local Lipschitz assumptions connect the fixed-point residual to objective error and distance to the solution set.

AuthorsOpenReview ↗

Response to Reviewer RBTa Point by Point - Part 2

  • Response to Question 1.

    Joint choice of cc and ρ\rho. We recommend selecting cc and ρ\rho jointly, with p=3/2p=3/2. Our sharp residual-rate analysis identifies p=3/2p=3/2 as the critical polynomial decay exponent for retaining the O(1/k)\mathcal O(1/k) residual rate when 0<ρ<20<\rho<2. A larger cc permits less accurate and potentially cheaper inner solves but increases the error contribution in the outer residual bound. Increasing ρ\rho reduces the exact-iteration contribution in our residual bound but amplifies the worst-case effect of computational errors through the factor 1+2ρ/(2−ρ)1+\sqrt{2\rho/(2-\rho)}. Consequently, larger values of ρ\rho may be beneficial when cc is small, whereas moderate values may be preferable when cc is large.

    Table 2 illustrates this dependence. At c=10c=10, increasing ρ\rho from 11 to 1.91.9 reduces the median CPU time from 6.1096.109 to 2.8442.844 seconds, whereas at c=1000c=1000, the same change increases it from 2.2502.250 to 10.64110.641 seconds. For practical implementation, we therefore recommend tuning cc over a logarithmic grid and jointly comparing several values of ρ\rho based on the total CPU time required to reach the desired accuracy. For our basis-pursuit instance, Table 2 suggests c∈[10,1000]c\in[10,1000] and ρ∈[1,1.9]\rho\in[1,1.9] as initial joint search ranges, with the lowest reported median CPU time among the tested combinations attained at (c,ρ)=(1000,1)(c,\rho)=(1000,1). These ranges are instance-dependent and should be adjusted according to problem scaling and computational requirements.

    Certifying inner accuracy without the exact solution. For the basis-pursuit experiment, given wk=(xk,yk)w^k=(x^k,y^k), the APG inner solver approximately minimizes

    f_k(x)=\frac12\\|x-x^k\\|^2+ \frac12\\|Ax-b+y^k\\|^2,$$ and sets $\widetilde y^{k+1}=y^k+A\widetilde x^{k+1}-b$. The gradient of the smooth part is $$\nabla f_k(x)=x-x^k+A^\top(Ax-b+y^k).$$ A minimum-norm subgradient $g_k(x)\in\partial\phi_k(x)$ can be computed componentwise as $$[g_k(x)]_i= \begin{cases} [\nabla f_k(x)]_i+\operatorname{sign}(x_i), & x_i\ne0,\\\\ \mathcal S_1([\nabla f_k(x)]_i), & x_i=0, \end{cases}$$ where $\mathcal S_1(t)=\operatorname{sign}(t) \max\\{|t|-1,0\\}$. With $L_{\mathrm{BP}}=1+\\|A\\|^2$, we employ the computable stopping criterion $$\boxed{ \sqrt{L_{\mathrm{BP}}}\\, \\|g_k(\widetilde x^{k+1})\\| \le c(k+1)^{-p}. }$$ To verify that this criterion guarantees the prescribed resolvent accuracy, let $\bar x^{k+1}$ denote the exact minimizer of $\phi_k$. By the $1$-strong convexity of $\phi_k$ and the dual update, we obtain $$\begin{aligned} \\|e_{k+1}\\| &\le \sqrt{L_{\mathrm{BP}}}\\, \\|\widetilde x^{k+1}-\bar x^{k+1}\\|\\\\ &\le \sqrt{L_{\mathrm{BP}}}\\, \\|g_k(\widetilde x^{k+1})\\|\\\\ &\le c(k+1)^{-p}. \end{aligned}$$ Thus, the stopping criterion guarantees the error requirement using only computable quantities, without evaluating the exact resolvent or the subproblem minimum. Further implementation details are provided in Appendix A.10, while Appendices A.6–A.8 establish corresponding computable stopping criteria or inner iteration budgets for the applications in Section 5. **Floating-point limitations.** Although the prescribed inner tolerance $\varepsilon_{k+1}=c(k+1)^{-p}$ decreases to zero, practical implementations terminate once a prescribed outer accuracy, typically $10^{-4}$ or $10^{-6}$, is reached. In our basis-pursuit experiment, with $c=10$ and $p=3/2$, the prescribed inner tolerance at iteration $25000$ is approximately $2.53\times10^{-6}$; Section 6 reports an iHPPM absolute KKT residual of approximately $10^{-4}$ at this iteration. This tolerance remains well above double-precision machine epsilon, although the attainable inner accuracy also depends on problem scaling and conditioning. For substantially longer computations, numerical precision may eventually limit the attainable inner accuracy. One practical safeguard is to impose a tolerance floor $\max\\{c(k+1)^{-p},\varepsilon_{\min}\\}$, where $\varepsilon_{\min}$ is chosen according to problem scaling and numerical precision (e.g., $\varepsilon_{\min}=10^{-12}$ for a suitably scaled problem). Another possible strategy is to periodically restart the Halpern iteration, updating its anchor and resetting the local iteration counter for both the Halpern weights and the inner tolerance schedule. Restart strategies have been explored in HPR-LP [2] and theoretically analyzed for Halpern PDHG by Lu and Yang [3]. Extending these analyses to our inexact setting is left for future work.
AuthorsOpenReview ↗

Response to Reviewer RBTa Point by Point - Part 3

  • Response to Question 2.

    The primary focus of this paper is monotone inclusion problems, which provide a unified framework encompassing optimization, games, and variational inequalities. The fixed-point residual is therefore a natural measure of convergence. For constrained convex optimization, the fixed-point residual is closely related to the KKT residual, which measures both feasibility and stationarity, whereas objective error alone does not capture feasibility. KKT residuals are widely used in the literature and optimization software as convergence criteria for problems such as basis pursuit, Lasso, and distributionally robust optimization (DRO). Accordingly, in our basis-pursuit experiment, Figure 1 reports the absolute KKT residual against both outer iterations and CPU time.

    Moreover, under an appropriate error-bound condition, the fixed-point residual controls the distance to the solution set. Let R=I−JAR=I-J_A and Sol=A−1(0)\mathrm{Sol}=A^{-1}(0). Suppose that, for some κ>0\kappa>0 and a neighborhood UU of a solution,

    \leq \kappa\operatorname{dist}(0,A(z)), \qquad z\in U.$$ Such local error bounds hold for polyhedral monotone operators [4], which arise in optimization problems such as basis pursuit and Lasso. For any $w$ with $z=J_A(w)\in U$, the resolvent identity $w-z\in A(z)$ yields $$\begin{aligned} \operatorname{dist}(w,\mathrm{Sol}) &\leq \\|w-z\\|+\operatorname{dist}(z,\mathrm{Sol})\\\\ &\leq (1+\kappa)\\|R(w)\\|. \end{aligned}$$ This bound also provides an objective accuracy guarantee when the primal objective $f$ is locally Lipschitz with constant $L_f$ near a primal–dual solution $w^\star=(x^\star,y^\star)$. In finite dimensions, this holds if $f$ is convex and finite on an open neighborhood of $x^\star$ (see Theorem 10.4 of [5]). For $w=(x,y)$ sufficiently close to $w^\star$, let $\bar w=(\bar x,\bar y)$ be its projection onto $\mathrm{Sol}$. Since $f(\bar x)=f^\star$, $$|f(x)-f^\star| \leq L_f\\|x-\bar x\\| \leq L_f(1+\kappa)\\|R(w)\\|.$$ Consequently, locally, the residual tolerance $\\|R(w)\\|\leq\delta/[L_f(1+\kappa)]$ guarantees the objective accuracy $|f(x)-f^\star|\leq\delta$.

References.

[1] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877–898, 1976. doi:10.1137/0314056.

[2] K. Chen, D. Sun, Y. Yuan, G. Zhang, and X. Zhao. HPR-LP: An implementation of an HPR method for solving linear programming. Mathematical Programming Computation, 18:183–210, 2026. doi:10.1007/s12532-025-00292-0.

[3] H. Lu and J. Yang. Restarted Halpern PDHG for linear programming. arXiv preprint arXiv:2407.16144, 2024.

[4] S. M. Robinson. Some continuity properties of polyhedral multifunctions. In H. König, B. Korte, and K. Ritter (eds.), Mathematical Programming at Oberwolfach, volume 14 of Mathematical Programming Studies, pages 206–214. Springer, Berlin, Heidelberg, 1981. doi:10.1007/BFb0120929.

[5] R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, 1997.

Thank you again for your constructive comments and suggestions. We have provided detailed responses to your concerns and revised the manuscript accordingly. We would greatly appreciate it if you could review our responses and consider the clarifications and revisions in your overall assessment. Thank you very much for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.