Fast, Exact Model Selection and Permutation Testing for l2-Regularized Logistic Regression

Bryan R. Conroy, Paul SajdaAISTATS 2012

Abstract

Training $\ell_2$-regularized logistic regression models repeatedly for cross-validation or permutation testing is a significant computational burden. We introduce a "simultaneous" solver that leverages shared data structures across related problems to provide exact solutions with speedups of up to 100x. By defining a shared template matrix and utilizing additive splitting techniques, our method significantly reduces the marginal cost of solving additional problems.

Introduction

In machine learning, model selection (e.g., cross-validation) and significance testing (e.g., permutation testing) often require training hundreds or thousands of related models. For linear models like Ridge Regression, closed-form solutions exist to accelerate this process. However, Logistic Regression requires iterative solvers like Iteratively Reweighted Least Squares (IRLS), where each step involves inverting a large Hessian matrix. Standard approaches treat each problem independently (tabula rasa), leading to immense redundant computation.

Methodology

The core innovation is a Simultaneous Logistic Regression solver based on stationary iterative methods. Instead of solving $P$ linear systems independently, we define a single "template" matrix $M$ shared across all problems. We then employ an additive splitting technique ($A_p = M - N_p$), where $N_p$ accounts for problem-specific differences in labels or data subsets.

Key technical highlights include:

  • Template Matrix Design: $M$ is constructed using the element-wise maximum of model fit variances, ensuring guaranteed convergence for all sub-problems.
  • Matrix Vectorization: Updates are computed via a single large matrix multiplication with Hadamard products, optimized for modern BLAS/LAPACK libraries.
  • Low-Rank Exploitation: For high-dimensional data ($D \gg N$), the system is transformed into a smaller $N \times N$ problem.
  • Continuation (Warm-Starting): Solutions from high-regularization ($\lambda$) versions accelerate convergence for lower $\lambda$ values.

Experimental Evaluation

The method was validated on three distinct datasets: MNIST handwritten digits (binary classification), EEG auditory oddball detection ($N=374, D=44$), and fMRI auditory cortex responses ($N=374, D=301$).

Effective problem size vs. training set size for MNIST (Digits 0 vs. 1). The low effective problem size relative to the training set size (up to 10,000 for LOO-CV) indicates significant speedups.

Results and Discussion

The proposed method achieved a 100x speedup on MNIST Leave-One-Out Cross-Validation (LOO-CV). The "effective problem size" ($P_{eff}$), representing the computational cost relative to a single direct solve, remains small even as the number of actual problems $P$ increases. For instance, in MNIST LOO-CV with $N=10,000$, the effective cost is equivalent to only ~100 individual solves.

Effective problem size vs. number of permutations for EEG and fMRI datasets. The speedup is more pronounced in the higher-dimensional fMRI data.

As shown in the experimental results, the speedup is particularly significant for high-dimensional data like fMRI compared to EEG. This is because the method reduces the burden of high-dimensional matrix inversions by moving the primary $D^3$ cost into a one-time setup phase. Unlike approximate methods, this approach converges to the exact IRLS solution.

Limitations and Future Work

The method is currently limited to $\ell_2$-regularization due to the requirement for twice-differentiable objective functions. It cannot be directly applied to $\ell_1$-regularized (Lasso) problems without modification. Future work includes extending this framework to other Generalized Linear Models (GLMs), such as Poisson regression, which follow a similar iterative training structure.

Summary updated

BibTeX
@article{conroy2012fast,
  author = {Bryan R. Conroy and Paul Sajda},
  title = {{Fast, Exact Model Selection and Permutation Testing for l2-Regularized Logistic Regression}},
  journal = {AISTATS},
  year = {2012},
}
Figure