Provably tuning the ElasticNet across instances
Authors: Nina Balcan
Mikhail Khodak
Dravyansh Sharma
Ameet Talwalkar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Elastic net
data-driven algorithm design
learning theory
regularization

Abstract: 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.

Provably tuning the ElasticNet across instances
Maria-Florina Balcan
Mikhail Khodak
Dravyansh Sharma
Ameet Talwalkar
Carnegie Mellon University*
Abstract
An important unresolved challenge in the theory 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 param- eters of Ridge regression, LASSO, and the ElasticNet across multiple problem instances, a setting that encompasses both cross-validation and multi-task hyperpa- rameter optimization. We obtain novel structural result for the ElasticNet which characterizes the loss as function of the tuning parameters as piecewise-rations. function with algebraic boundaries. We use this 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 ex- pected regret relative the optimal parameter pair. We further extend our results tuning classification algorithms obtained by thresholding regression fits regularized by Ridge, LASSO, or ElasticNet. Our results are the first general marning-theooree guarantees for this important class of problems that avoid strong assumptions on the data distribution. Furthermore, our g guarantees hold for both validation and popular information criterion objectives.
Introduction
LASSO A1 and their generalization the ElasticNet [28] are among the most popular algorithms in machine learning and statistics, with applications to linear classification, regression, data analysis, and feature selection IS
Ridge regression 30
Given supervised dataset (X, v) Rmxp x R with m datapoints and features, these algorithms compute the linear predictor
46
2x
20 24
((xw)
arg min by - x3112 + 1111811 + A211
(1)
A1
BERP
Here Å1, A2 2 0 are regularization coefficients constraining the é and &2 norms, respectively, of the model (3. For general ê₁ and X2 the above algorithm is the ElasticNet, while setting A = 0 recovers Ridge and setting A2 O recovers LASSO.
These coefficients play a crucial role across fields: in machine learning controlling the norm of implies provable generalization guarantees and prevent over-fitting in practice [44] in data analysis their combined use yields parsimonious and interpretable models (28). and in Bayesian statisties they correspond to imposing specific priors on 3 35 33 In practice, X2 regularizes 3 by uniformly shrinking all coefficients, while encourages the model vector be sparse. This means that while they do yield sarning-theoretic and statistical benefits, setting them to be too high will cause models to under-fit the data. The question how to set the regularization coefficients becomes even more unclear in the case of the ElasticNet, as one must juggle trade-offs between sparsity, feature correlation, and bias when setting both λ₁ and X2 simultaneously. As a result, there has been intense empirical and theoretical effort devoted to automatically tuning these parameters. Yet the
"Correspondence: dravyansêcs. cmu, cdu. Author emails: (ninamf, dravyans ) 8es. cmu. edu, { (khodak, talwalkari êcnu. edu
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

ofate-of-the-rt is quite unsatisfactory: proposed work consists of either heuristics without formal guarantees [26 approaches that optimize over finite grid or random set instead of the full or analyses that involve very strong theoretical assumptions [44]
continuous domain
In this work, we study a variant on the above well-established and intensely studied formulation. The key distinction is that instead of single dataset (X, y), we consider a collection of datasets or instances of the same underlying regression problem (X y and would like to learn a pair (A1, Aa) that selects model in equation ① that has low loss on validation dataset. This can be useful to model practical settings, for example where new supervised data is obtained several times or where the set of features may change frequently [19]. We do not require all examples across datasets to be i..d. draws from the same data distribution, and can capture more general data generation scenarios like cross- cross-validaree validation and multi-task learning 45]. Despite these advantages, we remark that our problem formulation is quite different from the standard single dataset setting. Our formulation treats the selection of regularization coefficients as data-driven algorithm design, which often used to study combinatorial problems [27] 3 and has connections to meta-learning [12
Our main contribution is a new structural result for the ElasticNet Regression problem, which implies generalization guarantees for selecting ElasticNet Regression coefficients in the multiple-instance setting. In partieular, Ridge and LASSO regressions are special cases. We extend results obtain low regret in the online learning setting, and to tuning related linear classification algorithms. In summary, we make the following key contributions:
We formulate the problem of tuning the ElasticNet question of learning X and Xg simulta- neously across multiple problem instances, either generated statistically or coming online. Our formulation captures relevant settings like cross-validation and multi-task learning.
We provide novel structural result (Theorem 2.2 that characterizes the loss of the ElasticNet fit. We show that the hyperparameter space can be partitioned by polynomial curves of bounded degrees into pieces where the loss is bivariate rational function. The result holds for both the usual Elas- ticNet validation objective and when it is augmented with information criteria like the AIC or BIC.
An important consequence of our structural result is a bound on the pseudo-dimension (Definition 5) for the loss function class, which yields strong generalization bounds for tuning A and X2 simultaneously in the statistical learning setting (Theorem 3.2p. Informally, for ElasticNet regression problems with at most p parameters, for any problem distribution D, we show that O (+ (p² log& + log })) problem instances (or datasets) are sufficient to learn e-approximation to the best (A1, A2), with probability at least 1 - 5.
In the online setting, we show under very mild data assumptions mucch weaker than prior work-that the problem satisfies a dispersion condition ( (9. As result we can tune all parameters across sequence of instances appearing online and obtain vanishing regret relative
to the optimal parameter in hindsight over the sequence (Theorem 3.3 at the rate Ó(1/vT wrt the length T' of the sequence.
We also give distributional and online learning results for regularized classifiers (Theorems
We include a couple of remarks to emphasize the generality and significance of our results. First, in our multiple-instanee formulation the different problem instances need not have the same number of examples, or even the same set of features. This allows us to handle practical scenarios where the set of features changes across datasets, and we can learn parameters that work well on average across multiple different but related regression tasks. Second, by generating problem instances iid from a fixed (training + validation) dataset, we can obtain iterations (training/valicae validation splits) of popular cross- cross-validade validation techniques (including the popular leave-one-our and Monte Carlo CV) and our result implies that Ó(p² /e2) iterations are enough to determine an ElasticNet parameter with loss within (w.h.p.) of the optimal parameter X over the distribution induced by the cross-validation splits.
Key challenges and insights. A major challenge in learning the ElasticNet parameters is that the variation of the solution path as function of X2 is hard to characterize. Indeed the original ElasticNet paper 47 suggests using the heuristic of grid search to learn a good Ag. even though A may be exactly optimized by computing full solution paths (for each 22). We approach this indirectly by utilizing
'The soft-O notation is used to emphasize dependence on T. and suppresses other factors as well as logarithmic terms.
2

---

characterization of the LASSO solution by 42], which is based on the KKT (Karush Kuhn-Tucker) optimality conditions, to arrive precise piecewise structure for the problem. In more detail, we use these conditions to come up with set of algebraic curves (polynomial equations in λ and X2) of bounded degrees, such that the set of possible discontinuities is contained within the zero-set of these curves, and the loss function behaves well in the each piece of the partition of the parameter domain by these curves. This characterization is crucial in establishing a bound on the structural complexity needed to provide strong generalization guarantees. We further show additional structure on these algebraic curves that (roughly speaking) imply that the curves do not concentrate in any region of the domain, allowing us use the powerful recipe of [8] for online learning.
Related work. Model selection for Ridge regression, LASSO or ElasticNet typically involves selecting the regularization parameter À for given data, although some parameter- free techniques for variable selection have been recently proposed [32]. Choosing 'optimal' parameters for tuning the regularization has been a subject of extensive theoretical and applied research. Much of this effort heuristic [26 61 or focused on developing tuning objectives beyond validation accuracy like AIC or BIC [1I
3 without providing procedures for provably optimizing them. The standard approach given a tuning objective is to optimize it over a grid or random set of parameters, for which there are guarantees [17), but this does not ensure optimality over the entire continuous tuning domain, especially since objectives such as 0-1 validation error or information criteria can have many discontinuities. Selecting a grid that is too fine too coarse result in either very inefficient or highly inaccurate estimates (respectively) for good parameters. Other guarantees make strong assumptions the data distribution such sub-Gaussian noise 44 [6 or depend on unknown parameters that are hard to quantify in practice 223 Recent work has shown asymptotic
consistency of cross-validation for ridge regression, even in the limiting case X2 0 which is particularly interesting for the overparameterized regime 2
610 A successful line of work has focused on efficiently obtaining models for different values of λ₁ using regularization paths [22], but the guarantees are computational rather than learning-theoretie or statistical. In contrast, we provide principled approaches that guarantee near-optimality of selected parameters with high confidence over the entire continuous domain of parameters.
Data-driven algorithm design has proved successful for tuning parameters for variety of combi- natorial problems like clustering, integer programming, auction design and graph- based learning We provide an application of these techniques to parameter tuning in a problem that is not inherently combinatorial by revealing a novel discrete structure. We identify the underlying piecewise structure of the ElasticNet loss function which is extremely effective in establishing searinngthhoores guarantees 10.. To exploit this piecewise structure, we analyze the learning-theor theoretic complexity of rational algebraic function classes and infer generalization guarantees. We also employ and extend general tools and techniques for online data-driven learning from to prove our online learning guarantees for regularization coefficient tuning.
701 5 4
g 4 to rational functions in order
2 Preliminaries and Key Structural Result
Given data (X, y) with X E Rmxp and y E R consisting of m labeled examples with p features, we seek estimators B E R which minimize the regularized loss. Popular regularization methods like LASSO and ElasticNet can be expressed as computing the solution of an optimization problem
g(Xww Xx
Earg min Ily + BEBP
where f: IRP + Rd gives the regularization penalty for estimator A E Rg is the regularization parameter, and d is the number of regularization parameters. d d= for Ridge and LASSO, and d = 2 for the ElasticNet. Setting f = f2 with fz( 11:312 yields Ridge regression, and setting f(3) = (3) := || corresponds to LASSO. Also using (Fx = (fi, (3)) gives the ElasticNet with regularization parameter À (A1, Note that we use the same À (with some notational overloading) to denote the regularization parameters for ridge, LASSO, or ElasticNet.
Px. We write 3(X.y) as simply 3x.f when the dataset (X,y) is clear from context. On any instance x E R" from the feature space, the prediction of the regularized estimator is given by the dot product
(a, Bx. The average squared loss over dataset (X', v/) with X' R xp and 3/ E 1Rm is given
3

---

by ((3x,5, (x)) /// |10 x' X'Bx.5 1 By setting (X', ) to be the training data (X, y), we get the training loss L (3x,, (X) We use (X Bval) to denote a validation split. Distributional and Online Settings. In the distributional or statistical setting, we receive a col- lection of n instances of the regression problem p(t) (x(() xx) D E Rm..p..m == Rpp x R x Rp' x I for [n]] generated i.id. from some problem distribution D. The problems are in the problem space given by 1mm.p = Um1 2m.20.mp5m.pp.5 Rmi.pi.ma (note that the problem distribution D is over .m,p) On any given instance p(1) the loss is given by the squared loss the validation set, (EN(), p()) 1, (x((()))))))) (x val v(il)) On the other hand, in the online setting, we receive sequence of T instances of the ElasticNet regression prob- lem p()) = (x y x
(6) Voal E 1mm for E [T] online. On any given instance p(i), the online learner is required select the regularization parameter A without observing Deal and experiences loss given by ((A(), p())) = (3 (1xx0) ((0)))
(i)
ffl (xxa b()))) The goal is to minimize the regret w.r.t. choosing the best fixed parameter in hindsight for the same problem sequence, i.e. Pr = E e(A(1), p(o) - mIn, Σ {(A, p(o). We also define average regret as 7 Rt and expected regret as E. Rr]] where the expectation is over both the randomness of the loss functions and any random coins used by the online algorithm.
Given class of regularization algorithms A parameterized by regularization parameter À over set of problem instances X. and given loss function E A x X' + IR which measures the loss of any algorithm in A on any fixed problem instance, consider the set of functions H.A {E(A,)) +) A E A}. For example, for the ElasticNet we have (EN P) = (2x (Xp: Vp)),, where yP) and (Xp.y'p) are the training and validation sets associated with problem P E X' respectively. Bounding the pseudo-dimension of H. gives a bound the sample complexity for uniform convergence which minimizes the average loss on any sample S of size n drawn i.idd. from any problem distribution D is guaranteed to be near-optimal with high probability 21 See Appendix AA for the relevant classic definitions and results. Define the dual class H." of a set of real-valued functions 7. C 2* as H. = {he H - E I E X} where h (h) = h(z). In the context of regression problems X, for each fixed problem instance x E X there is dual function Ag that computes the loss e( (..)) for any (primal) function hΛ = ((A.)) E H.A. For a function class H. showing that dual class H is sescewise-structuredd in the sense of Definition] and bounding the complexity of the duals of boundary and piece functions of H' are useful to understand the learnability of H [10].
guarantees, i.e.& bound on the sample size n for which the algorithm As
Definition 1 (Piecewise structured functions, (T).. A function class H C R that maps a domain X to R is (F, G, -iicceeee decomposable for a class G C {0, 1 of boundary functions and a class F S x of piece functions if the following holds: for every h E H, there are k boundary functions 91....,9h E G and a piece function fb E F for each bit vector b E {0, 13 such that for all x E X, h(x) = fn., (z)) where by = (g) (.) (z)) E 1]
Intuitively, real-valued function is piecewise-structure if the domain can be divided into pieces by a finite number of boundary functions (say linear or polynomial thresholds) and the function value over each piece is easy to characterize (e.g. constant, linear, polynomial). To state and understand our structural insights into the ElasticNet problem we will also need the definition of equicorrelation sets, the subset of features with maximum absolute correlation for any fixed '₁ useful for characterizing LASSO/ElasticNet solutions. For any subset & S [p] of the features, we define XE- = (... X.; ............. .)
as the m |E| matrix of columns X., of X corresponding to indices i E. Similarly Be E R él is the subset of estimators in 3 corresponding to indices in E. We will assume all the feature matrixes X (for training datasets) are in general position (Definition 6
Definition 2 (Equicorrelation sets,
Let 3 E arg aaggmin Ily - x312+ + 111131 The equicor- = }1). is simply the set of
relation set corresponding to 3r, E = covariates with maximum absolute correlation. We also define the equicorrelation sign vector for 8 as s = sign( X (v- X33))) E (+1).
{j E [p] - -X88)
Consider the class of algorithms consisting of FlasticNet regressors for different values of = (A1, oo) x (0, oo). We assume X1 0 for technical simplicity (cf. 42 ). We seek to solve

---

problems of the form P= (X, Xval Bvai) E II Hm.p. where (X, y) is the training set, (Xual, Bval) is the validation set with the same set of features, and m. p are upper bounds on the number of examples and features respectively in any dataset. Let HEN {fIN(A, X, X E (0, oo) x (0, 20) denote the set of loss functions for the class of algorithms consisting of FlasticNet regressors for different values of X E TR+ x R+ Additionally, we will consider information criterion based loss functions, eAC PA. P) = (A, P) + 21133,. Jax llo and 4 (A, P) (A, P) + 2|
((X.v)
Jus llo log m
39 Let
HEN and E denote the corresponding sets of loss functions. These criteria are popularly used to compute the squared loss on the training set, to give alternatives to gross-validation. We do not
make any assumption on the relation between training and validation sets in our formulation, so our analysis can capture these settings as well.
We will now establish a piecewise structure of the dual class loss functions (Definition ID A key obser- vation is that if the signed equicorrelation set (E,s) (i.e. a subset of features & S [p] with the same maximum absolute correlation, assigned fixed sign pattern 1-1,+1118 see Definition 2 is fixed, then the ElasticNet coefficients may be characterized (Lemma) c. and the loss is a fixed rational poly- nomial piece function of the parameters '1, A2. We then show the existence of a set of boundary func- tion curves G, such that any region of the parameter space located on a fixed side of all the curves (more formally, for fixed sign pattern in Definition[] in G has the same signed equicorrelation set. The bound- ary functions are a collection of possible curves at which a covariate may enter or leave the set È and correspond to algebraic curves. We make repeated use of the following lemma which provides useful properties of the piece functions as well the the boundary functions of the dual class loss functions. Lemma 2.1. Let A be an T x matrix. Consider the matrix B(A) (AT A + Alg) and À > 0.
Po 20)
À
f
Fi 2h Ag)
9.1A2)
Figure I: An illustration of the piecewise struc- ture of the ElasticNet loss, as function of the regularization parameters, for fixed prob- lem instance. Pieces are regions where some bounded degree polynomials (71, r2) have a fixed sign pattern (one of +1, =1), and in each piece the loss is fixed (rational) function.
1. Each entry of (()) is rational polynomial (r)(A)/Q(AA)or for i.j E [s] with each Psş of degree at most - 1, and Q of degree s.
2. Further, for i = j. Pss has degree - 1 and leading coefficient 1, and for i i j Psg has degree most 2. Also, Q(A) has leading coefficient
The proof is straightforward (Appendix C.. We will now formally state and prove our key structural result which is needed to establish our generalization and online regret guarantees in Section D
Theorem 2.2. Let be a set of functions {l> Im.p + R>0 A E R+ x R>o} that map a regression problem instance P E 1mm.p to the validation loss (X, of ElasticNet trained with regularization parameter X = (A1,>o) The dual class L is "F.9.p3' ppieeeeeee decomposable, with F Ugg + }b} consisting of rutional polynomial functions fa :1 + 92(A2)
(2(2,)2)) where
q1 Q2 have degrees at most 2p, and G = (gr L + 13} consisting of semi-algebraic set bounded by algebraic curves gr : uu H(((},, 22) < 0}, where is polynomial of degree in X and at most p in X2.
Proof. Let P = (X, y, X val Vval) Im, be regression problem instance. By using the standard reduction to LASSO 47 and well-known characterization of the LASSO solution in terms of equicor-
relation sets, we can characterize the solution BA./EN of the Elastic Net as follows (Lemma C.1
fr. = Xx + A2T - XX' - XXx + X2T
for some & E (p) and E 1JP, Thus for any x = (i1, A2), the prediction á any validation example with features x E RP satisfies (for some E, E 2ipl x 139)
ú = x.AJJE = xxxx X +
X xx + \24
'ee Definition 7 for definitions of standard terminology from algebraic geometry.
5

---

For any subset R S R², if the signed equicorrelation set (E,s) is fixed over R, then the above observation, together with Lemma C.2 implies that the loss function fFN P) is rational function (n(A where Qi is a bivariate polynomial with degree at most 2/E| and q2 is univariate of the form 92(A2) with degree 2/87-
To show the piecewise structure, we need to demonstrate a set boundary functions 9 = (gi...... Is. such that for any sign pattern {0, 1},, the signed equicorrelation set (E, s) for the region with sign pattern b is fixed. To this end, based on the observation above, we will consider the conditions (on A) under which covariate may enter or leave the equicorrelation set. We will show that this can happen only at one of a finite number of algebraic curves (with bounded degrees).
Condition for joining E. Fix &.s. 8. Also fix & &. If covariate j enters the equicorrelation set, the KKT conditions (Lemma B.1 applied to the LASSO problem corresponding to the ElasticNet (Lemma imply
(xt)) Xg((e o2>1)) =\i,
X
where C1 (Xg" xx) y¹ = (X x X
=VI== VI+ta (v2el)) 1²-
0 and
b V1+A2"
Rearranging, and simplifying, we get
xi X; x -x (
(x7) Xx X3) -
A 2 Xx Xx + )24(8) ) -Xx"" T y x57
2tj xx X + X21 (1)_ 1s 1
u35500 Note that the terms (x)) = Xg, (Xg) =x- y. and (xz))² "=) do not depend on
X2y. X or X2 (the Ag terms are zeroed out since j & E). Moreover, (Xg" T x;)= (Xe" X + )g(
Using Lemma C.2, we get algebraic curve (11, x2) = 0 with degree in a and [ε] in Xa corresponding to addition of j & & given E, s.
Condition for leaving E. Now consider a fixed j' E E, given fixed E, The coefficient of j' will be zero for >i = (e))g which simplifies A1((XE" Xx + )241)) s)2 ((gg"x
[ea]y.'
T Xg + x21 v)y- Again by Lemma C.2 we get an algebraic curve g,,1, A2)= = 0 with degree 1 in A and at most | in A2 corresponding to removal of j' E given E,
Putting the two together, we get E (²) ((p ()- i) p3" algebraic curves of degree I in d and at most in X2, across which the signed equicorrelation set may change. These curves characterize the complete set of points (A1,A2 at which (E, s) may possibly change. Thus by setting these p3" curves as the set of boundary functions g, E, S is guaranteed to be fixed for each sign pattern, and the corresponding loss takes the rational function form shown above.
The exact same piecewise structure can be established for the dual function classes for loss functions (EN (A, and ιBio (X.-). This is evident from the proof of Theorem 2.2 since any dual piece has fixed equicorrelation set, and therefore ||8]|o is fixed. Given this piecewise structure, a challenge to learning values of À that minimize the loss function is that the function may not be differentiable (or may even be discontinuous, for the information criteria based losses) at the piece boundaries, making well-known gradient-basee based (local) optimization techniques inapplicable here. In the following (specifically Algorithm D we will show that techniques from data-driven design may be used to overcome this optimization challenge.
3 Learning to Regularize the ElasticNet
We will consider the problem of learning provably good ElasticNet parameters for a given problem domain, from multiple datasets (problem instances) either available as a collection (Section 3. or arriving online (Section 3.2). Our parameter tuning techniques also apply to simpler regression techniques typically used for variable selection, like LARS and LASSO, which are reasonable choices if the features are not multicollinear. Proof details for this section are located in Appendix

---

3.1 Distributional Sefting
Our main result in this section is the following upper bound on the pseudo- dimension of the classes of loss functions for the ElasticNet, which implies that in our distributional setting it is possible to learn near-optimal values of À with polynomially many problem instances.
Theorem 3.1. PDIM(HEN) = Opp².. Further, (HI = Opp²) and PDIM BIC) = O(p²).
Proof Sketch. We use the (F. 1.9..3" ) -piecewise decomposable structure for the dual class function
HEN established in Theorem 2.2 We can bound the pseudo-dimension of the dual class of piece functions F= (a class of bivariate rational functions) by Ollog p) by giving an upper bound (of d()) on the number of sign patterns over 2² induced by k algebraic curves of degree most d. We can also bound the VC dimension of the dual class of boundary functions g in two variates) by Op)) using standard linearization argument. Finally, a powerful result from [[Q] (Theorem C.3) allows us to bound the pscudodimension of H. by combining the above results.
sets
A key challenge to establish the theorem is providing new bounds on the pseudo-dimension of rational functions of bounded degrees (Lemma C55
The upper bound above implies guarantee on the sample complexity of learning the ElasticNet tuning parameter, using standard Searning-hhoores results [ In our setting of learning from multiple problem instances, each sample dataset instance, so the sample complexity is simply the number of regression problem instances needed to learn the tuning parameters to any given approximation and confidence level.
Theorem 3.2 (Sample complexity of tuning the ElasticNet). Let D be an arbitary distribution over the problem space 1mm.p. There is an algorithm which given n O ( (p² log _ + log 4)) problem samples drawn from for any E > 0 and ô E (0, 1), outputs a regularization parameter for the ElasticNet such that with probability at least 1 over the draw of the problem samples, we have that
SIPDDLENN (A, P)] - min Epnn
Se
into well-known generalization guarantee for function classes with bounded pseudo-dimensions (Theorem A.
Proof. This follows from substituting our result in Theorem 3.1
Discussion and applications. Computing the parameters which minimize the loss on the problem samples (aka Empirical Risk Minimization, or ERM) achieves the sample complexity bound in Theorem 3.2 Even though we only need polynomially many samples to guarantee the selection of nearly-optimal parameters, it is not clear how to implement the ERM efficiently. Note that we do not assume the set of features is the same across problem instances, so our approach can handle feature reset i.c. different problem instances can differ in not only the number of examples but also the number of features. Moreover, as a special case application, we consider the commonly used techniques of leave-one-out cross validation (LOOCV) and Monte Carlo cross validation (repeated random test-validation splits, typically independent and in a fixed proportion). Given a dataset of size mer. LOOCV would require mir regression fits which can be inefficient for large dataset size. Alternately, we can consider draws from a distribution D 1.o0 which generates problem instances P from fixed dataset (X,y)= E Rm++xp Rm=+1 by uniformly selecting j E [m mn++1 1] and setting P (X-j+: V-J, Xj. ), Theorem 3.2 now implies that Ö(p² /e²) iterations are enough to determine an ElasticNet parameter with loss within e (w.h.p.) of the parameter X obtained from running the full LOOCV. Similarly, we can define distribution D DMC capture the Monte Carlo cross validation procedure and determine the number of iterations sufficient to get an c-approximation of the loss corresponding parameter selection with arbitrarily large number of runs of the procedure. Thus, in a very precise sense, our results answer the question of how much cross-validation is enough to effectively implement the above techniques.
Remark 1. While our result implies polynomial sample complexity, the question of learning the provably near-optimal parameter efficiently (even in output polynomial time) is left open. For the special cases of LASSO (>2 = 0) and Ridge (>1 =1-=0) 0), the piece boundaries of the piecewise polynomial dual class function may be computed efficiently (using the LARS-LASSO algorithm of (22) for LASSO, and solving linear systems and locating roots of polynomials for Ridge). This applies to online and classification settings in the following sections well.
7

---

3.2 Online Learning
We will now extend our results to learning the regularization coefficients given an online sequence of regression problems, such as when one needs to solve a new regression problem each day. Unlike the distributional setting above, we will not assume any problem distribution and our results will hold for an adversarial sequence of problem instances. We will need very mild assumptions on the data, namely boundedness of feature and prediction values and 'smoothness' of predictions (formally stated as Assumptions and 2 while our distributional results above hold for worst-case problem datasets. Our first assumption is that all feature values and predictions are bounded, for training as well as validation examples.
Assumption 1 (Boundedness). The predicted variable and all feature values are bounded by an absolute constant R, i.e. max[||x(0 loo,,0 [ly() loo
||xx (8) vol
loo (9) bl I R.
We will need the following definition of distribution smoothness to state our second assumption.
Definition 3. A continuous probability distribution is said to be re-ounded if the probability density function p(z) satisfies p(z) S K. k.for any x in the sample space.
For example, the normal distribution ((u, o²) with mean μr and standard deviation or is 0/22 bounded. We assume that the predicted variable y in the training set comes from k-bbunded (i.e. smooth) distribution, which does not require the strong tail decay of sub-Gaussian distributions 44 Moreover, the online adversary is allowed to change the distribution as long it is к- bounded. Note that our assumption also captures common data preprocessing steps, for example the jitter parameter in the popular Python library scikit-learn [y adds uniform noise to the values to help model stability. The assumption is formally stated as follows:
Assumption 2 (Smooth predictions). The predicted variables y in the training set are drawn from a joint k-bounded distribution, i.e. for each the variables y have a joint distribution with probability density bounded by K.
Under these assumptions, we can show that it is possible to learn the ElasticNet parameters with sublinear expected regret when the problem instances arrive online. The learning algorithm (Algo- rithm that achieves this regret is a continuous variant of the classic Exponential Weights algorithm [4 It samples points in the domain with probability inversely propotional the exponentiated loss. To formally state our result, we will need the following definition of dispersed loss functions. Informally speaking, it captures how amenable a set of non-Lipschitz functions is to online learning by measuring the worst rate of occurrence of non-Lipschitzness (or discontinuities) between any pair of points in the domain.
M show that dispersion is necessary and sufficient for learning piecewise Lipschitz functions.
Definition 4. Dispersion [ The sequence of random loss functions l1...., bT is 3-dispersed for
the Lipschitz constant L if. for all I'' and all e 2 9-, we have that, in expectation, at most Ö(ET) functions (the soft-O notation suppresses dependence on quantities beside e, T' and B. as well as logarithmic terms) are not L-Lipschitz,fr for any pair of points at distance e in the domain C. That is. for
all T and for all T-8,1 E max
Ktt [T] (e(p) - (400) > L /'|123]] Ö(ET).
p.p'EC
||o-o'll,
Our key contribution is to show that the loss sequence is dispersed (Definition 4 under the above assumptions. This involves establishing additional structure for the problem, specifically about the location of boundary functions in the piecewise structure from Theorem 2.2 This stronger character- ization coupled with results from [ on dispersion of algebraic discontinuities completes the proof.
Theorem 3.3. Suppose Assumptions and 2 hold. Let I1....,IT (0, ) + Rz0 denote an independent sequence of losses (e.g. fresh randomness is used to generate the validation set features each round) as a function of the ElasticNet regularization parameter X = (21;)2)
4(A)= -.(0 o (x(() Voul) ). The sequence of functions is ddispersed, and there is an online algorithm with Ō DTV expected regret. The result also holds for loss functions adjusted by
information criteria AIC and BIC.
Proof Sketch. We start with the (F, G, (.p...p3Pppppe -iccceiie decomposable structure for the dual class Observe that the rational piece functions in F do not introduce
function Hip from Theorem 2.2
'The Ō(-) notation hides dependence on logarithmic terms, well as quantities other than T'.
8

---

Algorithm Data-driven Regularization (④)
1: Input: Problems (X . and regularization penalty function f.
2: Hyperparameter: step size parameter E (0,
3: Output: Parameters (At) E C.C.C. I (LASSO/Ridge) or C RR+ (BlasticNet).
4: Set wh (A) 1 for all À E C.
5: for = 1,2..... .......Tu. do
6: W; == Jc (A)dX.
7: Sample À with probability Pa(A)= = (A)(A) W. output as X
8: Compute average loss function (AA) byo (Bx.5 (x((1) ,)))))
9: For each À E C, update weights (4+1(A) = (c(l-t((0)
any new discontinuities since the denominator polynomials do not have positive roots. For each of two types of boundary functions in & (corresponding leaving/entering the equicorrelation set) we show that the discontinuities between any pair of points A, X' lie along the roots of polynomials with non-leading coefficients bounded and smoothly distributed (bounded joint density). This allows to use results from 3 to establish dispersion, and therefore online learnability.
We remark that the above result holds for arbitrary training features and validation sets in the problem sequence that satisfy our assumptions, in particular the loss functions are only assumed to be independent but not identically distributed. In contrast, the results in the previous section needed them to be drawn from the same distribution. Also the parameters need to be selected online, and cannot be changed for already seen instances. This setting captures interesting practical settings where the set of features (including feature dimensions) and the relevant training set (including training size) may change over the online sequence. It is not clear how usual model selection techniques like cross-validation may be adapted to these challenging settings.
4 Extension to Regularized Least Squares Classification
Regression techniques can also be used to train binary classifiers by using an appropriate threshold on top of the regression estimate. Intuitively, regression learns linear mapping which projects the datapoints onto a one-dimensional space, i.e. a real number, after which threshold may be applied to classify the points. The use of thresholds make discrete classifications adds discontinuities to the empirical loss function. Thus, in general, the classification setting is more challenging as already includes the piecewise structure the regression loss. We provide statistical and online learning guarantees for Ridge and LASSO. For the ElasticNet we present the extensions needed to the arguments from the previous sections obtain results in the classification setting.
More formally, will restrict y to (0, 1) 1)m The estimator 2x. is obtained before, and the prediction on a test instance x may be obtained by taking the sign of a thresholded regression estimate, sign( (ar, 3x.y) - T), where sign IR + {0, maps E R to I(x 2 0} and 7 E R is the threshold. The threshold 5 corresponds to the intercept or bias of the learned linear classifier, here we will treat it as tunable hyperparameter (in addition to Y1 Ao F The average 0-1 loss over the
dataset (X, y) is given by (, ,, (X, 7), >m lya this section are in Appendix
m
3x,) r) Proofs from
4.1 Distributional setting
The problem setting is the same in Section 3.1 except that the labels y are binary and threshold for prediction. We bound the pseudo-dimension for classification loss on these problem instances, which as before (c.f. Theorems 3.1 and 5 samples are sufficient to generalize well over the problem distribution D. For Ridge and LASSO we
imply that polynomially many problem
'e still have problem instance specific bias in 3 using the standard trick of adding unit feature X. thus we generalize the common practice of using a fixed threshold. For example, the RidgeClassifier implementation Python library scikit-learn 1.1.1 37 assumes y E { {-1, +1)" and sets 7 =
"Squared loss and 0-1 loss identical in this setting.

---

upper bound the number of discontinuities of the piecewise constant classification loss by determining the values of where any prediction changes.
Theorem 4.1. Let Hiidze HiLASso and H'y denote the set of loss functions for classification problems with at most mn examples and p features, for linear classifiers regularized using Ridge, LASSO and ElasticNet regression respectively.
(i) PDIM Ridge) = (log mp)
(ii) (DIM(HiAsSO)) Opp log m). Further, the overparameterized regime (p >> m), we have that PDIM LASSO) = O( log p.)
(ii) (HIM(HEN) O(p² 2 log m))
The key difference with the bound for the regression loss in Theorem 3.1 is the additional (p log m) term which corresponds to discontinuities induced by the thresholding in the regression based classifiers. We can establish a structure similar Theorem 2.2 in this case (Lemma D.I)
4.2 Online setting
As in Section 3.2 we can define an online learning setting for classification. Note that the smoothness of the predicted variable not meaningful here, since y is binary vector. Instead we will assume that the validation examples have smooth feature values. Intuitively this means that small perturbations to the feature values does not meaningfully change the problem.
Assumption 3 (Smooth validation features). The feature values (0) )5k in the validation examples are drawn from a joint rs-ounded distribution.
Under the assumption, we show that we can learn the regularization parameters online, for each of Ridge, LASSO and ElastieNet estimators. The proofs straightforward extensions of the structural results developed in the previous sections, with minor technical changes to use the above validation set feature smoothness instead of Assumption 2 and are deferred the appendix.
Theorem 4.2. Suppose Assumptions and 3 hold. Let bl. (0, H x [-H, H + R denote an independent sequence of losses as a function of the regularization parameter X, (,,,, = te(3x, (x(), .)))))))))))))))))))) T). sequence of functions is 1/2 dispersed and there is an online algorithu with Ö(VT) expected regret.
))) If f is given by fi (LASSO). fa (Ridge), or FEN (ElasticNet) then the
5 Conclusions and Future Work
We obtain novel structural result for the ElasticNet loss as a function of the tuning parameters. Our characterization gives polynomial upper bounds for the sample complexity of learning the parameters from multiple instances coming from the same problem domain. For the ElasticNet we show generalization and online regret guarantees, but efficient implementation of the algorithms an interesting question for further work. Also we show general learning-theowe without any significant restrictions on the data-ge generating distribution, in learning from multiple problems. The problems may be drawn i.i.d. from an arbitrary problem distribution, or even arrive in an online sequence but with some smoothness properties. It is unclear if such guarantees may be given for tuning parameters for the more standard setting of tuning a single training set. this work we only give upper bounds on the sample complexity by bounding the pseudodimension, showing lower bounds an interesting direction for future work.
guarantees, i.e.
Acknowledgments
We thank Ryan Tibshirani for helpful discussions. This material is based on work supported by the National Science Foundation under grants CCF-1910321, 1755121, IIS- 1838017, 19S1190443, IIS-2046613, IIS-2112471, and SES-1919453; the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003; a Simons Investigator Award; an AWS Machine Learning Research Award; an Amazon Research Award; a Bloomberg Research Grant; a Microsoft Research Faculty Fellowship: funding from Meta, Morgan Stanley, and Amazon; and Facebook PhD Fellowship. Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies.
10

---

References
[1] Hirotugu Akaike. new look at the statistical model identification. IEEE transactions on automatic control, 19(6):716-722 1974.
[2] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. volume 9. cambridge university press Cambridge, 1999.
[3] Maria-Florina Balcan. Book chapter Data-Driven Algorithm Design, In Beyond Worst Case Analysis of Algorishms, T. Roughgarden (Ed). Cambridge University Press, 2020.
[4] Maria-Florina Balcan and Dravyansh Sharma. Data driven semi-supervised learning. Advances in Neural Information Processing Systems, 34, 2021.
[5] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of automated mechanism design. Advances in Neural Information Processing Systems, 29, 2016.
[6] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 JEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pages 603-614. IEEE, 2018.
[7] Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. International Conference on Learning Representations, 2019.
[8] Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed setting. In Conference on Uncertainty in Artificial Intelligence, pages 909-918. PMLR, 2020.
[9] Maria-Florins Balcan, Travis Dick, and Dravyansh Sharma. Learning piecewise Lipschitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics, pages 3567-3577. PMLR, 2020.
[10] Maria-Florine Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high- seghheerformin algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 919-932, 2021.
[11] Maria-Florine Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34, 2021.
[12] Maria-Florina F Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar, Learning- to-learn non-convex piecewise- -ireoeeewss--lsshhizz functions. Advances in Neural Information Processing Systems, 34: 5056-15069, 2021.
[13] Emmanuel J Candès and Yaniv Plan. Near-ideal model selection by 11 minimization. The Annals of Statisties, 2755))2145-2177, 2009.
[14] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[15] JM Chambers and TJ Hastie. Linear models. Chapter of statistical models S. Wadsworth & Brooks/Cole, 1992, 1992.
[16] Denis Chetverikov, Zhipeng Liao. and Victor Chernozhukov. On cross-validated lasso in high dimensions. The Annals of Statistics, 49(3): 1300-1130-1117, 2021.
[17] Michael Chichignoud, Johannes Lederer, and Martin J Wainwright. A practical scheme and fast algorithm Research, 17(1)8112-88) 2016.
the lasso with optimality guarantees. The Journal of Machine Learning
[18] Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions on electronic computers, (3):326334, 1965.

---

[19] Amit Dhurandhar and Marek Petrik. Efficient and accurate methods for updating generalized linear models with multiple feature additions. The Journal of Machine Learning Research, 15 (1):2607-2627, 2014.
[20] Edgar Dobriban and Stefan Wager. High-dimensional asymptoties of prediction: Ridge regres- sion and classification. The Annals of Statistics, 46(1):247-277 2018.
[21] Richard M Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290-330, 1967.
[22] Bradley Efron, Trevor Hastie, Jain Johnstone, and Robert Tibshirani. Least angle regression. The Annals of statistics, 32(2):407-44) 499, 2004.
[23] Jianqing Fan and Jinchi Lv. A selective overview of variable selection in high dimensional feature space. Statistica Sinica, 20(1):101, 2010.
[24] Manuel Drrmänddz-Delgado, Manisha Sanjay Sirsat, Eva Cernadas, Sadi Alawadi, Senén Barro, and Manuel Febrero-Band Bande. An extensive experimental survey regression methods. Neural Networks, 111:11 11:11 2019.
[25] Jean-Jacques Fuchs. Recovery of exact sparse representations in the presence of bounded noise. IEEE Transactions on Information Theory, (110):3601-3600 2005.
[26] Diane Galarneau Gibbons. A simulation study of some ridge estimators. Journal the American Statistical Association, 76(373):131-139, 1981.
[27] Rishi Gupta and Tim Roughgarden. A pac approach to application-specifi algorithm selection. SIAM Journal on Computing, 46(3))992 (113):9921117,,,, 2017.
[28] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[29] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986, 2022.
[30] Arthur E Hoerl and Robert W Kennard, Ridge regression: applications to nonorthogonal problems. Technometrics, 12(1):69-82 82, 1970.
[31] Lisa-Ann Kirkland, Frans Kanfer, and Sollie Millard. LASSO tuning parameter selection. In Annual Proceedings of the South African Statistical Association Conference, volume 2015, pages 49-56. South African Statistical Association (SASA), 2015.
[32] Johannes Lederer and Christian Müller Don't fall for tuning parameters: tuning-free variable selection in high dimensions with the TREX. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
[33] Qing Li and Nan Lin. The bayesian elastic net. Bayesian analysis, 5(L):151-170, 2010.
[34] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012.
[35] Kevin P Murphy, Machine learning: probabilistic perspective. MIT press, 2012.
[36] Pratik Patil, Yuting Wei, Alessandro Rinaldo, and Ryan Tibshirani. Uniform consistency of coossvvlidationn estimators for high-dimensional ridge regression. In International Conference on Artificial Intelligence and Statistics, pages 3178-3186, PMLR, 2021.
[37] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer. R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-leam: Machine Learning Python. Journal of Machine Learning Research, 12:2825-2830, 201
[38] David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
12

---

[39] Gideon Schwarz. Estimating the dimension of a model. The annals of statistics, pages 461-464, 1978.
[40] Igor Rostislavich Shafarevich. Basic Algebraic Geomerry:(by) IR Shafarevich Transl. from the Russian by KA Hirsch. Seringer-Verlage 1977.
[41] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-28) 1996.
[42] Ryan J Tibshirani. The lasso problem and uniqueness. Electronic Journal of statistics, 7: 1456-1490, 2013.
[43] Andrey N Tikonov and Vasily Arsenin. Solutions of ill-posed problems. New York: Winston, 1977.
[44] Tong Zhang- Some sharp performance bounds for least squares regression with regularization. The Annals of Statistics,
2009.
[45] Yu Zhang and Qiang Yang. A survey multi-task learning. IEEE Transactions Knowledge and Data Engineering, 2021.
[46] Peng Zhao and Bin Yu. Stagewise lasso. The Journal of Machine Learning Research, 8: 2701-2726, 2007.
[47] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the royal statistical society: series B (statistical methodology), 67(2):301-322 2005.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We emphasize we are in multiple
instance setting instead the standard setting.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "iWIuUZ0bj56", "reviewer": "Reviewer_yYWW", "summary": "This paper studies the validation loss of the elastic net as a function of its two hyperparameters, $\\lambda_1, \\lambda_2$. The authors allow \"validation loss\" to be fairly general: it is a function that maps a dataset and a setting of $(\\lambda_1, \\lambda_2)$ to the validation loss of the elastic net. They characterize this function as a piecewise rational polynomial as a function of $(\\lambda_1, \\lambda_2)$. They use this characterization to show that, given a set of validation losses and a distribution over this set (e.g. in leave-one-out cross-validation, the validation losses are the leave-one-out losses with the uniform distribution), a possibly small number of draws from this distribution are needed to minimize the average validation loss within $\\epsilon$ accuracy. The authors go on to show that validation losses can be minimized in an online setting, where we view each validation loss one-by-one. Finally, the authors prove similar results for binary classification, where classification is done by thresholding the predictions of the elastic net.", "questions": "- Can the authors provide a proof for the statement \"using simple algebra, the denominator...\"? \n\nI also have a few questions relating to the meaning of the author's results.\n- Is the algorithm in Theorem 3.3 just Algorithm 1? It's probably worth stating this if so. As-is, Algorithm 1 isn't really discussed in the paper.\n- One of the claims of Theorem 3.3 is about the $\\beta$-dispersion of a series of functions. Why is this something readers should care about (i.e. why have the authors put this in the theorem's statement)?\n- On lines 235-237, the authors state that they have solved the problem of optimizing the complex validation loss as a function of $(\\lambda_1, \\lambda_2)$. Which of their results back up this statement? It seems like Theorem 3.2 is about the number of validation samples required, and Theorem 3.3 has error growing with the square root of the number of samples.\n- The authors state that their \"assumption of smoothness [on $y$] is much weaker than sub-Gaussian noise assumptions in the literature.\" But this smoothness assumption is paired with assuming $y$ is a bounded random variable; isn't this much weaker than sub-Gaussianity, as boundedness implies sub-Gaussianity? \n- What exactly does it mean in Theorem 3.3 that $l_1, \\dots, l_T$ are \"independent\"? Are we assuming the existence of some distribution $\\mathcal{D}$ over losses, and $l_t$ are sampled i.i.d. from $\\mathcal{D}$? This should be stated more precisely.", "limitations": "I think the authors have addressed the limitations of their work, with the exception of a few of the points already discussed above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\nI think the technical contributions of this paper are pretty strong and original. As far as I know, no one has given this exact a characterization of the loss landscape of things similar to cross-validation for the elastic net. I can see some interesting future work building off of this paper -- e.g. what do the individual pieces of the loss look like? The author's observation about how much subsampling of leave-one-out CV is needed to get an accurate approximation is interesting as well. I actually think this is one of the most immediately practical pieces of advice from this paper, and might warrant a little more highlighting (e.g. as a corollary). I can't really comment on the strengths of their results about online learning, as I'm not as familiar with that literature (in particular, $\\sqrt{T}$ expected regret for $T$ problems sounds like a lot, but maybe this is near the best you can do?).\n\n**Weaknesses**\nI think there are two main directions for improvement of the paper. First, I think the authors have slightly oversold the weakness of their assumptions, and should tone down those claims a little bit. Second, the writing was pretty dense and could use some more discussion and careful definitions.\n\nOn the assumptions required for the authors' results:\n- The abstract states that the results do not require \"strong assumptions on the data distribution\". Assumption 1 (that the covariates and responses are all bounded) is definitely not a weak assumption. I think it wouldn't be unfair to say this is a \"strong\" assumption, as this disallows, say, a well-specified model in which responses are linear functions of the covariates with Gaussian noise.\n- The results are stated as being completely independent of data distribution (e.g. in \"Theorem 1.1 (Informal)\"). However, a number of the lemmas used (Lemmas B.2, B.3, and C.1) require the columns of the data matrix $X$ to be in general position. First, this condition should be stated in the results using these lemmas (e.g. in the statement of Lemma 2.1). Second, it should be clarified in exposition that the paper's results only apply to sets of problems / distributions over problems with covariate matrices with columns in general position. \n\n\nOn the writing being dense: The paper is pretty technical and uses a number of concepts from algebraic geometry and learning theory. These concepts are sometimes unexplained (e.g. just a definition is given) or lack a definition altogether. I think the results in this paper could be of interest beyond the learning theory community or algebraic statistics community, and so these concepts should be better explained (I think this is especially true of the concepts from algebraic geometry, which I suspect very few NeurIPS readers / attendees have experience with). Here are the things that stood out to me:\n- Piecewise structured functions could use a simple English description.\n- Pseudo-dimension should be defined and briefly explained. The abbreviation PDIM should also be explicitly defined.\n- Semi-algebraic sets and algebraic curves should be defined.\n- A precise statement of Bezout's theorem should be given in the form that is applied here (or, at least, a reference).\n- I thought the definition and explanation of $\\beta$-dispersion was really clear and helpful. \n\n**Miscellaneous things**\n- I think Lemma C.2 needs some conditions to ensure $A^T A + \\lambda I$ is invertible (what if $A$ is low rank? what if $\\lambda = -5345$?)\n- Line 215: \"based on the observation above\" there are many observations preceding this statement; it's not immediately clear which one this refers to.\n- What are the asterisks in the proof of Lemma 2.1 (around line 218)? Are these just typos? An asterisk appears on $\\lambda_1$ around line 223 as well, and then disappears in the next equation.\n- \"Using simple algebra, the denominator...\" Definitely $\\mathcal{E}$ depends on $\\lambda_1$ and $\\lambda_2$, and it's not immediately clear to me why that dependence gets canceled out in this expression. I think a proof should be given here.\n- Algorithm 1 is actually never discussed in the paper. I'm guessing it's the algorithm from Theorem 3.3, but this should really be made clear (and discussed).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i9JyBS-qIJ", "reviewer": "Reviewer_zfht", "summary": "The authors introduce a theoretical result that bounds the number of problems\nneeded to obtain a particular accuracy of $\\lambda_1$ and $\\lambda_2$ in\nhyper-parameter optimization for the elastic net for both offline and online\nlearning.", "questions": "- ~The authors in [1] state that the regularization path has at worst $(3^p +\n  1)/2$ segments. But you say, if I am understanding correctly, that it is\n  exactly $3^p$ (l. 587). Perhaps I am missing something, but why is your result\n  different? Should there be an O there?~\n- ~Why is there only a proof sketch and not a full proof for theorem 3.1?~\n- If I understand correctly, you arrive at your bound on the number of problems\n  needed by assuming the worst-case situation in terms of path complexity. What\n  is the impact of this on the tightness of the bound (and practical\n  usefulness)? I would assume that this would make the bound conservative (since\n  in practice no paths for real data contain $3^p$ segments).", "limitations": "- Consider demonstrating with a simple example what your results imply in terms\n  of the number of problems you need to solve for some real data set. Also show\n  via some simple experiment that standard approaches (such as 10-fold CV) can\n  fail (as you claim they do) and that your method solves this problem.\n- Move section 4 to the appendix since ordinary lasso classification is not a\n  standard or useful model.\n- ~State clearly what your contributions are in relation to previous work such as\n  [1, 2, 3, 4] and cite their work where appropriate. In particular there\n  seems to be overlap with [1] that isn't accounted for in the work.~\n- ~Consider amending the literature section in the paper by including some or\n  all of [1, 2, 3], and [4] regarding homotopy methods for the lasso.~\n- Include at the very least [5] in your literature section on hyper-parameter\n  tuning for the lasso.\n- It is not standard to call the Elastic Net (or elastic net) ElasticNet.\n  Consider adding a space.\n- l. 58. There should be a period at the end of the sentence.\n- l. 77. w.h.p. is not a standard abbreviation. Consider spelling it out.\n- l. 208. There should be a period at the end of the equation.\n- l. 271. There should be a period after $\\epsilon$.\n- l. 386. There is an extra space after \"values\".\n\n[2] P. Garrigues and L. Ghaoui, “An homotopy algorithm for the lasso with online\n    observations,” in Advances in neural information processing systems 21,\n    Vancouver, Canada, Dec. 2008, vol. 21, pp. 489–496. [Online]. Available:\n    https://proceedings.neurips.cc/paper/2008/file/38af86134b65d0f10fe33d30dd76442e-Paper.pdf\n\n[3] D. M. Malioutov, M. Cetin, and A. S. Willsky, “Homotopy continuation for\n    sparse signal representation,” in Proceedings. (ICASSP ’05). IEEE\n    International Conference on Acoustics, Speech, and Signal Processing, 2005,\n    Philadelphia, USA, Mar. 2005, vol. 5, pp. v733–v736. doi:\n    10.1109/ICASSP.2005.1416408.\n\n[4] M. Osborne, B. Presnell, and B. Turlach, “A new approach to variable\n    selection in least squares problems,” IMA Journal of Numerical Analysis,\n    vol. 20, no. 3, pp. 389–403, Jul. 2000, doi: 10.1093/imanum/20.3.389.\n\n[5] Q. Bertrand, Q. Klopfenstein, M. Blondel, S. Vaiter, A. Gramfort, and J.\n    Salmon, “Implicit differentiation of Lasso-type models for hyperparameter\n    optimization,” in Proceedings of the 37th International Conference on\n    Machine Learning, Nov. 2020, pp. 810–821. Accessed: Jun. 27, 2022. [Online].\n    Available: https://proceedings.mlr.press/v119/bertrand20a.html", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper seems to be theoretically sound and follows a logical progression.\n- The literature section on exact (homotopy) methods for the elastic net and\n  lasso is lacking and only insofar as I can see included the LARS paper at the\n  moment.\n- ~Section 2.1 and Lemma 2.1 seem to me to be related to the work in [1] and it is not quite clear what\n  the novelty and enhancements of the current work are.~\n- The bound on the number of problems needed for a certain accuracy in\n  estimating $\\lambda_1$ and $\\lambda_2$ would be a useful addition, although it\n  is not clear that the bound is useful in practice.\n- Section 4 does not seem to address a useful problem. Classification with the\n  ordinary (least-squares) elastic net is not a standard (or indeed useful) approach\n  to classification as compared to elastic net-regularized logistic regression.\n\n[1]: J. Mairal and B. Yu, “Complexity analysis of the lasso regularization path,”\n    in Proceedings of the 29th International Conference on Machine Learning,\n    Edinburgh, United Kingdom, Jun. 2012, pp. 1835–1842. [Online]. Available:\n    https://icml.cc/2012/papers/202.pdf", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DZ3cR_AGsLq", "reviewer": "Reviewer_MWke", "summary": "This submission derives new generalization bounds for tuning the regularization parameters for ridge-regression, LASSO, and the elastic net methods. \nIn particular, the authors study two settings: (i) tuning based on multiple draws of train/test splits from a fixed (but arbitrary) problem distribution and (ii) online learning, where new train/test splits are provided as problem instances at each time step.\nIn the former setting, the authors show $\\tilde O(p^3/\\\\epsilon^2)$ problem samples are required to come within $\\\\epsilon$ of the best (expected) loss.\nIn the latter setting, the authors impose a smoothness assumptions on the adversary in order to provide a continuous version of the multiplicative weights algorithm with sub-linear regret. \nBoth results rely on a novel characterization of the tuning objective as a piecewise rational function with boundaries given by polynomial curves.\nThe submission concludes with extensions to linear classification problems with a fixed decision threshold and squared loss.", "questions": "- Theorem 3.2/Theorem A.1: Is this result constructive or does it only give the existence of an algorithm?\n    For instance, I agree with the claim that \"our results answer the question ‘how much 288 cross-validation is enough’ to effectively implement the above techniques\", but this is separate from carrying out the optimization procedure in practice. \n\n- Algorithm 1: The optimization domain $C$ appears to be an uncountable set, in which case the density function $w_i$ defines an improper distribution (at least initially) and maybe highly discontinuous during execution of the algorithm. \n    As a result, Algorithm 1 appears to be unimplementable --- is this correct?\n\n- Are there any lower bounds for the sample complexity of learning $\\lambda$ in the distributional setting (regression of classification)? If so, it would be excellent to compare Theorem 3.2 to these rates. If not, it might be nice to comment on the challenges in developing these bounds. ", "limitations": "The limitations are properly addressed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a highly novel paper which tackles an excellent problem: how to properly tune regularization parameters for common algorithms. \nThe standard approach to tuning ridge regression, LASSO, or the elastic net methods is grid-search. \nHowever, as the authors note in the classification setting, some model choices, like thresholding, can induce discontinuities in the tuning objective and make grid-search unreliable.\nThus, developing better alternatives to grid-search is a important topic. \n\nThe theoretical bounds are novel and cover a range of important settings.\nI was particularly interested to see the online-learning results.\nThe only two potential issues I see with this work are implementability and the focus on problem-sample complexity, rather than example-sample complexity.\nThe apparent non-implementability of the actual methods for tuning the regularization parameters is somewhat disappointing, but not too surprising given the nature of the results.\nAnd, while the authors state that problem-sample complexity is more common, I think the problem sampling (which covers cross-validation) to be far more interesting. \n\n### Writing\n\nThe paper is very well written. \nI found only a few typos (see Minor Issues below).\nI particularly appreciate that the authors take care to give intuition for each theoretical result as well as discuss their implications. \nCongratulations on a very well-written paper.\n\n### Theory\n\n**Soundness**: This paper is outside of my core research area, so I'm not an expert on the theory. However, I briefly looked through the appendices and saw no major issues. \n\n**Implementability**: My understanding from the discussion is that the methods for tuning $\\\\lambda$ are not implementable (see Questions). \nThus, while the paper presents \"efficient algorithms\" (Line 402), efficiency is only in the sense of sample complexity, rather than computational complexity.\nI don't think this is an important issue, but I suggest the authors either comment on the complexity of tuning $\\\\lambda$ in practice, or clarify that they mean efficiency only in terms of samples. \n\n\n### Experiments\n\nN/A\n\n\n### Minor Comments and Typos: \n\n- Line 263: \"rational functions of bounded degrees .\" -- remove extra space before the period.\n- Line 286: \"$\\epsilon$-approximation of the loss corresponding parameter selection with arbitrarily...\"  --- I don't understand this sentence; perhaps a word is missing?\n- Line 369: \"only polynomially many problem samples to generalize well...\" -> \"only polynomially many problem samples are required to generalize well\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept