Tree-projected gradient descent for estimating gradient-sparse parameters on graphs

摘要

We study estimation of a gradient-sparse parameter vector $oldsymbol{heta}^* in mathbb{R}^p$, having strong gradient-sparsity $s^*:=|abla_G oldsymbol{heta}^*|_0$ on an underlying graph $G$. Given observations $Z_1,ldots,Z_n$ and a smooth, convex loss function $mathcal{L}$ for which $oldsymbol{heta}^*$ minimizes the population risk $mathbb{E}[mathcal{L}(oldsymbol{heta};Z_1,ldots,Z_n)]$, we propose to estimate $oldsymbol{heta}^*$ 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 $rac{s^*}{n} log (1+rac{p}{s^*})$ 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 $abla_G oldsymbol{heta}^*$. As applications of our general framework, we apply our results to the examples of linear models and generalized linear models with random design.