Combinatorial Preconditioners for Proximal Algorithms on Graphs.
We present a novel preconditioning technique for proximal optimizationmethods that relies on graph algorithms to construct effective preconditioners.Such combinatorial preconditioners arise from partitioning the graph intoforests. We prove that certain decompositions lead to a theoretically optimalcondition number. We also show how ideal decompositions can be realized usingmatroid partitioning and propose efficient greedy variants thereof forlarge-scale problems. Coupled with specialized solvers for the resulting scaledproximal subproblems, the preconditioned algorithm achieves competitiveperformance in machine learning and vision applications.
Continue reading and listening
Stay in the loop.
Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.