Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper extends Safaryan's smoothness-aware compression method to the general unbiased compression method. Meanwhile, the authors propose two non-linear compressors for DCGD+ and DIANA+.

strengths_and_weaknesses: Strengths

1.This paper has a solid theoretical analysis of convergence and communication complexity.

2.Two non-linear compressors are proposed for DCGD+ and DIANA+ and the theoretical results show their good performance.

3.The authors conduct serious experiments to evaluate their method. They are detailed and easy to follow.


 Weaknesses

1.This paper is an extended paper to Safaryan's, which reduces the significance. 

2.Though authors have discussed the technical contribution, the main difficulty of extending to the arbitrary unbiased compression operators seems to be easy to handle.

questions: Could you give the code for reproduction?
limitations: The authors have discussed the limitation in the detail.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper generalizes the smoothness-aware compression strategy to arbitrary unbiased compression. This trick was applied to two existing algorithms, DCGD and DIANA, improving communication complexity. Because it can be applied to any unbiased compression scheme, the quantization was improved further with block quantization and varying steps. 
strengths_and_weaknesses: Strengths
+ The proposed trick uses local second-order information to compress the gradient, largely improving existing compression techniques' performance.  
+ The convergence is provided for strongly convex functions under some assumptions. 

Weakness
+ The algorithm requires the smoothness matrix $L$, which may not be easily obtained. 
questions: How does the algorithm perform if the smoothness matrix $L$ is unknown (e.g., it takes too long to find it)? If the matrix is wrong, what will happen to the algorithm? 
+ Does the transfer of the matrix $L$ use compression? The matrix $L$ is not sparse, and the size is $d\times d$, which can take a long time. 
+ The convergence results require $\nu,$ $\nu_1$ being $O(1)$. In fact, the numbers can be in the order of $n$ and $d$ for IID data. In the numerical experiments, the data is split after random shuffled. So the number for $\nu$ and $\nu_1$ may be too big. It would be interesting to see the performance on heterogeneous data. 
limitations: Majors limitations are already listed in the Appendix A.3.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper is concerning compressed communication in distributed machine learning.
Smoothness Matrices by Safaryan et al. make it possible to use compressors with different smoothness information for each node, but the choice of compression function is restricted. This paper proposes a generalized method that allows Smoothness Matrices to be applied to any unbiased compressor below a certain variance. This paper further derives how to improve the existing methods called DCGD and DIANA with the proposed framework. 

## Afer author feedback
Considering the answers to my questions and other reviewers' question, I raise my score +1 upward. 
I expect the discussion about the assumption viloations to be inculded somewhere in the appendix. 

strengths_and_weaknesses: ## Originality: 


The main result extends the new distributed compression learning results proposed last year.

This paper proposes an algorithm that applies an extended version of Smoothenss Matrices to a broader class of compression (quantization) algorithms, though the reviewer cannot fully understand the technical originality of the main result (the first point in Appendix A.2?). 
If I correctly understand, the quantization methods applied to DCGD and DIANA are not new. 

## Quality: 

The validity of the proofs has not been verified. 
The technical ingenuity and the main idea are well understood.
The correspondence between the claims of the paper and the supporting theorem and experimental results is clear.



## Clarity: 

The structure of the paper and its arguments are written in an easy-to-understand manner. 
Even a non-expert reviewer (=me) on this topic can understand the technical innovations and results. 


## Significance: 

The reviewer mainly works on neural data (image) compression models and is not an expert on compression "communication" protocols in distributed machine learning. 
Thus the reviewer is not confident in accurately evaluating this study in the context of the distributed ML community. 

However, it is understandable that choosing an appropriate compression model is important to improve the efficiency of distributed compression learning. 
The original Smoothness Matrices method is restricted to a certain type of compressor, thus the contribution of the paper seems important.  

The numerical experimental results clearly show advancements brought by the proposed framework. However, the reviewer cannot judge how significant these advancements are.

questions: * Is the idea of multiplying L^{1/2} before and after Compressor a basic common practice? Has it been used in other papers? Or is it first conceived for this paper?

* How strictly must assumptions 1 and 2 be followed when dealing with uncontrolled real data?　Which assumption is more likely to cause practical problems in distributed compression learning when violated?

limitations: Discussed in aeepndx.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of distributed optimization over a parameter-server framework wherein the information exchanged from the workers to the server at every iteration is compressed to reduce the communication demand. To design better algorithms for this, the authors consider a different assumption on the smoothness structure of the objective function. They utilize the notion of **matrix smoothness** introduced in *Safaryan et al.* To solve the problem $\text{min}_{\mathbf{x \in \mathbb{R}^d}} f(\mathbf{x})$, where $f(\mathbf{x}) = \frac{1}{n}\Sigma f_i (\mathbf{x})$, existing works assume that each local function $f_i$, as well as the global objective $f$, is $L$-smooth. This assumption ignores the heterogeneity in the structure of the local objective functions, and the authors in this paper use **matrix-smoothness** to exploit this heterogeneity for designing compressors at each worker differently and achieve better convergence rates.

Scalar $L$-smoothness of a function $\phi(\mathbf{x})$ implies that the function curvature in the neighborhood of any point $\mathbf{x} \in \mathbb{R}^d$ in the domain of f can be upper bounded by a quadratic function. In other words, the Bregman divergence with respect to $\phi$ can be upper bounded by the Euclidean distance (with appropriate scaling), i.e. 

$D_{\phi}(\mathbf{x}, \mathbf{y}) \leq \frac{L}{2}\lVert \mathbf{x} - \mathbf{y} \rVert_2^2$.

The idea behind matrix $\mathbf{L}$-smoothness for any symmetric positive semi-definite (PSD) matrix $\mathbf{L}$ is to generalize this upper bound to Euclidean distance in a transformed space, i.e.,

$D_{\phi}(\mathbf{x}, \mathbf{y}) \leq \frac{1}{2}\lVert \mathbf{x} - \mathbf{y} \rVert_\mathbf{L}^2$.

Since $\mathbf{L}$ is PSD, its eigenvalue decomposition can be given as $\mathbf{L} = \mathbf{U}\mathbf{\Lambda}\mathbf{U}^T$, and hence for any $\mathbf{z} \in \mathbb{R}^d$,

$\lVert \mathbf{z} \rVert_\mathbf{L}^2 = \mathbf{z}^T \mathbf{L} \mathbf{z} = \mathbf{z}^T \mathbf{U}\mathbf{\Lambda}\mathbf{U}^T \mathbf{z}$, which gives,

$D_{\phi}(\mathbf{x}, \mathbf{y}) \leq \frac{1}{2}\lVert\mathbf{\Lambda}^{1/2}\mathbf{U}^T( \mathbf{x} - \mathbf{y})) \rVert_2^2$.

That is, this gives us a more refined (as well as generalized over scalar $L$-smoothness) information about the smoothness of the objective function, stating that the Bregman divergence of is upper bounded by the Euclidean distance between $\mathbf{x}$ and $\mathbf{y}$ after they have been unitarily transformed into the column space of $\mathbf{U}$, and each coordinate scaled differently in the transformed space. This **matrix smoothness** characterization of the objective function is a generalization of the scalar smoothness characterization, and its usefulness becomes apparent in designing compressors for the gradients of such functions. 

From my high-level understanding, this is because of the following reason (I request the authors to correct me if I am mistaken) -- When existing works design compressors for the gradients of functions for which only scalar $L$-smoothness information is known, the usual convergence analysis of the expected suboptimality gap is upper bounded by an expression consisting of the compression error measured in the Euclidean metric, i.e. $\mathbb{E}\lVert C(\mathbf{x}) - \mathbf{x} \rVert_2^2$ . This work considers general unbiased compressors $C(\cdot)$ that satisfy $\mathbb{E}\lVert C(\mathbf{x}) - \mathbf{x} \rVert_2^2 \leq \omega \lVert \mathbf{x} \rVert_2^2$. Here, $\omega \geq 0$ characterizes the expected compression error of $C(\cdot)$. On the other hand, when the matrix smoothness characterization of objective functions is assumed, since the Bregman divergence is upper bounded by a "transformed and scaled" Euclidean distance, in the convergence analysis, the expected suboptimality gap is upper bounded by an expression consisting of the compression error measured in the "transformed and scaled" Euclidean metric, i.e. $\mathbb{E}\lVert C(\mathbf{x}) - \mathbf{x} \rVert_{\mathbf{L}}^2$. This "transformed and scaled" compression error can be characterized similar to before as, $\mathbb{E}\lVert C(\mathbf{x}) - \mathbf{x} \rVert_{\mathbf{L}}^2 \leq \mathcal{L}\lVert \mathbf{x} \rVert_2^2$. Note that: 

$\mathbb{E}\lVert C(\mathbf{x}) - \mathbf{x} \rVert_{\mathbf{L}}^2 = \mathbb{E}\lVert \mathbf{\Lambda}^{1/2}\mathbf{U}^T(C(\mathbf{x}) - \mathbf{x}) \rVert_2^2 \leq \lambda_{max}(\mathbf{L})\mathbb{E}\lVert(C(\mathbf{x}) - \mathbf{x}) \rVert_2^2 \leq \lambda_{max}(\mathbf{L})\omega \lVert \mathbf{x} \rVert_2^2$.

So, the matrix smoothness approach yields *clear theoretical benefits* when the "transformed and scaled" upper bound coefficient $\omega \lambda_{max}(\mathbf{L})$ is smaller than the "Euclidean" coefficient, $\omega$. I understand this is *not* the only benefit of the matrix smoothness characterization, but an intuitive understanding nevertheless about why it should be better than the existing approaches.

The authors make use of this fact to propose smoothness-aware distributed methods with general unbiased compressors. They extend existing algorithms -- Distributed Compressed Gradient Descent (DCGD) of *Khirirat et al.* and DIANA *(Mischenko et al.)* and theoretically show benefits in the convergence rate, while also numerically verifying them. They then move on to concrete examples of unbiased compression, specifically non-subtractively dithered quantization. They propose **block quantization** and **quantization with varying steps**, and have solved optimization problems to determine the optimal number of quantization steps for each worker.

strengths_and_weaknesses: **Originality**: This work heavily relies on the work of *Safaryan et al.* that first proposed the matrix smoothness characterization and demonstrated its utility for random sparsification. Extension to general unbiased compressor is a natural extension to consider. Although the analysis of the proposed method is very similar to *Safaryan et al.*, the contributions are non-trivial. The authors have also clarified this already in Appendices **A.1** and **A.2**, highlighting the differences and the challenges in extending the work of *Safaryan et al.* to general unbiased compressors.

**Quality**: This work is pretty good. The authors have packed in a lot of ideas within 9 pages, which makes the presentation of the paper a little difficult to parse in some portions. Since this work is a generalization of Safaryan et al, some things are often not clear in a first reading. I was not aware of the work of Safaryan et al. and hence, had to go through that paper as well to appreciate this work. Although I understand it is difficult, the readers would appreciate if any paper is as self-contained as possible. Perhaps discuss important ideas like matrix smoothness on which you rely on in the appendix in more detail -- explaining the intuition, etc.  I have also reiterated this point in the *limitations* section of the review. I do have some more technical concerns that I have raised in the **Questions** section of the review.

**Clarity**: Although the work is original and non-trivial, I have several concerns about the presentation of the paper which I have listed below. Mostly they are minor, but I would appreciate if the authors address them.

1. In the abstract, the authors claim, "... our smoothness-aware quantization strategies outperform existing quantization schemes as well as the aforementioned smoothness-aware sparsification strategies with respect to **all relevant success measures** ...". "all relevant success measures" is an unnecessary phrase. The proposed smoothness aware strategies are not very efficient in terms of **computational complexity of preprocessing at the workers** (something the authors note in the Limitations section in Appendix **A.3**) as well as the memory requirements. The server needs to store the smoothness matrices of each worker separately -- for high-dimensional problems and a large number of workers this can be detrimental as it demands a $\mathcal{O}(nd^2)$ memory requirement. Perhaps rephrasing sentence to only include the metrics like *number of iterations*, *total amount of bits communicated*, and *wall-clock time* would be better.

2. In the characterization of unbiased compressors after line 73, $y$ is not required in $\forall x, y \in \mathbb{R}^d$.

3. The authors are sometimes inconsistent with their notations. The class of unbiased compressors is denoted as $\mathbb{B}(\omega)$, but in lines 85 and 118 for example, they add a superscript in $\mathbb{B}^d(\omega)$. The authors are requested to correct such typos.

4. In *Assumption 1*, the authors introduce the smoothness matrices $\mathbf{L}_i$ of the local loss functions $f_i$, and then state the $\mathbf{L}$-matrix smoothness of the global average function $f$. It is not clear if $\mathbf{L}$ is introduced for the first time as the smoothness matrix of the global objective $f$ here. Please mention it if that is the case. If $\mathbf{L}$ can be obtained from the local smoothness matrices $\mathbf{L}_i$, the authors are requested to mention that as well.

5. (I am not sure about this) In line 120, is *overparametrized* the correct term? Shouldn't the term *interpolation* be preferred? I guess a problem does not need to be overparametrized to satisfy $\nabla f_i(\mathbf{x^*}) = 0$ for all $i \in [n]$? Please correct me if I am mistaken.

6. (Line 122) (Just a mild suggestion regarding terminology) " ... we show later that the linear rate of DCGD+ can be much better than one of DCGD..." -- The convergence rate of an optimization algorithm is a function of the learning rate. The authors do not actually compare the linear convergence rate, but rather, the iteration complexity. Although they can be easily derived from one another, the iteration complexity is specified for a particular choice of learning rate (in this case, the maximum allowable learning rate is $\frac{1}{L + \frac{2}{n}\mathcal{L}_{max}}$). On the same note, in Theorem 2, the rate as a function of step-size $\gamma$ is not even mentioned in the statement, just the iteration complexity is mentioned. Please ensure consistency in whether you are comparing the convergence rate or the iteration complexity, and ensure uniformity of statements in Theorems 1 and 2.

7. (Lines 159 onwards) -- **Baseline for DCGD** Please mention the theorem/lemma from which the iteration complexity of DCGD, i.e. the expression $\mathcal{O}\left( \frac{L}{\mu} + \frac{\omega L_{max}}{n \mu} \right)$. Also, the authors mention, " ... optimal level of compression variance $\omega = \mathcal{O}(n)$" -- what is meant by "optimal" here and how is it derived -- please cite appropriately? Furthermore, the estimate of quantization variance $\omega = \text{min}\left( \frac{d}{s^2}, \frac{\sqrt{d}}{s} \right)$ is a consequence of the QSGD scheme of Alistarh et al. and the relevant theorem / lemma of that paper should be cited accordingly.

8. (Line 245) "complicated enough" --> "too complicated"

9. What is $D_f$ in the inequality after the equation in line 591? Is is the Bregman divergence between $x$ and $x^*$ with respect to $f$? Please mention. Could not find it in the table of notations either.

**Significance**: I agree that the work is significant enough for low-to-moderate dimensional optimization problems where the matrix smoothness structure can be exploited. Nevertheless, the domain of communication compression in distributed optimization is often motivated by the communication bottleneck of transmitting high dimensional vectors over a network. Does the proposed framework scale well enough for high dimensional problems? 
questions: The work is great and has enough theoretical and numerical simulations. However I have several concerns and I would appreciate if the authors addressed them. I would be more than happy to increase my review rating if they are appropriately addressed. They are as follows:

1. The intuition behind the importance of matrix smoothness for compression purposes makes sense. However, in the existing literature, the scalar $L$-smoothness assumption is utilized even in centralized optimization settings in the absence of any compression constraints. Does utilizing the matrix smoothness framework help in improving the convergence rates of uncompressed algorithms in any way? The matrix smoothness assumption was not natural to me after a first reading of this paper, so I resorted to reading the prior work of Safaryan et al. that introduced this notion. Safaryan et al. (https://arxiv.org/pdf/2102.07245.pdf) mention on Page 5 (first paragraph) -- *"Since the stepsizes and convergence rates of first-order methods depend on the smoothness constant(s) employed, convergence analysis relying on such crude approximation may be significantly suboptimal, and the methods too slow when implemented following the theory."* If this is the primary intuition behind the efficacy of matrix smoothness framework, shouldn't it also yield improved convergence rates for centralized optimization settings (without any compression) just because it allows for larger step sizes? The authors are requested to comment on this, and if they agree it is relevant, should probably discuss it somewhere in the paper.

2. In eq. (11) (after line 210), where does the $\beta$ come from? Although it is mentioned in the table of notations as a pre-specified parameter to which quantization is constrained, it should be introduced somewhere in the main paper as well. Moreover, in line (212), should it be $\frac{dT_{i,B}^2}{\beta - B}$ instead of $\frac{dT_{1,B}^2}{\beta - B}$ in the last term of the quadratic expression? Furthermore, even if it is a straightforward calculation, please mention how exactly do you arrive at the solution of (11) (perhaps in the appendix somewhere?)

3. In eq. (13), the first term of the objective function is $h_l \sqrt{d_l}$. This comes from the expression $\omega =  \text{min}\left( \frac{d}{s^2}, \frac{\sqrt{d}}{s} \right) = \text{min}\left( h^2d, h\sqrt{d} \right)$. For $h\sqrt{d}$ to be the minimum, we need $h\sqrt{d} \geq 1 \implies \frac{1}{h^2} \leq d$. Also, the constraint requires: $\Sigma_{l \in [B]} \left( \frac{1}{h_l^2} + \frac{\sqrt{d_l}}{h_l} \right) + B = \beta$. For a homogeneous setting where all local objective functions are the same $\mathbf{L}$-matrix smooth, this constraint becomes, $B \left( \frac{1}{h^2} + \frac{\sqrt{d}}{h} + 1 \right) = \beta \implies \beta \leq B (2d + 1)$. Moreover, since in Thm. 5, it is assumed that $\beta = \mathcal{O}(d/n)$, does this gives us any indication as to the regimes within which the proposed analysis will hold and the algorithm is provably beneficial? A straightforward answer may not be obvious, but since we already know that $n$ and $d$ cannot be too large (from the **Limitations** section owing to the increase in computational complexity) and the analysis further constrains the regimes where is it provably beneficial, the authors should add the discussion regarding this. On a similar note, the statement of Thm. 6 mentions "ignoring negligible term $n$". Is the number of workers ($n$) really negligible -- please justify?

4. In *block quantization*, the vector to be quantized is divided into blocks / subvectors and each block is treated independently, with each block having a (possibly) different quantization resolution. Isn't **quantization with varying steps** just not an extreme case of block quantization where each coordinate is a block by itself? Why does the analysis of *block quantization* simplify to that of *quantization with varying steps* for the choice of parameter $B = d$, where B is the number of blocks? Please justify why a separate analysis is necessary in Sec. 5 for quantization with varying steps.
limitations: The authors have adequately addresses the major limitations of this work in Sec. **A.3** of the appendix and I appreciate them adding this section, as computational complexity and memory requirements were a concern in my mind right from the beginning when I started reading this paper and got introduced to the notion of matrix smoothness. I imagine any reader in the audience would have similar concerns and hence Sec. A.3 is appreciated. Perhaps the authors could also add a footnote to the appendix somewhere in the main text of the paper. Apart from this, I have raised my other relevant concerns in **Strengths and Weaknesses** and **Questions** sections of the review. Once again, I would be more than happy to increase my scores if my concerns are addressed satisfactorily.
review_title: null

Meta-review: metareview: The reviewers are all in agreement that the paper passes the bar for acceptance, and no significant concerns remain following the review period.  Quite a few questions and concerns were raised in one of the original reviews, and the authors gave very detailed responses that the reviewer found to be sufficiently convincing.  The authors should carefully modify the paper in accordance with these comments/questions (and those of the other reviewers), particularly those of a technical nature.
confidence: Certain
Decision: Accept