Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training — part 6/7

Cleaned-text code points [77484, 91611). Bibliography omitted here; source.md includes it.

Let { θ ⁡ ( t ) } t = 0 1 \{\theta(t)\}_{t=0}^{1} be the solution of Equation 45 . We know that ∇ L ( θ ( t ) ) = ( 1 − t ) ∇ L ( θ ) \nabla L(\theta(t))=(1-t)\nabla L(\theta) for all t ∈ [ 0 , 1 ] t\in[0,1] and that θ ⁡ ( 1 ) = θ ∗ \theta(1)=\theta^{*} by Lemma D.4 . For case (1), by Lemma D.2 , we know that for any t ∈ [ 0 , 1 ] t\in[0,1] , ‖ θ ⁡ ( t ) − θ ∗ ‖ 2 ≤ R / 2 \left\|\theta(t)-\theta^{*}\right\|_{2}\leq R/2 . For case (2), by Lemma D.3 , we know that for any t ∈ [ 0 , 1 ] t\in[0,1] , ‖ θ ⁡ ( t ) − θ ∗ ‖ 2 ≤ R / 2 \left\|\theta(t)-\theta^{*}\right\|_{2}\leq R/2 . Thus in both two cases, ‖ θ ⁡ ( t ) − θ ‖ 2 = ‖ θ ⁡ ( t ) − θ ⁡ ( 0 ) ‖ 2 = ≤ ‖ θ ⁡ ( t ) − θ ∗ ‖ + ‖ θ ⁡ ( 0 ) − θ ∗ ‖ ≤ R \left\|\theta(t)-\theta\right\|_{2}=\left\|\theta(t)-\theta(0)\right\|_{2}=\leq\left\|\theta(t)-\theta^{*}\right\|+\left\|\theta(0)-\theta^{*}\right\|\leq R . By Assumption 4.2 , it holds that 2 ​ ( ∇ 2 L ​ ( θ ) ) − 1 ⪰ ( ∇ 2 L ​ ( θ ⁡ ( t ) ) ) − 1 ⪰ 1 2 ​ ( ∇ 2 L ​ ( θ ) ) − 1 . \displaystyle 2(\nabla^{2}L(\theta))^{-1}\succeq(\nabla^{2}L(\theta(t)))^{-1}\succeq\frac{1}{2}(\nabla^{2}L(\theta))^{-1}. (24) for all t ∈ [ 0 , 1 ] t\in[0,1] . Therefore, we have that L ⁡ ( θ ) − min ⁡ L = L ⁡ ( θ ⁡ ( 0 ) ) − L ⁡ ( θ ⁡ ( 1 ) ) = \displaystyle L(\theta)-\min L=L(\theta(0))-L(\theta(1))= ∫ t = 0 1 ( ∇ L ( θ ( t ) ) ) ⊤ ( ∇ 2 L ( θ ( t ) ) ) − 1 ∇ L ( θ ) \displaystyle\int_{t=0}^{1}(\nabla L(\theta(t)))^{\top}(\nabla^{2}L(\theta(t)))^{-1}\nabla L(\theta) = \displaystyle= ∫ t = 0 1 ( 1 − t ) ( ∇ L ( θ ) ) ⊤ ( ∇ 2 L ( θ ( t ) ) ) − 1 ∇ L ( θ ) . \displaystyle\int_{t=0}^{1}(1-t)(\nabla L(\theta))^{\top}(\nabla^{2}L(\theta(t)))^{-1}\nabla L(\theta). (25) The proof is completed by plugging Equation 24 into 25 and noting that ∫ t = 0 1 ( 1 − t ) = 1 / 2 \int_{t=0}^{1}(1-t)=1/2 . ∎

###### Lemma D.6 .

For any θ ∈ ℝ d \theta\in\mathbb{R}^{d} satisfying (1) L ⁡ ( θ ) − min ⁡ L ≤ μ ​ R 2 4 L(\theta)-\min L\leq\frac{\mu R^{2}}{4} or (2) ‖ ∇ L ​ ( θ ) ‖ 2 ≤ R ​ μ 2 \left\|\nabla L(\theta)\right\|_{2}\leq\frac{R\mu}{2} , it holds that L ⁡ ( θ ) − min ⁡ L ≤ μ − 1 ​ ‖ ∇ L ​ ( θ ) ‖ 2 2 \displaystyle L(\theta)-\min L\leq\mu^{-1}\left\|\nabla L(\theta)\right\|_{2}^{2} (26)

###### Proof of Lemma D.6 .

The proof of Lemma D.6 is almost the same as that of Lemma D.5 and thus omitted. ∎

###### Lemma D.7 .

For any θ ∈ ℝ d \theta\in\mathbb{R}^{d} satisfying L ⁡ ( θ ) − min ⁡ L ≤ μ ​ R 2 16 L(\theta)-\min L\leq\frac{\mu R^{2}}{16} , it holds that ‖ ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ‖ 2 ≤ 8 ​ ( L ​ ( θ ) − min ⁡ L ) μ . \displaystyle\left\|(\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\right\|_{2}\leq\sqrt{\frac{8(L(\theta)-\min L)}{\mu}}. (27)

###### Proof of Lemma D.7 .

By Lemma D.2 , we have that ‖ θ − θ ∗ ‖ 2 ≤ R \left\|\theta-\theta^{*}\right\|_{2}\leq R . By Assumption 4.2 , we have ∇ 2 L ​ ( θ ) ⪰ 1 2 ​ ∇ 2 L ​ ( θ ∗ ) ⪰ μ 2 ​ I d \nabla^{2}L(\theta)\succeq\frac{1}{2}\nabla^{2}L(\theta^{*})\succeq\frac{\mu}{2}I_{d} . By Lemma D.5 , we have that 4 ​ ( L ​ ( θ ) − min ⁡ L ) ≥ \displaystyle 4(L(\theta)-\min L)\geq ∇ L ( θ ) ⊤ ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) \displaystyle\nabla L(\theta)^{\top}(\nabla^{2}L(\theta))^{-1}\nabla L(\theta) (28) ≥ \displaystyle\geq ∇ L ( θ ) ⊤ ( ∇ 2 L ( θ ) ) − 1 ∇ 2 L ( θ ) ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) \displaystyle\nabla L(\theta)^{\top}(\nabla^{2}L(\theta))^{-1}\nabla^{2}L(\theta)(\nabla^{2}L(\theta))^{-1}\nabla L(\theta) (29) ≥ \displaystyle\geq μ 2 ‖ ∇ L ( θ ) ⊤ ( ∇ 2 L ( θ ) ) − 1 ‖ 2 2 . \displaystyle\frac{\mu}{2}\left\|\nabla L(\theta)^{\top}(\nabla^{2}L(\theta))^{-1}\right\|_{2}^{2}. (30) This completes the proof. ∎

###### Lemma D.8 .

For any θ ∈ ℝ d \theta\in\mathbb{R}^{d} satisfying that ‖ ( ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ‖ 2 ≤ R 2 \left\|((\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\right\|_{2}\leq\frac{R}{2} , it holds that L ( θ ) − min L ≤ ∇ L ( θ ) ⊤ ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ≤ 4 ( L ( θ ) − min L ) . \displaystyle L(\theta)-\min L\leq\nabla L(\theta)^{\top}(\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\leq 4(L(\theta)-\min L). (31)

###### Proof of Lemma D.8 .

Let { θ ⁡ ( t ) } t = 0 1 \{\theta(t)\}_{t=0}^{1} be the solution of Equation 45 and we claim that for all t ∈ [ 0 , 1 ] t\in[0,1] , ‖ θ ⁡ ( t ) − θ ‖ 2 ≤ R \left\|\theta(t)-\theta\right\|_{2}\leq R . Otherwise, let T T be the smallest positive number such that ‖ θ ⁡ ( T ) − θ ‖ 2 = R \left\|\theta(T)-\theta\right\|_{2}=R . Such T T exists because ‖ θ ⁡ ( t ) − θ ‖ 2 \left\|\theta(t)-\theta\right\|_{2} is continuous in t t and ‖ θ ⁡ ( 0 ) − θ ‖ 2 = 0 \left\|\theta(0)-\theta\right\|_{2}=0 . We have that R = \displaystyle R= ‖ θ ⁡ ( T ) − θ ⁡ ( 0 ) ‖ 2 ≤ ∫ t = 0 T ‖ d ​ θ ​ ( t ) d ​ t ‖ 2 ​ 𝑑 t \displaystyle\left\|\theta(T)-\theta(0)\right\|_{2}\leq\int_{t=0}^{T}\left\|\frac{\mathrm{d}\theta(t)}{\mathrm{d}t}\right\|_{2}\mathrm{d}t (32) = \displaystyle= ∫ t = 0 T ‖ ( ( ∇ 2 L ( θ ( t ) ) ) − 1 ∇ L ( θ ) ‖ 2 d t \displaystyle\int_{t=0}^{T}\left\|((\nabla^{2}L(\theta(t)))^{-1}\nabla L(\theta)\right\|_{2}\mathrm{d}t (33) ≤ \displaystyle\leq ∫ t = 0 T ‖ ( ∇ 2 L ( θ ( t ) ) ) − 1 ∇ 2 L ( θ ) ‖ 2 ‖ ( ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ‖ 2 d t \displaystyle\int_{t=0}^{T}\left\|(\nabla^{2}L(\theta(t)))^{-1}\nabla^{2}L(\theta)\right\|_{2}\left\|((\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\right\|_{2}\mathrm{d}t (34) ≤ \displaystyle\leq 2 ∫ t = 0 T ‖ ( ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ‖ 2 d t \displaystyle 2\int_{t=0}^{T}\left\|((\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\right\|_{2}\mathrm{d}t (35) ≤ \displaystyle\leq 2 ​ T ​ R 2 = R ​ T , \displaystyle 2T\frac{R}{2}=RT, (36) which implies T = 1 T=1 . Here in Equation 35 , we use Assumption 4.2 . Thus we conclude that for all t ∈ [ 0 , 1 ] t\in[0,1] , ‖ θ ⁡ ( t ) − θ ‖ 2 ≤ R \left\|\theta(t)-\theta\right\|_{2}\leq R . By Assumption 4.2 , it holds that 2 ​ ( ∇ 2 L ​ ( θ ) ) − 1 ⪰ ( ∇ 2 L ​ ( θ ⁡ ( t ) ) ) − 1 ⪰ 1 2 ​ ( ∇ 2 L ​ ( θ ) ) − 1 . \displaystyle 2(\nabla^{2}L(\theta))^{-1}\succeq(\nabla^{2}L(\theta(t)))^{-1}\succeq\frac{1}{2}(\nabla^{2}L(\theta))^{-1}. (37)

Therefore, we have that L ⁡ ( θ ) − min ⁡ L = L ⁡ ( θ ⁡ ( 0 ) ) − L ⁡ ( θ ⁡ ( 1 ) ) = \displaystyle L(\theta)-\min L=L(\theta(0))-L(\theta(1))= ∫ t = 0 1 ( ∇ L ( θ ( t ) ) ) ⊤ ( ∇ 2 L ( θ ( t ) ) ) − 1 ∇ L ( θ ) \displaystyle\int_{t=0}^{1}(\nabla L(\theta(t)))^{\top}(\nabla^{2}L(\theta(t)))^{-1}\nabla L(\theta) = \displaystyle= ∫ t = 0 1 ( 1 − t ) ( ∇ L ( θ ) ) ⊤ ( ∇ 2 L ( θ ( t ) ) ) − 1 ∇ L ( θ ) . \displaystyle\int_{t=0}^{1}(1-t)(\nabla L(\theta))^{\top}(\nabla^{2}L(\theta(t)))^{-1}\nabla L(\theta). (38) The proof is completed by plugging Equation 37 into 38 and noting that ∫ t = 0 1 ( 1 − t ) = 1 / 2 \int_{t=0}^{1}(1-t)=1/2 . ∎

###### Lemma D.9 .

If ρ ≤ R 2 ​ d \rho\leq\frac{R}{2\sqrt{d}} , then for any Δ ≤ R ​ ρ ​ μ 10 \Delta\leq\frac{R\rho\mu}{10} and any θ ∈ ℝ d \theta\in\mathbb{R}^{d} satisfying ∑ i = 1 d min { ρ | v i ⊤ ∇ L ( θ ) | , σ i − 1 | v i ⊤ ∇ L ( θ ) | 2 } ≤ Δ , \displaystyle\sum_{i=1}^{d}\min\{\rho\left|v_{i}^{\top}\nabla L(\theta)\right|,\sigma_{i}^{-1}\left|v_{i}^{\top}\nabla L(\theta)\right|^{2}\}\leq\Delta, (39) where ∇ 2 L ​ ( θ ) = V ⊤ ​ Σ ​ V \nabla^{2}L(\theta)=V^{\top}\Sigma V is the eigendecomposition of ∇ 2 L ​ ( θ ) \nabla^{2}L(\theta) , v i v_{i} is the i i th row of V V and Σ = diag ⁡ ( σ 1 , … , σ d ) \Sigma={\rm diag}(\sigma_{1},\ldots,\sigma_{d}) , it holds that L ⁡ ( θ ) − min ⁡ L ≤ Δ + 25 ​ Δ 2 ρ 2 ​ μ \displaystyle L(\theta)-\min L\leq\Delta+\frac{25\Delta^{2}}{\rho^{2}\mu} (40)

In particular, if we set Δ ≜ μ ​ ρ 2 20 \Delta\triangleq\frac{\mu\rho^{2}}{20} , we have L ⁡ ( θ ) − min ⁡ L ≤ μ ​ ρ 2 8 L(\theta)-\min L\leq\frac{\mu\rho^{2}}{8} .

###### Proof of Lemma D.9 .

Let I θ ≜ { i ∈ [ d ] ∣ | v i ⊤ ∇ L ( θ ) | σ i − 1 ≤ ρ } I_{\theta}\triangleq\{i\in[d]\mid\left|v_{i}^{\top}\nabla L(\theta)\right|\sigma_{i}^{-1}\leq\rho\} be the set of indices where clipping does not happen. Then we have that ∑ i ∈ I θ σ i − 1 | v i ⊤ ∇ L ( θ ) | 2 ≤ Δ \displaystyle\sum_{i\in I_{\theta}}\sigma_{i}^{-1}\left|v_{i}^{\top}\nabla L(\theta)\right|^{2}\leq\Delta (41) ∑ i ∉ I θ ρ | v i ⊤ ∇ L ( θ ) | ≤ Δ \displaystyle\sum_{i\notin I_{\theta}}\rho\left|v_{i}^{\top}\nabla L(\theta)\right|\leq\Delta (42) Now we consider a new strictly convex loss function in R | I θ | R^{|I_{\theta}|} , which is L L restricted on the space of { θ + ∑ i ∈ I θ w [ i ] ​ v i ∣ w ∈ ℝ | I θ | } \{\theta+\sum_{i\in I_{\theta}}w_{[i]}v_{i}\mid w\in\mathbb{R}^{|I_{\theta}|}\} , that is, L θ ​ ( w ) = L ⁡ ( θ + ∑ i ∈ I θ w [ i ] ​ v i ) L_{\theta}(w)=L(\theta+\sum_{i\in I_{\theta}}w_{[i]}v_{i}) . This new loss function L θ {L_{\theta}} clearly satisfy Assumption 4.2 since it is a restriction of L L into some subspace of ℝ d \mathbb{R}^{d} . By Lemma D.1 , we know that inf w L θ ​ ( w ) \inf_{w}L_{\theta}(w) can be attained and we denote it by w ∗ w^{*} . By Assumption 4.1 , we know that L θ L_{\theta} is strictly convex and thus ∇ 2 L θ ​ ( w ) ≻ 0 \nabla^{2}L_{\theta}(w)\succ 0 , which means Assumption 4.1 also holds for L θ L_{\theta} .

Next we will apply Lemma D.8 on L θ L_{\theta} at w = 0 w=0 . We use V I θ ∈ ℝ | I | × d V_{I_{\theta}}\in\mathbb{R}^{|I|\times d} to denote the submatrix of V V containing rows in I I for any I ⊂ [ d ] I\subset[d] . One can verify by chain rule that ∇ L θ ( w ) = V I θ ∇ L ( θ + V I θ ⊤ w ) \nabla L_{\theta}(w)=V_{I_{\theta}}\nabla L(\theta+V_{I_{\theta}}^{\top}w) and that ∇ 2 L θ ​ ( w ) = V I θ ​ ∇ 2 L ​ ( θ + V I θ ⊤ ​ w ) ​ V I θ ⊤ \nabla^{2}L_{\theta}(w)=V_{I_{\theta}}\nabla^{2}L(\theta+V_{I_{\theta}}^{\top}w)V_{I_{\theta}}^{\top} . Thus we have that ( ∇ 2 L θ ( 0 ) ) − 1 ∇ L θ ( 0 ) = V I θ ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) . \displaystyle(\nabla^{2}L_{\theta}(0))^{-1}\nabla L_{\theta}(0)=V_{I_{\theta}}(\nabla^{2}L(\theta))^{-1}\nabla L(\theta). (43) By the definition of I θ I_{\theta} , we know that ‖ V I θ ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ‖ ∞ ≤ ρ \left\|V_{I_{\theta}}(\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\right\|\infty\leq\rho . Thus ‖ ( ∇ 2 L θ ( 0 ) ) − 1 ∇ L θ ( 0 ) ‖ 2 ≤ d ‖ V I θ ( ∇ 2 L ( θ ) ) − 1 ∇ L ( θ ) ‖ ∞ = d ⋅ ρ ≤ R 2 \left\|(\nabla^{2}L_{\theta}(0))^{-1}\nabla L_{\theta}(0)\right\|_{2}\leq\sqrt{d}\left\|V_{I_{\theta}}(\nabla^{2}L(\theta))^{-1}\nabla L(\theta)\right\|_{\infty}=\sqrt{d}\cdot\rho\leq\frac{R}{2} . Thus we can apply Lemma D.8 on L θ L_{\theta} at w = 0 w=0 and conclude that L θ ( 0 ) − L θ ( w ∗ ) ≤ ∇ L θ ( 0 ) ⊤ ( ∇ 2 L θ ( 0 ) ) − 1 ∇ L θ ( 0 ) = ∑ i ∈ I θ σ i − 1 | v i ⊤ ∇ L ( θ ) | 2 ≤ Δ \displaystyle L_{\theta}(0)-L_{\theta}(w^{*})\leq\nabla L_{\theta}(0)^{\top}(\nabla^{2}L_{\theta}(0))^{-1}\nabla L_{\theta}(0)=\sum_{i\in I_{\theta}}\sigma_{i}^{-1}\left|v_{i}^{\top}\nabla L(\theta)\right|^{2}\leq\Delta (44) Thus L ⁡ ( θ ) − L ⁡ ( θ + V I θ ⊤ ​ w ∗ ) = L θ ​ ( 0 ) − L θ ​ ( w ∗ ) ≤ Δ L(\theta)-L(\theta+V_{I_{\theta}}^{\top}w^{*})=L_{\theta}(0)-L_{\theta}(w^{*})\leq\Delta .

It remains to show that L ⁡ ( θ + V I θ ⊤ ​ w ∗ ) − L ⁡ ( θ ∗ ) ≤ 25 ​ Δ 2 ρ 2 ​ μ L(\theta+V_{I_{\theta}}^{\top}w^{*})-L(\theta^{*})\leq\frac{25\Delta^{2}}{\rho^{2}\mu} . To do so, our strategy is to first show that ‖ ∇ L ​ ( θ + V I θ ⊤ ​ w ∗ ) ‖ 2 \left\|\nabla L(\theta+V_{I_{\theta}}^{\top}w^{*})\right\|_{2} is small and then to use Lemma D.6 . We will use I θ c I_{\theta}^{c} to denote the complement of I θ I_{\theta} in [ d ] [d] and V I θ c ∈ ℝ ( d − | I θ | ) × d V_{I_{\theta}^{c}}\in\mathbb{R}^{(d-|I_{\theta}|)\times d} to denote the submatrix of V V which contains all the rows that do not belong to I θ I_{\theta} . Note that w ∗ w^{*} is the minimizer of L θ L_{\theta} , we know that V I θ ∇ L ( θ + V I θ ⊤ w ∗ ) = 0 V_{I_{\theta}}\nabla L(\theta+V_{I_{\theta}}^{\top}w^{*})=0 and that ‖ ∇ L ( θ + V I θ ⊤ w ∗ ) ‖ 2 = ‖ V I θ c ∇ L ( θ + V I θ ⊤ w ∗ ) ‖ 2 \left\|\nabla L(\theta+V_{I_{\theta}}^{\top}w^{*})\right\|_{2}=\left\|V_{I_{\theta}^{c}}\nabla L(\theta+V_{I_{\theta}}^{\top}w^{*})\right\|_{2} .

Now we consider the following ODE d ​ w ​ ( t ) d ​ t = − ( ∇ 2 L θ ( w ( t ) ) ) − 1 ∇ L θ ( 0 ) , w ( 0 ) = 0 . \displaystyle\frac{\mathrm{d}w(t)}{\mathrm{d}t}=-(\nabla^{2}L_{\theta}(w(t)))^{-1}\nabla L_{\theta}(0),\quad w(0)=0. (45) By Lemma D.4 , we know this ODE has solution w ⁡ ( t ) w(t) over interval [ 0 , 1 ] [0,1] with w ⁡ ( 1 ) = w ∗ w(1)=w^{*} . With the same argument in the proof of Lemma D.8 , we know that ‖ w ⁡ ( t ) ‖ 2 ≤ R \left\|w(t)\right\|_{2}\leq R for all t ∈ [ 0 , 1 ] t\in[0,1] . Thus we have for any t ∈ [ 0 , 1 ] t\in[0,1] , ‖ V I θ c ​ d ∇ L ( θ + V I θ w ( t ) ) d ​ t ‖ 2 \displaystyle\left\|V_{I_{\theta}^{c}}\frac{\mathrm{d}\nabla L(\theta+V_{I_{\theta}}w(t))}{\mathrm{d}t}\right\|_{2} (46) = \displaystyle\ = ‖ V I θ c ∇ 2 L ( θ + V I θ w ( t ) ) V I θ ( ∇ 2 L θ ( w ( t ) ) ) − 1 ∇ L θ ( 0 ) ‖ 2 \displaystyle\left\|V_{I_{\theta}^{c}}\nabla^{2}L(\theta+V_{I_{\theta}}w(t))V_{I_{\theta}}(\nabla^{2}L_{\theta}(w(t)))^{-1}\nabla L_{\theta}(0)\right\|_{2} (47) = \displaystyle= ‖ V I θ c ∇ 2 L ( θ + V I θ w ( t ) ) V I θ V I θ ⊤ ( ∇ 2 L ( θ + V I θ w ( t ) ) ) − 1 ∇ L ( θ ) ‖ 2 \displaystyle\left\|V_{I_{\theta}^{c}}\nabla^{2}L(\theta+V_{I_{\theta}}w(t))V_{I_{\theta}}V_{I_{\theta}}^{\top}(\nabla^{2}L(\theta+V_{I_{\theta}}w(t)))^{-1}\nabla L(\theta)\right\|_{2} (48) ≤ \displaystyle\leq ‖ V I θ c ​ ∇ 2 L ​ ( θ + V I θ ​ w ​ ( t ) ) ‖ F \displaystyle\left\|V_{I_{\theta}^{c}}\sqrt{\nabla^{2}L(\theta+V_{I_{\theta}}w(t))}\right\|_{F} (49) ⋅ \displaystyle\cdot ‖ ∇ 2 L ​ ( θ + V I θ ​ w ​ ( t ) ) V I θ V I θ ⊤ ( ∇ 2 L ( θ + V I θ w ( t ) ) ) − 1 ∇ L ( θ ) ‖ 2 \displaystyle\left\|\sqrt{\nabla^{2}L(\theta+V_{I_{\theta}}w(t))}V_{I_{\theta}}V_{I_{\theta}}^{\top}(\nabla^{2}L(\theta+V_{I_{\theta}}w(t)))^{-1}\nabla L(\theta)\right\|_{2} (50)

For the first term ( Equation 49 ), by Assumption 4.2 , we have that ‖ V I θ c ​ ∇ 2 L ​ ( θ + V I θ ​ w ​ ( t ) ) ‖ F 2 ≤ 2 ​ V I θ c ​ ∇ 2 L ​ ( θ ) ​ V I θ c = 2 ​ ∑ i ∉ I θ σ i ≤ 2 ​ ∑ i ∉ I θ v i ⊤ ∇ L ( θ ) ρ ≤ 2 ​ Δ ρ 2 . \displaystyle\left\|V_{I_{\theta}^{c}}\sqrt{\nabla^{2}L(\theta+V_{I_{\theta}}w(t))}\right\|_{F}^{2}\leq 2V_{I_{\theta}^{c}}\nabla^{2}L(\theta)V_{I_{\theta}^{c}}=2\sum_{i\notin I_{\theta}}\sigma_{i}\leq 2\sum_{i\notin I_{\theta}}\frac{v_{i}^{\top}\nabla L(\theta)}{\rho}\leq\frac{2\Delta}{\rho^{2}}. (51)