sparse regression

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization

  • Hussein Hazimeh
  • Rahul Mazumder
  • Ali Saab
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Second-Order Cone Programming Tags , , , ,

    We consider the least squares regression problem, penalized with a combination of the L0 and L2 norms (a.k.a. L0 L2 regularization). Recent work presents strong evidence that the resulting L0-based estimators can outperform popular sparse learning methods, under many important high-dimensional settings. However, exact computation of L0-based estimators remains a major challenge. Indeed, state-of-the-art mixed … Read more

    Safe screening rules for L0-Regression

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , ,

    We give safe screening rules to eliminate variables from regression with L0 regularization or cardinality constraint. These rules are based on guarantees that a feature may or may not be selected in an optimal solution. The screening rules can be computed from a convex relaxation solution in linear time, without solving the L0 optimization problem. … Read more

    A mixed-integer optimization approach to an exhaustive cross-validated model selection for regression

  • Dennis Kreber
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , ,

    We consider a linear regression model for which we assume that many of the observed regressors are irrelevant for the prediction. To avoid overfitting, we conduct a variable selection and only include the true predictors for the least square fitting. The best subset selection gained much interest in recent years for addressing this objective. For … Read more

    Rank-one Convexification for Sparse Regression

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , , , ,

    Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an L0 constraint restricting the support of the estimators is a challenging non-convex optimization problem. In this paper, we derive new strong convex relaxations for sparse regression. These relaxations are based … Read more

    A Unified Framework for Sparse Relaxed Regularized Regression: SR3

  • Aleksandr Y. Aravkin
  • Peng Zheng
  • Travis Askham
  • Steve Brunton
  • Nathan Kutz
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization, Statistics Tags , , , ,

    Regularized regression problems are ubiquitous in statistical modeling, signal processing, and machine learning. Sparse regression in particular has been instrumental in scientific model discovery, including compressed sensing applications, vari- able selection, and high-dimensional analysis. We propose a broad framework for sparse relaxed regularized regression, called SR3. The key idea is to solve a relaxation of … Read more

    Convex optimization under combinatorial sparsity constraints

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    We present a heuristic approach for convex optimization problems containing sparsity constraints. The latter can be cardinality constraints, but our approach also covers more complex constraints on the support of the solution. For the special case that the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in … Read more

    Safe Feature Elimination in Sparse Supervised Learning

  • Laurent El Ghaoui
  • Tarek Rabbani
  • Vivian Viallon
    • Categories Applications - OR and Management Sciences Tags , , ,

    We investigate fast methods that allow to quickly eliminate variables (features) in supervised learning problems involving a convex loss function and a l1 -norm penalty, leading to a potentially substantial reduction in the number of variables prior to running the supervised learning algorithm. The methods are not heuristic: they only eliminate features that are guaranteed … Read more