A Variance-Reduced and Stabilized Proximal Stochastic Gradient Method with Support Identification Guarantees for Structured Optimization
A Variance-Reduced and Stabilized Proximal Stochastic Gradient Method with Support Identification Guarantees for Structured Optimization
复制标题
DOI：
--
复制
发表时间：
2023-02
影响因子：
1.6
通讯作者：
Yutong Dai;Guanyi Wang;Frank E. Curtis;Daniel P. Robinson
中科院分区：
文献类型：
--
作者：
Yutong Dai;Guanyi Wang;Frank E. Curtis;Daniel P. Robinson
本文介绍了一种新的具有方差减少和稳定性的近端随机梯度方法，用于最小化凸随机函数和群稀疏性正则化函数的总和。由于该方法可以被视为最近提出的算法 PStorm 的稳定版本，因此我们将我们的算法称为 S-PStorm。我们的分析表明S-PStorm具有很强的收敛结果。特别是，我们证明了 S-PStorm 在迭代正确识别（以高概率）最佳支持（即最佳解决方案的零和非零结构）之前所需的迭代次数的上限。文献中具有这种支持识别属性的大多数算法都使用方差减少技术，这些技术需要定期评估精确梯度或存储随机梯度的历史。与这些方法不同，S-PStorm 不需要这些方法中的任何一种就可以实现方差减少，这是有利的。此外，我们对 S-PStorm 的支持识别结果表明，在索引高于阈值的所有迭代中，很有可能正确识别最佳支持。我们认为这种类型的结果对于文献来说是新的，因为很少有其他结果证明在每次迭代中具有足够大的索引时以高概率识别最佳支持（这意味着最佳支持可能在某些迭代中被识别，但在其他迭代中则不然）。关于正则化逻辑损失问题的数值实验表明，S-PStorm 在衡量算法迭代识别最佳支持的效率和鲁棒性的各种指标方面均优于现有方法。
This paper introduces a new proximal stochastic gradient method with variance reduction and stabilization for minimizing the sum of a convex stochastic function and a group sparsity-inducing regularization function. Since the method may be viewed as a stabilized version of the recently proposed algorithm PStorm, we call our algorithm S-PStorm. Our analysis shows that S-PStorm has strong convergence results. In particular, we prove an upper bound on the number of iterations required by S-PStorm before its iterates correctly identify (with high probability) an optimal support (i.e., the zero and nonzero structure of an optimal solution). Most algorithms in the literature with such a support identification property use variance reduction techniques that require either periodically evaluating an exact gradient or storing a history of stochastic gradients. Unlike these methods, S-PStorm achieves variance reduction without requiring either of these, which is advantageous. Moreover, our support-identification result for S-PStorm shows that, with high probability, an optimal support will be identified correctly in all iterations with the index above a threshold. We believe that this type of result is new to the literature since the few existing other results prove that the optimal support is identified with high probability at each iteration with a sufficiently large index (meaning that the optimal support might be identified in some iterations, but not in others). Numerical experiments on regularized logistic loss problems show that S-PStorm outperforms existing methods in various metrics that measure how efficiently and robustly iterates of an algorithm identify an optimal support.