Tight analyses of first-order methods with error feedback

We sincerely thank the reviewer for their positive feedback and high ratings regarding the quality, clarity, and originality of our work. We also appreciate their familiarity with the relevant literature. Below, we respond to each of the reviewer’s comments and questions in detail.

The analysis is restricted to the single-client setting. This significantly limits the impact of the results, as some of the known challenges of CGD in the distributed setting, when n>1, are not present in the n=1 case. In particular, as noted by the authors and shown in prior work [...], CGD fails to converge in the distributed setting.

Additionally, in the single-node case, error feedback appears unnecessary and overly complex.

While we all agree that the multi-agent case is of importance and shows nuances, we believe the single-agent case to be of significant interest, and do not fully agree with the claim that EF is "unnecessary and overly complex" in the single-agent setting.

1. Many foundational works on error feedback [1–3] perform their analysis in the single-agent setting. E.g. Table 1 in [5] highlights this. It thus seems that the community does not disregard the importance of this regime for theoretical understanding.

2. We believe our analysis does reveal meaningful distinctions:

• CGD does not consistently outperform EF or EF21 across all step sizes. The superiority of CGD only holds under optimal tuning. In fact, one of CGD’s key advantages is its ability to operate using significantly larger step sizes, which offers useful intuition for its behavior and performance trade-offs. We generated a figure (prior to the announcement disallowing new figures in the rebuttal process) that showcases, for any fixed $(\eta, \epsilon)$, the log-ratio of optimization complexities between CGD and EF: for instance, for $\kappa=10$, depending on the step size, EF can be more than 100 times faster or 1000 times slower than CGD (in terms of number of steps required to achieve the same reduction in performance measure). We will add this figure to the paper.

• The equality of rates between EF and EF21 in this setting was, to the best of our knowledge, previously unknown. This equivalence can be revealed only by analysis using an optimal Lyapunov function, as the optimal rate is achieved for a very different Lyapunov function. For a fixed Lyapunov function, the rates of EF and EF21 are not the same—we will also provide an illustration of this fact.

3. Third, there exist links to quantized-aware-training of deep neural networks, which we should have highlighted (and will add):

BinaryConnect [6], which is one of the most popular algorithms for quantization-aware training of neural networks, combines gradient steps with quantization steps. Although not directly equivalent to CGD or EF, it is a natural example of a single-agent algorithm that combines quantization and GD. The adaptation of EF in the context of sparse neural networks leads to the work of Lin et al. [7], who perform sparse neural-network training by applying only sparse updates, which is equivalent to error feedback. The authors note this equivalence at the end of Section 3 (and are themselves among the active contributors to the field of error feedback, as they have co-authored [1-4]).

Generally speaking, the single-agent setting is thus relevant to the design of training methods for sparse or quantized neural networks—motivating the study of these algorithms even outside their typical distributed setting.

• [1] S. Stich, S.P. Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. JMLR, 2020.
• [2] A. Ajalloeian, S. Stich. Analysis of SGD with biased gradient estimators. , 2020.
• [3] S.P. Karimireddy, Q. Rebjock, S. Stich, M. Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. ICML, 2019.
• [4] S. Stich, J-B. Cordonnier, M. Jaggi. Sparsified SGD with memory. Neurips 2018.
• [5] P. Richtárik, I. Sokolov, I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Neurips, 2021.
• [6] M. Courbariaux, Y. Bengio, J-P. David. BinaryConnect: Training Deep Neural Networks with binary weights during propagations. Neurips 2015.
• [7] T. Lin, S. Stich, L. Barba, D. Dmitriev, M. Jaggi. Dynamic Model Pruning with Feedback. ICLR, 2020.

Therefore, the phrasing in line 239 “These results challenge the prevailing intuition that error feedback ensures convergence comparable to that of uncompressed methods” is misleading: the lack of convergence is not a matter of intuition but a rigorously established fact. On the other hand, CGD converges without issue in the single-node case.

There might a misunderstanding here: the claim we make in line 239 (and that echoes the way methods using error feedback are sometimes understood by the community) is that methods using error feedback achieve rates of convergence almost equivalent to the "no-compression case" (uncompressed methods), not to the "CGD case". What we show is that in the single agent deterministic case, they neither recover the performance of GD, nor that of CGD. More precisely, CGD, which we consider to be the baseline method in the single-agent setting, is considerably slower than uncompressed methods, and as EF and EF21 underperform relative to the baseline method in the single-agent case, they are by-extension also not comparable to uncompressed methods.

We thus think the phrasing of line 239 is fair, but can amend it if the reviewer believes it's misleading.

The paper lacks a clear rate comparison with classical results for EF [3] and EF21 [4]. In particular, Theorems 1 and 2 do not explicitly state the iteration complexity rates, and require additional manipulation to extract them.

Q: How do the convergence rates obtained in this work compare to the classical results for EF and EF21?

We agree that our original presentation did not make rate comparison easy. We highlighted the dependence on the step-size and the optimal Lagrange multiplier, but the resulting expression is not immediately comparable to existing bounds. For completeness, we provide below the cleanest closed form we have derived to date for our rate:

$$\rho = \sqrt{\epsilon} + \left(\frac{1 - \sqrt{\epsilon}}{2}\right) \left(\frac{\kappa - 1}{\kappa + 1}\right)^2 \left[1 - \sqrt{\epsilon} + \sqrt{(1 + \sqrt{\epsilon})^2 + \sqrt{\epsilon} 16 \frac{\kappa}{(\kappa - 1)^2}}\right],$$

where $\kappa := L/\mu$. Showing that this bound strictly improves upon other existing rates, such as the one under the PL-condition rate of [1], is straightforward (and natural: we have a tight rate under stricter assumptions); quantifying the margin analytically is less so, though feasible. We will therefore include the above parameterization as a remark in the revision, together with both an analytical discussion and a visual comparison against the PL-based rate.

Q: What's the primary challenge of analyzing the distributed setting?

This is a very good question. The main bottleneck in extending our approach to the multi-agent case is that the candidate Lyapunov function space grows quadratically (the Lyapunov functions may contain gradients, compressed messages from different functions, and error feedback terms, as well as crossed inner products); should the optimal function involve dense coefficient patterns, obtaining a closed-form via our approach requires substantial additional effort. One approach in that direction, that we are currently investigating, is the use of symmetries to reduce the size of the problem.

---

We thank the reviewer for their support and remain available for any further discussion.

---

We sincerely thank the reviewer for their thoughtful and constructive feedback on our work. Below, we address each point in the order raised.

The abstract does not mention single-agent.

We agree that the final clause of the abstract is ambiguous. We will revise it to:
"Our analysis is carried out in the simplified single-agent setting, which allows..."

Assumption 1 is made for deterministic compressors, while in the EF21 paper by Richtárik, the contractive compression operator is defined for stochastic compressors in expectation. Is it possible to extend the current results to the class of stochastic contractive compressors?

This is a good question: the proofs indeed carry over directly to stochastic contractive compressors—one simply applies the expectation bound on the compressor and uses linearity of expectation in the Lyapunov analysis. We have prepared and will provide a WolframScript that verifies the resulting inequalities, and we will spell out the stochastic version of the assumption as well as the corresponding theorem statements in the next revision. We thank the reviewer for making this comment, which helps broaden the scope of the analysis.

Typo l.132

We thank the reviewer for noticing this typo. It will be fixed in the next draft.

The main issue with the paper is its focus on the single-node regime. The core motivation for using gradient-type methods with compressed updates, such as EF, EF21, and CGD (Compressed Gradient Descent), is typically in the multi-node setting. It is unclear why it would be meaningful to consider these methods in the single-node setting, where compression is not useful. Could the authors clarify any potential benefits of using such methods in the single-node case?

The authors claim that studying the single-node setting can provide intuition. However, I find this potentially misleading. In the single-node setting, CGD can converge with an appropriate step size without any issues. In this scenario, EF and EF21 mechanisms seem redundant, since the standard CGD method can work without additional memory or algorithmic adjustments. On the other hand, in the multi-node setting, as the authors themselves mention, CGD may diverge regardless of the step size. [...]

We appreciate this important question—this is a point we should have made clearer and will detail in the revised version. We fully acknowledge (and we stated in the submitted draft) that some behaviors will differ when moving from the single-agent to the multi-agent setting. Nevertheless, we believe there are strong arguments in favor of providing a tight analysis in the single-agent case as a first step:

1. Practical relevance beyond distributed optimization

We would like to highlight the relevance of our work in the context of sparse/quantized neural-network training. BinaryConnect [1], which is one of the most popular algorithms for quantization-aware training of neural networks, combines gradient steps with quantization steps. Although not directly equivalent to CGD or EF, it is a natural example of a single-agent algorithm that combines quantization and GD. The adaptation of EF in the context of sparse neural networks leads to the work of Lin et al. [2], who perform sparse neural-network training by applying only sparse updates, which is equivalent to error feedback. The authors note this equivalence at the end of Section 3 (and are themselves among the active contributors to the field of error feedback, as they have co-authored [3-6]).

Generally speaking, the single-agent setting is thus relevant to the design of training methods for sparse or quantized neural networks—motivating the study of these algorithms even outside their typical distributed setting.

• [1] M. Courbariaux, Y. Bengio, J-P. David. BinaryConnect: Training Deep Neural Networks with binary weights during propagations. Neurips 2015.
• [2] T. Lin, S. Stich, L. Barba, D. Dmitriev, M. Jaggi. Dynamic Model Pruning with Feedback. ICLR, 2020.

2. Numerous key papers derive their analysis in the single-node case

We respectfully disagree that error feedback is simply redundant in the single-agent setting. In fact, many of the foundational (and well-cited) works that analyze error feedback [see, among others, 3–5] place themselves specifically in that single-agent regime for the analysis. This is underlined in other papers; see, for example, Table 1 of [7]. We believe such sustained interest means that the community considers the single-agent case insights to be valuable.

• [3] S. Stich, S.P. Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. JMLR, 2020.
• [4] A. Ajalloeian, S. Stich. Analysis of SGD with biased gradient estimators. , 2020.
• [5] S.P. Karimireddy, Q. Rebjock, S. Stich, M. Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. ICML, 2019.
• [6] S. Stich, J-B. Cordonnier, M. Jaggi. Sparsified SGD with memory. Neurips 2018.
• [7] P. Richtárik, I. Sokolov, I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Neurips, 2021.

3. Comparing EF, EF21, and CGD is far from straightforward even in the single-node case, and our analysis in the single-agent case already brings valuable insights:

• First, CGD does not consistently outperform EF or EF21 across all step sizes. The superiority of CGD only holds under optimal tuning. In fact, one of CGD’s key advantages is its ability to operate under significantly larger step sizes, which offers useful intuition for its behavior and performance trade-offs. We generated a figure (prior to the announcement disallowing new figures in the rebuttal process) that showcases, for any fixed $(\eta, \epsilon)$, the log-ratio of optimization complexities between CGD and EF: for instance, for $\kappa=10$, depending on the step size, EF can be more than 100 times faster or 1000 times slower than CGD (in terms of number of steps required to achieve the same reduction in performance measure). We will add this figure to the paper.

• Second, the equality of rates between EF and EF21 in this setting was, to the best of our knowledge, previously unknown. This equivalence can be revealed only by analysis using an optimal Lyapunov function, as the optimal rate is achieved for a very different Lyapunov function. For a fixed Lyapunov function, the rates of EF and EF21 are not the same—we will also provide an illustration of this fact.

We therefore believe that, although some behaviors will differ in the multi-agent case, the simplified setting considered in this work reveals non-trivial and meaningful insights. Providing a tight analysis under optimal step-size tuning allows us to offer a fair comparison between the methods and should act as a stepping stone for future work comparing these methods in the multi-agent, non-convex, or stochastic-gradient cases. Nevertheless, we are happy to better highlight the differences to be expected in multi agent in a dedicated subsection.

Another important point is that EF21 is typically analyzed in non-convex settings and also under the Polyak-Łojasiewicz (PL) condition. [...] . Showing that EF and EF21 perform identically in the strongly convex setting does not necessarily imply that the same will hold in the non-convex or multi-node case. In fact, theory currently favors EF21 in the non-convex regime.

Finally, another limitation is that the analysis assumes full-gradient updates. Stochasticity is not considered, even though stochastic gradients are essential in practical applications. Therefore, it would be valuable to compare these methods in the stochastic case.

• Regarding extensions: We agree that our work does not provide direct results under non-convex assumptions, nor does it use stochastic gradients. To avoid confusion, we have explicitly stated all of our assumptions in specific environments at the beginning of the paper, allowing readers to quickly verify the scope of our contributions. Extending our results to the non-convex setting and/or using stochastic gradients would be a very interesting contribution, but it would substantially change the scope of the current paper, which is already quite long. We consider either of those extensions to be exciting directions for future work in the field.

• Regarding non convexity:

  -- While a line of work has consisted in analyzing EF21 in non-convex settings [7–9], such analysis is not systematic; convexity assumptions are also common in the broader literature on distributed optimization, including [5, 6].

  -- More importantly, results under weaker assumptions come with looser convergence guarantees, and we believe they do not always bring a better understanding of the methods: strong convexity allows us to show rates that are likely to be better characterizations of performance around local minima-which could be argued correspond better to training behavior ultimately observed in practice. Moreover, on the technical side, while extending our technique to PL condition is of great interest, we are unaware of tight interpolation conditions for functions satisfying the PL condition. Providing them would on its own consitute a non-trivial research contribution. Overall, our choice is to focus on a setup powerful enough to provide a tight and fair comparison.

---

We hope our clarifications help resolve the earlier concerns and would be grateful if you might reconsider the score. We’re glad to provide any further details you’d find useful.

---

• [8] I. Fatkhullin, I. Sokolov, E. Gorbunov, Z. Li, P. Richtárik. EF21 with bells & whistles: practical algorithmic extensions of modern error feedback. JMLR , 2025.
• [9] L. Condat, K. Yi, P. Richtárik. EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. Neurips, 2022.

We thank the reviewer for their very positive comments on the execution of the paper, and for the ratings given. The typos found by the reviewer will be fixed in the next draft, and we thank them for pointing those out as well.

The paper only considers the exact-gradient case. Note that EF was largely motivated by the need of compressed GD to handle the stochastic noise (see “Error Feedback Fixes SignSGD and other Gradient Compression Schemes”, Section 3). Since the practical scenarios have stochastic noise, I question the significance of this work, in particular the conclusion “We also observed that their performance is strictly worse than that of compressed gradient descent – an outcome that, we believe, challenges the intuition of many in the field.”

We agree with the reviewer that it would be very interesting to see what the guarantees would look like with stochastic gradients. That being said, it would change the scope of the paper quite a bit. Deterministic gradients have been used in some landmark papers (e.g. [1]), or it is reported as a separate result (e.g. [2]). We consider it to be a different problem that we would prefer to leave as an exciting direction for future work.

Section 3: what is the optimal convergence rate for CGD?

We recover the following optimal rate for CGD, that was also given by [3, 4]:

$$\left(\frac{\kappa_{\sqrt{\epsilon}} - 1}{\kappa_{\sqrt{\epsilon}} + 1} \right)^2,$$

where $\kappa_{\sqrt{\epsilon}} = \frac{L (1 + \sqrt \epsilon)}{\mu (1 - \sqrt \epsilon)}$ (note that we define the conditioning number inversely compared to [3]).

The line for CGD in Figure 2 was generated simply by discretizing over the interval $\eta \in (0, 2/(L+\mu)]$, and manually selecting the step size that gave the best contraction. To reassure the reviewer: the plot was originally (before we knew the closed-form optimal step size for EF and EF21) using the same implementation, and simply looked like a discrete approximation of the smooth figure now present in the paper. We will update the plot to instead use the step size given in [4] directly in the next draft (while providing the reference and closed-form explicitly in the text).

In Section 2.1, you don’t talk about EF. Also, please mention EF21 when using reference [14].

We acknowledge that we should have discussed existing EF results and will incorporate this in the next draft. We will likewise replace the generic reference with an explicit mention of EF21 accompanied by the Richtárik citation.

---

We thank the reviewer again for their support and would happily participate in any further discussion if needed.

---

References:

• [1] P. Richtárik, I. Sokolov, I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems 34, 2021.
• [2] K. Gruntkowska, A. Tyurin, P. Richtárik. EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression. International Conference on Learning Representations, 2020.
• [3] E. De Klerk, F. Glineur, A. Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 2016.
• [4] O. Gannot. A frequency-domain analysis of inexact gradient methods. Mathematical programming, 2020.

We sincerely thank the reviewer for their detailed and thoughtful comments, particularly regarding the SDP formulation in the appendix. We appreciate the reviewer’s careful reading, as some highlighted questions will help significantly improve the clarity of the manuscript.

We first want to emphasize that the derivations and theoretical results presented in the main text remain correct and unaffected. In particular, it should be noted that the proofs of Theorems 1 and 2 do not rely on the SDP formulation and can be verified independently. We hope this reassures the reviewer regarding the validity of our results.

Below, we respond point by point to the reviewer’s remarks.

Why interpolation conditions for the compression look as in equations (35,36) in supplementary material?

Thank you for pointing this out. First, we acknowledge a clear typo in equation (36):

C\_i^{EF} = \\begin{bmatrix} \\bar{g}\_i \\\\ \\bar{c}\_i \\\\ \\mathbf{\\bar{c}}\_i \\end{bmatrix}^\\top C\_{EF} \\begin{bmatrix}\\bar{g}\_i \\\\ \\bar{c}\_i \\\\ \\mathbf{\\bar c}\_i\\end{bmatrix}.

This should instead be

C\_i^{EF} = \\begin{bmatrix}\\bar{g}\_i \\\\ \\bar{c}_i \\\\ \\mathbf{\\bar{e}}\_i\\end{bmatrix}^\\top C\_{EF} \\begin{bmatrix}\\bar{g}\_i \\\\ \\bar{c}\_i \\\\ \\mathbf{\\bar e}\_i\\end{bmatrix}.

We apologize for this oversight, which may have made interpretation difficult.

Let us now explain why we define equation 36 as we did. The interpolation condition, for any $i \\in \\{0, 1\\}$ can be written as

$$||(\eta g_i + e_i) - c_i|| ^2 \leq \epsilon ||\eta g_i + e_i||^2,$$

which is a direct discretization of Assumption 1 or equivalently,

$$||(\eta g_i + e_i) - c_i|| ^2 - \epsilon ||\eta g_i + e_i||^2 \le 0.$$

Equation 36 is simply a rephrasing of this condition, after expansion, in terms of the basis vectors we defined:

\\begin{aligned} &||(\\eta g\_i + e\_i) - c\_i|| ^2 - \\epsilon ||\\eta g\_i + e\_i||^2 \\\\ &=||c\_i||^2 + \\eta^2 ||g\_i||^2 + ||e\_i|| ^2 - 2\\eta \\langle g\_i, c\_i \\rangle -2 \\eta \\langle e\_i, g\_i \\rangle + 2 \\langle c\_i , e\_i \\rangle - \\epsilon \\eta^2 || g\_i||^2 - \\epsilon ||e\_i||^2 - 2\\epsilon \\eta \\langle g\_i, c\_i \\rangle \\\\ &= \\text{Tr}\\left(\\begin{bmatrix}g\_i \\\\ c\_i \\\\ e\_i\\end{bmatrix}^\\top C\^{EF} \\begin{bmatrix}g\_i \\\\ c\_i \\\\ e\_i\\end{bmatrix}\\right). \\end{aligned}

This can be seen directly by matching the coefficients we now wrote down explicitly, to that of the matrix in equation (35). Ultimately, $C_i^{EF}$ is defined such that the outer basis vectors are "picking" the contributions from the right vectors, and then assigning them the weights given in equation 35, i.e. s.t.:

\\begin{aligned} \\text{Tr}\\left(\\begin{bmatrix}g\_i \\\\ c\_i \\\\ e\_i\\end{bmatrix}^\\top C\^{EF} \\begin{bmatrix}g\_i \\\\ c\_i \\\\ e\_i\\end{bmatrix}\\right) \\end{aligned} = \\begin{aligned} \\text{Tr}\\left( B^\\top C_i\^{EF} B\\right) \\end{aligned}

From there on, the derivation follows step 1 and 2 from section A. The primal constraint \\text{Tr}\\left( B^\\top C_i\^{EF} B\\right) = \\text{Tr}\\left( C_i\^{EF} G \\right) \le 0 leads to the term $\sum_{i \in\{0,1\}} \gamma_i \cdot C_i^{E F}$ in eq. (EF-SDP) (following eq. (36)).

We will provide the details of this computation in the next version.

Additionally, we acknowledge that in the same subsection, we reused the notation $C_{ij}$, $c_{ij}$ (later referred to as $M_{ij}$ and $m_{ij}$) for the smoothness and strong convexity interpolation conditions. This overlaps with the notation used for $C_i^{EF}$ and $C_i^{EF21}$, and we understand this may have contributed to confusion. We sincerely apologize and have revised the appendix to improve the clarity and consistency of notation throughout.

Since I don't fully understand the point (could be due to poor explanation), it seems to me that the analysis does not actually cover the entire class of contractive compressors. I am afraid that it is restricted to linear contractive compressors such as the one shown in tightness analysis in equation (50). [...]. In fact, from the practical viewpoint, the most interesting contractive compressor is Top-$K$, but I am not sure this is covered in this framework.

We hope the explanation provided above clarifies how Assumption 1 is exactly encoded in the SDP without restriction. To further reassure the reviewer, we emphasize that the analysis of convergence rates is entirely decoupled from the SDP—it directly invokes Assumption 1 in the proofs, and does not necessitate any linearity. The SDP was used only to design the Lyapunov function we use in our analysis.

Regarding equation (50) specifically: it appears in the lower-bound construction, which is separate from the upper bound. We obtain this lower bound using a linear compressor given by eq. (50), on a specific function. It is sufficient to achieve the lower bound on this linear compressor to conclude, as it belongs to the more general set of compressors. The upper bound is obtained under the full generality of Assumption 1, and thus beyond linear contractiveness.

The Top-$K$ compressor is thus indeed included in our analysis.

It is unclear why the resulting Lyapunov function for EF21 does not include the function value? I would expect it should since analysis in (Richtarik et al 2021) is conducted using the function value as the potential and is tight if I understand it correctly.

It is indeed an interesting consequence of our analysis that the optimal Lyapunov function does not correspond to the ones in the literature (even for EF!). This is actually one strength of our approach to be able to automatically and exactly derive the best possible Lyapunov functions.

Regarding the analysis of (Richtarik et al 2021), there are a couple of differences on the assumption set. We are unsure about which exact tightness result you mention. Regardless, tightness results for a given Lyapunov function are very distinct from tightness results that say that no Lyapunov function can provide a better rate (and our result is tight in both senses). Getting results of the latter type typically requires using performance estimation techniques. It is thus not surprising that the use of these advanced tools enables us to find better Lyapunov functions.

We thank the reviewer for pointing out typos, which will be remedied in the next revision. We would just like to comment on the following:

If I understand it correctly, the definition of large $C_{i, j}$ coefficients in line 591 can be simplified using a norm squared instead of inner products.

Note that the basis vectors are row vectors, expressions like $\bar{g}_i^\top \bar{x}_j$ denote outer products (i.e. matrices), and not inner products (scalar). While we could reformulate these terms using a custom norm operator representing self-outer-products, we prefer to keep the current notation to avoid introducing new definitions that would require additional explanation. Instead, we have emphasized in the revised draft that the basis vectors are row vectors, to prevent further confusion.

From analysis, CGD allows larger step-size of order $1/L$ than EF and EF21 which require $(1-\sqrt{\epsilon})/L$. This can be also seen from upper bounds and convergence analysis. Is there an intuitive explanation why this happens?

We note that the optimal step size for CGD is given by [2]

$$\eta = \frac{2}{(1 - \sqrt{\epsilon})\mu + (1 + \sqrt{\epsilon}) L}.$$

The optimal rate for CGD is also given by [1, 2]

$$\left(\frac{\kappa_{\sqrt{\epsilon}} - 1}{\kappa_{\sqrt{\epsilon}} + 1} \right)^2,$$

where $\kappa_{\sqrt{\epsilon}} = \frac{L (1 + \sqrt \epsilon)}{\mu (1 - \sqrt \epsilon)}$ (note that we define the conditioning number inversely compared to [1]). An intuition for this is essentially that the uncertainty in the update direction is "rescaling" $L$ by adding "$\sqrt{\epsilon}$ uncertainty", and doing the converse operation for $\mu$.

As far as our step size is concerned, it is given by

$$\eta = \left(\frac{2}{L + \mu}\right) \left(\frac{1 - \sqrt{\epsilon}}{1 + \sqrt{\epsilon}}\right).$$

That is to say: in CGD, the "rescaling" is applied at the level of the smoothness and strong convexity constants, whereas the scaling for EF/EF21 is applied at the level of the step size.

---

We hope our responses have clarified any misunderstandings and that you will consider revising your score accordingly. We would be happy to provide further clarification if needed.

---

References:

• [1] E. De Klerk, F. Glineur, A. Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 2016.
• [2] O. Gannot. A frequency-domain analysis of inexact gradient methods. Mathematical programming, 2020.