Screening rules and its complexity for active set identification

MaRDI QIDQ5026418zbMATH OpenFDO

Authors Eugene Ndiaye, Olivier Fercoq, Joseph Salmon

Publication date 8 February 2022

Full work available at URL https://arxiv.org/abs/2009.02709, https://www.heldermann.de/JCA/JCA28/JCA284/jca28061.htm

zbMATH Keywords

convex optimizationnonsmooth optimizationactive set identificationscreening rules

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06)

Abstract: Screening rules were recently introduced as a technique for explicitly identifying active structures such as sparsity, in optimization problem arising in machine learning. This has led to new methods of acceleration based on a substantial dimension reduction. We show that screening rules stem from a combination of natural properties of subdifferential sets and optimality conditions, and can hence be understood in a unified way. Under mild assumptions, we analyze the number of iterations needed to identify the optimal active set for any converging algorithm. We show that it only depends on its convergence rate.

Recommendations

• Lasso screening rules via dual polytope projection
• Gap safe screening rules for sparsity enforcing penalties
• Strong Rules for Discarding Predictors in Lasso-Type Problems
• Identifying active manifolds.
• Screening for a reweighted penalized conditional gradient method

Cites work

• scientific article; zbMATH DE number 1667417 (Why is no real title available?)
• scientific article; zbMATH DE number 3728055 (Why is no real title available?)
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 7306914 (Why is no real title available?)
• A finite algorithm for finding the projection of a point onto the canonical simplex of \({\mathbb R}^ n\)
• A new approach to variable selection in least squares problems
• Activity identification and local linear convergence of forward-backward-type methods
• Advanced preprocessing techniques for linear and quadratic programming
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Fast projection onto the simplex and the l₁ ball
• From error bounds to the complexity of first-order descent methods for convex functions
• Gap safe screening rules for sparsity enforcing penalties
• Least angle regression. (With discussion)
• Model Selection and Estimation in Regression with Grouped Variables
• Online learning and online convex optimization
• Safe Feature Elimination in Sparse Supervised Learning
• Strong Rules for Discarding Predictors in Lasso-Type Problems
• Sure independence screening for ultrahigh dimensional feature space. With discussion and authors' reply
• Understanding machine learning. From theory to algorithms
• \(C^{1,\omega (\cdot )}\)-regularity and Lipschitz-like properties of subdifferential

Cited in

(5)

• Lasso screening rules via dual polytope projection
• Gap safe screening rules for sparsity enforcing penalties
• Search for sparse active inputs: a review
• Safe Rules for the Identification of Zeros in the Solutions of the SLOPE Problem
• Screening for a reweighted penalized conditional gradient method

Describes a project that uses

Uses Software

• Celer
• BLITZ

This page was built for publication: Screening rules and its complexity for active set identification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5026418)