betaFeedback

WorksComputer Science

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.

Introduction

The growing scale of data and computational demands of machine learning [1] have motivated distributed optimization methods [2] for the global objective

min⁡x∈Rn{f(x)=1G∑i∈Gfi(x)},(1)\min_{x \in\mathbb{R}^{n}} \left\{ f(x) = \frac{1}{G} \sum_{i \in\mathcal{G}} f_i(x) \right\}, \tag*{(1)}

where fif_i denotes the local loss at worker ii, G⊆{1,…,M}\mathcal{G} \subseteq\{1, \ldots, M\} is the fixed set of honest workers, and G=∣G∣≥1G = |\mathcal{G}| \ge1. The objective is the average loss over the honest workers, whose identities need not be known to the server; when all workers are honest, it reduces to the usual average over all MM workers. Distributed methods make large-scale training tractable when a single machine is insufficient, but introduce communication bottlenecks, synchronization overhead, and bandwidth limitations that can substantially hinder performance [3].

To mitigate the communication cost, a broad range of compression techniques has been proposed [4, 5], such as quantization [6], which lowers numerical precision, and sparsification [7], which communicates only the most informative coordinates. Workers transmit either compressed gradients [5] or auxiliary sequences that compensate for compression errors across iterations [8, 9, 10]. In both cases, the gradient estimator is obtained by averaging compressed vectors.

However, some distributed setups rely not on the mean itself, but on geometric relations between gradients. A prominent example is Byzantine-robust optimization [11], in which Byzantine workers attempt to derail training by sending arbitrary adversarial messages. One remedy is to assign reliability weights to workers [12], computed from inner products of local gradients with a trusted reference gradient [13, 14], so that workers not aligned with the reference direction are suppressed:

ωit=max⁡{⟨∇fi(xt),∇f0(xt)⟩,0}∑j=1Mmax⁡{⟨∇fj(xt),∇f0(xt)⟩,0},xt+1=xt−γ∑i=1Mωit∇fi(xt),(2)\omega_i^t = \frac{\max\left\{ \left\langle\nabla f_i(x^t), \nabla f_0(x^t) \right\rangle, 0 \right\}}{\sum_{j=1}^{M} \max\left\{ \left\langle\nabla f_j(x^t), \nabla f_0(x^t) \right\rangle, 0 \right\}}, \qquad x^{t+1} = x^t - \gamma\sum_{i=1}^{M} \omega_i^t \nabla f_i(x^t), \tag*{(2)}

where f0f_0 is a loss function defined on a trusted device. In this illustrative update, the iterate is left unchanged if the denominator is zero, and Byzantine workers may replace their gradients by arbitrary messages. Such methods depend on preserving ℓ2\ell_2-geometry rather than exact coordinate values, which motivates compression operators that approximately preserve Euclidean structure. Johnson–Lindenstrauss (JL) transforms [15] map high-dimensional vectors into a lower-dimensional space while approximately preserving pairwise distances and inner products. We focus on stochastic JL transforms, as they are simple to implement in practice. They have been successfully applied in nearest-neighbor search [16, 17], random partitioning [18], linear regression [19, 20], clustering [21, 22, 23, 24, 25, 26], differential privacy [27, 28], and numerical linear algebra [29, 30, 31].

In distributed optimization and federated learning, however, JL transforms have mostly been treated as unbiased sketching operators [32, 33, 34], leading to guarantees in expectation, or derandomized [35]. These works do not capitalize on the preservation of distances and inner products, and thus do not clearly distinguish JL transforms from standard sparsification or sketching schemes.

Our contributions. In this paper, we

  • Propose a JL-based communication mechanism for Byzantine-robust distributed optimization methods that rely on gradient alignment with a trusted reference gradient;

  • Use high-probability control of compressed honest gradients to derive convergence guarantees without convexity, under average data similarity and an explicit accuracy condition on the trusted reference gradient;

  • Validate our theoretical findings experimentally and demonstrate the practical effectiveness of the proposed approach.

Proposed Algorithm

Notation

We equip Rn\mathbb{R}^n with the standard Euclidean norm, ∥x∥≔⟨x,x⟩1/2\lVert x\rVert\coloneqq\langle x,x\rangle^{1/2}, x∈Rnx \in\mathbb{R}^n. Throughout the paper, f:Rn→Rf:\mathbb{R}^n \to\mathbb{R} denotes a differentiable objective function.

Assumption 1 (Smoothness) Differentiable function f0f_0 has LL-Lipschitz gradient for some L>0L > 0, i.e.

∥∇f0(x)−∇f0(y)∥≤L∥x−y∥∀x,y∈Rn.(3)\lVert\nabla f_0(x) - \nabla f_0(y)\rVert\le L\lVert x-y\rVert\quad\forall x,y \in\mathbb{R}^n. \tag*{(3)}

Moreover, f0inf⁡≔inf⁡x∈Rnf0(x)>−∞f_0^{\inf} \coloneqq\inf_{x\in\mathbb{R}^n} f_0(x) > -\infty.

JL Transforms

Definition 1 (JL Transform [15]) Given ε,δ∈(0,1)\varepsilon,\delta\in(0,1), a stochastic mapping h:Rn→Rkh:\mathbb{R}^n \to\mathbb{R}^k is called a JL transform if, for all u,v∈Rnu,v \in\mathbb{R}^n,

P[(1−ε)∥u−v∥2≤∥h(u)−h(v)∥2≤(1+ε)∥u−v∥2]≥1−δ.(4)\mathbb{P}\left[(1-\varepsilon)\lVert u-v\rVert^2 \le\lVert h(u)-h(v)\rVert^2 \le(1+\varepsilon)\lVert u-v\rVert^2\right] \ge1-\delta. \tag*{(4)}

In words, a JL transform preserves all pairwise distances up to a factor 1±ε1 \pm\varepsilon with probability at least 1−δ1-\delta, while reducing the dimension from nn to kk. If hh is linear, then h(0)=0h(0)=0, and taking v=0v=0 shows that norms are preserved as well: (1−ε)∥u∥2≤∥h(u)∥2≤(1+ε)∥u∥2(1-\varepsilon)\lVert u\rVert^2 \le\lVert h(u)\rVert^2 \le(1+\varepsilon)\lVert u\rVert^2. Since ⟨u,v⟩=14(∥u+v∥2−∥u−v∥2)\langle u,v\rangle= \frac{1}{4}\left(\lVert u+v\rVert^2-\lVert u-v\rVert^2\right), preserving the norms of u+vu+v and u−vu-v also preserves inner products.

Lemma 1. If hh is a linear JL Transform, then P[∣⟨h(u),h(v)⟩−⟨u,v⟩∣≤ε∥u∥∥v∥]≥1−2δ\mathbb{P}\left[\left|\langle h(u),h(v)\rangle-\langle u,v\rangle\right|\leq\varepsilon\lVert u\rVert\lVert v\rVert\right]\geq1-2\delta for all u,v∈Rnu,v\in\mathbb{R}^{n}.

We consider two standard linear constructions.

Definition 2 (Gaussian JL matrix). S∈Rk×nS\in\mathbb{R}^{k\times n} with i.i.d. entries [S]ij∼N(0,1k)[S]_{ij}\sim\mathcal{N}\left(0,\frac{1}{k}\right).

Definition 3 (Rademacher JL matrix). S∈Rk×nS\in\mathbb{R}^{k\times n} with i.i.d. entries [S]ij=±1k[S]_{ij}=\pm\frac{1}{\sqrt{k}}, each with probability 12\frac{1}{2}.

Both are JL transforms with distortion ε∈(0,1)\varepsilon\in(0,1) and failure probability δ∈(0,1)\delta\in(0,1) whenever k≥Cε−2log⁡(2/δ)k\geq C\varepsilon^{-2}\log(2/\delta), where C>0C>0 is a universal constant [36, 37]. To return to Rn\mathbb{R}^{n} for the optimization update, we use the lifted operator

JL⁡S(x):=STSx∈Rn.\operatorname{JL}_{S}(x)\mathrel{\mathop:}=S^{\mathsf{T}}Sx\in\mathbb{R}^{n}.

Lemma 2 (Unbiasedness). For SS as in Definitions 2 and 3, EJL⁡S(x)=x\mathbb{E}\operatorname{JL}_{S}(x)=x for all x∈Rnx\in\mathbb{R}^{n}.

Lemma 3 (Second moment). For all x∈Rnx\in\mathbb{R}^{n}, E∥JL⁡S(x)∥2=n+k+1k∥x∥2\mathbb{E}\lVert\operatorname{JL}_{S}(x)\rVert^{2}=\frac{n+k+1}{k}\lVert x\rVert^{2} for Gaussian and E∥JL⁡S(x)∥2=n+k−1k∥x∥2\mathbb{E}\lVert\operatorname{JL}_{S}(x)\rVert^{2}=\frac{n+k-1}{k}\lVert x\rVert^{2} for Rademacher SS.

Thus JL⁡S\operatorname{JL}_{S} resembles unbiased sparsification such as Randk, C(x)=nk∑i∈IxieiC(x)=\frac{n}{k}\sum_{i\in I}x_{i}e_{i} with I⊂[n]I\subset[n] a uniformly random subset of size kk, which is also unbiased with variance of order nk\frac{n}{k} [38]. The key distinction is that the transmitted message of Randk, hC(x):=nk(xi)i∈I∈Rkh_{C}(x)\mathrel{\mathop:}=\sqrt{\frac{n}{k}}(x_{i})_{i\in I}\in\mathbb{R}^{k} (so that C=hCThCC=h_{C}^{\mathsf{T}}h_{C}, just as JL⁡S=STS\operatorname{JL}_{S}=S^{\mathsf{T}}S), does not preserve norms with high probability. By linearity, the JL property for hCh_{C} reduces to P[∣∥hC(x)∥2/∥x∥2−1∣≤ε]≥1−δ\mathbb{P}\left[\left|\lVert h_{C}(x)\rVert^{2}/\lVert x\rVert^{2}-1\right|\leq\varepsilon\right]\geq1-\delta for all x∈Rn∖{0}x\in\mathbb{R}^{n}\setminus\{0\}. For x=e1x=e_{1} the ratio is 00 with probability 1−kn1-\frac{k}{n}, forcing δ≥1−kn\delta\geq1-\frac{k}{n}.

Lemma 4 (Operator-norm bound [39]). For SS as in Definitions 2 or 3, there exists a universal constant c>0c>0, independent of nn and kk, such that, with probability at least 1−δ1-\delta,

∥S∥≤1+cnk+clog⁡(2/δ)k.(5)\lVert S\rVert\leq1+c\sqrt{\frac{n}{k}}+c\sqrt{\frac{\log(2/\delta)}{k}}. \tag*{(5)}

Consequently, on the same event, ∥JL⁡S(x)∥2≤(1+cnk+clog⁡(2/δ)k)4∥x∥2\lVert\operatorname{JL}_{S}(x)\rVert^{2}\leq\left(1+c\sqrt{\frac{n}{k}}+c\sqrt{\frac{\log(2/\delta)}{k}}\right)^{4}\lVert x\rVert^{2} for every x∈Rnx\in\mathbb{R}^{n}.

The operator norm controls the lifted update, while the JL property controls the geometry of fixed vectors in the compressed space; the high-probability analysis uses both.

Grad-BANT

References

  1. [1]Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends® in machine learning, 14(1–2):1–210, 2021.arxiv.org/abs/1912.04977
  2. [2]Zhenheng Tang, Shaohuai Shi, Wei Wang, Bo Li, and Xiaowen Chu. Communication-efficient distributed deep learning: A comprehensive survey. arXiv preprint arXiv:2003.06307, 2020.arxiv.org/abs/2003.06307
  3. [3]Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.02189, 2019.arxiv.org/abs/1907.02189
  4. [4]Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.arxiv.org/abs/1602.05629
  5. [5]Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
  6. [6]Yue Yu, Jiaxiang Wu, and Longbo Huang. Double quantization for communication-efficient distributed optimization. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1805.10111
  7. [7]Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-efficient distributed optimization. Advances in Neural Information Processing Systems, 31, 2018.
  8. [8]Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252–3261. PMLR, 2019.arxiv.org/abs/1901.09847
  9. [9]Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34:4384–4396, 2021.arxiv.org/abs/2106.05203
  10. [10]Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. Optimization Methods and Software, pages 1–16, 2024.
  11. [11]Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International conference on machine learning, pages 5311–5319. PMLR, 2021.arxiv.org/abs/2012.10333
  12. [12]Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robust federated learning via trust bootstrapping. arXiv preprint arXiv:2012.13995, 2020.arxiv.org/abs/2012.13995
  13. [13]Haonan Yan, Wenjing Zhang, Qian Chen, Xiaoguang Li, Wenhai Sun, Hui Li, and Xiaodong Lin. Recess vaccine for federated learning: Proactive defense against model poisoning attacks. Advances in Neural Information Processing Systems, 36:8702–8713, 2023.arxiv.org/abs/2310.05431
  14. [14]Gleb Molodtsov, Daniil Medyakov, Sergey Skorik, Nikolas Khachaturov, Shahane Tigranyan, Vladimir Aletov, Aram Avetisyan, Martin Takáč, and Aleksandr Beznosikov. Trial and trust: Addressing byzantine attacks with comprehensive defense strategy. arXiv preprint arXiv:2505.07614, 2025.
  15. [15]William B Johnson, Joram Lindenstrauss, et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
  16. [16]Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 614–623, 1998.
  17. [17]Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal lsh for angular distance. Advances in neural information processing systems, 28, 2015.arxiv.org/abs/1509.02897
  18. [18]Jon M Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 599–608, 1997.DOI
  19. [19]Christina Heinze, Brian McWilliams, and Nicolai Meinshausen. Dual-loco: Distributing statistical estimation using random projections. In Artificial intelligence and statistics, pages 875–883. PMLR, 2016.arxiv.org/abs/1506.02554
  20. [20]Gian-Andrea Thanei, Christina Heinze, and Nicolai Meinshausen. Random projections for large-scale regression. Big and Complex Data Analysis: Methodologies and Applications, pages 51–68, 2017.arxiv.org/abs/1701.05325
  21. [21]Bin Tang, Michael Shepherd, Malcolm I Heywood, and Xiao Luo. Comparing dimension reduction techniques for document clustering. In Advances in Artificial Intelligence: 18th Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2005, Victoria, Canada, May 9-11, 2005. Proceedings 18, pages 292–296. Springer, 2005.
  22. [22]Christos Boutsidis, Anastasios Zou zias, and Petros Drineas. Random projections for k-means clustering. Advances in neural information processing systems, 23, 2010.arxiv.org/abs/1011.4632
  23. [23]Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 634–644. IEEE, 1999.
  24. [24]Thierry Urruty, Chabane Djeraba, and Dan A Simovici. Clustering by random projections. In Advances in Data Mining. Theoretical Aspects and Applications: 7th Industrial Conference, ICDM 2007, Leipzig, Germany, July 14-18, 2007. Proceedings 7, pages 107–119. Springer, 2007.DOI
  25. [25]Reinhard Heckel, Michael Tschannen, and Helmut Bölcskei. Dimensionality-reduced subspace clustering. Information and Inference: A Journal of the IMA, 6(3):246–283, 2017.arxiv.org/abs/1507.07105
  26. [26]Xiao Guo, Yixuan Qiu, Hai Zhang, and Xiangyu Chang. Randomized spectral co-clustering for large-scale directed networks. arXiv preprint arXiv:2004.12164, 2020.
  27. [27]Jalaj Upadhyay. Randomness efficient fast-johnson-lindenstrauss transform with applications in differential privacy and compressed sensing. arXiv preprint arXiv:1410.2470, 2014.
  28. [28]Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pages 3105–3114. PMLR, 2017.
  29. [29]David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.
  30. [30]Cameron Musco and Christopher Musco. Projection-cost-preserving sketches: Proof strategies and constructions. arXiv preprint arXiv:2004.08434, 2020.arxiv.org/abs/2004.08434
  31. [31]Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06), pages 143–152. IEEE, 2006.DOI
  32. [32]Zhao Song, Zheng Yu, and Lichen Zhang. Iterative sketching and its application to federated learning. 2021.
  33. [33]Mayank Shrivastava, Berivan Isik, Qiaobo Li, Sanmi Koyejo, and Arindam Banerjee. Sketching for distributed deep learning: A sharper analysis. Advances in Neural Information Processing Systems, 37:6417–6447, 2024.DOI
  34. [34]Xinyan Dai, Xiao Yan, Kaiwen Zhou, Han Yang, Kelvin KW Ng, James Cheng, and Yu Fan. Hyper-sphere quantization: Communication-efficient sgd for federated learning. arXiv preprint arXiv:1911.04655, 2019.arxiv.org/abs/1911.04655
  35. [35]Jayadev Acharya, Chris De Sa, Dylan Foster, and Karthik Sridharan. Distributed learning with sublinear communication. In International Conference on Machine Learning, pages 40–50. PMLR, 2019.arxiv.org/abs/1902.11259
  36. [36]Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60–65, 2003.
  37. [37]Dimitris Achlioptas. Database-friendly random projections: Johnson-lindenstrauss with binary coins. Journal of computer and System Sciences, 66(4):671–687, 2003.
  38. [38]Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1–50, 2023.
  39. [39]Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2 edition, 2026.
  40. [40]Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson-lindenstrauss transform. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pages 557–563, 2006.
  41. [41]Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02):115–126, 2011.arxiv.org/abs/1011.1595
  42. [42]Nir Ailon and Edo Liberty. An almost optimal unrestricted fast johnson-lindenstrauss transform. ACM Transactions on Algorithms, 9(3):1–12, 2013.
  43. [43]Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693–703. Springer, 2002.
  44. [44]Kenneth L Clarkson and David P Woodruff. Low rank approximation and regression in input sparsity time. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 81–90, 2013.
  45. [45]Daniel M Kane and Jelani Nelson. Sparser johnson-lindenstrauss transforms. Journal of the ACM, 61(1):1–23, 2014.
  46. [46]Ahmad Rammal, Kaja Gruntkowska, Nikita Fedin, Eduard Gorbunov, and Peter Richtárik. Communication compression for byzantine robust learning: New efficient algorithms and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 1207–1215. PMLR, 2024.arxiv.org/abs/2310.09804

Paper details

vlnc:W_cq2vsp6m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents