As per definition in an Introduction to Online Convex Optimization by E. Hazan ( 2015). Can't figure out to proof that the dual norm of the following defined matrix norms equals the inverse matrix norm:
$||x||_A = \sqrt{x^T A x}$
$||x||_A^* = ||x||_{A^{-1}}$
Sure. (You need to assume that $A$ is symmetric positive definite, which ensures that $x^T A x > 0$ for all nonzero $x$.)
We assume $x \neq 0$, otherwise the result is trivial. First recall that $$ \|x\|_{A}^\ast := \sup\{x^T y : y^T A y \leq 1\} $$
So consider $y = A^{-1} x/\sqrt{x^T A^{-1} x}$ (the denominator is nonzero since $A$ is full rank and $x$ is nonzero). Note that $y^T A y = 1$, and hence this implies $\|x\|_{A}^\ast \geq \sqrt{x^T A^{-1} x}$.
Conversely, note whenever $y^T A y \leq 1$, we may define $z = A^{1/2} y$, in which case $x^T y = x^T A^{-1/2} z$, where $\|z\|_2 \leq 1$. But then by Cauchy-Schwarz, we have $x^T y \leq \|A^{-1/2} x\|_2 \|z\|_2 \leq \sqrt{x^T A^{-1} x}$. Passing to the supremum over $y$, we have shown $\|x\|_{A}^\ast \leq \sqrt{x ^T A^{-1} x}$.