On Johnson-Lindenstrauss Transforms for Byzantine-Robust Optimization

Aleksandr Shestakov; Vladimir Aletov; Aleksandr Beznosikov

cs.LGOct 20, 2026

On Johnson-Lindenstrauss Transforms for Byzantine-Robust Optimization

Authors: Aleksandr Shestakov, Vladimir Aletov, Aleksandr Beznosikov

Organizations: Basic Research of Artificial Intelligence Laboratory · MBZUAI · Federated Learning Problems Laboratory

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.

Figures & tables

Compressor	GPU, ms	CPU, ms	Peak, MB	Stored, MB	Uplink, MB
Gaussian JL, Kronecker (ours)	$6.5$	$155$	$92.5$	$69.9$	$21.3$
Rademacher JL, Kronecker (ours)	$8.1$	$160$	$92.5$	$69.9$	$21.3$
SRHT	$55.0$	$718$	$181.2$	$117.9$	$21.3$
SRFT	$12.7$	$659$	$131.1$	$63.9$	$21.3$
SRHT, whole vector †	$30.6$	$927$	$644.3$	$106.6$	$21.3$
SRFT, whole vector †	$8.8$	$693$	$432.0$	$64.0$	$21.3$

Table 1: Cost of applying each compressor to ResNet-18 parameters at

k/n=0.5

: compression and decompression time, peak memory, memory for the compressor state (Stored) and per-client uplink message size. JL compressors and PowerSGD are applied layer-wise, Rand-

k

to the flattened parameter vector; † applied to the flattened parameter vector.

		(a) random matrix $4096\times 4096$			(b) real ResNet-18 gradients
		20 draws of $(S,u,v)$ , mean $\pm$ std			100 pairs, mean $\pm$ std
Compressor	Variant	$k/n$	$\Delta_{\mathrm{ip}}$ , $10^{-4}$	$\Delta_{\theta}$ , deg	$k/n$	$\Delta_{\mathrm{ip}}$ , $10^{-4}$	$\Delta_{\theta}$ , deg
Kronecker JL (ours)	Rad.	$0.500$	$5.0\pm 4.5$	$0.011\pm 0.0090$	$0.500$	$194\pm 156$	$1.1\pm 1.7$
	Gauss.	$0.500$	$8.7\pm 8.3$	$0.017\pm 0.013$	$0.500$	$94\pm 86$	$0.8\pm 0.7$
SRHT	layer	$0.500$	$2.5\pm 1.9$	$0.0060\pm 0.0056$	$0.500$	$103\pm 80$	$0.55\pm 0.43$
	whole	–	–	–	$0.500$	$302\pm 251$	$1.31\pm 1.23$

Table 2: Distortion of inner products (

\Delta_{\mathrm{ip}}

) and angles (

\Delta_{\theta}

) under compression, mean

\pm

std. (a) Random

4096\times 4096

; (b) stochastic ResNet-18 gradient vs. trust-set gradient. All compressors use

k/n=0.5

; for Adaptive JL,

k/n

is set implicitly by the target

\varepsilon

from equation 12 .

Table 3

(a) best accuracy
Method	none	LF $60\%$	SF $60\%$	RG $40\%$	ALIE $60\%$	IPM $70\%$
FedAvg (Adam)	$0.917$	$0.276$	$0.331$	$0.132$	$0.145$	$0.100$
CC	$0.928$	$0.828$	$0.574$	$0.122$	$0.143$	$0.100$
CC + bucketing	$0.840$	$0.897$	$0.891$	$0.134$	$0.143$	$0.100$
CC + FBM	$0.924$	$0.855$	$0.892$	$0.116$	$0.184$	$0.100$
Safeguard	$0.921$	$0.104$	$0.858$	$0.132$	$0.113$	$0.137$

Table 5: Comparison with Byzantine-robust baselines under different attacks (Byzantine fraction in the header): (a) best test accuracy; (b) full-gradient uploads

G

to reach

60\%

test accuracy. Baselines are uncompressed; Grad-BANT + JL uses

k/n=0.5

. –: not reached.

Attack	IID	$\alpha=1.0$	$\alpha=0.5$	$\alpha=0.2$
No attack	$0.910$	$0.896$	$0.872$	$0.842$
Label flipping	$0.862$	$0.857$	$0.782$	$0.742$
Sign flipping	$0.878$	$0.871$	$0.832$	$0.753$
IPM	$0.827$	$0.826$	$0.699$	$0.669$

Table 6: Best test accuracy of Grad-BANT + JL (

k/n=0.5

) under heterogeneous data split by a Dirichlet distribution with concentration

\alpha

(smaller

\alpha

means stronger heterogeneity). Byzantine fractions:

60\%

for label and sign flipping,

70\%

for IPM.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Attack	Byzantine behavior	Byz. fraction
Label flipping (LF)	Data poisoning: Byzantine clients compute gradients on their local data with each label $y$ replaced by $C-1-y$ .	$40\%$ , $60\%$
Sign flipping (SF)	Byzantine clients send the negated honest gradient $-g_{i}$ .	$60\%$
Random gradients (RG)	Byzantine clients send random vectors with i.i.d. Gaussian entries, $\xi\sim\mathcal{N}(0,s^{2}I)$ .	$40\%$ , $60\%$
ALIE	Omniscient attack: Byzantine clients send $\bar{g}-z\,\sigma$ , a small coordinate-wise perturbation of the honest mean that stays within the spread of honest gradients and thus evades robust aggregation rules.	$60\%$
IPM	Omniscient attack: Byzantine clients send $-\epsilon\,\bar{g}$ with $\epsilon>0$ , so that the inner product between the aggregated update and the true gradient becomes negative.	$70\%$

Appendix

Table 7: Byzantine attacks used in the experiments. Here

g_{i}

denotes the stochastic gradient that an honest client

i

would send,

\bar{g}

and

\sigma

denote the coordinate-wise mean and standard deviation of the honest clients’ gradients, and

C

is the number of classes.

(a) size, all $10$ classes
Trust set	R $\to 60$	R $\to 80$	Best	Final
$100$	$21$	$61$	$0.844$	$0.683$
$500$	$21$	$65$	$0.841$	$0.674$
$1000$	$23$	$64$	$0.839$	$0.622$
$1500$	$22$	$65$	$0.840$	$0.835$
$2000$	$27$	$66$	$0.838$	$0.838$

Appendix

Table 8: Effect of the trust set on Grad-BANT + JL: (a) size; (b) distribution shift,

1500

images. R

\to 60

and R

\to 80

: rounds to reach

60\%

and

80\%

test accuracy; Best and Final: best and last-round accuracy; –: not reached. Label flipping,

60\%

Byzantine clients,

k/n=0.5

, IID data,

100

rounds.

Trust set	Epochs	@20	@50	@100	@200	Best
$100$	$7936$	$0.258\pm 0.019$	$0.260\pm 0.014$	$0.280\pm 0.012$	$0.270\pm 0.015$	$0.287\pm 0.010$
$500$	$1587$	$0.387\pm 0.021$	$0.407\pm 0.027$	$0.410\pm 0.046$	$0.428\pm 0.024$	$0.439\pm 0.023$
$1000$	$794$	$0.466\pm 0.015$	$0.496\pm 0.011$	$0.515\pm 0.016$	$0.501\pm 0.003$	$0.542\pm 0.012$
$1500$	$529$	$0.523\pm 0.017$	$0.554\pm 0.021$	$0.577\pm 0.015$	$0.578\pm 0.008$	$0.609\pm 0.006$
$2000$	$397$	$0.554\pm 0.015$	$0.607\pm 0.012$	$0.615\pm 0.012$	$0.628\pm 0.011$	$0.653\pm 0.004$

Appendix

Table 9: Training ResNet-18 on the trust set alone, without federation. @

r

: CIFAR-10 test accuracy after

62r

optimizer steps, i.e., the computation of one client over

r

rounds. Epochs: passes over the trust set. Mean

\pm

std over

3

seeds; each seed samples a different trust set. Federated training with the same trust set sizes reaches

0.89

–

0.92

(Table 8 (a)).

$k/n=0.5$
Compressor	Variant	$\Delta_{\mathrm{ip}}$ , $10^{-4}$	$\Delta_{\theta}$ , deg
Kronecker JL (ours)	Rad.	$194\pm 156$	$1.1\pm 1.7$
	Gauss.	$94\pm 86$	$0.8\pm 0.7$
SRHT	layer	$103\pm 80$	$0.55\pm 0.43$
	whole	$302\pm 251$	$1.31\pm 1.23$
SRFT	layer	$120\pm 125$	$0.63\pm 0.58$

Appendix

Table 10: Distortion of inner products (

\Delta_{\mathrm{ip}}

) and angles (

\Delta_{\theta}

) under compression at different compression rates: stochastic ResNet-18 gradient vs. trust-set gradient,

100

pairs, mean

\pm

std. The rows for

k/n=0.5

and for Adaptive JL are repeated from Table 2 . For Adaptive JL,

k/n=0.240

is set implicitly by the target

\varepsilon=0.3

from equation 12 .

(a) rounds to $80\%$
$k/n$	$0.9$	$0.7$	$0.5$	$0.3$	$0.1$
No attack	$54$	$45$	$41$	$45$	$73$
Label flipping $60\%$	$71$	$62$	$57$	$60$	$71$
Sign flipping $60\%$	$68$	$47$	$46$	$61$	$58$
IPM $70\%$	$68$	$56$	$48$	$51$	$68$
(b) traffic to $80\%$ , full-gradient uploads

Appendix

Table 11: Communication efficiency of Grad-BANT + JL for different compression rates

k/n

(IID data,

200

rounds, single seed): (a) rounds and (b) traffic in full-gradient uploads (a round costs

k/n

units) to reach

80\%

test accuracy; (c) best test accuracy. Columns

0.9

–

0.5

use Rademacher JL, columns

0.3

–

0.1

use Gaussian JL.

Robust Optimization

Robust optimization studies decisions that remain effective when data, models, or operating conditions are uncertain or adversarial.

See all 49 papers

Byzantine-Robust Optimization under $(L_0, L_1)$ -Smoothness
Mar 12, 2026Arman Bolatov, Samuel Horváth, Martin Takáč +1Distributed Optimization Byzantine-Robust Federated Learning
Mohamed bin Zayed University of Artificial Intelligence, UAE
Accelerating Byzantine-Robust Distributed Learning with Compressed Communication via Double Momentum and Variance Reduction
Mar 16, 2026Yanghao Li, Changxin Liu, Yuhao YiDistributed Optimization Communication-Efficient Distributed Training
Sichuan University · East China University of Science and Technology
Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout
Apr 1, 2026Amirhossein Dezhboro, Fateme Maleki, Arman Adibi +2Decentralized Optimization Stochastic Gradient Descent
Department of Systems Engineering, Stevens Institute of Technology, Hoboken, NJ 07030. · Department of Industrial and Systems Engineering, Rutgers University, Piscataway, NJ 08854. · School of Computer and Cyber Sciences, Augusta University, Augusta, GA 30912. +1

Mar 12, 2026J/K move · Enter open · S save

Byzantine-Robust Optimization under $(L_0, L_1)$ -Smoothness

Arman Bolatov, Samuel Horváth, Martin Takáč, Eduard Gorbunov

Mohamed bin Zayed University of Artificial Intelligence, UAE

Distributed Optimization Byzantine-Robust Federated Learning Stochastic Gradient Descent

Open paper AskPDF arXiv

We consider distributed optimization under Byzantine attacks in the presence of

(L_0,L_1)

-smoothness, a generalization of standard

L

-smoothness that captures functions with state-dependent gradient Lipschitz constants. We propose Byz-NSGDM, a normalized stochastic gradient descent method with momentum that achieves robustness against Byzantine workers while maintaining convergence guarantees. Our algorithm combines momentum normalization with Byzantine-robust aggregation enhanced by Nearest Neighbor Mixing (NNM) to handle both the challenges posed by

(L_0,L_1)

-smoothness and Byzantine adversaries. We prove that Byz-NSGDM achieves a convergence rate of

O(K^{-1/4})

up to a Byzantine bias floor proportional to the robustness coefficient and gradient heterogeneity. Experimental validation on heterogeneous MNIST classification, synthetic

(L_0,L_1)

-smooth optimization, and character-level language modeling with a small GPT model demonstrates the effectiveness of our approach against various Byzantine attack strategies. An ablation study further shows that Byz-NSGDM is robust across a wide range of momentum and learning rate choices.

Abstract

Robust Optimization

Explore similar work

Byzantine-Robust Optimization under (L0,L1)(L_0, L_1)(L0​,L1​)-Smoothness

Accelerating Byzantine-Robust Distributed Learning with Compressed Communication via Double Momentum and Variance Reduction

Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout

Byzantine-Robust Optimization under $(L_0, L_1)$ -Smoothness