This is a resource page for the TREX which allows sparse tuning-free variable selection for linear regression. The TREX is currently available as MATLAB package. R/Python packages are under development.
The forward model is assumed to be the standard linear model:
Here, X is a known design matrix and y is a known continuous response vector. The vector β comprises the unknown coefficients and σ an unknown scale.
The TREX estimator [1] is based on solving the following objective function:
The constant c is by default set to c=0.5, thus requiring no tuning (as compared to, e.g, the Lasso). However, the objective is non-convex and comprises 2p minima.
Several different algorithmic strategies are available to solve the objective. A proximal gradient descent for an approximate solution has been introduced in [1], referred to as q-TREX. Via appropriate reformulation and decomposition, the TREX can be solved exactly by solving 2p convex Second-Order Cone Programs (SOCPs) [2], referred to as c-TREX. Alternatively, the convex subproblems in the c-TREX can also be solved with Douglas-Rachford proximal splitting [3]. The latter algorithm also allows solving sub-problems of the generalized TREX [3]:
where any q>1 can be chosen. Note that in the limit q=1, the TREX reduces to the Sqrt-Lasso [4].
The package includes all of the above algorithmic strategies in one framework. Theoretical bounds for the TREX prediction error are available in [5].
The TREX package contains the following files and folders
- examples/ (different scenarios), also includes figure creation for [2].
- solvers/ (Schmidt's PSG code, place the ecos/SCS solver here (after download))
- trex/ (TREX solvers (both single and multi-thread versions), TREX knockoff filter)
- misc/ (additional files including barweb plotting and the knockoff filter (after download))
Two solvers have been tested to solve the TREX problem in SOCP form.
-
ecos: Conic solver for the c-TREX. The software can be downloaded here. The MATLAB interface can be found here.
-
SCS: SOCP solver for the c-TREX. SCS can be downloaded here.
The solver packages should be compiled and placed in the solver/ folder.
Knockoff filtering with the TREX requires the MATLAB knockoff filter package by Barber-Foygel and Candes. The software can be downloaded here.
The deprecated link during initial development was here
Please place it in the misc/ folder
The proximal solvers from [1] and [3] are fully integrated and do not rely on external software.
To include the package in your MATLAB environment, type first
install_trexThe code builds on results from the following papers:
- [1] J Lederer, CL Müller, Don't fall for tuning parameters: tuning-free variable selection in high dimensions with the TREX, Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015
- [2] J Bien, I Gaynanova, J Lederer, CL Müller, Non-convex global minimization and false discovery rate control for the TREX, Journal of Computational and Graphical Statistics 27 (1), 23-33, 2018
- [3] PL Combettes, CL Müller, Perspective functions: Proximal calculus and applications in high-dimensional statistics, Journal of Mathematical Analysis and Applications 457 (2), 1283-1306, 2018
- [4] A Belloni, V Chernozhukov, L Wang, Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming Biometrika, 98(4), 2011
- [5] J Bien, I Gaynanova, J Lederer, CL Müller, Prediction error bounds for linear regression with the TREX, Test 28 (2), 451-474, 2019
Maintainer:
- Christian L. Müller, Center for Computational Mathematics, Flatiron Institute, Simons Foundation (cmueller@flatironinstitute.org)
Workaround for compiling SCS code using mex for Mac OS X with MATLAB 2015a and Xcode 7+ http://www.mathworks.com/matlabcentral/answers/246507-why-can-t-mex-find-a-supported-compiler-in-matlab-r2015b-after-i-upgraded-to-xcode-7-0