6 Additional Simulations↩︎

In this section, we present additional simulation results that are not included in the main text due to space limitations. These supplementary results provide further support for the theoretical findings reported in the paper.

6.1 Varying the level of sparsity and contamination↩︎

We fix \(p=1000,~ n=600\), vary sparsity level \(s\) from 7 to 35 and contamination level \(o\) from 12 to 120. All non-zero signals take a value of 1. The \(\ell_2\) estimation errors of \(\beta^*\) are shown in Figure 4.

As illustrated in Figure 4, the \(\ell_2\) estimation error \(\|\tilde{\beta} - \beta^*\|_2\) grows linearly with the contamination proportion \(o/n\), yet it grows only on the order of \(\sqrt{s}\) of the sparsity level \(s\). This empirical behavior matches our theoretical guarantees (summarized in Table 1 in our manuscript): No matter in which signal cases, for fixed \(o\), the \(\ell_2\) error bound increases linearly in \(\sqrt{s}\); for fixed \(s\), it increases linearly in \(o\). In particular, when \(o/n \le 1/5\), the \(\ell_2\) error bound in Theorem 3 can be rewritten as \[\|\tilde{\beta} - \beta^*\|_2 \;\asymp\; \sigma\sqrt{\frac{s}{\,n - o\,}} \;\asymp\; \sigma\sqrt{\frac{s}{n}} \left(1 + \frac{o}{n} \right),\] which explains the linear relationship with \(o\).

6.2 Asymptotic normality↩︎

We then consider the asymptotic normality of the estimator obtained from two-stage AC-IHT by constructing the z-score based on Corollary 2 with 300 replications. Specifically, we set the 5th and 6th elements of \(\gamma\) to 1 and all others to 0. We assess the asymptotic normality of AC-IHT, IHT-\(\ell_1\), and AC-SCAD by using histograms, Q-Q plots, and the \(R^2\) values from the no-intercept linear fit of these Q-Q plots.

As illustrated in Figure 5, AC-IHT exhibits the best asymptotic normality performance: Its histogram closely aligns with the normal density curve, and the points in its Q-Q plot lie almost perfectly along the diagonal, with an \(R^2 = 0.9891\). In contrast, IHT-\(\ell_1\) and AC-SCAD show noticeable deviations and lower \(R^2\) values.

6.3 Heavy tailedness↩︎

Following the theoretical extension in the discussion section, we conduct supplementary experiments under heavy-tailed noise settings. Specifically, we generate i.i.d. white noise from Student’s t-distributions with 2 and 3 degrees of freedom and assume no adversarial contamination, while keeping all other model configurations identical to those in Section 4. And we include the Oracle Huber estimator as an ideal reference, which is the Huber estimator with the known support set. Results over 100 replications are reported in Table 4, with standard errors shown in parentheses. The findings demonstrate that our AC-IHT method achieves favorable performance in both estimation accuracy and support recovery, which aligns with its minimax near-optimal guarantee in Theorem 7.

6.4 Dynamic of convergence↩︎

In this subsection, we examine the iteration-wise convergence behavior of AC-IHT under varying sample sizes and contamination levels. Specifically, we consider sample sizes \(n\in\{300, 500, 700\}\) and numbers of contaminated observations \(o\in\{10, 30\}\), while keeping all other simulation settings the same as in the beginning of Section 4. Estimation accuracy is assessed using the \(\ell_2\) error (\(L_2\)) and the \(\ell_\infty\) error (\(L_{\max}\)), and support recovery accuracy is evaluated by the Matthews Correlation Coefficient (MCC). The corresponding iteration trajectories are displayed in Figure 6.

Figure 6 shows a consistent convergence pattern across all configurations. The errors \(L_2\) and \(L_{\max}\) decrease during the initial iterations and then level off after about 20 iterations, whereas MCC rises toward one after about 15 iterations and remains stable thereafter, indicating reliable support recovery. Moreover, larger sample sizes improve estimation and support recovery performance, as evidenced by smaller \(L_2/L_{\max}\) and higher MCC. When the contamination level increases from \(o=10\) to \(o=30\), convergence becomes slightly slower, and the terminal errors are mildly larger, particularly for smaller \(n\), which aligns with our theoretical results.

6.5 Relationship between signal strength and sparsity.↩︎

Assumption 4 indicates that the required signal strength (for \(\theta^*\)) increases as \(o\) decreases. The following simulation validates this phenomenon. Following the simulation settings in Section 4, we fix the non-zero entries of \(\theta^*\) at 0.2, and examine the support recovery of \(\theta^*\) as \(o\) increases under standard Gaussian noise. The simulation result in Figure 7 (with 100 replications) shows that as \(o(= \| \theta^*\|_0)\) increases, the MCC (Matthews Correlation Coefficient) rises and the averaged Hamming loss \(\left(\frac{\left | \text{supp}(\theta^*) \triangle \text{supp}(\hat{\theta})\right |}{o}\right)\) decreases. This indicates that a larger \(o\) makes the “theta-min” condition easier to satisfy, yielding progressively more accurate outlier identification. And this result aligns with the relationship between \(o\) and the signal strength in Assumption 4.

7 Proof of Proposition 1↩︎

Throughout this proof, \(C_1>0\) is treated as a fixed constant, and Assumption 2 is used in the concrete form stated in Proposition 1. We first prove the restricted isometry of \(X\). For a fixed set \(S\subset[p]\) with \(|S|=C_1s\), by Remark 5.40 in [47], we obtain \[\label{eq:32spec32norm} \mathbf{P} \left( \left\|\frac{1}{n} X_{\cdot S}^\top X_{\cdot S}- \Sigma_{SS} \right\|_2 > \max(\iota , \iota^2) \right) \le 2e^{- u},\tag{19}\] where \(\iota = \left(C \vee \frac{1}{\sqrt c}\right) \left( \sqrt{\frac{C_1s}{n}} + \sqrt{\frac{u}{n}} \right),\) and \(C,c\) are constants depending only on \(\|\Sigma\|_2\). Let \(C_\Sigma := C^2 \vee \frac{1}{c} \vee 1 .\) By taking \(u=3C_1s\log p\) and using \(n\ge 30M^2C_1C_\Sigma \max(s\log p,o\log n),\) we have \(\iota\vee\iota^2=\iota\le 1/(2M)\), which yields that \[\label{eq:32X32Sigma} \begin{align} &\mathbf{P} \left( \sup_{S\subset [p]:~ |S| \le C_1 s} \left\|\frac{1}{n} X_{\cdot S}^\top X_{\cdot S}- \Sigma_{SS} \right\|_2 > \frac{1}{2M}\right)\\ \le& \sum_{ S\subset [p]:~ |S| = C_1 s} \mathbf{P} \left( \left\|\frac{1}{n} X_{\cdot S}^\top X_{\cdot S}- \Sigma_{SS} \right\|_2 > \max(\iota , \iota^2) \right)\\ \le& 2\binom p{ C_1 s} \exp\left(- 3C_1 s\log p\right)\\ \le& 2 \exp\left( -2C_1 s\log p \right). \end{align}\tag{20}\] By Weyl’s inequality, with probability at least \(1 - 2 \exp(-2C_1 s \log p)\) we have that, \[\label{eq:32weyl} \max_{S\subset [p]:~ |S| \le C_1 s}~ \max_{1\le k \le |S|}~ \left| \Lambda_k\left( \frac{1}{n} X_{\cdot S}^\top X_{\cdot S}\right) - \Lambda_k (\Sigma_{SS})\right| \le \frac{1}{2M}.\tag{21}\] Consequently, the restricted isometry property follows immediately from this uniform eigenvalue bound and the definition of eigenvalue.

We then prove the restricted incoherence of \(X\). Similar to 19 , for fixed sets \(S\subset[p]\) with \(|S|= C_1 s\) and \(O \subset [n]\) with \(|O |=C_1 o\), we have \[\mathbf{P} \left( \left\|\frac{1}{C_1 o} X^\top_{O, S} X_{O, S} - \Sigma_{SS} \right\|_2 >\max(\tau , \tau^2) \right) \le 2e^{-v},\] where \(\tau = \left(C \vee \frac{1}{\sqrt c}\right) \cdot \left(\sqrt{\frac{ s}{o} } +\sqrt{\frac{v}{C_1 o} } \right)\). By setting \(v =3C_1 s\log p+3C_1 o \log n\) and applying a union bound, we obtain \[\begin{align} &\mathbf{P} \left\{ \sup_{O \subset [n]: ~|O| \le C_1 o }~ \sup_{S\subset[p]:~ |S| \le C_1 s} \left\|\frac{1}{C_1 o} X^\top_{O, S} X_{O, S} - \Sigma_{SS} \right\|_2 >\max(\tau , \tau^2) \right\} \\ \le& \binom{p}{C_1 s} \binom{n}{C_1 o } 2e^{-v}\\ \le& 2 e^{-2 C_1 s \log p}. \end{align}\] Consequently, for any \(S \subset [p]\) with \(|S| \le C_1 s\) and \(O \subset [n]\) with \(|O| \le C_1 o\), it holds that \[\label{eq:32inco32induction} \begin{align} \|X_{O, S} \|_2 =&\sqrt{\left\| X^\top_{O,S} X_{O,S} \right\|_2 }\\ \le & \sqrt{C_1 o \| \Sigma_{SS}\|_2 + C_1 o (\tau + \tau^2 ) }\\ \le& \sqrt{ C_1 o M +C_1 C_\Sigma \left( \sqrt{so} + \sqrt{\frac{vo}{C_1}} +2s+ \frac{2v}{C_1} \right) }\\ \le& \sqrt{ C_1 o M + 10 C_1 C_\Sigma \left(s \log p + o \log n\right) }\\ \le& \sqrt{C_1} C_M\cdot \sqrt{ s \log p+ o \log n} \end{align}\tag{22}\] with probability at least \(1-2\exp(-2C_1s\log p)\). Here \(C_M:=\sqrt{M+ 10C_\Sigma}>1\) is a constant depending only on \(M\). Therefore, we prove the restricted incoherence property and complete the proof of Proposition 1.

8 Proof of Theorem 1↩︎

We introduce some definitions that will be used in the following proofs. Define \[\Phi := \frac{ \eta }{n} X^{\top} X - I_p \in \mathbb{R}^{p\times p}, \quad ~\Xi := \frac{1}{n} X^{\top}\xi \in \mathbb{R}^{p}.\] For ease of display, we assume \(\sigma=1\) in the main proof.

Three parts constitute the proof of Theorem 1. We first introduce some useful preliminaries, and then prove the sparsity and error bounds by using mathematical induction. Finally, we verify the validity of our proposed threshold sequence.

8.1 Preliminary↩︎

Define the event \[\label{eq:32good32event32of32Th1} \mathcal{E}: = \left\{ \left\| \Xi \right\|_\infty < 4\sqrt{\frac{M\log p}{n}} , \text{ and } \left\| \frac{1}{\sqrt n} \xi \right\|_\infty < 3\sqrt{\frac{ \log n}{n} }\right\},\tag{23}\]

and \[\mathcal{E}_X:= \begin{Bmatrix} \frac{1}{2M} \le \Lambda_k\left( \frac{1}{n} X_{\cdot S}^\top X_{\cdot S}\right) \le 2M, \text{ for every }S \subset [p]:~ |S| \le (2B+1)s \text{ and } 1\le k \le |S|, \\ \sup_{S\subset[p]:~ |S| \le (B+1) s} ~ \sup_{O\subset[n]:~ |O| \le (B+1)o} \left\| X_{O,S} \right\|_2 \le {(\sqrt B+1)} f \sqrt n \end{Bmatrix},\] where \[\label{eq:32B32delta} B:= \left(\frac{\kappa+\delta}{\kappa- \delta}\right)^2>1, \quad \delta := \frac{4M^2}{4M^2 +1}\in (0,1), \quad f:= C_M \sqrt{\frac{s \log p + o \log n}{n}}.\tag{24}\] Throughout the proof of Theorem 1, Assumption 2 is used in the concrete form \[n\ge C_{\mathrm{Th1}}\{s\log p+o\log n\},\] where \(C_{\mathrm{Th1}}\) is a fixed constant depending only on \(M,\eta,\kappa\), chosen large enough so that \[C_{\mathrm{Th1}} \ge \max\left\{ 30M^2(2B+1)C_\Sigma,~ \frac{32\eta^2\kappa^2C_M^2}{(\kappa-\delta)^4},~ 4MC_M^2 \right\}.\]

Therefore, with \(n \ge 30M^2(2B+1)C_\Sigma \{s\log p+o\log n\}\), we confirm that the restricted isometry part of \(\mathcal{E}_X\) follows from Proposition 1 with \(C_1=2B+1\), and the restricted incoherence part follows from Proposition 1 with \(C_1=B+1\). Since \(B=\left(\frac{\kappa+\delta}{\kappa-\delta}\right)^2\) is fixed once \(M\) and \(\kappa \in(\delta,1)\) are fixed, these choices of \(C_1\) are admissible under Proposition 1, hence we have \(\mathbf{P}(\mathcal{E}_X) \ge 1- 4p^{-2(1+B)s}\).

Similarly, with \(n\ge 30M^2C_\Sigma\max(s\log p,o\log n)\), by Lemma 1 we have \(\mathbf{P}(\mathcal{E}) \ge 1-2p^{-2s} - 2p^{-3}- 2n^{-3}\). And we conclude that \[\mathbf{P}(\mathcal{E}\cap\mathcal{E}_X) \ge 1-O(p^{-2}+n^{-3}).\] The proof of Theorem 1 is then based on the event \(\mathcal{E}\cap\mathcal{E}_X\).

In the iteration algorithm, we take the learning rate \(\eta \in \left[\frac{2M}{4M^2 + 1}, \frac{4M}{4M^2 + 1} \right]\) and the decay rate \(\kappa \in (\delta,1)\). And we use the thresholds \[\label{eq:32lambda32infty} \begin{align} \lambda_{\beta, \infty} &= \frac{16\eta \kappa }{\kappa- \delta} \sqrt{\frac{M \log p}{n}} + \frac{48\eta^2 \kappa^2 C_M }{(\kappa- \delta)^3} \sqrt{\frac{s\log p+ o\log n}{ns}} \sqrt{\frac{o \log n}{n}} \\ & {\asymp \sqrt{\frac{\log p}{n}} + {\frac{o \log n}{n\sqrt s}} }, \\ \lambda_{\theta, \infty} &= \frac{12\eta \kappa }{\kappa- \delta} \sqrt{\frac{\log n}{n}} + \frac{64\eta^2 \kappa^2 C_M \sqrt M }{(\kappa- \delta)^3} \sqrt{\frac{s\log p+ o\log n}{no}} \sqrt{\frac{s \log p}{n}}\\ & {\asymp \sqrt{\frac{\log n}{n}} + {\frac{s \log p}{n\sqrt o}} }. \end{align}\tag{25}\] For the given thresholds \(\lambda_{\beta,\infty}\) and \(\lambda_{\theta,\infty}\) in 25 , we can always choose sufficiently large initial thresholds \(\lambda_{\beta,0}~ (>\lambda_{\beta,\infty})\) and \(\lambda_{\theta,0}~(>\lambda_{\theta,\infty})\) satisfying \[\label{eq:32lambda0s} \sqrt s \lambda_{\beta,0} > \|\beta^* \|_2, \quad \sqrt o \lambda_{\theta,0} > \|\theta^* \|_2, \quad \frac{\lambda_{\beta,0}}{\lambda_{\theta,0}} =\frac{\lambda_{\beta,\infty}}{\lambda_{\theta,\infty}}.\tag{26}\] The detailed threshold initialization is provided in Section 8.4, where we utilize the conditions of Theorem 1 and the high-probability restricted incoherence property from Proposition 1 to establish a feasible range for the initial thresholds.

Additionally, by the decomposition, we define \[\label{eq:32decomposition} \begin{align} H_{\beta}^{t+1} :=& {\beta}^t + \frac{\eta}{n}X^{\top}(Y - X {\beta}^t - \sqrt{n} {\theta}^t) \\ = &\beta^* + \Phi(\beta^* - \beta^t) + \frac{\eta}{\sqrt n} X^\top (\theta^* - \theta^t) + \eta\Xi \in \mathbb{R}^p,\\ H_{\theta}^{t+1} :=& \theta^t + \frac{\eta}{\sqrt{n}}(Y - X\beta^t - \sqrt{n}\theta^t)\\ =& \theta^* + (\eta-1) (\theta^* - \theta^t) + \frac{\eta}{\sqrt n} X (\beta^* - \beta^t) + \frac{\eta}{\sqrt n} \xi \in \mathbb{R}^n. \end{align}\tag{27}\]

8.2 Mathematical induction↩︎

Recall \(S^* = supp(\beta^*)\) and \(O^* = supp(\theta^*)\). We aim to use mathematical induction to prove the following \[\begin{align} \| \beta^t_{(S^*)^c} \|_0 < B s,& \quad \|\theta^{t}_{(O^*)^c}\|_0 < Bo,\tag{28}\\ \| \beta^t - \beta^* \|_2 \le (\sqrt B+1) \cdot \sqrt s \lambda_{\beta, t},& \quad \| \theta^{t} - \theta^* \|_2 \le (\sqrt B+1) \cdot \sqrt o \lambda_{\theta, t}.\tag{29} \end{align}\] hold for all \(t\ge 0\).

First, by 26 , we guarantee that both 28 and 29 hold at \(t=0\), with \(\beta^0 = \mathbf{0}_p\) and \(\theta^0 = \mathbf{0}_n\). By using mathematical induction, assume that 28 and 29 hold at iteration \(t\) for some \(t \ge 0\), and then we aim to prove that they remain valid at iteration \(t+1\).

Proof of sparsityIn the \((t+1)\)-th iteration, we first prove 28 reasoning by the absurd. Assume that \(\|\beta^{t+1}_{(S^*)^c}\|_0 \ge Bs\) or \(\|\theta^{t+1}_{(O^*)^c}\|_0 \ge Bo\) holds at first. It then follows that there exist subsets \(\tilde{S} \subset (S^*)^c\) or \(\tilde{O} \subset (O^*)^c\) such that \(\|\tilde{S}\|_0 = Bs\) or \(\|\tilde{O}\|_0 = Bo\), satisfying \[\label{eq:32abs1} Bs \lambda_{\beta,t+1}^2 < \sum_{i \in \tilde{S}}(H_{\beta,i}^{t+1})^2 \mathbf{1}\{ |H_{\beta,i}^{t+1}|\geq \lambda_{\beta,t+1} \}\tag{30}\] or \[\label{eq:32abs2} B o \lambda_{\theta,t+1}^2 < \sum_{j \in \tilde{O}}(H_{\theta,j}^{t+1})^2 \mathbf{1}\{ |H_{\theta,j}^{t+1}|\geq \lambda_{\theta,t+1} \}.\tag{31}\]

Since \(\beta_{\tilde{S}}^* = \mathbf{0}_{Bs}\) and \(\theta_{\tilde{O}}^* = \mathbf{0}_{Bo}\), under event \(\mathcal{E}\), if 30 holds, by decomposition 27 we have \[\label{absurd32beta} \begin{align} \sqrt{Bs}\lambda_{\beta,t+1}&\leq \sqrt{\sum_{i \in \tilde{S}}\langle \Phi_{\cdot i}, \beta^* - \beta^t \rangle^2} + \sqrt{\sum_{i \in \tilde{S}}\frac{\eta^2}{n}\langle X_{\cdot i}, \theta^* - \theta^t \rangle^2} + \eta \sqrt{Bs} \| \Xi\|_\infty\\ &\overset{(i)}{\leq} \delta \|\beta^* - \beta^t\|_2+ \eta (\sqrt B +1)f\cdot \|\theta^* - \theta^t\|_2 + \eta \sqrt{Bs} \| \Xi\|_\infty \\ &\overset{(ii)}{<} \delta (\sqrt B+1) \cdot \sqrt s \lambda_{\beta, t} + \eta (\sqrt B+1)^2 f \cdot \sqrt o \lambda_{\theta, t} + 4 \eta (\sqrt B +1) \sqrt{ s} \sqrt{\frac{M\log p}{n}} \\ &\overset{(iii)}{\leq} \frac{2 \delta}{\kappa-\delta}\cdot \sqrt s \lambda_{\beta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt o \lambda_{\theta, t+1} + \frac{8 \eta \kappa}{\kappa-\delta} \sqrt{ s} \sqrt{\frac{M\log p}{n}}, \end{align}\tag{32}\] where:

• Inequality (i) follows from the fact \[\label{eq:32inner32products} \begin{align} &\quad \sum_{i \in \tilde{S}}\langle \Phi_{\cdot i}, \beta^* - \beta^t \rangle^2 \leq \sum_{i \in S^{'}}\langle \Phi_{\cdot i}, \beta^* - \beta^t \rangle^2~ \quad\text{ (define } S^{'} = \tilde{S}\cup\text{supp}(\beta^* - \beta^t) ) \\ & =~ (\beta^* - \beta^t)^\top_{S^{'}}\Phi^\top_{S^{'}S^{'}}\Phi_{S^{'}S^{'}}(\beta^* - \beta^t)_{S^{'}}~\leq~ \|\Phi_{S^{'}S^{'}}\|_2^2\|\beta^* - \beta^t\|_2^2\\ &= \left\{ \left|\Lambda_{\max} \left( \frac{\eta (X^\top X)_{S' S^{'}}}{n} \right) - 1 \right| \bigvee \left| 1 - \Lambda_{\min} \left( \frac{\eta (X^\top X)_{S' S^{'}}}{n} \right) \right| \right\}^2 \|\beta^* - \beta^t\|_2^2\\ &\leq (1- \eta/(2M) )^2\|\beta^* - \beta^t\|_2^2 \quad\text{(By } \mathcal{E}_X \text{ and the range of } \eta \text{)}\\ &\leq \delta^2\|\beta^* - \beta^t\|_2^2, \quad\text{(Equation \eqref{eq:32B32delta})} \end{align}\tag{33}\] and \[\label{eq:32inner32products322} \begin{align} \frac{1}{n}\sum_{i \in \tilde{S}}\langle X_{\cdot i}, \theta^* - \theta^t \rangle^2 &= \frac{1}{n}(\theta^* - \theta^t)^\top_{O'}X_{O'\tilde{S}}X^\top_{O'\tilde{S}}(\theta^* - \theta^t)_{O'}~ \quad\text{ (define } O^{'} = \text{supp}(\theta^* - \theta^t) )\\ &\leq \frac{1}{n}\|X_{O'\tilde{S}}\|_2^2\cdot \|\theta^* - \theta^t\|_2^2 \\ &\leq (\sqrt B +1)^2 f^2 \cdot \|\theta^* - \theta^t\|_2^2. \quad\text{(By } \mathcal{E}_X \text{)} \end{align}\tag{34}\]

• Inequality (ii) follows from the event \(\mathcal{E}\) and the assumption 29 at the \(t\)-th iteration.

• Inequality (iii) follows the relationship: \[\label{eq:32relation32b32lambda} \sqrt B + 1 = \frac{2 \kappa}{\kappa - \delta}, \quad \lambda_{\beta,t+1} = \max(\kappa \lambda_{\beta,t}, ~ \lambda_{\beta, \infty}), \quad \lambda_{\theta,t+1} = \max(\kappa \lambda_{\theta,t}, ~ \lambda_{\theta, \infty}).\tag{35}\]

Similarly, if 31 holds, we have \[\label{absurd32theta} \begin{align} \sqrt{Bo}\lambda_{\theta, t+1}&\leq |\eta -1| \cdot \| \theta^*- \theta^t\|_2 + \sqrt{\sum_{j \in \tilde{O}}\frac{\eta^2}{n}\langle X_{j \cdot}^\top, \beta^* - \beta^t \rangle^2} + \eta \sqrt{\sum_{j \in \tilde{O}}\frac{1}{n}\xi^2_j}\\ &\leq \delta\| \theta^*- \theta^t\|_2 + \eta (\sqrt B +1)f \| \beta^* - \beta^t\|_2 + 3\eta \sqrt{ B o} \sqrt{\frac{\log n}{n}}\\ &< \frac{2 \delta}{\kappa-\delta}\cdot \sqrt o \lambda_{\theta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt s \lambda_{\beta, t+1} + \frac{6\eta \kappa}{\kappa-\delta} \sqrt{ o} \sqrt{\frac{\log n}{n}}, \end{align}\tag{36}\] where:

• The second inequality follows from the fact \[\label{eq:32inner32products323} \begin{align} \frac{1}{n}\sum_{j \in \tilde{O}}\langle X_{j \cdot}^\top, \beta^* - \beta^t \rangle^2 &\leq \frac{1}{n}(\beta^* -\beta^t)^\top_{S^{''}} X_{\tilde{O} S^{''}}^\top X_{\tilde{O} S^{''}}(\beta^* -\beta^t)_{S^{''}} ~ \quad\text{ (define } S^{''} = \text{supp}(\beta^* - \beta^t) )\\ &\leq \frac{1}{n}\|X_{\tilde{O} S^{''}}\|_2^2 \cdot \|\beta^* -\beta^t\|_2^2\\ &\leq (\sqrt B +1)^2 f^2\cdot \|\beta^* - \beta^t\|_2^2 \quad\text{(By } \mathcal{E}_X ), \end{align}\tag{37}\] and the fact \(|\eta-1| < \delta\) in the case \(\eta \in \left[\frac{2M}{4M^2 + 1}, \frac{4M}{4M^2 + 1} \right]\).

• The derivation of the last inequality is analogous to that of (ii) and (iii) in 32 .

Combining 32 and 36 , to prove \(\|\beta^{t+1}_{(S^*)^c}\|_0 < Bs\) and \(\|\theta^{t+1}_{(O^*)^c}\|_0 < Bo\) by contradiction, it suffices to show that: \[\label{eq:32keypoint} \begin{cases} \frac{2 \delta}{\kappa-\delta}\cdot \sqrt s \lambda_{\beta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt o \lambda_{\theta, t+1} + \frac{8 \eta \kappa}{\kappa-\delta} \sqrt{ s} \sqrt{\frac{M\log p}{n}} \le \sqrt{ Bs} \lambda_{\beta, t+1},\\ \frac{2 \delta}{\kappa-\delta}\cdot \sqrt o \lambda_{\theta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt s \lambda_{\beta, t+1} + \frac{6\eta \kappa}{\kappa-\delta} \sqrt{ o} \sqrt{\frac{\log n}{n}} \le \sqrt{ Bo} \lambda_{\theta, t+1}. \\ \end{cases}\tag{38}\] We first assume that there exist suitable sequence \(\{(\lambda_{\beta,t},~\lambda_{\theta,t} ) \}_{t \ge 0}\) satisfying this system 38 , and we will construct its explicit form in Section 8.3.

Proof of error boundsOnce the sparsity results are established in the \((t+1)\)-th iteration, we turn to derive upper bounds on estimation errors. We establish that \[\label{eq:32th132upper32bound1} \begin{align} &\| \beta^{t+1} - \beta^*\|_2 \\ &\le \Bigg\{ \sum_{i \in S^*}\left( - H_{\beta,i}^{t+1} \mathbf{1}(|H_{\beta,i}^{t+1}|< \lambda_{\beta,t+1}) + \langle \Phi_{\cdot i}, \beta^* - \beta^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \theta^t \rangle + \eta \Xi_i \right)^2 \\ &\quad \quad\quad \left.+ \sum_{i \in S^{t+1}\setminus S^*}\left( \langle \Phi_{\cdot i}, \beta^* - \beta^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \theta^t \rangle + \eta \Xi_i \right)^2 \right\}^{1/2}\\ &\le \sqrt{\sum_{i \in S^*} \left( H_{\beta,i}^{t+1} \right)^2 \mathbf{1}(|H_{\beta,i}^{t+1}|< \lambda_{\beta,t+1})} + \sqrt{\sum_{i \in S^{t+1} \cup S^*} \langle \Phi_{\cdot i}, \beta^* - \beta^t \rangle^2 } \\ &\quad \quad + \eta \sqrt{\sum_{i \in S^{t+1} \cup S^*} \frac{1}{n}\langle X_{\cdot i}, \theta^* - \theta^t \rangle^2 } + \eta\sqrt{\sum_{i \in S^{t+1} \cup S^*} \Xi_i^2 } \\ &\overset{(i)}\leq \sqrt{s}\lambda_{\beta, t+1} + \delta\| \beta^t - \beta^*\|_2 + \eta (\sqrt B +1)f\cdot \|\theta^* - \theta^t\|_2 + 4 \eta (\sqrt B+1) \sqrt{s} \sqrt{\frac{M\log p}{n}} \\ &\overset{(ii)}\leq \sqrt{s}\lambda_{\beta, t+1} + \frac{2 \delta}{\kappa-\delta}\cdot \sqrt s \lambda_{\beta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt o \lambda_{\theta, t+1} + \frac{8 \eta \kappa}{\kappa-\delta} \sqrt{ s} \sqrt{\frac{M\log p}{n}}, \end{align}\tag{39}\] where recall \(S^{t+1} = \text{supp}(\beta^{t+1}),\;S^{*} = \text{supp}(\beta^{*})\). Here, inequality (i) follows from 33 and 34 again, and inequality (ii) follows analogously to (ii) and (iii) in 32 . Similar to 39 , we derive that \[\label{eq:32th132upper32bound2} \begin{align} \| \theta^{t+1} - \theta^*\|_2 &\leq \sqrt{o}\lambda_{\theta, t+1} + \delta\| \theta^t - \theta^* \|_2 + \eta (\sqrt B +1) f \| \beta^t - \beta^* \|_2 + 3\eta \sqrt{(B+1) o} \sqrt{\frac{\log n}{n}} \\ &< \sqrt{o}\lambda_{\theta, t+1} + \frac{2 \delta}{\kappa-\delta}\cdot \sqrt o \lambda_{\theta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt s \lambda_{\beta, t+1} + \frac{6\eta \kappa}{\kappa-\delta} \sqrt{ o} \sqrt{\frac{\log n}{n}}. \end{align}\tag{40}\] Therefore, to ensure that the \(\ell_2\) error bounds after the \((t+1)\)-th iteration satisfies 29 , it suffices for the sequence \(\{ ( \lambda_{\beta,t}, \lambda_{\theta,t} ) \}_{t \ge 0}\) to satisfy \[\begin{cases} \sqrt s \lambda_{\beta, t+1} + \frac{2 \delta}{\kappa-\delta}\cdot \sqrt s \lambda_{\beta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f\sqrt o \lambda_{\theta, t+1} + \frac{8 \eta \kappa}{\kappa-\delta} \sqrt{ s} \sqrt{\frac{M\log p}{n}} \le (\sqrt B+1) \sqrt{ s} \lambda_{\beta, t+1},\\ \sqrt{o}\lambda_{\theta, t+1} + \frac{2 \delta}{\kappa-\delta}\cdot \sqrt o \lambda_{\theta, t+1} + \frac{4 \eta \kappa}{(\kappa-\delta)^2} \cdot f \sqrt s \lambda_{\beta, t+1} + \frac{6\eta \kappa}{\kappa-\delta} \sqrt{ o} \sqrt{\frac{\log n}{n}} \le (\sqrt B+1) \sqrt{ o} \lambda_{\theta, t+1},\\ \end{cases}\] which is equivalent to the system 38 . Consequently, we next focus on constructing a suitable set of solutions for \(\{ ( \lambda_{\beta,t}, \lambda_{\theta,t} ) \}_{t \ge 0}\).

8.3 Appropriate threshold sequence↩︎

Define \[W_1 := \frac{4 \eta \kappa}{(\kappa-\delta)^2}, \quad W_2 := \frac{8 \eta \kappa}{\kappa-\delta} \sqrt{\frac{Ms\log p}{n}}, \quad W_3:= \frac{6\eta \kappa}{\kappa-\delta} \cdot\sqrt{\frac{o\log n}{n}},\] and note that \(\sqrt B = \frac{\kappa+ \delta}{\kappa - \delta}\). Then the system 38 reduces to the inequalities \[\label{eq:32concise} \begin{cases} W_1 \cdot f\sqrt o \lambda_{\theta, t+1} + W_2 \le \sqrt{s} \lambda_{\beta, t+1},\\ W_1 \cdot f\sqrt s \lambda_{\beta, t+1} + W_3 \le \sqrt{ o} \lambda_{\theta, t+1}. \\ \end{cases}\tag{41}\] The feasible region for \((\sqrt s\lambda_{\beta, t+1}, \sqrt{ o} \lambda_{\theta, t+1})\) is illustrated as the shaded area in Figure 8. Given the update rule \[\begin{align} \lambda_{\beta,t+1} &= (\kappa \times\lambda_{\beta,t}) \vee\lambda_{\beta,\infty},\\ \lambda_{\theta,t+1} &= (\kappa \times\lambda_{\theta,t}) \vee\lambda_{\theta,\infty}, \end{align}\] maintaining the ratio \(\frac{\lambda_{\beta,0}}{\lambda_{\theta,0}} = \frac{\lambda_{\beta,\infty}}{\lambda_{\theta,\infty}}\) ensures that the iterate trajectory \(\{ ( \lambda_{\beta,t}, \lambda_{\theta,t} ) \}_{t \ge 0}\) follows a linear path toward the origin, such as the solid purple or dashed red rays shown in Figure 8. Specifically, in the case \(1-W_1^2 f^2 > 1/2\), i.e., \[n > 32 \frac{\eta^2 \kappa^2 C_M^2}{(\kappa-\delta)^4} (s\log p + o \log n),\] the target purple endpoint \(\left( \sqrt s\lambda_{\beta,\infty} = 2W_2 +2 f W_1 W_3 ,~ \sqrt o \lambda_{\theta, \infty} =2W_3 +2f W_1 W_2 \right)\) lies within the feasible region. Consequently, the purple ray (passing through this endpoint and maintaining \(\frac{\lambda_{\beta,t}}{\lambda_{\theta,t}} = \frac{\lambda_{\beta,\infty}}{\lambda_{\theta,\infty}}\)) constitutes a valid threshold update trajectory.

Therefore, by using the thresholds in 25 , we prove that \[\begin{align} \| \beta^{t+1}_{S^c} \|_0 < B s,& \quad \|\theta^{t+1}_{O^c}\|_0 < B o,\\ \| \beta^{t+1} - \beta^* \|_2 \le (\sqrt B+1) \cdot \sqrt s \lambda_{\beta, t+1},& \quad \| \theta^{t+1} - \theta^* \|_2 \le (\sqrt B+1) \cdot \sqrt o \lambda_{\theta, t+1} \end{align}\] hold simultaneously in the (\(t+1\))-th iteration, which completes the proof of Theorem 1.

8.4 Threshold initialization↩︎

Here we provide some practical guidance for selecting the initial tuning parameters \(\lambda_{\beta,0}\) and \(\lambda_{\theta,0}\). With a probability greater than \(1-O(p^{-2}+n^{-3})\), we have the decomposition \[\begin{align} \sqrt s \left\| \frac{1}{n}X^\top Y \right\|_\infty \ge & \left\| \left( \frac{1}{n}X^\top Y\right)_{S^*} \right\|_2\\ \ge &\left\| \left( \frac{1}{n}X^\top X\right)_{S^*,S^*} \beta^*_{S^*} \right\|_2 - \left\| \left( \frac{1}{\sqrt n}X^\top \theta^*\right)_{S^* } \right\|_2 - \left\| \left(\Xi\right)_{S^* } \right\|_2 \\ \ge & \frac{1}{2M}\left\| \beta^* \right\|_2 - f\left\| \theta^* \right\|_2 - 4\sqrt M \sqrt{\frac{s\log p}{n}}, \end{align}\] and \[\begin{align} \sqrt o \left\| \frac{1}{\sqrt{n}} Y \right\|_\infty \ge & \left\| \left( \frac{1}{\sqrt{n}} Y\right)_{O^*} \right\|_2\\ \ge &\left\|\theta^*\right\|_2 - \left\| \left( \frac{1}{\sqrt n} X \beta^*\right)_{O^* } \right\|_2 - \left\| \frac{1}{\sqrt n} \xi_{O^* } \right\|_2 \\ \ge & \left\|\theta^*\right\|_2 - f\left\| \beta^* \right\|_2 - 3\sqrt{\frac{o\log n}{n}}. \end{align}\] For both inequalities, the final step relies on the restricted incoherence property given in Proposition 1, with \(C_1 = 1\). And the sample-size assumption on which Proposition 1 depends is fulfilled under the sample condition presented in Section 8.1.

By combining these inequalities, we obtain \[\sqrt s \left\| \frac{1}{n}X^\top Y \right\|_\infty + 4\sqrt M \sqrt{\frac{s\log p}{n}} + f \sqrt o \left\| \frac{1}{\sqrt{n}} Y \right\|_\infty + 3f\sqrt{\frac{o\log n}{n}} \ge \left( \frac{1}{2M} - f^2\right) \left\| \beta^* \right\|_2.\] Then, under the assumption \(n \ge 4M C_M^2(s\log p + o \log n)\), it follows that \[\frac{\| \beta^*\|_2}{\sqrt s} \le 4M\left( 4 + \left\| \frac{1}{n}X^\top Y \right\|_\infty + \left\| Y \right\|_\infty \right).\] Similarly, by \(4Mf^2 \le 1\), \(M >1\) and \[\sqrt o \left\| \frac{1}{\sqrt{n}} Y \right\|_\infty +3\sqrt{\frac{o\log n}{n}} + 2Mf \sqrt s \left\| \frac{1}{n}X^\top Y \right\|_\infty + 2Mf 4\sqrt M \sqrt{\frac{s\log p}{n}} \ge (1-2Mf^2) \left\|\theta^*\right\|_2,\] we have \[\frac{\| \theta^*\|_2}{\sqrt o} \le 8\sqrt M+ 2 \left\| \frac{1}{\sqrt{n}} Y \right\|_\infty + \left\| \frac{1}{\sqrt n}X^\top Y \right\|_\infty .\] Consequently, with probability at least \(1-O(p^{-2}+n^{-3})\), we can construct valid initial thresholds \(\lambda_{\beta,0}\) and \(\lambda_{\theta,0}\) based on \[\begin{align} \lambda_{\beta,0} \ge &~ 4M\left( 4 + \left\| \frac{1}{n}X^\top Y \right\|_\infty + \left\| Y \right\|_\infty \right)+ \lambda_{\beta,\infty},\\ \lambda_{\theta,0} \ge&~ 8\sqrt M+ 2 \left\| \frac{1}{\sqrt{n}} Y \right\|_\infty + \left\| \frac{1}{\sqrt n}X^\top Y \right\|_\infty + \lambda_{\theta,\infty}. \end{align}\]

9 Proof of Theorem 2↩︎

Throughout this proof, Assumption 2 is used in the same concrete form as in the proof of Theorem 1, i.e., \(n\ge C_{\mathrm{Th1}} (s\log p+o\log n)\). The proof of Theorem 2 proceeds in two steps. First, we introduce some useful preliminaries. Then, we prove that, under Assumption 3, a carefully chosen stopping time yields an error bound sharper than Theorem 1.

9.1 Preliminary↩︎

By Lemma 1, we have \[\begin{align} \mathbf{P}\left\{\underbrace{ \frac{1}{n} \left\| X_{\cdot S^*}^\top \xi \right\|_2 \le \sqrt{\frac{4Ms +6M \log(1/\varrho)}{n}} }_{=:\mathcal{E}'} \right\} \ge 1- O\left(p^{-2s} + \varrho \right), \end{align}\] and this proof is based on the event \(\mathcal{E}' \cap \mathcal{E} \cap \mathcal{E}_X\).

In the second-stage iteration, we apply the thresholds of the same values as the endpoints in 25 : \[\lambda_{\beta} = \lambda_{\beta, \infty}, \quad \lambda_{\theta} = \lambda_{\theta, \infty},\] therefore, by Theorem 1, with a probability greater than \(1 - O(p^{-2} + n^{-3})\) we have the following \[\begin{align} \| \tilde{\beta}^{t}_{S^{*c}} \|_0 \le B s,& \quad \| \tilde{\theta}^{t}_{O^{*c}} \|_0 \le B o,\tag{42}\\ \| \tilde{\beta}^t - \beta^* \|_2 \le (\sqrt B+1) \cdot \sqrt s \lambda_{\beta},& \quad \| \tilde{\theta}^{t} - \theta^* \|_2 \le (\sqrt B+1) \cdot \sqrt o \lambda_{\theta}, \tag{43} \end{align}\] hold for all \(t\ge 0\), regardless of whether Assumption 3 holds (the definition of \(B\) follows 24 ). Moreover, as Assumption 3 holds, i.e., \[\label{eq:32betamin32in32th2} \min_{i \in S^*} |\beta_i^*| \ge \left( \frac{4 \kappa}{\kappa-\delta} + \frac{\kappa-\delta}{4 \kappa} \right) \cdot \lambda_\beta ,\tag{44}\] we can further prove a sharper error bound of \(\tilde{\beta}^t\). Before we prove this refined bound, we rewrite the decomposition as \[\begin{align} \tilde{H}_{\beta}^{t+1} :=& \tilde{\beta}^t + \frac{\eta}{n}X^{\top}(Y - X \tilde{\beta}^t - \sqrt{n} \tilde{\theta}^t) \\ = &\beta^* + \Phi(\beta^* - \tilde{\beta}^t) + \frac{\eta}{\sqrt n} X^\top (\theta^* - \tilde{\theta}^t) + \eta\Xi \in \mathbb{R}^p,\\ \tilde{H}_{\theta}^{t+1} :=&\tilde{\theta}^t + \frac{\eta}{\sqrt{n}}(Y - X \tilde{\beta}^t - \sqrt{n}\tilde{\theta}^t)\\ =& \theta^* + (\eta-1) (\theta^* - \tilde{\theta}^t) + \frac{\eta}{\sqrt n} X (\beta^* -\tilde{\beta}^t) + \frac{\eta}{\sqrt n} \xi \in \mathbb{R}^n. \end{align}\]

9.2 Sharper bound under Assumption 3↩︎

In the second-stage iteration, by 42 we guarantee the sparsity of solution sequences \(\left\{ \tilde{\beta}^t \right\}_{t \ge 0}\) and \(\left\{ \tilde{\theta}^t \right\}_{t \ge 0}\). Then, under the event \(\mathcal{E}' \cap \mathcal{E} \cap \mathcal{E}_X\), for every \(t \ge 0\) we have \[\label{eq:32th632beta-min} \begin{align} &\sum_{i \in S^*} \left( \tilde{H}_{\beta,i}^{t+1} \right)^2 \mathbf{1}(| \tilde{H}_{\beta,i}^{t+1}|< \lambda_{\beta})\\ \le & \sum_{i \in S^*} \lambda_{\beta}^2 \cdot \mathbf{1} \left( |\beta^*_i| - \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle \right| - \eta\left|\Xi_i \right| < \lambda_{\beta} \right)\\ \le & \sum_{i \in S^*} \lambda_{\beta}^2 \cdot \mathbf{1} \left( \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* -\tilde{\theta}^t \rangle \right| > |\beta_i^*| - \lambda_\beta - \eta \|\Xi\|_\infty \ge \frac{3 \kappa + \delta}{\kappa - \delta}\lambda_\beta \right)\\ \le & \left(\frac{\kappa - \delta}{3 \kappa + \delta} \right)^2 \sum_{i \in S^*} \left( \langle \Phi_{\cdot i}, \beta^* -\tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle \right)^2, \end{align}\tag{45}\] where the second inequality follows from the signal condition 44 and the fact \(\|\eta\Xi\|_\infty \le \frac{\kappa - \delta}{4 \kappa } \lambda_\beta\) under the event \(\mathcal{E}\).

On the set \(\tilde{S}^{t+1} \setminus S^*\), by \(\|\eta\Xi\|_\infty \le \frac{\kappa - \delta}{4 \kappa } \lambda_\beta\) we have \[\label{absurd32beta5} \begin{align} &\sum_{i \in \tilde{S}^{t+1} \setminus S^*} (\eta \Xi_i)^2 \mathbf{1}\{ | \tilde{H}_{\beta,i}^{t+1}|\geq \lambda_{\beta} \}\\ \leq& \sum_{i \in \tilde{S}^{t+1} \setminus S^* } (\eta \Xi_i)^2 \mathbf{1} \left\{ \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle \right| \ge \lambda_\beta - \| \eta\Xi\|_\infty \ge \frac{3\kappa + \delta}{\kappa -\delta} \|\eta \Xi \|_\infty \right\} \\ \leq& \left( \frac{\kappa-\delta}{3 \kappa + \delta}\right)^2 \sum_{i \in \tilde{S}^{t+1} \setminus S^* } \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle \right|^2. \end{align}\tag{46}\] Therefore, \[\label{eq:32th632upper32bound1} \begin{align} &\quad \quad \|\tilde{\beta}^{t+1} - \beta^*\|_2 \\ &\le \Bigg\{ \sum_{i \in S^*}\left( - \tilde{H}_{\beta,i}^{t+1} \mathbf{1}(| \tilde{H}_{\beta,i}^{t+1}|< \lambda_{\beta}) + \langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta }{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle + \eta \Xi_i \right)^2 \\ &\quad \quad \left.+ \sum_{i \in \tilde{S}^{t+1}\setminus S^*}\left( \langle \Phi_{\cdot i}, \beta^* -\tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle + \eta\Xi_i \mathbf{1} \left( | \tilde{H}_{\beta,i}^{t+1}|\geq \lambda_{\beta} \right) \right)^2 \right\}^{1/2}\\ &\le \sqrt{\sum_{i \in \tilde{S}^{t+1} \cup S^*} \langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle^2 } + \sqrt{\sum_{i \in \tilde{S}^{t+1} \cup S^*} \frac{\eta^2}{n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle^2 } + \eta \sqrt{\sum_{i \in S^*} \Xi_i^2 } \\ &\quad + \sqrt{\sum_{i \in S^*} \left( \tilde{H}_{\beta,i}^{t+1} \right)^2 \mathbf{1}(| \tilde{H}_{\beta,i}^{t+1}|< \lambda_{\beta}) + \sum_{i \in \tilde{S}^{t+1}\setminus S^*} (\eta\Xi_i)^2 \mathbf{1} \left(| \tilde{H}_{\beta,i}^{t+1}|\ge \lambda_{\beta} \right) } \\ &\leq \frac{ 4 \kappa\delta}{3\kappa + \delta} \| \tilde{\beta}^t - \beta^*\|_2 + \frac{ 8 \kappa^2 \eta}{(3\kappa + \delta)(\kappa - \delta)} \cdot f \| \tilde{\theta}^t - \theta^* \|_2 + \eta \sqrt{\frac{4Ms +6M \log(1/\varrho)}{n}}, \end{align}\tag{47}\] where the last inequality follows from 45 , 46 , the sparsity results 42 and the event \(\mathcal{E}'\). Combining 47 and 43 , with a constant \(C_1\) (depending only on \(\kappa, \eta\), and \(M\)), we have \[\| \tilde{\beta}^{t+1} - \beta^*\|_2 \le \frac{ 4 \kappa\delta}{3\kappa + \delta} \| \tilde{\beta}^t - \beta^*\|_2 + C_1\left( \sqrt{\frac{s + \log (1/\varrho)}{n} } + \frac{s \log p + o \log n}{n} \right),\] by \(4 \kappa\delta < 3 \kappa + \delta\), we further get that \[\| \tilde{\beta}^{t} - \beta^*\|_2 \le \left( \frac{ 4 \kappa\delta}{3\kappa + \delta} \right)^t \cdot \| \tilde{\beta}^0 - \beta^*\|_2 + \frac{C_1}{1- \frac{4\kappa \delta}{3 \kappa + \delta}} \left( \sqrt{\frac{s + \log (1/\varrho)}{n} } + \frac{s \log p + o \log n}{n} \right)\] holds for every \(t\ge 0\). Additionally, from Theorem 1, we have \[\mathbf{P}\left\{ \| \tilde{\beta}^0 - \beta^*\|_2^2 \lesssim \frac{s\log p}{n} + \frac{o^2 \log^{2 } n}{n^2} \right\} \ge 1- O\left(p^{-2} + n^{-3} \right).\] Therefore, with a sufficiently large constant \(C_2\), for every \(t \ge C_2 \log n\), with a probability greater than \(1-\varrho -O(p^{-2}+n^{-3})\) we get the sharper error bound: \[\| \tilde{\beta}^{t} - \beta^*\|_2 \lesssim \sqrt{\frac{s +\log (1/\varrho)}{n}} + \frac{s\log p+ o \log n}{n}.\] Combining this bound and 42 , we complete the proof of Theorem 2.

10 Proof of Corollary 1↩︎

Sharper error bound: Under the beta-min Assumption 3 and taking \(\varrho = p^{-2}\), from Theorem 2 we learn that \[\label{eq:32sharp32bound} \| \tilde{\beta}^t - \beta^*\|_2 \le C\left( \sqrt{\frac{s + \log p}{n}} + \frac{s\log p+ o \log n}{n} \right),\tag{48}\] holds for every \(t \ge C_2 \log n\), with a probability greater than \(1-O(p^{-2}+n^{-3})\).

On true support: On the true support \(S^* = \text{supp}(\beta^*)\), we have \[\label{eq:32almost32full} \begin{align} \left | \text{supp}(\beta^*) - \text{supp}(\tilde{\beta}^t)\right | &= \sum_{i\in S^*}\mathbf{1}\{ | \tilde{H}^{t}_{\beta,i}| < \lambda_{\beta} \}\\ &\overset{(i)}\le \sum_{i\in S^*} \mathbf{1} \left( \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* -\tilde{\theta}^t \rangle \right| > \frac{3 \kappa + \delta}{\kappa - \delta}\lambda_\beta \right)\\ &\lesssim \sum_{i\in S^*} \frac{ \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* -\tilde{\theta}^t \rangle \right|^2}{\lambda_{\beta}^2}\\ &\lesssim \frac{\| \beta^* - \tilde{\beta}^t \|_2^2 + f^2 \| \theta^* - \tilde{\theta}^t \|_2^2 }{ \lambda_\beta^2 }\\ &\overset{(ii)}\lesssim \frac{\frac{s+ \log p}{n}+\left( \frac{s\log p}{n} \right)^2 + \left( \frac{o\log n}{n} \right)^2 }{\frac{s\log p}{n} + \left( \frac{o\log n}{n} \right)^2 }\cdot s\\ & \overset{(iii)}= \left(\frac{1}{\log p} + \frac{1}{s} + \frac{s\log p}{n} + o(1) \right) \cdot s\\ &= o(s), \end{align}\tag{49}\] where inequality (i) comes from 45 , inequality (ii) comes from the sharper bound 48 and 43 , and inequality (iii) comes from the condition \(n \succ s\log p \succ \frac{o^2\log^{2}n}{n }\).

On non-support: By \(\sum_{i\notin S^*}\mathbf{1}(\tilde{\beta}^t_i\neq 0)\leq B s\), we conclude that \[\begin{align} & \quad\left|\text{supp}(\tilde{\beta}^t) - \text{supp}(\beta^*) \right| = \sum_{i\notin S^*}\mathbf{1}\{ | \tilde{H}^{t}_{\beta,i}|\ge \lambda_{\beta} \}\\ &\overset{(i)}\leq \sum_{i\notin S^*} \mathbf{1} \left\{ \left|\langle \Phi_{\cdot i}, \beta^* - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^* - \tilde{\theta}^t \rangle \right| \ge \lambda_\beta - \| \eta\Xi\|_\infty \ge \frac{3\kappa + \delta}{4 \kappa} \lambda_\beta \right\}\\ &=o(s), \end{align}\] where inequality follows from 46 , and the last equation comes from a similar process in 49 . Therefore, by taking the stopping time \(t \ge C_2 \log n\) we have \[\mathbf{P} \left\{ \left | \text{supp}(\beta^*)\; \triangle \;\text{supp}(\tilde{\beta}^t)\right | = o(s) \right\} \ge 1 - O(p^{-2} + n^{-3}),\] which completes the proof of Corollary 1.

11 Proof of Theorem 3↩︎

Throughout this proof, Assumption 2 is used in the concrete form \[n\ge C_{\mathrm{Th3}}\{s\log p+o\log n\},\] where \(C_{\mathrm{Th3}}\) is a fixed constant depending only on \(M,\eta,\kappa\), chosen large enough to dominate the concrete sample-size constants used in the proof of Theorem 1, Lemma 2, and Lemma 3, satisfying: \[C_{\mathrm{Th3}} \ge \max \left\{ C_{\mathrm{Th1}},~30M^2 C_{\Sigma}, ~ 6M C_M^2, ~ \frac{16C_M^2}{(\kappa-\delta)^4} \right\}.\] The proof of Theorem 3 proceeds in three steps: First, we introduce some useful preliminaries. Second, by mathematical induction, we prove that, under beta-min and theta-min conditions, i.e., Assumptions 3 and 4, the output of Algorithm 2 converges to the oracle estimation \(\beta^\dagger\). Finally, we derive the variable selection consistency.

11.1 Preliminary↩︎

Assume \(supp(\theta^*) \ne \emptyset\). For ease of exposition, we will denote \((O^*)^c\) as \(-O^*\) throughout the following proof. Recall the formula of the oracle estimation: \[\label{oracle32solution} \begin{align} \beta^{\dagger}_{S^*} &:= \beta^{*}_{S^*} + (X^{\top}_{-O^*,S^*}X_{-O^*,S^*})^{-1}X_{-O^*,S^*}^{\top}\xi_{-O^*} \in \mathbb{R}^{|S^*|}, \\ \beta^{\dagger}_{-S^*} &:= \mathbf{0} \in \mathbb{R}^{p-|S^*|},\\ \theta^{\dagger}_{O^*} &:= \theta^{*}_{O^*} + \frac{1}{\sqrt{n}} \Big\{ \xi_{O^*} - X_{O^*,S^*}(X_{-O^*,S^*}^{\top}X_{-O^*,S^*})^{-1}X^{\top}_{-O^*,S^*}\xi_{-O^*} \Big\} \in \mathbb{R}^{|O^*|},\\ \theta^{\dagger}_{-O^*} &:= \mathbf{0} \in \mathbb{R}^{n-|O^*|}. \end{align}\tag{50}\]

Therefore, we can rewrite the decomposition in the second-stage algorithm as: \[\begin{align} \tilde{H}_{\beta}^{t+1} =& \tilde{\beta}^t + \frac{\eta}{n}X^{\top}(Y - X \tilde{\beta}^t - \sqrt{n} \tilde{\theta}^t) \\ = & \beta^{\dagger} + \Phi(\beta^{\dagger} - \tilde{\beta}^{t}) + \frac{\eta}{\sqrt{n}} X^{\top}(\theta^{\dagger} - \tilde{\theta}^{t}) + \eta\Xi^{\dagger}, \\ \tilde{H}_{\theta}^{t+1} =& \tilde{\theta}^t + \frac{\eta}{\sqrt{n}}(Y - X \tilde{\beta}^t - \sqrt{n}\tilde{\theta}^t) \\ = &\theta^{\dagger} + (\eta-1) (\theta^\dagger - \tilde{\theta}^t) + \frac{\eta}{\sqrt n} X (\beta^{\dagger} - \tilde{\beta}^{t}) + \frac{\eta}{\sqrt{n}}\xi^{\dagger}, \end{align}\] where \[\begin{align} \Xi_{S^*}^\dagger &:= \mathbf{0} \in \mathbb{R}^{|S^*|},\\ \Xi_{-S^*}^\dagger &:= \frac{1}{n}X_{-O^*,-S^*}^{\top} \Big\{ I_{n-o} - X_{-O^*,S^*}(X_{-O^*,S^*}^{\top}X_{-O^*,S^*})^{-1}X_{-O^*,S^*}^{\top} \Big\} \xi_{-O^*} \in \mathbb{R}^{p-|S^*|},\\ \xi_{O^*}^\dagger &: = \mathbf{0} \in \mathbb{R}^{|O^*|}, \end{align}\] and \[\begin{align} \xi_{-O^*}^\dagger &:= \Big\{ I_{n-o} - X_{-O^*,S^*}(X_{-O^*,S^*}^{\top}X_{-O^*,S^*})^{-1}X_{-O^*,S^*}^{\top} \Big\} \xi_{-O^*} \in \mathbb{R}^{n-|O^*|}. \end{align}\]

We specify Assumptions 3 and 4 as \[\label{eq:32betathetamin} \begin{align} \min_{i \in S^*} |\beta_i^*| \ge \frac{4 \kappa}{\kappa - \delta} \lambda_\beta + 5 \sqrt{\frac{M \log p}{n}} , \quad \min_{k \in O^*} |\theta_k^*| \ge \frac{4 \kappa}{\kappa - \delta} \lambda_\theta + 4 \sqrt{\frac{\log n}{n}}, \end{align}\tag{51}\] where \(\lambda_\beta = \lambda_{\beta, \infty}\) and \(\lambda_\theta = \lambda_{\theta, \infty}\) follows from 25 . Define the event \[\begin{align} \mathcal{E}_{oracle}: = \begin{Bmatrix} \|\Xi^{\dagger} \|_\infty < 4 \sqrt{\frac{M \log p}{n} } , & \left\|\frac{\xi^{\dagger} }{\sqrt{n}} \right\|_\infty < 3 \sqrt{\frac{\log n}{n}} ;& \\ \left\|\beta^{\dagger} -\beta^{*}\right\|_\infty < 5 \sqrt{\frac{M \log p}{n}} , & \left\|\theta^{\dagger} -\theta^{*}\right\|_\infty < 4 \sqrt{\frac{\log n}{n}} . \end{Bmatrix} \end{align}\] And the following proof is based on the event \(\mathcal{E}_{oracle} \cap \mathcal{E}_X\), which holds with a probability greater than \(1- O(p^{-2} + n^{-3} )\) by Lemma 2 and Proposition 1.

11.2 Convergence to oracle estimation↩︎

Similar to 45 , under the event \(\mathcal{E}_{oracle}\) and the beta-min condition in 51 , we have \[\label{eq:32th832beta-min} \begin{align} &\sum_{i \in S^*} \left( \tilde{H}_{\beta,i}^{t+1} \right)^2 \mathbf{1}(| \tilde{H}_{\beta,i}^{t+1}|< \lambda_{\beta}) \\ \le & \sum_{i \in S^*} \lambda_{\beta}^2 \cdot \mathbf{1} \left( |\beta^{\dagger}_i| - \left|\langle \Phi_{\cdot i}, \beta^{\dagger} - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^{\dagger} - \tilde{\theta}^t \rangle \right| < \lambda_{\beta} \right)\\ \le & \sum_{i \in S^*} \lambda_{\beta}^2 \cdot \mathbf{1} \left( \left|\langle \Phi_{\cdot i}, \beta^\dagger - \tilde{\beta}^t \rangle + \frac{1}{\sqrt n}\langle X_{\cdot i}, \theta^\dagger -\tilde{\theta}^t \rangle \right| > |\beta^*_i| - \| \beta^\dagger - \beta^*\|_\infty - \lambda_\beta \ge \frac{3\kappa + \delta}{\kappa - \delta}\lambda_{\beta} \right)\\ \le & \left(\frac{\kappa-\delta}{3\kappa + \delta }\right)^2 \sum_{i \in S^*} \left( \langle \Phi_{\cdot i}, \beta^\dagger -\tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^\dagger - \tilde{\theta}^t \rangle \right)^2, \end{align}\tag{52}\] leading that \[\label{eq:32th832upper32bound1} \begin{align} &\quad \quad \|\tilde{\beta}^{t+1} - \beta^{\dagger}\|_2 \\ &\le \Bigg\{ \sum_{i \in S^*}\left( - \tilde{H}_{\beta,i}^{t+1} \mathbf{1}(| \tilde{H}_{\beta,i}^{t+1}|< \lambda_{\beta}) + \langle \Phi_{\cdot i}, \beta^{\dagger} - \tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^{\dagger} - \tilde{\theta}^t \rangle \right)^2 \\ &\quad \quad \left.+ \sum_{i \in \tilde{S}^{t+1}\setminus S^*}\left( \langle \Phi_{\cdot i}, \beta^{\dagger} -\tilde{\beta}^t \rangle + \frac{\eta}{\sqrt n}\langle X_{\cdot i}, \theta^{\dagger} - \tilde{\theta}^t \rangle + \eta \Xi_i^\dagger \mathbf{1} \left( | \tilde{H}_{\beta,i}^{t+1}|\geq \lambda_{\beta} \right) \right)^2 \right\}^{1/2}\\ &\le \sqrt{\sum_{i \in \tilde{S}^{t+1} \cup S^*} \langle \Phi_{\cdot i}, \beta^{\dagger} - \tilde{\beta}^t \rangle^2 } + \sqrt{\sum_{i \in \tilde{S}^{t+1} \cup S^*} \frac{\eta^2}{n}\langle X_{\cdot i}, \theta^{\dagger} - \tilde{\theta}^t \rangle^2 } \\ &\quad + \left\{ \sum_{i \in S^*} \left( \tilde{H}_{\beta,i}^{t+1} \right)^2 \mathbf{1}(| \tilde{H}_{\beta,i}^{t+1}|< \lambda_{\beta})\right.\\ &\qquad \quad \left.+ \sum_{i \in \tilde{S}^{t+1}\setminus S^*} \left(\eta \Xi^{\dagger}_i \right)^2 \mathbf{1} \left( \left|\langle \Phi_{\cdot i}, \beta^{\dagger} - \tilde{\beta}^t \rangle + \frac{\eta \langle X_{\cdot i}, \theta^{\dagger} - \tilde{\theta}^t \rangle}{\sqrt n} \right| \ge \lambda_\beta- \|\eta \Xi^\dagger \|_\infty \ge \frac{3\kappa + \delta}{\kappa - \delta} |\eta \Xi^{\dagger}_i| \right) \right\}^{1/2}\\ &\leq \frac{ 4 \kappa }{ 3 \kappa + \delta } \left(\delta \| \tilde{\beta}^t - \beta^{\dagger}\|_2 + \frac{2\kappa \eta}{\kappa - \delta} \cdot f \| \tilde{\theta}^t - \theta^{\dagger} \|_2 \right), \end{align}\tag{53}\] where the second inequality follows from the event \(\mathcal{E}_{oracle}\). The last inequality follows from 52 , the techniques 33 and 34 , and the sparsity result 42 derived in Theorem 2, which holds consistently for every \(t \ge 0\) with a probability greater than \(1- O\left(p^{-2} +n^{-3} \right)\).

Similarly, the event \(\mathcal{E}_{oracle}\) and the theta-min condition in 51 yield that \[\label{eq:32th832theta-min} \begin{align} &\sum_{i \in O^*} \left( \tilde{H}_{\theta,i}^{t+1} \right)^2 \mathbf{1}(| \tilde{H}_{\theta,i}^{t+1}|< \lambda_{\theta})\\ \le & \sum_{i \in O^*} \lambda_{\theta}^2 \cdot \mathbf{1} \left( \left| ({ \eta }-1) (\theta^\dagger_i - \tilde{\theta}^t_i ) + \frac{ \eta }{\sqrt n} X_{i \cdot} (\beta^{\dagger} - \tilde{\beta}^{t}) \right| > |\theta_i^*| - \|\theta^\dagger - \theta^* \|_\infty - \lambda_\theta \ge \frac{3\kappa + \delta}{\kappa - \delta}\lambda_{\theta} \right)\\ \le & \left( \frac{\kappa - \delta}{3\kappa + \delta} \right)^2 \sum_{i \in O^*} \left( ({ \eta }-1) (\theta^\dagger_i - \tilde{\theta}^t_i ) + \frac{ \eta }{\sqrt n} X_{i \cdot} (\beta^{\dagger} - \tilde{\beta}^{t}) \right)^2, \end{align}\tag{54}\] which leads to \[\label{eq:32th832upper32bound2} \begin{align} &\quad \quad \|\tilde{\theta}^{t+1} - \theta^{\dagger}\|_2 \\ &\le \Bigg\{ \sum_{i \in O^*}\left( - \tilde{H}_{\theta,i}^{t+1} \mathbf{1}(| \tilde{H}_{\theta,i}^{t+1}|< \lambda_{\theta}) + ({ \eta }-1) (\theta^\dagger_i - \tilde{\theta}^t_i ) + \frac{ \eta }{\sqrt n} X_{i \cdot} (\beta^{\dagger} - \tilde{\beta}^{t}) \right)^2 \\ &\quad \quad \left.+ \sum_{i \in \tilde{O}^{t+1}\setminus O^*}\left( ({ \eta }-1) (\theta^\dagger_i - \tilde{\theta}^t_i ) + \frac{ \eta }{\sqrt n} X_{i \cdot} (\beta^{\dagger} - \tilde{\beta}^{t}) + \frac{\eta}{\sqrt{n}}\xi_i^\dagger \mathbf{1} \left( | \tilde{H}_{\theta,i}^{t+1}|\geq \lambda_{\theta} \right) \right)^2 \right\}^{1/2}\\ &\le \sqrt{\sum_{i \in \tilde{O}^{t+1} \cup O^*} \left( ({ \eta }-1) (\theta^\dagger_i - \tilde{\theta}^t_i ) + \frac{ \eta }{\sqrt n} X_{i \cdot} (\beta^{\dagger} - \tilde{\beta}^{t}) \right)^2 }\\ &\quad + \left\{ \sum_{i \in O^*} \left( \tilde{H}_{\theta,i}^{t+1} \right)^2 \mathbf{1}(| \tilde{H}_{\theta,i}^{t+1}|< \lambda_{\theta}) \right.\\ &\qquad \quad \left.+ \sum_{i \in \tilde{O}^{t+1}\setminus O^*} \left( \frac{\eta \xi^{\dagger}_i}{\sqrt n}\right)^2 \mathbf{1} \left( \left| ({ \eta }-1) (\theta^\dagger_i - \tilde{\theta}^t_i ) + \frac{ \eta }{\sqrt n} X_{i \cdot} (\beta^{\dagger} - \tilde{\beta}^{t}) \right| \ge \lambda_\theta - \left|\frac{\eta \xi^{\dagger}_i}{\sqrt{n}}\right| \ge \frac{3\kappa + \delta}{\kappa - \delta} \left|\frac{\eta \xi^{\dagger}_i}{\sqrt{n}}\right| \right) \right\}^{1/2}\\ &\leq \frac{4 \kappa }{3 \kappa + \delta } \left( \delta \| \tilde{\theta}^t - \theta^{\dagger}\|_2 + \frac{2 \kappa \eta}{\kappa - \delta} \cdot f \| \tilde{\beta}^t - \beta^{\dagger}\|_2 \right). \end{align}\tag{55}\] Combining 53 and 55 , we conclude that \[\label{eq:32dynamic32sol} \begin{align} \|\tilde{\beta}^{t} - \beta^{\dagger}\|_2 \le& \left(\frac{4 \kappa \delta }{3 \kappa + \delta } + \frac{8 \kappa^2 \eta \cdot f }{(3 \kappa + \delta)(\kappa - \delta) } \right)^{t} \cdot \frac{ \|\tilde{\beta}^{0} - \beta^{\dagger}\|_2 + \|\tilde{\theta}^{0} - \theta^{\dagger}\|_2}{2}\\ &+ \left(\frac{4 \kappa \delta }{3 \kappa + \delta } - \frac{8 \kappa^2 \eta \cdot f }{(3 \kappa + \delta)(\kappa - \delta) } \right)^{t} \cdot \frac{ \|\tilde{\beta}^{0} - \beta^{\dagger}\|_2 - \|\tilde{\theta}^{0} - \theta^{\dagger}\|_2}{2}, \\ \le & \left(\frac{4 \kappa \delta }{3 \kappa + \delta } + \frac{8 \kappa^2 \eta \cdot f }{(3 \kappa + \delta)(\kappa - \delta) } \right)^{t} \cdot\left( \|\tilde{\beta}^{0} - \beta^{\dagger}\|_2 + \|\tilde{\theta}^{0} - \theta^{\dagger}\|_2\right) \end{align}\tag{56}\] simultaneously hold for every \(t \ge 0\). Define \(C_0:= \|\tilde{\beta}^{0} - \beta^{\dagger}\|_2 + \|\tilde{\theta}^{0} - \theta^{\dagger}\|_2 < \infty\) and \(r : =\frac{4 \kappa \delta }{3 \kappa + \delta } + \frac{8 \kappa^2 \eta \cdot f }{(3 \kappa + \delta)(\kappa - \delta) }\), by the definition of \(f\) in 24 and the sample size assumption \(n \ge \frac{16 C_M^2}{(\kappa - \delta)^4}\cdot ( s\log p + o \log n )\), we conclude that \(r \le \frac{2 \kappa + 4\kappa \delta - 2 \delta}{3 \kappa + \delta} <1\). Therefore, we prove that, with a probability greater than \(1 - O(p^{-2} + n^{-3})\), \[\label{eq:32final32sol} \| \tilde{\beta}^t - \beta^\dagger \|_2 \leq C_0 \times r^t\tag{57}\] holds for every \(t \ge 0\) in the second-stage algorithm.

11.3 Oracle estimation rate↩︎

According to 50 , with a probability greater than \(1- O(p^{-2})\), we have \[\label{oracle32rate321} \begin{align} \|\beta^{\dagger} - \beta^*\|_2 &= \left\| (X^{\top}_{-O^*,S^*}X_{-O^*,S^*})^{-1} X_{-O^*,S^*}^{\top}\xi_{-O^*} \right\|_2 \\ &\leq \frac{3M}{n} \cdot \left\|X_{-O^*,S^*}^{\top}\xi_{-O^*}\right\|_2, \end{align}\tag{58}\] where the last inequality follows from Lemma 3, which implies \[\left\| (X^{\top}_{-O^*,S^*}X_{-O^*,S^*})^{-1} \right\|_2 = \frac{1}{ \Lambda_{\min} \left( X^{\top}_{-O^*,S^*}X_{-O^*,S^*} \right) } \le \frac{3M}{n}.\] For a given design \(X\), from Theorem 2.1 of [48], we learn that \[\label{eq:32oracle32prob} \begin{align} \mathbf{P}_{\xi | X}\Bigg\{ \left\| X_{-O^*,S^*}^\top \xi_{-O^*} \right\|_2^2 \ge& tr\left( X_{-O^*,S^*}^\top X_{-O^*,S^*} \right)+2\left\| X_{-O^*,S^*}^\top X_{-O^*,S^*} \right\|_F\sqrt{u}&\\ &\quad +2\Lambda_{\max}\left( X_{-O^*,S^*}^\top X_{-O^*,S^*} \right) u ~ \Big | ~ X\Bigg\} \le e^{-u}. \end{align}\tag{59}\] Additionally, if \(X \in \mathcal{E}_X\), we further conclude that \[\begin{align} tr\left( X_{-O^*,S^*}^\top X_{-O^*,S^*} \right) \le& tr\left( X_{\cdot,S^*}^\top X_{\cdot,S^*} \right) \le 2Mns,\\ \left\| X_{-O^*,S^*}^\top X_{-O^*,S^*} \right\|_F^2 \le & s \left\| X_{-O^*,S^*}^\top X_{-O^*,S^*} \right\|_2^2 \le s \left\| X_{\cdot,S^*}^\top X_{\cdot,S^*} \right\|_2^2 \le 4M^2 n^2 s,\\ \Lambda_{\max}\left( X_{-O^*,S^*}^\top X_{-O^*,S^*} \right)\le & \left\| X_{\cdot,S^*}^\top X_{\cdot,S^*} \right\|_2 \le 2M n. \end{align}\] Therefore, by taking \(u= \log(1/ \varrho)\) into 59 , we have \[\label{oracle32rate322} \begin{align} & \mathbf{P}_{\xi ,X} \left( \left\| X_{-O^*,S^*}^\top \xi_{-O^*} \right\|_2^2 \ge 2M n( 2s + 3 \log(1/ \varrho)) \right)\\ \le & \mathbf{P}_{\xi ,X} \left( \mathcal{E}_X^c\right) + \mathbf{E}_{X} \left\{ \mathbf{1}(\mathcal{E}_X)\cdot \mathbf{P}_{\xi |X} \left( \left\| X_{-O^*,S^*}^\top \xi_{-O^*} \right\|_2^2 \ge 2M n( 2s + 3 \log(1/ \varrho)) ~ \big| X \right) \right\}\\ \le& 4p^{-2s} + \varrho. \end{align}\tag{60}\] Combining 56 , 58 and 60 , with taking the stopping time \(t \ge \frac{\log(C_0 n) }{\log(1/r)}\), by 57 we guarantee that \[\label{eq:32entry32error} \sup_{i \in [p]}|\beta_i^\dagger - \tilde{\beta}_i^t| \le \|\tilde{\beta}^{t} - \beta^{\dagger}\|_2 \le \frac{1}{n},\tag{61}\] and \[\| \tilde{\beta}^t - \beta^* \|_2 \le \|\tilde{\beta}^{t} - \beta^{\dagger}\|_2 + \|\beta^{\dagger} - \beta^*\|_2 ~\le ~ \frac{1}{n} + 9M^{3/2} \sqrt{\frac{s + \log(1/\varrho)}{n}} ~\asymp ~\sqrt{\frac{s+ \log(1/\varrho)}{n-o}},\] with a probability at least \(1 -\varrho - O(p^{-2} + n^{-3} )\).

11.4 Variable selection consistency↩︎

By 61 , we conclude that:

• For every \(i \in S^*\), under the signal condition 51 we have \[|\tilde{\beta}^t_i| \ge |\beta_i^*| - |\beta_i^\dagger- \beta_i^*| - |\beta_i^\dagger - \tilde{\beta}_i^t| \ge \frac{4 \kappa}{\kappa - \delta} \lambda_{\beta} - \frac{1}{n} > 0,\] which proves that the whole support set \(S^*\) is recovered.

• For every \(i \notin S^*\), we have \[|\tilde{\beta}^t_i| \le |\beta_i^\dagger| + |\beta_i^\dagger - \tilde{\beta}_i^t| \le \frac{1}{n} < \lambda_\beta,\] which proves that we cannot discover any entry on \((S^*)^c\) by using the hard-thresholding parameter \(\lambda_\beta\).

Therefore, with a probability greater than \(1- O(p^{-2} + n^{-3})\), we have \[\text{supp}(\tilde{\beta}^t ) = \text{supp} (\beta^\dagger) = \text{supp} (\beta^*), \quad \text{for every } t \ge C \log n,\] which achieves the variable selection consistency of \(\tilde{\beta}\). Meanwhile, by utilizing the technique similar to 56 , we also establish the convergence of the estimator \(\{\tilde{\theta}^t\}_{t \ge 0}\) to the oracle \(\theta^\dagger\), therefore demonstrating the selection consistency of \(\tilde{\theta}\).

12 Proof of Corollary 2↩︎

For every vector \(\gamma\in \mathbb{R}^s\) with \(\|\gamma\|_2<\infty\), according to Theorem 3, we have \[\sqrt{n}\gamma^{\top} \tilde{\beta}_{S^*} = \sqrt{n}\gamma^{\top}\beta^{\dagger}_{S^*} + o_p(1).\] Therefore, by Slutsky’s Lemma, we only need to prove the asymptotic normality of \(\beta^{\dagger}_{S^*}\). By 50 , \[\begin{align} &\sqrt n \gamma^\top ( \beta^{\dagger}_{S^*} - \beta^*_{S^*}) \\ =& \sqrt n \gamma^\top \left(\frac{X^{\top}_{-O^*,S^*}X_{-O^*,S^*}}{n-o} \right)^{-1} \frac{X^{\top}_{-O^*,S^*} \xi_{-O^*}}{n-o} \\ = & \frac{n}{n-o} \cdot \frac{1}{\sqrt n} \gamma^\top \Sigma_{S^*, S^*}^{-1} X_{-O^*,S^*}^{\top}\xi_{-O^*}\\ & + \sqrt n\gamma^\top \Sigma_{S^*, S^*}^{-1} \left\{ \Sigma_{S^*, S^*} - \frac{X^{\top}_{-O^*,S^*}X_{-O^*,S^*}}{n-o} \right\} \left(\frac{X^{\top}_{-O^*,S^*}X_{-O^*,S^*}}{n-o} \right)^{-1} \frac{X_{-O^*,S^*}^{\top}\xi_{-O^*}}{ n - o}\\ = & \frac{n}{n-o} \cdot\frac{1}{\sqrt n} \gamma^\top \Sigma_{S^*, S^*}^{-1} X_{-O^*,S^*}^{\top}\xi_{-O^*} + O_p\left( \frac{ n s \log p}{ (n-o)^{3/2}}\right) . \end{align}\] where the last equality follows from 60 and a similar technique used in 20 . Define \(\epsilon_i := \frac{1}{\sqrt n} \gamma^\top \Sigma_{S^*, S^*}^{-1} X^{\top}_{i,S^*}\xi_{i}\). Clearly, \(\{\epsilon_i\}_{i \in -O^*}\) are independent and zero-mean, and \[\label{Lyapunov321} \begin{align} \sum_{i\in -O^*} \text{Var}(\epsilon_i) = \sum_{i\in -O^*} \frac{1}{n} c_{\xi}\sigma^2\gamma^{\top}\Sigma_{S^*, S^*}^{-1} \gamma \geq \frac{c_{\xi}\sigma^2\|\gamma\|^2_2}{2M}, \end{align}\tag{62}\] where \(c_{\xi} = \frac{\text{var}(\xi_i)}{\sigma^2}\) is a posotive constant. By the Cauchy-Schwarz inequality, we have \[\begin{align} \sum_{i\in - O^*}\mathbf{E} |\epsilon_i|^3 &= n^{-3/2}\sum_{i\in - O^*} \mathbf{E} \left( | \gamma^{\top} \Sigma_{ S^*, S^*}^{-1} X^{\top}_{i, S^*} |^3 \right) \cdot \mathbf{E} |\xi_i|^3\\ & \lesssim \frac{\|\gamma\|^3_2 \cdot \| \Sigma_{ S^*, S^*}^{-1}\|_2^3 \cdot \mathbf{E} (\|X^{\top}_{i, S^*} \|_2^3) \cdot\sigma^3 }{n^{1/2}} \\ & \lesssim \frac{\sigma^3 s^{3/2}}{n^{1/2}} \|\gamma\|^3_2~ , \end{align}\] where the last inequality comes from the property of sub-Gaussian random variable. Since \[\begin{align} \frac{\sum_{i\in - O^*}\mathbf{E} |\epsilon_i|^3 }{ \left(\sum_{i\in -O^*} \text{Var}(\epsilon_i) \right)^{3/2}} \lesssim s^{3/2} n^{-1/2}, \end{align}\] by Lyapunov’s central limit theorem and Slutsky’s Lemma, with \(n \succ s^3,~ n\gtrsim o \log n\), we conclude that \[\frac{1}{\sqrt n} \gamma^\top \Sigma_{S^*, S^*}^{-1} X_{-O^*,S^*}^{\top}\xi_{-O^*} \overset{D}\to \mathcal{N} \left(0\;,\;c_{\xi}\sigma^2\gamma^{\top} \Sigma_{S^*, S^*}^{-1} \gamma \right).\] Furthermore, combining with \(\sqrt n \succ s \log p\), we get \[\sqrt{n}\gamma^{\top}( \tilde{\beta}_{S^*} - \beta^*_{S^*}) \overset{D}\to \mathcal{N} \left(0\;,\;c_{\xi}\sigma^2\gamma^{\top} \Sigma_{S^*, S^*}^{-1} \gamma \right)\] for every \(\gamma\in \mathbb{R}^s\) with \(\|\gamma\|_2<\infty\). Therefore, we complete the proof of Corollary 2.

13 Proof of minimax lower bounds↩︎

The proof of lower bounds proceeds in three steps. We first follow the proof technique in [14] and get an estimation lower bound of the \(\epsilon\)-contamination model. Then, we employ a Bayesian method to connect our empirical contamination model with the \(\epsilon\)-contamination model, thereby establishing Theorem 4. We finally apply a similar technique to obtain the lower bound for variable selection, and complete the proof of Theorem 5.

For ease of display, we denote by \(\pi_{\Sigma} (X_{i,\cdot})\) the distribution of the \(i\)-th observation \(X_{i, \cdot} \in \mathbb{R}^p\) for each uncontaminated index \(i\). We also assume the noise \(\xi_i\) follows from a Gaussian distribution \(\mathcal{N} (0, \sigma^2)\) independently for each \(i \in [n]\).

13.1 Estimation lower bound related to \(\epsilon'\)-contamination model↩︎

We assume \(s\) is an even number, and construct two coefficient vectors as \[\label{eq:32beta12} \begin{align} \beta^{(1)} & := (\underbrace{\lambda, \cdots, \lambda}_{s}~,~ \underbrace{0, \cdots, 0 }_{p-s})^\top \in \mathbb{R}^p,\\ \beta^{(2)} & := (\underbrace{0, \cdots, 0 }_{s/2}~, ~\underbrace{\lambda, \cdots, \lambda}_{s}~,~ \underbrace{0, \cdots, 0 }_{p- {3s}/2} )^\top \in \mathbb{R}^p, \end{align}\tag{63}\] where \(\lambda = \sqrt{\frac{1}{8C_{2s}}}\cdot \frac{\sigma}{\sqrt s} \cdot \frac{ o}{n}\). Let \(\mathbf{P}_{1}\) denote the joint distribution of \((X_{i\cdot}, Y_i)\) given \(\beta^{(1)}\), where assume that \(X_{i,\cdot} \in \mathbb{R}^{1 \times p}\) has marginal density function \(\pi_\Sigma(\cdot)\) and, conditional on \(X_{i\cdot}\) and \(\beta^{(1)}\), \(Y_i\) follows a normal distribution \(\mathcal{N}( X_{i,\cdot} \beta^{(1)}, \sigma^2)\). Similarly, we define \(\mathbf{P}_{2}\) as the joint distribution of \((X_{i\cdot}, Y_i)\) given \(\beta^{(2)}\). It is straightforward to learn that \[\begin{align} 0< \left\{ TV(\mathbf{P}_1 , \mathbf{P}_2 ) \right\}^2 ~\le& KL(\mathbf{P}_1 \| \mathbf{P}_2 )\\ =& \frac{1}{2\sigma^2} \left( \beta^{(1)} - \beta^{(2)} \right)^\top \Sigma \left( \beta^{(1)} - \beta^{(2)} \right) \\ \overset{(i)}\le& \frac{C_{2s}}{2\sigma^2} \cdot s \lambda^2\\ = & \left( \frac{o}{4n} \right)^2 ~< ~ \left( \frac{o/(4n)}{1- o/(4n)} \right)^2, \end{align}\] where inequality (i) follows from \(\sup_{S\subset [p]: |S| \le 2s} \Lambda_{1}(\Sigma_{S,S}) \le C_{2s}\) and the construction in 63 . We then define \(\epsilon' := \frac{TV(\mathbf{P}_1 , \mathbf{P}_2 )}{1+TV(\mathbf{P}_1 , \mathbf{P}_2 )}\), and it is directly to learn that \(0 < \epsilon' < o/(4n)\).

Define density functions \[p_1=\frac{\mathrm d \mathbf{P}_{1}}{\mathrm d\left( \mathbf{P}_{1} + \mathbf{P}_{2}\right)}, \quad p_2=\frac{\mathrm d \mathbf{P}_{2}}{\mathrm d\left( \mathbf{P}_{1} + \mathbf{P}_{2}\right)}.\] Define \(\mathbf{Q}_{1} \text{ and } \mathbf{Q}_{2}\) (both are the joint distributions of \((X_{i\cdot}, Y_i)\)) by their density functions \[\label{eq:32Qs} \begin{align} \frac{\mathrm d \mathbf{Q}_{1}}{\mathrm d \left( \mathbf{P}_{1} + \mathbf{P}_{2}\right)}& =\frac{\left( p_2 -p_1 \right) \cdot \mathbf{1}(p_2 \ge p_1) }{\operatorname{TV}\left( \mathbf{P}_{1}, \mathbf{P}_{2} \right)} ,\\ \frac{ \mathrm d \mathbf{Q}_{2}}{ \mathrm d\left( \mathbf{P}_{1} + \mathbf{P}_{2}\right)}& =\frac{\left( p_1 -p_2 \right) \cdot \mathbf{1}(p_1 > p_2) }{\operatorname{TV}\left( \mathbf{P}_{1}, \mathbf{P}_{2} \right)}. \end{align}\tag{64}\] Following the proof of Theorem 5.1 in [14], it is easy to check that both \(\mathbf{Q}_{1} \text{ and } \mathbf{Q}_{2}\) are well-defined probability measures. It can also be checked that \[\label{eq:32equal} \begin{align} \frac{\mathrm d\left( (1-\epsilon') \mathbf{P}_1 + \epsilon' \mathbf{Q}_1 \right) }{\mathrm d \left( \mathbf{P}_{1} + \mathbf{P}_{2}\right)} & =\left(1-\epsilon'\right) p_{1}+\epsilon^{\prime} \frac{ (p_{2}-p_{1} ) \cdot \mathbf{1}(p_2 \ge p_1)}{\epsilon' / (1-\epsilon')} \\ & =\left(1-\epsilon'\right) p_2 +\epsilon^{\prime} \frac{ (p_1 - p_2 ) \cdot \mathbf{1}(p_1 > p_2)}{\epsilon' / (1-\epsilon')} \\ & = \frac{\mathrm d\left( (1-\epsilon') \mathbf{P}_2 + \epsilon' \mathbf{Q}_2 \right) }{\mathrm d \left( \mathbf{P}_{1} + \mathbf{P}_{2}\right)}. \end{align}\tag{65}\] We construct the prior of \(\beta\) as \[\label{eq:32pi32beta} \pi_\beta(\beta = \beta^{(1)}) = \pi_\beta(\beta = \beta^{(2)}) = 1/2,\tag{66}\] where recall the construction of \(\beta^{(1)}\) and \(\beta^{(2)}\) in 63 . Therefore, for any \(q \in [1,2]\), we derive that \[\label{eq:32bayes32lower32bound} \begin{align} &\inf_{\hat{\beta}} \mathbf{E}_{\beta \sim \pi_\beta} \mathbf{E}_{Y,X | \epsilon', \beta, \mathbf{Q}(\beta)} \left( \| \hat{\beta} - \beta\|_q^q \right)\\ \ge & \frac{s\lambda^q}{2^q} \cdot \inf_{\hat{\beta}} \frac{1}{2} \left\{ \left[ (1-\epsilon') \mathbf{P}_1 + \epsilon' \mathbf{Q}_1 \right]\left( \|\hat{\beta} - \beta^{(1)} \|_q \ge \frac{s^{1/q}\lambda }{2} \right) \right.\\ & \quad \quad \quad \quad \quad~ \left. + \left[ (1-\epsilon') \mathbf{P}_2 + \epsilon' \mathbf{Q}_2 \right]\left( \|\hat{\beta} - \beta^{(2)} \|_q \ge \frac{s^{1/q}\lambda }{2} \right) \right\}\\ \overset{(i)}\ge & \frac{s\lambda^q}{8} \cdot \inf_{\hat{\beta}} \left\{ \left[ (1-\epsilon') \mathbf{P}_1 + \epsilon' \mathbf{Q}_1 \right]\left( \psi^*(\hat{\beta}) =2 \right) + \left[ (1-\epsilon') \mathbf{P}_2 + \epsilon' \mathbf{Q}_2 \right]\left( \psi^*(\hat{\beta}) =1 \right) \right\}\\ = & \frac{1}{8 (8 C_{2s})^{q/2}} \cdot \frac{\sigma^q s^{1-q/2} o^q}{n^q} ~\left( = \frac{s\lambda^q}{8} \right), \end{align}\tag{67}\] where \(\mathbf{E}_{Y,X | \epsilon', \beta, \mathbf{Q}(\beta)}\) denotes an expectation based on the joint distribution of \((X_{i, \cdot }, Y_i)_{i \in [n]}\), with each \((X_{i, \cdot }, Y_i) \sim (1- \epsilon') \mathbf{P}_\ell + \epsilon' \mathbf{Q}_\ell\) independently for \(\beta = \beta^{(\ell)}\), and we use \(\mathbf{Q} (\beta^{(\ell)}) = \mathbf{Q}_\ell\) to emphasize that in our construction the contamination distribution is partially determined by \(\beta\). Additionally, in inequality (i) we define the selector \(\psi^*(\hat{\beta}) = \arg \min_{\ell \in \{1,2\}} \| \hat{\beta} - \beta^{(\ell)}\|_q\), and this inequality holds because that \(\psi^*(\hat{\beta}) =2 \Rightarrow \|\hat{\beta} - \beta^{(1)} \|_q \ge \|\hat{\beta} - \beta^{(2)} \|_q \Rightarrow s^{1/q} \lambda = \| \beta^{(1)} - \beta^{(2)} \|_q \le 2 \|\hat{\beta} - \beta^{(1)} \|_q\). And the last equality follows from 65 .

13.2 Estimation lower bound in Theorem 4↩︎

Section 13.1 gives a minimax estimation lower bound under the Huber contamination model \((X_{i, \cdot }, Y_i) \sim (1- \epsilon') \mathbf{P} + \epsilon' \mathbf{Q}\). However, this lower bound 67 cannot be applied directly in our frequentist-setting model. Given \(\beta, n, k, \sigma\) and \(\pi_\Sigma(\cdot)\), we define the distribution class of \((X_i, Y_i)_{i \in [n]}\) as \[\begin{align} \mathcal{P}_{\beta,k} =& \left\{ (n-k) \text{ observations are drawn from } \pi_\Sigma(X_{i,\cdot}) \times \mathcal{N}(Y_i, X_{i,\cdot} \beta, \sigma^2) , \right.\\ & \quad k \text{ observations are drawn from arbitrary } \mathbf{Q} \left. \right\} . \end{align}\] Define \(\mathcal{M}(\beta,o) : = \bigcup_{0 \le k \le o}\mathcal{P}_{\beta,k}\), and in this subsection, we focus on deriving a lower bound as \[\label{eq:32freq32lower32prototype} \inf_{\hat{\beta}} ~\sup_{ \beta : \| \beta\|_0 \le s}~ \sup_{\mathbf{R} \in \mathcal{M}(\beta,o)} ~\mathbf{E}_{\mathbf{R}} \left( \| \hat{\beta}- \beta\|_q^q \right) \gtrsim \sigma^q s \left(\frac{ \log (ep/s)}{n}\right)^{q/2} +\sigma^q s^{1-q/2} \frac{ o^q}{n^q} ,\tag{68}\] where \(\mathbf{R}\) is a joint distribution of \((X_{i\cdot}, Y_i)_{i\in [n]}\).

It is straightforward to apply the uncontaminated result [36], [37] to get \[\begin{align} &\inf_{\hat{\beta}} ~\sup_{ \beta : \| \beta\|_0 \le s}~ \sup_{\mathbf{R} \in \mathcal{M}(\beta,o)}\mathbf{E}_{\mathbf{R}} \left( \| \hat{\beta}- \beta\|_q^q \right)\\ \ge & \inf_{\hat{\beta}} ~\sup_{ \beta : \| \beta\|_0 \le s}~ \sup_{\mathbf{R} \in \mathcal{P}_{\beta, k=0}}\mathbf{E}_{\mathbf{R}} \left( \| \hat{\beta}- \beta\|_q^q\right) \gtrsim \sigma^q s \left(\frac{ \log (ep/s)}{n}\right)^{q/2}, \end{align}\] for any \(q \in [1,2]\), therefore we only need to derive the term \(\sigma^q s^{1-q/2} \frac{o^q}{n^q}\).

We first get a lower bound as \[\label{eq:32post32mean} \begin{align} &\inf_{\hat{\beta}} ~\sup_{\beta: \|\beta\|_0 \le s} ~\sup_{\mathbf{R} \in \mathcal{M} (\beta,o)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\| \hat{\beta}(Y,X) - \beta \right\|_q^q \\ = & \inf_{\hat{\beta}} ~\sup_{\beta: \|\beta\|_0 \le s} ~\sup_{k \le o} ~ \sup_{\mathbf{R} \in \mathcal{P}_{\beta,k} } \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\| \hat{\beta}(Y,X) - \beta \right\|_q^q\\ \overset{(i)}\ge &\inf_{\hat{\beta}}~ \mathbf{E}_{\beta \sim \pi_{\beta}} \mathbf{E}_{k \sim \pi_{k}^o} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \sum_{j\in[p]} \left| \hat{\beta}_j (Y,X) - \beta_j \right|^q\\ \overset{(ii)}\ge &\sum_{j\in [p]}~ \inf_{\hat{\beta}_j(Y,X)}~ \mathbf{E}_{\beta ,k} \mathbf{E}_{X,Y|\beta,k} \left| \hat{\beta}_j(Y,X) - \beta_j \right|^q \\ \overset{(iii)}= &\sum_{j\in [p]}~ \inf_{\hat{\beta}_j(Y,X)}~ \mathbf{E}_{Y,X} \mathbf{E}_{\beta, k | Y,X} \left| \hat{\beta}_j(Y,X) - \beta_j \right|^q \\ = &\sum_{j\in [p]} \mathbf{E}_{Y,X}~ \mathbf{E}_{\beta,k|Y,X} \left| \hat{M}_j(Y,X) - \beta_j \right|^q. \end{align}\tag{69}\] Some remarks on 69 :

1. In inequality (i), we first construct a distribution \(\pi_k := Binomial(n, \epsilon')\) and denote \(\pi_k^o\) the conditional distribution of \(\pi_k\) given \(0\le k\le o\). Once \(\beta (= \beta^{(\ell)})\) and \(k\) are generated, we use \(\mathbf{Q}(\beta)\) (derived in 64 ) to represent the contaminated distribution, and denote by \(\mathcal{P}_{\beta, k }(\mathbf{Q}(\beta))\) the subset of \(\mathcal{P}_{\beta,k}\), given the contamination \(\mathbf{Q} = \mathbf{Q}(\beta)\). It is then clear that \(|\mathcal{P}_{\beta, k }(\mathbf{Q}(\beta))| = \binom nk\), and we write \(\mathbf{R} \sim U\!\bigl(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta))\bigr)\) to denote the uniform distribution over the collection \(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta))\). Equivalently, each subset of size \(k\) is chosen as the outlier set with probability \(1/\binom{n}{k}\).

2. In inequality (ii), we write \(\mathbf{E}_{\beta,k}\) as an abbreviation of \(\mathbf{E}_{\beta \sim \pi_{\beta}} \mathbf{E}_{k \sim \pi_{k}^o}\). And we write the abbreviation \(\mathbf{E}_{X,Y|\beta,k}\) since the joint distribution of \((X,Y)\) is fully specified given \(\beta\) and \(k\): \[\mathbb{P}\left( X,Y | \beta = \beta^{(\ell)}, k \right) = \frac{1}{\binom nk} \sum_{O\subset [n]: |O|=k} \left\{ \prod_{i \in O} Q(X_{i\cdot}, Y_i) \cdot \prod_{i \notin O}\pi_\Sigma(X_{i\cdot})\mathcal{N} \left(Y_i, X_{i\cdot}\beta^{(\ell)}, \sigma^2 \right)\right\},\] as we discussed in inequality (i).

3. In equality (iii), we denote by \(\mathbf{E}_{\beta, k|Y,X}\) the conditional expectation based on the probability measure \[\pi^o_{\beta, k|Y,X}(\beta^{(\ell)}, k):= \frac{ \mathbb{P}\left( \beta = \beta^{(\ell)}, k , X,Y\right) }{ \sum_{\ell' \in \{1,2\}, 0\le k' \le o}\mathbb{P}\left( \beta = \beta^{(\ell')}, k=k' , X,Y\right) },\] where \[\begin{align} &\mathbb{P}\left( \beta = \beta^{(\ell)}, k , X,Y\right)\\ :=& \frac{1}{2} \times \frac{\binom nk (\epsilon')^k (1-\epsilon')^{n-k}}{\sum_{0\le k'\le o}\binom n{k'} (\epsilon')^{k'} (1-\epsilon')^{n-k'}}\\ &~\times \frac{1}{\binom nk} \sum_{O\subset [n]: |O|=k} \left\{ \prod_{i \in O} Q(X_{i\cdot}, Y_i) \cdot \prod_{i \notin O } \pi_\Sigma(X_{i\cdot})\mathcal{N} \left(Y_i, X_{i\cdot}\beta^{(\ell)}, \sigma^2 \right)\right\}. \end{align}\]

4. In the last equality, by Theorem 1.1 on page 228 in [49], there exists a Bayes estimator \(\hat{M}_j(Y,X)\) achieving the infimum. Additionally, this estimator is better than the zero estimator, leading \[\label{eq:32lq} \begin{align} |\hat{M}_j(Y,X)| \le& \left| \mathbf{E}_{\beta, k|Y,X} (\hat{M}_j(Y,X) - \beta_j)\right| + \left| \mathbf{E}_{\beta, k|Y,X} \beta_j \right|\\ \overset{\text{(Jensen)}}{\le}& \left( \mathbf{E}_{\beta, k|Y,X} \left|\hat{M}_j(Y,X) - \beta_j \right|^q \right)^{1/q} + \left( \mathbf{E}_{\beta, k|Y,X} \left| \beta_j \right|^q \right)^{1/q}\\ \le& 2 \left( \mathbf{E}_{\beta, k|Y,X} \left| \beta_j \right|^q \right)^{1/q}. \end{align}\tag{70}\]

Therefore, we bridge the \(\epsilon'\)-contamination model 67 and our frequentist-setting model for any \(q \in [1,2]\): \[\label{eq:32bridge} \begin{align} &\inf_{\hat{\beta}} \mathbf{E}_{\beta \sim \pi_\beta} \mathbf{E}_{Y,X | \epsilon', \beta, \mathbf{Q}(\beta)} \left( \| \hat{\beta} - \beta\|_q^q \right)\\ =& \inf_{\hat{\beta}} \mathbf{E}_{\beta \sim \pi_{\beta} } \mathbf{E}_{k\sim \pi_{k}} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}}\sum_{j\in [p]} \left| \hat{\beta}_j (Y,X) - \beta_j \right|^q\\ \le & \mathbf{E}_{\beta \sim \pi_{\beta} } \mathbf{E}_{k\sim \pi_{k}} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\{ \mathbf{1} ( k\le o)\cdot \sum_{j\in [p]} \left| \hat{M}_j (Y,X) - \beta_j \right|^q \right\}\\ & + \mathbf{E}_{\beta \sim \pi_{\beta} } \mathbf{E}_{k\sim \pi_{k}} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\{ \mathbf{1} ( k > o) \cdot \sum_{j\in [p]} \left| \hat{M}_j (Y,X) - \beta_j \right|^q \right\}\\ \overset{\text{(Jensen)}}\le & \mathbf{E}_{\beta \sim \pi_{\beta} } \mathbf{E}_{k\sim \pi_{k}^o} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\{ \sum_{j\in [p]} \left| \hat{M}_j (Y,X) - \beta_j \right|^q \right\}\\ &+ 2^{q-1}\sum_{j\in [p]} \mathbf{E}_{\beta \sim \pi_{\beta} } \mathbf{E}_{k\sim \pi_{k}} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\beta,k}(\mathbf{Q}(\beta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\{ \mathbf{1} ( k > o) \cdot \left( |\hat{M}_j (Y,X)|^q + |\beta_j|^q \right) \right\} \\ \le & \inf_{\hat{\beta}} ~\sup_{\beta: \|\beta\|_0 \le s} ~\sup_{\mathbf{R} \in \mathcal{M} (\beta,o)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\| \hat{\beta}(Y,X) - \beta \right\|_q^q + 15 s \lambda^q \cdot \pi_k (k > o), \end{align}\tag{71}\] where the last inequality follows from 69 , 70 , and also the fact \[\mathbf{E}_{\beta, k|Y,X} \left( \left| \beta_j \right|^q \right) \begin{cases} \le \lambda^q & \text{ if } j \le 3s/2, \\ =0 & \text{ if } 3s/2 < j \le p, \end{cases}\] leading by the construction of \(\pi_\beta\) (63 and 66 ).

By Bernstein’s inequality (Appendix D.4 in [50]), we have \[\pi_k (k > o) \le \exp\left(- \frac{\frac{1}{n} (o-n \epsilon')^2 }{2 \epsilon' + \frac{2}{3} \frac{o-n \epsilon'}{n}} \right) \le \exp(-9o/16),\] where the last inequality follows from \(\epsilon' \le o/(4n)\). Therefore, combining 67 and 71 , for any \(q \in [1,2]\), we have the lower bound \[\begin{align} &\inf_{\hat{\beta}} ~\sup_{\beta: \|\beta\|_0 \le s} ~\sup_{\mathbf{R} \in \mathcal{M} (\beta,o)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\| \hat{\beta}(Y,X) - \beta \right\|_q^q \\ \ge & s \lambda^q \left( \frac{1}{8} - 15 \exp(-9o/16) \right)\\ \ge& \frac{(8C_{2s})^{-q/2}}{80 } \cdot \sigma^q s^{1-q/2} \frac{ o^q}{n^q}, \end{align}\] where the last inequality follows from the assumption \(o \ge 9\). Hence, we complete the proof of Theorem 4.

13.3 Selection lower bound in Theorem 5↩︎

The proof of Theorem 5 is quite similar to that of Theorem 4. Define \[\mathcal{B}(s,a):= \left\{ \beta \in \mathbb{R}^p: ~ \|\beta\|_0 \le s , \min_{i: \beta_i \ne 0} |\beta_i| \ge a \right\}.\] From [51] and Fano’s inequality [52], we have \[\inf_{\hat{S}} ~\sup_{\beta \in \mathcal{B} \left(s, ~c_1 \sigma \sqrt{ (\log (ep/s))/n} \right) }~\sup_{\mathbf{R} \in \mathcal{P}_{\beta, k=0} } \mathbf{E}_\mathbf{R} \Big\{ \left| \hat{S}( X,Y) ~ \triangle~ \text{supp}(\beta)\right| \Big\} \ge c_2 s,\] where \(\inf_{\hat{S}}\) denotes the infimum over all support set estimation \(\hat{S}\) based on \((X,Y)\), and \(c_1, c_2 >0\) are two absolute constants. Therefore, we only need to prove the selection lower bound based on the parameter subspace \(\mathcal{B}(s, \lambda)\) with \(\lambda = \sqrt{\frac{1}{8C_{2s}}}\cdot \frac{\sigma}{\sqrt s} \cdot \frac{ o}{n}\). We introduce the decoder \(\eta = \eta (\beta) \in \{0,1 \}^p\), with each \(\eta_i = \left\{ \eta(\beta)\right\}_i = \mathbf{1}(\beta_i \ne 0)\). Denote the selector \(\hat{\eta}(X,Y) \in \{ 0,1\}^p\) as the estimator of \(\eta(\beta)\). By using the same technique in Section 13.1, we have \[\label{eq:32bayes32selection32lower32bound} \begin{align} &\inf_{\hat{\eta}} \mathbf{E}_{\beta \sim \pi_\beta} \mathbf{E}_{Y,X | \epsilon', \beta, \mathbf{Q}(\beta)} \left( \left\| \hat{\eta}( X,Y)\;- \eta(\beta) \right\|_2^2 \right)\\ = &\inf_{\hat{S}} \mathbf{E}_{\beta \sim \pi_\beta} \mathbf{E}_{Y,X | \epsilon', \beta, \mathbf{Q}(\beta)} \left( \left| \hat{S}( X,Y) ~ \triangle~ \text{supp}(\beta)\right| \right)\\ \ge & \frac{s}{2} \cdot \inf_{\hat{\beta}}~ \frac{1}{2}\cdot \left\{ \left[ (1-\epsilon') \mathbf{P}_1 + \epsilon' \mathbf{Q}_1 \right]\left( \left| \hat{S}( X,Y) ~ \triangle~ \text{supp}(\beta^{(1)})\right| \ge \frac{s}{2} \right) \right.\\ & \quad \quad \quad \quad \quad~ \left. + \left[ (1-\epsilon') \mathbf{P}_2 + \epsilon' \mathbf{Q}_2 \right]\left( \left| \hat{S}( X,Y) ~ \triangle~ \text{supp}(\beta^{(2)})\right| \ge \frac{s}{2} \right) \right\}\\ \ge & \frac{s}{4}. \end{align}\tag{72}\]

We next analyze the selection lower bound in our setting. Here we rewrite the prior \(\pi_\beta\) as a prior on \(\eta\), i.e., \(\pi_\eta(\eta = \eta^{(\ell)}) = 1/2 , \quad \ell =1 ,2\), where \[\begin{align} \eta^{(1)} & := (\underbrace{1, \cdots, 1}_{s}~,~ \underbrace{0, \cdots, 0 }_{p-s})^\top \in \mathbb{R}^p,\\ \eta^{(2)} & := (\underbrace{0, \cdots, 0 }_{s/2}~, ~\underbrace{1, \cdots, 1}_{s}~,~ \underbrace{0, \cdots, 0 }_{p- {3s}/2} )^\top \in \mathbb{R}^p. \end{align}\] Thus \(\beta^{(\ell)} = \lambda \eta^{(\ell)}\). And we get two results similar to 69 and 71 : \[\begin{align} &\inf_{\hat{\eta}} ~\sup_{\beta \in \mathcal{B}(s, \lambda) } ~\sup_{\mathbf{R} \in \mathcal{M} (\beta,o)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\| \hat{\eta}(Y,X) - \eta(\beta) \right\|_2^2\\ \ge &\inf_{\hat{\eta}}~ \mathbf{E}_{\eta \sim \pi_{\eta}} \mathbf{E}_{k \sim \pi_{k}^o} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{ \lambda \eta,k}(\mathbf{Q}(\lambda\eta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \sum_{j\in[p]} \left( \hat{\eta}_j (Y,X) - \eta_j \right)^2\\ \ge &\sum_{j\in [p]} \mathbf{E}_{Y,X}~ \mathbf{E}_{\eta,k|Y,X} \left( \hat{T}_j(Y,X) - \eta_j \right)^2, \end{align}\] and \[\begin{align} &\inf_{\hat{\eta}} \mathbf{E}_{\beta \sim \pi_\beta} \mathbf{E}_{Y,X | \epsilon', \beta, \mathbf{Q}(\beta)} \left( \| \hat{\eta} - \eta\|_2^2 \right)\\ \le & \mathbf{E}_{\eta \sim \pi_{\eta} } \mathbf{E}_{k\sim \pi_{k}^o} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\lambda \eta,k}(\mathbf{Q}( \lambda \eta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\{ \sum_{j\in [p]} \left( \hat{T}_j (Y,X) - \eta_j \right)^2 \right\}\\ &+ 2s \cdot \mathbf{E}_{\eta \sim \pi_{\eta} } \mathbf{E}_{k\sim \pi_{k}} \mathbf{E}_{\mathbf{R} \sim U\left(\mathcal{P}_{\lambda \eta,k}(\mathbf{Q}(\lambda \eta)) \right)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\{ \mathbf{1} ( k > o) \right\} \\ \le & \inf_{\hat{\eta}} ~\sup_{\beta \in \mathcal{B}(s, \lambda)} ~\sup_{\mathbf{R} \in \mathcal{M} (\beta,o)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left\| \hat{\eta}(Y,X) - \eta(\beta) \right\|_2^2 ~+~ 2s \cdot \pi_k (k > o), \end{align}\] where \(\hat{T}_j (Y,X) := \mathbf{E}_{\eta,k|Y,X}(\eta_j) \in [0,1]\). Therefore, \[\begin{align} &\inf_{\hat{S}} ~\sup_{\beta \in \mathcal{B}(s, \lambda)} ~\sup_{\mathbf{R} \in \mathcal{M} (\beta,o)} \mathbf{E}_{(X,Y) \sim\mathbf{R}} \left| \hat{S}( X,Y) ~ \triangle~ \text{supp}(\beta)\right| \\ \ge & \frac{s}{4} - 2s \cdot \exp(-9o/16) \\ \ge& \frac{s}{5}, \end{align}\] where the last inequality follows from \(o \ge 8\), and thus we complete the proof of Theorem 5.

14 Technical Lemmas↩︎

Next, we control the error related to the oracle estimator. Recall that \[\begin{align} \beta^{\dagger}_{S^*} &= \beta^{*}_{S^*} + (X^{\top}_{-O^*,S^*}X_{-O^*,S^*})^{-1}X_{-O^*,S^*}^{\top}\xi_{-O^*},\quad \beta^{\dagger}_{-S^*} = \mathbf{0} , \\ \theta^{\dagger}_{O^*} &= \theta^{*}_{O^*} + \frac{1}{\sqrt{n}} \Big\{ \xi_{O^*} - X_{O^*,S^*}(X_{-O^*,S^*}^{\top}X_{-O^*,S^*})^{-1}X^{\top}_{-O^*,S^*}\xi_{-O^*} \Big\},\quad \theta^{\dagger}_{-O^*} = \mathbf{0} , \\ \Xi_{S^*}^\dagger &= \mathbf{0},\quad \xi_{O^*}^\dagger = \mathbf{0},\\ \Xi_{-S^*}^\dagger &= \frac{1}{n}X_{-O^*,-S^*}^{\top} \Big\{ I_{n-o} -P_{-O^*,S^*} \Big\} \xi_{-O^*},\\ \xi_{-O^*}^\dagger &= \Big\{ I_{n-o} - P_{-O^*,S^*} \Big\} \xi_{-O^*}, \end{align}\] where we define \[P_{-O^*,S^*} := X_{-O^*,S^*}(X_{-O^*,S^*}^{\top}X_{-O^*,S^*})^{-1}X_{-O^*,S^*}^{\top} \in \mathbb{R}^{(n-o) \times (n-o)}.\]

15 Additional Details about the Extension to GLM↩︎

In the Discussion section, we extend the two-stage AC-IHT algorithm to the setting of generalized linear models (GLMs). Compared to the linear model case, only the gradient descent step requires modification. Therefore, we begin by analyzing the decomposition of \(H_{\beta}^{t+1}\) and \(H_{\theta}^{t+1}\).

15.1 Preliminary↩︎

Let \(X^{(i)} \in \mathbb{R}^{p \times 1}\) be the transformation of the \(i\)th row of X. We have \[\label{eq:GLMH95beta} \begin{align} H^{t+1}_{\beta} :=& \beta^t - \frac{ \eta }{n} \sum_{i=1}^n X^{(i)}\left(b'(\zeta_i^t) - Y_i \right)\\ =& \beta^* -(\beta^*-\beta^t) - \frac{ \eta }{n} \sum_{i=1}^n X^{(i)}\Big\{ \left(b'(\zeta_i^t) - b'(\zeta_i^*)\right) -\left(Y_i - b'(\zeta_i^*)\right) \Big\}\\ =& \beta^* + \left(\frac{ \eta }{n} \sum_{i=1}^n b''( \tilde{\zeta}_i^t ) X^{(i)} (X^{(i)})^{\top} - \mathbf{I}_p \right) \left( \beta^* -\beta^t\right) \\ &+ \frac{{ \eta }}{\sqrt{n}}\left( \sum_{i=1}^n b''( \tilde{\zeta}_i^t)X^{(i)}e_i^\top\right)(\theta^* - \theta^t)+\frac{ \eta }{n} \sum_{i=1}^n X^{(i)}\left(Y_i-b'(\zeta_i^*)\right) \\ =& \beta^* + \tilde{\Phi}^t \left( \beta^* -\beta^t\right) + \frac{{ \eta }}{\sqrt{n}}(\tilde{X}^{t})^{\top}\left( \theta^* - \theta^t\right) + { \eta }\tilde{\Xi} , \end{align}\tag{81}\]

\[\label{eq:GLMH95theta} \begin{align} H^{t+1}_{\theta} :=& \theta^t - \frac{ \eta }{\sqrt{n}} \sum_{i=1}^n e_i\left(b'(\zeta_i^t) - Y_i \right)\\ =& \theta^* -(\theta^*-\theta^t) - \frac{ \eta }{\sqrt{n}} \sum_{i=1}^n e_i\Big\{ \left(b'(\zeta_i^t) - b'(\zeta_i^*)\right) -\left(Y_i - b'(\zeta_i^*)\right) \Big\}\\ =& \theta^* + \frac{ \eta }{\sqrt{n}}\left( \sum_{i=1}^n b''( \tilde{\zeta}_i^t ) e_i (X^{(i)})^\top \right) \left( \beta^* -\beta^t\right) + \left( { \eta }\sum_{i=1}^n b''( \tilde{\zeta}_i^t)e_ie_i^\top -\mathbf{I}_n\right)(\theta^* - \theta^t)\\ &+\frac{ \eta }{\sqrt{n}} \sum_{i=1}^n e_i\left(Y_i-b'(\zeta_i^*)\right) \\ =& \theta^* + \frac{ \eta }{\sqrt{n}}\tilde{X}^{t} \left( \beta^* -\beta^t\right) + \tilde{D}^t\left( \theta^* - \theta^t\right) + \frac{ \eta }{\sqrt{n}}\tilde{\xi} , \end{align}\tag{82}\] where \(\zeta^t_i := (X^{(i)})^\top \beta^t + \sqrt n e_i^\top\theta^t\), \(\tilde{\zeta}_i^t = \lambda^t \zeta^t_i + (1-\lambda^t) \zeta^*_i\) for some \(\lambda^t \in (0,1)\), and \(\tilde{\Phi}^t := \frac{ \eta }{n} \sum_{i=1}^n b''(\tilde{\zeta}_i^t) X^{(i)} (X^{(i)})^\top -I_p \in \mathbb{R}^{p \times p}\), \(\tilde{X}^t := \sum_{i=1}^n b''( \tilde{\zeta}_i^t)e_i(X^{(i)})^\top\in\mathbb{R}^{n \times p}\), \(\tilde{\Xi} := \frac{1}{n} \sum_{i=1}^n X^{(i)}\left(Y_i-b'(\zeta^*_i)\right) \in \mathbb{R}^p\), \(e_i \in \mathbb{R}^{n\times 1}\) be the \(i\)-th standard basis vector, \(\tilde{D}^t := { \eta }\text{diag}(b''( \tilde{\zeta}_1^t),\ldots,b''( \tilde{\zeta}_n^t)) - I_n = { \eta } \sum_{i=1}^n b''( \tilde{\zeta}_i^t) e_i e_i^\top - I_n \in \mathbb{R}^{n \times n}\) and \(\tilde{\xi} := \sum_{i=1}^n e_i\left(Y_i-b'(\zeta_i^*)\right)\). The decomposition of \(H^{t+1}_\beta\) and \(H^{t+1}_\theta\) reveals that the structure of \(H^{t+1}_\beta\) is similar to 27 in the proofs of Theorems 1 and 2.

15.2 Useful lemmas↩︎

The following lemmas establish that \(\tilde{X}^t\), \(\tilde{\Phi}^t\), \(\tilde{\Xi}\), and \(\tilde{\xi}\) retain the same properties as those in the proofs of Theorems 1 and 2.

15.3 Proof of Theorem 6↩︎

We are now ready to present the proof of Theorem 6. The proof is divided into three steps: Step 1: establishing the convergence property of the first-stage algorithm (Theorem 1, GLM version); Step 2: establishing the signal adaptive result of the second-stage algorithm (Theorem 2, GLM version). Define \(M ' : =\max \left( M , ~\frac{M}{L},~MU \right)\).

Step 1 (First stage Algorithm 1, GLM version) Define the event \[\mathcal{E}_{GLM}: = \left\{ \left\| \tilde{\Xi} \right\|_\infty < 4\sqrt{\frac{aUM'\log p}{n}} , \text{ and } \left\| \frac{1}{\sqrt n} \tilde{\xi} \right\|_\infty < 3\sqrt{\frac{ aU \log n}{n} }\right\},\] and \[\mathcal{E}_{X,GLM}:= \begin{Bmatrix} \frac{1}{2M'} \le \Lambda_k\left( \frac{1}{n} \sum_{i=1}^n b''(\tilde{\zeta}_i^t) X^{(i)}_S (X^{(i)}_S)^\top \right) \le 2M',~ S \subset [p]:~ |S| \le (2B'+1)s \text{ and } 1\le k \le |S|, \\ \sup_{S\subset[p]:~ |S| \le (B'+1) s} ~ \sup_{O\subset[n]:~ |O| \le (B'+1)o} \left\| \tilde{X}_{O,S}^t \right\|_2 \le {(\sqrt {B'}+1)} f' \sqrt n \end{Bmatrix},\]

where \[\label{eq:32B32delta32GLM} B':= \left(\frac{\kappa'+\delta'}{\kappa'- \delta'}\right)^2>1, \quad \delta' := \frac{4M'^2}{4M'^2 +1}\in (0,1), \quad f':= C_M U \sqrt{\frac{s \log p + o \log n}{n}},\tag{85}\] and the decay rate \(\kappa' \in \left( \delta',1 \right)\). The event \(\mathcal{E}_{X,GLM}\) follows from Lemma 4 with \(C_1=2B'+1\) for the restricted isometry part and \(C_1=B'+1\) for the restricted incoherence part. These choices are fixed once \(M,L,U\) and \(\kappa'\) are fixed. By Lemmas 4 and 5, we have \(\mathbf{P}(\mathcal{E}_{GLM} \cap \mathcal{E}_{X,GLM}) \ge 1- O\left(p^{-2} + n^{-3}\right)\). Under the event \(\mathcal{E}_{GLM} \cap \mathcal{E}_{X,GLM}\), we choose some proper parameters \[\label{eq:32glm32lambda} \begin{align} \lambda_{\beta, \infty} &\asymp \sqrt{aU} \left( \sqrt{\frac{ \log p}{n}} + \frac{o \log n}{n \sqrt s} \right), \\ \lambda_{\theta, \infty} &\asymp \sqrt{aU} \left( \sqrt{\frac{\log n}{n}} + \frac{s \log p}{n \sqrt o} \right). \end{align}\tag{86}\] Then, by choosing the learning rate \(\eta' \in \left[\frac{2M'}{4M'^2 + 1}, \frac{4M'}{4M'^2 + 1} \right]\) and applying a proof process similar to that in Section 8.2, we ensure that, with probability at least \(1 - O(p^{-2}+n^{-3})\), both estimators are \(\ell_0\)-sparse, i.e., \(\|\widehat{\beta}^{GLM}\|_0 \lesssim s,~\|\widehat{\theta}^{GLM}\|_0 \lesssim o,\) and satisfies \[\begin{align} \| \widehat{\beta}^{GLM} - \beta^* \|_2^2 \lesssim & aU\left( \frac{s \log p}{n} + \frac{o^2 \log^{2} n}{n^2} \right),\\ \| \widehat{\theta}^{GLM} - \theta^* \|_2^2 \lesssim& aU \left( \frac{o\log n}{n} + \frac{s^2 \log^{2} p}{n^2} \right). \end{align}\]

Step 2 (Second-stage Algorithm 2, GLM version) Following Lemmas 1 and 5, we have \[\begin{align} \mathbf{P}\left\{\underbrace{ \frac{1}{n} \left\| X_{\cdot S^*}^\top \tilde{\xi} \right\|_2 \le \sqrt{aUM} \sqrt{\frac{4 s +6 \log(1/\varrho)}{n}} }_{=:\mathcal{E}'_{GLM}} \right\} \ge 1- O\left(p^{-2s} + \varrho \right). \end{align}\] We fix the threshold parameters \(\lambda_\beta\), \(\lambda_\theta\) as in 86 . Then, under the signal condition \[\label{eq:32betamin32in32th6} \min_{i \in S^*} |\beta_i^*| \ge \left( \frac{4 \kappa'}{\kappa'-\delta'} + \frac{\kappa'-\delta'}{4 \kappa'} \right) \cdot \lambda_\beta \asymp \sqrt{aU} \left( \sqrt{\frac{ \log p}{n}} + \frac{o \log n}{n \sqrt s} \right),\tag{87}\] by applying a proof technique similar to that in Section 9.2, we get the sharper bound \[\| \tilde{\beta}^{GLM} - \beta^*\|_2 \lesssim \sqrt{\frac{s +\log (1/\varrho)}{n}} + \frac{s\log p+ o \log n}{n},\] with a probability greater than \(1 - \varrho - O(p^{-2}+n^{-3})\). Therefore, we complete the proof of Theorem 6, demonstrating the signal adaptivity of our procedure under the GLM setting.

16 Proof of Theorem 7↩︎

We first establish the estimation error bound for the regime where \(\delta \in (0, 1)\). Before proceeding to the main analysis, we provide some necessary probabilistic inequalities.

16.0.0.1 Concentration of \(|\Xi_j'|\).

Define \[\Xi_j' := \frac{1}{n} \sum_{i=1}^n X_{ij} \xi_i = \frac{1}{n} \sum_{i=1}^n X_{ij} \psi_\tau(\epsilon_i), \text{ for every } j \in [p].\] For every \(k\ge 2\), by the definition of \(\psi_\tau(\cdot)\), we have the moment inequality \[\begin{align} \mathbf{E}( |\xi_i|^k) =& \mathbf{E}\left\{ \tau^k \mathbf{1} ( |\epsilon_i| > \tau) \right\} + \mathbf{E}\left\{ |\epsilon_i|^k \mathbf{1} ( |\epsilon_i| \le \tau) \right\}\\ \le & \mathbf{E}\left\{ \tau^k \frac{|\epsilon_i|^{1+\delta}}{\tau^{1+\delta}}\cdot \mathbf{1} ( |\epsilon_i| > \tau) \right\} + \mathbf{E}\left\{ |\epsilon_i|^k \frac{\tau^{k-1-\delta}}{|\epsilon_i|^{k-1-\delta}} \cdot \mathbf{1} ( |\epsilon_i| \le \tau) \right\}\\ \le& \tau^{k-1-\delta} \mathbf{E}\left\{ |\epsilon_i|^{1+\delta} \mathbf{1} ( |\epsilon_i| > \tau) + |\epsilon_i|^{1+\delta}\mathbf{1} ( |\epsilon_i| \le \tau) \right\}\\ \le & v_\delta \tau^{k-1-\delta}. \end{align}\] By the sub-Gaussian property, we obtain \[\mathbf{E} ( |X_{ij}|^k ) = \int_{t \in \mathbb{R}^+} \mathbf{P}(|X_{ij}|^k > t) \mathrm d t \le (2\Sigma_{jj})^{k/2} k \Gamma(k/2).\] Then, for every \(\lambda\) satisfying \(|\lambda| \le \frac{1}{2 \tau \sqrt{ 2 \Sigma_{jj} } }\), we get a Bernstein-type bound: \[\begin{align} \mathbf{E}(e^{\lambda X_{ij} \xi_j }) \le & 1 + \frac{1}{2} \lambda^2 \mathbf{E}X_{ij}^2 \xi_j^2 + \sum_{k\ge 3} \frac{\lambda^k}{k!} \mathbf{E} |X_{ij} \xi_j|^k\\ \le & 1 + 2\lambda^2\Sigma_{jj} v_\delta \tau^{1-\delta} + \sum_{k\ge 3} \frac{\lambda^k v_\delta \tau^{k-1-\delta} \cdot (\sqrt{2 \Sigma_{jj}})^k ~k!}{k!} \\ \le & 1+ 4\lambda^2\Sigma_{jj} v_\delta \tau^{1-\delta} \\ \le& \exp(4\lambda^2\Sigma_{jj} v_\delta \tau^{1-\delta}), \text{ for each } (i,j) \in [n] \times [p]. \end{align}\] Therefore, by the probability union bound, we get the concentration inequality \[\label{eq:32heavy32Xi} \mathbf{P} \left( \max_{j \in [p]}\left[ |\Xi_j'| - \frac{v_\delta \sqrt{2 \Sigma_{jj}} }{\tau^\delta} - \frac{6 \sqrt{2 \Sigma_{jj}}\cdot \tau \log p }{n}\right] \ge 0 \right) \le 2 p^{-2}.\tag{88}\]

16.0.0.2 Concentration of \(\|\theta^*\|_0\).

We next bound the term \(\|\theta^*\|_0 = \sum_{i \in [n]} \mathbf{1}(\epsilon_i - \psi_\tau(\epsilon_i) \ne 0 ) = \sum_{i \in [n]} \mathbf{1}( |\epsilon_i| > \tau )\). Define \(q:= \mathbf{P}( |\epsilon_i| > \tau ) \le \frac{v_\delta}{\tau^{1+\delta}}\). By Bernstein’s inequality (Appendix D.4 in [50]), we have \[\label{eq:32heavy32o} \begin{align} \mathbf{P}\left( \| \theta^*\|_0 \ge \frac{2nv_\delta}{\tau^{1+\delta}} \right) \le &\mathbf{P}\left\{ \frac{1}{n} \sum_{i \in [n]} \mathbf{1}(|\epsilon_i| > \tau) \ge q+ \frac{v_\delta}{\tau^{1+\delta}} \right\} \\ \le &\exp\left( -\frac{n (v_\delta/\tau^{1+\delta})^2}{2q(1-q) + 2/3 \cdot v_\delta/\tau^{1+\delta}}\right) \le \exp\left( -\frac{n v_\delta}{ 3\tau^{1+\delta} }\right). \end{align}\tag{89}\]

Take \(\tau = \left( \frac{n v_\delta}{6 \log p}\right)^{\frac{1}{1+\delta}}\). We now replace the event \(\mathcal{E}\) 23 (in the proof of Theorem 1) by the newly defined \(\mathcal{E}_{heavy}\): \[\mathcal{E}_{heavy}:= \begin{Bmatrix} \left\| \Xi' \right\|_\infty \le \frac{v_\delta \sqrt{2 \max_j \Sigma_{jj}} }{\tau^\delta} + \frac{6 \sqrt{2 \max_j \Sigma_{jj}}\cdot \tau \log p }{n}, \\ o \le \frac{2nv_\delta}{\tau^{1+\delta}}, \text{ and }~\left\| \xi \right\|_\infty \le\tau \end{Bmatrix}.\] By 88 and 89 , we have \(\mathbf{P}(\mathcal{E}_{heavy}) \ge 1- 3p^{-2}\).

16.0.0.3 Near-optimal error bound.

We first construct a suitable \(\lambda_{\theta,0}\). According to 26 , it suffices to ensure that \[\label{eq:32lambda32032heavy} \sqrt o \lambda_{\theta,0} > \|\theta^* \|_2 \vee (\sqrt o \lambda_{\theta, \infty}).\tag{90}\] Following the proof of Theorem 1, we aim to choose a proper \(\lambda_{\theta, \infty}\) such that \[\sqrt o \lambda_{\theta, \infty} \gtrsim \sqrt{o} \left\| \frac{1}{\sqrt n} \xi \right\|_\infty + \sqrt{\frac{s\log p + o \log n}{n}} \cdot \sqrt s \| \Xi' \|_\infty.\] Additionally, \[\begin{align} &\sqrt{o} \left\| \frac{1}{\sqrt n} \xi \right\|_\infty + \sqrt{\frac{s\log p + o \log n}{n}} \cdot \sqrt s \| \Xi' \|_\infty\\ \lesssim & \tau \sqrt{\frac{o}{n}} + \sqrt{\frac{s\log p + o \log n}{n}} \cdot \sqrt s \left( \frac{v_\delta }{\tau^\delta} + \frac{\tau \log p }{n} \right)\\ \asymp& \tau \sqrt{\frac{o}{n}} \left( 1 + \sqrt{\frac{s\log p}{n}} \sqrt{\frac{s\log p + o \log n}{n}} \right)\\ \asymp& \tau \sqrt{\frac{o}{n}}, \end{align}\] where the second equality uses \(o \asymp \log p\), and the last equality follows from the sample size condition \(n \gtrsim (s+\log n)\log p\). Therefore, it is enough to choose \[\lambda_{\theta,0} \gtrsim \frac{1}{\sqrt n} \left( \|\epsilon \|_\infty \vee \tau \right) \asymp \frac{1}{\sqrt n} \left( \|\epsilon \|_\infty \bigvee \left( \frac{n v_\delta}{\log p}\right)^{\frac{1}{1+\delta}} \right),\] which guarantees 90 . Moreover, by the union bound and the Markov inequality, for every \(r >0\), \[\mathbf{P} ( \|\epsilon \|_\infty > r) \le n \mathbf{E}\left\{ \mathbf{1} \left( |\epsilon|^{1+\delta}>r^{1+\delta} \right)\right\} \le \frac{n v_\delta}{r^{1+\delta}} .\] Hence, by taking \(\lambda_{\theta,0} \gtrsim n^{-1/2} (nv_\delta/\varrho)^{\frac{1}{1+\delta}}\), we ensure that, with probability at least \(1-\varrho-O(p^{-2})\), the initial threshold \(\lambda_{\theta,0}\) satisfies 90 .

Following the proof of Theorems 1 and 2, with a probability greater than \(1-\varrho- O(p^{-2})\), the output of our AC-IHT algorithm satisfies \[\begin{align} \| \tilde{\beta} - \beta^*\|_2 \lesssim& \sqrt s \|\Xi' \|_\infty + \sqrt{\frac{s\log p + o \log n}{n}} \cdot \sqrt{o} \left\| \frac{1}{\sqrt n} {\xi} \right\|_\infty\\ \lesssim & \frac{\sqrt s v_\delta}{\tau^\delta} + \frac{\sqrt s \log p}{n}\tau + \sqrt{\frac{v_\delta s \log p}{n} \tau^{1-\delta} } + \frac{v_\delta \sqrt{\log n}}{\tau^\delta} \\ \lesssim& \frac{ v_\delta \sqrt{s+\log n}}{\tau^\delta} + \frac{\sqrt{s+\log n} \log p}{n}\tau \\ \asymp & v_\delta^{\frac{1}{1+\delta}} \sqrt{s+\log n} \left( \frac{\log p}{n} \right)^{\frac{\delta}{1+\delta}}, \end{align}\] where the first two inequalities follow from Assumption 1, which imposes constant upper and lower bounds on the spectrum of \(\Sigma\).

In the case \(\delta \ge 1\), by the moments inequality, we have \(v_1^{1/2} := (\mathbf{E} |\epsilon_i|^2)^{1/2} \le (\mathbf{E} |\epsilon_i|^{1+\delta})^{1/(1+\delta)} \le v_\delta^{1/(1+\delta)}\). Then we take \(\delta'=1\) and \(v_{\delta'} = v_1\). Following the proof sketch provided above, with a probability at least \(1 - \varrho -O(p^{-2})\), we can choose \(\lambda_{\theta,0} \gtrsim \sqrt{v_1/\varrho }\) and get the upper bound \[\| \tilde{\beta} - \beta^*\|_2 \lesssim v_{\delta'}^{\frac{1}{1+{\delta'}}} \sqrt{s+\log n} \left( \frac{\log p}{n} \right)^{\frac{{\delta'}}{1+{\delta'}}} = \sqrt{\frac{v_1 (s+ \log n) \log p}{n}}.\] Therefore, we complete the proof of Theorem 7, demonstrating the applicability of our algorithm to the high-dimensional heavy-tailed regression.