Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs
Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Sheng Xu;Z. Fan;S. Negahban
中科院分区：
文献类型：
--
作者：
Sheng Xu;Z. Fan;S. Negahban
我们研究对一个梯度稀疏参数向量\(\boldsymbol{\theta}^* \in \mathbb{R}^p\)的估计，它在一个底层图\(G\)上具有强梯度稀疏度\(s^*:=\|\nabla_G \boldsymbol{\theta}^*\|_0\)。给定观测值\(Z_1,\ldots,Z_n\)以及一个光滑的凸损失函数\(\mathcal{L}\)，\(\boldsymbol{\theta}^*\)使总体风险\(\mathbb{E}[\mathcal{L}(\boldsymbol{\theta};Z_1,\ldots,Z_n)]\)最小化，我们提议通过一种投影梯度下降算法来估计\(\boldsymbol{\theta}^*\)，该算法迭代地且近似地将梯度步投影到在图\(G\)的低度生成树上具有小梯度稀疏度的向量空间上。我们表明，在损失函数满足适当的受限强凸性和平滑性假设的条件下，所得的估计量能达到平方误差风险\(\frac{s^*}{n} \log (1+\frac{p}{s^*})\)，至多相差一个与\(G\)无关的乘法常数。相比之下，先前的多项式时间算法仅在更特殊的设定下，或者在对\(G\)和/或\(\nabla_G \boldsymbol{\theta}^*\)的稀疏模式有额外假设的情况下，才被证明能达到这一保证。作为我们通用框架的应用，我们将我们的结果应用于具有随机设计的线性模型和广义线性模型的例子。
We study estimation of a gradient-sparse parameter vector $\boldsymbol{\theta}^* \in \mathbb{R}^p$, having strong gradient-sparsity $s^*:=\|\nabla_G \boldsymbol{\theta}^*\|_0$ on an underlying graph $G$. Given observations $Z_1,\ldots,Z_n$ and a smooth, convex loss function $\mathcal{L}$ for which $\boldsymbol{\theta}^*$ minimizes the population risk $\mathbb{E}[\mathcal{L}(\boldsymbol{\theta};Z_1,\ldots,Z_n)]$, we propose to estimate $\boldsymbol{\theta}^*$ 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^*}{n} \log (1+\frac{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 $\nabla_G \boldsymbol{\theta}^*$. As applications of our general framework, we apply our results to the examples of linear models and generalized linear models with random design.