Problem 2.3: Improved Constant for Hard Thresholding Bound

From Rigollet Chapter 2, Problem 2.3.

In the proof of Theorem 2.11, the bound |θ̂ᴴᴿᴰ_j - θ*_j| ≤ 4·min(|θ*_j|, τ) can be improved to |θ̂ᴴᴿᴰ_j - θ*_j| ≤ 3·min(|θ*_j|, τ).

That is, on the event A = {max_j |ξ_j| ≤ τ} (where y_j = θ*_j + ξ_j), we have: |θ̂ᴴᴿᴰ_j - θ*_j| ≤ 3 · min(|θ*_j|, τ)

Key idea (tighter case analysis)

• Case |y_j| > 2τ: θ̂_j = y_j, so |θ̂_j - θ*_j| = |ξ_j| ≤ τ. Since |θ*_j| ≥ |y_j| - |ξ_j| > 2τ - τ = τ, we get min(|θ*_j|, τ) = τ, hence |ξ_j| ≤ τ = min(|θ*_j|, τ) ≤ 3·min(|θ*_j|, τ).

• Case |y_j| ≤ 2τ: θ̂_j = 0, so |θ̂_j - θ*_j| = |θ*_j|. We have |θ*_j| ≤ |y_j| + |ξ_j| ≤ 2τ + τ = 3τ.

  • If |θ*_j| ≤ τ: min(|θ*_j|, τ) = |θ*_j|, so |θ*_j| ≤ 3·|θ*_j| = 3·min(|θ*_j|, τ).
  • If |θ*_j| > τ: min(|θ*_j|, τ) = τ, and |θ*_j| ≤ 3τ = 3·min(|θ*_j|, τ).

noncomputable def Rigollet.hardThresh {d : ℕ} (τ : ℝ) (y : Fin d → ℝ) : Fin d → ℝ

Hard thresholding estimator (coordinate-wise): keeps y_j if |y_j| > 2τ, else sets to 0.

theorem Rigollet.problem_2_3_improved_hard_threshold_bound (d : ℕ) (τ : ℝ) (hτ : 0 < τ) (θstar ξ y : Fin d → ℝ) (hy : ∀ (j : Fin d), y j = θstar j + ξ j) (hA : ∀ (j : Fin d), |ξ j| ≤ τ) (j : Fin d) : |hardThresh τ y j - θstar j| ≤ 3 * min |θstar j| τ

Problem 2.3: On the event A = {∀ j, |ξ_j| ≤ τ}, the hard thresholding estimator satisfies the improved bound (with constant 3 instead of 4):

|θ̂ᴴᴿᴰ_j - θ*_j| ≤ 3 · min(|θ*_j|, τ)

Here y_j = θ*_j + ξ_j is the sub-Gaussian sequence model, and θ̂ᴴᴿᴰ_j = y_j · 𝟙(|y_j| > 2τ) is the hard thresholding estimator.