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 ∈ R n { f ( x ) = 1 G ∑ i ∈ G f i ( 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)} x ∈ R n min { f ( x ) = G 1 i ∈ G ∑ f i ( x ) } , (1)
where f i f_i f i denotes the local loss at worker i i i , G ⊆ { 1 , … , M } \mathcal{G} \subseteq\{1, \ldots, M\} G ⊆ { 1 , … , M } is the fixed set of honest workers, and G = ∣ G ∣ ≥ 1 G = |\mathcal{G}| \ge1 G = ∣ G ∣ ≥ 1 . 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 M M M 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:
ω i t = max { ⟨ ∇ f i ( x t ) , ∇ f 0 ( x t ) ⟩ , 0 } ∑ j = 1 M max { ⟨ ∇ f j ( x t ) , ∇ f 0 ( x t ) ⟩ , 0 } , x t + 1 = x t − γ ∑ i = 1 M ω i t ∇ f i ( x t ) , (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)} ω i t = ∑ j = 1 M max { ⟨ ∇ f j ( x t ) , ∇ f 0 ( x t ) ⟩ , 0 } max { ⟨ ∇ f i ( x t ) , ∇ f 0 ( x t ) ⟩ , 0 } , x t + 1 = x t − γ i = 1 ∑ M ω i t ∇ f i ( x t ) , (2)
where f 0 f_0 f 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 ℓ 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 R n \mathbb{R}^n R n with the standard Euclidean norm, ∥ x ∥ ≔ ⟨ x , x ⟩ 1 / 2 \lVert x\rVert\coloneqq\langle x,x\rangle^{1/2} ∥ x ∥ : = ⟨ x , x ⟩ 1/2 , x ∈ R n x \in\mathbb{R}^n x ∈ R n . Throughout the paper, f : R n → R f:\mathbb{R}^n \to\mathbb{R} f : R n → R denotes a differentiable objective function.
Assumption 1 (Smoothness) Differentiable function f 0 f_0 f 0 has L L L -Lipschitz gradient for some L > 0 L > 0 L > 0 , i.e.
∥ ∇ f 0 ( x ) − ∇ f 0 ( y ) ∥ ≤ L ∥ x − y ∥ ∀ x , y ∈ R n . (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)} ∥ ∇ f 0 ( x ) − ∇ f 0 ( y )∥ ≤ L ∥ x − y ∥ ∀ x , y ∈ R n . (3) Moreover, f 0 inf ≔ inf x ∈ R n f 0 ( x ) > − ∞ f_0^{\inf} \coloneqq\inf_{x\in\mathbb{R}^n} f_0(x) > -\infty f 0 i n f : = inf x ∈ R n f 0 ( x ) > − ∞ .
JL Transforms
Definition 1 (JL Transform [15 ] ) Given ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , a stochastic mapping h : R n → R k h:\mathbb{R}^n \to\mathbb{R}^k h : R n → R k is called a JL transform if, for all u , v ∈ R n u,v \in\mathbb{R}^n u , v ∈ 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)} P [ ( 1 − ε ) ∥ u − v ∥ 2 ≤ ∥ h ( u ) − h ( v ) ∥ 2 ≤ ( 1 + ε ) ∥ u − v ∥ 2 ] ≥ 1 − δ . (4)
In words, a JL transform preserves all pairwise distances up to a factor 1 ± ε 1 \pm\varepsilon 1 ± ε with probability at least 1 − δ 1-\delta 1 − δ , while reducing the dimension from n n n to k k k . If h h h is linear, then h ( 0 ) = 0 h(0)=0 h ( 0 ) = 0 , and taking v = 0 v=0 v = 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 ( 1 − ε ) ∥ u ∥ 2 ≤ ∥ h ( u ) ∥ 2 ≤ ( 1 + ε ) ∥ u ∥ 2 . Since ⟨ u , v ⟩ = 1 4 ( ∥ 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) ⟨ u , v ⟩ = 4 1 ( ∥ u + v ∥ 2 − ∥ u − v ∥ 2 ) , preserving the norms of u + v u+v u + v and u − v u-v u − v also preserves inner products.
Lemma 1. If h h h 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 P [ ∣ ⟨ h ( u ) , h ( v )⟩ − ⟨ u , v ⟩ ∣ ≤ ε ∥ u ∥ ∥ v ∥ ] ≥ 1 − 2 δ for all u , v ∈ R n u,v\in\mathbb{R}^{n} u , v ∈ R n .
We consider two standard linear constructions.
Definition 2 (Gaussian JL matrix). S ∈ R k × n S\in\mathbb{R}^{k\times n} S ∈ R k × n with i.i.d. entries [ S ] i j ∼ N ( 0 , 1 k ) [S]_{ij}\sim\mathcal{N}\left(0,\frac{1}{k}\right) [ S ] ij ∼ N ( 0 , k 1 ) .
Definition 3 (Rademacher JL matrix). S ∈ R k × n S\in\mathbb{R}^{k\times n} S ∈ R k × n with i.i.d. entries [ S ] i j = ± 1 k [S]_{ij}=\pm\frac{1}{\sqrt{k}} [ S ] ij = ± k 1 , each with probability 1 2 \frac{1}{2} 2 1 .
Both are JL transforms with distortion ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and failure probability δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) whenever k ≥ C ε − 2 log ( 2 / δ ) k\geq C\varepsilon^{-2}\log(2/\delta) k ≥ C ε − 2 log ( 2/ δ ) , where C > 0 C>0 C > 0 is a universal constant [36 , 37 ] . To return to R n \mathbb{R}^{n} R n for the optimization update, we use the lifted operator
JL S ( x ) : = S T S x ∈ R n . \operatorname{JL}_{S}(x)\mathrel{\mathop:}=S^{\mathsf{T}}Sx\in\mathbb{R}^{n}. JL S ( x ) : = S T S x ∈ R n .
Lemma 2 (Unbiasedness). For S S S as in Definitions 2 and 3, E JL S ( x ) = x \mathbb{E}\operatorname{JL}_{S}(x)=x E JL S ( x ) = x for all x ∈ R n x\in\mathbb{R}^{n} x ∈ R n .
Lemma 3 (Second moment). For all x ∈ R n x\in\mathbb{R}^{n} x ∈ R n , E ∥ JL S ( x ) ∥ 2 = n + k + 1 k ∥ x ∥ 2 \mathbb{E}\lVert\operatorname{JL}_{S}(x)\rVert^{2}=\frac{n+k+1}{k}\lVert x\rVert^{2} E ∥ JL S ( x ) ∥ 2 = k n + k + 1 ∥ x ∥ 2 for Gaussian and E ∥ JL S ( x ) ∥ 2 = n + k − 1 k ∥ x ∥ 2 \mathbb{E}\lVert\operatorname{JL}_{S}(x)\rVert^{2}=\frac{n+k-1}{k}\lVert x\rVert^{2} E ∥ JL S ( x ) ∥ 2 = k n + k − 1 ∥ x ∥ 2 for Rademacher S S S .
Thus JL S \operatorname{JL}_{S} JL S resembles unbiased sparsification such as Randk, C ( x ) = n k ∑ i ∈ I x i e i C(x)=\frac{n}{k}\sum_{i\in I}x_{i}e_{i} C ( x ) = k n ∑ i ∈ I x i e i with I ⊂ [ n ] I\subset[n] I ⊂ [ n ] a uniformly random subset of size k k k , which is also unbiased with variance of order n k \frac{n}{k} k n [38 ] . The key distinction is that the transmitted message of Randk, h C ( x ) : = n k ( x i ) i ∈ I ∈ R k h_{C}(x)\mathrel{\mathop:}=\sqrt{\frac{n}{k}}(x_{i})_{i\in I}\in\mathbb{R}^{k} h C ( x ) : = k n ( x i ) i ∈ I ∈ R k (so that C = h C T h C C=h_{C}^{\mathsf{T}}h_{C} C = h C T h C , just as JL S = S T S \operatorname{JL}_{S}=S^{\mathsf{T}}S JL S = S T S ), does not preserve norms with high probability. By linearity, the JL property for h C h_{C} h C reduces to P [ ∣ ∥ h C ( 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 P [ ∥ h C ( x ) ∥ 2 / ∥ x ∥ 2 − 1 ≤ ε ] ≥ 1 − δ for all x ∈ R n ∖ { 0 } x\in\mathbb{R}^{n}\setminus\{0\} x ∈ R n ∖ { 0 } . For x = e 1 x=e_{1} x = e 1 the ratio is 0 0 0 with probability 1 − k n 1-\frac{k}{n} 1 − n k , forcing δ ≥ 1 − k n \delta\geq1-\frac{k}{n} δ ≥ 1 − n k .
Lemma 4 (Operator-norm bound [39 ] ). For S S S as in Definitions 2 or 3, there exists a universal constant c > 0 c>0 c > 0 , independent of n n n and k k k , such that, with probability at least 1 − δ 1-\delta 1 − δ ,
∥ S ∥ ≤ 1 + c n k + c log ( 2 / δ ) k . (5) \lVert S\rVert\leq1+c\sqrt{\frac{n}{k}}+c\sqrt{\frac{\log(2/\delta)}{k}}. \tag*{(5)} ∥ S ∥ ≤ 1 + c k n + c k log ( 2/ δ ) . (5) Consequently, on the same event, ∥ JL S ( x ) ∥ 2 ≤ ( 1 + c n k + c log ( 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} ∥ JL S ( x ) ∥ 2 ≤ ( 1 + c k n + c k l o g ( 2/ δ ) ) 4 ∥ x ∥ 2 for every x ∈ R n x\in\mathbb{R}^{n} x ∈ 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
Many Byzantine-resilient methods exploit gradient similarity to distinguish honest workers from adversarial ones. We introduce Grad-BANT (Algorithm 1), inspired by [13 ] . As in equation (2) , it relies on a trial function f 0 f_0 f 0 stored on the trusted server, whose gradient ∇ f 0 ( x ) \nabla f_0(x) ∇ f 0 ( x ) is used to score the received messages; its accuracy with respect to the honest objective is specified in Assumption 3.
Algorithm 1: Grad-BANT
1: Parameters: $x^0 \in \mathbb{R}^n$, $\omega_i^{-1}=1/M$, stepsize $\gamma>0$, momentum $\beta \in (0,1]$, smoothness constant $L>0$
2: for $t=0,1,\ldots,T-1$ do
3: Generate a fresh $S_t$; server sends $x^t$ and the sketch seed to workers
4: for all $i=1,\ldots,M$ in parallel do
5: Honest worker: $g_i^t=\nabla f_i(x^t)$; send $y_i^t=S_tg_i^t$ to server
6: end for
7: $u_i^t=S_t^\mathsf{T}y_i^t$; $\theta_i^t=\langle S_t\nabla f_0(x^t),y_i^t\rangle-\frac{L\gamma}{2}\lVert u_i^t\rVert^2$
8: if all $[\theta_i^t]_0=0$ then
9: $\omega_i^t=(1-\beta)\omega_i^{t-1}+\frac{\beta}{M}$
10: else
11: $\omega_i^t=(1-\beta)\omega_i^{t-1}+\beta\frac{[\theta_i^t]_0}{\sum_{j=1}^{M}[\theta_j^t]_0}$
12: end if
13: $x^{t+1}=x^t-\gamma S_t^\mathsf{T}\sum_{i=1}^{M}\mathbb{I}_{[\theta_i^t>0]}\omega_i^t y_i^t$
14: end for
At each iteration, an honest worker sends y i t = S t g i t y_i^t=S_tg_i^t y i t = S t g i t with g i t = ∇ f i ( x t ) g_i^t=\nabla f_i(x^t) g i t = ∇ f i ( x t ) , while a Byzantine worker may send any finite, measurable y i t ∈ R k y_i^t\in\mathbb{R}^k y i t ∈ R k , possibly chosen after observing the current sketch and the honest messages; u i t = S t T y i t u_i^t=S_t^\mathsf{T}y_i^t u i t = S t T y i t denotes the lifted message. Each sketch is sampled independently of all data and previous randomness after x t x^t x t is determined, so the honest gradients and the reference gradient are fixed conditional on the history before sampling S t S_t S t .
The trust score θ i t \theta_i^t θ i t measures how well the lifted message aligns with the trusted reference gradient ∇ f 0 ( x t ) \nabla f_0(x^t) ∇ f 0 ( x t ) , while accounting for its norm: if ⟨ ∇ f 0 ( x t ) , u i t ⟩ > L γ 2 ∥ u i t ∥ 2 \langle\nabla f_0(x^t),u_i^t\rangle>\frac{L\gamma}{2}\lVert u_i^t\rVert^2 ⟨ ∇ f 0 ( x t ) , u i t ⟩ > 2 L γ ∥ u i t ∥ 2 , the direction is sufficiently aligned with the trusted descent direction and receives a positive weight; otherwise, it is suppressed by the indicator in the update. The scores are clipped by [ x ] 0 : = max { x , 0 } [x]_0\mathrel{\mathop:}=\max\{x,0\} [ x ] 0 : = max { x , 0 } and normalized. If all scores are non-positive, we blend the previous weights with uniform weights (line 9) and leave the iterate unchanged. The momentum parameter β \beta β smooths the evolution of the weights over time.
For honest workers, the server thus uses the compressed alignment terms ⟨ S t ∇ f 0 ( x t ) , S t g i t ⟩ \langle S_t\nabla f_0(x^t),S_tg_i^t\rangle ⟨ S t ∇ f 0 ( x t ) , S t g i t ⟩ , which the JL property keeps close to the exact ones with high probability, while the norm penalty is evaluated on the actual lifted message. The aggregated update is lifted back to R n \mathbb{R}^n R n via S t T S_t^\mathsf{T} S t T (line 13). Our analysis uses the aggregate honest alignment and the sum of honest squared norms; it does not require the compressed and uncompressed scores to select the same workers. We require the following similarity condition.
Assumption 2 (Data similarity) The honest workers are said to satisfy ( δ 1 , δ 2 ) (\delta_1,\delta_2) ( δ 1 , δ 2 ) -data similarity if there exist δ 1 , δ 2 ≥ 0 \delta_1,\delta_2\geq0 δ 1 , δ 2 ≥ 0 such that
1 G ∑ i ∈ G ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 ≤ δ 1 + δ 2 ∥ ∇ f ( x ) ∥ 2 , ∀ x ∈ R n . (6) \frac{1}{G}\sum_{i\in G}\lVert\nabla f_i(x)-\nabla f(x)\rVert^2\leq\delta_1+\delta_2\lVert\nabla f(x)\rVert^2,\qquad\forall x\in\mathbb{R}^n. \tag*{(6)} G 1 i ∈ G ∑ ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 ≤ δ 1 + δ 2 ∥ ∇ f ( x ) ∥ 2 , ∀ x ∈ R n . (6)
This condition bounds heterogeneity on average over the honest workers, which is weaker than imposing it on every honest worker. Since f f f is their average, it also gives
1 G ∑ i ∈ G ∥ ∇ f i ( x ) ∥ 2 = ∥ ∇ f ( x ) ∥ 2 + 1 G ∑ i ∈ G ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 ≤ ( 1 + δ 2 ) ∥ ∇ f ( x ) ∥ 2 + δ 1 . (7) \frac{1}{G}\sum_{i\in\mathcal{G}}\|\nabla f_i(x)\|^2 = \|\nabla f(x)\|^2 + \frac{1}{G}\sum_{i\in\mathcal{G}}\|\nabla f_i(x)-\nabla f(x)\|^2 \le(1+\delta_2)\|\nabla f(x)\|^2+\delta_1. \tag*{(7)} G 1 i ∈ G ∑ ∥∇ f i ( x ) ∥ 2 = ∥∇ f ( x ) ∥ 2 + G 1 i ∈ G ∑ ∥∇ f i ( x ) − ∇ f ( x ) ∥ 2 ≤ ( 1 + δ 2 ) ∥∇ f ( x ) ∥ 2 + δ 1 . (7)
The next assumption quantifies how accurately the trusted reference represents the objective; η 0 \eta_0 η 0 and η 1 \eta_1 η 1 capture the mismatch between the trial and the true data distributions.
Assumption 3 (Reference accuracy)
There exist η 0 ≥ 0 \eta_0 \ge0 η 0 ≥ 0 and η 1 ∈ [ 0 , 1 ) \eta_1 \in[0,1) η 1 ∈ [ 0 , 1 ) such that
∥ ∇ f 0 ( x ) − ∇ f ( x ) ∥ 2 ≤ η 0 + η 1 ∥ ∇ f ( x ) ∥ 2 , ∀ x ∈ R n . (8) \|\nabla f_0(x)-\nabla f(x)\|^2 \le\eta_0+\eta_1\|\nabla f(x)\|^2,\qquad\forall x\in\mathbb{R}^n. \tag*{(8)} ∥∇ f 0 ( x ) − ∇ f ( x ) ∥ 2 ≤ η 0 + η 1 ∥∇ f ( x ) ∥ 2 , ∀ x ∈ R n . (8)
Theorem 1
Suppose that Assumptions 1, 2, and 3 hold. Let T ≥ 1 T\ge1 T ≥ 1 be an integer, β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] , and ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) satisfy
d : = 1 − η 1 − ε 2 > 0. d \mathrel{\mathop:}= 1-\eta_1-\varepsilon^2>0. d : = 1 − η 1 − ε 2 > 0. Use fresh Gaussian or Rademacher JL matrices in Algorithm 1, and set
ρ = ( 1 + c n k + c log ( 8 T / δ ) k ) 2 , Δ 0 = f 0 ( x 0 ) − f 0 inf , (9) \rho=\left(1+c\sqrt{\frac{n}{k}}+c\sqrt{\frac{\log(8T/\delta)}{k}}\right)^2,\qquad\Delta_0=f_0(x^0)-f_0^{\inf}, \tag*{(9)} ρ = ( 1 + c k n + c k log ( 8 T / δ ) ) 2 , Δ 0 = f 0 ( x 0 ) − f 0 i n f , (9) where c c c is the constant in Lemma 4. Then, for any stepsize
0 < γ ≤ d 2 L ρ ( 1 + ε ) ( 1 + δ 2 ) , (10) 0<\gamma\le\frac{d}{2L\rho(1+\varepsilon)(1+\delta_2)}, \tag*{(10)} 0 < γ ≤ 2 L ρ ( 1 + ε ) ( 1 + δ 2 ) d , (10) after T T T iterations we have
1 T ∑ t = 0 T − 1 ∥ ∇ f ( x t ) ∥ 2 ≤ 4 M Δ 0 γ β G d T + 2 η 0 d + 2 L γ ρ ( 1 + ε ) δ 1 d , (11) \frac{1}{T}\sum_{t=0}^{T-1}\|\nabla f(x^t)\|^2\le\frac{4M\Delta_0}{\gamma\beta GdT}+\frac{2\eta_0}{d}+\frac{2L\gamma\rho(1+\varepsilon)\delta_1}{d}, \tag*{(11)} T 1 t = 0 ∑ T − 1 ∥∇ f ( x t ) ∥ 2 ≤ γ β G d T 4 M Δ 0 + d 2 η 0 + d 2 L γ ρ ( 1 + ε ) δ 1 , (11) with probability at least 1 − δ 1-\delta 1 − δ , provided that k ≥ C ε − 2 log ( 8 T / δ ) k\ge C\varepsilon^{-2}\log(8T/\delta) k ≥ C ε − 2 log ( 8 T / δ ) for a sufficiently large universal constant C > 0 C>0 C > 0 .
The proof is given in Appendix § 9 . Neither convexity nor a small upper bound on δ 2 \delta_2 δ 2 is required [14 ] . The reference error contributes an explicit residual term, heterogeneity affects both the admissible stepsize and the last term in equation (11) , and the factor M / ( β G ) M/(\beta G) M / ( β G ) reflects the fraction of honest workers and the weight update. With S t = I n S_t=I_n S t = I n (ε = 0 \varepsilon=0 ε = 0 , ρ = 1 \rho=1 ρ = 1 ), the same analysis gives the uncompressed guarantee.
Efficient Implementation
Beyond communication, scalability in large-scale distributed learning is limited by the cost of storing and applying the compression operator: a dense Gaussian or Rademacher matrix S ∈ R k × n S\in\mathbb{R}^{k\times n} S ∈ R k × n requires O ( n k ) O(nk) O ( nk ) memory and O ( n k ) O(nk) O ( nk ) operations per application, which is prohibitive for modern models. We therefore discuss structured and sparse JL constructions, whose geometric guarantees depend on the construction and its parameters, and their use within Grad-BANT.
Efficient JL Transforms
Dense JL matrices can be replaced by the SRHT S S R H T = n / k R T H D S_{\mathrm{SRHT}}=\sqrt{n/k}\,R_THD S SRHT = n / k R T H D , with a random diagonal sign matrix D D D , the normalized Walsh–Hadamard matrix H H H , and a sampler R T R_T R T of k k k coordinates, or by the related FJLT [40 , 41 , 42 ] , both applied in O ( n log n ) O(n \log n) O ( n log n ) time, or by sparse sketches such as CountSketch [43 , 44 , 45 ] , applied in O ( n ) O(n) O ( n ) time. All of them are generated from a random seed, so the server broadcasts only the seed of S t S_t S t . The appendix verifies unbiasedness and second-moment bounds for these sketches, which suffices for the expectation analysis (Theorem 8); the high-probability guarantee of Theorem 1 additionally requires the inner-product, Frobenius-norm, and operator-norm events of Appendix § 9 .
Per-layer Sketching
Applying a single JL transform to the entire parameter vector may be impractical for large models, and even infeasible for large language models. A natural remedy is per-layer sketching, where each layer x w ∈ R n w x_w \in\mathbb{R}^{n_w} x w ∈ R n w of x = ( x 1 , … , x W ) x=(x_1,\ldots,x_W) x = ( x 1 , … , x W ) is compressed by its own JL transform S w ∈ R k w × n w S_w \in\mathbb{R}^{k_w \times n_w} S w ∈ R k w × n w , i.e., S = blockdiag ( S 1 , … , S W ) S=\operatorname{blockdiag}(S_1,\ldots,S_W) S = blockdiag ( S 1 , … , S W ) . If each layerwise transform preserves norms, so does the full block-diagonal transform.
Theorem 2 (Per-layer norm preservation ) Let x = ( x 1 , … , x W ) ∈ R n ∖ { 0 } x=(x_1,\ldots,x_W) \in\mathbb{R}^{n}\setminus\{0\} x = ( x 1 , … , x W ) ∈ R n ∖ { 0 } , where x w ∈ R n w x_w \in\mathbb{R}^{n_w} x w ∈ R n w and ∑ w = 1 W n w = n \sum_{w=1}^{W} n_w=n ∑ w = 1 W n w = n . Let S = blockdiag ( S 1 , … , S W ) S=\operatorname{blockdiag}(S_1,\ldots,S_W) S = blockdiag ( S 1 , … , S W ) , where S w ∈ R k w × n w S_w \in\mathbb{R}^{k_w \times n_w} S w ∈ R k w × n w are random matrices defined on a common probability space. Suppose that, for each w w w , there exist parameters ε w ≥ 0 \varepsilon_w \ge0 ε w ≥ 0 and δ w ∈ [ 0 , 1 ] \delta_w \in[0,1] δ w ∈ [ 0 , 1 ] such that, for every fixed z ∈ R n w z \in\mathbb{R}^{n_w} z ∈ R n w ,
P ( ∣ ∥ S w z ∥ 2 − ∥ z ∥ 2 ∣ > ε w ∥ z ∥ 2 ) ≤ δ w . \mathbb{P}\left(\left|\lVert S_w z\rVert^2-\lVert z\rVert^2\right|>\varepsilon_w\lVert z\rVert^2\right)\le\delta_w. P ( ∥ S w z ∥ 2 − ∥ z ∥ 2 > ε w ∥ z ∥ 2 ) ≤ δ w . Then, for every fixed x ∈ R n ∖ { 0 } x \in\mathbb{R}^{n}\setminus\{0\} x ∈ R n ∖ { 0 } ,
P ( ∣ ∥ S x ∥ 2 − ∥ x ∥ 2 ∣ > ( ∑ w = 1 W α w ( x ) ε w ) ∥ x ∥ 2 ) ≤ ∑ w = 1 W δ w . \mathbb{P}\left(\left|\lVert Sx\rVert^2-\lVert x\rVert^2\right|>\left(\sum_{w=1}^{W}\alpha_w(x)\varepsilon_w\right)\lVert x\rVert^2\right)\le\sum_{w=1}^{W}\delta_w. P ( ∥ S x ∥ 2 − ∥ x ∥ 2 > ( w = 1 ∑ W α w ( x ) ε w ) ∥ x ∥ 2 ) ≤ w = 1 ∑ W δ w . where α w ( x ) : = ∥ x w ∥ 2 / ∥ x ∥ 2 \alpha_w(x)\mathrel{\mathop:}=\lVert x_w\rVert^2/\lVert x\rVert^2 α w ( x ) : = ∥ x w ∥ 2 / ∥ x ∥ 2 .
If the layerwise distribution of gradient energy is known, the sketch dimensions can be allocated non-uniformly across layers.
Corollary 1 (Energy-aware allocation ) Let ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) and use Gaussian or Rademacher sketches on the active layers, with dimensions
k w = ⌈ C log ( 2 W / δ ) ε w 2 ⌉ , k_w=\left\lceil\frac{C\log(2W/\delta)}{\varepsilon_w^2}\right\rceil, k w = ⌈ ε w 2 C log ( 2 W / δ ) ⌉ , where C > 0 C>0 C > 0 is a sufficiently large universal constant. Fix x ∈ R n ∖ { 0 } x\in\mathbb{R}^{n}\setminus\{0\} x ∈ R n ∖ { 0 } and let α w ( x ) = ∥ x w ∥ 2 / ∥ x ∥ 2 \alpha_w(x)=\lVert x_w\rVert^2/\lVert x\rVert^2 α w ( x ) = ∥ x w ∥ 2 / ∥ x ∥ 2 . For all active layers with α w ( x ) > 0 \alpha_w(x)>0 α w ( x ) > 0 , set
ε w = ε α w ( x ) − 1 / 3 ∑ j : α j ( x ) > 0 α j ( x ) 2 / 3 , δ w = δ W . (12) \varepsilon_w=\frac{\varepsilon\alpha_w(x)^{-1/3}}{\sum_{j:\alpha_j(x)>0}\alpha_j(x)^{2/3}},\qquad\delta_w=\frac{\delta}{W}. \tag*{(12)} ε w = ∑ j : α j ( x ) > 0 α j ( x ) 2/3 ε α w ( x ) − 1/3 , δ w = W δ . (12) Assume that ε w < 1 \varepsilon_w<1 ε w < 1 and k w ≤ n w k_w\le n_w k w ≤ n w for every active layer. Inactive layers are omitted, with k w = 0 k_w=0 k w = 0 . Then, for this fixed vector x x x , the block-diagonal sketch satisfies an ε \varepsilon ε -distortion guarantee with probability at least 1 − δ 1-\delta 1 − δ , and the total number of transmitted coordinates scales as
∑ w = 1 W k w = Θ ( log ( 2 W / δ ) ε 2 ( ∑ w = 1 W α w ( x ) 2 / 3 ) 3 ) . \sum_{w=1}^{W}k_w=\Theta\left(\frac{\log(2W/\delta)}{\varepsilon^2}\left(\sum_{w=1}^{W}\alpha_w(x)^{2/3}\right)^3\right). w = 1 ∑ W k w = Θ ε 2 log ( 2 W / δ ) ( w = 1 ∑ W α w ( x ) 2/3 ) 3 .
In this feasible regime, energy-aware allocation can reduce the total communication cost for the fixed vector compared to a uniform allocation.
Matrix and Tensor Extensions
Neural network parameters are naturally matrices or higher-order tensors, which suggests sketches that respect this structure. For X ∈ R n 1 × n 2 X \in\mathbb{R}^{n_1 \times n_2} X ∈ R n 1 × n 2 , instead of applying a dense sketch to vec ( X ) \operatorname{vec}(X) vec ( X ) , one can use two smaller JL matrices S 1 ∈ R k 1 × n 1 S_1 \in\mathbb{R}^{k_1 \times n_1} S 1 ∈ R k 1 × n 1 and S 2 ∈ R k 2 × n 2 S_2 \in\mathbb{R}^{k_2 \times n_2} S 2 ∈ R k 2 × n 2 and set
S ( X ) = S 1 X S 2 T ∈ R k 1 × k 2 , vec ( S ( X ) ) = ( S 2 ⊗ S 1 ) vec ( X ) . S(X) = S_1 X S_2^{\mathsf{T}} \in\mathbb{R}^{k_1 \times k_2}, \qquad\operatorname{vec}(S(X)) = (S_2 \otimes S_1)\operatorname{vec}(X). S ( X ) = S 1 X S 2 T ∈ R k 1 × k 2 , vec ( S ( X )) = ( S 2 ⊗ S 1 ) vec ( X ) .
A dense sketch of vec ( X ) ∈ R n 1 n 2 \operatorname{vec}(X) \in\mathbb{R}^{n_1 n_2} vec ( X ) ∈ R n 1 n 2 to dimension k k k requires O ( n 1 n 2 k ) O(n_1 n_2 k) O ( n 1 n 2 k ) memory, whereas the Kronecker-structured sketch stores only S 1 S_1 S 1 and S 2 S_2 S 2 , i.e., O ( n 1 k 1 + n 2 k 2 ) O(n_1 k_1 + n_2 k_2) O ( n 1 k 1 + n 2 k 2 ) memory, for a compressed dimension k 1 k 2 k_1 k_2 k 1 k 2 . This dimension may not be optimal, but the savings in memory and implementation cost are essential for large-scale models. The same idea extends to higher-order tensors.
Theorem 3 (Kronecker-structured JL transform) Let S = S d ⊗ S d − 1 ⊗ … ⊗ S 1 S = S_d \otimes S_{d-1} \otimes\ldots\otimes S_1 S = S d ⊗ S d − 1 ⊗ … ⊗ S 1 , where S j ∈ R k j × n j S_j \in\mathbb{R}^{k_j \times n_j} S j ∈ R k j × n j are independent Gaussian or Rademacher JL matrices, and suppose that min j ∈ [ d ] k j = Ω ( d 2 log ( 2 d / δ ) ε 2 ) \min_{j \in[d]} k_j = \Omega\left(\frac{d^2 \log(2d/\delta)}{\varepsilon^2}\right) min j ∈ [ d ] k j = Ω ( ε 2 d 2 l o g ( 2 d / δ ) ) . Then, for every fixed tensor X ∈ R n 1 × … × n d X \in\mathbb{R}^{n_1 \times\ldots\times n_d} X ∈ R n 1 × … × n d , with S ( X ) S(X) S ( X ) defined by vec ( S ( X ) ) = S vec ( X ) \operatorname{vec}(S(X)) = S\operatorname{vec}(X) vec ( S ( X )) = S vec ( X ) ,
P ( ∣ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 ∣ > ε ∥ X ∥ F 2 ) ≤ δ . \mathbb{P}\left(\left|\lVert S(X)\rVert_F^2-\lVert X\rVert_F^2\right| > \varepsilon\lVert X\rVert_F^2\right) \leq\delta. P ( ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 > ε ∥ X ∥ F 2 ) ≤ δ .
As for per-layer sketches, their use in the high-probability convergence proof requires the theoretical justifying specified in Appendix § 9 . Overall, dense Gaussian and Rademacher projections are useful for theory and small-scale experiments, whereas structured, sparse, per-layer, and Kronecker-based sketches reduce the cost of applying and storing the compression operator.
Experiments
Comparison of Compressors
In this section we compare several compressors along two axes: the time and memory required to compress and decompress the transmitted parameters and the extent to which they satisfy the JL-properties required by our Algorithm 1.
Table 1 reports the cost of applying each compressor to the parameters of a ResNet18 model. For RandK we treat all parameters as a single flattened vector, whereas for the JL-based compressors and PowerSGD we compress each layer separately. For SRFT and SRHT we consider both scenarios, since these methods can operate in either one without incurring a significant memory or time overhead compared to the remaining JL compressors. CountSketch is omitted from the experiments, as it is not readily supported by standard PyTorch tensor operations. Stored denotes the additional memory required to keep the compressor’s internal state (e.g. the JL matrix). All measurements are taken at a compression rate of 50%.
Table 1. Cost of applying each compressor to ResNet-18 parameters at k / n = 0.5 k/n = 0.5 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 k k to the flattened parameter vector; † applied to the flattened parameter vector.
As the table shows, our JL variant is the fastest among all JL-based methods, and is outperformed only by RandK on GPU, which is unsurprising since that method merely selects a subset of coordinates. At the same time, in terms of peak memory and CPU time our method outperforms every compressor considered. Applying SRHT and SRFT to the full parameter vector offers no practical advantage over layer-wise application. The effect on running time is marginal (a minor speedup on GPU and a 5–30% slowdown on CPU), whereas peak memory consumption increases by a factor of 3.3–3.6.
Table 2 compares several quantities that measure how well the JL properties are preserved by the different compression methods. Here Δ i p \Delta_{\mathrm{ip}} Δ ip and Δ θ \Delta_{\theta} Δ θ denote the quantities
Table 2. Distortion of inner products (Δ i p \Delta_{\mathrm{ip}} Δ ip ) and angles (Δ θ \Delta_{\theta} Δ θ ) under compression, mean ± std. (a) Random 4096 × 4096 4096 \times4096 4096 × 4096 ; (b) stochastic ResNet-18 gradient vs. trust-set gradient. All compressors use k / n = 0.5 k/n = 0.5 k / n = 0.5 ; for Adaptive JL, k / n k/n k / n is set implicitly by the target ε \varepsilon ε from equation (12) .
Δ i p = ∣ ⟨ S u , S v ⟩ − ⟨ u , v ⟩ ∣ ∥ u ∥ ∥ v ∥ , Δ θ = ∣ ∠ ( S u , S v ) − ∠ ( u , v ) ∣ . \Delta_{\mathrm{ip}} = \frac{\left|\langle Su,Sv\rangle-\langle u,v\rangle\right|}{\lVert u\rVert\lVert v\rVert}, \qquad\Delta_{\theta} = \left|\angle(Su,Sv)-\angle(u,v)\right|. Δ ip = ∥ u ∥ ∥ v ∥ ∣ ⟨ S u , S v ⟩ − ⟨ u , v ⟩ ∣ , Δ θ = ∣ ∠ ( S u , S v ) − ∠ ( u , v ) ∣ .
Δ i p \Delta_{\mathrm{ip}} Δ ip measures the deviation of the inner product of the compressed and uncompressed vectors, whereas the Δ θ \Delta_{\theta} Δ θ measures the distortion of the angle between the vectors caused by compression.
The table reports results for two setups: setup (a) is the compression of two 4096 × 4096 4096 \times4096 4096 × 4096 matrices, and setup (b) is the compression of an actual stochastic gradient of a ResNet18 model and its comparison against the gradient computed on the trust set, as used in Algorithm 1. For all compressors except AdaptiveJL the compression rate is fixed at 50%. For AdaptiveJL the compression rate is determined implicitly by the parameter ε \varepsilon ε . We therefore report results for several values of ε \varepsilon ε . A comparison of the compressors at other compression rates is provided in Appendix § 6 .
As the table shows, RandK performs reasonably well in the first setup, which can be attributed to the random construction of the matrices and to the unbiasedness of the compressor. However, on real gradients the method distorts both the inner product and the angle quite severely. In contrast, the JL-based methods perform well in both scenarios. We also note separately that SRFT and SRHT applied to the gradient as a single vector yield the worst results among all JL-based methods considered, which together with Table 1 , indicates that layer-wise compression is preferable.
Comparison with Byzantine Baselines
This section presents experiments comparing Algorithm 1 against a range of federated learning methods under various Byzantine attack scenarios. All results are reported in the tables below. Every experiment is run in the setting of training a ResNet18 model on the CIFAR-10 dataset. All methods are trained for T = 200 T = 200 T = 200 communication rounds with the data distributed uniformly across M = 10 M = 10 M = 10 clients. To compare methods with different compression levels, we measure communication in full gradient uploads : a compressed message of k k k coordinates counts as k / n k/n k / n of a full gradient, where n n n is the number of model parameters, and uploads are summed over all M M M clients. After t t t rounds this gives
G ( t ) = ∑ s = 1 t ∑ i = 1 M k s , i n , (13) G(t) = \sum_{s=1}^{t}\sum_{i=1}^{M}\frac{k_{s,i}}{n}, \tag*{(13)} G ( t ) = s = 1 ∑ t i = 1 ∑ M n k s , i , (13)
which reduces to G ( t ) = t M k / n G(t) = tM k/n G ( t ) = tM k / n for a fixed compression ratio and to G ( t ) = t M G(t) = tM G ( t ) = tM without compression. Over the full T = 200 T = 200 T = 200 rounds an uncompressed method thus performs 2000 full-gradient uploads, and a method with k / n = 0.5 k/n = 0.5 k / n = 0.5 performs 1000. Details on the attack scenarios and additional experiments are deferred to Appendix § 6 .
Table 3 reports the results of applying different compressors to FedAvg and GradBant, both in the attack-free setting and under the LABEL FLIPPING (LF) attack. For each configuration, the table reports the number of full-gradient transmissions required to reach a given value of the target metric, together with the best test accuracy attained. Columns G→60 and G→80 report G ( t ) G(t) G ( t ) from equation (13) at the first round t t t at which the test accuracy reaches 60% and 80%, respectively. For AdaptiveJL, k / n k/n k / n denotes the average over rounds and clients.
Table 3. FedAvg and Grad-BANT with different compressors: (a) no attack, (b) label flipping with 60% Byzantine clients.
In the attack-free setting, all compressors perform similarly for both algorithms. Once the attack is enabled, every compressor in the FedAvg setting fails to learn and shows almost no accuracy improvement throughout training. In contrast, for GradBant the properties of the compressor start to matter. All JL compressors which preserve inner products continue to work, whereas the RandK compressor is likewise compromised by the attack.
Table 4 compares Byzantine-robust methods with compression [46 ] under two different attacks. Unlike ours, the remaining methods do not use a trust set, and consequently cannot tolerate a Byzantine majority. When the number of Byzantine clients approaches one half, these methods yield results that lag far behind our algorithm.
Table 4. Best test accuracy of Byzantine-robust methods with compression under label flipping (LF) and random gradients (RG) with 40% and 60% Byzantine clients. All methods use the k / n = 0.5 k/n = 0.5 k / n = 0.5 .
Finally, Table 5 compares (a) the best test accuracy and (b) the number of full-gradient uploads G G G required to reach 60% accuracy for Byzantine-robust baselines without compression and for our algorithm with a compression rate of 50% under several attacks. The results show that GradBant requires fewer full-gradient transmissions than the remaining baselines to reach 60% accuracy. We note that under the ALIE attack our method does not reach this level of accuracy, plateauing at 53.9%. In terms of best accuracy, our method outperforms all baselines under the IPM attack. In the attack-free scenario and under SignFlip and LabelFlip our method stays close to the strongest baselines.
Table 5. Comparison with Byzantine-robust baselines under different attacks (Byzantine fraction in the header): (a) best test accuracy; (b) full-gradient uploads G G G to reach 60% test accuracy. Baselines are uncompressed; Grad-BANT + JL uses k / n = 0.5 k/n = 0.5 k / n = 0.5 . –: not reached.
Heterogenious scenario
In this section, we consider a scenario with heterogeneous data distribution across clients. To model heterogeneity, we use a Dirichlet(α \alpha α ) distribution to partition the dataset samples among clients. This makes the clients heterogeneous both in local dataset size and in the label distribution of their samples. Table 6 reports the training results of our algorithm under four heterogeneity scenarios, both without any attack and under three different attacks.
Table 6. Best test accuracy of Grad-BANT + JL (k / n = 0.5 k/n = 0.5 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.
All results are reported at a 50% compression rate. As expected, the final model quality degrades as the degree of heterogeneity increases. However, our algorithm remains highly robust to it. In all scenarios, it loses at most 19% accuracy in the worst case and 7% on average relative to the uniform (IID) data distribution.
Conclusion
We studied Johnson–Lindenstrauss transforms as communication-efficient compressors for Byzantine-robust distributed optimization. Unlike standard sparsification, JL transforms preserve Euclidean geometry with high probability, which suits methods that weight workers by gradient alignment. For a JL-compressed variant of Grad-BANT, we proved a high-probability convergence guarantee under smoothness, average data similarity, and an explicit accuracy condition on the trusted reference gradient, without convexity or a small relative heterogeneity parameter. We also studied structured, sparse, per-layer, and Kronecker-structured sketches, which reduce the cost of storing and applying dense projections in large models; their moment bounds support the expectation analysis, while the high-probability guarantee additionally requires geometric concentration bounds. The experiments confirm that JL-based compression reduces communication while maintaining Byzantine robustness, suggesting that preserving geometric structure is an important design principle for compression in robust distributed learning.
References
Experimental Details
Protocol.
Hardware. All experiments were conducted on a single NVIDIA A100 GPU with 80 GB of memory. Running all experiments required approximately 200 GPU-hours in total.
Hyperparameters. The hyperparameters of each method were tuned via grid search. For each method, all tables report the results obtained with the configuration that achieved the highest validation accuracy.
Table 7. Byzantine attacks used in the experiments. Here g i g_i g i denotes the stochastic gradient that an honest client i i i would send, g ˉ \bar{g} g ˉ and σ \sigma σ denote the coordinate-wise mean and standard deviation of the honest clients’ gradients, and C C C is the number of classes.
Trial ablation
In this section, we study how the size and distribution of the trust set affect the performance of Algorithm 1. All experiments use k / n = 0.5 k/n = 0.5 k / n = 0.5 , label flipping with 60% Byzantine clients, IID data, and 100 training rounds. The results are summarized in Table 8 .
Table 8. Effect of the trust set on Grad-BANT + JL: (a) size; (b) distribution shift, 1500 images. R→ 60 and R→ 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 k/n = 0.5 k / n = 0.5 , IID data, 100 rounds.
Trust set size. Table 8 (a) shows that the size of the trust set has little effect on either the best test accuracy or the convergence speed. As the size increases from 100 to 2000 images, the best accuracy varies only between 0.838 and 0.844, and the number of rounds needed to reach 60% and 80% accuracy changes by at most 6 and 5 rounds, respectively.
Trust set distribution. Table 8 (b) considers a trust set of 1500 images whose distribution differs from uniform. Shifts in image appearance slow down training but do not prevent convergence. With grayscale images, reaching 60% and 80% accuracy takes 6 and 13 more rounds, respectively, while the best accuracy decreases only slightly, from 0.840 to 0.831. Strong augmentation has a larger effect. Reaching 60% accuracy takes almost three times as many rounds, 80% is never reached, and the best accuracy is 0.761. In both cases, training remains stable, and the final accuracy coincides with the best one. In contrast, class coverage is critical. When the trust set contains only 5 of the 10 classes, the best accuracy remains high (0.828), but training becomes unstable and the final accuracy drops to 0.636. With only 2 classes, the method fails completely: the accuracy never exceeds 0.16, which is close to random guessing.
Overall, Algorithm 1 is robust to the size of the trust set and to moderate shifts in its appearance. The key requirement is that the trust set covers all classes; its size mainly affects the stability of training in later rounds.
Training on the trust set alone. To check whether federated training is necessary when a trust set is available, we train ResNet-18 centrally on the trust set alone, using the same optimizer (Adam, learning rate 0.003), batch size (64), and augmentation as the clients. The budget is 12 400 optimizer steps, which matches the local computation of one client over 200 rounds. Table 9 shows that this baseline is far behind federated training. With 1500 images, the best accuracy is 0.609, whereas Algorithm 1 with a trust set of the same size reaches 0.913 within 100 rounds, even with 60% Byzantine clients (Table 8 ). The gap grows as the trust set shrinks: with 100 images, training on the trust set alone reaches at most 0.287, while the federated method still reaches 0.894. Even with 2000 images, the best accuracy is only 0.653. Moreover, the accuracy saturates early: between the 100th and 200th round-equivalents, it changes by less than 0.02 for all sizes, and the final accuracy is below the best one, which suggests overfitting to the small sample.
Table 9. Training ResNet-18 on the trust set alone, without federation. @ r r r : CIFAR-10 test accuracy after 62 r 62r 62 r optimizer steps, i.e., the computation of one client over r r 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)).
Additional experiments
Table 10 extends the comparison of Table 2 to compression rates k / n ∈ { 0.5 , 0.3 , 0.1 } k/n \in\{0.5, 0.3, 0.1\} k / n ∈ { 0.5 , 0.3 , 0.1 } in the same setting: the distortion is measured between the stochastic ResNet-18 gradient and the trust-set gradient over 100 pairs. As expected, the inner-product distortion Δ i p \Delta_{\mathrm{ip}} Δ ip increases monotonically for all compressors as the compression becomes stronger. Reducing k / n k/n k / n from 0.5 to 0.1 increases Δ i p \Delta_{\mathrm{ip}} Δ ip by a factor of 3.0–5.2 for Kronecker JL and of about 5 for layer-wise SRHT and SRFT.
Table 10: Distortion of inner products (Δ i p \Delta_{\mathrm{ip}} Δ 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 k/n = 0.5 k / n = 0.5 and for Adaptive JL are repeated from Table 2 . For Adaptive JL, k / n = 0.240 k/n = 0.240 k / n = 0.240 is set implicitly by the target ε = 0.3 \varepsilon= 0.3 ε = 0.3 from equation (12) .
Table 10.
Kronecker JL remains competitive with layer-wise SRHT and SRFT at all compression rates: at every k / n k/n k / n , one of its variants attains the smallest mean Δ i p \Delta_{\mathrm{ip}} Δ ip among all compressors, although the differences are within one standard deviation. The angle errors of all JL-type methods are of the same order, ranging from 0.55° at k / n = 0.5 k/n = 0.5 k / n = 0.5 to 4.2° at k / n = 0.1 k/n = 0.1 k / n = 0.1 .
Applying SRHT and SRFT to the whole parameter vector does not reduce the distortion. At k / n = 0.5 k/n = 0.5 k / n = 0.5 , it increases Δ i p \Delta_{\mathrm{ip}} Δ ip by a factor of 2.9 for SRHT and 3.9 for SRFT; at smaller k / n k/n k / n , the whole-vector variants are comparable to the layer-wise ones or worse by up to a factor of 1.5.
Rand-k k k yields the largest Δ i p \Delta_{\mathrm{ip}} Δ ip at every compression rate, 4–38 times larger than that of the other compressors, and its distortion grows the fastest as k / n k/n k / n decreases. At the same time, its angle error remains comparable to that of the other methods.
Finally, Adaptive JL with target ε = 0.3 \varepsilon= 0.3 ε = 0.3 selects k / n = 0.240 k/n = 0.240 k / n = 0.240 and attains Δ i p \Delta_{\mathrm{ip}} Δ ip comparable to that of Gaussian Kronecker JL at k / n = 0.5 k/n = 0.5 k / n = 0.5 (96 vs. 94 ⋅ 10 − 4 \cdot10^{-4} ⋅ 1 0 − 4 ), i.e., with less than half the message size.
Table 11 shows that stronger compression substantially reduces the communication required to reach 80% test accuracy. Moderate compression does not slow down training: in all settings, the number of rounds needed to reach 80% is smallest at k / n = 0.5 k/n = 0.5 k / n = 0.5 . At k / n = 0.1 k/n = 0.1 k / n = 0.1 , more rounds are required, but each round is much cheaper, so the total traffic decreases by a factor of 2.8–4.0 compared to k / n = 0.5 k/n = 0.5 k / n = 0.5 and by a factor of 6.7–10.6 compared to k / n = 0.9 k/n = 0.9 k / n = 0.9 . At the same time, the best accuracy at k / n = 0.1 k/n = 0.1 k / n = 0.1 is at most 0.018 lower than at k / n = 0.5 k/n = 0.5 k / n = 0.5 .
Table 11. Table 11: Communication efficiency of Grad-BANT + JL for different compression rates k / n k/n k / n (IID data, 200 rounds, single seed): (a) rounds and (b) traffic in full-gradient uploads (a round costs k / n k/n 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.
Technical Statements
Statement below is crucial for deriving high-probability convergence of proposed methods
Lemma 5. Suppose we have events E 1 , E 2 , … , E n E_1, E_2, \ldots, E_n E 1 , E 2 , … , E n that holds with following probabilities:
P [ E i ] ≥ 1 − δ i , \mathbb{P}[E_i] \ge1-\delta_i, P [ E i ] ≥ 1 − δ i , Then,
P [ ⋂ i = 1 n E i ] ≥ 1 − ∑ i = 1 n δ i \mathbb{P}\left[\bigcap_{i=1}^{n} E_i\right] \ge1-\sum_{i=1}^{n}\delta_i P [ i = 1 ⋂ n E i ] ≥ 1 − i = 1 ∑ n δ i Proof.
P [ ⋂ i = 1 n E i ] = 1 − P [ ⋃ i = 1 n E i ‾ ] ≥ 1 − ∑ i = 1 n P [ E i ‾ ] ≥ 1 − ∑ i = 1 n δ i \mathbb{P}\left[\bigcap_{i=1}^{n} E_i\right] = 1-\mathbb{P}\left[\bigcup_{i=1}^{n}\overline{E_i}\right] \ge1-\sum_{i=1}^{n}\mathbb{P}\left[\overline{E_i}\right] \ge1-\sum_{i=1}^{n}\delta_i P [ i = 1 ⋂ n E i ] = 1 − P [ i = 1 ⋃ n E i ] ≥ 1 − i = 1 ∑ n P [ E i ] ≥ 1 − i = 1 ∑ n δ i
Next lemma will be useful throughout some theorems, allowing us to deal with norms:
Lemma 6 (Young’s inequality). Let x , y ∈ R n x,y \in\mathbb{R}^{n} x , y ∈ R n . Then, for any α > 0 \alpha> 0 α > 0 we have
⟨ x , y ⟩ ≤ 1 2 α ∥ x ∥ 2 + α 2 ∥ y ∥ 2 . \langle x,y\rangle\le\frac{1}{2\alpha}\lVert x\rVert^{2}+\frac{\alpha}{2}\lVert y\rVert^{2}. ⟨ x , y ⟩ ≤ 2 α 1 ∥ x ∥ 2 + 2 α ∥ y ∥ 2 .
JL Statements
We start with the properties of a single sketch: inner-product preservation, moments of the lifted vector, and high-probability norm bounds. We then show how these properties extend to structured matrices, separate layers, and tensor modes. Throughout, S x Sx S x is the compressed vector and S T S x S^{\mathsf{T}}Sx S T S x is the lifted vector used in the update. We write ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ for the Euclidean norm of a vector or the operator norm of a matrix, and ∥ ⋅ ∥ F \|\cdot\|_{F} ∥ ⋅ ∥ F for the Frobenius norm of a matrix or tensor.
From norm preservation to inner products
Lemma 7 (Preservation of scalar product )
Let S S S be a linear JL transform with distortion ε \varepsilon ε and one-vector failure probability δ \delta δ . For every fixed x , y ∈ R n x,y\in\mathbb{R}^{n} x , y ∈ R n ,
P [ ∣ ⟨ S x , S y ⟩ − ⟨ x , y ⟩ ∣ ≤ ε ∥ x ∥ ∥ y ∥ ] ≥ 1 − 2 δ . \mathbb{P}\left[\left|\langle Sx,Sy\rangle-\langle x,y\rangle\right|\leq\varepsilon\|x\|\|y\|\right]\geq1-2\delta. P [ ∣ ⟨ S x , S y ⟩ − ⟨ x , y ⟩ ∣ ≤ ε ∥ x ∥∥ y ∥ ] ≥ 1 − 2 δ .
Proof. The claim is immediate if either vector is zero. By linearity, it is enough to prove it for unit vectors. Apply the JL property to x + y x+y x + y and x − y x-y x − y . With probability at least 1 − 2 δ 1-2\delta 1 − 2 δ , both squared norms are preserved within relative error ε \varepsilon ε . On this event, polarization and the parallelogram identity give
∣ ⟨ S x , S y ⟩ − ⟨ x , y ⟩ ∣ ≤ ε 4 ( ∥ x + y ∥ 2 + ∥ x − y ∥ 2 ) = ε 2 ( ∥ x ∥ 2 + ∥ y ∥ 2 ) = ε . \begin{aligned}
\left|\langle Sx,Sy\rangle-\langle x,y\rangle\right|\leq\frac{\varepsilon}{4}\left(\|x+y\|^{2}+\|x-y\|^{2}\right) \\
&=\frac{\varepsilon}{2}\left(\|x\|^{2}+\|y\|^{2}\right)=\varepsilon.
\end{aligned} ∣ ⟨ S x , S y ⟩ − ⟨ x , y ⟩ ∣ ≤ 4 ε ( ∥ x + y ∥ 2 + ∥ x − y ∥ 2 ) = 2 ε ( ∥ x ∥ 2 + ∥ y ∥ 2 ) = ε .
For general nonzero vectors, apply this bound to x / ∥ x ∥ x/\|x\| x /∥ x ∥ and y / ∥ y ∥ y/\|y\| y /∥ y ∥ , and multiply by ∥ x ∥ ∥ y ∥ \|x\|\|y\| ∥ x ∥∥ y ∥ .
Lemma 8 (Simultaneous upper JL bound )
Let S S S be a linear JL transform with distortion ε \varepsilon ε and one-vector failure probability δ \delta δ . For fixed vectors v 1 , … , v m ∈ R n v_{1},\ldots,v_{m}\in\mathbb{R}^{n} v 1 , … , v m ∈ R n ,
P [ ∥ S v i ∥ 2 ≤ ( 1 + ε ) ∥ v i ∥ 2 for all i = 1 , … , m ] ≥ 1 − m δ . \mathbb{P}\left[\|Sv_{i}\|^{2}\leq(1+\varepsilon)\|v_{i}\|^{2}\ \text{ for all }i=1,\ldots,m\right]\geq1-m\delta. P [ ∥ S v i ∥ 2 ≤ ( 1 + ε ) ∥ v i ∥ 2 for all i = 1 , … , m ] ≥ 1 − m δ .
Proof. Each upper bound fails with probability at most δ \delta δ . Take the union bound over the m m m vectors.
Dense sketches: moments and operator norms
The next identity gives the moments of both dense sketches and the sparse Gaussian construction below. It also allows an independent orthogonal transformation before sketching.
Lemma 9 (Moments of a normalized i.i.d. matrix )
Let A ∈ R k × n A\in\mathbb{R}^{k\times n} A ∈ R k × n have i.i.d. entries with
E A 11 = 0 , E A 11 2 = 1 , E A 11 4 = μ 4 < ∞ . \mathbb{E}A_{11}=0,\qquad\mathbb{E}A_{11}^{2}=1,\qquad\mathbb{E}A_{11}^{4}=\mu_{4}<\infty. E A 11 = 0 , E A 11 2 = 1 , E A 11 4 = μ 4 < ∞. Let U ∈ R n × n U\in\mathbb{R}^{n\times n} U ∈ R n × n be orthogonal and independent of A A A ; U U U may be deterministic or random. For S = A U / k S=AU/\sqrt{k} S = A U / k ,
E [ S T S ] = I n , E ∥ S T S x ∥ 2 = ( 1 + n − 2 + μ 4 k ) ∥ x ∥ 2 . \mathbb{E}[S^{\mathsf{T}}S]=I_{n},\qquad\mathbb{E}\|S^{\mathsf{T}}Sx\|^{2}=\left(1+\frac{n-2+\mu_{4}}{k}\right)\|x\|^{2}. E [ S T S ] = I n , E ∥ S T S x ∥ 2 = ( 1 + k n − 2 + μ 4 ) ∥ x ∥ 2 . The second identity holds for every fixed x ∈ R n x\in\mathbb{R}^{n} x ∈ R n .
Proof. First take U = I n U=I_n U = I n , and write the rows of A A A as column vectors a 1 , … , a k a_1,\ldots,a_k a 1 , … , a k . Since E [ a r a r T ] = I n \mathbb{E}[a_r a_r^{\mathsf{T}}]=I_n E [ a r a r T ] = I n ,
E [ S T S ] = 1 k ∑ r = 1 k E [ a r a r T ] = I n . \mathbb{E}[S^{\mathsf{T}}S]=\frac{1}{k}\sum_{r=1}^{k}\mathbb{E}[a_r a_r^{\mathsf{T}}]=I_n. E [ S T S ] = k 1 r = 1 ∑ k E [ a r a r T ] = I n .
For the second moment, expand
E ∥ A T A x ∥ 2 = ∑ r , s = 1 k E [ ⟨ a r , a s ⟩ ⟨ a r , x ⟩ ⟨ a s , x ⟩ ] . \mathbb{E}\lVert A^{\mathsf{T}}Ax\rVert^2=\sum_{r,s=1}^{k}\mathbb{E}\left[\langle a_r,a_s\rangle\langle a_r,x\rangle\langle a_s,x\rangle\right]. E ∥ A T A x ∥ 2 = r , s = 1 ∑ k E [ ⟨ a r , a s ⟩ ⟨ a r , x ⟩ ⟨ a s , x ⟩ ] .
If r ≠ s r\ne s r = s , conditioning on a r a_r a r shows that the corresponding expectation is E ⟨ a r , x ⟩ 2 = ∥ x ∥ 2 \mathbb{E}\langle a_r,x\rangle^2=\lVert x\rVert^2 E ⟨ a r , x ⟩ 2 = ∥ x ∥ 2 . For a diagonal term, independence and centering of the entries remove all mixed terms, giving
E [ ∥ a r ∥ 2 ⟨ a r , x ⟩ 2 ] = ∑ j = 1 n ( ∑ i ≠ j x i 2 + μ 4 x j 2 ) = ( n − 1 + μ 4 ) ∥ x ∥ 2 . \begin{aligned}
\mathbb{E}\left[\lVert a_r\rVert^2\langle a_r,x\rangle^2\right]=\sum_{j=1}^{n}\left(\sum_{i\ne j}x_i^2+\mu_4x_j^2\right) \\
&=(n-1+\mu_4)\lVert x\rVert^2.
\end{aligned} E [ ∥ a r ∥ 2 ⟨ a r , x ⟩ 2 ] = j = 1 ∑ n i = j ∑ x i 2 + μ 4 x j 2 = ( n − 1 + μ 4 ) ∥ x ∥ 2 .
There are k ( k − 1 ) k(k-1) k ( k − 1 ) off-diagonal terms and k k k diagonal terms. Dividing their sum by k 2 k^2 k 2 yields
E ∥ S T S x ∥ 2 = k ( k − 1 ) + k ( n − 1 + μ 4 ) k 2 ∥ x ∥ 2 = ( 1 + n − 2 + μ 4 k ) ∥ x ∥ 2 . \mathbb{E}\lVert S^{\mathsf{T}}Sx\rVert^2=\frac{k(k-1)+k(n-1+\mu_4)}{k^2}\lVert x\rVert^2=\left(1+\frac{n-2+\mu_4}{k}\right)\lVert x\rVert^2. E ∥ S T S x ∥ 2 = k 2 k ( k − 1 ) + k ( n − 1 + μ 4 ) ∥ x ∥ 2 = ( 1 + k n − 2 + μ 4 ) ∥ x ∥ 2 .
For general U U U , condition on U U U . Orthogonality reduces the calculation to the case just proved with x x x replaced by U x Ux U x , whose norm equals ∥ x ∥ \lVert x\rVert ∥ x ∥ . Averaging over U U U proves both identities.
Lemma 10 (Gaussian and Rademacher moments) Let S ∈ R k × n S\in\mathbb{R}^{k\times n} S ∈ R k × n have independent entries, either S i j ∼ N ( 0 , 1 / k ) S_{ij}\sim\mathcal{N}(0,1/k) S ij ∼ N ( 0 , 1/ k ) or S i j ∈ { − 1 / k , 1 / k } S_{ij}\in\{-1/\sqrt{k},1/\sqrt{k}\} S ij ∈ { − 1/ k , 1/ k } with equal probabilities. In both cases E [ S T S ] = I n \mathbb{E}[S^{\mathsf{T}}S]=I_n E [ S T S ] = I n , and for every fixed x ∈ R n x\in\mathbb{R}^n x ∈ R n ,
E ∥ S T S x ∥ 2 = { n + k + 1 k ∥ x ∥ 2 , Gaussian , n + k − 1 k ∥ x ∥ 2 , Rademacher . \mathbb{E}\lVert S^{\mathsf{T}}Sx\rVert^2=
\begin{cases}
\dfrac{n+k+1}{k}\lVert x\rVert^2, & \text{Gaussian},\\
\dfrac{n+k-1}{k}\lVert x\rVert^2, & \text{Rademacher}.
\end{cases} E ∥ S T S x ∥ 2 = ⎩ ⎨ ⎧ k n + k + 1 ∥ x ∥ 2 , k n + k − 1 ∥ x ∥ 2 , Gaussian , Rademacher .
Proof. Apply Lemma 9 with U = I n U=I_n U = I n . The fourth moment of a standard Gaussian entry is 3, and that of a Rademacher entry is 1.
We next bound the operator norm. Every such bound also controls the reconstructed vector, since for every matrix S S S and every x x x ,
∥ S T S ∥ = ∥ S ∥ 2 , ∥ S T S x ∥ 2 ≤ ∥ S ∥ 4 ∥ x ∥ 2 . \lVert S^{\mathsf{T}}S\rVert=\lVert S\rVert^2,\qquad\lVert S^{\mathsf{T}}Sx\rVert^2\le\lVert S\rVert^4\lVert x\rVert^2. ∥ S T S ∥ = ∥ S ∥ 2 , ∥ S T S x ∥ 2 ≤ ∥ S ∥ 4 ∥ x ∥ 2 .
The following standard estimate will be used for the Rademacher and sparse Gaussian constructions. Its subgaussian norm is defined, for a scalar X X X and a random vector Z Z Z , by
∥ X ∥ ψ 2 : = inf { s > 0 : E e X 2 / s 2 ≤ 2 } , ∥ Z ∥ ψ 2 : = sup ∥ u ∥ = 1 ∥ ⟨ Z , u ⟩ ∥ ψ 2 . \lVert X\rVert_{\psi_2}:=\inf\{s>0:\mathbb{E}e^{X^2/s^2}\le2\},\qquad\lVert Z\rVert_{\psi_2}:=\sup_{\lVert u\rVert=1}\lVert\langle Z,u\rangle\rVert_{\psi_2}. ∥ X ∥ ψ 2 := inf { s > 0 : E e X 2 / s 2 ≤ 2 } , ∥ Z ∥ ψ 2 := ∥ u ∥ = 1 sup ∥⟨ Z , u ⟩ ∥ ψ 2 .
Lemma 11 (Subgaussian operator-norm estimate [39 ] ) Let A ∈ R m × n A \in\mathbb{R}^{m \times n} A ∈ R m × n have independent, mean-zero, isotropic, subgaussian rows A 1 , … , A m A_1,\ldots,A_m A 1 , … , A m , with ∥ A i ∥ ψ 2 ≤ K \lVert A_i\rVert_{\psi_2} \le K ∥ A i ∥ ψ 2 ≤ K for all i i i . There is a universal constant C > 0 C > 0 C > 0 such that, for every t ≥ 0 t \ge0 t ≥ 0 ,
P [ ∥ A ∥ ≤ m + C K 2 ( n + t ) ] ≥ 1 − 2 e − t 2 . \mathbb{P}\left[\lVert A\rVert\le\sqrt{m}+CK^2(\sqrt{n}+t)\right] \ge1-2e^{-t^2}. P [ ∥ A ∥ ≤ m + C K 2 ( n + t ) ] ≥ 1 − 2 e − t 2 .
Lemma 12 (Gaussian and Rademacher operator norms ) There is a universal constant C > 0 C > 0 C > 0 such that, for a Gaussian or a Rademacher JL matrix S ∈ R k × n S \in\mathbb{R}^{k \times n} S ∈ R k × n and every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
∥ S ∥ ≤ 1 + C ( n k + log ( 2 / δ ) k ) . \lVert S\rVert\le1+C\left(\sqrt{\frac{n}{k}}+\sqrt{\frac{\log(2/\delta)}{k}}\right). ∥ S ∥ ≤ 1 + C ( k n + k log ( 2/ δ ) ) . Squaring the right-hand side bounds ∥ S T S ∥ \lVert S^{\mathsf{T}}S\rVert ∥ S T S ∥ ; its fourth power times ∥ x ∥ 2 \lVert x\rVert^2 ∥ x ∥ 2 bounds ∥ S T S x ∥ 2 \lVert S^{\mathsf{T}}Sx\rVert^2 ∥ S T S x ∥ 2 simultaneously for all x ∈ R n x \in\mathbb{R}^n x ∈ R n .
Proof. In the Gaussian case, write S = A / k S=A/\sqrt{k} S = A / k with standard Gaussian entries in A A A . By Vershynin [39 Corollary 7.3.2] , there is a universal constant c 0 > 0 c_0 > 0 c 0 > 0 such that, for every t ≥ 0 t \ge0 t ≥ 0 ,
P [ ∥ A ∥ ≥ k + n + t ] ≤ 2 e − c 0 t 2 . \mathbb{P}\left[\lVert A\rVert\ge\sqrt{k}+\sqrt{n}+t\right] \le2e^{-c_0t^2}. P [ ∥ A ∥ ≥ k + n + t ] ≤ 2 e − c 0 t 2 .
Taking t = log ( 2 / δ ) / c 0 t=\sqrt{\log(2/\delta)/c_0} t = log ( 2/ δ ) / c 0 and dividing by k \sqrt{k} k gives, with probability at least 1 − δ 1-\delta 1 − δ ,
∥ S ∥ ≤ 1 + n k + 1 c 0 log ( 2 / δ ) k , \lVert S\rVert\le1+\sqrt{\frac{n}{k}}+\frac{1}{\sqrt{c_0}}\sqrt{\frac{\log(2/\delta)}{k}}, ∥ S ∥ ≤ 1 + k n + c 0 1 k log ( 2/ δ ) ,
which is the stated bound for any C ≥ max { 1 , c 0 − 1 / 2 } C \ge\max\{1,c_0^{-1/2}\} C ≥ max { 1 , c 0 − 1/2 } .
In the Rademacher case, write again S = A / k S=A/\sqrt{k} S = A / k . Its independent rows are mean-zero and isotropic. For each unit vector u u u , Hoeffding’s lemma gives
E e λ ⟨ A i , u ⟩ ≤ e λ 2 / 2 \mathbb{E}e^{\lambda\langle A_i,u\rangle}\le e^{\lambda^2/2} E e λ ⟨ A i , u ⟩ ≤ e λ 2 /2
for all λ ∈ R \lambda\in\mathbb{R} λ ∈ R , so their subgaussian norms are bounded by a universal constant. Apply Lemma 11 with m = k m=k m = k and t = log ( 2 / δ ) t=\sqrt{\log(2/\delta)} t = log ( 2/ δ ) , and divide by k \sqrt{k} k . Enlarging C C C if necessary, one constant serves both constructions. The remaining claims follow from ∥ S T S ∥ = ∥ S ∥ 2 \lVert S^{\mathsf{T}}S\rVert=\lVert S\rVert^2 ∥ S T S ∥ = ∥ S ∥ 2 and ∥ S T S x ∥ ≤ ∥ S T S ∥ ∥ x ∥ \lVert S^{\mathsf{T}}Sx\rVert\le\lVert S^{\mathsf{T}}S\rVert\lVert x\rVert ∥ S T S x ∥ ≤ ∥ S T S ∥ ∥ x ∥ .
Preserving the total squared norm of several vectors
The convergence proof needs a bound on the sum of the squared norms of the compressed honest gradients. Applying a separate JL guarantee to every gradient would introduce a failure-probability factor equal to the number of honest workers. For Gaussian and Rademacher sketches, we can instead control this sum directly. Place the vectors in the columns of a fixed matrix V ∈ R n × N V \in\mathbb{R}^{n \times N} V ∈ R n × N . Then ∥ V ∥ F 2 \lVert V\rVert_F^2 ∥ V ∥ F 2 is their total squared norm and ∥ S V ∥ F 2 \lVert SV\rVert_F^2 ∥ S V ∥ F 2 is the corresponding quantity after compression. We first give an elementary concentration bound used in the Gaussian case.
Lemma 13 (Weighted chi-square concentration). Let a 1 , … , a r ≥ 0 a_1,\ldots,a_r \ge0 a 1 , … , a r ≥ 0 and let Z 1 , … , Z r Z_1,\ldots,Z_r Z 1 , … , Z r be independent χ k 2 \chi_k^2 χ k 2 random variables. For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
P [ ∣ 1 k ∑ i = 1 r a i Z i − ∑ i = 1 r a i ∣ > ε ∑ i = 1 r a i ] ≤ 2 e − k ε 2 / 16 . \mathbb{P}\left[\left|\frac{1}{k}\sum_{i=1}^{r}a_iZ_i-\sum_{i=1}^{r}a_i\right|>\varepsilon\sum_{i=1}^{r}a_i\right]\le2e^{-k\varepsilon^2/16}. P [ k 1 i = 1 ∑ r a i Z i − i = 1 ∑ r a i > ε i = 1 ∑ r a i ] ≤ 2 e − k ε 2 /16 . Proof. The claim is immediate if all weights vanish. Otherwise, divide the weights by their sum, so that ∑ i a i = 1 \sum_i a_i=1 ∑ i a i = 1 . For a single collection of independent standard Gaussian variables g i g_i g i , the Gaussian moment-generating function gives, for 0 ≤ λ ≤ 1 / 4 0\le\lambda\le1/4 0 ≤ λ ≤ 1/4 ,
log E exp ( λ ∑ i a i ( g i 2 − 1 ) ) = − λ − 1 2 ∑ i log ( 1 − 2 λ a i ) ≤ 4 λ 2 ∑ i a i 2 ≤ 4 λ 2 , \log\mathbb{E}\exp\left(\lambda\sum_i a_i(g_i^2-1)\right)=-\lambda-\frac{1}{2}\sum_i\log(1-2\lambda a_i)\le4\lambda^2\sum_i a_i^2\le4\lambda^2, log E exp ( λ i ∑ a i ( g i 2 − 1 ) ) = − λ − 2 1 i ∑ log ( 1 − 2 λ a i ) ≤ 4 λ 2 i ∑ a i 2 ≤ 4 λ 2 , log E exp ( − λ ∑ i a i ( g i 2 − 1 ) ) = λ − 1 2 ∑ i log ( 1 + 2 λ a i ) ≤ λ 2 ∑ i a i 2 ≤ λ 2 . \log\mathbb{E}\exp\left(-\lambda\sum_i a_i(g_i^2-1)\right)=\lambda-\frac{1}{2}\sum_i\log(1+2\lambda a_i)\le\lambda^2\sum_i a_i^2\le\lambda^2. log E exp ( − λ i ∑ a i ( g i 2 − 1 ) ) = λ − 2 1 i ∑ log ( 1 + 2 λ a i ) ≤ λ 2 i ∑ a i 2 ≤ λ 2 . The second bound also holds for every λ ≥ 0 \lambda\ge0 λ ≥ 0 . Write each Z i Z_i Z i as the sum of k k k independent squared standard Gaussian variables. Independence across these k k k repetitions and the exponential Markov inequality give upper and lower tail bounds
e − k λ ε + 4 k λ 2 and e − k λ ε + k λ 2 , e^{-k\lambda\varepsilon+4k\lambda^2}\qquad\text{and}\qquad e^{-k\lambda\varepsilon+k\lambda^2}, e − k λ ε + 4 k λ 2 and e − k λ ε + k λ 2 , respectively. Taking λ = ε / 8 \lambda=\varepsilon/8 λ = ε /8 in the first bound and λ = ε / 2 \lambda=\varepsilon/2 λ = ε /2 in the second proves the result.
Lemma 14 (Preservation of a fixed Frobenius norm). Let S ∈ R k × n S\in\mathbb{R}^{k\times n} S ∈ R k × n be a Gaussian or Rademacher JL matrix. There is a universal constant c 1 > 0 c_1>0 c 1 > 0 such that, for every fixed matrix V ∈ R n × N V\in\mathbb{R}^{n\times N} V ∈ R n × N and every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
P [ ∣ ∥ S V ∥ F 2 − ∥ V ∥ F 2 ∣ > ε ∥ V ∥ F 2 ] ≤ 2 e − c 1 k ε 2 . \mathbb{P}\left[\left|\|SV\|_F^2-\|V\|_F^2\right|>\varepsilon\|V\|_F^2\right]\le2e^{-c_1k\varepsilon^2}. P [ ∥ S V ∥ F 2 − ∥ V ∥ F 2 > ε ∥ V ∥ F 2 ] ≤ 2 e − c 1 k ε 2 . In particular, the bound does not depend on the number of columns N N N .
Proof. The case V = 0 V=0 V = 0 is immediate.
Gaussian sketches. Take a compact singular value decomposition of V V V , with nonzero singular values σ 1 , … , σ r \sigma_1,\ldots,\sigma_r σ 1 , … , σ r . Gaussian rotational invariance gives
∥ S V ∥ F 2 = d 1 k ∑ i = 1 r σ i 2 Z i , ∥ V ∥ F 2 = ∑ i = 1 r σ i 2 , \|SV\|_F^2 \mathrel{\overset{d}{=}} \frac{1}{k}\sum_{i=1}^{r}\sigma_i^2Z_i,\qquad\|V\|_F^2=\sum_{i=1}^{r}\sigma_i^2, ∥ S V ∥ F 2 = d k 1 i = 1 ∑ r σ i 2 Z i , ∥ V ∥ F 2 = i = 1 ∑ r σ i 2 , where the Z i Z_i Z i are independent χ k 2 \chi_k^2 χ k 2 variables. Apply Lemma 13 with weights σ i 2 \sigma_i^2 σ i 2 .
Rademacher sketches. Let ξ 1 , … , ξ k \xi_1,\ldots,\xi_k ξ 1 , … , ξ k be the rows of k S \sqrt{k}S k S , viewed as column vectors, and set B = V V ⊤ B=VV^\top B = V V ⊤ . Then
k ∥ S V ∥ F 2 = ∑ ℓ = 1 k ξ ℓ ⊤ B ξ ℓ , E ∥ S V ∥ F 2 = tr ( B ) = ∥ V ∥ F 2 . k\|SV\|_F^2=\sum_{\ell=1}^{k}\xi_\ell^\top B\xi_\ell,\qquad\mathbb{E}\|SV\|_F^2=\operatorname{tr}(B)=\|V\|_F^2. k ∥ S V ∥ F 2 = ℓ = 1 ∑ k ξ ℓ ⊤ B ξ ℓ , E ∥ S V ∥ F 2 = tr ( B ) = ∥ V ∥ F 2 . Apply the Hanson–Wright inequality to the concatenated vector of all k n kn k n independent signs and the block-diagonal matrix with k k k copies of B B B . For every s > 0 s>0 s > 0 , this gives
P [ ∣ k ∥ S V ∥ F 2 − k ∥ V ∥ F 2 ∣ > s ] ≤ 2 exp ( − c min { s 2 k ∥ B ∥ F 2 , s ∥ B ∥ } ) . (14) \mathbb{P}\left[\left|k\|SV\|_F^2-k\|V\|_F^2\right|>s\right]\le2\exp\left(-c\min\left\{\frac{s^2}{k\|B\|_F^2},\frac{s}{\|B\|}\right\}\right). \tag*{(14)} P [ k ∥ S V ∥ F 2 − k ∥ V ∥ F 2 > s ] ≤ 2 exp ( − c min { k ∥ B ∥ F 2 s 2 , ∥ B ∥ s } ) . (14)
Since B B B is positive semidefinite, both ∥ B ∥ \lVert B\rVert ∥ B ∥ and ∥ B ∥ F \lVert B\rVert_F ∥ B ∥ F are at most tr ( B ) = ∥ V ∥ F 2 \operatorname{tr}(B)=\lVert V\rVert_F^2 tr ( B ) = ∥ V ∥ F 2 . With s = k ε ∥ V ∥ F 2 s=k\varepsilon\lVert V\rVert_F^2 s = k ε ∥ V ∥ F 2 and 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , the minimum is at least k ε 2 k\varepsilon^2 k ε 2 . Choosing a common constant for the two constructions completes the proof.
This estimate concerns one fixed matrix V V V , rather than all matrices simultaneously. It also applies conditionally when V V V is determined by the past and S S S is sampled independently afterwards. Together with an operator-norm bound, it controls the lifted vectors through
∥ S T S V ∥ F 2 ≤ ∥ S ∥ 2 ∥ S V ∥ F 2 . \lVert S^{\mathsf T}SV\rVert_F^2\leq\lVert S\rVert^2\lVert SV\rVert_F^2. ∥ S T S V ∥ F 2 ≤ ∥ S ∥ 2 ∥ S V ∥ F 2 .
The same Frobenius-norm estimate will allow us to compress a tensor one mode at a time below.
Structured sketches
The following results give the same moment and operator-norm information for SRHT, the FJLT with a sparse Gaussian core, and CountSketch.
Lemma 15 (SRHT ) Assume that n n n is a power of two and 1 ≤ k ≤ n 1\leq k\leq n 1 ≤ k ≤ n . Let H H H be the normalized Walsh–Hadamard matrix, let D D D have independent Rademacher entries on its diagonal, and let T ⊂ [ n ] T\subset[n] T ⊂ [ n ] be a uniformly random k k k -element subset independent of D D D . If R T R_T R T restricts a vector to its coordinates in T T T , define
S = n k R T H D . S=\sqrt{\frac{n}{k}}R_THD. S = k n R T H D . Then
E [ S T S ] = I n , E ∥ S T S x ∥ 2 = n k ∥ x ∥ 2 . \mathbb{E}[S^{\mathsf T}S]=I_n,\qquad\mathbb{E}\lVert S^{\mathsf T}Sx\rVert^2=\frac{n}{k}\lVert x\rVert^2. E [ S T S ] = I n , E ∥ S T S x ∥ 2 = k n ∥ x ∥ 2 . The second identity holds for every fixed x ∈ R n x\in\mathbb{R}^n x ∈ R n . Moreover, ∥ S ∥ = n / k \lVert S\rVert=\sqrt{n/k} ∥ S ∥ = n / k almost surely.
Proof. The matrix R T T R T R_T^{\mathsf T}R_T R T T R T is the coordinate projector onto T T T . Each coordinate is selected with probability k / n k/n k / n , so
E [ R T T R T ] = k n I n . \mathbb{E}[R_T^{\mathsf T}R_T]=\frac{k}{n}I_n. E [ R T T R T ] = n k I n .
Since H D HD H D is orthogonal, conditioning on D D D gives
E [ S T S ∣ D ] = n k D H T E [ R T T R T ] H D = I n . \mathbb{E}[S^{\mathsf T}S\mid D]=\frac{n}{k}DH^{\mathsf T}\mathbb{E}[R_T^{\mathsf T}R_T]HD=I_n. E [ S T S ∣ D ] = k n D H T E [ R T T R T ] H D = I n .
Also, R T R T T = I k R_TR_T^{\mathsf T}=I_k R T R T T = I k implies
S S T = n k I k , ( S T S ) 2 = n k S T S . SS^{\mathsf T}=\frac{n}{k}I_k,\qquad(S^{\mathsf T}S)^2=\frac{n}{k}S^{\mathsf T}S. S S T = k n I k , ( S T S ) 2 = k n S T S .
The first identity gives ∥ S ∥ = n / k \lVert S\rVert=\sqrt{n/k} ∥ S ∥ = n / k . The second and unbiasedness give
E ∥ S T S x ∥ 2 = x T E [ ( S T S ) 2 ] x = n k ∥ x ∥ 2 . \mathbb{E}\lVert S^{\mathsf T}Sx\rVert^2=x^{\mathsf T}\mathbb{E}[(S^{\mathsf T}S)^2]x=\frac{n}{k}\lVert x\rVert^2. E ∥ S T S x ∥ 2 = x T E [( S T S ) 2 ] x = k n ∥ x ∥ 2 .
Lemma 16 (FJLT with a sparse Gaussian core). Assume that n n n is a power of two. Let H H H be the normalized Walsh–Hadamard matrix, let D D D be a diagonal Rademacher matrix, and let P ∈ R k × n P \in\mathbb{R}^{k \times n} P ∈ R k × n have independent entries
P i j = { 0 , with probability 1 − q , g i j / q , with probability q , g i j ∼ N ( 0 , 1 ) , q ∈ ( 0 , 1 ] . P_{ij} =
\begin{cases}
0, & \text{with probability } 1-q,\\
g_{ij}/\sqrt{q}, & \text{with probability } q,
\end{cases}
\qquad g_{ij} \sim\mathcal{N}(0,1), \qquad q \in(0,1]. P ij = { 0 , g ij / q , with probability 1 − q , with probability q , g ij ∼ N ( 0 , 1 ) , q ∈ ( 0 , 1 ] . Assume that all random choices are independent, and define S = P H D / k S = PHD/\sqrt{k} S = P H D / k . Then
E [ S T S ] = I n , E ∥ S T S x ∥ 2 = ( 1 + n − 2 + 3 / q k ) ∥ x ∥ 2 \mathbb{E}[S^{\mathsf{T}}S] = I_n, \qquad\mathbb{E}\lVert S^{\mathsf{T}}Sx\rVert^2 = \left(1+\frac{n-2+3/q}{k}\right)\lVert x\rVert^2 E [ S T S ] = I n , E ∥ S T S x ∥ 2 = ( 1 + k n − 2 + 3/ q ) ∥ x ∥ 2 for every fixed x ∈ R n x \in\mathbb{R}^n x ∈ R n .
Moreover, for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
∥ S ∥ ≤ 1 + C q ( n k + log ( 2 / δ ) k ) , \lVert S\rVert\le1+\frac{C}{q}\left(\sqrt{\frac{n}{k}}+\sqrt{\frac{\log(2/\delta)}{k}}\right), ∥ S ∥ ≤ 1 + q C ( k n + k log ( 2/ δ ) ) , where C > 0 C>0 C > 0 is universal.
Proof. The entries of P P P satisfy
E P 11 = 0 , E P 11 2 = 1 , E P 11 4 = 3 / q . \mathbb{E}P_{11}=0,\qquad\mathbb{E}P_{11}^{2}=1,\qquad\mathbb{E}P_{11}^{4}=3/q. E P 11 = 0 , E P 11 2 = 1 , E P 11 4 = 3/ q .
The moment identities follow from Lemma 9 with A = P A=P A = P and the independent orthogonal matrix U = H D U=HD U = H D . To bound the operator norm, observe that
E e λ P 11 = 1 − q + q e λ 2 / ( 2 q ) ≤ e λ 2 / ( 2 q ) . \mathbb{E}e^{\lambda P_{11}}=1-q+qe^{\lambda^2/(2q)}\le e^{\lambda^2/(2q)}. E e λ P 11 = 1 − q + q e λ 2 / ( 2 q ) ≤ e λ 2 / ( 2 q ) .
By independence, for a row p p p of P P P and a unit vector u u u ,
E e ⟨ p , u ⟩ ≤ ∏ j = 1 n e λ 2 u j 2 / ( 2 q ) = e λ 2 / ( 2 q ) . \mathbb{E}e^{\langle p,u\rangle}\le\prod_{j=1}^{n}e^{\lambda^2u_j^2/(2q)}=e^{\lambda^2/(2q)}. E e ⟨ p , u ⟩ ≤ j = 1 ∏ n e λ 2 u j 2 / ( 2 q ) = e λ 2 / ( 2 q ) .
Thus the rows are mean-zero and isotropic, with subgaussian norms at most C / q C/\sqrt{q} C / q . Lemma 11 , with t = log ( 2 / δ ) t=\sqrt{\log(2/\delta)} t = log ( 2/ δ ) , gives
∥ P ∥ ≤ k + C q ( n + log ( 2 / δ ) ) \lVert P\rVert\le\sqrt{k}+\frac{C}{q}\left(\sqrt{n}+\sqrt{\log(2/\delta)}\right) ∥ P ∥ ≤ k + q C ( n + log ( 2/ δ ) )
with the claimed probability, after changing the universal constant. Finally, orthogonality of H D HD H D gives ∥ S ∥ = ∥ P ∥ / k \lVert S\rVert=\lVert P\rVert/\sqrt{k} ∥ S ∥ = ∥ P ∥ / k .
:::
Lemma 17 (CountSketch). Let h ( 1 ) , … , h ( n ) h(1),\ldots,h(n) h ( 1 ) , … , h ( n ) be independent and uniform on [ k ] [k] [ k ] , and let σ ( 1 ) , … , σ ( n ) \sigma(1),\ldots,\sigma(n) σ ( 1 ) , … , σ ( n ) be independent Rademacher signs, independent of h h h . Define S ∈ R k × n S \in\mathbb{R}^{k \times n} S ∈ R k × n by
S r j = σ ( j ) 1 { h ( j ) = r } . S_{rj}=\sigma(j)1_{\{h(j)=r\}}. S r j = σ ( j ) 1 { h ( j ) = r } . Then
E [ S T S ] = I n , E ∥ S T S x ∥ 2 = ( 1 + n − 1 k ) ∥ x ∥ 2 \mathbb{E}[S^{\mathsf{T}}S]=I_n,\qquad\mathbb{E}\lVert S^{\mathsf{T}}Sx\rVert^2=\left(1+\frac{n-1}{k}\right)\lVert x\rVert^2 E [ S T S ] = I n , E ∥ S T S x ∥ 2 = ( 1 + k n − 1 ) ∥ x ∥ 2 for every fixed x ∈ R n x \in\mathbb{R}^n x ∈ R n .
If N r = # { j ∈ [ n ] : h ( j ) = r } N_r = \#\{j \in[n] : h(j) = r\} N r = # { j ∈ [ n ] : h ( j ) = r } is the number of coordinates assigned to row r r r , then
S S T = diag ( N 1 , … , N k ) , ∥ S ∥ 2 = max 1 ≤ r ≤ k N r . SS^{\mathsf{T}} = \operatorname{diag}(N_1,\ldots,N_k), \qquad\lVert S\rVert^2 = \max_{1\le r\le k} N_r. S S T = diag ( N 1 , … , N k ) , ∥ S ∥ 2 = 1 ≤ r ≤ k max N r .
Consequently, for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
∥ S ∥ 2 ≤ n k + 2 n k log k δ + 2 3 log k δ . \lVert S\rVert^2 \le\frac{n}{k}+\sqrt{\frac{2n}{k}\log\frac{k}{\delta}}+\frac{2}{3}\log\frac{k}{\delta}. ∥ S ∥ 2 ≤ k n + k 2 n log δ k + 3 2 log δ k .
Proof. Every column contains one nonzero entry of magnitude one. Hence ( S T S ) j j = 1 (S^{\mathsf{T}}S)_{jj}=1 ( S T S ) j j = 1 , while for i ≠ j i\ne j i = j ,
( S T S ) i j = σ ( i ) σ ( j ) 1 { h ( i ) = h ( j ) } . (S^{\mathsf{T}}S)_{ij}=\sigma(i)\sigma(j)\mathbf{1}_{\{h(i)=h(j)\}}. ( S T S ) ij = σ ( i ) σ ( j ) 1 { h ( i ) = h ( j )} .
Independent centered signs make the off-diagonal expectations zero, proving unbiasedness. To compute the second moment, write
( S T S x − x ) j = σ ( j ) ∑ i ≠ j σ ( i ) 1 { h ( i ) = h ( j ) } x i . (S^{\mathsf{T}}Sx-x)_j=\sigma(j)\sum_{i\ne j}\sigma(i)\mathbf{1}_{\{h(i)=h(j)\}}x_i. ( S T S x − x ) j = σ ( j ) i = j ∑ σ ( i ) 1 { h ( i ) = h ( j )} x i .
After squaring, the mixed terms vanish in expectation. Since each pair of coordinates collides with probability 1 / k 1/k 1/ k ,
E ∥ S T S x − x ∥ 2 = 1 k ∑ j = 1 n ∑ i ≠ j x i 2 = n − 1 k ∥ x ∥ 2 . \mathbb{E}\lVert S^{\mathsf{T}}Sx-x\rVert^2=\frac{1}{k}\sum_{j=1}^{n}\sum_{i\ne j}x_i^2=\frac{n-1}{k}\lVert x\rVert^2. E ∥ S T S x − x ∥ 2 = k 1 j = 1 ∑ n i = j ∑ x i 2 = k n − 1 ∥ x ∥ 2 .
Unbiasedness now gives the claimed second moment.
Distinct rows of S S S have disjoint supports, and the squared norm of row r r r is N r N_r N r . This proves the formula for S S T SS^{\mathsf{T}} S S T and its operator norm. For each r r r , the count N r N_r N r is binomial with mean n / k n/k n / k . Bernstein’s inequality gives, for every u ≥ 0 u\ge0 u ≥ 0 ,
P [ N r > n k + 2 n u k + 2 u 3 ] ≤ e − u . \mathbb{P}\left[N_r>\frac{n}{k}+\sqrt{\frac{2nu}{k}}+\frac{2u}{3}\right]\le e^{-u}. P [ N r > k n + k 2 n u + 3 2 u ] ≤ e − u .
Take u = log ( k / δ ) u=\log(k/\delta) u = log ( k / δ ) and apply the union bound over the k k k rows.
Per-layer sketching
We now combine the one-layer guaranties using the block-diagonal structure of the sketch. Write
x = ( x 1 , … , x W ) , x w ∈ R n w , n = ∑ w = 1 W n w , S = diag ( S 1 , … , S W ) , x=(x_1,\ldots,x_W), \qquad x_w\in\mathbb{R}^{n_w}, \qquad n=\sum_{w=1}^{W}n_w, \qquad S=\operatorname{diag}(S_1,\ldots,S_W), x = ( x 1 , … , x W ) , x w ∈ R n w , n = w = 1 ∑ W n w , S = diag ( S 1 , … , S W ) ,
where S w ∈ R k w × n w S_w\in\mathbb{R}^{k_w\times n_w} S w ∈ R k w × n w . The key identities are
∥ x ∥ 2 = ∑ w = 1 W ∥ x w ∥ 2 , ∥ S x ∥ 2 = ∑ w = 1 W ∥ S w x w ∥ 2 . \lVert x\rVert^2=\sum_{w=1}^{W}\lVert x_w\rVert^2, \qquad\lVert Sx\rVert^2=\sum_{w=1}^{W}\lVert S_wx_w\rVert^2. ∥ x ∥ 2 = w = 1 ∑ W ∥ x w ∥ 2 , ∥ S x ∥ 2 = w = 1 ∑ W ∥ S w x w ∥ 2 .
S T S = diag ( S 1 T S 1 , … , S W T S W ) , ∥ S T S x ∥ 2 = ∑ w = 1 W ∥ S w T S w x w ∥ 2 . S^{\mathsf{T}}S=\operatorname{diag}(S_1^{\mathsf{T}}S_1,\ldots,S_W^{\mathsf{T}}S_W), \qquad\lVert S^{\mathsf{T}}Sx\rVert^2=\sum_{w=1}^{W}\lVert S_w^{\mathsf{T}}S_wx_w\rVert^2. S T S = diag ( S 1 T S 1 , … , S W T S W ) , ∥ S T S x ∥ 2 = w = 1 ∑ W ∥ S w T S w x w ∥ 2 .
As in the main text, for x ≠ 0 x\ne0 x = 0 we use the energy fractions
α w ( x ) = ∥ x w ∥ 2 ∥ x ∥ 2 , ∑ w = 1 W α w ( x ) = 1. \alpha_w(x)=\frac{\lVert x_w\rVert^2}{\lVert x\rVert^2}, \qquad\sum_{w=1}^{W}\alpha_w(x)=1. α w ( x ) = ∥ x ∥ 2 ∥ x w ∥ 2 , w = 1 ∑ W α w ( x ) = 1.
Thus, squared-norm bounds combine as energy-weighted averages, whereas operator-norm bounds combine by taking the largest layer bound.
Theorem 4 (Per-layer JL properties) Suppose that, for each w w w , there are ε w ≥ 0 \varepsilon_w \ge0 ε w ≥ 0 and δ w ∈ [ 0 , 1 ] \delta_w \in[0,1] δ w ∈ [ 0 , 1 ] such that, for every fixed u ∈ R n w u \in\mathbb{R}^{n_w} u ∈ R n w ,
P [ ∣ ∥ S w u ∥ 2 − ∥ u ∥ 2 ∣ > ε w ∥ u ∥ 2 ] ≤ δ w . \mathbb{P}\left[\left|\lVert S_wu\rVert^2-\lVert u\rVert^2\right|>\varepsilon_w\lVert u\rVert^2\right]\le\delta_w. P [ ∥ S w u ∥ 2 − ∥ u ∥ 2 > ε w ∥ u ∥ 2 ] ≤ δ w . Then, for every fixed x ≠ 0 x\ne0 x = 0 ,
P [ ∣ ∥ S x ∥ 2 − ∥ x ∥ 2 ∣ > ( ∑ w = 1 W α w ( x ) ε w ) ∥ x ∥ 2 ] ≤ ∑ w = 1 W δ w . \mathbb{P}\left[\left|\lVert Sx\rVert^2-\lVert x\rVert^2\right|>\left(\sum_{w=1}^{W}\alpha_w(x)\varepsilon_w\right)\lVert x\rVert^2\right]\le\sum_{w=1}^{W}\delta_w. P [ ∥ S x ∥ 2 − ∥ x ∥ 2 > ( w = 1 ∑ W α w ( x ) ε w ) ∥ x ∥ 2 ] ≤ w = 1 ∑ W δ w . In particular, if max w ε w ≤ ε \max_w\varepsilon_w\le\varepsilon max w ε w ≤ ε , then S S S satisfies the ( ε , ∑ w δ w ) (\varepsilon,\sum_w\delta_w) ( ε , ∑ w δ w ) distributional JL property. If the blocks are independent, both failure bounds can be replaced by 1 − ∏ w = 1 W ( 1 − δ w ) 1-\prod_{w=1}^{W}(1-\delta_w) 1 − ∏ w = 1 W ( 1 − δ w ) .
Proof. Fix x ≠ 0 x\ne0 x = 0 . With probability at least 1 − ∑ w δ w 1-\sum_w\delta_w 1 − ∑ w δ w , every layer satisfies ∣ ∥ S w x w ∥ 2 − ∥ x w ∥ 2 ∣ ≤ ε w ∥ x w ∥ 2 \left|\lVert S_wx_w\rVert^2-\lVert x_w\rVert^2\right|\le\varepsilon_w\lVert x_w\rVert^2 ∥ S w x w ∥ 2 − ∥ x w ∥ 2 ≤ ε w ∥ x w ∥ 2 . On this event,
∣ ∥ S x ∥ 2 − ∥ x ∥ 2 ∣ ≤ ∑ w = 1 W ∣ ∥ S w x w ∥ 2 − ∥ x w ∥ 2 ∣ ≤ ∑ w = 1 W ε w ∥ x w ∥ 2 = ( ∑ w = 1 W α w ( x ) ε w ) ∥ x ∥ 2 . \left|\lVert Sx\rVert^2-\lVert x\rVert^2\right|
\le\sum_{w=1}^{W}\left|\lVert S_wx_w\rVert^2-\lVert x_w\rVert^2\right|
\le\sum_{w=1}^{W}\varepsilon_w\lVert x_w\rVert^2
=\left(\sum_{w=1}^{W}\alpha_w(x)\varepsilon_w\right)\lVert x\rVert^2. ∥ S x ∥ 2 − ∥ x ∥ 2 ≤ w = 1 ∑ W ∥ S w x w ∥ 2 − ∥ x w ∥ 2 ≤ w = 1 ∑ W ε w ∥ x w ∥ 2 = ( w = 1 ∑ W α w ( x ) ε w ) ∥ x ∥ 2 .
The weighted distortion is at most max w ε w \max_w\varepsilon_w max w ε w , since the weights sum to one. For independent blocks, the layer success events are independent, so their intersection has probability at least ∏ w ( 1 − δ w ) \prod_w(1-\delta_w) ∏ w ( 1 − δ w ) .
The same block identities give the properties of the lifted map S T S S^{\mathsf{T}}S S T S needed in the optimization analysis. None of the next three results requires independence between layers.
Lemma 18 (Per-layer unbiasedness) If E [ S w T S w ] = I n w \mathbb{E}[S_w^{\mathsf{T}}S_w]=I_{n_w} E [ S w T S w ] = I n w for every layer, then
E [ S T S ] = I n , E [ S T S x ] = x for all x ∈ R n . \mathbb{E}[S^{\mathsf{T}}S]=I_n,\qquad\mathbb{E}[S^{\mathsf{T}}Sx]=x\quad\text{for all }x\in\mathbb{R}^n. E [ S T S ] = I n , E [ S T S x ] = x for all x ∈ R n .
Proof. Take expectations in the block-diagonal identity for S T S S^{\mathsf{T}}S S T S .
Lemma 19 (Per-layer second moment) Suppose, for each layer, there is ω w ≥ 0 \omega_w\ge0 ω w ≥ 0 such that
E ∥ S w T S w u ∥ 2 ≤ ω w ∥ u ∥ 2 for every u ∈ R n w . \mathbb{E}\lVert S_w^{\mathsf{T}}S_wu\rVert^2\le\omega_w\lVert u\rVert^2\qquad\text{for every }u\in\mathbb{R}^{n_w}. E ∥ S w T S w u ∥ 2 ≤ ω w ∥ u ∥ 2 for every u ∈ R n w . Then, for every x ≠ 0 x\ne0 x = 0 ,
E ∥ S T S x ∥ 2 ≤ ( ∑ w = 1 W α w ( x ) ω w ) ∥ x ∥ 2 ≤ ( max w ω w ) ∥ x ∥ 2 . \mathbb{E}\lVert S^{\mathsf{T}}Sx\rVert^2\le\left(\sum_{w=1}^{W}\alpha_w(x)\omega_w\right)\lVert x\rVert^2\le\left(\max_w\omega_w\right)\lVert x\rVert^2. E ∥ S T S x ∥ 2 ≤ ( w = 1 ∑ W α w ( x ) ω w ) ∥ x ∥ 2 ≤ ( w max ω w ) ∥ x ∥ 2 .
Proof. Using the sum of squared block norms and linearity of expectation gives
E ∥ S T S x ∥ 2 = ∑ w = 1 W E ∥ S w T S w x w ∥ 2 ≤ ∑ w = 1 W ω w ∥ x w ∥ 2 . \mathbb{E}\lVert S^{\mathsf{T}}Sx\rVert^2
=\sum_{w=1}^{W}\mathbb{E}\lVert S_w^{\mathsf{T}}S_wx_w\rVert^2
\le\sum_{w=1}^{W}\omega_w\lVert x_w\rVert^2. E ∥ S T S x ∥ 2 = w = 1 ∑ W E ∥ S w T S w x w ∥ 2 ≤ w = 1 ∑ W ω w ∥ x w ∥ 2 .
Divide by ∥ x ∥ 2 \lVert x\rVert^2 ∥ x ∥ 2 and use ∑ w α w ( x ) = 1 \sum_w\alpha_w(x)=1 ∑ w α w ( x ) = 1 .
Lemma 20 (Per-layer high-probability norm bound ) Suppose P [ ∥ S w ∥ 2 ≤ c w ] ≥ 1 − δ w \mathbb{P}[\lVert Sw\rVert^{2} \le c_w] \ge1-\delta_w P [∥ S w ∥ 2 ≤ c w ] ≥ 1 − δ w for every layer. Then, with probability at least 1 − ∑ w δ w 1-\sum_w \delta_w 1 − ∑ w δ w ,
∥ S ∥ 2 = ∥ S T S ∥ ≤ max w c w , \lVert S\rVert^{2}=\lVert S^{\mathsf{T}}S\rVert\le\max_w c_w, ∥ S ∥ 2 = ∥ S T S ∥ ≤ w max c w , and, on the same event, for every x ≠ 0 x\ne0 x = 0 ,
∥ S x ∥ 2 ≤ ( ∑ w = 1 W α w ( x ) c w ) ∥ x ∥ 2 , \lVert Sx\rVert^{2}\le\left(\sum_{w=1}^{W}\alpha_w(x)c_w\right)\lVert x\rVert^{2}, ∥ S x ∥ 2 ≤ ( w = 1 ∑ W α w ( x ) c w ) ∥ x ∥ 2 , ∥ S T S x ∥ 2 ≤ ( ∑ w = 1 W α w ( x ) c w 2 ) ∥ x ∥ 2 . \lVert S^{\mathsf{T}}Sx\rVert^{2}\le\left(\sum_{w=1}^{W}\alpha_w(x)c_w^{2}\right)\lVert x\rVert^{2}. ∥ S T S x ∥ 2 ≤ ( w = 1 ∑ W α w ( x ) c w 2 ) ∥ x ∥ 2 .
Proof. A union bound ensures that all inequalities ∥ S w ∥ 2 ≤ c w \lVert S_w\rVert^{2}\le c_w ∥ S w ∥ 2 ≤ c w hold on an event of the stated probability. On this event, block diagonality gives
∥ S ∥ 2 = ∥ S T S ∥ = max w ∥ S w ∥ 2 ≤ max w c w . \lVert S\rVert^{2}=\lVert S^{\mathsf{T}}S\rVert=\max_w\lVert S_w\rVert^{2}\le\max_w c_w. ∥ S ∥ 2 = ∥ S T S ∥ = w max ∥ S w ∥ 2 ≤ w max c w .
For any x x x , summing the layer bounds gives
∥ S x ∥ 2 ≤ ∑ w c w ∥ x w ∥ 2 , ∥ S T S x ∥ 2 ≤ ∑ w ∥ S w ∥ 4 ∥ x w ∥ 2 ≤ ∑ w c w 2 ∥ x w ∥ 2 . \lVert Sx\rVert^{2}\le\sum_w c_w\lVert x_w\rVert^{2},\qquad
\lVert S^{\mathsf{T}}Sx\rVert^{2}\le\sum_w\lVert S_w\rVert^{4}\lVert x_w\rVert^{2}\le\sum_w c_w^{2}\lVert x_w\rVert^{2}. ∥ S x ∥ 2 ≤ w ∑ c w ∥ x w ∥ 2 , ∥ S T S x ∥ 2 ≤ w ∑ ∥ S w ∥ 4 ∥ x w ∥ 2 ≤ w ∑ c w 2 ∥ x w ∥ 2 .
Substituting ∥ x w ∥ 2 = α w ( x ) ∥ x ∥ 2 \lVert x_w\rVert^{2}=\alpha_w(x)\lVert x\rVert^{2} ∥ x w ∥ 2 = α w ( x ) ∥ x ∥ 2 proves the claim.
Allocating the sketch dimensions. Theorem 4 shows that a layer containing little of a vector’s energy can tolerate a larger relative distortion. For Gaussian and Rademacher sketches, this allows a smaller sketch dimension, since k w k_w k w scales as ε w − 2 \varepsilon_w^{-2} ε w − 2 . The following allocation uses this weighted distortion budget for a fixed vector.
Corollary 2 (Energy-aware allocation ) Fix x ≠ 0 x\ne0 x = 0 and ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) . For every layer with α w ( x ) > 0 \alpha_w(x)>0 α w ( x ) > 0 , choose a Gaussian or Rademacher sketch with
ε w = ε α w ( x ) − 1 / 3 ∑ j = 1 W α j ( x ) 2 / 3 , δ w = δ W , k w = ⌈ C log ( 2 W / δ ) ε w 2 ⌉ , \varepsilon_w=\frac{\varepsilon\alpha_w(x)^{-1/3}}{\sum_{j=1}^{W}\alpha_j(x)^{2/3}},\qquad
\delta_w=\frac{\delta}{W},\qquad
k_w=\left\lceil\frac{C\log(2W/\delta)}{\varepsilon_w^{2}}\right\rceil, ε w = ∑ j = 1 W α j ( x ) 2/3 ε α w ( x ) − 1/3 , δ w = W δ , k w = ⌈ ε w 2 C log ( 2 W / δ ) ⌉ , where C > 0 C>0 C > 0 is a sufficiently large universal constant. Assume that ε w < 1 \varepsilon_w<1 ε w < 1 and k w ≤ n w k_w\le n_w k w ≤ n w for all such layers. Layers with x w = 0 x_w=0 x w = 0 are omitted, with k w = 0 k_w=0 k w = 0 .
Then, for this fixed vector,
P [ ∣ ∥ S x ∥ 2 − ∥ x ∥ 2 ∣ ≤ ε ∥ x ∥ 2 ] ≥ 1 − δ , \mathbb{P}\left[\left|\lVert Sx\rVert^{2}-\lVert x\rVert^{2}\right|\le\varepsilon\lVert x\rVert^{2}\right]\ge1-\delta, P [ ∥ S x ∥ 2 − ∥ x ∥ 2 ≤ ε ∥ x ∥ 2 ] ≥ 1 − δ , and the total number of transmitted coordinates satisfies
∑ w = 1 W k w = Θ ( log ( 2 W / δ ) ε 2 ( ∑ w = 1 W α w ( x ) 2 / 3 ) 3 ) . \sum_{w=1}^{W}k_w=\Theta\left(\frac{\log(2W/\delta)}{\varepsilon^{2}}\left(\sum_{w=1}^{W}\alpha_w(x)^{2/3}\right)^{3}\right). w = 1 ∑ W k w = Θ ε 2 log ( 2 W / δ ) ( w = 1 ∑ W α w ( x ) 2/3 ) 3 .
Proof. The one-layer JL guarantees and a union bound give simultaneous success on all nonzero layers with probability at least 1 − δ 1-\delta 1 − δ . Zero layers contribute no error for the fixed vector x x x . The total relative distortion on this event is at most
∑ w : α w ( x ) > 0 α w ( x ) ε w = ε ∑ w : α w ( x ) > 0 α w ( x ) 2 / 3 ∑ j = 1 W α j ( x ) 2 / 3 = ε , \sum_{w:\alpha_w(x)>0}\alpha_w(x)\varepsilon_w
=\varepsilon\frac{\sum_{w:\alpha_w(x)>0}\alpha_w(x)^{2/3}}{\sum_{j=1}^{W}\alpha_j(x)^{2/3}}
=\varepsilon, w : α w ( x ) > 0 ∑ α w ( x ) ε w = ε ∑ j = 1 W α j ( x ) 2/3 ∑ w : α w ( x ) > 0 α w ( x ) 2/3 = ε ,
as in Theorem 4. To count coordinates, substitute the chosen distortions:
∑ w : α w ( x ) > 0 1 ε w 2 = ( ∑ j = 1 W α j ( x ) 2 / 3 ) 2 ε 2 ∑ w : α w ( x ) > 0 α w ( x ) 2 / 3 = 1 ε 2 ( ∑ w = 1 W α w ( x ) 2 / 3 ) 3 . \sum_{w:\alpha_w(x)>0}\frac{1}{\varepsilon_w^2}
=
\frac{\left(\sum_{j=1}^{W}\alpha_j(x)^{2/3}\right)^2}{\varepsilon^2}
\sum_{w:\alpha_w(x)>0}\alpha_w(x)^{2/3}
=
\frac{1}{\varepsilon^2}\left(\sum_{w=1}^{W}\alpha_w(x)^{2/3}\right)^3. w : α w ( x ) > 0 ∑ ε w 2 1 = ε 2 ( ∑ j = 1 W α j ( x ) 2/3 ) 2 w : α w ( x ) > 0 ∑ α w ( x ) 2/3 = ε 2 1 ( w = 1 ∑ W α w ( x ) 2/3 ) 3 .
Since 0 < ε w < 1 0<\varepsilon_w<1 0 < ε w < 1 and log ( 2 W / δ ) ≥ log 2 \log(2W/\delta)\ge\log2 log ( 2 W / δ ) ≥ log 2 , rounding each nonzero layer’s dimension changes it by at most a universal constant factor. Multiplying the last identity by log ( 2 W / δ ) \log(2W/\delta) log ( 2 W / δ ) therefore gives the stated total dimension.
The allocation depends on the energy profile of x x x : its guarantee is for that fixed vector, with these dimensions chosen before the sketches are drawn. It applies only in the stated feasible regime ε w < 1 \varepsilon_w<1 ε w < 1 and k w ≤ n w k_w\le n_w k w ≤ n w .
Kronecker sketches: compressing one tensor mode at a time
Per-layer sketches act on separate blocks. A Kronecker sketch instead applies several smaller matrices to different modes of the same tensor. We use the notation from the main text: for X ∈ R n 1 × ⋯ × n d X\in\mathbb{R}^{n_1\times\cdots\times n_d} X ∈ R n 1 × ⋯ × n d and S j ∈ R k j × n j S_j\in\mathbb{R}^{k_j\times n_j} S j ∈ R k j × n j , define
S ( X ) = X × 1 S 1 ⋯ × d S d , S = S d ⊗ ⋯ ⊗ S 1 . S(X)=X\times_1S_1\cdots\times_dS_d,\qquad S=S_d\otimes\cdots\otimes S_1. S ( X ) = X × 1 S 1 ⋯ × d S d , S = S d ⊗ ⋯ ⊗ S 1 .
Here X × j S j X\times_jS_j X × j S j means multiplication along the j j j th mode. More explicitly, if X ( j ) X_{(j)} X ( j ) is the matrix formed by arranging the mode-j j j fibers of X X X as columns, then
( X × j S j ) ( j ) = S j X ( j ) , vec ( S ( X ) ) = S vec ( X ) . (X\times_jS_j)_{(j)}=S_jX_{(j)},\qquad\operatorname{vec}(S(X))=S\operatorname{vec}(X). ( X × j S j ) ( j ) = S j X ( j ) , vec ( S ( X )) = S vec ( X ) .
Both unfolding and vectorization preserve the Frobenius norm. Thus a single mode multiplication can be analyzed using a matrix Frobenius-norm bound. We prove this composition step once, then apply it to dense sketches and to general JL factors.
Theorem 5 (Combining independent Frobenius-norm guarantees) Let X X X be a fixed tensor and let S 1 , … , S d S_1,\ldots,S_d S 1 , … , S d be independent random matrices. Fix ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and δ 1 , … , δ d ∈ [ 0 , 1 ] \delta_1,\ldots,\delta_d\in[0,1] δ 1 , … , δ d ∈ [ 0 , 1 ] . Suppose that, for each j j j and every fixed matrix V V V with n j n_j n j rows,
P [ ∣ ∥ S j V ∥ F 2 − ∥ V ∥ F 2 ∣ > ε 4 d ∥ V ∥ F 2 ] ≤ δ j . \mathbb{P}\left[\left|\lVert S_jV\rVert_F^2-\lVert V\rVert_F^2\right|>\frac{\varepsilon}{4d}\lVert V\rVert_F^2\right]\le\delta_j. P [ ∥ S j V ∥ F 2 − ∥ V ∥ F 2 > 4 d ε ∥ V ∥ F 2 ] ≤ δ j . Then
P [ ∣ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 ∣ > ε ∥ X ∥ F 2 ] ≤ ∑ j = 1 d δ j . \mathbb{P}\left[\left|\lVert S(X)\rVert_F^2-\lVert X\rVert_F^2\right|>\varepsilon\lVert X\rVert_F^2\right]\le\sum_{j=1}^{d}\delta_j. P [ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 > ε ∥ X ∥ F 2 ] ≤ j = 1 ∑ d δ j . Proof. Let X ( 0 ) = X X^{(0)}=X X ( 0 ) = X and X ( j ) = X ( j − 1 ) × j S j X^{(j)}=X^{(j-1)}\times_jS_j X ( j ) = X ( j − 1 ) × j S j denote the tensor after the first j j j multiplications. Conditional on S 1 , … , S j − 1 S_1,\ldots,S_{j-1} S 1 , … , S j − 1 , the tensor X ( j − 1 ) X^{(j-1)} X ( j − 1 ) is fixed and S j S_j S j remains independent. The assumption applied to ( X ( j − 1 ) ) ( j ) (X^{(j-1)})_{(j)} ( X ( j − 1 ) ) ( j ) therefore gives
P [ ∣ ∥ X ( j ) ∥ F 2 − ∥ X ( j − 1 ) ∥ F 2 ∣ > ε 4 d ∥ X ( j − 1 ) ∥ F 2 ∣ S 1 , … , S j − 1 ] ≤ δ j . \mathbb{P}\left[\left|\lVert X^{(j)}\rVert_F^2-\lVert X^{(j-1)}\rVert_F^2\right|>\frac{\varepsilon}{4d}\lVert X^{(j-1)}\rVert_F^2\mathrel{\Big|}S_1,\ldots,S_{j-1}\right]\le\delta_j. P [ ∥ X ( j ) ∥ F 2 − ∥ X ( j − 1 ) ∥ F 2 > 4 d ε ∥ X ( j − 1 ) ∥ F 2 S 1 , … , S j − 1 ] ≤ δ j . Taking expectations and a union bound, all d d d steps satisfy their bounds with probability at least 1 − ∑ j δ j 1-\sum_j\delta_j 1 − ∑ j δ j . On this event,
( 1 − ε 4 d ) d ∥ X ∥ F 2 ≤ ∥ S ( X ) ∥ F 2 ≤ ( 1 + ε 4 d ) d ∥ X ∥ F 2 . \left(1-\frac{\varepsilon}{4d}\right)^d\lVert X\rVert_F^2\le\lVert S(X)\rVert_F^2\le\left(1+\frac{\varepsilon}{4d}\right)^d\lVert X\rVert_F^2. ( 1 − 4 d ε ) d ∥ X ∥ F 2 ≤ ∥ S ( X ) ∥ F 2 ≤ ( 1 + 4 d ε ) d ∥ X ∥ F 2 .
For 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , Bernoulli’s inequality and 1 + u ≤ e u 1+u\le e^u 1 + u ≤ e u give
( 1 − ε 4 d ) d ≥ 1 − ε 4 ≥ 1 − ε , ( 1 + ε 4 d ) d ≤ e ε / 4 ≤ 1 + ε . \left(1-\frac{\varepsilon}{4d}\right)^d\ge1-\frac{\varepsilon}{4}\ge1-\varepsilon,\qquad\left(1+\frac{\varepsilon}{4d}\right)^d\le e^{\varepsilon/4}\le1+\varepsilon. ( 1 − 4 d ε ) d ≥ 1 − 4 ε ≥ 1 − ε , ( 1 + 4 d ε ) d ≤ e ε /4 ≤ 1 + ε .
This proves the claim. The proof also shows that it is enough to bound the conditional failure probability at each step; a simultaneous guarantee over all possible intermediate tensors is not required.
Theorem 6 (Gaussian and Rademacher Kronecker sketches ) Let the factors S j ∈ R k j × n j S_j\in\mathbb{R}^{k_j\times n_j} S j ∈ R k j × n j be independent Gaussian or Rademacher JL matrices. There is a universal constant c > 0 c>0 c > 0 such that, for every fixed tensor X X X and every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
P [ ∣ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 ∣ > ε ∥ X ∥ F 2 ] ≤ 2 ∑ j = 1 d e − c ε 2 k j / d 2 ≤ 2 d e − c ε 2 min j k j / d 2 . \mathbb{P}\left[\left|\|S(X)\|_F^2-\|X\|_F^2\right|>\varepsilon\|X\|_F^2\right]\le2\sum_{j=1}^{d}e^{-c\varepsilon^2k_j/d^2}\le2d e^{-c\varepsilon^2\min_j k_j/d^2}. P [ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 > ε ∥ X ∥ F 2 ] ≤ 2 j = 1 ∑ d e − c ε 2 k j / d 2 ≤ 2 d e − c ε 2 m i n j k j / d 2 . Consequently, failure probability at most δ \delta δ is ensured by
min 1 ≤ j ≤ d k j ≥ C d 2 ε 2 log 2 d δ , \min_{1\le j\le d} k_j\ge C\frac{d^2}{\varepsilon^2}\log\frac{2d}{\delta}, 1 ≤ j ≤ d min k j ≥ C ε 2 d 2 log δ 2 d , where C > 0 C>0 C > 0 is a sufficiently large universal constant. The same bounds hold for ∥ S x ∥ 2 2 \|Sx\|_2^2 ∥ S x ∥ 2 2 with x = vec ( X ) x=\operatorname{vec}(X) x = vec ( X ) .
Proof. Lemma 14 , with distortion ε / ( 4 d ) \varepsilon/(4d) ε / ( 4 d ) , bounds the failure probability at step j j j by 2 e − c 1 k j ε 2 / ( 16 d 2 ) 2e^{-c_1k_j\varepsilon^2/(16d^2)} 2 e − c 1 k j ε 2 / ( 16 d 2 ) . Apply the conditioning argument of Theorem 5 and set c = c 1 / 16 c=c_1/16 c = c 1 /16 . The dimension bound follows by requiring each of the d d d terms to be at most δ / d \delta/d δ / d . Vectorization gives the final assertion.
When only a fixed-vector JL guarantee is available. The preceding dense-sketch result uses the Frobenius-norm estimate of Lemma 14 , whose failure probability is independent of the matrix rank. For another construction, we can obtain a Frobenius-norm guarantee from fixed-vector bounds, at the cost of a rank factor.
Lemma 21 (From fixed vectors to a fixed matrix ) Fix ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and δ ∈ [ 0 , 1 ] \delta\in[0,1] δ ∈ [ 0 , 1 ] . Let S ∈ R k × n S\in\mathbb{R}^{k\times n} S ∈ R k × n be a random matrix such that, for every fixed vector u ∈ R n u\in\mathbb{R}^n u ∈ R n ,
P [ ∣ ∥ S u ∥ 2 2 − ∥ u ∥ 2 ∣ > ε ∥ u ∥ 2 ] ≤ δ . \mathbb{P}\left[\left|\|Su\|_2^2-\|u\|^2\right|>\varepsilon\|u\|^2\right]\le\delta. P [ ∥ S u ∥ 2 2 − ∥ u ∥ 2 > ε ∥ u ∥ 2 ] ≤ δ . Then, for every fixed matrix V V V with n n n rows,
P [ ∣ ∥ S V ∥ F 2 − ∥ V ∥ F 2 ∣ > ε ∥ V ∥ F 2 ] ≤ rank ( V ) δ . \mathbb{P}\left[\left|\|SV\|_F^2-\|V\|_F^2\right|>\varepsilon\|V\|_F^2\right]\le\operatorname{rank}(V)\delta. P [ ∥ S V ∥ F 2 − ∥ V ∥ F 2 > ε ∥ V ∥ F 2 ] ≤ rank ( V ) δ . Proof. The assertion is immediate for V = 0 V=0 V = 0 . Otherwise, let u i u_i u i be its left singular vectors and σ i > 0 \sigma_i>0 σ i > 0 its nonzero singular values. Then
∥ S V ∥ F 2 = ∑ i σ i 2 ∥ S u i ∥ 2 , ∥ V ∥ F 2 = ∑ i σ i 2 . \|SV\|_F^2=\sum_i\sigma_i^2\|Su_i\|^2,\qquad\|V\|_F^2=\sum_i\sigma_i^2. ∥ S V ∥ F 2 = i ∑ σ i 2 ∥ S u i ∥ 2 , ∥ V ∥ F 2 = i ∑ σ i 2 . There are rank ( V ) \operatorname{rank}(V) rank ( V ) unit vectors u i u_i u i . A union bound ensures that all their squared norms are preserved within ε \varepsilon ε with failure probability at most rank ( V ) δ \operatorname{rank}(V)\delta rank ( V ) δ . Multiplying their bounds by σ i 2 \sigma_i^2 σ i 2 and summing proves the claim.
Theorem 7 (Kronecker sketches from fixed-vector guarantees) Fix ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and δ 1 , … , δ d ∈ [ 0 , 1 ] \delta_1,\ldots,\delta_d \in[0,1] δ 1 , … , δ d ∈ [ 0 , 1 ] . Let X X X be fixed and let S 1 , … , S d S_1,\ldots,S_d S 1 , … , S d be independent. Suppose that, for each j j j and every fixed u ∈ R n j u \in\mathbb{R}^{n_j} u ∈ R n j ,
P [ ∣ ∥ S j u ∥ 2 − ∥ u ∥ 2 ∣ > ε 4 d ∥ u ∥ 2 ] ≤ δ j . \mathbb{P}\left[\left|\|S_j u\|^2-\|u\|^2\right|>\frac{\varepsilon}{4d}\|u\|^2\right]\leq\delta_j. P [ ∥ S j u ∥ 2 − ∥ u ∥ 2 > 4 d ε ∥ u ∥ 2 ] ≤ δ j . Then
P [ ∣ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 ∣ > ε ∥ X ∥ F 2 ] ≤ ∑ j = 1 d rank ( X ( j ) ) δ j . \mathbb{P}\left[\left|\|S(X)\|_F^2-\|X\|_F^2\right|>\varepsilon\|X\|_F^2\right]\leq\sum_{j=1}^{d}\operatorname{rank}(X_{(j)})\delta_j. P [ ∥ S ( X ) ∥ F 2 − ∥ X ∥ F 2 > ε ∥ X ∥ F 2 ] ≤ j = 1 ∑ d rank ( X ( j ) ) δ j . Proof. Use the intermediate tensors X ( j ) X^{(j)} X ( j ) from Theorem 5. The first j − 1 j-1 j − 1 mode multiplications only form linear combinations of columns in the mode-j j j unfolding. Hence
rank ( ( X ( j − 1 ) ) ( j ) ) ≤ rank ( X ( j ) ) . \operatorname{rank}\left((X^{(j-1)})_{(j)}\right)\leq\operatorname{rank}(X_{(j)}). rank ( ( X ( j − 1 ) ) ( j ) ) ≤ rank ( X ( j ) ) . Conditional on the first j − 1 j-1 j − 1 factors, Lemma 21 therefore bounds the failure probability of step j j j by rank ( X ( j ) ) δ j \operatorname{rank}(X_{(j)})\delta_j rank ( X ( j ) ) δ j . The same union bound and multiplication of stepwise norm bounds complete the proof. □
The two composition theorems can be used at any desired distortion ε \varepsilon ε : evaluate each factor’s available failure bound at ε / ( 4 d ) \varepsilon/(4d) ε / ( 4 d ) and substitute it for δ j \delta_j δ j . For Gaussian and Rademacher factors, the direct Frobenius bound gives the stronger, rank-independent result above.
The lifted operator. Finally, the algebra of Kronecker products transfers unbiasedness and operator-norm bounds from the factors to the full sketch.
Lemma 22 (Unbiasedness and norm of Kronecker sketches) For independent factors S j ∈ R k j × n j S_j \in\mathbb{R}^{k_j\times n_j} S j ∈ R k j × n j , let S = S d ⊗ ⋯ ⊗ S 1 S=S_d\otimes\cdots\otimes S_1 S = S d ⊗ ⋯ ⊗ S 1 . If E [ S j ⊤ S j ] = I n j \mathbb{E}[S_j^\top S_j]=I_{n_j} E [ S j ⊤ S j ] = I n j for every j j j , then
E [ S ⊤ S ] = I n 1 ⋯ n d . \mathbb{E}[S^\top S]=I_{n_1\cdots n_d}. E [ S ⊤ S ] = I n 1 ⋯ n d . For every realization,
∥ S ∥ = ∏ j = 1 d ∥ S j ∥ . \|S\|=\prod_{j=1}^{d}\|S_j\|. ∥ S ∥ = j = 1 ∏ d ∥ S j ∥. In particular, whenever ∥ S j ∥ 2 ≤ c j \|S_j\|^2\leq c_j ∥ S j ∥ 2 ≤ c j for all j j j ,
∥ S ∥ 2 = ∥ S ⊤ S ∥ ≤ ∏ j = 1 d c j , ∥ S ⊤ S x ∥ 2 ≤ ( ∏ j = 1 d c j ) 2 ∥ x ∥ 2 for all x . \|S\|^2=\|S^\top S\|\leq\prod_{j=1}^{d}c_j,\qquad\|S^\top Sx\|^2\leq\left(\prod_{j=1}^{d}c_j\right)^2\|x\|^2\quad\text{for all }x. ∥ S ∥ 2 = ∥ S ⊤ S ∥ ≤ j = 1 ∏ d c j , ∥ S ⊤ S x ∥ 2 ≤ ( j = 1 ∏ d c j ) 2 ∥ x ∥ 2 for all x . Proof. The mixed-product identity gives
S ⊤ S = ( S d ⊤ S d ) ⊗ ⋯ ⊗ ( S 1 ⊤ S 1 ) . S^\top S=(S_d^\top S_d)\otimes\cdots\otimes(S_1^\top S_1). S ⊤ S = ( S d ⊤ S d ) ⊗ ⋯ ⊗ ( S 1 ⊤ S 1 ) . Independence lets us take expectations factor by factor, proving unbiasedness. The singular values of a Kronecker product are products of the singular values of its factors, which proves the operator-norm identity. The remaining bounds follow from ∥ S ⊤ S ∥ = ∥ S ∥ 2 \|S^\top S\|=\|S\|^2 ∥ S ⊤ S ∥ = ∥ S ∥ 2 and ∥ S ⊤ S x ∥ ≤ ∥ S ⊤ S ∥ ∥ x ∥ \|S^\top Sx\|\leq\|S^\top S\|\|x\| ∥ S ⊤ S x ∥ ≤ ∥ S ⊤ S ∥∥ x ∥ . □
These results separate the ingredients needed later: norm and inner-product preservation control geometry in the compressed space, while moments and operator norms control the lifted update. A structured construction can be used in the high-probability convergence theorem once its parameters provide all three sketch events specified in Appendix § 9 .
Byzantine-robust Analysis
We prove convergence for fixed realized local and trusted objectives satisfying Assumptions 1, 2, and 3. The constants in these assumptions describe the optimization instance directly; no statistical model for the trusted dataset is imposed.
Descent and convergence
Let F t \mathcal{F}_t F t denote the history before sampling S t S_t S t , including the fixed objectives, the current iterate, and all previous randomness and messages, and write E t [ ⋅ ] = E [ ⋅ ∣ F t ] \mathbb{E}_t[\cdot]=\mathbb{E}[\cdot\mid\mathcal{F}_t] E t [ ⋅ ] = E [ ⋅ ∣ F t ] . The gradients g 0 t = ∇ f 0 ( x t ) g_0^t=\nabla f_0(x^t) g 0 t = ∇ f 0 ( x t ) , g t = ∇ f ( x t ) g^t=\nabla f(x^t) g t = ∇ f ( x t ) , and g i t = ∇ f i ( x t ) g_i^t=\nabla f_i(x^t) g i t = ∇ f i ( x t ) for i ∈ G i\in\mathcal{G} i ∈ G are F t \mathcal{F}_t F t -measurable. The sketch S t S_t S t is independent of F t \mathcal{F}_t F t , while Byzantine messages may depend on the current sketch and honest messages. No worker has access to future sketch randomness. All probabilities and expectations below keep the objectives and the initial iterate fixed.
We first derive an estimate for the scalar product that appears in both convergence proofs.
Lemma 23 Let x ∈ R n x\in\mathbb{R}^n x ∈ R n satisfy the reference-accuracy inequality in Assumption 3. Then, for every ε ∈ [ 0 , 1 ) \varepsilon\in[0,1) ε ∈ [ 0 , 1 ) ,
⟨ ∇ f 0 ( x ) , ∇ f ( x ) ⟩ − ε ∥ ∇ f 0 ( x ) ∥ ∥ ∇ f ( x ) ∥ ≥ 1 − η 1 − ε 2 2 ∥ ∇ f ( x ) ∥ 2 − η 0 2 . (15) \left\langle\nabla f_0(x),\nabla f(x)\right\rangle-\varepsilon\left\|\nabla f_0(x)\right\|\left\|\nabla f(x)\right\|\geq\frac{1-\eta_1-\varepsilon^2}{2}\left\|\nabla f(x)\right\|^2-\frac{\eta_0}{2}. \tag*{(15)} ⟨ ∇ f 0 ( x ) , ∇ f ( x ) ⟩ − ε ∥ ∇ f 0 ( x ) ∥ ∥ ∇ f ( x ) ∥ ≥ 2 1 − η 1 − ε 2 ∥ ∇ f ( x ) ∥ 2 − 2 η 0 . (15) Proof. Let g 0 = ∇ f 0 ( x ) g_0=\nabla f_0(x) g 0 = ∇ f 0 ( x ) and g = ∇ f ( x ) g=\nabla f(x) g = ∇ f ( x ) . By completing the square,
⟨ g 0 , g ⟩ − ε ∥ g 0 ∥ ∥ g ∥ = 1 2 ( ∥ g 0 ∥ − ε ∥ g ∥ ) 2 + 1 2 ( ( 1 − ε 2 ) ∥ g ∥ 2 − ∥ g 0 − g ∥ 2 ) \left\langle g_0,g\right\rangle-\varepsilon\left\|g_0\right\|\left\|g\right\|=\frac{1}{2}\left(\left\|g_0\right\|-\varepsilon\left\|g\right\|\right)^2+\frac{1}{2}\left((1-\varepsilon^2)\left\|g\right\|^2-\left\|g_0-g\right\|^2\right) ⟨ g 0 , g ⟩ − ε ∥ g 0 ∥ ∥ g ∥ = 2 1 ( ∥ g 0 ∥ − ε ∥ g ∥ ) 2 + 2 1 ( ( 1 − ε 2 ) ∥ g ∥ 2 − ∥ g 0 − g ∥ 2 ) ≥ 1 − η 1 − ε 2 2 ∥ g ∥ 2 − η 0 2 , \geq\frac{1-\eta_1-\varepsilon^2}{2}\left\|g\right\|^2-\frac{\eta_0}{2}, ≥ 2 1 − η 1 − ε 2 ∥ g ∥ 2 − 2 η 0 , where the last inequality follows from Assumption 3.
Further, we establish the descent lemma used for convergence both in expectation and with high probability.
Lemma 24 Let f 0 f_0 f 0 have an L L L -Lipschitz gradient. Then every iteration of Algorithm 1 satisfies f 0 ( x t + 1 ) ≤ f 0 ( x t ) f_0(x^{t+1})\leq f_0(x^t) f 0 ( x t + 1 ) ≤ f 0 ( x t ) and
f 0 ( x t + 1 ) ≤ f 0 ( x t ) − γ β M ⟨ g 0 t , ∑ i ∈ G u i t ⟩ + L γ 2 β 2 M ∑ i ∈ G ∥ u i t ∥ 2 , f_0(x^{t+1})\leq f_0(x^t)-\frac{\gamma\beta}{M}\left\langle g_0^t,\sum_{i\in\mathcal{G}}u_i^t\right\rangle+\frac{L\gamma^2\beta}{2M}\sum_{i\in\mathcal{G}}\left\|u_i^t\right\|^2, f 0 ( x t + 1 ) ≤ f 0 ( x t ) − M γ β ⟨ g 0 t , i ∈ G ∑ u i t ⟩ + 2 M L γ 2 β i ∈ G ∑ u i t 2 , where u i t = S t ⊤ y i t u_i^t=S_t^\top y_i^t u i t = S t ⊤ y i t . For honest workers, u i t = S t ⊤ S t g i t u_i^t=S_t^\top S_tg_i^t u i t = S t ⊤ S t g i t .
Proof. The initial weights are non-negative and sum to one, and both branches of the weight update preserve these properties. Set
v t = ∑ i = 1 M ω i t I [ θ i t > 0 ] u i t , q i t = [ θ i t ] 0 , Q t = ∑ i = 1 M q i t . v^t=\sum_{i=1}^{M}\omega_i^t\mathbb{I}_{[\theta_i^t>0]}u_i^t,\qquad q_i^t=[\theta_i^t]_0,\qquad Q^t=\sum_{i=1}^{M}q_i^t. v t = i = 1 ∑ M ω i t I [ θ i t > 0 ] u i t , q i t = [ θ i t ] 0 , Q t = i = 1 ∑ M q i t . Applying convexity of the squared norm to the vectors I [ θ i t > 0 ] u i t \mathbb{I}_{[\theta_i^t>0]}u_i^t I [ θ i t > 0 ] u i t with weights ω i t \omega_i^t ω i t gives
∥ v t ∥ 2 ≤ ∑ i = 1 M ω i t I [ θ i t > 0 ] ∥ u i t ∥ 2 . \left\|v^t\right\|^2\leq\sum_{i=1}^{M}\omega_i^t\mathbb{I}_{[\theta_i^t>0]}\left\|u_i^t\right\|^2. v t 2 ≤ i = 1 ∑ M ω i t I [ θ i t > 0 ] u i t 2 .
Applying smoothness to the actual aggregated update, we obtain
f 0 ( x t + 1 ) ≤ f 0 ( x t ) − γ ⟨ g 0 t , v t ⟩ + L γ 2 2 ∥ v t ∥ 2 ≤ f 0 ( x t ) − γ ∑ i = 1 M ω i t 1 [ θ i t > 0 ] ( ⟨ g 0 t , u i t ⟩ − L γ 2 ∥ u i t ∥ 2 ) = f 0 ( x t ) − γ ∑ i = 1 M ω i t q i t ≤ f 0 ( x t ) . \begin{aligned}
f_0(x^{t+1}) &\le f_0(x^t)-\gamma\langle g_0^t,v^t\rangle+\frac{L\gamma^2}{2}\lVert v^t\rVert^2 \le f_0(x^t)-\gamma\sum_{i=1}^{M}\omega_i^t\mathbb{1}_{[\theta_i^t>0]}\left(\langle g_0^t,u_i^t\rangle-\frac{L\gamma}{2}\lVert u_i^t\rVert^2\right)\\
&=f_0(x^t)-\gamma\sum_{i=1}^{M}\omega_i^tq_i^t\le f_0(x^t).
\end{aligned} f 0 ( x t + 1 ) ≤ f 0 ( x t ) − γ ⟨ g 0 t , v t ⟩ + 2 L γ 2 ∥ v t ∥ 2 ≤ f 0 ( x t ) − γ i = 1 ∑ M ω i t 1 [ θ i t > 0 ] ( ⟨ g 0 t , u i t ⟩ − 2 L γ ∥ u i t ∥ 2 ) = f 0 ( x t ) − γ i = 1 ∑ M ω i t q i t ≤ f 0 ( x t ) .
If Q t > 0 Q^t>0 Q t > 0 , the weight update gives
∑ i = 1 M ω i t q i t = ( 1 − β ) ∑ i = 1 M ω i t − 1 q i t + β ∑ i = 1 M ( q i t ) 2 Q t ≥ β ∑ i = 1 M ( q i t ) 2 Q t ≥ β Q t M ≥ β M ∑ i ∈ G θ i t . \sum_{i=1}^{M}\omega_i^tq_i^t=(1-\beta)\sum_{i=1}^{M}\omega_i^{t-1}q_i^t+\beta\frac{\sum_{i=1}^{M}(q_i^t)^2}{Q^t}\ge\beta\frac{\sum_{i=1}^{M}(q_i^t)^2}{Q^t}\ge\frac{\beta Q^t}{M}\ge\frac{\beta}{M}\sum_{i\in\mathcal{G}}\theta_i^t. i = 1 ∑ M ω i t q i t = ( 1 − β ) i = 1 ∑ M ω i t − 1 q i t + β Q t ∑ i = 1 M ( q i t ) 2 ≥ β Q t ∑ i = 1 M ( q i t ) 2 ≥ M β Q t ≥ M β i ∈ G ∑ θ i t .
The first inequality drops a non-negative term. The second follows from ( Q t ) 2 ≤ M ∑ i ( q i t ) 2 (Q^t)^2\le M\sum_i(q_i^t)^2 ( Q t ) 2 ≤ M ∑ i ( q i t ) 2 , and the last uses Q t ≥ ∑ i ∈ G q i t ≥ ∑ i ∈ G θ i t Q^t\ge\sum_{i\in\mathcal{G}}q_i^t\ge\sum_{i\in\mathcal{G}}\theta_i^t Q t ≥ ∑ i ∈ G q i t ≥ ∑ i ∈ G θ i t . If Q t = 0 Q^t=0 Q t = 0 , then v t = 0 v^t=0 v t = 0 and ∑ i ∈ G θ i t ≤ 0 \sum_{i\in\mathcal{G}}\theta_i^t\le0 ∑ i ∈ G θ i t ≤ 0 . Thus, in both cases,
f 0 ( x t + 1 ) ≤ f 0 ( x t ) − γ β M ∑ i ∈ G θ i t . f_0(x^{t+1})\le f_0(x^t)-\frac{\gamma\beta}{M}\sum_{i\in\mathcal{G}}\theta_i^t. f 0 ( x t + 1 ) ≤ f 0 ( x t ) − M γ β i ∈ G ∑ θ i t .
Substituting θ i t = ⟨ g 0 t , u i t ⟩ − L γ 2 ∥ u i t ∥ 2 \theta_i^t=\langle g_0^t,u_i^t\rangle-\frac{L\gamma}{2}\lVert u_i^t\rVert^2 θ i t = ⟨ g 0 t , u i t ⟩ − 2 L γ ∥ u i t ∥ 2 proves the claimed bound. The argument uses smoothness of f 0 f_0 f 0 and convexity of the squared norm, without assuming convexity of f 0 f_0 f 0 .
We are now ready to present the convergence results. First, we derive convergence in expectation. To cover the different sketches mentioned above, we introduce two assumptions.
Assumption 4 (Unbiasedness) The lifted operator is conditionally unbiased if, for every F t \mathcal{F}_t F t -measurable vector v ∈ R n v\in\mathbb{R}^n v ∈ R n ,
E t [ S t T S t v ] = v . \mathbb{E}_t[S_t^{\mathsf{T}}S_tv]=v. E t [ S t T S t v ] = v .
Assumption 5 (Second moment boundedness in expectation) There exists Ω ≥ 1 \Omega\ge1 Ω ≥ 1 such that, for every F t \mathcal{F}_t F t -measurable vector v ∈ R n v\in\mathbb{R}^n v ∈ R n ,
E t ∥ S t T S t v ∥ 2 ≤ Ω ∥ v ∥ 2 . \mathbb{E}_t\lVert S_t^{\mathsf{T}}S_tv\rVert^2\le\Omega\lVert v\rVert^2. E t ∥ S t T S t v ∥ 2 ≤ Ω ∥ v ∥ 2 .
Theorem 8 Suppose that Assumptions 1, 2, 3, 4, and 5 hold. Let T ≥ 1 T\ge1 T ≥ 1 be an integer, β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] , Δ 0 = f 0 ( x 0 ) − f i n f \Delta_0=f_0(x^0)-f^{\mathrm{inf}} Δ 0 = f 0 ( x 0 ) − f inf , and choose γ > 0 \gamma>0 γ > 0 such that
D E ≔ 1 − η 1 − L γ Ω ( 1 + δ 2 ) > 0. D_E\mathrel{\mathop{\coloneqq}}1-\eta_1-L\gamma\Omega(1+\delta_2)>0. D E : = 1 − η 1 − L γ Ω ( 1 + δ 2 ) > 0. Then, after T T T iterations of Algorithm 1,
1 T ∑ t = 0 T − 1 E ∥ ∇ f ( x t ) ∥ 2 ≤ 2 M Δ 0 γ β G D E T + η 0 + L γ Ω δ 1 D E . (16) \frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\lVert\nabla f(x^t)\rVert^2\le\frac{2M\Delta_0}{\gamma\beta G D_E T}+\frac{\eta_0+L\gamma\Omega\delta_1}{D_E}. \tag*{(16)} T 1 t = 0 ∑ T − 1 E ∥ ∇ f ( x t ) ∥ 2 ≤ γ β G D E T 2 M Δ 0 + D E η 0 + L γ Ω δ 1 . (16)
In particular, if 0 < γ ≤ 1 − η 1 2 L Ω ( 1 + δ 2 ) 0 < \gamma\le\frac{1-\eta_1}{2L\Omega(1+\delta_2)} 0 < γ ≤ 2 L Ω ( 1 + δ 2 ) 1 − η 1 , then
1 T ∑ t = 0 T − 1 E ∥ ∇ f ( x t ) ∥ 2 ≤ 4 M Δ 0 γ β G ( 1 − η 1 ) T + 2 η 0 1 − η 1 + 2 L γ Ω δ 1 1 − η 1 . (17) \frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\lVert\nabla f(x^t)\rVert^2 \le\frac{4M\Delta_0}{\gamma\beta G(1-\eta_1)T}+\frac{2\eta_0}{1-\eta_1}+\frac{2L\gamma\Omega\delta_1}{1-\eta_1}. \tag*{(17)} T 1 t = 0 ∑ T − 1 E ∥ ∇ f ( x t ) ∥ 2 ≤ γ β G ( 1 − η 1 ) T 4 M Δ 0 + 1 − η 1 2 η 0 + 1 − η 1 2 L γ Ω δ 1 . (17)
Proof. Taking conditional expectation in Lemma 24 and using 1 G ∑ i ∈ G g i t = g t \frac{1}{G}\sum_{i\in G}g_i^t=g^t G 1 ∑ i ∈ G g i t = g t , we obtain
E t f 0 ( x t + 1 ) ≤ f 0 ( x t ) − γ β G M ⟨ g 0 t , g t ⟩ + L γ 2 β Ω 2 M ∑ i ∈ G ∥ g i t ∥ 2 ≤ f 0 ( x t ) − γ β G 2 M ( ( 1 − η 1 ) ∥ g t ∥ 2 − η 0 ) + L γ 2 β Ω G 2 M ( ( 1 + δ 2 ) ∥ g t ∥ 2 + δ 1 ) = f 0 ( x t ) − γ β G 2 M ( D E ∥ g t ∥ 2 − η 0 − L γ Ω δ 1 ) . \begin{aligned}
\mathbb{E}_t f_0(x^{t+1}) \le f_0(x^t)-\frac{\gamma\beta G}{M}\langle g_0^t,g^t\rangle+\frac{L\gamma^2\beta\Omega}{2M}\sum_{i\in G}\lVert g_i^t\rVert^2 \\
&\le f_0(x^t)-\frac{\gamma\beta G}{2M}\left((1-\eta_1)\lVert g^t\rVert^2-\eta_0\right)+\frac{L\gamma^2\beta\Omega G}{2M}\left((1+\delta_2)\lVert g^t\rVert^2+\delta_1\right) \\
&= f_0(x^t)-\frac{\gamma\beta G}{2M}\left(D_E\lVert g^t\rVert^2-\eta_0-L\gamma\Omega\delta_1\right).
\end{aligned} E t f 0 ( x t + 1 ) ≤ f 0 ( x t ) − M γ β G ⟨ g 0 t , g t ⟩ + 2 M L γ 2 β Ω i ∈ G ∑ ∥ g i t ∥ 2 ≤ f 0 ( x t ) − 2 M γ β G ( ( 1 − η 1 ) ∥ g t ∥ 2 − η 0 ) + 2 M L γ 2 β Ω G ( ( 1 + δ 2 ) ∥ g t ∥ 2 + δ 1 ) = f 0 ( x t ) − 2 M γ β G ( D E ∥ g t ∥ 2 − η 0 − L γ Ω δ 1 ) .
Here, the second inequality uses Lemma 23 with ε = 0 \varepsilon=0 ε = 0 and equation (7) : Assumption 3 controls alignment, while Assumption 2 bounds the honest squared norms. Taking full expectation, summing over t = 0 , … , T − 1 t=0,\ldots,T-1 t = 0 , … , T − 1 , and using f 0 ( x T ) ≥ f 0 f i n f_0(x^T)\ge f_0^{\mathrm{fin}} f 0 ( x T ) ≥ f 0 fin gives equation (16) . Under the displayed stepsize restriction, D E ≥ ( 1 − η 1 ) / 2 D_E\ge(1-\eta_1)/2 D E ≥ ( 1 − η 1 ) /2 , which proves the last bound.
For fresh Gaussian and Rademacher matrices, Lemmas 2 and 3 give Ω = ( n + k + 1 ) / k \Omega=(n+k+1)/k Ω = ( n + k + 1 ) / k and Ω = ( n + k − 1 ) / k \Omega=(n+k-1)/k Ω = ( n + k − 1 ) / k , respectively. The expectation is over the subsequent algorithmic randomness for fixed objectives satisfying the stated assumptions.
We now derive convergence with high probability. The proof needs three events for each fresh sketch: preservation of one inner product, control of the total compressed honest energy, and an operator-norm bound.
Theorem 9 (Theorem 1 from the main part ). Under the assumptions and notation of Theorem 1, except for its stepsize restriction, define
c γ ≔ L γ ρ ( 1 + ε ) , D γ ≔ d − ( 1 + δ 2 ) c γ . c_\gamma\coloneqq L\gamma\rho(1+\varepsilon),\qquad D_\gamma\coloneqq d-(1+\delta_2)c_\gamma. c γ : = L γ ρ ( 1 + ε ) , D γ : = d − ( 1 + δ 2 ) c γ . More generally, for every γ > 0 \gamma>0 γ > 0 with D γ > 0 D_\gamma>0 D γ > 0 , we have
1 T ∑ t = 0 T − 1 ∥ ∇ f ( x t ) ∥ 2 ≤ 2 M Δ 0 γ β G D γ T + η 0 + c γ δ 1 D γ . (18) \frac{1}{T}\sum_{t=0}^{T-1}\lVert\nabla f(x^t)\rVert^2\le\frac{2M\Delta_0}{\gamma\beta G D_\gamma T}+\frac{\eta_0+c_\gamma\delta_1}{D_\gamma}. \tag*{(18)} T 1 t = 0 ∑ T − 1 ∥ ∇ f ( x t ) ∥ 2 ≤ γ β G D γ T 2 M Δ 0 + D γ η 0 + c γ δ 1 . (18) with probability at least 1 − δ 1-\delta 1 − δ . The stepsize in Theorem 1 gives equation (11) .
Proof. Set q = δ / ( 4 T ) q=\delta/(4T) q = δ / ( 4 T ) and let V t ∈ R n × G V_t\in\mathbb{R}^{n\times G} V t ∈ R n × G be the matrix whose columns are the honest gradients g i t g_i^t g i t . Conditional on F t \mathcal{F}_t F t , both V t V_t V t and the pair ( g 0 t , g t ) (g_0^t,g^t) ( g 0 t , g t ) are fixed. Lemma 14 gives
P [ ∥ S t V t ∥ F 2 > ( 1 + ε ) ∥ V t ∥ F 2 ∣ F t ] ≤ 2 e − c 1 k ε 2 ≤ q \mathbb{P}\left[\lVert S_tV_t\rVert_F^2>(1+\varepsilon)\lVert V_t\rVert_F^2\mid\mathcal{F}_t\right]\le2e^{-c_1k\varepsilon^2}\le q P [ ∥ S t V t ∥ F 2 > ( 1 + ε ) ∥ V t ∥ F 2 ∣ F t ] ≤ 2 e − c 1 k ε 2 ≤ q when k ≥ C ε − 2 log ( 8 T / δ ) k\ge C\varepsilon^{-2}\log(8T/\delta) k ≥ C ε − 2 log ( 8 T / δ ) for a sufficiently large universal constant C C C . The same lemma for a single column gives the fixed-vector JL bound with failure probability at most q q q . Applying Lemma 7 then gives
∣ ⟨ S t g 0 t , S t g t ⟩ − ⟨ g 0 t , g t ⟩ ∣ ≤ ε ∥ g 0 t ∥ ∥ g t ∥ \left|\langle S_tg_0^t,S_tg^t\rangle-\langle g_0^t,g^t\rangle\right|\le\varepsilon\lVert g_0^t\rVert\lVert g^t\rVert ⟨ S t g 0 t , S t g t ⟩ − ⟨ g 0 t , g t ⟩ ≤ ε ∥ g 0 t ∥ ∥ g t ∥ with conditional failure probability at most 2 q 2q 2 q . Finally, Lemma 4 gives ∥ S t ∥ 2 ≤ ρ \lVert S_t\rVert^2\le\rho ∥ S t ∥ 2 ≤ ρ with conditional failure probability at most q q q . Thus, with conditional probability at least 1 − 4 q 1-4q 1 − 4 q , all three events hold.
On their intersection, Lemma 23 implies
⟨ g 0 t , 1 G ∑ i ∈ G u i t ⟩ = ⟨ S t g 0 t , S t g t ⟩ ≥ ⟨ g 0 t , g t ⟩ − ε ∥ g 0 t ∥ ∥ g t ∥ ≥ d 2 ∥ g t ∥ 2 − η 0 2 . \left\langle g_0^t,\frac{1}{G}\sum_{i\in\mathcal{G}}u_i^t\right\rangle=\left\langle S_tg_0^t,S_tg^t\right\rangle\ge\left\langle g_0^t,g^t\right\rangle-\varepsilon\lVert g_0^t\rVert\lVert g^t\rVert\ge\frac{d}{2}\lVert g^t\rVert^2-\frac{\eta_0}{2}. ⟨ g 0 t , G 1 i ∈ G ∑ u i t ⟩ = ⟨ S t g 0 t , S t g t ⟩ ≥ ⟨ g 0 t , g t ⟩ − ε ∥ g 0 t ∥ ∥ g t ∥ ≥ 2 d ∥ g t ∥ 2 − 2 η 0 .
Moreover, using the operator norm and the Frobenius norm in this order,
∑ i ∈ G ∥ u i t ∥ 2 = ∥ S t ⊤ S t V t ∥ F 2 ≤ ∥ S t ⊤ ∥ 2 ∥ S t V t ∥ F 2 ≤ ρ ( 1 + ε ) ∥ V t ∥ F 2 ≤ ρ ( 1 + ε ) G ( ( 1 + δ 2 ) ∥ g t ∥ 2 + δ 1 ) . \begin{aligned}
\sum_{i\in\mathcal{G}}\lVert u_i^t\rVert^2=\lVert S_t^\top S_tV_t\rVert_F^2\le\lVert S_t^\top\rVert^2\lVert S_tV_t\rVert_F^2\le\rho(1+\varepsilon)\lVert V_t\rVert_F^2 \\
&\le\rho(1+\varepsilon)G\left((1+\delta_2)\lVert g^t\rVert^2+\delta_1\right).
\end{aligned} i ∈ G ∑ ∥ u i t ∥ 2 = ∥ S t ⊤ S t V t ∥ F 2 ≤ ∥ S t ⊤ ∥ 2 ∥ S t V t ∥ F 2 ≤ ρ ( 1 + ε ) ∥ V t ∥ F 2 ≤ ρ ( 1 + ε ) G ( ( 1 + δ 2 ) ∥ g t ∥ 2 + δ 1 ) .
Substituting these two estimates into Lemma 24 yields
f 0 ( x t + 1 ) ≤ f 0 ( x t ) − γ β G 2 M ( d ∥ g t ∥ 2 − η 0 ) + L γ 2 β ρ ( 1 + ε ) G 2 M ( ( 1 + δ 2 ) ∥ g t ∥ 2 + δ 1 ) = f 0 ( x t ) − γ β G 2 M ( D γ ∥ g t ∥ 2 − η 0 − c γ δ 1 ) . \begin{aligned}
f_0(x^{t+1})\le f_0(x^t)-\frac{\gamma\beta G}{2M}\left(d\lVert g^t\rVert^2-\eta_0\right)+\frac{L\gamma^2\beta\rho(1+\varepsilon)G}{2M}\left((1+\delta_2)\lVert g^t\rVert^2+\delta_1\right) \\
&=f_0(x^t)-\frac{\gamma\beta G}{2M}\left(D_\gamma\lVert g^t\rVert^2-\eta_0-c_\gamma\delta_1\right).
\end{aligned} f 0 ( x t + 1 ) ≤ f 0 ( x t ) − 2 M γ β G ( d ∥ g t ∥ 2 − η 0 ) + 2 M L γ 2 β ρ ( 1 + ε ) G ( ( 1 + δ 2 ) ∥ g t ∥ 2 + δ 1 ) = f 0 ( x t ) − 2 M γ β G ( D γ ∥ g t ∥ 2 − η 0 − c γ δ 1 ) .
Let E t E_t E t be the intersection of the three sketch events at iteration t t t . Although the iterates are adaptive, their conditional failure probabilities are bounded for every history. Therefore,
P [ ⋃ t = 0 T − 1 E t c ] ≤ ∑ t = 0 T − 1 E [ P ( E t c ∣ F t ) ] ≤ 4 T q = δ . \mathbb{P}\left[\bigcup_{t=0}^{T-1}E_t^c\right]\le\sum_{t=0}^{T-1}\mathbb{E}\left[\mathbb{P}(E_t^c\mid\mathcal{F}_t)\right]\le4Tq=\delta. P [ t = 0 ⋃ T − 1 E t c ] ≤ t = 0 ∑ T − 1 E [ P ( E t c ∣ F t ) ] ≤ 4 T q = δ .
On ⋂ t = 0 T − 1 E t \bigcap_{t=0}^{T-1}E_t ⋂ t = 0 T − 1 E t , summing the descent inequality and using f 0 ( x T ) ≥ f 0 inf f_0(x^T)\ge f_0^{\inf} f 0 ( x T ) ≥ f 0 i n f gives
γ β G D γ 2 M ∑ t = 0 T − 1 ∥ g t ∥ 2 ≤ Δ 0 + γ β G T 2 M ( η 0 + c γ δ 1 ) . \frac{\gamma\beta GD_\gamma}{2M}\sum_{t=0}^{T-1}\lVert g^t\rVert^2\le\Delta_0+\frac{\gamma\beta GT}{2M}\left(\eta_0+c_\gamma\delta_1\right). 2 M γ β G D γ t = 0 ∑ T − 1 ∥ g t ∥ 2 ≤ Δ 0 + 2 M γ β GT ( η 0 + c γ δ 1 ) .
Dividing by γ β G D γ T / ( 2 M ) \gamma\beta GD_\gamma T/(2M) γ β G D γ T / ( 2 M ) proves equation (18) . Finally, the stepsize in Theorem 1 gives D γ ≥ d / 2 D_\gamma\ge d/2 D γ ≥ d /2 , which proves equation (11) .
The probability estimates involve only honest gradients and the trusted reference, all fixed before the fresh sketch is sampled. No geometric preservation event is imposed on Byzantine messages. The same proof applies to another sketch construction if it provides the three conditional events above with the stated failure probabilities and a suitable value of ρ \rho ρ ; the required dimension must then be established for that construction.