acceptodds
Under review as a conference paper at ICLR 2027

One-Prox Random Reshuffling for Nonsmooth Nonconvex Optimization: Complexity and KL Last-Iterate Rates

Abstract

Random reshuffling (RR) has been widely applied to large-scale finite-sum optimization. However, existing proximal RR methods for such problems with nonsmooth structure typically either require multiple proximal evaluations per epoch or couple the proximal parameter with the reshuffling stepsize. In this paper, we propose a proximal algorithm for nonsmooth nonconvex random reshuffling (PNRR) that simultaneously addresses these two issues. PNRR requires only one proximal evaluation per epoch while allowing the proximal parameter to be chosen independently of the reshuffling stepsize and kept constant. We establish finite-time complexity guarantees for PNRR, including an incremental first-order oracle complexity of and a proximal oracle complexity of . Compared with several representative methods, the complexity advantage of PNRR becomes more pronounced in the high-accuracy regime. Under the Kurdyka–\Lojasiewicz (KL) framework, we further prove that the whole sequence generated by PNRR converges to a critical point. Moreover, under polynomially decaying stepsizes, we obtain explicit polynomial convergence rates for the function values, stationarity measure, and iterate error, while exponentially decaying stepsizes yield geometric convergence of all three quantities when the KL exponent is below . Numerical experiments on logistic regression and nonconvex binary classification demonstrate the competitive and stable performance of PNRR.

Primary area:
optimization
Keywords:
proximal random reshuffling, full-sequence convergence, Kurdyka--{\L}ojasiewicz analysis, nonsmooth optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_t6jqOpenReview ↗
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
  1. The paper proposed a random shuffling algorithm that only requires proximal oracle evaluation once per epoch.

  2. The paper presented a theoretical analysis of the proposed algorithm, and the proof is correct.

Critical weaknesses
  1. The algorithm relies on a strong proximal oracle in line 8 of Algorithm 1. Since h1h_1 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 h1h_1 is simple enough. But for nonconvex nonsmooth problem, it does not easy to solve this problem easily.

  2. In Section 3, the authors assume that the auxiliary function HH is KL instead of the original objective function P(x)P(x) or fi(x)f_i(x). Such an assumption on the auxiliary function is quite unusual.

  3. In Assumption 3.1, the authors assume the bounded iterates instead of deriving the property.

  4. 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
  1. Response to “The algorithm relies on a strong proximal oracle in line 8 of Algorithm 1. Since h1 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 h1h_1 is simple enough. But for nonconvex nonsmooth problem, it does not easy to solve this problem easily.”

Re: We thank the reviewer for this important observation. We agree that computing a global solution of the proximal subproblem can be challenging when h1h_1 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 h1h_1.

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 nn, making the reduction in proximal evaluations particularly beneficial when these computations are costly.

To further demonstrate the practical applicability of PNRR to nonconvex h1h_1, we have added experiments involving nonconvex regularization. We consider logistic regression with nonconvex ℓ1/2\ell_{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\epsilon=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−310^{-3} relative to PminP_{min} in logistic regression with ℓ12\ell_{\frac12} regularization.

Algorithmspliceheart_scalefourclass_scale
proxSGD8.9690.5025.702
Full Gradient0.5360.6700.112
PNRR0.2580.0990.096

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.

  1. Response to "In Section 3, the authors assume that the auxiliary function H is KL instead of the original objective function PP or fif_i. 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 HH in this paper is naturally derived from the difference structure of the objective through Fenchel conjugacy. Specifically, since h2h_2 is convex, we have P(x)=inf⁡wH(x,w)P(x)=\inf_w H(x,w), with equality P(x)=H(x,w)P(x)=H(x,w) whenever w∈∂h2(x)w\in\partial h_2(x), as follows from (3) and (4). Moreover, the approximate descent and subgradient estimates in our analysis are established for HH. Therefore, imposing the KL property on HH is natural for establishing full-sequence convergence.

This assumption is also verifiable for a broad class of structured problems. For instance, when ff, h1h_1, and h2h_2 are semialgebraic, the conjugate h2∗h_2^* and hence HH 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 h2=0h_2=0, the KL property of HH is equivalent to that of PP. We have clarified the construction of HH 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.

  1. 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 P(xt)P(x^t). Consequently, boundedness of the iterates follows whenever PP has bounded sublevel sets (e.g., if PP 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.

  1. 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.

Reviewer_BK29OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes PNRR for nonsmooth nonconvex optimization problems with a difference structure h1−h2h_1-h_2. The method performs one proximal evaluation per epoch while decoupling the proximal parameter from the reshuffling gradient stepsize. Theoretically, an IFO complexity of O(nϵ−2)O(n\epsilon^{-2}) and a proximal oracle complexity of O(ϵ−2)O(\epsilon^{-2}) are established under a lifted stationarity measure. The authors further prove full-sequence convergence and last-iterate convergence rates under the KL framework. Preliminary numerical experiments illustrate the performance of PNRR.

Critical strengths

The proposed new algorithm PNRR decouples the proximal parameter from the reshuffling gradient stepsize, which is simple but useful. The convergence analysis of the PNRR is well-established and comprehensive.

Critical weaknesses

The numerical experiments are insufficient.

  1. Less proximal steps is one of the claimed advantages of this paper. But the models have simple proximal operators in the numerical experiments. If proximal steps are not time consuming, does PNRR perform better than other methods?
  2. In the comparison, only "epoch" is considered as the measure of x-axis, and PNRR performs similarly to norm-PRR in several cases. Wall-clock comparisons would better support the claimed computational advantages.
Questions for authors
  1. The theory does not require convexity on h1h_1. However, when h1h_1 is nonconvex, the proximal subproblem is also nonconvex, how to obtain the global solution of the subproblem in practice?
  2. How to understand the following sentence in the abstract:"the complexity advantage of PNRR becomes more pronounced in the high-accuracy regime"?
  3. In Table 1, why the complexity for PNRR is written in O(⋅)O(\cdot) form, rather than in an explicit form as for the other comparison algorithms?
  4. In experiments "Binary classification with nonconvex regularization", the optimization problem is nonconvex, how to compute the global minimum PminP_{min} in the definition of the relative error?
3 comments
AuthorsOpenReview ↗

Response to the Critical Weaknesses

  1. Response to “Less proximal steps is one of the claimed advantages of this paper. But the models have simple proximal operators in the numerical experiments. If proximal steps are not time consuming, does PNRR perform better than other methods?”

Re: We thank the reviewer for this insightful question. We have conducted additional experiments to evaluate PNRR with inexpensive proximal evaluations and structured nonconvex proximal operators.

For inexpensive proximal evaluations, we have supplemented our original experiments with wall-clock time and time-to-stationarity comparisons. Table 1 in this comment (Table 2 in the revised manuscript) shows that PNRR outperforms norm-PRR in objective-target reaching time across all three datasets. Table 2 in this comment (Table 3 in the revised manuscript) further shows that PNRR reaches the prescribed objective targets within 12 seconds on all three datasets, whereas neither SGD-DC nor the full-gradient method reaches these targets within the 120-second budget, as indicated by "not reach" in the table. Moreover, the time-to-stationarity results (Figures 4 and 5 in the revised manuscript) show that PNRR generally reaches prescribed stationarity tolerances in less computational time. In addition, for nonconvex binary classification, PNRR reduces the objective value substantially faster than the full-gradient method across all three datasets, while SGD-DC exhibits larger fluctuations (Figure 2 in the revised manuscript). These results demonstrate that PNRR remains computationally competitive even when proximal evaluations are not time consuming.

Table 1: Wall-clock time (in seconds) to first reach 10−310^{-3} relative to PminP_{min} in logistic regression with convex regularization.

Algorithma1aa9asplice
proxRR0.74939.78010.431
proxSGD1.39872.42118.585
norm-PRR3.34042.8760.140
PNRR1.72826.3870.102

Table 2: Wall-clock time (in seconds) to first reach 10−310^{-3} relative to PminP_{min} in binary classification with nonconvex regularization.

AlgorithmMNISTGISETTECINA
SGD-DCnot reachnot reachnot reach
Full Gradientnot reachnot reachnot reach
PNRR10.9779.83211.422

For structured nonconvex regularizers, we have added logistic regression experiments with ℓ1/2\ell_{1/2} regularization, whose proximal subproblem admits a globally optimal solution through coordinatewise thresholding. Table 3 in this comment (Table 4 in the revised manuscript) shows that PNRR achieves the shortest objective value reaching times across all three datasets. Furthermore, the results in Figures 3 and 6 in the revised manuscript show that PNRR achieves rapid objective reduction and favorable stationarity residuals. For example, on heart-scale, PNRR reaches the stationarity tolerance ϵ=10−3\epsilon=10^{-3} in approximately 0.1 seconds, compared with 0.6 seconds for the full-gradient method. These results further demonstrate the practical effectiveness of PNRR for structured nonconvex problems.

Table 3: Wall-clock time (in seconds) to first reach 10−310^{-3} relative to PminP_{min} in logistic regression with ℓ12\ell_{\frac12} regularization.

Algorithmspliceheart_scalefourclass_scale
proxSGD8.9690.5025.702
Full Gradient0.5360.6700.112
PNRR0.2580.0990.096
  1. Response to “In the comparison, only ‘epoch’ is considered as the measure of x-axis, and PNRR performs similarly to norm-PRR in several cases. Wall-clock comparisons would better support the claimed computational advantages."

Re: We thank the reviewer for this valuable suggestion. We have added wall-clock time comparisons to provide a more comprehensive evaluation of computational efficiency.

We agree that PNRR and norm-PRR exhibit comparable convergence behavior in terms of objective value versus epoch in several cases. However, epoch count alone does not fully reflect computational cost, since PNRR requires only one proximal evaluation per epoch, whereas norm-PRR requires nn. As shown in Table 1 in this comment, PNRR outperforms norm-PRR in wall-clock time across all three datasets and achieves the shortest target-reaching times on a9a and splice.

Furthermore, the time-to-stationarity results (Figure 4 in the revised manuscript) show that PNRR reaches ϵ=10−3\epsilon=10^{-3} on a1a in approximately 5.2 seconds, compared with 10 seconds for norm-PRR, and reaches ϵ=10−2\epsilon=10^{-2} on a9a in approximately 12 seconds, compared with 22 seconds. On splice, PNRR reaches ϵ=10−3\epsilon=10^{-3}, whereas norm-PRR fails to reach this tolerance within the 60-second budget. These results provide further quantitative evidence of PNRR's computational advantages beyond epoch-based comparisons.

AuthorsOpenReview ↗

Response to the Questions For Authors

  1. Response to “The theory does not require convexity on h1h_1. However, when h1h_1 is nonconvex, the proximal subproblem is also nonconvex, how to obtain the global solution of the subproblem in practice?”

Re: We thank the reviewer for this important question. We agree that allowing nonconvex h1h_1 in the theoretical analysis does not imply that its proximal subproblem can always be solved efficiently. As discussed in [1] and [2], computing proximal operators for general nonconvex regularizers can be challenging. Our convergence analysis considers exact proximal updates. Therefore, in practice, we focus on structured nonconvex regularizers whose proximal subproblems admit computable global solutions.

To further demonstrate the practical applicability of PNRR to nonconvex h1h_1, we have added logistic regression experiments with nonconvex ℓ1/2\ell_{1/2} regularization (Section 4.3). Although the proximal subproblem is nonconvex, it is separable and admits a global solution through a closed-form coordinatewise thresholding rule, as detailed in Appendix E.3. The time-to-stationarity results (Figure 6 in the revised manuscript) show that PNRR reaches ϵ=10−3\epsilon=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−310^{-3} relative to PminP_{min} in logistic regression with ℓ12\ell_{\frac12} regularization.

Algorithmspliceheart_scalefourclass_scale
proxSGD8.9690.5025.702
Full Gradient0.5360.6700.112
PNRR0.2580.0990.096

These results demonstrate that globally optimal proximal updates are computationally feasible for structured nonconvex regularizers, while PNRR maintains favorable computational efficiency.

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.

  1. Response to “ How to understand the following sentence in the abstract: ‘the complexity advantage of PNRR becomes more pronounced in the high-accuracy regime’?”

Re: We thank the reviewer for this question. The statement refers to the dependence of the established IFO and PO complexity upper bounds on the target stationarity tolerance ϵ\epsilon. As shown in Table 1 in the revised manuscript, PNRR achieves an ϵ−2\epsilon^{-2} dependence in both complexities. For norm-PRR, the bounds contain an additional factor max⁡(1,Lnϵ)\max(1,\frac{\sqrt{L}}{\sqrt{n}\epsilon}), leading to an ϵ−3\epsilon^{-3} dependence when ϵ\epsilon is sufficiently small for fixed nn and LL. Similarly, the bounds for proxSGD exhibit an ϵ−4\epsilon^{-4} dependence in the high-accuracy regime when the variance bound B>0B>0. Thus, the theoretical advantage of PNRR becomes more pronounced as ϵ\epsilon decreases, under the respective assumptions and for fixed problem parameters.

To further investigate this behavior in practice, we have added time-to-stationarity experiments (Figure 4-6 in the revised manuscript) to compare the computational time required to reach different stationarity tolerances. For example, on a1a at ϵ=10−3\epsilon=10^{-3}, PNRR requires approximately 5.2 seconds, compared with 10 seconds for norm-PRR. Similarly, on a9a at ϵ=10−2\epsilon=10^{-2}, PNRR requires approximately 12 seconds, compared with 22 seconds for norm-PRR. These results provide empirical evidence of PNRR's computational efficiency at the tested high-accuracy tolerances, consistent with the theoretical comparison.

AuthorsOpenReview ↗

Response to the Questions For Authors

  1. Response to "In Table 1, why the complexity for PNRR is written in O(⋅)\mathcal{O}(\cdot) form, rather than in an explicit form as for the other comparison algorithms?"

Re: We thank the reviewer for this helpful suggestion. We agree that presenting the complexity of PNRR in O(⋅)\mathcal{O}(\cdot) notation, while reporting explicit bounds for the comparison algorithms, may make the comparison less transparent and consistent.

To address this issue, we have added Corollary C.6 to the revised manuscript, which establishes explicit IFO and PO complexity bounds for PNRR when h2=0h_2=0, consistent with the setting considered in Table 1 shown in the revised manuscript. Specifically, the IFO and PO complexities are reported as nLδϵ2\frac{nL\delta}{\epsilon^2} and Lδϵ2\frac{L\delta}{\epsilon^2}, respectively, where δ\delta is explicitly defined in the corollary. We have also updated Table 1 accordingly to provide a clearer and more consistent comparison with existing methods.

  1. Response to "In experiments 'Binary classification with nonconvex regularization', the optimization problem is nonconvex, how to compute the global minimum PminP_{min} in the definition of the relative error?"

Re: We thank the reviewer for pointing this out. Since the optimization problem is nonconvex, computing its global minimum is generally difficult. In our experiments, Pmin⁡P_{\min} is defined as the minimum objective value attained across all iterates of all compared algorithms for each dataset. This provides a common reference value for all algorithms on the same dataset, allowing a consistent comparison of their relative errors without requiring knowledge of the unknown global minimum. We have revised the corresponding description in the manuscript to clarify this definition.

Reviewer_YTPnOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes PNRR for nonsmooth nonconvex finite-sum optimization. PNRR requires only one proximal evaluation per epoch and decouples the proximal parameter from the reshuffling stepsize. It achieves O(nϵ−2)O(n\epsilon^{-2}) IFO and O(ϵ−2)O(\epsilon^{-2}) PO complexity, and establishes last-iterate rates under KL assumption.

Critical strengths

The proposed PNRR requires only one proximal evaluation per epoch while decoupling the proximal parameter from the reshuffling stepsize, addressing a trade-off in existing proximal RR methods.

The paper establishes improved oracle complexity bounds in the high-accuracy regime, together with KL-based last-iterate rates for nonsmooth nonconvex problems.

Critical weaknesses

The O(nϵ−2)O(n\epsilon^{-2}) IFO complexity matches that of norm-PRR for sufficiently large nn. The overall computational advantage over the full gradient method is also less clear.

Questions for authors

How does PNRR compare with the full gradient method and other methods (e.g., proxSGD) in overall computational cost?

2 comments

Response to "The IFO complexity O(nϵ−2)O(n\epsilon^{−2}) matches that of norm-PRR for sufficiently large nn. The overall computational advantage over the full gradient method is also less clear."

Re: We thank the reviewer for this observation. We agree that, for sufficiently large nn, PNRR and norm-PRR have comparable IFO complexity. However, the overall computational cost is not determined solely by the number of gradient evaluations. Proximal evaluations can be computationally expensive, particularly for structured nonsmooth regularizers. Although PNRR and norm-PRR have comparable IFO complexity in this regime, PNRR requires only one proximal evaluation per epoch, whereas norm-PRR performs nn. Regarding the comparison with full-gradient methods, we do not claim a general advantage in oracle complexity.

To further assess practical computational efficiency, we have added wall-clock and time-to-stationarity comparisons. As shown in the following table (Table 2 in the revised manuscript), PNRR outperforms norm-PRR across all three datasets and achieves the shortest target-reaching times on a9a and splice.

Wall-clock time (in seconds) to first reach 10−310^{-3} relative to PminP_{min} in logistic regression with convex regularization.

Algorithma1aa9asplice
proxRR0.74939.78010.431
proxSGD1.39872.42118.585
norm-PRR3.34042.8760.140
PNRR1.72826.3870.102

Moreover, the time-to-stationarity results (Figures 4 and 5 in the revised manuscript) show that PNRR reaches ϵ=10−3\epsilon=10^{-3} on a1a in approximately 5 seconds, compared with 10 seconds for norm-PRR. For nonconvex binary classification, PNRR reaches ϵ=0.1\epsilon=0.1 within approximately 10 seconds on all three datasets, whereas the full-gradient method fails to reach this tolerance within the 60-second budget.

These results demonstrate the practical computational benefits of PNRR.

Response to “How does PNRR compare with the full gradient method and other methods (e.g., proxSGD) in overall computational cost?”

Re: We thank the reviewer for this question. From a theoretical perspective, PNRR achieves an IFO complexity of O(nϵ−2)O(n\epsilon^{-2}) and a PO complexity of O(ϵ−2)O(\epsilon^{-2}). Compared with proxSGD and norm-PRR, PNRR requires only one proximal evaluation per epoch instead of nn, which is particularly beneficial when proximal evaluations are expensive. Although we do not claim a universal oracle-complexity advantage over the full-gradient method, PNRR can exploit incremental gradient information during each epoch. To facilitate a clearer comparison, we have provided explicit IFO and PO complexity bounds nLδϵ2\frac{nL\delta}{\epsilon^2} and Lδϵ2\frac{L\delta}{\epsilon^2}, respectively, in Corollary C.6.

From a practical perspective, we have added wall-clock and time-to-stationarity comparisons, together with experiments involving nonconvex h1h_1. As shown in the following table (Table 3 in the revised manuscript), PNRR reaches an objective gap of 10−310^{-3} within 12 seconds on all three datasets, whereas neither SGD-DC nor the Full Gradient method reaches the same targets within the 120-second budget, as indicated by "not reach" in the table.

Wall-clock time (in seconds) to first reach 10−310^{-3} relative to PminP_{min} in binary classification with nonconvex regularization.

AlgorithmMNISTGISETTECINA
SGD-DCnot reachnot reachnot reach
Full Gradientnot reachnot reachnot reach
PNRR10.9779.83211.422

Furthermore, the following table (Table 4 in the revised manuscript) shows that PNRR achieves the shortest target-reaching times across all three datasets with nonconvex ℓ1/2\ell_{1/2} regularization, outperforming both proxSGD and the Full Gradient method.

Wall-clock time (in seconds) to first reach 10−310^{-3} relative to PminP_{min} in logistic regression with ℓ12\ell_{\frac12} regularization.

Algorithmspliceheart_scalefourclass_scale
proxSGD8.9690.5025.702
Full Gradient0.5360.6700.112
PNRR0.2580.0990.096

These results demonstrate that PNRR achieves favorable overall computational costs compared with the full-gradient method and other methods, such as proxSGD.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.