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 $\ell_p$ regularized least squares problem, the $\ell_p$ 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 local Lipschitz continuous.
Introduction: The Lipschitz Continuity Challenge
In machine learning and signal processing, many tasks are formulated as composite optimization problems: minimizing a smooth loss function $f$ plus a non-smooth regularizer $g$. The standard approach, the Proximal Gradient (PG) method, relies on the assumption that the gradient of $f$ is globally Lipschitz continuous. This implies the function's slope does not change too abruptly, allowing for a stable quadratic upper bound.
However, many modern applications—such as phase retrieval, blind deconvolution, and problems involving $\ell_p$ norms with $1 < p < 2$—violate this assumption. While the Bregman Proximal Gradient (BPG) was developed to handle these "relatively smooth" functions by using a non-Euclidean distance, it often results in subproblems that are computationally expensive and lack closed-form solutions.
The ABPG Framework: Bridging Efficiency and Flexibility
The authors introduce the Approximate Bregman Proximal Gradient (ABPG) algorithm to address these computational hurdles. The core innovation is the use of a second-order Taylor approximation of the Bregman distance. This approximation transforms the potentially complex BPG subproblem into a simpler quadratic form.
When the kernel function $\phi$ is chosen such that its Hessian is diagonal (separable), the ABPG subproblem reduces to a standard proximal mapping. This allows for efficient, often closed-form updates, significantly reducing the per-iteration cost compared to exact Bregman methods.
To ensure stability despite the approximation, the algorithm incorporates a backtracking line search. This ensures that the objective function decreases sufficiently at each step, maintaining the convergence properties of the more complex BPG.
Theoretical Unification and Convergence
A significant contribution of this work is demonstrating that ABPG serves as a unifying framework. By selecting different kernel functions $\phi$, ABPG recovers several classical algorithms as special cases. For instance, if the Hessian of the kernel is the identity matrix, ABPG becomes the standard Proximal Gradient method. If it matches the Hessian of the objective function, it recovers the Proximal Newton method.
Theoretically, the authors establish global subsequential convergence under the "smooth adaptable" (L-smad) assumption. This property is a generalization of relative smoothness, allowing the algorithm to handle functions where the gradient is not even locally Lipschitz continuous at certain points, such as the origin in $\ell_p$ problems with $p \in (1, 2)$.
Experimental Validation
The algorithm was tested against several benchmarks, including $\ell_p$ regularized least squares and nonnegative linear systems.
- Handling Non-Lipschitz Singularities: In $\ell_p$ problems where $p=1.1$, standard methods like Proximal Gradient or Regularized Newton often fail to converge because the gradient becomes unbounded near zero. ABPG, by contrast, handles these singularities gracefully and was the only method to consistently reach a solution within 1,000 iterations.
- Computational Speed: In applications like nonnegative linear systems using Kullback-Leibler divergence, ABPG's closed-form subproblems allowed it to outperform the standard BPG in terms of wall-clock time.
- Robustness: Across various $\ell_p$ loss scenarios, ABPG consistently achieved lower objective values and higher reconstruction accuracy than Proximal Gradient with Line Search (PGL).
Conclusion
ABPG offers a powerful alternative for nonconvex optimization where traditional Lipschitz assumptions fail. By approximating the Bregman distance, it maintains the theoretical benefits of relative smoothness while providing the computational simplicity of proximal gradient methods. Future work will focus on developing accelerated versions of ABPG and extending global convergence proofs to more general classes of composite problems.
Summary updated