PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning with Structured Sparsity

Junzhou Huang, Tong Zhang, Dimitris Metaxas

arXiv:0903.3002v2stat.MEmath.ST

TL;DR

The paper addresses the lack of a general theory and algorithm for exploiting arbitrary structure in sparse learning. It formalizes structure through coding complexity, develops coding-complexity regularization and a structured greedy algorithm, and reports improved performance on some real problems with natural structures.

  • Problem

    Existing structured sparsity work lacked a general theoretical framework quantifying its effectiveness relative to standard sparsity.

  • Method

    The paper defines structured sparsity through coding complexity, develops coding-complexity regularization, and proposes a structured greedy algorithm.

  • Results

    Experiments demonstrate significant improvements on some real problems with natural structures.

  • Takeaways & Limitations

    Structured sparsity generalizes group sparsity and can exploit meaningful structures to improve standard sparse learning.

  • Takeaways & Limitations

    The paper does not analyze backward greedy strategies, although they can remove the O(ln(1/ϵ)) factor for relevant settings.

Abstract

from arXiv · show

This paper investigates a new learning formulation called structured sparsity, which is a natural extension of the standard sparsity concept in statistical learning and compressive sensing. By allowing arbitrary structures on the feature set, this concept generalizes the group sparsity idea that has become popular in recent years. A general theory is developed for learning with structured sparsity, based on the notion of coding complexity associated with the structure. It is shown that if the coding complexity of the target signal is small, then one can achieve improved performance by using coding complexity regularization methods, which generalize the standard sparse regularization. Moreover, a structured greedy algorithm is proposed to efficiently solve the structured sparsity problem. It is shown that the greedy algorithm approximately solves the coding complexity optimization problem under appropriate conditions. Experiments are included to demonstrate the advantage of structured sparsity over standard sparsity on some real applications.

1 Introduction

The paper studies sparse coefficient estimation under fixed design, then extends sparse learning to exploit known structure in coefficient patterns. It contrasts structured approaches with standard L1 and greedy methods for the generally NP-hard L0 problem.

  • The task is to estimate a sparse target coefficient vector from random observations with a fixed data matrix and noise-driven randomization.
  • L0 regularization provides a natural sparse-learning formulation using a desired sparsity level and least-squares loss.
  • Because the L0 optimization problem is generally NP-hard, practical alternatives include L1 convex relaxation and greedy algorithms such as OMP.
  • Structured sparsity incorporates prior knowledge that certain coefficient patterns are more likely, generalizing group sparsity.
  • The paper aims to improve standard sparse learning when meaningful structures exist in the coefficient vector.

2 Related Work

Prior work studied several structured sparsity settings, but lacked a general framework that quantifies their effectiveness relative to standard sparsity. This paper targets that gap across quantification, compressive sensing measurements, and noisy estimation accuracy.

  • Group Lasso theory established superiority over standard Lasso for strongly group-sparse signals, a special case of the paper’s broader framework.
  • Group Lasso does not handle the paper’s more general structures, while CAP handles overlapping groups without an established effectiveness theory.
  • Earlier work provided empirical evidence for structured sparsity, but no general theoretical framework quantified its effectiveness.
  • The paper focuses on quantifying structured sparsity, required compressive-sensing measurements, and estimation accuracy under stochastic noise.
  • The paper contributes an efficient algorithm intended to solve a wide class of structured sparsity problems.

3 Structured Sparsity

Structured sparsity assigns coding costs to support patterns and measures coefficient complexity by combining support size with coding length. Small coding complexity supports effective learning, while the framework is motivated by an information-theoretic representation of structured signals.

  • Structured sparsity assigns each support set F a coding cost cl(F), representing an upper bound on the bits needed to encode F.
  • The framework models sparsity patterns probabilistically through weights related to 2^-cl(F).
  • The structured sparse coding complexity is defined as c(F) = |F| + cl(F), combining support size with its coding length.
  • A coefficient vector’s coding complexity is obtained from the structured coding complexity of sets containing its support.
  • Small coding complexity is associated with effective learning, including good in-sample prediction and compressive-sensing reconstruction performance.
  • The coding-based penalty is related to, but distinct from, the standard MDL penalty for model selection.

4 Structured Sparsity Examples

The paper develops structured coding schemes for groups, hierarchies, and graphs, showing how structure can reduce coding complexity and support efficient learning. Block coding approximates these schemes so structured greedy algorithms can exploit them.

  • Block coding: Block coding builds subset codes from a manageable collection of base blocks, including all singleton blocks.Every feature subset can then be represented as a union of blocks, and the resulting coding length is sub-additive.
  • Group and non-uniform sparsity: Standard sparsity is recovered when coding uses only singleton blocks, while non-uniform codes assign shorter lengths to features more likely to be nonzero.Group sparsity similarly assigns codes to groups, with singleton codes effectively excluded under strong group sparsity.
  • Group and non-uniform sparsity: g log2(2m) is the group coding length for g disjoint groups, versus gk0 log2(p) for standard sparsity when each group has size k0.The smaller group coding complexity is associated with improved learning behavior in the paper’s analysis.
  • Hierarchical sparsity: Hierarchical and zero-tree structures can yield coding lengths as low as O(|F| + log2 p), or O(|F|) when selected nodes include their parents.Tree codes represent selections through left-child, right-child, or both-child decisions at internal nodes.
  • Graph sparsity: Graph sparsity introduces a graph over features, including a previously unconsidered general structure, and codes connected regions using local neighborhood information.For a single connected component containing the starting node, the coding length is O(|F|), independent of p.
  • Graph sparsity: Connected graph codes can be approximated by block coding with cl(F) = O(|F| + log2 p), enabling the structured greedy algorithm to use them.The construction uses connected base blocks of size up to δ log2 p/5 and requires no more than p1+δ base blocks.

5 Algorithms for Structured Sparsity

The paper extends greedy sparse selection to structured sparsity by replacing feature-count penalties with coding-complexity penalties and searching over structured blocks. Under stated approximation conditions, StructOMP approximately solves the structured optimization problem.

  • Structured regularization: Coding-complexity regularization penalizes the coding complexity of the selected feature set instead of its cardinality.It is presented as a natural extension of L0 regularization to structured sparsity.
  • Algorithmic formulation: The structured optimization problems are generally hard, while convex relaxation methods for general structured sparsity are not known to the authors.The paper therefore extends forward greedy selection by using a block structure.
  • Structured greedy algorithm: StructOMP searches over a computationally manageable block set rather than all feature subsets up to a fixed coding complexity.Blocks are added one at a time, limiting the search space while exploiting the specified structure.
  • Assumptions: The theoretical analysis assumes that the underlying coding scheme can be approximated by block coding using the algorithm’s base blocks.The paper notes that effectiveness is not ruled out when this approximation does not hold, but the analysis does not establish that case.
  • Structured greedy algorithm: The greedy criterion measures objective reduction per unit increase in coding complexity and generalizes the standard greedy selection rule.For least-squares regression, the gain can be approximated using projections onto subspaces generated by the selected features.
  • Approximation guarantee: Maximizing the approximate gain ratio yields an approximation ratio γ ≥ ρ−(B)/ρ+(B) under the stated bounds on the ratio.The algorithm also automatically adds blocks that increase the feature set without increasing coding complexity.

6 Theory of Structured Sparsity

The theory formalizes structured sparsity through coding complexity and establishes guarantees for regularization and structured greedy methods. Under stated noise, random-design, and eigenvalue conditions, structured methods can improve sample complexity or approximate sparse targets efficiently.

  • Structured conditions: Structured sparse eigenvalue and RIP conditions replace support size with coding complexity, generalizing standard sparsity analysis.The sparse eigenvalue condition considers submatrices with small coding cost, potentially yielding larger lower eigenvalue bounds than standard sparsity.
  • Structured conditions: n = O((k/k0) ln(p/k0)) random projections suffice for group sparsity, versus n = O(k ln(p)) for standard sparsity.This bound is stated for the structured RIP condition with Gaussian random matrices.
  • Regularization: Coding complexity regularization gives prediction guarantees for approximate minimizers under sub-Gaussian noise and structured eigenvalue assumptions.Theorem 6.2 applies to any estimator whose empirical objective is within ϵ of the target's objective.
  • Regularization: As n →∞ and s/n →0, constrained regularization approaches the best prediction performance among vectors with coding complexity at most s.The result remains meaningful even when the target's prediction error is large because it compares against the best estimator in the constrained class.
  • Regularization: In noiseless compressive sensing, exact reconstruction is possible when ρ−(2c(¯β)) > 0 and n = O(c(¯β)).The constrained coding complexity method sets s = c(¯β) in this result.
  • Structured greedy algorithm: The structured greedy algorithm approximately solves coding-complexity optimization, requiring O(ln(1/ϵ))c(¯β, B) complexity for accuracy ϵ.For weakly sparse compressible signals, the logarithmic factor can be removed, and the method achieves optimal rates up to a constant O(q).

7 Experiments

Experiments compare StructOMP with OMP, Lasso, and group Lasso across structured one-dimensional signals, wavelet-sparse images, and structured background-subtracted images. StructOMP generally achieves the strongest recovery, while standard-method performance varies with signal sparsity and structure.

  • Experimental setup: The experiments evaluate StructOMP against OMP, Lasso, and group Lasso using relative recovery error on graph-structured signals and structured image data.Graph sparsity is treated as more general than group sparsity, with group Lasso included for selected one-dimensional examples.
  • Simulated 1D signals: 0.0246 recovery error: StructOMP nearly perfectly recovers the graph-structured 1D signal, outperforming OMP, Lasso, and all tested group sizes.The comparison uses n = 160; group Lasso errors range from 0.2646 to 0.4832, versus 0.9921 for OMP and 0.8660 for Lasso.
  • Simulated 1D signals: StructOMP is superior across sample sizes for weakly sparse 1D signals, while OMP performs better than Lasso in this setting.The weakly sparse experiment averages results over 100 runs per sample size; its single example reports StructOMP error 0.0846.
  • 2D image compressive sensing: StructOMP performs better than OMP and Lasso for Haar-wavelet tree-structured image coefficients, while OMP and Lasso have similar performance on weakly sparse images.The image experiment averages recovery performance over 100 random runs for each sample size.
  • 2D image compressive sensing: Structured background-subtracted surveillance images are recovered from compressive measurements using StructOMP in a setting where foreground objects cluster into groups.The paper describes these images as both spatially sparse and clustered, motivating structured recovery.

8 Discussion

The discussion frames structured sparsity through coding complexity and positions StructOMP as an efficient general structured-sparsity algorithm. The paper reports lower complexity for structured targets and improvements on naturally structured problems.

  • Discussion: The framework generalizes group sparsity by allowing prior knowledge to favor arbitrary sparsity patterns.Group sparsity is included as a special case of the broader structured-sparsity framework.
  • Discussion: Structured sparsity measures learning complexity with coding complexity c(β̄), which can be smaller than the standard sparsity complexity when the support has a short coding length.The paper contrasts c(β̄) ≤ ∥β̄∥0 + cl(supp(β̄)) with the standard complexity ∥β̄∥0 ln p.
  • Discussion: Experiments report significant improvements on real problems with natural structures.The discussion links these improvements to the paper’s structured-sparsity framework.
  • Discussion: StructOMP is presented as the first efficient algorithm proposed for general structured-sparsity learning and is effective under appropriate conditions.The paper identifies convex relaxation and backward greedy strategies as directions for future work.

B Proof of Theorem 6.1

The proof establishes a structured restricted-isometry result by controlling each support subspace and then applying a union bound over supports weighted by coding length.

  • Proof of Theorem 6.1: Lemma B.1 provides a high-probability bound for every coefficient vector supported on a fixed set F of size k.The probability exceeds 1 − 3(1 + 8/δ)^k e^(−nδ^2/8).
  • Proof of Theorem 6.1: Coding length enters the proof through the union bound over support sets satisfying |F| + cl(F) ≤ s.This replaces an enumeration based only on ordinary support size.
  • Proof of Theorem 6.1: The resulting union bound establishes the structured RIP in Equation (4).The proof concludes this step after aggregating the fixed-support bounds.

C Proof of Theorem 6.2 and Theorem 6.3

These proofs derive concentration and estimation bounds under Assumption 6.1, then specialize them to approximate empirical-risk minimizers regularized by coding complexity.

  • Proof of Theorems 6.2 and 6.3: Lemma C.1 bounds the loss-related stochastic terms uniformly over coefficients supported on a fixed subset F.Its probability statement is conditioned on Assumption 6.1.
  • Proof of Theorems 6.2 and 6.3: The proof uses projection matrices and decomposes the noise into components aligned with and orthogonal to the subspace generated by X_F.The decomposition relies on PF Xβ = Xβ and ∥Xβ − PF Ey∥2 = ∥Xβ − Ey∥2.
  • Proof of Theorems 6.2 and 6.3: Lemma C.2 extends the fixed-support result uniformly to all β ∈ R^p with probability 1 − η.The extension is obtained by aggregating support-specific bounds using coding lengths.
  • Proof of Theorems 6.2 and 6.3: Approximate minimizers satisfying Q̂(β̂) + λc(β̂) ≤ Q̂(β̄) + λc(β̄) + ϵ receive an oracle-style bound involving c(β̄), c(β̂), λ, and ϵ.The proof combines Lemmas C.2 and C.3 through a union bound.
  • Proof of Theorems 6.2 and 6.3: Theorem 6.3’s error control follows by applying Lemma C.4 with λ = 0 and simplifying the resulting inequalities.The proof records the resulting square-root bound and its direct consequence.

D Proof of Theorem 6.4 and Theorem 6.5

The section proves Theorems 6.4 and 6.5 by applying a sub-additive coding-scheme lemma to derive greedy-step bounds, recurrence inequalities, and a stopping-time contradiction.

  • Proof of Theorem 6.4 and Theorem 6.5: Lemma D.1 assumes a sub-additive coding scheme and provides the key bound for covered vectors under a coding-complexity condition.The lemma is applied with different comparison vectors throughout the proof.
  • Proof of Theorem 6.4 and Theorem 6.5: At each greedy step, Lemma D.1 yields a residual-decrease inequality involving γ′ and the coding-complexity increment c(β(k)) − c(β(k−1)).The proof then converts this inequality into an exponential residual bound.
  • Proof of Theorem 6.4 and Theorem 6.5: The contradiction argument shows that stopping cannot occur while the tracked comparison index remains nonnegative, because stopping requires c(β(k)) > s.The proof concludes the theorem after establishing this contradiction.

E Proof of Corollary 6.1

The corollary proof constructs a sequence of comparison values, establishes a simultaneous high-probability inequality, and applies Theorem 6.5 to obtain the desired bound.

  • Proof of Corollary 6.1: The proof defines f_j as the minimum comparison value over a sequence of scales and assumes f_0 is attained at ℓ_0 = 0.This sequence is used to organize the probabilistic bound across j.
  • Proof of Corollary 6.1: The relevant inequality holds for all j with probability 1−η after combining the scale-wise probability bounds.The proof explicitly states this simultaneous probability guarantee.
  • Proof of Corollary 6.1: Choosing ϵ = 2an/s′q + 2σ2[ln(2/η) + 1] allows Theorem 6.5 to be applied and yields the desired bound.The derivation also uses ln(α + β) ≤ α + ln(β) for α, β ≥ 1.
Loading 0903.3002v2…