Combinatorial Preconditioners for Proximal Algorithms on Graphs
We present a novel preconditioning technique for proximal optimization methods that relies on graph algorithms to construct effective preconditioners. Such combinatorial preconditioners arise from partitioning the graph into forests. We prove that certain decompositions lead to a theoretically optimal condition number. We also show how ideal decompositions can be realized using matroid partitioning and propose efficient greedy variants thereof for large-scale problems. Coupled with specialized solvers for the resulting scaled proximal subproblems, the preconditioned algorithm achieves competitive performance in machine learning and vision applications.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningSimilar Papers 제목 키워드 기반
A General Family of Stochastic Proximal Gradient Methods for Deep Learning
We study the training of regularized neural networks where the regularizer can be non-smooth and non-convex. We propose a unified framework for stochastic proximal gradient descent, which we term ProxGen, that allows for…
QuantizationOptimization 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 pr…
Adaptive Proximal Gradient Methods for Structured Neural Networks
We consider the training of structured neural networks where the regularizer can be non-smooth and possibly non-convex. While popular machine learning libraries have resorted to stochastic (adaptive) subgradient approach…
QuantizationA Non-asymptotic Analysis for Learning and Applying a Preconditioner in MCMC
Preconditioning is a common method applied to modify Markov chain Monte Carlo algorithms with the goal of making them more efficient. In practice it is often extremely effective, even when the preconditioner is learned f…
MindX: Denoising Mixed Impulse Poisson-Gaussian Noise Using Proximal Algorithms
We present a novel algorithm for blind denoising of images corrupted by mixed impulse, Poisson, and Gaussian noises. The algorithm starts by applying the Anscombe variance-stabilizing transformation to convert the Poisso…
Combinatorial OptimizationDenoising