DC approximation approaches for sparse optimization

Hoai An Le Thi; Tao Pham Dinh; Hoai Minh Le; Xuan Thanh Vo

Source-linked AI summary

DC approximation approaches for sparse optimization

Hoai An Le Thi, Tao Pham Dinh, Hoai Minh Le, Xuan Thanh Vo

arXiv:1407.0286v2Jul 1, 2014math.NAcs.LGstat.ML

TL;DR

Sparse optimization requires tractable methods for problems involving the difficult zero-norm. The paper unifies nonconvex approximations through DC programming and DCA, proves consistency and exact-equivalence results, and develops algorithms whose behavior depends on the decomposition and initialization.

Problem
Nonconvex zero-norm approximations can yield good sparsity but remain difficult, while consistency between approximate and original problems has been insufficiently established.
Method
The paper studies a common DC approximation of the zero-norm, analyzes sparse-inducing penalties, and develops DCA schemes within a DC programming framework.
Results
The analysis links approximate and original global and local minimizers, while suitable parameters make some Capped-ℓ1 and SCAD approximate problems equivalent to the original problem.
Takeaways & Limitations
The framework provides theoretical justification and algorithmic tools for nonconvex sparse optimization, including DCA variants covering standard sparse approximation algorithms.
Takeaways & Limitations
DCA quality depends on selecting an appropriate DC decomposition and a good initial point for the specific problem structure.

Abstract

from arXiv · show

Sparse optimization refers to an optimization problem involving the zero-norm in objective or constraints. In this paper, nonconvex approximation approaches for sparse optimization have been studied with a unifying point of view in DC (Difference of Convex functions) programming framework. Considering a common DC approximation of the zero-norm including all standard sparse inducing penalty functions, we studied the consistency between global minimums (resp. local minimums) of approximate and original problems. We showed that, in several cases, some global minimizers (resp. local minimizers) of the approximate problem are also those of the original problem. Using exact penalty techniques in DC programming, we proved stronger results for some particular approximations, namely, the approximate problem, with suitable parameters, is equivalent to the original problem. The efficiency of several sparse inducing penalty functions have been fully analyzed. Four DCA (DC Algorithm) schemes were developed that cover all standard algorithms in nonconvex sparse approximation approaches as special versions. They can be viewed as, an $\ell _{1}$-perturbed algorithm / reweighted-$\ell _{1}$ algorithm / reweighted-$\ell _{1}$ algorithm. We offer a unifying nonconvex approximation approach, with solid theoretical tools as well as efficient algorithms based on DC programming and DCA, to tackle the zero-norm and sparse optimization. As an application, we implemented our methods for the feature selection in SVM (Support Vector Machine) problem and performed empirical comparative numerical experiments on the proposed algorithms with various approximation functions.

1 Introduction

Sparse optimization models sparsity through the zero-norm, but its discontinuity makes resulting nonconvex problems difficult. The paper unifies nonconvex approximations within DC programming, establishing consistency and exact-equivalence results while developing algorithms and analyzing applications.

Motivation: The zero-norm counts nonzero variables and models sparsity, but its discontinuity at the origin makes optimization problems involving it challenging.Sparse optimization places the zero-norm in objectives or constraints, often to select representative variables.
Applications: Sparse optimization appears in compressed sensing, portfolio selection, feature selection, regression, classification, and other application domains.The paper specifically discusses feature selection for preserving or improving classifier discrimination in high-dimensional data.
Existing approaches: Existing approaches treat the zero-norm through convex approximation, nonconvex approximation, or nonconvex exact reformulation.Convex approaches are easier to solve but may fail to attain zero-norm solutions, whereas nonconvex approximations remain difficult because of local minima.
Contributions: The paper uses DC programming and DCA to provide a unified theoretical and computational framework for nonconvex sparse optimization.The setting includes polyhedral convex feasible sets and finite DC objectives.
Contributions: The common DC approximation links global and local minimizers of approximate and original problems, with some approximate minimizers exactly solving the original problem.Under concavity and boundedness conditions, some optimal approximate solutions coincide with original solutions.
Contributions: Capped-ℓ1 and SCAD are identified as the best approximations under suitable parameter comparisons, and suitable parameters can make their approximate problems equivalent to the original problem.The equivalence result is established through exact penalty techniques for these particular approximations.

2 Outline of DC programming and DCA

DC programming represents nonconvex objectives as differences of convex functions, while DCA repeatedly solves convex subproblems formed by affine majorization. The framework supplies optimality, duality, descent, and convergence results, but algorithm quality depends on the DC decomposition and initialization.

DC programming: A DC function is represented as g − h, where g and h are proper lower-semicontinuous convex functions.Convex constraints can be incorporated into the objective through an indicator function.
DC programming: DC programming extends convex programming to a broad class of nonconvex objectives while retaining access to convex-optimization tools.Its central difficulty is distinguishing local from global solutions and lacking verifiable global optimality conditions.
DC duality: DC duality associates primal and dual DC programs with the same optimal value and relationships between their solution sets.Under technical conditions, transportation results also hold for local solutions.
DCA: DCA affine-majorizes the concave part −h and minimizes the resulting convex program at each iteration.Each iteration uses a subgradient of h at the current iterate to construct the convex subproblem.
DCA guarantees: DCA is a descent method without line search, and its iterates have convergence guarantees under stated boundedness, polyhedral, or subanalytic conditions.The cited properties include critical-point convergence, linear convergence, finite convergence for polyhedral DC programs, and whole-sequence convergence for subanalytic data.
Algorithm design: DCA performance depends on the chosen DC decomposition, whose selection affects convergence speed, robustness, efficiency, and the globality of computed solutions.Practical DCA also requires an appropriate initial point and efficient solution of each convex subproblem.

3 DC approximation approaches: consistency results

The paper formulates zero-norm approximation within a general DC framework and establishes consistency results for global and local solutions as approximation tightness increases.

Problem formulation: The ℓ0-problem minimizes f(x, y) + λ∥x∥0 over a convex feasible set, with the zero-norm counting nonzero components.The step-function representation ∥x∥0 = Σ_i s(x_i) motivates continuous approximations rθ.
DC approximation framework: The approximation family rθ is modeled as an even, increasing DC function satisfying structural assumptions that support the consistency analysis.The assumptions include evenness, monotonicity, a DC representation, nonnegative subgradient products, and vanishing subgradients away from zero as θ grows.
DC approximation framework: Problems (12) and (13) are equivalent for global and local solutions after introducing z = |x|, while the reformulated problem can also transfer global solutions back.The reformulation uses the set Ω1 = {(x, y, z): (x, y) ∈ K, |x_i| ≤ z_i}.
Global consistency: As θ increases, convergent global minimizers of approximate problems become global minimizers of the original problem, and compactness gives uniform proximity to the original solution set.Under a finite-set condition, sufficiently large θ makes approximate global minimizers in that set also solve the original problem.
Scope and motivation: The analysis extends prior consistency results and is motivated by the fact that approximate problems remain nonconvex, so practical methods generally rely on local algorithms.The paper also notes that the evenness assumption can be weakened to monotonicity on either side of zero.
Local consistency: Analogous consistency holds for local optimality conditions: convergent approximate stationary points approach original ones, with compactness and finite-set results providing stronger guarantees.Theorem 2 parallels Theorem 1 for the sets L and Lθ defined by the respective necessary local conditions.

4 DC approximation functions

The paper unifies standard zero-norm penalty functions as DC approximations and compares their tightness using matched parameter choices. Capped-ℓ1 and SCAD emerge as the closest approximations, with Capped-ℓ1 enjoying exact equivalence under suitable conditions.

Approximation families: Standard nonconvex penalties—including exponential, ℓp, SCAD, logarithmic, and Capped-ℓ1 functions—are treated as instances of a common DC approximation framework.PiL is included as a more general nonconcave piecewise-linear DC approximation.
Approximation construction: Logarithmic, SCAD, and ℓp functions require scaling and additive adjustment to directly approximate the zero-norm, while ℓp with 0 < p < 1 also uses ε to avoid singularity.The adjustment preserves the original problem while producing the approximation forms used in the analysis.
Parameter comparison: Approximation tightness is compared by matching the right derivatives at zero, while Figure 1 visualizes the resulting approximation functions and parameter settings.The comparison excludes ℓp-norm with 0 < p < 1 and PiL from the shared-derivative property.
Exact equivalence: For compact polyhedral feasible sets, Capped-ℓ1 is equivalent to the original problem for suitable parameters; for box constraints, an exact threshold θ0 is computed.The equivalence is obtained through exact penalty techniques in the compact polyhedral case and directly in the box case.

5 A deeper study on Capped-ℓ1 approximation problems

This section connects continuous penalized reformulations with the Capped-ℓ1 approximation. Under suitable parameter conditions, the approximation is equivalent to the original sparse problem, including in feature-selection SVM settings.

The section establishes the Capped-ℓ1 approximation through binary-variable reformulation, continuous penalization, and parameter-dependent equivalence results.
Exact penalty techniques reformulate the ℓ0-regularized problem as a continuous nonconvex program equivalent to the original problem for sufficiently large penalty parameters.
The Capped-ℓ1 penalty uses rcap(t) = min{θ|t|, 1} and links the continuous penalized formulation to the approximation problem through equivalent optimal solutions.
For τ ≥ λ, the penalized formulation and the Capped-ℓ1 approximation are equivalent in their optimal solutions and objective values.
When τ exceeds a threshold involving λ and τ0, the Capped-ℓ1 approximation is equivalent to the original sparse problem.
5.2 A special case: In feature-selection SVM, the Lipschitz condition on the loss yields equivalence between the original and Capped-ℓ1 problems when θ > κ/λ.

6 DCA for solving the problem (12)

The section develops DCA schemes for concave sparse-inducing approximations and shows how they recover reweighted-ℓ1 and reweighted-ℓ2 procedures. Their formulations differ in sparsity behavior, computational cost, and convergence properties.

6.1 The first DCA scheme: For concave r, the paper constructs DC decompositions and applies DCA directly to the approximate sparse optimization problem.
6.1 The first DCA scheme: If η ≥ r′(0), then ψ(t) = η|t| − r(|t|) is convex, enabling the DC formulation used by the first DCA scheme.
6.2 DCA2 - Relation with reweighted-ℓ1 procedure: The second DCA scheme iteratively solves weighted-ℓ1 subproblems, with weights updated according to the chosen approximation function.
6.3 DCA3 - Relation with reweighted-ℓ2 procedure: The third DCA scheme introduces a perturbation parameter ε > 0 and produces weighted-ℓ2 subproblems at each iteration.
6.3 DCA3 - Relation with reweighted-ℓ2 procedure: With ε = 0, the weighted-ℓ2 update covers standard reweighted-ℓ2 algorithms, but the derivative at zero is not well-defined.
6.4 Discussion on the three DCA based algorithms 1, 2 and 3: Algorithms 1 and 2 have finite convergence for polyhedral DC programs, whereas Algorithm 3 is generally more expensive and lacks a polyhedral DC structure.
6.4 Discussion on the three DCA based algorithms 1, 2 and 3: The expected sparsity ordering is Algorithm 1, then Algorithm 2, then Algorithm 3, because their induced slope ranges increasingly encourage zero components.

7 Application to Feature selection in SVM

The paper applies DC approximations and DCA schemes to feature selection in linear SVMs, where sparsity is imposed through the zero-norm. For polyhedral feasible sets, several approximate formulations are equivalent to the original problem, and the algorithms have finite convergence and local-solution guarantees under stated conditions.

SVM formulation: Feature selection in two-class linear SVMs is formulated using classification-error slack variables and a sparsity-inducing penalty on the feature vector.The slack variables represent classification errors, while the objective combines average classification error with a sparsity term.
DC approximation: The SVM formulation is embedded in the paper’s general DC approximation framework, with equivalent approximate problems constructed over a polyhedral convex set.The feasible-set representation introduces bounds linking auxiliary variables to feature coefficients.
DC approximation: For polyhedral K, all listed approximation functions except r = rP iL yield approximate problems equivalent to problem (60) in the sense of Corollary 1.This equivalence is stated for the approximation functions in Table 2, excluding r = rP iL.
Exactness conditions: For Capped-ℓ1, choosing θ > θ∗ makes the approximate and original SVM problems equivalent.The stated threshold is θ∗ := 1−λ as given in the supplied passage.
DCA schemes: DCA1 and DCA2 generate critical points after finitely many iterations and, under differentiability conditions for Capped-ℓ1, those points are local solutions.The same local-solution conclusion is stated for DCA1 and DCA2 when the relevant second DC component is differentiable at the limit point.
DCA schemes: DCA4 for r = rP iL also reaches a critical point after finitely many iterations and obtains a local solution when the relevant differentiability condition holds.The condition is expressed through |x∗θ for all i in the supplied passage.

3. Compute

Experiments compare DCA schemes and zero-norm approximations for accuracy, sparsity, runtime, and agreement with globally solved instances. Updating θ improves Capped-ℓ1 results, while DCA1 is generally the strongest overall scheme.

DCA scheme comparison: Up to 99% fewer selected features are obtained on large datasets, with DCA1 achieving better sparsity than DCA2/DCA3 on 6 out of 7 datasets.The experiments evaluate sparsity by selected-feature count and percentage.
DCA scheme comparison: DCA1 outperforms DCA2 and DCA3 across accuracy, sparsity, and CPU time for Capped-ℓ1 approximation.DCA1 is faster than DCA2 on 5 out of 7 datasets, while DCA1 and DCA2 are faster than DCA3 because they solve linear programs rather than a convex quadratic program.
DCA1 and Updating θ: Updating θ improves both accuracy and sparsity over fixed-parameter DCA1 across all datasets.Except for WPBC(24), it also improves sparsity over cross-validation-selected θ; accuracy remains comparable.
Comparison with CPLEX: Updating θ matches CPLEX on accuracy and selected-feature count for Ionosphere and WPBC(60), while CPLEX fails to provide a solution for large datasets within 3600 seconds.For WPBC(24), CPLEX selects 7 features versus 8 for Updating θ, with equal training accuracy.
Approximation comparison: Capped-ℓ1 gives the best accuracy among tested approximations, winning all training sets and 4 of 7 test sets.For Breast, the algorithms select about thirty features out of 24481 while reaching up to 98.7% training correctness; CPU time is below 34 seconds except Gisette.

8 Conclusion

The paper unifies nonconvex sparse approximation methods within DC programming, establishing theoretical relationships between approximate and original problems and linking the resulting algorithms to standard approaches.

DC approximation approaches are studied from both theoretical and algorithmic perspectives for sparse optimization.The framework addresses problems involving the zero-norm through DC programming and DCA.
The analysis establishes consistency between global or local minimizers of approximate problems and those of the original problem.Under several cases, minimizers of the approximate problem also solve the original problem.
For bounded polyhedral convex feasible sets and concave approximations, sufficiently large parameters make the approximate and original problems equivalent.The Capped-ℓ1 and SCAD approximations can likewise have the same optimal-solution set as the original problem for sufficiently large θ.
Three DC formulations yield three DCA schemes whose relationships with standard sparse approximation approaches are established.The unified framework connects existing sparsity-inducing methods through DC decompositions and interprets the algorithms as perturbed or reweighted methods.
The unified DC framework clarifies relationships among existing sparsity-inducing methods and exploits DC decompositions of objective functions.The algorithms are viewed as ℓ1-perturbed or reweighted-ℓ1 approaches, with a reweighted-ℓ2 connection for convex objectives.