Safe Peeling for L0-Regularized Least-Squares with supplementary material

Abstract--We introduce a new methodology dubbed "safe The rest of the paper is organized as follows. Our peeling This paper focuses on the resolution of the so-called "l IV and its performance is regularized least-squares" problem given by illustrated in Sec. V. Proofs of the results presented in the p Unfortunately, this problem also turns out to be has to be understood component-wise, e.g., x [l,u] means NP-hard [4, Th. 1]. Moreover, η() denotes the indicator function flurry of contributions proposing tractable procedures able to which equals to 0 if the condition in argument is fulfilled and recover approximate solutions of (1-P). This observation, combined with some recent III. Due to space limitation, we only review the elements of A standard approach is to use a Branch-and-Bound (BnB) interest to introduce the proposed peeling method. We refer the algorithm that solves (1-P), see [6-11]. In this paper, we propose a new strategy, dubbed "safe peeling", to accelerate the exact resolution of (1-P). In a A. Pruning nutshell, our contribution is a computationally simple test applied at each node of the BnB decision tree to identify some The crux of BnB methods consists in identifying and discarding intervals of R In this section, we introduce our proposed peeling procedure. This assumption will One ubiquitous approach in the literature [7, 9, 13] to find be relaxed later on in Sec. A proof of this result is available in App. A. A consequence On the one hand, item i) implies that the pruning test (4) of preserving the pruning decision is that taking the new involves the following quantity (rather than p This additional constraint usually takes the form " M x This impairment pertains to a large class of mixed-integer problems and with M > 0 and is known as "Big-M" constraint, see [7, Sec.