TITLE: Let $L$ be a Lie algebra over $\mathbb{C}$. Show that if $L' \neq L$ then $L$ has infinitely many non-isomorphic 1-dimensional modules.
QUESTION [0 upvotes]: Let $L$ be a Lie algebra over $\mathbb{C}$. Show that if $L' \neq L$ then $L$ has infinitely many non-isomorphic 1-dimensional modules.
I have already shown that if $\gamma: L \rightarrow gl(1,F)$ is a one dimensional representation then $\gamma(L')=0$. I have also showed that any representation of $\frac{L}{L'}$ can be seen as a representation of $L$ on which $L'$ acts trivially...
What is the most natural way to define a representation $\gamma: \frac{L}{L'} \rightarrow gl(1,F)$? How do I get inifitely many non-isomorphic of them?? Just sending all of $\frac{L}{L'}$ to a fixed complex number or something?? Help and detailed answers appreciated!

REPLY [4 votes]: For a linear form  $\lambda\in L^*$ on $L$ the map $\rho_{\lambda} : L\rightarrow \mathfrak{gl}_n(k)$ with $x\mapsto \lambda(x)$ is a representation if and only if $\lambda$ vanishes on $L'=[L,L]$.
This $1$-dimensional representation then is denoted by $k_{\lambda}$.
So the map $\lambda\rightarrow k_{\lambda}$ induces
a bijection of $(L/L')^*$  and the isomorphism classes of all $1$-dimensional representations of $L$.
So if $L'\neq L$, the space $(L/L')^*$ has infinitely many elements, over an infinite field $k$.


TITLE: Showing that for complex numbers $z_1,z_2,z_3$, $|z_1z_2+z_2z_3+z_3z_1|=|z_1+z_2+z_3|$ given that $|z_i|=1$.
QUESTION [2 upvotes]: Let $z_1,z_2$ and $z_3$ be complex numbers such that $|z_i|=1$ for $i=1,2,3$. Show that $|z_1z_2+z_2z_3+z_3z_1|=|z_1+z_2+z_3|$

This is an exercise from Jonathan S. Golan's book on Linear Algebra. To check that it is true for particular values of $z_i$, it is quite obvious that it holds when $z_i$ are the cube roots of unity.
I have checked it by computing both sides with $z_i=e^{i\theta_i}$, but the computation is extremely long and tedious. I was wondering if there is a more elegant way of proving this.
Apologies if this is a duplicate.

REPLY [0 votes]: The way you proposed to derive the identity can be made a bit less tedious by not trying to meet all the multiplications "head-on".  If we write $ \ z_{i} \ = \ e^{ \ i \ · \ \theta_{i}} \ \ , $ the sum $ \ z_1 + z_2 + z_3 \ $ has some (generally non-unit) modulus $ \ | \ z_1 + z_2 + z_3 \ | \ \ . $  On the Argand diagram, conjugation is equivalent to reflection about the " $ \ x-$axis", so certainly $ \ | \ z_1 + z_2 + z_3 \ | \  = \ | \ \overline{z_1} + \overline{z_2} + \overline{z_3} \ | \ = \ | \ e^{ \ -i \ · \ \theta_1} + e^{ \ -i \ · \ \theta_2} + e^{ \ -i \ · \ \theta_3} \ | $ $ = \left| \ \frac{1}{z_1} + \frac{1}{z_2} + \frac{1}{z_3} \ \right| \ \ . $
But since $$ \ | \ z_1 \ · \ z_2 \ · \ z_3 \ | \ \  = \  \ | \ e^{ \ i \ · \ (\theta_1 + \theta_2 + \theta_3)}  \ | \ \ = \ \ 1 \ \ , $$
we may write
$$  | \ z_1 + z_2 + z_3 \ | \ \  = \ \ | \ z_1 \ · \ z_2 \ · \ z_3 \ | \ · \ \left| \ \frac{1}{z_1} + \frac{1}{z_2} + \frac{1}{z_3} \ \right| $$
$$  = \  \  \left| \ (z_1  ·  z_2 \ ·  z_3) \ · \ \left(\frac{1}{z_1} + \frac{1}{z_2} + \frac{1}{z_3} \right) \ \right|  $$ $$ = \ \  | \ [ \ e^{ \ i \ · \ (\theta_1 + \theta_2 + \theta_3)} \ ] \ · \ (e^{ \ -i \ · \ \theta_1} \ + \ e^{ \ -i \ · \ \theta_2} \ + \ e^{ \ -i \ · \ \theta_3}) \  | $$
$$ = \ \  | \  e^{ \ i \ · \ (\theta_2 + \theta_3)} \ +  \ e^{ \ i \ · \ (\theta_1 + \theta_3)} \ +  \ e^{ \ i \ · \ (\theta_1 + \theta_2)}  \  | \ \
  = \ \  | \ z_2z_3 \   +    \ z_1z_3 \ + \ z_1z_2 \ |  \ \ .  $$
(Except for the choice of using the "polar form", this approach is not significantly different from the other algebraic calculations from the other respondents.)


TITLE: The order of multiplication in conjugation action of permutation group
QUESTION [0 upvotes]: My book has an example that a permutation group $S_n$ acts on itself through conjugation,i.e. the group action is defined by $\tau x\tau^{-1}$ that $x$ and $\tau$ are both elements of $S_n$.
Why the order of multiplying $\tau$ and $\tau^{-1}$on $x$ matters? For $\tau x\tau^{-1}$, I can prove it is a group action:
1.$exe^{-1}=x$
2.$(g_1 g_2)x = g_1 g_2 x g_2^{-1} g_1^{-1} = g_1(g_2 x g_2^{-1})g_1^{-1} = g_1(g_2(x)) $
But for $\tau^{-1} x \tau$,
$(g_1 g_2)x = g_2^{-1} g_1^{-1} x g_1 g_2 $ while $(g_1(g_2(x)) = g_1(g_2^{-1}x g_2) = g_1^{-1}g_2^{-1}xg_2g_1$
However, if $\tau y\tau^{-1}=x$ , then $\tau^{-1} x \tau = y$, so isn't it just an action in the opposite direction?  Should $\tau^{-1} x \tau$ be considered a group action?

REPLY [1 votes]: It turns out that the second action is not an action of the symmetric group $S_n$, but an action of its opposite group: $(S_n,\bullet)$, with $g\bullet h=h.g$. Since the symmetric group is not commutative, these actions are not the same.


text:
\section{Additional Use-case: Teaching Linear Ranking via Pairwise Comparisons}
\label{appendix: teaching ranking}

In this section, we would talk about the problem of teaching a randomly selected ranking of $n$ objects embedded in a $d$-dimensional space. Consider a set $\Theta$ of $n$ objects embedded in $\Rd$ (in general position). We define a ranking on the objects as an ordering $\sigma: \bracket{n} \rightarrow \bracket{n}$ of the form:
\begin{align*}
    \sigma\parenb{\Theta}:= \theta_{\sigma(1)} \prec \theta_{\sigma(2)}\cdots \prec \theta_{\sigma(n-1)} \prec \theta_{\sigma(n)}
\end{align*}
where $\theta_i \prec \theta_j$ implies $\theta_i$ precedes $\theta_j$ in ranking. The problem of interest is to construct a random ranking using \tt{pairwise comparisons} of the form:
\begin{align*}
    q_{i,j}:= \curlybracket{\theta_i \prec \theta_j}
\end{align*}
The response or label of $q_{i,j}$ is binary and denoted as $y_{i,j} := \mathbf{1} \curlybracket{q_{i,j}}$ where $\mathbf{1}$ is the indicator function; ties are not allowed. This is a well-studied problem in the literature and in the general setting it requires $\Theta(n \log n)$ bits of information to specify a ranking. But by imposing certain constraints on the embedding of the objects into the $d$-dimensional Euclidean space, \citet{jamieson2011active} shows we can get rid of the $n$ factor in the active query complexity.

\begin{figure*}[h]
\centering

		\includegraphics[width=.4\linewidth]{fig/example-ranking-illu.pdf}

  \caption{Teaching ranking via pairwise comparisons.}

	\label{fig:example.ranking}
	\vspace{-3mm}
\end{figure*}

We assume that for any ranking $\sigma$, there is a \tt{reference point} $r_{\sigma}$ such that if $\sigma$ ranks $\theta_i \prec \theta_j$ , then $||\theta_i - r_{\sigma}|| < ||\theta_j - r_{\sigma}||$. We refer to such assumption as {\bf E1}---This leads to an interpretation of a query ``is $\theta_i$ closer to $r_{\sigma}$ than $\theta_j$'', as identifying which side of the bisecting hyperplane (as shown in \defref{bisecting hyperplane}) of $\theta_i$ and $\theta_j$ does $r_{\sigma}$ lies in (as shown in \figref{fig:example.ranking}).
Before we discuss our teaching results and connections to the prior work of \citet{jamieson2011active}, we mention our key assumption \citep[also mentioned in][]{jamieson2011active} over the space of rankings as follows:
\begin{assumption}[\textbf{E1 embedding}]
The set of $n$ objects are embedded in $\Rd$ (in general position) and we will also use $\theta_1,\theta_2,\cdots,\theta_n$ to refer to their (known) locations in $\Rd$. Every ranking $\sigma$ can be specified by a reference point $r_{\sigma}$ $\in \Rd$, as follows. The Euclidean distances between the reference and objects are consistent with the ranking in the following sense: if the $\sigma$ ranks $\theta_i \prec \theta_j$ , then $||\theta_i - r_{\sigma}|| < ||\theta_j - r_{\sigma}||$. Let $\Sigma_{n,d}$ denote the set of all possible rankings of the $n$ objects that satisfy this embedding condition.
\end{assumption}
We assume that every pairwise comparison is consistent with the ranking to be learned. That is, if the reference ranks $\theta_i \prec \theta_j$, then $\theta_i$ must precede $\theta_j$ in the (full) ranking. We define the notion of bisecting hyperplane corresponding to objects $\theta_i$ and $
\theta_j$ as follows:
\begin{definition}[Bisecting hyperplane]\label{bisecting hyperplane}
A hyperplane $h_{i,j}$ in $\Rd$ is a bisecting hyperplane to objects $\theta_i$ and $\theta_j$ if both are equidistant from $h_{i,j}$ and $h_{i,j}\cdot (\theta_i - \theta_j) = 0$.
\end{definition}
Thus, $n$ objects lead to $\binom{n}{2}$ hyperplanes (one query for each pair of objects) in $\Rd$:\\
\[\underbrace{n\: \textnormal{embedded objects in\:} \Rd}_{\textnormal{Rankings of\:} \Theta}
    \stackrel{\boldsymbol{\textbf{E1}}}{\:\leadsto\:} \underbrace{ {\tiny \binom{n}{2}} \textnormal{ hyperplanes in\:} \Rd}_{\textnormal{Convex polytopes : reference points}}\]

Each convex polytope corresponds to a reference point, thereby to a ranking of objects.
\paragraph{Geometric interpretation of E1} We summarize the geometric interpretation of the key assumption which follows similar motivations as given in \citet[section 3]{jamieson2011active}. If we consider two objects $\theta_i$ and $\theta_j$ in $\Rd$, querying for $y_{i,j}$ corresponding to $q_{i,j}$ is equivalent to ascertaining to which halfspace of the orthogonal bisecting hyperplane of $\theta_i$ and $\theta_j$, $r_{\sigma}$ belongs to. The set of all possible pairwise comparison queries can be represented as $\binom{n}{2}$ distinct halfspaces in $\Rd$. The intersections of these halfspaces partition $\Rd$ into a number of cells termed as $d$-cells, and each one corresponds to a unique ranking of $\Theta$. Arbitrary rankings are not possible due to the embedding assumption \textbf{E1}. Similar to \cite{jamieson2011active},  we represent the set of rankings possible under \textbf{E1} by $\Sigma_{n,d}$. The cardinality of $\Sigma_{n,d}$ is equal to the number of cells in the partition.\\
\newline
Now, we formulate the teaching problem of linear rankings under the mentioned assumptions here.
\paragraph{Teaching rankings as teaching convex polytopes} Denote the $\binom{n}{2}$ hyperplanes induced by pairwise-comparison of $n$ embedded objects by $\Hndp$.
Following our teaching framework in \secref{section: teaching framework}, we know that $\regionpair$ induced by $\cA(\Hndp)$ forms the underlying hypothesis class; with instances $\Hndp$ and corresponding labeling set $\{1,-1\}$. Thus, teaching a ranking $r_{\sigma}$ corresponds to providing the teaching set $\mathcal{TS}(\Hndp,r_{\sigma})$ to a learner.

Interestingly, we note that

the hyperplanes induced by pairwise comparison of objects are no longer in general position. For example, in \figref{fig:example.ranking}, the three bisecting hyperplanes induced by any three points (in $\reals^2$) intersect at an 1-d subspace. When the embedded objects follow the assumption {\bf E1}(embedding) \citep{jamieson2011active}\footnote{We work in noise-free setting thus consistency is assumed similar to \cite{jamieson2011active}} show that the average query complexity for active ranking is $\mathcal{O}(d\log n)$. In contrast, we would show that the average teaching complexity of ranking via pairwise comparisons is $\mathcal{O}(d)$ via our \algoref{algo: teaching ranking}.
\subsection{Algorithm for Teaching Rankings}
We present our basic algorithm for teaching a ranking via pairwise comparisons. We assume we are given a set of $n$ objects $\Theta$ embedded in $\Rd$ in general position and a uniformly random ranking $r_{\sigma} \in \Sigma_{n,d}$ over it.

\begin{algorithm}
\caption{Teaching Ranking via Pairwise Comparisons}
\label{algo: teaching ranking}
\setcounter{AlgoLine}{0}
\nl {\bf Input}: $n$ objects in $\mathbb{R}^d$, random ranking $r_{\sigma} \in \Sigma_{n,d}$ {\label{lst:line:pair01}}\\
\Begin{
\nl $\mathcal{TS}(\Hndp,r_{\sigma}) \leftarrow$ {\bf FindLabels}$\parenb{r_{\sigma}}$ \tcc{indentifies  $\mathcal{TS}(\Hndp,r_{\sigma})$ via linear programming} {\label{lst:line:dual02}}
\nl\For {$(h,l)$ $\in$ $\mathcal{TS}(\Hndp,r_{\sigma})$ {\label{lst:line:dual03}}}{
teacher provides halfspace queries $(h,l)$
}
}
\end{algorithm}

Note that to teach the ranking $r_{\sigma}$ teacher has to provide the labels in $\mathcal{TS}(\Hndp,r_{\sigma})$. Since, $\mathcal{TS}(\Hndp,r_{\sigma})$ corresponds to the labels of the query hyperplanes which form the bounding set for $r_{\sigma}$, thus the entire ranking can be \tt{inferred}. \algoref{algo: teaching ranking} is straight forward in which for the set of objects $\Theta$ and a random ranking $r_{\sigma}$  teacher identifies the pair of comparisons using the subroutine \textbf{FindLabels}($\cdot$) and iteratively provides the labels (or halfspace queries) $\mathrm{wrt}$ the reference $r_{\sigma}$.
As discussed for \algoref{algo: teaching halfspace}, the subroutine \textbf{FindLabels}($\cdot$) can obtain the enclosing region in $\cO(n^4)$ iteration by solving linear equations system corresponding to $\cO(n^2)$ constraints.

\subsection{Average Complexity of Teaching Linear Ranking Functions}
Before we delve into the relevant results of the subsection, we would motivate the notations.
\paragraph{Notations} Consider the set of $n$ objects $\Theta = \parenb{\theta_1,\theta_2,\cdots,\theta_n}$ embedded in $\Rd$ in general position. We denote by $h_{i,j}$ the bijecting hyperplane for the pairwise comparison $q_{i,j}$ for objects $\theta_i$ and $\theta_j$. We use $C(n,d)$ to denote the number of regions or equivalently $d$-cells induced by query hyperplanes corresponding to pairwise comparisons of the embedded objects. $F(n,d)$ denotes the number of faces induced on all the query hyperplanes by their intersections.\\
\newline
The ideas behind the bound share similar motivations as for \thmref{theorem: Main Theorem}. Since the rankings are selected uniform at random, if we ascertain the number of faces for any region on average we get the bound. Thus, first we mention a recursion on $C(n,d)$ stated in \cite{jamieson2011active}. Then, we provide the result for the total number of faces induced on all the bisecting hyperplanes.

\begin{lemma}[Lemma 1, \cite{jamieson2011active}]\label{pairwise regions}
 Assume {\bf E1}. Let $C(n, d)$ denote the number of $d$-cells (regions) defined by the hyperplane arrangement of pairwise comparisons between these objects (\tt{i.e.} $C(n, d) = |\Sigma_{n,d}|)$. $C(n, d)$ satisfies the recursion:
 \begin{equation*}
     C(n,d) = C(n-1, d) + (n-1)C(n-1, d-1)
 \end{equation*}
\end{lemma}

\begin{lemma}\label{pairwise faces}
 Assume {\bf E1}. Let $F(n, d)$ denote the number of faces induced by the hyperplane arrangement of pairwise comparisons between these objects. $F(n, d)$ satisfies the recursion:
 \begin{equation*}
     F(n,d) = \binom{n}{2}\cdot C(n-1, d-1)
 \end{equation*}
\end{lemma}
\begin{proof}
If we consider any object say $\theta_k$, then the pairwise comparison induced hyperplane $h_{k,i}$ for a fixed $i \neq k$ is \textit{uniquely} intersected by query hyperplanes induced by pairwise comparison of other objects since they are in general position. Thus, on the $(d-1)$-dimensional hyperplane $h_{k,i}$ there are $\binom{n-1}{2}$ intersections (flats of dimension $d-2$). Following the discussion for Lemma 1, \cite{jamieson2011active} we note that the number of regions or $(d-1)$-cells induced on the bisecting hyperplane $h_{k,i}$ for a query is \tt{exactly} $C(n-1,d-1)$. Since there are $\binom{n}{2}$ hyperplanes for all the pairwise queries, thus the lemma follows.
\end{proof}
\begin{corollary}[Corollary 1, \cite{jamieson2011active}]\label{cor:nowak}
 There exist positive real numbers $k_1$ and $k_2$ such that
 \begin{equation*}
     k_1\frac{n^{2d}}{2^d d!} < C(n,d) < k_2\frac{n^{2d}}{2^d d!}
 \end{equation*}
for $n > d+1$. If $n \le d+1$, then $C(n,d) = n!$.
\end{corollary}

The following result shows that even under this special arrangement of hyperplanes, the average complexity for teaching such a ranking is $\bigTheta{d}$.
\begin{theorem}\label{theorem: teaching ranking}
Assume $\bf{E1}$ and $r_{\sigma}$ $\sim$ $\mathcal{U}$. There exists a teaching algorithm which requests $\bigTheta{d}$ pairwise comparisons on average for ranking \tt{i.e.} $\mathbb{E}_{\mathcal{U}}[M_n] = \bigTheta{d}$ where $M_n$ denotes a random variable for the number of pairwise
comparisons requested by an algorithm. In other words, the average teaching complexity of ranking via pairwise comparisons is $\bigTheta{d}$.
\end{theorem}
\subsection{Proof of \thmref{theorem: teaching ranking}}
We would prove the main result in two parts: (i) \lemref{lemma: pairwise lower bound} claims the upper bound on the average teaching complexity and (ii) \lemref{lemma: pairwise upper bound} claims the average teaching complexity. Thus, we show the proof of the main result by combining (i) and (ii). Similar to \secref{subsection: main theorem}, we analyze the following ratio to achieve the bounds:
\begin{align}
    \underbrace{\expctover{r_{\sigma}\sim\cU}{|\mathcal{TS}(\Hndp,r_{\sigma})|} = \frac{2\cdot\ff\parenb{\cA(\Hndp)}}{\fr\parenb{\cA(\Hndp)}} =
    \frac{ \text{\lemref{pairwise faces}}}{\text{\lemref{pairwise regions}}} }_{\textbf{Average teaching complexity of ranking}}
    \tag{A.7}\label{eqn:tag:a.7}
\end{align}
Key idea of the proofs is to control the rate in \ref{eqn:tag:a.7}.
Let us denote by  $M_n$ a random variable for the number of labels provided by the teacher for a uniformly random sampled ranking $r_{\sigma} \in \Sigma_{n,d}$. We say $\sigma$ $\sim \mathcal{U}$ for ease of notation. We would show that \algoref{algo: teaching ranking}, runs for at most $\mathcal{O}(d)$ in the following lemma \footnote{Note that \citet{Fukuda1991BoundingTN} established an $\bigO{d}$ average complexity for teaching convex polytopes under any hyperplane arrangement. Therefore one can apply \cite{Fukuda1991BoundingTN} to achieve the upper bound in \thmref{theorem: teaching ranking}. Here, we provide an alternative proof of the upper bound, which could be of separate interest.}.

\begin{lemma}\label{lemma: pairwise upper bound}
Assume $\bf{E1}$ and $\sigma$ $\sim$ $\mathcal{U}$. Let the random variable $M_n$ denote the number of pairwise
comparisons that are requested in the teaching \algoref{algo: teaching ranking}, then
\begin{equation*}
    \mathbb{E}_{\mathcal{U}}[M_n] \le c\cdot d
\end{equation*}
for some positive constant $c$.
\end{lemma}
\begin{proof}
For teaching, the labels of enclosing query hyperplanes of the reference point $r_{\sigma}$ induced by the objects, should be specified. Since the rankings are sampled uniformly at random, each ranking is enclosed by $F(n,d)\big/C(n,d)$ hyperplanes on average. We prove the theorem in two cases using the \corref{cor:nowak} and \lemref{pairwise faces}.\\
\newline
\underline{\textbf{Case} 1:} $n > d+1$ ($n$ is sufficiently large)\\
\begin{align*}
 \frac{F(n,d)}{C(n,d)}  &= \frac{\binom{n}{2}\cdot C(n-1, d-1)}{C(n,d)} \le \binom{n}{2} \cdot\Biggparen{k_2 \frac{(n-1)^{2(d-1)}}{2^{d-1}(d-1)!}}\cdot\frac{1}{k_1 \frac{n^{2d}}{2^dd!}} = \Biggparen{1 - \frac{1}{n}}^{2d-1}\frac{k_2}{k_1}d \le c\cdot d
\end{align*}
The second inequality follows from \corref{cor:nowak}.
\newline
\underline{\textbf{Case} 2:} $n \le d+1$\\
\begin{equation*}
    \frac{F(n,d)}{C(n,d)} = \frac{\binom{n}{2}\cdot (n-1)!}{n!} = \frac{n-1}{2} \le \frac{d}{2}
\end{equation*}

Thus, in the two cases we have shown that $\frac{F(n,d)}{C(n,d)}$ = $\mathcal{O}(d)$. This proves the lemma.
\end{proof}

We would show that \algoref{algo: teaching ranking}, runs for at least $\bigOmega{d}$ in the following lemma for sufficiently large $n$.
\begin{lemma}\label{lemma: pairwise lower bound}
Assume $\bf{E1}$ and $\sigma$ $\sim$ $\mathcal{U}$. Let the random variable $M_n$ denote the number of pairwise
comparisons that are requested in the teaching \algoref{algo: teaching ranking}, then for sufficiently large $n > d$:
\begin{equation*}
    \mathbb{E}_{\mathcal{U}}[M_n] \ge c\cdot d
\end{equation*}
for some positive constant $c$.
\end{lemma}
\begin{proof}
Following similar steps in upper bound provided in \lemref{lemma: pairwise upper bound}, but instead using opposite side of bounds in \corref{cor:nowak}, we get:\\

For $n > d+1$ ($n$ is sufficiently large)
\begin{align*}
 \frac{F(n,d)}{C(n,d)}  &= \frac{\binom{n}{2}\cdot C(n-1, d-1)}{C(n,d)} \ge \binom{n}{2} \cdot\Biggparen{k_1 \frac{(n-1)^{2(d-1)}}{2^{d-1}(d-1)!}}\cdot\frac{1}{k_2 \frac{n^{2d}}{2^dd!}} = \Biggparen{1 - \frac{1}{n}}^{2d-1}\frac{k_1}{k_2}d \ge c\cdot d
\end{align*}
The second inequality follows from \corref{cor:nowak}. In the last inequality we note that $\parenb{1 - \frac{1}{n}}^{2d-1}$ is bounded since $ \lim_{n \to \infty} \parenb{1 - \frac{1}{n}}^{n} = \frac{1}{e}$ and is increasing for large enough $n$.

Thus, we have shown that $\frac{F(n,d)}{C(n,d)}$ = $\bigOmega{d}$. This proves the lemma.
\end{proof}

\begin{proof}[Proof of \thmref{theorem: teaching ranking}]
In \lemref{lemma: pairwise upper bound} and \lemref{lemma: pairwise lower bound}, we showed the required bounds of $\cO(d)$ and $\bigOmega{d}$, and thus $\mathbb{E}_{\mathcal{U}}[M_n] = \bigTheta{d}$, which completes the proof.
\end{proof}

config: arxiv


TITLE: How is the expression for Bias-Variance obtained?
QUESTION [1 upvotes]: In
  this
  video lecture they say:
If $Y=f(X) + \epsilon$ where $\epsilon$ is the error for input $X$, then
  expectation value $E[\epsilon]=0$ and $\text{Var}[\epsilon]=\sigma^2$.
Then it is said that
$\text{EPE}(x_0)=E[(Y-f(x_0))^2|X=x_0]$        ----------- $(1)$
$\implies \text{EPE}(x_0)=E[(E[\hat{f}(x_0)]-\hat{f}(x_0))^2|X=x_0] +
 E[\hat{f}(x_0)-E[Y]]^2+\sigma^2 = \frac{\sigma^2}{k}$   -------- $(2)$
The first term on the right hand side is called the variance and the
  second term is called the bias.
$\implies \text{EPE}(x_0) = \frac{\sigma^2}{k} +
 [f(x_0)-E[\frac{1}{k}\sum_{l=1}^{k}f(x_{(l)})]]^2 + \sigma^2$
  ---------- $(3)$

Questions:

How do we get to step $(2)$ from step $(1)$? What does $\hat{f}$ mean?
Why is the variance term $\sigma^2/k$ ($k$ I think is the number of sample data points)?
Why does the bias term equal $[f(x_0)-E[\frac{1}{k}\sum_{l=1}^{k}f(x_{(l)})]]^2$ ?

REPLY [1 votes]: In step 1 we have that $\textrm{ESE} = \textrm{E}[(Y-f(x_0))^2]$. By adding and subtracting $E[\hat{f}(x_0)]$ we obtain:
\begin{equation}
\begin{split}
\textrm{ESE} & = \textrm{E}[(Y-f(x_0))^2]\\
 & = \textrm{E}[(Y-\textrm{E}[\hat{f}(x_0)] + \textrm{E}[\hat{f}(x_0)]- f(x_0))^2]
\end{split}
\end{equation}
Expanding this equation gives us the outer and inner terms squared, and the cross terms:
\begin{equation}
\begin{split}
\textrm{ESE} & = \textrm{E}[(Y-f(x_0))^2]\\
 & = \textrm{E}[(Y-\textrm{E}[\hat{f}(x_0)])^2] + \textrm{E}[(\textrm{E}[\hat{f}(x_0)]- f(x_0))^2] + 2\textrm{E}[(Y-\textrm{E}[\hat{f}(x_0)])(\textrm{E}[\hat{f}(x_0)]- f(x_0))]
\end{split}
\end{equation}
Note that all of the values in the second expectation are constants, so we can get rid of the outer expectation and obtain:
\begin{equation}
\begin{split}
\textrm{ESE} & = \textrm{E}[(Y-\textrm{E}[\hat{f}(x_0)])^2] + (\textrm{E}[\hat{f}(x_0)]- f(x_0))^2 + 2\textrm{E}[(Y-\textrm{E}[\hat{f}(x_0)])(\textrm{E}[\hat{f}(x_0)]- f(x_0))]
\end{split}
\end{equation}
So we can see that the first term is the variance, the escond term is the bias of the estimate $\hat{f}(x_0)$ squared, and the right term is left to deal with.
If we can show that the right term is $0$, then we are done.
Expanding the righthand term gives us:
\begin{equation}
\begin{split}
2\textrm{E}[(Y-\textrm{E}[\hat{f}(x_0)])(\textrm{E}[\hat{f}(x_0)]- f(x_0))] & = 2\textrm{E}[Y\textrm{E}[\hat{f}(x_0)]-\textrm{E}[\hat{f}(x_0)]^2 -\textrm{E}[\hat{f}(x_0)]f(x_0) + Yf(x_0)]\\
&=  2(\textrm{E}[Y]\textrm{E}[\hat{f}(x_0)]-\textrm{E}[\hat{f}(x_0)]^2 -\textrm{E}[\hat{f}(x_0)]f(x_0) + \textrm{E}[Y]f(x_0))
\end{split}
\end{equation}
If $\textrm{E}[\hat{f}(x_0)] = f(x_0)$ then these terms cancel and we get just the bias and variance.


TITLE: bounds in centralized and distributed
QUESTION [2 upvotes]: If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?

REPLY [5 votes]: I'm not aware of a general rule to convert centralized bounds to the distributed setting. In the distributed setting, local computation is given for free but the difficulty lies in breaking the symmetry - a node needs to accumulate enough information about it's neighborhood to make a decision about being part of the output set, e.g. being in the MIS. (Taking this a step further, we can think of an $r$-round algorithm as a function mapping $r$-neighborhoods to a yes/no decision.)
For example, for certain $n$-node graphs with max degree $\Delta$ there is an $\Omega(\sqrt{\log n}+\log \Delta)$ lower bound [2] known on the number of distributed rounds, that holds for (the distributed version of) computing a constant approximation of a minimum vertex cover or of a minimum dominating set.
While the above problems are known to be NP-complete, the same lower bound also holds for problems for which there are polynomial time centralized algorithms like computing a maximal independent set or finding a maximal matching.
For most of these problems the lower bound is almost tight; there are distributed algorithms that run in polylogarithmic rounds (see [2] and references therein).
On the other hand, some NP complete problems even allow constant time solutions in the distributed setting! In [1] there's an $O(1)$ round distributed algorithm for $O(n^{1/2+\varepsilon} \chi)$-coloring, which itself is NP complete.
[1] Leonid Barenboim. On the Locality of Some NP-Complete Problems
http://arxiv.org/abs/1204.6675
[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer. Local Computation: Lower and Upper Bounds.
http://arxiv.org/pdf/1204.6675v1.pdf