- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposed a random shuffling algorithm for solving the composite DC problem. The algorithm only evaluates the proximal oracle once per epoch, and it allows the proximal parameter to be constant. They establish finite-time complexity guarantees for PNRR, and they obtained improved convergence rate for KL problems.
Critical strengths
-
The paper proposed a random shuffling algorithm that only requires proximal oracle evaluation once per epoch.
-
The paper presented a theoretical analysis of the proposed algorithm, and the proof is correct.
Critical weaknesses
-
The algorithm relies on a strong proximal oracle in line 8 of Algorithm 1. Since is generally nonconvex nonsmooth, solving this proximal subproblem could take a lot of computational time. Usually, we obtain such proximal oracle for convex nonsmooth problem, and the solution can be exact if is simple enough. But for nonconvex nonsmooth problem, it does not easy to solve this problem easily.
-
In Section 3, the authors assume that the auxiliary function is KL instead of the original objective function or . Such an assumption on the auxiliary function is quite unusual.
-
In Assumption 3.1, the authors assume the bounded iterates instead of deriving the property.
-
The writing of this paper can be further polished:
- The presentation of Table 1 is messy. You may consider moving the references from footnotes into the table.
- The font of Figures 1 and 2 are really small.
Questions for authors
See the weakness.
2 comments
- Response to "In Section 3, the authors assume that the auxiliary function H is KL instead of the original objective function or . Such an assumption on the auxiliary function is quite unusual."
Re: We thank the reviewer for this comment. Imposing the KL property on an auxiliary function is a well-established approach in nonconvex optimization to analyze convergence; see, e.g., [3, 4].
The auxiliary function in this paper is naturally derived from the difference structure of the objective through Fenchel conjugacy. Specifically, since is convex, we have , with equality whenever , as follows from (3) and (4). Moreover, the approximate descent and subgradient estimates in our analysis are established for . Therefore, imposing the KL property on is natural for establishing full-sequence convergence.
This assumption is also verifiable for a broad class of structured problems. For instance, when , , and are semialgebraic, the conjugate and hence are semialgebraic, which guarantees the KL property. Moreover, the auxiliary functions in our numerical experiments are locally subanalytic, since the losses are either polynomial or real analytic and the nonsmooth regularization terms have semialgebraic structure. Thus, the required KL property can also be verified for these models.
Furthermore, Lemma 2.4 establishes that, under the stated conditions, accumulation points of the lifted iterates correspond to critical points of the original problem. When , the KL property of is equivalent to that of . We have clarified the construction of in Remark 2.2 and discussed the applicability of its KL assumption in Section 3.
References
[3] iPiano: Inertial Proximal Algorithm for Non-Convex Optimization. Ochs et al. (2014), SIAM Journal on Imaging Sciences, 7(2):1388–1419.
[4] Inertial Proximal Alternating Minimization for Nonconvex and Nonsmooth Problems. Zhang and He (2017), Journal of Inequalities and Applications, 2017:232.
- Response to "In Assumption 3.1, the authors assume the bounded iterates instead of deriving the property.“
Re: We thank the reviewer for this comment. The boundedness assumption is standard in KL-based full-sequence convergence analysis, as also adopted in related works such as Li et al. (2023) and Qiu et al. (2025). More importantly, for PNRR, the boundedness of the iterates can be guaranteed under a natural additional condition on the objective function.
Specifically, Proposition C.4(i), which does not rely on Assumption 3.1(i), already provides a uniform upper bound on . Consequently, boundedness of the iterates follows whenever has bounded sublevel sets (e.g., if is coercive). Thus, Assumption 3.1(i) is automatically satisfied under this sufficient condition. We have added this observation in Remark 3.2 of the revised manuscript.
- Response to "The writing of this paper can be further polished.“
Re: We thank the reviewer for this helpful suggestion. We have revised Table 1 by moving the detailed assumptions and references to Appendix B.2, thereby improving its readability. We have also enlarged the font sizes in the figures to improve readability. In addition, we have further polished the writing and presentation throughout the manuscript.
Re: We thank the reviewer for this important observation. We agree that computing a global solution of the proximal subproblem can be challenging when h1 is nonconvex and nonsmooth. This is a common challenge in nonconvex proximal optimization, as discussed in [1, 2]. Our theoretical analysis relies on exact proximal updates and does not guarantee their efficient computation for arbitrary nonconvex h1.
Nevertheless, for structured nonconvex regularizers with globally computable proximal operators, PNRR can be efficiently implemented. In particular, PNRR requires only one proximal evaluation per epoch, whereas norm-PRR and proxSGD require n, making the reduction in proximal evaluations particularly beneficial when these computations are costly.
To further demonstrate the practical applicability of PNRR to nonconvex h1, we have added experiments involving nonconvex regularization. We consider logistic regression with nonconvex ℓ1/2 regularization (Section 4.3), whose proximal subproblem admits a global solution through coordinatewise thresholding, as detailed in Appendix E.3. The time-to-stationarity results (Figure 6 in the revised manuscript) show that PNRR reaches ϵ=10−3 on heart-scale in approximately 0.1 seconds, compared with 0.6 seconds for the full-gradient method. Moreover, the following table (Table 4 in the revised manuscript) shows that PNRR achieves the shortest objective-target reaching times across all three datasets.
Wall-clock time (in seconds) to first reach 10−3 relative to Pmin in logistic regression with ℓ21 regularization.
These results demonstrate that, although computing exact proximal updates can be challenging for general nonconvex nonsmooth regularizers, PNRR maintains favorable computational efficiency on structured problems.
References
[1] Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity. Yao and Kwok (2018), Journal of Machine Learning Research, 18(179):1–52.
[2] Efficient Inexact Proximal Gradient Algorithm for Nonconvex Problems. Yao et al. (2017), IJCAI, pp. 3308–3314.