Proof. Given that ATEE  succeeds with high probability, the contraction of each iteration is characterized by 5. By solving the recursion, we have the desired convergence. ◻

Proof. The proof of 1 heavily relies on the analysis in [5]. Given that \(\nabla f_{\mathcal{B}_i}(\mathbf{\Theta})\) can be expressed as multiplication of two matrices, we slightly abuse the notation \(\mathbf{A}, \mathbf{B}\) to denote the pair of matrices that \(\mathbf{A}\mathbf{B}^\top = \nabla f_{\mathcal{B}_i}(\mathbf{\Theta})\).

Denote the output of Compressed-Product as \(\mathbf{s}\). Define the hash function \(h_1, h_2: [p] \rightarrow [b]\) and \(s_1, s2: [p] \rightarrow \{-1, 1\}\). Let \(h\) be the hash function that satisfies \(h(i,j) = h_1(i) + h_2(j) \mod b\), and \(s\) be \(s(i,j) = s_1(i) s_2(j)\). Let \(\mathbf{1}_{i,j}^{q}\) be the indicator of event \(\{ h(i,j)=q \}\). Define the index set of the top \(2k\) elements (with largest abstract value) of \(\mathbf{A}\mathbf{B}^\top\) to be \(\Psi_{2k}\). Denote the index set of the elements with absolute value greater than \(\Delta\) as \(\Psi_{\Delta}\). Let \(\Psi = \Psi_{2k} \cap \Psi_{\Delta}\), and we are interested in finding all indices in \(\Psi\).

Our proof consists of the following four main steps.

Step I: Bound the variance of a single decoded entry.

\[\begin{align} \mathbf{s}_q = \sum_{(i,j)\in [p]\times [p]} \mathbf{1}_{i,j}^q s(i,j)(\mathbf{A}\mathbf{B}^\top )_{ij} \end{align}\] For \((i^\star, j^\star)\in \Psi\), with \(q^\star = h(i^\star, j^\star)\) we have: \[\begin{align} \mathbf{s}_{q^\star} = s(i^\star, j^\star) (\mathbf{A}\mathbf{B}^\top)_{i^\star j^\star} + \sum_{(i,j)\neq (i^\star, j^\star ), (i,j)\in [p]\times [p]} \mathbf{1}_{i,j}^{q^\star} s(i,j) (\mathbf{A}\mathbf{B}^\top )_{ij} \end{align}\] Then, \[\begin{align} |\mathbf{s}_{q^\star}| \ge & s(i^\star, j^\star) \mathop{\mathrm{sign}}\left( \left( \mathbf{A}\mathbf{B}^\top\right)_{i^\star j^\star} \right) \mathbf{s}_{q^\star} \\ =& \left\vert (\mathbf{A}\mathbf{B}^\top)_{i^\star j^\star} \right\vert + s(i^\star, j^\star) \mathop{\mathrm{sign}}\left( \left( \mathbf{A}\mathbf{B}^\top\right)_{i^\star j^\star} \right) \sum_{(i,j)\neq (i^\star, j^\star ), (i,j)\in [p]\times [p]} \mathbf{1}_{i,j}^{q^\star} s(i,j) (\mathbf{A}\mathbf{B}^\top )_{ij} \end{align}\] Let \(\mathbf{s}_{q^\star}' = s(i^\star, j^\star) \mathop{\mathrm{sign}}\left( \left( \mathbf{A}\mathbf{B}^\top\right)_{i^\star j^\star} \right) \sum_{(i,j)\neq (i^\star, j^\star ), (i,j)\in [p]\times [p]} \mathbf{1}_{i,j}^{q^\star} s(i,j) (\mathbf{A}\mathbf{B}^\top )_{ij}\). We have: \[\begin{align} \mathbb{P}\left( error in one bit \right) \le \mathbb{P}\left( |\mathbf{s}_{q^\star}'| \ge \frac{\Delta}{2} \right) \le \frac{4\mathtt{var}(\mathbf{s}_{q^\star}')}{\Delta^2} \end{align}\] Taking expectation over all possible partitions (based on \(h\)), we have: \[\begin{align} \mathbb{E}_{h}\left[ \mathtt{var}(\mathbf{s}_{q^\star}') \right] = \frac{1}{b} \sum_{(i,j)\neq (i^\star, j^\star ), (i,j)\in [p]\times [p]} (\mathbf{A}\mathbf{B}^\top )_{ij}^2 \le \frac{\left\| \mathbf{A}\mathbf{B}^\top \right\|_F^2}{b}. \end{align}\]

Step II: Bound the failure probability of recovering a single large entry.

By Markov’s inequality, we have \[\begin{align} \mathbb{P}\left( \mathtt{var}(\mathbf{s}_{q^\star}') \ge \frac{c\left\| \mathbf{A}\mathbf{B}^\top \right\|_F^2}{b} \right) \le \frac{1}{c}. \end{align}\] Given the upper bound on \(\mathtt{var}(\mathbf{s}_{q^\star}')\), which happens with probability at least \(1-\frac{1}{c}\) due to the randomness from \(h\), the only left randomness comes from \(s(i,j)\). Note that we use the same \(h\) for every \(t\) . Then, \[\begin{align} \mathbb{P}\left( |\mathbf{s}_{q^\star}'| \ge \frac{\Delta}{2} \right) \le \frac{4c}{\Delta^2} \frac{\left\| \mathbf{A}\mathbf{B}^\top \right\|_F^2}{b} \end{align}\] The above inequality gives an error bound for each bit in the error-correcting code. Thus for a length \(l\) code, the expected number of wrong bits is: \[\begin{align} \mathbb{E}\left[number of wrong bits \right] = \sum_{r=0}^{2l-1} \mathbb{P}\left(the r^{\mathtt{th}} bit is wrong\right) \le \frac{4lc}{\Delta^2} \frac{\left\| \mathbf{A}\mathbf{B}^\top \right\|_F^2}{b} \end{align}\] By using an expander code, we can tolerate a constant fraction of error \(\delta\) which is independent of message length \(\log p\), with a code length \(l = \mathcal{O}{(\log p)}\) [33]. By Markov’s inequality, and combining with the probability bound on \(h\), \[\begin{align} \mathbb{P}\left( (i^\star, j^\star)not recovered \right) \le \mathbb{P}\left(more than \delta l wrong bits\right) \le \frac{4c}{\Delta^2} \frac{\left\| \mathbf{A}\mathbf{B}^\top \right\|_F^2}{ b\delta} + \frac{1}{c} \end{align}\] Optimizing over the constant \(c\) (by setting \(c=\frac{\Delta \sqrt{b\delta}}{2 \left\| \mathbf{A}\mathbf{B}^\top \right\|_F}\)), we have \[\begin{align} \mathbb{P}\left( (i^\star, j^\star)not recovered \right) \le \frac{4}{\Delta} \frac{\left\| \mathbf{A}\mathbf{B}^\top \right\|_F}{ \sqrt{b\delta }} \end{align}\] By choosing \(b\ge \frac{144\left\| \mathbf{A}\mathbf{B}^\top \right\|_F^2}{\Delta^2 \delta}\), we have \[\begin{align} \mathbb{P}\left( (i^\star, j^\star)not recovered \right) \le \frac{1}{3}. \end{align}\] For simplicity, we take \(\delta = {1\over 3}\). Combining the assumption that \(\left\| \mathbf{A}\mathbf{B}^\top \right\|_F= \left\| \nabla f_{\mathcal{B}_i}(\mathbf{\Theta}) \right\|_F\). Taking \(\Delta \ge {\left\| \nabla f_{\mathcal{B}}(\mathbf{\Theta}) \right\|_F}/\sqrt{{2k}}\), which implies \(b\ge{432\left\| \nabla f_{\mathcal{B}_i}(\mathbf{\Theta}) \right\|_F^2\over \Delta^2}\) will give a constant probability to successfully recover \((i^\star, j^\star)\).

Step III: Union bound over all large entries. Repeat the count sketch and sub-linear extraction for \(d\) times and take the \((i,j)\) pair that are recovered more than \(d/2\) times, we have that \[\begin{align} \mathbb{P}\left( (i^\star, j^\star)not recovered for more than d/2 times\right) \le \exp\left( -\frac{d}{48}\right). \end{align}\] Since the events of recovering different \((i,j)\in \Psi\) are not independent (because of the dependency induced by \(h\) functions), we use union bound over all the elements in \(\Psi\). Thus we have \[\begin{align} \mathbb{P}\left( \Psinot recovered \right) \le |\Psi| \exp\left(-\frac{d}{48}\right) \le 2k\exp \left(-\frac{d}{48}\right) \end{align}\] By taking \(d=48\log(2ck)\), we obtain the desired constant success rate \(1-\frac{1}{c}\) for recovering \(\Psi\).

Step IV: For the overall time complexity of the Interaction Top Elements Extraction (ATEE), encoding the index will take \(\mathcal{O}(pl)\). Each compressed product step will take \(\mathcal{O}(mp+mb\log b)\) and it will be repeatedly calculated for \(2l\) times, where \(l\) is the length of the expander code. Given that expander code has a linear decoding complexity, thus the extraction step can be done with \(\mathcal{O}(bl)\). The above mentioned procedure will be repeated for \(d\) times. Putting everything together, we have the time complexity for ATEE  is \[\begin{align} \mathcal{O}\left(\underbrace{\log (ck)}_{repeat d times}\left[\underbrace{p\log(p)+b\log(p)}_{encode \& decode} + \underbrace{\log(p)\left[mp+mb\log(b)\right]}_{compressed product}\right] \right) \end{align}\] which achieves sub-quadratic time complexity. Ignoring the logarithm term, the time complexity is \(\widetilde{\mathcal{O}}(m(p+b))\), which naturally implies that the space complexity is \(\widetilde{\mathcal{O}}(m(p+b))\). ◻

Proof. By RSM, we have \[\begin{align} \left\| \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}) - \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^\star) \right\|_F \le L_{2k} \left\| \mathbf{\Theta}- \mathbf{\Theta}^\star \right\|_F,\;\forall\mathbf{\Theta}\; s.t. \left\vert \mathtt{supp}{(\mathbf{\Theta})}\cup\mathtt{supp}{(\Theta^\star)} \right\vert \le 2k \end{align}\] By triangle inequality, \[\begin{align} \left\| \nabla f_{\mathcal{B}_t} \right\|_F \le L_{2k}\left\| \mathbf{\Theta}-\mathbf{\Theta}^\star \right\|_F+\left\| \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^\star) \right\|_F \end{align}\] By the fact that \(\left\| \mathbf{\Theta} \right\|_F\le \sqrt{k}\omega\), the first term can be directly bounded by \(L_{2k}\left\| \mathbf{\Theta}- \mathbf{\Theta}^\star \right\|_F\le 2L_{2k}\sqrt{k}\omega\). For the last term we have \(\left\| \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^\star) \right\|_F\le G\). Thus we have, \[\begin{align} \left\| \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}) \right\|_F\le 2L_{2k}\sqrt{k}\omega + G \end{align}\] ◻

Proof.  
With stochastic gradient descent, we have \(\mathbf{G}^t = \nabla f_{\mathcal{B}t}(\mathbf{\Theta}^{t-1})\) as the gradient at step \(t\). The per-round convergence can be separately analyzed for the two cases.
ATEE  succeeds: \(\Lambda \subseteq \widetilde{\Lambda}\). Before analyzing \(\mathbf{\Theta}^t\), we first construct an intermediate parameter \(\widetilde{\mathbf{\Theta}}^t\) as, \[\begin{align} \widetilde{\mathbf{\Theta}}^t = \mathcal{H}_k\left({\mathbf{\Theta}^{t-1}-\eta\mathcal{P}_{\Lambda_{2k}\cup\mathtt{supp}{(\mathbf{\Theta}^{t-1}})}}\left(\mathbf{G}_t\right)\right) = \mathcal{H}_k\left(\mathbf{\Theta}^{t-1}-\eta\mathbf{G}_t\right) \end{align}\] The second inequality directly comes from 4. This is actually the best situation we can hope for. In this situation, the approximation projection in ATEE  doesn’t affect the update. We will start with the bound on \(\left\| \widetilde{\mathbf{\Theta}}^t-\mathbf{\Theta}^\star \right\|_F^2\). \(\mathbf{\Theta}^t\) will then be compared with \(\widetilde{\mathbf{\Theta}}^t\) to obtain the error bound. We will never refer to \(\widetilde{\mathbf{\Theta}}^t\) in practice, but this construction makes the proof much clear. Consider the proxy \[\begin{align} \mathbf{Z}^t = \mathbf{\Theta}^{t-1} - \eta \mathbf{G}^t \end{align}\] Let \(\Omega = \mathtt{supp}(\mathbf{\Theta}^{t-1}) \cup \mathtt{supp}(\widetilde{\mathbf{\Theta}}^{t}) \cup \mathtt{supp}(\mathbf{\Theta}^\star)\), \[\begin{align} \label{eqt:guarantee-2} \left\| \widetilde{\mathbf{\Theta}}^t - \mathbf{\Theta}^\star \right\|_F^2 = \left\| \mathcal{H}_k\left(\mathbf{Z}^t\right) - \mathbf{\Theta}^\star \right\|_F^2 = \left\| \mathcal{H}_k\left(\mathcal{P}_{\Omega}\left(\mathbf{Z}^t\right)\right) - \mathbf{\Theta}^\star \right\|_F^2 \le \nu \left\| \mathcal{P}_{\Omega}\left(\mathbf{Z}^t\right) - \mathbf{\Theta}^\star \right\|_F^2 \end{align}\tag{3}\] Notice that \[\begin{align} & \left\| \mathcal{P}_{\Omega}\left(\mathbf{Z}^t\right) - \mathbf{\Theta}^\star \right\|_F^2 \\ = & \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star - \eta \mathcal{P}_{\Omega}(\mathbf{G}^t) \right\|_F^2 \nonumber \\ \le & \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \eta^2 \left\| \mathcal{P}_{\Omega}(\mathbf{G}^t) \right\|_F^2 - 2\eta \left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathbf{G}^t \right\rangle \label{eqt:guarantee-1} \end{align}\tag{4}\] Notice that \(\mathbb{E}[\mathbf{G}^t] = \nabla F(\mathbf{\Theta}^{t-1})\). 4 includes three terms: (i) the first term is the contraction term which will be kept, (ii) the second term is controlled by first using 3 then taking expectation, and (iii) the third term is controlled by first taking the expectation and then using the RSC property. Therefore, \[\begin{align} & \mathbb{E}_{\mathcal{B}_t}\left[ \left\| \widetilde{\mathbf{\Theta}}^t - \mathbf{\Theta}^\star \right\|_F^2 \right] \\ \le & \mathbb{E}_{\mathcal{B}_t}\left[ \nu \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \nu \eta^2 \left\| \mathcal{P}_{\Omega}(\mathbf{G}^t) \right\|_F^2 - 2\nu \eta \left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathbf{G}^t \right\rangle \right] \\ \begingroup \refstepcounter{relctr} \stackrel{\textrm{(\alph{relctr})}}{\mathstrut{\le}} \originallabel{rel:3} \endgroup & \nu \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 - 2\nu \eta \left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \nabla F\left(\mathbf{\Theta}^{t-1}\right) \right\rangle\\ & + \nu\eta^2 \left[2L_{2k}^2\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^{*} \right\|_F^2 + 2\mathbb{E}_{\mathcal{B}_t}\left[\left\| \mathcal{P}_\Omega\nabla f_{\mathcal{B}_t}\left(\mathbf{\Theta}^{*}\right) \right\|_F^2\right]\right]\\ = & \nu \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \nu\eta^2 \left[2L_{2k}^2\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^{*} \right\|_F^2 + 2\mathbb{E}_{\mathcal{B}_t}\left[\left\| \mathcal{P}_\Omega\nabla f_{\mathcal{B}_t}\left(\mathbf{\Theta}^{*}\right) \right\|_F^2\right]\right]\\ & - 2\nu \eta \left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \nabla F\left(\mathbf{\Theta}^{t-1}\right)- \nabla F\left(\mathbf{\Theta}^\star\right) \right\rangle + 2\nu \eta \left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \nabla F\left(\mathbf{\Theta}^\star\right) \right\rangle \\ \begingroup \refstepcounter{relctr} \stackrel{\textrm{(\alph{relctr})}}{\mathstrut{\le}} \originallabel{rel:4} \endgroup & \nu \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \nu\eta^2 \left[2L_{2k}^2\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^{*} \right\|_F^2 + 2\mathbb{E}_{\mathcal{B}_t}\left[\left\| \mathcal{P}_\Omega\nabla f_{\mathcal{B}_t}\left(\mathbf{\Theta}^{*}\right) \right\|_F^2\right]\right]\\ & - 2\nu \eta \alpha_{2k} \left\| \mathbf{\Theta}^{t-1}-\mathbf{\Theta}^\star \right\|_F^2 + 2\nu \eta \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F\left\| \mathcal{P}_{\Omega}\nabla F\left(\mathbf{\Theta}^\star\right) \right\|_F \\ = & \nu \left(1 - 2\eta \alpha_{2k} + 2\eta^2 L_{2k}^2 \right) \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 \\ & + 2\nu \eta \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F\left\| \mathcal{P}_{\Omega}\left(\nabla F\left(\mathbf{\Theta}^\star\right)\right) \right\|_F+ 2\nu \eta^2\mathbb{E}_{\mathcal{B}_t}\left\| \mathcal{P}_{\Omega} \left(\nabla f_{\mathcal{B}_t} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 \end{align}\] where the first inequality is due to 3 and 4 . [rel:3] plugs in the result from 3 and takes expectation over the gradient. [rel:4] uses RSC property and Cauchy-Shwartz inequality.
Suppose each coordinate of \(\mathbf{\Theta}\) is bounded by \(\omega\), we know that \(\left\| \mathbf{\Theta}^{t-1} \right\|_F \le \sqrt{k}\omega\) and \(\left\| \mathbf{\Theta}^\star \right\|_F \le \sqrt{k}\omega\), we further have \[\begin{align} \mathbb{E}_{\mathcal{B}_t}\left[ \left\| \widetilde{\mathbf{\Theta}}^t - \mathbf{\Theta}^\star \right\|_F^2 \right] \le &\nu \left(1 - 2\eta \alpha_{2k} + 2\eta^2 L_{2k}^2 \right) \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 \\ &+ 4\nu \eta \sqrt{k}\omega\left\| \mathcal{P}_{\Omega}\left(\nabla F\left(\mathbf{\Theta}^\star\right)\right) \right\|_F+ 2\nu \eta^2\mathbb{E}_{\mathcal{B}_t}\left\| \mathcal{P}_{\Omega} \left(\nabla f_{\mathcal{B}_t} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 \end{align}\] where the second line in the statistical error in SGD. With the definition of \(\kappa_1, \sigma_{GD}^2\), \[\begin{align} \mathbb{E}_{\mathcal{B}_t}\left[ \left\| \widetilde{\mathbf{\Theta}}^t - \mathbf{\Theta}^\star \right\|_F^2 \right] \le \kappa_1 \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \sigma_{GD}^2 \end{align}\] Now we turn to \(\mathbf{\Theta}^t\) which is given by \[\begin{align} \mathbf{\Theta}^t = \mathcal{H}_k\left({\mathbf{\Theta}^{t-1}-\eta\mathcal{P}_{\widetilde{\Lambda}\cup\mathtt{supp}{(\mathbf{\Theta}^{t-1}})}}\left(\mathbf{G}_t\right)\right) \end{align}\] It is very similar to \(\widetilde{\mathbf{\Theta}}^t\), except that \(\Lambda_{2k}\) is replaced by \(\widetilde{\Lambda}\), which is the support we actually obtain.
By definition, we have either \(\Lambda_\Delta \subseteq \Lambda_{2k}\) or \(\Lambda_{2k} \subseteq \Lambda_{\Delta}\). Recall that \(\Lambda = \Lambda_{2k}\cap\Lambda_\Delta\) and in this case where ATEE  recovers \(\Lambda\), we have \(\Lambda \subseteq \widetilde{\Lambda}\). Thus it is either \(\Lambda_{2k}\subseteq\widetilde{\Lambda}\) or \(\Lambda_{\Delta}\subseteq\widetilde{\Lambda}\).

1. \(\Lambda_{2k}\subseteq\widetilde{\Lambda}\). In this case, simply applying corollary 4 with \(G = \mathcal{P}_{\widetilde{\Lambda}\cup\mathtt{supp}{(\mathbf{\Theta}^{t-1}})}\left(\mathbf{G}_t\right)\), we have \[\begin{align} \mathbf{\Theta}^t = \mathcal{H}_k\left({\mathbf{\Theta}^{t-1}-\eta\mathcal{P}_{\widetilde{\Lambda}\cup\mathtt{supp}{(\mathbf{\Theta}^{t-1}})}}\left(\mathbf{G}_t\right)\right) = \mathcal{H}_k\left({\mathbf{\Theta}^{t-1}-\eta\mathcal{P}_{\Lambda_{2k}\cup\mathtt{supp}{(\mathbf{\Theta}^{t-1}})}}\left(\mathbf{G}_t\right)\right)=\widetilde{\mathbf{\Theta}}^t \end{align}\] Also, by \(\Lambda_{2k}\subseteq\Lambda_{\Delta}\), we know that \(k_{\Delta}=|\Lambda_{2k}\backslash\Lambda_{\Delta}|=0\), which indicates \(\sigma_{\Delta|GD}^2=0\).

2. \(\Lambda_{\Delta}\subseteq\widetilde{\Lambda}\). Here we can apply 5 and have, \[\begin{align} \|\mathbf{\Theta}^t - \widetilde{\mathbf{\Theta}}^t\|_F\le 2\eta\Delta\sqrt{k_\Delta},~~~ \|\mathbf{\Theta}^t - \widetilde{\mathbf{\Theta}}^t\|_F^2\le 2\eta^2\Delta^2{k_\Delta} \end{align}\] Thus, we can bound the error \(\mathbb{E}_{\mathcal{B}_t}\left[\left\| \mathbf{\Theta}^t-\mathbf{\Theta}^\star \right\|_F^2\right]\) as, \[\begin{align} \mathbb{E}_{\mathcal{B}_t}\left[\left\| \mathbf{\Theta}^t-\mathbf{\Theta}^\star \right\|_F^2\right] &= \mathbb{E}_{\mathcal{B}_t}\left[\left\| \widetilde{\mathbf{\Theta}}^t-\mathbf{\Theta}^\star \right\|_F^2\right] + 2\mathbb{E}_{\mathcal{B}_t}\left[\left\langle \widetilde{\mathbf{\Theta}}^t-\mathbf{\Theta}^\star, \mathbf{\Theta}^t-\widetilde{\mathbf{\Theta}}^t \right\rangle \right] + \mathbb{E}_{\mathcal{B}_t}\left[\|\mathbf{\Theta}^t - \widetilde{\mathbf{\Theta}}^t\|_F^2\right]\\ & \le \mathbb{E}_{\mathcal{B}_t}\left[\left\| \widetilde{\mathbf{\Theta}}^t-\mathbf{\Theta}^\star \right\|_F^2\right] + 4\sqrt{k_\Delta}\eta \sqrt{k}\omega\Delta + 2k_\Delta\eta^2\Delta^2 \\ & = \mathbb{E}_{\mathcal{B}_t}\left[\left\| \widetilde{\mathbf{\Theta}}^t-\mathbf{\Theta}^\star \right\|_F^2\right] + \sigma^2_{\Delta|GD} \end{align}\]

Combining the two cases above, we have the desired convergence rate for \(\Lambda \subseteq \widetilde{\Lambda}\).

ATEE  fails: \(\Lambda \not\subset \widetilde{\Lambda}\). This is the worst case when support recovery completely fails and we have no control over \(\widetilde{\Lambda}\). The update in this case is \[\begin{align} \mathbf{\Theta}^t = \mathcal{H}_k \left( \widetilde{\mathbf{Z}}^t \right), ~~{\mathbf{Z}}^t = \mathbf{\Theta}^{t-1} - \eta\left[\mathbf{G}^t - \mathcal{P}_{\widetilde{\Lambda}^C\backslash\mathtt{supp}(\mathbf{\Theta}^{t-1})}(\mathbf{G}^t)\right] \end{align}\] Similar as the previous case, let \(\Omega = \mathtt{supp}(\mathbf{\Theta}^{t-1}) \cup \mathtt{supp}(\mathbf{\Theta}^{t}) \cup \mathtt{supp}(\mathbf{\Theta}^\star)\), we have \[\begin{align} \left\| \mathbf{\Theta}^t - \mathbf{\Theta}^\star \right\|_F^2 \le \nu \left\| \mathcal{P}_{\Omega}\left({\mathbf{Z}}^t \right) - \mathbf{\Theta}^\star \right\|_F^2 \end{align}\] and \[\begin{align} \left\| \mathcal{P}_{\Omega}\left( {\mathbf{Z}}^t \right) - \mathbf{\Theta}^\star \right\|_F^2 \le & \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \eta^2\left\| \mathcal{P}_{\Omega}\left(\mathbf{G}^t- \mathcal{P}_{\widetilde{\Lambda}^C\backslash\mathtt{supp}(\mathbf{\Theta}^{t-1})}(\mathbf{G}^t)\right) \right\|_F^2 \\ & - 2\eta\left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathcal{P}_{\Omega}(\mathbf{G}^t) \right\rangle\\ & + 2\eta\left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathcal{P}_{\Omega}\mathcal{P}_{\widetilde{\Lambda}\backslash\mathtt{supp}(\mathbf{\Theta}^{t-1})}(\mathbf{G}^t) \right\rangle\\ \le & \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \eta^2\left\| \mathcal{P}_{\Omega}\left(\mathbf{G}^t\right) \right\|_F^2- 2\eta\left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathcal{P}_{\Omega}(\mathbf{G}^t) \right\rangle\\ & + 2\eta\left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathcal{P}_{\Omega}\mathcal{P}_{\widetilde{\Lambda}\backslash\mathtt{supp}(\mathbf{\Theta}^{t-1})}(\mathbf{G}^t) \right\rangle \end{align}\] The bound for the first three terms are same as the bound for 4 . It left to bound the last term, \[\begin{align} &\left\langle \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star, \mathcal{P}_{\Omega}\mathcal{P}_{\widetilde{\Lambda}\backslash\mathtt{supp}(\mathbf{\Theta}^{t-1})}(\mathbf{G}^t) \right\rangle \\ \le &\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F \left\| \mathcal{P}_{\Omega}\mathcal{P}_{\widetilde{\Lambda}\backslash\mathtt{supp}(\mathbf{\Theta}^{t-1})}\left(\nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{t-1})\right) \right\|_F \\ \le &\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F \left\| \mathcal{P}_{\Omega}\left(\nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{t-1})- \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{*})\right) \right\|_F + \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F \left\| \mathcal{P}_{\Omega}\left(\nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{*})\right) \right\|_F\\ \le &\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F \left\| \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{t-1})- \nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{*}) \right\|_F + \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F \left\| \mathcal{P}_{\Omega}\left(\nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{*})\right) \right\|_F\\ \le &L_{2k}\left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + 2\sqrt{k}\omega\left\| \mathcal{P}_{\Omega}\left(\nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^{*})\right) \right\|_F \end{align}\] Putting the bounds together, we have \[\begin{align} \mathbb{E}_{\mathcal{B}_t}\left[ \left\| \mathbf{\Theta}^t - \mathbf{\Theta}^\star \right\|_F^2 \right] \le & \nu\left(1-2\eta\alpha_{2k}+ 2\eta^2 L_{2k}^2 + 2\eta L_{2k}\right)\left\| \mathbf{\Theta}^{t-1}-\Theta^\star \right\|_F^2 \\ & + 4\nu \eta \sqrt{k}\omega\left\| \mathcal{P}_{\Omega}\left(\nabla F\left(\mathbf{\Theta}^\star\right)\right) \right\|_F + 2\nu\eta^2\mathbb{E}_{\mathcal{B}_t}\left\| \mathcal{P}_{\Omega} \left(\nabla f_{\mathcal{B}_t} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 \\ & + 4\nu\eta\sqrt{k}\omega\mathbb{E}_{\mathcal{B}_{t}}\left\| \mathcal{P}_{\Omega} \left(\nabla f_{\mathcal{B}_t} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F \end{align}\] Define \(\sigma_{Fail|GD}^2=\max_{|\Omega|\le2k+K}\left[4\nu \eta\sqrt{k}\omega\mathbb{E}_{\mathcal{B}_t}\left[\left\| \mathcal{P}_{\Omega}\left(\nabla f_{\mathcal{B}_t}\left(\mathbf{\Theta}^\star\right)\right) \right\|_F\right]\right]\) Then, \[\begin{align} \mathbb{E}_{\mathcal{B}_t}\left[ \left\| \mathbf{\Theta}^t - \mathbf{\Theta}^\star \right\|_F^2 \right] \le \nu \left(1 - 2\eta \alpha_{2k} + 2\eta^2 L_{2k}^2 + 2\eta L_{2k}\right) \left\| \mathbf{\Theta}^{t-1} - \mathbf{\Theta}^\star \right\|_F^2 + \sigma_{GD}^2 + \sigma_{Fail|GD}^2 \end{align}\] ◻

Proof. With the definition of \(\sigma_1^2, \sigma_2^2, \kappa_1, \kappa_2\), the per-round convergence result of 2 can be rewritten as:

1. Success Case: \[\begin{align} \mathbb{E}_{B_{t+1}}\left[\left\| \mathbf{\Theta}^{t+1}-\mathbf{\Theta}^\star \right\|_F^2+{\sigma_1^2\over \kappa_1-1}\right]\le \kappa_1\mathbb{E}_{B_{t}}\left[\left\| \mathbf{\Theta}^t - \mathbf{\Theta}^\star \right\|_F^2+{\sigma_1^2\over \kappa_1-1}\right] \end{align}\]

2. Failure Case: \[\begin{align} \mathbb{E}_{B_{t+1}}\left[\left\| \mathbf{\Theta}^{t+1}-\mathbf{\Theta}^\star \right\|_F^2+{\sigma_1^2\over \kappa_1-1}\right]\le \kappa_2\mathbb{E}_{B_{t}}\left[\left\| \mathbf{\Theta}^t - \mathbf{\Theta}^\star \right\|_F^2+{\sigma_1^2\over \kappa_1-1}\right] + \left(\kappa_2-1\right)\left({\sigma_2^2\over \kappa_2-1}-{\sigma_1^2\over\kappa_1-1}\right) \end{align}\]

For each iteration, the count sketch succeeds with probability \(1-{1\over c}\). Denote the success indicator at iteration \(t\) as \(\phi_t\), and let \(\Phi_t = \left\{\phi_0,\phi_1, ..., \phi_t\right\}\), we can combine those two cases and obtain, \[\begin{align} \mathbb{E}_{B_{t+1}, \Phi_{t+1}}\left[\left\| \mathbf{\Theta}^{t+1}-\mathbf{\Theta}^\star \right\|_F^2+{\sigma_1^2\over \kappa_1-1}\right]\le &\left(\kappa_1 + {1\over c}\left(\kappa_1-\kappa_2\right)\right)\mathbb{E}_{B_{t}, \Phi_{t}}\left[\left\| \mathbf{\Theta}^t - \mathbf{\Theta}^\star \right\|_F^2+{\sigma_1^2\over \kappa_1-1}\right] \\ &+ {1\over c}\left(\kappa_2-1\right)\left({\sigma_2^2\over \kappa_2-1}-{\sigma_1^2\over\kappa_1-1}\right) \end{align}\] With a telescope sum, we have the desired error bound. ◻

Proof. We first vectorize the quadratic features. For an arbitrary data point \({\mathbf{x}, y}\), we know that \(\mathbf{x}\in \mathbb{R}^{p}\), where the first \(p-1\) coordinates independently come from a zero mean, bounded distribution and the last coordinate is a constant 1. Denote the \(i\)-th coordinate of \(\mathbf{x}\) as \(x_i\), we first vectorize the quadratic features, define \[\begin{align} \mathbf{v}= [x_1x_2, x_1x_3, ..., x_{p-1}x_p]^\top \end{align}\] Here, for the quadratic terms, we only consider the interaction terms with no squared terms like \(x_i^2\). Given that there will only be \(p\) different squared terms, one can regress with the squared terms first, and the residual model will have no dependency on the squared terms. Replace \(x_p\) with 1, we have \[\begin{align} \mathbf{v}= [x_1x_2, x_1x_3, ..., x_{p-2}x_{p-1}, x_1, ..., x_{p-1}]^\top \end{align}\] Given that \(x_1, ..., x_{p-1}\) are all i.i.d. and zero mean, after normalizing the variance of \(x_i\), it is not hard to verify that \[\begin{align} \mathbb{E}[\mathbf{v}\mathbf{v}^\top] = \mathbf{I} \end{align}\] Given that \(\alpha, L\) are the smallest and largest eigenvalue of \(\mathbb{E}[\mathbf{v}\mathbf{v}^\top]\), asymptotically, we have the strong convexity and smoothness parameter \(\alpha = L = 1\), which directly implies that the restricted version \(\alpha_k = L_k = 1\). Thus the deterministic requirement can be easily satisfied with infinite sample. Now we turn to the minimum sample we need to have the desired \(\alpha_k, L_k\).

To show the \(k\)-restricted strong convexity and smoothness, we will first focus on an arbitrary \(k\) sub-matrix of \(\mathbb{E}[\mathbf{v}\mathbf{v}^\top]\) and show the concentration. Then the desired claim will follow by applying a union bound over all \(k\) sub-matrices.

Denote a set of indices \({\mathcal{S}}\subseteq \{1, ..., |\mathbf{v}|\}\), where \(|{\mathcal{S}}| = k\). Define the corresponding sub-vector drawn from \(\mathbf{v}\) as \(\mathbf{z}= \mathbf{v}_{\mathcal{S}}\). Define the restricted expected Hessian matrix as \(\mathbf{H}= \mathbb{E}[\mathbf{z}\mathbf{z}^\top]\), let the finite sample Hessian matrix as \(\widehat\mathbf{H}= \frac{1}{m}\sum_{i=1}^m\mathbf{z}_i\mathbf{z}_i^\top\). Denote the difference as \[\begin{align} \mathbf{D}_i &= \frac{1}{m}\mathbf{z}_i\mathbf{z}_i^\top - \frac{1}{m}\mathbb{E}[\mathbf{z}\mathbf{z}^\top] \\ \mathbf{D}&= \sum_{i=1}^m\mathbf{D}_i = \frac{1}{m}\sum_{i=1}^m\mathbf{z}_i\mathbf{z}_i^\top - \mathbb{E}[\mathbf{z}\mathbf{z}^\top] = \widehat\mathbf{H}- \mathbf{H} \end{align}\]

Given that \(\mathbf{H}= \mathbf{I}\), we can show the concentration of \(\alpha_k, L_k\) as long as we can control \(\mathbf{D}\). Given that \(\mathbf{v}\) is bounded, we know that \(\mathbf{v}\) is sub-gaussian. Thus, bounding \(\|\mathbf{D}\|\) is equivalent to showing concentration of the covariance matrix estimation of sub-gaussian random vectors. Using the Corollary 5.50 in [34], we have that with \(m \ge C(t/\epsilon)^2k\), where \(C\) depends only on the sub-gaussian norm \(\|\mathbf{v}\|_{\psi_2}\). It’s not hard to verify that \(\|\mathbf{v}\|_{\psi_2} \le B\). Then we have that \[\begin{align} \mathbb{P}(\|\mathbf{D}\| \ge \epsilon) \le 2\exp(-t^2k) \end{align}\]

Thus we obtain the bound for one particular \(k\)-sub-matrix. Taking an union bound over all \(k\)-sub-matrices, we have that \[\begin{align} \mathbb{P}(L_k \ge 1+\epsilon) &\le {|\mathbf{v}|\choose k}\mathbb{P}(\|\mathbf{D}\|\ge \epsilon)\\ & \le \exp\left(k\log(2ep^2/k)-t^2k\right) \end{align}\]

By choosing \(t^2 \ge \log(p)\), which implies that \(m \gtrsim B k\log(p)/\epsilon^2\), we have \(L_k\le 1+\epsilon\) with high probability. With a symmetric argument, we know that under same condition, we have \(\alpha_k \ge 1-\epsilon\) with high probability. ◻

Proof. With 3 showing the linear convergence, we know that the per iteration complexity dominates the overall complexity of IntHT. By 1 and 1, we show setting \(b\) to \(\mathcal{O}(k)\) is sufficient for ATEE to recover the support. 4 provides that the minimum batch size \(m\) required for quadratic regression is \(\mathcal{O}({k\log p})\). Combining those results, we conclude that the complexity of IntHT is \(\widetilde{\mathcal{O}}(k(k+p))\). In the regime when \(k\) is \(\mathcal{O}(p^\gamma)\) for \(\gamma < 1\), IntHT achieves sub-quadratic complexity. ◻

Proof. Similar to the ATEE  succeeds case, define \[\begin{align} \widetilde{\mathbf{\Theta}}^i_{j+1} = \mathcal{H}_k\left({\mathbf{\Theta}^{i}_{j}-\eta\mathcal{P}_{\Lambda_{2k}\cup\mathtt{supp}{(\mathbf{\Theta}^{i}_{j}})}}\left(\mathbf{G}^i_{j}\right)\right) = \mathcal{H}_k\left(\mathbf{\Theta}^i_{j}-\eta\mathbf{G}^i_{j}\right) \end{align}\] The second equality is given by 4. By applying 5, we can also have \[\begin{align} \|\mathbf{\Theta}^i_{j+1} - \widetilde{\mathbf{\Theta}}^i_{j+1}\|_F \le 2\eta\Delta\sqrt{k_\Delta},~~~ \|\mathbf{\Theta}^i_{j+1} - \widetilde{\mathbf{\Theta}}^i_{j+1}\|_F^2 \le 2\eta^2\Delta^2{k_\Delta} \end{align}\] which further implies \[\begin{align} \left\| \mathbf{\Theta}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2 & =\left\| \mathbf{\Theta}^i_{j+1}-\widetilde{\mathbf{\Theta}}^i_{j+1} \right\|_F^2+\left\| \widetilde{\mathbf{\Theta}}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2+2\left\langle \mathbf{\Theta}^i_{j+1}-\widetilde{\mathbf{\Theta}}^i_{j+1}, \widetilde{\mathbf{\Theta}}^i_{j+1}-\mathbf{\Theta}^\star \right\rangle\\ & \le \left\| \widetilde{\mathbf{\Theta}}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2 + 4\sqrt{k_\Delta}\eta \sqrt{k}\omega\Delta + 2k_\Delta\eta^2\Delta^2 \\ & = \left\| \widetilde{\mathbf{\Theta}}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2 + \sigma^2_{\Delta|SVRG} \end{align}\] The last equality defines \(\sigma'^2_{\Delta|SVRG}\). To bound \(\left\| \widetilde{\mathbf{\Theta}}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2\), the high level idea is similar to the proof of Theorem 10 in [19]. We first define, \[\begin{align} \mathbf{Z}^i_{j+1} = \mathbf{\Theta}^{i}_j - \eta \mathbf{G}^i_j \end{align}\] Let \(\Omega = \mathtt{supp}(\mathbf{\Theta}^i_{j}) \cup \mathtt{supp}(\widetilde{\mathbf{\Theta}}^{i}_{j+1}) \cup \mathtt{supp}(\mathbf{\Theta}^\star)\), \[\begin{align} \left\| \widetilde{\mathbf{\Theta}}^i_{j+1} - \mathbf{\Theta}^\star \right\|_F^2 = \left\| \mathcal{H}_k\left(\mathbf{Z}^i_{j+1}\right) - \mathbf{\Theta}^\star \right\|_F^2 = \left\| \mathcal{H}_k\left(\mathcal{P}_{\Omega}\left(\mathbf{Z}^i_{j+1}\right)\right) - \mathbf{\Theta}^\star \right\|_F^2 \le \nu \left\| \mathcal{P}_{\Omega}\left(\mathbf{Z}^i_{j+1}\right) - \mathbf{\Theta}^\star \right\|_F^2 \end{align}\] where the last inequality follows from 2. Thus we have \[\begin{align} & \mathbb{E}_{b_j}\left[ \left\| \widetilde{\mathbf{\Theta}}^i_{j+1} - \mathbf{\Theta}^\star \right\|_F^2 \right] \\ \le & \mathbb{E}_{b_j}\left[ \nu \left\| \mathcal{P}_{\Omega}\left(\mathbf{Z}^i_{j+1}\right) - \mathbf{\Theta}^\star \right\|_F^2 \right] \\ = & \mathbb{E}_{b_j}\left[ \nu \left\| \mathbf{\Theta}^i_{j} - \mathbf{\Theta}^\star \right\|_F^2 + \nu \eta^2 \left\| \mathcal{P}_{\Omega}(\mathbf{G}^i_{j}) \right\|_F^2 - 2\nu \eta \left\langle \mathbf{\Theta}^i_{j} - \mathbf{\Theta}^\star, \mathbf{G}^i_{j} \right\rangle \right] \end{align}\] The second term can be bounded by using 3 and we can take expectation directly on the third term, since \(\mathbb{E}_{b_j}[\mathbf{G}^i_{j}]=\nabla F(\mathbf{\Theta}^i_j)\). For brevity, denote \(L=L_{|\Omega|}\).We then have, \[\begin{align} & \mathbb{E}_{b_j}\left[ \left\| \widetilde{\mathbf{\Theta}}^i_{j+1} - \mathbf{\Theta}^\star \right\|_F^2 \right] \\ \le & \nu \left\| \mathbf{\Theta}^i_{j} - \mathbf{\Theta}^\star \right\|_F^2 + 4\nu\eta^2L_{2k}\left[F(\mathbf{\Theta}^i_j)-F(\mathbf{\Theta}^\star) + F(\mathbf{\Theta}^i_0) - F(\mathbf{\Theta}^\star)\right] - 2\nu \eta \left\langle \mathbf{\Theta}^i_{j} - \mathbf{\Theta}^\star, \nabla F\left(\mathbf{\Theta}^i_{j}\right) \right\rangle \\ & - 4\nu \eta^2 L_{2k} \left\langle \nabla F(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_j+\mathbf{\Theta}^i_0-2\mathbf{\Theta}^\star \right\rangle + 4\nu \eta^2\left\| \mathcal{P}_{\Omega} \left(\nabla F \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2\\ \le & \nu(1-\eta\alpha_{2k}) \left\| \mathbf{\Theta}^i_{j} - \mathbf{\Theta}^\star \right\|_F^2 - 2\nu\eta(1-2\eta L_{2k})\left[F(\mathbf{\Theta}^i_j)-F(\mathbf{\Theta}^\star)\right] + 4\nu\eta^2L_{2k}\left[F(\mathbf{\Theta}^i_0) - F(\mathbf{\Theta}^\star)\right] \\ & + 4\nu \eta^2 L_{2k} \left\| \nabla F(\mathbf{\Theta}^\star) \right\|_F\left\| \mathbf{\Theta}^i_j+\mathbf{\Theta}^i_0-2\mathbf{\Theta}^\star \right\|_F + 4\nu \eta^2\left\| \mathcal{P}_{\Omega} \left(\nabla F \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 \end{align}\] where the first inequality plugs in the result from 3 and takes expectation of \(\mathbf{G}^i_j\). The second inequality uses RSC property and Cauchy-Shwartz inequality. For brevity, define \(\sigma' = \max_{|\Omega|=3k+K}\left\| \mathcal{P}_{\Omega}F(\mathbf{\Theta}^*) \right\|_F\), we have that \[\begin{align} \mathbb{E}_{b_j}\left[\left\| \widetilde{\mathbf{\Theta}}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2\right] \le & \nu(1-\eta\alpha_{2k})\left\| \mathbf{\Theta}^i_{j}-\mathbf{\Theta}^\star \right\|_F^2-2\nu\eta(1-2\eta L_{2k})\left[F(\mathbf{\Theta}^i_{j})-F_(\mathbf{\Theta}^\star))\right]\\ & + 4\nu\eta^2L_{2k}\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right] + 4\nu\eta \sigma'(4L_{2k}\sqrt{k}\omega+\sigma') \end{align}\] Thus for \(\mathbb{E}_{b_j}\left[\left\| \mathbf{\Theta}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2\right]\), we have \[\begin{align} \mathbb{E}_{b_j}\left[\left\| \mathbf{\Theta}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2\right] \le & \nu(1-\eta\alpha_{2k})\left\| \mathbf{\Theta}^i_{j}-\mathbf{\Theta}^\star \right\|_F^2-2\nu\eta(1-2\eta L_{2k})\left[F(\mathbf{\Theta}^i_{j})-F_(\mathbf{\Theta}^\star))\right]\\ & + 4\nu\eta^2L_{2k}\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right] + 4\nu\eta \sigma'(4L_{2k}\sqrt{k}\omega+\sigma') + \sigma^2_{\Delta|SVRG} \end{align}\] By a telescope sum, define \(B_t=\left\{b_1, b_2,...,b_t\right\}\) \[\begin{align} \mathbb{E}_{B_t}\left[\left\| \mathbf{\Theta}^{i}_t-\mathbf{\Theta}^\star \right\|_F^2\right] \le & [\nu(1-\eta\alpha_{2k})-1]\sum_{j=0}^{t-1}\left\| \mathbf{\Theta}^i_{j+1}-\mathbf{\Theta}^\star \right\|_F^2 + \left\| \mathbf{\Theta}^i_0-\mathbf{\Theta}^\star \right\|_F\\ & - 2\nu\eta(1-2\eta L_{2k})\sum_{j=0}^{t-1}\left[F(\mathbf{\Theta}^i_{j+1})-F(\mathbf{\Theta}^\star))\right]\\ & + 4\nu\eta^2L_{2k}m\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right] + 4\nu\eta \sigma'(4L_{2k}\sqrt{k}\omega+\sigma')m + m\sigma^2_{\Delta|SVRG} \\ = & [\nu(1-\eta\alpha_{2k})-1]m\mathbb{E}_{B_t, j'}\left\| \mathbf{\Theta}^{i+1}_0-\mathbf{\Theta}^\star \right\|_F^2 + \left\| \mathbf{\Theta}^i_0-\mathbf{\Theta}^\star \right\|_F\\ & - 2\nu\eta(1-2\eta L_{2k})\mathbb{E}_{B_t, j'}\left[F(\mathbf{\Theta}^{i+1}_0)-F(\mathbf{\Theta}^\star))\right]\\ & + 4\nu\eta^2L_{2k}m\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right] + 4\nu\eta \sigma'(4L_{2k}\sqrt{k}\omega+\sigma')m + m\sigma^2_{\Delta|SVRG} \end{align}\] By using RSC, we have \({2\over\alpha_{2k}}\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)-\left\langle \nabla F(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_0-\mathbf{\Theta}^\star \right\rangle \right] \ge \left\| \mathbf{\Theta}^i_0-\mathbf{\Theta}^\star \right\|_F^2\), thus \[\begin{align} \mathbb{E}_{B_t}\left[\left\| \mathbf{\Theta}^{i}_t-\mathbf{\Theta}^\star \right\|_F^2\right] \le & [\nu(1-\eta\alpha_{2k})-1]m\mathbb{E}_{B_t, j'}\left\| \mathbf{\Theta}^{i+1}_0-\mathbf{\Theta}^\star \right\|_F^2 \\ & - 2\nu\eta(1-2\eta L_{2k})\mathbb{E}_{B_t, j'}\left[F(\mathbf{\Theta}^{i+1}_0)-F(\mathbf{\Theta}^\star))\right]\\ & + \left({2\over\alpha_{2k}}+4\nu\eta^2L_{2k}m\right)\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right] \\ & + 4\nu\eta \sigma'(4L_{2k}\sqrt{k}\omega+\sigma')m + {2\over \alpha_{2k}}\sqrt{k}\omega\sigma'+ m\sigma^2_{\Delta|SVRG} \end{align}\] By assumption, we have \([\nu(1-\eta\alpha_{2k})-1] \le 0\). For simplicity, define \[\begin{align} \sigma_{SVRG} = {4\nu\eta \sigma'(4L_{2k}\sqrt{k}\omega+\sigma')m + {2\over \alpha_{2k}}\sqrt{k}\omega\sigma'+ m\sigma^2_{\Delta|SVRG}\over 2 \nu\eta(1-2\eta L_{2k})m} \end{align}\] Choosing \(\eta<{1\over2L_{2k}}\), we have \[\begin{align} \mathbb{E}_{B_t}\left[F(\mathbf{\Theta}^{i+1}_0)-F(\mathbf{\Theta}^\star))\right] \le \left({1\over\alpha_{2k}\nu\eta(1-2\eta L_{2k})m}+{2\eta L_{2k}\over1-2\eta L_{2k}}\right)\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right] + \sigma_{SVRG} \end{align}\] Typically \(m\) is quite large, thus for the condition of convergence, we require that \[\begin{align} {2\eta L_{2k}\over 1-2\eta L_{2k}} < 1\Rightarrow \eta < {1\over 4L_{2k}} \end{align}\] Define, \[\begin{align} \kappa_{SVRG} &= {1\over\alpha_{2k}\nu\eta(1-2\eta L_{2k})m}+{2\eta L_{2k}\over1-2\eta L_{2k}} \end{align}\] We have the linear convergence given by \[\begin{align} \mathbb{E}_{B_t}\left[F(\mathbf{\Theta}^{i+1}_0)-F(\mathbf{\Theta}^\star))\right] \le \kappa_{SVRG}\left[F(\mathbf{\Theta}^{i}_0)-F(\mathbf{\Theta}^\star)\right]+\sigma_{SVRG} \end{align}\] ◻

Proof. We give the proof here for completeness. Also, the proof here is much concise than the original proof in [19] and a related result shown in [18]. \[\begin{align} \left\| \mathcal{H}_k(\mathbf{B}) - \mathbf{\Theta} \right\|_F^2 = & \underbrace{\left\| \mathcal{P}_{\mathtt{supp}(\mathcal{H}_k(\mathbf{B})) \backslash \mathtt{supp}(\mathbf{\Theta})} \left( \mathbf{B}\right) \right\|_F^2}_{\left\| \mathbf{B}_1 \right\|_F^2} + \underbrace{ \left\| \mathcal{P}_{\mathtt{supp}(\mathcal{H}_k(\mathbf{B})) \cap \mathtt{supp}(\mathbf{\Theta})} \left(\mathbf{B}- \mathbf{\Theta}\right) \right\|_F^2 }_{\left\| \mathbf{B}_2 - \mathbf{\Theta}_2 \right\|_F^2}\\ & + \underbrace{ \left\| \mathcal{P}_{ \mathtt{supp}^c(\mathcal{H}_k(\mathbf{B})) \cap \mathtt{supp}(\mathbf{\Theta}) }\left(\mathbf{\Theta}\right) \right\|_F^2 }_{\left\| \mathbf{\Theta}_3 \right\|_F^2} \end{align}\] On the other hand, \[\begin{align} \left\| \mathbf{B}- \mathbf{\Theta} \right\|_F^2 = & \underbrace{ \left\| \mathcal{P}_{\mathtt{supp}(\mathcal{H}_k(\mathbf{B})) \backslash \mathtt{supp}(\mathbf{\Theta})} \left( \mathbf{B}\right) \right\|_F^2}_{\left\| \mathbf{B}_1 \right\|_F^2} + \underbrace{ \left\| \mathcal{P}_{\mathtt{supp}(\mathcal{H}_k(\mathbf{B})) \cap \mathtt{supp}(\mathbf{\Theta})} \left(\mathbf{B}- \mathbf{\Theta}\right) \right\|_F^2 }_{\left\| \mathbf{B}_2 - \mathbf{\Theta}_2 \right\|_F^2}\\ & + \underbrace{\left\| \mathcal{P}_{ \mathtt{supp}^c(\mathcal{H}_k(\mathbf{B})) \cap \mathtt{supp}(\mathbf{\Theta}) }\left(\mathbf{B}- \mathbf{\Theta}\right) \right\|_F^2}_{\left\| \mathbf{B}_3 - \mathbf{\Theta}_3 \right\|_F^2} + \underbrace{\left\| \mathcal{P}_{ \mathtt{supp}^c(\mathcal{H}_k(\mathbf{B})) \backslash \mathtt{supp}(\mathbf{\Theta})}\left(\mathbf{B}\right) \right\|_F^2}_{\left\| \mathbf{B}_4 \right\|_F^2} \end{align}\] \[\begin{align} &\max_{\mathbf{B}, \mathbf{\Theta}} \frac{\left\| \mathcal{H}_k(\mathbf{B}) - \mathbf{\Theta} \right\|_F^2}{\left\| \mathbf{B}- \mathbf{\Theta} \right\|_F^2} \\ = & \max_{\mathbf{B}, \mathbf{\Theta}} \frac{ \left\| \mathbf{B}_1 \right\|_F^2 + \left\| \mathbf{B}_2 - \mathbf{\Theta}_2 \right\|_F^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 }{ \left\| \mathbf{B}_1 \right\|_F^2 + \left\| \mathbf{B}_2 - \mathbf{\Theta}_2 \right\|_F^2 + \left\| \mathbf{B}_3 - \mathbf{\Theta}_3 \right\|_F^2 + \left\| \mathbf{B}_4 \right\|_F^2} \\ \le & \max_{\mathbf{B}, \mathbf{\Theta}} \frac{ \left\| \mathbf{B}_1 \right\|_F^2 + \left\| \mathbf{B}_2 - \mathbf{\Theta}_2 \right\|_F^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 }{ \left\| \mathbf{B}_1 \right\|_F^2 + \left\| \mathbf{B}_2 - \mathbf{\Theta}_2 \right\|_F^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 + \left\| \mathbf{B}_3 \right\|_F^2 - 2\left\langle \mathbf{B}_3, \mathbf{\Theta}_3 \right\rangle} \\ \le & \max\left\{ 1, \max_{\mathbf{B}, \mathbf{\Theta}} \frac{ \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert {\mathbf{B}_{1,\min}}^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 }{ \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert {\mathbf{B}_{1,\min}}^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 + \left\| \mathbf{B}_3 \right\|_F^2 - 2\left\langle \mathbf{B}_3, \mathbf{\Theta}_3 \right\rangle} \right\} \\ \le & \max\left\{ 1, \max_{\mathbf{B}, \mathbf{\Theta}} \frac{ \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert {\mathbf{B}_{1,\min}}^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 }{ \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert {\mathbf{B}_{1,\min}}^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 + \left\vert \mathtt{supp}(\mathbf{\Theta}_3) \right\vert \mathbf{B}_{1,\min}^2 - 2\mathbf{B}_{1,\min} \left\| \mathbf{\Theta}_{3} \right\|_1 } \right\} \triangleq \gamma \end{align}\] We determine \(\gamma\) by observing \[\begin{align} & \frac{ \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert {\mathbf{B}_{1,\min}}^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 }{ \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert {\mathbf{B}_{1,\min}}^2 + \left\| \mathbf{\Theta}_3 \right\|_F^2 + \left\vert \mathtt{supp}(\mathbf{\Theta}_3) \right\vert \mathbf{B}_{1,\min}^2 - 2\mathbf{B}_{1,\min} \left\| \mathbf{\Theta}_{3} \right\|_1 } \le \gamma, ~~~~~~~~ \forall \mathbf{B}, \mathbf{\Theta}\\ \Leftrightarrow & (\gamma-1) \left\| \mathbf{\Theta}_3 \right\|_F^2 - 2\gamma \mathbf{B}_{1,\min}^2 + \left( \gamma \left\vert \mathtt{supp}(\mathbf{\Theta}_3)\right\vert + (\gamma -1) \left\vert \mathtt{supp}(\mathbf{B}_1) \right\vert \right)\mathbf{B}_{1,\min}^2 \ge 0, ~~~~~~~~ \forall \mathbf{B}, \mathbf{\Theta}\\ \Leftrightarrow & 4\gamma^2 \mathbf{B}_{1,\min}^2 \le 4(\gamma - 1) \left[ \gamma + (\gamma-1) \frac{\mathtt{supp}(\mathbf{B}_1)}{\mathtt{supp}(\mathbf{\Theta}_3)} \right] \mathbf{B}_{1,\min}^2 \\ \Leftarrow & \gamma^2 \le (\gamma - 1) \left[ \gamma + (\gamma-1) \frac{1}{\rho} \right] \\ \Leftarrow & \gamma = 1 + \frac{\rho + \sqrt{(4+\rho)\rho}}{2}, ~~~~~~~~where\rho=\frac{\min\{K, p^2-k\} }{k-K+\min\{K, p^2-k\} } \end{align}\] ◻

Proof. Define the auxiliary function \[\begin{align} \label{eqt:co-ercivity} g(\mathbf{\Xi}) := f(\mathbf{\Xi}) - \left\langle \nabla f(\mathbf{\Theta}), \mathbf{\Xi} \right\rangle \end{align}\tag{5}\] Notice that the gradient of \(g(\cdot)\) satisfies: \[\begin{align} \left\| \nabla g(\mathbf{\Xi}) - \nabla g(\mathbf{\Xi}') \right\|_F = \left\| \nabla f(\mathbf{\Xi}) - \nabla f(\mathbf{\Xi}') \right\|_F \le L_{\left\| \mathbf{\Xi}- \mathbf{\Xi}' \right\|_0} \left\| \mathbf{\Xi}- \mathbf{\Xi}' \right\|_F \end{align}\] which implies \[\begin{align} g(\mathbf{\Xi}) - g(\mathbf{\Xi}') - \left\langle \nabla g(\mathbf{\Xi}'), \mathbf{\Xi}- \mathbf{\Xi}' \right\rangle \le \frac{L_r}{2} \left\| \mathbf{\Xi}- \mathbf{\Xi}' \right\|_F^2 \end{align}\] where \(r=|\mathtt{supp}(\mathbf{\Xi}- \mathbf{\Xi}')|\). On the other hand, \[\begin{align} g(\mathbf{\Xi}) - g(\mathbf{\Theta}) = f(\mathbf{\Xi}) - f(\mathbf{\Theta}) - \left\langle \nabla f(\mathbf{\Theta}), \mathbf{\Xi}- \mathbf{\Theta} \right\rangle \ge 0 \end{align}\] as long as \(f(\cdot)\) satisfies \(|\mathtt{supp}(\mathbf{\Xi}) \cup \mathtt{supp}(\mathbf{\Theta})|\)-RC. Take \(\mathbf{\Xi}= \mathbf{\Theta}'- \frac{1}{L_{|\Omega|}} \mathcal{P}_{\Omega} \nabla g(\mathbf{\Theta}')\), \(\mathbf{\Xi}'= \mathbf{\Theta}'\), then, \[\begin{align} g(\mathbf{\Theta}) \le & g(\mathbf{\Theta}'- \frac{1}{L_{|\Omega|}} \mathcal{P}_{\Omega} \nabla g(\mathbf{\Theta}')) \\ \le & g(\mathbf{\Theta}') + \left\langle \nabla g(\mathbf{\Theta}'), - \frac{1}{L_{|\Omega|}} \mathcal{P}_{\Omega} \nabla g(\mathbf{\Theta}') \right\rangle + \frac{1}{2 L_{|\Omega|}} \left\| \mathcal{P}_{\Omega} \nabla g(\mathbf{\Theta}') \right\|_F^2 \\ = & g(\mathbf{\Theta}') - \frac{1}{2 L_{|\Omega|}} \left\| \mathcal{P}_{\Omega} \nabla g(\mathbf{\Theta}') \right\|_F^2 \end{align}\] Plug in the definition in 5 gives the result we want. ◻

Proof.  

1. SGD: \[\begin{align} & \mathbb{E}_{\mathcal{B}_t}\left\| \mathcal{P}_{\Omega}\left(\mathbf{G}^t \right) \right\|_F^2 = \mathbb{E}_{\mathcal{B}_t}\left\| \mathcal{P}_{\Omega}\left( \nabla f_{\mathcal{B}_t} \left(\mathbf{\Theta}^{t-1}\right) \right) \right\|_F^2 \\ \le & 2 \mathbb{E}_{\mathcal{B}_t} \left\| \mathcal{P}_{\Omega}\left( \nabla f_{\mathcal{B}_t}\left( \mathbf{\Theta}^{t-1}\right) - \nabla f_{\mathcal{B}_t}\left(\mathbf{\Theta}^\star\right) \right) \right\|_F^2 + 2\left\| \mathcal{P}_{\Omega} \left(\nabla f_{\mathcal{B}_t} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 \\ \le & 2L_{2k}^2\left\| \mathbf{\Theta}^{t-1}-\mathbf{\Theta}^\star \right\|_F^2+2\left\| \mathcal{P}_\Omega\left(\nabla f_{\mathcal{B}_t}(\mathbf{\Theta}^\star)\right) \right\|_F^2 \end{align}\] The first inequality is by algebra, the second inequality holds by RSM.

2. SVRG: \[\begin{align} \left\| \mathcal{P}_{\Omega}(\mathbf{G}^i_j) \right\|_F^2 =& \left\| \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_j\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_0\right)+\nabla F \left(\mathbf{\Theta}^{i}_0\right)\right) \right\|_F^2 \\ \le & 2 \left\| \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_j\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 \\ & + 2 \left\| \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_0\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^\star\right)-\nabla F \left(\mathbf{\Theta}^{i}_0\right)\right) \right\|_F^2 \end{align}\] Expand the later square, we have \[\begin{align} \left\| \mathcal{P}_{\Omega}(\mathbf{G}^i_j) \right\|_F^2 \le & 2 \left\| \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_j\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2 + 2 \left\| \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_0\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^\star\right)\right) \right\|_F^2\\ & + 2 \left\| \mathcal{P}_\Omega\nabla F \left(\mathbf{\Theta}^{i}_0\right) \right\|_F^2 - 4\left\langle \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_0\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^\star\right)\right), \mathcal{P}_\Omega\nabla F \left(\mathbf{\Theta}^{i}_0\right) \right\rangle \end{align}\] By applying 2 to bound the first two terms, we have \[\begin{align} \left\| \mathcal{P}_{\Omega}(\mathbf{G}^i_j) \right\|_F^2 \le & 4L_{2k}\left[f_{b_j}(\mathbf{\Theta}^i_j)-f_{b_j}(\mathbf{\Theta}^\star)-\left\langle \nabla f_{b_j}(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_{j}-\mathbf{\Theta}^\star \right\rangle\right] \\ & + 4L_{2k}\left[f_{b_j}(\mathbf{\Theta}^i_0)-f_{b_j}(\mathbf{\Theta}^\star)-\left\langle \nabla f_{b_j}(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_{0}-\mathbf{\Theta}^\star \right\rangle\right]\\ & + 2 \left\| \mathcal{P}_\Omega\nabla F \left(\mathbf{\Theta}^{i}_0\right) \right\|_F^2 - 4\left\langle \mathcal{P}_{\Omega}\left(\nabla f_{b_j} \left(\mathbf{\Theta}^{i}_0\right)-\nabla f_{b_j} \left(\mathbf{\Theta}^\star\right)\right), \mathcal{P}_\Omega\nabla F \left(\mathbf{\Theta}^{i}_0\right) \right\rangle \end{align}\] Taking expectation over \(b_j\), we have \[\begin{align} \mathbb{E}_{b_j}\left\| \mathcal{P}_{\Omega}(\mathbf{G}^i_j) \right\|_F^2 \le & 4L_{2k}\left[F(\mathbf{\Theta}^i_j)-F(\mathbf{\Theta}^\star)\right] + 4L_{2k}\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right]\\ & -4L_{2k}\left\langle \nabla F(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_{j}+\mathbf{\Theta}^j_0-2\mathbf{\Theta}^\star \right\rangle\\ & + 2\left\langle 2\mathcal{P}_{\Omega}\left(\nabla F \left(\mathbf{\Theta}^\star\right)\right) - \mathcal{P}_{\Omega}\left(\nabla F \left(\mathbf{\Theta}^{i}_0\right)\right), \mathcal{P}_\Omega\nabla F \left(\mathbf{\Theta}^{i}_0\right) \right\rangle\\ = & 4L_{2k}\left[F(\mathbf{\Theta}^i_j)-F(\mathbf{\Theta}^\star)\right] + 4L_{2k}\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right]\\ & -4L_{2k}\left\langle \nabla F(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_{j}+\mathbf{\Theta}^j_0-2\mathbf{\Theta}^\star \right\rangle\\ & + \left\| 2\mathcal{P}_\Omega\left(\nabla F(\mathbf{\Theta}^\star)\right) \right\|_F^2-\left\| 2\mathcal{P}_\Omega(\nabla F(\mathbf{\Theta}^\star)-\nabla F(\mathbf{\Theta}^i_0)) \right\|_F^2\\ & - \left\| \mathcal{P}_{\Omega}\left(\nabla F(\mathbf{\Theta}^i_0)\right) \right\|_F^2 \\ \le & 4L_{2k}\left[F(\mathbf{\Theta}^i_j)-F(\mathbf{\Theta}^\star)\right] + 4L_{2k}\left[F(\mathbf{\Theta}^i_0)-F(\mathbf{\Theta}^\star)\right]\\ & -4L_{2k}\left\langle \nabla F(\mathbf{\Theta}^\star), \mathbf{\Theta}^i_{j}+\mathbf{\Theta}^j_0-2\mathbf{\Theta}^\star \right\rangle + 4\left\| \mathcal{P}_\Omega\left(\nabla F(\mathbf{\Theta}^\star)\right) \right\|_F^2 \end{align}\]

 ◻

Proof. Denote \(\mathbf{\Theta}^+=\mathcal{H}_k \left( \mathbf{\Theta}- \eta \mathbf{G}\right)\). Define \(\Lambda_{new}\) to be the indices set of \(k\)-largest elements in \(G\) that doesn’t belong to \(\mathtt{supp}(\mathbf{\Theta})\). It can be easily verified that \[\begin{align} \mathcal{H}_k \left( \mathbf{\Theta}- \eta \mathbf{G}\right) = \mathcal{H}_k \left( \mathbf{\Theta}- \eta\mathcal{P}_{\mathtt{supp}(\mathbf{\Theta})\cup\Lambda_{new}}\left(\mathbf{G}\right) \right) \end{align}\] Given that \(|\mathtt{supp}(\mathbf{\Theta})|\le k\), by pigeonhole principle, we have \(\Lambda_{new}\subseteq\Lambda_{2k}\), thus \[\begin{align} \mathcal{H}_k \left( \mathbf{\Theta}- \eta\mathcal{P}_{\mathtt{supp}(\mathbf{\Theta})\cup\Lambda_{new}}\left(\mathbf{G}\right) \right) = \mathcal{H}_k\left(\mathbf{\Theta}- \eta \mathcal{P}_{\mathtt{supp}(\mathbf{\Theta}) \cup \Lambda_{2k}} (\mathbf{G}) \right) \end{align}\] ◻

Proof. Define \[\begin{align} \Gamma_0 = \mathtt{supp}(\mathbf{\Theta}^+)\cap\mathtt{supp}(\widetilde{\mathbf{\Theta}}^+), \Gamma_1 = \mathtt{supp}(\mathbf{\Theta}^+)\backslash\mathtt{supp}(\widetilde{\mathbf{\Theta}}^+), \Gamma_2=\mathtt{supp}(\widetilde{\mathbf{\Theta}}^+)\backslash\mathtt{supp}(\mathbf{\Theta}^+) \end{align}\] We have that \[\begin{align} \mathbf{\Theta}^+-\widetilde{\mathbf{\Theta}}^+ = \mathcal{P}_{\Gamma_1}(\mathbf{\Theta}^+) - \mathcal{P}_{\Gamma_2}(\widetilde{\mathbf{\Theta}}^+) \end{align}\] By definition of \(\mathbf{\Theta}^+, \widetilde{\mathbf{\Theta}}^+\), it is easy to verify that \[\begin{align} \|\mathcal{P}_{\Gamma_1}(\mathbf{\Theta}^+)\|_\infty \le \|\mathcal{P}_{\Gamma_2}(\widetilde{\mathbf{\Theta}}^+)\|_\infty \end{align}\] Also, since the elements that is greater than \(\eta\Delta\) can only come from \(\mathtt{supp}(\mathbf{\Theta})\cup \Lambda_\Delta\), and given that \(\Lambda_{\Delta}\subseteq\widetilde{\Lambda}\), we know that \[\begin{align} i \in \mathtt{supp}(\mathbf{\Theta}^+), \forall i\;s.t. \widetilde{\mathbf{\Theta}}^+_i\ge \eta\Delta \Rightarrow i \in \Gamma_0, \forall i\;s.t. \widetilde{\mathbf{\Theta}}^+_i\ge \eta\Delta \end{align}\] Thus we have \[\begin{align} \|\mathcal{P}_{\Gamma_2}(\widetilde{\mathbf{\Theta}}^+)\|_\infty \le \eta\Delta \end{align}\] By 4, we know that \[\begin{align} \widetilde{\mathbf{\Theta}}^+=\mathcal{H}_{k}\left(\mathbf{\Theta}-\eta\mathcal{P}_{\Lambda_{2k}\cup\mathtt{supp}({\mathbf{\Theta}})}(\mathbf{G}_t)\right) \end{align}\] Thus we have \(|\Gamma_2|\le k_\Delta\) and given that \(|\mathtt{supp}(\mathbf{\Theta}^+)| = |\widetilde{\mathtt{supp}}(\mathbf{\Theta}^+)|\), we have \(|\Gamma_1|=|\Gamma_2|\). Thus, \[\begin{align} \left\| \mathbf{\Theta}^+-\widetilde{\mathbf{\Theta}}^+ \right\|_F = \left\| \mathcal{P}_{\Gamma_1}(\mathbf{\Theta}^+) - \mathcal{P}_{\Gamma_2}(\widetilde{\mathbf{\Theta}}^+) \right\|_F \le \eta\Delta \sqrt{2k_\Delta} \end{align}\] ◻