- 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
- The paper gives a precise answer to a clear theoretical question. The difference between relaxation parameters below 2 and at 2 is especially useful.
- The matching lower bounds support the claimed thresholds. The applications show where the new bounds improve earlier results.
Critical weaknesses
- 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
- 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?
- The constants in the bound grow as the relaxation parameter approaches 2. How would you choose this parameter in practice?
- 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
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.Response to Reviewer AXti Point by Point - Part 3
Finite-sum monotone inclusions. Consider and , where and is maximally monotone. Under the assumptions of [7], including monotonicity of , , 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.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 , , and , there exist a maximally monotone operator on an infinite-dimensional real Hilbert space, an initial point , and an error sequence satisfying 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.
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× speedup in total CPU time to reach a KKT residual of 10−4.