On Newton Screening
arXiv:2001.10616
Abstract
Screening and working set techniques are important approaches to reducing the size of an optimization problem. They have been widely used in accelerating first-order methods for solving large-scale sparse learning problems. In this paper, we develop a new screening method called Newton screening (NS) which is a generalized Newton method with a built-in screening mechanism. We derive an equivalent KKT system for the Lasso and utilize a generalized Newton method to solve the KKT equations. Based on this KKT system, a built-in working set with a relatively small size is first determined using the sum of primal and dual variables generated from the previous iteration, then the primal variable is updated by solving a least-squares problem on the working set and the dual variable updated based on a closed-form expression. Moreover, we consider a sequential version of Newton screening (SNS) with a warm-start strategy. We show that NS possesses an optimal convergence property in the sense that it achieves one-step local convergence. Under certain regularity conditions on the feature matrix, we show that SNS hits a solution with the same signs as the underlying true target and achieves a sharp estimation error bound with high probability. Simulation studies and real data analysis support our theoretical results and demonstrate that SNS is faster and more accurate than several state-of-the-art methods in our comparative studies.
arXiv commentThis paper has fatal mistakes
References in corpus (11)
- Pathwise coordinate optimization
- Lasso Screening Rules via Dual Polytope Projection
- Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
- Screening Tests for Lasso Problems
- Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso
- Safe Screening With Variational Inequalities and Its Application to LASSO
- A Safe Screening Rule for Sparse Logistic Regression
- GAP Safe Screening Rules for Sparse-Group-Lasso
- Dual Extrapolation for Sparse Generalized Linear Models
- A Semismooth Newton Method for Fast, Generic Convex Programming
- A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems