  An important unresolved challenge in the theory of regularization is to set
the regularization coefficients of popular techniques like the ElasticNet with
general provable guarantees. We consider the problem of tuning the
regularization parameters of Ridge regression, LASSO, and the ElasticNet across
multiple problem instances, a setting that encompasses both cross-validation
and multi-task hyperparameter optimization. We obtain a novel structural result
for the ElasticNet which characterizes the loss as a function of the tuning
parameters as a piecewise-rational function with algebraic boundaries. We use
this to bound the structural complexity of the regularized loss functions and
show generalization guarantees for tuning the ElasticNet regression
coefficients in the statistical setting. We also consider the more challenging
online learning setting, where we show vanishing average expected regret
relative to the optimal parameter pair. We further extend our results to tuning
classification algorithms obtained by thresholding regression fits regularized
by Ridge, LASSO, or ElasticNet. Our results are the first general
learning-theoretic guarantees for this important class of problems that avoid
strong assumptions on the data distribution. Furthermore, our guarantees hold
for both validation and popular information criterion objectives.
