Major
Presentation and clarity
In general, the paper as a whole is very poorly written in my opinion. I found it difficult to understand even rereading parts of it a few times. The explanations are often unnecessarily complicated, the notation is very inconsistent, and the connection between the different parts of the paper is not always clear (I elaborate on all of this below in the "Minor" section).
Very limited theoretical novelty
I think the paper has very limited theoretical novelty. Most of the theoretical analysis, which is presented as one of the main contributions of the paper, consists of results that are either well-known, taken directly from prior work, or so straightforward that it would be better to explain them directly rather than present them as separate theorems. More specifically:
-
Theorem 4.1: I'm not sure why this is presented as a theorem. This is a very well-known result that follows directly from the definition of Top-K. It should not be presented as a theoretical contribution of this work.
-
Theorem 4.2: I also don't know why this is presented as a theorem. The proof is essentially one step, and the conclusion follows immediately from the assumption itself. More importantly, it's a bit unclear under what conditions the assumed inequality (Eq. 19) actually holds for the gradients considered in this paper. Without a proper justification of this assumption, the result provides very limited insight.
-
Theorem 4.4: This theorem is presented as a convergence guarantee for LaplaceK, but the proof is simply the result from Karimireddy et al. (2019), which is cited in only the appendix and not in the theorem itself. Since Laplace-K implements the exact Top-K operator, the existing convergence guarantee applies directly and trivially. It is misleading to present this as a separate theoretical contribution, and especially without making it much clearer that the result is directly taken from prior work.
-
Theorem 4.5: I also don't understand why this is presented as a separate theorem. This is essentially identical to Theorem 4.4, with only a different contraction coefficient. Both theorems follow directly from the same existing result (Karimireddy 2019) and could easily be combined with 4.4 (if presented at all).
-
Lemma 4.7: This can be summarized in one line of math as it follows directly from the survival function of the Laplace distribution. I don't think it warrants a separate lemma and proof.
-
A similar argument applies to several other lemmas and theorems in this section. Many of these are straightforward consequences of standard identities, assumptions, or previously established results. While some of the distribution-dependent characterizations may be useful, their novelty and significance are not sufficiently explained.
I think the entire theoretical section needs a major revision. There are too many separate theorems and lemmas with very limited novelty, and it is unclear what the authors are trying to establish beyond applying known results to their setting. The paper should clearly distinguish between established results and its own contributions, consolidate the redundant statements, and focus on results that actually provide new insights into the proposed method.
Potential inconsistency between the exact Top-K guarantee and the experiments
The authors repeatedly emphasize that LaplaceK preserves the exact Top-K operator. Specifically, the threshold and candidate-selection procedure only affect the computational path, but the final selected coordinates and their values remain identical to those of standard Top-K.
However, in Appendix C.3 the authors compare Laplace and Gaussian priors and report that the Laplace prior consistently achieves faster convergence and higher final accuracy. I find this very difficult to reconcile with the claimed exactness of the method.
If both priors are used only to identify candidate sets, and both implementations ultimately perform exact Top-K selection (using a fallback when necessary), shouldn't they produce exactly the same compressed updates? Under otherwise identical training conditions, the optimization trajectories should also be (nearly) identical.
The authors even argue that the Laplace prior preserves important coordinates more reliably than the Gaussian prior. But this seems to directly contradict the claim that both implementations preserve exact Top-K selection.
I think this requires a clear explanation. Either there are important implementation details that are missing, or the proposed method does not always preserve the exact Top-K operator as claimed.
Insufficient justification of the Laplace structure
The Laplace-like distribution of the error-compensated gradients is the central observation motivating the entire paper, yet I don't think it is sufficiently demonstrated or justified.
The authors mainly rely on gradient histograms that visually resemble a Laplace distribution. However, a sharp peak around zero and symmetric tails do not necessarily establish that the gradients follow a Laplace distribution, particularly in the tails, which are precisely the part that matters for Top-K selection.
I would have expected a more thorough and quantitative characterization of this structure, including goodness-of-fit measures, comparisons with alternative distributions, and an analysis of how accurately the proposed Laplace model predicts the actual Top-K threshold.
Also, it is unclear how consistent this structure is across training iterations, model architectures, layers, and different sparsity levels.
Given that this observation is the main motivation for the proposed algorithm, I think a much stronger empirical justification is necessary.
Limited experimental evaluation and statistical reporting.
In general, I think the experimental section is quite limited given the motivation and claims of the paper.
Table 1 presents "the average wall-clock time across repeated runs", yet the main text does not specify how many runs were used and does not present any measure of uncertainty (like SEM or CI). The same applies to Figure 2, the results are presented without error bars / shaded confidence regions, and there is no mention of the number of runs used and it's also unclear whether the runs used different random seeds.
There are some variability measurements are in the appendix, but I think the main results should include sufficient information to assess the reliability of the reported results.
Additionally, I would have expected a more detailed breakdown of the computational savings. Since the main contribution of the paper is reducing the overhead of Top-K selection, a direct comparison of the selection time itself, rather than only the overall training time, would be particularly informative. It would also be useful to report the fraction of iterations in which the proposed selection procedure succeeds, how often the global fallback is required, and how these quantities affect the overall performance.
Unclear scaling behavior.
In Table 1, I would have expected the gains of the proposed method to increase with the size of the model, or at least for the authors to investigate how model size affects the improvements.
However, in the ResNet models the relative improvement in wall-clock time compared to TopK actually decreases as the models become larger. I understand that the computational savings do not necessarily have to increase monotonically with model size. But given that computational efficiency is the main contribution of the paper, I think this behavior deserves some discussion/explanation.
Minor
-
In the introduction, the sentence "Quantization introduces approximation noise, whereas sparsification may bias updates when important coordinates are omitted" is not entirely accurate. Both quantization and sparsification can be biased or unbiased, depending on the compressor. I suggest revising this.
-
The sentence "The standard analysis treats Top-k through the same generic contraction used for Random-k" could be clearer. While the unscaled Random-k operator considered in the paper does satisfy this contraction bound, this is not generally true for the commonly used unbiased (scaled) Random-k compressor. Moreover, Top-K and Random-k are not necessarily treated identically in existing analyses. I think it wouldbe better if the authors should clarify precisely which formulations they are referring to.
-
I found the notation somewhat unusual and very inconsistent. For example, Top-K already has an explicit parameter K that is commonly used in the literature, so I'm not sure why the authors primarily define it through a density parameter. This is not incorrect, but I think it makes the presentation less intuitive.
-
There are numerous notation inconsistencies throughout the paper, including:
- Using ϵ in Section 2 and e in Section 3 for the error-feedback residual.
- Using T0 and τt for the threshold, rather than consistent notation, e.g., τ0 and τt.
- Using Pτ and Ct for closely related candidate sets.
- Using both ρ and d for the retained density, while d is also used to denote the dimension of the model.
- Using bold notation for vectors in Section 2 but not consistently throughout the rest of the paper.
I think these inconsistencies are unnecessary and make an already difficult-to-follow paper even harder to read.
-
The parameter T is widely used in the optimization literature to denote the number of iterations (which is also the case in the Theorems you present). I would suggest using a different symbol for the integer threshold-search budget.
-
Section 3 uses Ct to denote the cardinality of the set of coordinates satisfying the threshold, while Algorithm 1 uses C for the set itself and c for its cardinality. Although these are technically different symbols, I think the notation could be made much more consistent.
-
In Appendix B, it would be more natural to present the proof of Theorem 4.2 before the proof of Theorem 4.4, following the order of the results in the main text.
-
Figure 2 is poorly organized in my opinion. It would be much easier to follow if the accuracy and wall-clock plots for each model were presented side by side, rather than splitting some models across rows. I also think the figure is unnecessarily large for the main paper and could be moved to the appendix, espeically since much of this info is already summarized in Table 1. The discussion of the figure in the main text is also limited.
Dear authors,
I apologize if my initial review is too long. I gave an extreme score, so I needed to justify it thoroughly.
That said, I understand these rebuttals require significant effort and time. Therefore, if it would help alleviate the load, you can focus on addressing the following points, which can affect my decision the most:
Regarding the part "Very limited theoretical novelty", I'm not sure much can be done here, but if you have further general thoughts on this, I would like to hear them (there is no need, however, to address each and every one of the things I listed there directly).
There is also no need to address the "Minor" section.
Looking forward to your response (although I don't mean to pressure you further with this comment, quite the opposite).