Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 205 / 4

Solution

λ P (β), P (β) = \sum_{j = 1}^{q} m_{j} ∥ β_{G_{j}} ∥_{2} .

∣ u^{T} v ∣ \leq \sum_{j} ∥ u_{G_{j}} ∥_{2} ∥ v_{G_{j}} ∥_{2} \leq max_{k} m_{k}^{- 1} ∥ v_{G_{k}} ∥_{2} \sum_{j} m_{j} ∥ u_{G_{j}} ∥_{2} .

Put

δ = β - β^{0}

. Comparing the objective at

β

and

β^{0}

gives

\frac{1}{2 n} ∥ X δ ∥_{2}^{2} \leq \frac{1}{n} ϵ^{T} X δ + λ {P (β^{0}) - P (β)} .

Ω

, the preceding duality inequality gives

\frac{1}{n} ∣ ϵ^{T} X δ ∣ \leq λ P (δ) .

P (δ) \leq P (β^{0}) + P (β)

then yields

\frac{1}{n} ∥ X (β^{0} - β) ∥_{2}^{2} \leq 4 λ P (β^{0}) .

When

m_{j} = r

and

X_{G_{j}}^{T} X_{G_{j}} = n I_{r}

\frac{∥ X _{G_{j}}^{T} ϵ ∥ _{2}^{2}}{n} \sim χ_{r}^{2} .

δ_{0} = n λ^{2} - 1 \in (0, 1)

, the exponential Markov inequality and the supplied chi-square moment-generating-function bound give

P (χ_{r}^{2} > r (1 + δ_{0})) \leq exp (- r δ_{0}^{2} /8) .

The prescribed equation makes this

q^{- (A + 1)}

q

groups therefore gives

P (Ω) \geq 1 - q^{- A} .

There are no discussions about this article yet.

There are currently no matching articles.