A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems

Tianxiang Liu, Ting Kei Pong, Akiko TakedaMath. Program 2019 · OpenReview

TL;DR

This paper introduces a novel algorithm, the Successive Difference-of-Convex Approximation Method (SDCAM), to tackle a challenging class of optimization problems that combine smooth functions with multiple non-convex, non-smooth components. SDCAM efficiently handles these complex problems by approximating the non-smooth parts with their Moreau envelopes, enabling the use of standard first-order methods and guaranteeing convergence to a stationary point.

What Problem Does This Paper Address?

Many real-world problems in areas like machine learning, signal processing, and finance involve optimizing functions that are not "nice" – they can be non-smooth (having sharp corners or discontinuities) and non-convex (having multiple local minima). Specifically, this paper focuses on problems where the objective function is a sum of a smooth part and several non-negative, proper, closed, and possibly non-convex non-smooth functions. These non-smooth functions are often composed with linear maps, which is common when introducing multiple regularization terms to encourage specific structures in the solution (e.g., sparsity, low-rank).

The core challenge lies in the coupling of these non-smooth functions. While standard methods like proximal gradient descent work well when there's only one non-smooth term whose proximal mapping is easy to compute, the presence of multiple, coupled non-smooth terms makes computing the overall proximal mapping intractable. This prevents the direct application of these efficient first-order methods.

Methods

The authors propose a Successive Difference-of-Convex Approximation Method (SDCAM). The key idea is to iteratively approximate the non-smooth components of the objective function using their Moreau envelopes. A Moreau envelope is a smoothing technique that replaces a non-smooth function with a smooth one, and importantly, the Moreau envelope of a non-negative proper closed function is a continuous difference-of-convex (DC) function.

In each iteration, SDCAM constructs an approximation function by replacing the original non-smooth terms with their Moreau envelopes. This approximation function, being a DC function, can then be minimized using first-order methods combined with majorization techniques. The authors leverage a key observation: the Moreau envelope of a non-negative proper closed function can be expressed as the supremum of affine functions, which leads to a difference-of-convex representation. This allows for efficient minimization using techniques like the Nonmonotone Proximal Gradient method with Majorization (NPGmajor), which is detailed in the appendix. The efficiency stems from the fact that the proximal mappings of the individual non-smooth functions are assumed to be easy to compute. The algorithm is proven to generate a bounded sequence, and any accumulation point is shown to be a stationary point of the original problem under suitable assumptions.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and demonstrates its applicability through examples and numerical experiments on synthetic data generated according to specific problem structures.

Key Insights and Ideas

  • Moreau Envelopes as a Unifying Smoothing Tool: The paper highlights the power of Moreau envelopes not just for smoothing, but specifically for transforming non-smooth, non-convex functions into continuous difference-of-convex functions. This transformation is crucial for enabling efficient optimization.
  • DC Representation for Efficient Minimization: The key insight is that Moreau envelopes of non-negative proper closed functions can be represented as the supremum of affine functions, leading to a DC representation. This allows existing efficient DC programming techniques to be applied.
  • Bridging the Gap for Coupled Non-smoothness: SDCAM effectively addresses the challenge of coupled non-smooth terms by breaking down the problem into a sequence of subproblems where each non-smooth term is handled individually via its Moreau envelope.
  • Guaranteed Convergence for Non-convex Problems: The method provides a theoretical guarantee of convergence to a stationary point, which is a significant achievement for non-convex optimization problems.

Key Results

  • Algorithm Development: The paper proposes and details the SDCAM algorithm for solving a specific class of nonconvex nonsmooth optimization problems.
  • Theoretical Guarantees: The authors prove that the sequence generated by SDCAM is bounded and that any accumulation point is a stationary point of the objective function under suitable assumptions.
  • Numerical Performance: The paper demonstrates the efficiency of SDCAM through numerical experiments on two types of problems: nonconvex fused regularized problems and simultaneously sparse and low-rank matrix optimization problems. In these experiments, SDCAM generally achieved comparable or better results in terms of function values and sometimes fewer iterations compared to existing methods like smoothing-based approaches.

Limitations and Future Work

  • Assumptions: The method relies on several assumptions, including the existence of easy-to-compute proximal mappings for individual non-smooth functions and the level-boundedness of the smooth part plus one of the non-smooth functions. The applicability of SDCAM depends on these conditions being met.
  • Global Minimizers: While SDCAM guarantees convergence to a stationary point, it does not guarantee convergence to a global minimizer for general non-convex problems. The paper notes that under a stronger condition on the approximation accuracy, accumulation points can be shown to be global minimizers.
  • Future Work: The paper suggests exploring the application of SDCAM to a wider range of structured optimization problems and further investigating its theoretical properties and practical performance. The numerical results also hint at potential improvements by comparing different parameter settings and termination criteria.

Summary updated

Abstract

We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a smooth function and a finite number of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises naturally in various applications when different regularizers are introduced for inducing simultaneous structures in the solutions. Solving these problems, however, can be challenging because of the coupled nonsmooth functions: the corresponding proximal mapping can be hard to compute so that standard first-order methods such as the proximal gradient algorithm cannot be applied efficiently. In this paper, we propose a successive difference-of-convex approximation method for solving this kind of problems. In this algorithm, we approximate the nonsmooth functions by their Moreau envelopes in each iteration. Making use of the simple observation that Moreau envelopes of nonnegative proper closed functions are continuous difference-of-convex functions, we can then approximately minimize the approximation function by first-order methods with suitable majorization techniques. These first-order methods can be implemented efficiently thanks to the fact that the proximal mapping of each nonsmooth function is easy to compute. Under suitable assumptions, we prove that the sequence generated by our method is bounded and any accumulation point is a stationary point of the objective. We also discuss how our method can be applied to concrete applications such as nonconvex fused regularized optimization problems and simultaneously structured matrix optimization problems, and illustrate the performance numerically for these two specific applications.
BibTeX
@inproceedings{liu2019successive,
  author = {Tianxiang Liu and Ting Kei Pong and Akiko Takeda},
  title = {{A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems}},
  booktitle = {Math. Program},
  year = {2019},
  url = {https://openreview.net/forum?id=RZn5SFxsa0},
}
Figure