Efficient Elastic Net Regularization for Sparse Linear Models
This work addresses the computational bottleneck in training sparse models for high-dimensional data, such as text classification, but it is incremental as it extends existing delayed update methods to specific regularizers.
The paper tackles the problem of efficiently training sparse linear models with elastic net regularization by introducing an algorithm that applies stochastic gradient updates only to non-zero features and uses dynamic programming for constant-time delayed updates. The result is a method that trains a logistic regression classifier with elastic net regularization over 2000 times faster on a dataset with 260,941 features and an average of 88 non-zero features per example.
This paper presents an algorithm for efficient training of sparse linear models with elastic net regularization. Extending previous work on delayed updates, the new algorithm applies stochastic gradient updates to non-zero features only, bringing weights current as needed with closed-form updates. Closed-form delayed updates for the $\ell_1$, $\ell_{\infty}$, and rarely used $\ell_2$ regularizers have been described previously. This paper provides closed-form updates for the popular squared norm $\ell^2_2$ and elastic net regularizers. We provide dynamic programming algorithms that perform each delayed update in constant time. The new $\ell^2_2$ and elastic net methods handle both fixed and varying learning rates, and both standard {stochastic gradient descent} (SGD) and {forward backward splitting (FoBoS)}. Experimental results show that on a bag-of-words dataset with $260,941$ features, but only $88$ nonzero features on average per training example, the dynamic programming method trains a logistic regression classifier with elastic net regularization over $2000$ times faster than otherwise.