%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Convergence and Loss Bounds for Bayesian Sequence Prediction %% %% Marcus Hutter: Start: 15.08.01 LastEdit: 16.01.03 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %-------------------------------% % Compiler-Switches % %-------------------------------% \newif\iftwocol\twocoltrue %format as twocolumn-document %-------------------------------% % Document-Style % %-------------------------------% \documentclass[twoside\iftwocol,twocolumn\else,12pt\fi]{article} \usepackage{latexsym} \pagestyle{myheadings} \markboth{\sc Marcus Hutter, Technical Report, IDSIA-09-01 }{\sc Convergence and Loss Bounds for Bayesian Sequence Prediction} \setcounter{tocdepth}{4} \setcounter{secnumdepth}{2} \topmargin=-10mm \oddsidemargin=-10mm \evensidemargin=-10mm \textwidth=18cm \textheight=23cm \unitlength=1mm \sloppy %\def\baselinestretch{0.96} %-------------------------------% % My Math-Spacings % %-------------------------------% \def\,{\mskip 3mu} \def\>{\mskip 4mu plus 2mu minus 4mu} \def\;{\mskip 5mu plus 5mu} \def\!{\mskip-3mu} \def\dispmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip= 4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu} \def\textmuskip{\thinmuskip= 0mu \medmuskip= 1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu} \textmuskip \def\beq{\dispmuskip\begin{equation}} \def\eeq{\end{equation}\textmuskip} \def\beqn{\dispmuskip\begin{displaymath}}\def\eeqn{\end{displaymath}\textmuskip} \def\bqa{\dispmuskip\begin{eqnarray}} \def\eqa{\end{eqnarray}\textmuskip} \def\bqan{\dispmuskip\begin{eqnarray*}} \def\eqan{\end{eqnarray*}\textmuskip} %-------------------------------% % Macro-Definitions % %-------------------------------% \renewenvironment{abstract}{\begin{quote}{\noindent\bf Abstract.}}{\end{quote}} \newenvironment{keywords}{\begin{quote}{\noindent\bf Keywords.}}{\end{quote}} \newtheorem{exercise}{$\!\!$}[section] \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \def\ftheorem#1#2#3{\begin{theorem}[#2]\label{#1} \it #3 \end{theorem} } \def\fcorollary#1#2#3{\begin{corollary}[#2]\label{#1} \it #3 \end{corollary} } \def\flemma#1#2#3{\begin{lemma}[#2]\label{#1} \it #3 \end{lemma} } \def\fdefinition#1#2#3{\begin{definition}[#2]\label{#1} \it #3 \end{definition} } \def\subsection#1{\vspace{1ex}\noindent{\bf #1.}} \def\toinfty#1{\stackrel{#1\to\infty}{\longrightarrow}} \def\nq{\hspace{-1em}} \def\qed{\hspace*{\fill}$\Box\quad$} \def\odt{{\textstyle{1\over 2}}} \def\odf{{\textstyle{1\over 4}}} \def\odA{{\textstyle{1\over A}}} \def\odn{{\textstyle{1\over n}}} \def\eps{\varepsilon} \def\vec#1{{\bf #1}} \def\M{{\cal M}} \def\X{{\cal X}} \def\Y{{\cal Y}} \def\F{{\cal F}} \def\E{{\bf E}} \def\P{{\bf P}} \def\B{\Set{B}} % Binary set (or \set{B}) \def\Set#1{\if#1Q{I\!\!\!#1}\else\if#1Z{Z\!\!\!Z}\else{I\!\!#1}\fi\fi} \def\qmbox#1{{\quad\mbox{#1}\quad}} \def\sumprime{\mathop{{\sum\nolimits'}}} \def\tolim{\mathop{\longrightarrow}\limits} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % T i t l e - P a g e % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\vspace*{-2cm} {\normalsize Technical Report IDSIA-09-01 \hfill 15 August 2001 -- 16 January 2003\\[1mm]} \huge\sc\hrule height1pt \vskip 2mm Convergence and Loss Bounds for \\ Bayesian Sequence Prediction \vskip 2mm \hrule height1pt} \author{Marcus Hutter \\[1ex] \small IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland% \thanks{This work was supported by SNF grant 2000-61847.00 to J\"urgen Schmidhuber.} \\ \small marcus@idsia.ch, http://www.idsia.ch/$^{_{_\sim}}\!$marcus } \date{} \maketitle % typeset the title of the contribution \begin{abstract} The probability of observing $x_t$ at time $t$, given past observations $x_1...x_{t-1}$ can be computed with Bayes' rule if the true generating distribution $\mu$ of the sequences $x_1x_2x_3...$ is known. If $\mu$ is unknown, but known to belong to a class $\M$ one can base ones prediction on the Bayes mix $\xi$ defined as a weighted sum of distributions $\nu\in\M$. % Various convergence results of the mixture posterior $\xi_t$ to the true posterior $\mu_t$ are presented. In particular a new (elementary) derivation of the convergence $\xi_t/\mu_t\to 1$ is provided, which additionally gives the rate of convergence. % A general sequence predictor is allowed to choose an action $y_t$ based on $x_1...x_{t-1}$ and receives loss $\ell_{x_t y_t}$ if $x_t$ is the next symbol of the sequence. No assumptions are made on the structure of $\ell$ (apart from being bounded) and $\M$. % The Bayes-optimal prediction scheme $\Lambda_\xi$ based on mixture $\xi$ and the Bayes-optimal informed prediction scheme $\Lambda_\mu$ are defined and the total loss $L_\xi$ of $\Lambda_\xi$ is bounded in terms of the total loss $L_\mu$ of $\Lambda_\mu$. It is shown that $L_\xi$ is bounded for bounded $L_\mu$ and $L_\xi/L_\mu\to 1$ for $L_\mu\to \infty$. Convergence of the instantaneous losses are also proven. \end{abstract} \begin{keywords} Bayesian sequence prediction; general loss function and bounds; convergence; mixture distributions% \end{keywords} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{secInt} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %------------------------------% \subsection{Setup} %------------------------------% We consider inductive inference problems in the following form: Given a string $x_1 x_2 ... x_{t-1}$, we want to predict its continuation $x_t$. We assume that the strings which have to be continued are drawn from a probability distribution $\mu$. The maximal prior information a prediction algorithm can possess is the exact knowledge of $\mu$, but in many cases the true generating distribution is not known. % In order to overcome this problem a mixture distribution $\xi$ is defined as a $w_\nu$ weighted sum over distributions $\nu\in\cal M$, where $\cal M$ is any discrete (hypothesis) set including $\mu$. We assume that $\M$ is known and contains the true distribution, i.e. $\mu\in\M$. % Since the posterior $\xi_t$ can be shown to converge rapidly to the true posterior $\mu_t$, making decisions based on $\xi$ is often nearly as good as the infeasible optimal decision based on the unknown $\mu$ \cite{Feder:98}. In this work we compare the expected loss of predictors based on mixture $\xi$ to the expected loss of informed predictors based on $\mu$. %------------------------------% \subsection{Contents} %------------------------------% Section \ref{secSetup} introduces concepts and notation needed later, including strings, probability distributions, mixture distributions, expectations, and various types of convergence and distance measures. % Section \ref{secConv} summarizes various convergence results of the mixture distribution $\xi$ to the true distribution $\mu$. We provide a new (elementary) derivation of the posterior convergence in ratio, which is not based on Martingales, but on the Hellinger distance, and compare it to related known results \cite{Doob:53,Li:97,Vovk:87,Vitanyi:00}. % Section \ref{secLoss} introduces the decision theoretic setup, where an action/prediction $y_t$ results in a loss $\ell_{x_t y_t}$ if $x_t$ is the next symbol of the sequence. Improving upon previous results in \cite{Feder:98,Hutter:01alpha,Hutter:01loss}, the expected total (or cumulative) loss $L_\xi$ made by the Bayes-optimal prediction scheme based on mixture $\xi$ minus the expected total loss $L_\mu$ of the optimal informed prediction scheme based on $\mu$ is bounded by $O(\sqrt{L_\mu})$. Some popular loss functions, including the absolute, square, logarithmic, Hellinger, and error loss are discussed. % A Proof of the loss bound is given in Section \ref{secLProof}. % Convergence of the instantaneous losses are briefly studied in Section \ref{secILoss}. % Section \ref{secConc} recapitulates the assumptions made in this work and possible relaxations, mentions some optimality properties of $\xi$ proven in \cite{Hutter:01op}, and provides an outlook to future work. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries}\label{secSetup} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %------------------------------% \subsection{Strings and Probability Distributions} %------------------------------% We denote strings over a finite alphabet $\X$ by $x_1x_2...x_n$ with $x_t\in\X$. We abbreviate $x_{n:m}:=x_nx_{n+1}...x_{m-1}x_m$ and $x_{0. \eeq $\xi$ is called a Bayes-mixture. The weights $w_\nu$ may be interpreted as the prior belief in environment $\nu\in\M$. The most interesting property the mixture distribution $\xi$ is that it multiplicatively dominates all distributions in $\M$: \beq\label{unixi} \xi(x_{1:n}) \;\geq\; w_\nu\!\cdot\!\nu(x_{1:n}) \quad\mbox{for all}\quad \nu\in\M. \eeq In the following, we assume that $\M$ is known and contains the true distribution, i.e. $\mu\in\M$. % If $\M$ is chosen sufficiently large, then $\mu\in\M$ is not a serious constraint. Generic classes, especially where $\M$ contains {\em all} (semi)computable probability distributions are discussed in \cite{Solomonoff:78,Li:97,Hutter:01alpha,Hutter:01op}. % Generalizations to the case where $\M$ does not contain $\mu$ are briefly discussed in \cite{Hutter:01op} and more intensively in a related context in \cite{Gruenwald:98}. %------------------------------% \subsection{Expectations and convergence measures} %------------------------------% We use $\E[..]$ to denote expectations w.r.t.\ the ``true'' distribution $\mu$ and abbreviate $\E_t[..]:=\E[..|x_{\eps$ (or $|\xi'_t-\mu'_t|>\eps$) is bounded by $\eps^{-2}\ln w_\mu^{-1}$. Note also the subtle difference between $(iii)$ and $(v)$. If $x_{1:\infty}$ is a $\mu$-random sequence, and $x'_{1:\infty}$ is {\em any} (possibly constant and not necessarily $\mu$-random) sequence then $\mu'_t-\xi'_t$ converges to zero, but no statement is possible for $\xi'_t/\mu'_t$, since $\lim\,\inf\mu'_t$ could be zero. On the other hand, if we stay {\em on} the $\mu$-random sequence ($x'_{1:\infty} = x_{1:\infty}$), $(v)$ shows that $\xi_t/\mu_t \to 1$ (whether $\inf\mu_t$ tends to zero or not does not matter). % Indeed, it is easy to see that $\xi(1|0_{\,\gamma$, where $\gamma := {\ell_{01}-\ell_{00}\over \ell_{01}-\ell_{00}+\ell_{10}-\ell_{11}}$ and $\rho_i = \rho(i|x_{\,\rho_1$. Since all predictions $y$ lie in the subset $\{0,1\}\subset[0,1]$ and $|x - y| = 1 - \delta_{xy}$ for $y \in \{0,1\}$ this case coincides with the binary error case above. The same holds for the $\alpha$-loss $|x-y|^\alpha$ with $0 < \alpha \leq 1$. The $\mu$-expected loss is $l_t^{\Lambda_\rho} = \mu(i|x_{ \odt$. % For the {\em quadratic loss} $\ell_{xy} = (x - y)^2 \in [0,1]$ the action/prediction $y_t^{\Lambda_\rho} = \arg\min_{y\in[0,1]}\{\rho_1(1 - y)^2+\rho_0 y^2\} = \rho_1$ is proportional to the $\rho$-probability of $x_t = 1$ and $l_t^{\Lambda_\rho} = \E_t(1-\rho(x_t|x_{ 1$ we get $y_t^{\Lambda_\rho}=(1 + \sqrt[\alpha-1]{\scriptstyle \rho_0/\rho_1})^{-1}$. For arbitrary finite alphabet $\X$ and vector-valued predictions $\vec y$ the quadratic loss may be generalized to $\ell_{x\vec y} = \odt \vec y^T{\bf A}_x\vec y + \vec b_x^T\vec y + c_x$. % The {\em Hellinger loss} can be written for binary outcome in the form $\ell_{xy} = 1 - \sqrt{|1 - x - y|} \in [0,1]$ with $y_t^{\Lambda_\rho} = {\rho_1^2/(\rho_0^2+\rho_1^2)}$ and $l_t^{\Lambda_\rho} = 1-{(\mu_0\rho_0 + \mu_1\rho_1)/ \sqrt{\rho_0^2+\rho_1^2}}$. % The {\em logarithmic loss} $\ell_{xy} = -\ln|1 - x - y| \in [0,\infty]$ is unbounded. But since the corresponding action is $y_t^{\Lambda_\rho} = \rho_1$ the expected loss is $l_t^{\Lambda_\rho} = - \E_t\ln \rho(x_t|x_{ 0$ and $B > 0$, which satisfy the linear inequality \beq\label{Eineq3} L_n^{\Lambda_\xi} \;\leq\; (A+1)L_n^{\Lambda_\mu} + (B+1)D_n. \eeq If we could show \beq\label{eineq3} l_t^{\Lambda_\xi}(x_{ \ell_{is}\forall i$ and $\ell_{is} > \ell_{im}\forall i$ contradict the first/second inequality (\ref{lcnstr}). Hence we can assume $\ell_{0m} \geq \ell_{0s}$ and $\ell_{1m} \leq \ell_{1s}$. The symmetric case $\ell_{0m} \leq \ell_{0s}$ and $\ell_{1m} \geq \ell_{1s}$ is proven analogously or can be reduced to the first case by renumbering the indices ($0\leftrightarrow 1$). Using the abbreviations $a := \ell_{0m} - \ell_{0s}$, $b := \ell_{1s} - \ell_{1m}$, $c := y_1\ell_{1m} + y_0\ell_{0s}$, $y = y_1 = 1 - y_0$ and $z = z_1 = 1 - z_0$ we can write (\ref{lossineqf2}) as \beq\label{lossineqf3}\textstyle f(y,z) \;:=\; \eeq \beqn\textstyle B'[y\ln{y\over z}+(1\!-\!y)\ln{1-y\over 1-z}] + A'(1\!-\!y)a-yb+Ac \;\stackrel?\geq\; 0 \eeqn for $zb \leq (1-z)a$ and $0 \leq a,b,c,y,z \leq 1$. The constraint (\ref{lcnstr}) on $y$ has been dropped since (\ref{lossineqf3}) will turn out to be true for all $y$. Furthermore, we can assume that $d := A'(1-y)a-yb \leq 0$ since for $d > 0$, $f$ is trivially positive. Multiplying $d$ with a constant $\geq 1$ will decrease $f$. Let us first consider the case $z \leq \odt$. We multiply the $d$ term by $1/b \geq 1$, i.e. replace it with $A'(1-y){a\over b}-y$. From the constraint on $z$ we known that ${a\over b} \geq {z\over 1-z}$. We can decrease $f$ further by replacing ${a\over b}$ by ${z\over 1-z}$ and by dropping $Ac$. Hence, (\ref{lossineqf3}) is proven for $z \leq \odt$ if we can prove \beq\label{lossineq1}\textstyle f_1(y,z) := B'[ \iftwocol ... \else y\ln{y\over z}+(1\!-\!y)\ln{1-y\over 1-z} \fi] %[...] + A'(1\!-\!y){z\over 1-z}-y \;\stackrel?\geq\; 0 \;\mbox{for}\; z\leq\odt. \eeq In the next paragraph of this section %Section \ref{secSPProofs} we prove that it holds for $B \geq\odA+1$. The case $z \geq \odt$ is treated similarly. We scale $d$ with $1/a \geq 1$, i.e. replace it with $A'(1-y)-y{b\over a}$. From the constraint on $z$ we know that ${b\over a} \leq {1-z\over z}$. We decrease $f$ further by replacing ${b\over a}$ by ${1-z\over z}$ and by dropping $Ac$. Hence (\ref{lossineqf3}) is proven for $z \geq \odt$ if we can prove \beq\label{lossineq2}\textstyle f_2(y,z) := B'[ \iftwocol ... \else y\ln{y\over z}+(1\!-\!y)\ln{1-y\over 1-z} \fi] %[...] + A'(1\!-\!y)-y{1-z\over z} \;\stackrel?\geq\; 0 \;\mbox{for}\; z\geq\odt. \eeq In the second next paragraph of this section %In Section \ref{secSPProofs} we prove that it holds for $B \geq\odA+1$. So in summary we proved that (\ref{Eineq3}) holds for $B \geq\odA+1$. Inserting $B =\odA+1$ into (\ref{Eineq3}) and minimizing the r.h.s.\ w.r.t.\ $A$ leads to the last bound of Theorem \ref{thULoss} with $A = \sqrt{D_n/L_n^{\Lambda_\mu}}$. Actually inequalities (\ref{lossineq1}) and (\ref{lossineq2}) also hold for $B \geq \odf A+\odA$, which, by the same minimization argument, proves the slightly tighter second bound in Theorem \ref{thULoss}. Unfortunately, the current proof is very long and complex, and involves some numerical or graphical analysis for determining intersection properties of some higher order polynomials. This or a hopefully simplified proof will be postponed. The cautious reader may check the inequalities (\ref{lossineq1}) and (\ref{lossineq2}) numerically for $B = \odf A+\odA$. \qed %------------------------------% \subsection{Binary loss inequality for $z\leq\odt$ (\ref{lossineq1})}\label{appLossIneq1} %------------------------------% We now prove $f_1(y,z)\geq 0$ for $z\leq\odt$ and suitable $A' \equiv A + 1$ and $B' \equiv B + 1$. We do this by showing that $f_1\geq 0$ at all extremal values and ``at'' boundaries. $f_1\to +\infty$ for $z\to 0$, if we choose $B'>0$. For the boundary $z = \odt$ we lower bound the relative entropy by the sum over squares $s\leq d$ (\ref{entroineq2}) \beqn f_1(y,\odt)\geq 2B'(y-\odt)^2+A'(1-y)-y\geq 0 \quad\mbox{for}\quad B\geq\odf A+\odA \eeqn as can be shown by minimizing the r.h.s.\ w.r.t.\ $y$. Furthermore for $A \geq 4$ and $B \geq 1$ we have $f_1(y,\odt) \geq 2(1-y)(3-2y) \geq 0$. Hence $f_1(y,\odt) \geq 0$ for $B \geq \odA+1$, since for $A \geq 4$ it implies $B \geq 1$ and for $A \leq 4$ it implies $B \geq \odf A+\odA$. % The extremal condition $\partial f/\partial z = 0$ (keeping $y$ fixed) leads to \beqn y \;=\; y^* \;:=\; z\!\cdot\!{B'(1\!-\!z)+A'\over B'(1\!-\!z)+A'z}. \eeqn Inserting $y^*$ into the definition of $f_1$ and, again, replacing the relative entropy by the sum over squares ($y\ln{y\over z}+(1\!-\!y)\ln{1-y\over 1-z}\geq 2(y-z)^2$), which is a special case of $s\leq d$ (\ref{entroineq2}), we get \beqn\textstyle f_1(y^*,z) \geq 2B'(y^*\!-\!z)^2+A'(1\!-\!y^*){z\over 1-z}-y^* = {z(1-z)\cdot g_1(z)\over [B'(1-z)+A'z]^2}, \eeqn \beqn\textstyle g_1(z) := 2B'A'^2z(1-z)+[(A'-1)B'(1-z)-A'](B'+A'{z\over 1-z}). \eeqn We have reduced the problem to showing $g_1 \geq 0$. If the bracket $[...]$ is positive, then $g_1$ is positive. If the bracket is negative, we can decrease $g_1$ by increasing ${z\over 1-z} \leq 1$ in $(B'+A'{z\over 1-z})$ to $1$. The resulting expression is now quadratic in $z$ with minima at the boundary values $z = 0$ and $z = \odt$. It is therefore sufficient to check \beqn g_1(0)\geq (AB-1)(A+B+2)\geq 0 \qmbox{and} \eeqn \beqn g_1(\odt)\geq \odt(AB-1)(2A+B+3)\geq 0 \eeqn which is true for $B \geq \odA$. In summary we have proved (\ref{lossineq1}) for $B \geq \odA + 1$ and $A > 0$. \qed %------------------------------% \subsection{Binary loss inequality for $z\geq\odt$ (\ref{lossineq2})}\label{appLossIneq2} %------------------------------% We now prove we show $f_2(y,z)\geq 0$ for $z\geq\odt$ and suitable $A' \equiv A + 1 > 1$ and $B' \equiv B + 1 > 2$ similarly as in the last paragraph by proving that $f_2\geq 0$ at all extremal values and ``at'' boundaries. $f_2\to +\infty$ for $z\to 1$. The boundary $z = \odt$ has already been checked in in the last paragraph. The extremal condition $\partial f/\partial z = 0$ (keeping $y$ fixed) leads to \beqn y \;=\; y^* \;:=\; z\!\cdot\!{B'z\over (B'+1)z-1}. \eeqn Inserting $y^*$ into the definition of $f_2$ and replacing the relative entropy by the sum over squares $s\leq d$ (\ref{entroineq2}), we get \beqn\textstyle f_2(y^*,z) \geq 2B'(y^*-z)^2+A'(1-y^*)-y^*{1-z\over z} = {z(1-z)\cdot g_2(z)\over [(B'+1)z-1]^2}, \eeqn \beqn\textstyle g_2(z) \;:=\; [(A'-1)B'z-A'+2z(1-z)] (B'\!+\!1\!-\!{1\over z})+2(1-z)^2. \eeqn We have reduced the problem to showing $g_2 \geq 0$. Since $(B' + 1 - {1\over z}) \geq 0$ it is sufficient to show that the bracket is positive. We solve $[...] \geq 0$ w.r.t.\ $B$ and get \beqn B\geq {1-2z(1-z)\over z}\!\cdot\!{1\over A}+{1-z\over z}. \eeqn For $B \geq \odA + 1$ this is satisfied for all $\odt \leq z \leq 1$. In summary we have proved (\ref{lossineq2}) for $B \geq \odA + 1$ and $A > 0$. \qed %------------------------------% \subsection{General loss inequality (\ref{lossineqa})}\label{appLossIneqa} %------------------------------% We reduce \beq\label{lossineqf2a} f(\vec y,\vec z):= B'\sum_{i=1}^N y_i\ln{y_i\over z_i} + A'\sum_{i=1}^N y_i \ell_{im}\!-\sum_{i=1}^N y_i \ell_{is} \;\geq\; 0 \eeq \beq\label{liac}\textstyle \mbox{for}\quad \sum_{i=1}^Nz_i d_i\geq 0, \quad d_i:=\ell_{im}-\ell_{is} \eeq to the binary $N = 2$ case. We do this by keeping $\vec y$ fixed and showing that $f$ as a function of $\vec z$ is positive at all extrema in the interior of the simplex $\Delta:=\{\vec z: \sum_iz_i=1, z_i\geq 0\}$ of the domain of $\vec z$ and ``at'' all boundaries. First, the boundaries $z_i \to 0$ are safe as $f \to \infty$ for $B' > 0$. Variation of $f$ w.r.t.\ to $\vec z$ leads to a minimum at $\vec z = \vec y$. If $\sum_i z_i d_i \geq 0$, we have \beqn f(\vec y,\vec y) \!=\! \sum_i y_i(A'\ell_{im}\!-\!\ell_{is}) \geq \sum_i y_i(\ell_{im}\!-\!\ell_{is}) = \sum_i z_id_i \geq 0. \eeqn In the first inequality we used $A'>1$. If $\sum_i z_i d_i< 0$, $\vec z = \vec y$ is outside the valid domain due to the constraint (\ref{liac}) and the valid minima are attained at the boundary $\Delta\cap P$, $P := \{\vec z:\sum_iz_id_i=0\}$. We implement the constraints with the help of Lagrange multipliers and extremize \beqn L(\vec y,\vec z) := f(\vec y,\vec z) + B'\lambda\sum z_i + B'\mu\sum z_id_i. \eeqn $\partial L/\partial z_i=0$ leads to $y_i=y_i^*:=z_i(\lambda+\mu d_i)$. Summing this equation over $i$ we obtain $\lambda=1$. $\mu$ is a function of $\vec y$ for which a formal expression might be given. If we eliminate $y_i$ in favor of $z_i$, we get \beqn\textstyle f(\vec y^*,\vec z) \;=\; \sum_i c_iz_i \qmbox{with} \eeqn \beqn c_i:=(1+\mu d_i)(B'\ln(1+\mu d_i)+A'\ell_{im}-\ell_{is}). \eeqn In principle $\mu$ is a function of $\vec y$ but we can treat $\mu$ directly as an independent variable, since $\vec y$ has been eliminated. The next step is to determine the extrema of the function $f=\sum c_iz_i$ for $\vec z\in\Delta\cap P$. For clearness we state the line of reasoning for $N=3$. In this case $\Delta$ is a triangle. As $f$ is linear in $\vec z$ it assumes its extrema at the vertices of the triangle, where all $z_i=0$ except one. But we have to take into account a further constraint $\vec z\in P$. The plane $P$ intersects triangle $\Delta$ in a finite line (for $\Delta\cap P=\{\}$ the only boundaries are $z_i\to 0$ which have already been treated). Again, as $f$ is linear, it assumes its extrema at the ends of the line, i.e. at edges of the triangle $\Delta$ on which all but two $z_i$ are zero. With a similar line of arguments for $N>3$ we conclude that a necessary condition for a minimum of $f$ at the boundary is that at most two $z_i$ are non-zero. But this implies that all but two $y_i$ are zero. If we had eliminated $\vec z$ in favor of $\vec y$, we could not have made the analogous conclusion because $y_i=0$ does not necessarily imply $z_i=0$. We have effectively reduced the problem of showing $f(\vec y^*,\vec z)\geq 0$ to the case $N=2$. We can go back one step further and prove (\ref{lossineqf2a}) for $N=2$, which implies $f(\vec y^*,\vec z)\geq 0$ for $N=2$. A proof of (\ref{lossineqf2a}) for $N=2$ implies, by the arguments given above, that it holds for all $N$. This is what we set out to show here. \qed The $N=2$ case has been proven in the previous paragraphs. This completes the proof of Theorem \ref{thULoss}. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Instantaneous Losses}\label{secILoss} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Since $L_n^{\Lambda_\xi} - L_n^{\Lambda_\mu}$ is not finitely bounded by Theorem \ref{thULoss} it cannot be used directly to conclude analogously $l_t^{\Lambda_\xi} - l_t^{\Lambda_\mu} \to 0$. It would follow from $\xi_t\to\mu_t$ by continuity if $l_t^{\Lambda_\xi}$ and $l_t^{\Lambda_\mu}$ were continuous functions of $\xi_t$ and $\mu_t$. $l_t^{\Lambda_\mu}$ is a continuous piecewise linear concave function, but $l_t^{\Lambda_\xi}$ is an, in general, discontinuous function of $\xi_t$ (and $\mu_t$). Fortunately it is continuous at the one necessary point $\xi_t=\mu_t$. This allows to bound $l_t^{\Lambda_\xi} - l_t^{\Lambda_\mu}$ in terms of $\xi_t-\mu_t$. %------------------------------% \ftheorem{thILoss}{Instantaneous Loss Bound}{ %------------------------------% Under the same conditions as in Theorem \ref{thULoss}, for discrete $\M$ the following relations hold for the instantaneous losses $l_t^{\Lambda_\mu}(x_{