Abstract
We consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of $\ell_2$- or $\ell_\infty$-norms over groups of variables. Whereas much effort has been put in developing fast optimization techniques when the groups are disjoint or embedded in a hierarchy, we address here the case of general overlapping groups. To this end, we present two different strategies: On the one hand, we show that the proximal operator associated with a sum of $\ell_\infty$-norms can be computed exactly in polynomial time by solving a quadratic min-cost flow problem, allowing the use of accelerated proximal gradient methods. On the other hand, we use proximal splitting techniques, and address an equivalent formulation with non-overlapping groups, but in higher dimension and with additional constraints. We propose efficient and scalable algorithms exploiting these two strategies, which are significantly faster than alternative approaches. We illustrate these methods with several problems such as CUR matrix factorization, multi-task learning of tree-structured dictionaries, background subtraction in video sequences, image denoising with wavelets, and topographic dictionary learning of natural image patches.
Introduction
In high-dimensional machine learning, sparsity-inducing penalties like the $\ell_1$ norm (Lasso) are standard tools for feature selection. By forcing many model weights to exactly zero, these methods identify the most relevant variables. However, standard $\ell_1$ regularization treats variables as independent entities, ignoring the inherent structural relationships often present in real-world data—such as spatial proximity in images, temporal continuity in video, or hierarchical structures in biological networks.
Structured sparsity-inducing norms, such as the Group Lasso, address this by penalizing groups of variables together. While optimization is straightforward when these groups are disjoint or hierarchically nested, it becomes significantly more complex when groups overlap arbitrarily (e.g., sliding windows in image processing). This paper introduces a novel framework that maps the optimization of overlapping $\ell_\infty$ group norms to network flow problems, providing a fast, exact, and scalable solution.
The Optimization Challenge: Overlapping Groups
When groups of variables overlap, the proximal operator—a key component in modern first-order optimization methods—does not have a closed-form solution. Previous attempts to solve this problem typically relied on:
- Subgradient Descent: Often slow to converge.
- Smoothing Techniques: These approximate the norm but fail to produce "true" zeros, undermining the primary goal of structured sparsity.
- Variable Splitting: Methods like ADMM can handle overlaps by duplicating variables, but they often suffer from high memory overhead and slower convergence in high dimensions.
The authors seek to overcome these limitations by developing an exact proximal operator that maintains the sparsity structure while remaining computationally efficient.
Proposed Methodology
1. Network Flow Optimization (ProxFlow)
The core contribution of this work is the mathematical proof that computing the proximal operator for a sum of overlapping $\ell_\infty$-norms is equivalent to solving a quadratic min-cost flow problem.
The authors construct a directed graph where nodes represent variables and groups, capacities correspond to regularization weights, and costs are derived from the residuals. They introduce a custom divide-and-conquer algorithm, ProxFlow, which recursively utilizes the push-relabel max-flow algorithm. This approach allows for the exact calculation of the proximal operator in polynomial time. Furthermore, they demonstrate that the dual norm—essential for calculating duality gaps and determining convergence—can be computed using a similar max-flow formulation.
2. Proximal Splitting (ADMM)
For cases where the network flow equivalence does not directly apply—specifically when using $\ell_2$-norms for overlapping groups—the authors utilize an Alternating Direction Method of Multipliers (ADMM) approach. By introducing latent variables to decouple the overlaps, they transform the problem into a higher-dimensional space where the groups are disjoint, allowing for standard proximal updates.
Experimental Evaluation
The algorithms were tested across a diverse range of tasks to evaluate speed and accuracy:
- Computational Efficiency: On synthetic benchmarks with 1 million variables, the ProxFlow algorithm computed the proximal operator in 113 seconds, compared to 525 seconds for standard parametric max-flow algorithms (GGT). Generic interior-point methods were unable to handle the problem size.
- Image Denoising: Using a grid-based overlapping norm ($\Omega_{grid}$) on 12 standard test images, the proposed method improved the Peak Signal-to-Noise Ratio (PSNR) by up to 1.92 dB over standard $\ell_1$ soft-thresholding.
- Background Subtraction: In video analysis using the Wallflower dataset, the structured penalty effectively removed "salt and pepper" noise in foreground detection by enforcing spatial consistency, a feat standard $\ell_1$ models failed to achieve.
- Matrix Factorization: In CUR matrix factorization tasks across four gene-expression datasets, the convex approach matched the performance of traditional randomized sampling methods while providing the stability of a deterministic solution.
Key Insights and Conclusion
The realization that overlapping $\ell_\infty$ penalties can be mapped to network flow is a significant theoretical and practical advancement. Unlike approximate methods, the ProxFlow algorithm guarantees "true" zeros, preserving the interpretability of the sparsity pattern. While the network flow trick is currently restricted to $\ell_\infty$ sums, it provides a blueprint for leveraging combinatorial optimization in convex learning problems. Future work may extend these insights to other complex norms, such as those encouraging unions of groups or total-variation penalties, further bridging the gap between structured regularization and efficient large-scale optimization.
Summary updated