New Bounds for Hyperparameter Tuning of Regression Problems Across Instances
Authors: Nina Balcan
Anh Tuan Nguyen
Dravyansh Sharma
Venue: NeurIPS 2023 poster (2023)
Keywords: Elastic Net
logistic regression
data-driven algorithm design
learning theory
regularization

Abstract: The task of tuning regularization coefficients in regularized regression models with provable guarantees across problem instances still poses a significant challenge in the literature. This paper investigates the sample complexity of tuning regularization parameters in linear and logistic regressions under $\ell_1$ and $\ell_2$-constraints in the data-driven setting. For the linear regression problem, by more carefully exploiting the structure of the dual function class, we provide a new upper bound for the pseudo-dimension of the validation loss function class, which significantly improves the best-known results on the problem. Remarkably, we also instantiate the first matching lower bound, proving our results are tight. For tuning the regularization parameters of logistic regression, we introduce a new approach to studying the learning guarantee via an approximation of the validation loss function class. We examine the pseudo-dimension of the approximation class and construct a uniform error bound between the validation loss function class and its approximation, which allows us to instantiate the first learning guarantee for the problem of tuning logistic regression regularization coefficients.

New Bounds for Hyperparameter Tuning of Regression Problems Across Instances
Maria-Florina Balean Carnegie Mellon University ninamf cmu. edu
Anh Tuan Nguyen Carnegie Mellon University atnguyendcs. edu
Dravyansh Sharma Carnegie Mellon University dravyans@cs. cmu. edu
Abstract
The task of tuning regularization coefficients in regularized regression models with provable guarantees across problem instances still poses a significant challenge the literature. This paper investigates the sample complexity of tuning regular- ization parameters in linear and logistic regressions under & and ég-constraints in the data-driven setting. For the linear regression problem, by more carefully exploiting the structure of the dual function class, we provide a new upper bound for the pseudo -imunndimnnnonn of the validation loss function class, which significantly improves the best-known results on the problem. Remarkably, we also instantiate the first matching lower bound, proving our results are tight. For tuning the regular- ization parameters of logistic regression, we introduce new approach to studying the learning guarantee via an approximation of the validation loss function class. We examine the pseudo-dimension of the approximation class and construct uni- form error bound between the validation loss function class and its approximation, which allows us to instantiate the first learning guarantee for the problem of tuning logistic regression regularization coefficients.
Introduction
Regularized linear models, including the Elastic Net [1, and Regularized Logistic Regression 4 well as their variants 77 have found widespread use in diverse fields and numerous application domains. Thanks to their simplicity and interpretability. those methods are popular choices for controlling model complexity, improving robustness, and preventing overfitting by selecting relevant features 4 8 9]. Moreover, regularized linear models can be adapted to the non-linear regime using kernel methods [TO significantly expanding their applicability to wide range of problems. In typical applications, one needs to solve not only single regression problem instance, but several related problems from the same domain. Can we learn how regularize with good generalization across the related problem instances?
Suppose have regression dataset (X, y) RMxP > where X is design matrix with m samples and p features, and is a target vector. Regularized linear models aim to compute an estimator 3(X.v) by solving the optimization problem
((X.)) argmin [133, (X,,)) A ||3|| + do [| BE3P
where (A1, E 2R are the regularization coefficients. For instance, E R y Rm, and [(3, (X, v)) = _ ly X (squared-loss function), we get the well-known Elastic Net M. On the other hand, if E {(},, 0), (0, A2)} for λι y (+1)", and 1(8, (X, x))) m E log(1 exp(-eppp y 3)), obtain regularized logistic regression.
Correspondence: atnguyen@cs, cmu edu.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In regularized linear models, the parameters À play crucial role in controlling the sparsity (41) and shrinkage (62) constraints, and are essential in ensuring better generalization and robustness 1 A popular approach in practice is cross-validation which involves choosing a finite grid of values of and iteratively solving the regression problem for multiple values of À and evaluating on held-out validation sets to determine the optimal parameter. Principled techniques with theoretical guarantees suffer from various limitations, for example require strong assumptions about the original problem [3], or aim to search the optimal parameter over discrete subset instead of the whole continuous domain. Moreover, repeatedly solving the regression problem is particularly inefficient if we have multiple problem instances from the same problem domain.
In this work, we investigate an alternative setting for tuning regularization parameters, namely data-driven algorithm design, following the previous line of work by Balcan et al. [14]. Unlike
the traditional approach, which involves considering a single dataset (X, y). in the data-driven
approach, we analyze a collection of datasets or problem instances (X((', (()) x-(1 (9)
Vval drawn
from an underlying problem distribution D. Our objective to determine the optimal regularization parameters À so that when using the training set (X((), y()) and À to select a model in Optimization
problem the selected model minimizes loss on the validation set (xx(a) Ival ). As remarked by Balcan et al. [14, data-driven algorithm design can handle more diverse data generation scenarios in practice, including cross validation and multitask-Iearmn [15 We emphasize that the data-driven setting differs significantly from the standard single dataset setting.
(8)
In this paper, we consider the problem of tuning regularization parameters in regularized logistic regression and the Elastic Net across multiple problem instances. Our contributions are:
We present an improved upper bound (Theorem 3.3) on the pseudo-dimension for tuning the Elastic Net regularization parameters across problem instances by establishing novel structural result for the validation loss function class (Theorem 3.2). We provide crucial refinement to the piecewise structure of this function class established by Balcan et al. [1], by providing bound on the number of distinct functional behaviors across the pieces. This enables us to describe the computation of the validation loss function as GJ algorithm [17]. which yields upper-bound of (p) on the eseudo-dimension, a significant improvement of the prior best bound of O(p²) by Balcan et al. [14), and corresponding improvement in the sample complexity (Theorem 3.4).
Furthermore, establish the tightness of our result by providing the first asymptotically matching lower bound of ?(p) on the pscudo-dimensee (Theorem 3.5). It is worth noting that our results have direct implications for other specialized cases, such as LASSO and Ridge Regression.
We further extend our results on the Elastic Net to regularized kernel linear regression problem (Corollary(3a. (.6).
We propose a novel approach to analyze the problem of tuning regularization parameters in regularized logistic regression, which involves indirectly investigating an approximation of the validation loss function class. Using this approach, we instantiate the first learning guarantee for this problem in the data-driven setting (Theorem 4.4
1.1 Related work
Model selection for regularized linear models. Extensive research has focused on the selection of optimal parameters for regularized linear models, including the Elastic Net and regularized logistic regression. This process usually entails choosing the appropriate regularization coefficients for a given dataset [18] 19] Nevertheless. a substantial proportion of this research relies on heuristic approaches that lack theoretical guarantees (20 21). Others have concentrated on creating tuning objectives that go beyond validation error [22 23 but with no clearly defined procedures for provably optimizing them. The conventional method for selecting a tuning regularization parameter through grid-based selection, which aims to choose the parameter from subset, known grid, within the parameter space. While this approach provides certain guarantees [24]. falls short in delivering an optimal solution across the entire continuous parameter space, particularly when using tuning objectives that exhibit numerous discontinuities. Additionally, the grid- technique is highly sensitive to density, as selecting a grid that is either too dense or too coarse might result in inefficient search or highly inaccrrate solutions. Other guarantees require strong assumptions on the data distribution,
such as sub-Gauee Gabb-aas noise (25] [3] Some studies focus evaluating regularized linear models by

---

Train peoblem instances pr?
Hypee parameerr tuiing aigecilam
(drawn From
pd (i E (1, N))
(x09) y/ X v
(A)csng data (X0%) ynl)
Hypar-parmmen tuning algonthm
1221
Compate voliristion k(P9), A)lor (lyon (X22
Eup
P90
Figure I: The process of tuning regularization parameter À across problem instances. Given set of N problem instances (P(1) ..... P(N) drawn from some problem distribution D, one seeks to choose the best parameter Ả by minimizing the total validation loss Σi= h(P(0; A).
constructing solution paths [26 2 27). However, it is important to note that these approaches are primarily computational nature and do not provide theoretical guarantees.
Data-driven algorithm design. Data-driven algorithms can adapt their internal structure or parame- ters to problem instances from unknown application-specific distributions. It is proved to be effective for a variety of combinatorial problems, such as clustering, integer programming, auction design, and graph-based
semi-supervised learning [28 29 30 31. Balcan et al. 14] recently introduced a novel approach to tuning regularization parameters in regularized linear regression models, such Elastic Net and its variants. They applied data-driven analysis reveal the underlying discrete structure of the problem and leveraged a general result from 33 to obtain an upper bound on the pseudo-dimension of the problem. To provably tune the regularization parameters across problem instances, they proposed simple ERM learner and provided sample complexity guarantee for such learner. However, the general techniques from [32] do not always lead optimal bounds on the pseudodimension. Our paper is an example of problem where these bounds (as derived in (14) are sub-optimal, and more specialized techniques due [1 result in the tighter bounds that we obtain. Also prior work does not establish any lower bound on the pseudodimension. Furthermore, it should be noted that their analysis heavily relies on the assumption of having a closed-font representation of the Elastic Net estimator [27]. This approach may not be applicable in analyzing other regularized linear models, such as regularized logistic regression, for which we propose an alternative approach.
Problem setting
In this section, we provide a formal definition of the problem of tuning regularization parameters in the Elastic Net and regularized logistic regression (RLR) across multiple problem instances, which follows the settings by Balcan et al. [14]. Given problem instance P (X, X Vval). where (X, E mpxp y" represents the training dataset with m samples and p fcatures, and (Xeat: Dval) E Rmm xP x yrm denotes the validation split with m' samples, we consider the estimator ((x,)) (A) defined as:
B(x.v) (A) E argmin 1(3, (X, v)) + (A, R(3)), BERP
where 1(8, (X, y)) represents the objective loss function, À denotes the regularization coefficients, and R(3) [1].3 11, [1 represents the regularization vector function.
For instance, À E 2 y = R, and 1(B, (X, y)) LEN (B, (X, + 1 we get the well- Elastic Net. On the other hand, if X E ((), 0), (0, X2) for X1 0, y E {=1)m. and 1(3, (X, IRIR (8, (X,))) or & regularization. Note that for the Flastic Net hyperparameter tuning problem, we allows the regularization coefficients of both é,, lg are positive, while in the Regularized Logistic Regression
E log(1 + exp(- (8)) we obtain RLR with L

---

problem, we consider either & or E2 as the regularization term. We then use the validation set va Uval) to calculate the validation loss h(,, P) = (() (A), (Xaa,, (va))) corresponding to the problem instance P and learned regularization parameters X.
In the data-driven setting. we receive collection of problem instances p(o) (x(1), ,y(0) (1 Yeal) E Rm..g.m: for i E [n], where Rmi.pi,nn == I Xp: x) x RP' xymi The problem space 1mm.p is given by Um, Um, 20. Sp Smpmm.p..m. and we assume that problem instance P is drawn i.dd from the problem distribution over Hm... Remarkably, in this setting, problem instances can have varying training and validation sample sizes, well different sets of features. This general framework applies to practical scenarios where the feature sets differ among instances and allows one to learn regularization parameters that effectively work on average across multiple different but related problem instances. See Figure | for an illustration of the setting.
The goal here is to learn the value À s.t. with high probability over the draw of n problem instances, the expected validation loss EppDhh(A (A, P) is close to miny EP-D [A, P)]- This paper primarily focuses on providing learning guarantees in terms of sample complexity for the problem of tuning regularization parameters in the Elastic Net and regularized logistic regression (RLR). Specifically, we aim to address the question of how many problem instances are required learn value of À that per- forms well across all problems P drawn from the problem distribution D. To achieve this, we analyze the pseudo-dimension (in the case of the Elastic Nec) or the Rademacher Complexity (for RLR) of the validation loss function class H {h(2,) -) À E AJ, where A represents the search space for X.
3 Tight pseudo-dimension bounds for Elastic Net hyperparameter tuning
In this section, we will present our results on the pseudo-dimension upper and lower bounds for the regularized linear regression problem in the data-driven setting. Classic Gaaming-thhoretic results [33 34 connect the pseudo-dimension of the validation loss function class (parameterized by the regularization coefficient) with the sample complexity of the number of problem instances (P(1), p(m)) drawn i.i.d. from some unknown problem distribution DD needed for learning good regularization parameters with high confidence, Let hEN (A, P) = 1EN (3) (3(xx.)) (A), (X Iva)) ) be the validation loss function of the Elastic Net, and HEN {MEN A P) Im.. - Rxo X E IR3,0) be the corresponding validation loss function class, we now present tight bounds for Pdim(HEN).
3.1 The Goldberg-Jerrum framework
Recently, Bartlett et al. 33 instantiate a simplified version of the well-known Goldberg-Jerrum (GJ) Framework [17). The GJ framework offers general pseudo-dimension upperbound for wide class of functions in which each function can be computed by GJ algorithm. We provide a brief overview of the GJ Framework which is useful in establishing our improved pseudo-dimension upper bound. Definition 1 (GJ Algorithm, (II). A GJ algorithm I operates on real-valued inputs, and can perform two types of operations:
x, x, and Arithmetic operators of the form v" = O v', where O E (+, [,,,,,,,,+
Conniiionnal statements of the form "if 2 0... .l."..... "
In both cases, and v' are either inputs or values previously computed by the algorithm.
General speaking. each intermediate value of the GJ algorithm I' can be described by a rational function, which is fractional between two polynomials, of the algorithm's 's inputs. The degree of a rational function equal to the maximum degree of the polynomials in its numerator and its denominator. We can define two quantities that represent the complexity of GJ algorithms.
Definition 2 (Complexity of GJ algorithm, (3I].. The degree of a GJ algorithun is the maximum degree of any rational function it computes of the inputs. The predicate complexity of a GJ algorithm the number of distinct rational functions that appear in its conditional statements.
The following theorem essentially shows that for any function class F. if we can describe any function ʃ E F by a GJ algorithm of which the degree and predicate complexity are at most and A. respectively, then we can automatically obtain the upper bound for the pscudo secudo-dimension of F.

---

Theorem 3.1 (3I.). Suppose that each function f E F is specified by real parameters. Suppose that for every x E and E. there is a GJ algorithm Fzr that given f E J, returns "true" " if f(x) 2 and "false" otherwise. Assume that T zgr has degree A and predicate complexity A. Then, Pd) Om log(AA))
3.2 Upper bound
Our work improves on prior research 14] by presenting an upper bound on the pseudo-dimension of Elastic Net validation loss function class HEN parameterized by X. We extend the previous seceewis-ddccoposalee structure of the loss function by providing a bound on the number of distinct rational piece functions for any fixed problem instance (Definition 3). This allows us to use a GJ algorithm and Theorem 3.1 to obtain better bounds on the number of distinct predicates that need to be computed. While prior research only used a bound on the number of distinct loss function pieces generated by algebraic boundaries, our new observation that the loss function has a limited number of possible distinct functional behaviors yields a tighter upper bound on the pseudo-dimension (Theorem 3.2). In Theorem 3.5 we will demonstrate the tightness of our upper bound by providing a novel lower bound for the problem.
We first provide refinement of the piece-wise decomposable function class terminology introduced by [22 which useful for establishing our improved upper bound. Intuitively, this corresponds to real-valued functions for which the domain is partitioned by finitely many boundary functions such that the function is cell-behaved each piece in the partition, i.e. can be computed using a piece function from another function class.
Tildir A2)
f1(A)
f2(4)
M
F2(A)
fa(A)
(s(A)
Tappp A2) =
>
An illustration of piece-wise structure of H (hpp HEN R2 P E II mm.p) Given problem instance P, the function (A) = M(P;(PPP A) a fixed rational function f((A) each piece (piece function), that is regulated by boundary functions I., of the form 1 (A;(A) < 0). As mentioned in our main result, there are at most 3 functions ft of degree at most 2p, and at most p3" functions Dr, where T; is polynomial of degree most p.
Figure 2:
Definition 3. A function class H. S RY that maps a domain Y to IR is (F, kF, k.kg) wise decomposable for a class G of boundary functions and class E RD of piece functions if the following holds: for every h E H. (1) there are kg functions (1) g(k)) E G and function Sb E F for each bit vector b E (0, 13 s.t. for all E y, hly) ha, (v) where by = (v).,, (ko) (1))} E {0, 130,, and (2) there is at most ky different functions in F.
A key distinction from 332 is the finite bound k-= on the number of different piece functions needed define any function in the class H. Under this definition we give the following more refined structure for the Elastic Net loss function class by extending arguments from 14].
Theorem 3.2. Let H.N = {AEN(A..-) Imm.p + Rzo A E RZ be the class of Elastic Net validation loss function class. Consider the dual class Hix = (hi : HEN -> Ro P. mm..). where hep (hpxxx(> -)) = (A, P). Then Hix is (F,3.. -"_
decomposable, where the piece function class F (fg HEN >> mK} consists at most 3 rational functions fan.gp hhg((,,)
q ai())d2)) of degree at most 2p, and the boundary function class G = {gr HEN {0, 1}} consists
5

---

of semi semi-algebraic sets bounded by at most p3" algebraic curves 9r hav(),-) + ((r(A1, < 0}, where a polynomial of degree at most p.
Figure 2 demonstrates the piece-wise structure of HEN which allows us to establish an improved upper bound on the pseudo-dimension.
Theorem 3.3. Let HEN = (/gg((A,) 11 + R20 | E E Ro0 be the Elastic Net validation loss function class that maps problem instance P to validation loss (vat( P). Then Pdim(HEN) O(p).
Proof Sketch. For every problem instance E Imm.p. and a threshold r E IR, consider the computation {/EN (x, P) - 0} for any h E HEN. From Theorem 3.2 (A, P) r 2 0} as a GJ algorithm [p, which specified by 2 parameters λ1 X2, has degree of at most 2p, and has predicate complexity of at most (p + 1)3" (See Figure 3). Then Theorem 3.1
describe
implies that Pdim(HEN) = O(p).
Ps) <?
True
Fatse
Py(Ass <00
Ag(A < o2
(x,(As. <
As) As) < 07
True
Faloo
True
Falso
AA) + 2
-
(M + 0?
As(An -
False
False
Figure 3: An illustration of how 1(hhx(A, P) 0} computed as a GJ algorithm. The number of boundary (polynomial) functions kig is at most p33, and there are at most M = 3" distinct (rational) piece functions. All the polynomial and rational functions are of degree most 2p.
The detailed proof of Theorem 3.3 can be found on Appendix B.1.2 Recent work by Balcan et al. 14] also studied the Elastic Net, and showed the piece-wise structure of the dual function of the validation loss function which implies
upper bound of Opp²) by employing the general tool from We establish a tighter bound of Opp) in Theorem 3.3 by establishing additional properties of the loss function class and giving GJ algorithm for computing the loss functions.
32
To guarantee the boundedness of the considered validation loss function classes, will have the following assumptions for the data and regularization parameters. The first assumption is that all features and target values in the training and validation examples are bounded, The second assumption is that we only consider regularization coefficient values À within an interval [Amin Amax]. In practice, those assumptions are naturally satisfied by data normalization.
Assumption 1 (Bounded covariate and label). We assume that all the feature vectors and tar- get values in training and validation set is upper-bounded by absolute constants R₁ and R2, i.e. max{1] |lo ||x < R1, and max maxxlllyllc || //aaalloc I R2.
Assumption 2 (Bounded Coefficient). We assume that X E [Amins Amax]] with Amin > 0.
Under Assumptions 2 Theorem 3.3 immediately implies the following generalization guarantee for Elastic Net hyperparameter tuning.
Theorem 3.4. Let 'D be an arbitrary distribution over the problem instance space Tyn.g Under Assumptions 7 2 the loss functions in HEN have range bounded by some constant H (Lemma H² (p
log()))) sample problem instances drawn from DD the algorithm outputs a regularization parameter & such that with probability at least 8, EpEphen P) < miny E Ep P) +
C.1. Then there exists algorithm s.t. for any e, > O, given N = 0
Proof. Denote X argmin, EPEDREN (A, P). From Theorems 3.3 and A.2 given 0 0 (p log(}) ( problem instances p(0) for E [N] drawn from D, w.p. 5, we have E. EP (2, P)
H2
N Dí=1 EN (A, + < EN hEN p(() + (E* +

---

3.3 Lower bound
Remarkably, we are able establish a matching lower bound on the pseudo-dimension of the Elastic Net loss function class, parameterized by the regularization parameters. Note that every Elastic Net problem can be converted to an equivalent LASSO problem [T. In fact, we show something stronger, that the pseudo-dimension of even the LASSO regression loss function class (parameterized by regression coefficient X1) is St(p), from which the above observation follows (by taking 22 = 0 in our construction). Our proof of the lower bound adapts the "adversarial strategy" of [35] which used to design a worst-case LASSO regularization path. While [35) construct a single dataset to bound the number of segments in the piecewise-linear LASSO solution path, we create a collection of problem instances for which all above- below sign patterns may be achieved by selecting regularization parameters from different segments of the solution path.
Theorem 3.5.
Let HLASSO be set of functions {hLASSO(A,)) -) -mm.p Rzo X } that map a regression problem instance P E 1mm to the validation loss hA P) of LASSO trained with regularization parameter X. Then Pdim(HHasae) is a(p)..
p problem instances for LASSO regression given by val (1) ). where the training set ( = (X*, y²) is fixed and set using the "adversarial strategy" of (35), Proposition 2. The validation sets given by single examples (x(() (.())) = (c,, 0), where c; are standard basis vectors in R We will now proceed to provide the witnesses r IN and À values to exhibit a pseudo-shattering of these problem instances.
Proof Sketch. Consider N
p(() (x()), y((), x
Corresponding subset T [p] of problem instances, we will provide value of \y such that, have (ASSO (y, p()) r; iff T, for each i [p] and each T S [p]. We set all witnesses ri = O for all E [p]. As consequence of Theorem 1 in [35], the regularization path of (X*, y²) consists of a linear segment corresponding all 2 unsigned sparsity patterns in {0, 13.² (we will not need all the segments in the construction, but note that it is guaranteed to contain all distinct unsigned sparsity patterns) and we select \T as any interior point corresponding to linear segment with sparsity pattern {(c1,.... Cp) | = 0 iff i E T), i.e. elements in T are exactly the ones with sparsity pattern O. Therefore, 187 e parameter Åy. This implies the desired shattering condition w.r.t. witnesses = O,...,TN = 0. Therefore, Pdim(PLAAssO) 2 p. See Appendix B.2 for full proof.
iff T. where $7 is the LASSO regression fit for regularization
3.4 Hyperparameter tuning in Regularized Kernel Regression
The Kernel Least Squares Regression 4 is natural generalization of the linear regression problem, which uses kernel to handle non-linearity. In this problem. each sample has p1 feature, corresponding to real-valued target. Formally, each problem instance P drawn from II can be described as
P= (X, y, Xval, Mval) E TR x R x TR xp: x Rmmm
common issue in practice is that the relation between y and X is non-linear in the original space. To overcome this issue, consider the mapping R - R which maps the original input space to a new feature space in which we hopefully can perform linear regression. Define <(X) (0(x1.. ..., (f xmpp our goal is find vector E TRP2 that the squared loss Ily - o( x x012 2 + R([[O]]) minimized, where the regularization term R[[[@]] is any strictly mono- tonically increasing function of the Hilbert space norm. It is well-known from the literature (e.g. (36)) that under the Representer Theorem's 's conditions, the optimal value 0* can be linearly represented by row vectors of o(X), i.e., 0 = o(X)3 Σ (2, where 3 = (81 ($1...., ,,,)) E R". This directly includes the &g regularizer but does not include & regularization. To overcome this issue, Roth ((3) proposed an alternative approach to regularized kernel regression. which directly restricts the representation of coefficient / via a linear combination of ((x;)) for E [m)] The regularized kernel regression hence can be formulated as
3(xa) = argmin 1 BERm 2
lly - K311 + A || + A 11311
where k(xx,²) (0(x), 4(x')) the kernel mapping, and the Gram matrix K satisfies [K]k k(x,, for all i [m].
7

---

Clearly, the problem above is a linear regression problem. Formally, denote (A, P) b - K (A)ll2 and let HKER ( .) mm Rzo E R The following result
is a direct corollary of Theorem 3.3 which gives an upper bound for the pseudo-dimensiog of HXER-
Corollary 3.6. Pdim (HKER) (m))
Note that here denotes the training set size for single problem instance, and Corollary 3.6 implies a guarantee on the number of problem instances needed for learning a good regularization parameter Our results do not make any assumptions the m samples within a problem instance/dataset; if these samples within problem instances are further assumed to be i.i.d. draws from some data distribution (distinct from problem distribution D), then well-known results imply that m = O(k logp) samples are sufficient to learn the optimal LASSO where denotes the number of non-zero coefficients in the optimal regression fit.
for kernel regression via classic results [33 [
coefficient 37 38,
Hyperparameter tuning for Regularized Logistic Regression
Logistic regression is more naturally suited to applications modeling probability of an event, like medical risk for a patient (39, predicting behavior in markets [40), failure probability of an engineering system [41] and many more applications [42]. It is a fundamental statis- tical technique for classification, and regularization is again crucial for avoiding overfitting and estimating variable importance. In this section, we will present learning guarantees for tuning the Regularized Logistic Regression (RLR) regularization coefficients across in- stances. Given a problem instance P drawn from a problem distribution D over II, let hRLR (A, P) = ( (A), (X )vai)) be the RLR validation loss function class (defined in Sec- tion 2. and let HRIR = {RRIR R (A,-) :) Im,p - R20 | À E R be the RLR validation loss function class, our goal is provide learning guarantee for HRLR. Besides,
also study the commonly used 0-1 validation loss function class HRLR = { (A, :) : Imm.p - Rz0 A E Ryo]. where
1.1-1 (A, P) 1 Em' 1 (y (A) S 0). which will cover in Section 4.3 Similarly, to
guarantee the boundedness of HRLR. we also assume that Assumptions I and 2 also hold in this setting,
4.1
Approximate solutions of Regularized Logistic Regression
The main challenge in analyzing the regularized logistic regression, unlike the regularized logistic regression problem, that the solution xxx,y) corresponding to problem instance P and particular value À >> 0 does not have a closed form depending A. We then propose alternative approach to this end, which examining via the approximation 3(6) (x..)) (A) of the solution ((x,,) (A).
Algorithm 1 Approximate incremental quadratic algorithm for RLR with & penalty, 22
Set 58(²) = 3/xx,) (Amin) ). t f= 0, small constant E Ryu, and A = { [3
(xxxx) x) (Amin)) + 0}.
while \ < Amax do
A--1 = d1 +
(
(8(0) - V22 -
(110) (x.8) 1-1 (B80)((..))) + det1 sgn (3!0)
A
[8(c)
=
[+] -A
A AU (j + A|V((3(()
1413 (1(B))))(X,))) > A411}
(X,x))
A AV {j E
|
< <0}
1=t+1
The approximation Algorithm (Algorithm for the solution ((A) of RLR under & (or f2) Given a problem instance P, and a sufficiently small 2 yields approximation 3/c)
constraint were first proposed by Rosset 26 2
(X.y) of (xxx))) that are piece- linear functions of in total (Amax Amin)/c [26]. Moreover, it is also guaranteed that the error between a(c) and ((x,)) is uniformly upper bounded for all X E [Amin: Amax).
step-size >> O, using Algorithms
(x,))
8

---

Algorithm 2 Approximate incremental quadratic algorithm for RLR with & penalty,
Set 860) ((),)) (Xmi))) O.
while X mmxx do
A-1 = x te
g (A) B.60) - V ,x,,((,))) + 21 Vi (x.0() + 22
1=t+1
Theorem 4.1 (Theorem 1, (2 Given problem instance P. for small enough c, there is uniform bound () on the error (x(( (A) 3(0) (X.x) (2) for any X E [Amin, Amax).
Denote MigR (A, RRR [8 (A), (Aval, Mval)) the approximation function of the validation loss (RLR(A, P). Using Theorem 4.1 and note that the loss f(=) log(1+e is 1-Lipschitz, we can show that the difference between h (A, P) and hRLR (A, P) is uniformly upper-bounded.
Lemma 4.2. The approximation error of the validation loss function is uniformly upper-bounded | P) h,ux(>, P)| = =(e)), for all E [Amius Amax].
We now present one of our main results, which is the ggeudo-dimensee bound of the approximate validation loss function class HRLRR
Theorem 4.3. Consider the RLR under & (or Ez) constraint with parameter E [Amius Amaxk that take a problem instance P drawn from an unknown problem distribution D over 1m Under Assumptions and 2 HRLR is bounded by some constant H (Lemma C.2) Suppose that we use Algorithm (or Algorithm 2 approximate the solution ((x (A) by (xx (A) with uniform error ((e²) for any X E [Amin; Amax], where is the approximation step-size. Consider the approximation validation loss function class H((e) (hkile (X,
-): Im Rz0 X [Amiuy Amaxl) }, where
m
HRLR (A. (A. P)
1 m
log(1 + exp( Hap(-1o y:o g(() ((x (xxx) (A)))
is the approximate validation loss. Then we have Pdim Pdim(Hkkee) O(m² + log(1/C) Further, we assume that O(vH) where H is the upperbound of HALR under Assumptions and 2 Given any set S of T problem instances drawn from a problem distribution DD over 11m.p. the empirical Rademacher complexity S (HH))) S) O(H ((m² log(1/e))/T).
The key observation here is that the approximation solution ((.y)) is piece-wise linear over (Amax - Amin)/ //e pieces, leading to the fact that the approximate validation loss function li (A, .) is a "special function" (Pfaffian function (43) in each piece, which is combination of exponentiation of linear functions of A. The detailed proof of Theorem 4.3 can be found on the Appendix D.3
4.2 Learning guarantees for Regularized Logistic Regression hyperparameter tuning
Our goal now is use the upper bound for empirical Rademacher complexity of the validation loss function class HRLR- We use techniques for approximate data-driven algorithm design due to combining the uniform error upper bound between validation loss function hRLR (A, P) and its approximation RLR (X, P) (Lemma 4.2 and empirical Rademacher complexity of approximation validation loss function class H(L) (Theorem 4.3), to obtain a bound on the empirical Rademacher complexity of HRLR. This allows us to give learning guarantee for the regularization parameters X, which formalized by the following theorem.
29
Theorem 4.4. Consider the RLR under & (or Ea) constraint. Under Assumptions 7 bounded by some constant H (Lemma C.2 Consider the class function HALR P (2.
HALR is
1mm + Rx0 X DAmin Amax] where h (X, P)) is the validation loss corresponding to problem

---

instance P and the E (l2) parameter X. Given any set S of I problem instances drawn from problem distribution D over gm for any (A, E HAIR. w.p. 1 for any ò (0, 1), we have
so H
m² log(1/e) + VV
1 7
1
(A p(O) (ERDD PJ]
log
for some sufficiently small E.
The proof detail of Theorem i. included in the Appendix [.3] The above generalization guarantee gives a bound on the average error on RLR validation loss over the problem distribution, for the parameter learned from T problem instances. In commonly used approaches, the validation set size is small or a constant, and our result can be interpreted as the upper bound on the generalization error in terms of the number of problem instances 7 and the step length e. We only consider RLR under & (or f2) constraints, which are commonly studied in the literature, our analysis could be easily extended RLR under Ey constraint for any 2 1.
4.3 An extension to 0-1 loss
Since logistic regression is often used for binary classification tasks, it is interesting consider the 0-1 loss as the validation loss function. It has been shown that 1(z S 0} S 4log(1 + +-) for any
44
This inequality, combined with Theorem 4.4 directly provides learning guarantee for the
0-1 validation loss function.
Theorem 4.5. Let T > 262 and E 10, where c is the approximation step-size. Then for any n 2 STT/2,6) = 2 H² (m +mog 1)+log )). if we have n problem instances (p(t), (p(i)....,,P p(n)), drawn (r/2-
ii.d. from some problem distribution D over 1m, to learn the regularization parameter X ,ERM for RLR via ERM, then
EpaD
(104 (X ERM PI)) < RIR
min XE Aemininn
Ep-D P)) 4T.
The detailed proof of Theorem 4.5 can be found on Appendix D.4 It is worth noting that we are providing learning guarantee for 0-1 validation loss function class H-RLR indirectly via the validation loss function class HRLR with cross-entrops objective function, which is arguably not optimal. The question of how to provide true PAC-learnable guarantee for H remains interesting challenge.
Conclusion and future work
In this work, we present novel learning guarantees for tuming regularization parameters for both the Elastic Net and Regularized Logistic Regression models, across problem instances. For the Elastic Net, we propose fine-grained structural results that pertain to the tuning of regularization parameters. We use them to give improved upper bound the pseudo-dimensee of the relevant validation loss function class of and we prove that our new bound is tight.
For the problem of tuning regularization parameters in regularized logistic regression, propose an alternative approach that involves analyzing the approximation of the original validation loss function class. This approximation, characterized by piece-wise linear representation, provides useful analytical tool in the absence an exact dependence of the logistic loss on the regularization parameters. Additionally, we employ upper bound on the approximation error between the original and approximated functions, to obtain a learning guarantee for the original validation loss function class. Remarkably, our proposed approach is not restricted solely to regularized logistic regression but can be extended to wide range of other problems, demonstrating its generality and applicability.
It is worth noting that this work only focuses on the sample complexity aspect of the hyperparameter tuning in the Elastic Net and Regularized Logistic Regression. The question of computational complexity in this setting is an interesting future direction. Other interesting questions include designing hyperparameter tuning techniques for this setting that are robust to adversarial attacks, and hyperparameter tuning for Regularized Logistic Regression with both e and &g constraints.
10

---

Acknowledgement
We thank Yingyu Liang for useful discussions during early stages of this work and Mikhail Khodak for helpful feedback. This work was supported in part by NSF grants CCF-1910321 and SES-1919453, the Defense Advanced Research Projects Agency under cooperative agreement HR00112020003, and Simons Investigator Award.
References
[1] Hui Zou and Trevor Hastie. Regularization and variable selection via the Elastic Net. Journal of the Royal Statistical Society: Series (Statistical Methodology), 6712)301-330, 2005.
[2] Saharon Rosset. Following curved regularized optimization solution paths. Advances in Neural Information Processing Systems, 17, 2004.
[3] Volker Roth. The generalized LASSO. IEEE transactions on neural networks, 15(1):16-28, 2004.
[4] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[5] Arthur Hoerl and Robert Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55-67, 1970.
[6] Robert Tibshirani. Regression shrinkage and selection via the LASSO. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[7] Martin Wainwright. High-dimensional statistics; non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[8] Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-277 2018.
[9] Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[10] Gang Wang, Dit-Yan Yeung, and Frederick H Lochovsky. The kernel path in kernelized LASSO. In Artificial Intelligence and Statistics, pages 580-587. PMLR, 2007.
[11] Yunlong Feng, Shao-Gao Lv, Hanyuan Hang, and Johan Suykens. Kernelized Elastic Net regular- ization: generalization bounds, and sparse recovery. Neural computation, 28(3):525-562, 2016.
[12] Kevin P Murphy. Machine learning: probabilistic perspective. MIT press, 2012.
[13] Tong Zhang. Some sharp performance bounds for least squares regression with L1 regularization. The Annals of Statistics, pages 2109-21433 2009.
[14] Maria-Florima Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the Elastic Net across instances. In Advances in Neural Information Processing Systems, 2022.
[15] Rich Caruana. Multitask leamiin. Machine learning, 28:41-75, 1997.
[16) Mervyn Stone. Cross-validation: A review. Statistics: A Journal of Theoretical and Applied Statistics, 11):127-13, 1978.
[17] Paul Goldberg and Mark Jerrum. Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. In Proceedings of the sixth annual conference Computational learning theory, pages 361-369, 1993.
[18] Li Wang, Michael D Gordon, and Ji Zhu. Regularized least absolute deviations regression and an efficient algorithm for parameter tuning. Sixth International Conference on Data Mining (ICDM'06 '06), pages 690-700. IEEE, 2006.

---

[19] Denny Wu and Ji Xu. On the optimal weighted L2 regularization in overparameteriized linear regression, Advances in Neural Information Processing Systems, 33:10112-10123, 2020.
[20] Diane Galarneau Gibbons. A simulation study of some ridge estimators. Journal of the American Statistical Association, 766373):111-13,, 1981.
[21] 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.
[22] Yosiyuki Sakamoto, Makio Ishiguro, and Genshiro Kitagawa. Akaike information criterion statisties. Dordrecht, The Netherlands: D. Reidel, 8 81110.5555):2685, 1986.
[23] Gideon Schwarz. Estimating the dimension a model. The annals of statistics, pages 461-464, 1978.
[24] Michael Chichignoud, Johannes Lederer, and Martin Wainwright. A practical scheme and fast algorithm tune the LASSO with optimality guarantees. The Journal of Machine Learning Research, 17(1):8162 16--8181, 2016.
[25] Denis Chetverikov, Zhipeng Liao, and Victor Chernozhukov. On cross-validated LASSO in high dimensions. The Annals of Statistics, 4900):1300-1317, 2021.
[26] Saharon Rosset. Topics in regularization and boosting. PhD thesis, Stanford University, 2003.
[27] Ryan Tibshirani. The LASSO problem and uniqueness. Electronic Journal of Statistics, 7:1456-1490, 2013.
[28] Rishi Gupta and Tim Roughgarden. A PAC approach to pepiication-speciffe algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 123-134, 2016.
[29] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik, Refined bounds for algorithm configuration: The knife-edge of dual class approximability. In International Conference on Machine Learning, pages 580-590. PMLR, 2020.
[30] Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts. Advances in Neural Information Processing Systems, 35:33890-33903, 2022.
[31] Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference Learning Theory, pages 2013 2040. PMLR, 2022.
[32] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn perfhrmeformin algorithms? Generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 919-932, 2021.
[33] Martin Anthony and Peter Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, USA, 1st edition, 2009.
[34] Maria-Florina Balcan. Book chapter Data-Driven Algorithm Design. In Beyond Worst Case Analysis of Algorithms, T. Roughgarden (Ed). Cambridge University Press, 2020.
[35] Julien Mairal and Bin Yu. Complexity analysis of the LASSO regularization path. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages
2012.
[36] Bernhard Schölkopf, Ralf Herbrich, and Alex Smola. generalized representer theorem. In Computational Learning Theory: 14th Annual Conference Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, FuroCOL.T200 Amsterdam, The Netherlands, July 16 19, 2001 Proceedings 14, pages 416-426. Springer, 2001.
12

---

[37] Martin Wainwright, Information- theoretic bounds on sparsity recovery in the high-dimensionn and noisy setting. In 2007 IEEE International Symposium on Information Theory, pages 961-965. IEFE, 2007.
[38] Martin Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using LI-constrained quadratic programming (LASSO). IEEE transactions on information theory, 55(5):2183-222 2009.
[39] Peter Armitage, Geoffrey Berry, and John Nigel Scott Matthews. Statistical methods in medical research. John Wiley & Sons, 2008.
[40] Michael JA Berry and Gordon S Linoff. Data mining techniques: for marketing, sales, and customer relationship management. John Wiley & Sons, 2004.
[41] Sanjay Kumar Palei and Samir Kumar Das. Logistic regression model for prediction of roof fall risks in bord and pillar workings in coal mines: approach. Safety science, 47(1):88 11:8-18888,.. 96, 2009.
[42] David W Hosmer Jr, Stanley Lemeshow, and Rodney X Sturdivant. Applied logistic regression, volume 398. John Wiley & Sons, 2013.
[43] Askold G Khovanski. Fewnomials, volume 88. American Mathematical Soc., 1991.
[44] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
[45] Richard M Dudley. Universal, Donsker classes and metric entropy. The Annals of Probability. 1306-13666 1987.
13


Reviews:
[{"review_id": "bvbJyBc8ab", "reviewer": "Reviewer_be6e", "summary": "This paper studies the sample complexity of tuning regularization parameters in linear and logistic regressions under $\\ell_1$ and $\\ell_2$ constraints in the data-driven setting. Theoretically, it provides a new bound for the pseudo-dimension of the validation loss function class, which significantly improves the best-known results on the problem. Besides, it provides the matching lower bound. Moreover, it also provides a new bound for tuning the regularization parameters of logistic regression, which previous work cannot do.", "questions": "None", "limitations": "Please see the weakness part.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "First of all, I have to admit that I am not an expert in the area of data-driven algorithm design and may miss some related work. Overall, I think this is a solid theoretical work.\n\n- Overall, this paper is well-written and discussions about the comparisons with the related work are clear.\n- The considered problem (e.g., hyperparameter tuning or model selection) is important for the machine learning community. \n- The theoretical results seem right although I have not carefully checked the proofs line-by-line.\n- Theoretically, the obtained upper bound is tight since the (nearly) matched lower bound is provided.\n- In contrast with previous work, it is good to provide the analysis for the logistic regression as it might provide techniques to analyze more general settings with non-closed solution forms.", "weaknesses": "- Although this is a pure theory work, it would be better to add experimental results to illustrate its applications in practice.\n- While the considered setting is the hyperparameter tuning across instances, more discussions can be added to illustrate its practicality over previous work with a single instance.\n\n\n\nMinor issues:\n\ntypos：\n- In lines 503-507 (i.e., Lemma A.1), it is not consistent about the expression of non-increasing (or decreasing) and non-decreasing (or increasing).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments, and for appreciating the theoretical contributions of our work.\n\n\n**Typos in Lines 503-507**: Thank you for pointing out. We will fix the typos in the revised manuscript.\n\n\n**Concerning practicality over single instance work**: In most applications, one needs to solve multiple instances of a regression problem repeatedly, and doing a multi-fold cross-validation on each problem instance can be computationally expensive, Furthermore, collecting all the problem instances to build a single super-instance may not work as examples across instances may not be i.i.d., and moreover may be infeasible to compute as well. We will emphasize this difference in the camera-ready version of the paper.\n"}, {"review_id": "zfn0kvCaBG", "reviewer": "Reviewer_QofD", "summary": "The main idea of this paper is to address the challenge of tuning regularization coefficients in regression models with provable guarantees across problem instances. The authors investigate the sample complexity of tuning regularization parameters in linear and logistic regressions under l1 and l2 constraints in the data-driven setting. They provide new upper bounds for the pseudo-dimension of the validation loss function class, which significantly improves the existing results on the problem. Additionally, the paper introduces a new approach for studying the learning guarantee in logistic regression regularization coefficients. Overall, the paper aims to contribute to the literature by providing improved bounds and advancements in the field of hyperparameter tuning for regression problems.", "questions": "Is it possible to provide any experimental study?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Improved Bounds: One strength of this paper is that it provides improved upper bounds for the pseudo-dimension of the validation loss function class in linear and logistic regressions. These improved bounds contribute to a better understanding of the sample complexity of tuning regularization parameters in regression models.\n2. Generality and Applicability: The proposed approach for analyzing the approximation of the original validation loss function class is not limited to regularized logistic regression but can be extended to a wide range of other problems. This demonstrates the generality and applicability of the approach, making it a valuable contribution to the field.\n", "weaknesses": "1. Lack of Experimental Validation: The paper focuses on theoretical analysis and bounds but does not provide experimental validation or empirical results to support the proposed approach. Including experimental validation would have added practical relevance and strengthened the paper's findings by demonstrating the effectiveness of the approach in real-world scenarios.\n2. Lack of Clarity and Visual Support: One weakness of this paper is the insufficient clarity in explaining the problem it addresses. The excessive repetition of formulas and the absence of visual aids, such as graphs or charts, make it difficult for readers to understand the main ideas and practical implications of the research. The lengthy theoretical derivations, while comprehensive, may hinder the overall comprehension of the paper's intended message.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing constructive feedback.\n\n**Clarity and visual support**: We will take your comment into account for the camera-ready version. We already have a figure illustrating the computation of the GJ algorithm (Figure 1) and we are happy to use the additional page in the camera ready version to provide additional illustrations and figures explaining our setting.\n\n\n**Experimental Validation**: Our theory gives bounds on the sample complexity of the ERM and we view our primary contribution as theoretical – including tight bounds improving over previous best-known bounds, and analysis for logistic regression where no closed-form solution is known – we leave the extension of the ideas to practical methods in more application-oriented research for future work."}, {"review_id": "Uuyk917bMr", "reviewer": "Reviewer_aDmj", "summary": "The paper analyses the complexity of hypotheses classes where the hyperparameter of logistic regression and linear regression are tuned, in the setting where multiple datasets are available.", "questions": "see above", "limitations": "A challenge is to give a tighter PAC bound for the 01 loss for RLR", "rating": 7, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper derives tighter upperbounds for the elastic net setting and proves a matching lowerbound, which are extended to KRR, for the setting where regularization parameters are learned from problem instances (e.g. metalearning). The regularized logistic regression setting is tackled by approximating the function class.", "weaknesses": "1 While I am quite familiar with learning theory (e.g. VC bounds, PAC, pseudo-dimension) I really have a hard time grasping the problem setting. I had to consult [15] and [27] for that. I think the paper could be greatly improved by clarifying the problem setting in more detail, with some example settings machine learners will be familiar with. E.g. the example of cross validation of [15]. It would also be good to clarify generally what are the inputs to the learner; it is still a bit unclear to me. So are [X_train, y_train, X_test] the inputs? And the output is $\\lambda$? The strange thing is, is that the hypothesis seems to take $\\lambda$ as input (definition of h), while the $\\lambda$ seems the thing we want to learn. \n\n2 Furthermore, in line 124 it is stated \"the learning algorithm in this scenario has been mentioned in [15], which is based on simulated annealing\" this seems wrong, as the learner in that work [15] is operating in the online learning setting, while the current work seems more to focus on the statistical learning setting. Shouldn't instead be the ERM learner or CV learner of [15] be mentioned? \n\n3 Generally, I think more examples are necessary to grasp the main point of the setting. It would also be clear to further clarify why this is an important problem to study; for which learners can we now derive theoretical guarantees? \n\n4 Once I had clarified the setting I had no time to read the paper furthermore in detail, so I cannot judge the other aspects in more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback. We really appreciate that the reviewer acknowledges the contribution of our work and also thank them for their time understanding our work. We will take the reviewer’s comments into account for improving the readability of the paper and use the extra page in the camera-ready version to provide additional illustrations and discussion explaining our setting (see also, attached PDF).\n\n\n\n\n**Improving clarification of the setting**: We will include examples and illustrations to further clarify our setting. For simplicity, consider the LASSO regression problem: the inputs of the learner are problem instances $P$, which are specified by the tuple $P = (X, y, X\\_\\text{val}, y\\_\\text{val})$. Given a problem instance $P$ and a regularization parameter $\\lambda > 0$, we can define the loss function $h(P; \\lambda) = \\frac{1}{2} \\|\\|y\\_\\text{val} - X\\_\\text{val} \\hat{\\beta}\\|\\|\\_2^2$, where $\\hat{\\beta} = \\text{argmin}\\_{\\beta}\\frac{1}{2}\\|\\|y - X\\beta\\|\\|_2^2+\\lambda\\|\\|\\beta\\|\\|\\_1$, and our goal is to learn a good value $\\lambda$. So the hypothesis set is the family of regression algorithms $h(\\cdot; \\lambda)$ parameterized by $\\lambda$ (not taking a fixed $\\lambda$ as an input), and our goal is to learn a good value $\\lambda$ corresponding to a good regularization for typical problem instances $P$. We will emphasize and illustrate this point to clarify the setting in the revised draft. \n\n\n\n\nWe agree that including the example of cross-validation in [1] helps clarify the settings of this work and we will include it in the final version of the paper. In particular, $(X_\\text{val}, y_\\text{val})$ could correspond to validation splits from a fixed dataset to capture usual cross-validation. The setting of course is more general and captures multi-task learning as well where the goal is to learn a common hyperparameter that works well across related tasks.\n\n\n**Comparison with prior work [1]**: While [1] considers both the statistical learning setting and the online setting, we mainly focus on the statistical learning setting improving the results of [1] for the elastic net regression in this setting to obtain asymptotically tight bounds on the pseudo-dimension. We also consider logistic regression which involves technical novelty as no closed-form solution is known.\n\n\n**More discussion on the importance of this line of work**: the problem of tuning regularization parameters in regularized linear models has always been a fundamental issue: choosing inappropriate parameters might cause the model to underfit the data or impair the effect of regularization. In this work, we study a variant of the tuning regularization parameter problem, which involves tuning across multiple problem instances from the same underlying problem distribution. This setting is general and can handle practical scenarios, including the case where the feature set of the problem instances varies or when regression instances from the same domain need to be solved repeatedly. Hence, theoretical analysis for this problem is important and worth exploring.\n\n**Concern about the statement in Line 124**: Thank you for correcting this. It is true that the ERM learner should be mentioned instead. \n\n\nWe hope that our answers satisfy the reviewer. If any further clarification is required, please let us know. \n\n\n**References:**\n\n[1] Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar, Provably Tuning Elastic-Net Across Instances, NeurIPS’23.\n"}, {"review_id": "BGMWDVk7TK", "reviewer": "Reviewer_Ca6P", "summary": "The authors tackle the problem of hyperparameter tuning across problem instances, as proposed by Balcan et al. (2022). They propose three novel learning guarantees regarding the sample complexity of tuning regularization parameters: i) an improved upper bound on the pseudo-dimension for elastic net; ii) a matching lower bound in the same setting; iii) a bound on the pseudo-dimension and on the generalization error for logistic regression.", "questions": "1) Can the authors define formally the probability space used for the problems (Line 117)? It is a bit disturbing to manipulate objects of varying size.\n2) Should it be $h_{b_y}$ and $g^{(1)}(y)$ in Lines 183-184?", "limitations": "Limitations are not addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents new results, which either improve the state-of-the-art (i) or pave a new way (ii and iii) in analyzing common learning techniques. I think these results are topical and interesting for the community.", "weaknesses": "As an unschooled researcher regarding the theory of hyperparameter tuning across instances, I found the paper not that easy to read. I particular, I missed the target the authors aimed at (it is stated at the end), which would help me to understand. Here are some remarks which may help in improving the paper:\n1) Some elementary definitions are missing and curb the reader understanding (particularly the pseudo-dimension, the Rademacher complexity and the ERM principle in Theorem 4.5). Also, a comment for Theorem 3.1 would be appreciated. As for me, a simple improvement of the paper would be to state informally a kind of Theorem 4.4 at the beginning, such that the reader is more able to understand Sections 3 and 4.\n2) Minor comments: “optimization problem 1” should have capital letters, a “be” is missing Line 188, an “of” is missing Line 191, “an GJ algorithm” in the caption of Figure 1 should be “a GJ algorithm”, “Roth et al. ([3])” Line 251 should be “Roth [3]”, increasingness of $R(||\\theta||)$ would be better place before stating the representer expansion, the update of $\\beta_t^{(\\epsilon)}$ in Algorithm 1 should be stored in $\\beta_{t+1}^{(\\epsilon)}$ instead of $\\beta^{(\\epsilon)}(\\lambda)$, moreover it involves the difference of two vectors of different sizes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback and suggestions. We really appreciate that the reviewer acknowledges the theoretical contributions of our paper and we will address the reviewer’s concerns as below. In particular, we will state the target early on in the paper for improving clarity.\n\n\n**Typos in Lines 183-184, and minor comments**: thank you for pointing them out, we will fix those typos in the revised draft.\n\n\n**Additional comments for Theorem 3.1, and 4.4**: thank you for your suggestion. We will add comments and further discussion before the statements of those results in the revised draft for a better presentation. \n\n\n**Adding elementary definitions and results**: unfortunately, due to the space limitation, we could only add some of the elementary definitions in the Appendix (Appendix A). We will try our best to use the additional page in the camera-ready version to integrate the fundamental notions in the main body.\n\n\n**Concerns about varying sizes of problem instances**: nice catch! It is true that this setting allows the number of train ($m$) and validation ($m’$) samples in each problem instance $P$ to vary. It does not even require the feature set across the different problem instances is the same: different problem instances might have different feature sets or even different numbers of features. This makes the settings incredibly general and can handle feature reset, as mentioned in [1]. \n\nAs mentioned in our work, given a tuple $(m\\_i, m’\\_i, p\\_i)$ of number of train samples, number of validation samples, and number of features, we denote the set of problem instances of that shape $\\mathcal{R}\\_{m\\_i, m’\\_i, p\\_i}$. Assume that for any problem instance, the validation set can only take at most $m$ samples, and have at most $p$ features, the problem space can be defined as a finite union $\\Pi_{m,p} = \\cup_{m\\_1 \\geq 0, m\\_2 \\leq m, p\\_1 \\leq p}\\mathcal{R}\\_{m\\_1, m\\_2, p\\_1}$. Then, the problem distribution $\\mathcal{D}$ is simply some unknown distribution over $\\Pi_{m, p}$. We will elaborate on this point more carefully in the revised draft. \n\n\n**References:**\n\n[1] Maria-Florina Balcan, Mikhail Khodak, Dravyansh Sharma, Ameet Talwalkar. Provably Tuning Elastic-Net Across Instances. NeurIPS’23\n"}]

Author rebuttal:

We thank all the reviewers for their thoughtful comments and suggestions. We are glad that all of the reviewers appreciate our theoretical contribution. The main concerns are the clarity of the settings and more visual supports, which we aim to improve by providing figures describing key concepts of our work. We attached the figures in this rebuttal as a demonstration. 


Thank you again for your hard work and feel free to let us know if there is any other concern. 


Meta-review: This paper was generally well-received by the reviewers. The results were seen as novel and the problem studied was seen as important. Some reviewers (e.g QofD,aDmj ) raised concerns about the lack of experiments and reviewer (e.gaDmj,Ca6P
 ) raised on the clarity of the presentation and notably on the lack of basic definition and background given on the the mutlti dataset setting considered here. The camera ready version should  correct this and introduce some more formal remarks about the application to cross validation should as the datasets are assumed in section 2 to be sampled i.i.d. In summary a good work that passes the bar for publication at Neurips.
Decision: Accept (poster)