\subsection{Properties of Reductions}
Ultimately, the real test of a learning model is whether it allows for
tractable analysis leading to useful learning algorithms.  We address
that point later, and first
note several desirable properties of this definition.
                                                                                
\subsubsection{Non-triviality of the definition}
Definition~\ref{definition:reduction} is only significant when the
oracle learner's loss rate is small.  We can show that for every
reduction this is sometimes the case.  Consequently, trivial
reductions that either never call $A$ or create ``hard'' subproblems
with arbitrarily large informational lower bounds on errors are not
allowed.

\begin{proposition}
For every error-limiting reduction $R$, every training set $S$, and
test example $(x,k)$, there exists an oracle $A$ such that
$$\bE_h [h(x)] = \arg \min_{y \in Y} \lossfunc(k,y)=0,$$ where $h$
is the hypothesis output by $R(S,A)$, and the expectation
is over the randomization used by $R$ in forming $h$.
\end{proposition}
This proposition states that the reduction must make a non-trivial use
of its oracle $A$ (although it does not forbid some almost always
suboptimal behaviors like encrypting $x$).
\begin{proof}
We first note that there must exist a sub-hypothesis $h'$ used by the
hypothesis $h$ which the reduction creates.  This is so because the
convention $\max_{\emptyset} = 0$ in the error limiting reduction
implies $\lossfunc(k,h(x)) = g(\max_{\emptyset}) = g(0) = 0$.
(Recall that the error limitation property holds for all $D$, in particular for
the deterministic $D$ with all probability mass on $(x,k)$.)
The
fact that $\lossfunc(k,y)$ is nonconstant (in both arguments) implies
that there exists $(x,k)$ such that any prediction
machine\footnote{Note that a machine with state is required rather
than a (stateless) function to cope with the situation where the
reduction uses the same $x'$ twice.} $h$ satisfies $\lossfunc(k,h(x))
> 0$, a contradiction.  Consequently, at least one call to $A$ must be
made.

                                                                                
Next note that for all error limiting reductions $R$, samples $S$, and
test samples $(x,k)$, there exists an $h'$ (and thus an $A$ outputting
$h'$) such that $h'(x') = \arg \min_{y' \in Y'} \lossfunc(k',y') = 0$.
This is obvious if the reduction is deterministic.  Since $h'$ is a
prediction machine, this is sufficient to predict perfectly for every
element $(x',k') \in S'$.
                                                                                
In the case of a randomized reduction, note that for every randomized
reduction $R$ there exists a deterministic reduction $R'$ taking one
additional argument (a randomly chosen string) with the same output
behavior as $R$.  Consequently, there exists an oracle $A$ dependent
on this random string which achieves error rate $0$.  Since $g(0) =
0$, this must imply that $h(x) = \arg \min_{y \in Y} \lossfunc(k,y) =
0$.  \qed
\end{proof}
                                                                                
\subsubsection{Composition}
                                                                                
Since our motivation for studying reductions is to reduce the number of
distinct problems which must be considered, it is natural to want to
compose two or more reductions to obtain new ones.
It is easy to see that reductions defined above compose.
                                                                                
\begin{proposition}
If $R_{12}$ is a reduction from task ${\task}_1$ to ${\task}_2$
with error limitation $g_{12}$ and $R_{23}$ is a reduction from task
${\task}_2$ to ${\task}_3$ with error limitation $g_{23}$, then the
composition $R_{12}\circ R_{23}$ is a reduction from ${\task}_1$ to
${\task}_3$ with error limitation $g_{12} \circ g_{23}$.
\end{proposition}
\begin{proof}
Given oracle access to any learning algorithm $A$ for ${\task}_3$,
reduction $R_{23}$ yields a learning algorithm for ${\task}_2$ such that for
any $X_2$ and $D_2$, it produces a hypothesis with loss rate
$h'_{D_2} \leq g_{23}(h''_{D_3})$,
where
$h''_{D_3}$ is the maximum loss rate
of a hypothesis $h''$ output by $A$ (over all invocations).
We also know that $R_{12}$ yields a
learning algorithm for ${\task}_1$ such that for all $X_1$ and $D_1$ we have:
$$h_{D_1}\leq g_{12}(h'_{D_2}) \leq
g_{12}(g_{23}(h''_{D_3})),$$ where $h'_{D_2}$ is the maximum
loss rate of a hypothesis $h'$ output by $R_{23}(A)$.
Finally, notice that $g_{12}\circ g_{23}$ is continuous, monotone
nondecreasing, and $g_{12}(g_{23}(0))=0$.
\qed
\end{proof}

