- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper addresses distributed gradient descent with Byzantine workers, and applies a standard technique of weighing the gradient updates according to their deviation from a reference gradient, under the intuition that this would diminish the contribution of workers which attempt to disrupt the gradient descent algorithm. The novelty is in compressing the partial gradients using JL, an inner-product-preserving transform. The authors analyze the convergence under several assumptions about the distribution of partial gradients, discuss several efficient implementations such as applying the compression transform in a batched or sparse manner, and discuss matrix/tensor extensions. Several experiments are done, which support the claim that the JL transform performs well.
Critical strengths
The paper utilizes the JL transform in a relevant application domain.
Critical weaknesses
• The main weakness I identified is the apparent non-necessity of comparing the sketch of the reference gradient against the sketch of the partial gradient. If the partial gradient is decompressed anyway (when computing u_i^t), it seems to make more sense to compare it against the full reference gradient, not against its sketched version.
• The algorithm requires a trusted server, and no discussion is made regarding what that means or how that affects the communication or trust issues in the system.
• The per-layer, sparse, and tensor extension of the main scheme are nice to have, but are rather straightforward.
• A seed for the sketching matrix must be communicated to every worker at each iteration. A discussion regarding the overhead of transmitting the seed appears missing.
• The necessity of using the JL transform (or for that matter, any inner-product preserving transform) is not clear. Why can’t the workers use any lossy-compression algorithm (PCA, Lempel-Ziv, etc.), then the server would decompress the partial gradient and compare against the full reference gradient? The convergence would then be easier to analyze, simply as a function of decompression loss: if compressing and decompressing v results in v+epsilon, then one would only need to analyze the size of <epsilon,u> in the estimation of <u,v+epsilon>. Additional concerns arise regarding complexity, see below.
Questions for authors
- Can you explain why you compare sketches in line 7 of Algorithm 1 instead of comparing u_i^t (which is computed anyway) against the full reference gradient \nabla f_0? Would this alternative method have smaller complexity (since \nabla f_0 would not need to be compressed) and smaller error (again since \nabla f_0 is not compressed)?
- What is the importance of inner-product-preservation? Why can’t the workers employ any lossy-compression algorithm on the partial gradient and send to the server, which would in turn decompress and compare against the full reference gradient? This approach seems to broaden the spectrum of possible compression algorithms significantly, would not need to communicate a seed, and might result in better convergence guarantees.
- Algorithm 1: Missing quantifier on i, in the parameters, and in lines 9 and 11. Is that for all i? Also, T not given as parameter.
- “measurable y_i^t”… what does that mean in the context of a vector? “Measurable” usually refers to a set or a function.
- Does “sketch seed” mean the seed used to generate S_t? How big is it?
- “Since f is their average” appears incorrect, it is generally not true that 1/G sum_i f_i =f.
- Please explain the equality in (7).
- “Per-layer sketching” – The proposed method appears to be a partitioning approach, where different entries of x are grouped together and sketched together using a smaller sketching matrix S_i. Is there any reason to group weight by layer, vs. grouping them in any other way? If not, what would be the best way to group the weights?
- Theorem 3.1: In which conditions is the given assumption correct? Does this assumption relate to the JL condition?
- Similar to the unclear condition in Theorem 3.1, could you explain the condition under the probability in Theorem 3.3? It appears to bound the norm difference between the compressed and non-compressed versions of X, and not the difference between the compressions of two different tensors as required in the JL condition, and as required in Algorithm 1. Can you explain how this alternative condition aids in performing Algorithm 1?