Problem 5.5 — Exercise: Minimax Rate over Sobolev Ellipsoids

From: Rigollet, "High Dimensional Statistics", Chapter 5 Problem Set

Exercise for the reader. This problem is left as an exercise in the textbook and does not need to be fully proven in the formalization. The sorry instances below are intentional — the proof requires the Pinsker estimator (projection onto first N Fourier coefficients) for the upper bound and the Varshamov-Gilbert + Fano construction for the lower bound, both of which are deep arguments outside core Chapter 5.

Statement: The minimax rate over the Sobolev ellipsoid Θ(β,Q) is n^{-2β/(2β+1)}.

def Chapter5.Problem55.sobolevEllipsoid (d : ℕ) (β Q : ℝ) : Set (Fin d → ℝ)

The Sobolev ellipsoid Θ(β, Q) in the sequence space: Θ(β, Q) = {θ : Fin d → ℝ | Σⱼ (j+1)^{2β} θⱼ² ≤ Q}.

noncomputable def Chapter5.Problem55.sobolevMinimaxRisk (d : ℕ) (β Q σ : ℝ) (n : ℕ) : ℝ

Minimax risk over the Sobolev ellipsoid Θ(β, Q). In the full formalization this would be: R*(Θ(β,Q)) = inf_{θ̂} sup_{θ ∈ Θ(β,Q)} E_θ[‖θ̂ − θ‖²]. Axiomatized as a function since the full measure-theoretic construction of the GSM minimax risk is not available.

theorem Chapter5.Problem55.sobolevMinimaxRisk_nonneg (d : ℕ) (β Q σ : ℝ) (n : ℕ) (hβ : β ≥ 5 / 3) (hQ : 0 < Q) (hσ : 0 < σ) (hn : 0 < n) : 0 ≤ sobolevMinimaxRisk d β Q σ n

The minimax risk is nonneg (it is an infimum of nonneg quantities).

theorem Chapter5.Problem55.problem_5_5 (β : ℝ) (hβ : β ≥ 5 / 3) (Q : ℝ) (hQ : 0 < Q) (σ : ℝ) (hσ : 0 < σ) (n : ℕ) (hn : 0 < n) (d : ℕ) (hd : 0 < d) : ∃ (C : ℝ) (C' : ℝ), 0 < C ∧ 0 < C' ∧ C' * ↑n ^ (-(2 * β) / (2 * β + 1)) ≤ sobolevMinimaxRisk d β Q σ n ∧ sobolevMinimaxRisk d β Q σ n ≤ C * ↑n ^ (-(2 * β) / (2 * β + 1))

Problem 5.5. The minimax rate over Θ(β,Q) is n^{-2β/(2β+1)}. There exist C, C' > 0 such that C' · n^{-2β/(2β+1)} ≤ R*(Θ(β,Q)) ≤ C · n^{-2β/(2β+1)}

Hint (from book): Consider functions of the form f_j = (C/√n) Σ_{i=1}^{N} ω_{ji} φ_i where C is a constant, ω_j ∈ {0,1}^N for some appropriately chosen N and {φ_j}_{j≥1} is the trigonometric basis. The upper bound uses the Pinsker estimator (projection onto the first N Fourier coefficients with N ~ n^{1/(2β+1)}); the lower bound uses Varshamov-Gilbert + Fano.