Journal Home Page

Cumulative Index

List of all Volumes

Complete Contents
of this Volume

Previous Article

Next Article

Journal of Convex Analysis 28 (2021), No. 4, 1053--1072
Copyright Heldermann Verlag 2021

Screening Rules and its Complexity for Active Set Identification

Eugene Ndiaye
Riken AIP, Japan

Olivier Fercoq
LTCI, TÚlÚcom Paris, and: Institut Polytechnique de Paris, Palaiseau, France

Joseph Salmon
IMAG, UniversitÚ Montpellier, France

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.

Keywords: Convex optimization, screening rules, active set identification, nonsmooth optimization.

MSC: 49M29, 65K05, 90C06, 90C25.

[ Fulltext-pdf  (1482  KB)] for subscribers only.