text:
\section{Introduction}
One of the most common problems in statistics is linear regression. Given
$p$ samples of
$n$-dimensional input data $x_i^\mu, i=1,\ldots,n$ and 1-dimensional output
data $y^\mu$, with $\mu=1,\ldots,p$, find weights $w_i, w_0$ that best
describe the relation
\begin{align}
\label{eq:regress}
y^\mu = \sum_{i=1}^n w_i x_i^\mu + w_0+\xi^\mu
\end{align}
for all $\mu$. $\xi^\mu$ is zero-mean noise with inverse variance $\beta$.

The ordinary least square (OLS) solution is given by $\vw = \chi^{-1} \vb$
and $w_0=\bar{y}-\sum_i w_i \bar{x}_i$,
where $\chi$ is the input covariance matrix $\vb$ is the vector of
input-output covariances and $\bar{x}_i, \bar{y}$ are the mean values.
There are several problems with the OLS approach. When $p$ is small, it
typically has a low prediction accuracy due to over fitting. In particular,
when $p<n$, $\chi$ is not of maximal rank and so its inverse is not uniquely defined.
In addition, the OLS solution is not sparse: it will find a solution $w_i\ne 0$
for all $i$. Therefore, the interpretation of the OLS solution is often
difficult.

These problems are well-known, and there exist a number of approaches
to overcome these problems.
The simplest approach is called ridge regression. It adds a
regularization term $\frac{1}{2}\lambda \sum_i w_i^2$ with $\lambda>0$
to the OLS criterion. This has the effect that the input covariance matrix $\chi$ gets
replaced by $\chi +\lambda I$ which is of maximal rank for
all $p$. One optimizes $\lambda$ by cross validation. Ridge regression
improves the prediction accuracy but not the interpretability of the
solution.

Another approach is Lasso \cite{tibshirani96}. It solves the OLS
problem under the linear constraint $\sum_i |w_i|\le t$. This problem
is equivalent to adding an $L_1$ regularization term $\lambda \sum_i
|w_i|$ to the OLS criterion. The optimization of the quadratic error
under linear constraints can be solved efficiently.
See \cite{friedman2009}
for a recent account.  Again, $\lambda$ or $t$ may be found through
cross validation.  The advantage of the $L_1$ regularization is that
the solution tends to be sparse. This improves both the prediction
accuracy and the interpretability of the solution.

The $L_1$ or $L_2$ regularization terms are known as shrinkage priors because
their effect is to shrink the size of $w_i$.  The idea of shrinkage prior has
been generalized by \cite{frank1993} to the form $\lambda \sum_i |w_i|^q$ with
$q>0$ and $q=1,2$ corresponding to the Lasso and ridge case, respectively.
Better solutions can be obtained for $q<1$, however the resulting optimization
problem is no longer convex and therefore more difficult to solve.

An alternative Bayesian approach to obtain a sparse solution using an $L_0$
penalty was proposed by \cite{george1993}. They introduce $n$ variational
selector variables $s_i$ such that the prior distribution over $w_i$ is a
mixture of a narrow (spike) and wide (slab) Gaussian distribution, both
centered on zero. The posterior distribution over $s_i$ indicates whether the
input feature $i$ is included in the model or not.  Since the number of subsets
of features is exponential in $n$, for large $n$ one cannot compute the
solution exactly. In addition, the posterior is a complex high dimensional
distribution of the $w_i$ and the other (hyper) parameters of the model.  The
computation of the posterior requires thus the use of MCMC sampling
\cite{george1993} or  a variational Bayesian approximation
\cite{titsias2012,logsdon2010,Yoshida,lobato}.

Although Bayesian approaches tend to over fit less than a maximum likelihood or
maximum a posteriori method (MAP approach), they also tend  to be relatively
slow.  Here we propose a partial Bayesian approach, where we apply a
variational approximation to integrate out the binary (selector) variables in combination
with a MAP approach for the remaining parameters.  For clarity, we analyse this
idea in its most simple form, in the absence of (hierarchical) priors. Instead,
we infer the sparsity prior through cross validation. As we will motivate
below, we call the method the Variational Garrote (VG).

The paper is organized as follows. In section~\ref{variational} we
introduce the model and we derive the variational approximation.
We show that the combination of the variational approximation and
$L_0$ regularization has the effect of making the problem effectively
of maximal rank by introducing a 'variational ridge term'. As a
result, the solution is well defined even when $p<n$ as long as the
number of predictive features is less than $p$ (which is controlled
by the sparsity prior).

To gain further insight,  in section~\ref{univariate} we
study the case when the design matrix is orthogonal. In this case the
solution can be computed exactly in closed form with no need to resort to approximations.
In the variational approximation, we show for the uni-variate case that the solution is
either unique or has two solutions, depending on the input-output
correlations, the number of samples $p$ and on the sparsity prior
$\gamma$. We derive a phase plot and show that the solution is
unique, when the sparsity prior is not too strong {\em or} when the
input-output correlation is not too large.  The input-output behavior
of the VG is shown to be close to optimal as a smoothed version of
hard feature selection. We argue that this behavior also holds
in the multi-variate case.

In section~\ref{numerical} we compare the VG with a number of other MAP
methods, such as Lasso and ridge regression and with the paired mean field
method (PMF) \cite{titsias2012}, a recently proposed variational bayesian
method.  We show that the VG and PMF significantly outperform the Lasso and
ridge regression on a large number of different examples both in terms of the
accuracy of the solution, as well as in prediction error.  In addition, we show
that the VG do not suffer from the inconsistency of the Lasso method when the
input correlations are large.  We show in detail how all methods compare as a
function of the level of noise, the sparsity of the target solution, the number
of samples and the number of irrelevant predictors.   Globally, VG is
significantly faster than PMF and tends to perform better as the
problems become denser and in problems with strongly correlated inputs.

\section{The variational approximation}
\label{variational}
Consider the regression model of the form
\footnote{We assume from here on without loss of generality that
$\frac{1}{p}\sum_{\mu=1}^p x_i^\mu=\frac{1}{p}\sum_{\mu=1}^p y^\mu=0$}
\begin{eqnarray}
y^\mu=\sum_{i=1}^n w_i s_i x^\mu_i+\xi^\mu\qquad \sum_{i=1}^n s_i \le
t
\label{vg}
\end{eqnarray}
with $s_i=0,1$.  The bits $s_i=1$ will identify the predictive inputs
$i$.
Using a Bayesian description, and denoting the data by $D: \{\vx^\mu,y^\mu\},
\mu=1,\ldots,p$, the likelihood term is given by
\begin{align}
\label{likelihood}
p(y|\vx,\vs,\vw,\beta)&=\sqrt{\frac{\beta}{2\pi}}\exp\left(-\frac{\beta}{2}\left(y-\sum_{i=1}^n
w_i s_i x_i\right)^2\right)\nonumber\\
p(D|\vs,\vw,\beta)&=\prod_\mu p(y^\mu|\vx^\mu,\vs,\vw,\beta)\notag\\
&=\left(\frac{\beta}{2\pi}\right)^{p/2}\exp\left(-\frac{\beta p}{2}\left(\sum_{i,j=1}^n
s_i s_j w_i w_j \chi_{ij}-2\sum_{i=1}^n w_i s_i b_i +\sigma_y^2\right)
\right)
\end{align}
with
$b_i=\frac{1}{p}\sum_\mu x_i^\mu y^\mu,
\sigma_y^2=\frac{1}{p}\sum_\mu (y^\mu)^2,
\chi_{ij}=\frac{1}{p}\sum_\mu x_i^\mu x_j^\mu$.

We should also specify prior distributions over $\vs,\vw,\beta$.
For concreteness, we assume that the prior over $\vs$ is factorized
over the individual $s_i$, each with identical prior probability:
\begin{align}
\label{prior}
p(\vs|\gamma)& =\prod_{i=1}^n p(s_i|\gamma)  &
p(s_i|\gamma)& =\frac{\exp\left(\gamma s_i\right)}{1+\exp(\gamma)}
\end{align}
with $\gamma$ given which specifies the sparsity of the solution.
We denote by $p(\vw,\beta)$ the prior over
the inverse noise variance $\beta$ and the feature weights $\vw$. We will
leave this prior unspecified since its choice does not affect the variational approximation.
\footnote{
It can be shown that the regression model specified by Eqs.~\ref{likelihood} and~\ref{prior} is identical to the spike and slab model, with the difference that the latter usually contains a (Gaussian) prior over the $w_i$ which could also be added in the above representation\cite{titsias2012}. See appendix~\ref{sec:pmf} for details.

}

The posterior becomes
\begin{eqnarray}
p(\vs,\vw,\beta|D,\gamma)=\frac{p(\vw,\beta)p(\vs|\gamma)p(D|\vs,\vw,\beta)}{p(D|\gamma)}
\label{posterior}
\end{eqnarray}
Computing the MAP estimate or computing statistics from the
posterior is complex in particular due to the discrete nature or $\vs$.  We propose
to compute a variational approximation to the marginal posterior
$p(\vw,\beta|D,\gamma)=\sum_{\vs} p(\vs,\vw,\beta|D,\gamma)$ and computing the
MAP solution with respect to $\vw,\beta$. Since $p(D|\gamma)$ does not depend on
$\vw,\beta$ we can ignore it.

\iffalse
The model as specified by the likelihood
Eq.~\ref{likelihood} and the prior Eq.~\ref{prior} is related
to the spike and slab model \cite{george1993} in the following sense.
The spike and slab
model has a quadratic likelihood $p(D|\vw',\beta)$ that does not depend on selector
variables. Instead, it has a prior $p(\vw'|\vs)$ that depends on selector bits
$\vs$ so that the posterior over $\vw',\vs$ is proportional to
\begin{eqnarray*}
\exp\left(-\frac{\beta}{2}\sum_\mu\left(y^\mu - \sum_i w'_i
x_i^\mu\right)^2-
\frac{1}{2}\sum_{i=1}^n s_i \beta_+
(w'_i)^2-\frac{1}{2}\sum_{i=1}^n (1-s_i) \beta_- (w'_i)^2+\gamma \sum_i s_i \right)
\end{eqnarray*}
with $\beta_\mp$ the spike and slab precisions, respectively. By making the
substitution $w_i'=w_i s_i$, this expression becomes
\begin{eqnarray*}
\exp\left(-\frac{\beta}{2}\sum_\mu\left(y^\mu - \sum_i s_i w_i
x_i^\mu\right)^2-
\frac{1}{2}\sum_{i=1}^n s_i \beta_+
w_i^2+\gamma \sum_i s_i \right)
\end{eqnarray*}
where we have used that $s_i^2=s_i$ and $s_i(1-s_i)=0$.  This
expression is identical to the Garrote Eq.~\ref{posterior} in the
limit of infinitely wide slab ($\beta_+=0$). The Garrote
parametrization has the advantage over the spike-and-slab
parametrization that it does not require the spike prior involving the
large constant $\beta_-$ or, equivalently, a delta distribution for
$w'_i$.
\fi

The posterior distribution Eq.~\ref{posterior} for given $\vw,\beta$ is a
typical Boltzmann distribution involving terms linear and quadratic in $s_i$.
It is well-known that when the effective couplings $w_i w_j \chi_{ij}$ are
small, one can obtain good approximations using methods that originated in the
statistical physics community and where $s_i$ denote binary spins. Most
prominently, one can use the mean field or variational approximation
\cite{jordan1998}, the TAP approximation \cite{kap99e} or belief propagation
(BP) \cite{murphy99}.  For introductions into these methods also see
\cite{opper2001a,wainwright2008}.  Here, we will develop a solution based on
the simplest possible variational approximation and leave the possible
improvements using BP or structured mean field approximations to the future.

We approximate the sum by the variational bound using Jensen's inequality.
\begin{align}
\label{bound}
\log \sum_{\vs}p(\vs|\gamma)p(D|\vs,\vw,\beta)& \ge -\sum_{\vs} q(\vs) \log
\frac{q(\vs)}{p(\vs|\gamma)p(D|\vs,\vw,\beta)}\notag\\&=-F(q,\vw,\beta)
\end{align}
$q(\vs)$ is called the variational approximation and can be any
positive probability distribution on $\vs$ and $F(q,\vw,\beta)$ is called the variational
free energy.
The optimal $q(\vs)$ is found by
minimizing $F(q,\vw,\beta)$ with respect to $q(\vs)$ so that the
tightest bound - best approximation - is obtained.

In order to be able to compute the variational free energy efficiently,
$q(\vs)$ must be a tractable probability distribution, such as a chain or a
tree with limited tree-width \cite{barber98b}. Here we consider the simplest
case where $q(\vs)$ is a fully factorized distribution: $q(\vs)=\prod_{i=1}^n q_i(s_i)$ with $q_i(s_i)=m_i s_i
+(1-m_i)(1-s_i)$, so that $q$ is fully specified by the expected values
$m_i=q_i(s_i=1)$, which we collectively denote by $\vm$.
The expectation values with respect to $q$ can now be easily evaluated
and the result is
\begin{align}
\label{F}
F&=
\frac{\beta p}{2}\left(\sum_{i,
j}^n m_i m_j w_i w_j \chi_{ij}+\sum_i m_i(1-m_i) w_i^2
\chi_{ii}-2\sum_{i=1}^n m_i w_i b_i
+\sigma_y^2\right)\nonumber\\
&-\gamma\sum_{i=1}^n m_i +\sum_{i=1}^n \left(m_i \log m_i+(1-m_i)\log
(1-m_i)\right)-\frac{p}{2}\log\frac{\beta}{2\pi}
\end{align}
where we have omitted terms independent of $m,\beta,w$.
The first line is due to the
likelihood term, the
second line is due to the prior on $\vs$ and the entropy of
$q(\vs)$.
The approximate marginal posterior is then
\begin{align*}
p(\vw,\beta|D,\gamma)&\propto p(\vw,\beta)\sum_{\vs}p(\vs|\gamma)p(D|\vs,\vw,\beta)\\
& \approx p(\vw,\beta)
\exp(-F(\vm,\vw,\beta,\gamma))
\end{align*}

We can compute the variational approximation $\vm$ for given
$\vw,\beta,\gamma$
by minimizing $F$ with respect to $\vm$.
In addition,
$p(\vw,\beta|D,\gamma)$ needs to be maximized with respect to
$\vw,\beta$.
Note, that the variational approximation only depends on the likelihood term and
the prior on $\gamma$, since these are the only terms that depend on $\vs$.
Thus, for given $\vw$, the variational approximation does not depend on the
particular choices for the prior $p(\vw,\beta)$.
For concreteness, we assume a flat prior $p(\vw,\beta)\propto 1$. We set
the derivatives of $F$ with
respect $\vm,\vw,\beta$ equal to zero. This gives the
following set of fixed point equations:
\begin{eqnarray}
m_i&=&\sigma\left(\gamma+\frac{\beta p}{2}w_i^2 \chi_{ii}\right)
\label{m}\\
\vw&=&(\chi')^{-1} \vb \label{v}\qquad
\chi'_{ij}=\chi_{ij}m_j+(1-m_j)\chi_{jj}\delta_{ij}\\
\frac{1}{\beta}&=&\sigma_y^2-\sum_{i=1}^n m_i w_i b_i
\label{beta}
\end{eqnarray}
with $\sigma(x)=(1+\exp(-x))^{-1}$ and where in Eq.~\ref{beta} we have
used Eq.~\ref{v}.
Eqs.~\ref{m}-\ref{beta} provide the final solution. They can be solved by fixed point iteration as outlined in
Algorithm~\ref{algorithm}: Initialize $\vm$ at random. Compute $\vw$ by
solving the linear system Eq.~\ref{v} and $\beta$ from Eq.~\ref{beta}.
Compute a new solution for $\vm$ from Eq.\ref{m}.

Within the variational/MAP approximation the predictive model is given by
\begin{eqnarray}
y&=&\sum_i m_i w_i x_i +\xi\label{prediction}
\end{eqnarray}
with $\av{\xi^2}=1/\beta$ and $\vm,\vw,\beta$ as estimated by the above procedure.
Eq.~\ref{prediction} has some similarity with Breiman's non-negative
Garrote method \cite{breiman93}. It computes the solution in a two step approach: it computes first $w_i$ using OLS and then finds $m_i$
by minimizing
\begin{eqnarray*}
\sum_\mu \left(y^\mu -\sum_{i=1}^n x_i^\mu w_i m_i\right)^2\quad
\mathrm{subject~to}\quad  m_i\ge 0\quad \sum_i m_i \le t
\end{eqnarray*}
Because of this similarity, we refer to our method as the variational
Garrote (VG).
Note, that because of the OLS step the non-negative garrote requires that $p\ge
n$.  Instead, the variational solution Eqs.~\ref{m}-\ref{beta} computes the
entire solution in one step (and as we will see does not require $p\ge n$).

Let us pause to make some observations about this solution. One
might naively expect that the variational approximation would simply
consist of replacing $w_i s_i$ in Eq.~\ref{vg} by its variational
expectation $w_i m_i$. If this were the case, $\vm$ would
disappear entirely from the equations and one would expect in Eq.~\ref{v} the OLS solution with the
normal input covariance matrix $\chi$ instead of the new matrix
$\chi'$ (note, that in the special case that $m_i=1$ for all $i$,
$\chi'=\chi$ and Eq.~\ref{v} does reduce to the OLS
solution).
Instead, $\vm$ and
$\vw$ are both to be optimized, giving in general a
different solution than the OLS solution \footnote{The technical reason that
this does not occur is that in the computation of the expectation with respect to the distribution $q$
that results in Eq.~\ref{F}
one has $\av{s_i s_j}=m_i m_j$ for $i\ne j$, but
$\av{s_i^2}=\av{s_i}=m_i$.}.

When $m_i<1$, $\chi'$ differs from $\chi$ by rescaling with $m_i$ and adding a positive
diagonal to it, a 'variational ridge'. This is similar to the mechanism of ridge regression,
but with the important difference that the diagonal term depends
on $i$ and is dynamically adjusted depending on the solution for
$\vm$.  Thus, the sparsity prior together with variational approximation
provides a mechanism that solves the rank problem.
When all $m_i<1$, $\chi'$ is of maximal rank. Each $m_i$ that approaches 1,
reduces the rank by one.
Thus, if $\chi$ has rank $p<n$, $\chi'$ can be still of rank $n$
when no more than $p$ of the $m_i=1$, the remaining $n-p$ of the $m_i<1$
making up for the rank deficiency. Note, that the size of $m_i$ (and thus the rank
of $\chi'$) is
controlled by $\gamma$ through Eq.~\ref{m}.

In the above procedure, we compute the VG solution for fixed $\gamma$
and choose its optimal value through cross validation on independent
data \cite{mitchell1988}. This has the advantage that our result
is independent of our (possibly incorrect) prior belief.

But another important advantage of varying $\gamma$ manually is
that it helps to avoid local minima.  When we increase $\gamma$
from a negative value $\gamma_\mathrm{min}$ to a maximal value  $\gamma_\mathrm{max}$
in small steps, we obtain a sequence
of solutions with decreasing sparseness. These solutions will better
fit the data and as a result $\beta$ increases with $\gamma$. Thus,
increasing $\gamma$ implements an annealing mechanism where we
sequentially obtain solutions at lower noise levels. We found
empirically that this approach is effective to reduce the problem
of local minima. To further deal with the effect of hysteresis (see
section~\ref{univariate}) we
recompute the solution  from $\gamma_\mathrm{max}$ down to
$\gamma_\mathrm{min}$ and choose the solution with lowest free
energy.

The minimal value of $\gamma$ is chosen as the largest value such that
$m_i=\epsilon$, with $\epsilon$ small. We find from
Eqs.~\ref{m}-\ref{beta} that
\begin{eqnarray}
\gamma_\mathrm{min} =-\frac{p
b_i^2\chi_{ii}}{2\sigma_y^2}+\sigma^{-1}(\epsilon)+{\cal O}(\epsilon)\label{gamma_min}
\end{eqnarray}
with $\sigma^{-1}(x)=\log(x/(1-x))$.
We heuristically set the maximal value of $\gamma$ as well as the step
size.

In appendix~\ref{dual} we provide an alternative fixed point iteration
scheme that is more efficient in the large $n$ small $p$ limit.
Whereas Eqs.~\ref{m}-\ref{beta} require the repeated solution of
a $n$-dimensional linear system, the dual formulation,
Eqs.~\eqref{m},\eqref{w2},\eqref{A}-\eqref{lambda1}, requires the repeated
solution of a $p$ dimensional linear system.
Algorithm \ref{algorithm} summarizes the VG method.

\begin{algorithm}
\SetKwFunction{VG}{VG}\SetKwFunction{VG}{VG}
 \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
 \SetKwInOut{Function}{function}
 \SetKwInOut{Output}{output}
\Input{Data $D: \{\vx^\mu,y^\mu\},\mu=1,\ldots,p$ ; $\epsilon$ and step-size $\Delta \gamma$}
\Output{$\vw,\vm,\beta,\gamma$ solution with minimal cross validation error }
\nl Preprocess data such that $\sum_\mu x_i^\mu=\sum_\mu y^\mu=0$ and partition $D$ in $D^{\text{train}}$, $D^{\text{val}}$\\
\nl Compute $b_i =\frac{1}{p}\sum_\mu x_i^\mu y^\mu$ and if $n<p$ compute $\chi_{ij}=\frac{1}{p}\sum_\mu x_i^\mu x_j^\mu$\\
\nl Compute $\gamma_\mathrm{min}$ from $\epsilon$
 and $\gamma_\mathrm{max}$ from $\gamma_\mathrm{min}$ and $\Delta\gamma$ \\
\nl \For(// FORWARD PASS){$\gamma=\gamma_\mathrm{min}:\Delta \gamma:\gamma_\mathrm{max}$}
{
\nl $\eta\leftarrow 1$\\
\nl \While{not converged}{
\nl Compute $\vw,\beta$ from Eqs.~\eqref{v}-\eqref{beta} ($n<p$)
	or Eqs.~\eqref{w2},~\eqref{A}-\eqref{lambda1} ($n>p$)\
\nl Compute $\vm'$ using a smoothed version of Eq.~\eqref{m}: $m_i'\leftarrow (1-\eta) m_i + \eta \sigma(\ldots)$\\
\nl \If{$\max_i |m_i'-m_i|>0.1$}{
\nl $\eta\leftarrow \eta/2$}
\nl $\vm\leftarrow\vm'$\\
}
\nl    Store solution $(\vw_1,\vm_1,\beta_1)_\gamma$ and $F_1(\gamma)\leftarrow F((\vw_1,\vm_1,\beta_1)_\gamma)$ from Eq.~\eqref{F}\\
}
\nl \For(// BACKWARD PASS){$\gamma=\gamma_\mathrm{max}:-\Delta \gamma:\gamma_\mathrm{min}$}
{
\nl As $\mathbf{5}-\mathbf{11}$\\
\nl    Store solution $(\vw_2,\vm_2,\beta_2)_\gamma$ and $F_2(\gamma)\leftarrow F((\vw_2,\vm_2,\beta_2)_\gamma)$ from Eq.~\eqref{F}\\
}
\nl \For{$\gamma=\gamma_\mathrm{min}:\Delta \gamma:\gamma_\mathrm{max}$}{
\nl Choose solution $(\vw,\vm,\beta)_\gamma$ that has minimal $F_{1,2}(\gamma)$\\
\nl     Compute cross validation error on $D^{\text{val}}$ using Eq.~\eqref{prediction} \\
 }
\nl Select $\vw,\vm,\beta,\gamma$ with minimal cross validation error\\
\caption{The Variational Garrote algorithm.}\label{algorithm}
\end{algorithm}

\section{Orthogonal and uni-variate case}
\label{univariate}
In order to obtain further insight in the solution, consider the case in
which the inputs are uncorrelated: $\chi_{ij}=\delta_{ij}$. In this
case, we can derive the MAP solution of Eq.~\ref{posterior} exactly, without the need to
resort to the variational approximation. Eq.~\ref{posterior}
reduces to a distribution that factorizes over $i$ with
log probability proportional to
\begin{eqnarray*}
L=\frac{p}{2}\log\beta-\frac{\beta p}{2}\left(\sum_{i=1}^n s_i
(w_i^2-2w_i b_i)
 +\sigma_y^2\right)+\gamma \sum_{i=1}^n s_i
\end{eqnarray*}
Maximizing wrt $w_i,\beta$ yields $w_i=b_i$,
$\beta^{-1}=\sigma_y^2-\sum_{i=1}^n s_i
b_i^2$ and
\begin{eqnarray*}
L=\frac{p}{2}\log\beta+\sum_{i=1}^n s_i \left(\frac{\beta
p}{2}b_i^2+\gamma\right)-\frac{\beta p}{2} \sigma_y^2
\end{eqnarray*}
Assume without loss of generality that $b_i^2$ are sorted in decreasing order. $L$ is maximized by setting $s_i=1$ when $\frac{\beta
p}{2}b_i^2+\gamma>0$ and $s_i=0$ otherwise. Thus, the optimal solution
is $s_{1:k}=1, s_{k+1:n}=0$, $\beta^{-1}=\sigma_y^2-\sum_{i=1}^k
b_i^2$ with $k$ the smallest integer such that
\begin{eqnarray}
\frac{\beta p}{2}b_{k+1}^2+\gamma <0
\label{switch_exact}
\end{eqnarray}
By varying $\gamma$ from small to large, we find a sequence of
solutions with decreasing sparsity.

In the variational approximation the solution is very similar but not identical. Eq.~\ref{v} gives the same solution
$w_i=b_i$. Eqs.~\ref{m} and~\ref{beta} become
\begin{eqnarray*}
m_i&=&\sigma\left(\gamma+\frac{\beta p}{2}b_i^2\right)\\
1/\beta&=&\sigma_y^2-\sum_i b_i^2 m_i
\end{eqnarray*}
which we can interpret as the variational approximations of
Eq.~\ref{switch_exact}, with $m_{1:k}\approx 1$ and $m_{k+1:n}\approx
0$.
The term $\sum_i b_i^2 m_i$ is the explained variance and is subtracted from
the total output variance to give an estimate of the noise variance
$1/\beta$.
\iffalse
When $m_i=1$, the explained variance is maximal.
The Garrote solution with $0\le m_i \le 1$ has reduced explained variance
with (hopefully) a better prediction accuracy and interpretability.
\fi

Note that the posterior is factorized in $s_i$, the variational approximation is not identical to the exact map solution Eq.~\ref{switch_exact}, although the results are very similar. The relation is $s_i=0 \Leftrightarrow m_i < 0.5$ and $s_i=1 \Leftrightarrow m_i > 0.5$.

In order to further analyze the variational solution, we consider the
$1$-dimensional case. The variational equations become
\begin{eqnarray}
m&=& \sigma\left(\gamma + \frac{p}{2}
\frac{\rho}{1-\rho m}\right)=f(m)\label{univ1}\\
\frac{1}{\beta}&=&\sigma^2_y(1-m \rho)\label{univ2}
\end{eqnarray}
with $\rho=b^2/\sigma_y^2$ the squared correlation coefficient.

In Eq.~\ref{univ1}, we have eliminated $\beta$ and we must find a
solution for $m$ for this non-linear equation. We see that it depends
on the input-output correlation $\rho$, the number of samples $p$ and
the sparsity $\gamma$.
For $p=100$, the solution for different $\rho,\gamma$ is
illustrated in figure~\ref{file4b} (see appendix~\ref{appendix:univ}).
\begin{figure}
\begin{center}
\includegraphics[width=0.6\textwidth]{fig_univariate}
\end{center}
\caption{
Phase plot $\rho,\gamma$ for $p=100$ giving the different solutions for $m$.
Dashed and dot-dashed lines for $\rho>\rho^*=0.28$ are from
Eq.~\ref{appendix_univ2} where two solutions for $m$ exist. Solid line for
$\rho<\rho^*$ is the solution for
$\gamma$ when $m=1/2$, to indicate the transition from the unique solution
$m\approx 0$ to the unique solution $m\approx 1$.
Dotted line is the exact transition from $s=0$ to $s=1$ from
Eq.~\ref{switch_exact}.
Insets indicate solutions for $m$ versus $\rho$ for $\gamma=-10,p=100$ (top-right)
and for $\gamma=-40,p=100$ (bottom-left).
In the lower left corner of the insets, the unique solution $m\approx 0$ is found. In the top
right corner, the unique solution $m\approx 1$ is found. Between the dot-dashed and the dashed line, the two variational solutions $m\approx 0$ and $m\approx 1$ co-exist.
}
\label{file4c}
\end{figure}
Eq.~\ref{univ1} has one or three solutions for $m$, depending on the values of
$\gamma,\rho,p$.
The three solutions correspond to two local
minima and one local maximum of the free energy $F$.
For $\gamma=-40$ and $\gamma=-10$, we plot the stable solution(s) for different values of
$\rho$ in the inserts in fig.~\ref{file4c}.
The best variational solution for $m$ is given by the
solution with the lowest free energy, indicated by the solid lines in
the inserts in fig.~\ref{file4c}.

Fig.~\ref{file4c} further shows the phase plot of $\gamma,\rho$ that indicates that the
variational solution is unique for $\gamma>\gamma^*$ or for $\rho<\rho^*$.
The solid line for $0<\rho<\rho^*$
in fig.~\ref{file4c}
indicates a smooth (second
order) phase transition from $m=0$ to $m=1$.
For $\rho>\rho^*$, the
transition from $m=0$ to $m=1$ is discontinuous: for each $\rho$ there is
a range of values of
$\gamma$ where two variational solutions $m\approx 0$ and $m\approx 1$ co-exist.
For comparison, we also show the line $\gamma=-p\rho/2$ that separates the
solution $s=0$ and $s=1$ according the the exact (non-variational) solution
Eq.~\ref{switch_exact}.

The multi-valued variational solution results in a hysteresis effect.  When the
solution is computed for increasing $\gamma$, the $m\approx 0$ solution is
obtained until it no longer exists. If the sequence of solutions is computed
for decreasing $\gamma$ the $m\approx 1$ solution is obtained for values of
$\gamma$ where previously the $m\approx 0$ solution was obtained.

From this simple one-dimensional case we may infer
that the variational
approximation is relatively easy to compute in the uni-modal region (small $\rho$
or $\gamma$ not too negative) and becomes more inaccurate in the region where
multiple minima exist (region between the dot-dashed and dashed lines in fig.~\ref{file4c}) .

It is interesting to compare the uni-variate solution of the variational garrote with ridge
regression, Lasso or Breiman's Garrote, which was previously done for the
latter three methods in \cite{tibshirani96}. Suppose that data are generated from
the model $y=w x + \xi$ with $\av{\xi^2}=\av{x^2}=1$. We compare the solutions as a
function of $w$. The OLS solution is approximately given by $w_\mathrm{ols}\approx
\av{x y}=w$, where we ignore the statistical deviations of order $1/p$ due to the finite
data set size. Similarly, the ridge
regression solution is given by $w_\mathrm{ridge}\approx \lambda w$, with $0<
\lambda < 1$ depending on the ridge prior.
The Lasso solution (for non-negative $w$) is given by
$w_\mathrm{lasso}=(w-\gamma)^+$ \cite{tibshirani96}, with $\gamma$ depending on the
$L_1$ constraint.
Breiman's Garrote solution is given by $w_\mathrm{garrote}=(1-\frac{\gamma}{w^2})^+ w$
\cite{tibshirani96}, with $\gamma$ depending on the
$L_1$ constraint. The VG solution is given by $w_\mathrm{vg}=m w$,
with $m$ the solution of Eq.~\ref{univ1}. Note, that the VG solution
depends, in addition to $w,\gamma$, on the unexplained variance $\sigma_y^2$ and the number of
samples $p$, whereas the other methods do not.

The qualitative difference of the solutions is shown in fig.~\ref{file5a}.
\begin{figure}
\begin{center}
\includegraphics[width=0.5\textwidth]{fig_overshrinkage}
\end{center}
\caption{Uni-variate solution for different regression methods. All methods yield a
shrinked solution (deviation from diagonal line). Variational Garrote (VG) with
$\gamma=-10, p=100$ and $\sigma_y^2=1$. Ridge regression with $\lambda=0.5$. Garrote with
$\gamma=1/4$. Lasso with $\gamma=1/2$.
}\label{file5a}
\end{figure}
The ridge regression solution is off by a constant multiplicative factor.
The Lasso solution is zero for small $w$ and for larger $w$ gives a solution that
is shifted downwards by a constant factor.
Breiman's Garrote is identical to the Lasso for small $w$ and shrinks less for larger
$w$. The VG gives an almost ideal behavior and can
be interpreted as a soft version of variable selection: For small
$w$ the solution is close to zero and the variable is ignored, and
above a threshold it is identical to the OLS solution.

The qualitative nature of the phase plot fig.~\ref{file4c} and the
input-output behavior fig.~\ref{file5a} extends to the multi-variate
orthogonal case. The symmetry breaking of feature $i$ is independent
of all other features, except for the term $\delta= \sum_{j\ne
i}b_j^2 m_j$ that enters through $\beta$. If we increase $\gamma$, $\delta$ increases in steps
each time that one of the features $j$ switches from $m_j\approx 0$ to
$m_j\approx 1$.
Thus $\delta$ is constant almost always, except at the step points.
Since the critical values of $\rho$ and $\gamma$ depend in a simple
way on $\delta$, the phase plot for the multivariate orthogonal
case is qualitatively the same as for the uni-variate case.

\section{Numerical examples}
\label{numerical}
In the following examples, we compare the VG with Lasso, ridge regression and
in some cases, with the paired mean field approach (PMF) \cite{titsias2012}.

For most of the examples, we generate a training set, a validation set and a
test set.  Inputs are generated from a zero mean multi-variate Gaussian
distribution with specified covariance structure.  We generate outputs
$y^\mu=\sum_i \hat{w}_i x_i^\mu +d\xi^\mu$ with $d\xi^\mu \in
{\cal N}(0,\hat{\sigma})$ and $\hat{w}_i$ depending on the problem.

For VG, ridge regression and Lasso, we optimize the model parameters on the
training set and, when necessary, optimize the hyper parameters ($\gamma$ in
the case of VG, $\lambda$ in the case of ridge regression and Lasso) that
minimize the quadratic error on the validation set.  For the Lasso, we used the
method described in \cite{friedman2009}
\footnote{
\url{http://www-stat.stanford.edu/~tibs/glmnet-matlab/}.}.

Comparison with PMF is performed using the software available online for the
regression case with one-dimensional output
\footnote{
\url{http://www.well.ox.ac.uk/~mtitsias/software.html}.}.
Since PMF optimizes hyperparameters as well, we merge both training and
validation sets and the resulting dataset is used as input for the PMF method.
This ensures that all methods use the same data for parameter estimation.

We define the solution vector for a given method as $\vv$.  For VG, the
components are $v_i\equiv m_i w_i$.  In the case of PMF, $m_i$ corresponds to
the spike-and-slab variational posterior and $w_i$ to the variational mean for
the weights \footnote{ The notation in~\cite{titsias2012} uses $\tilde w_i$ for
$w_i$ and $\gamma_i$ for $m_i$.  }.  For Ridge and Lasso $v_i\equiv w_i$.

\subsection{Small Example 1}
In the first example, we take independent inputs $x_i^\mu \in
{\cal N}(0,1)$ and a teacher weight vector with only one non-zero entry:
$\hat{w}=(1,0,\ldots,0)$, $n=100$ and $\hat{\sigma}=1$. The training set size
$p=50$, validation set size $p_v=50$ and test set size $p_t=400$.
\begin{figure}
\begin{center}
\includegraphics[width=0.65\textwidth]{fig1}
\end{center}
\caption{Top left (a): Minimal variational free energy versus $\gamma$. The two
curves correspond to warm start solution from small to large $\gamma$ ('forward') and from
large to small $\gamma$ ('backward') (see also Algorithm~\ref{algorithm}).
Top right (b): Training and validation error versus $\gamma$. The optimal $\gamma$
minimizes the validation error.
Bottom left (c): Solution $v_1=m_1 w_1$ and $\max_{i=2:n} |m_i w_i|$. The correct
solution is found in the range $\gamma\approx-20$ to $\gamma\approx -5$.
Bottom right (d): Optimal solution $v_i=w_i m_i$ versus $i$.
}
\label{file7a}
\end{figure}
We choose $\epsilon=0.001$ in Eq.~\ref{gamma_min},
$\gamma_\mathrm{max}=0.02
\gamma_\mathrm{min}, \Delta \gamma=-0.02 \gamma_\mathrm{min}$
(see Algorithm~\ref{algorithm} for details).

Results for a single run of the VG are shown in fig.~\ref{file7a}.  In
fig.~\ref{file7a}a, we plot the minimal variational free energy $F$ versus
$\gamma$ for both the forward and backward run.  Note, the hysteresis effect
due to the local minima. For each $\gamma$, we use the solution with the lowest
$F$.  In fig.~\ref{file7a}b, we plot the training error and validation error
versus $\gamma$. The optimal $\gamma\approx -21$ is denoted by a star and the
corresponding $\sigma=1/\sqrt{\beta}=1.05$.  In fig.~\ref{file7a}c, we plot the
non-zero component $v_1=m_1 w_1$ and the maximum absolute value of the
remaining components versus $\gamma$. Note the robustness of the VG solution in
the sense of the large range of $\gamma$ values for which the correct solution
is found.  In fig.~\ref{file7a}d, we plot the optimal solution $v_i=m_i w_i$
versus $i$.

In fig.~\ref{file7b} we show the Lasso (top row) and ridge regression (bottom row)
results for the same
data set. The optimal value for $\lambda$ minimizes the validation error (star).
In fig.~\ref{file7b}b,c we see that the Lasso selects a number of
incorrect features as well. Fig. ~\ref{file7b}b also shows that the
Lasso solution with a larger $\lambda$ in
the range $0.45<\lambda< 0.95$ could select the single correct feature, but
would then estimate $\hat{w}_1$ too small due to the large shrinkage effect.
Ridge regression gives very bad results. The non-zero feature is too
small and the remaining features have large values. Note from fig.~\ref{file7b}e,
that ridge regression yields a non-sparse solution for all values of $\lambda$.
\begin{figure}
\begin{center}
\includegraphics[width=0.8\textwidth]{fig_lr}
\end{center}
\caption{Regression solution for Lasso and ridge regression
for same data set as in fig.~\ref{file7a}.
Top row (a,b,c): Lasso. Bottom row (d,e,f): Ridge regression.
Left column (a,d): training and validation errors versus $\lambda$.
Middle column (b,e): Solution for the non-zero feature $v_1$ and the
zero-features $\max_{i=2:n} |v_i|$.
Right column (c,f): Optimal Lasso and ridge regression solution $v_i$ versus $i$.
}
\label{file7b}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}{l|r|r|r|r|r}
			&Train					&Val				&Test				&\# non-zero		&$\|\delta \vv\|_1$ 	\\\hline
Ridge		&$  0.60 \pm   0.43$	&$  1.72 \pm   0.39$&$  1.80 \pm   0.12$&$-$					&$  3.97 \pm   1.23$\\
Lasso		&$  0.78 \pm   0.26$	&$  1.07 \pm   0.20$&$  1.17 \pm   0.20$&$  8.65 \pm   6.75  $&$  0.80 \pm   0.57$\\
PMF       &$  -$    &$-$                  &$  1.02 \pm   0.10$&$   1.5 \pm   1.19 $&$  0.33 \pm   0.37$\\
VG			&$  0.85 \pm   0.22$	&$  0.96 \pm   0.17$&$  1.01 \pm   0.10$&$ 1.20 \pm   0.52$&$  0.31 \pm   0.30$ \\
True		&$  0.93 \pm   0.14$	&$  0.87 \pm   0.20$&$  0.98 \pm   0.04$&$1$			&$0$
\end{tabular}
\end{center}
\caption{Results for Example 1 averaged over 20 instances.
Train is mean squared error (MSE) on the training set.  Val is MSE on the
validation set.  Test is MSE on the test set.  \#~non-zero is the number of
non-zero elements in the Lasso solution and $\sum_{i=1}^n (m_i>0.5)$ for
VG and PMF.  $\|\delta\vv\|_1=\sum_{i=1}^n |v_i-\hat{w}_i|$.
}
\label{table1}
\end{table}
Table~\ref{table1} shows that the VG significantly outperforms the Lasso method
and ridge regression both in terms of prediction error, the accuracy of the
estimation of the parameters and the number of non-zero parameters. In this
simple example, there is no significant difference in the prediction error of
Lasso, PMF and VG, but the Lasso solution is significantly less sparse.  There
is no significant difference between the solutions found by PMF and VG.

\subsection{Small Example 2}
In the second example, we consider the effect of correlations in
the input distribution. Following \cite{tibshirani96} we generate input data
from a multi-variate Gaussian distribution with covariance matrix
$\chi_{ij}=\zeta^{|i-j|}$, with $\zeta=0.5$. In addition, we choose multiple
features non-zero: $\hat{w}_i=1, i=1,2,5,10,50$ and all other $\hat{w}_i=0$. We
use $n=100, \hat{\sigma}=1$ and $p/p_v/p_t=50/50/400$.  In table~\ref{table2}
we compare the performance of the VG, Lasso, ridge regression and PMF
on 20 random instances.
\begin{table}
\begin{center}
\begin{tabular}{l|r|r|r|r|r}
			&Train					&Val				&Test				&\# non-zero		&$\|\delta\vv\|_1$ 	\\\hline
Ridge		&$  0.32 \pm   0.27$	&$  3.30 \pm   0.67$&$  3.46 \pm   0.31$&$-$					&$ 11.09 \pm   0.93$\\
Lasso		&$  0.75 \pm   0.37$	&$  1.39 \pm   0.37$&$  1.48 \pm   0.29$&$ 16.30 \pm   6.60$&$  2.08 \pm   0.87$\\
PMF       &$  -$    &$-$                  &$  1.06 \pm   0.11$&$   5.15 \pm   0.49 $&$  0.67 \pm   0.35$\\
VG			&$  0.80 \pm   0.25$	&$  1.13 \pm   0.31$&$  1.15 \pm   0.21$&$  5.05 \pm   0.51$&$  0.83 \pm   0.54$\\
True		&$  0.93 \pm   0.14$	&$  0.87 \pm   0.20$&$  0.98 \pm   0.04$&5&0
\end{tabular}
\end{center}
\caption{Results for Example 2. For definitions see caption of Table~\ref{table1} above.
}
\label{table2}
\end{table}
We see that the VG and PMF significantly outperform the Lasso method and ridge
regression both in terms of prediction error and accuracy of the estimation of
the parameters. Again, there is no significant difference between PMF and VG.

\subsection{Effect of the noise}
In this subsection we show the accuracy VG, Lasso and PMF as a function of the
noise~$\hat{\sigma}^2$.  We generate data with $n=100, p=100, p_v=20$ and
$\hat{w}_i=1$ for $20$ randomly chosen components $i$.  We vary
$\hat{\sigma}^2$ in the range $10^{-4}$ to $10$ for for two values of the
correlation strength in the inputs $\zeta=0.5, 0.95$.

For weakly correlated inputs, Fig.~\ref{plot_sigma}a., we distinguish three
noise domains: for large noise all methods produce errors of ${\cal O}(1)$ and fail
to find the predictive features.  For intermediate and low noise levels, VG and
PMF are significantly better than Lasso.  In the limit of zero noise, the error
of VG and PMF keeps on decreasing whereas the Lasso error saturates to a
constant value.

For strongly correlated inputs, Fig.~\ref{plot_sigma}b., we observe
that whereas the error of VG scales approximately as before,
PMF gets stuck in local minima in some instances, yielding worse
average performance than VG.  See section~\ref{discussion} for a further
discussion of this point.

\begin{figure}
\begin{center}
\includegraphics[width=0.8\textwidth]{fig_noise_rho_MLJ}
\end{center}
\caption{
Accuracy of VG, Lasso and PMF as a function of the noise.  Errorbars of
$\parallel\delta\vv\parallel_1$ for $10$ different random instances.  Data is
generated using $n=100, p=100, p_v=20$ and $\hat{w}_i=1$ for $20$ randomly
chosen components $i$.  We consider
two values of the correlation strength in the inputs: \textbf{(a)} weakly
correlated inputs $\zeta=0.5$ and \textbf{(b)}~strongly correlated inputs
$\zeta=0.95$.
For PMF we choose the best solution (the one with highest value of the bound)
for $10$ different random initializations for each of the $10$ instances.
}
\label{plot_sigma}
\end{figure}
\subsection{Analysis of consistency: VG vs Lasso}
It is well-known that the Lasso method may yield inconsistent results when
input variables are correlated. In \cite{Zhao:2006:MSC:1248547.1248637},
necessary and sufficient conditions for consistency are derived. In addition,
they give a number of examples where Lasso gives inconsistent results.  Their
simplest example has three input variables, $x_1,x_2,x_3$.
$x_1,x_2,\xi,e$ are independent and Normal distributed random
variables, $x_3=2/3 x_1 + 2/3 x_2 + \xi$ and $y=\sum_{i=1}^3 \hat{w}_i
x_i + e$, $p=1000$. When $\hat{w}=(-2,3,0)$ (Example b) this example is consistent, but
when $\hat{w}=(2,3,0)$ (Example a) this example violates the consistency
condition. The Lasso and VG solution for Example a for different values of $\lambda$ and $\gamma$ are
shown in fig.~\ref{zhao1}a,b, respectively. The VG solution $v_i=m_i w_i$ in terms of
$m_i$ and $w_i$ is shown in fig.~\ref{zhao1}c,d.
\begin{figure}
\begin{center}
\includegraphics[width=0.8\textwidth]{zhao1.eps}
\end{center}
\caption{
(Color online) Lasso and VG solution for the inconsistent Example a of
\cite{Zhao:2006:MSC:1248547.1248637}.  Top left: Lasso solution versus
$\lambda$ is called inconsistent because it does not contain a $\lambda$ for
which the correct sparsity ($w_{1,2}\ne 0, w_3=0$) is obtained.
Top right: the VG solution for $\vv$ versus $\gamma$ contains large range of
$\gamma$ for which the correct solution is obtained.  Bottom left: VG
solution for $\vm$ (curves for $m_{1,2}$ are identical). Bottom right: VG
solution for $\vw$. }
\label{zhao1}
\end{figure}
The average results over 100 instances for Example~a and Example~b are shown in
table~\ref{zhao2}.
\begin{table}
\begin{center}
\begin{tabular}{l|r|r||r|r}
			&\multicolumn{2}{|c||}{Example a}  &\multicolumn{2}{|c}{Example b} \\
			&$\|\delta\vv\|_1$	&
$\max(|v_3|)$&$\|\delta\vv\|_1$ &       $\max(|v_3|)$\\\hline
Ridge		&$0.64 \pm 0.18$    &$0.48$	&$0.02 \pm 0.02$&$0.27$\\
Lasso		&$0.19 \pm 0.14$    &$0.30$	&$0.00 \pm 0.00$&$0.00$\\
VG   		&$0.05 \pm 0.03$    &$0.00$	&$0.00 \pm 0.00$&$0.00$
\end{tabular}
\end{center}
\caption{Accuracy of Ridge, Lasso and VG for Example 1a,b from
\cite{Zhao:2006:MSC:1248547.1248637}. $p=p_v=1000$. Parameters $\lambda$ (Ridge
and Lasso) and $\gamma$ (VG) optimized through cross validation. $\|\delta
\vv\|_{1}$ as before, $\max(|v_3|)$ is maximum over $100$ trials of the absolute
value of $v_3$.  Example a is inconsistent for Lasso and yields much larger
errors than the VG. Example b is consistent and the quality of the Lasso
and VG are similar. Ridge regression is bad for both examples.
}
\label{zhao2}
\end{table}
We see that the VG does not suffer from inconsistency and always finds the
correct solution. This is remarkable as one might have feared that the
non-convexity of the VG would result in sub-optimal local minima.

\subsection{Boston-housing dataset: VG vs PMF}
We now focus on comparing in more detail the performance of VG with PMF.  In
\cite{titsias2012}, the Boston-housing
dataset\footnote{\texttt{http://archive.ics.uci.edu/ml/datasets/Housing}} is
used to test the accuracy of the PMF approximation.

This is a linear regression problem that consists of $456$ training examples
with one-dimensional response variable $y$ and $13$ predictors that include
housing values.  We use here the same setup as in \cite{titsias2012} to compare
VG with PMF. For PMF, hyperparameters were fixed to values
$\sigma=0.1\times\text{var}(y), \pi = 0.25, \sigma_w = 1$ where var(y) denotes
the output variance. For the VG, we use $\beta = 1/\sigma^2$, $\gamma =
\log(\pi/(1-\pi))$ and hyperparameter $\sigma_w$ is implicitly equal to
$\infty$ in the VG
(see Appendix \ref{sec:pmf} for details of how both models compare).  Since
$\gamma$ and $\beta$ are given, the VG algorithm reduces to iterate
eqs.~\eqref{m} and~\eqref{v} starting from a random $\vm$.  Similarly, the PMF
reduces to perform an E-step given the fixed hyperparameter values.

As in \cite{titsias2012}, we use random initial values for the variational
parameters \emph{between} $0$ and~$1$ (\emph{soft} initialization) and random
values \emph{equal to} $0$ or $1$ (\emph{hard} initialization).  We considered
as ground truth $\hat{w}\equiv\vw^\text{tr}$ the result of the efficient paired Gibbs
sampler developed in \cite{titsias2012}.

\begin{table}
\begin{center}
\begin{tabular}{l|c|c}
 & \emph{soft}-error & \emph{extreme}-error \\\hline
 PMF \cite{titsias2012} & 0.208 [0.002, 0.454]  & 0.204 [0.002, 0.454]  \\
 PMF & 0.237 [0.001, 0.454]  & 0.209 [0.001, 0.454] \\
 VG & 0.006 [0.006, 0.006]  & 0.006 [0.006, 0.006] \\
\end{tabular}
\end{center}
\caption{
Comparison of VG and PMF in the Boston-housing dataset in terms of
approximating the ground-truth $\hat{w}$.  Average errors
$\|\delta\vv\|_1=\sum_{i=1}^n |v_i-\hat{w}_i|$
, with $v_i$ the approximation of VG or PMF, together with $95\%$
confidence intervals (given by percentiles) obtained after $300$
random initializations for both soft and extreme initializations.
}
\label{housing}
\end{table}
Table \ref{housing} shows the results.  The first and second rows show the
errors reported in \cite{titsias2012} and the errors that we obtain using their
software, respectively.  We observe a small discrepancy in the average errors.
However, if we consider the percentiles, the results are consistent.  In
practice, what we observe is that PMF finds two local optima depending on the
initialization: one is the correct solution (error $\approx 10^{-3}$) whereas
the other has error $0.454$. These two solutions are found
equally often for both soft or hard initializations, showing no dependence on
the type of initialization, in agreement with \cite{titsias2012}.

The results of VG are shown on the third row.  Contrary to PMF, the VG shows no
dependence on the initialization and always finds a solution with an error of
order $10^{-3}$.  These results give evidence that the combined variational/MAP
approach of VG can be better than PMF avoiding local minima.

\subsection{Dependence on the Number of Samples}
We now analyze the performance of all considered methods as a function of the
proportion of samples available. We first analyze the case when inputs are not
correlated and then consider correlations of practical relevance that
appear in genetic datasets.

For these experiments, we generate the data for dimension $n=500$ and noise
level $\beta=1$.  We explore two scenarios: very sparse problems with only
$10\%$ of active predictors and denser problems with $25\%$ of active
predictors. The weights of the active predictors are set to~$1$.

\subsubsection{Uncorrelated Case}
\begin{figure*}
\begin{center}
\includegraphics[width=.65\textwidth]{fig_toy_MLJ3}
\end{center}
\caption{
\textbf{Uncorrelated case}: Performance as a function of
number of training samples $p$ for two levels of sparsity ($10\%$ and
$25\%$ of non-zero entries).  For each value averages over $20$ runs are
plotted.  \textbf{Top:} area under the ROC curves (see text for definition).
\textbf{Middle:}~reconstruction error, defined as
$\|\delta\vv\|_1=\sum_{i=1}^n |v_i-\hat{w}_i|$.
\textbf{Bottom:} generalization
error, defined as the MSE in the test set.
For all methods except for PMF, train set size is $p$
and validation sets size $p_v=p/30$.  For PMF the
training set has size $p + p_v$. Lowest curve shows theoretically optimal generalization
error obtained by using the target weights from which the data is generated.
}
\label{fig:toy}
\end{figure*}

Figure~\ref{fig:toy} shows results of performance for uncorrelated inputs.  Top
plots show the area under the Receiver Operating Characteristic (ROC) curve.
The ROC curve is calculated by thresholding the weight estimates.  Those
weights that lie above (below) the threshold are considered as active
(inactive) predictors.
The ROC curve plots the fraction of true positives versus the fraction of false positives for all threshold values.
The area under the curve
measures the ability of the method to correctly classify those predictors that
are and are not active.  A value of~1 for the area represents a perfect classification
whereas 0.5 represents random classification. The ROC is plotted as a function of the
fraction of samples relative to the number of inputs: $p/n$.

For both VG and PMF, we observe in all performance measures a transition from a
regime where solutions are poor to a regime with almost perfect recovery.  This
transition, not noticeable in the other (convex) methods, occurs at around
$35\%$ of examples for $10\%$ of sparsity (left column) and shifts to higher
values for denser problems ($\approx 60\%$ for $25\%$ of sparsity, right
column).

If we compare VG with PMF we see that in the regime where both methods perform well,
PMF performs slightly better than VG in terms of reconstruction error but
their performance is identical in terms of the area under the ROC curve.  The difference
between VG and PMF is slightly more
pronounced for denser problems.  We also see that Lasso performs
better than Ridge regression, but the difference between both methods tends to
be smaller for denser problems. Both Lasso and ridge regression are significantly worse than
VG and PMF.

\subsubsection{Correlated case: Genetic dataset}
\begin{figure*}
\begin{center}
\begin{tabular}[t]{cc}
    \includegraphics[width=.33\textwidth]{correlations1} &
    \includegraphics[width=.65\textwidth]{fig_genetics_MLJ3}
    \end{tabular}
\end{center}
\caption{
\textbf{Correlated case}: \textbf{(LEFT)} (Color online) Example of
input correlation matrix. \textbf{(RIGHT)} Performance as a function of
number of training samples $p$ for two levels of sparsity ($10\%$ and
$25\%$ of non-zero entries).  For each value averages over $20$ runs are
plotted.  \textbf{Top:} area under the ROC curves (see text for definition).
\textbf{Middle:}~reconstruction error, defined as
$\|\delta\vv\|_1=\sum_{i=1}^n |v_i-\hat{w}_i|$.
\textbf{Bottom:} generalization
error, defined as the MSE in the validation set.
For all methods except for PMF, train set size is $p$
and validation sets size $p_v=p/10$.  For PMF the
training set has size $p + p_v$.
}
\label{fig:correl}
\end{figure*}
We now consider correlated inputs. We use input data obtained from a genetic domain,
where inputs $x_i$ denote single nucleotide polymorphisms (SNPs) that have
values $x_i=\{0,1,2\}$. SNPs typically show correlations structured in blocks,
where nearby SNPs are highly correlated, but show no dependence on distant
SNPs. An example of such correlation matrix can be seen in Figure
\ref{fig:correl} (left). The output data are generated as above.

Figure \ref{fig:correl} (right) shows the results.  Contrary to the
uncorrelated case, the existence of strong correlations between some of the
predictors prevents a clear distinction between solution regimes as a function
of training set size.  We observe, as before, that both VG and PMF are the
preferable methods for sufficiently large training set size. In the three performance measures considered, VG performs better or
comparable to PMF.  Interestingly, the difference between VG and PMF becomes more
significant for denser problems, when we expect more difficulty due to more
presence of local minima.

\subsection{Scaling with dimension $n$}
\begin{figure*}
\begin{center}
    \includegraphics[width=\textwidth]{fig_scaling_MLJ2}
\end{center}
\caption{
\textbf{Scaling with $n$}:
performance of VG, PMF and Lasso as a function of the number of features $n$.
Data are generated as in Example 2. $p=100,p_v=100,\beta=2,\zeta=0$.
}
\label{fig:scaling}
\end{figure*}
We conclude our empirical study by analyzing how the methods scale, both in terms of the quality of the
solution as in terms of CPU times, as a
function of the number of features $n$ for a constant number of samples.
We use the data as in Example 2 above, with uncorrelated inputs.

Figure \ref{fig:scaling} shows the results for VG, PMF and Lasso.  For the
VG, we use the dual method described in the appendix \ref{dual}.
Fig.~\ref{fig:scaling}a shows that the VG and PMF have constant quality in
terms of the error $\|\delta\vv\|_1$, whereas the quality of the Lasso
deteriorates with $n$.  Fig.~\ref{fig:scaling}b shows that the VG and PMF
have close to optimal norms $L_0=5$ and that the $L_0$ norm of the Lasso
deteriorates with $n$.  Fig.~\ref{fig:scaling}c shows that the computation time
of all methods scales approximately linear with $n$.  Lasso is significantly
faster than VG and PMF, and VG is significantly faster than PMF. Note, however
that the VG and the PMF methods are implemented in Matlab whereas the Lasso
method uses an optimized Fortran implementation.

\section{Discussion}
\label{discussion}
In this paper, we have introduced a new variational method for sparse regression
using $L_0$ penalty. We have presented a minimal version of the
model with no (hierarchical) prior distributions to highlight
some important features: the variational ridge term that dynamically
regularizes the regression; the input-output behavior as a smoothed
version of hard feature selection; a phase plot that shows when the
variational solution is unique in the orthogonal design case for
different $p,\rho,\gamma$.  We have also shown numerically that the VG
is efficient and accurate and yields results that significantly
outperform other considered methods.

The VG suffers from local minima as can be expected for any method that needs
to solve a non-convex problem, like the PMF.  From the numerical experiments we
can conclude that VG is on average preferable to PMF in practical scenarios
with strongly correlated inputs and/or moderately sparse problems, where the
local minima problem is more severe.  Although we have no principled solution
for the local minima problem, we think that the combined variational/MAP
approach together with the the annealing procedure that results from increasing
$\gamma$, followed by a "heating" phase to detect hysteresis works well in
practice, helping to avoid local minima.  Another obvious approach is to use
multiple restarts or using more powerful approximations, such as structured
mean field approximation or belief propagation.  We remark that the PMF in the
general setting \cite{titsias2012} includes an extra layer of flexibility that
can be used to capture correlations between input variables.  Such extensions
can also be considered for VG.

We have not explored the use of different priors on $\vw$ or on
$\beta$. In addition, a prior could be imposed on $\gamma$.  It is
likely that for particular problems the use of a suitable prior
could further improve the results.

We have seen that the performance of the VG is excellent in the zero noise
limit. In this limit, the regression problem reduces to a compressed sensing
problem \cite{candes2005,donoho2006}. The performance of compressed sensing
with $L_q$ sparseness penalty was analyzed theoretically in
\cite{kabashima2009}, showing the superiority of the $L_1$ penalty in
comparison to the $L_2$ penalty and suggesting the optimality of the $L_0$
penalty. Our numerical result are in agreement with this finding.

Our implementation uses parallel updating of Eqs.~\ref{m}-\ref{beta}, or
Eqs.~\ref{m},\ref{w2},~\ref{A}-\ref{lambda1} when using the dual
formulation. One may consider also a sequential updating. This was done
successfully for the Lasso based on the idea of the Gauss-Seidel algorithm
\cite{friedman2009}. The advantage of such an approach is that each update
is linear in both $n$ and $p$, since only the non-zero components need to
be updated. However, the number of updates to converge will be larger. The
proof of convergence for such a coordinate descend method for the VG is
likely to be more complex than for the Lasso due to non-convexity. As a
result, a smoothing parameter $\eta \ne 1$ (see Algorithm~\ref{algorithm})
may still be required.

\subsubsection*{Acknowledgments}
We would like to thank M. Titsias for providing the code of PMF and specially
the Boston Housing files.  We also thank Kevin Sharp and Wim Wiegenrick for
useful discussions and anonymous reviewers for helping on improving the
manuscript.

redpajama_set_name: RedPajamaArXiv


text:
Q: Chapter heading vertical shift on page with multiple minipages Im trying to create a document with only minipages to not break the content over different pages. But when the minipages reach the 2nd page of a chapter, the chapter heading layout is shifted vertically and the content of the 1st page is somehow distributed over the entire page instead of top aligned.
I've found that introducing a \vfill after the 1st minipage solves the header layout but the other minipages are then placed on the bottom while I want the spacing to be at the bottom.
Any suggestions?
Example:
\documentclass{book}
\usepackage{lipsum}

\begin{document}

\chapter{Correct layout}
\begin{minipage}{\textwidth}
\lipsum[1]
\end{minipage}

\chapter{Shifted layout}
\begin{minipage}{\textwidth}
\lipsum[2]
\end{minipage}

\begin{minipage}{\textwidth}
\lipsum[2]
\end{minipage}

\begin{minipage}{\textwidth}
\lipsum[1-2]
\end{minipage}

\end{document}

A: As suggested by moewe
\raggedbottom does what I want
\documentclass{book}
\usepackage{lipsum}
\raggedbottom

\begin{document}

\chapter{Correct layout}
\begin{minipage}{\textwidth}
\lipsum[1]
\end{minipage}

\chapter{No more shift}
\begin{minipage}{\textwidth}
\lipsum[2]
\end{minipage}

\begin{minipage}{\textwidth}
\lipsum[2]
\end{minipage}

\begin{minipage}{\textwidth}
\lipsum[1-2]
\end{minipage}

\end{document}

redpajama_set_name: RedPajamaStackExchange


text:
Cole strikes out 11, Diaz homers, Astros win 3-2 at Seattle
Houston Astros starting pitcher Gerrit Cole throws against the Seattle Mariners in the first inning of a baseball game Sunday, April 14, 2019, in Seattle. (AP Photo/Elaine Thompson)
Houston Astros' Michael Brantley, right, and Seattle Mariners catcher Omar Narvaez watch the path of Brantley's two-run single in the sixth inning of a baseball game Sunday, April 14, 2019, in Seattle. (AP Photo/Elaine Thompson)
Seattle Mariners shortstop Tim Beckham, right, throws to first after forcing out Houston Astros' Alex Bregman (2) at second base in the eighth inning of a baseball game Sunday, April 14, 2019, in Seattle. Beckham completed the double play, throwing out Michael Brantley at first. (AP Photo/Elaine Thompson)
Seattle Mariners starting pitcher Marco Gonzales, left, heads back to the mound as Houston Astros' Jose Altuve (27) and Tony Kemp (18) celebrate scoring with Carlos Correa in the sixth inning of a baseball game Sunday, April 14, 2019, in Seattle. (AP Photo/Elaine Thompson)
SEATTLE — Aledmys Diaz has to take his opportunities when he can with the Houston Astros.
Diaz responded to his first start at designated hitter this season Sunday by hitting a home run in the seventh inning that made the difference in Houston's 3-2 victory over the Seattle Mariners, the ninth straight win for the Astros.
Diaz was traded from the Blue Jays this winter. With stars nearly everywhere in the lineup, Diaz has served as Houston's utility infielder, filling in at first, second and shortstop already. He's been in the starting lineup three times in April, going 5 for 12 with two homers in those games.
"He's not getting to play a lot. He played almost every day last season, so the attitude has been great," Astros manager AJ Hinch said. "He's willing to do anything. Guys are rooting for him in there."
Gerrit Cole had a strong start for Houston, striking out 11 in six innings. Cole (1-2) gave up two runs on four hits, including a leadoff home run to Mitch Haniger, and did not walk a batter. Cole has pitched at least six innings in each of his four starts.
Haniger's homer, his fifth, extended the Mariners' major league record streak to 18 games with a home run to start the season. Haniger also doubled and scored both Seattle runs.
Cole and the Astros bullpen shut down the Mariners, who entered leading the majors with 7.29 runs a game. After Domingo Santana hit a run-scoring double in the third for Seattle's second run, no other Mariners hitters reached base, with Houston retiring the last 19 Seattle batters.
Hector Rondon, Ryan Pressly and Roberto Osuna each pitched a perfect inning in relief for Houston, with Osuna working the ninth for his seventh save.
"Our whole bullpen is really good," Cole said. "They're not afraid to pitch in leverage or clean up your mess. As starters, we just try to minimize their workload as best we can."
There were some close calls for Osuna. Haniger appeared to start the ninth inning with an infield single, but was ruled out on replay. Santana had fans on their feet with a long drive down the right field line that went foul before striking out, and Daniel Vogelbach worked a full count before striking out looking to end the game.
"It's a game of inches. I thought Domingo's ball had a chance there in the ninth to sneak around the foul pole. Just didn't happen," Seattle manager Scott Servais said. "We just went up against really good pitching this weekend."
Mariners starter Marco Gonzalez was trying for his fifth straight win to open the season, and looked on track early. Gonzalez allowed just one hit over the first five innings as Seattle opened a 2-0 lead.
The Astros took over in the sixth. Singles by Tony Kemp, Jose Altuve and Alex Bregman loaded the bases. Michael Brantley then drove in two runs with another single, trying the game and ending Gonzalez's day.
Brandon Brennan struck out the next two batters to end the inning. In the seventh, Diaz led off with his second homer, the first run Brennan (1-1) allowed after starting the season with 11 1/3 scoreless innings.
This was the 10th time Cole has struck out at least 11 batters in his career. In six of those 10 games, Cole has also not allowed a walk.
Mariners: Placed starting LHP Wade LeBlanc on the 10-day injured list with a Grade 2 right oblique strain. LeBlanc is expected to be out four to six weeks. Seattle recalled RHP Erik Swanson from Triple-A Tacoma on Sunday. Swanson is expected to take LeBlanc's upcoming spot in the rotation on Wednesday against Cleveland.
The Mariners traded C David Freitas to the Milwaukee Brewers for minor league RHP Sal Biasi.
Astros: RHP Colin McHugh (2-1, 2.65 ERA) makes his fourth start at Oakland on Tuesday. McHugh has one win against the Athletics this season, after his pitched six one-run innings on April 5.
Mariners: LHP Yusei Kikuchi (0-0, 4.15) is looking for his first major league decision in his fifth start as Seattle starts a three-game home series against Cleveland.
Beyonce proves she's in a lane of her own at MTV...
Beyonce proved once again she is a contemporary rock star, and she used the MTV Video Music Awards...
For retired US Open champ Flavia Pennetta, no...
Flavia Pennetta arrived back at Arthur Ashe Stadium and had one question: "Where is it?"
'Can't hear anything': As rain pelts Open roof,...
When heavy rain began pelting the closed roof atop Arthur Ashe Stadium, Andy Murray couldn't pick...
Cubs hit 3 homers, beat Pirates 8-3 to complete...
Trout, Pujols power Angels to 9-2 victory over...
Donaldson homers, scores go-ahead run in Braves'...
Jul 10, 2019 US Women's World Cup champs arrive home ahead of...
Jul 9, 2019 Nuggets acquire Jerami Grant from Thunder for...

redpajama_set_name: RedPajamaCommonCrawl


text:
Now Reading: Political Intelligence
Texas Observer Staff Mar 17, 2000, 12:00 am CST
S.O.A. NO MORE?
Counterpunch reports that the Army's current counterattack to the continuing public protests against Fort Benning's School of the Americas (a.k.a "School of Assassins") is a classic one: change the name. Under draft federal legislation now being circulated in Congress by the U.S. Army lobbyists, "the butchers of tomorrow will learn their skills at the "United States Military Institute for Hemispheric Security Cooperation," or U.S.M.I.H.S.C.
Try finding a nasty translation for that one. According to the February 1-15 Counterpunch, the contemplated name change is part of a series of cosmetic measures including more training of law enforcement and civilian personnel, provision for "democratic enhancement training" with courses in "peace operations" and a human rights requirement, expansion of the "Board of Visitors" to include more high-profile supporters, and perhaps moving some of the more objectionable coursework abroad or to less well-known U.S. installations. At the same time, the newsletter reports, the S.O.A.'s Board is hoping to increase the School's funding while publicly discrediting longtime opponents, like Father Roy Bourgeois, as "un-American." For more detail, see the website at www.counterpunch.org.
WHO'S RIGHTER?
Although the presidential campaign has stolen most of the headlines this primary season, state pollwatchers have been entertained by the Republican battle for Senate District 3, where three candidates are wrassling for the right to oppose Democrat David Fisher, who is unopposed in the primary. District 3 is the key battleground for control of the Senate, where Republicans hold only a one vote margin (16-15). Incumbent Republican Drew Nixon finally decided to abandon the seat in the wake of his embarrassing Austin arrest (during the 1997 session) for soliciting a prostitute who turned out to be a cop, and illegal gun possession. (Also in play is District 2, where incumbent Democrat David Cain currently remains favored to win in November.)
Of the three Republican candidates, Conroe building contractor Van Brookshire is running a self-funded, low-profile race, but Todd Staples, an incumbent House member from Palestine, and Woodlands homebuilder Les Tarrance have been happily slinging money (estimated to reach nearly $500,000 each by primary time) and mud at each other for several weeks. Tarrance (brother of national Republican pollster Lance Tarrance) has accused Staples of being a do-nothing and distant representative, while Staples calls Tarrance a "carpetbagger" for moving into the district to run for Senate, and a "deadbeat" for failing to pay state franchise taxes for several years.
Both candidates recite predictable right-wing mantras — less government, abortion restrictions, lower taxes — differing only on school vouchers, which Staples supports and Tarrance says he opposes. But by their friends you will know them. Tarrance is backed by former Governor Bill Clements and big Dallas GOP donor Louis Beecherl, with endorsements from the Texas Medical Association, the Texas Association of Builders, and the Texas Municipal Police Officers Association. Staples counts among his supporters several dozen Republican legislators (including Senate colleagues John Carona and Florence Shapiro), the Texas Farm Bureau, and the Texas Association of Realtors. He also touts approval of his House voting record from the state Eagle Forum and the Christian Coalition.
With friends like those, Political Intelligence wonders, who needs principles? Staples still appears to have the inside track, although Tarrance hails from the heavily Republican Woodlands and may make it a race. The question remains whether the loser will bloody the winner badly enough to help Democrat Fisher (who can for the moment stand aside looking noble) in November.
CLOUDS OVER CLEAR LAKE.
Seabrook citizens sent an open letter to Governor Bush March 2, asking him to take action against plans by an international joint venture of Elf Atochem and Nippon Shokubai to build an American Acryl acrylic acid plant in Seabrook. According to the letter, the plant, to be built within one to three miles of every home in Seabrook, will emit over 800,000 pounds of toxic and smog-forming chemicals, "roughly the equivalent of adding almost 8,000 cars to Seabrook and Clear Lake." The letter would also include a hazardous waste incinerator, likely to emit PCBs and dioxins into the neighboring air.
The letter points to Elf Atochem's poor environmental record in the Houston area, and argues that the T.N.R.C.C. has allowed the company to evade proper pollution control scrutiny by using planning loopholes and declaring many of the potential hazardous emissions "confidential," despite citizen protests to the Attorney General. Partly because of a rushed permitting process, state administrative judge Mike Rogan was scheduled to make a decision March 3 on three air pollution permits for the plant.
"So time is of the essence," wrote the citizens, "we make a plea for you, Governor Bush, to stop the issuance of the air permits and not allow this foreign-owned plant to be built. We understand that your campaign accepted money from this company, but perhaps you did not know the complete facts that we have discovered, and if you did know how your citizens could be harmed by this foreign-owned chemical company you would of course do the right thing to protect us."
If the Governor or his aides received the letter, it apparently had little effect: Neil Carman of the Sierra Club told Political Intelligence that the administrative judge "slam-dunked" the approval for Elf Atochem, as expected. Perhaps Sam Wyly of Bush's "Republicans for Clean Air" can use the decision as an another occasion to explain why the Governor is a true friend of the environment.
IT'S ABOUT THE MONEY.
If the money doesn't flow, the wheels don't turn, the vote doesn't get turned out, and candidates go down in flames. John Sharp predicts a well-funded Democratic effort this year. "I've committed to raising my hundred to two hundred [thousand], and a bunch of other people are doing it," he said. Democrats are focusing their cash on a few key House races, plus the all-important Senate District 3 race which will determine who will have a sixteen-to-fifteen advantage in the Senate. According to a report in Ross Ramsey's Texas Weekly, Republican Lieutenant Governor Rick Perry is warning lobbyists that he is keeping track of who is siding with David Fisher, the Democratic candidate in this race, and who is supporting the Republican cause. Donors to Fisher may find it difficult to ply their trade in the next legislative session.
Republicans in all state races will receive a boost from the Governor's presidential campaign, as the best-funded candidate in history floods the airwaves with TV and radio ads. The national Democratic party, meanwhile, is unlikely to spend any money challenging the Governor in Texas (assuming he gets the nomination). But they did get a boost in the form of an assurance from House Minority Leader Dick Gephardt, who has reportedly promised that all Democratic Congressional Campaign Committee money raised in Texas will be spent on Texas races. That means more TV and other advertising in districts where a Democratic Congressman has a contested race, which will boost turnout for all Democratic candidates. It also frees up other Democratic money to go to state-level candidates. As John Sharp observes, even in the disastrous 1998 elections, state-level Democrats candidates did well in districts which also hosted a Congressional contest.
PAINTER VS. WORLD, II.
In the mind of Midland County Sheriff Gary Painter, Wyatt Earp still patrols the high plains, Ronald Reagan presides over the White House, the sheriff's word is still the law of the land, the Texas Attorney General is just another lawyer, and the drug war is the only war we've got. As Nate Blakeslee reported ("The Law West of the Pecos," December 10) the prodigious drug warrior's latest project is S.T.A.R. (Sheriffs of Texas Agreed Response), a weekend posse of sheriff's deputies from across the state. Ostensibly conceived as a statewide emergency response team, Painter and his chief deputy Clayton McKinney have been training the group in drug interdiction and tactical (i.e., S.W.A.T.) operations, complete with armored personnel carriers, automatic weapons, fatigues, etc.
S.T.A.R. has become an issue in Painter's campaign for his fifth term as sheriff. Republican primary opponent Mike Hall labeled the operation a waste of taxpayers' money and Midland County deputies' time. He says he will discontinue it if he wins the primary (there is no Democratic candidate). Now County Judge Bill Morrow has requested a ruling from John Cornyn about the legality of S.T.A.R., asking specifically if (1) the sheriff has the authority to contract with other sheriffs without approval of the commissioners court, and (2) whether S.T.A.R. conflicts with the state's own Emergency Management System. The state's emergency plan, created by statute, "is a pretty complicated system," Morrow told Political Intelligence. Each governmental entity has its prescribed duties and obligations — none of which call for army tanks or armored personnel carriers, Morrow points out. At issue is the county's liability for damage to people or property during a S.T.A.R. operation or training session, several of which have taken place hundreds of miles from Midland. It's the same issue that fueled Painter's battle with an earlier commissioners court, when then-County Judge Bro Seltzer successfully reined in Painter's out-of-county drug operations. The judge has yet to hear from the Attorney General, but Painter and company apparently aren't holding their breath. "If they outlaw the agreement, hell, we don't care," Clayton McKinney told the Midland Reporter-Telegram. "It don't change anything." It appears the voters of Midland County will get their say before the A.G. does: the Republican primary is March 14.
GOD'S PROSECUTOR.
Ever since he helped put together the Houston "Straight Slate" to punish a mayor and city council members who backed gay and lesbian employment rights, Dr. Steve Hotze has been doing God's work in the Devil's city. The Houston Republican M.D. promotes what he considers a Bible-based political philosophy, and in the March primary is supporting a candidate who defines the extreme right in Harris County politics. Chuck Rosenthal is one of five Republicans in the race to oppose Jim Dougherty, the lone Democrat hoping to replace retiring Harris County District Attorney Johnny Holmes.
Houston Chronicle political reporter Julie Mason described Republican D.A. candidate forums as pretty close to "howling at the moon." Mason took Rosenthal to task for describing the D.A.'s office as insensitive to minorities — then referring to Asians as "Orientals." And while it's hard to imagine anyone with stronger capital punishment convictions than Holmes — his office leads the nation in capital murder prosecutions — Rosenthal promises to bring a novel twist to the application of the state's death penalty statute. He describes the death penalty as a "biblical proposition," and argues that "government is instituted by God and has the authority to carry out God's law." Rosenthal told the Chronicle he realizes that some people have concerns about God in politics. "I understand the squeamishness of it."
GOD'S LOBBYIST FINED.
Hotze's Conservative Republicans of Harris County set a record at the Texas Ethics Commission, which levied a $5,000 fine against the PAC that has a history of attacking moderate Republicans. Two other Hotze PACs, Citizens for Restoration (which advocates New Testament content in public school curriculum) and the Houston Republican Forum were also fined a combined total of $1,900. Charges include failure to comply with state law requiring full disclosure of the source and use of political funds, and failure to properly label and identify political mailings. Hotze is a major player in Houston Republican politics and at one time his tactics were so divisive that there were two Harris County Republican parties.
One complaint was filed by Betsy Lake, the former Republican Party Chair driven from office by the Hotze Repubs. Hotze's pre-primary mailings make or break county Republican candidates, and one of the fines levied was for a pre-primary mailing that appeared to be a party mailout but listed only PAC endorsements. Hotze also recently went after an incumbent George W. Bush appointee to the bench in Houston, supporting the challenger.
According to Houston Press political columnist Tim Fleck, Hotze's snubbing of Judge Martha Hill Jamison, a Democrat-turned-Republican, started a foodfight at a prayer luncheon where Phil Gramm was the keynote speaker. Hotze stiffed another luncheon guest, Republican Judge Sharolyn Wood, who has served on the bench in Houston for eighteen years. Hotze endorsed a mediator, K. Allan Davis, who got the PAC's blessing because he is a devout Baptist. Several contributors called demanding that Conservative Republicans of Harris County return money contributed to sponsor the prayer luncheon.


When Tourism Australia designed the adventure for Oprah in Australia, I am certain they thought we have to show Oprah experiences that will leave her with a sense of awe! Experiences that are uniquely Australian and no matter where she went in the world she could only do this in Australia.
Here is a summary of Oprah's experiences!
Helicopter over the Great Barrier Reef – I have been fortunate enough to fly over the Great Barrier Reef by helicopter and the view is simply stunning. The enormity and scale of the reef can only really be appreciated from the air. Even for people who have done everything – this is must – one of nature's masterpieces at its best. As they say "only in Australia".
Beach BBQ – Where did Oprah have a beach BBQ? Where else but on Whitehaven Beach! Truly one of the most spectacular spots in Australia. A private boat trip on qualia's luxury vessel "Atomic" from Hamilton Island is something special; the trip to Whitehaven through the myriad of Whitsunday islands is exceptional on its own let alone the vista and location that greets one on arrival at the beach. A picnic and a snorkel is a must or simply just swim and enjoy the setting.
Uluru – The Outback – Uluru is the spiritual heart of Australia and highly sacred to the local Aboriginal people. There is something very special about the first time you lay eyes on Uluru – it certainly leaves you with a sense of wonder not only about its magnitude and size but it has a presence and feeling that is hard to describe. I think you realise that it is truly ancient piece of Australia and will be there for millions of years to come. Sunrise at Uluru is a must along with table 131 with dinner under the outback sky. Staying at Longitude is the only option in my opinion.
Melbourne – The city of Melbourne has a unique vibe and it just knows it's cool. From the cafes and laneways to the famous MCG and Rod Laver Arena it has something for everyone. Known as the cultural centre of Australia I love Melbourne because there is always something interesting happening whether it be an event at Federation square or a strolling down Southbank and people watching. Staying at The Lyall in hip South Yarra is a must and the restaurants in the area are all of great quality with a huge variety of choice. Plan a trip to the Yarra Valley or the Mornington peninsula but always go with a guide otherwise you will miss the secrets that only a local will know.
Sydney – If you are staying in Sydney you need a view of the famous harbour and the view from the rooftop lounge at the Intercontinental is without compare with vistas spanning out across the Opera House and to the Bridge. Always book a room that gives you access to the rooftop lounge because whether you are having breakfast or cocktails the lounge is the place to be. When in Sydney you must do at least 3 things these being. 1 Sail on the harbour 2. Climb the bridge – I know it is commercial but it is very cool! And 3 go to Bondi and do a surf lesson – I know Oprah did 2 of the 3 I will let you guess which one she skipped.


Vybz Kartel was rushed to the Kingston Public Hospital earlier today following his complaints of having severe chest pains.
The "Worl Boss" Deejay was in handcuff and accompanied by heavily armed police officers. He was treated at the hospital and then taken back into custody at the Horizon Remand Center.
Many of Adidja Palmer's fans and well-wishers gathered outside the hospital to show their support. He is reportedly doing much better since his visit to the hospital.


The work of artists like the Japanese illustrator Yoshi Sislay, the Italian Lorenzo Petrantoni, French artist Christian Gastaldi, the American Matt W. Moore, the Russian design studio the Dopludo Collective, Mister Mourau from Portugal and Spaniards Alex Trochut, Aleix Gordo, Marta Cerdá and Brosmind are permanently exposed in this Barcelona hotel. We could describe the hotel as a true artistic laboratory. The artists were selected by the famous Barcelona-based interior designer Jaime Beriestain who gave them absolute freedom to develop their 'creations'. Each artist was assigned an area of the landmark building which was designed by renowned architectural firm Cirici & Bassó.
The work by Yoshi Sislay can be admired in the lobby and hallways of the seventh floor of the Vincci Bit Barcelona. The superb illustrations on the ceilings and walls seem to contain characters that grow and move. The Japanese artist included a game in the work to amuse the hotel guests. If they can find seven Dragon Balls in the work then they can make a wish.
On the sixth floor there is a mural with black and white illustrations by Lorenzo Petrantoni where guests will recognise famous personalities from the nineteenth century to up to President Obama.
The hallway of the fifth floor was created by Brosmind. Colourful elements and characters star in the original drawings printed on wallpaper. On the fourth floor there are optical illusions by Matt W. Moore. A mural of geometric shapes with secondary colours (orange, green and purple) interspersed with grey and black.
On the third floor Aleix Gordo created his own world with spray and acrylic paint. Inspired by the aesthetics of the 50s, Alex Trochut expresses a sense of joy in his dreamlike mural on the second floor.
In 23 days Mister Morau created detailed drawings of cities and buildings representing a strip of buildings spreading along the corridor of the first floor.
The Barcelona beach is only a ten minute walk from this hotel and the subway is just five minutes away. The hotel has a terrace with a small swimming pool on the eighth floor where guests can have private parties. There is also a gym with sauna and steam room. So, if you want to combine art with a hotel stay in Barcelona this novel hotel may well be worth a try.
This entry is filed under Barcelona Hotels.


text:
Be afraid. A political coup is underway in the UK – Kenny MacAskill
Conservative party leadership contender Boris Johnson has not ruled out suspending the Westminster parliament to force through a no-deal Brexit without MPs' consent. (Picture: PA Wire)
Kenny MacAskill
The leaking of UK Ambassador Sir Kim Darroch's scathing assessment of Donald Trump is the latest sign of the soft political coup being carried out by pro-Brexit politicians who care only about power and their own self-interest, writes Kenny MacAskill.
Political coups come in all shapes and form. I read the biography of Victor Jara, the Chilean folksinger murdered by the Pinochet regime. His widow narrated the growing tensions as the oligarchs ramped up opposition to Salvador Allende's democratically elected government. Fear grew before finally it erupted, with military jets bombing the presidential palace and opponents rounded up and killed. It's to Britain's eternal shame that Thatcher consorted with the Fascist Chilean General.
Now I don't for a minute believe that anything like that will ever occur here. But a soft political coup is under way, replicating what's been happening across the Atlantic. In the USA, Trump used his personal wealth and connections, along with those of other super-rich oligarchs, to win the election and take control. Despite losing the popular vote by a considerable margin – winning because of the US electoral college system – he showed neither magnanimity nor made any attempt to broker consensus.
Instead it's been open partisanship and outright nepotism. Military commanders removed, others patently unfit for office such as Brett Kavanaugh appointed to the Supreme Court and now Ivanka Trump elevated to a position of some latter-day Henry Kissinger, despite possessing neither the academic record nor intellect.
READ MORE: How Donald Trump will benefit from leak of UK Ambassador's scathing memo – Martyn McLaughlin
READ MORE: Was Donald Trump memo leak a plot by Brexiteers? – Angus Robertson
So it is with the UK and I fear that, with a Boris Johnson Prime Ministership, it's only going to get worse. Oligarchs and the super-rich using their wealth and their media influence to lie and distort. A referendum won with dodgy money and by telling flagrant untruths, even if it was the stupidity of David Cameron that brought it into being. The people who propagated those untruths have been easing themselves into position whilst easing out those who don't agree with them.
Talk of proroguing Parliament's an abomination. Boris Johnson's great hero Winston Churchill didn't even consider that when the country's back was to the wall and a Nazi invasion loomed. Instead, in the national interest, Churchill created a coalition government that not only saw the country through the war but established the welfare state.
But Britain's new ruling class are entirely narcissistic and care only about power and their self-interest. The rights of others matter not one jot and the national interest an irrelevancy – understandable when you consider that they offshore much of their wealth and that, to them, loyalty to the UK is about ensuring privacy in London's financial centre. Deep state indeed.
Stabbing Sir Kim Darroch in the back's the clear embodiment of that. The potential and practical damage to the UK is incalculable. Hey ho, it has removed someone who isn't at one with them or prepared to do their bidding, but so what? Joe Kennedy this is not. JFK's father was the US Ambassador in London but had to be removed in 1940, not just for his opposition to the policies of Churchill in opposing Hitler, but even those of President Roosevelt in trying to sustain democracies.
Now, I've met Darroch when he was at UKREP, as UK representation in Brussels is termed. He's no friend of mine or of Scottish independence. Long before Jeremy Hunt's outrageous decision to rescind support for a First Minister in overseas travel, the FCO was already doing it surreptitiously. Dealing with devolution went from the patronising, through bemusement, to seeking to thwart. Less crass than what the Foreign Secretary proposes, but probably more effective.
But that was because Darroch's a consummate professional and representing his nation's interests. Likewise, full and frank reports from Washington are needed and what he said frankly only echoed what's boradcast nightly on CNN or has already been exposed by White House whistleblowers.
The crime's not what the UK's most senior diplomat reported but its public release. Suggestion of it being the Russians is absurd. This can only have come from the highest level and either from a senior political figure or at their behest. As some have correctly surmised, the answer to the question of who stands to benefit is the Brexiteers, who seem prepared to burn the UK Ambassador – if not the entire UK house down.
Michael Bayne: Give them a Ring – businesses in need of machinery can make big savings
The fallout has seen the outgoing Prime Minister caught in a firestorm unleashed by Trump. It's not just the damage to UK-US relations but how it exposes the weakness of the UK to the rest of the world.
New Britannia's diminishing power and stature are there for all to see. Run for naked self-interest, beholden to and dependent upon an American President who demeans the office and with the UK's global standing sinking even faster than the respect and warmth that once existed for the country.
Too little and too late, the likes of Sir John Major and William Hague are speaking out. But as with Trump and the Republicans, the monster has been unleashed and the Grand Old Party has lost control.
Be afraid, because for these charlatans, our institutions and our interests are as dispensable as the UK Ambassador.


'Electronic business': the experience of russian-swedish program for vocational retraining // Vestnik of the Kazan technological university. – Т. 15, № 19. – Kazan, 2012. – P. 235 - 239.
Planning of joint academic work of students via networks // International conference "ITON-2012", Kazan, 8-12 october. – Kazan, 2012. – P. 172 - 175.
The integrated approach to creation e-learning courses // Open and distance education. — R. 2 (46). — Tomsk, TSU, 2012. — P. 24-27.
Irina Y. Malkova, Artem V. Feschenko.
Potential social networks for designing e-learning courses // Open and distance education. — R. 2 (46). — Tomsk, TSU, 2012. — P. 46-50.


text:
Володимир Миколайович Миски́-Оглу́ ( 18 жовтня 1948, Жданов) — український художник; член творчого об'єднання «Маріуполь–87».

Біографія
Народився 18 жовтня 1948 року в місті Жданові (нині Маріуполь, Україна). У 1970-ті роки навчався у художній студії Будинку культури заводу «Азовсталь» під керівництвом Якова Никодимова.

Творчість
Працює в галузі станкового живопису і графіки. Створював пейзажі, натюрморти, портрети в реалістичному стилі. Серед робіт:

живопис
 «Теплі трави» (1976);
 «Спогади про Рембрандта» (1990-ті);
 «Художник» (1991);
 «Тиша вечора. Квіти у корзинці» (1993);
 «Автопортрет» (1994);
 «Дівчинка з собачкою» (1995);
 «Мій друг звіробій» (2000-ні);
 «Весняна майстерня художника» (2000-ні);
 «Танець із невідомим» (2018).
</div>
Брав участь у всеукраїнських виставках з 1976 року, зарубіжних — з 1991 року. Персональні виставки відбулися у Маріуполі у 1991, 2003, 2009, 2018 роках.

Деякі роботи художника зберігаються в Маріупольському краєзнавчому музеї, в приватних колекціях України, Франції, Австрії.

Примітки

Література

Українські живописці
Радянські художники
Українські графіки
Радянські графіки
Художники Маріуполя
Українські пейзажисти
Радянські художники-пейзажисти
Українські портретисти
Радянські художники-портретисти
Українські натюрмортисти
Радянські натюрмортисти
Художники-реалісти

redpajama_set_name: RedPajamaWikipedia


If you're a part of the ultimate girl gang aka the bridal party, there's only one thing you're looking forward to more than the wedding itself, and that's the hen's night.
Unlike those lucky Europeans who can take a short plane ride to a holiday destination for the weekend, us Aussie's are a little more limited. Luckily for us, Melbourne is an urban destination of hen's party dreams!
In a city where exclusive restaurants and hotels actually double as nightclubs (seriously!), and an empty doorway can lead to the best night of your life, prepare for a girl's night on the town that you won't forget for a very, long time.
In a city as versatile as this, there's something to suit every kind of bride and every type of bridal party. From private booths in luxurious nightclubs to a high tea with panoramic views of the skyline, you can literally have it all in just one weekend.
When cocktails, male strippers and travelling in VIP limousines is on the cards then why, oh why would you go anywhere else?
Set in Melbourne VIP's favourite boutique hotel The Adelphi, head to Mon Bijou during the day or night. This Instagram worthy space offers an unforgettable experience since its set in a penthouse, high above the clouds. Posing incredible views of the city with its feminine yet fierce décor, this venue is one of the best places to start your Melbourne hen's weekend. With the option to enjoy a first-class high tea dining experience with all of your girls, to a little later where you can spend your evening sipping on modern cocktails, it's perfect for making your hens dreams come true! The best of both worlds under one, gorgeous roof.
Baroq house, the perfect venue for you and your girls to… play. Featuring a number of exclusive rooms (with just as many bars!), this nightclub offers luxurious booths, opulent table settings and a hidden outdoor area. Party the night in your own private booth with table service like an A-lister and enjoy the atmosphere of the nightclub that's hidden within a 19th century cobblestoned laneway. A hidden gem, the mansion style building and incredible décor makes for one of the classiest hen's nights a girl could ever wish for.
If you and the whole girl gang are after a trendy spot that you probably won't leave until the very early hours of the morning, Bond is the one for you. Located on the cities vibrant Bond St, your jaw will literally drop as soon as you set foot through the door. Golden, glitzy and glamorous, the amphitheatre setup makes Bond the modern-day Studio 54. Perfect for the wilder of hen's parties, you can dance to live music and the cities coolest DJ's. Whether you hire your own private area or party amongst the cities elite, you and your bridesmaids are in for a night to remember.
Not sure where to host your hen's night? Speak to an events planner at Collective Establishments for a tailor-made package party deal. Like we said, the possibilities are endless in a city that never really sleeps.


Mood instability is a core clinical feature of affective disorders, particularly major depressive disorder (MDD) and bipolar disorder (BD). It may be a useful construct in line with the Research Domain Criteria (RDoC) approach, which proposes studying dimensional psychopathological traits that cut across diagnostic categories as a more effective strategy for identifying the underlying biology of psychiatric disorders. Here we report a genome-wide association study (GWAS) of mood instability in a very large study of 53,525 cases and 60,443 controls from the UK Biobank cohort, the only such GWAS reported to date. We identified four independent loci (on chromosomes eight, nine, 14 and 18) significantly associated with mood instability, with a common SNP-based heritability estimate for mood instability of approximately 8%. We also found a strong genetic correlation between mood instability and MDD (0.60, SE=0.07, p=8.95xl0−17), a small but statistically significant genetic correlation with schizophrenia (0.11, SE=0.04, p=0.01), but no genetic correlation with BD. Several candidate genes harbouring variants in linkage disequilibrium with the associated loci may have a role in the pathophysiology of mood disorders, including the DCC netrin 1 receptor (DCC), eukaryotic initiation factor 2B (EIF2B2), placental growth factor (PGF) and protein tyrosine phosphatase, receptor type D (PTPRD) genes. Strengths of this study include the large sample size; however, our measure of mood instability may be limited by the use of a single self-reported question. Overall, this work suggests a polygenic basis for mood instability and opens up the field for the further biological investigation of this important cross-diagnostic psychopathological trait.


text:
Law Society blog - Theresa May
Here are all the posts tagged with "Theresa May".
Westminster weekly update: Lord chancellor announces £2 million boost for UK lawtech
Your weekly update from the Law Society's public affairs team on all the latest developments and debates in Parliament and across Whitehall.
Westminster weekly update: Law Society gives evidence on court and tribunal reforms
Westminster weekly update: Prime minister appears before senior backbenchers
Westminster weekly update: Lord chancellor quizzed by Justice Committee on LASPO
Westminster weekly update: Commons votes on amendments to Brexit motion
On Tuesday, the Commons voted on a series of amendments to the prime minister's motion on Brexit.
Westminster weekly update: Prime minister makes statement to the commons
Last Monday the prime minister made a statement to the Commons, setting out her intention for proceeding with the Brexit process.
Westminster weekly update: Government loses on Withdrawal Agreement but wins confidence vote
On Tuesday the government's Brexit withdrawal agreement was rejected in Parliament by a margin of 230 votes - the largest defeat ever suffered by a sitting government.
Westminster weekly update: Courts and Tribunals Bill progresses while meaningful vote postponed
The Courts and Tribunals (Judiciary and Functions of Staff) Bill completed its passage through the House of Commons after concluding its remaining stages last week.
Westminster weekly update: Parliament returns from conferences to justice questions and Counter-Terrorism Bill
Parliament returns from its conference recess this week, and justice-related issues will take centre-stage as the Lord Chancellor and his ministerial team face questions in the House of Commons on Tuesday morning.
Prisons and Courts Bill falls
Last Tuesday, the prime minister announced that she will be asking Parliament to vote for a general election on 8 June. On Wednesday, the House of Commons surpassed the two thirds majority needed to approve the motion by 522 to 13.
Snap general election 2017 and the legal profession
On Tuesday 18 April the prime minister took Westminster and the country by surprise in announcing that she will be tabling a motion to the House of Commons to call for a General Election. On 19 April the House of Commons surpassed the two thirds majority needed to approve the motion by 522 to 13 and approved that a General Election will take place on 8 June.
Article 50 is triggered and the Law Society gave evidence to Prisons and Courts Bill
This week the House of Commons will begin its Easter recess and will return on Monday 18 April. The House of Lords will continue to sit with a number of motions on Brexit and evidence sessions on co-operation with the EU on criminal justice and security.
Article 50 likely to be triggered this week
The prime minister is expected to trigger Article 50 by her 31 March deadline.
Brexit priorities for the legal sector
The legal sector is playing a key role in shaping the upcoming negotiations for exiting the EU. Robert Bourns considers priorities for the profession during this period of transition.
The spectre of May vs. Osborne
Richard Messingham reflects on a week when the home secretary Theresa May managed to steer clear of significant controversy when she introduced some long awaited changes to the law on investigatory powers.


Sherine Abdel Wahab, known simply as Sherine, had apologized after being caught on tape joking with concert goers that Nile water could give them parasites.
The Cairo misdemeanour court convicted her of having spread "false news." Judicial officials said she would remain free on bail pending an appeal.
"bilharzia", a name for the parasitic disease schistosomiasis which was once widespread in Egypt.
She later apologized in a Facebook posting.