acceptodds
Under review as a conference paper at ICLR 2027

Randomized Subspace Nesterov Accelerated Gradient

Abstract

Randomized-subspace methods use only low-dimensional projected-gradient information, offering potential savings in directional-derivative queries and communication volume. Designing Nesterov-accelerated methods for general randomized subspaces that preserve this low-dimensional information structure while allowing improvements over full-gradient Nesterov acceleration in oracle complexity is technically nontrivial. We develop randomized-subspace Nesterov accelerated gradient methods for smooth convex and smooth strongly convex optimization under matrix smoothness and generic sketch moment assumptions. A key technical ingredient is a three-sequence formulation tailored to matrix smoothness. The resulting theory establishes accelerated convergence guarantees and makes explicit how matrix smoothness and the sketch distribution jointly determine the complexity. In oracle complexity, the dimension factor of full-dimensional Nesterov acceleration is replaced by the sketch-dependent factor , where is the subspace dimension and and are sketch moment parameters, identifying regimes in which randomized-subspace acceleration improves over full-dimensional Nesterov acceleration. For standard sketch families, we derive explicit complexity factors that enable direct comparison across sketch distributions.

Primary area:
optimization
Keywords:
randomized subspace methods, Nesterov acceleration, matrix smoothness, convex optimization, convergence analysis

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_hvUEOpenReview ↗
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 dd oracle calls while an rr-dimensional projected gradient costs rr. 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 O(nd)O(nd) 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 d=1000d=1000 and an effective rank of reff=2r_{\mathrm{eff}}=2, 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 C(g)=PP⊤gC(g)=PP^\top g? 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
AuthorsOpenReview ↗

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ω≥dr\omega\ge 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ωr\omega by rωℓr\sqrt{\omega\ell}, which can be smaller than dd. For rank-one Haar sketches, the improvement in this factor over full-gradient NAG is (d+2)/(reff+2)\sqrt{(d+2)/(r_{\mathrm{eff}}+2)}, of order d\sqrt 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≥(1+Lηk)(1+ωLi)2.p\ge\frac{(1+L\eta_k)(1+\omega_{\mathrm{Li}})}{2}. Under the parameter correspondence given in Appendix A.3, this condition requires ℓ≥ω\ell\ge\omega, excluding the important regime ℓ<ω\ell<\omega 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 ω\omega and the curvature-dependent moment through ℓ\ell, 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 ωℓ\sqrt{\omega\ell}. 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 ℓ\ell. 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\sqrt 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.

AuthorsOpenReview ↗

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 dd to rr. 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 1010 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 r=1r=1. 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 L/μ\sqrt{L/\mu} 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 1.80×1031.80\times10^3 to 5.06×1065.06\times10^6. 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 reff=2r_{\mathrm{eff}}=2 and varied δdiag\delta_{\mathrm{diag}}, primarily to compare Haar and Gaussian sketches with Coordinate sketches. To complement them, we added experiments on simple diagonal quadratic objectives with reff∈{2,20,200}r_{\mathrm{eff}}\in\lbrace2,20,200\rbrace, fixing d=1000d=1000 and the condition number. The case reff=2r_{\mathrm{eff}}=2 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 22 and 2020, whereas the ordering reverses at 200200. 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 QH=dreff+2d+2≤d.Q_{\mathrm H}=d\sqrt{\frac{r_{\mathrm{eff}}+2}{d+2}}\le d. Even at reff=dr_{\mathrm{eff}}=d, 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.

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

This paper studies Nesterov acceleration for randomized subspace gradient methods in convex optimization. In particular, it replaces the full gradient ∇f(xk)\nabla f(x_k) with PkPk⊤∇f(xk)P_kP_k^\top\nabla f(x_k), where Pk∈Rd×rP_k\in\mathbb R^{d\times r} is a random sketch matrix with r≪dr\ll d. The paper proposes three-sequence accelerated algorithms using only rr directional-derivative queries per iteration. Under matrix smoothness and sketch moment assumptions, the algorithms improve the oracle complexity factor from dd to rωℓr\sqrt{\omega\ell}. The paper also derives explicit bounds for Haar, coordinate, and Gaussian sketches, identifying conditions under which the proposed methods outperform standard Nesterov acceleration. Finally, the paper gives an empirical evaluation that supports its theoretical results and demonstrates the practical advantage of the proposed algorithms.

Critical strengths
  • The paper addresses an interesting optimization problem of extending Nesterov acceleration to general randomized subspace gradient methods. The theoretical contribution of this paper is solid. In particular, the three-sequence coupling allows handling the sketch second moment and the matrix smoothness interaction separately, leading to the improved complexity factor rωℓr\sqrt{\omega\ell}.

  • The experiments in this paper show the advantage of the proposed algorithm, and the empirical evaluations are generally consisent with theoretical prediction.

Critical weaknesses

I do not see some critical weaknesses of this paper, but I have a few questions below.

Questions for authors
  1. It would be good if the authors could give the comparison results with stronger baselines as well.
  2. The algorithm needs a good estimation of the lower/upper bound for some parameters. Can the authors give more discussion about this?
2 comments
AuthorsOpenReview ↗

Response to Reviewer 2qch

We thank the reviewer for the positive assessment of the theoretical contribution and for noting the consistency between the empirical results and the theoretical predictions. Changes to the manuscript are shown in red in the revised PDF.

Q1. Comparison with stronger baselines

Revision to the manuscript. We have expanded the theoretical discussions of ACGD and nonuniform accelerated coordinate descent in Appendices A.3 and A.5, respectively. We have also added experimental comparisons with ACGD in Section 6.1 (Figure 2) and with nonuniform accelerated coordinate descent in Appendix G.6 (Figure 6), with a pointer to the latter from Section 6.2.

Please see our response to Reviewer 4nM9, W2 & Q2, for the comparison with nonuniform accelerated coordinate descent, including additional experiments, and our response to Reviewer hvUE, W1, W2 & Q1, for the comparison with ACGD using the same sketch operators, including additional experiments.

Q2. Obtaining the required parameter bounds

Revision to the manuscript. We have added a discussion of the required parameter bounds to Appendix A.4 of the revised manuscript, with a pointer from Section 5.

Our method does not require the exact value of L=∥L∥L=\lVert \mathbb{L} \rVert; an upper bound Lˉ≥L\bar L\ge L is sufficient. Indeed, L~=(Lˉ/L)L\widetilde{\mathbb L}=(\bar L/L)\mathbb L satisfies Assumptions 2.1 and 2.2 with the same ℓ\ell. By Assumption 2.1, LL is also a smoothness constant in the usual scalar sense, so using an upper bound is the same as in standard NAG. Similarly, in the strongly convex setting, a positive lower bound on μ\mu is sufficient, as in standard NAG. The parameter ω\omega depends only on the sketch distribution, not on the objective, and can be computed explicitly for each sketch distribution, as shown in Table 2. In contrast, ℓ\ell depends on the interaction between the smoothness matrix and the sketch distribution. For Haar, coordinate, and Gaussian sketches, Table 2 gives explicit formulas for ℓ\ell in terms of reffr_{\mathrm{eff}} and δdiag\delta_{\mathrm{diag}}. Thus, knowing these quantities or upper bounds on them allows us to compute an admissible value of ℓ\ell explicitly. For generalized linear models, including logistic regression, linear regression, and SVM with smooth hinge loss, the smoothness matrix L\mathbb L can be constructed explicitly (Safaryan et al., 2021; Wang et al., 2022). Therefore, for such problems, ℓ\ell can be computed using L\mathbb L. Even when detailed information about L\mathbb L is unavailable, Proposition 2.3 allows the conservative choice ℓ=ω\ell=\omega, which preserves the convergence guarantee. Moreover, in the newly added Appendix A.5, we show that, for Haar and Gaussian sketches, the smoothness parameters can be set using only tr⁡(L)\operatorname{tr}(\mathbb L), without requiring LL separately, since the algorithms require LL and ℓ\ell only through their product LℓL\ell.

Thanks to the authors for the detailed response. I think my questions have been adequately addressed.

Reviewer_4nM9OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper develops randomized-subspace Nesterov methods for smooth convex and strongly convex optimization. Under matrix smoothness and sketch moment assumptions, it proves accelerated rates whose directional-derivative complexity depends on the interaction between curvature and sketch distribution. Explicit bounds for Haar, coordinate, and Gaussian sketches identify regimes that improve on full-gradient Nesterov under this oracle model. Experiments on quadratic objectives and logistic regression illustrate the predicted behavior.

Critical strengths
  1. The analysis separates sketch variance from curvature-dependent descent. The accelerated bounds depend on ωℓ\sqrt{\omega\ell} rather than ω\omega, allowing sharper guarantees when ℓ≪ω\ell\ll\omega. This yields a meaningful improvement over analyses based only on scalar smoothness and identifies when subspace acceleration reduces directional-derivative complexity relative to full-gradient Nesterov.

  2. The framework gives explicit, interpretable comparisons between sketch distributions. The Haar, coordinate, and Gaussian bounds expose the roles of effective rank and coordinate alignment. The quadratic experiments isolate these effects, while logistic-regression experiments provide additional evidence. This makes the theory useful for understanding how sketch choice affects convergence.

Critical weaknesses
  1. The methodological novelty is insufficiently established. Vaswani, Bach, and Schmidt (2019), Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron already analyze the same three-sequence stochastic acceleration structure under a strong-growth condition, which the estimator PP⊤∇fPP^\top\nabla f satisfies. The apparent advance is a sharper matrix-dependent descent estimate, rather than a new acceleration mechanism. This refinement is useful, but the paper does not explain why it constitutes a substantial methodological contribution.

  2. The oracle advantage is not established against a stronger existing baseline. Nonuniform accelerated coordinate descent has the normalized complexity factor

    =\frac{\sum_i\sqrt{\mathbf L_{ii}}}{\sqrt L} \le \sqrt{d\,r_{\mathrm{eff}}} \le Q_H<Q_G.$$ Thus, when coordinate smoothness constants are available, its known bounds have no worse parameter dependence than the reported Haar and Gaussian bounds. This method is also absent from the experiments. Comparisons with full-gradient Nesterov and uniform coordinate sampling therefore do not establish a compelling advantage over existing methods, especially without runtime or memory measurements.
Questions for authors
  1. Novelty clarification. How do Algorithms 1–2 differ from the three-sequence stochastic acceleration of Vaswani, Bach, and Schmidt (2019)? Beyond replacing the scalar-smoothness descent estimate with a matrix-dependent estimate, which new argument is required?

  2. Comparison with existing methods. Nonuniform accelerated coordinate descent satisfies

    =\frac{\sum_i\sqrt{\mathbf L_{ii}}}{\sqrt L} \le \sqrt{d\,r_{\mathrm{eff}}} \le Q_H<Q_G.$$ Under what information or computational constraints does the proposed method offer an advantage over this baseline? Can a comparison on the existing benchmarks establish that advantage?
  3. Experimental clarification. Are projected gradients evaluated directly through directional derivatives, or formed from full gradients? What are the measured runtime and memory costs relative to NAG and accelerated coordinate descent, including sketch generation and parameter estimation?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 4nM9 (1/2)

We thank the reviewer for recognizing the distinction between sketch variance and curvature-dependent descent, and the value of the comparisons between sketch distributions. Changes to the manuscript are shown in red in the revised PDF.

W1 & Q1. Relationship to Vaswani et al. (2019) and the technical contribution

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 relationships to Vaswani et al. (2019) and ACGD and the differences in convergence analysis. We have also added Vaswani et al. (2019) to the Introduction.

We thank the reviewer for pointing out this connection. 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.

In the framework of Vaswani et al. (2019), our projected-gradient estimator satisfies the strong-growth condition with ρ=ω\rho=\omega. Their Theorems 1 and 2 yield the oracle factor rω≥dr\omega\ge d (Proposition 2.3), matching the order obtained from the three-sequence accelerated compressed-gradient framework of Li et al. (2020), as already discussed in Appendix A.3 of the submitted manuscript. Thus, this direct specialization does not establish an oracle-complexity improvement over full-gradient NAG. To overcome this limitation, we introduce matrix smoothness and exploit its interaction with sketch moments, replacing rωr\omega by rωℓr\sqrt{\omega\ell}, which can be smaller than dd. For rank-one Haar sketches, the improvement in this factor over full-gradient NAG is (d+2)/(reff+2)\sqrt{(d+2)/(r_{\mathrm{eff}}+2)}, of order d\sqrt d in favorable low-effective-rank regimes.

At the level of update rules, the coefficient choices specified in their Theorems 1 and 2 do not, in general, reproduce RS-NAG-SC and RS-NAG-C, respectively. However, our algorithms can be recovered from their general 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 3 requires η≤1/(ρL)\eta\le 1/(\rho L). Substituting ρ=ω\rho=\omega and our step size η=1/(Lℓ)\eta=1/(L\ell) requires ℓ≥ω\ell\ge\omega, excluding the important regime ℓ<ω\ell<\omega in which our oracle-complexity improvement is obtained. In contrast, in addition to the matrix-dependent descent estimate, Theorems 3.3 and 4.3 separately control the sketch second moment through ω\omega and the curvature-dependent moment through ℓ\ell, 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 ωℓ\sqrt{\omega\ell}. 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 ℓ\ell. 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\sqrt 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.

For the analogous distinction from ACGD and the additional experimental comparison with ACGD using the same sketches, please see our response to Reviewer hvUE, W1, W2 & Q1.

AuthorsOpenReview ↗

Response to Reviewer 4nM9 (2/2)

W2 & Q2. Comparison with nonuniform accelerated coordinate descent

Revision to the manuscript. We have added the trace-only parameter bounds and three examples to Appendix A.5 of the revised manuscript, with a pointer from Footnote 2 in Section 5. The additional experimental comparison with NU-ACDM is presented in Appendix G.6, with a pointer from Section 6.2.

Allen-Zhu et al. (2016) use nonuniform importance sampling based on all dd coordinate-wise smoothness constants Lii\mathbb L_{ii}. We do not claim that our analysis for general sketches improves upon their convergence rate. Instead, the distinction lies in the smoothness information required for parameter selection. Our r=1r=1 uniform-coordinate specialization depends only on max⁡iLii\max_i \mathbb L_{ii} (Footnote 2). Moreover, for Haar and Gaussian sketches, the smoothness parameters can be set using only tr⁡(L)\operatorname{tr}(\mathbb L), since the algorithms require LL and ℓ\ell only through LℓL\ell (see Appendix A.5). Appendix A.5 also shows that, for r=1r=1, the same oracle-complexity orders are preserved with at most a factor of 3\sqrt 3 increase in the bounds. This distinction matters when trace information is more natural or cheaper to obtain than the individual Lii\mathbb L_{ii}. Appendix A.5 illustrates this with matrix-free PDE inverse problems, portfolio optimization, and distributed logistic regression.

To examine the communication implications for distributed logistic regression, one of the examples in Appendix A.5, we added a comparison on the gisette dataset under the same cumulative communication-bit budget, including parameter initialization. In this setting, each worker sends one scalar for rank-one Haar RS-NAG and dd scalars for NU-ACDM during initialization, while both methods send one scalar per worker per iteration during optimization. Figure 6 shows regimes in which Haar RS-NAG is advantageous under the same communication budget, including initialization costs. As the budget increases further, the objective gaps become comparable; this does not change the finding that such advantageous regimes exist. The experimental details are given in Appendix G.6.

Q3. Implementation and the experimental cost metric

Revision to the manuscript. In response to your question, we have made the implementation explicit and clarified its communication-cost interpretation in Section 6.2. We have also expanded Appendix B to explain the concrete communication-bit accounting methods used in gradient-compression research, adding Li and Richtárik (2021) and Deng et al. (2025) alongside the previously cited Li et al. (2020).

For logistic regression, the gradient has a closed form and is straightforward to evaluate. In these experiments, we form the full gradient and then project it. As explained in the Introduction and Section 2.1, in distributed optimization, the full gradient can be projected before communication, reducing the number of communicated gradient scalars from dd to rr. Thus, the main 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 research also uses communication-cost accounting of the same kind as our oracle-complexity measure. We have further noted in the revised manuscript that Li and Richtárik (2021) and Deng et al. (2025), in addition to Li et al. (2020), use similar communication-bit accounting and evaluate experimental performance in terms of communication bits. Thus, the communication-cost interpretation of our oracle-complexity measure is grounded in existing gradient-compression research.

For the measured-computation and modeled-communication experiment, which includes sketch generation and projection in the measured computation time, please see our response to Reviewer hvUE, W3 & Q2. For the comparison with nonuniform accelerated coordinate descent, including the initial communication cost of obtaining the smoothness parameters, please see W2 & Q2 above.

Thank you for the clarification. The contribution is now better defined: a sharper matrix-dependent convergence analysis within an existing acceleration framework. The distinction between sketch variance and curvature-dependent descent, and the limitation of the earlier step-size condition, substantially address my novelty concern.

The trace-only parameter choice provides a useful motivation when individual coordinate smoothness constants are unavailable. However, the reported advantage over nonuniform accelerated coordinate descent depends on initialization costs and the communication budget. Since the experiments compute full gradients before projection, they do not establish computational or memory savings.

These clarifications justify increasing my score from 2 to 3, with remaining reservations about methodological novelty and practical efficiency.

Thank you for reconsidering our response and raising your score. We appreciate your recognition of our clarified technical contribution and your assessment of our comparison with nonuniform accelerated coordinate descent.

In addition to the nontrivial coefficient choices, the limitations of Vaswani et al.'s analysis even when those choices reproduce our updates, and our technical contribution discussed in our earlier response, the additional ACGD comparison (Section 6.1, Figure 2) further illustrates the significance of these contributions. Under the same rank-one Haar sketches, initial points, and oracle budget, RS-NAG achieves smaller objective gaps than ACGD with the parameters of Li et al. (2020) on all four quadratic problems.

To further assess whether RS-NAG can offer practical efficiency gains under communication constraints even when full gradients are computed before projection, we conducted an additional experiment combining measured computation time, including full-gradient computation, sketch generation, and projection, with separately modeled communication time (Section 6.2, Table 4; Appendix G.7). The results show that, under the specified communication model, the communication-time savings from transmitting fewer gradient scalars can outweigh the increased computation time associated with more iterations and other factors. Specifically, the best tested RS-NAG configurations reach the same relative objective-gap target in less modeled total time than NAG on all six datasets at bandwidths of 10 Mbps and below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.