L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing

arXiv:2604.16949 · cs.LG, eess.SP, stat.ME · Submitted 2026-04-18 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing".

Jane: The gist The paper proposes two new algorithms, which are duals of each other,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: Let's talk about the title and who wrote this paper, "L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing."

Jane: The authors are Yun-Peng Li and Hans-Andrea Loeliger from ETH Zürich, and they are proposing these new dual algorithms.

Lu: The authors clearly have a strong background in the math of computing and factor graphs, which is exactly where this paper lives.

Meng: It’s not just about applying some existing technique; they are building something new by using parametric Gaussian message passing in a specific way for L1 regularization.

Lalam: It suggests that you can solve these path problems by modeling them as state space models, which is a powerful way to approach them.

Tom: Basically, the title tells us the methods they use—parametric Gaussian message passing—and what they are solving—L1 regularization paths in linear models.

Jane: So, what does this actually mean for someone who isn't deep into state space modeling? It means we might be able to compute these complex paths using tools that rely on matrix multiplications.

Lu: The paper points out that the proposed methods are broadly applicable and usually only require matrix multiplications, which is a good sign for practical use.

Meng: That’s important because it suggests the complexity can be competitive with prior methods in some cases, which is what engineers care about when implementing something.

The paper's summary: Tom: Now, let's look at the actual summary of "L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing."

Jane: The authors summarize that they are looking at fitting a linear model while minimizing a cost function involving an L1 penalty on either the independent or dependent variables.

Lu: They set up this problem using linear state space models where the states evolve according to specific dynamics and outputs are determined by those states.

Meng: This statistical model allows them to express both problems (five) and (eight) as a joint Maximum A Posteriori estimate of the independent variables and the dependent variables <ref:2604.16949#pg2>.

Lalam: The joint probability density function is given as a product of conditional densities involving Gaussian distributions, parameterized by variances related to s squared.

Tom: So, they’re using this statistical setup to get a handle on the joint MAP estimate for both the inputs and the outputs simultaneously.

Jane: What’s interesting is how they use this framework to derive specific path algorithms for computing u hat of s squared for problem (one) <ref:2604.16949#pg1>.

Lu: They propose Algorithm two which uses parametric Gaussian message passing in a factor graph and repeatedly calls Algorithm one or BFFD, with specific conditions satisfied to track the active segments of the cost function <ref:2604.16949#pg2>.

Meng: This is basically a dynamic way to track where the cost function is active as you vary s squared.

The paper's improvements: Tom: Let's talk about what the paper actually suggests as improvements over existing methods.

Jane: The key improvement, especially for algorithm two is its use of parametric BFFD according to Section three point three, which tracks the active segments in a variation of standard ideas used in active-set methods <ref:2604.16949#pg2>.

Lu: The authors prove that when BFFD is called with those specific conditions satisfied, then for all n, (i) minus W X n is a linear function of s squared and minus X n is an affine function of s squared.

Meng: That's a huge statement because it means the posterior mean m X n—which they call the estimate x hat n—is an affine function of s squared.

Lalam: And they also show that the dual algorithm, algorithm four which computes y hat of s squared for problem (two), has similar properties regarding linear and affine functions of s squared <ref:2604.16949#pg2>.

Tom: So, essentially they prove these specific functional forms for the estimates under these conditions for both the primal and dual paths.

Jane: It’s a lot to unpack because it ties the algorithmic structure directly to how the solution behaves as you change the parameter s squared, which is what makes these paths useful.

Conclusion: Tom: So, wrapping up with the conclusion of "L1 Regularization Paths in Linear Models by Parametric Gaussian Message Passing."

Jane: The paper summarizes that they have developed two dual algorithms, PathBFFD for the input path and PathFFBDD for the output path.

Lu: They show that these methods are particularly attractive if the matrix F in problems (one) or (two) admits a low-dimensional state space representation <ref:2604.16949#pg2>.

Meng: From an engineering standpoint, this means if we can find a low-dimensional way to represent the matrix F, these algorithms become very efficient.

Lalam: Lalam thinks that these proposed algorithms could significantly improve how we handle L1 regularized least squares when K is much larger than L, which is important for machine learning.

Tom: They conclude by showing that the final result of Algorithm two gives us a list of knots s squared zero through s squared l minus one and infinity, along with the affine representations u hat n of s squared between those points <ref:2604.16949#pg2>.

Jane: It’s a solid piece of work because it provides concrete methods for computing these paths using Gaussian message passing.

Lu: Overall, it lays down a foundation for applying this framework to more general continuous piecewise linear and convex regularizing cost functions in the future.

Meng: For practical implementation, the focus will be on how smoothly we can connect these different segments together efficiently when dealing with large matrices.

Lalam: It’s exciting because it gives us a framework that applies to a lot of different L1 regularization problems, not just one specific case.

ETH Zürich

cs.LG, eess.SP, stat.ME

Submitted: 2026-04-18

Updated: 2026-10-13

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 80/100

The gist: The gist The paper proposes two new algorithms, which are duals of each other, for computing L1 regularization paths in linear models by applying parametric Gaussian message passing in state space

Key concepts

L1 Regularization Paths: These are specific sequences of parameter values that define how the solution changes when applying an L1 penalty (like Lasso) to a linear model. Finding these paths helps understand the regularization effect across different penalty strengths.
Parametric Gaussian Message Passing: This is a technique used within state space models where Gaussian distributions are passed between different parts of the model. It allows the algorithm to track how uncertainty evolves as parameters change, which is key for finding the exact paths efficiently.
State Space Model: The linear model problem is reformulated using a state space model, where variables evolve over time or steps according to certain rules. This framework helps structure the complex optimization problem into a sequence of manageable probabilistic steps.

Terminology

Regularization — 4× in this paper · explained in 3 episodes

Summary

The gist The paper proposes two new algorithms, which are duals of each other, for computing L1 regularization paths in linear models by applying parametric Gaussian message passing in state space models.

Problem Formulation and Context

The work considers fitting a linear model by minimizing a cost function involving an L1 penalty on the independent variables or the dependent variables, specifically addressing problems (1) and (2) which are numerically computed as regularization paths for all values of the parameter and. The proposed methods are broadly applicable, usually requiring only matrix multiplications, and their complexity can be competitive with prior methods in some cases. The paper focuses on efficiently computing the exact paths in (1) and (2), which are parametric quadratic programming problems.

Statistical State Space Model

The problem is reformulated in terms of linear state space models where states evolve according to and outputs are determined by. For the general case (5), the joint probability density function is given by a product of conditional densities involving Gaussian distributions parameterized by variances related to s squared. This statistical model allows both (5) and (8) to amount to the joint MAP estimate of the independent variables X0 and U = (U1,..., UN)T and the dependent variables X1,..., XN and Y = (Y1,..., YN)T.

Regularized Input Path by Parametric Backward Filtering Forward Deciding

The proposed algorithm for computing the path uˆ(s 2) for (1) is Algorithm 2, which employs parametric Gaussian message passing in a factor graph. This involves repeatedly calling Algorithm 1 (BFFD) with specific conditions satisfied to track the active segments of the cost function. The algorithm determines knots s 2 l,n = sup s 2: uˆ n(s 2) is in the active subdomain of.

Regularized Output Path by Parametric Forward Filtering Backward Dual Deciding

The dual algorithm for computing the path yˆ(s 2) for (2) is Algorithm 4, which uses parametric FFBDD. This algorithm repeatedly calls Algorithm 3 (FFBDD) with specific conditions satisfied to track the active segments of the cost function. The algorithm determines knots s 2 l,n = sup s 2: yˆ n(s 2) is in the active subdomain of.

Complexity and Novelty

The space complexity of PathBFFD is O (NM + M 2) in total, and the time complexity is O (NM 3) per knot in general, although it can be reduced to O (NM squared + M 3) per knot if the matrix A permits matrix-(square-)matrix multiplication with O (M 2). The essential novelty of Algorithm 2 is its use of parametric BFFD according to Section 3.3, which tracks the active segments in a variation of standard ideas in active-set methods. The paper proves that when BFFD is called with the above conditions satisfied, then for all n, (i) ←− WXn is a linear function of s-2 and ←− ㉯Xn is an affine function of s squared; (ii) the posterior mean mXn (= the estimate xˆ n) is an affine function of s squared; and (iii) ←− VUn is a linear function of s squared and ←− mUn is an affine function of s squared. The dual algorithm similarly shows that for all n, (i) −Vxn is a linear function of s squared and −mXn is an affine function of s squared; (ii) the dual mean ˜㉯Xn is an affine function of s-2; and (iii) −Vyn is a linear function of s squared and −mYn is an affine function of s squared. The proposed algorithms are especially attractive if the matrix F in (1) or (2) admits a low-dimensional state space representation.

Numerical Examples

The paper demonstrates PathBFFD and PathFFBDD for filtering a global warming dataset [7] and regression on a diabetes dataset [5]. The results show snapshots of the exact regularization paths computed by PathBFFD and (as a sanity check) by genLASSO. The time complexity of the algorithms used in these examples is shown in Table 2. PathBFFD is attractive for L1 regularized least squares if K >> L, which is an important case in machine learning. The final result of Algorithm 2 consists of the list s 2 0 = 0, s 2 1,..., s 2 l-1, s 2 l = ∞ and the affine representations uˆ n (s 2) between these points. The essential novelty of Algorithm 2 is its use of parametric BFFD according to Section 3.3. The proposed algorithms are especially attractive if the matrix F in (1) or (2) admits a low-dimensional state space representation.

Appendices

Appendix A reproduces some tables from [14] and [13], which are used in the proposed algorithms. Appendix B gives the simplified versions of the proposed algorithms for two important special cases. Appendices C and D prove the pivotal Propositions 3.1 and 4.1 and provide details of the proposed algorithms. The tables in Appendix A improve on the tables in [13]. Table A.2 shows Gaussian message passing through composite linear blocks. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.1 shows Gaussian message passing through elementary linear constraints. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.2 shows Gaussian message passing through composite linear blocks. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.1 shows Gaussian message passing through elementary linear constraints. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.2 shows Gaussian message passing through composite linear blocks. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.1 shows Gaussian message passing through elementary linear constraints. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.2 shows Gaussian message passing through composite linear blocks. Table A.3 shows Posteriors (m, V) and their duals (㉯, ⊨). Table A.1 shows Gaussian message passing through elementary linear constraints. Table A.

Improvements for AI systems

Bold header: PathBFFD for L1 Regularization Paths

This algorithm computes the exact paths in (1) and (2), which are parametric quadratic programming problems, by exploiting a state space model of the input matrix, making it applicable to L1 regularization of independent variables.

Bold header: PathFFBDD for Dual Regularization Paths

This dual algorithm computes the path for dependent variables by utilizing Parametric FFBDD, which is described as dual to BFFD and effectively solves the convex dual of (8) by dynamic programming.

Bold header: Generalization to Piecewise Linear Convex Costs

The methods are designed to handle cost functions where L1 regularization has long been heavily used, specifically supporting general continuous piecewise linear and convex regularizing cost functions.