BALSON: Bayesian Least Squares Optimization with Nonnegative L1-Norm Constraint

Jiyang Xie, Zhanyu Ma, Guoqiang Zhang, Jing-Hao Xue, Jen-Tzung Chien, Zhiqing Lin, Jun Guo

Introduction

Least Squares Optimization (LSO) is a fundamental tool in statistics and machine learning for fitting models by minimizing the sum of squared errors. However, standard LSO often results in overfitted models with numerous small, non-zero parameters. To address this, researchers frequently employ constraints such as the $L_1$-norm (to encourage sparsity) and nonnegativity (crucial for physical systems like fluid dynamics or bioinformatics where negative values are physically impossible).

While frequentist methods like LASSO are common, they lack a probabilistic framework for uncertainty. Conversely, standard Bayesian approaches like the Bayesian LASSO use a Laplace prior, which has "negative support" and thus does not inherently respect nonnegativity constraints. This paper introduces BALSON (BAyesian Least Squares Optimization with Nonnegative $L_1$-norm constraint), a framework that naturally integrates both sparsity and nonnegativity.

Methodology

The BALSON framework treats optimization as a Maximum A Posteriori (MAP) estimation problem. The core innovation lies in the choice of prior and the mapping between frequentist and Bayesian components.

Conceptual comparison between frequentist and Bayesian approaches to constrained optimization.
  1. Likelihood: A standard Gaussian likelihood is used to model data-fitting errors.
  2. Prior: Instead of a Laplace prior, the authors employ a Dirichlet distribution. The Dirichlet distribution is defined on a simplex, meaning its components are non-negative and sum to a constant. This perfectly mirrors a normalized $L_1$ constraint.
  3. Posterior Approximation: Since the combination of a Gaussian likelihood and a Dirichlet prior is not analytically tractable, the authors approximate the posterior as a Dirichlet distribution by matching its statistical moments (mean and variance).
  4. Sampling Algorithms: To estimate these moments, four sampling methods were evaluated: Rejection Sampling (RS), Importance Sampling (IS), and their iterative resampling counterparts (RSIRS and ISIRS). The RSIRS method proved most effective for refining parameter estimates.

Key Insights

The Dirichlet distribution's geometry is leveraged for sparsity. When its parameters ($\alpha$) are less than 1, the distribution's mode pushes toward the edges of the simplex, naturally enforcing sparsity. Furthermore, the authors demonstrate that Bayesian LASSO can be viewed as a special case of BALSON, making it a more general and unified framework.

Experimental Setup

The framework was evaluated using a Polynomial Curve Fitting task. A 5-dimensional polynomial curve was fitted to noisy data (100 training points) generated from a known sparse, non-negative parameter vector. Performance was measured using Mean Squared Error (MSE) on 1000 test points and a sparsity score. BALSON was compared against frequentist LASSO, Interior-Point (IP) methods, and standard Bayesian LASSO.

Key Results

Experimental results demonstrate that BALSON variants, particularly RSIRS and ISIRS, significantly outperform traditional methods in both accuracy and sparsity.

Performance comparison of BALSON variants against baseline methods in terms of MSE and sparsity.
  • Accuracy: BALSON-RSIRS achieved an MSE of 0.0116, a substantial improvement over LASSO (0.0209) and Bayesian LASSO (0.0370).
  • Sparsity: BALSON-ISIRS achieved a sparsity score of 0.8675, far exceeding LASSO (0.6660) and Bayesian LASSO (0.3833).
  • Visual Fidelity: Qualitative analysis showed that BALSON's fitted curves were significantly closer to the ground truth than baseline methods, which often over-smoothed or misestimated peaks.

Conclusion and Future Work

BALSON provides a robust Bayesian alternative for constrained optimization. While it offers superior performance, it is computationally more intensive than frequentist methods due to its reliance on iterative sampling. Future work aims to replace sampling with Variational Bayes (VB) methods to improve speed and determinism. The authors also plan to apply this framework to real-world challenges in hyperspectral imaging and compressive sensing.

Summary updated

Abstract

A Bayesian approach termed the BAyesian Least Squares Optimization with Nonnegative L1-norm constraint (BALSON) is proposed. The error distribution of data fitting is described by Gaussian likelihood. The parameter distribution is assumed to be a Dirichlet distribution. With the Bayes rule, searching for the optimal parameters is equivalent to finding the mode of the posterior distribution. In order to explicitly characterize the nonnegative L1-norm constraint of the parameters, we further approximate the true posterior distribution by a Dirichlet distribution. We estimate the moments of the approximated Dirichlet posterior distribution by sampling methods. Four sampling methods have been introduced and implemented. With the estimated posterior distributions, the original parameters can be effectively reconstructed in polynomial fitting problems, and the BALSON framework is found to perform better than conventional methods.
BibTeX
@inproceedings{xie2018balson,
  author = {Jiyang Xie and Zhanyu Ma and Guoqiang Zhang and Jing-Hao Xue and Jen-Tzung Chien and Zhiqing Lin and Jun Guo},
  title = {{BALSON: Bayesian Least Squares Optimization with Nonnegative L1-Norm Constraint}},
  booktitle = {MLSP},
  year = {2018},
  url = {https://openreview.net/forum?id=JGHqezQKd8},
}
Figure