“Active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?
“Active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?
复制标题
近端梯度的“活动集复杂性”：找到稀疏模式需要多长时间？
作者：
J. Nutini;Mark W. Schmidt;W. Hare
近端梯度方法被发现对于解决非负约束或 ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} 的最小化问题非常有效\setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document}-正则化。在适当的非简并条件下，众所周知，这些算法可以在有限次数的迭代中识别出此类问题的最佳稀疏模式。然而，尚不清楚这可能需要多少次迭代。我们引入了“活动集复杂度”的概念，在这些情况下，它是算法保证识别出最终稀疏模式之前的迭代次数。在最小化强凸平滑函数和可分离凸非平滑函数之和的常见情况下，我们进一步给出了近端梯度方法的活动集复杂性的界限。
Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document}-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may take. We introduce the notion of the “active-set complexity”, which in these cases is the number of iterations before an algorithm is guaranteed to have identified the final sparsity pattern. We further give a bound on the active-set complexity of proximal gradient methods in the common case of minimizing the sum of a strongly-convex smooth function and a separable convex non-smooth function.