Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs

Abstract

We study estimation of a gradient-sparse parameter vector ${\mathbf{\theta }}^{\ast }\in {\mathbb{R}}^p$, having strong gradient-sparsity $s^{\ast }:=\Vert {\nabla }_G{\mathbf{\theta }}^{\ast }{\Vert }_0$ on an underlying graph $G$. Given observations $Z_1,\dots ,Z_n$ and a smooth, convex loss function $\mathcal{L}$ for which ${\mathbf{\theta }}^{\ast }$ minimizes the population risk $\mathbb{E}[\mathcal{L}(\mathbf{\theta };Z_1,\dots ,Z_n)]$, we propose to estimate ${\mathbf{\theta }}^{\ast }$ by a projected gradient descent algorithm that iteratively and approximately projects gradient steps onto spaces of vectors having small gradient-sparsity over low-degree spanning trees of $G$. We show that, under suitable restricted strong convexity and smoothness assumptions for the loss, the resulting estimator achieves the squared-error risk $\frac{s^{\ast }}{n}\log (1+\frac{p}{s^{\ast }})$ up to a multiplicative constant that is independent of $G$. In contrast, previous polynomial-time algorithms have only been shown to achieve this guarantee in more specialized settings, or under additional assumptions for $G$ and/or the sparsity pattern of ${\nabla }_G{\mathbf{\theta }}^{\ast }$. As applications of our general framework, we apply our results to the examples of linear models and generalized linear models with random design.

References in corpus (8)

• Optimal detection of changepoints with a linear computational cost
• Detection of an anomalous cluster in a network
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• Correlated variables in regression: clustering and sparse estimation
• Properties and refinements of the fused lasso
• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Iterative Alpha Expansion for estimating gradient-sparse signals from linear measurements