  This work considers variational Bayesian inference as an inexpensive and
scalable alternative to a fully Bayesian approach in the context of
sparsity-promoting priors. In particular, the priors considered arise from
scale mixtures of Normal distributions with a generalized inverse Gaussian
mixing distribution. This includes the variational Bayesian LASSO as an
inexpensive and scalable alternative to the Bayesian LASSO introduced in [56].
It also includes priors which more strongly promote sparsity. For linear models
the method requires only the iterative solution of deterministic least squares
problems. Furthermore, for $n\rightarrow \infty$ data points and p unknown
covariates the method can be implemented exactly online with a cost of O(p$^3$)
in computation and O(p$^2$) in memory. For large p an approximation is able to
achieve promising results for a cost of O(p) in both computation and memory.
Strategies for hyper-parameter tuning are also considered. The method is
implemented for real and simulated data. It is shown that the performance in
terms of variable selection and uncertainty quantification of the variational
Bayesian LASSO can be comparable to the Bayesian LASSO for problems which are
tractable with that method, and for a fraction of the cost. The present method
comfortably handles n = p = 131,073 on a laptop in minutes, and n = 10$^5$, p =
10$^6$ overnight.
