Abstract
Structured sparsity has recently emerged in statistics, machine learning and signal processing as a promising paradigm for learning in high-dimensional settings. All existing methods for learning under the assumption of structured sparsity rely on prior knowledge on how to weight (or how to penalize) individual subsets of variables during the subset selection process, which is not available in general. Inferring group weights from data is a key open research problem in structured sparsity. In this paper, we propose a Bayesian approach to the problem of group weight learning. We model the group weights as hyperparameters of heavy-tailed priors on groups of variables and derive an approximate inference scheme to infer these hyperparameters. We empirically show that we are able to recover the model hyperparameters when the data are generated from the model, and we demonstrate the utility of learning weights in synthetic and real denoising problems.
Introduction
In high-dimensional statistics, where the number of variables often exceeds the number of observations, sparsity-inducing methods like the Lasso are essential for model interpretability and generalization. However, many real-world signals exhibit inherent structures—such as genes organized in pathways or wavelet coefficients forming trees—that standard sparsity models ignore. Structured sparsity (e.g., Group Lasso) addresses this by penalizing groups of variables together.
The primary challenge in structured sparsity is the requirement for prior knowledge: one must manually define the groups and their relative importance (weights). If these weights are misspecified, the model's performance degrades. This work introduces a Bayesian framework to automatically learn these group weights from data, effectively "learning the structure" itself.
Methodology: Bayesian Multi-Task Learning
The proposed approach leverages multi-task learning, assuming that while individual tasks (e.g., different image patches) may have different coefficients, they share a common underlying structure.
Model Representation
The coefficient vector $w$ is modeled as a sum of latent vectors $v_A$, where each $v_A$ is supported on a specific group of variables $A \in \mathcal{A}$. This allows for overlapping groups, where a single variable can be influenced by multiple structural components.
Probabilistic Framework
The model assigns "super-Gaussian" (heavy-tailed) priors to the latent vectors $v_A$. These priors, such as Student’s $t$ or Generalized Gaussian distributions, naturally encourage sparsity by driving the weights of irrelevant groups toward infinity.
To handle the intractability of these priors, the authors derive a scalable variational inference scheme. This provides closed-form updates for group weights. Furthermore, to manage the potentially exponential number of candidate groups, an Active Set procedure is employed. This greedy algorithm starts with simple groups and iteratively incorporates more complex overlapping structures based on their learned relevance.
Experimental Evaluation
The framework was evaluated on synthetic data and real-world image denoising tasks.
Synthetic Data
In simulations, the model successfully recovered true hyperparameters and signal components. In scenarios with overlapping groups, the "Structured" and "Structured (Active Set)" variants reduced squared error by approximately 20-25% compared to standard Lasso-based models.
Image Denoising
The method was applied to benchmark images (Barbara, Fingerprint, Lena, House) using Haar wavelet decompositions. On the Fingerprint image, which contains highly structured directional textures, the learned structure outperformed fixed tree-structured models (Tree-$\ell_2$). This demonstrates that data-driven structure learning can surpass expert-defined heuristics.
Discussion and Conclusion
This research bridges the gap between frequentist sparsity-inducing norms and Bayesian heavy-tailed priors. A key insight is the necessity of multi-task data: observing the structure across multiple related instances is crucial for reliable weight inference.
While the Active Set procedure offers scalability, it remains a greedy heuristic. Future work includes extending the likelihood models beyond Gaussian noise to accommodate classification tasks and exploring more complex structural search strategies. By automating structure discovery, this framework significantly broadens the applicability of structured sparsity to domains where prior knowledge is scarce.
Summary updated