**Bert Kappen**

(Radboud University Nijmegen)

Wednesday 11th April 2012

16:00

** **

B10 Seminar Room, Basement,

Alexandra House, 17 Queen Square, London, WC1N 3AR

**The variational Garrote**

In this talk, I present a new solution method for sparse regression using $L_0$ regularization. The model introduces a sparseness mechanism in the likelihood, instead of in the prior, as is done in the spike and slab model. The posterior probability for $s_i$ is computed in the variational approximation. The variational parameters appear in the approximate model in a way that is similar to Breiman's Garrote model. I refer to this method as the variational Garrote (VG).

The VG is compared numerically with the Lasso method and with ridge regression. Numerical results on synthetic data show that the VG yields more accurate predictions and more accurately reconstructs the true model than the other methods. The naive implementation of the VG scales cubic with the number of features. By introducing Lagrange multipliers we obtain a dual formulation of the problem that scales cubic in the number of samples, but close to linear in the number of features.