Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning

Abstract

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.

Presented at the 23 rd International Conference on Artificial Intelligence and Statistics (AISTATS) 2020. Code: https://github.com/zhenzhangye/graph_TV_recond

References in corpus (5)

• Modular proximal optimization for multidimensional total-variation regularization
• The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• Efficient evaluation of scaled proximal operators