acceptodds
Under review as a conference paper at ICLR 2027

On Johnson-Lindenstrauss Transforms for Byzantine-Robust Optimization

Abstract

The growing scale of data and models in machine learning calls for efficient optimization methods. Distributed optimization addresses this challenge, with compression mechanisms helping to reduce communication costs. A classical tool for dimensionality reduction is the Johnson-Lindenstrauss (JL) transform, which is simple to implement and offers strong geometric guarantees. In particular, JL transforms approximately preserve inner products and pairwise distances between vectors with high probability. In this paper, we exploit this property in Byzantine-robust optimization, where worker messages are weighted according to their alignment with a trusted reference gradient. We further support our theoretical findings with experimental results.

Primary area:
optimization
Keywords:
byzantine-robust optimization, random sketches

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_PfnXOpenReview ↗
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
  1. 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)?
  2. 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.
  3. 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.
  4. “measurable y_i^t”… what does that mean in the context of a vector? “Measurable” usually refers to a set or a function.
  5. Does “sketch seed” mean the seed used to generate S_t? How big is it?
  6. “Since f is their average” appears incorrect, it is generally not true that 1/G sum_i f_i =f.
  7. Please explain the equality in (7).
  8. “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?
  9. Theorem 3.1: In which conditions is the given assumption correct? Does this assumption relate to the JL condition?
  10. 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?
Reviewer_NddeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper adds compression to Byzantine robust training, where the server uses a small trusted dataset to score workers. Workers send JL sketched gradients, which keep inner products with high probability. Author argues Rand k only keeps them on average. The paper proves a high-probability convergence bound for dense Gaussian or Rademacher sketches. Experiments use ResNet18 on CIFAR10 with 10 clients and up to 60% Byzantine workers.

Critical strengths

Trust score defences need inner products that hold on each draw, not just on average. Authors provide this HDP type guarantee. Byzantine gradients need no JL guarantee because of the trusted dataset setting.

Critical weaknesses

Major issue: The theory shows no communication saving. The step size scales as 1/ρ≈k/n1/\rho \approx k/n, so total uplink is Ω(n)\Omega(n), which is no better than no compression. The bound also comes only from descent on f0f_0, so training on the trusted data alone gives the same guarantee. The workers add nothing in theory.

There is no uncompressed ablation of what authors have proposed.

Questions for authors

What is the total communication needed to reach ϵ\epsilon accuracy? Is it ever less than without compression?

Can you show in theory that the workers help beyond training on f0f_0 alone?

How does Grad-BANT do without compression? How is LL set in practice?

What sketch sizes are used per layer, and what ε\varepsilon does Theorem 3.3 give at those sizes?

Reviewer_HZZNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies Byzantine-robust distributed optimization with compressed uplink communication and a trusted reference objective. In Grad-BANT, honest workers transmit sketches of their gradients. The server scores the received messages using trusted-gradient alignment and a quadratic penalty, and aggregates messages with positive scores.

Theorem 2.11 establishes a finite-horizon, high-probability stationarity guarantee for Gaussian and Rademacher sketches under reference-accuracy and honest-worker heterogeneity assumptions. The paper also discusses structured implementations and evaluates compressor geometry, Byzantine attacks, and trust-set sensitivity.

Critical strengths
  1. The trusted-descent mechanism supports a meaningful adaptive robustness guarantee.

The quadratic score provides a deterministic safeguard for arbitrary received messages. The proof separates this safeguard from concentration of the honest/reference quantities, allowing Byzantine messages to depend on the current sketch and honest messages. This is a useful feature of the analysis (Algorithm 1; Theorem 2.11; Appendix D).

  1. The experiments include relevant diagnostics for a trusted-reference method.

The paper examines compressor distortion, computational cost, attack behavior, trust-set size, and class coverage. The trust-only baseline and the deterioration under inadequate reference-data coverage are particularly useful for understanding when the method can help and where it is sensitive (Tables 1–3 and 8–9).

Critical weaknesses
  1. The theorem does not yet establish an overall communication advantage.

In Theorem 2.11, the admissible stepsize decreases with the reconstruction factor (\rho). Taking (\gamma=s/\rho), with a fixed feasible (s), keeps the residual terms fixed but makes the sufficient iteration count for a fixed target accuracy proportional to (\rho). In the strong-compression regime allowed by the theorem, (\rho) scales as (n/k). Consequently, the leading total-uplink bound contains (Mk\rho), which remains of order (Mn).

This is a limitation of the available upper bound, rather than an impossibility result for practical savings. Nevertheless, a clearer comparison with the (S_t=I) specialization is needed to explain what overall communication benefit follows from the analysis, beyond transmitting fewer coordinates in each round.

  1. The experimental implementation and controls do not sufficiently isolate the compression benefit.

Algorithm 1 uses exact gradients and a specified score-weighted update, while the experimental descriptions refer to stochastic gradients and Adam. The paper should state precisely what is transmitted, where Adam is applied, and how the coefficient (L\gamma) in the quadratic score is selected.

It is also unclear whether any TS baseline in Table 5 is exactly the same implementation with (S_t=I). Moreover, Table 11 changes both the compression ratio and the compressor family: its caption specifies Rademacher JL for ratios 0.9–0.5 and Gaussian JL for 0.3–0.1. Together with the single-seed evaluation in that table, this makes the effect of compression strength difficult to isolate. A fixed-family sweep, a clearly matched uncompressed control, and variability across runs would materially strengthen the empirical conclusion.

Questions for authors
  1. What total-uplink complexity follows from Theorem 2.11 relative to its (S_t=I) specialization after accounting for the dependence of the stepsize on (\rho)?

  2. What exactly is transmitted in the experiments, where is Adam applied, and how is (L\gamma) chosen? Experimental pseudocode would help.

  3. Does one of the TS baselines implement uncompressed Grad-BANT? Can the compression-rate study hold the compressor family fixed and report variability across seeds?

  4. Please reconcile the Table 8/Table 9 accuracies, correct the unresolved Table 10 entry, and clarify the communication normalization.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.