Convex and Network Flow Optimization for Structured Sparsity

Julien Mairal, Rodolphe Jenatton, Guillaume Obozinski, Francis R. Bach

TL;DR

This paper tackles the optimization of machine learning models with structured sparsity, specifically when variables are organized into overlapping groups. The authors make a clever connection between the proximal operator of overlapping $\ell_\infty$ group norms and network flow optimization, enabling exact, lightning-fast solutions using a custom min-cost flow algorithm.

What Problem Does This Paper Address?

In sparse machine learning (like Lasso), the $\ell_1$ norm is used to force many model weights to exactly zero, effectively selecting only the most important features. However, standard $\ell_1$ regularization ignores structural relationships between variables—like spatial proximity in pixels, temporal links in video, or hierarchical relationships in gene networks.

To fix this, researchers use "structured sparsity-inducing norms" (like the Group Lasso), which penalize groups of variables together. This is relatively easy to optimize when the groups are disjoint (non-overlapping). But when groups overlap (e.g., sliding 3x3 patches in an image), the optimization becomes notoriously difficult. Existing methods for overlapping groups either rely on slow subgradient descents, approximate smoothing techniques that fail to produce "true" zeros, or memory-heavy variable splitting. The authors needed a fast, exact way to compute the "proximal operator" for overlapping groups to unlock the use of fast, modern gradient methods (like FISTA).

Methods

The paper explores two main strategies for optimizing models with overlapping group penalties:

  1. Network Flow Optimization (The Core Novelty): The authors mathematically prove that computing the proximal operator for a sum of overlapping $\ell_\infty$-norms is equivalent to solving a quadratic min-cost flow problem on a specifically constructed directed graph.
  2. They design a canonical graph where nodes represent variables and groups, capacities represent the regularization weights, and costs represent the residuals.
  3. They propose a custom divide-and-conquer algorithm ("ProxFlow") that recursively uses standard max-flow algorithms (specifically, the push-relabel algorithm) to solve this exact problem.
  4. They also show that computing the dual norm (necessary for calculating duality gaps to know when to stop the algorithm) can be solved using a similar max-flow approach.
  5. Proximal Splitting (ADMM): For cases where the network flow trick doesn't apply (like using $\ell_2$-norms instead of $\ell_\infty$), they detail an Alternating Direction Method of Multipliers (ADMM) approach. This works by duplicating variables to artificially decouple the overlaps into a higher-dimensional space, though it is more memory-intensive.

Datasets

The authors evaluate their methods across a wide variety of tasks and datasets:

  • Speed Benchmarks: Synthetic data using overcomplete Discrete Cosine Transform (DCT) dictionaries.
  • Wavelet Denoising: 12 standard classical test images (with added Gaussian noise).
  • CUR Matrix Factorization: Four gene-expression datasets (9_Tumors, Brain_Tumors1, Leukemia1, SRBCT).
  • Background Subtraction: The Wallflower dataset (hand-segmented video sequences).
  • Topographic Dictionary Learning: Databases of 100,000 natural image patches (12x12 pixels).
  • Multi-Task Hierarchical Learning: 50,000 natural image patches (8x8 pixels).

Key Insights and Ideas

  • The Graph Connection: The most elegant insight is the realization that overlapping $\ell_\infty$ penalties map perfectly to a network flow graph. Solving the min-cost flow problem is equivalent to routing the maximum amount of "flow" (regularization penalty) to the variables with the highest residuals.
  • True Zeros Matter: Unlike smoothing techniques or ADMM (which often yield very small but non-zero values), the exact proximal operator guarantees "true" zeros. This preserves the exact desired sparsity structure, which is vital for interpretability.
  • Empirical vs. Theoretical Complexity: While standard parametric max-flow algorithms have better theoretical worst-case bounds, the authors' custom divide-and-conquer approach is vastly faster in practice because it exploits the specific bipartite-like structure of the graphs generated by these regularizers.

Key Results

  • Massive Speedups: On a massive problem with 1 million variables, their "ProxFlow" algorithm solved the proximal operator in just 113 seconds. A standard parametric max-flow algorithm (GGT) took 525 seconds, and generic interior point methods couldn't even run due to computational burden.
  • Better Image Denoising: Using a grid-based overlapping norm ($\Omega_{grid}$) improved the Peak Signal-to-Noise Ratio (PSNR) by up to 1.92 dB over standard $\ell_1$ soft-thresholding.
  • Cleaner Video Segmentation: In background subtraction, the structured penalty successfully removed scattered "salt and pepper" artifacts in foreground detection that plague standard $\ell_1$ models, because it enforced spatial consistency.
  • Deterministic CUR Factorization: Their convex approach matched the explained variance of traditional randomized sampling methods for matrix factorization, but with the benefit of being entirely deterministic.

Limitations and Future Work

  • Norm Restrictions: The elegant network flow equivalence only applies to sums of $\ell_\infty$-norms. If a practitioner wants to use $\ell_2$-norms for the overlapping groups, they cannot use the fast graph algorithm and must fall back on the slower, memory-intensive ADMM approach.
  • Future Directions: The authors suggest extending these network flow ideas to other complex structured norms (such as those that encourage unions of groups rather than intersections of zero-patterns) or to total-variation based penalties, which also share connections to min-cost flow problems.

Summary updated

Abstract

We consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of l2- or l∞-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 l∞-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.
BibTeX
@article{mairal2011convex,
  author = {Julien Mairal and Rodolphe Jenatton and Guillaume Obozinski and Francis R. Bach},
  title = {{Convex and Network Flow Optimization for Structured Sparsity}},
  journal = {J. Mach. Learn. Res.},
  year = {2011},
  url = {https://openreview.net/forum?id=LojwiwY3HVD},
}

Loading related content...

Figure