text:
\begin{appendices}

\section{Proof of Lemma \ref{lemma1}}\label{app_proof_of_lemma_1}

To prove the claim in Lemma \ref{lemma1} we first prove the following intermediate lemma.

 \begin{lemma} \label{lemma3}
Consider the non-negative sequence $e_t$ satisfying the inequality
\begin{equation}\label{eq:recursive_expression}
    e_{t+1}\leq \left(1-\frac{a}{T^{2\delta}}\right) e_t +\frac{b}{T^{3\delta}},
\end{equation}
for $t\geq 0$, where $a$ and $b$ are positive constants, $\delta\in[0,1/2)$, and $T$ is the total number of iterations. Then, after $T \geq \max \left\{ a^{1/(2\delta)}, \exp\left(\exp\left(1/\left(1-2\delta\right)\right)\right) \right\}$ iterations the iterate $e_T$ satisfies

\begin{equation}\label{lkjnjlknl}
    e_T \leq \mathcal{O}\left(\frac{b}{aT^{\delta}}\right).
\end{equation}

\end{lemma}

\begin{proof}
Use the expression in \eqref{eq:recursive_expression} for steps $t-1$ and $t$ to obtain

\begin{align}
    e_{t+1}
    & \leq  \left(1-\frac{a}{T^{2\delta}}\right)^2 e_{t-1} \nonumber\\
    & \quad +\left[1+\left(1-\frac{a}{T^{2\delta}}\right) \right]\frac{b}{T^{3\delta}},
\end{align}

where $T \geq a^{1/(2\delta)}$. By recursively applying these inequalities for all steps $t\geq 0$ we obtain that

\begin{align}
    & e_{t} \leq  \left(1-\frac{a}{T^{2\delta}}\right)^t e_{0}
     \nonumber\\
     &+\frac{b}{T^{3\delta}} \left[1+\left(1-\frac{a}{T^{2\delta}}\right) +\dots +\left(1-\frac{a}{T^{2\delta}}\right)^{t-1} \right] \nonumber\\
     &\leq  \left(1-\frac{a}{T^{2\delta}}\right)^t e_{0}
     +\frac{b}{T^{3\delta}} \left[\sum_{s=0}^{t-1}\left(1-\frac{a}{T^{2\delta}}\right)^{s} \right] \nonumber\\
     &\leq  \left(1-\frac{a}{T^{2\delta}}\right)^t e_{0}
     +\frac{b}{T^{3\delta}} \left[\sum_{s=0}^{\infty}\left(1-\frac{a}{T^{2\delta}}\right)^{s} \right] \nonumber\\
     &=  \left(1-\frac{a}{T^{2\delta}}\right)^t e_{0}
     +\frac{b}{T^{3\delta}} \left[\frac{1}{1- \left( 1-\frac{a}{T^{2\delta}} \right) } \right] \nonumber\\
     &=  \left(1-\frac{a}{T^{2\delta}}\right)^t e_{0}
     +\frac{b}{aT^{\delta}}.
\end{align}

Therefore, for the iterate corresponding to step $t=T$ we can write

\begin{align}
    e_{T}
     &\leq
      \left(1-\frac{a}{T^{2\delta}}\right)^T e_{0}
     +\frac{b}{aT^{\delta}}  \nonumber\\
     &\leq
      \exp \left({-aT^{(1-2\delta)}} \right) e_{0}
     +\frac{b}{aT^{\delta}}  \label{eq:withexp} \\
     &=
      \mathcal{O}\left(\frac{b}{ aT^{\delta}}\right),
\end{align}

and the claim in \eqref{lkjnjlknl} follows. Note that for the last inequality we assumed that the exponential term in is negligible comparing to the sublinear term. It can be verified for instance if $1-2\delta$ is of $\mathcal{O} \left( 1/\log(\log(T)) \right)$ or greater than that, it satisfies this condition. Moreover, setting $\delta=1/2$ results in a constant (and hence non-vanishing) term in (\ref{eq:withexp}).
\end{proof}

 Now we are at the right position to prove Lemma \ref{lemma1}. We start by evaluating the gradient function of $h_{\al}$ at the concatenation of local variables at time $t \geq 1$, that is $\gr h_{\al}(\bx_t)= \big(\bI - \bW \big) \bx_t + \al \gr F(\bx_t)$. Consider the vector $\bz_t=[\bz_{1,t};\dots;\bz_{n,t}]$ as the concatenation of the quantized variant of the local updates $\bx_t=[\bx_{1,t};\dots;\bx_{n,t}]$. Then, we obtain that the expression on the right hand side of \eqref{eq:rule-matrix}, i.e.,

 \begin{equation}\label{eq:htilde}
     \widetilde{\gr}h_{\al}(\bx_t)=\big(\bW_{D} - \bW\big) \bz_{t} + \big(\bI - \bW_D \big) \bx_t + \al \gr F(\bx_{t}),
 \end{equation}

 defines a stochastic estimate of the true gradient of $h_{\al}$ at time $t$, i.e., $\gr h_{\al}(\bx_t)$. We let $\cF^t$ denote a sigma algebra that measures the history of the system up until time $t$ and take the conditional expectation $\Expc[\cdot|\cF^t]$ from both sides of (\ref{eq:htilde}). It yields

 \begin{align}
     &\Expc \left[  \widetilde{\gr}h_{\al}(\bx_t) \vert \cF^t \right] \nonumber\\
     & \quad = \left(\bW_{D} - \bW \right) \Expc \left[\bz_{t}|\cF^t \right] + \left(\bI - \bW_D \right) \bx_t + \al \gr F(\bx_{t}), \nonumber\\
     & \quad = \left(\bI - \bW \right) \bx_t + \al \gr F(\bx_t)\nonumber\\
     & \quad = \gr h_{\al}(\bx_t),
 \end{align}

 where we used the fact that $\Expc \left[\bz_{t}|\cF^t \right]=\bx_t$ (Assumption \ref{assump3}). Hence, $\widetilde{\gr}h_{\al}$ is an unbiased estimator for the true gradient $\gr h_{\al}$. Now, we can rewrite the update rule (\ref{eq:rule-matrix}) as

 \begin{equation} \label{eq:hsgd}
     \bx_{t+1} = \bx_{t} - \eps \widetilde{\gr}h_{\al}(\bx_t),
 \end{equation}

 which resembles the stochastic gradient descent (SGD) update with step-size $\eps$ for minimizing the objective function $h_{\al}(\bx)$ over $\bx \in \mathbb{R}^{np}$. Intuitively, one can expect that, for proper pick of step-size, the the sequence $\{\bx_t;t=1,2,\dots\}$ produced by update rule (\ref{eq:hsgd}) converges to the unique minimizer of $h_{\al}(\bx)$. More precisely, we can write for $t\geq 1$,

 \begin{align}
& \bE \left[ \norm{\bx_{t+1} - \bx^*_{\al}}^2 \vert \cF^t\right] \nonumber\\
&\quad = \bE \left[\norm{\bx_{t} - \eps \widetilde{\gr}h_{\al}(\bx_t) - \bx^*_{\al}}^2 | \cF^t\right]  \nonumber\\
 &\quad= \norm{\bx_{t} - \bx^*_{\al}}^2 -2 \eps \left\langle \bx_{t} - \bx^*_{\al}, \bE \left[\widetilde{\gr}h_{\al}(\bx_t)| \cF^t \right] \right\rangle \nonumber\\
 &\quad \quad + \eps^2 \bE \left[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\right]  \nonumber\\
 &\quad= \norm{\bx_{t} - \bx^*_{\al}}^2 -2 \eps \left\langle \bx_{t} - \bx^*_{\al}, {\gr}h_{\al}(\bx_t) \right\rangle \nonumber\\
 &\quad \quad + \eps^2 \bE \left[ \norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\right]  \nonumber\\
 &\quad\leq \left(1-2 \mu_{\al} \eps \right)\norm{\bx_{t} - \bx^*_{\al}}^2 + \eps^2 \bE \left[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\right]. \label{eq:bound1}
\end{align}

 We have used the facts that $\widetilde{\gr}h_{\al}$ is unbiased and $h_{\al}$ is strongly convex with parameter $\mu_{\al}$. Next, we bound the second term in (\ref{eq:bound1}), that is

\begin{align}
\bE & \left[ \norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 \vert \cF^t\right] \nonumber\\
&= \bE \left[ \norm{ \left(\bW_{D} - \bW\right) \bz_{t} + \left(\bI - \bW_D \right) \bx_t + \al \gr F(\bx_{t})}^2 \vert \cF^t\right] \nonumber\\
&\leq \norm{{\gr}h_{\al}(\bx_t)}^2 + \bE \left[ \norm{ \left(\bW_{D} - \bW\right)( \bz_{t} -\bx_t)}^2  \vert \cF^t\right]  \nonumber\\
&\leq L^2_{\al} \norm{\bx_{t} - \bx^*_{\al}}^2 + { n}\sigma^2 \norm{W-W_D}^2, \label{eq:bound2}
\end{align}

where we used the smoothness of $h_{\al}$ and boundedness of quantization noise. Plugging (\ref{eq:bound2}) into (\ref{eq:bound1}) yields

\begin{align}
 \bE \left[\norm{\bx_{t+1} - \bx^*_{\al}}^2 | \cF^t\right]
 &\leq \left(1-2 \mu_{\al} \eps + \eps^2 L^2_{\al} \right)\norm{\bx_{t} - \bx^*_{\al}}^2 \nonumber\\
 & \quad + \eps^2 { n}\sigma^2 \norm{W-W_D}^2. \label{eq:bound3}
\end{align}

Let us define the sequence $e_t := \bE \left[\norm{\bx_{t} - \bx^*_{\al}}^2 \right]$ as the expected squared deviation of the local variables from the optimal solution ${\bx_{\al}^*}$ at time $t \geq 1$. By taking the expectation of both sides of (\ref{eq:bound3}) with respect to all sources of randomness from $t=0$ we obtain that

\begin{align}\label{eq:bound4}
 e_{t+1} &\leq  \big(1-2 \mu_{\al} \eps + \eps^2 L^2_{\al} \big)e_t + \eps^2 { n}\sigma^2 \norm{W-W_D}^2 \nonumber\\
 &= \big(1-\eps (2 \mu_{\al}  - \eps L^2_{\al}) \big)e_t + \eps^2 {  n}\sigma^2 \norm{W-W_D}^2.
\end{align}

Notice that for the specified choice of $\eps$ and $T\geq T_1$, we have $T^{\delta} \geq T_1^{\delta} \geq  \frac{c_1 (1+c_2 L)^2}{c_2 \mu} $ and therefore

\begin{align}
\eps &= \frac{c_1}{T^{3\delta/2}}\nonumber\\
&\leq \frac{c_2 \mu }{(1+c_2 L)^2} \cdot \frac{1}{T^{\delta/2}}\nonumber\\
&\leq \frac{\mu_{\al}}{ \big(1-\lambda_n(W) + \al L \big)^2 }\nonumber\\
&\leq \frac{\mu_{\al}}{L^2_{\al}}.
\end{align}

Therefore, (\ref{eq:bound4}) can be written as

\begin{align}\label{eq:bound5}
 e_{t+1} &\leq  \left(1-\eps \left(2 \mu_{\al}  - \eps L^2_{\al} \right) \right)e_t + \eps^2 {  n}\sigma^2 \norm{W-W_D}^2 \nonumber\\
 &\leq \left(1- \mu_{\al} \eps \right)e_t + \eps^2 {  n}\sigma^2\norm{W-W_D}^2 \nonumber\\
 &= \left(1- \frac{c_1 c_2 \mu}{T^{2\delta}} \right) e_t + \frac{c^2_1 {  n}\sigma^2 \norm{W-W_D}^2}{T^{3\delta}} .
\end{align}

Now we let $a=c_1 c_2 \mu$ and $b=c^2_1 {  n}\sigma^2 \norm{W-W_D}^2$ and employ Lemma \ref{lemma3} to conclude that

 \begin{align}\label{eq:lemma1}
e_T &= \Expc \left[  \norm{\bx_T - \bx^*_{\al}}^2 \right]  \nonumber\\
 &\leq \mathcal{O}\left(\frac{b}{a T^{\delta}}\right) \nonumber\\
 & = \mathcal{O} \left( \frac{c_1 { n} \sigma^2 \norm{W\!-\!W_D}^2}{\mu c_2} \frac{1}{T^{\delta}} \right),
\end{align}

and the proof of Lemma \ref{lemma1} is complete.

\section{Proof of Lemma \ref{lemma2}}\label{app_proof_of_lemma_2}

First, recall the penalty function minimization in (\ref{eq:hmin}). Following sequence is the update rule associated with this problem when the gradient descent method is applied to the objective function $h_{\al}$ with the unit step-size $\gamma=1$,

\begin{equation}\label{eq:gd}
\bu_{t+1} = \bu_{t} - \gamma \gr h_{\al} (\bu_t)= \bW \bu_t - \al \gr F(\bu_t).
\end{equation}

From analysis of GD for strongly convex objectives, the sequence $\{ \bu_{t} : t=0,1,\cdots\}$ defined above exponentially converges to the minimizer of $h_{\al}$, $\bx^*_{\al}$, provided that $1=\gamma \leq \frac{2}{L_{\al}}$. The latter condition is satisfied if we make $\al \leq \frac{1+\lambda_n(W)}{L}$, implying $L_{\al} = 1-\lambda_n(W) + \al L \leq 2$. Therefore,

\begin{align}\label{eq:gd}
 \norm{\bu_{t} - \bx^*_{\al}}^2 &\leq (1- \mu_{\al})^{t}\norm{\bu_{0} - \bx^*_{\al}}^2 \nonumber\\
 &= (1- \al \mu)^{t}\norm{\bu_{0} - \bx^*_{\al}}^2.
\end{align}

\iffalse
If we take $\al=\frac{c_2}{T^{(1-\delta)/4}}$, then (\ref{eq:gd}) implies

\begin{align}\label{eq:gd2}
    \norm{\bu_{T} - \bx^*_{\al}}^2 &\leq \cO\Big( (1-\frac{c_2}{T^{(1-\delta)/4}})^T\Big)\nonumber\\
    &=\cO \Big( e^{-c_2 T^{(3+\delta)/4}} \Big) = o(1).
\end{align}

{\color{red} We still don't know whether $\norm{\bu_{0} - \bx^*_{\al}}^2$ is bounded, so I think (45) can not be derived from (44) unless we assume $\norm{\bx^*} \leq B$ and do the following:\\
Let $\bu_{0}=0$. Then from (44), we have

\begin{align}
    \norm{\bu_{T} - \bx^*_{\al}}^2 &\leq   e^{-c_2 T^{(3+\delta)/4}}   \norm{\bx^*_{\al}}^2 \\
    &\leq 2  e^{-c_2 T^{(3+\delta)/4}}  \Big( \norm{\bx^* - \bx^*_{\al}}^2 + \norm{\bx^*}^2 \Big) \\
    &\leq 2  e^{-c_2 T^{(3+\delta)/4}}  \Big( \norm{\bx^* - \bx^*_{\al}}^2 + B^2 \Big)
\end{align}

}
\fi
If we take $\bu_{0}=0$, then (\ref{eq:gd}) implies

\begin{align}
    \norm{\bu_{T} - \bx^*_{\al}}^2 &\leq   (1- \al \mu)^{T}  \norm{\bx^*_{\al}}^2\nonumber \\
    &\leq 2  (1- \al \mu)^{T}  \left( \norm{\bx^* - \bx^*_{\al}}^2 + \norm{\bx^*}^2 \right) \nonumber\\
    &= 2  (1- \al \mu)^{T}  \left( \norm{\bx^* - \bx^*_{\al}}^2 + n \norm{\widetilde{\bx}^*}^2 \right) \label{eq:bounduT},
\end{align}

where $f_0 = f(0)$ and $f^* = \text{min}_{\bx \in \mathbb{R}^p} f(\bx) = f(\widetilde{\bx}^*)$. On the other hand, it can be shown \cite{yuan2016convergence} that if $\al \leq \text{min} \left\{ \frac{1+\lambda_n(W)}{L} , \frac{1}{\mu  + L } \right\}$, then the sequence $\{ \bu_{t} : t=0,1,\cdots\}$ defined in (\ref{eq:gd}) converges to the $\cO \left(\frac{\al}{1-\beta} \right)$-neighborhood of the optima $\bx^*$, i.e.,

\begin{equation}\label{eq:gd3}
    \norm{\bu_{t} - \bx^*} \leq \cO\left(\frac{\al}{1-\beta} \right).
\end{equation}

If we take $\al=\frac{c_2}{T^{\delta/2}}$, the condition $T \geq T_2$ implies that $\al \leq \text{min} \left\{ \frac{1+\lambda_n(W)}{L} , \frac{1}{\mu  + L } \right\}$. Therefore, (\ref{eq:gd3}) yields

\begin{equation}\label{eq:gd4}
    \norm{\bu_{T} - \bx^*} \leq \cO \left(\frac{\al}{1-\beta} \right).
\end{equation}

More precisely, we have the following (See Corollary 9 in \cite{yuan2016convergence}):

\begin{equation} \label{eq:exactb}
    \norm{\bu_{T} - \bx^*} \leq \sqrt{n} \left(  c^T_3 \norm{\widetilde{\bx}^*} + \frac{c_4}{\sqrt{1-c^2_3}} + \frac{\al D}{1-\beta} \right),
\end{equation}

where

\begin{equation}
    c^2_3 = 1 - \frac{1}{2} \cdot \frac{\mu L}{\mu + L}  \al ,

\end{equation}

\begin{align}
	\frac{c_4}{\sqrt{1-c^2_3}} &= \frac{\al L D}{1-\beta} \sqrt{ 4 \left( \frac{\mu+L}{\mu L} \right)^2 - 2 \cdot \frac{\mu+L}{\mu L} \al } \nonumber \\
	& \leq \frac{2 \al  D }{  (1-\beta)} \left(1+L / \mu \right).
\end{align}

From (\ref{eq:exactb}) and (\ref{eq:gd4}), we have for $T \geq T_2$

\begin{align} \label{eq:boundT2}
   \norm{\bx^*_{\al} - \bx^*}^2 &= \norm{\bx^*_{\al} -\bu_{T}+\bu_{T}- \bx^*}^2 \nonumber\\
   &\leq 2\norm{\bx^*_{\al} -\bu_{T}}^2 + 2\norm{\bu_{T}- \bx^*}^2 \nonumber\\
   &\leq 4  (1- \al \mu)^{T}  \left( \norm{\bx^* - \bx^*_{\al}}^2 + n \norm{\widetilde{\bx}^*}^2 \right) \nonumber\\
   & \quad + 2n \Bigg(  \left( 1 - \frac{1}{2} \cdot \frac{\mu L}{\mu + L}  \al \right)^{T/2} \norm{\widetilde{\bx}^*} \nonumber\\
   & \quad +  \frac{\al D}{1-\beta} \left(3+ 2L / \mu \right) \Bigg)^2.
\end{align}

Note that for our pick $\al = \frac{c_2}{T^{\delta/2}}$, we can write

\begin{align}
	(1- \al \mu)^{T} &\leq \exp\left( -c_2 T^{1-\delta/2} \right) \eqqcolon e_1(T),  \nonumber\\
	\left( 1 - \frac{1}{2} \cdot \frac{\mu L}{\mu + L}  \al \right)^{T/2} &\leq \exp \left( -\frac{1}{2} \cdot \frac{\mu L}{\mu + L}c_2 T^{1-\delta/2} \right)\nonumber\\
	& \eqqcolon e_2(T).
\end{align}

Therefore, from (\ref{eq:boundT2}) we have

\begin{align} \label{eq:boundT3}
   \norm{\bx^*_{\al} - \bx^*}^2  &\leq  \frac{1}{\left( 1 - 4e_1(T)  \right)} \Bigg\{ 4e_1(T) n \norm{\widetilde{\bx}^*}^2  \nonumber \\
   &\quad + 2n e^2_2(T) \norm{\widetilde{\bx}^*}^2 \nonumber \\
   &\quad+ 4n e_2(T) \norm{\widetilde{\bx}^*} \frac{\al D}{1-\beta} \left(3+ 2L / \mu \right) \nonumber \\
   &\quad+ 2n D^2 \left(3+ 2L / \mu \right)^2 \left( \frac{\al}{1-\beta}  \right)^2 \Bigg\} \nonumber \\
   &\leq  \frac{4n \left( 2 e_1(T) + e^2_2(T) \right)}{\left( 1 - 4e_1(T)  \right)} \frac{f_0 - f^*}{\mu} \nonumber \\
   &\quad + \frac{4 \sqrt{2} n e_2(T)}{\left( 1 - 4e_1(T)  \right)} \sqrt{ \frac{f_0 - f^*}{\mu} } \frac{\al D}{1-\beta} \left(3+ 2L / \mu \right) \nonumber \\
   &\quad+ \frac{2n D^2 \left(3+ 2L / \mu \right)^2}{\left( 1 - 4e_1(T)  \right)} \left( \frac{\al}{1-\beta}  \right)^2,
\end{align}

where we used the fact that $\norm{\widetilde{\bx}^*}^2 \leq 2(f_0 - f^*)/ \mu$. Let $B_1(T)$ denote the bound in RHS of (\ref{eq:boundT3}). Given the fact that the terms $e_1(T)$ and $e_2(T)$ decay exponentially, i.e. $e_1(T)=o\left( \al^2 \right)$ and $e_2(T)=o\left( \al^2 \right)$,  we have

\begin{align} \label{eq:boundT4}
   \norm{\bx^*_{\al} - \bx^*} &\leq \cO \left( \sqrt{2n} D \left(3+ 2L/\mu\right) \left( \frac{\al}{1-\beta}  \right) \right) \nonumber \\
   &=  \cO \left( \frac{\sqrt{2n} c_2 D \left(3+ 2L/\mu\right)}{ 1-\beta}  \frac{1}{T^{\delta/2}} \right)
\end{align}

which concludes the claim in Lemma \ref{lemma2}.
Moreover, due to the exponential decay of the two terms $e_1(T)$ and $e_2(T)$, we have

\begin{align}
   B_1(T) &\approx 2n D^2 \left( 3+ 2L / \mu \right)^2 \left( \frac{\al}{1-\beta}  \right)^2 \\
   & = \frac{2n c^2_2 D^2 \left(3+ 2L/\mu\right)^2 }{(1-\beta)^2}  \frac{1}{T^{\delta}}.
\end{align}

\section{Proof of Theorem \ref{thm2}}\label{app_proof_of_theorem_2}

Note that the steps of the proof are similar to the one for Theorem \ref{thm1}. There, we derived the convergence rate of each worker, i.e. $\bE \Big[\norm{\bx_{i,T} - \widetilde{\bx}^*}^2\Big]$ by bounding two quantities $\Expc \Big[\norm{\bx_T - \bx^*_{\al}}^2 \Big]$ and $\norm{\bx^*_{\al} - \bx^*}$ as in Lemma \ref{lemma1} and \ref{lemma2} respectively. Here, replacing Assumption \ref{assump3} by Assumption \ref{assump5} acquires only the former quantity to revisit.
From (\ref{eq:bound1}), we have that for $t\geq 1$,

 \begin{align}
 \bE \left[ \norm{\bx_{t+1} - \bx^*_{\al}}^2 \vert \cF^t \right] &\leq (1-2 \mu_{\al} \eps)\norm{\bx_{t} - \bx^*_{\al}}^2 \nonumber\\
 & \quad + \eps^2 \bE \left[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\right]. \label{eq:newbound2}
\end{align}

 Considering Assumption \ref{assump5}, the second term in RHS of (\ref{eq:bound2}) can be bounded as follows,

\begin{align}
\bE & \left[ \norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 \vert \cF^t\right] \nonumber\\
&= \bE \left[ \norm{ \left(\bW_{D} - \bW\right) \bz_{t} + \left(\bI - \bW_D \right) \bx_t + \al \gr F(\bx_{t})}^2 \vert \cF^t\right] \nonumber\\
&\leq \norm{{\gr}h_{\al}(\bx_t)}^2 + \bE \left[ \norm{ \left(\bW_{D} - \bW\right)( \bz_{t} -\bx_t)}^2  \vert \cF^t\right]  \nonumber\\
&\leq L^2_{\al} \norm{\bx_{t} - \bx^*_{\al}}^2 + \eta^2 \norm{W-W_D}^2 \norm{\bx_{t}}^2 \nonumber\\
&= L^2_{\al} \norm{\bx_{t} - \bx^*_{\al}}^2 + \eta^2 \norm{W-W_D}^2 \norm{\bx_{t} - \bx^*_{\al} + \bx^*_{\al}}^2 \nonumber\\
& \leq \left( L^2_{\al} + 2 \eta^2 \norm{W - W_D} \right) \norm{\bx_{t} - \bx^*_{\al}}^2 \nonumber\\
& \quad + 2 \eta^2 \norm{W - W_D}^2 \norm{\bx^*_{\al}}^2. \label{eq:newg1}
\end{align}

Moreover, since the solution to Problem (\ref{eq:main}), i.e. $\norm{\widetilde{\bx}^*}$ (hence $\norm{{\bx}^*}$) is assumed to be bounded, the (unique) minimizer of $h_{\al}(\cdot)$, i.e. $\norm{{\bx}^*_{\al}}$ is also bounded as follows,

\begin{align}
\norm{\bx^*_{\al}}^2 &= \norm{\bx^*_{\al} - \bx^* + \bx^*}^2 \nonumber\\
& \leq 2\norm{\bx^*_{\al} - \bx^*}^2 + 2\norm{\bx^*}^2 \nonumber\\
&\leq 2 B_1(T) + \frac{4n(f_0 - f^*)}{\mu} \nonumber\\
&\leq 2 B_1(1) + \frac{4n(f_0 - f^*)}{\mu} \eqqcolon n \widetilde{B}^2. \label{eq:xstarb}
\end{align}

 Plugging (\ref{eq:newg1}) and (\ref{eq:xstarb}) into (\ref{eq:newbound2}) yields

 \begin{align}
 &\bE \left[\norm{\bx_{t+1} - \bx^*_{\al}}^2 | \cF^t \right] \nonumber\\
 &  \leq \left(1-2 \mu_{\al} \eps + \eps^2 \left(L^2_{\al} + + 2 \eta^2 \norm{W - W_D}^2 \right) \right)\norm{\bx_{t} - \bx^*_{\al}}^2 \nonumber\\
 & \quad + \eps^2 n \widetilde{B}^2 \norm{W-W_D}^2. \label{eq:newitr}
\end{align}

 Let us pick

\begin{align}
    \widetilde{T}_1 \coloneqq & \text{max} \Bigg\{ e^{e^{\frac{1}{1-2\delta}}},  \left\lceil \left( c_1 c_2 \mu \right)^{1/(2\delta)} \right\rceil , \nonumber\\
    & \left\lceil \left( \frac{c_1 ((2+c_2 L)^2 + 2 \eta^2 \norm{W-W_D}^2)}{c_2 \mu} \right)^{1/\delta} \right\rceil \Bigg\}.
\end{align}

For $ T \geq \widetilde{T}_1 $, we have

\begin{align}
    \eps &= \frac{c_1}{T^{3\delta/2}}\nonumber\\
    &\leq \frac{c_2 \mu }{(2+c_2 L)^2 + 2 \eta^2 \norm{W-W_D}^2} \cdot \frac{1}{T^{\delta/2}}\nonumber\\
    &\leq \frac{\mu_{\al}}{ \big(1-\lambda_n(W) + \al L \big)^2 + 2 \eta^2 \norm{W-W_D}^2 }\nonumber\\
    &= \frac{\mu_{\al}}{L^2_{\al}+ 2 \eta^2 \norm{W-W_D}^2},
\end{align}

which together with (\ref{eq:newitr}) yields

\begin{align}
    \bE \left[\norm{\bx_{t+1} - \bx^*_{\al}}^2 \right] &\leq (1- \mu_{\al} \eps ) \bE \left[\norm{\bx_{t+1} - \bx^*_{\al}}^2 \right] \nonumber\\
    & \quad + 2 \eps^2 n \widetilde{B}^2 \eta^2 \norm{W-W_D}^2.
\end{align}

Finally, from Lemma \ref{lemma3} with $a=c_1 c_2 \mu$ and $b=2c^2_1 {  n} \widetilde{B}^2 \eta^2 \norm{W-W_D}^2$, we have that

 \begin{align} \label{eq:boundTh2}
    \Expc \left[ \norm{\bx_T - \bx^*_{\al}}^2 \right]
    &\leq \frac{2 c_1 {  n}\widetilde{B}^2 \eta^2 \norm{W-W_D}^2}{\mu c_2} \frac{1}{T^{\delta}}  \nonumber\\
    & \quad +  \exp\left( -c_1 c_2 \mu  T^{\delta}  \right) \sqrt{n} \widetilde{B}.
\end{align}

Let $B_2(T)$ denote the bound in RHS of (\ref{eq:boundTh2}). Due to the exponential decay of the second term in $B_2(T)$, we have

 \begin{align}  \label{eq:bound2Th2}
    \Expc \left[ \norm{\bx_T - \bx^*_{\al}}^2 \right]
    \leq \mathcal{O} \left( \frac{2 c_1 {  n}\widetilde{B}^2 \eta^2 \norm{W-W_D}^2}{\mu c_2} \frac{1}{T^{\delta}} \right),
\end{align}

and

 \begin{align}
    B_2(T) \approx \frac{2 c_1 {  n}\widetilde{B}^2 \eta^2 \norm{W-W_D}^2}{\mu c_2} \frac{1}{T^{\delta}}.
\end{align}

Hence, by putting (\ref{eq:bound2Th2}) together with Lemma \ref{lemma2} we conclude the claim for any $T \geq \widetilde{T}_0 \coloneqq \text{max} \left\{ \widetilde{T}_1, T_2 \right\}$.

\end{appendices}


TITLE: What does it mean that the set of polynomials is dense in $C^0([a,b],R)$
QUESTION [1 upvotes]: What does it mean that the set of polynomials is dense in $C^0([a,b],R)$
$C^0( [a,b ], R )$ is the set of continuos functions.
As I understand it, for the set of polynomials (call this set $P $) to be dense in $C^0( [a,b ], R )$, we need to have that $\bar P =C^0( [a,b ], R )$.
But then what is the topology of $C^0( [a,b ], R ) $, so that each open set in $C^0( [a,b ], R )$ contains a point in $P $ (ie a polynomial).
Intutively I understand this as that a small perturbation of a function in $C^0( [a,b ], R ) $ makes it equal to a polynomial, but can this be formalized somewhat?
Thanks in advance!

REPLY [3 votes]: The space of continuous real-valued functions on $[a, b]$, denoted $C([a, b], \mathbb{R})$, is equipped with the supremum norm $$\|f\| = \sup\{|f(x)| \mid x \in [a, b]\}.$$ Note, as $f$ is continuous on a compact set, it attains its supremum so in particular, it is finite. This endows $C([a, b], \mathbb{R})$ with the topology of uniform convergence, i.e. $f_n \to f$ with respect to this norm if and only if $f_n \to f$ uniformly.
The correct statement is that the set of real polynomials on $[a, b]$ is dense in $C([a, b], \mathbb{R})$ with respect to the supremum norm. So given any $f \in C([a, b], \mathbb{R})$, there exists a sequence of polynomials $p_n$ with $p_n \to f$ uniformly.
This fact can be proved by using the Stone-Weierstrass Theorem.


TITLE: Munkres supplementary exercises chapter 3(nets) question 10
QUESTION [0 upvotes]: Prove the following.

X is compact if and only if every net in X has a convergent subnet.

I am stuck in proving the (<=) side.
https://dbfin.com/topology/munkres/chapter-3/supplementary-exercises-nets/problem-10-solution/ I did find a solution here, but I think it has an error. The set $K$ of all finite subsets of $J$ should have the empty set as an element in order to have a well-defined partial relation(because two finite subsets of $J$ can be disjoint, but there still should be an element of $K$ that is a subset of both). And in the last part, from $ \beta \subset \{k\}$ it is possible that $\beta $ is the empty set, so it is impossible to conclude that $U \cap B_k \neq 0$.

REPLY [0 votes]: Yes, if $\{A_i\mid i \in I\}$ is a family of closed sets with the FIP, let $I^\ast$ be the set of all non-empty finite subsets of $I$ under inclusion (so $I \le J \iff I \subseteq J$). This is a partial order and $I,J \in I^\ast$ have a common upperbound $I \cup J \in I^\ast$, so it's clearly a directed set.
The confusion probably comes from the fact that many natural nets are ordered by families of sets under reverse inclusion (like neighbourhood systems). So the tendency is to take reverse inclusion instead of the correct inclusion. Here larger subsets will bring us "closer" to the intersection so inclusion is also intuitively correct if you think about it.
The proof then writes itself (with AC): for each $I \in I^\ast$ pick (heavy use of AC) $x_I \in \bigcap_{i \in I} A_i$, using that the family has the FIP.
This defines a net $I^\ast \to X$ so this must have an accumulation point $p \in X$. The claim is that $p \in \bigcap_{i \in I} A_i$ which would finish the proof. To this end, fix $i \in I$ and let $U$ be any neighbourhood of $p$. Then $\{i\} \in I^\ast$ and so there is some $J \in I^\ast$ such that $\{i\} \le J$ (so $i \in   J$) and $x_J \in U$. In particular, $$x_J \in\bigcap_{j \in J} A_j \subseteq A_i \text{ so } A_i \cap U \neq \emptyset$$
As $U$ was arbitrary, $p \in \overline{A_i} = A_i$. As $i \in I$ was arbitrary we are done.
As an alternative to this proof, let $\mathcal{U}$ be an open cover of $X$  and assume it has no finite subcover (or we'd be done). Take as partial order $I$ all finite subsets of $\mathcal{U}$ again under inclusion. The union of any two finite subfamilies is again one, so directedness is again clear. As a net pick $x_I \in X\setminus \bigcup I$, exploiting the fact that there is no finite subcover. If $p$ is an accumulation point of this net, it is in some $U_p \in \mathcal{U}$ (we started with a cover) and so for some $J \ge \{U_p\}$ we have $x_J \in U_p$ which gives an immediate contradiction: $x_J \notin \bigcup J$ while $x_J \in U_p \in J$. So no such open cover without a finite subcover can exist in a space where every net has an accumulation point, which shows the implication.


TITLE: How prove this $\frac{dr_{1}}{dr_{2}}=\frac{\cos{\theta_{1}}}{\cos{\theta_{2}}}$
QUESTION [0 upvotes]: Question:
let two point $O_{1},O_{2}$, such
$$PO_{1}=r_{1},PO_{2}=r_{2}$$ There is a curve  $AB$
and the  point $P\in AB$,and EF is a tangent curve AB,and the tangent is $P$.
let
$$\angle CPE=\theta_{1},\angle DPE=\theta_{2}$$
show that
$$\dfrac{dr_{1}}{dr_{2}}=\dfrac{\cos{\theta_{1}}}{\cos{\theta_{2}}}$$
Thank you ,I fell this reslut is clearly,But I can't prove it.Thank you very much

REPLY [0 votes]: hint: draw a more careful diagram using a ruler, and introduce a point P' which is a distance $ds$ along the tangent $EF$.  use the cosine rule in triangles $O_1PP'$ and $O_2PP'$, then subtract the results to eliminate $r_1^2$, $r_2^2$ and $ds^2$. take the limit so $dr_1^2$ and $dr_2^2 \rightarrow 0$ and you've nearly done.


TITLE: Finite extension of fields with no primitive element
QUESTION [34 upvotes]: What is an example of a finite field extension which is not generated by a single element?
Background: A finite field extension E of F is generated by a primitive element if and only if there are a finite number of intermediate extensions. See, for example, [Lang's Algebra, chapter V, Theorem 4.6].

REPLY [2 votes]: If you're willing to work with commutative rings instead of just fields, you can gain some Galois-theoretic insight by base-changing to an algebraic closure $\bar{K}$ (or even a suitably large finite field extension).  Tensor product takes any primitive extension of your original field $K$ to a $\bar{K}$-algebra generated by a single element, so it suffices to find an extension that base changes to a $\bar{K}$-algebra generated by at least 2 elements.
If we take Alon Amit's minimal example $K = F(x,y), L = F(x^{1/p},y^{1/p})$, we can tensor it up to $\bar{K}[r,s]/(r^p-x,s^p-y)$.  By a suitable change of coordinates, we see that the spectrum of $\bar{K} \otimes_K L$ is a trivial torsor under $\alpha_p \times \alpha_p$ (and $\mu_p \times \mu_p$ and various other groups).  This description descends to $L$, but the torsor becomes nontrivial over $K$.  However, we do see that there is a 2-dimensional tangent space, and this gives us the derivations in KConrad's answer.  Furthermore, intermediate fields are fixed by subgroup schemes, and since we are in the the height one setting, these are cut out by the infinitely many $K$-rational slopes in the tangent space.
It's been almost 5 years since JBorger's comment to KConrad's answer, so I'm not sure if he's still interested.  Anyway, there is a Galois theory with group schemes that can be applied to purely inseparable extensions, worked out more or less in Chase, S.U.: Infinitesimal Group Scheme Actions on Finite Field Extensions Am. J. Math., Vol. 98, No.2, pp. 441-480 (1976).  Basically, you can corepresent the functor $A \mapsto \text{Aut}_A(L \otimes_K A)$ by a Hopf algebra over $K$, whose spectrum is called the Galois group scheme of $L/K$.  As far as I can tell, in our case, it is the Weil restriction of $\alpha_p \times \alpha_p$ (or $\mu_p \times \mu_p$, etc. - these are not canonical) along $L/K$, and the coordinate ring has dimension $(p^2)^{p^2}$.  I think there is a Galois correspondence involving subgroup schemes and descent data, but I haven't actually read the paper thanks to the paywall.


TITLE: Question about polynomial formula of degree $5$.
QUESTION [3 upvotes]: I understand there is a result that is proved using abstract algebra like Galois theory that there isn't a formula for degree $5$ or higher polynomials.
Does this just apply to polynomials whose coefficients are integers, real numbers, complex numbers or any field?

REPLY [1 votes]: This result (Abel's theorem) is valid for any field of characteristic $0$, and relies on the following result, proved by Galois:

A polynomial equation over a field of characteristic $0$ is solvable by radicals if and only if its Galois group is solvable.

Now with literal coefficients, the Galois group of a polynomial of degree $n$ is the symmetric group $S_n$, which is not solvable for $n\ge 5$. For details on what is a solvable group, you can see Wikipedia.
The situation is more complex in characteristic $p>0$, because if a root has order divisible to the characteristic, it gives rise to a so-called non-separable extension, i.e. it is not a simple root of its minimal polynomial, contrary to the case of characteristic $0$.


TITLE: What is the probability that the polynomial has real roots?
QUESTION [1 upvotes]: The variables $a$, $b$ and $c$ are iid random variables with exponential distribution with common parameter $1$. What is the probability that the polynomial $ax^2+bx+c$ has real roots?
My attempt:
$\Pr[ax^2+bx+c\;\text{has real roots}]=\Pr[b^2-4ac\geqslant0]=\Pr[b\geqslant2\sqrt{ac}\;\text{or}\;b\leqslant-2\sqrt{ac}]=\Pr[b\geqslant2\sqrt{ac}]=\int_0^\infty\int_0^\infty\int_{2\sqrt{ac}}^\infty f_{a,b,c}(a,b,c)dadbdc$
Am I right? How can I continue?

REPLY [5 votes]: \begin{align}
\mathsf P\left(a\gt \frac{b^2}{4c}\right)
&=\int_0^\infty\int_0^\infty\int_{\frac{b^2}{4c}}^\infty\exp(-a-b-c)\,\mathrm da\,\mathrm db\,\mathrm dc\\
&=\int_0^\infty\int_0^\infty\exp\left(-\frac{b^2}{4c}-b-c\right)\mathrm db\,\mathrm dc\\
&=\int_0^\infty\int_0^\infty c\exp\left(-\frac{s^2}4c-sc-c\right)\mathrm ds\,\mathrm dc\\
&=\int_0^\infty\int_0^\infty c\exp\left(-\left(\frac s2+1\right)^2c\right)\mathrm dc\,\mathrm ds\\
&=\int_0^\infty\left(\frac s2+1\right)^{-4}\,\mathrm ds\\
&=16\int_2^\infty s^{-4}\,\mathrm ds\\
&=\frac23
\end{align}
(where I used the substitution $b=sc$), so the desired probability is $\frac13$. As I wrote in a comment, I'm surprised that this has such a nice closed form, even more so that the probability is $\frac13$, which cries out for a solution with a transformation to three symmetric quantities of which one must be the greatest; I've posted a new question about this: Symmetric proof for the probability of real roots of a quadratic with exponentially distributed parameters.


TITLE: Parseval Theorem for Lp Norms
QUESTION [3 upvotes]: After doing much research online, it seems that Parseval's Theorem is only valid for $L_2$ norms. So for example, for a time-domain signal $f(t)$ and with it's frequency response $F(j\omega)$, then Parseval's theorem states the following $$\|f(t) \|_2 = \|F(j\omega) \|_2$$
However, is there a similar representation for the $L_1$ norm, or the $L_\infty$ norm? It seems that since $L_p$ for $p \neq 2$ are not Hilbert spaces, then the frequency-domain equivalent of such spaces do not exist. Is this true?
Thanks for your help!

REPLY [3 votes]: There is the Hausdorff-Young inequality: $$\|F\|_q \leq \|f\|_p$$ for $1 < p \leq 2$, $1/p + 1/q = 1$.
https://en.wikipedia.org/wiki/Hausdorff%E2%80%93Young_inequality


TITLE: Calculating Coherence Length and spectral width given an interferogram
QUESTION [1 upvotes]: I'm currently doing a lab in which we use a Michelson-Morley interferometer to analyse different light source. One of the mirrors in the interferometer is moved by a stepper motor. One of the light sources we use is a blue LED. Through a data collection programme, we build up an interferogram of the intensity of the light as it moves through the null point (with intensity on the y-axis and the amount of steps the motor has turned):

If we take a fast-fourier transform of this we will get a wavelength spectrum which looks like this:

We are then asked to calculate the coherence length and spectral width using the following formulae:
$\Delta \nu \times L =\tfrac{c}{2\pi}$ and
$\Delta \nu =\Delta \lambda \tfrac{c}{\lambda ^2}$
Not much context was given in the lab script for these formulae, but from what I could gather, I thought $\Delta \nu$ referred to the spectral width, $L$ referred to the coherence length (?), $\lambda$ referred to the mean/peak wavelength and $\Delta \lambda$ refers to the full width half maximum of the wavelength spectrum (?)
Again, I'm not sure if I have interpreted that correctly, but assuming I did, the values I got for the coherence length and spectral width were as follows:
$L=1.12*10^-6$ and $\Delta \nu = 4.26*10^{13}$
They seem to be on the correct order of magnitude, but the reason I am unsure is that when I look at different light sources (e.g. a white LED), the wavelength spectrum has more than one peak, so I'm not sure how I'm supposed to determine the "mean wavelength" and $\Delta \lambda$ from those.

REPLY [0 votes]: So, first, those seem to be in the right order. But I would mention that the $\Delta$'s are typically $1/e^{2}$ and not FWHM. Which answers then the question regarding broadband sources. You would in principle take the whole spectrum in the frequency domain and calculate its standard deviation to find the effective bandwidth of the source. The center of mass of the spectrum is its central frequency.


TITLE: The equivalence between the statements
QUESTION [2 upvotes]: Statement 1: Suppose for sake of contradiction that there is no non-negative rational number $x$ for which $x^2 < 2 < (x+ \epsilon)^2 $ .
Statement 2: This means that whenever $x$ is non-negative and $x^2 < 2$, we must also have $(x + \epsilon)^2 < 2$.
How does statement 2 logically follows from statement 1? I am not able to understand that statement 1 and statement 2 are same.
(Reference: http://www.math.ucla.edu/~tao/resource/general/131ah.1.03w/week2.pdf, proposition 7, page no. 9)

REPLY [0 votes]: Statement 1: Suppose for sake of contradiction that there is no non-negative rational number $x$  for which $x^2 <2<(x+ϵ)^2$
Statement 2: This means that whenever $x$  is non-negative and $x^2 <2$ , we must also have $(x+ϵ)^2 <2$ .
How does statement 2 logically follows from statement 1? I am not able to understand that statement 1 and statement 2 are same.

They are not (quite) the same, the implication includes the fact that $\sqrt 2$ is irrational, and that $\epsilon$ is rational.   By reason that if $x$ and $\epsilon$ are both rational, then their sum cannot equal a square root of $2$.
Statement 1 is: $\neg \exists x \Big(x\in\Bbb Q^+\cap\{0\} \wedge x^2< 2< (x+\epsilon)^2\Big)
\\ \Updownarrow \quad (\text{dual negation})
\\ \forall x \neg \Big(x\in\Bbb Q^+\cap\{0\} \wedge (x^2< 2) \wedge (2<(x+\epsilon)^2)\Big)
\\ \Updownarrow \quad (\text{DeMorgan's Law})
\\ \forall x \Big(x\notin\Bbb Q^+\cap\{0\} \vee \neg (x^2< 2) \vee \neg(2 < (x+\epsilon)^2)\Big)
\\ \Updownarrow\quad(\text{Implication Equivalence})
\\ \forall x \Big(\neg\big(x\notin\Bbb Q^+\cap\{0\} \vee \neg (x^2< 2)\big) \to \neg(2 < (x+\epsilon)^2)\Big)
\\ \Updownarrow\quad(\text{DeMorgan's Law})
\\ \forall x \Big(\big(x\in\Bbb Q^+\cap\{0\} \wedge (x^2< 2)\big) \to ((x+\epsilon)^2\leq 2)\Big)
\\ \Downarrow \quad (\epsilon\in\Bbb Q, \sqrt 2\notin\Bbb Q)
\\ \forall x \Big(\big(x\in\Bbb Q^+\cap\{0\} \wedge (x^2< 2)\big) \to ((x+\epsilon)^2 < 2)\Big)
$
Which is statement 2.


TITLE: Ask the expectation of sample variance in terms of $X_i$ and $X_j$
QUESTION [1 upvotes]: Let $X_1,..., X_n$ be a random sample. Then one version of the sample variance formula is
$$S^2 = \frac{1}{2n(n-1)} \Sigma_{i=1}^n \Sigma_{j=1}^n (X_i - X_j)^2$$
Then suppose $n = 4$ and $E(X_i)=0$, I know $S^2 = \frac{1}{24} \Sigma_{i=1}^n \Sigma_{j=1}^n (X_i - X_j)^2$
But one reference said $E(S^2) = 24 E(X_i)^2$
I do not see how to derive the above.

REPLY [1 votes]: If $i \not = j$ then $\mathbb E\left[(X_i-X_j)^2\right] = 2 \sigma^2$ so $E\left[S^2\right] = \mathbb E\left[\frac{1}{2n(n-1)} \sum\limits_{i=1}^n \sum\limits_{j=1}^n (X_i - X_j)^2\right] = \sigma^2$, which is why this is a suggested measure of the sample variance.
$\mathbb E\left[X_i^2\right] = \sigma^2 + \left(E\left[X_i\right]\right)^2$, so if $E\left[X_i\right] =  0$ then you would have $\mathbb E\left[X_i^2\right] =\mathbb E\left[\frac1n \sum\limits_{i=1}^n X_i^2\right]= \sigma^2= \mathbb E\left[S^2\right]$.
But $\frac1n \sum\limits_{i=1}^n X_i^2$ is not the sample variance: it is a measure of the second moment about $0$ rather than the second moment about the sample mean.


TITLE: limit epsilon-delta definition vs. continuity
QUESTION [1 upvotes]: Based on the following problem from this source:
$f(x) = \begin{cases}x^2 &, \text{ if } x \text{ rational} \\ x &, \text{ if } x \text{ irrational}\end{cases}$
has $\lim_{x\to 1} f(x) = 1$
and on this math.stackexchange answer, I suspect that limit does not require a "continuous" domain.
But, why the common $\epsilon$-$\delta$ definition of a limit $\lim_{x\to a}f(x) = L$ ($a$ is neither $-\infty$ nor $\infty$) never emphasizes that point? For example, my textbook simply says $x$ without explaining any property about $x$, and therefore, I was wrongfully led to believe that $x$ must come from a "continuous" domain.
I see that Wikipedia's article on precise definition of limit explicitly states that $x \in D \subseteq \mathbb{R}$. But, I think it may also wrongfully lead people to believe that limit $\lim_{x\to a}f(x) = L$ also works when the domain is so discontinuous like the set $\mathbb{Z}$ of integers and $a$ is neither $-\infty$ nor $\infty$.
Now I am wondering: what is the precise definition of limit $\lim_{x\to a}f(x) = L$ ($a$ is neither $-\infty$ nor $\infty$) especially when it comes to being precise about the $x$?

REPLY [0 votes]: When we define limit we consider $a$ to be a cluster point of the domain.By a cluster point we mean the following:
If $a$ is a cluster point of $A$ then $(a-\delta,a+\delta)\cap A\setminus \{a\}\neq\phi$
So the exact definition of a limit is
Let $\epsilon >0$ be arbitrary.Then $ f$ has $L $ has limit as $x \rightarrow a$ if corresponding to $\epsilon >0 \exists \delta >0 $ such that whenever $x\in  (a-\delta,a+\delta)\cap A\setminus \{a\}, |f(x)-L|<\epsilon$ .


text:
\section{Integral of Integrable Function is Homogeneous}
Tags: Measure Theory

\begin{theorem}
Let $\struct {X, \Sigma, \mu}$ be a [[Definition:Measure Space|measure space]].
Let $f: X \to \overline \R$ be a [[Definition:Integrable Function on Measure Space|$\mu$-integrable function]].
Let $\lambda \in \R$.
Then:
:$\displaystyle \int \lambda f \rd \mu = \lambda \int f \rd \mu$
where $\lambda f$ is the [[Definition:Pointwise Scalar Multiplication|pointwise $\lambda$-multiple]] of $f$.
\end{theorem}

config: wiki


text:
\begin{document}
\title{A New Theoretical Evaluation Framework for \\Satisfaction Equilibria in Wireless Networks}
\author{\IEEEauthorblockN{Michail Fasoulakis\IEEEauthorrefmark{1},
Eirini Eleni Tsiropoulou\IEEEauthorrefmark{2},
Symeon Papavassiliou\IEEEauthorrefmark{1}}\\
 \{mfasoul@netmode.ntua.gr, eirini@unm.edu, papavass@mail.ntua.gr\} \\
\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering,\\ National Technical University of Athens (NTUA), Greece}\\
\IEEEauthorblockA{\IEEEauthorrefmark{2}Department of Electrical and Computer Engineering,\\
 University of New Mexico, USA}}
\maketitle

\begin{abstract}
In this paper, a theoretical evaluation framework regarding the \textit{Satisfaction Equilibrium (SE)} in wireless communication networks is introduced and examined. To study these equilibria operation points, we coin some new concepts, namely the \textit{Valued Satisfaction Equilibrium}, the \textit{Price of Efficiency} and the \textit{Max Price of Satisfaction}, which can be used for measuring the efficiency of the obtained equilibria solutions. The aforementioned framework is analyzed and evaluated in a wireless communication environment under the presence of the Gaussian Interference channel (GIC). Within this setting, a non-cooperative game among the users is studied, where users aim in a selfish manner to meet their Quality of Service (QoS) prerequisite. However instead of maximizing the QoS which is generally energy costly, we evangelize that better energy-efficiency is achieved by targeting satisfactory QoS levels only. The sufficient and necessary conditions that lead to the \textit{Satisfaction Equilibrium} are provided for the two-user case and the \textit{Efficient Satisfaction Equilibrium (ESE)} is determined, where the users satisfy their QoS constraints with the lowest possible cost. Moreover, specific measures for evaluating the efficiency of various satisfaction equilibria, in a formal and quantitative manner, expressing the tradeoff with respect to the achieved utility or a given objective function and corresponding cost, are defined and analyzed.
\end{abstract}

\begin{IEEEkeywords}
Game Theory, QoS Satisfaction, Satisfaction Equilibrium, Price of Efficiency.
\end{IEEEkeywords}

\section{Introduction}
Current and future wireless networks face new and interesting challenges in the increasingly changing communications environment. The volume of the transmitted data traffic and the number of users are continuously increasing. Typically, these systems present competitive environments that induce constraints, and users evolve with others, where their decisions and actions are interdependent.

In such a competitive and distributed environment, \textit{Game Theory} arises as a natural choice and a powerful theoretical tool to cope with the corresponding resource allocation problems, while reflecting and modeling the different interactions among the users \cite{lasaulce2011game}. Respecting the need for distributed and scalable solutions and algorithms, the focus has been placed on the study of non-cooperative game theory paradigm where decisions are taken autonomously by the end users \cite{elhammouti2017self}.

The majority of existing approaches have relied on the principles of Expected Utility Maximization, where users aim at selfishly maximizing their own degree of satisfaction upon receiving a service, as expressed through various forms of utility functions, resulting to some equilibrium \cite{tsiropoulou2017supermodular}. However, firstly a major disadvantage that is common to most of these equilibrium concepts (e.g., Nash equilibrium) is that stability depends on whether or not each user achieves the highest performance possible. This does not necessarily properly reflect in reality the most desirable solution, neither from a single user point of view nor from a network point of view, as a user may require only to ensure a specific minimum QoS condition \cite{southwell2014quality}. To overcome this constraint and problem, in this work a new solution concept known as Satisfaction Equilibrium (SE) \cite{ross2006satisfaction} is adopted and exploited in the realm of wireless communications environments. The main purpose of this paper is to introduce a holistic theoretical analysis and evaluation framework for studying these equilibria in wireless communication networks, with respect to conditions of existence and their efficiency. Its application in the presence of \textit{Gaussian Interference channel (GIC)} is specifically analyzed and examined.

\subsection{Related work and our contribution}
Most of the efforts so far in the wireless communications research community were concentrated on the total QoS maximization, which however resulted in unjustified network resources drainage or unfair resources allocation among the users \cite{tsiropoulou2016uplink}. Instead, in our work to overcome these deficiencies, we adopt the philosophy of aiming satisfactory QoS \cite{ross2006satisfaction,meriaux2012achievability,perlaza2012quality} rather than targeting optimality in terms of QoS maximization \cite{katsinis2017joint}. There are two key motivating factors behind this consideration. The first one refers to meeting user expectations. Several types of services are either simply interested in achieving a minimum QoS level, or corresponding users are insensitive to small QoS changes \cite{ross2006satisfaction}. Furthermore, users may not be willing to consume additional resources or pay higher price for a better QoS level, which in turn translates to an increase in network capacity in terms of satisfied users \cite{meriaux2012achievability}. The second factor behind the choice of satisfactory solutions stems from the need of energy consumption reduction \cite{perlaza2012quality, goonewardena2017generalized}. QoS maximization typically requires unnecessarily high energies \cite{tsiropoulou2017supermodular}, whereas achieving an efficient and feasible network operation point that meets users’ expectations can result in substantial energy savings, a critical factor in several resource-constrained environments.

This objective in this paper is treated via a novel mathematical concept within the framework of game theory, referred to as satisfaction equilibrium (SE) \cite{perlaza2012quality}. For studying these equilibria, we introduce and coin some new concepts, namely the \textit{Valued Satisfaction equilibrium}, the \textit{Price of Efficiency} and the \textit{Max Price of Satisfaction}, that can be used for benchmarking purposes of the achievable solutions. The applicability of the aforementioned framework and concepts are demonstrated considering a wireless communication environment characterized by Gaussian Interference channel, where the users have limited transmission power \cite{fasoulakis2017gaussian}. Towards this direction, we formulated the \textit{Gaussian Interference channel} as a non-cooperative game among the users, where each user has a minimum QoS prerequisite, represented as a minimum achievable data rate. Specific necessary and sufficient conditions that lead to the SE for the two-user case are obtained. The satisfaction equilibrium point is achieved when all the users of the network (i.e., players in the game) satisfy their minimum QoS requirements irrespective of the utility value they achieve. Relaxing the maximization assumptions essentially we enlarge the potential set of feasible strategies since instead of restricting ourselves to solutions that permit global optimum, we follow a less restrictive approach and extend the solution space to a broader set. Subsequently the main objective becomes - in contrast to reaching other forms of equilibria such as Nash equilibrium (NE) - to reach a network state in which all end users satisfy their individual QoS by investing the minimum effort, referred to as Efficient Satisfaction Equilibrium (ESE) \cite{meriaux2012achievability}.

\subsection{Outline}

The remaining of this work is organized as follows. In Section \ref{sec:Game Theory}, the fundamental concepts from the field of Game Theory are initially presented. Therefore, concepts such as satisfaction equilibrium and efficient satisfaction equilibrium are reviewed, while the new concepts and terms of valued satisfaction equilibrium, price of efficiency, and max price of satisfaction are defined. In Section \ref{sec:Model}, the baseline proposed Gaussian Interference Channel model is introduced, as well as the users' adopted utility function and accordingly the corresponding game theoretic formulation of satisfying users' QoS prerequisites is presented. Section \ref{sec:Existence} discusses the conditions that lead to the satisfaction equilibrium for the two-user case, while in Section \ref{sec:PoE} the price of efficiency and max price of satisfaction for evaluating the efficiency of the various SEs in a formal and quantitative manner, are analyzed. Finally Section \ref{sec:Conclusions} concludes this article.

\section{Game theory definitions} \label{sec:Game Theory}
We consider formally a game in satisfaction form as a tetrad
\[G = \Big(N, \{A_i\}_{i \in N}, \{u_i\}_{i\in N}, \{f_i\}_{i\in N}\Big),\]
where $N$ is the set of the players with size $|N|$, $A_i$ is the set of all possible pure strategies (actions) of the player $i$, $u_i$ is the utility function of the player $i$ and $f_i$ is the set of all satisfied actions under a constraint of the player $i$ given the actions of all other players.
A strategy profile is an $|N|$-tuple $\mathbf{a}=(a_1,a_2, \dots, a_{|N|}) \in A_1\times A_2\times \dots \times A_{|N|}$ of the strategies of the players. Also, $\mathbf{a_{-i}}$ is the strategy profile of all players except for the player $i$.
We have the following definitions.

\begin{definition}[Nash equilibrium \cite{nash1951non}]
A Nash equilibrium is a strategy profile $\mathbf{a^*} = (a_i^*, \mathbf{a_{-i}^*})$ such that, for any $i$ and any strategy $a_i \in A_i$,
\[u_i(a_i^*,\mathbf{a_{-i}^*}) \geq u_i(a_i,\mathbf{a_{-i}^*}).\]
\end{definition}

\begin{definition}[Generalized Nash equilibrium \cite{debreu1952social}]
A Generalized Nash equilibrium is a strategy profile $\mathbf{a^*} = (a_i^*, \mathbf{a_{-i}^*})$ such that, for any $i$,
\[a_i^* \in f_i(\mathbf{a_{-i}^*}), \text{ and}\]
\[u_i(a_i^*,\mathbf{a_{-i}^*}) \geq u_i(a_i,\mathbf{a_{-i}^*}),\]
for any $a_i \in f_i(\mathbf{a_{-i}^*})$.
\end{definition}

\begin{definition}[Satisfaction equilibrium \cite{perlaza2012quality}]
A satisfaction equilibrium is a strategy profile $\mathbf{a^*} = (a_i^*, \mathbf{a_{-i}^*})$ such that, for any $i$,
\[a_i^* \in f_i(\mathbf{a_{-i}^*}).\]
\end{definition}

\begin{definition}[Efficient satisfaction equilibrium \cite{perlaza2012quality}]
An efficient satisfaction equilibrium is a strategy profile $\mathbf{a^*} = (a_i^*, \mathbf{a_{-i}^*})$ such that, for any $i$,
\[a_i^* \in f_i(\mathbf{a_{-i}^*}), \text{ and }c_i(\mathbf{a^*}) \leq c_i(\mathbf{a}),\]
for any $\mathbf{a} = (a_i, \mathbf{a_{-i}^*})$ with $a_i \in f_i(\mathbf{a_{-i}^*})$, where $c_i: A_1 \times A_2 \times \dots A_{|N|} \mapsto \R_{+}$ is a cost function.
\end{definition}

In the following we first introduce the \textit{Valued Satisfaction equilibrium}, which essentially corresponds to efficient satisfaction equilibria, with a new cost function ${c_i}/{u_i}$ measuring the tradeoff between the achieved utility $u_i$ and the corresponding initial cost $c_i$. Specifically:

\begin{definition}[Valued satisfaction equilibrium]
A valued satisfaction equilibrium is a strategy profile $\mathbf{a^*} = (a_i^*,\mathbf{a_{-i}^*})$ such that, for any $i$,
\[a_i^* \in f_i(\mathbf{a_{-i}^*}), \text{ and}\]
\[\frac{c_i(\mathbf{a^*})}{u_i(\mathbf{a^*})} \leq \frac{c_i(\mathbf{a})}{u_i(\mathbf{a})},\]
for any for any $\mathbf{a} = (a_i, \mathbf{a_{-i}^*})$ with $a_i \in f_i(\mathbf{a_{-i}^*})$, where $c_i$ is the cost function and $u_i$ the utility function, assuming that $c_i(a)>0$ and $u_i(a)>0$ for any $a \in A_1 \times A_2 \times \dots A_{|N|}$.
\end{definition}

Below, we also introduce a new concept, referred to as Price of Efficiency, to measure the efficiency of the efficient satisfaction equilibria. Intuitively, this concept aims to evaluate in a formal and quantitative manner, the efficient satisfaction equilibria solution, in terms of tradeoff between the achieved utility and cost, when compared to the valued satisfaction equilibrium operation point.

\begin{definition}[Price of Efficiency]
Let $\mathbf{a^*}$ be a strategy profile such that it is the best valued satisfaction equilibrium (under the summation function). Furthermore, let $\mathbf{a}$ be a strategy profile such that $\mathbf{a}$ is the worst efficient satisfaction equilibrium (under the summation function). Then, the Price of Efficiency (PoE) is
\[PoE = \frac{\sum\limits_{\forall i}\frac{c_i(\mathbf{a})}{u_i(\mathbf{a})}}{\sum\limits_{\forall i}\frac{c_i(\mathbf{a^*})}{u_i(\mathbf{a^*})}},\]
assuming that $c_i(a)>0$ and $u_i(a)>0$ for any $a \in A_1\times A_2\times \dots \times A_{|N|}$.
\end{definition}

Last but not least, we also define a measure indicating the maximum price (i.e., distance) characterizing the achievable satisfaction equilibria, under the consideration of an objective function $g$. Formally:
\begin{definition}[Max Price of Satisfaction]
Let $\mathbf{a^*}$ be a strategy profile such that it is a satisfaction equilibrium and it is an optimal of an objective function $g$, i.e., $g$ is the sum of the utilities (utilitarian optimum). Furthermore, let $\mathbf{a}$ be a strategy profile such that $\mathbf{a}$ is the worst satisfaction equilibrium under the objective function $g$. Then, the Max Price of Satisfaction (MPoSa) is
\[ MPoSa = \frac{g(\mathbf{a^*})}{g(\mathbf{a})},\]
assuming that $g(a)>0$ for any $a \in A_1\times A_2\times \dots \times A_{|N|}$.
\end{definition}
Since, $g(\mathbf{a^*}) \geq g(\mathbf{a})$, we have that the MPoSA is no less than one.
\section{The Model} \label{sec:Model}
We consider $|N|$ pairs of transmitter-receiver in the Gaussian Interference Channel. Any transmitter $i\in\{1,2,\dots,|N|\}$ uses the same frequency to transmit her message to her receiver $i$ and simultaneously interferes the receivers of the other transmitters. Any receiver $i$ treats the signal of a transmitter $j$ different than $i$ as interference. We can see this competitive situation as a non-cooperative game \cite{osborne1994course}. Any transmitter wants to maximize her rate.
The set of the pure strategies of any transmitter $i$ is the power $p_i \in [0, P_{\max}]$ that chooses to transmit her message, where $P_{\max}$ is the maximum possible power, imposed by physical constraints and equipment characteristics. The utility function of any transmitter $i$ is

\begin{equation}
\label{utility function}
u_i(p_i,\mathbf{p_{-i}}) = \frac{1}{2}\log\Bigg(1+\frac{{h_{ii}p_i}}{{\sum\limits_{\substack{j=1 \\ j\neq i}}^{|N|}h_{ji}p_j+ I}}\Bigg),
\end{equation}
where $h_{ji}>0$ is the channel attenuation between the transmitter $j$ and the receiver $i$, $\mathbf{p_{-i}}$ is the vector of the powers of the transmitters except for the transmitter $i$ and $I>0$ is the \emph{Additive White Gaussian Noise (AWGN)} of the channel. This can be written as
\begin{equation}
\label{utility function2}
u_i(p_i,\mathbf{p_{-i}}) = \frac{1}{2}\log\Bigg(1+\frac{{p_i}}{{\sum\limits_{\substack{j=1 \\ j\neq i}}^{|N|}a_{ji}p_j+ I_i}}\Bigg),
\end{equation}
where $a_{ji} = h_{ji}/h_{ii}>0$ is the new channel attenuation between the transmitter $j$ and the receiver $i$ and $I_i = I/h_{ii}$. We give the following definitions in the context of the Gaussian Interference channel.

\begin{definition}[Nash equilibrium]
A strategy profile $(p_i^*, \mathbf{p_{-i}^*})$ is a Nash equilibrium such that, for any $i$ and for any $p_i$,
\[u_i(p_i^*,\mathbf{p_{-i}^*}) \geq u_i(p_i,\mathbf{p_{-i}^*}),\]
in other words $p_i^*$ is a best-response strategy to the strategies $\mathbf{p_{-i}^*}$ of the other transmitters.
\end{definition}

\begin{definition}[Generalized Nash equilibrium]
A strategy profile $(p_i^*, \mathbf{p_{-i}^*})$ is a generalized Nash equilibrium such that, for any $i$ and for any $p_i$ such that $u_i(p_i,\mathbf{p_{-i}^*}) \geq \Gamma_i$, we have
\[u_i(p_i^*,\mathbf{p_{-i}^*}) \geq u_i(p_i,\mathbf{p_{-i}^*}),\]
where $\Gamma_i$ is a positive constant representing user's $i$ QoS prerequisites in terms of achievable transmission data rate.
\end{definition}

\begin{definition}[Satisfaction equilibrium]
A strategy profile $(p_i^*, \mathbf{p_{-i}^*})$ is a satisfaction equilibrium such that, for any $i$,
\[u_i(p_i^*,\mathbf{p_{-i}^*}) \geq \Gamma_i,\]
in other words $p_i^*$ is a satisfaction strategy to the strategies $\mathbf{p_{-i}^*}$ of the other transmitters, $\Gamma_i$ is the satisfaction threshold (positive constant) of the transmitter $i$.
\end{definition}

\begin{definition}[Efficient satisfaction equilibrium]
A strategy profile $(p_i^*, \mathbf{p_{-i}^*})$ is an efficient satisfaction equilibrium, if it is a satisfaction equilibrium and, for any $i$ and any $p_i$ such that $u_i(p_i,\mathbf{p_{-i}^*}) \geq \Gamma_i$, we have
\[p_i^* \leq p_i,\]
or in other words the transmitter $i$ uses the less power to be satisfied.
\end{definition}

\begin{definition}[Valued satisfaction equilibrium]
A strategy profile $(p_i^*, \mathbf{p_{-i}^*})$ is a valued satisfaction equilibrium, if it is a satisfaction equilibrium and, for any $i$ and any $p_i$ such that $u_i(p_i,\mathbf{p_{-i}^*}) \geq \Gamma_i$, we have
\[\frac{p_i^*}{u_i(p_i^*,\mathbf{p_{-i}^*})} \leq \frac{p_i}{u_i(p_i,\mathbf{p_{-i}^*})}.\]

\end{definition}

\section{Existence of SE} \label{sec:Existence}

The satisfaction equilibria of the Gaussian Interference channel have been studied previously in \cite{meriaux2012achievability,perlaza2012quality} but no conditions of existence have been given. In this paper we will investigate the conditions of existence of satisfaction equilibria in this scenario.
By the utility function of the player $i$ we have
\begin{align}
\label{area of SE}
u_i(p_i,\mathbf{p_{-i}}) =  \frac{1}{2}\log\Bigg(1+\frac{{p_i}}{{\sum\limits_{\substack{j=1 \\ j\neq i}}^{|N|}a_{ji}p_j+ I_i}}\Bigg) \geq \Gamma_i \\
\Leftrightarrow p_{i} \geq (4^{\Gamma_i}-1)\Big(\sum\limits_{\substack{j=1 \\ j\neq i}}^{|N|}a_{ji}p_j+I_i\Big).
\end{align}
These are the inequalities that characterize the region of the SE. We can write up the inequalities (\ref{area of SE}) as a linear system
\begin{align}
\label{linear system}
\pmb{A}\cdot \pmb{p} \geq \pmb{b},
\end{align}
where \\
\begin{multline*}
\pmb{A} = \begin{pmatrix} 1 && a_{21}(1-4^{\Gamma_1}) && \dots && a_{|N|1}(1-4^{\Gamma_1}) \\ a_{12}(1-4^{\Gamma_2}) && 1  && \dots && a_{|N|2}(1-4^{\Gamma_2}) \\ &&  && \dots && && \\ a_{1|N|}(1-4^{\Gamma_{|N|}}) && a_{2|N|}(1-4^{\Gamma_{|N|}}) && \dots &&  1 \end{pmatrix},\\\\
\pmb{p} = \begin{pmatrix} p_1 \\ p_2 \\ \dots \\ p_{|N|} \end{pmatrix}, \text{ and }
\pmb{b} = \begin{pmatrix} (4^{\Gamma_1}-1)I_1 \\ (4^{\Gamma_2}-1)I_2 \\ \dots \\ (4^{\Gamma_{|N|}}-1)I_{|N|}
\end{pmatrix}.
\end{multline*}
There is at least one SE if there is at least one feasible solution in the system $\pmb{A}\cdot \pmb{p} \geq \pmb{b}$ .

\subsection{Two-player game}
We study the conditions of existence of the SE in the case of the two players and we conclude to the following Theorems.
\begin{theorem}
The satisfaction equilibrium region of the two-player game is the region such that $p_1 \geq (4^{\Gamma_1}-1)(a_{21}p_2+I_1)$ and $p_2 \geq (4^{\Gamma_2}-1)(a_{12}p_1+I_2)$.
\end{theorem}
\begin{proof}
By the utility function of the player 1 we have
\begin{multline*}
u_1(p_1,p_2) = \frac{1}{2}\log\Big(1+\frac{p_1}{a_{21}p_2+I_1}\Big)\geq \Gamma_1\\ \Leftrightarrow p_1 \geq (4^{\Gamma_1}-1)(a_{21}p_2+I_1).
\end{multline*}
Similarly, for the player 2 we have
\begin{multline*}
u_2(p_2,p_1) = \frac{1}{2}\log\Big(1+\frac{p_2}{a_{12}p_1+I_2}\Big)\geq \Gamma_2\\ \Leftrightarrow p_2 \geq (4^{\Gamma_2}-1)(a_{12}p_1+I_2).
\end{multline*}
Since, $\Gamma_1$ and $\Gamma_2$ are positive is clear that $(4^{\Gamma_1}-1)(a_{21}p_2+I_1) > 0$ and $(4^{\Gamma_2}-1)(a_{12}p_1+I_2) > 0$.
\end{proof}

\begin{theorem}
\label{intersection}
There is at least one satisfaction equilibrium if and only if the lines \begin{equation} \label{line 1} p_2 = {p_1}/({(4^{\Gamma_1}-1)a_{21}})-{I_1}/{a_{21}}\end{equation} and \begin{equation}\label{line 2} p_2 = (4^{\Gamma_2}-1)(a_{12}p_1+I_2) \end{equation} cross in the first quadrant, or in other words $a_{21}a_{12} < \frac{1}{(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)}$.
\end{theorem}
\begin{proof}
Graphically, there is at least one feasible solution in the area described by $p_1 \geq (4^{\Gamma_1}-1)(a_{21}p_2+I_1)$ and $p_2 \geq (4^{\Gamma_2}-1)(a_{12}p_1+I_2)$ if and only if the two lines $p_2 = \frac{p_1}{(4^{\Gamma_1}-1)a_{21}}-\frac{I_1}{a_{21}}$ and $p_2 = (4^{\Gamma_2}-1)(a_{12}p_1+I_2)$ cross each other in the first quadrant. In order the two lines to cross each other in the first quadrant the slope of the first one must be greater than the slope of the second one. Thus, $\frac{1}{(4^{\Gamma_1}-1)a_{21}} > (4^{\Gamma_2}-1)a_{12}$.
\end{proof}
\begin{figure}
\centering
\captionsetup{justification=centering}
\subfigure{
\begin{tikzpicture}[scale = 1.5]
\draw [<->,thick] (0,2) node (yaxis) [above] {$p_2$}
     |- (2.7,0) node (xaxis) [right] {$p_1$};
\draw (0.5,0) coordinate (a_1) -- (2,1.7) coordinate (a_2);
\draw (0.5,0) node [below] {$(4^{\Gamma_1}-1)I_1$};
\draw (0,0.5) coordinate (b_1) -- (2.5,1) coordinate (b_2);
\draw (0,0.5) node [left] {$(4^{\Gamma_2}-1)I_2$};
\coordinate (c) at (intersection of a_1--a_2 and b_1--b_2);
\draw (c) node [above left] {ESE};
\fill[red] (c) circle (1pt);
\draw (1.3,0.9) -- (1.3,0.76);
\draw (1.4,1.02) -- (1.4,0.78);
\draw (1.5,1.13) -- (1.5,0.8);
\draw (1.6,1.24) -- (1.6,0.82);
\draw (1.7,1.36) -- (1.7,0.84);
\draw (1.8,1.47) -- (1.8,0.86);
\draw (1.6,1.2) node [above left] {$(\ref{line 1})$};
\draw (2,0.4) node [above left] {$(\ref{line 2})$};
\end{tikzpicture}
}
\caption{The area of the satisfaction equilibria}
\end{figure}

\begin{theorem}
The efficient satisfaction equilibrium exists if and only if $a_{21}a_{12} < \frac{1}{(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)}$ and is equal to $\Big(\frac{(4^{\Gamma_1}-1)(a_{21}(4^{\Gamma_2}-1)I_2+I_1)}{1-(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)a_{21}a_{12}},\frac{(4^{\Gamma_2}-1)(a_{12}(4^{\Gamma_1}-1)I_1+I_2)}{1-(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)a_{21}a_{12}}\Big)$.
\end{theorem}
\begin{proof}
For fixed strategy of the one player, the other player tries to be satisfied with the minimum power in the satisfaction equilibrium region. So, it is easy to see that the efficient satisfaction equilibrium must be on all boundaries of the satisfaction region. This is the cross point of the lines (\ref{line 1}) and (\ref{line 2}).
The cross point is the solution of the system
\begin{align*}
p_1 = (4^{\Gamma_1}-1)(a_{21}p_2+I_1),\\
p_2 = (4^{\Gamma_2}-1)(a_{12}p_1+I_2),
\end{align*}
which has solution the pair $\Big(\frac{(4^{\Gamma_1}-1)(a_{21}(4^{\Gamma_2}-1)I_2+I_1)}{1-(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)a_{21}a_{12}},\frac{(4^{\Gamma_2}-1)(a_{12}(4^{\Gamma_1}-1)I_1+I_2)}{1-(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)a_{21}a_{12}}\Big)$.
We want this solution to be non negative. Since the nominators are non negative the denominators must be positive, so $1-(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)a_{21}a_{12}>0$. But this holds since $a_{21}a_{12} < \frac{1}{(4^{\Gamma_1}-1)(4^{\Gamma_2}-1)}$.
\end{proof}
By this theorem we conclude to the following lemma.
\begin{lemma}
The efficient satisfaction equilibrium is unique.
\end{lemma}

We now search for the valued satisfaction equilibria of the game and we conclude to the following theorem.
\begin{theorem}
\label{Valued SE}
The valued satisfaction equilibrium coincides with the efficient satisfaction equilibrium.
\end{theorem}
\begin{proof}
We do the analysis from the player 1 point of view, the analysis for the other player is symmetric.
Fix a strategy $p_2^*$ of the player 2. Then, we search for the strategy of the player 1 that minimizes the $\frac{p_1}{\frac{1}{2}\log(1+\frac{p_1}{a_{21}p_2^*+I_1})}$. The derivative of this is
\begin{multline*}
\frac{\frac{1}{2}\log(1+\frac{p_1}{a_{21}p_2^*+I_1}) - \frac{\frac{1}{2}p_1}{p_1+a_{21}p_2^*+I_1}}{\frac{1}{4}(\log(1+\frac{p_1}{a_{21}p_2^*+I_1}))^2}\\
= \frac{\frac{1}{2}\log(1+\frac{p_1}{a_{21}p_2^*+I_1}) - \frac{1/2}{1+\frac{a_{21}p_2^*+I_1}{p_1}}}{\frac{1}{4}(\log(1+\frac{p_1}{a_{21}p_2^*+I_1}))^2},
\end{multline*}
which is positive for $p_1>0$, so in this interval the function is increasing. Thus, the best strategy for the player 1 is the minimum in the satisfaction equilibrium area. This means similarly to the ESE that the valued satisfaction equilibrium is on all boundaries of the satisfaction equilibrium area, so on the cross point.
\end{proof}

\section{The Price of Efficiency and the Max Price of Satisfaction} \label{sec:PoE}
We study the Price of Efficiency in the Gaussian Interference channel as a measurement of the efficiency of the efficient satisfaction equilibrium in terms of the tradeoff between the achieved rate and the power cost to achieve this rate. We conclude to the following theorem.

\begin{theorem}
The Price of Efficiency in the Gaussian Interference channel is equal to 1.
\end{theorem}
\begin{proof}
Since, the efficient satisfaction equilibrium coincides with the valued satisfaction equilibrium it is easy to see that the PoE is equal to 1.
\end{proof}

We now study the maximum price of satisfaction taking as an objective function a function that minimizes the sum of the powers, or in other words maximizes the ratio one over the sum of the powers. It is easy to see that the efficient satisfaction equilibrium is the optimum solution of this objective function in the area of the satisfaction equilibria. On the other hand assuming that the $(P_{\max},P_{\max})$ is in the satisfaction equilibrium area, this is the worst case of this objective function. Thus, it is easy to see that the maximum price of satisfaction is equal to the ratio $\frac{2P_{\max}}{\sum\limits_{\forall i} P_i}$, where $P_i$ is the power of the player $i$ in the ESE.

\section{Concluding Remarks} \label{sec:Conclusions}
In this paper, we argued that by rethinking the overall traditional QoS provisioning and user experience perception in wireless networks that targeted QoS maximization, we can devise energy-efficient, scalable, and rewarding solutions from both practical and theoretical viewpoints, through the adoption of the general concept of satisfaction equilibrium. Therefore, a novel holistic framework was introduced towards studying different efficient and feasible wireless network operation points (i.e., different game theoretic satisfaction equilibria points) that meet users’ expectations, while resulting in substantial cost or energy savings, which are critical factors especially in resource-constrained environments. This new framework was in particular analyzed in a wireless communication environment under the presence of the Gaussian Interference channel, while the efficiency of the various satisfaction equilibria was evaluated in a formal and quantitative manner. The current analysis can be extended via considering multi-service wireless communication environments, where the users' utilities are differentiated based on their requested services, i.e., real-time and non-real time services \cite{tsiropoulou2013efficient}. In this case, the study of Price of Efficiency is interesting and challenging, as the problem becomes more complicated indicating that the PoE may not be equal to $1$.

It should be noted that the realization of new decision-making paradigms addressing the requirements of flexibility, adaptability, and autonomicity in future wireless networks, depends on bridging the gap between the considered game theoretic methodologies described above, and practical wireless applications and settings. The efficient computation of the satisfaction equilibria is hard in practice even for games which satisfy the necessary conditions of existence and convergence to them in theory, due to the inherent difficulties that wireless networks face in practice. Part of our current and future research work, includes the use of learning approaches in game theory, in order to deal with the technical and implementation challenges stemming from the incompleteness of available information regarding the game structure and uncertainty on the observations of the users and their actions in the game that in turn may influence decision making and equilibrium identification and convergence.

\section*{Acknowledgment}
\noindent
The research of Dr. Michail Fasoulakis and Dr. Symeon Papavassiliou was partially supported by the NTUA-GSRT Research Award under Grant Number 67104700. The research of Dr. Eirini Eleni Tsiropoulou was conducted as part of the UNM Research Allocation Committee award and the UNM Women in STEM Faculty Development Fund.
\bibliographystyle{IEEEtran}
\bibliography{bibl}
\end{document}

config: arxiv


TITLE: Looking for reference to a couple of proofs regarding the Stereographic Projection.
QUESTION [1 upvotes]: I'm looking for a reference to rigorous proofs of the following two claims (if someone is willing to write down a proof that would also be excellent):

The Stereographic Projection is a Homeomorphism between $S^{n}\backslash\left\{ N\right\}$ (the sphere without its north pole) and $\mathbb{R}^{n}$ for $n\geq2$.
The Stereographic Projection is a Homeomorphism between $S^{n}$ and the one point compactification of $\mathbb{R}^{n}$

Help would be appreciated.

REPLY [0 votes]: For the first request just try to write down explicitly the function that defines such a projection, by considering an hyperplane which cuts the sphere along the equator.
Consider $S^n$ in $R^{n+1}$, with $R^n$ as the subset with $x_{n+1}=0$. The North pole is $(0,0,..,0,1)$ and the image of each point is the intersection of the line between such a point and the north pole and the above mentioned hyperplane. Thus you need to find (solving with respect to $t$) $\{(0,...,1) + t((x_1,..,x_{n+1})-(0,...,1)): t \in \mathbb{R} \}\bigcap\{x_{n+1}=0\}$ which yields the desired $t$ and so the image of the point.


TITLE: Phase invariant under Galilean transformation?
QUESTION [2 upvotes]: I just watched this video from MIT explaining Galilean transformation of ordinary waves.

https://www.youtube.com/watch?v=YdtHAIh-kas

Early on, the professor goes on to say that the phase is exactly the same in all inertial frames of reference, and I can't really see why. I intuitively have a feeling that the angular frequency of the wave changes if we are in a translating frame of reference relative to a stationary one, however, is there any way to understand why the phase is the same.
Maybe I'm just misunderstanding the definition of phase. But I'd be glad if anyone could clarify as to why this is the case (meaning without any proof of that $\omega' = \omega(1-\frac{v}{c})$ ) which he already shows in the video. More of a intuitive explanation is searched for, maybe some real life example.
Thanks.

REPLY [1 votes]: Early on, the professor goes on to say that the phase is exactly
the same in all inertial frames of reference, and I can't really
see why.
[...] is there any way to understand why the phase is the same.

There is nothing mysterious about the invariance of the phase.
To understand this consider 2-dimensional water waves on the sea
and a swimmer at its surface.
Let an observer at the beach watch the waves and the swimmer.
From his reference frame (with coordinates $x,y,t$)
the height of the waves is described by
$$h=A\cos(\underbrace{k_x x + k_y y - \omega t}_{=\ \phi}).$$
Suppose at a certain point in time ($t$) the swimmer is at the peak of a wave.
Because $\cos(\phi)$ has a maximum at $\phi=0$,
that means the wave phase at the swimmer is $\phi=0$.
Let a second observer from an airplane flying above the sea also
watch the waves and the swimmer.
From his reference frame (with coordinates $x',y',t$)
the height of the waves is described by
$$h=A\cos(\underbrace{k'_x x' + k'_y y' - \omega' t}_{=\ \phi'}).$$
As seen from the airplane, at the same certain point in time ($t$)
the swimmer has other spatial coordinates ($x',y'$). But of course
he is still at the peak of a wave, meaning his phase is $\phi'=0$.
You can repeat the reasoning above for the swimmer being
at the bottom of a wave (meaning $\phi=\phi'=180°$)
or at any other intermediate place/time of a wave ($\phi=\phi'$).
Hence it is always $$\phi =\phi'$$ or
$$k_x x + k_y y - \omega t = k'_x x' + k'_y y' - \omega' t$$


TITLE: What is the correct quantization of Hamiltonians of the form $H=x·p$ whose naive quantization is not Hermitian?
QUESTION [2 upvotes]: As we all learn in Basic Quantum Mechanics (the first quantization), we promote the classical variables to operators. Say, the classical hamiltonian $\frac{p^2}{2m}+V(x)$ to $-\frac{\hbar^2}{2m}\frac{d^2}{dx^2}+V(x)$, where we have replaced $p$ by $-i\hbar \frac{\partial}{\partial x}$ in coordinate representation.
But if the classical Hamiltonian of a conservative system $H = \omega x p$, where $\omega$ is a constant, this method fails as the constructed Hamiltonian of the form $-i\hbar \omega x\frac{\partial}{\partial x}$ is not hermitian.
What is wrong here?

REPLY [8 votes]: This problem is rooted in the way we derive quantum mechanics from the classical theory. Basically a quantum theory is a more complex object than a classical theory, so you will need to specify more information about it in order to it to be well defined. Thus after you have defined the hilbert space and it's operators you will need to choose an ordering prescription that will generalize your operators in the case of non commuting objects and that will reduce to the classical case when $\hat{x}$ and $\hat{p}$ (and so on) are not operators. So a possible choice for $\hat{H}$ is $$ \hat{H}=\frac{\omega}{2}(\hat{x}\hat{p}+\hat{p}\hat{x})$$ is the symmetrized ordering (also called weyl quantization) but really it's kinda aribtrary as long as $\hat{H}$ is hermitian (since it's observable) and reduces to it's classical analogue when: $$\hat{p}\rightarrow p\\\hat{x} \rightarrow x$$ A method to deal with those cases was developed by Weyl, Wigner and others and has generated various methods of quantization wich are more elegant than the "brute force" canonical quantization.

REPLY [5 votes]: When you have a product of operators in the classical Hamiltonian, the ordering of the operators in the quantum prescription is ambiguous. In the general case, suppose we have some classical operator $o=px$. As you noted, simply writing $O=PX$ is not Hermitian. The standard procedure is to symmetrize the sum, so that
$$O=\frac{PX+XP}{2}$$
As noted by Shankar on page 120 of Principles of Quantum Mechanics, there is no general procedure for three or more operators.


TITLE: Why $2j+1$ number of states?
QUESTION [0 upvotes]: In this statement from Modern Quantum Mechanics by J.J. Sakurai:

If $j$ is an integer, all $m$ values are integers; if $j$ is a half-integer, all $m$ values are half-integers. The allowed $m$-values for a given $j$ are
  $$m = \underbrace{-j,-j+1,\ldots,j-1,j}_{2j+1 {~\rm{states}}}$$

It says that $m$ will have a total of $2j+1$ states. I do not see this, however. Perhaps it is obvious, but could someone explain or show me why if $m$ goes from $-j,\ldots,j$ it will give $2j+1$ number of states?

REPLY [4 votes]: The $2j$ is from the positive and negative j values, and the additional  $+1$ accounts for $j=0$.


text:
/-
Copyright (c) 2020 Kevin Buzzard. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kevin Buzzard
-/
import algebra.group.pi
import algebra.group.commute
import data.int.basic
import tactic.linarith

/-!
# IMO 2019 Q1

Determine all functions `f : ℤ → ℤ` such that, for all integers `a` and `b`,
`f(2a) + 2f(b) = f(f(a+b))`.

The desired theorem is that either:
  -  `f = λ _, 0`
  -  `∃ c, f = λ x, 2 * x + c`

Note that there is a much more compact proof of this fact in Isabelle/HOL
  - http://downthetypehole.de/paste/4YbGgqb4
-/

theorem imo2019Q1 (f : ℤ → ℤ) :
  (∀ a b : ℤ, f (2 * a) + 2 * (f b) = f (f (a + b))) ↔
    (f = 0) ∨ ∃ c, f = λ x, 2 * x + c :=
begin
  split, swap,
  -- easy way: f(x)=0 and f(x)=2x+c work.
  { rintros (rfl|⟨c, rfl⟩); intros; simp only [pi.zero_apply]; ring },
  -- hard way.
  intro hf, -- functional equation
  -- Using `h` for `(0, b)` and `(-1, b + 1)`, we get `f (b + 1) = f b + m`
  obtain ⟨m, H⟩ : ∃ m, ∀ b, f (b + 1) = f b + m,
  { refine ⟨(f 0 - f (-2)) / 2, λ b, _⟩,
    refine sub_eq_iff_eq_add'.1 (int.eq_div_of_mul_eq_right two_ne_zero _),
    have h1 : f 0 + 2 * f b = f (f b) := by simpa using hf 0 b,
    have h2 : f (-2) + 2 * f (b + 1) = f (f b) := by simpa using hf (-1) (b + 1),
    linarith },
  -- Hence, `f` is an affine map, `f b = f 0 + m * b`
  obtain ⟨c, H⟩ : ∃ c, ∀ b, f b = c + m * b,
  { refine ⟨f 0, λ b, _⟩,
    induction b using int.induction_on with b ihb b ihb,
    { simp },
    { simp [H, ihb, mul_add, add_assoc] },
    { rw ← sub_eq_of_eq_add (H _),
      simp [ihb]; ring } },
  -- Now use `hf 0 0` and `hf 0 1` to show that `m ∈ {0, 2}`
  have H3 : 2 * c = m * c := by simpa [H, mul_add] using hf 0 0,
  obtain (rfl|rfl) : 2 = m ∨ m = 0 := by simpa [H, mul_add, H3] using hf 0 1,
  { right, use c, ext b, simp [H, add_comm] },
  { left, ext b, simpa [H, two_ne_zero] using H3 }
end

subset_name: curated


TITLE: Counterexample to Eisenstein criterion
QUESTION [1 upvotes]: We know Eisenstein criterion about irreducibility of polynomials: if $q(x) = x^n + a_{n-1}x^{n-1} + \dots +a_0 \in \mathbb{Z}[x]$ is such that $\exists p$ prime number with $ p \mid a_{i} \ \forall i \ , \ p^2 \nmid a_0$ then $q(x)$ is irreducible over $\mathbb{Q}$.
The question is : how to find a counterexample in the case $p$ is not a prime ?

REPLY [3 votes]: You mean like $(x-2)(x+2)=x^2-4$ for $p=4$?
Method used to find this counterexample:
Thought: Keep things simple. Just have a monic leading term and then a constant.
Asked self: Do I know any easy factorizations for binomials?
Thought: Of course: $(a-b)(a+b)=a^2-b^2$
Completed: Use $a=x$ and pick any $b$ but make sure $b^2\neq 1$ and use $p=b^2$


TITLE: Proving $\sin(x) < x$ for $0<x<2\pi$
QUESTION [0 upvotes]: Prove that $\sin(x) < x$ when  $0<x<2\pi.$

I have been struggling on this problem for quite some time and I do not understand some parts of the problem. I am supposed to use rolles theorem and Mean value theorem
First using the mean value theorem I got $\cos(x) = \dfrac {\sin(x)}x$
 and since $1 ≥ \cos x ≥ -1$ , $1 ≥ \dfrac {\sin(x)}x$ which is $x ≥ \sin x$ for all $x ≥ 0$.
Here the first issue is that I didn't know how to change $≥$ to $>$.
The second part is proving when $x<2\pi$ and this part I have no idea.
I know that $2\pi > 1$ , and $1 ≥ \sin x$ and my thought process ends here.

REPLY [0 votes]: Let $f(x) = \sin x, x \in \Bbb R.$ Let $x \in (0,1)$ then using Lagrange's MVT on the interval $[0,x]$ we get $$\frac {f(x)-f(0)} {x-0} = f'(c)$$  where $c \in (0,x) \subset (0,1).$Therefore we have $$\frac {\sin x} {x} = \cos c < 1,$$ since $0<c<1$ and $\cos x$ is strictly decreasing on $\left (0, {\pi} \right )$ and hence on $(0,1).$ Hence for all $x \in (0,1)$ we have $\sin x < x.$ Also for $x=1$ we have $\sin x = \sin 1 < \sin \left (\frac {\pi} {2} \right ) = 1,$ since $1 < \frac {\pi} {2}$ and $\sin x$ is strictly increasing on $\left (0,\frac {\pi} {2} \right ).$  Also for $x > 1$ we have $\sin x \leq 1 < x.$ So we have $\sin x < x$ for all $x > 0.$


TITLE: What is the definition of the contraction $\iota_\wedge (e)$?
QUESTION [0 upvotes]: Let $V$ be vector space and let $\wedge V$ be the exterior algebra of $V$.
If $e \in V$, what is the definition of the operator which is called the contraction by $e$ : $$\iota_\wedge(e): \wedge V \rightarrow \wedge V$$

REPLY [2 votes]: First define $\iota_\wedge(e):\Lambda^p(V)\to\Lambda^{p-1}(V)$ by
$$
\iota_\wedge(e)\omega(x_1,\ldots,x_{p-1}) = \omega(e,x_1,\ldots,x_{p-1}).
$$
Then extend this to $\Lambda(V)$ by linearity.