Exercises

For $|r| \le \delta$, $\rho_\delta'(r) = r$. For $|r|>\delta$, $\rho_\delta'(r) = \delta \cdot \mathrm{sgn}(r)$.

At $r=\delta$, the quadratic piece gives $\delta$ and the linear piece gives $\delta$. Same at $r=-\delta$. Hence $\rho_\delta \in C^1$.

If fewer than $k{+}1$ points are moved to infinity, the trimmed mean still averages only finite values. Hence the asymptotic breakdown point is $k/n$.

With $k=\lfloor n/4\rfloor$, breakdown is $1/4$ — intermediate between the mean ($0$) and the median ($1/2$).

$\psi(r) = \rho'(r) = r$. Under $F=\mathcal{N}(0,1)$, $\mathbb{E}[\psi'(X)]=1$. Hence $\mathrm{IF}(x;\bar X,F) = x/1 = x$.

$|\mathrm{IF}(x)| \to \infty$ as $|x|\to\infty$: a single outlier of magnitude $M$ shifts the mean by $M/n$, which is unbounded in $M$.

$\hat p_h(x) = \dfrac{1}{nh}\sum_{i=1}^n K\!\left(\dfrac{x-x_i}{h}\right)$.

$\int \hat p_h(x) dx = \dfrac{1}{nh}\sum_i \int K\!\left(\dfrac{x-x_i}{h}\right) dx = \dfrac{1}{n}\sum_i \int K(u)du = 1$.

$k$ is symmetric ($k(x,x')=k(x',x)$) and for every finite set $\{x_1,\dots,x_n\}$ the Gram matrix $K_{ij}=k(x_i,x_j)$ is positive semidefinite: $\boldsymbol{\alpha}^T \mathbf{K}\boldsymbol{\alpha} \ge 0$ for all $\boldsymbol{\alpha}\in\mathbb{R}^n$.

Equivalently, $k(x,x') = \sum_j \lambda_j \phi_j(x)\phi_j(x')$ with $\lambda_j\ge 0$ (in $L^2$ of a compact set).

$\psi_\delta(r) = r$ for $|r|\le\delta$ and $\psi_\delta(r)=\delta\,\mathrm{sgn}(r)$ for $|r|>\delta$. Thus $\psi_\delta(r) = w(r)\,r$ with $w(r) = \min(1,\delta/|r|)$.

The score equation $\sum_i w(r_i)(y_i-\theta)=0$ becomes $\theta^{(t+1)} = \dfrac{\sum_i w_i^{(t)} y_i}{\sum_i w_i^{(t)}}$ with $w_i^{(t)} = w(y_i-\theta^{(t)})$.

IRLS is a majorization-minimization scheme: at each step outliers (large residuals) get downweighted to $\delta/|r_i|<1$.

$\dfrac{d\,\mathrm{AMISE}}{dh} = -\dfrac{R(K)}{nh^2} + h^3 \mu_2(K)^2 R(p'') = 0$, giving $h^\star = \left(\dfrac{R(K)}{n\mu_2(K)^2 R(p'')}\right)^{1/5}$.

Substituting back, $\mathrm{AMISE}(h^\star) \propto n^{-4/5}$. This is the classical non-parametric rate for densities with bounded second derivative — slower than the parametric $n^{-1}$.

By the representer theorem, $f^\star = \sum_{j=1}^n \alpha_j k(x_j,\cdot)$ for some $\boldsymbol{\alpha}\in\mathbb{R}^n$.

Using the reproducing property $f(x_i)=(\mathbf{K}\boldsymbol{\alpha})_i$ and $\|f\|_\mathcal{H}^2 = \boldsymbol{\alpha}^T\mathbf{K}\boldsymbol{\alpha}$, the objective is $\|\mathbf{y}-\mathbf{K}\boldsymbol{\alpha}\|^2 + \lambda\boldsymbol{\alpha}^T\mathbf{K}\boldsymbol{\alpha}$.

Setting the gradient to zero: $-2\mathbf{K}(\mathbf{y}-\mathbf{K}\boldsymbol{\alpha})+2\lambda\mathbf{K}\boldsymbol{\alpha}=0$, so $\boldsymbol{\alpha}^\star = (\mathbf{K}+\lambda\mathbf{I})^{-1}\mathbf{y}$ and $f^\star(x) = \mathbf{k}(x)^T(\mathbf{K}+\lambda\mathbf{I})^{-1}\mathbf{y}$.

The posterior $f_* \mid \mathbf{y}$ is Gaussian with $\mu_*(x_*) = \mathbf{k}_*^T (\mathbf{K}+\sigma_n^2 \mathbf{I})^{-1}\mathbf{y}$ and $\sigma_*^2(x_*) = k_{**} - \mathbf{k}_*^T(\mathbf{K}+\sigma_n^2 \mathbf{I})^{-1}\mathbf{k}_*$.

The posterior mean equals the KRR solution with $\lambda=\sigma_n^2$. The posterior variance is a pure GP feature: KRR gives no uncertainty.

$\psi_c(0)=0$, $\psi_c(r)$ grows, reaches a maximum, then decreases back to $0$ at $|r|=c$. Therefore $\psi_c' = \rho_c''$ is negative for some $r$, so $\rho_c$ is non-convex.

Gradient descent / IRLS may converge to a local minimum. Good initialization (e.g. by a convex M-estimate like Huber) is essential in practice.

$(1+x_1 x_1'+x_2 x_2')^2 = 1 + 2x_1 x_1' + 2x_2 x_2' + (x_1 x_1')^2 + (x_2 x_2')^2 + 2 x_1 x_2 x_1' x_2'$.

$\phi(x) = (1,\sqrt{2}x_1,\sqrt{2}x_2,x_1^2,x_2^2,\sqrt{2}x_1 x_2) \in \mathbb{R}^6$. Then $\langle\phi(x),\phi(x')\rangle = k(x,x')$.

We compute inner products in a 6-dimensional feature space at the cost of a scalar multiplication and addition.

$\mathbf{x}^{(t+1)} = \mathcal{S}_{\tau^{(t)}}\!\left(\mathbf{W}_e^{(t)}\mathbf{y} + \mathbf{W}_s^{(t)}\mathbf{x}^{(t)}\right)$. All $(\mathbf{W}_e^{(t)},\mathbf{W}_s^{(t)},\tau^{(t)})$ are learned by backprop.

Per layer: $\mathbf{W}_e^{(t)}\in\mathbb{R}^{N\times m}$ has $Nm$ parameters, $\mathbf{W}_s^{(t)}\in\mathbb{R}^{N\times N}$ has $N^2$, and $\tau^{(t)}\in\mathbb{R}$ gives $1$. Total per layer: $Nm+N^2+1$. Over $T$ layers: $T(Nm+N^2+1)$.

Huber showed that the minimax density over the $\varepsilon$-contamination class $\{(1-\varepsilon)\mathcal{N}(0,1)+\varepsilon H\}$ is $p^\star(r) \propto \exp(-\rho_\delta(r))$: Gaussian on the core $|r|\le\delta$, Laplace tails outside.

Under $p^\star$, the log-likelihood is $-\sum_i \rho_\delta(r_i) + \text{const}$. Maximizing the log-likelihood is exactly Huber M-estimation.

The Huber M-estimator is the MLE for the worst-case density in the contamination ball — hence minimax-optimal.

$\mathbb{E}[\hat m_h(x_0) \cdot \hat f_h(x_0)] \approx m(x_0) p(x_0) + \tfrac{h^2 \mu_2}{2}((mp)'')(x_0) + O(h^4)$ where $\hat f_h$ is the KDE of the design density.

$\mathbb{E}[\hat f_h(x_0)] \approx p(x_0) + \tfrac{h^2 \mu_2}{2} p''(x_0)$.

Ratio expansion gives $\mathrm{Bias}(\hat m_h(x_0)) = \dfrac{h^2 \mu_2}{2} \left(m''(x_0) + 2\dfrac{m'(x_0)p'(x_0)}{p(x_0)}\right) + o(h^2)$. The second term is the "design bias" — it vanishes only when $p'(x_0)=0$ or $m$ is flat.

$\mathbb{E}\|\boldsymbol{\theta} - f(\mathbf{y})\|^2 = \mathbb{E}\|\boldsymbol{\theta}-\mathbb{E}[\boldsymbol{\theta}\mid\mathbf{y}]\|^2 + \mathbb{E}\|\mathbb{E}[\boldsymbol{\theta}\mid\mathbf{y}]-f(\mathbf{y})\|^2$. First term is irreducible; the second is minimized at $f^\star(\mathbf{y})=\mathbb{E}[\boldsymbol{\theta}\mid\mathbf{y}]$.

Neural nets with sufficient width can approximate $f^\star$ uniformly on compacta to any $\epsilon>0$. Thus the population minimizer matches $f^\star$.

By uniform law of large numbers, the empirical MSE converges to the population MSE, so the minimizer of the empirical MSE converges to $f^\star$ as $n\to\infty$, i.e. to the MMSE estimator.

Since $\mathcal{S}_\tau$ is $1$-Lipschitz, a perturbation $\delta^{(t)}$ at layer $t$ is amplified by $\|\mathbf{W}_s^{(t)}\|_2$ plus an injected term $\|\mathbf{W}_e^{(t)}\|_2 \cdot \|\Delta\mathbf{x}^\star\|$.

With $L=\max_t \|\mathbf{W}_s^{(t)}\|_2$ and uniform $\|\mathbf{W}_e^{(t)}\|_2 \le B$, $\|\hat{\mathbf{x}}^{(T)}_{\text{test}} - \hat{\mathbf{x}}^{(T)}_{\text{train}}\| \le B \eta \|\mathbf{x}^\star\| \cdot \dfrac{L^T - 1}{L-1}$.

If $L \ge 1$, the bound grows exponentially with depth — a concrete failure mode of distribution-shifted unfolded networks.