WHInter: A Working set algorithm for High-dimensional sparse second order Interaction models
Learning sparse linear models with two-way interactions is desirable in many application domains such as genomics. l1-regularised linear models are popular to estimate sparse models, yet standard implementations fail to address specifically the quadratic explosion of candidate two-way interactions in high dimensions, and typically do not scale to genetic data with hundreds of thousands of features. Here we present WHInter, a working set algorithm to solve large l1-regularised problems with two-way interactions for binary design matrices. The novelty of WHInter stems from a new bound to efficiently identify working sets while avoiding to scan all features, and on fast computations inspired from solutions to the maximum inner product search problem. We apply WHInter to simulated and real genetic data and show that it is more scalable and two orders of magnitude faster than the state of the art.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression
Owing to their statistical properties, non-convex sparse regularizers have attracted much interest for estimating a sparse linear model from high dimensional data. Given that the solution is sparse, for accelerating conv…
regressionAn Average Classification Algorithm
Many classification algorithms produce a classifier that is a weighted average of kernel evaluations. When working with a high or infinite dimensional kernel, it is imperative for speed of evaluation and storage issues t…
ClassificationGeneral ClassificationEfficient Binary Embedding of Categorical Data using BinSketch
In this work, we present a dimensionality reduction algorithm, aka. sketching, for categorical datasets. Our proposed sketching algorithm Cabin constructs low-dimensional binary sketches from high-dimensional categorical…
Dimensionality ReductionSharp Convergence Rates for Forward Regression in High-Dimensional Sparse Linear Models
Forward regression is a statistical model selection and estimation procedure which inductively selects covariates that add predictive power into a working statistical regression model. Once a model is selected, unknown r…
Model SelectionregressionVocal Bursts Intensity PredictionAccelerating Spherical k-Means
Spherical k-means is a widely used clustering algorithm for sparse and high-dimensional data such as document vectors. While several improvements and accelerations have been introduced for the original k-means algorithm,…
ClusteringComputational Efficiency