Close Search Advanced
Journals
Resources
About Us
Open Access

Proximal-Proximal-Gradient Method

Proximal-Proximal-Gradient Method
Preview
Add to basket

Year:    2019

Author:    Ernest K. Ryu, Wotao Yin

Journal of Computational Mathematics, Vol. 37 (2019), Iss. 6 : pp. 778–812

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. We demonstrate the empirical effectiveness of both methods through experiments on a CUDA GPU. A key strength of PPG and S-PPG is, compared to 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. Such non-diminishing step size allows them to be fast.

Submit Article

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

DOI:    https://doi.org/10.4208/jcm.1906-m2018-0282

Journal of Computational Mathematics, Vol. 37 (2019), Iss. 6 : pp. 778–812

Published online:    2019-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    35

Keywords:    Proximal-gradient ADMM Finito MISO SAGA Operator splitting First-order methods Distributed optimization Stochastic optimization Almost sure convergence linear convergence.

Author Details

Ernest K. Ryu

Wotao Yin

  1. Gradient-based sparse principal component analysis with extensions to online learning

    Qiu, Yixuan | Lei, Jing | Roeder, Kathryn

    Biometrika, Vol. 110 (2023), Iss. 2 P.339

    https://doi.org/10.1093/biomet/asac041 [Citations: 4]

  2. Graph and Distributed Extensions of the Douglas–Rachford Method

    Bredies, Kristian | Chenchene, Enis | Naldi, Emanuele

    SIAM Journal on Optimization, Vol. 34 (2024), Iss. 2 P.1569

    https://doi.org/10.1137/22M1535097 [Citations: 1]

  3. Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

    Mao, Xianghui | Yuan, Kun | Hu, Yubin | Gu, Yuantao | Sayed, Ali H. | Yin, Wotao

    IEEE Transactions on Signal Processing, Vol. 68 (2020), Iss. P.2513

    https://doi.org/10.1109/TSP.2020.2983167 [Citations: 28]

  4. Magnetic resonance image restoration via least absolute deviations measure with isotropic total variation constraint

    Gu, Xiaolei | Xue, Wei | Sun, Yanhong | Qi, Xuan | Luo, Xiao | He, Yongsheng

    Mathematical Biosciences and Engineering, Vol. 20 (2023), Iss. 6 P.10590

    https://doi.org/10.3934/mbe.2023468 [Citations: 1]

  5. Sub-linear convergence of a stochastic proximal iteration method in Hilbert space

    Eisenmann, Monika | Stillfjord, Tony | Williamson, Måns

    Computational Optimization and Applications, Vol. 83 (2022), Iss. 1 P.181

    https://doi.org/10.1007/s10589-022-00380-0 [Citations: 2]

  6. Sublinear Convergence of a Tamed Stochastic Gradient Descent Method in Hilbert Space

    Eisenmann, Monika | Stillfjord, Tony

    SIAM Journal on Optimization, Vol. 32 (2022), Iss. 3 P.1642

    https://doi.org/10.1137/21M1427450 [Citations: 1]

  7. Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints

    Xu, Yangyang

    SIAM Journal on Optimization, Vol. 30 (2020), Iss. 2 P.1664

    https://doi.org/10.1137/18M1229869 [Citations: 17]