Network Flow Algorithms for Structured Sparsity

Julien Mairal; Rodolphe Jenatton; Guillaume Obozinski; Francis Bach

Source-linked AI summary

Network Flow Algorithms for Structured Sparsity

Julien Mairal, Rodolphe Jenatton, Guillaume Obozinski, Francis Bach

arXiv:1008.5209v1Aug 31, 2010cs.LGstat.ML

TL;DR

General overlapping groups make structured sparse optimization challenging. The paper connects the proximal problem to quadratic min-cost flow, develops an exact polynomial-time procedure, and demonstrates scalability across structured sparse learning applications.

Problem
General overlapping groups make the structured sparse optimization problem challenging, beyond disjoint or specially hierarchical group structures.
Method
The paper casts the proximal operator for sums of overlapping group ℓ∞-norms as a quadratic min-cost flow problem and solves it with an efficient procedure.
Results
The method is fast and scalable, applies to problems with millions of variables, and supports applications including video background subtraction and hierarchical dictionary learning.
Takeaways & Limitations
Network flow optimization enables structured sparse regularization for a wider range of overlapping-group learning applications.
Takeaways & Limitations
The formulation assumes the scalars u_j and the entries of ξ are non-negative.

Abstract

from arXiv · show

We consider a class of learning problems that involve a structured sparsity-inducing norm defined as the sum of $\ell_\infty$-norms over groups of variables. Whereas a lot of effort has been put in developing fast optimization methods when the groups are disjoint or embedded in a specific hierarchical structure, we address here the case of general overlapping groups. To this end, we show that the corresponding optimization problem is related to network flow optimization. More precisely, the proximal problem associated with the norm we consider is dual to a quadratic min-cost flow problem. We propose an efficient procedure which computes its solution exactly in polynomial time. Our algorithm scales up to millions of variables, and opens up a whole new range of applications for structured sparse models. We present several experiments on image and video data, demonstrating the applicability and scalability of our approach for various problems.

Algorithmes de Flots pour Parcimonie Structurée

L’article traite la parcimonie structurée avec des groupes éventuellement chevauchants au moyen de l’optimisation de flots. Il propose une procédure polynomiale applicable à de grands problèmes et l’évalue sur des données d’images et de vidéos.

La norme étudiée est une somme de normes ℓ∞ sur des groupes de variables et vise des problèmes d’apprentissage régularisés.
Le problème proximal associé est dual d’un problème de flot à coût quadratique sur un réseau.
La procédure proposée calcule exactement la solution en temps polynomial et traite des problèmes comportant des millions de variables.
Des expériences sur des données d’images et de vidéos montrent l’utilité et l’efficacité de l’approche pour plusieurs problèmes.

1 Introduction

Les méthodes de parcimonie structurée cherchent à encoder les relations entre variables, mais les groupes généraux chevauchants restent difficiles à optimiser. Le papier relie alors l’opérateur proximal à un flot quadratique et fournit une procédure évolutive, évaluée sur plusieurs applications.

La norme ℓ1 favorise la parcimonie sans représenter les relations spatiales, temporelles ou hiérarchiques entre variables.
Les régularisations structurées encodent des motifs de coefficients non nuls, mais leur optimisation est généralement difficile à cause de composantes non lisses.
Le papier montre que l’opérateur proximal de la norme structurée se calcule par un problème de flot à coût quadratique.
Il présente une procédure rapide et évolutive pour des problèmes structurés à groupes chevauchants auparavant peu traités efficacement.
La méthode est appliquée notamment à la soustraction d’arrière-plan vidéo et à l’estimation de structures hiérarchiques pour des dictionnaires d’images.

2 Structured Sparse Models

Le modèle pénalise des groupes de variables au moyen d’une norme structurée et utilise des méthodes proximales pour résoudre le problème convexe non lisse. L’extension proposée couvre les groupes généraux chevauchants.

Le problème combine une fonction convexe différentiable f et une régularisation convexe non lisse Ω qui induit la parcimonie.
La norme structurée est une somme pondérée de normes ℓ∞ appliquées aux coefficients appartenant aux groupes G.
Avec des groupes chevauchants, la norme met simultanément à zéro des ensembles de variables et rend la résolution du problème difficile.
Méthodes proximales: Les méthodes proximales linéarisent f à chaque itération et résolvent un problème proximal pour traiter la somme f + λΩ.
Extension: L’approche étend les méthodes antérieures aux groupes généraux chevauchants lorsque Ω est une somme pondérée de normes ℓ∞.

3 A Quadratic Min-Cost Flow Formulation

The paper reformulates the proximal problem for weighted sums of ℓ∞-norms over overlapping groups as a quadratic min-cost flow problem. It then exploits the resulting graph structure to compute the proximal operator exactly and efficiently, while also supporting dual-norm evaluation and convergence monitoring.

3 A Quadratic Min-Cost Flow Formulation: The convex dual of the proximal problem is reformulated as a quadratic min-cost flow problem for general overlapping groups.The formulation establishes a connection between structured sparsity optimization and network flow methods.
3.1 Graph Model: The canonical graph contains group vertices, variable vertices, source-to-group arcs with capacities ληg, and variable-to-sink arcs with quadratic costs.Flow conservation makes each variable’s sink flow equal to the sum of flows arriving from its incident groups.
3.1 Graph Model: Minimizing sink-edge costs under source-arc capacities is equivalent to solving the dual optimization problem.The source capacities encode group constraints, while the sink costs reproduce the dual objective.
3.1 Graph Model: Nested groups permit graph simplification by replacing edges from a larger group to variables in a contained group with one infinite-capacity, zero-cost group-to-group edge.The simplification preserves the optimal value while reducing the number of edges.
3.2 Computation of the Proximal Operator: Single-group instances admit O(p) projection methods, while tree-structured cases can be solved in O(pd), with d denoting tree depth.These special cases provide computational context for the more difficult overlapping-group setting.
3.2 Computation of the Proximal Operator: The dedicated algorithm exploits the fact that non-zero costs occur only on sink edges, achieving better empirical performance than more general parametric-flow approaches despite a weaker worst-case guarantee.The authors report that its empirical speed advantage is substantial on the structured graphs considered.
3.2 Computation of the Proximal Operator: Algorithm 1 solves the proximal operator by alternating relaxed lower-bound computation, maximum-flow updates, minimum-cut decomposition, and recursive flow computation.It initializes the graph, updates variable flows through max-flow, separates saturated regions with a minimum cut, and solves the resulting subgraphs.
3.3 Computation of the Dual Norm: The dual norm is used to monitor proximal-method convergence through a Fenchel duality gap subject to the constraint Ω*(κ) ≤ λ.Evaluating this criterion requires the dual norm associated with the structured regularizer.

4 Applications and Experiments

Experiments evaluate ProxFlow on structured sparse regression, background subtraction, and hierarchical dictionary learning. The method compares favorably with generic optimizers, preserves sparsity, and scales to very large problems while structured regularization improves foreground detection.

4.1 Speed Comparison: ProxFlow obtains sparse solutions, whereas QP, CP, and subgradient descent do not in the reported regression experiments.On a problem with (n, p) = (100, 10^6), ProxFlow reached a relative duality gap of 0.0006 after 12 hours, versus 0.02 for subgradient descent.
4.2 Background Subtraction: The background-subtraction model combines sparse coding with an error vector whose structured penalty uses overlapping 3×3 image squares.The structured term addresses scattered foreground and background regions induced by an unstructured ℓ1 penalty.
4.3 Multi-Task Learning of Hierarchical Structures: Hierarchical dictionary learning prunes a shared initial tree across signals using an additional joint regularization term.The experiments alternate between dictionary and coefficient updates and handle graphs with approximately 4·10^7 vertices and edges.
4.2 Background Subtraction: 98.8% of pixels matched ground truth with Ω versus 87.0% without on one image, while another achieved 93.8% versus 90.4%.Figure 3 compares foreground masks detected with ℓ1 and with ℓ1+Ω.

5 Conclusion

The paper introduces a network-flow framework for structured sparse problems with arbitrary overlapping groups. Its proximal operator becomes a quadratic min-cost flow problem, enabling an efficient algorithm and applications beyond previously addressed sparse models.

Conclusion: The framework handles sums of ℓ∞-norms over arbitrary overlapping groups and connects their optimization to network flow methods.The formulation extends structured sparsity beyond disjoint or tree-structured groups.
Conclusion: The proximal operator is computed through a quadratic min-cost flow problem, allowing accelerated gradient methods.The paper proposes an efficient and simple algorithm for this flow problem.
Conclusion: Experiments demonstrate applicability across learning problems that had not previously been addressed within sparse methods.The reported applications include image and video data.

A Equivalence to Canonical Graphs

Equivalent canonical graphs preserve the relevant min-cost flow solution while replacing certain group-to-variable arcs with zero-cost, infinite-capacity paths. Feasible flows correspond through path-flow constructions in both directions.

Graph equivalence: Equivalent graphs share source and sink arcs with identical costs and capacities, while group-to-variable arcs correspond uniquely to zero-cost, infinite-capacity paths.The definition also requires every such path in the transformed graph to correspond to an original arc.
Graph equivalence: Equivalent graphs have the same optimal min-cost flow cost and identical optimal flows on variable-to-sink arcs.The flow cost depends only on the flows entering the sink from variable nodes.
Flow correspondence: A feasible flow on the original graph maps to a path-flow sum on the equivalent graph with the same cost.Each original arc is replaced by its corresponding path carrying the same flow amount.
Flow correspondence: Conversely, path-flow decomposition maps any feasible flow on the equivalent graph back to a feasible flow on the original graph.Each path flow corresponds to a unique original arc, while unused original arcs receive zero flow.

B Convergence Analysis

The paper states that the correctness of the proximal-operator and dual-norm algorithms is established in this section.

Convergence Analysis: The section proves correctness of Algorithm 1 for computing the proximal operator and Algorithm 2 for computing the dual norm Ω⋆.

B.1 Computation of the Proximal Operator

The proximal-operator algorithm alternates projection, max-flow computation, and recursive graph splitting until optimality conditions hold. It converges in finite polynomial time and exactly solves the proximal problem.

The algorithm uses optimality conditions for the primal and dual problems to certify termination and correctness.
Minimum-cut structure separates the graph into V + and V −, with no arcs from V + to V − and saturated arcs from s to V − and V + to t.
Algorithm 1 converges in a finite and polynomial number of operations and solves the proximal problem exactly.
Each iteration projects onto an ℓ1-ball, computes a max-flow, and either stops or splits the graph into two non-empty parts.
Recursive processing updates flows independently on the two subgraphs while preserving the relevant canonical graph structure and optimality conditions.

B.2 Computation of the Dual Norm Ω⋆

The dual norm is reformulated as a flow optimization problem and solved by a recursive max-flow procedure. The resulting algorithm computes the dual norm in finite polynomial time and supports duality-gap evaluation.

The dual norm admits a variational formulation involving flow variables, a scalar τ, and group-capacity constraints.
Strong duality converts the conic primal formulation into a dual problem with flow-feasibility and ℓ1 constraints on group flows.
Algorithm 2 computes the value of the dual norm in a finite and polynomial number of operations.
Algorithm 2 recursively applies max-flow computations and graph splits to solve the dual-norm optimization problem.
The dual norm is required for evaluating the duality gap used as the stopping criterion in FISTA.

D.1 Speed comparison of Algorithm 1 with parametric max-flow algorithms

ProxFlow is compared with two parametric max-flow implementations on problems ranging from 10^4 to 10^6 variables and a 57,600-pixel image task. It consistently outperforms both baselines across tested regularization regimes.

The benchmark compares ProxFlow with GGT and SIMP on DCT problems containing 10^4, 10^5, and 10^6 variables and on 57,600-pixel images.
The experiments were conducted using a single-core 2.33 Ghz machine and reported execution times for each algorithm.
ProxFlow consistently outperforms GGT and SIMP for regularization values spanning different regimes, despite the comparison reporting one primary λ value.