Screening Rules for Convex Problems
We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations, and works in two steps. First, given any approximate point, the structure of the objective function and the duality gap is used to gather information on the optimal solution. In the second step, this information is used to produce screening rules, i.e. safely identifying unimportant weight variables of the optimal solution. Our general framework leads to a large variety of useful existing as well as new screening rules for many applications. For example, we provide new screening rules for general simplex and $L_1$-constrained problems, Elastic Net, squared-loss Support Vector Machines, minimum enclosing ball, as well as structured norm regularized problems, such as group lasso.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Safe Sample Screening for Robust Support Vector Machine
Robust support vector machine (RSVM) has been shown to perform remarkably well to improve the generalization performance of support vector machine under the noisy environment. Unfortunately, in order to handle the non-co…
Screening Rules for Lasso with Non-Convex Sparse Regularizers
Leveraging on the convexity of the Lasso problem , screening rules help in accelerating solvers by discarding irrelevant variables, during the optimization process. However, because they provide better theoretical guaran…
Celer: a Fast Solver for the Lasso with Dual Extrapolation
Convex sparsity-inducing regularizations are ubiquitous in high-dimensional machine learning, but solving the resulting optimization problems can be slow. To accelerate solvers, state-of-the-art approaches consist in red…
Safe screening rules for L0-regression
We give safe screening rules to eliminate variables from regression with L0 regularization or cardinality constraint. These rules are based on guarantees that a feature may or may not be selected in an optimal solution. …
regressionLasso Screening Rules via Dual Polytope Projection
Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve…