L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing

Abstract:The paper proposes new algorithms for computing the regularization path of linear-model fitting (i) with L1 costs for the independent variables and L2 costs for the dependent variables, and (ii) with L2 costs for the independent variables and L1 costs for the dependent variables. Unlike previously proposed algorithms, the proposed algorithms for (i) and (ii) are exact duals of each other. The heart of the proposed algorithms is parametric Gaussian message passing (i.e., Kalman-type forward-backward recursions) in the pertinent factor graphs. We first develop such algorithms for linear models with general (but preferably low-dimensional) state space representations. We then specialize to specific state space representations of generic linear models; in this case, the structure of the factor graph allows to refine the proposed algorithms such that the computational complexity drops to linear scale.

Machine Learning (cs.LG); Signal Processing (eess.SP); Methodology (stat.ME)

arXiv:2604.16949 [cs.LG]

(or arXiv:2604.16949v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2604.16949 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.