A graph-manipulation technique reduces the cost of diagonal-preconditioned RHMC fixed-point iterations from quadratic to linear in dimension for coordinate-friendly targets.
Coordinate Friendly Structures, Algorithms and Applications
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize. The great performance of coordinate update methods depends on solving simple sub-problems. To derive simple subproblems for several new classes of applications, this paper systematically studies coordinate-friendly operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history. The obtained algorithms are scalable to large instances through parallel and even asynchronous computing. We present numerical examples to illustrate how effective these algorithms are.
verdicts
UNVERDICTED 3representative citing papers
SGDA-B is the first backtracking-enabled stochastic GDA algorithm for nonconvex-concave minimax problems that achieves the best known complexity bounds among methods agnostic to L, μ, and σ².
Introduces bAdag, an AdaGrad-based block coordinate gradient method with ergodic sublinear convergence proofs for smooth nonconvex objectives under block Lipschitz gradient assumptions, covering cyclic, uniform random, and Gauss-Southwell selection plus box constraints.
citing papers explorer
-
Hessian-informed, Coordinate Friendly Hamiltonian Monte Carlo in Linear Time
A graph-manipulation technique reduces the cost of diagonal-preconditioned RHMC fixed-point iterations from quadratic to linear in dimension for coordinate-friendly targets.
-
A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems
SGDA-B is the first backtracking-enabled stochastic GDA algorithm for nonconvex-concave minimax problems that achieves the best known complexity bounds among methods agnostic to L, μ, and σ².
-
bAdag: an adaptive block coordinate gradient method for smooth nonconvex functions
Introduces bAdag, an AdaGrad-based block coordinate gradient method with ergodic sublinear convergence proofs for smooth nonconvex objectives under block Lipschitz gradient assumptions, covering cyclic, uniform random, and Gauss-Southwell selection plus box constraints.