Source-linked AI summary
A proximal difference-of-convex algorithm with extrapolation
Bo Wen, Xiaojun Chen, Ting Kei Pong
TL;DR
The paper addresses potentially slow proximal DCA iterations for level-bounded DC problems by adding extrapolation. It proposes pDCAe, proves stationary-point and convergence results under KL-based assumptions, and reports that it usually outperforms proximal DCA and GIST on two DC regularized least-squares classes.
Problem
Proximal DCA has simple subproblems but can be potentially slow because it coincides with proximal gradient when the concave part is absent.
Method
The paper proposes pDCAe, which adds extrapolation to proximal DCA and allows parameter choices including FISTA with fixed restart.
Results
pDCAe has stationary cluster points under level-boundedness, globally converges under KL and differentiability assumptions, and usually outperforms proximal DCA and GIST on two DC regularized least-squares classes.
Takeaways & Limitations
Extrapolation provides a general pDCA framework that retains proximal DCA as a special case while supporting convergence guarantees and empirical improvements on the tested models.
Takeaways & Limitations
The convergence guarantees rely on assumptions such as level-boundedness, and whole-sequence convergence additionally requires the KL property and locally Lipschitz differentiability of P2.
Abstract
from arXiv · showhide
We consider a class of difference-of-convex (DC) optimization problems whose objective is level-bounded and is the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous concave function. While this kind of problems can be solved by the classical difference-of-convex algorithm (DCA) [26], the difficulty of the subproblems of this algorithm depends heavily on the choice of DC decomposition. Simpler subproblems can be obtained by using a specific DC decomposition described in [27]. This decomposition has been proposed in numerous work such as [18], and we refer to the resulting DCA as the proximal DCA. Although the subproblems are simpler, the proximal DCA is the same as the proximal gradient algorithm when the concave part of the objective is void, and hence is potentially slow in practice. In this paper, motivated by the extrapolation techniques for accelerating the proximal gradient algorithm in the convex settings, we consider a proximal difference-of-convex algorithm with extrapolation to possibly accelerate the proximal DCA. We show that any cluster point of the sequence generated by our algorithm is a stationary point of the DC optimization problem for a fairly general choice of extrapolation parameters: in particular, the parameters can be chosen as in FISTA with fixed restart [15]. In addition, by assuming the Kurdyka-Łojasiewicz property of the objective and the differentiability of the concave part, we establish global convergence of the sequence generated by our algorithm and analyze its convergence rate. Our numerical experiments on two difference-of-convex regularized least squares models show that our algorithm usually outperforms the proximal DCA and the general iterative shrinkage and thresholding algorithm proposed in [17].
1 Introduction
The paper studies DC optimization and motivates a proximal DCA with extrapolation to address the potential slowness of proximal DCA while preserving simple subproblems. It establishes stationary-point and global-convergence results under stated assumptions and evaluates the method numerically.
- Motivation: DC optimization objectives can be decomposed into convex components, but classical DCA subproblem difficulty depends heavily on the chosen decomposition.DCA linearizes the concave part and solves a convex problem at each iteration.
- Motivation: The proximal DCA uses a decomposition that also quadratically majorizes the smooth convex term, yielding efficiently solvable subproblems when the proper closed convex function has an easy proximal mapping.This decomposition is adopted in prior work and is designed to simplify each iteration.
- Motivation: Extrapolation adds momentum from previous iterates and achieves O(1/k^2) function-value convergence for FISTA, compared with O(1/k) for proximal gradient in convex settings.The paper uses this convex-optimization success as motivation for accelerating proximal DCA.
- Contributions: The proposed pDCAe covers FISTA with fixed-restart parameters, proves stationary cluster points under level-boundedness, and establishes whole-sequence convergence and rate analysis under KL and differentiability assumptions.The method is evaluated on ℓ1−2 and logarithmic regularized least-squares models.
- Organization: The paper is organized around preliminaries, problem formulation and algorithm design, convergence analysis, and numerical experiments.The numerical section follows the convergence-rate analysis.
2 Notation and preliminaries
This section establishes notation for functions, domains, level-boundedness, subdifferentials, and gradients, then recalls the KL property and its uniformized form for convergence analysis.
- Function preliminaries: A proper function never equals −∞ and has a nonempty domain, while closedness means lower semicontinuity and level-boundedness means bounded lower-level sets.These definitions apply to extended-real-valued functions used throughout the analysis.
- Subdifferentials: The limiting subdifferential reduces to the classical convex subdifferential for convex functions and to the gradient for continuously differentiable functions.The paper also uses partial gradients for individual coordinates.
- KL property: The KL property is recalled as a convergence-analysis tool and is satisfied by broad classes including proper closed semialgebraic functions.It is defined through a neighborhood, an auxiliary concave function, and a derivative inequality.
- KL property: A proper closed function satisfying the KL property at every point in the domain of its subdifferential is called a KL function.This terminology is used in the later global-convergence assumptions.
- Uniformization: The uniformized KL property provides common parameters and an auxiliary function near a compact set where the function is constant and satisfies the KL property pointwise.The result applies to nearby points whose function values lie in a specified interval above the common value.
3 Problem formulation and the proximal difference-of-convex algorithm with extrapolation
The paper formulates a level-bounded DC problem with smooth and nonsmooth components, explains why proximal DCA offers simpler but potentially slow subproblems, and introduces pDCAe with broad extrapolation choices.
- Problem formulation: The target problem combines a smooth convex function with Lipschitz gradient, a proper closed convex function, and a continuous convex term subtracted from the objective.The objective is assumed level-bounded, ensuring a finite infimum and nonempty global minimizer set.
- DCA and proximal DCA: Natural DCA decomposition produces convex subproblems that need not have closed-form or simple solutions.Their difficulty depends on the selected DC decomposition.
- DCA and proximal DCA: The proximal DCA replaces the smooth term with a quadratic majorant, producing subproblems equivalent to evaluating a proximal operator that is easy to compute for many choices of P1.The resulting iterate is uniquely defined because P1 is proper closed convex.
- Motivation for extrapolation: Despite simple subproblems, proximal DCA can be slow because it becomes proximal gradient when P2 = 0, motivating extrapolation to accelerate it.The paper specifically targets the practical iteration burden associated with proximal gradient.
- pDCAe: pDCAe reduces to proximal DCA when βt ≡ 0 and permits parameter sequences satisfying {βt} ⊆ [0, 1) and sup_t βt < 1.These conditions include choices from FISTA with fixed or adaptive restart.
4 Convergence analysis
The analysis establishes that pDCAe has bounded iterates and stationary accumulation points under level-boundedness, then proves whole-sequence convergence and rates under additional KL and differentiability assumptions.
- Global subsequential convergence: Under level-boundedness and admissible extrapolation parameters, pDCAe generates a bounded sequence whose accumulation points are stationary.The proof uses a decreasing Lyapunov-type expression involving the objective and successive-iterate differences.
- Global subsequential convergence: The objective is constant on the set of accumulation points of the pDCAe sequence.This conclusion follows after establishing that all accumulation points are stationary and that the objective values converge.
- Global convergence and convergence rate: When P2 is continuously differentiable near the stationary-point set with locally Lipschitz gradient, and the auxiliary function E is KL, the whole sequence converges to a stationary point.The theorem also establishes convergence of the augmented accumulation-point set and summability of successive differences.
- Global convergence and convergence rate: The KL exponent determines the convergence regime: finite termination for θ = 0, linear convergence for θ ∈ (0, 1/2], and a sublinear bound for θ ∈ (1/2, 1).The stated bounds are respectively eventual constancy, c1η^t, and c2t^(-(1-θ)).
5 Numerical experiments
The experiments evaluate pDCAe against pDCA and GIST on ℓ1−2 and logarithmic regularized least squares problems using randomized instances. Across both regularizers and tested parameter settings, pDCAe is reported to outperform both comparison methods.
- Experimental setup: The experiments compare pDCAe, pDCA, and GIST on DC regularized least squares models with ℓ1−2 and logarithmic regularizers.The tests use randomized instances with normalized Gaussian design matrices and sparse Gaussian signals.
- Experimental setup: pDCAe uses extrapolation parameters with both fixed-restart and adaptive-restart strategies, whereas pDCA is the βt ≡0 special case.Both methods are initialized at the origin; pDCA uses the same Lipschitz parameter L = λmax(A^T A).
- ℓ1−2 regularizer: The ℓ1−2 experiments average CPU time, iterations, and termination function values over 30 random instances for ten problem-size triples and two λ settings.The settings are λ = 5 × 10^-4 and λ = 1 × 10^-3.
- Logarithmic regularizer: The logarithmic-regularizer experiments use the same ten problem-size triples, 30-instance averaging, and two λ settings as the ℓ1−2 tests.The reported measures are λmax(A^T A) computation time, iterations, CPU time, and termination function values.
- Logarithmic regularizer: pDCAe always outperforms pDCA and GIST in the reported logarithmic-regularizer experiments.The conclusion is drawn from the tabled CPU times, iteration counts, and termination function values.
6 Conclusion
The paper proposes pDCAe, an extrapolated proximal DCA that includes FISTA-style fixed-restart parameters. It establishes subsequential and, under additional assumptions, global convergence with rate analysis, while experiments report improved performance over pDCA and GIST.
- Conclusion: pDCAe extends proximal DCA with extrapolation and reduces to proximal DCA when βt ≡0.Its framework permits a wide range of extrapolation parameters, including FISTA with fixed restart.
- Conclusion: Under level-boundedness, every cluster point generated by pDCAe is stationary, and the algorithm has global subsequential convergence.With the Kurdyka–Łojasiewicz property and locally Lipschitz differentiability of P2, the full sequence globally converges and its rate is analyzed.
- Conclusion: Numerical experiments on two DC regularized least squares classes show that pDCAe usually outperforms proximal DCA and GIST.The tested classes are summarized in the paper as two difference-of-convex regularized least squares models.