L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing

arXiv cs.LG / 4/21/2026

📰 NewsDeveloper Stack & InfrastructureModels & Research

共有:

Key Points

The paper studies how to compute L1 regularization paths in a state-space framework that unifies problems such as L1-regularized Kalman smoothing, linear SVM, and LASSO.
It introduces two dual algorithms, one for L1 regularization on independent variables and another for L1 regularization on dependent variables.
The core technique is parametric Gaussian message passing, implemented via Kalman-style forward-backward recursions on the relevant factor graphs.
The authors claim broad applicability and that the methods often rely mainly on matrix multiplications, with competitiveness versus earlier approaches in some settings.

Abstract

The paper considers the computation of L1 regularization paths in a state space setting, which includes L1 regularized Kalman smoothing, linear SVM, LASSO, and more. The paper proposes two new algorithms, which are duals of each other; the first algorithm applies to L1 regularization of independent variables while the second applies to L1 regularization of dependent variables. The heart of the proposed algorithms is parametric Gaussian message passing (i.e., Kalman-type forward-backward recursions) in the pertinent factor graphs. The proposed methods are broadly applicable, they (usually) require only matrix multiplications, and their complexity can be competitive with prior methods in some cases.