The Complexity of Selecting Overlapping Sparse Groups

This direction is merged into another direction: integrality-preserving linear relaxation. Its last version stays readable and citable here.

Version 1 of 18 papers21 conceptsfrozen 2026-10-04

In high-dimensional data analysis, we often assume that only a few variables are truly relevant. This is the principle of sparsity. However, in many domains, variables don't act in isolation; they belong to predefined structures, such as genes in a biological pathway or coefficients in a wavelet tree.

To capture this, researchers use group sparsity, where we select entire groups of variables rather than individual ones. While this makes models more interpretable, it introduces a significant computational hurdle: when groups overlap, deciding which ones to "turn on" becomes a complex combinatorial puzzle.

The Combinatorial Bottleneck

The fundamental challenge in group-sparse model selection is that selecting one group changes the marginal utility of selecting another. If two groups share many variables, picking both might be redundant.

Luca Baldassarre, Nirav Bhan, and Anastasios Kyrillidis established in Tractability of Interpretability via Selection of Group-Sparse Models that this selection process is formally equivalent to the Weighted Maximum Coverage problem. In this framing, you have a "budget" of groups you can pick, and you want to cover the maximum "signal weight" possible. Because Weighted Maximum Coverage is a classic NP-hard problem, finding the absolute best set of overlapping groups is computationally intractable for general structures.

The Topology of Overlap

The difficulty of the problem isn't just about the number of groups, but how they intersect. We can visualize these dependencies using an intersection graph, where each node is a group and an edge exists between two nodes if their groups share at least one variable.

Research by Volkan Cevher and his colleagues demonstrates that the "loopiness" of this graph determines whether we can solve the problem efficiently:

  1. Acyclic Structures (Trees): If the intersection graph is a tree or a forest (no cycles), the problem becomes tractable. In Group-Sparse Model Selection: Hardness and Relaxations, the authors show that Dynamic Programming (DP) can find the exact optimal selection in polynomial time. This DP approach is often significantly faster and more accurate than standard convex relaxations (like the Group Lasso).
  2. Cyclic Structures: As soon as the groups form complex loops or cycles, the complexity scales exponentially with the "treewidth" of the graph. In these cases, exact solutions are no longer feasible for large datasets.

Greedy Approximations and Guarantees

When exact solutions are out of reach, we turn to approximation algorithms. A common strategy is the greedy approach: pick the group that provides the most "new" signal, then repeat.

In Sparse group covers and greedy tree approximations, Siddhartha Satpathi and Luca Baldassarre analyzed greedy algorithms for these structures. They proved that for certain signal approximations, a greedy strategy can achieve a $1 - 1/e$ approximation guarantee. This means that even if we can't find the perfect set of groups, we can efficiently find a set that is at least ~63% as good as the optimum.

Why This Matters for Interpretability

The drive to solve these hard combinatorial problems isn't just about optimization—it's about interpretability. As Cong Han Lim and Stephen Wright note in k-Support and Ordered Weighted Sparsity for Overlapping Groups: Hardness and Algorithms, using sophisticated sparsity norms is only useful if we can actually compute the resulting models.

By identifying the boundary between tractable (acyclic) and intractable (cyclic) group structures, this research provides a roadmap for designing models. If a researcher can frame their domain knowledge into a tree-like group structure, they gain access to exact, efficient, and highly interpretable model selection. If the domain requires cycles, they must rely on greedy approximations with known theoretical limits.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_complexity_of_selecting_overlapping__6d2b5e97,
  title = {The Complexity of Selecting Overlapping Sparse Groups},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-complexity-of-selecting-overlapping-sparse-groups/rdr_6d2b5e97688f43aea0be5d9e5f56bbf9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_complexity_of_selecting_overlapping__6d2b5e97_v1,
  title = {The Complexity of Selecting Overlapping Sparse Groups},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-complexity-of-selecting-overlapping-sparse-groups/rdr_6d2b5e97688f43aea0be5d9e5f56bbf9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}