Home

Welcome to the PQSQ-regularized-regression wiki! Here you have short introduction into PQSQ-based regression regularization method. This page also contains some Supplementary Material to the paper "Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning" by A.N.Gorban, E.Mirkes, A.Zinovyev.

Brief description of the algorithm for PQSQ-based regularization method

basic approach to regularise regression using arbitrary regularization term approximated by PQSQ function

PQSQ-based regularized regression is a solution of the following optimization problem

where N is the number of data points, m is the number of attributes, x are dependent and y is independent variables, β are regression coefficients, λ is the regularization parameter, and u(x) is a piecewise quadratic function penalizing the absolute values of the regression coefficients. u(x) can imitate L₁ norm (lasso-like) or a mixture of L₁ and L₂ norm (elastic net-like) or any other penalty. Solution of this problem can be found by iterations; at each iteration a simply modified system of linear equations for usual regression is solved. Convergence of the algorithm is guaranteed by the general theory of the cones of minorant functions.

Below is an example of a PQSQ (piece-wise quadratic function of subquadratic growth) potential function u(x). f(x) is a majorant function; here it is f(x)=x; the potential is defined with trimming after r₃.

PQSQ function can be used to approximate spheres in various metrics. For example, below are approximations of a L₁ sphere in 2D. The precision of approximation depends on the choice of intervals. In practice, using 5 intervals gives a reasonably precise approximation.

PQSQ regularized regression works just as regularized regression based on L₁-norm (lasso) by confining the regression coefficients to a sphere of certain radius:

'black hole' trick for introducing sparsity in the regression estimation

Unlike pure L₁-based penalty, the coefficients of PQSQ-regularized regression diminish with increase of λ but there is nothing to shrink them to exact zero values, same as in ridge regression. However, it is relatively straightforward to modify the algorithm, to achieve sparsity of the regression solution. The 'black hole' trick consists in eliminating from regression training after each iteration all regression coefficients β^k smaller by absolute value than a given parameter ε ('black hole radius'). Those regression coefficients which have passed the 'black hole radius' are put to zero and do not have any chance to change their values in the next iterations.

Time performance comparison for 8 datasets of various sizes (MatLab lasso function, ordinary laptop)

Comparison with MatLab lasso function of approximation error for regularized regression for 8 datasets of different sizes

Links to the datasets used in the PQSQ method testing (most are from UC Irvine Machine Learning Repository, Regression tasks)

Breast cancer Wisconsin dataset

Prostate cancer dataset: original example from the seminal LASSO paper

ENergy Efficiency (ENB2012) dataset

Parkinsons Telemonitoring dataset

Communities and Crime dataset. Note: 'Crime reduced' dataset has been formed by selecting each 10th row of the complete Crime matrix.

Forest Fires dataset

'Random' regression example was constructed using the code from the MATLAB lasso command documentation:

         n = 1000;
         p = 250;
         X = randn(n,p);
         beta = randn(p,1); beta0 = randn;
         Y = beta0 + X*beta + randn(n,1);