Variational Inference of Penalized Regression with Submodular Functions
Koh Takeuchi, Yuichi Yoshida, Yoshinobu Kawahara
Abstract
Various regularizers inducing structured-sparsity are constructed as Lovász extensions of submodular functions. In this paper, we consider a hierarchical probabilistic model of linear regression and its kernel extension with this type of regularization, and develop a variational inference scheme for the posterior estimate on this model. We derive an upper bound on the partition function with an approximation guarantee, and then show that minimizing this bound is equivalent to the minimization of a quadratic function over the polyhedron determined by the corresponding submodular function, which can be solved efficiently by the proximal gradient algorithm. Our scheme gives a natural extension of the Bayesian Lasso model for the maximum a posteriori (MAP) estimation to a variety of regularizers inducing structured sparsity, and thus this work provides a principled way to transfer the advantages of the Bayesian formulation into those models. Finally, we investigate the empirical performance of our scheme with several Bayesian variants of widely known models such as Lasso, generalized fused Lasso, and non-overlapping group Lasso.
BibTeX
@InProceedings{pmlr-v115-takeuchi20a,
title = {Variational Inference of Penalized Regression with Submodular Functions},
author = {Takeuchi, Koh and Yoshida, Yuichi and Kawahara, Yoshinobu},
booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference},
pages = {1202--1211},
year = {2020},
editor = {Adams, Ryan P. and Gogate, Vibhav},
volume = {115},
series = {Proceedings of Machine Learning Research},
month = {22--25 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v115/takeuchi20a/takeuchi20a.pdf},
url = {https://proceedings.mlr.press/v115/takeuchi20a.html},
abstract = {Various regularizers inducing structured-sparsity are constructed as Lovász extensions of submodular functions. In this paper, we consider a hierarchical probabilistic model of linear regression and its kernel extension with this type of regularization, and develop a variational inference scheme for the posterior estimate on this model. We derive an upper bound on the partition function with an approximation guarantee, and then show that minimizing this bound is equivalent to the minimization of a quadratic function over the polyhedron determined by the corresponding submodular function, which can be solved efficiently by the proximal gradient algorithm. Our scheme gives a natural extension of the Bayesian Lasso model for the maximum a posteriori (MAP) estimation to a variety of regularizers inducing structured sparsity, and thus this work provides a principled way to transfer the advantages of the Bayesian formulation into those models. Finally, we investigate the empirical performance of our scheme with several Bayesian variants of widely known models such as Lasso, generalized fused Lasso, and non-overlapping group Lasso.}
}