Problem 1 (yau-contest 2019)

Given a set $\mathcal X$, $m \in \mathbb N$ and a hypothesis space $\mathcal H$, define

$$\Pi_{\mathcal H}(m)=\max_{x_1,x_2,\ldots,x_m\in S\subset \mathcal X}\left|\{(h(x_1),h(x_2),\ldots,h(x_m))\mid h\in \mathcal H\}\right|,$$

where $|S|$ denotes the cardinality of the set $S$. The VC dimension of $\mathcal H$ is

$$\mathrm{VC}(\mathcal H)=\max\{m: \Pi_{\mathcal H}(m)=2^m\}.$$

(i) Let $\mathcal X=\mathbb R$. If $a\le b$, define $h(x;a,b)=1$ if $x\in[a,b]$ and $h(x)=-1$ if $x\notin[a,b]$. Find the VC dimension of the hypothesis space $\mathcal H=\{h(x;a,b)\mid a,b\in\mathbb R,\ a\le b\}$.

(ii) Let $\mathcal X=\mathbb R^d$, $\mathcal H$ to be the set of linear classifiers, i.e. $\mathcal H=\{f(x)\mid f(x)=\operatorname{sign}(w^Tx+b),\ w\in\mathbb R^d,\ b\in\mathbb R\}$ where $\operatorname{sign}(x)=1$ if $x>0$, $\operatorname{sign}(x)=-1$ if $x<0$ and $\operatorname{sign}(x)=0$ if $x=0$. Show that the VC dimension of $\mathcal H$ is $d+1$.

Problem 2 (yau-contest 2019)

Consider Richardson’s difference scheme for the heat equation $u_t=u_{xx}$:

$$\frac{1}{2k}\big(u(x,t+k)-u(x,t-k)\big)=\frac{1}{h^2}\big(u(x-h,t)-2u(x,t)+u(x+h,t)\big).$$

(i) Show that this scheme has second-order truncation error.

(ii) Use either ODE principles or von Neumann analysis to show that this scheme is unconditionally unstable.

(iii) Demonstrate a minor modification of the left-side of Richardson’s scheme that yields a familiar unconditionally stable scheme and prove it.

Problem 3 (yau-contest 2019)

Let $\varnothing\ne K$ be a closed convex set in $\mathbb R^n$, i.e., $K$ is a closed set and for any $x,y\in K$ and $\lambda\in(0,1)$, $\lambda x+(1-\lambda)y\in K$. For any $z\in\mathbb R^n$, let $\Pi_K(z)$ denote the metric projection of $z$ onto $K$, which is the unique optimal solution of following problem:

$$\min\ \frac{1}{2}\lVert y-z\rVert_2^2,\quad \text{s.t.}\ \ y\in K.\tag{1}$$

Show that

(i) the point $y\in K$ solves (1) if and only if

$$(z-y)^T(d-y)\le 0,\quad \forall\ d\in K;$$

(ii) for any $y,z\in\mathbb R^n$,

$$\lVert\Pi_K(y)-\Pi_K(z)\rVert_2\le \lVert y-z\rVert_2;$$

(iii) $\Theta(\cdot)$ is continuously differentiable with its gradient given by

$$\nabla\Theta(z)=z-\Pi_K(z),$$

where for any $z\in\mathbb R^n$, $\Theta(z):=\tfrac{1}{2}\lVert z-\Pi_K(z)\rVert_2^2$.

Problem 4 (yau-contest 2019)

The scientists FitzHugh (1961) and Nagumo, Arimoto, Yoshizawa (1962) derived a mathematical model to characterize the behavior of a neuron under the externally injected current $I$:

$$\begin{cases}
\dfrac{dV}{dt}=V-\tfrac{1}{3}V^3-W+I,\\[4pt]
\dfrac{dW}{dt}=\dfrac{1}{\tau}\big(V+a-bW\big),
\end{cases}$$

where the variable $V$ describes the membrane potential of the neuron, the variable $W$ describes the current arising from opening and closing of ion channels on the neurons membrane. The variables $\tau$, $a$ and $b$ are parameters with typical values: $a=0.7$, $b=0.8$ and $\tau=13$.

(i) For a small positive constant current $I$, how the neuron behaves.

(ii) For a large positive constant current $I$, how the neuron behaves.

(iii) Suppose one injects a pulse current with different magnitude at some time $t_0$, i.e., $I=I_0\delta(t-t_0)$, where $I_0$ describes the magnitude of the pulse, analyze the dynamical behavior of the neuron when $I_0$ is small or large.