PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex and Network Flow Optimization for Structured Sparsity

Julien Mairal, Rodolphe Jenatton, Guillaume Obozinski, Francis Bach

arXiv:1104.1872v3math.OCcs.LGstat.ML

TL;DR

Structured sparsity can encode patterns among nonzero variables, but optimization with general overlapping groups is challenging. The paper develops flow-based proximal computation and proximal splitting strategies for these problems. It demonstrates the methods on a range of learning applications, including CUR factorization and image denoising.

  • Problem

    Structured regularization can encode patterns among nonzero variables, but solving problems with general overlapping groups is challenging.

    Source: §1 · p. 2, §2 · p. 3, §2.2 · p. 5

  • Method

    The paper computes the proximal operator for sums of overlapping ℓ∞-norms through quadratic min-cost flow and also develops proximal splitting methods.

    Source: §1 · p. 2, §6 · pp. 25–26

  • Results

    Experiments demonstrate the methods on a wide class of learning problems not previously addressed with convex sparse methods, including CUR factorization and image denoising.

    Source: §1 · pp. 2–3, §6 · p. 26

  • Takeaways & Limitations

    The efficiently computed proximal operator can serve as a modular building block for other optimization problems, including dictionary learning inner loops.

    Source: §6 · p. 26

    Regularizer choice depends on the desired zero pattern: for selecting a union of pathways, the paper identifies Ω′ rather than Ω as natural.

    Source: §2.2 · p. 5

Abstract

from arXiv · show

We consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of l_2- or l_infinity-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_infinity-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.

1. Introduction

The introduction motivates structured sparsity for learning problems where nonzero variables have spatial, temporal, hierarchical, or other group structure. It presents flow-based proximal computation and proximal splitting as strategies for optimization with general overlapping groups.

1. Introduction

  • Unlike ℓ1 regularization, group-norm regularizations can encode structure in nonzero patterns, but their optimization is difficult in part because of nonsmooth components.The paper focuses on the challenging case of general overlapping groups.Source: §1 · p. 2
  • Proximal splitting addresses an equivalent formulation with non-overlapping groups in a higher-dimensional space and with additional constraints.The introduction also presents efficient evaluation of the dual norm, enabling computation of duality gaps.Source: §1 · p. 2
  • The proximal operator for a sum of overlapping ℓ∞-norms can be computed exactly and efficiently by solving a quadratic min-cost flow problem.This enables proximal gradient methods for structured sparsity.Source: §1 · p. 2
  • The methods are demonstrated on CUR matrix factorization, video background subtraction, hierarchical dictionary learning, wavelet denoising, and topographic dictionary learning.The introduction describes a new CUR technique exploiting structured sparse regularization.Source: §1 · pp. 2–3

1.1 Notation

  • The notation section uses bold lowercase letters for vectors and uppercase letters for matrices.It also introduces ℓq, ℓ∞, and Frobenius norms, among other notation.Source: §1.1 · p. 3

2. Structured Sparse Models

The section frames structured sparsity as selecting few nonzero coefficients in patterns such as groups, trees, or overlapping groups. It distinguishes nonconvex and convex formulations, then reviews convex norms and optimization approaches for overlapping groups.

2. Structured Sparse Models

  • Structured sparsity seeks solutions with few nonzero coefficients arranged in patterns such as groups, trees, or overlapping groups.Source: §2 · p. 3

2.1 Nonconvex Approaches

  • Nonconvex approaches encode allowed nonzero patterns or encourage patterns with small coding length, while another penalty encourages specified groups to be zero together.The coding-length formulation favors patterns representable as a union of a small number of groups; its convex envelope on the unit ℓ∞-ball yields structured sparsity-inducing norms.Source: §2.1 · pp. 3–4

2.2 Convex Approaches with Sparsity-Inducing Norms

  • For convex structured regularization, the objective combines a convex function with a norm formed by weighted ℓ2- or ℓ∞-norms over groups.The function is usually an empirical risk or data-fitting term, and the groups may overlap.Source: §2.2 · p. 4
  • With non-overlapping groups, the group-Lasso selects variables in groups; with overlapping groups, the norm sets groups of variables to zero together.The paper focuses on solving the overlapping-group case; a different norm that encourages patterns as unions of groups is outside its scope.Source: §2.2 · p. 5

2.3 Convex Optimization Methods Proposed in the Literature

  • Generic subgradient and interior-point methods may scale poorly or fail to produce exact zeros, motivating dedicated optimization procedures.Source: §2.3 · p. 5
  • Earlier dedicated methods mainly address sums of ℓ2-norms, using variational formulations, working sets, or smoothing; smoothing requires a precision choice and may not preserve the encoded structure.The reviewed variational formulations are not known for sums of ℓ∞-norms.Source: §2.3 · pp. 5–6

3. Optimization with Proximal Gradient Methods

This section develops proximal-gradient methods for structured sparsity with general overlapping ℓ∞ groups, using a quadratic min-cost flow formulation to compute the proximal operator. It also describes monitoring convergence with a duality-gap certificate whose evaluation requires computing the dual norm through a network-flow problem.

3.1 Proximal Gradient Methods

  • Proximal-gradient updates linearize the smooth objective and solve a strongly convex proximal problem, whose exact solution enables the methods’ fast convergence rates.The quadratic term keeps the update near the smooth objective’s linear approximation; L is an upper bound on the Lipschitz constant of ∇f.Source: §3.1 · p. 7

Definition 1 (Proximal Operator)

  • The section defines the proximal operator as the unique solution of a regularized quadratic problem and notes that tree-structured sums of ℓ2- or ℓ∞ norms admit a closed-form composition.For tree-structured groups, the composition can be computed in O(p) operations.Source: Definition 1 (Proximal Operator) · pp. 7–8

3. Optimization with Proximal Gradient Methods

  • For general overlapping groups with ℓ∞ norms, the paper’s first contribution is to address the proximal operator case that earlier work had not specifically optimized.The section assumes a differentiable objective with Lipschitz-continuous gradient and uses proximal-gradient methods; the ℓ∞ norm’s piecewise linearity is central to the approach.Source: §3 · p. 6, Definition 1 (Proximal Operator) · p. 8

3.2 Dual of the Proximal Operator

  • For general overlapping ℓ∞ groups, the proximal problem’s convex dual can be reformulated as quadratic min-cost flow, with the primal solution recovered from the dual variables.Given a dual solution ξ⋆, the corresponding primal solution is w⋆ = u − ∑g∈G ξ⋆g.Source: §3.2 · p. 8

3.3 Graph Model

  • The canonical graph encodes group capacities and variable flows so that minimizing its flow costs is equivalent to the dual problem; simplifying edges for nested groups reduces graph size without changing the optimum.For h ⊂ g, edges from g to variables in h can be replaced by one edge from g to h.Source: §3.3 · p. 10

3.4 Computation of the Proximal Operator

  • The proposed computeFlow algorithm exploits the graph’s structure to solve the general overlapping-group problem and is reported to run much faster in practice than the parametric max-flow approach.When a lower bound is unattainable, minimum-cut decomposition splits the problem into smaller independent problems solved recursively; the proposed algorithm has weaker worst-case guarantees, up to a factor |V|.Source: §3.4 · pp. 10, 12

3.5 Computation of the Dual Norm

  • The dual norm is identified as useful for working-set algorithms and for proving estimation or prediction guarantees, while the section also announces a related algorithm to compute it.Source: §3.2 · p. 8, §3.5 · p. 13
  • The duality gap certifies (sub)optimality: zero gap means the optimum is reached, and under strong duality the converse also holds.It serves as the convergence criterion for the proximal method on problem (2).Source: §3.5 · p. 13
  • When |V+| and |V−| are not approximately balanced, the algorithm incurs a factor |V|, although practical speed differs from theoretical worst-case complexity.The passage notes |V+| ≈ |V−| ≈ |V|/2 as the balanced case.Source: §3.5 · p. 13
  • Evaluating the gap requires a feasible dual variable, found by computing the dual norm through a flow problem that minimizes τ while saturating sink capacities κ_j.The source-to-group arc capacities are τη_g; the arcs leading to the sink have capacities κ_j.Source: §3.5 · p. 14

4. Optimization with Proximal Splitting Methods

Proximal splitting handles losses that need not be differentiable and regularizers formed from sums of ℓ2- or ℓ∞-norms, under stated assumptions. Variable splitting and ADMM variants provide approaches for overlapping groups, including loss-splitting and design-matrix strategies.

4. Optimization with Proximal Splitting Methods

  • Unlike proximal-gradient methods, proximal splitting does not require differentiable f and accommodates sums of ℓ2- or ℓ∞-norms, subject to its stated assumptions.The paper notes that proximal-gradient methods offer line-search tuning, known convergence rates, and sparse solutions with true zeros.Source: §4 · pp. 14–15

4.1 Algorithms

  • Variable splitting introduces one z_g per group and applies ADMM iterations over primal variables and dual ascent; convergence holds for every γ>0, though tuning affects speed.The z_g updates have closed-form solutions when the required group proximal operators are available.Source: §4.1 · pp. 15–16

4. Optimization with Proximal Splitting Methods

  • The paper reports no known efficient exact proximal algorithm for sums of ℓ2-norms, and does not pursue approximate computation because it may be expensive and require handling approximate proximal steps.Proximal splitting can handle sums of ℓ2-norms, while the exact-proximal limitation concerns the proximal-gradient strategy discussed in the passage.Source: §4.1 · p. 15, §4 · p. 15

4.1.1 SPLITTING THE LOSS FUNCTION f

  • For square and hinge losses, splitting f across training points yields efficient ADMM steps when each component proximal operator is closed-form, but may use substantial memory for large n.The square-loss example defines one component function per training point.Source: §4.1.1 · p. 16

4.1.2 DEALING WITH THE DESIGN MATRIX

  • For f(w)=f̃(Xw), introducing v=Xw and choosing Q=δI−XᵀX with δ large enough simplifies w minimization while preserving convergence.The method replaces the quadratic coupling with a proximity term around the current estimate of w.Source: §4.1.2 · p. 16

5. Applications and Experiments

The experiments apply the structured-sparsity methods to speed benchmarking, wavelet denoising, CUR factorization, background subtraction, topographic dictionary learning, and learning hierarchical structures. They compare the proposed methods with alternative approaches and report benefits within several tested settings.

5.1 Speed Benchmark

  • ProxFlow performs consistently better than Lin-ADMM, which outperforms ADMM; all three compare favorably with other methods except ADMM at large scale, and only ProxFlow yields sparse solutions.For the small-scale problem, ProxFlow and Lin-ADMM perform similarly.Source: §5.1 · p. 17, Figure 2 · p. 18

5.2 Wavelet Denoising with Structured Sparsity

  • For wavelet denoising, Ωgrid results are significantly better than Ωtree, indicating that encouraging spatial consistency in wavelet coefficients is more effective than hierarchical coding; the approach is relatively fast despite the problem’s high dimension.Solving the Ωgrid proximal problem for an image with 512 × 512 = 262144 pixels takes approximately 4–6 seconds on a single-core 3.07 GHz CPU.Source: §5.2 · pp. 18–19

5.3 CUR-like Matrix Factorization

  • The sparsity-based CUR approach and the sampling scheme perform similarly on four gene-expression datasets, while the sparsity-based approach is not randomized.The sampling results average five initializations; Figure 3 plots explained variance across the datasets.Source: §5.3 · p. 20, Figure 3 · p. 21

5.4 Background Subtraction

  • For the two tested images, overlapping-group regularization improves background subtraction over ℓ1 by removing scattered artifacts; non-overlapping groups improve on ℓ1 but introduce block artifacts.The comparison includes original images, estimated backgrounds, and foreground masks.Source: §5.4 · pp. 20, 22, Figure 4 · p. 23

5.5 Topographic Dictionary Learning

  • The method learns topographic dictionaries using overlapping 3×3 or 4×4 groups, and the resulting examples resemble topographic maps reported in prior work.The dictionaries contain 400 elements and are learned on whitened natural image patches.Source: §5.5 · pp. 22, 24, Figure 5 · p. 24

5.6 Multi-Task Learning of Hierarchical Structures

  • On natural-image patch denoising at noise standard deviation 0.2, learning the hierarchy significantly outperforms standard sparse coding and predefined-tree dictionary learning in a range of settings.No significant improvements were observed at lower noise levels; the large training graphs required heuristics for selecting regularization parameters.Source: §5.6 · p. 25

6. Conclusion

The paper presents optimization methods for structured sparsity with overlapping groups, including an efficient quadratic min-cost-flow formulation for the proximal operator of sums of ℓ∞-norms. The conclusion highlights the operator’s modular use and the methods’ application across learning problems.

6. Conclusion

  • The proximal operator for sums of ℓ∞-norms over overlapping groups is a quadratic min-cost-flow problem with an efficient, simple algorithm.The paper presents optimization methods for structured problems involving sums of ℓ2- or ℓ∞-norms over overlapping groups.Source: §6 · p. 25
  • Figure 6 shows a hierarchy pruned from a 76-element tree and plots mean square error against dictionary size, with error bars of two standard deviations across three runs.Source: Figure 6 · p. 26
  • Efficient proximal computation supports accelerated gradient methods and serves as a reusable building block, including for repeated inner-loop problems in dictionary learning.The conclusion identifies other structured norms and total-variation penalties as future directions for proximal-operator computation.Source: §6 · p. 26

Appendix A. Equivalence to Canonical Graphs

The appendix defines when a graph with a different arc set is equivalent to the canonical graph for a group structure. Under those conditions, the optimal min-cost-flow cost and variable-to-sink arc flows are preserved.

Appendix A. Equivalence to Canonical Graphs

  • Equivalent graphs share the canonical graph’s source and sink arcs, with the same costs and capacities.Source: Appendix A · pp. 26–27
  • Each canonical group-to-variable arc must correspond to a unique zero-cost, infinite-capacity path, and such paths cannot occur for absent arcs.Source: Appendix A · p. 27
  • Under these equivalence conditions, both graphs have the same optimal flow cost and the same flows on arcs from variables to the sink.Source: Appendix A · p. 27

Appendix B. Convergence Analysis

The appendix states that it proves the convergence and correctness of the proximal-operator algorithm and the correctness of the dual-norm algorithm.

Appendix B. Convergence Analysis

  • The analysis establishes convergence and correctness for the proximal-operator algorithm and correctness for the dual-norm algorithm.Source: Appendix B · p. 27

B.1 Computation of the Proximal Operator

The analysis characterizes optimality through primal-dual conditions, then proves that Algorithm 1 terminates in polynomial time and solves the proximal problem. Its correctness proof relies on recursively splitting the graph at a cut and processing the resulting parts.

B.1 Computation of the Proximal Operator

  • Primal-dual optimality conditions characterize solutions and interpret the flow as maximizing feasible flow toward variables with the largest residuals.Flow from a group is directed to variables with maximum residual, subject to capacity constraints.Source: §B.1 · pp. 27–28

Proposition 1 (Convergence of Algorithm 1)

  • Algorithm 1 converges in a finite, polynomial number of operations; each recursive part uses an ℓ1-ball projection and a max-flow algorithm.The proof establishes that both sides of the computed cut are nonempty.Source: Proposition 1 (Convergence of… · p. 29

Proposition 2 (Correctness of Algorithm 1)

  • Algorithm 1 solves the proximal problem by recursively splitting the graph at a cut and processing the two resulting parts independently.The proof establishes correctness first for canonical graphs and then extends it to equivalent graphs.Source: Proposition 2 (Correctness of… · pp. 29, 30, 32

B.2 Computation of the Dual Norm Ω⋆

The dual norm is derived through a convex primal-dual formulation, and Algorithm 2 computes it in finitely many polynomially many operations. The correctness proof uses max-flow/min-cut bounds and an inductive argument over graph nodes.

B.2 Computation of the Dual Norm Ω⋆

  • The dual-norm computation is formulated as a network-flow problem extending a variational result of Jenatton et al. (2009).The proof also establishes that equivalent graphs yield the same τ values and (s,t)-cuts at each step.Source: §B.2 · p. 32, Proposition 3 (Convergence and… · p. 34
  • The dual-norm derivation introduces primal variables α_g and conic constraints ∥z_g∥∞ ≤ α_g, then uses strong duality to obtain the dual problem.The stated justification is Slater’s condition for generalized conic inequalities.Source: §B.2 · pp. 32–33

Proposition 3 (Convergence and correctness of Algorithm 2)

  • Algorithm 2 computes the dual norm in a finite and polynomial number of operations.Its convergence follows because each recursive call strictly decreases the vertex-set cardinality, requiring finitely many max-flow calls.Source: Proposition 3 (Convergence and… · p. 33
  • For the canonical graph, the proof inducts on node count and uses max-flow/min-cut to show that the stopping value of τ is optimal.When the constraints are infeasible at the current τ, the algorithm splits the vertices into two non-empty parts and updates τ.Source: Proposition 3 (Convergence and… · p. 33

Appendix C. Algorithm FISTA with duality gap

This section describes FISTA for solving the primal problem with a duality-gap stopping criterion. It constructs a dual candidate from the primal iterate and evaluates the gap using the dual norm.

Appendix C. Algorithm FISTA with duality gap

  • In this section, FISTA is applied to solve problem (2), with a duality gap as the stopping criterion; the experimental implementation is summarized in Algorithm 3.In the experiment, the line-search parameter ν is set to 1.5.Source: Appendix C · p. 34
  • For models Xw, Fenchel duality gives a duality gap, and a dual candidate κ is chosen using the optimality conditions for the primal-dual pair.X is an n-by-p matrix, typically the design matrix of n observations in p dimensions.Source: Appendix C · p. 34
  • Evaluating the duality gap requires computing the dual norm Ω⋆, which the procedure delegates to Algorithm 2.The section refers to the proximal operator associated with λΩ as prox_λΩ.Source: Appendix C · p. 34

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

The speed comparison benchmarks ProxFlow against GGT and SIMP on DCT-derived problems and background-subtraction images. ProxFlow consistently outperforms both alternatives across the tested λ values and observed regularization regimes.

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

  • The benchmark compares ProxFlow with GGT and SIMP, parametric max-flow methods, on DCT problems with 10^4, 10^5, and 10^6 variables and background-subtraction images of 57,600 pixels.The comparison uses the paraF C++ implementation for GGT and SIMP.Source: Appendix D · p. 34
  • Execution times are averaged over five runs on a single-core 2.33 GHz machine.The passage introduces a table of average execution times and problem statistics, but does not provide its values here.Source: Appendix D · p. 35
  • ProxFlow consistently outperforms GGT and SIMP for λ values corresponding to different regularization regimes.The reported speed comparison uses a single λ from the corresponding paper experiments, with consistency across other regimes also observed.Source: Appendix D · p. 35

Related papers

Loading 1104.1872v3…