Source-linked AI summary
A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
Pinghua Gong, Changshui Zhang, Zhaosong Lu, Jianhua Huang, Jieping Ye
TL;DR
Non-convex penalties can improve sparse learning formulations, but their associated optimization problems are difficult to solve efficiently at scale. The paper introduces GIST, combining proximal updates with BB-initialized line searches, and reports convergence guarantees and efficient performance on large-scale data sets.
Problem
Non-convex sparsity-inducing penalties are difficult to optimize, while the commonly used Multi-Stage convex relaxation is computationally expensive for large-scale problems.
Method
GIST iteratively solves a proximal operator problem, using closed-form solutions for many penalties and BB-initialized monotone or non-monotone line searches.
Results
GIST converges under both line-search criteria, with limit points that are critical points, and experiments demonstrate fast convergence on large-scale data sets.
Takeaways & Limitations
GIST provides an efficient iterative approach for a general class of non-convex sparse-learning optimization problems.
Takeaways & Limitations
The paper leaves theoretical performance bounds, including prediction and parameter-estimation error bounds, for future work.
Abstract
from arXiv · showhide
Non-convex sparsity-inducing penalties have recently received considerable attentions in sparse learning. Recent theoretical investigations have demonstrated their superiority over the convex counterparts in several sparse learning settings. However, solving the non-convex optimization problems associated with non-convex penalties remains a big challenge. A commonly used approach is the Multi-Stage (MS) convex relaxation (or DC programming), which relaxes the original non-convex problem to a sequence of convex problems. This approach is usually not very practical for large-scale problems because its computational cost is a multiple of solving a single convex problem. In this paper, we propose a General Iterative Shrinkage and Thresholding (GIST) algorithm to solve the nonconvex optimization problem for a large class of non-convex penalties. The GIST algorithm iteratively solves a proximal operator problem, which in turn has a closed-form solution for many commonly used penalties. At each outer iteration of the algorithm, we use a line search initialized by the Barzilai-Borwein (BB) rule that allows finding an appropriate step size quickly. The paper also presents a detailed convergence analysis of the GIST algorithm. The efficiency of the proposed algorithm is demonstrated by extensive experiments on large-scale data sets.
1. Introduction
Sparse learning benefits from sparse representations, but ℓ0-based optimization is difficult and ℓ1 regularization can be suboptimal because it over-penalizes solutions. The paper proposes GIST to address the difficulty of optimizing a broad class of non-convex penalties.
- ℓ0 regularization promotes sparsity but creates a discontinuous, non-convex optimization problem that is challenging to solve.
- ℓ1 regularization is a continuous convex surrogate that has succeeded in many applications but can be suboptimal because it loosely approximates ℓ0 and over-penalizes.
- Non-convex penalties such as ℓq-norm, SCAD, LSP, MCP, GP, and capped-ℓ1 were proposed to better approximate ℓ0.
- GIST solves optimization problems for a large class of non-convex penalties using proximal operators, closed-form for many commonly used penalties.
2. The Proposed Algorithm: GIST
GIST addresses non-convex regularized optimization by combining proximal updates with BB-initialized line search under stated smoothness, DC, and lower-boundedness assumptions. Its convergence analysis establishes critical-point results for both monotone and non-monotone criteria.
- Problem formulation: The formulation assumes a continuously differentiable loss with Lipschitz-continuous gradient, a continuous penalty expressible as a difference of convex functions, and an objective bounded from below.These are assumptions A1–A3 used throughout the paper.
- Proximal update: GIST generates iterates by taking a gradient step on the loss and then solving an equivalent proximal operator problem.The proximal center is u^(k) = w^(k) − ∇l(w^(k))/t^(k).
- Proximal update: For the regularizers listed in Table 1, the proximal subproblem has closed-form solutions, although some resulting subproblems may remain non-convex.Closed forms are explicitly noted for commonly used penalties, including ℓ1 and Capped ℓ1.
- Step-size initialization: GIST initializes each outer-iteration step size with the Barzilai-Borwein rule, using t^(k)I to approximate the loss Hessian and reduce line-search cost.The initialization is motivated by the importance of reducing the line-search cost for fast convergence.
- Line search: The algorithm supports monotone and non-monotone line searches, with the latter accepting an iterate whose objective exceeds the current value if it improves over the maximum from the previous m iterations.Here m > 1, and the monotone criterion uses σ ∈ (0, 1).
3. Related Work
The related work covers convex-relaxation, iterative-shrinkage, reweighted, and sequential-convex approaches for non-convex regularized optimization. It positions GIST as a broader proximal framework and contrasts its computational strategy with MS and SCP.
- Multi-Stage convex relaxation: MS convex relaxation rewrites the problem into a sequence of convex optimization problems.Each subproblem is convex, but generally lacks a closed-form solution.
- Multi-Stage convex relaxation: The MS method costs k times one convex solve for k outer iterations, making it expensive for large-scale problems.The stated cost reflects repeatedly solving the convex subproblem.
- Iterative shrinkage methods: IST methods generate iterates through a proximal problem but require a convex regularizer, whereas GIST handles both convex and non-convex cases.The paper presents GIST as a more general framework than these IST variants.
- Reweighted methods: VIRL generates iterates for a weighted non-convex optimization problem and uses the previous step-size initialization in its line search.Its line search increases the step parameter geometrically until the criterion is met.
- Sequential Convex Programming: SCP linearizes the concave component of the regularizer, while GIST uses the original regularizer in its proximal operator.The paper states that experiments compare GIST and SCP efficiency.
4. Experiments
The experiments evaluate GIST against MS and SCP on twelve high-dimensional sparse data sets under fixed implementation and stopping settings. BB-initialized GIST variants converge rapidly and attain the smallest objective values in the reported comparisons.
- Experimental setup: Twelve high-dimensional sparse data sets are used to compare GIST, MS, and SCP for capped ℓ1-regularized logistic regression.Two data sets are preprocessed as two-class problems; the remaining ten are converted from multi-class to two-class tasks.
- Convergence comparison: GISTbb-Monotone and GISTbb-Nonmonotone decrease objective values rapidly, converge fastest, and achieve the smallest objective values.These observations are reported across the parameter settings shown in Figure 1.
- Convergence comparison: GISTbb-Nonmonotone can temporarily increase the objective value but finally converges and is faster overall than GISTbb-Monotone in most cases.The result indicates an acceleration associated with the non-monotone line-search criterion.
- Convergence comparison: SCPbb-Nonmonotone is comparable in several cases but is slower and reaches larger objective values than GISTbb-Nonmonotone in the remaining cases.The comparison supports using the original regularizer in GIST's proximal operator.
5. Conclusions
The paper concludes that GIST efficiently solves a broad class of non-convex sparse-learning problems, with convergence guarantees and fast empirical convergence. It identifies theoretical performance analysis as future work.
- GIST solves a general class of non-convex optimization problems encountered in sparse learning.
- The algorithm combines a proximal operator with Barzilai-Borwein step-size initialization and monotone or non-monotone line-search criteria.
- GIST converges under both monotone and non-monotone line-search criteria.
- Experiments on large-scale data sets demonstrate fast convergence of the proposed algorithm.
- Future work will analyze theoretical performance measures including prediction-error and parameter-estimation error bounds.
Appendix: Solutions to Problem (2)
The appendix derives solutions to the coordinate-wise proximal subproblems for several non-convex penalties. It characterizes candidate solutions and selects the one minimizing the corresponding univariate objective.
- Problem (2) decomposes into d independent univariate optimization problems.
- LSP: For LSP, the update uses sign(u)x, where x is selected by evaluating stationary points and feasible-region endpoints.
- LSP: For LSP, the candidate set can contain three or one elements depending on the stated discriminant condition; otherwise it is {0}.
- SCAD: SCAD is handled by recasting problem (9) into three subproblems and selecting among candidate solutions using their objective values.
- MCP and Capped ℓ1: MCP and capped ℓ1 are likewise recast into two subproblems, with the solution determined by comparing the resulting objective values.