- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Randomized Subspace Nesterov Accelerated Gradient (RS-NAG) methods for smooth convex and strongly convex optimization. By combining randomized projected gradients with Nesterov-type acceleration under matrix smoothness assumptions, the authors establish accelerated convergence guarantees with improved directional-derivative oracle complexity in favorable curvature regimes. The paper further derives explicit complexity bounds for Haar, coordinate, and Gaussian sketches and evaluates the methods on synthetic quadratic problems and real-world logistic-regression datasets.
Critical strengths
The paper provides a theoretically meaningful refinement of accelerated randomized optimization by distinguishing gradient-estimator variance from its interaction with objective curvature. This yields improved oracle-complexity bounds over generic compressed-gradient analyses when the curvature-dependent factor is sufficiently small.
The analysis derives explicit complexity factors for different sketch distributions and relates their performance to the objective's spectral structure. The theoretical characterization, supported by experiments on quadratic and logistic-regression problems, provides useful insights into when particular sketching strategies are advantageous.
Critical weaknesses
-
The proposed three-sequence acceleration framework closely resembles Accelerated Compressed Gradient Descent (ACGD) by Li et al. (2020). In particular, both RS-NAG-C and RS-NAG-SC appear to be recoverable from the general ACGD update framework through appropriate parameter choices and the projected-gradient compressor (C(g)=PP^\top g). Therefore, the claimed novelty of the three-sequence acceleration mechanism is not sufficiently justified.
-
The main technical contribution appears to be a sharper convergence analysis that exploits matrix smoothness and the interaction between the sketch distribution and objective curvature, allowing a less conservative step size and improved oracle-complexity bounds. While this is a meaningful theoretical refinement, its distinction from extending the existing ACGD analysis remains unclear. The authors should explicitly establish the relationship to ACGD and clarify which aspects of the proposed method are fundamentally new. Furthermore, an experimental comparison against ACGD using identical sketch operators would help isolate the benefits of the matrix-aware analysis from those of the existing acceleration framework.
-
The evaluation exclusively uses directional-derivative oracle counts, assuming a full gradient costs oracle calls while an -dimensional projected gradient costs . However, this may not reflect actual computational costs. For the paper's logistic-regression problems, both a full-gradient evaluation and a single dense directional-derivative evaluation require operations. Consequently, the substantial oracle-complexity improvements might not translate into practical efficiency. Wall-clock time, FLOPs, and peak memory comparisons would substantially strengthen the results.
-
The paper primarily compares against standard GD, Nesterov acceleration, RS-GD, and uniform coordinate sampling. Several relevant accelerated approaches are missing from the empirical evaluation: Accelerated compressed-gradient methods, especially ACGD (Li et al., 2020) / Nonuniform accelerated coordinate descent (Allen-Zhu et al., 2016). These comparisons are important for determining whether the improvements come from the proposed algorithm or simply from adopting a more favorable curvature-aware step size.
-
The four synthetic quadratic experiments use and an effective rank of , potentially creating favorable conditions for curvature-aware randomized subspace methods. Although the paper also evaluates twelve logistic-regression datasets, it does not establish whether the improvements generalize to more diverse optimization problems. Experiments across different effective ranks and condition numbers would better characterize when the method is advantageous. An actual memory-constrained or distributed optimization experiment would also support its motivation.
Questions for authors
-
How does the proposed RS-NAG framework differ algorithmically from ACGD (Li et al., 2020), given that both RS-NAG-C and RS-NAG-SC appear to be recoverable through appropriate parameter choices and the projected-gradient compressor ? Could the authors clarify the novelty beyond the sharper matrix-smoothness-based convergence analysis and provide a comparison with ACGD under identical sketch operators to isolate the benefits of the proposed approach?
-
Since directional-derivative oracle complexity may not reflect actual computational cost, could the authors report wall-clock time, FLOPs, and peak memory usage to substantiate the claimed efficiency improvements?
-
How does the method perform across different effective ranks and condition numbers, beyond the favorable low-rank quadratic settings? Could the authors also demonstrate its effectiveness on more complex objectives or practical memory-constrained or distributed optimization tasks?
2 comments
Response to Reviewer hvUE (2/2)
W3 & Q2. Oracle complexity and practical costs
Revision to the manuscript. Section 6.2 now clarifies implementation and the communication-cost interpretation; Appendix B adds Li and Richtárik (2021) and Deng et al. (2025) alongside Li et al. (2020); and Section 6.2 adds an experiment combining measured computation and modeled communication time (Table 4; Appendix G.7).
Since the logistic-regression gradient can be readily computed in closed form, we form the full gradient and then project it in our experiments. As explained in the Introduction and Section 2.1, projecting before communication in distributed optimization reduces the communicated gradient scalars from to . Thus, these experiments remain meaningful as optimization-performance comparisons in terms of gradient-communication cost. As already noted in Footnote 1 of Section 2.1, gradient-compression studies use accounting like our oracle measure. The revised manuscript further notes that Li and Richtárik (2021) and Deng et al. (2025), alongside Li et al. (2020), use similar bit accounting to evaluate experiments. Thus, the communication-cost interpretation of our oracle-complexity measure is grounded in existing gradient-compression research.
We use communicated scalars as an experimental metric because, unlike elapsed communication time, this count does not depend on a particular implementation or environment. Nevertheless, it alone does not account for actual elapsed time, including sketch generation, projection, bandwidth, and latency. To complement the oracle-complexity experiments, the additional experiment considers the same six logistic-regression datasets. We measured the timed update-loop GPU computation, including sketch generation, full-gradient formation, projection, and the update. Computation time was measured; communication was modeled rather than physically executed. The experimental details are given in Appendix G.7; the implementation does not assume computational savings from forward-mode AD. Table 4 shows that RS-NAG required more compute-only time than NAG, consistent with the iteration-complexity trade-off. However, under the communication model, RS-NAG was faster on all six datasets at Mbps and below. In particular, as bandwidth decreased and communication accounted for a larger share of the modeled total time, the empirically preferred choice shifted to . This trend is consistent with the conclusion of Proposition 5.2 concerning the oracle-complexity measure.
W4. Experimental comparisons with accelerated baselines
For ACGD with the same sketch operators and its additional experiment, see W1, W2 & Q1 above; for nonuniform accelerated coordinate descent (Allen-Zhu et al., 2016) and its additional experiment, see our response to Reviewer 4nM9, W2 & Q2.
W5 & Q3. Effective rank, condition number, and practical settings
Revision to the manuscript. We have added the condition-number table for all twelve datasets to Appendix G.9 (Table 6) and the effective-rank experiment to Appendix G.8 (Figure 7), with a pointer to the latter from Section 6.1.
In the strongly convex setting, both full-gradient NAG and RS-NAG share the same dependence in oracle complexity, so condition numbers do not affect their theoretical relative comparison and were omitted from the submitted manuscript. In response to your comment, Table 6 now reports that the twelve logistic-regression datasets cover a wide range of condition numbers, from approximately to . The experiments in Section 6.2 and Appendix G.4 show advantages across these datasets, which have different effective ranks and condition numbers. The small effective ranks observed on these real-world datasets also support the method's practical relevance.
The original quadratic examples fixed and varied , primarily to compare Haar and Gaussian sketches with Coordinate sketches. To complement them, we added experiments on simple diagonal quadratic objectives with , fixing and the condition number. The case coincides with the strongly convex diagonal example in the original experiments. The experimental details, including the problem construction, are given in Appendix G.8. Figure 7 shows that Haar RS-NAG achieves smaller objective gaps at effective ranks and , whereas the ordering reverses at . The stronger advantage at smaller effective ranks is broadly consistent with the theoretical dependence on effective rank. Regarding the theoretical bound, Proposition 5.2 gives Even at , this factor equals that of full-gradient NAG, so the theoretical oracle-complexity factor does not become worse.
For the additional experiment on distributed-optimization, please see W3 & Q2 above.
Response to Reviewer hvUE (1/2)
We thank the reviewer for recognizing the theoretical value of separating the gradient estimator's second moment from its interaction with curvature, and of the resulting comparisons between sketch distributions. Changes to the manuscript are shown in red in the revised PDF.
W1, W2 & Q1. Differences from ACGD, novelty, and experimental comparison
Revision to the manuscript. In response to your comments, we have clarified the contribution statement in the Introduction and expanded Appendix A.3 of the revised manuscript to explain the algorithmic relationship to ACGD and the differences in convergence analysis. We have also added an experimental comparison with ACGD to Section 6.1 (Figure 2).
We thank the reviewer for pointing out the connection to ACGD. We did not intend to claim that the three-sequence acceleration mechanism itself was new. As discussed in lines 89–92 and Appendix A.3 of the submitted manuscript, our focus is on obtaining sharper accelerated convergence guarantees by exploiting the interaction between sketch moments and matrix smoothness. In lines 109–111 of the submitted manuscript, we described our contribution as a "novel three-sequence coupling tailored to the interaction between sketch moments and matrix smoothness." Our intended emphasis was on "tailored to the interaction between sketch moments and matrix smoothness," rather than on the novelty of the three-sequence structure itself. We have clarified this wording in the Introduction of the revised manuscript.
As already shown in Appendix A.3 of the submitted manuscript, specializing the existing ACGD guarantees to the projected-gradient compressor yields the oracle factor rω≥d (Proposition 2.3), which cannot establish an improvement over full-gradient NAG. To overcome this limitation, we introduce matrix smoothness and exploit its interaction with sketch moments, replacing rω by rωℓ, which can be smaller than d. For rank-one Haar sketches, the improvement in this factor over full-gradient NAG is (d+2)/(reff+2), of order d in favorable low-effective-rank regimes.
At the level of update rules, the coefficient choices specified in Theorems 2 and 3 of Li et al. (2020) do not, in general, reproduce RS-NAG-C and RS-NAG-SC, respectively. However, our algorithms can be recovered from their general ACGD framework through a careful choice of coefficients; the correspondence is given in Appendix A.3. We emphasize that designing these coefficients is itself nontrivial. More importantly, recovering the updates does not make their existing convergence analysis directly applicable: their Lemma 1 requires p≥2(1+Lηk)(1+ωLi). Under the parameter correspondence given in Appendix A.3, this condition requires ℓ≥ω, excluding the important regime ℓ<ω in which our oracle-complexity improvement is obtained. Thus, adjusting the coefficients within the existing ACGD analysis does not yield our guarantees. In contrast, in addition to the matrix-dependent descent estimate, Theorems 3.3 and 4.3 separately control the sketch second moment through ω and the curvature-dependent moment through ℓ, and combine these two moment bounds to establish accelerated convergence analyses for the convex and strongly convex settings, respectively. Specifically, we choose parameters compatible with these distinct moment bounds and prove the corresponding Lyapunov inequalities, obtaining accelerated convergence guarantees with an iteration-complexity factor of ωℓ. Moreover, establishing when these improvements can actually be obtained requires further mathematical analysis. In Section 5, we evaluate the interaction with curvature for Haar, coordinate, and Gaussian sketches and derive explicit values of ℓ. Proposition 5.2 further establishes the optimal sketch dimension and relationships among the complexity factors of these distributions. Together, these results characterize both the conditions under which improvements are possible and their magnitude, including the order-d improvement noted above.
Thus, our contribution is the refinement of the three-sequence framework, both algorithmically and analytically, to obtain accelerated guarantees sharp enough to establish oracle-complexity improvements over full-gradient NAG, which are not obtained from the existing scalar-smoothness or generic-compressor analyses discussed in Appendix A.3.
In addition, we conducted an additional experiment comparing RS-NAG with ACGD (Li et al., 2020). The experimental details are given in Section 6.1 of the revised manuscript. Figure 2 shows that RS-NAG achieves a smaller objective gap on all four quadratic problems, thus also demonstrating experimentally the benefit of exploiting the interaction between matrix smoothness and sketch moments.