# Provably tuning the ElasticNet across instances

arXiv: https://arxiv.org/abs/2207.10199 · HTML: https://mlsanity.com/paper/2207.10199/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 65 references that are in the map.
- First posted on arXiv 20 Jul 2022.

## Builds on (most cited first, 13 of 13)

- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Learning-to-learn non-convex piecewise-Lipschitz functions](https://mlsanity.com/paper/2108.08770/) (2021)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019)
- [Data driven semi-supervised learning](https://mlsanity.com/paper/2103.10547/) (2021)
- [Don't Fall for Tuning Parameters: Tuning-Free Variable Selection in High Dimensions With the TREX](https://mlsanity.com/paper/1404.0541/) (2014)

## Built on by (most cited first, 14 of 14)

- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Offline-to-online hyperparameter transfer for stochastic bandits](https://mlsanity.com/paper/2501.02926/) (2025)
- [Efficiently Learning the Graph for Semi-supervised Learning](https://mlsanity.com/paper/2306.07098/) (2023)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Subsidy design for better social outcomes](https://mlsanity.com/paper/2409.03129/) (2024)
- [Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees](https://mlsanity.com/paper/2502.12937/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)
- [Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances](https://mlsanity.com/paper/2310.02246/) (2023)
- [Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming](https://mlsanity.com/paper/2505.11636/) (2025)
- [Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2608.17343/) (2026)
- [Sparse Priors for Efficient Distribution Learning](https://mlsanity.com/paper/2609.20883/) (2026)

## Abstract (arXiv)

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.