Past exam of the algorithmic foundations of learning course of the University of Oxford / 2025 / 2 / a / i

Work for an arbitrary realization of the sequence, and set $u_t=X_t^T{V}_{t-1}^{-1}{X}_t$. In the Loewner order,By the spectral theorem for real symmetric matrices, every eigenvalue of $V_{t-1}$ is at least $\lambda$. The matrix inverse therefore has eigenvalues at most ${\lambda }^{-1}$, andFor $0\le u\le 1$, put $g(u)=2\log (1+u)-u$. Since $g(0)=0$ and $g^{\prime }(u)=(1-u)/(1+u)\ge 0$, we have $u\le 2\log (1+u)$. The matrix determinant lemma now givesTaking logarithms and using a telescoping sum,This elliptical potential bound holds for every realization and every $n$, without a probabilistic exceptional event. The condition $\lambda \ge 1$ is what ensures $u_t\le 1$.