Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new notion of smoothness called matrix smoothness which leads to better theory bounds and a data-dependent compression scheme. The compression scheme is applied to three existing algorithms resulting in improved convergence bounds in smooth and strongly convex setting. Simple experiments are done to show the effectiveness of the proposed scheme.
main_review: The idea of using smoothness matrices to improve convergence bounds as well as perform data-dependent compression seems novel but kind of infeasible for large-scale problems (see next section). Theoretically, the proposed scheme seems to offer a significant speed-up when importance sampling is used. The paper is reasonably well-written. Some comments:
1) Since you consider strongly convex and smooth objectives, it’d be good to show how much speed-up you get in practice vs. how much you expect theoretically.
2) Is it possible to give an estimate of the speed-up when you use uniform sampling and not importance sampling?
3) In Theorem 2 for DCGD+, sigma^{*} can become large if $L_i^{*}$ is poorly conditioned (then the max eigenvalue of its inverse will become large)?
4) line 195 - typo “compression”
Please see my concerns in the next section.
limitations_and_societal_impact: I have concerns about the feasibility of the proposed method. First, I expect it’d be hard to estimate the matrices $\mathbb{L}_i$ especially in high-dimensional deep learning settings. Second, modern ReLU networks don’t satisfy smoothness so this method may not be applicable there. It’d be nice to know if it can be extended for non-convex and non-smooth deep learning problems. The proposed compression scheme would probably increase per-client or per-device computation because you need to invert the $L_i$’s.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes several optimization concepts: compression, variance reduction, and acceleration, using the assumption of smoothness matrices rather than the smoothness parameter. Sketching matrices are designed as sum_{i\in S} L^{1/2}_i c_i * L^{1/2,dagger}_i where L_i is the "smoothness matrix" associated with the ith data sample. Taking this additional information into account, which for generalized linear models is not too hard to compute, it is suggested that there can be a factor of min(n,d) improvement in unaccelerated methods and sqrt(min(m,n)) benefit in accelerated methods. 
main_review: This work is interesting, and though the contribution feels incremental, the L_i matrices are indeed not complicated to precompute for most applications. Overall, the writing is fairly clean and the results do seem novel, though it is unclear to me if they are a bit incremental, as it seems to be not that much of an improvement over using leverage scores. 

The one big weakness is that it seems most of the paper is actually in a 50 page appendix, which is not just extra experiments and a few lengthy proofs, but quite a bit of clarifying text and interpretations as well. Moreover many of the proofs pushed to the appendix are short, so it is not the lengthiness of the proofs that is causing such a big appendix. The impact is that while I can check a few pages of the appendix, I cannot reasonably judge all 50 pages in this short review period, nor do I think that is fair compared to the other works that squeezed all the big ideas in the first 8 pages. At the very least, the authors should condense their main story to clearly and succinctly outline how to get their main constant factor improvements. That being said, the parts I was able to read seem reasonable; the proof techniques seem standard and the results follow expected trends. 

Specific critiques:
 - The definition of L_i in (5) should be rank m_i for problems like logistic regression, but could be of higher rank in a neural network model. These two regimes seem a bit separate: sketching should make a big impact in shallow models (like logistic regression) but in the extreme case of m_i = 1, L_i matrix shouldn't be that much more handy than L_i scalar, and it seems that this is somewhat the example shown in the experimental results. On the other hand, a deep model that can overfit may have a more complex L_i. Am I misinterpreting this? Are the experiments using L_i that have more interesting rank? These details should be included in the main paper, not in the appendix. 

 - Are the results significantly better than using leverage scores? What are the main scenarios where this method would give benefit? 

 - Can the authors point to a specific scenario where L_i the matrix is giving a significant benefit over L_i a smoothness constant? e.g. give a specific sparsification scheme that is used in practice, or a dataset type with such features in the data matrix? 
limitations_and_societal_impact: No negative societal impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The papers consider the standard distributed optimization scenarios, where a server wants to minimize the average of $n$ loss functions, which are evenly distributed across $n$ participating worker nodes. Typically, optimization problems designed for such distributed optimization scenarios assume a blanket smoothness constant for the average and the individual functions involved. Instead, the authors consider the notion of matrix smoothness, where the distance between the points in defining the smoothness is measured with matrix norm (of a smoothness matrix). Under the assumption that the individual loss function satisfies matrix smoothness with different matrices, the authors design compression algorithms using these smoothness matrices and then use them in conjunction with various distributed optimization algorithms. The authors show that as a result of their smoothness-aware compression, they improve over the convergence guarantees of the standard baseline algorithms considered, namely, DCGD, DIANA, ADIANA.
main_review: Originality:

  a) The notion of matrix smoothness considered in this paper is a novel one. None of the present distributed algorithms have exploited loss function smoothness to this granularity to the best of my knowledge. As the authors show, this notion can further improve the performance of distributed optimization algorithms.

  b) The compression operator proposed is tailored to the smoothness matrix of the loss function and therefore improves over the performance of generic compression operators proposed in the literature.
 
 c) The distributed optimization algorithms used by the authors seem to only differ in the compression part with respect to the ones present in the literature.

Presentation:

a) The paper's presentation is excellent. The introduction clearly mentions the paper's main ideas, contributions, and comparison to prior work.

 b) A minor point would be to clarify if the authors introduce the notion of matrix smoothness or was it already present in the literature. (Either way, my review would remain unchanged based on this point, but it will be instructive for the reader.)


Significance: 

 a) The idea of using smoothness to this granularity is a novel one and can significantly improve the performance of distributed optimization algorithms.  However, it is unclear to me how the precise smoothness matrix could be identified for complicated loss 
functions. 

b) This work could also inspire other research works to explore other properties of functions to this granularity (e.g., Strong Convexity).

To summarize, I like this paper and recommend that it be accepted.


limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The authors are in general positive agreement as to both the theoretical and empirical contributions of this paper. I would recommend this be accepted.
Decision: Accept (Poster)