Generalized Linear Model Regression under Distance-to-set Penalties

Jason Xu, Eric C. Chi, Kenneth LangeNeurIPS 2017 · OpenReview

Fitting Generalized Linear Models (GLMs) under complex constraints is a foundational task in statistics and machine learning. A paper presented at NIPS 2017 introduces a novel framework that replaces traditional "shrinkage" penalties, like the LASSO, with "distance-to-set" penalties. This shift provides a more flexible and less biased approach to performing sparse, shape-constrained, and low-rank regression.

The Problem with Traditional Penalties

In many applications, we need to impose constraints on regression models. For example, we might require that only a few variables are used (sparsity) or that coefficients follow a specific order (isotonic regression).

The standard tool for enforcing sparsity is the LASSO ($\ell_1$ penalty). While highly effective and computationally friendly, LASSO has a major drawback: shrinkage. Because it penalizes the absolute magnitude of coefficients, it artificially pulls them toward zero. This biases the estimates of the "true" effects and often forces the model to include spurious variables (false positives) to compensate for the shrunken true signals.

Conversely, methods like "best subset selection" are mathematically ideal for sparsity but are computationally NP-hard, making them impossible to solve efficiently for large datasets. The authors aim to bridge this gap by creating a method that is computationally efficient like LASSO but avoids the bias of shrinkage, even when dealing with non-convex constraints like matrix rank.

A New Approach: Distance-to-Set Penalties

The core idea of the paper is to minimize a loss function that combines the negative log-likelihood of the GLM with a distance-to-set penalty. Instead of penalizing the size of the parameter vector $\beta$, the authors penalize the squared Euclidean distance from $\beta$ to a target constraint set $C$.

Because the distance penalty drops to exactly zero once the parameter vector enters the constraint set, the model does not suffer from the constant "pull" toward zero that causes bias in LASSO.

Optimization via Majorization-Minimization

To solve this new objective, the authors employ the Majorization-Minimization (MM) Principle. The MM algorithm solves a difficult optimization problem by iteratively minimizing a simpler "surrogate" function that upper-bounds the original objective.

Illustration of the Majorization-Minimization (MM) principle, showing surrogate functions bounding the objective.

The authors demonstrate that the squared distance to a set is easily majorized by the distance to the projection of the current point onto that set. This means that as long as a set has an efficient projection operator (which is true for sparse vectors, isotone cones, and low-rank matrices), the problem can be solved efficiently.

To make the algorithm scale to high dimensions, they employ the Woodbury Formula for efficient matrix inversion and Quasi-Newton acceleration to speed up the convergence of the MM iterates.

Key Results and Insights

The authors evaluated their method on synthetic simulations (sparse regression and matrix regression) as well as real-world datasets, including Global Temperature Anomalies and a high-dimensional EEG Alcoholism dataset.

  • Eliminating Bias and Lowering Error: In sparse Poisson and Logistic regression simulations, the MM distance penalty consistently achieved lower Mean Squared Error (MSE) and significantly less bias than LASSO, MCP, and SCAD.
  • Direct Sparsity Control: Unlike LASSO, where practitioners must tune a penalty parameter $\lambda$ and hope it yields the desired sparsity, this method allows a researcher to explicitly request exactly $k$ predictors by projecting directly onto that specific set.
  • Handling Non-Convexity: The algorithm provides strong convergence guarantees even for non-convex constraints, such as restricting the rank of a matrix.
Comparison of relative error and mean squared error across different regularization methods.

In real-world testing on the EEG dataset (122 subjects, 16,000+ dimensions), the distance-based approach achieved a misclassification error of 0.1475, outperforming spectral shrinkage methods. Despite the complexity of the constraints, the algorithm converged on this high-dimensional data in just 31 seconds on a standard laptop.

Limitations and Future Work

While highly effective, the primary computational bottleneck of the method remains matrix inversion. Although the Woodbury formula mitigates this when observations are fewer than predictors, extremely high-dimensional "big data" settings may require further modifications, such as coordinate or block descent variants.

Additionally, because the constraints can be non-convex, the algorithm is guaranteed to find a stationary point, but not necessarily the global minimum. However, empirical results strongly suggest that the local minima found are of very high quality. Future directions include exploring alternate Bregman divergences and applying the framework to "quasi-likelihood" estimation to extend the method beyond standard exponential family distributions.

Summary updated

Abstract

Estimation in generalized linear models (GLM) is complicated by the presence of constraints. One can handle constraints by maximizing a penalized log-likelihood. Penalties such as the lasso are effective in high dimensions but often lead to severe shrinkage. This paper explores instead penalizing the squared distance to constraint sets. Distance penalties are more flexible than algebraic and regularization penalties, and avoid the drawback of shrinkage. To optimize distance penalized objectives, we make use of the majorization-minimization principle. Resulting algorithms constructed within this framework are amenable to acceleration and come with global convergence guarantees. Applications to shape constraints, sparse regression, and rank-restricted matrix regression on synthetic and real data showcase the strong empirical performance of distance penalization, even under non-convex constraints.
BibTeX
@inproceedings{xu2017generalized,
  author = {Jason Xu and Eric C. Chi and Kenneth Lange},
  title = {{Generalized Linear Model Regression under Distance-to-set Penalties}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=r1WfUvbubB},
}
Figure