When \(\mathcal {O}=\emptyset \)  the performance guarantee in (REF ) is better than existing bounds for regularized algorithms [1]}, [2]} and match, up to logarithmic factors, the best available bounds that can be obtained by combining the tesselation result in Theorem REF  with Plan and Vershynin's [3]} linear programming estimator. Moreover, in the presence of adversarial errors, the convergence rate obtained in (REF ) improves over the rate for the regularized estimator by [1]} if \((|\mathcal {O}|\log (p)\log (n)^5/n)^{4}=o(s\log (p)/n)\)  and otherwise their algorithm achieves faster convergence rates. If \(\beta ^*\)  is exactly \(s\) -sparse, i.e. at most \(s\)  entries of \(\beta ^*\)  are non-zero, then the rate in (REF ) is suboptimal in the dependence on \(s\log (p)/n\)  and \(|\mathcal {O}|/n\)  and faster rates were obtained for a (non-interpolating) regularized estimator in [5]}.
