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$).
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.
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