Proximal-Proximal-Gradient Method

Abstract

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 the proximal-gradient method and ADMM and is applicable to minimization problems written as a sum of many differentiable and many non-differentiable convex functions. The non-differentiable functions can be coupled. We furthermore present a related stochastic variation, 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 convex functions. We present many applications that can benefit from PPG and S-PPG and prove convergence for both methods. A key strength of PPG and S-PPG is, compared to existing methods, its ability to directly handle a large sum of non-differentiable non-separable functions with a constant stepsize independent of the number of functions. Such non-diminishing stepsizes allows them to be fast.

References in corpus (7)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• The composite absolute penalties family for grouped and hierarchical variable selection
• Structured Variable Selection with Sparsity-Inducing Norms
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Generalized Forward-Backward Splitting
• Smoothing proximal gradient method for general structured sparse regression
• An optimal randomized incremental gradient method

Cited by in corpus (10)

• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Primal-dual stochastic gradient method for convex programs with many functional constraints
• Distributed Proximal Splitting Algorithms with Rates and Acceleration
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• MISO is Making a Comeback With Better Proofs and Rates
• A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints
• An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method
• Solving A Class of Nonsmooth Resource Allocation Problems with Directed Graphs though Distributed Smooth Multi-Proximal Algorithms
• A Smooth Double Proximal Primal-Dual Algorithm for a Class of Distributed Nonsmooth Optimization Problem