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

Zhenzhang Ye, Thomas Möllenhoff, Tao Wu, Daniel Cremers
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:657-668, 2020.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-ye20a, title = {Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning}, author = {Ye, Zhenzhang and M\"ollenhoff, Thomas and Wu, Tao and Cremers, Daniel}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {657--668}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/ye20a/ye20a.pdf}, url = {https://proceedings.mlr.press/v108/ye20a.html}, 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.} }
Endnote
%0 Conference Paper %T Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning %A Zhenzhang Ye %A Thomas Möllenhoff %A Tao Wu %A Daniel Cremers %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-ye20a %I PMLR %P 657--668 %U https://proceedings.mlr.press/v108/ye20a.html %V 108 %X 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.
APA
Ye, Z., Möllenhoff, T., Wu, T. & Cremers, D.. (2020). Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:657-668 Available from https://proceedings.mlr.press/v108/ye20a.html.

Related Material