  Theoretical results show that Bayesian methods can achieve lower bounds on
regret for online logistic regression. In practice, however, such techniques
may not be feasible especially for very large feature sets. Various
approximations that, for huge sparse feature sets, diminish the theoretical
advantages, must be used. Often, they apply stochastic gradient methods with
hyper-parameters that must be tuned on some surrogate loss, defeating
theoretical advantages of Bayesian methods. The surrogate loss, defined to
approximate the mixture, requires techniques as Monte Carlo sampling,
increasing computations per example. We propose low complexity analytical
approximations for sparse online logistic and probit regressions. Unlike
variational inference and other methods, our methods use analytical closed
forms, substantially lowering computations. Unlike dense solutions, as Gaussian
Mixtures, our methods allow for sparse problems with huge feature sets without
increasing complexity. With the analytical closed forms, there is also no need
for applying stochastic gradient methods on surrogate losses, and for tuning
and balancing learning and regularization hyper-parameters. Empirical results
top the performance of the more computationally involved methods. Like such
methods, our methods still reveal per feature and per example uncertainty
measures.
