论文标题
通过基于主动集合的组合重新调节优化图形总变化
Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning
论文作者
论文摘要
加权图上的结构化凸优化可在机器学习和计算机视觉中找到许多应用。在这项工作中，我们提出了一种新型的自适应预处理策略，用于该问题类别的近端算法。根据当前迭代处的“主动集”，对局部线性收敛速率进行了尖锐的分析，我们的预调节器的驱动。我们表明，非活动边缘的嵌套孔分解产生了保证的局部线性收敛速率。此外，我们提出了一种实用的贪婪启发式方法，该敏锐的启发式方法可以意识到这种嵌套的分解，并在几个数值实验中表明，当应用于近端梯度或原始偶发型混合梯度算法时，我们的修复策略实现了竞争性的表现。我们的结果表明，局部收敛分析可以作为选择近端算法中可变指标的指南。
Structured convex optimization on weighted graphs finds numerous applications in machine learning and computer vision. In this work, we propose a novel adaptive preconditioning strategy for proximal algorithms on this problem class. Our preconditioner is driven by a sharp analysis of the local linear convergence rate depending on the "active set" at the current iterate. We show that nested-forest decomposition of the inactive edges yields a guaranteed local linear convergence rate. Further, we propose a practical greedy heuristic which realizes such nested decompositions and show in several numerical experiments that our reconditioning strategy, when applied to proximal gradient or primal-dual hybrid gradient algorithm, achieves competitive performances. Our results suggest that local convergence analysis can serve as a guideline for selecting variable metrics in proximal algorithms.
