Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
复制标题
希尔伯特空间中的阈值梯度方法：支持辨识和线性收敛
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Villa
中科院分区：
文献类型：
--
作者：
Guillaume Garrigos;L. Rosasco;S. Villa
研究了可分Hilbert空间中的正则化最小二乘优化问题。我们表明，迭代软阈值算法（ISTA）线性收敛，而不作任何假设的线性算子发挥作用或对问题。结果得到结合两个关键概念：扩展支持的概念，一个有限集包含的支持，和条件的概念在有限维集。我们证明了ISTA确定的解决方案扩展支持有限次迭代后，我们推导出线性收敛的条件性质，这是总是满足的最小二乘问题的101。我们的分析扩展到整个阈值梯度算法类别，我们为这些算法提供了强收敛性以及收敛率的概念性新证明。
We study the ℓ1 regularized least squares optimization problem in a separable Hilbert space. We show that the iterative soft-thresholding algorithm (ISTA) converges linearly, without making any assumption on the linear operator into play or on the problem. The result is obtained combining two key concepts: the notion of extended support, a finite set containing the support, and the notion of conditioning over finite-dimensional sets. We prove that ISTA identifies the solution extended support after a finite number of iterations, and we derive linear convergence from the conditioning property, which is always satisfied for ℓ1 regularized least squares problems. Our analysis extends to the entire class of thresholding gradient algorithms, for which we provide a conceptually new proof of strong convergence, as well as convergence rates.
DOI：
10.1287/moor.2017.0889
发表时间：
2016-02
期刊：
Math. Oper. Res.
影响因子：
--
作者：
D. Drusvyatskiy;A. Lewis
通讯作者：
D. Drusvyatskiy;A. Lewis