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_trex

The 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 ([email protected])

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