text:
\begin{document}

\icmltitle{Supplementary Materials}

\begin{icmlauthorlist}
    \icmlauthor{Huang Fang}{ubc}
    \icmlauthor{Nicholas J.~A.~Harvey}{ubc}
    \icmlauthor{Victor S.~Portella}{ubc}
    \icmlauthor{Michael P. Friedlander}{ubc}
    \end{icmlauthorlist}

    \icmlaffiliation{ubc}{Department of Computer Science, University of British Columbia, Canada}

    \icmlcorrespondingauthor{Huang Fang}{hgfang@cs.ubc.ca}
    \icmlcorrespondingauthor{Nicholas J.~A.~Harvey}{nickhar@cs.ubc.ca}
    \icmlcorrespondingauthor{Victor S.~Portella}{victorsp@cs.ubc.ca}
    \icmlcorrespondingauthor{Michael P.~Friedlander}{mpf@cs.ubc.ca}

\appendix

\section{Facts and propositions}

\subsection{Scalar inequalities}

\begin{fact}
\FactName{quadratic}
For any $a > 0$ and $b, x \in \R$, we have $-a x^2 + b x \leq b^2 / 4a$.
\end{fact}

\begin{fact}
\FactName{ExpTaylor2}
$ e^{-x} \leq 1 - x + \frac{x^2}{2} $ for $x \geq 0$.
\end{fact}

\begin{fact}
\FactName{SquareRoot}
$\sum_{i=1}^t \frac{1}{\sqrt{i}} \leq 2\sqrt{t} - 1$ for $t \geq 1$.
\end{fact}

\begin{fact}
\FactName{LogBound}
$\log(x) \leq x-1$ for $x \geq 0$.
\end{fact}

The following proposition is a variant of an inequality
that is frequently used in online learning; see, e.g., \citep[Lemma 3.5]{AuerCG02}, \citep[Lemma 4]{McMahan17}.

\begin{restatable}{proposition}{Auer}
\label{prop:at_sum}
Let $u>0$ and $a_1, a_2, \ldots, a_T \in [0,u]$.
Then
\[
\sum_{t=1}^T \frac{a_t}{\sqrt{ u + \sum_{i<t} a_i }}
~\leq~ 2 \sqrt{ \sum_{t=1}^T a_t }.
\]
\end{restatable}

Although it is easy to prove this inequality by induction, the following proof may provide more intuition.
The proof is based on a generic lemma on approximating sums by integrals.

\begin{lemma}[Sums with chain rule]
\label{lem:SumIntegral}
Let $S \subseteq \R$ be an interval.
Let $F : S \rightarrow \R$ be concave
and differentiable on the interior of $S$.
Let $u \geq 0$ and let $A : \set{0,\ldots,T} \rightarrow S$ satisfy $A(i)-A(i-1) \in [0,u]$ for each $1 \leq i \leq T$.
Then
$$
\sum_{i=1}^T F'\big( u+A(i-1) \big) \cdot (A(i) - A(i-1))
    ~\leq~ F(A(T))-F(A(0)).
$$
\end{lemma}

As $u \rightarrow 0$, the left-hand side becomes comparable to
$\int_0^T F'(A(x)) A'(x) \, dx$,
an expression that has no formal meaning since $A$ is only defined on integers.
If this expression existed, it would equal the right-hand side by
the chain rule.

\begin{proof}[Proof of Lemma~\ref{lem:SumIntegral}]
Since $F$ is concave, $f:=F'$ is non-increasing.
Fix any $1 \leq i \leq T$
and observe that $f(x)  \geq f(A(i)) \geq f(u+A(i-1))$ for all $x \leq A(i)$.
Thus
$$ f(u+A(i-1))\cdot(A(i)-A(i-1))
    ~\leq~ \int_{A(i-1)}^{A(i)} f(x) \, dx
    ~=~ F(A(i))-F(A(i-1)). $$
Summing over $i$, the right-hand side telescopes, which yields the result.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:at_sum}]
Apply Lemma~\ref{lem:SumIntegral}
with $S = \R_{\geq 0}$, $F(x) = 2 \sqrt{x}$ and $A(i) = \sum_{1 \leq j \leq i} a_j$.
\end{proof}

\begin{proposition}
\PropositionName{ineq_xy}
Let $x,y, \alpha, \beta > 0$.
\begin{align*}
\text{If}\quad
x-y &~\leq~ \alpha \sqrt{x} + \beta \\
\text{then}\quad
x-y &~\leq~ \alpha \sqrt{y} + \beta + \alpha \sqrt{\beta} + \alpha^2.
\end{align*}
\end{proposition}

\begin{proof}
The proposition's hypothesis yields
\[
y + \beta + \frac{\alpha^2}{4}
~\geq~ x - \alpha \sqrt{x} + \frac{\alpha^2}{4}
~=~ \left( \sqrt{x} - \frac{\alpha}{2} \right)^2.
\]
Taking the square root and rearranging,
\[
\sqrt{x} ~\leq~
    \sqrt{y + \beta + \frac{\alpha^2}{4}} + \frac{\alpha}{2}.
\]
Squaring both sides and rearranging,
\begin{align*}
x
&~\leq~ y + \alpha \sqrt{y + \beta + \frac{\alpha^2}{4}} + \beta + \frac{\alpha^2}{2} \\
&~\leq~ y + \alpha \sqrt{y} + \alpha\sqrt{\beta} + \beta + \alpha^2,
\end{align*}
by subadditivity of the square root.
\end{proof}

\subsection{Bregman divergence properties}
\label{app:Bregman}

The following lemma collects basic facts regarding the Bregman
divergence induced by a mirror map of the Legendre type.
See~\citep{mdlec} and~\citep[Chapter~26]{roc70}. For a detailed
discussion on the necessity (or the lack thereof) of mirror maps of
Legendre type, see~\citep[Chapter~5]{introduction-online-optimization}

\begin{lemma} \label{lem:bregman-div} The Bregman divergence induced
  by $\Phi$ satisfies the following properties:
\begin{itemize}
    \item $D_\Phi(x, y)$ is convex in $x$;
    \item $\nabla \Phi ( \nabla \Phi^* (z) ) = z$ \ and \
      $\nabla^* \Phi ( \nabla \Phi (x) ) = x$ \ for all $x$ and $z$;
    \item
      $D_\Phi(x, y) = D_{ \Phi^* } ( \nabla \Phi(y), \nabla \Phi(x) )$
      \ for all $x$ and $y$.
\end{itemize}
\end{lemma}

\begin{proposition}
\PropositionName{BregmanStrong}
If $\Phi$ is $\rho$-strongly convex with respect to $\norm{\cdot}$ then
$D_\Phi(x,y) \geq \frac{\rho}{2} \norm{x-y}^2$.
\end{proposition}

\subsubsection{Differences of Bregman divergences}
\AppendixName{TriBrerocg}

Recall that in Section~\ref{sec:preliminaries} we defined the notation
\[
\TriBreg{a}{b}{c}
 ~\coloneqq~ D_\Phi(a,c) - D_\Phi(b,c)
 ~=~ \Phi(a)-\Phi(b) - \inner{ \nabla \Phi(c) }{ a-b }.
\]
This has several useful properties, which we now discuss.

\begin{proposition}
\PropositionName{TriBregLinear}
$\TriBreg{a}{b}{p}$ is linear in $\hat{p}$.
In particular,
\[
\TriBreg{a}{b}{\Grad \Phi^*(\hat{p}-\hat{q})}
    ~=~ \TriBreg{a}{b}{p} + \inner{\hat{q}}{a-b}
    \qquad\forall \hat{q} \in \bR^n.
\]
\end{proposition}
\begin{proof}
Immediate from the definition.
\end{proof}

\begin{proposition}
\PropositionName{GeneralBregmanTriangle}
For all $a,b,c,d \in \cD$,
$$

\TriBreg{a}{b}{d} - \TriBreg{a}{b}{c}
~=~
\inner{ \hat{c} - \hat{d} }{ a - b }
~=~ \TriBreg{a}{b}{d} + \TriBreg{b}{a}{c}.
$$
\end{proposition}
\begin{proof}

The first equality holds from \Proposition{TriBregLinear}
with $\hat{p} = \hat{c}$ and $\hat{q} = \hat{c} - \hat{d}$.
The second equality holds since $\TriBreg{b}{a}{c} = -\TriBreg{a}{b}{c}$.
\end{proof}

An immediate consequence is the ``generalized triangle inequality
for Bregman divergence''.
See Bubeck~\citep[Eq.~(4.1)]{Bubeck15}, Beck and Teboulle \citep[Lemma 4.1]{BeckT03}
or Zhang~\citep[Eq.~(3)]{mdlec}.

\begin{proposition}
\PropositionName{BregmanTriangle}
For all $a,b,d \in \cD$,
$$ D_\Phi(a,d) - D_\Phi(b,d) + D_\Phi(b,a)
~=~
\inner{ \hat{a} - \hat{d} }{ a - b }
$$
\end{proposition}
\begin{proof}
Apply \Proposition{GeneralBregmanTriangle} with $c=a$ and use $D_\Phi(a,a)=0$.
\end{proof}

\begin{proposition}
\PropositionName{BregmanIdentity}
Let $a,b,c,u,v \in \R^n$ satisfy
$\gamma \hat{a} + (1-\gamma) \hat{b} = \hat{c}$
for some $\gamma \in \bR$.
Then
$$
        \gamma   \TriBreg{u}{v}{a}
\:+\: (1-\gamma) \TriBreg{u}{v}{b}
~=~              \TriBreg{u}{v}{c}.
$$
\end{proposition}

\begin{proof}
By definition of $D_\Phi$, the claimed identity is equivalent to
$$
      (1-\gamma) \big( \Phi(u)-\Phi(v) - \inner{\Grad \Phi(a)}{u-v} \big)
\:+\:   \gamma   \big( \Phi(u)-\Phi(v) - \inner{\Grad \Phi(b)}{u-v} \big)
~=~
                 \big( \Phi(u)-\Phi(v) - \inner{\Grad \Phi(c)}{u-v} \big).
$$
This equality holds by canceling $\Phi(u)-\Phi(v)$ and by the assumption that
$\Grad \Phi(c) = (1-\gamma) \Grad\Phi(a) + \gamma \Grad\Phi(b)$.
\end{proof}

The following proposition is the ``Pythagorean theorem for Bregman divergence''.
Recall that $\Pi_\cX^\Phi(y) = \argmin_{u \in \cX} D_\Phi(u,y)$.
Proofs may be found in~\citep[Lemma 4.1]{Bubeck15}
or~\citep[Eq.~(17)]{mdlec}.

\begin{proposition}
\PropositionName{BregmanProjection}
Let $\cX \subset \bR^n$ be a convex set.
Let $p \in \bR^n$ and $\pi = \Pi_\cX^\Phi(p)$.
Then
$$
\TriBreg{z}{\pi}{p}
    ~\geq~ \TriBreg{z}{\pi}{\pi}
    ~=~    D_\Phi(z,\pi)
    \qquad\forall z \in \cX.
$$
\end{proposition}

A generalization of the previous proposition can be obtained by using the linearity property.

\begin{proposition}
\PropositionName{GeneralBregmanProjection}
Let $\cX \subset \bR^n$ be a convex set.
Let $p \in \bR^n$ and $\pi = \Pi_\cX^\Phi(p)$.
Then
$$
\TriBreg{v}{\pi}{\Grad \Phi^*(\hat{p}-\hat{q})}
    ~\geq~ \TriBreg{v}{\pi}{\Phi^*(\hat{\pi}-\hat{q})}
    \qquad\forall v \in \cX ,\, \hat{q} \in \bR^n.
$$
\end{proposition}
\begin{proof}
\begin{align*}
\TriBreg{v}{\pi}{\Grad \Phi^*(\hat{p}-\hat{q})}
    &~=~ \TriBreg{v}{\pi}{p} + \inner{\hat{q}}{v-\pi}
        &&\qquad\text{(by \Proposition{TriBregLinear})} \\
    &~\geq~ \TriBreg{v}{\pi}{\pi} + \inner{\hat{q}}{v-\pi}
        &&\qquad\text{(by \Proposition{BregmanProjection})} \\
    &~=~ \TriBreg{v}{\pi}{\Grad \Phi^*(\hat{\pi}-\hat{q})}
        &&\qquad\text{(by \Proposition{TriBregLinear})} \qedhere
\end{align*}
\end{proof}

\comment{
\begin{lemma}
\label{lemma:cvx}
    $D_{\Phi}(x, \nabla \Phi^*(\hat{y}) ) $ is convex in $\hat{y}$.
\end{lemma}

\begin{proof}(Proof of Lemma~\ref{lemma:cvx}.)
  Use Lemma~\ref{lem:bregman-div} (in Appendix~\ref{app:Bregman}) to deduce that
  \begin{align*}
    D_{\Phi}(x, \nabla \Phi^*(\hat{y}) ) & = D_{\Phi^*}( \nabla \Phi( \nabla \Phi^*(\hat{y}) ), \nabla \Phi(x) )  = D_{\Phi^*}(\hat{y}, \nabla \Phi(x)).
  \end{align*}
  Lemma~\ref{lem:bregman-div} states that $D_{\Phi^*}(\hat{y}, \hat{x})$ is convex in $\hat{y}$.
  We conclude that $D_{\Phi}(x, \nabla \Phi^*(\hat{y}) ) $ is convex in $\hat{y}$.
\end{proof}
}

\section{Missing details from the proof of~\Theorem{somd}}
\AppendixName{dsomd_details}

Due to space constraints we had to omit some calculations  from the proof of~\Theorem{somd} the main body of the paper. In particular, we claimed that summing the expression from \Claim{NewDSOMD} over \(t \in [T]\) yields~\Theorem{somd}. For the sake of completeness we present the missing calculations.
\\

    \begin{mdframed}
        Summing \eqref{eq:regret_at_each_round} over $t$
        and using \Claim{NewDSOMD} leads to the desired telescoping sum.
        \begin{align*}
        \sum_{t=1}^T \big( f_t(x_t) - f_t(z) \big)
            &~\leq~ \sum_{t=1}^T \Bigg(\frac{
            \TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} + \Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big) D_\Phi(z, x_1) + \frac{D_\Phi(z, x_t)}{\eta_t} -\frac{D_\Phi(z, x_{t+1})}{\eta_{t+1}} \Bigg) \nonumber
            \\
            &~\leq~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t}
              \:+\: \left( \frac{1}{\eta_1} + \sum_{t=1}^T \left( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \right)  \right){D_\Phi(z, x_1)}  \nonumber
            \\
            &~=~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} \:+\: \frac{ D_\Phi(z, x_1) }{\eta_{T+1}}.
        \end{align*}
    \end{mdframed}

\section{Proof of \Theorem{psomd}}
\AppendixName{psomd_proof}

\begin{proofof}{\Theorem{psomd}}
    \mbox{}
\begin{mdframed}
    Fix $z \in \X$. The first step is the same as in \Theorem{somd}.
\begin{align}
    f_t(x_t) - f_t(z) &~\overset{\rm(i)}\leq~ \langle \ghat_t, x_t - z \rangle \nonumber \\
    &~=~ \frac{1}{\eta_t} \langle \hat{x}_t - \hat{w}_{t+1}, x_t - z \rangle \nonumber \\

    &~\overset{\rm(ii)}=~ \frac{1}{\eta_t} \Big( D_\Phi(x_t, w_{t+1} ) + D_\Phi(z, x_t) - D_\Phi(z, w_{t+1}) \Big)
    \EquationName{PrimalOMDSubgradient}

\end{align}
Here (i) is the subgradient inequality.
For (ii), recall our notation $\hat x_t = \nabla \Phi(x_t)$ and
$\hat w_{t+1} = \Grad \Phi(w_{t+1})$,
then use the generalized triangle inequality for Bregman divergences (\Proposition{BregmanTriangle}).
\end{mdframed}

From \Claim{NewPSOMD} and the definition $\gamma_t = \eta_{t+1}/\eta_t$, we obtain
\begin{align}\EquationName{PrimalOMDConvexity}
D_\Phi(z,w_{t+1})
    ~\geq~ \frac{\eta_t}{\eta_{t+1}} D_\Phi(z,x_{t+1})
        - \Big(\frac{\eta_t}{\eta_{t+1}}-1\Big) D_\Phi(z,x_1)
        + D_\Phi(y_{t+1},w_{t+1}).
\end{align}
\begin{mdframed}
The remainder is very similar to \Theorem{somd}.
Plugging \eqref{eq:PrimalOMDConvexity} into \eqref{eq:PrimalOMDSubgradient}, we obtain
\begin{align}\nonumber
\eqref{eq:PrimalOMDSubgradient}
 &~\leq~ \frac{1}{\eta_t} \Bigg( D_\Phi(x_t, w_{t+1} ) + D_\Phi(z, x_t) - \frac{\eta_t}{\eta_{t+1}} D_\Phi(z, x_{t+1}  ) + \Big(\frac{\eta_t}{\eta_{t+1}}-1\Big) D_\Phi(z, x_1) - D_\Phi( y_{t+1}, w_{t+1}) \Bigg)

\\\label{eq:regret_at_each_round2}
 &~=~ \frac{D_\Phi(x_t, w_{t+1} ) - D_\Phi( y_{t+1}, w_{t+1})}{\eta_t} + \frac{D_\Phi(z, x_t)}{\eta_t} -\frac{D_\Phi(z, x_{t+1})}{\eta_{t+1}} + \Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big) D_\Phi(z, x_1).
\end{align}

Summing \eqref{eq:regret_at_each_round2} over $t$, the $D_\Phi(z,x_t)$ terms telescope, and we obtain
\begin{align}\nonumber
&\sum_{t=1}^T \big( f_t(x_t) - f_t(z) \big)\\  \nonumber
    &~\leq~ \sum_{t=1}^T \Bigg(\frac{D_\Phi(x_t, w_{t+1} ) - D_\Phi( y_{t+1}, w_{t+1})}{\eta_t} + \frac{D_\Phi(z, x_t)}{\eta_t} -\frac{D_\Phi(z, x_{t+1})}{\eta_{t+1}} + \Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big) D_\Phi(z, x_1) \Bigg) \nonumber
    \\
    &~\leq~ \sum_{t=1}^T \frac{D_\Phi(x_t, w_{t+1} ) - D_\Phi( y_{t+1}, w_{t+1})}{\eta_t}
      \:+\: \left( \frac{1}{\eta_1} + \sum_{t=1}^T \left( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \right)  \right){D_\Phi(z, x_1)}  \nonumber
    \\
    &~=~ \sum_{t=1}^T \frac{D_\Phi(x_t, w_{t+1} ) - D_\Phi( y_{t+1}, w_{t+1})}{\eta_t} \:+\: \frac{ D_\Phi(z, x_1) }{\eta_{T+1}}, \label{eq:regret}
\end{align}
as desired.
\end{mdframed}

\end{proofof}

\section{Proof of \Theorem{DualAveraging}}
\AppendixName{da_regret_proof}

\begin{proofof}{{\Theorem{DualAveraging}}}
As previously mentioned, this proof parallels the proof of \Theorem{somd}.
\begin{mdframed}
    Fix $z \in \X$. The first step is very similar to the proof of \Theorem{somd}.
    \begin{align}
        f_t(x_t) - f_t(z) &~\leq~ \inner{ \ghat_t }{ x_t - z }
        \qquad\text{(subgradient inequality)}
        \nonumber\\
        &~=~ \frac{1}{\eta_t} \inner{ \hat{y}_t - \hat{w}_{t+1} }{ x_t - z } \qquad\text{(by \eqref{eq:Lazy})}\nonumber\\
        &~=~ \frac{1}{\eta_t} \Big( D_\Phi(x_t,w_{t+1})
        - D_\Phi(z,w_{t+1}) + \TriBreg{z}{x_t}{y_t} \Big)
        .
        \EquationName{da_regret_at_each_round}
    \end{align}
    where we have used \Proposition{GeneralBregmanTriangle} instead of \Proposition{BregmanTriangle}.
    \end{mdframed}

    As in the proof of \Theorem{somd}, the next step is to relate $D_\Phi(z,w_{t+1})$ to $D_\Phi(z,y_{t+1})$ so that \eqref{eq:da_regret_at_each_round} can be bounded using a telescoping sum.
    The following claim is similar to \Claim{NewDSOMD}.

    \begin{claim}
    \ClaimName{NewDA}
    Assume that $\gamma_t = \eta_{t+1}/\eta_t \in (0,1]$.
    Then
    \[
    \eqref{eq:da_regret_at_each_round}
    ~\leq~
    \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} +
    \underbrace{\Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big)}_{\text{telescopes}}
    D_\Phi(z, x_1) +
    \underbrace{\frac{\TriBreg{z}{x_t}{y_t}}{\eta_t} -\frac{\TriBreg{z}{x_{t+1}}{y_{t+1}}}{\eta_{t+1}}}_{\text{telescopes}}.
    \]
    \end{claim}
    \begin{proof}
    The first two steps are identical to the proof of \Claim{NewDSOMD}.
    \begin{alignat*}{2}
    &         \gamma_t \big(D_\Phi(z,w_{t+1}) - D_\Phi(x_{t+1},w_{t+1})\big)
    \:+\: (1-\gamma_t) D_\Phi(z,x_1) &&\\
    ~\geq~&
             \gamma_t \TriBreg{z}{x_{t+1}}{w_{t+1}}
    \:+\: (1-\gamma_t) \TriBreg{z}{x_{t+1}}{x_1}
        &&\qquad\text{(since $D_\Phi(x_{t+1},x_1)\geq 0$ and $\gamma_t \leq 1$)}\\
    ~=~&
    \TriBreg{z}{x_{t+1}}{y_{t+1}}
    &&\qquad\text{(by \Proposition{BregmanIdentity} and \eqref{eq:DAStabilization})}.
    \end{alignat*}
    Rearranging and using $\gamma_t > 0$ yields
    \begin{equation}\EquationName{DARearrange}
    D_\Phi(z,w_{t+1})
    ~\geq~
    D_\Phi(x_{t+1},w_{t+1})
    \:-\: \Big(\frac{1}{\gamma_t}-1\Big) D_\Phi(z,x_1)
    \:+\:
    \frac{\TriBreg{z}{x_{t+1}}{y_{t+1}}}{\gamma_t}.
    \end{equation}
    Plugging this into \eqref{eq:da_regret_at_each_round} yields
    \begin{align*}
    \eqref{eq:da_regret_at_each_round}
    &~=~
    \frac{1}{\eta_t} \Big( D_\Phi(x_t,w_{t+1})
        - D_\Phi(z,w_{t+1}) + \TriBreg{z}{x_t}{y_t} \Big)
    \\
    &~\leq~
    \frac{1}{\eta_t} \Bigg( D_\Phi(x_t,w_{t+1})
    - D_\Phi(x_{t+1},w_{t+1})
    + \Big(\frac{1}{\gamma_t}-1\Big) D_\Phi(z,x_1)
    - \frac{\TriBreg{z}{x_{t+1}}{y_{t+1}}}{\gamma_t}
    + \TriBreg{z}{x_t}{y_t}
     \Bigg),
    \end{align*}
    by \eqref{eq:DARearrange}.
    The claim follows by the definition of $\gamma_t$.
    \end{proof}

    \begin{mdframed}
    The final step is very similar to the proof of \Theorem{somd}.
    Summing \eqref{eq:da_regret_at_each_round} over $t$ and using \Claim{NewDA} leads to the desired telescoping sum.
    \begin{align*}
    \sum_{t=1}^T \big( f_t(x_t) - f_t(z) \big)
        &~\leq~ \sum_{t=1}^T \Bigg(\frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} + \Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big) D_\Phi(z, x_1) + \frac{\TriBreg{z}{x_t}{y_t}}{\eta_t} -\frac{\TriBreg{z}{x_{t+1}}{y_{t+1}}}{\eta_{t+1}} \Bigg)
        \\
        &~\leq~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t}
          \:+\: \left( \frac{1}{\eta_1} + \sum_{t=1}^T \left( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \right)  \right){D_\Phi(z, x_1)}
        \\
        &~=~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} \:+\: \frac{ D_\Phi(z, x_1) }{\eta_{T+1}}.
    \end{align*}
    For the second inequality we have also used that $\TriBreg{z}{x_1}{y_1}=D_\Phi(z,x_1)$ since $x_1=y_1$. Thus, the above shows that
    \begin{equation}\EquationName{DAAlmostDone}
      \mathrm{Regret}(T, z) ~\leq~ \sum_{t=1}^T \frac{
      \TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} + \frac{ D_\Phi(z, x_1) }{\eta_{T+1}}
      \quad \forall T > 0.
    \end{equation}

    \end{mdframed}

    Notice that \eqref{eq:DAAlmostDone} is syntactically identical to \eqref{eq:RegretBound};
    the only difference is the definition of $w_{t+1}$ in these two settings.
    However the bound \eqref{eq:DAAlmostDone} requires further development because, curiously, this proof has not yet used the definition of $x_t$.
    To conclude the theorem, we will provide an upper bound on \eqref{eq:DAAlmostDone} that incorporates the definition $x_t = \Pi_\cX^\Phi(y_t)$.
    Specifically, we will control $\TriBreg{x_t}{x_{t+1}}{w_{t+1}}$ by applying \Proposition{GeneralBregmanProjection} as follows.
    Taking $p = y_t$, $\pi = x_t = \Pi_\cX^\Phi(y_t)$, $v=x_{t+1}$ and $\hat{q} = \eta_t \ghat_t$, we obtain
    \begin{align*}
        \TriBreg{x_t}{x_{t+1}}{w_{t+1}}
            &~=~ -\TriBreg{v}{\pi}{\Grad\Phi^*(\hat{p} - \hat{q})}
                \qquad\text{(since $\hat{w}_{t+1} = \hat{y}_t - \eta_t \ghat_t = \hat{p}-\hat{q}$)} \\
            &~\leq~ -\TriBreg{v}{\pi}{\Grad\Phi^*(\hat{\pi} - \hat{q})}
                \qquad\text{(by \Proposition{GeneralBregmanProjection})} \\
            &~=~ \TriBreg{x_t}{x_{t+1}}{\Grad\Phi^*(\hat{x}_t - \eta_t \ghat_t)}.
    \end{align*}
    Plugging this into \eqref{eq:DAAlmostDone} completes the proof.
\end{proofof}

\section{Additional proofs for \Section{strongly-convex-ds-omd}}
\AppendixName{strongly-convex-ds-omd}

\begin{proofof}{\Proposition{StrongConvexBound}}
First we apply \Proposition{BregmanTriangle} with $a=x$, $b=x'$ and $d=\Grad\Phi^*(\hat{x}-\hat{q})$ to obtain
\begin{align*}
\TriBreg{x}{x'}{w}

&~=~ \inner{\hat{x}-\hat{d}}{x-x'} - D_\Phi(x',x) \\
&~=~ \inner{\hat{q}}{x-x'} - D_\Phi(x',x) \\
&~\leq~ \norm{\hat{q}}_* \norm{x-x'} - \frac{\rho}{2}\norm{x-x'}^2
    &&\qquad\text{(definition of dual norm and \Proposition{BregmanStrong})}\\
&~\leq~ \norm{\hat{q}}_*^2 / 2 \rho
    &&\qquad\text{(by \Fact{quadratic})}.
    \qedhere
\end{align*}
\end{proofof}

\section{Additional proofs for \Section{rwm-ds-omd}}
\AppendixName{rwm-ds-omd}

An initial observation shows that
$\Lambda$ is non-negative in the experts' setting.
\begin{proposition}
\PropositionName{LambdaNonNeg}
$\Lambda(a,b) \geq 0$ for all $a \in \cX$, $b \in \cD$.
\end{proposition}
\begin{proof}
Let us write $\Lambda(a,b) = - \sum_{i=1}^n a_i \ln \frac{b_i}{a_i} +
\ln\big(\sum_{i=1}^n b_i\big)$. Since $a$ is a probability distribution,
we may apply Jensen's inequality to show that this expression is
non-negative.
\end{proof}

\begin{proofof}{\Proposition{dual_somd_KL}}
Since $a, b \in \cX$ we have $\norm{a}_1=\norm{b}_1=1$.
Then
\begin{align*}
\TriBreg{a}{b}{c}
        &~=~ D_\KL(a,c) - D_\KL(b,c) \\
        &~=~ \big(D_\KL(a,c) + 1 - \norm{c}_1 + \ln\norm{c}_1\big)
           - \big(D_\KL(b,c) + 1 - \norm{c}_1 + \ln\norm{c}_1 \big) \\
        &~=~ \Lambda(a,c) - \Lambda(b,c)
        \qquad\text{(by definition of $\Lambda$)} \\
        &~\leq~ \Lambda(a,c)
        \qquad\text{(by \Proposition{LambdaNonNeg}).}
        \qedhere
\end{align*}
\end{proofof}

\begin{proofof}{\Proposition{LambdaTaylor}}
Let $b = \Grad\Phi^*(\hat{a}-\eta\hat{q})$.
By \eqref{eq:ExpertMirror}, $b_i = a_i \exp(-\eta \hat{q}_i)$.
Then
\begin{align*}
\Lambda(a,\Grad\Phi^*(\hat{a}-\eta\hat{q}))
&~=~ \sum_{i=1}^n a_i \ln(a_i/b_i) + \ln \norm{b}_1 \\
&~=~ \sum_{i=1}^n \eta a_i \hat{q}_i + \ln\Big(\sum_{i=1}^n a_i \exp(-\eta \hat{q}_i) \Big)\\
&~\leq~ \sum_{i=1}^n \eta a_i \hat{q}_i + \sum_{i=1}^n a_i \exp(-\eta \hat{q}_i) - 1
\qquad\text{(by \Fact{LogBound})}\\
&~\leq~ \sum_{i=1}^n \eta a_i \hat{q}_i
 + \sum_{i=1}^n a_i \left( 1 - \eta \hat{q}_i + \frac{ \eta^2 \hat{q}_{i}^2 }{2} \right) - 1 \qquad\text{(by \Fact{ExpTaylor2})} \\
&~\leq~ \eta^2 \sum_{i=1}^n a_i \hat{q}_i/2,
\end{align*}
using $\sum_{i=1}^n a_i = 1$ (since $a \in \cX$)
and $\hat{q}_i^2 \leq \hat{q}_i$ (since $\hat{q} \in [0,1]^n$).
\end{proofof}

\section{Remarks on lower bounds fo the expert's problem}
\label{sec:app_lowerbound}

We have seen that dual averaging achieves
regret $\sqrt{ T \ln n }$ for all $T$.  Here we present a
lower bound analysis for DA showing that this is the best one can hope for.

\begin{theorem}
\label{thm:lowerbound_arwm}
There exists a value of $n$ such that,
for every $T>0$, there exists a sequence of vectors $\{c_i \mid c_i \in \{0,1\}^n \}_{i=1}^T$, such that
\[
    \underset{t \to \infty}{\lim }\ \frac{ \mathrm{Regret}_{\text{DA} }(t)  }{ \sqrt{ t \ln n } }
    ~\geq~ 1,

\]
where $\mathrm{Regret}_{\text{DA} }(T)$ denotes the worst-case regret (that is, taking the supremum of the comparison point over the simples) of the dual averaging algorithm used in \citep[Theorem 2.4]{introduction-online-optimization}.
\end{theorem}

It is known in the literature~\citep[\S 3.7]{game_prediction} that no algorithm can achieve a regret bound better than $\sqrt{\smash[b]{\sfrac{T}{2} \, \ln n}}$ for the problem of learning with expert advice (as $(T,n) \rightarrow \infty$).

Thus, there is still a $\sqrt{2}$ gap between the best upper and lower bounds (that hold for all $T$) for prediction with expert advice.
This gap was previously pointed out by \citet[pp.~52]{Ger11}.

\begin{algorithm}[H]
    \caption{Adaptive randomized weighted majority based on DA~\cite{game_prediction}}
    \label{alg:lazy_arwm_supp}
 \begin{algorithmic}
    \STATE {\bfseries Input:} $\eta:\mathbb{N} \rightarrow \R $

    \STATE $x_1 = [1/n, 1/n, ...]$
    \FOR{$t=1,2,\ldots$}
         \STATE Incur cost $f(x_t)$ and receive $\ghat_t \in \partial f_t(x_t)$
         \FOR{j=1,2,...,n}
             \STATE $y_{t+1,j} = x_{1,j} \exp \left( - \eta_t \sum_{k=1}^t \ghat_{k}(j) \right)$
         \ENDFOR
         \STATE $x_{t+1} = y_{t+1} / \| y_{t+1} \|_1$
    \ENDFOR

 \end{algorithmic}
 \end{algorithm}

\begin{proof}
The detailed algorithm described in \citep[Theorem 2.4]{introduction-online-optimization} is shown in Algorithm~\ref{alg:lazy_arwm_supp}, where $\eta_t$ is set as $\sqrt{4\ln n/ t}$, we consider the case when $n=2$, and construct the following cost vectors:
\[
c_t =
\begin{cases}
[1, 0]^\intercal \qquad 1 \leq t <  \tau, t~\text{is odd} \\
[0, 1]^\intercal \qquad 1 \leq t <  \tau, t~\text{is even} \\
[1, 0]^\intercal \qquad \tau \leq t \leq T,
\end{cases}
\qquad \forall t \geq 1,
\]
where $\tau \coloneqq \lfloor T - \log (T) \sqrt{T} \rfloor$.
Without loss of generality, we assume that $\tau$ is an odd number.

Throughout the remainder of this proof, denote \(\Regret(T)\) as the worts-case regret on \(T\) rounds, that is,
\begin{equation*}
    \Regret(T) \coloneqq \sup_{z \in \Delta_n} \Regret(T, z).
\end{equation*}
It is obvious that the second expert is the best one and our regret at time $T$ is
\[
\mathrm{Regret}(T) = \sum_{ 1 \leq t < \tau } c_t^\intercal x_t -  \frac{\tau -1 }{2} + \sum_{ \tau \leq t \leq  T } c_t^\intercal x_t
\]
It is also easy to check that
\[
x_t =
\begin{cases}
[1/2, 1/2]^\intercal \qquad 1 \leq t <  \tau, t~\text{is odd} \\
\displaystyle \left[\frac{1}{1+\exp(\eta_{t-1}) } , \frac{1}{1 + \exp( -\eta_{t-1} )} \right]^\intercal \qquad 1 \leq t < \tau, t~\text{is even} \\
\displaystyle \left[\frac{1}{1+\exp(\eta_{t-1}(t - \tau) ) } , \frac{1}{1 + \exp( -\eta_{t-1}(t - \tau) )} \right]^\intercal \qquad \tau \leq t \leq T
\end{cases}
\]
\begin{align*}
    \mathrm{Regret}(T) = \underbrace{ \sum_{1 \leq t < \tau, t~\text{is even} } \left( \frac{1}{1 + \exp( -\eta_{t-1} )} - \frac{1}{2} \right) }_{\text{Term 1}}+ \underbrace{ \sum_{t=\tau}^T \frac{1}{1 + \exp((t - \tau)\eta_{t-1} )} }_{ \text{Term 2} }
\end{align*}

For Term 1,
\begin{align*}
    \text{Term 1} & \overset{\rm(i)} \geq  \sum_{1 \leq t < \tau, t~\text{is even} } \frac{1 - \exp( - \eta_{t-1} ) }{4} \\
     & = \sum_{1 \leq t < \tau, t~\text{is even} } \frac{\eta_{i-1}}{4} + O( \eta_{i-1}^2 ) \\
     & \overset{\rm(ii)} \geq \frac{ \sqrt{4 \ln n} }{4} \sqrt{\tau} + o(\tau)
\end{align*}
where (i) is true by $\frac{1}{2 - x} - \frac{1}{2} \geq \frac{x}{4}~ \forall x \in (0, 1) $ and (ii) is true by using the fact that $\sum_{t=1}^\tau \frac{1}{\sqrt{t}} \geq 2\sqrt{\tau} - 2 $

By the definition of $\tau$, we have $\displaystyle \lim_{T \to \infty} \frac{\tau}{T} = 1$, thus
\begin{align}
    \lim_{T \to \infty} \frac{ \text{Term 1} }{ \sqrt{T \ln n} } = \frac{1}{2}. \label{eq:term1}
\end{align}

For Term 2,
\begin{align}
    \text{Term 2} & =  \sum_{t=\tau}^T \frac{1}{1 + \exp( (t - \tau)\eta_{t-1} )} \nonumber \\
    & \geq \sum_{t=\tau}^T \frac{1}{1 + \exp((t - \tau)\sqrt{ \frac{4\ln n}{t-1} } )} \nonumber \\
    & \geq \sum_{t=\tau}^T \frac{1}{1 + \exp((t - \tau)\sqrt{ \frac{4\ln n}{\tau-1} } )} \nonumber \\
    & \geq \int_{t=\tau}^{T} \frac{1}{1 + \exp((t - \tau)\sqrt{ \frac{4\ln n}{\tau-1} } )} dt \nonumber \\
    & = \int_{y=0}^{ \log(T)\sqrt{T} } \frac{1}{1 + \exp(y\sqrt{ \frac{4\ln n}{\tau-1} } )} dy  \label{eq:term2}
\end{align}
Note that
\[
\int \frac{1}{1 + \exp(\beta y)} dy = y - \frac{\ln \left( 1 + e^{\beta y} \right)  }{\beta}
\]
Set $\beta = \sqrt{ \frac{4\ln n}{\tau-1} }$ and plug the above result to Eq~\ref{eq:term2}, we get the following,
\begin{align*}
    \text{Term 2} \geq \log(T) \sqrt{T} - \frac{\ln\left(1 + \exp\left( \sqrt{ \frac{4\ln n}{\tau-1} } \log(T) \sqrt{T} \right) \right) }{ \sqrt{ \frac{4\ln n}{\tau-1} } } + \frac{\ln 2}{\sqrt{ \frac{4\ln n}{\tau-1} }}
\end{align*}
Using the fact that $\ln \left( 1+e^x \right) = x + o(x)$,
\begin{align*}
    \text{Term 2} \geq \log(T) \sqrt{T} - \log(T) \sqrt{T} + o\left( \sqrt{ \frac{4\ln n}{\tau-1} } \log(T) \sqrt{T} \right) + \ln2 \sqrt{ \frac{  ( \tau - 1) }{4 \ln n} }
\end{align*}
Note that $n = 2$, thus
\begin{align}
    \lim_{T \to \infty} \frac{ \text{Term 2} }{ \sqrt{T \ln n} } = \lim_{T \to \infty} \frac{\ln2 \sqrt{ \frac{  ( \tau - 1) }{4 \ln 2} }}{ \sqrt{T \ln 2} } = \frac{1}{2} \label{eq:term3}
\end{align}

Combining Eq.~\ref{eq:term1} and Eq.~\ref{eq:term3}, we conclude that
\[
    \lim_{T \to \infty} \frac{ \mathrm{Regret(T)} }{ \sqrt{T \ln n} } = \lim_{T \to \infty} \frac{ \text{Term 1} }{ \sqrt{T \ln n} } + \lim_{T \to \infty} \frac{ \text{Term 2} }{ \sqrt{T \ln n} } \geq  \frac{1}{2} + \frac{1}{2} = 1.\qedhere
\]
\end{proof}

\section{Aditional proofs for \Section{comparison}}
\AppendixName{comparison_app}

At many points throughout this section we will need to talk about optimality
condition for problems where we minimize a convex function over a convex set. Such conditions depend on the \emph{normal cone} of the set on which the
optimization is taking place.

\begin{definition}
    The normal cone to $C \subseteq \Reals^n$ at $x \in \Reals^n$ is the set $N_C(x)
    \coloneqq \{ s\in \R^n \mid \langle s, y - x \rangle \leq 0~\forall y \in C\}$.
\end{definition}

\begin{lemma}[\protect{\citep[Theorem~27.4]{roc70}}]
     \label{lemma:opt_condition}
    Let \(h \colon \Ccal \to \Reals\) be a closed convex function such that \((\relint \Ccal)\cap(\relint \X)\neq \emptyset \). Then, \(x \in \argmin_{z \in \X} h(z) \) if and only if there is \(\ghat \in \subdiff[h](x)\) such that \( -\ghat \in N_\X(x) \).
\end{lemma}

Using the above result allows us to derive a useful characterization of points that realize the Bregman projections.
\begin{lemma} \label{lemma:projection}

    Let \(y \in \Dcal\) and \(x \in \bar{\Dcal}\). Then \(x =
    \Pi_\X^\Phi(y)\) if and only if \(x \in \Dcal \cap \X \) and \(\nabla \Phi(y) - \nabla
    \Phi(x) \in N_\X(x)\).
\end{lemma}
\begin{proof}
    Suppose \(x \in \Dcal \cap \X \) and \(\nabla \Phi(y) - \nabla
    \Phi(x) \in N_\X(x)\). Since \(\nabla \Phi(y) - \nabla
    \Phi(x) = - \nabla(D_{\Phi}(\cdot,y))(x)\), by Lemma~\ref{lemma:opt_condition} we conclude that \(x \in \argmin_{z \in \X} D(z, y)\). Now suppose \(x =
    \Pi_\X^\Phi(y)\).  By Lemma~\ref{lemma:opt_condition} together with the definition of Bregman divergence, this is the case if and only if there is \(-g \in \subdiff[\Phi](x)\) such that \(-(g - \nabla \Phi(y)) \in N_\X(x)\). Since \(\Phi\) is of Legendre type we have \(\subdiff[\Phi](z) = \emptyset\) for any \(z \not\in \Dcal\) (see~\citep[Theorem~26.1]{roc70}). Thus, \(x \in \Dcal\) and \(g = \nabla \Phi(x)\) since \(\Phi\) is differentiable. Finally, \(x \in \X\) by the definition of Bregman projection.
\end{proof}

Before proceding to the proof of the results from \Section{comparison}, we need to state on last result about the relation of subgradients and conjugate functions.

\begin{lemma}[\protect{\citep[Theorem~23.5]{roc70}}]
    \label{lemma:subdiff_attainability}
    Let \(f \colon \X \to \Reals\), let \(x \in \X\) and let \(\yhat \in \Reals^n\). Then \( \yhat \in \subdiff(x)\) if and only if \(x\) attains \(\sup_{x \in
    \Reals^n}(\iprod{\yhat}{x} - f(x)) = f^*(\yhat)\).
\end{lemma}

\begin{proofof}{Proposition~\ref{prop:prox-ds-omd}}
    Let \(t \geq 1\) and let \(F_t \colon \Dcal \to \Reals\) be the function
    being minimized on the right-hand side of~\eqref{eq:ds-omd_proximal}. By
    definition we have \(x_{t+1} = \Pi_{\X}^\Phi({y}_{t+1})\). Using the
    optimality conditions of the Bregman projection, we have
    \begin{equation*}
        x_{t+1} = \Pi_{\X}^\Phi({y}_{t+1})
        \iff \yhat_{t+1} - \xhat_{t+1}
        \in N_\X(x_{t+1}),  \quad  \text{(by Lemma~\ref{lemma:projection})}
    \end{equation*}

    By further using the definitions
    from Algorithm~\ref{alg:somd} we get
    \begin{align*}
        \hat{y}_{t+1} - \xhat_{t+1}
        &= \gamma_t(\hat{x}_t - \eta_t \ghat_t)
        + (1 - \gamma_t) \hat{x}_1 - \xhat_{t+1}\\

        &=  \gamma_t(\xhat_t - \xhat_{t+1}
        - \eta_t \ghat_t)
        + (1 - \gamma_t) (\xhat_1 - \xhat_{t+1}) \\

        &= - \gamma_t\paren[\big]{\nabla(D_\Phi(\cdot, x_{t}))(x_{t+1})
        + \eta_t \ghat_t}
        - (1 - \gamma_t) \nabla(D_\Phi( \cdot, x_1 ) )(x_{t+1}) \\
        &= - \nabla F_t(x_{t+1})

    \end{align*}
    Thus, we have \(- \nabla F_t(x_{t+1}) \in N_{\X}(x_{t+1}) \).
    By the optimality conditions from Lemma~\ref{lemma:opt_condition} we
    conclude that \(x_{t+1} \in \argmin_{x \in \X} F_t(x)\), as desired.
\end{proofof}

\Theorem{avg_min_form} is an easy consequence of the following proposition.

\begin{proposition}
    \PropositionName{general_avg_min_form}
    Let $\{f_t\}_{t \geq 1}$ with $f_t : \X \rightarrow \R$ be a
    sequence of convex functions and let \(\eta \colon \Naturals \to \Reals_{>0}\) be non-increasing. Let $\{x_t\}_{t \geq 1}$ and
    \(\{\ghat_t\}_{t \geq 1}\) be as in Algorithm~\ref{alg:somd}.
    Define $\gamma^{[i,t]} \coloneqq \prod_{j = i}^t \gamma_j$

    for every~\(i,t  \in \Naturals\). Then, there are $\{p_t\}_{t \geq 1}$ with $p_t \in N_X(x_t)$ for each $t \geq 1$ such that
    \begin{equation}
        \label{eq:ds-omd_min_form}
        \{x_{t + 1}\}
        = \argmin_{x \in \X}
        \paren[\Big]{\sum_{i = 1}^t \gamma^{[i,t]}\iprod{\eta_i \ghat_i + p_i}{x} - \paren[\Big]{\gamma^{[1,t]} + \sum_{i = 1}^t \gamma^{[i+1, t]} (1 - \gamma_i)} \iprod{\xhat_1}{x} + \Phi(x)},
        \qquad \forall t \geq 0.
    \end{equation}
\end{proposition}
\begin{proof}
    First of all, in order to prove~\eqref{eq:ds-omd_min_form} we claim it
    suffices to prove that there are \(\{p_t\}_{t \geq 1}\) with \(p_t \in
    N_X(x_t)\) for each \(t \geq 1\) such that
    \begin{equation}
        \label{eq:ds-omd_min_form_proof_1}
        \yhat_{t+1}
        = - \sum_{i = 1}^t \gamma^{[i,t]}(\eta_i \ghat_i + p_i)
        + \paren[\Big]{\gamma^{[1,t]}
        + \sum_{i = 1}^t \gamma^{[i+1,t]} (1 - \gamma_i)} \xhat_1,
        \qquad \forall t \geq 0.

    \end{equation}
    To see the sufficiency of this claim, note that
    \begin{align*}
        x_{t+1} = \Pi_\X^{\Phi}(y_{t+1}))
        &\iff \yhat_{t+1} - \xhat_{t+1} \in N_\X(x_{t+1})&
        \quad \text{(Lemma~\ref{lemma:projection})}
        \\
        &\iff \yhat_{t+1}  \in \subdiff[(\Phi
        + {\indic[\X]{\cdot}})](x_{t+1})
        &\quad (\subdiff[({\indic[\X]{\cdot}})](x) = N_{\X}(x))
         \\
        &\iff x_{t+1} \in \argmax_{x \in \Reals^n}
        \paren[\big]{\iprod{\yhat_{t+1}}{x}
        - \Phi(x) - {\indic[\X]{x}}}
        &\quad (\text{Lemma~\ref{lemma:subdiff_attainability}})\\
        & \iff x_{t+1} \in \argmin_{x \in \X}\paren[\big]{-\iprod{\yhat_{t+1}}{x}
        + \Phi(x)}.
    \end{align*}
    The above together with~\eqref{eq:ds-omd_min_form_proof_1}
    yields~\eqref{eq:ds-omd_min_form}. Let us now
    prove~\eqref{eq:ds-omd_min_form_proof_1} by induction on \(t \geq 0\).

    For \(t = 0\)~\eqref{eq:ds-omd_min_form_proof_1} holds trivially.
    Let \(t > 0\). By definition, we have \(\yhat_{t+1} = (1 -
    \gamma_t)(\xhat_t - \eta_t \ghat_t) + \gamma_t \xhat_1\). At this point,
    to use the induction hypothesis, we need to write \(\xhat_t\) in
    function of \(\yhat_t\). From the definition of
    Algorithm~\ref{alg:somd}, we have \(x_t = \Pi_X^{\Phi}(y_t)\). By
    Lemma~\ref{lemma:projection}, the latter holds if and only if
    \(\yhat_t - \xhat_t  \in N_\X(x_t)\). That is, there is \(p_t \in
    N_\X(x_t)\) such that \(\xhat_t = \yhat_t - p_t\). Plugging these
    facts together and using our induction hypothesis we have
    \begin{align*}
        \yhat_{t+1}
        &= \gamma_t(\xhat_t - \eta_t \ghat_t) + (1 - \gamma_t) \xhat_1
        = \gamma_t(\yhat_t - \eta_t \ghat_t - p_t) + (1 - \gamma_t) \xhat_1\\
        &\stackrel{\text{I.H.}}{=} \gamma_t\paren[\Big]{
            -\sum_{i = 1}^{t-1} \gamma^{[i,t-1]}(\eta_i \ghat_i + p_i)
            - \eta_t \ghat_t - p_t + \paren[\Big]{\gamma^{[1,t-1]}
            + \sum_{i = 1}^{t-1} \gamma^{[i+1,t-1]} (1 - \gamma_i) } \xhat_1
        }
        + (1 - \gamma_t )\xhat_1\\
        &= -\sum_{i = 1}^{t} \gamma^{[i,t]}(\eta_i \ghat_i + p_i)
             + \paren[\Big]{\gamma^{[1,t]}
            + \sum_{i = 1}^{t} \gamma^{[i+1,t]} (1 - \gamma_i) } \xhat_1,
    \end{align*}
    and this finishes the proof of~\eqref{eq:ds-omd_min_form_proof_1}.
\end{proof}

\begin{proofof}{\Theorem{avg_min_form}}
    Define $\gamma^{[i,t]}$
    for every~\(i,t  \in \Naturals\) as in \Proposition{general_avg_min_form}. If \(\gamma_t = 1\) for all \(t \geq 1\), then \(\gamma^{[i,t]} =
    1\) for any \(t,i \geq 1\). Moreover,  if~\(\gamma_t =
    \tfrac{\eta_{t+1}}{\eta_t}\) for every \(t \geq 1\), then for every \(t, i
    \in \Naturals\) with \(t \geq i\) we have \(\gamma^{[i,t]} =
    \tfrac{\eta_{t+1}}{\eta_i}\), which yields \(\gamma^{[i,t]}(\eta_i \ghat_i + p_i) =
    \eta_t \ghat_i + \tfrac{1}{\eta_i} p_i\) and
    \begin{equation*}
        \gamma^{[1,t]} + \sum_{i = 1}^t \gamma^{[i+1,t]} (1 - \gamma_i)
        = \frac{\eta_{t+1}}{\eta_1}
    + \sum_{i = 1}^t \frac{\eta_{t+1}}{\eta_{i+1}}
        \paren[\Big]{1 - \frac{\eta_{i+1}}{\eta_i}}
        = \frac{\eta_{t+1}}{\eta_1}
        + \eta_{t+1} \sum_{i = 1}^t
        \paren[\Big]{\frac{1}{\eta_{i+1}}  - \frac{1}{\eta_i}}
        = 1. \qedhere
        \end{equation*}
\end{proofof}

\section{Dual Stabilized OMD with Composite Functions}
\AppendixName{regularized_problems}

In this section we extend the Dual-Stabilized OMD to the case where the
functions revealed at each round are
composite~\cite{Xiao,Duchi10compositeobjective}. More specifically, at each
round \(t \geq 1\) we see a function of the form \(f_t + \Psi\), where \(f_t
\colon \X \to \Reals\) is convex and Lipschitz continuous and \(\Psi\) is a
fixed convex function which we assume to be ``easy'', i.e., such that we know
how to efficiently compute points in \(\argmin_{x \in \X}(D_{\Phi}(x,\xbar) +
\Psi(x))\). In fact, we could simply use the original Dual-Stabilized OMD in
this setting, but this approach has some drawbacks. One issue is that
subgradients of \(\Psi\) would end-up appearing on the regret bound from
Theorem~\ref{thm:somd}, which is not ideal: we want bounds which are unaffected
by the ``easy'' function \(\Psi\). Another drawback is that we would not be
using the knowledge of the structure of the functions, which is in many cases
sub-optimal. For example, in an online learning problem one may artificially add
the \(\ell_1\)-norm to each function in order to induce sparsity on the iterates
of the algorithm. However, using subgradients of the \(\ell_1\)-norm instead of
the norm itself does not induce sparsity~\cite{McMahan11a}. Finally, the
analysis of Dual-Stabilized OMD adapted to the composite setting that we develop
in this section is an easy extension of the original analysis of
\Section{StabilizedOMD}. This is interesting since in the literature the
algorithms for the composite setting usually require a more intricate analysis,
such as in the analysis of Regularized DA from~\cite{Xiao}, or the use of
powerful results, such as the duality between strong convexity and strong
smoothness used in~\cite{McMahan17}. An important exception is the analysis of
the composite objective mirror descent from~\cite{Duchi10compositeobjective} is
already elegant. Sill, it does not directly applies when we use
dual-stabilization and uses proof techniques more specially-tailored for the
proximal step form of writing OMD.

In the composite setting we assume without loss of generality that \(\X =
\Reals^n\) since we may substitute \(\Psi\) by \(\Psi + \indic[\X]{\cdot}\)
where \(\indic[\X]{x} = 0\) if \(x \in \X\) and is \(+\infty\) anywhere else. To
avoid comparing the loss of the algorithm with points outside of the effective
domain of \(\Psi\) in the definition of regret, denoted by \(\dom \Psi\), we
define the \(\Psi\)-regret of the sequence of functions \(\{f_t\}_{t \geq 1}\) (against a comparison point \(z \in \dom \Psi\)) by
and iterates \(\{x_t\}_{t \geq 1}\) by
\begin{equation*}
    \Reg^{\Psi}(T, z)
    \coloneqq
    \sum_{t = 1}^T\big(f_t(x_t) + \Psi(x_t)\big) -
    \sum_{t = 1}^T\big( f_t(z) + \Psi(z)\big),
    \quad \forall T \geq 0.
\end{equation*}

To adapt the Dual Stabilization method to this setting, we use the same idea as
in~\cite{Duchi10compositeobjective}. Namely, we modify the proximal-like
formulation of Dual Stabilization from Proposition~\ref{prop:prox-ds-omd} so
that we do not linearize (i.e., take the subgradient) of  the function \(\Psi\),
which yields
\begin{equation*}
    \{x_{t+1}\} \coloneqq \argmin_{x \in \X}
    \paren[\Big]{ \gamma_t\paren[\big]{\eta_t(\iprod{\ghat_t}{x} + \Psi(x))
    + D_{\Phi}(x, x_t)} + (1 - \gamma_t) D_{\Phi}(x, x_1)},
    \quad \forall t \geq 0.
\end{equation*}

\begin{algorithm}

       \caption{Dual-stabilized OMD with dynamic learning
       rate $\eta_t$ and additional regularization function~\(\Psi\).}
       \label{alg:reg-somd}
       \begin{algorithmic}
         \STATE {\bfseries Input:}
         ${x}_1 \in \argmin_{x \in \Reals^n} \Psi(x) ,\
         \eta:\mathbb{N} \rightarrow \R_+,\
         \gamma : \mathbb{N} \to [0, 1] $
         \STATE $\hat{y}_1 = \nabla \Phi(x_1)$
         \FOR{$t=1,2,\ldots$}
            \STATE Incur cost $f_t(x_t)$ and receive $\ghat_t \in \partial f_t(x_t)$
            \STATE \vspace{-21pt} \addtolength{\jot}{-3pt}
                \begin{flalign}
                    & \hat{x}_t = \nabla \Phi(x_t) &&\text{$\rhd$ map primal iterate to dual space} \nonumber
                    \\
                    & \hat{w}_{t+1} = \hat{x}_t - \eta_t \ghat_t &&\text{$\rhd$ gradient step in dual space} \EquationName{CompGradientStep}
                    \\
                    & \hat{y}_{t+1} = \gamma_t \hat{w}_{t+1} + (1-\gamma_t) \hat{x}_1 &&\text{$\rhd$ stabilization in dual space} \EquationName{Comp-DSOMDHyp}
                    \\
                    & y_{t+1} = \nabla \Phi^*( \hat{y}_{t+1} ) &&\text{$\rhd$ map dual iterate to primal space}\hspace{5cm} \nonumber
                    \\
                    & \alpha_{t+1} \coloneqq \eta_t\gamma_t &&\text{$\rhd$ compute scaling factor for \(\Psi\)} \nonumber
                    \\
                    & x_{t+1} =
                \Pi^{\Phi}_{\alpha_{t+1}\Psi}(y_{t+1}) &&\text{$\rhd$ project onto feasible region} \EquationName{Comp-DSOMDHyp2}
                \end{flalign}
            \vspace{-21pt}

       \ENDFOR

    \end{algorithmic}
    \end{algorithm}

Although we do not prove the equivalence for the sake of conciseness, on
Algorithm~\ref{alg:reg-somd} we present the above procedure written in a form
closer to Algorithm~\ref{alg:somd}. In this new algorithm, we extend the
definition of Bregman Projection and define the \(\Psi\)-Bregman projection by
\(\{\Pi^{\Phi}_{\Psi}(y)\} \coloneqq \argmin_{x \in \Reals^n}(D_\Phi(x,y) +
\Psi(y))\). The next lemma shows an analogue of the generalized pythagorean
theorem for the \(\Psi\)-Bregman Projection.

\begin{lemma}
    \label{lemma:regularized_bregman_pythagorean}
    Let \(\alpha > 0\) and \(\ybar \coloneqq \Pi_{\alpha \Psi}^{\Phi}(y)\). Then,
\begin{equation*}
    D_{\Phi}(x, \ybar) + D_{\Phi}(\ybar, y)
    \leq D_{\Phi}(x,y) + \alpha(\Psi(x) - \Psi(\ybar)), \qquad
    \forall x \in \Reals^n.
\end{equation*}
\end{lemma}
\begin{proof}
    By the optimality conditions of the projection, we have \(\nabla \Phi (y) -
    \nabla \Phi(\ybar) \in \subdiff[(\alpha\Psi)](\ybar)\). Using the generalized
    triangle inequality for Bregman Divergences (Lemma~\ref{lem:bregman-div}) and the subgradient inequality,
    we get
  \begin{equation*}
    D_\Phi(x, \ybar) + D_\Phi(\ybar, y) - D_\Phi(x,y)
    = \iprod{\nabla \Phi(y) - \nabla \Phi(\ybar)}{x - \ybar}
    \overset{\rm(i)}{\leq} \alpha(\Psi(x) - \Psi(\ybar)).
  \end{equation*}
  where (i) follows from \(\nabla \Phi (y) - \nabla \Phi(\ybar) \in \subdiff[(\alpha \Psi)](\ybar)\) and the convexity of $\alpha \Psi(\cdot)$.
\end{proof}

In the next theorem we show that the regret bound we have for the
Dual-Stabilized OMD still holds in this setting when
using~Algorithm~\ref{alg:reg-somd}, and the proof boils down to simple
modifications to the original proof of Theorem~\ref{thm:somd}.

\begin{theorem}
Suppose that $\Phi$ is $\rho$-strongly convex with respect to a norm $\| \cdot
\|$ and \(\Psi\) be a convex function such that \(\dom \Psi \subseteq \X\). Set $\gamma_t = \eta_{t+1}/\eta_{t}$ for each $t \geq 1$.
 Let $x_1 \in \argmin_{x \in \dom \Psi} \Psi(x)$ and $\{x_t\}_{t \geq 1}$ be the
sequence of iterates generated by Algorithm~\ref{alg:reg-somd}. Then for any sequence
of convex functions $\{f_t\}_{t \geq 1}$ with each $f_t \colon \X \rightarrow \R$ and \(z \in \X\),
    \begin{equation}
        \label{eq:reg_somd_bound}
        \Reg^{\Psi}(T,z) ~\leq~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} + \frac{ D_\Phi(z, x_1) }{\eta_{T+1}},
  \quad \forall T > 0.
    \end{equation}
\end{theorem}
\begin{proof}
    Let \(z \in \dom \Psi\) and \(t \in \Naturals\).
    \begin{mdframed}
        By~\eqref{eq:regret_at_each_round}, we have
    \begin{equation}
        \label{eq:one_round_bound_regularized}
        f_t(x_t) + \Psi(x_t) - f_t(z) - \Psi(z)
        \leq
        \frac{1}{\eta_t} \Big( D_\Phi(x_t, w_{t+1} ) + D_\Phi(z, x_t) - D_\Phi\big(z, {w}_{t+1}  \big)   \Big)
        + \Psi(x_t) - \Psi(z).
    \end{equation}
    \end{mdframed}
    As in Theorem~\ref{thm:somd}, let us prove bound the above expression by
    something with telescoping terms.

\begin{claim}
    \ClaimName{CompositeDSOMD}
    Assume that $\gamma_t = \eta_{t+1}/\eta_t \in (0,1]$.
    Then
    \[
    \eqref{eq:one_round_bound_regularized}
    ~\leq~
    \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} + \underbrace{\Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big)}_{\text{telescopes}} D_\Phi(z, x_1) +
    \underbrace{\frac{D_\Phi(z, x_t)}{\eta_t} -\frac{D_\Phi(z, x_{t+1})}{\eta_{t+1}}}_{\text{telescopes}}
    + \underbrace{\Psi(x_t) - \Psi(x_{t+1})}_{\text{telescopes}}.
    \]
\end{claim}
\begin{proof}
    Fix \(z \in \dom \Psi \). First we derive the inequality
    \begin{align*}
    &\gamma_t  \big( D_\Phi(z,w_{t+1}) - D_\Phi(x_{t+1},w_{t+1}) \big)
        \:+\: (1-\gamma_t) D_\Phi(z,x_1) &&
        \\
    ~\geq~&     \gamma_t  \TriBreg{z}{x_{t+1}}{w_{t+1}}
        \:+\: (1-\gamma_t) \TriBreg{z}{x_{t+1}}{x_1}
        \qquad&&\text{(since $D_\Phi(x_{t+1},x_1)
        \geq 0$ and $\gamma_t \leq 1$)}
        \\
    ~=~&        \TriBreg{z}{x_{t+1}}{y_{t+1}}
        \qquad &&\text{(by \Proposition{BregmanIdentity} and \eqref{eq:Comp-DSOMDHyp})}
        \\
    ~\geq~&     D_\Phi(z,x_{t+1})  + \alpha_{t+1} \big( \Psi( x_{t+1} ) - \Psi( z ) \big)
    \qquad &&\text{(by Lemma~\ref{lemma:regularized_bregman_pythagorean} and \eqref{eq:Comp-DSOMDHyp2})}.
\end{align*}
Rearranging and using both $\gamma_t>0$ and \(\alpha_{t+1} = \eta_t \gamma_t\)
yields
\begin{equation}\EquationName{CompDSOMDRearranged}
D_\Phi(z, w_{t+1})
    ~\geq~
        D_\Phi(x_{t+1}, w_{t+1})
        - \Big(\frac{1}{\gamma_t}-1\Big) D_\Phi(z, x_1)
        + \frac{1}{\gamma_t} D_\Phi( z, x_{t+1} )
        + \eta_t \big( \Psi( x_{t+1} )
        - \Psi( z ) \big).
\end{equation}
Plugging this into \eqref{eq:one_round_bound_regularized}
yields
\begin{align*}
\eqref{eq:one_round_bound_regularized}
    ~=~& \frac{1}{\eta_t} \Big(
            D_\Phi(x_t,w_{t+1}) - D_\Phi(z,w_{t+1}) + D_\Phi(z,x_t)
        \Big) + \Psi(x_t) - \Psi(z)\\
    ~\leq~& \frac{1}{\eta_t} \Bigg(
        \TriBreg{x_t}{x_{t+1}}{w_{t+1}}
            + \Big(\frac{1}{\gamma_t}-1\Big) D_\Phi(z, x_1)
            - \frac{1}{\gamma_t} D_\Phi( z, x_{t+1} )
            + D_\Phi(z,x_t)
        \Bigg) + \Psi(x_t) - \Psi(x_{t+1}).
\end{align*}
The claim follows by the definition of $\gamma_t$.
\end{proof}\begin{mdframed}
    The final step is very similar to the standard OMD proof.
    Summing \eqref{eq:one_round_bound_regularized} over $t$
    and using \Claim{CompositeDSOMD} leads to the desired telescoping sum.
    \begin{equation*}
        \begin{aligned}
            \sum_{t=1}^T \big( f_t(x_t) - f_t(z) \big)
                &~\leq~ \sum_{t=1}^T \Bigg(\frac{
                \TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} &+&~~ \Big( \frac{1}{\eta_{t+1}} - \frac{1}{\eta_t} \Big) D_\Phi(z, x_1) + \frac{D_\Phi(z, x_t)}{\eta_t} -\frac{D_\Phi(z, x_{t+1})}{\eta_{t+1}}
                \nonumber
                \\
                & &+&~~  \Psi(x_t) - \Psi(x_{t+1})\Bigg)
                \\
                &~\leq~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t}
                  &+&~~  \frac{ D_\Phi(z, x_1) }{\eta_{T+1}} + \Psi(x_1) - \Psi(x_{T+1})  \nonumber
                \\
                &~\leq~ \sum_{t=1}^T \frac{\TriBreg{x_t}{x_{t+1}}{w_{t+1}}}{\eta_t} &+&~~ \frac{ D_\Phi(z, x_1) }{\eta_{T+1}},
            \end{aligned}
    \end{equation*}
    where in the last step inequality we used \(x_1 \in \argmin_{x \in \X} \Psi(x)\).
    \end{mdframed}

\end{proof}

\bibliographystyle{icml2020}
\bibliography{ref}

\makeatletter\@input{xx_main.tex}\makeatother

\end{document}


TITLE: Induction, cardinality with natural numbers
QUESTION [1 upvotes]: Say you prove a statement $P(n)$ by induction, for all $n$ in $\mathbb{N}$.
Does the set {$P(k): k \in \mathbb{N}$ s.t. P(k) is true} have the same cardinality as the set of all natural numbers? Is there a bijection here?
For some reason I can't find much. Google is pulling up a lot of "use induction to prove the union of $n$ countably infinite sets is countably infinite" which isn't quite what I'm asking, I think.
Thank you for any help!

REPLY [2 votes]: Not necessarily.
Suppose $P(k)=P$ for all $k$ (in other words, the statement $P(k)$ does not vary with $k$). If $P$ is true, it is of course trivial to show that $P(k)$ is true for any $k$. Moreover, the set $\{ P(k)|k \in \mathbb{N} \land P(k) \}$ is just $\{ P \}$, which obviously has cardinality smaller than $\mathbb{N}$.
Of course, this is a very unusual case, and typically $P(m) \not = P(n)$ for $m \not = n$, in which case the function $f(k) = P(k)$ is a bijection between $\mathbb{N}$ and $\{ P(k)|k \in \mathbb{N} \land P(k) \}$, and thus they will have the same cardinality in that case. But as I showed above, this is not necessarily the case.


TITLE: Why normal reaction, tension, and friction forces are reference frame-independent?
QUESTION [1 upvotes]: I can not provide a whole manuscript of examples where I can justify that these forces are reference independent.
I don't think that there is any such case where these forces are reference-dependent. What is the main reason that they are reference independent?
Please provide the solutions which are in the domain of Newtonian mechanics. Every suggestion is important to me.
EDIT
A pure mathematical description of these forces would be quite helpful for me instead of specific cases.

REPLY [0 votes]: Let’s look at this example.
Your choice of the generalized coordinate can be q1 or q2 or q3. To calculate the equation of motion you give the components of the position vector R in inertial space, which can be coordinate system 1 or 2 or 3.
So the equation of motion is a function of g1 or q2 or q3.
But to calculate the normal force N , you allows a deflection towards the force N (qn), which don’t depend of a coordinate system and is unique.
Fazit
You have different choices to choose the generalized coordinate and your inertial systems, but only one choice of coordinate , which is independent of a coordinate system to calculate the reaction force.
For a conservative system , the equation of motion don’t depend on the reaction force.
I am not sure if this answer your question?


TITLE: Does the lumen value of a light bulb take into account the inverse square law and volume of a room?
QUESTION [0 upvotes]: For example, I am trying to calculate the number of 800lm light bulbs required to light a 16sq meter bed room with a 2.5m celling that doubles as a study. Assuming 75 lux is required, this converts to 1200 lumens. Below are what I have calculated so far:
Let x be the number of light bulbs required:
1/2.5^2 * 800lm x = 1200lm
x = 9.375
Which seems quite unreasonable... How would anyone need 9 bulbs in a room? Where is the error here? Do I not need to consider the inverse square law?

REPLY [2 votes]: If you are living with rooms that you describe then the simplest way to do the calculation is to work out the luminous flux (lumens) by multiplying the illuminance (lux) that you require by the base area of the room (metre$^2$).
So in your case you have evaluated the luminous flux that you require as $16\times 75 = 1200 \, \rm lm$.
Now divide this value by the luminous flux emitted by one bulb and a value of $\frac {1200}{800}= 1.5$ which you might consider more reasonable.
But as you know nothing in real life is that easy although if you double the number of lamps you will probably find the light levels in your room adequate except perhaps at your desk?
Now to get a better estimate you ought to look first at the level of illuminance that you require?
Here is a typical table with the values either at floor level eg for a corridor or at $0.75 \,\rm m$ above floor level for a study.

The rule of thumb for conversion between lumens and watts for different types of bulbs are shown in the table below.

The type of lamp used is obviously important but so is the way the lamp emits light.
An incandescent bulb distributes light in almost all directions whereas an LED tends to be very directional with a "beam angle" given in the specifications.
The room that you are in will also affect things not just due to its size but also due to the surface reflectance of the ceiling, walls, and floor which is encompassed in an average room reflectance factor called the luminaire utilisation factor ($U$) and there is also the ageing of the bulb and the bulb getting dirty with time factors which need to be taken into consideration - the maintenance factor ($M$).
So with next degree of sophistication the total number of lumens you need is $\dfrac{EA}{UM}$ where $E$ is the required illuminance (lus) and $A$ is the area (m$^2$).
Using The Installer's Guide to Lighting Design I estimated a value of $U=0.4$ and $M=0.8$ for your room which gave a value of approximately $3800 \,\rm lm$ for an illuminance of $75\,\rm lx$ and a much higher value of $25,000 \,\rm lm$ if the illuminance is $500\,\rm lx$.
Perhaps a suitably positioned, reasonably high powered, medium beam angle LED will do the trick?
One of the comments summed it up very well -"The inverse square law is exactly why they make table lamps".
You will note that the inverse square law is not used directly in any of the calculations because you are dealing with reflected light as well as direct light.


TITLE: Proof Check: Continuity of Kernel Operator
QUESTION [1 upvotes]: Let $T_{k}: C([0,1]) \to C([0,1])$
Where $(T_{k}x)(s)=\int_{0}^{s}k(s,t)x(t)dt$
Show that $T_{k}$ is well-defined.
My work: We of course simply want to show that $T_{k}x \in C([0,1])$
Let $x \in C([0,1])$ and $s \in [0,1]$ arbitrary, I will initially compute $\vert (T_{k}x)(s)-(T_{k}x)(y)\vert$ for any arbitrary $y < s$ and then come up with estimates.

My computation: $\vert
 (T_{k}x)(s)-(T_{k}x)(y)\vert=\vert\int_{0}^{s}k(s,t)x(t)dt-\int_{0}^{y}k(y,t)x(t)dt\vert=\vert\int_{y}^{s}k(s,t)x(t)dt+\int_{0}^{y}(k(s,t)-k(y,t))x(t)dt\vert\leq
 \int_{y}^{s}\vert k(s,t)x(t)\vert dt+ \int_{0}^{y}\vert
k(s,t)-k(y,t)\vert \vert x(t)\vert dt\leq\sup\limits_{t}\vert
 k(s,t)\vert\vert x(t)\vert\vert s -y\vert+ \sup\limits_{t}\vert
 k(s,t)-k(y,t)\vert\vert x(t)\vert\vert y\vert\leq \sup\limits_{t}\vert
 k(s,t)\vert\vert x(t)\vert\vert s -y\vert+ \sup\limits_{t}\vert
k(s,t)-k(y,t)\vert\vert x(t)\vert$

Now, let $\epsilon >0$.
so for the term $\sup\limits_{t}\vert
 k(s,t)\vert\vert x(t)\vert\vert s -y\vert$ we can select $\delta_{1}:=\frac{\epsilon}{2\sup\limits_{t}\vert
 k(s,t)\vert\vert x(t)\vert}$
and for the term $\sup\limits_{t}\vert
k(s,t)-k(y,t)\vert\vert x(t)\vert$ we can select $\delta_{2}:=\frac{\epsilon}{2\sup\limits_{t}x(t)}$.
Then for any $y \in [0,1]$ so that $\vert s-y\vert<\delta:=\min\{\delta_{1},\delta_{2}\}$ and thus $\vert
 (T_{k}x)(s)-(T_{k}x)(y)\vert< \epsilon$
Either I am wrong, or there must be a more elegant solution.

REPLY [1 votes]: The $\delta_2$ isn't what you want.  What's useful is the following:  Assuming $k\in C([0,1]^2)$, there is some $\delta_2>0$ such that if $x,y\in[0,1]^2$ and $d(x,y)<\delta_2$ (choose your favorite $p$-metric on $[0,1]^2$), then $|k(x)-k(y)|<\frac{\varepsilon}{2\|x\|}$, where $\|x\|=\sup_{t\in[0,1]}|x(t)|$.  Then if $|s_2-s_1|<\delta_2$, we have $d((s_1,t),(s_2,t))<\delta_2$ for all $t\in[0,1]$, and thus
$$\int_0^{s_1}|k(s_2,t)-k(s_1,t)||x(t)|\ dt<\varepsilon.$$
Then the rest of the proof goes the same.
As far as elegance is concerned, that's a matter of opinion. But results of this nature don't really have (what I would call) elegant proofs.


TITLE: Can I switch the convention of QCD by replacing coupling constant $g$ with $-g$?
QUESTION [3 upvotes]: There are two equivalent conventions in QCD that give two different definitions of the covariant derivative operator: ${D_\mu } = {\partial _\mu } - {\rm{i}}gA_\mu ^\alpha {T_\alpha }$ and ${D_\mu } = {\partial _\mu } + {\rm{i}}gA_\mu ^\alpha {T_\alpha }$.
And my question is can I switch the conventions of a book simply by replacing all the coupling constant $g$ with $-g$ in its formulas?
I see the value of coupling constant $g$ is always positive in both conventions, does that mean the sign of coupling constant $g$ will not affect on observable quantities?

REPLY [1 votes]: Well in SM you compute observable using the squared module of the amplitudes. The sign in front of the coupling enter in the amplitude with the Feynman rules of the vertix so if it doesn't matter when you compute the module. It's the same if you i or -i into the Feynman rule


TITLE: Telescoping with imaginary numbers
QUESTION [1 upvotes]: If $\omega^{1997} = 1$ and $\omega \neq 1$, then
$$ \frac{1}{1 + \omega} + \frac{1}{1 + \omega^2} + \dots + \frac{1}{1 + \omega^{1997}}$$
can be written in the form $m/n$, where $m$ and $n$ are relatively prime positive integers. Find the remainder when $m + n$ is divided by 1000.
I really can't seem to find the complex number w that satisfies this condition, and I cannot find any patterns/telescoping methods.  Can anyone help me or give me some pointers?
Thanks!

REPLY [6 votes]: Hint: Just apply the old Gauss trick ! We have

$$\dfrac1{1+w^k}~+~\dfrac1{1+w^{1997-k}}~=~\dfrac1{1+w^k}~+~\dfrac{w^k}{w^k+w^{1997}}~=~\dfrac1{1+w^k}+\dfrac{w^k}{w^k+1}=1.$$

If the sum would have started with $~\dfrac1{1+w^0}=\dfrac12~,~$ then the final result would have been
$\dfrac{1998}2~.~$ As it stands, however, we must subtract $~\dfrac12,~$ thus arriving at $~\dfrac{1997}2~.$


TITLE: How do I "recalculate" a median number?
QUESTION [0 upvotes]: I'm not sure how to explain the question, so I'll do it by an example.
The median age in some country is 41.7. 50% is younger than 41.7, 50% is older.
How would I calculate the percentage of the population being younger and older than say, 31.4, in that country, based on 41.7 being the median age?

REPLY [1 votes]: Even if you know the median, you would need to know what distribution it is (the shape of a graph of the data) because it could be skewed to one side. For things like age, it's likely to be a normal distribution. If that is the case, then you'd need to know more about the data (like the standard deviation or variance or total number of people etc.) to help solve your problem. In other words, knowing the median could tell you where the middle of the distribution is but you don't know how much it's stretched out sideways.


TITLE: about Dirichlet test in convergence
QUESTION [0 upvotes]: whether this infinite sequence $\sum_{n=1}^\infty \frac{(-1)^ncos(nx)}{\sqrt n}$ converge  on $\mathbb R$. I know that it would converge uniformly intuitivly on [$-\pi+\delta$, $\pi-\delta$] where $\delta$ is from $-\pi$ to $\pi$. However, I don't know how to prove my intuition. Thanks for helping.

REPLY [2 votes]: Note that, for any $N\in\mathbb N$, and $x$ in such an interval,\begin{align}\left\lvert\sum_{n=1}^N(-1)^n\cos(nx)\right\rvert&=\left\lvert\sum_{n=1}^N(-1)^n\operatorname{Re}(e^{inx})\right\rvert\\&=\left\lvert\operatorname{Re}\left(\sum_{n=1}^N(-e^{ix})^n\right)\right\rvert\\&=\left\lvert\operatorname{Re}\left(\frac{-e^{ix}-(-1)^{N+1}e^{(N+1)ix}}{1+e^{ix}}\right)\right\rvert\\&\leqslant\left\lvert\frac{-e^{ix}-(-1)^{N+1}e^{(N+1)ix}}{1+e^{ix}}\right\rvert\\&\leqslant\frac2{\bigl\lvert1+e^{ix}\bigr\rvert}.\end{align}Can you take it from here?


TITLE: well-defined function verification
QUESTION [1 upvotes]: Let $G_m$ denote the set of invertible congruence classes in $Z_m$ . Define a map $F: G_{mn} → G_{m} × G_{n}$ by the rule $F([a]_{mn}) = ([a]_m , [a]_n)$.
if ($m,$n) = 1 prove that $F$ is a well-defined function.
I know from the definition of well-defined that the function's output is the same whatever the representative we use, but I'm stuck proving it in this case.

REPLY [2 votes]: It is sufficient to show that the map $[a]_{mn}\mapsto[a]_m$ is well-defined, since if this is well defined, then clearly $[a]_{mn}\mapsto[a]_n$ is well-defined, and hence the product, $[a]_{mn}\mapsto([a]_m, [a]_n)$, is also well-defined.
First let's see an example where it fails. Take $m=3$ and $n=3$, so that $mn=9$. Consider $[2]_{9}$. Then we cannot choose whether $[2]_m=1$ and $[2]_n=2$ or whether $[2]_m=2$ and $[2]_n=1$.
Now suppose $(m,n)=1$. For any $a$ such that $[a]_{mn}\in G_{mn}$,
$$
a = cmn + s
$$
for $s=0,1,\dots,mn-1$. Furthermore, because $(m,n)=1$, we can find a $b = 0,1,\dots,n-1$ and an $r=0,1,\dots,m-1$ such that
$$
s = bm + r
$$
Then it is clear that $[a]_m=[r]_m$, so it is well-defined. We need only show now that $[r]_m\in G_m$. However, this is clear, since $[a]_{mn}\in G_{mn}\implies (s, mn)=1\implies(s,m)=(r,m)=1\implies[r]_m\in G_m$.


TITLE: Polar to cartesian equation conversion
QUESTION [3 upvotes]: I have a polar equation defined as:
$r = ae^{θ \tan m}$
where, $a$ and $m$ are constants, $θ$ is the angle between the horizontal axis from the origin $(x_c,y_c)$ to the coordinate. $e$ refers to exponent.
The equation is illustrated below:
How can I express the above polar equation in Cartesian form? (i.e. I want to get the Cartesian equation that describes the line which passes through the coordinates as indicated by the broken red lines in the above illustration)
The motive behind this is to find the gradient of the broken red line given specified coordinates which lie along the broken red line.

REPLY [2 votes]: Your curve is a logarithmic spiral
$r= ae^{b\theta} $ with $b=\tan m$.
You can express such curve in a parametric form as:
$$
x(t)=ae^{bt}\cos t
$$
$$
y(t)=ae^{bt}\sin t
$$
This is the simpler way to write out the cartesian coordinates.


TITLE: Units of the Boltzmann constant in $2$ dimensions
QUESTION [0 upvotes]: I am answering a question in which volume is given as $m^2$ which I assume means that the question is considering a $2$ dimensional box for the volume. I am trying to calculate $N$ using the given variables however if I don't adjust the units of Boltzmann's constant from $J/k$ to $J/m.K$ then the units won't cancel appropriately. So I am tempted to just use units of $J/m.K$ for it however am I allowed to do this, is there any repercussions for this? is the constant the same value?

REPLY [0 votes]: There are two possibilities:

The question is incorrect.
The question is correct and you'd have to assume that the thickness of the container will be equal to the diameter of the particles, in which case, you'll be able to preserve the 2 dimensional characteristic of the motion and at the same time, you will also not face anh problems regarding the units.


text:
\section{Introduction} \label{sec:intro}

Recovery of sparse or compressible signals from a limited number of noisy linear projections is a problem that has received considerable attention in signal processing and statistics. Suppose, for instance, that a vector $\bx$ of length $n$ is known to have exactly $k$ nonzero elements, but the values and locations of these elements are unknown and must be estimated from a set of $m$ noisy linear projections (or samples \cite{unser00}) of the form
\begin{align}\label{eq:model}
Y_i = \langle \bphi_i,\bx \rangle + W_i \quad \text{for} \quad i = 1,\cdots,m
\end{align}
where $\bphi_i$ are known sampling vectors, $\langle \cdot,\cdot \rangle$ denotes the usual euclidean inner product, and $W_i$ is additive white Gaussian noise. Then, a key insight from sparse signal recovery is that the number of samples required for reliable estimation depends primarily on the number of nonzero elements, and is potentially much less than the length of the vector $\bx$.

One estimation problem of particular interest is to determine which elements of the vector $\bx$ are nonzero. This problem, which is refered to as {\em sparsity pattern} recovery in this paper, is known variously throughout the literature as support recovery or model selection and has applications in compressed sensing \cite{Donoho_IT06,CandesRombergTao06A, CandesTao06}, sparse approximation \cite{DevoLore93}, signal denoising \cite{Chen_JSC98}, subset selection in regression \cite{Miller90}, and structure estimation in graphical models \cite{MeinBuhl06}.

A large body of recent work \cite{MeinBuhl06, ZhaoYu_JMLR06, Wainwright_tech_07, aeron-2007,aeron-2008, Wainwright_SharpThresholds_IEEE09, Wainwright_InfoLimits_IEEE09, akcakaya_IEEE10, Reeves_masters, RG08, FLetcher_IEEE09, Wang_IEEE10, RG-Lower-Bounds}
has considered exact recovery of the sparsity pattern by deriving necessary and sufficient conditions on scalings of the tuple $(n,k,m)$ to ensure that the probability of exact recovery tends to one as the vector length $n$ becomes large. In particular, one line of work has considered the fundamental limitations of the recovery problem that apply to any possible estimator, regardless of computationally complexity. In the noiseless setting, for instance, it has been shown that $m_n = k_n +1$ samples are necessary and sufficient for an NP-hard combinatorial estimator \cite{Feng_ICASP96 ,Natar95}.

In presence of noise, however, support recovery depends critically on properties of the nonzero elements and cannot be characterized solely in terms of the dimensions $n$ and $k$. In this setting, Wainwright \cite{Wainwright_InfoLimits_IEEE09} showed that $m = k+1+ C \cdot k \log n$ samples are sufficient for an NP-hard combinatorial estimator where $C$ is a finite constant that depends on the per-sample signal-to-noise ratio (SNR), the size of the smallest nonzero element, and various properties of the sampling vectors. Ensuing work by Fletcher, Rangan, and Goyal \cite{FLetcher_IEEE09} and Wang, Wainwright, and Ramchandran \cite{Wang_IEEE10}, showed that, for a potentially different constant $C$, this scaling is also necessary for any algorithm.

In conjunction with the fundamental limitations outlined above, another line of work has studied scaling conditions for computationally tractable algorithms. In the noiseless setting, Donoho and Tanner \cite{DT09} showed that $m = 2 k \log(n/m)$ samples are sufficient for a polynomial-time linear program known as Basis Pursuit \cite{Chen_JSC98}. In the noisy setting, Wainwright \cite{Wainwright_SharpThresholds_IEEE09} showed that $m= k + 1 + C_1 \cdot k \log n$ is sufficient for a polynomial-time algorithm known as the Lasso \cite{Tibsh96}, and \cite{FLetcher_IEEE09} showed that $m= k + 1 + C_2 \cdot k \log n$ is sufficient for a thresholding estimator where $C_1$ and $C_2$ are finite constants that depend on the SNR, the size of the smallest nonzero element, and and various properties of the sampling vectors.

Although the scaling conditions outlined above show that exact recovery is possible with a relatively small number of samples, there exist two important limitations. First, if there is a non-vanishing fraction of nonzero elements, that is if $k/n \rw \Omega$ for some {\em sparsity rate} $\Omega>0$, then these results say that the ratio $m/n$ must grow without bound with $n$ in order to overcome the effect of noise. This behavior is in marked contrast to other recovery tasks, such as estimation of the vector $\bx$ with bounded mean squared error (MSE), which require only $m > \rho \cdot n$ samples for some finite {\em sampling rate} $\rho$ (see \cite{DonohoEladTemlyakov_IEEtrans06,CandesRombergTao06}). If noise is due to quantization, this means that accurate estimation with respect to MSE requires only fixed bit-rate whereas exact recovery of the sparsity pattern requires an unbounded bit-rate.

The second limitation is that scaling results in terms of the dimensions $(n,k,m)$ do not tell the whole story. Often, one needs to know the exact constants involved in the bounds, or at least the dependence of these constants on parameters such as the SNR or various assumptions about the vector $\bx$. For many of the estimation tasks considered throughout the compressed sensing literature, these properties are not well understood. As a result, the majority of sufficient conditions are far more conservative than those suggested by empirical evidence, and the optimality (or gap from optimality) of existing algorithms is difficult to determine due to the potential looseness of the necessary conditions.

\subsection{Outline of Main results}
In the present work, we derive upper bounds on the number of samples needed for {\em approximate} recovery of the sparsity pattern in the high dimensional setting when there exists a non-vanishing fraction of nonzero elements. In particular, we consider two different estimation algorithms---the NP-hard combinatorial optimization algorithm studied by Wainwright and the computationally efficient thresholding algorithm studied by Fletcher et al.---and characterize the sampling rate $\rho=m/n$ needed to ensure the number of errors in the estimated sparsity pattern does not exceed $\alpha \cdot k$ for some error rate $\alpha$. Corresponding lower bounds, which apply to any estimator, are derived in the companion paper \cite{RG-Lower-Bounds}. An example of these bounds is shown in Figure \ref{fig:example1}.

\begin{figure}[htbp]
\centering
\psfrag{x1}[]{\small SNR (dB)}
\psfrag{y1}[B]{\small Sampling Rate $\rho$}
\psfrag{t1}[B]{}
\psfrag{MC Upper Bound [?]}[l]{\small  \begin{minipage}{1.4in} \centering Thresholding Upper Bound\\  (Theorem 2) \end{minipage}}
\psfrag{ML Upper Bound [?]}[l]{\small \begin{minipage}{1.45in} \centering  Comb. Opt. Upper Bound\\ (Theorem 1) \end{minipage}}

\psfrag{Lower Bound}[lb]{\small Lower Bound \cite{RG-Lower-Bounds}}
\psfrag{(This Paper)}[lT]{}
\epsfig{file=figures-upper-bounds/introfig.eps, width = \columnwidth}
\caption{Bounds on the asymptotic sampling rate $\rho=m/n$ and SNR required to identify the locations of at least $90\%$ of the nonzero elements of a vector $\bx \in \mathbb{R}^n$ with sparsity rate  $\Omega = k/n = 10^{-4}$ when the power of the smallest nonzero element is at least 20\% of the average power of the nonzero elements.}
\label{fig:example1}
\end{figure}

The contributions of this paper directly address the limitations of the scaling results for exact recovery outlined above. With respect to the first limitation, we show that any error fraction $\alpha>0$ can be achieved using a finite sampling rate $\rho$. In other words, approximate sparsity pattern recovery has the same scaling behavior as estimation of $\bx$ with bounded mean squared error. If noise is due to quantization, this means that a fixed bit-rate is sufficient for approximate sparsity pattern recovery.

With respect to the second limitation, our lower bounds are derived with an explicit dependence on various key problem parameters such as the SNR, the sparsity rate, and the relative size of the smallest nonzero elements. These bounds allow us to consider a wide variety of problem settings where the unknown vectors may be deterministic or stochastic and the magnitude of the smallest nonzero element may tend to zero as the vector length becomes large. Our framework allows us to address a number of important questions:

\begin{itemize}
\item What is the tradeoff between the sampling rate and the SNR? Our bounds show that there are two fundamentally different settings. If the SNR is small relative to the desired distortion then the number of samples needed is inversely proportional to the SNR. However, if the SNR is large relative to the desired distortion, then the number of samples needed is inversely proportional to the logarithm of the SNR.

\item What is the tradeoff between optimality and computational complexity? As illustrated in Figure~\ref{fig:example1}, our bounds show that a computationally simple thresholding estimator is near-optimal in the low-SNR setting. In the high SNR-setting, however, only the computationally hard estimator is shown to attain near-optimal performance. These results suggest that significant computational challenges arise in the high-SNR setting where the difficulty of estimation is due primarily to the uncertainty about the nonzero values.

\item What happens as the desired error rate tends to zero? Our bounds show that the sampling rate depends on the inverse of the error rate $1/\alpha$. If the magnitudes of the nonzero elements have a fixed lower bound that is independent of $n$ then this dependence is logarithmic. Otherwise, the dependence is polynomial.

\item What is the effect of prior information? The upper bounds in this paper correspond to estimators that know the approximate number of nonzero elements, but have no prior information about their values. The lower bounds in the companion paper \cite{RG-Lower-Bounds} apply to settings where the estimator may know statistical information such as the average power, range of values, or distribution. Interestingly, the resulting bounds show that in many cases this additional knowledge does not significantly improve the ability to estimate the sparsity pattern.
\end{itemize}

Beyond these results, our framework also permits us to prove some further insights. For instance, we show that the sampling rate distortion function is a convex function and that, in certain settings, i.i.d. sampling matrices are asymptotically strictly suboptimal.

This paper is organized as follows: Section \ref{sec:formulation} provides a precise problem formulation. Sections \ref{sec:sufML} and \ref{sec:sufTH} provide achievable bounds for two different estimators. Section \ref{sec:rate-sharing} provides improved bounds using a particular set of sampling matrices that we will refer to as ``rate-sharing'' matrices. Section \ref{sec:scaling} analyzes the scaling behavior of these bounds with respect to various key properties. Section \ref{sec:examples} presents specific examples and illustrations, and proofs are given in the Appendices. The following section provides a brief, and necessarily incomplete, overview of work related to this paper.

\subsection{Related Work}

One line of related research \cite{Mallat93, DonoJohn94, Tibsh96, Chen_JSC98, Fuchs_IT05,  CandesTao_IT05,  Donoho_IT06,  CandesRombergTao06A, CandesTao06, DT09, DonohoEladTemlyakov_IEEtrans06, CandesRombergTao06, Tropp_IT06, DonoForMost06, Haupt06, Massart07} has focused on the approximation of sparse vectors with respect to the $\ell_2$ norm. From a scaling perspective, one particularly important result from this literature \cite{DonohoEladTemlyakov_IEEtrans06, CandesRombergTao06} is that any $k$-sparse vector $\bx$ of length $n$ can be approximated with bounded mean squared error $\|\bx -\hat{\bx}\|^2/n < C_1/\text{SNR}$ using $m = \lceil C_2 \cdot k \log(n/k) \rceil$ samples and a quadratic program known as {Basis Pursuit} \cite{Chen_JSC98} where $C_1,C_2$ are finite constants. In the absence of any noise, this result provides sufficient conditions for exact recovery of $\bx$, which in turn implies exact sparsity pattern recovery. In the presence of noise, however, it is important to observe that bounds on the mean squared error are insufficient to determine the accuracy of the estimated sparsity pattern.

Another line of related research\cite{Weid00, Fletcher_JASP06,Sarvotham_Allerton06, Fletcher_SSP07, Fletcher_SP08, WeidVett08} has focused on the rate-distortion behavior of sparse sources from an information-theoretic  perspective. While these works provide valuable insights into the tradeoff between the SNR and the accuracy of approximation of $\bx$ in the $\ell_2$ sense, they do not directly address the problem of sparsity pattern recovery.

Most closely related to the work in this paper is work which has focused directly on sparsity pattern recovery in the presence of noise \cite{MeinBuhl06, ZhaoYu_JMLR06, Wainwright_tech_07, aeron-2007,aeron-2008, Wainwright_SharpThresholds_IEEE09, Wainwright_InfoLimits_IEEE09, akcakaya_IEEE10, Reeves_masters, RG08, FLetcher_IEEE09, Wang_IEEE10, RG-Lower-Bounds}.
As discussed in the introduction, it is now well understood that $m = k +1  + C \cdot k \log n$ samples are both necessary and sufficient for exact recovery when the SNR is finite and there exists a fixed lower bound on the magnitude of the smallest nonzero elements.

The problem of approximate support recovery with a nonzero error rate $\alpha$ has also been considered in recent work. For the special case where the values of the nonzero elements are known, Aeron, Zhao, and Saligrama \cite{aeron-2007,aeron-2008} showed that $m = C \cdot k \log(n/k)$ samples are necessary and sufficient where the constant $C$ is given explicitly in terms of the error rate $\alpha$, the SNR, and nonzero values. In the more general setting where the nonzero values are unknown the necessary and sufficient condition $m = C \cdot k \log(n/k)$ was derived independently by Akcakaya and Tarokh \cite{akcakaya_IEEE10} and the authors of this paper \cite{Reeves_masters, RG08, RG-Lower-Bounds} for the special case where $k/n \rw \Omega \in (0,1)$. While the work of \cite{akcakaya_IEEE10} provides bounds for a variety of scalings, actual upper and lower bounds on the constant $C$ are not explicitly stated. By contrast, the upper bounds in this paper, in conjunction with the lower bounds in the companion paper \cite{RG-Lower-Bounds}, provide a tight characterization of the constant $C$ for the setting of linear sparsity and show how this constant depends on various key properties such as the SNR, the size of the $\alpha k$'th smallest nonzero element, and the distortion $\alpha$. Furthermore, while the upper bounds of \cite{akcakaya_IEEE10} correspond to a computationally hard joint typicality decoding strategy, which requires knowledge of both the sparsity $k$ as well as the SNR, we show the same scaling can be achieved using a computationally tractable thresholding estimator which depends only on the sparsity $k$.

config: arxiv


TITLE: Lindelof Hypothesis implying Selberg Eigenvalue Conjecture?
QUESTION [9 upvotes]: The Generalized Lindelof Hypothesis says that for the $L$-function of an automorphic form we have
$$L(1/2+it)\ll Q(t)^{\epsilon}$$
for any $\epsilon>0$ where $Q(t)$ is the conductor of $L(s)$ at $t$.
For a Maass form $\phi$ of level $N>1$ and eigenvalue $1/4+\lambda^2$, will Lindelof Hypothesis imply Selberg Eigenvalue conjecture, i.e., $\lambda\geq 0$?
I know that functoriality results such as Gelbart-Jacquet, Shahidi, Kim gives a very good bound, such as Kim-Sarnak bound of 7/64. Obviously functoriality for of all symmetric powers implies the Selberg eigenvalue conjecture. The proof involves some non-vanishing results for families of $L$-functions (Kim-Sarnak, Luo-Rudnick-Sarnak). I am thinking about the relation of the Selberg eigenvalue conjectures and the GRH/Lindelof.
Lastly, GRH itself at a single point for one L-function probably does not say much about the Selberg eigenvalue conjecture because GRH only excludes non-trivial zeros. A violation of Selberg eigenvalue conjecture will give us a zero from Gamma factors (thus it is trivial zero). But family of L-functions with GRH or Lindelof possibly can tells more about non-vanishing (trivial zeros) of L-functions.

REPLY [4 votes]: To see that this is not the case, consider that it is well known that the Generalized Riemann Hypothesis implies the Lindelöf hypothesis.
On the other hand, not even the full GRH implies the Selberg Eigenvalue conjecture (or any other Generalized Ramanujan-type conjecture).
In fact, the best bound we can prove under GRH for a Maass form $\pi$ is $|\mathrm{Re}\mu_\pi(\infty,j)|\leq 1/4$, which is quite far from the $|\mathrm{Re}\mu_\pi(\infty,j)|=0$ we need.
There's also an argument of Sarnak that goes something like this:
Take $\pi$ a Maass form, and assume we know all the general Ramanujan conjectures for $\pi$ (we know from Langlands that we can treat the eigenvalue conjecture as a Ramanujan conjecture at infinity).
Then we can prove that $L(s,\pi)$ is uniformly bounded in $\mathrm{Re}(s)>1+\epsilon$, with $\epsilon >0$, but we can't push this result even to $\mathrm{Re}(s)=1$.
On the other direction, we have the same problem when we try to use the Generalized Lindelöf hypothesis to give information about $\pi$ beyond $\mathrm{Re}(s)=1$.


TITLE: Show $E\left(\mathbf{X}_i \otimes \mathbf{u}_i\right)=\mathbf{0}$ implies $E\left(\mathbf{X}_i^{\top}\mathbf{G}\mathbf{u}_i\right)=\mathbf{0}$
QUESTION [1 upvotes]: Let $\mathbf{X}_i$ be a $G \times K$ random matrix, and let $\mathbf{u}_i$ be a $G \times 1$ random vector, and suppose we have a sample of $i=1,\ldots,N$ of each.
Suppose the following condition holds:
\begin{equation}
E\left(\mathbf{X}_i \otimes \mathbf{u}_i\right)=\mathbf{0}
\end{equation}
where "$\otimes$" denotes the Kronecker Product.
Now show, for some arbitrary $G \times G$ symmetric matrix $\mathbf{G}$, that
\begin{equation}
E\left(\mathbf{X}_i^{\top}\mathbf{G}\mathbf{u}_i\right)=\mathbf{0}
\end{equation}
is implied by the first condition.

The first condition (the one involving the Kronecker Product) essentially says that every component of $\mathbf{X}_i$ is uncorrelated with every element of $\mathbf{u}_i$. Therefore, the argument is this: Because of the first condition, therefore any linear combination of $\mathbf{X}_i$ is uncorrelated with $\mathbf{u}_i$. This is the explanation given, and supposedly this is trivial, but I'm trying to see it mathematically.
Thanks for your help!

REPLY [2 votes]: I think it can be helpful to leave the matrix world temporarily to see what it means in terms of scalar variables. Let's see if you agree...
Let $\mathbf X_i$ consist of elements $x_i^{(j, k)}$ and $\mathbf u_i$ of elements $u_i^{(l)}$, where $j=1, \dots G$,  $k=1, \dots, K$ and $l=1, \dots, G$. The $G^2\times K$ matrix $E(\mathbf X_i \otimes \mathbf u_i)$ consists of elements $E(x_i^{(j, k)}u_i^{(l)})$, so the condition is equal to postulating $E(x_i^{(j, k)}u_i^{(l)})=0$.
If we denote the elements of $\mathbf G$ by $g^{(m, l)}$ the product $\mathbf G \mathbf u_i$ will be $G\times 1$ with elements $\sum_{l=1}^G g^{(m, l)}u_i^{(l)}$. So then what we have is
$$
E(\mathbf X_i'\mathbf G \mathbf u_i)=E\left(\begin{pmatrix}x_i^{(1, 1)} & x_i^{(2, 1)} & \dots & x_i^{(G, 1)}\\
x_i^{(1, 2)} & x_i^{(2, 2)} & \dots & x_i^{(G, 2)}\\
\vdots & \vdots & \ddots & \vdots\\
x_i^{(1, K)} & x_i^{(2, K)} & \dots & x_i^{(G, K)} \end{pmatrix}\begin{pmatrix}\sum_{l=1}^G g^{(1, l)}u_i^{(l)}\\\sum_{l=1}^G g^{(2, l)}u_i^{(l)} \\ \vdots \\ \sum_{l=1}^G g^{(G, l)}u_i^{(l)}\end{pmatrix}\right)\\
=E\left(\begin{pmatrix}\sum_{j=1}^G\sum_{l=1}^G g^{(j, l)}x_i^{(j, 1)}u_i^{(l)}\\\sum_{j=1}^G\sum_{l=1}^G g^{(j, l)}x_i^{(j, 2)}u_i^{(l)} \\ \vdots \\ \sum_{j=1}^G\sum_{l=1}^G g^{(j, l)}x_i^{(j, G)}u_i^{(l)}\end{pmatrix}\right)\\
=\begin{pmatrix}\sum_{j=1}^G\sum_{l=1}^G g^{(j, l)}E(x_i^{(j, 1)}u_i^{(l)})\\\sum_{j=1}^G\sum_{l=1}^G g^{(j, l)}E(x_i^{(j, 2)}u_i^{(l)}) \\ \vdots \\ \sum_{j=1}^G\sum_{l=1}^G g^{(j, l)}E(x_i^{(j, G)}u_i^{(l)})\end{pmatrix}=\boldsymbol{0}
$$
I think this shows the "linear combination" part of the answer quite well.