   6.0017 \,  11.9993
& 
    0.2618   \, 0.1117 \,   0.0933
\\ \hline
$z\ped{o}\apex{wc}$ &  
   -2.0007  \,  6.0005 \,  12.0006
& 
    0.0420  \,  0.0183  \,  0.0151
\\ \hline
$z\ped{o}\apex{pr}$  &  
   -2.0008  \,  6.0004 \,  12.0004
& 
    0.0364  \,  0.0162  \,  0.0140
\\ 
\hline
$\|z\ped{o}\apex{ls}-z\apex{true}\|_{\infty}$   & 
   0.4764&    0.0762\\
\hline
$\|z\ped{o}\apex{wc}-z\apex{true}\|_{\infty}$   & 
    0.1864&    0.0148\\
\hline
$\|z\ped{o}\apex{pr} -z\apex{true}\|_{\infty} $ & 
    0.1725&    0.0134\\
\hline
\hline
\end{tabular}}
\end{center}
\label{default}
\end{table}%


\begin{figure}[ht]
\centerline{
\includegraphics[width=22cm]{hist3.eps}
}
\caption{Relative frequencies for least-square estimates (cyan), worst-case optimal estimate (blue) and probabilistic-optimal (green). To allow comparison, the histograms have been normalized so that so that the area under the bars is equal to one.
\label{fig-es-compare}}
\end{figure}





\section{Conclusions}
\label{sec-conclusions}
This paper deals with the rapprochement between the stochastic and worst-case settings for system identification. The problem is formulated within the probabilistic setting of information-based complexity, and it is focused on the idea of discarding sets of small measure from the set of deterministic estimates. The paper establishes rigorous optimality properties of a trade-off curve, called \textit{violation function}, which  shows how the radius of information decreases as a function of the accuracy.  Subsequently, randomized and deterministic algorithms for computing the optimal violation function  have been presented. Their performance has been successfully tested on a numerical example.

\section{Acknowledgements}
The authors would like to thank Prof.\ Takayuki Wada for the enlightening discussions about stochastic optimization, and for clarifying the quasi-concavity properties in Theorem \ref{th-difference}, and Prof.\ Libor Vesely for clarifying properties of the Chebychev center of convex sets. The authors are also indebted to the anonymous reviewers for the numerous comments that allowed to improve the content of the paper.

\appendices

\section{Proof of Theorem \ref{theorem1}}
\label{app-theorem1}

Consider the transformation matrix  $T=\left[T_{1}\; T_{2}\right]$, where $T_{1}$  is an orthonormal basis of the column space of ${\cal I}$
and  $T_{2}$ is an orthonormal basis of the null space of  ${\cal I}^{\top}\!$.
Furthermore, define the linear transformation $\bar {\eta}\doteq T^{\top}\! {\eta}$, and
 the set $\bar \mathcal{N} \doteq \left\{\bar {\eta} \in\Real{m} \,:\, T^{-\!\top}\bar {\eta} \in \mathcal{N}\right\}$.
Then, if the random variable ${\eta}$  is uniform on $\mathcal{N}$,
the linearly transformed random variable $\bar {\eta}$ is uniform on $\bar \mathcal{N}$
(see e.g.\ \cite{Halmos:50}). 
Next, by multiplying equation (\ref{meas}) from the left by $T^{\top}\!\!\!$, and defining
$\bar {\cal I}_{1}\doteq T_{1}^{\top}\! {\cal I}$ and $\bar y_{i}\doteq T_{i}^{\top}\! y$,
$\bar {\eta}_{i}\doteq T_{i}^{\top}\! {\eta}$, $i=1,2$, we get
\begin{equation}
\label{qqq}
\left\{
\begin{array}{lcll}
\bar {\cal I}_{1}x &+ &\bar {\eta}_{1} &= \bar y_{1}\\
&&\bar {\eta}_{2} &= \bar y_{2},
\end{array}
\right.
\end{equation}
since, by construction,  $T_{2}^{\top}\! {\cal I} =0$.
It follows from definition (\ref{set}) that a point $x\in X$ belongs to ${\cI^{-1}_{y}} $ if and only if there exists  
$\bar {\eta}=\left[
\begin{smallmatrix}
\bar {\eta}_{1}\\
\bar {\eta}_{2}
\end{smallmatrix}
\right]\in \bar \mathcal{N}$ such that  (\ref{qqq}) holds, i.e.\ if there exist $\bar {\eta}_{1}$ in the  set
$
\bar \mathcal{N}_{1}
\doteq
\left\{
\bar {\eta}_{1} \in \Real{n}\,:\,
\left[
\begin{smallmatrix}
\bar {\eta}_{1}\\
\bar y_{2}
\end{smallmatrix}
\right]\in\bar \mathcal{N}
\right\}
$
for which $\bar {\cal I}_{1}x + \bar {\eta}_{1} = \bar y_{1}$.
Note that the set $\bar \mathcal{N}_{1}$ represents the intersection of the set $\bar \mathcal{N}$ with the hyperplane $
\left\{
\bar {\eta} = \left[
\begin{smallmatrix}
\bar {\eta}_{1}\\
\bar {\eta}_{2}
\end{smallmatrix}
\right]\in\Real{m}
\,:\,\bar {\eta}_{2}=\bar y_{2}\right\}$.
Since $\bar {\eta}$ is uniform on $\bar \mathcal{N}$, it is also uniform on any subset of $\bar \mathcal{N}$, and in particular on this intersection set.
Hence, $\bar {\eta}_{1}$ is uniformly distributed on $\bar \mathcal{N}_{1}$.

Statement (i) is proved noting that, from (\ref{qqq}), an element $x\in{\cI^{-1}_{y}} \subset\Real{n}$ can be written as the  mapping of  $\bar {\eta}_{1}\in\bar \mathcal{N}_{1}\subset\Real{m}$
through the one-to-one affine transformation $x={\cal I}_{1}^{-1}(\bar {\eta}_{1}-\bar y_{1})$. Since bijective linear transformations preserve uniformity \cite{PapPil:02}, it follows that the random variable $x$ is uniformly distributed on ${\cI^{-1}_{y}} $.

Point (ii) follows immediately from the fact that the image of a uniform density through a linear operator $\Real{n}\to\Real{s}$ with $s\le n$ is log-concave (see e.g.\ \cite{PapPil:02}).
\hfill $\square$

\section{Proof of Theorem \ref{th-difference}}
\label{app-th-difference}

To prove point (i), we first 
consider equation  (\ref{vr-opt}). Recalling that ${\mu}_{\Q}$ is the uniform measure over~$\mathcal{N}$, we  write
\begin{eqnarray*}
\lefteqn{
v\ped{o}(r)
=\inf_{{\cal A}}\frac{\vol{ \left\{x \in {\cI^{-1}_{y}} \,:\, \|{\cal S}  x - {\cal A}(y) \| > r \right\}}}{\vol{{\cI^{-1}_{y}} }}   }  \\
&=&\frac{1}{\vol{{\cI^{-1}_{y}} }}\inf_{z\ped{c}} \vol{
\left\{x \in {\cI^{-1}_{y}}  \,:\, \|  {\cal S} x 
- z\ped{c} \| > r 
\right\} } \nonumber \\
&=&\frac{1}{\vol{{\cI^{-1}_{y}} }}\inf_{z\ped{c}} \vol{ 
\left\{x \in {\cI^{-1}_{y}}  \,:\,   x\not\in   \cC(z\ped{c},r)
\right\} } \nonumber \\
&=&\frac{1}{\vol{{\cI^{-1}_{y}} }}\inf_{z\ped{c}} \vol{ 
{\cI^{-1}_{y}}  
\setminus  \cC(z\ped{c},r)}.
\label{Dx}
\end{eqnarray*}
Next, we