# Meeting notes 08/03
Hi from Tony !

Consider the term $\sum_{t=0}^{T} e^{(f_T -f _{t+1})/\epsilon} \eta_t \prod_{s=t+1}^{T} (1-\eta_{s})$.

Assume there exists some $M$ such that $\exp\left((f_{t_1} - f_{t_2})/\epsilon\right) < M$ for any $t_1,t_2>0$,
$$
\sum_{t=0}^{T} e^{(f_T -f _{t+1})/\epsilon} \eta_t \prod_{s=t+1}^{T} (1-\eta_{s}) \leq M \sum_{t=0}^{T} \eta_t \prod_{s=t+1}^{T} (1-\eta_{s}) .
$$

Suppose $\eta_0=1$ and $\eta_t = t^{\beta}$ for $-1<\beta<-\frac{1}{2}$, because we want $\sum\eta_t = \sum t^{\beta}=\infty$ and $\sum\eta_t^2 = \sum t^{2\beta}<\infty$.

$$\sum_{t=0}^T \eta_t \prod_{s=t+1}^{T} (1-\eta_{s})= \left( \sum_{t=0}^{L}+ \sum_{L+1}^T \right) \eta_t \prod_{s=t+1}^{T} (1-\eta_{s})$$

Consider the first term on the RHS,
\begin{align*}
\sum_{t=0}^{L} \eta_t \prod_{s=t+1}^{T} (1-\eta_{s}) & \leq \sum_{t=0}^{L} \eta_0 \exp \left( -\sum_{s=t+1}^{T} \eta_s \right)\\
&\leq (L+1) \exp \left( - (T-L) \eta_T \right) ,
\end{align*}

taking $L=\frac{T}{2}$, then
$$
L \eta_{0} \exp \left( - (T-L) \eta_T \right) = \exp \left( - \frac{T^{1+\beta}}{2} \right) \left( \frac{T}{2}+1 \right)
$$

Now consider the second term on the RHS,
\begin{align*}
\sum_{t = L+1}^T \eta_t \prod_{s=t+1}^{T} (1-\eta_{s}) &\leq \sum_{t=L+1}^T \eta_t (1-\eta_T)^{(T-t)}\\
& < \eta_L \sum_{t=L+1}^T (1-\eta_T)^{(T-t)} \hspace{2em}\text{as } \eta_t < \eta_L\\
&= \eta_L \left( 1- \eta_T\right)^{T-L-1}\frac{1-(1-\eta_T)^{T-L}}{\eta_T},
\end{align*}

$\le \eta_L/\eta_T.$

hence this term is bounded.

-----------------

\begin{align*}
\int_{A} \int_{Y}g(y)d \pi' (x,y) &= \int_{A}\int_{Y} \min \left\{ \frac{d\beta_a}{d \left( {P_2}_{\sharp}\pi'\right)}, 1\right\} d\pi'(x,y)\\
&\leq \int_{A}\int_{Y} d\pi'(x,y) = \int_{A}\int_{Y} f(x) d\gamma(x,y)\\
&\leq \int_{A}\int_{Y} \min \left\{ \frac{d\alpha_a}{d\alpha'}, 1\right\} d\gamma(x,y)\\
&\leq \int_{A}\int_{Y} \frac{d\alpha_a}{d\alpha'} d\gamma(x,y) = \int_{A} \frac{d\alpha_a}{d\alpha'} \int_{Y}d\gamma(x,y)\\
&= \int_{A} \frac{d\alpha_a}{d\alpha'} d\alpha'\\
&\leq \int_{A} d\alpha_a(x)
\end{align*}

Now we will show that $\|\epsilon_1\|_{TV} = \|\epsilon_2\|_{TV}$,
\begin{align*}
\|\epsilon_1\|_1 &= \int d\left(\alpha(x) - {P_1}_{\sharp} \pi''(x)\right)\\
&= 1 - \int d\left( {P_1}_{\sharp} \pi''(x)\right)\\
&= 1- \int\int d\pi''(x,y)
\end{align*}

\begin{align*}
{P_1}_{\sharp} \gamma' &={P_1}_{\sharp} \left( \pi''\right) + \frac{\epsilon_1\|\epsilon_2\|_{TV} }{\|\epsilon_1\|_{TV}} \\
&= {P_1}_{\sharp} \pi'' + \alpha - {P_1}_{\sharp}\pi'' = \alpha,
\end{align*}

% explain more on the first line
% Def of pushforwards

Now let $\Delta = \|\gamma\|_{TV} - \|\pi''\|_{TV}$. Notice that as a result of Steps $2$ and $5$ in the Algorithm, we have $f$ and $g$ are uniformly bounded by $1$. Therefore,
\begin{align*}
\Delta &= \int \int d\gamma(x, y) - \int \int \left| f(x)g(y) \right|d\gamma(x,y)\\
&= \int \int \left(1- f(x)g(y) \right)d\gamma(x,y)\\
&= \int\int \left(1-f(x)\right)d\gamma(x,y) +\int\int f(x)\left( 1-g(y)\right)d\gamma(x,y)\\
&= \int\left(1-f(x)\right)d\alpha'(x)+\int \left(1-g(y)\right)d\beta'(x)\\
& = \int d\left( \alpha'(x) - \alpha_a(x) \right)_+ + \int d\left( \beta'(y) - \beta_a(y) \right)_+
\end{align*}

% need more words for the last line

$f=f_+ - f_-$ % check def

$$f_+, f_-\ge 0$$.

Consider the first term on the RHS,
\begin{align*}
\int \left( d\alpha'(x) - d\alpha_a(x)\right)_+ &= \frac{1}{2} \int \left( d\alpha'(x) - d\alpha_a(x)\right)_+ + \frac{1}{2} \left( \int \left( d\alpha'(x) - d\alpha_a(x)\right) + \int \left( d\alpha'(x) - d\alpha_a(x)\right)_- \right)\\
&= \frac{1}{2}\left(\| \alpha'-\alpha_a \|_{TV} +\|\alpha'\|_{TV} - \int d\alpha_a+ \int \alpha_s(x) - \int \alpha_s \right)
\end{align*}

$\int \left( d\alpha'(x) - d\alpha_a(x)\right) = \|\alpha'\|_{TV} - \int d\alpha_a(x)$
$\frac{1}{2} \int \left( d\alpha'(x) - d\alpha_a(x)\right)_+ - \frac{1}{2} \left( \int \left( d\alpha'(x) - d\alpha_a(x)\right)_- \right)$

----------

$$
\int \int d \left( \beta'(y) - \beta_a(y) \right)_+
\leq \int d\left ( {P_2}_{\sharp} \gamma(x,y)-\beta_a(y)\right)_+
\leq \left\| {P_2}_{\sharp} \gamma - \beta_a \right\|_{TV}
$$

\begin{align*}
\left\| \gamma' -\gamma \right\|_{TV} & \leq \left\| \gamma -\pi'' \right\|_{TV} + \left\| \pi'' -\gamma' \right\|_{TV}\\
& = \int\int \left|1-f(x)g(y) \right|d\gamma + \int\int\frac{1}{\|\epsilon_1\|_{TV}} d\epsilon_1(x)d\epsilon_2(y)\\
& = \int\int \left(1-f(x)g(y) \right)d\gamma + \frac{1}{\|\epsilon_1\|_{TV}}\int d\epsilon_1(x)\int d\epsilon_2(y) \\
& = \|\gamma\|_{var} - \|\pi''\|_{var} + \|\epsilon_1(x) \epsilon_2(y)\|_{TV}/\|\epsilon_1(x)\|_{TV} \\
& = \Delta + 1 - \|\pi''\|_{var}\\
& = 2\Delta+1-\|\gamma\|_{TV}\\
& \leq \left(\| \alpha'-\alpha_a\|_{TV} +\|\alpha'\|_{TV} - \int d\alpha_a(x)\right) + 2\left\| {P_2}_{\sharp} \gamma - \beta_a \right\|_{TV} +1-\|\gamma\|_{TV}\\
& \leq 2\| {P_1}_{\sharp} \gamma - \alpha_a\|_{TV} + 2 \| {P_2}_{\sharp} \gamma-\beta_a\|_{TV}.
\end{align*}