&\leq \underbrace{\|\Delta_{t-1}-\eta [\nabla L_{t-1}(\theta_{t-1})]_{\mathcal{F}^{t-1}}\|_2}_{A} +\eta \underbrace{\|\tilde{\nabla}_{t, \mathcal{F}^{t-1}}-[\nabla L_{t-1}(\theta_{t-1})]_{\mathcal{F}^{t-1}}\|_2}_{B}.
\end{align*}

We first bound the term $B$. Specifically, we have

\begin{align*}
\|\tilde{\nabla}_{t, \mathcal{F}^{t-1}}-[\nabla L_{t-1}(\theta_{t-1})]_{\mathcal{F}^{t-1}}\|_2&=\|[\tilde{\nabla}_{t}-\nabla L_{t-1}(\theta_{t-1})]_{\mathcal{F}^{t-1}}\|_2\\
&\leq \sqrt{|\mathcal{F}^{t-1}|} \|\tilde{\nabla}_{t}-\nabla L_{t-1}(\theta_{t-1})\|_\infty \\
&\leq \sqrt{|\mathcal{F}^{t-1}|} (\underbrace{\|\tilde{\nabla}L_{t-1}(\theta_{t-1})-\nabla L_{t-1}(\theta_{t-1})\|_\infty}_{B_1}+\underbrace{\|\phi_t\|_\infty}_{B_2})
\end{align*}

For term $B_2$, by Lemma <ref> we have with probability at least $1-\delta'$

\begin{equation}
B_2\leq O\left(\frac{(\tau_1^2\sqrt{dk'}+\tau_1\tau_2\sqrt{d})\sqrt{\log \frac{d}{\delta'}} }{\sqrt{m}\epsilon}\right).
\end{equation}

For $B_1$, we have

\begin{align*}
B_1\leq \underbrace{\sup_{\|\theta\|_2\leq 1}\| \tilde{\nabla}L_{t-1}(\theta)- \nabla L_\mathcal{P}(\theta)\|_\infty}_{B_{1, 1}} + \underbrace{\sup_{\|\theta\|_2\leq 1} \|\nabla L_{t-1}(\theta)-\nabla L_\mathcal{P}(\theta)\|_\infty}_{B_{1, 2}}.
\end{align*}

Next we bound the term $B_{1, 1}$, we have

\begin{align*}
&\sup_{\|\theta\|_1\leq 1}\| \tilde{\nabla}L_{t-1}(\theta)- \nabla L_\mathcal{P}(\theta)\|_\infty\leq   \sup_{\|\theta\|_1\leq 1}\|[\frac{1}{m}\sum_{i=1}^n \tilde{x}_i\tilde{x}_i^T-\mathbb{E}[xx^T]]\theta\|_\infty+ \sup_{\|\theta\|_1\leq 1}\|\frac{1}{m}\sum_{i=1}^m \tilde{x}_i\tilde{y}_i-\mathbb{E}[xy]\|_\infty \\
&\leq \|[\frac{1}{m}\sum_{i=1}^n \tilde{x}_i\tilde{x}_i^T-\mathbb{E}[xx^T]]\|_{\infty, \infty}+\|\frac{1}{m}\sum_{i=1}^m \tilde{x}_i\tilde{y}_i-\mathbb{E}[xy]\|_\infty.
\end{align*}

We consider the first term $\|[\frac{1}{m}\sum_{i=1}^n \tilde{x}_i\tilde{x}_i^T-\mathbb{E}[xx^T]]\|_{\infty, \infty}$, for simplicity for each $j, k\in [d]$ denote $\hat{\sigma}_{jk}=(\frac{1}{n}\sum_{i=1}^n \tilde{x}_i\tilde{x}_i^T)_{jk}=\frac{1}{n}\sum_{i=1}^n\tilde{x}_{i,j}\tilde{x}_{i, k}$, $\tilde{\sigma}_{jk}= (\mathbb{E}[\tilde{x}\tilde{x}^T])_{jk}= \mathbb{E}[\tilde{x}_j\tilde{x}_k]$ and $\sigma_{jk}=(\mathbb{E}[{x}{x}^T])_{jk}= \mathbb{E}[{x}_j{x}_k]$. We have

\begin{equation*}
|\hat{\sigma}_{jk}- \sigma_{jk}| \leq |\hat{\sigma}_{jk}-\tilde{\sigma}_{jk}|+|\tilde{\sigma}_{jk}-\sigma_{jk}|.
\end{equation*}

We know that $|\tilde{x}_j\tilde{x}_k|\leq \tau_1^2$ and $\text{Var}(\tilde{x}_j\tilde{x}_k)\leq  \text{Var}(x_jx_k)\leq \mathbb{E}(x_jx_k)^2\leq  O(\sigma^4)$. By Bernstein's inequality we have

\begin{equation}
\mathbb{P}(\max_{j,k} |\hat{\sigma}_{jk}-\tilde{\sigma}_{jk}|\leq C\sqrt{ \frac{\sigma^4 t}{m}}+\frac{\tau_1^2 t}{m})\geq 1-d^2\exp(-t)
\end{equation}

Moreover, we have

\begin{align*}
&|\tilde{\sigma}_{jk}-\sigma_{jk}|=|\mathbb{E}[|\tilde{x}_j(\tilde{x}_k-x_k)\mathbb{I}({|x_k|\geq \tau_1})]+|\mathbb{E}[|x_k(\tilde{x}_j-x_j)\mathbb{I}({|x_j|\geq \tau_1})]\\
&\leq \sqrt{\mathbb{E}(\tilde{x}_j (\tilde{x}_k-x_k))^2 \mathbb{P}( |x_k|\geq \tau_1) } + \sqrt{\mathbb{E}  ((\tilde{x}_j-x_j) x_k)^2 \mathbb{P} (|x_j|\geq \tau_1)}\\
&\leq O(\frac{\sigma^2}{n}),
\end{align*}

where the last inequality is due to the assumption on sub-Gaussian where $\mathbb{P} (|x_j|\geq \tau_1)\leq 2\exp(-\frac{\tau_1^2}{2\sigma^2})=  O(\frac{1}{n})$, $\mathbb{E}(\tilde{x}_j (\tilde{x}_k-x_k))^2\leq  4\mathbb{E}(x_j x_k))^2 \leq O(\sigma^4)$ and $\mathbb{E}  ((\tilde{x}_j-x_j) x_k)^2\leq  4\mathbb{E}(x_j x_k))^2\leq O(\sigma^4) $. In total we have with probability at least $1-\delta'$

\begin{equation*}
\|[\frac{1}{m}\sum_{i=1}^n \tilde{x}_i\tilde{x}_i^T-\mathbb{E}[xx^T]]\|_{\infty, \infty} \leq O(\frac{\sigma^2 \log n \log \frac{d}{\delta'}}{\sqrt{m}}).
\end{equation*}

We can use the same technique to term $\|\frac{1}{m}\sum_{i=1}^m \tilde{x}_i\tilde{y}_i-\mathbb{E}[xy]\|_\infty$, for simplicity for each $j \in [d]$ denote $\hat{\sigma}_{j}=\frac{1}{n}\sum_{i=1}^n \tilde{y}_i\tilde{x}_j$, $\tilde{\sigma}_{j}= \mathbb{E}[\tilde{y}\tilde{x}_j]$ and $\sigma_{j}= \mathbb{E}[y{x}_j]$. We have

\begin{equation*}
|\hat{\sigma}_{j}- \sigma_{j}| \leq |\hat{\sigma}_{j}-\tilde{\sigma}_{j}|+|\tilde{\sigma}_{j}-\sigma_{j}|.
\end{equation*}

Since $|\tilde{x}_{j}\tilde{y}|\leq \tau_1\tau_2 $ and we have the following by the Holder's inequality

\begin{align*}
\text{Var}(\tilde{x}_{j}\tilde{y})\leq \text{Var}(x_jy)\leq  \mathbb{E}[x_j^2y^2] \leq (\mathbb{E}[y^{4}])^{\frac{1}{2}}(\mathbb{E}[|x_j|^{4}])^{\frac{1}{2}}\leq O(\sigma^4)
\end{align*}

Thus, by Bernstein's inequality we have  for all $j\in [d]$

\begin{equation*}
\mathbb{P}(  |\hat{\sigma}_{j}-\tilde{\sigma}_{j}|\leq O(\sqrt{\frac{\sigma^4 t}{m}}+\frac{\tau_1\tau_2t}{m}))\geq 1-d\exp(-t).
\end{equation*}

\begin{align*}
&|\tilde{\sigma}_{j}-\sigma_{j}|\leq |\mathbb{E}[\tilde{y}(\tilde{x}_j-x_j)\mathbb{I}(|x_j|) \geq \tau_1 ] |+|\mathbb{E}[x_j(\tilde{y}-y) \mathbb{I}(|y|\geq \tau_2)]|\\
&\leq \sqrt{\mathbb{E}((\tilde{y}(\tilde{x}_j-x_j))^2 \mathbb{P}( |x_j|\geq \tau_1 ) }  + \sqrt{\mathbb{E}  (x_j(\tilde{y}-y))^2 \mathbb{P} (|y|\geq \tau_2)}\\
&\leq O(\frac{\sigma^2}{n}+\frac{\sigma^2}{n})\leq O(\frac{\sigma^2}{n})
\end{align*}

we can easily see that with probability at most $1-\delta'$,

\begin{equation}\label{aeq:38}
\|\frac{1}{m}\sum_{i=1}^m \tilde{x}_i\tilde{y}_i-\mathbb{E}[xy]\|_\infty\leq O(\frac{\sigma^2 \log n \log \frac{d}{\delta'}}{\sqrt{m}}).
\end{equation}

Thus with probability at least $1-\delta'$

\begin{equation}\label{aeq:39}
B_{1, 1}\leq O(\frac{\sigma^2 \log n \log \frac{d}{\delta'}}{\sqrt{m}}).
\end{equation}

Next, we consider $B_{1, 2}$, similar to $B_{1, 1}$ we have

\begin{align*}
\sup_{\|\theta\|_2\leq 1} \|\nabla L_{t-1}(\theta)-\nabla L_\mathcal{P}(\theta)\|_\infty\leq  \|[\frac{1}{m}\sum_{i=1}^n {x}_i{x}_i^T-\mathbb{E}[xx^T]]\|_{\infty, \infty}+\|\frac{1}{m}\sum_{i=1}^m {x}_i{y}_i-\mathbb{E}[xy]\|_\infty.
\end{align*}

For term $ \|[\frac{1}{m}\sum_{i=1}^n {x}_i{x}_i^T-\mathbb{E}[xx^T]]\|_{\infty, \infty}$, by Lemma <ref> we have with probability at least $1-O(d^{-8})$ we have

\begin{equation*}
\|[\frac{1}{m}\sum_{i=1}^n {x}_i{x}_i^T-\mathbb{E}[xx^T]]\|_{\infty, \infty}\leq O(\sqrt{\frac{\log d}{m}}).
\end{equation*}

For term $\|\frac{1}{m}\sum_{i=1}^m {x}_i{y}_i-\mathbb{E}[xy]\|_\infty$, we consider each coordinate, $\frac{1}{m}\sum_{i=1}^m {x}_{i,j}{y}_i-\mathbb{E}[x_jy]$. Noted that $x_j$ is $\sigma^2$-sub-Gaussian and $y$ is $\sigma^2$-sub-Gaussian, thus, by Lemma <ref> we have $x_jy$ is sub-exponential with $\|x_jy\|_{\psi_1}\leq O(\sigma^2)$. Thus, by Bernstein's inequality, we have with probability at least $1-\zeta'$

\begin{equation*}
|\frac{1}{m}\sum_{i=1}^m {x}_{i,j}{y}_i-\mathbb{E}[x_jy]|\leq O(\frac{\sigma^2 \sqrt{\log 1/{\delta'}}}{\sqrt{m}}).
\end{equation*}

Thus, with probability at least $1-\zeta'$

\begin{equation*}
\|\frac{1}{m}\sum_{i=1}^m {x}_i{y}_i-\mathbb{E}[xy]\|_\infty\leq O(\frac{\sigma^2 \sqrt{\log d/{\delta'}}}{\sqrt{m}}).
\end{equation*}

Thus, with probability at least $1-O(d^{-8})$ we have

$$B_{1, 2}\leq O(\frac{\sqrt{\log d}}{\sqrt{m}}).$$

$$B_{1}\leq O(\frac{\sqrt{\log d}}{\sqrt{m}}).$$

Thus, we have

\begin{equation}
B \leq O\left(\sqrt{2k'+k}\frac{(\tau_1^2\sqrt{dk'}+\tau_1\tau_2\sqrt{d})\sqrt{\log \frac{d}{\delta'}} }{\sqrt{m}\epsilon}\right).
\end{equation}

In the following, we consider term $A$. Noted that we have $y_i=\langle x_i, \theta^*\rangle+\zeta_i$, thus, we have

\begin{align*}
&\underbrace{\|\Delta_{t-1}-\eta [\nabla L_{t-1}(\theta_{t-1})]_{\mathcal{F}^{t-1}}\|_2}_{A}\leq \|\Delta_{t-1}-\eta [\frac{1}{m}\sum_{i=1}^m (x_i(\langle x_i, \theta_{t-1}-\theta^*\rangle)+x_i\zeta_i)]_{\mathcal{F}^{t-1}}\|_2\\
&\leq \|\Delta_{t-1}-\eta [\frac{1}{m}\sum_{i=1}^m (x_i(\langle x_i, \theta_{t-1}-\theta^*\rangle)]_{\mathcal{F}^{t-1}}\|_2+ |\sqrt{\mathcal{F}^{t-1}}|\|\frac{1}{m}\sum_{i=1}^m x_i\zeta_i\|_\infty.
\end{align*}

We first consider the term $\|\frac{1}{m}\sum_{i=1}^m x_i\zeta_i\|_\infty$. Specifically, we consider each coordinate $j\in [d]$, $|\frac{1}{m}\sum_{i=1}^m x_{i, j}\zeta_i|$. Since $\mathbb{E}[\zeta_i]=0 $ and is independent on $x$ we have $\mathbb{E}[\zeta_i x_{j}]=0$. Moreover, we have

\begin{equation*}
\|\zeta_i\|_{\psi_2}\leq \|\langle x_i, \theta^*\rangle\|_{\psi_2}+\|y_i\|_{\psi_2}\leq O(\sigma)=O(1).
\end{equation*}

Thus, $\|\zeta x\|_{\psi_1}\leq O(\sigma^2)$ by Lemma <ref>. By Bernstein's inequality we have

\begin{equation}
|\frac{1}{m}\sum_{i=1}^m x_{i, j}\zeta_i|\leq O(\frac{\sqrt{\log 1/\delta'}}{\sqrt{m}}).
\end{equation}

Thus, with probability $1-O(d^{-c})$ we have

\begin{equation*}
\|\frac{1}{m}\sum_{i=1}^m x_i\zeta_i\|_\infty\leq O(\frac{\sqrt{\log d}}{\sqrt{m}}).
\end{equation*}

Finally, we consider the term $\|\Delta_{t-1}-\eta [\frac{1}{m}\sum_{i=1}^m (x_i(\langle x_i, \theta_{t-1}-\theta^*\rangle)]_{\mathcal{F}^{t-1}}\|_2$:

\begin{align*}
\|\Delta_{t-1}-\eta [\frac{1}{m}\sum_{i=1}^m (x_i(\langle x_i, \theta_{t-1}-\theta^*\rangle)]_{\mathcal{F}^{t-1}}\|_2 =\|[(I-D^{t-1})\Delta_{t-1}]_{\mathcal{F}^{t-1}}\|_2,
\end{align*}

where $D^{t-1}=\frac{1}{m} \sum_{i \in S_t}   {x}_i {x}_i^T \in \mathbb{R}^{d \times d}$.
Since $\operatorname{Supp}\left(D^{t-1} \Delta_{t-1}\right) \subset \mathcal{F}^{t-1}$ (by assumption), we have $\left\|\Delta_{t-1}-\eta D_{\mathcal{F}^{t-1}, \cdot}^{t-1} \Delta_{t-1}\right\|_2 \leq\left\|\left(I-\eta D_{\mathcal{F}^{t-1}, \mathcal{F}^{t-1}}\right)\right\|_2\left\|\Delta_{t-1}\right\|_2$. Next we will bound the term $\|\left(I-\eta D_{\mathcal{F}^{t-1}, \mathcal{F}^{t-1}}\right)\|_2$, where $I$ is the $\left|\mathcal{F}^{t-1}\right|$-dimensional identity matrix.

Before giving analysis, we show that each of the partitioned dataset safisfies the Restriced Isometry Property (RIP) defined as follows.

We say that a data matrix $X\in \mathbb{R}^{n\times d}$ satisfies the Restricted Isometry Property (RIP) with parameter $2 k^{\prime}+k$, if for any $v \in \mathbb{R}^p$ with $\|v\|_0 \leq 2 k'+k$, there exists a constant $\Delta$ which satisfies $(1-\Delta)\|v\|^2 \leq \frac{1}{n}\left\|Xv\right\|_2^2 \leq(1+\Delta)\|v\|_2^2$.

The following lemma states that with high probability, where $c$ is some constant each $X_{S_t}$ on our algorithm satisfies Definition <ref> and thus we can make use of this property to bound the term $D_{\mathcal{F}^{t-1}, \mathcal{F}^{t-1}}^{t-1}$.

(Theorem 10.5.11 in [50]). Consider an $n \times d$ matrix $A$ whose rows ($A_i$) are independent, isotropic, and sub-gaussian random vectors, and let $K:=\max _i\left\|A_i\right\|_{\psi_2}$. Assume that

n \geq C K^4 s \log (e d / s).

Then, with probability at least $1-2 \exp \left(-c n / K^4\right)$, the random matrix $A$ satisfies RIP with parameters $s$ and $\Delta=0.1$.

Thus, since $\{x_i\}$ are isotropic and $\|x_i\|_{\psi_2}\leq O(\sigma)$, we have  with probability at least $1-2 T\exp \left(-c m / \sigma^4\right)$, $\{X_{S_t}\}_{t=1}^T$ all satisfy RIP  when $m\geq \tilde{\Omega}(\sigma^4 (2k'+k))$. By the RIP property and $\left|\mathcal{F}^{t-1}\right| \leq 2 k^{\prime}+k$, we obtain the following using Lemma <ref> for any $\left|\mathcal{F}^{t-1}\right|$-dimensional vector $v$

0.9\|v\|_2^2 \leq v^T D_{\mathcal{F}^{t-1}, \mathcal{F}^{t-1}}^{t-1} v \leq 1.1 \|v\|_2^2 .

Thus, $\left\|\left(I-\eta D_{\mathcal{F}^{t-1}, \mathcal{F}^{t-1}}^{t-1}\right)\right\|_2 \leq \max \left\{1- \eta \cdot 0.9,  \eta\cdot 1.1-1 \right\}$.
This means that we can take $\eta=O(1)$ such that

\left\|\left(I-\eta D_{\mathcal{F}^{t-1}, \mathcal{F}^{t-1}}^{t-1}\right)\right\|_2 \leq \frac{2}{7}.

In total we have with probability at least $1-O(d^{-c})$

\begin{equation}
\left\|\tilde{\theta}_{t-\frac{1}{2}}-\theta^*\right\|_2\leq \frac{2}{7}\|\Delta_{t-1}\|_2+ O\left(\sqrt{2k'+k}\frac{(\tau_1^2\sqrt{dk'}+\tau_1\tau_2\sqrt{d})\sqrt{\log \frac{d}{\delta'}} }{\sqrt{m}\epsilon}\right).
\end{equation}

Our next task is to bound $\left\|\theta_t^{\prime}-\theta^*\right\|_2$ by $\left\|\tilde{\theta}_{t-\frac{1}{2}}-\theta^*\right\|_2$ by Lemma <ref> .
Thus, we have $\left\|\theta_t^{\prime}-\tilde{\theta}_{t-\frac{1}{2}}\right\|_2^2 \leq \frac{\left|\mathcal{F}^{t-1}\right|-k^{\prime}}{\left|\mathcal{F}^{t-1}\right|-k}\left\|\tilde{\theta}_{t-\frac{1}{2}}-\theta^*\right\|_2^2 \leq \frac{k^{\prime}+k}{2 k^{\prime}}\left\|\tilde{\theta}_{t-\frac{1}{2}}-\theta^*\right\|_2^2$.

Taking $k^{\prime}=8 k$, we get

\left\|\theta_t^{\prime}-\tilde{\theta}_{t-\frac{1}{2}}\right\|_2 \leq \frac{3}{4}\left\|\tilde{\theta}_{t-\frac{1}{2}}-\theta^*\right\|_2

\left\|\theta_t^{\prime}-\theta^*\right\|_2 \leq \frac{7}{4}\left\|\tilde{\theta}_{t-\frac{1}{2}}-\theta^*\right\|_2 \leq \frac{1}{2}\left\|\Delta_{t-1}\right\|_2+O\left(\sqrt{k}\frac{(\tau_1^2\sqrt{dk}+\tau_1\tau_2\sqrt{d})\sqrt{\log \frac{d}{\delta'}} }{\sqrt{m}\epsilon}\right).

Finally, we need to show that $\left\|\Delta_t\right\|_2=\left\|\theta_t-\theta^*\right\|_2 \leq\left\|\theta_t^{\prime}-\theta^*\right\|_2$, which is due to the Lemma <ref>.
Putting all together, we have the following with probability at least $1-O(d^{-c})$,

\left\|\Delta_t\right\|_2 \leq \frac{1}{2}\left\|\Delta_{t-1}\right\|_2+O\left(\sqrt{k}\frac{\log n\sqrt{Tdk\log{d}} }{\sqrt{n}\epsilon}\right).

Thus,  with probability at least $1-O(T d^{-c})$ we have

\left\|\Delta_T\right\|_2 \leq (\frac{1}{2})^T \left\|\theta^* \right\|_2+O\left(\frac{k\log n\sqrt{Td\log{d}} }{\sqrt{n}\epsilon}\right).

Take $T=O(\log n)$. We have the result.

§ UPPER BOUND OF LDP-IHT FOR GENERAL SUB-GAUSSIAN DISTRIBUTIONS

LDP Iterative Hard Thresholding
[1]
Input:   Private data $\left\{\left(x_i, y_i\right)\right\}_{i=1}^n \in\left(\mathbb{R}^d \times \mathbb{R}\right)^n$. Iteration number $T$, privacy parameter $\epsilon$, step size $\eta$, truncation parameters $\tau, \tau_1, \tau_2$, threshold $k'$. Initial parameter $\theta_0=0$.

For the $i$-th user with $i\in [n]$, truncate his/her data as follows:
shrink $x_i$ to $\tilde{x}_i$ with $\widetilde{{x}}_{ij}=\operatorname{sgn}\left(x_{ij}\right) \min \left\{\left|x_{ij}\right|, \tau_1\right\}$ for $j\in[d]$, and $\tilde{y}_i:=\operatorname{sgn}\left(y_i\right) \min \left\{\left|y_i\right|, \tau_2\right\}$.  Partition the users into $T$ groups. For $t=1, \cdots, T$, define the index set $S_t=\{(t-1) \left.\left\lfloor\frac{n}{T}\right\rfloor+1, \cdots, t\left\lfloor\frac{n}{T}\right\rfloor \right\}$; if $t=T$, then $S_t=$ $S_t \bigcup\left\{t\left\lfloor\frac{n}{T}\right\rfloor+1, \cdots, n\right\}$.

$t=1,2, \cdots, T$
The server sends $\theta_{t-1}$ to all the users in $S_t$. Each user $i \in S_t$ perturbs his/her own gradient: let $\nabla_i=$ $\tilde{x}_i^T\left(\left\langle\theta_{t-1}, \tilde{x}_i\right\rangle-\tilde{y}_i\right)$, compute $z_i=\mathcal{R}_\epsilon^r\left(\nabla_i\right)$, where $\mathcal{R}_\epsilon^r$ is the randomizer defined in (<ref>) with $r=\sqrt{d}\tau_1(2\sqrt{k'}\tau_1+\tau_2)$ and send back to the server.

The server computes $\tilde{\nabla}_{t-1}=\frac{1}{\left|S_t\right|} \sum_{i \in S_t} z_i$ and performs the gradient descent update $\tilde{\theta}_t=\theta_{t-1}-$ $\eta_0 \tilde{\nabla}_{t-1}$.

$\theta_t^{\prime}=\operatorname{Trunc}(\tilde{\theta}_{t-1}, k^{\prime})$.

$\theta_t=\arg _{\theta \in \mathbb{B}_2(2)}\left\|\theta-\theta_t^{\prime}\right\|_2$.
Output: $\theta_T$

Theorem <ref> establishes the upper bound specifically for isotropic sub-Gaussian distributions. However, we can also demonstrate that the aforementioned upper bound also holds for general sub-Gaussian distributions, albeit with different parameters. Notably, for general sub-Gaussian distributions, we need to slightly modify the LDP-IHT algorithm (Algorithm <ref>). Specifically, rather than projecting onto the unit $\ell_2$-norm ball, here we need to project onto the centered  $\ell_2$-norm ball with radius 2 (actually, we can project onto any centered ball with a radius larger than $1$). See Algorithm <ref> for details. Such a modification is necessary for our proof, as we can show that with high probability, $\|\theta_t'\|_2\leq 2$ for all $t\in [T]$, which implies there is no projection with high probability.  Since we use a different radius, the $\ell_2$-norm sensitivity of $\nabla_i$ also has been changed to ensure $\epsilon$-LDP. In the following, we present the theoretical result assuming that the initial parameter $\theta_0$ is sufficently close to $\theta^*$.

For any $\epsilon>0$, Algorithm <ref> is $\epsilon$-LDP.  Moreover, under Assumptions <ref> and <ref>, if the initial parameter $\theta_0$  satisfies $\|\theta_0-\theta^*\|_2\leq \frac{1}{2}\frac{\mu}{\gamma}$ and $n$ is sufficiently large such that $n\geq \tilde{\Omega}(\frac{k'^2 d}{ \epsilon^2}) $, setting $\eta_0=\frac{2}{3\gamma}$, $k'=72\frac{\gamma^2}{\mu^2}k$, with probability at least $1-\delta'$ we have

\begin{equation*}
\|\theta_T-\theta^*\|_2\leq O(\frac{\sqrt{d}k\log^2n \sqrt{\log \frac{d}{\delta}}}{\sqrt{n}\epsilon}),
\end{equation*}

where $\gamma=\lambda_{\max} (\mathbb{E}[xx^T])$, $\mu=\lambda_{\min} (\mathbb{E}[xx^T])$, big-$O$ and big-$\Omega$ notations omit the terms of $\sigma, \gamma$ and $\mu$.

The proof of privacy is almost the same as the proof of Theorem <ref>. The only difference is that here we have $\|\nabla_i\|_2\leq \sqrt{d}\tau_1(2\sqrt{k'}\tau_1+\tau_2)$.
In the following, we will show the utility. We first recall two definitions and one lemma.

A function $f$ is $L$-Lipschitz w.r.t the norm $\|\cdot\|$ if  for all $w, w'\in\mathcal{W}$, $|f(w)-f(w')|\leq L\|w-w'\|$.

A function $f$ is $\alpha$-smooth on $\mathcal{W}$ if for all $w, w'\in \mathcal{W}$, $f(w')\leq f(w)+\langle \nabla f(w), w'-w \rangle+\frac{\alpha}{2}\|w'-w\|_2^2.$

For any index set $I$, any $v\in \mathbb{R}^{|I|}$, let $\tilde{v}=\text{Trunc}(v, k)$. Then for any $v^*\in \mathbb{R}^{|I|}$ such that $\|v^*\|_0\leq k^*$ we have

\begin{equation}
\|\tilde{v}-v\|_2^2\leq \frac{|I|-k}{|I|-k^*}\|v^*-v\|_2^2.
\end{equation}

For simplicity we denote $L(\theta)=\mathbb{E}[(\langle x, \theta \rangle-y)^2]$, $\tilde{\nabla} L_{t-1}=\frac{1 }{m}\sum_{x\in \tilde{D}_t} \tilde{x}(\langle \tilde{x},  \theta_{t-1} \rangle-\tilde{y}) $,  $\nabla L_{t-1}=
\nabla L(\theta_{t-1})=\mathbb{E}[x(\langle x, \theta_{t-1}\rangle-y)$, $S^{t-1}=\text{supp}(\theta_{t-1})$, $S^{t}=\text{supp}(\theta_t)$, $S^*=\text{supp}(\theta^*)$ and $I^t=S^{t}\bigcup S^{t-1} \bigcup S^*$. We can see that $|S^{t-1}|\leq k'$, $|S^{t}|\leq k'$ and $|I^t|\leq 2k'+k$.  We let  $\gamma=\lambda_{\max} (\mathbb{E}[xx^T])$, $\mu=\lambda_{\min} (\mathbb{E}[xx^T])$ and $\eta_0=\frac{\eta}{\gamma}$ for some $\eta$. We can easily see that $L(\cdot)$ is $\mu$-strongly convex and $\gamma$-smooth.

Then from the smooth property we have

\begin{align}
& \LD-\LT \nm \notag \\
&\leq \lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge + \frac{\gamma}{2}\|\theTR_{t}-\thet_{t-1}\|_2^2 \nm \\
&=\lge \theTR_{t,I^t}-\thet_{t-1,I^t}, \nabla L_{t-1, I^t}\rge + \frac{\gamma}{2 }\| \theTR_{t,I^t}-\thet_{t-1,I^t}\|_2^2 \nm \\
&\leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t}\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t}\|_2^2+(1-\eta)\lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge \label{aeq:46}
\end{align}

First, let us focus on the third term of (<ref>).

\begin{align}
\lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge &= \lge \theTR_{t,\sunion}-\thet_{t-1, \sunion}, \nabla L_{t-1,\sunion} \rge \nm \\
&=  \lge \theTR_{t,S^{t}}-\thet_{t-1,S^{t}}, \nabla L_{t-1, S^{t}}  \rge+ \lge \theTR_\sdiffb-\thet_{t-1,\sdiffb}, \nabla L_{t-1, \sdiffb} \rge \nm \\
&=  \lge \theTR_{t,S^{t}}-\thet_{t-1,S^{t}}, \nabla L_{t-1, S^{t}}  \rge- \lge \thet_{t-1,\sdiffb}, \nabla L_{t-1, \sdiffb} \rge, \label{aeq:47}
\end{align}

where the last equality is due to that $\theTR_\sdiffb=0$.
By Lemma <ref> and the definition, we know that $\theTR_{t}$ can be written as $\theTR_{t}=\thehat_{t,S^{t}}+\phi_{t,S^{t}}$, where $\thehat_t=(\theta_{t-1}-\eta_0\tilde{\nabla} L_{t-1})_{S^{t}}$ and $\phi_t$ is a sub-Gaussian vector with variance $=O\left(\frac{d\tau_1^2(k'\tau_1^2+\tau_2^2)}{m\epsilon^2}\right)$. Thus,

\begin{align}\label{aeq:48}
& \lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge= \lge \thehat_{t, S^{t}}-\thet_{t-1,S^{t}}, \nabla L_{t-1, S^{t}} \rge \nm\\
&+\lge \phi_{t,S^{t}},\nabla L_{t-1, S^{t}}\rge -\lge \thet_{t-1,\sdiffb},\nabla L_{t-1, \sdiffb}  \rge.
\end{align}

For the first term in (<ref>) we have

\begin{align}
& \lge \thehat_{t, S^{t}}-\thet_{t-1,S^{t}}, \nabla L_{t-1, S^{t}} \rge = \lge -\eta_0\tilde{\nabla} L_{t-1,S^{t}}, \nabla L_{t-1, S^{t}} \rge =-\frac{\eta}{\gamma} \lge \tilde{\nabla} L_{t-1,S^{t}}, \nabla L_{t-1, S^{t}} \rge \nm \\
&= -\frac{\eta}{\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2-\frac{\eta}{\gamma} \langle \tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}, \nabla L_{t-1, S^{t}} \rge \nm \\
&\leq -\frac{\eta}{\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2+ \frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2+ \frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2 \nm \\
&= -\frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2+\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2 \label{aeq:49}.
\end{align}

Take (<ref>) into (<ref>) we have for $c_{1}>0$

\begin{multline}\label{aeq:50}
\begin{aligned}
\lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge \leq&  -\frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2+\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2\\
+\frac{1}{4c_1}\|\nabla L_{t-1, S^{t}}\|_2^2-\lge \thet_{t-1,\sdiffb},\nabla L_{t-1, \sdiffb}  \rge.
\end{aligned}
\end{multline}

For the last term of (<ref>) we have

\begin{align}
&-\lge \thet_{t-1,\sdiffb},\nabla L_{t-1, \sdiffb}  \rge \nm\\ &\leq \frac{\gamma}{2\eta}(\|\thet_{t-1,\sdiffb}-\frac{\eta}{\gamma}\nabla L_{t-1, \sdiffb}\|_2^2-(\frac{\eta}{\gamma})^2 \|\nabla L_{t-1, \sdiffb}\|_2^2) \nm \\
&=\frac{\gamma}{2\eta} \|\thet_{t-1,\sdiffb}-\frac{\eta}{\gamma}\nabla L_{t-1, \sdiffb}\|_2^2-\frac{\eta}{2\gamma} \|\nabla L_{t-1, \sdiffb}\|_2^2 \nm\\
&\leq \frac{\eta}{2\gamma}(1+\frac{1}{c_1})\|\nabla L_{t-1, \sdiffa}\|^2_2+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2\nm \\
&-\frac{\eta}{2\gamma} \|\nabla L_{t-1, \sdiffb}\|_2^2,\label{aeq:51}
\end{align}

where the last inequality comes from

\begin{align*}
&\|\thet_{t-1,\sdiffb}-\frac{\eta}{\gamma}\nabla L_{t-1, \sdiffb}\|_2-\frac{\eta}{\gamma}\|\nabla L_{t-1, \sdiffb}-\tilde{\nabla} L_{t-1, \sdiffb}-\phi_{t, \sdiffb}\|_2  \\
&\leq \|\thet_{t-1,\sdiffb}-\frac{\eta}{\gamma}(\tilde{\nabla} L_{t-1, \sdiffb}+\phi_{t, \sdiffb})\|_2\\ &\leq \|\thet_{t-1,\sdiffa}-\frac{\eta}{\gamma}(\tilde{\nabla} L_{t-1, \sdiffa}+\phi_{t, \sdiffa})\|_2=\frac{\eta}{\gamma}\|\tilde{\nabla} L_{t-1, \sdiffa}+\phi_{t, \sdiffa}\|_2\\
&\leq \frac{\eta}{\gamma}\|\nabla L_{t-1, \sdiffa}\|_2+\frac{\eta}{\gamma}\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|_2,
\end{align*}

where the second inequality is due to the fact that $|\sdiffa| = |\sdiffb|$. the definitions of hard thresholding, $\theta'_{t}=(\thet_{t-1}-\frac{\eta}{\gamma}(\tilde{\nabla} L_{t-1}+\phi_{t}))_{S^t}$, $S^t$ and $S^{t-1}$; the first equality is due to $\text{Supp}(\theta_{t-1})=S^{t-1}$
Thus we have

\begin{multline*}
\frac{\gamma}{2\eta}\|\thet_{t-1,\sdiffb}-\frac{\eta}{\gamma}\nabla L_{t-1, \sdiffb}\|^2_2 \\
\leq \frac{\eta}{2\gamma}(1+\frac{1}{c_1})\|\nabla L_{t-1, \sdiffa}\|^2_2+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2
\end{multline*}

We can easily see that

\begin{align*}
&\frac{\eta }{2\gamma}\|\nabla L_{t-1, S^{t}\backslash S^{t-1}}\|_2^2-\frac{\eta}{2\gamma} \|\nabla L_{t-1, \sdiffb}\|_2^2 -\frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2\\
=& -\frac{\eta}{2\gamma} \|\nabla L_{t-1, \sdiffb}\|_2^2-\frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\bigcap S^{t-1}}\|_2^2 \\
=&-\frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\bigcup S^{t-1}}\|_2^2.
\end{align*}

In total

\begin{multline}\label{aeq:53}
\lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge \\
\leq -\frac{\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\bigcup S^{t-1}}\|_2^2 +(\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2+\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2\\+c_{1}\|\phi_{t,S^{t}}\|_2^2+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2
\end{multline}

Take (<ref>) into (<ref>) we have

\begin{align}
\leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t}\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t}\|_2^2+(1-\eta)\lge \theTR_{t}-\thet_{t-1}, \nabla L_{t-1} \rge  \nm \\
&\leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t}\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t}\|_2^2-\frac{(1-\eta)\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\bigcup S^{t-1}}\|_2^2
\nm \\& +(1-\eta) (\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2 +(1-\eta)[\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2+c_{1}\|\phi_{t,S^{t}}\|_2^2\nm \\ &+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2] \nm  \\
& \leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2\nm\\
&- \frac{\eta^2}{2\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2 -\frac{(1-\eta)\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\bigcup S^{t-1}}\|_2^2 \nm \\
& +(1-\eta) (\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2 \nm  +(1-\eta)[\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2+c_{1}\|\phi_{t,S^{t}}\|_2^2 \nm \\ &+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2] \nm  \\
& \leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2- \frac{\eta^2}{2\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2  \nm \\& -\frac{(1-\eta)\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2+(1-\eta) (\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2 \nm\\
&+\underbrace{(1-\eta)(\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2+c_{1}\|\phi_{t,S^{t}}\|_2^2+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2)}_{N_0^t}, \label{aeq:54}
\end{align}

where the last inequality is due to $S^{t}\backslash(S^* \bigcup S^{t-1})\subseteq S^{t}\bigcup S^{t-1}$. Next we will analyze the term $ \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2$ in (<ref>).

Let $R$ be a subset of $\sdiffb$ such that $|R|=|I^t\backslash (S^*\bigcup S^{t-1})|=|S^{t}\backslash (S^{t-1}\bigcup S^*)|$. By the definition of hard thresholding,  we can easily see

\begin{multline}\label{aeq:55}
\begin{aligned}
\|\theta_{t-1,R}-\frac{\eta}{\gamma}(\tilde{\nabla} L_{t-1,R}+ \phi_{t, R} )\|_2^2 \leq&  \|(\theta_{t-1}-\frac{\eta}{\gamma}(\tilde{\nabla} L_{t-1}+\phi_{t} ))_{I^t\backslash (S^*\bigcup S^{t-1})}\|_2^2\\ =&\frac{\eta^2}{\gamma^2}\|(\tilde{\nabla} L_{t-1}+\phi_{t} )_{I^t\backslash (S^*\bigcup S^{t-1})}\|_2^2.
\end{aligned}
\end{multline}

Thus we have

\begin{equation}\label{aeq:56}
\begin{aligned}
&(\frac{\eta}{\gamma}) \|\nabla L_{t-1, I^t\backslash (S^*\bigcup S^{t-1})}\|_2\\
\geq& \underbrace{\|\theta_{t-1,R}-\frac{\eta}{\gamma}\nabla L_{t-1, R}\|_2}_{a}
-\frac{\eta}{\gamma}(\underbrace{\|\tilde{\nabla} L_{t-1,R}-\nabla L_{t-1, R}+\phi_{t, R}\|_2}_b\\
+&\underbrace{\|\nabla L_{t-1, I^t\backslash (S^*\bigcup S^{t-1})}-\tilde{\nabla} L_{t-1,I^t\backslash (S^*\bigcup S^{t-1})}-\phi_{t, I^t\backslash (S^*\bigcup S^{t-1})}\|_2}_c)\\
\end{aligned}
\end{equation}

Then we have for any $c_2>0$

\begin{align}
&\frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2\nm\\
&\leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\gamma}{2}( \frac{\eta^2}{\gamma^2}(b+c)^2+a^2-\frac{2\eta}{\gamma}(b+c)a) \nm\\
&\leq  \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\gamma}{2}(1-\frac{1}{c_2})a^2+(2c_2-\frac{1}{2})\frac{\eta^2}{\gamma}(b+c)^2 \nm\\
&=\frac{\gamma}{2}\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2+\frac{\gamma}{2c_2}\|\theta_{t-1,R}-\frac{\eta}{\gamma}\nabla L_{t-1, R}\|_2^2 \nm\\
& + \underbrace{(4c_2-1)\frac{\eta^2}{\gamma}(\|\tilde{\nabla} L_{t-1,R}-\nabla L_{t-1, R} + \phi_{t,I^{t}}\|_2^2+\|\nabla L_{t-1, I^t\backslash (S^*\bigcup S^{t-1})}-\tilde{\nabla} L_{t-1,I^t\backslash (S^*\bigcup S^{t-1})} -\phi_{t, I^t\backslash (S^*\bigcup S^{t-1})}\|_2^2)}_{N^t_1}\label{aeq:56}\\
&\leq \frac{\gamma}{2}\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2+\frac{\gamma}{c_2}\|\theta_{t-1,R}-\frac{\eta}{\gamma}(\tilde{\nabla} L_{t-1, R}+\phi_{t, R}) \|_2^2 \nm\\
& +\underbrace{\frac{\eta^2}{c_2\gamma}\|\nabla L_{t-1, I^t\backslash R}-(\tilde{\nabla} L_{t-1, R}+\phi_{t, R})\|_2^2+N^t_1}_{N_2^t}\label{aeq:57}  \\
&=  \frac{\gamma}{2}\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2+N_2^t, \label{aeq:58}
\end{align}

where (<ref>) is due to that $\theta'_{t-1, R}=0$, thus $\|\theta'_{t-1, R}-(\theta_{t-1,R}-\frac{\eta}{\gamma}\nabla L_{t-1, R})\|_2=  \|\theta_{t-1,R}-\frac{\eta}{\gamma}\nabla L_{t-1, R}\|_2$. In the following, we will consider the first term in (<ref>).

In Lemma <ref>, take $v=\thet_{t-1,I^t\backslash R}-\frac{\eta}{\gamma} (\tilde{\nabla} L_{t-1,I^t\backslash R}+\phi_{t-1,I^t\backslash R})$, $\tilde{v}=\text{Trunc}(v, k')=\theta'_{t-1, I^t \backslash R}$, $I=I^t\backslash R$, $v^*=\theta^*_{I^t\backslash R}=\theta^*$, we have

\begin{equation*}
\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}-\frac{\eta}{\gamma} (\tilde{\nabla} L_{t-1,I^t\backslash R}+\phi_{t-1,I^t\backslash R})\|_2^2\leq \frac{|I^t\backslash R|-k'}{|I^t\backslash R|-k}\|\theta^*-\thet_{t-1,I^t\backslash R}-\frac{\eta}{\gamma} ( \tilde{\nabla} L_{t-1,I^t\backslash R}+\phi_{{t-1,I^t\backslash R}} )\|_2^2.
\end{equation*}

Then we have

\begin{align*}
&(1-\frac{1}{c_3})\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2-(c_3-1)\frac{\eta^2}{\gamma^2}\|\nabla L_{t-1, I^t\backslash R}-\tilde{\nabla} L_{t-1,I^t\backslash R}-\phi_{t-1,I^t\backslash R}\|_2^2 \nm \\&\leq
\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \tilde{\nabla} L_{t-1,I^t\backslash R}\|_2^2 \\
&\leq \frac{|I^t\backslash R|-k'}{|I^t\backslash R|-k}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \tilde{\nabla} L_{t-1,I^t\backslash R}\|_2^2 \\
&\leq \frac{|I^t\backslash R|-k'}{|I^t\backslash R|-k}\left((1+\frac{1}{c_3})\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2 +(1+c_3)\frac{\eta^2}{\gamma^2}\|\nabla L_{t-1, I^t\backslash R}-\tilde{\nabla} L_{t-1,I^t\backslash R}-\phi_{t-1,I^t\backslash R} \|_2^2 \right)
\end{align*}

Since $|I^t\backslash R|\leq 2k'+k$ and $k'\geq k$, we have $\frac{|I^t\backslash R|-k'}{|I^t\backslash R|-k}\leq \frac{k'+k}{2k'}\leq \frac{2k'}{k+k'}$. Thus

\begin{multline*}
\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2\leq \frac{2k}{k+k^{\prime}}\frac{c_3+1}{c_3-1}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2\\+ ((1+c_3)\frac{2k}{k+k'}+c_3-1)\frac{\eta^2}{\gamma^2}\|\nabla L_{t-1, I^t\backslash R}-\tilde{\nabla} L_{t-1,I^t\backslash R}-\phi_{t-1,I^t\backslash R} \|_2^2
\end{multline*}

Take $c_3=5$ and $k'=O(k)$,  we have

\begin{align}\label{aeq:60}
&\|\theta'_{t,I^t\backslash R}-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2\leq \frac{3}{2}\frac{2k}{k+k^{\prime}}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2\nm \\
&+\underbrace{O(\frac{\eta^2}{\gamma^2}\|\nabla L_{t-1, I^t\backslash R}-\tilde{\nabla} L_{t-1,I^t\backslash R}-\phi_{t-1,I^t\backslash R} \|_2^2)}_{N_3^t}.
\end{align}

Take (<ref>) into (<ref>) we have

\begin{align}
&\frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2\nm \\
&\leq \frac{3\gamma}{2}\frac{k}{k+k'}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2+N_2^t+\gamma N_3^t. \label{aeq:64}
\end{align}

\begin{align}
&\frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2\nm \\
&\leq \frac{3\gamma s^*}{2(s+s^*)}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2+ \frac{\gamma}{2c}(1+\frac{1}{c})\|\frac{\eta}{\gamma}\nabla L_{t-1, I^t\backslash (S^*\bigcup S^{t-1})}\|_2^2+\frac{\gamma}{2}\|\phi_{t,S^{t}}\|_2^2  \nm \\
&  + N_1^t+N_3^t\\
&=  \frac{3\gamma s^*}{2(s+s^*)}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2+ \frac{\gamma}{2c}(1+\frac{1}{c})\|\frac{\eta}{\gamma}\nabla L_{t-1, S^{t}}\|_2^2  \nm \\
&\qquad  +\frac{\gamma}{2}\|\phi_{t,S^{t}}\|_2^2+ N_1^t+N_3^t \\
&= \frac{3 s^*}{s+s^*}(
\eta \lge  \theta^*-\thet_{t-1}, \nabla L_{t-1} \rge +\frac{\gamma}{2}\|\theta^*-\thet_{t-1}\|_2^2+\frac{\eta^2}{2c \gamma }\|\nabla L_{t-1, I^t}\|_2^2)+ \frac{\eta^2}{2c\gamma}(1+\frac{1}{c})\|\nabla L_{t-1, S^{t}}\|_2^2  \nm \\
&\qquad  +\frac{\gamma}{2}\|\phi_{t,S^{t}}\|_2^2+  N_1^t+N_3^t  \\
&\leq \frac{3 s^*}{s+s^*}(
\eta (L(\theta^*)-\LT
)+\frac{\gamma-\eta \mu}{2}\|\theta^*-\thet_{t-1}\|_2^2+\frac{\eta^2}{2c \gamma }\|\nabla L_{t-1, I^t}\|_2^2)+ \frac{\eta^2}{2c\gamma}(1+\frac{1}{c})\|\nabla L_{t-1, S^{t}}\|_2^2  \nm \\
&\qquad  +\underbrace{\frac{\gamma}{2}\|\phi_{t, S^{t}}\|_2^2+  N_1^t+N_3^t }_{N_2^t}.  \label{aeq:64}
\end{align}

Take (<ref>) into (<ref>) we have

\begin{align}
&\LD-\LT \nm \\
&\leq \frac{\gamma}{2}\|\theTR_{t,I^t}-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t }\|_2^2-\frac{\eta^2}{2\gamma}\|\nabla L_{t-1, I^t\backslash (S^{t-1}\bigcup S^*)}\|_2^2- \frac{\eta^2}{2\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2  \nm \\& -\frac{(1-\eta)\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2+(1-\eta) (\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2 +N_0^t \nm \\
&\leq \frac{3\gamma }{2}\frac{k}{k'+k}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2- \frac{\eta^2}{2\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2  \nm \\& -\frac{(1-\eta)\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2+(1-\eta) (\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2+N_0^t+N_2^t+\gamma N_3^t.
\end{align}

Note that when $\eta\geq  \frac{1}{2}$, there exists a sufficiently large $c_1$ is  such that  $\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1}\leq \frac{\eta}{4\gamma}$, we have

\begin{align*}
&(1-\eta) (\frac{1}{4c_1}+ \frac{\eta}{2\gamma c_1})\|\nabla L_{t-1, S^{t}}\|_2^2\leq
\frac{\eta(1-\eta)}{4\gamma} \|\nabla L_{t-1, S^{t}}\|_2^2
\\
& \leq \frac{\eta^2}{4\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2  +\frac{(1-\eta)\eta}{4\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2
\end{align*}

\begin{align*}
&\LD-\LT \nm \\
\leq& \frac{3\gamma }{2}\frac{k}{k'+k}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2- \frac{\eta^2}{2\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2  \nm \\
-&\frac{(1-\eta)\eta}{2\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2+\frac{(1-\eta)}{4c}\|\nabla L_{t-1, S^{t}}\|_2^2+N_0^t+N_2^t+\gamma N_3^t \\
\leq &\frac{3\gamma }{2}\frac{k}{k'+k}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2- \frac{\eta^2}{4\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2 \nm \\
-&\frac{(1-\eta)\eta}{4\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2+N_0^t+N_2^t+\gamma N_3^t
\end{align*}

It is notable that by strong convexity

\begin{align*}
&\frac{3\gamma }{2}\frac{k}{k'+k}\|\theta^*-\thet_{t-1,I^t\backslash R}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t\backslash R}\|_2^2  \\
&\leq \frac{3\gamma }{2}\frac{k}{k'+k}\|\theta^*-\thet_{t-1,I^t}+\frac{\eta}{\gamma} \nabla L_{t-1, I^t}\|_2^2 \\
&= \frac{3\gamma }{2}\frac{k}{k'+k} (\|\theta^*-\thet_{t-1,I^t\backslash R}\|_2^2+\frac{\eta^2}{\gamma^2}\| \nabla L_{t-1, I^t}\|_2^2+\frac{2\eta}{\gamma}\langle \theta^*-\thet_{t-1,I^t}, \nabla L_{t-1, I^t} \rangle) \\
&= \frac{3\gamma }{2}\frac{k}{k'+k} (\|\theta^*-\thet_{t-1,I^t\backslash R}\|_2^2+\frac{\eta^2}{\gamma^2}\| \nabla L_{t-1, I^t}\|_2^2+\frac{2\eta}{\gamma}\langle \theta^*-\thet_{t-1}, \nabla L_{t-1} \rangle)\\
&\leq  \frac{3k}{k'+k} \big(\frac{\gamma}{2}\|\theta^*-\thet_{t-1}\|_2^2+ \frac{\eta^2}{2 \gamma }\|\nabla L_{t-1, I^t}\|_2^2+\eta (L(\theta^*)-\LT)-\frac{\eta\mu}{2}\|\theta^*-\theta_{t-1}\|_2^2\big)
\end{align*}

Take $\eta=\frac{2}{3}$, $k'=72\frac{\gamma^2}{\mu^2}k$ so that $\frac{3 k}{k'+k}\leq \frac{\mu^2}{24\gamma(\gamma-\eta \mu)}\leq \frac{1}{8}$, we have

\begin{align}
\leq& \frac{3 k}{k+k^{\prime}}(
\eta (L(\theta^*)-\LT)+\frac{\gamma-\eta \mu}{2}\|\theta^*-\thet_{t-1}\|_2^2+\frac{\eta^2}{2 \gamma }\|\nabla L_{t-1, I^t}\|_2^2)  \nm \\
-&  \frac{\eta^2}{4\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2-\frac{(1-\eta)\eta}{4\gamma} \|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2   +N_0^t+N_2^t+\gamma N_3^t\nm \\
\leq& \frac{2 k}{k'+k}(L(\theta^*)-\LT)+ \frac{\mu^2}{48\gamma}\|\theta^*-\theta_{t-1}\|_2^2+\frac{1}{36\gamma}\|\nabla L_{t-1, I^t}\|_2^2 \nm \\
-&\frac{1}{9\gamma}\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2-\frac{1}{18\gamma}\|\nabla L_{t-1, S^{t}\backslash(S^* \bigcup S^{t-1})}\|_2^2+N_0^t+N_2^t+\gamma N_3^t \nm \\
\leq & \frac{2 k}{k+k'}(L(\theta^*)-\LT)-\frac{3}{36\gamma}(\|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2-\frac{\mu^2}{4}\|\theta^*-\theta_{t-1}\|_2^2)+N_0^t+N_2^t+\gamma N_3^t \label{aeq:68}\\
\leq &(\frac{2 k}{k+k'}+\frac{\mu}{24\gamma})(L(\theta^*)-\LT)+N_0^t+N_2^t+\gamma N_3^t \label{aeq:69}.
\end{align}

Where (<ref>) is due to the following lemma:
[Lemma 6 in [28]]

\begin{equation}
|\nabla L_{t-1, (S^{t-1}\bigcup S^*)}\|_2^2-\frac{\mu^2}{4}\|\theta^*-\theta_{t-1}\|_2^2\geq \frac{\mu}{2}(\LT-L(\theta^*)).
\end{equation}

\begin{equation*}
\LD- L(\theta^*)\leq (1-\frac{5}{72}\frac{\mu}{\gamma})( \LT- L(\theta^*))+N_0^t+N_2^t+\gamma N_3^t.
\end{equation*}

Next, we will bound the term $N_0^t+N_2^t+\gamma N_3^t$. For $N_0^t$ we have

\begin{align*}
N_0^t&=(1-\eta)(\frac{\eta}{2\gamma}\|\tilde{\nabla} L_{t-1,S^{t}}-\nabla L_{t-1, S^{t}}\|_2^2\\
&+c_{1}\|\phi_{t,S^{t}}\|_2^2+\frac{2\eta}{\gamma}(1+c_1)\|\nabla L_{t-1, \sdiffa}-\tilde{\nabla} L_{t-1, \sdiffa}-\phi_{t, \sdiffa}\|^2_2)\\
&=O(\frac{1}{\gamma}k' \|\tilde{\nabla} L_{t-1}-\nabla L_{t-1}\|_\infty^2+\gamma k'\|\phi_t\|_\infty^2).
\end{align*}

By (<ref>), we know that with probability at least $1-\delta'$

\begin{equation}
\|\tilde{\nabla} L_{t-1}-\nabla L_{t-1}\|_\infty \leq O(\frac{\sigma^2 \log n \log \frac{d}{\delta'}}{\sqrt{m}}).
\end{equation}

Moreover, by Lemma <ref> we have with probability at least $1-\delta'$

\begin{equation}
\|\phi_t\|_\infty \leq O\left(\frac{(\tau_1^2\sqrt{dk'}+\tau_1\tau_2\sqrt{d})\sqrt{\log \frac{d}{\delta'}} }{\sqrt{m}\epsilon}\right).
\end{equation}

Thus, with probability at least $1-\delta'$ we have

\begin{equation*}
N_0^t=O(\frac{\sigma^4 d{k'}^2\log d/\delta' \log^2 n}{m\epsilon^2}).
\end{equation*}

Similarly, we have

\begin{equation*}
N_2^t, N_3^t=O(\frac{\sigma^4 d{k'}^2 \log d/\delta'  \log^2 n}{m\epsilon^2}).
\end{equation*}

Thus we have with probability at least $1-\delta'$

\begin{equation}
\LD- L(\theta^*)\leq (1-\frac{5}{72}\frac{\mu}{\gamma})( \LT- L(\theta^*))+O(\frac{\sigma^4 d{k'}^2\log d/\delta'  \log^2 n}{m\epsilon^2}).\label{aeq:73}
\end{equation}

In the following we will assume the above event holds. We note that by our model for any $\theta$

\begin{equation*}
\gamma \|\theta-\theta^*\|_2^2\geq   L(\theta) - L(\theta^*)\geq \mu \|\theta-\theta^*\|_2^2.
\end{equation*}

In the following we will show that $\theta_t=\theTR_{t}$ for all $t$. We will use induction, assume $\theta_i=\theTR_{i}$ holds for all $i\in [t-1]$, we will show that it will also true for $t$. Use (<ref>) for $i\in [t-1]$ we have

\begin{align}
\mu \|\theTR_{t}-\theta^*\|_2^2&\leq  \LD- L(\theta^*)\nm \leq (1-\frac{5}{72}\frac{\mu}{\gamma})( \LT- L(\theta^*))+O(\frac{\sigma^4 d{k'}^2\log d/\delta'  \log^2 n}{m\epsilon^2})\\ &\leq(1-\frac{5}{72}\frac{\mu}{\gamma})^t( L(\theta_0)- L(\theta^*))+
O(\frac{\sigma^4 d{k'}^2\log d/\delta'  \log^2 n}{m\epsilon^2}) \nm \\
&\leq \gamma(1-\frac{5}{72}\frac{\mu}{\gamma})^{t-1} \|\theta_0-\theta^*\|_2^2
+O(\frac{\gamma}{\mu}\frac{\sigma^4 d{k'}^2\log d \log^2 n}{m\epsilon^2})\nm
\end{align}

When $\|\theta_0-\theta^*\|_2^2\leq \frac{1}{2}\frac{\mu}{\gamma}$, and $n$ is large enough such that

\begin{align*}
&n\geq \tilde{\Omega}(\frac{\gamma}{\mu^2} \frac{k'^2 d \sigma^4 T}{ \epsilon^2})
\end{align*}

Then $\|\theTR_{t}\|_2\leq \|\theta^*\|_2+\sqrt{\frac{1}{2}+\frac{1}{2}}\leq 2$. Thus $\theta_t=\theTR_{t}$. So we have with probability at least $1-\delta'$

\begin{align}
&\mu \|\theTR_{t}-\theta^*\|_2^2\leq  L(\theta^{T})- L(\theta^*)\leq(1-\frac{5}{72}\frac{\mu}{\gamma})^T( L(\theta_0)- L(\theta^*))+O(\frac{\gamma}{\mu}\frac{\sigma^4 d{k'}^2 T\log \frac{dT}{\delta'} \log^2 n}{n\epsilon^2})  \nm
\end{align}

Thus, take $T=\tilde{O}(\frac{\gamma}{\mu}\log n)$ and  $k'= O( (\frac{\gamma}{\mu})^2 k)$ we have the result.


# Introducing DictaLM \- A Large Generative Language Model for Modern Hebrew

Shaltiel Shmidman1,†, Avi Shmidman1,2,‡, Amir David Nissan Cohen2,†, Moshe
Koppel1,2,†
1DICTA / Jerusalem, Israel 2Bar Ilan University / Ramat Gan, Israel
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

We present DictaLM, a large-scale language model tailored for Modern Hebrew.
Boasting 7B parameters, this model is predominantly trained on Hebrew-centric
data. As a commitment to promoting research and development in the Hebrew
language, we release both the foundation model and the instruct-tuned model
under a Creative Commons license111For specifics on the license, visit
https://creativecommons.org/licenses/by-sa/4.0/. Concurrently, we introduce
DictaLM-Rab, another foundation model geared towards Rabbinic/Historical
Hebrew. These foundation models serve as ideal starting points for fine-tuning
various Hebrew-specific tasks, such as instruction, Q&A Cohen et al. (2023),
sentiment analysis Amram et al. (2018), and more Bareket and Tsarfaty (2021).
This release represents a preliminary step, offering an initial Hebrew LLM
model for the Hebrew NLP community to experiment with.

##  1 Introduction

Language models have revolutionized the realm of natural language processing,
facilitating significant advancements in tasks ranging from sentiment analysis
to machine translation. As the breadth and depth of these models expand, so
does the aspiration for linguistic diversity. Yet, while the majority of
state-of-the-art models cater predominantly to widely spoken languages, there
exists a vast landscape of languages and dialects that are underrepresented in
currently existing large-scale language models. Hebrew is one such language.

In this paper, we make strides to bridge this gap by introducing DictaLM \-
the first large-scale language model crafted for Modern Hebrew. By leveraging
a dataset dominated by Hebrew-centric content, our endeavor was not only to
construct a model adept at understanding and generating Modern Hebrew but also
to lay down a foundation that facilitates further advancements in the field.
As part of this initiative, we also present DictaLM-Rab, a parallel model
pretrained for Rabbinic/Historical Hebrew, thereby encompassing the vast
chronological spectrum of the Hebrew language. This release serves as a
preliminary step, providing an initial tentative version to the Hebrew NLP
community as a foundation for further refinements, adaptations, and
collaborative enhancements. Figure 1 demonstrates example output from the
instruct-tuned model.

Figure 1: We present two instances of DictaLM utilization: in the first
instance, the model exhibits common sense reasoning, while in the second, it
displays worldly knowledge.

##  2 Datasets

In this section, we elucidate the datasets employed for training and fine-
tuning DictaLM. The assemblage of data, amassing a total of 7.5 billion
tokens, originates from a mixture of authentic sources; no synthetic data was
added. The pre-training phase is followed by a fine-tuning stage through
instruct datasets derived from Hebrew Question-Answering datasets and a
translated version of the MPT Instruct Dataset.

###  2.1 Pre-training Data

The dataset is built up of several different components:

C4 [80%]. We start with the HeDC4 corpus released by Shalumov and Haskey
(2023), and continue further cleaning it. We removed approximately 15% of the
corpus using various techniques including histograms, gibberish detectors, as
well as removing sentences that had a very high perplexity when running
through a Modern Hebrew BERT model. In addition, we limited our training
corpus to contain only words in English and Hebrew, and all other languages
were reduced to a designated <foreign> token to avoid cluttering the tokenizer
with non-Hebrew tokens. The resulting corpus contains approximately 6B byte-
pair tokens.

Other sources [20%]. We collected data from various other sources including
news sites, blogs, tv and movie subtitles, novels, and more. This data was
also run through a similar cleaning process to the C4 corpus, as described
above, and resulted in an additional 1.5B byte-pair tokens.

####  2.1.1 Instruct Data

Our instruct-tuning data contains a mixture of 2 different datasets, each
processed and modified in order to teach the model to follow as many different
instructions as possible.

QA Datasets. We take the HeQ Cohen et al. (2023) and ParaShoot Keren and Levy
(2021) training datasets and format them as instructions. The prompt contains
the context paragraph followed by the question, with a system instruction. The
system instruction starts with a general instruction (in Hebrew) stating
"Please read the following paragraph and answer the question that comes
after", and 60% of the time also instructs the system to format a specific
type of response (e.g., "Short and to the point", "Please cite the sentence to
support your answer", and more). We list a few examples in Appendix A.

Translated MPT Instruct. We took the MPT Instruct Dataset from
huggingface222https://huggingface.co/datasets/mosaicml/dolly_hhrlhf and ran it
through a translation API. We then reformatted the prompt to remove the
constant structure, and left the question only. We then added in each question
three times: Once with no system prompt, and twice with two different prompts
chosen based on the length of the response, asking the model to be concise,
expand, answer in X sentences, etc. We list a few examples in Appendix B.

##  3 Model architecture

###  3.1 Tokenizer

A major problem we encountered when attempting to use other multilingual LLMs
for Hebrew was the tokenization. When the corpus contains a very small
percentage of a language, then the number of tokens representing that language
in the vocabulary is significantly reduced. In addition, due to the nature of
UTF-8 encoding, byte-pair tokenization methods result in even scarcer
representation of Hebrew in the vocabulary. As can be seen in OpenAI’s GPT-3
tokenizer333https://platform.openai.com/tokenizer, if one inserts a few
paragraphs of Hebrew text, the tokenizer will average 1.1 tokens per
character.

We train our tokenizer using the byte-pair encoding (BPE) algorithm Sennrich
et al. (2015) on our cleaned corpus with a vocabulary size of 56000. The
resulting tokenizer had a ratio of approximately 1.3 tokens per word.

###  3.2 Architecture

In this section, we detail the architectural framework of DictaLM. Following
recent work on large language models, our network is based on the transformer
architecture Vaswani et al. (2017). Our architecture encompasses several
enhancements aimed at boosting training stability and overall performance:

Normalization. To improve training stability and balance the input, we
normalize the input of each transformer layer before and after the attention
calculation. We use the LayerNorm1P normalization with $\epsilon=1e-5$, which
is a slightly modified version of the FastLayerNorm normalization offered by
NVIDIA’s APEX library444https://github.com/NVIDIA/apex.

GeLU Activation. As reported by Hendrycks and Gimpel (2023), we use the GeLU
activation function.555We considered using other activations (such as SwiGLU
Shazeer (2020)), but in the end we went with GeLU

Rotary Embeddings. Shown to be effective for extending the sequence length
without a performance trase-off, we use rotary positional embedding (RoPE)
with a $0.5\%$ dimension percentage, introduced by Su et al. (2022), at each
layer of the network.

Separate embedding and output weights. As shown by Welch et al. (2020),
separating the embeddings and the output weights leads to better performance.

###  3.3 Training Details and Hyperparameters

We trained our model using the NeMo framework666https://github.com/NVIDIA/NeMo
which is highly optimized for training compute-heavy machine learning models
on NVIDIA hardware. We pre-trained the model on 8 H100 GPUs with tensor
parallel size of 2 for a total of 150 hours completing 2.5 epochs ($\sim$18.5B
tokens), and then fine-tuning for instructions for 8 hours. The training was
done in a combination of bf16 and fp8 precision using NVIDIA’s transformer
engine777https://github.com/NVIDIA/TransformerEngine. The training was done
with a global batch size of 128. We used the FusedAdam optimizer, with an
initial learning rate of $0.00016$, betas of $0.9,0.95$ and the Cosine-
Annealing schedule with a warmup of 750 steps and a minimum learning rate of
$1e-5$. The details for the model size are listed in Table 1.

Max Sequence Length | 2048
---|---
Num Layers | 32
Hidden Size | 4096
Intermediate Size | 10880
Attention Heads | 32
Table 1: Model size

###  3.4 DictaLM-Rab Model

In addition to the model we described above, we also trained a model DictaLM-
Rab for use with Rabbinic Hebrew tasks. We used the same approach as above,
adjusting the input corpus to contain a large sampling of Rabbinic Hebrew
data.

Specifically, we added a corpus of 1.2B tokens of Rabbinic Hebrew texts taken
from various sources (e.g. Sefaria888https://www.sefaria.org.il/,
Dicta999https://library.dicta.org.il/). We combined this corpus together with
the modern Hebrew corpus that we described above, sampling the data such that
fifty percent of the training sequences would be from the Rabbinic Hebrew
corpus (with oversampling).

The model uses the same tokenizer as DictaLM, and was trained for a total of
1.5 iterations ($\sim$12.5B tokens).

We are pleased to also release this foundation model, tailored to benefit
researchers working on Rabbinic Hebrew. This model can be used as a base model
for fine-tuning on specific tasks relevant to the Rabbinic Hebrew domain. Our
internal experiments reveal encouraging results with Rabbinic texts, details
of which will be shared in forthcoming publications.

##  4 Drawbacks

Our model was trained on the full dataset without any censorship for offensive
or biased material, and therefore it may generate sentences that are offensive
to some users.

Also, we would like to highlight that this project is in its alpha phase.
While we are releasing DictaLM to facilitate research endeavors, and while we
believe that it can serve as a useful foundation for specific fine-tuned tasks
in the realm of Hebrew NLP, we acknowledge that the quality of the model does
not yet match industry standards.

##  5 Conclusion

We are pleased to present the three models described within this paper: the
two foundational models (suitable as base models for further fine-tuning for
tasks concerning both Modern and Rabbinic Hebrew), and the instruct model,
fine-tuned to address instruction prompts in Modern Hebrew. The public release
of these models aims to contribute to the advancement of research and
development within the Hebrew NLP domain. The models can be accessed via the
following links:

  * •

Foundation model DictaLM: https://huggingface.co/dicta-il/dictalm-7b

  * •

Instruct model DictaLM-Instruct: https://huggingface.co/dicta-
il/dictalm-7b-instruct

  * •

Foundation model for Rabbinic Hebrew DictaLM-Rab:
https://huggingface.co/dicta-il/dictalm-rab-7b

## References

  * Amram et al. (2018) Adam Amram, Anat Ben David, and Reut Tsarfaty. 2018.  Representations and architectures in neural sentiment analysis for morphologically rich languages: A case study from Modern Hebrew.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2242–2252, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Bareket and Tsarfaty (2021) Dan Bareket and Reut Tsarfaty. 2021.  Neural Modeling for Named Entities and Morphology (NEMO2).  _Transactions of the Association for Computational Linguistics_ , 9:909–928.
  * Cohen et al. (2023) Amir DN Cohen, Hilla Merhav Fine, Yoav Goldberg, and Reut Tsarfaty. 2023.  Heq: a large and diverse hebrew reading comprehension benchmark.
  * Hendrycks and Gimpel (2023) Dan Hendrycks and Kevin Gimpel. 2023.  Gaussian error linear units (gelus).
  * Keren and Levy (2021) Omri Keren and Omer Levy. 2021.  Parashoot: A hebrew question answering dataset.  In _Proceedings of the 3rd Workshop on Machine Reading for Question Answering_ , pages 106–112.
  * Sennrich et al. (2015) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015.  Neural machine translation of rare words with subword units.  _CoRR_ , abs/1508.07909.
  * Shalumov and Haskey (2023) Vitaly Shalumov and Harel Haskey. 2023.  Hero: Roberta and longformer hebrew language models.  _arXiv:2304.11077_.
  * Shazeer (2020) Noam Shazeer. 2020.  Glu variants improve transformer.
  * Su et al. (2022) Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. 2022\.  Roformer: Enhanced transformer with rotary position embedding.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _CoRR_ , abs/1706.03762.
  * Welch et al. (2020) Charles Welch, Rada Mihalcea, and Jonathan K. Kummerfeld. 2020.  Improving low compute language modeling with in-domain embedding initialisation.

##  Appendix A Appendix: Instruct Examples from QA Datasets

##  Appendix B Appendix: Instruct Examples from Translated MPT-Instruct