Safe Peeling for L0-Regularized Least-Squares with supplementary material
We introduce a new methodology dubbed ``safe peeling'' to accelerate the resolution of L0-regularized least-squares problems via a Branch-and-Bound (BnB) algorithm. Our procedure enables to tighten the convex relaxation considered at each node of the BnB decision tree and therefore potentially allows for more aggressive pruning. Numerical simulations show that our proposed methodology leads to significant gains in terms of number of nodes explored and overall solving time.s show that our proposed methodology leads to significant gains in terms of number of nodes explored and overall solving time.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
A recently introduced technique for a sparse optimization problem called "safe screening" allows us to identify irrelevant variables in the early stage of optimization. In this paper, we first propose a flexible framewor…
Supplementary material for Uncorrected least-squares temporal difference with lambda-return
Here, we provide a supplementary material for Takayuki Osogami, "Uncorrected least-squares temporal difference with lambda-return," which appears in {\it Proceedings of the 34th AAAI Conference on Artificial Intelligence…
Node-screening tests for L0-penalized least-squares problem with supplementary material
We present a novel screening methodology to safely discard irrelevant nodes within a generic branch-and-bound (BnB) algorithm solving the l0-penalized least-squares problem. Our contribution is a set of two simple tests …
regressionA Risk Comparison of Ordinary Least Squares vs Ridge Regression
We compare the risk of ridge regression to a simple variant of ordinary least squares, in which one simply projects the data onto a finite dimensional subspace (as specified by a Principal Component Analysis) and then pe…
regressionFinite Sample System Identification: Improved Rates and the Role of Regularization
This paper studies low-order linear system identification via regularized regression. The nuclear norm of the system’s Hankel matrix is added as a regularizer to the least-squares cost function due to the following advan…