Technical Report: A Generalized Matching Pursuit Approach for Graph-Structured Sparsity
This addresses a bottleneck in data mining and machine learning for handling complex sparsity patterns, though it is incremental as it extends existing matching pursuit methods to graph structures.
The paper tackles sparsity-constrained optimization for general nonlinear functions with graph-structured sparsity constraints by proposing Graph-Mp, an efficient approximation algorithm that matches the guarantees of linear model methods and outperforms state-of-the-art approaches in connected subgraph detection tasks.
Sparsity-constrained optimization is an important and challenging problem that has wide applicability in data mining, machine learning, and statistics. In this paper, we focus on sparsity-constrained optimization in cases where the cost function is a general nonlinear function and, in particular, the sparsity constraint is defined by a graph-structured sparsity model. Existing methods explore this problem in the context of sparse estimation in linear models. To the best of our knowledge, this is the first work to present an efficient approximation algorithm, namely, Graph-structured Matching Pursuit (Graph-Mp), to optimize a general nonlinear function subject to graph-structured constraints. We prove that our algorithm enjoys the strong guarantees analogous to those designed for linear models in terms of convergence rate and approximation accuracy. As a case study, we specialize Graph-Mp to optimize a number of well-known graph scan statistic models for the connected subgraph detection task, and empirical evidence demonstrates that our general algorithm performs superior over state-of-the-art methods that are designed specifically for the task of connected subgraph detection.