source/tex/Appendices/technical.tex

% !TEX root = ../main.tex

\section{Technical Lemmas}
\label{app:technical}
\begin{Lemma}[{Lemma 4.8 of \citet{pogodin2019first}}]
    \label{lem:sum_cvx}
    Let $a_1, a_2, \ldots, a_T$ be non-negative real numbers. Then
    $$
    \sum_{t=1}^T \frac{a_t}{\sqrt{1+\sum_{s=1}^{t-1} a_s}} \leq 4 \sqrt{1+\sum_{t=1}^T a_t}+\max _{t \in[T]} a_t .
    $$
\end{Lemma}
\begin{Lemma}[{Lemma 9 of \citet{yan2023universal}}]
    \label{lem:sum_scvx}
    For a sequence of $\{a_t\}_{t=1}^T$ and $b$, where $a_t, b > 0$ for any $t \in [T]$, denoting by $a_{\max} \define \max_t a_t$ and $A \define \ceil{b \sumT a_t}$, we have
    \begin{equation*}
        \sumT \frac{a_t}{bt} \le \frac{a_{\max}}{b} (1 + \log A) + \frac{1}{b^2}.
    \end{equation*}
\end{Lemma}
\begin{Lemma}[{Lemma 9 of \citet{zhao2024adaptivity}}]
    \label{lem:small-loss-sqrt}
    For any $x, y, a, b>0$ satisfying $x-y \le  \sqrt{a x}+b$, it holds that
    \begin{equation*}
        x-y \le  \sqrt{a y+ab}+a+b.
    \end{equation*}
\end{Lemma}
\begin{Lemma}[{Lemma 16 of \citet{orabona2012beyond}}]
    \label{lem:small-loss-log}
    If $a, b, c, x, y>0$ satisfy $x-y \le  a \log (b x+c)$, then it holds that
    \begin{equation*}
        x-y \le  a \log \sbr{2 a b \log \frac{2 a b}{e} + 2by + 2c}.
    \end{equation*}
\end{Lemma}