Proximal-Proximal-Gradient Method (Journal of Computational Mathematics, 2021)
In this paper, we present the proximal-proximal-gradient method (PPG), a novel optimization method that is simple to implement and simple to parallelize. PPG generalizes theproximal-gradient method and ADMM and is applicable to minimization problems written as a sum of many differentiable and many non-differentiable convex functions. Thenon-differentiable functions can be coupled. We furthermore present a related stochasticvariation, which we call stochastic PPG (S-PPG). S-PPG can be interpreted as a generalization of Finito and MISO over to the sum of many coupled non-differentiable convexfunctions.We present many applications that can benefit from PPG and S-PPG and prove convergence for both methods. We demonstrate the empirical effectiveness of both methodsthrough experiments on a CUDA GPU. A key strength of PPG and S-PPG is, comparedto existing methods, their ability to directly handle a large sum of non-differentiable non-separable functions with a constant step size independent of the number of functions. Suchnon-diminishing step size allows them to be fast.
Keywords: Proximal-gradient; ADMM; Finito; MISO; SAGA; Operator splitting; First-order methods; Distributed optimization; Stochastic optimization; Almost sure convergence; linear convergence.