An Inexact Bregman Proximal Difference-of-Convex Algorithm with Two Types of Relative Stopping Criteria

Lei Yang, Jingjing Hu, Kim-Chuan TohJ. Sci. Comput 2025 · DOI

TL;DR

This paper introduces a new algorithm, the inexact Bregman proximal difference-of-convex algorithm (iBPDCA), designed to solve a broad class of optimization problems that are common in machine learning and signal processing. The key innovation is the use of "inexact" subproblem solving with novel relative stopping criteria, making the algorithm more practical and efficient for real-world applications.

What Problem Does This Paper Address?

Many optimization problems in fields like compressed sensing, statistical regression, and machine learning can be formulated as minimizing a function that is a "difference of convex" (DC) functions. These problems are challenging because they can be non-convex, and standard optimization techniques might struggle. While existing methods like the DC algorithm (DCA) and its variants (like proximal DCA and Bregman proximal DCA) exist, they often require solving subproblems exactly. This exactness requirement can be computationally prohibitive, especially for large-scale problems, limiting their practical applicability. This paper aims to bridge this gap by developing an algorithm that allows for approximate solutions to these subproblems, making it more flexible and efficient without sacrificing convergence guarantees.

Methods

The core contribution is the development of an inexact Bregman proximal difference-of-convex algorithm (iBPDCA). This algorithm builds upon the Bregman proximal DC algorithm (BPDCA) but crucially allows for inexact solutions to the subproblems. The novelty lies in the introduction of two types of relative stopping criteria (SC1 and SC2). These criteria control the error introduced in solving the subproblems in each iteration. Unlike previous inexact methods that might require exact subgradient computations or global Lipschitz continuity assumptions, the iBPDCA is more general. It leverages the concept of an "L-smooth adaptable property" which is less restrictive. The algorithm's convergence is established under standard assumptions, including the Kurdyka-Łojasiewicz (KL) property, ensuring both global subsequential and sequential convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on synthetic and standard benchmark datasets.

Key Insights and Ideas

  • Practicality through Inexactness: The most significant insight is that allowing inexact solutions to subproblems, controlled by well-defined relative stopping criteria, doesn't hinder convergence but greatly enhances practical applicability and efficiency.
  • Two Relative Stopping Criteria: The introduction of SC1 and SC2 offers distinct strategies for error control. SC1 uses the current iteration's Bregman distance, while SC2 uses the preceding one. This difference, though subtle, impacts theoretical analysis and computational performance, with SC2 potentially offering advantages in verification cost.
  • Broader Applicability: The iBPDCA framework is designed to be versatile, encompassing existing exact and inexact methods and potentially introducing new ones. Its flexibility allows it to adapt to different DC decompositions of a problem, facilitating the design of more efficient algorithms.
  • Less Restrictive Assumptions: By using the "L-smooth adaptable property" instead of global Lipschitz continuity, the iBPDCA can handle a wider range of objective functions.

Key Results

The paper establishes:

  • Global Convergence: Both global subsequential and global sequential convergence of the generated iterates are proven under suitable conditions.
  • Superior Performance: Numerical experiments on the $\ell_1-\ell_2$ regularized least squares problem and the constrained $\ell_1-\ell_2$ sparse optimization problem demonstrate that the iBPDCA (both SC1 and SC2 variants) outperforms existing algorithms like GIST, nmAPG, pDCAe, and ESQMe in terms of computational time and convergence speed, especially for large-scale problems.
  • Validation of Stopping Criteria: The numerical results empirically validate the necessity and significance of developing different types of stopping criteria for efficient subproblem computation.

Limitations and Future Work

  • Summable Error Condition: The theoretical analysis for global sequential convergence relies on a summable error condition ($\sum ||\Delta^k|| < \infty$). While the paper shows this can be verified, it acknowledges that eliminating this requirement for convergence would be an interesting future research direction.
  • Assumption E: The requirement for the error term $\delta_k$ to eventually become zero (Assumption E) might limit applicability in some complex constraint scenarios. Investigating how to remove this restriction is suggested.
  • Computational Cost of SC2: While SC2 offers practical benefits, its verification can be more computationally intensive than SC1 in certain scenarios, particularly when the kernel function leads to expensive Bregman distance calculations. The paper notes that SC2 can be more advantageous for large-scale problems due to a more economical checking strategy.
  • Future Research: The authors suggest exploring extensions of the BPDCAe algorithm to an inexact version as a future research topic.

Summary updated

BibTeX
@article{yang2025inexact,
  author = {Lei Yang and Jingjing Hu and Kim-Chuan Toh},
  title = {{An Inexact Bregman Proximal Difference-of-Convex Algorithm with Two Types of Relative Stopping Criteria}},
  journal = {J. Sci. Comput.},
  year = {2025},
  doi = {10.1007/s10915-025-02904-2},
}
Figure