Approximate bregman proximal gradient algorithm for relatively smooth nonconvex optimization

2023/11/14 by Shota Takahashi, Akiko Takeda · 8 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Applied mathematics #Bregman divergence #Computer science #Convergence (economics) #Lipschitz continuity #Mathematical analysis #Mathematical optimization #Mathematics #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.1007/s10589-024-00618-z

published in Computational Optimization and Applications 90(1), 227-256 (Springer Science+Business Media)

openalex publication_date 2024/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

Abstract In this paper, we propose the approximate Bregman proximal gradient algorithm (ABPG) for solving composite nonconvex optimization problems. ABPG employs a new distance that approximates the Bregman distance, making the subproblem of ABPG simpler to solve compared to existing Bregman-type algorithms. The subproblem of ABPG is often expressed in a closed form. Similarly to existing Bregman-type algorithms, ABPG does not require the global Lipschitz continuity for the gradient of the smooth part. Instead, assuming the smooth adaptable property, we establish the global subsequential convergence under standard assumptions. Additionally, assuming that the Kurdyka–Łojasiewicz property holds, we prove the global convergence for a special case. Our numerical experiments on the ℓ _p <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:math> regularized least squares problem, the ℓ _p <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:math> loss problem, and the nonnegative linear system show that ABPG outperforms existing algorithms especially when the gradient of the smooth part is not globally Lipschitz or even locally Lipschitz continuous.

Citations

• On Information and Sufficiency
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• New Bregman proximal type algorithms for solving DC optimization problems

Cited by

• Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions
• Majorization-Minimization Bregman Proximal Gradient Algorithms for NMF with the Kullback–Leibler Divergence
• First-order majorization-minimization meets high-order majorant: Boosted inexact high-order forward-backward method
• Approximate Bregman proximal gradient algorithm with variable metric Armijo--Wolfe line search
• On Relatively Smooth Optimization over Riemannian Manifolds
• Linesearch-free adaptive Bregman proximal gradient for convex minimization under local relative smoothness
• Robust Sparse Phase Retrieval: Statistical Guarantee, Optimality Theory and Convergent Algorithm
• On the Iterate Convergence of Bregman Projected Gradient Method

Related

• Bregman Proximal Gradient Algorithm with Extrapolation for a class of Nonconvex Nonsmooth Minimization Problems
• Approximate Bregman proximal gradient algorithm with variable metric Armijo--Wolfe line search
• A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems
• Inexact Bregman Proximal Gradient Method and its Inertial Variant with Absolute and Partial Relative Stopping Criteria
• Linesearch-free adaptive Bregman proximal gradient for convex minimization under local relative smoothness